Robust MADER: Decentralized Multiagent Drone Trajectory Planner

May 1, 2023

Massachusetts Institute of Technology, Cambridge, MA

Due to its wide range of applications, multiagent UAV trajectory planning has been extensively studied. For reliable real-world deployment, it is essential that a trajectory planner be robust to both communication delays and dynamic environments; however, achieving robustness to both communication delays and dynamic environments has not been addressed in the literature. Multiagent trajectory planners can be centralized (one machine plans every agent’s trajectory) or decentralized (each agent plans its own trajectory). Decentralized planners are more scalable and robust to failures of the centralized machine. Despite these advantages, a decentralized scheme requires communication between the agents, and communication delays could potentially introduce failure in the trajectory deconfliction between the agents. It is also worth noting that there are two layers of decentralization— decentralized planning and decentralized communication architecture. Even if the planning algorithm is decentralized, agents may still require a centralized communication architecture, such as Wi-Fi. Multiagent planners can also be classified according to whether or not they are asynchronous. Asynchronous planning enables each agent to independently trigger the planning step without considering the planning status of other agents. In contrast to synchronous planners, which require all agents to wait at a so-called synchronization barrier until planning can be globally triggered, asynchronous methods tend to be more scalable. They are, however, also more susceptible to communication delays since agents plan and execute trajectories independently.

Many state-of-the-art decentralized trajectory planners do not consider communication delays or explicitly state assumptions about communication. For example, SCP, decNS, and LSC are decentralized and synchronous, but SCP and decNS implicitly and LSC explicitly assume a perfect communication environment without any communication delays. The algorithm decMPC is decentralized, but it requires synchronicity and communication delays to be within a fixed planning period. EDG-Team is a decentralized semi-asynchronous planner, which solves joint optimization as a group. EDG-Team cooperatively tackles the path planning problem but implicitly assumes no communication delays.

ADPP is asynchronous1 and decentralized, but it assumes perfect communication without delay. Our previous work MADER is asynchronous and decentralized but assumes no communication delays. EGO-Swarm also proposes a decentralized, asynchronous planner that requires agents to periodically broadcast a trajectory at a fixed frequency, and each agent immediately performs collision checks upon receiving the message. EGO-Swarm is the first fully decentralized, asynchronous trajectory planner successfully demonstrating hardware experiments, yet it still suffers from collisions due to communication delays, as shown in Section III. AsyncBVC proposes an asynchronous decentralized trajectory planner that can guarantee safety even with communication delays. However, its future trajectories are constrained by past separating planes, which can over constrain the solution space and hence increase conservatism. Further, it relies on discretization when solving the optimization problem, meaning that safety is only guaranteed on the discretization points. Additionally, AsyncBVC was only tested in simulations, so its applicability in real-world hardware is unclear. In contrast, our approach instead is able to guarantee safety in a continuous approach by leveraging the MINVO basis.

Additionally, to achieve reliable real-world deployment, which involves not only static obstacles, but also dynamic obstacles, it is crucial to achieve robustness in dynamic environments. However, as seen in Table II, hardware demonstrations in dynamic environments have not been tested in the literature. For clarification, we define a dynamic environment as an environment with dynamic obstacles. The difference between an agent and an obstacle is that an agent can make decisions based on given information. An obstacle, on the other hand, simply follows a pre-determined trajectory regardless of what else is in the environment.

To address robustness to communication delays in dynamic environments, we propose Robust MADER (RMADER), a decentralized and asynchronous multiagent trajectory planner that is capable of generating collision-free trajectories in dynamic environments even in the presence of realistic communication delays. RMADER is the first approach to demonstrate trajectory planning in dynamic environments while maintaining robustness to communication delays.

This work was performed by Kota Kondo and Reinaldo Figueroa for the Massachusetts Institute of Technology. For more information, download the Technical Support Package (free white paper) here  under the Vehicles and Robotics category.

---

---

This Brief includes a Technical Support Package (TSP).

Robust MADER: Decentralized Multiagent Drone Trajectory Planner

(reference MIT-0623) is currently available for download from the TSP library.

LOGIN TO DOWNLOAD

Don't have an account? Sign up here.

---