Efficient Multi-Agent Trajectory Planning with Feasibility Guarantee using Relative Bernstein Polynomial
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 \textit{dummy 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.
Code (1)
Tasks
Collision AvoidanceCPUTrajectory PlanningSimilar Papers 제목 키워드 기반
Decentralized Contingency MPC based on Safe Sets for Nonlinear Multi-agent Collision Avoidance
Decentralized collision avoidance remains challenging, particularly when agents do not communicate any information related to planned trajectories. Most existing approaches either rely on conservative coordination mechan…
Collision AvoidanceMulti-Agent gatekeeper: Safe Flight Planning and Formation Control for Urban Air Mobility
We present Multi-Agent gatekeeper, a framework that provides provable safety guarantees for leader-follower formation control in cluttered 3D environments. Existing methods face a trad-off: online planners and controller…
Collision AvoidanceLearning to Predict Vehicle Trajectories with Model-based Planning
Predicting the future trajectories of on-road vehicles is critical for autonomous driving. In this paper, we introduce a novel prediction framework called PRIME, which stands for Prediction with Model-based Planning. Unl…
Autonomous DrivingMotion ForecastingPredictionTime-aware Motion Planning in Dynamic Environments with Conformal Prediction
Safe navigation in dynamic environments remains challenging due to uncertain obstacle behaviors and the lack of formal prediction guarantees. We propose two motion planning frameworks that leverage conformal prediction (…
Motion PlanningOptimizing Trajectories for Highway Driving with Offline Reinforcement Learning
Implementing an autonomous vehicle that is able to output feasible, smooth and efficient trajectories is a long-standing challenge. Several approaches have been considered, roughly falling under two categories: rule-base…
Autonomous DrivingOffline RLreinforcement-learningReinforcement Learning+1