2 hours ago
1
Drone shows are an increasingly popular form of large-scale light display. These shows incorporate hundreds to thousands of airborne bots, each programmed to fly in paths that together form intricate shapes and patterns across the sky. When they go as planned, drone shows can be spectacular. But when one or more drones malfunction, as has happened recently in Florida, New York, and elsewhere, they can be a serious hazard to spectators on the ground.
Drone show accidents highlight the challenges of maintaining safety in what engineers call “multiagent systems” — systems of multiple coordinated, collaborative, and computer-programmed agents, such as robots, drones, and self-driving cars.
Now, a team of MIT engineers has developed a training method for multiagent systems that can guarantee their safe operation in crowded environments. The researchers found that once the method is used to train a small number of agents, the safety margins and controls learned by those agents can automatically scale to any larger number of agents, in a way that ensures the safety of the system as a whole.
In real-world demonstrations, the team trained a small number of palm-sized drones to safely carry out different objectives, from simultaneously switching positions midflight to landing on designated moving vehicles on the ground. In simulations, the researchers showed that the same programs, trained on a few drones, could be copied and scaled up to thousands of drones, enabling a large system of agents to safely accomplish the same tasks.
“This could be a standard for any application that requires a team of agents, such as warehouse robots, search-and-rescue drones, and self-driving cars,” says Chuchu Fan, associate professor of aeronautics and astronautics at MIT. “This provides a shield, or safety filter, saying each agent can continue with their mission, and we’ll tell you how to be safe.”
Fan and her colleagues report on their new method in a study appearing this month in the journal IEEE Transactions on Robotics. The study’s co-authors are MIT graduate students Songyuan Zhang and Oswin So as well as former MIT postdoc Kunal Garg, who is now an assistant professor at Arizona State University.
Mall margins
When engineers design for safety in any multiagent system, they typically have to consider the potential paths of every single agent with respect to every other agent in the system. This pair-wise path-planning is a time-consuming and computationally expensive process. And even then, safety is not guaranteed.
“In a drone show, each drone is given a specific trajectory — a set of waypoints and a set of times — and then they essentially close their eyes and follow the plan,” says Zhang, the study’s lead author. “Since they only know where they have to be and at what time, if there are unexpected things that happen, they don’t know how to adapt.”
The MIT team looked instead to develop a method to train a small number of agents to maneuver safely, in a way that could efficiently scale to any number of agents in the system. And, rather than plan specific paths for individual agents, the method would enable agents to continually map their safety margins, or boundaries beyond which they might be unsafe. An agent could then take any number of paths to accomplish its task, as long as it stays within its safety margins.
In some sense, the team says the method is similar to how humans intuitively navigate their surroundings.
“Say you’re in a really crowded shopping mall,” So explains. “You don’t care about anyone beyond the people who are in your immediate neighborhood, like the 5 meters surrounding you, in terms of getting around safely and not bumping into anyone. Our work takes a similar local approach.”
Safety barrier
In their new study, the team presents their method, GCBF+, which stands for “Graph Control Barrier Function.” A barrier function is a mathematical term used in robotics that calculates a sort of safety barrier, or a boundary beyond which an agent has a high probability of being unsafe. For any given agent, this safety zone can change moment to moment, as the agent moves among other agents that are themselves moving within the system.
When designers calculate barrier functions for any one agent in a multiagent system, they typically have to take into account the potential paths and interactions with every other agent in the system. Instead, the MIT team’s method calculates the safety zones of just a handful of agents, in a way that is accurate enough to represent the dynamics of many more agents in the system.
“Then we can sort of copy-paste this barrier function for every single agent, and then suddenly we have a graph of safety zones that works for any number of agents in the system,” So says.
To calculate an agent’s barrier function, the team’s method first takes into account an agent’s “sensing radius,” or how much of the surroundings an agent can observe, depending on its sensor capabilities. Just as in the shopping mall analogy, the researchers assume that the agent only cares about the agents that are within its sensing radius, in terms of keeping safe and avoiding collisions with those agents.
Then, using computer models that capture an agent’s particular mechanical capabilities and limits, the team simulates a “controller,” or a set of instructions for how the agent and a handful of similar agents should move around. They then run simulations of multiple agents moving along certain trajectories, and record whether and how they collide or otherwise interact.
“Once we have these trajectories, we can compute some laws that we want to minimize, like say, how many safety violations we have in the current controller,” Zhang says. “Then we update the controller to be safer.”
In this way, a controller can be programmed into actual agents, which would enable them to continually map their safety zone based on any other agents they can sense in their immediate surroundings, and then move within that safety zone to accomplish their task.
“Our controller is reactive,” Fan says. “We don’t preplan a path beforehand. Our controller is constantly taking in information about where an agent is going, what is its velocity, how fast other drones are going. It’s using all this information to come up with a plan on the fly and it’s replanning every time. So, if the situation changes, it’s always able to adapt to stay safe.”
The team demonstrated GCBF+ on a system of eight Crazyflies — lightweight, palm-sized quadrotor drones that they tasked with flying and switching positions in midair. If the drones were to do so by taking the straightest path, they would surely collide. But after training with the team’s method, the drones were able to make real-time adjustments to maneuver around each other, keeping within their respective safety zones, to successfully switch positions on the fly.
In similar fashion, the team tasked the drones with flying around, then landing on specific Turtlebots — wheeled robots with shell-like tops. The Turtlebots drove continuously around in a large circle, and the Crazyflies were able to avoid colliding with each other as they made their landings.
“Using our framework, we only need to give the drones their destinations instead of the whole collision-free trajectory, and the drones can figure out how to arrive at their destinations without collision themselves,” says Fan, who envisions the method could be applied to any multiagent system to guarantee its safety, including collision avoidance systems in drone shows, warehouse robots, autonomous driving vehicles, and drone delivery systems.
This work was partly supported by the U.S. National Science Foundation, MIT Lincoln Laboratory under the Safety in Aerobatic Flight Regimes (SAFR) program, and the Defence Science and Technology Agency of Singapore.
