Proximal operators for multi-agent path planning

 

We address the problem of planning collision-free paths for multiple agents using optimization methods known as proximal algorithms.

January 25, 2015
Association for the Advancement of Artificial Intelligence (AAAI) 2015

 

Authors

Jose Bento (Disney Research)

Nate Derbinsky (Disney Research)

Charles Mathy (Disney Research)

Jonathan Yedidia (Disney Research)

Proximal operators for multi-agent path planning

Abstract

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, spacetime 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.

Copyright Notice