Multi-Agent Path Finding on Ozobots

Roman Barták, Ivan Krasicenko, Jirí SvancaraIJCAI 2019 · DOI

TL;DR

This paper introduces a novel system for evaluating different abstract models of Multi-Agent Path Finding (MAPF) by executing the generated plans on physical Ozobot robots. The key insight is that abstract MAPF models, while theoretically sound, can exhibit significant differences in real-world execution due to factors like varying action durations, highlighting the importance of bridging the gap between theoretical frameworks and practical robotics.

What Problem Does This Paper Address?

Multi-Agent Path Finding (MAPF) is a fundamental problem in robotics and AI, concerning how multiple agents can navigate an environment without colliding. While many abstract models and algorithms exist for MAPF, there's a significant challenge in understanding how these theoretical plans translate to the real world. Abstract models often simplify actions (e.g., a single "move" action) and assume uniform durations, which doesn't reflect the complexities of physical robots. These robots have distinct, potentially variable, action durations (e.g., turning versus moving forward) and may require different low-level commands. This paper addresses the gap between abstract MAPF models and their practical execution on physical robots, specifically investigating how different abstractions impact real-world plan performance.

Methods

The authors developed a software system that facilitates the entire MAPF pipeline, from problem definition to real-world execution. The system includes:

  • Visual Map Editor: Users can design grid-based environments, define obstacles, and set agent start and goal locations.
  • MAPF Solvers Integration: The system interfaces with solvers written in the Picat programming language, which encode various MAPF models (including classical, 1-robust, and models with turning actions) and translate them into SAT problems.
  • Plan Visualization: Generated abstract plans can be visualized as Gantt charts, showing the sequence of actions for each agent over time.
  • Simulation and Execution: Plans can be simulated within the software or exported for execution on physical Ozobot robots.
  • Plan Translation: Crucially, the abstract plans are translated into sequences of commands that Ozobots can understand. This involves mapping abstract actions to Ozobot's capabilities (wait, move forward, turn left/right, move). The system allows users to specify action durations for execution, acknowledging that these can vary.

The core novelty lies in the end-to-end system that bridges abstract MAPF models with physical robot execution, allowing for direct empirical evaluation of different abstractions.

Datasets

The paper does not discuss specific pre-existing datasets for MAPF evaluation. Instead, it focuses on creating custom MAPF scenarios using its own map editor. These scenarios are designed to be "smaller but dense environments with tight plans," which are typical outputs of optimal MAPF solvers and are particularly challenging for real-world execution.

Key Insights and Ideas

  • The Abstraction Gap is Real: The most significant insight is that theoretical MAPF plans, even when optimal in an abstract sense, can perform very differently when executed on physical robots. This is due to the simplified assumptions in abstract models regarding action durations and capabilities.
  • Action Durations Matter: The system's ability to specify and account for different action durations (e.g., turning vs. moving) is critical for realistic plan execution. Variations in these durations can lead to unexpected collisions or deadlocks.
  • Bridging Theory and Practice: The developed system provides a valuable research tool for the MAPF community, enabling empirical validation of abstract models in a tangible, real-world setting.
  • Ozobots as a Practical Platform: Using Ozobots offers an accessible platform for this research, requiring no specialized robotics expertise, thus democratizing the study of MAPF execution.

Key Results

The paper reports on initial empirical evaluations that show "significant differences when the plans for different abstract models are executed on robots." While specific quantitative metrics (like success rates or collision counts for each model) are not detailed in this excerpt, the qualitative finding is that the choice of abstract MAPF model has a discernible impact on the success and behavior of plans executed on Ozobots. The system successfully translates abstract plans into executable sequences for the robots and allows for visualization of this execution.

Limitations and Future Work

  • Blind Execution: Currently, the system assumes "blind execution," meaning robots do not use sensors during execution to adapt to unforeseen circumstances.
  • Limited Robot Capabilities: The Ozobot's movement capabilities are relatively simple.
  • Future Work:
    • Conducting wider experimental studies to better understand the relationship between abstract models and real-world performance.
  • Investigating how factors like the ratio of edge length to robot size influence execution.
  • Exploring plan-execution policies that incorporate sensor information and inter-agent communication.
  • Developing more advanced execution strategies by modifying command sequences.

Summary updated

BibTeX
@inproceedings{bartak2019multi,
  author = {Roman Barták and Ivan Krasicenko and Jirí Svancara},
  title = {{Multi-Agent Path Finding on Ozobots}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/933},
}
Figure