Collision Detection for Agents in Multi-Agent Pathfinding

Thayne T. Walker, Nathan SturtevantarXiv 2019 · DOI · arXiv

Abstract

Recent work on the multi-agent pathfinding problem (MAPF) has begun to study agents with motion that is more complex, for example, with non-unit action durations and kinematic constraints. An important aspect of MAPF is collision detection. Many collision detection approaches exist, but often suffer from issues such as high computational cost or causing false negative or false positive detections. In practice, these issues can result in problems that range from inefficiency and annoyance to catastrophic. The main contribution of this technical report is to provide a high-level overview of major categories of collision detection, along with methods of collision detection and anticipatory collision avoidance for agents that are both computationally efficient and highly accurate.

Introduction: The Problem of Continuous Motion

Traditional Multi-Agent Pathfinding (MAPF) often relies on a "grid world" abstraction where agents move between discrete cells in synchronized turns. While this simplifies computation, real-world applications—such as robotics, autonomous drones, and high-fidelity simulations—require continuous motion, varying speeds, and kinematic constraints like acceleration.

In these complex environments, standard collision detection methods often fail in two critical ways:

  1. Type I Errors (False Positives): These occur when using oversized "geometric containers" or bounding boxes. If a bounding box is too large, the system may report a collision where none actually exists, forcing agents into inefficient, zig-zagging paths to avoid imaginary obstacles.
  2. Type II Errors (False Negatives): These occur in sampling-based systems where agent positions are checked at discrete time intervals. If the sampling rate is too low, an agent might "tunnel" through another between samples—the "bullet-through-paper" problem. In safety-critical systems, these errors are catastrophic.
Figure 5: Geometric containers (bounding boxes) can lead to Type I errors (false positives) where collisions are reported despite clear paths.
Figure 6: Sampling-based methods risk Type II errors (false negatives), missing collisions that occur between discrete time steps.

The challenge lies in creating a collision detection system that is computationally efficient enough for real-time pathfinding while remaining mathematically exact to guarantee safety.

Methods: Algebraic Collision Detection

To address these limitations, this work introduces Algebraic Collision Detection, moving beyond simple geometric approximations.

Segmented Motion

The framework defines motion as a series of segments or "actions" with discrete lengths. This approach bridges the gap between discrete graph-based planning and continuous physical execution, allowing for complex maneuvers within a structured search space.

Closed-Form Solutions

For circular agents, the distance between two agents over time can be represented as a polynomial. By solving for the roots of these equations, we can determine the exact start and end times of any potential collision:

  • Constant Velocity: This scenario results in a quadratic equation, which is computationally trivial to solve.
  • Constant Acceleration: This scenario results in a quartic (4th-degree) equation. While more complex, it still allows for exact solutions without the risks of sampling.

The Conic Section Approach and Velocity Obstacles

To facilitate collision avoidance, the framework maps collision conditions into a "delay space." For constant velocity agents, the collision boundary in the "time vs. delay" plane forms a conic section—specifically an ellipse. By analyzing the geometry of this ellipse, an agent can instantly calculate the minimum delay required to let another agent pass safely. This adapts the concept of Velocity Obstacles (VO) for segmented motion, providing a geometric representation of all unsafe velocities.

Key Insights: The Geometry of Avoidance

One of the most elegant contributions is the transformation of the collision problem into the study of ellipses. By finding the extrema of an ellipse in the time-delay plane, an agent can determine the "unsafe interval" of start times without needing to simulate the entire motion.

Furthermore, the authors argue for the prioritization of safety over optimality. While Type I errors (being too cautious) result in sub-optimal paths, Type II errors (missing a crash) invalidate the entire plan. Algebraic methods are inherently superior because they eliminate Type II errors entirely. The math also robustly handles temporal offsets, accounting for agents that start their segments at different times—a common occurrence in real-world multi-agent systems.

Results and Future Work

The paper provides specific quadratic and quartic formulas for finding exact conflict intervals and introduces an algorithm to compute the range of start times that lead to collisions. This allows pathfinders to "prune" unsafe branches during the search process efficiently. For constant velocity agents, a direct formula for minimum delay is provided, eliminating the need for iterative "guess-and-check" methods.

Limitations

Currently, the closed-form solutions are optimized for circular (2D) and spherical (3D) agents. Complex polygonal shapes or high-aspect-ratio agents (like long vehicles) still require more intensive geometric intersection tests. Additionally, while the constant velocity case has a neat "ellipse" solution for delays, the constant acceleration case leads to a "quartic plane curve," which currently requires iterative methods like binary search for certain delay calculations. Future research aims to derive exact formulations for these acceleration-based unsafe intervals to match the efficiency of the velocity-only case.

Summary updated

Abstract

Recent work on the multi-agent pathfinding problem (MAPF) has begun to study agents with motion that is more complex, for example, with non-unit action durations and kinematic constraints. An important aspect of MAPF is collision detection. Many collision detection approaches exist, but often suffer from issues such as high computational cost or causing false negative or false positive detections. In practice, these issues can result in problems that range from inefficiency and annoyance to catastrophic. The main contribution of this technical report is to provide a high-level overview of major categories of collision detection, along with methods of collision detection and anticipatory collision avoidance for agents that are both computationally efficient and highly accurate.
BibTeX
@misc{walker2019collision,
  author = {Thayne T. Walker and Nathan Sturtevant},
  title = {{Collision Detection for Agents in Multi-Agent Pathfinding}},
  year = {2019},
  eprint = {1908.09707},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1908.09707},
}
Figure