# Efficient Multi-Agent Trajectory Planning with Feasibility Guarantee using Relative Bernstein Polynomial

arXiv: https://arxiv.org/abs/1909.10219 · HTML: https://mlsanity.com/paper/1909.10219/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Sep 2019.

## Built on by (most cited first, 6 of 6)

- [Discrete-Guided Diffusion for Scalable and Safe Multi-Robot Motion Planning](https://mlsanity.com/paper/2508.20095/) (2025)
- [PRIMER: Perception-Aware Robust Learning-based Multiagent Trajectory Planner](https://mlsanity.com/paper/2406.10060/) (2024)
- [Flow-Opt: Scalable Centralized Multi-Robot Trajectory Optimization with Flow Matching and Differentiable Optimization](https://mlsanity.com/paper/2510.09204/) (2025)
- [LEARN: Learning End-to-End Aerial Resource-Constrained Multi-Robot Navigation](https://mlsanity.com/paper/2511.17765/) (2025)
- [Multi-Robot Motion Planning from Vision and Language using Heat-Inspired Diffusion](https://mlsanity.com/paper/2512.13090/) (2025)
- [Training-Free Diffusion Planning with Analytical Local Scores](https://mlsanity.com/paper/2610.01959/) (2026)

## Abstract (arXiv)

This paper presents a new efficient algorithm which guarantees a solution for a class of multi-agent trajectory planning problems in obstacle-dense environments. Our algorithm combines the advantages of both grid-based and optimization-based approaches, and generates safe, dynamically feasible trajectories without suffering from an erroneous optimization setup such as imposing infeasible collision constraints. We adopt a sequential optimization method with textitdummy agents to improve the scalability of the algorithm, and utilize the convex hull property of Bernstein and relative Bernstein polynomial to replace non-convex collision avoidance constraints to convex ones. The proposed method can compute the trajectory for 64 agents on average 6.36 seconds with Intel Core i7-7700 @ 3.60GHz CPU and 16G RAM, and it reduces more than 50% of the objective cost compared to our previous work. We validate the proposed algorithm through simulation and flight tests.