ESO-MAPF: Bridging Discrete Planning and Continuous Execution in Multi-Agent Pathfinding

Ján Chudý, Pavel SurynekAAAI 2021 · DOI

Abstract

Multi-Agent Pathfinding (MAPF) typically relies on discrete abstractions that fail to account for the continuous dynamics of physical robots. This paper introduces Environment Surface Outputs for MAPF (ESO-MAPF), a platform that bridges the planning-acting gap. By utilizing a computer screen as a dynamic environment, ESO-MAPF translates discrete SAT-based plans into continuous trajectories visualized as animated curves. Low-cost Ozobot Evo robots then execute these paths using reflex-based line following. Our results demonstrate that this approach improves execution robustness and provides a valuable tool for studying the synchronization between high-level planning and physical acting.

Introduction

In Multi-Agent Pathfinding (MAPF), researchers often employ a convenient abstraction: agents are represented as points on a graph, and time progresses in discrete intervals. While this simplification facilitates mathematical modeling and algorithmic development, it neglects the complexities of real-world robotic execution. Physical robots possess momentum, experience drift, and require continuous control signals rather than instantaneous teleportation between nodes.

Discrete graph representation of a MAPF problem.

The authors identify a significant "planning-acting chain" gap. Most MAPF research focuses on "thinking" (the algorithm), treating "acting" (execution) as an afterthought. Rigidly compiled discrete plans often fail when robots encounter physical delays. ESO-MAPF addresses this by providing a flexible, low-cost platform to study the intersection of discrete planning and continuous execution.

Methodology

The ESO-MAPF platform operates through a three-stage pipeline:

  1. Discrete Planning: The system employs a state-of-the-art SAT-based planner to determine Sum-of-Costs (SoC) optimal paths on a 4-connected grid. This stage handles the high-level logic of route determination.
  2. Plan Conversion: The discrete plan is converted into a continuous schedule. Grid movements are replaced with "primitive actions"—sequences of path segments tailored to the context of the move, such as distinguishing between sharp turns and straight-line segments.
  3. Physical Acting and Sensing: In a novel approach, robots (Ozobot Evos) are placed on a horizontal flat-screen monitor. The screen serves as the environment, displaying animated curves—the Environment Surface Outputs—directly beneath the robots.
The ESO-MAPF platform overview, showing the Ozobot Evo and the screen-based execution environment.

The robots utilize built-in line-following sensors to track these curves. To maintain synchronization, the system uses colored path segments to signal speed adjustments, creating a real-time feedback loop between the digital plan and physical agents.

Evaluation and Results

The platform was evaluated using standard MAPF benchmarks translated into visual formats for the screen-based environment, utilizing Ozobot Evo robots as physical agents.

Key findings include:

  • Successful Integration: The system demonstrated a complete planning-acting chain where discrete plans were reliably executed by physical robots with minimal error.
  • Robustness: Reflex-based line following proved significantly more robust than traditional methods relying on direct movement commands, as the environment itself (the screen) dynamically guides the agents.
  • Bottleneck Identification: Observations suggest that computational complexity in the planner remains the primary bottleneck in multi-agent systems, justifying the continued use of discrete abstractions for complex pathfinding while improving the execution layer.

Conclusion and Future Work

ESO-MAPF provides an accessible platform for both research and education, highlighting the challenges of physical desynchronization in robotic swarms. Current limitations include a restriction to 4-connected grids and physical scaling constraints imposed by screen size. Future work will explore integrating continuous planners into the first stage of the chain to further enhance swarm fluidity and simplify the conversion process.

Summary updated

BibTeX
@inproceedings{chudy2021eso,
  author = {Ján Chudý and Pavel Surynek},
  title = {{ESO-MAPF: Bridging Discrete Planning and Continuous Execution in Multi-Agent Pathfinding}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i18.17997},
}
Figure