Proximal Operators for Multi-Agent Path Planning

José Bento, Nate Derbinsky, Charles Mathy, Jonathan S. YedidiaAAAI 2015 · DOI

Introduction

Multi-agent path planning (MAPP) is a fundamental challenge in robotics, requiring the coordination of numerous agents to move from starting positions to goals without collisions. As the number of agents increases, traditional sampling-based methods like RRT* often fail due to the exponential growth of the search space. Optimization-based approaches offer a faster alternative but are frequently hindered by the complexity of continuous-time collision constraints. This paper, originally presented at AAAI 2015, introduces high-performance "proximal operators" that enable multi-agent planning to scale efficiently to 3D environments and incorporate automatic task assignment.

The Challenge of Collision Constraints

A primary difficulty in MAPP is ensuring that agents do not collide at any point between discrete time steps. This is a "semi-infinite programming" (SIP) problem because it involves an infinite number of potential collision points along a continuous trajectory. Previous optimization frameworks were often limited to 2D space and required manual assignment of agents to specific goals, limiting their utility in dynamic or complex 3D scenarios.

Methodology

The authors utilize Proximal Algorithms, specifically the Alternating Direction Method of Multipliers (ADMM) and the Three Weight Algorithm (TWA). These algorithms decompose a large, global optimization problem into smaller, independent operators that can be solved in parallel.

SIP Reduction and Dimension Agnosticism

The technical core of the paper is a rigorous proof that the complex SIP collision-avoidance problem can be reduced to a single-constraint non-convex problem. By identifying the "worst-case" point in time—the moment when two agents are closest—the system can ensure a collision-free path throughout the entire interval. This reduction provides a closed-form solution that is dimension-agnostic, allowing the same mathematical framework to work for 2D, 3D, or even higher-dimensional spaces without a significant increase in computational difficulty.

Landmark Operators for Task Assignment

To address the problem of goal assignment, the researchers introduced "Landmark Operators." Instead of pre-assigning Robot A to Goal 1, the system treats goals as landmarks in space-time. Using linear assignment algorithms like the Hungarian method, the system dynamically decides which robot is best suited for which landmark based on the current global state, significantly increasing the flexibility of formation control.

Computational Efficiency

The implementation includes shortcuts to skip expensive calculations in "trivial" cases where agents are far apart. By focusing heavy computation only on near-miss scenarios, the algorithm achieves substantial speedups.

Experimental Evaluation and Results

The researchers evaluated their approach using several simulated benchmarks, most notably the CONF1 scenario. In CONF1, agents are placed on the perimeter of a circle (2D) or the surface of a sphere (3D) and must move to the exact opposite side, forcing them to navigate through a dense bottleneck at the center.

Performance and scalability of proximal algorithms in the CONF1 scenario.

Key Findings

  • Speed and Scalability: The new implementation is 7.25x to 8.62x faster than previous state-of-the-art methods for the most difficult collision calculations. As shown in the experimental data, convergence time scales predictably with the number of agents.
  • Parallel Performance: Because proximal operators are computed independently, the algorithm is "embarrassingly parallel." Utilizing 8 CPU cores resulted in a roughly 2x speedup in convergence time compared to single-core execution.
  • 3D and Formation Control: The framework successfully handled 3D spherical agents, a task the previous version could not perform. In the "Movie" problem, agents acted as pixels to form moving shapes, with landmark operators automatically reassigning roles to maintain the most efficient global paths.

Conclusion and Future Work

By refining the mathematical building blocks of collision avoidance, this work provides a scalable framework for complex multi-robot coordination. While highly effective, the authors note that the non-convex nature of the problem means the algorithm can occasionally settle into local minima, requiring random restarts to find global optima. Future research may focus on extending these operators to non-spherical agent geometries and further optimizing the handling of complex obstacle boundaries.

Summary updated

BibTeX
@inproceedings{bento2015proximal,
  author = {José Bento and Nate Derbinsky and Charles Mathy and Jonathan S. Yedidia},
  title = {{Proximal Operators for Multi-Agent Path Planning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2015},
  doi = {10.1609/aaai.v29i1.9672},
}
Figure