Collaboration during high-speed motion may be essential for sensing and data gathering. In this case, vehicles must arrive at given waypoints all at the same time and avoid collisions with obstacles and each other; otherwise, they are free to choose their own trajectories.
Existing methods for multi-agent trajectory generation often rely on overly conservative constraints to reduce the complexity of this high-dimensional planning problem, leading to suboptimal solutions. We developed a novel modular structure for the Bayesian optimization model that consists of multiple Gaussian process surrogate models that represent the dynamic feasibility and collision avoidance constraints. This modular structure alleviates the stark increase in computational cost with problem dimensionality and enables the use of minimal constraints in the joint optimization of the multi-agent trajectories. The efficiency of the algorithm is further improved by introducing a scheme for simultaneous evaluation of the Bayesian optimization acquisition function and random sampling.
We applied this modular BayesOpt algorithm to optimize multi-agent trajectories through six unique environments using multi-fidelity evaluations from various data sources. We found that the resulting trajectories are faster than those obtained from two baseline methods. We validated the optimized trajectories were validated in real-world experiments using four quadcopters that fly within centimeters of each other at speeds up to 7.4 m/s.
The cooperative multi-agent system is composed of multiple robots that collaborate with each other to achieve the goal.Existing literature has considered cooperative multi-agent motion planning in various contexts, including for mobile robots, manipulators, and unmanned aerial vehicle (UAV) systems. In the field of UAV motion planning, cooperative multi-agent systems are often utilized in robotics applications in which multiple vehicles must simultaneously visit certain locations, e.g., to collect synchronized sensor measurements from different viewpoints or to complete a coordinated task or motion in a cooperative manner, e.g., in target or perimeter defense games where a team of UAVs aims to stop intruders.
These multi-agent planning problems have two properties in common that are particularly relevant when trajectories must be as fast as possible. First, collision avoidance between agents should be considered in a spatio-temporal manner, which means that trajectories may intersect as long as vehicles pass through the intersection at different times. Second, vehicles are only required to attain their position within the multi-agent formation at specific points in the trajectory. This implies that---when traveling between these specific waypoints---agents may deviate from the formation in order to achieve more efficient, i.e., faster, trajectories. Our aim is to generate time-optimal multi-agent trajectories that connect specified start and end points and synchronously attain a sequence of formation waypoints along the way by explicitly leveraging these two properties described above.
We focus on a multi-agent trajectory optimization problem in which quadcopter vehicles are tasked with traversing a complex environment as fast as possible while avoiding collisions with obstacles and with each other. This is challenging because spatio-temporal collision avoidance and formation synchronization require joint and holistic consideration of the agent trajectories. Consequently, the dimension of the input space rapidly increases with the number of agents, leading to the prohibitive computational cost. The problem is further complicated by the fact that fast and agile flight in tight formations is intrinsically complex.
We propose an algorithm that enables efficient optimization of multi-vehicle trajectories by alleviating the explosion of computational cost commonly associated with high dimensionality. The algorithm leverages Bayesian optimization to efficiently sample the search space and build surrogate models that represent the dynamic feasibility and collision avoidance constraints. First, we present a modular Bayesian optimization architecture that reduces the computational burden of multi-agent optimization. Second, we combine the BayesOpt acquisition function evaluation and random sampling steps to further improve the overall efficiency of Bayesian optimization. Third, we demonstrate that our novel BayesOpt architecture can be applied in a multi-fidelity framework with objective and constraint evaluations from various data sources. Fourth, we present extensive experimental results from the proposed algorithm in six unique environments with obstacles and we evaluate the resulting trajectories in both simulation and real-world flight experiments.
Gilhyun Ryou, Ezra Tal and Sertac Karaman,Cooperative Multi-Agent Trajectory Generation with Modular Bayesian OptimizationRobotics: Science and Systems (RSS), 2022.