Optimized and kinematically feasible multi-agent motion planning
For researchers and practitioners in multi-agent motion planning, this work provides a practical framework that combines discrete search with continuous optimization to produce kinematically feasible and optimized trajectories.
This work proposes a two-step method for multi-agent motion planning that first finds an initial feasible solution using CBS or PBS, then improves it via a multi-phase optimal control problem. Evaluated on tractor-trailer systems, CBS achieved higher success rates and lower runtime than PBS, with both yielding similar solution quality after improvement.
Multi-agent motion planning (MAMP) is an important problem for autonomous systems with multiple agents. In this work we propose a two-step method for finding optimized and kinematically feasible solutions to MAMP problems. The first step finds an initial feasible solution using state-of-the-art methods such as conflict-based search (CBS) or priority-based search (PBS), and the second step is an improvement step which improves the solution by solving a multi-phase optimal control problem (OCP) where the initial solution is used to warm-start the solver. We also propose a method for generating motion primitives in an optimized way under the constraint that the primitive durations are all multiples of the same sample time. We evaluate our proposed framework on a MAMP problem for tractor-trailer systems. We extend the safe interval path planning with interval projections (SIPP-IP) algorithm so it can handle more general cost functions and larger agents, but our results show that for the tractor-trailer system a simple lattice-based planner performs better due to less conservative collision checks. Our experiments also indicate that CBS performs better than PBS for this system as it achieves a higher success rate in environments with obstacles and had a lower average runtime, although both planners achieve solutions of similar quality after the improvement step.