Proximal Operators for Multi-Agent Path Planning
DOI:
https://doi.org/10.1609/aaai.v29i1.9672Keywords:
Alternating direction method of multipliers, Proximal operators, Non-convex optimization, Distributed optimization, Message-passing algorithm, Semi-infinite programming, Multi-agent trajectory planning, Collision avoidance, Waypoint assignmentAbstract
We address the problem of planning collision-free paths for multiple agents using optimization methods known as proximal algorithms. Recently this approach was explored in Bento et al. (2013), which demonstrated its ease of parallelization and decentralization, the speed with which the algorithms generate good quality solutions, and its ability to incorporate different proximal operators, each ensuring that paths satisfy a desired property. Unfortunately, the operators derived only apply to paths in 2D and require that any intermediate waypoints we might want agents to follow be preassigned to specific agents, limiting their range of applicability. In this paper we resolve these limitations. We introduce new operators to deal with agents moving in arbitrary dimensions that are faster to compute than their 2D predecessors and we introduce landmarks, space-time positions that are automatically assigned to the set of agents under different optimality criteria. Finally, we report the performance of the new operators in several numerical experiments.
