Multi-Robot Motion Planning with Dynamics Guided by Multi-Agent Search

Duong Le, Erion PlakuIJCAI 2018 · DOI

TL;DR

This paper introduces a novel multi-robot motion planning approach that combines the strengths of sampling-based planning for dynamic feasibility with multi-agent search for efficient coordination. By using multi-agent search over a discrete abstraction to guide a continuous motion tree expansion, the method significantly speeds up the planning process for robots with complex dynamics in cluttered environments.

What Problem Does This Paper Address?

Planning the coordinated movement of multiple robots in a shared environment is a notoriously difficult problem. Each robot has its own physical limitations (dynamics like acceleration and turning radius) and must avoid collisions with both static obstacles and other robots. Traditional approaches either plan for each robot independently, risking deadlocks, or try to plan for all robots simultaneously in a high-dimensional "composite" state space, which quickly becomes computationally intractable as the number of robots increases. This paper tackles the challenge of finding dynamically feasible, collision-free paths for multiple robots efficiently, especially in complex scenarios where their movements are interdependent.

Methods

The core innovation lies in coupling two distinct planning paradigms:

  • Discrete Abstraction & Multi-Agent Search: The complex continuous world is simplified into a discrete "roadmap" representation. Here, robot dynamics are ignored, and the focus is on connectivity. Multi-agent search algorithms (like A* variants) are then used on this discrete roadmap to find non-conflicting paths for each robot. This provides a high-level, coordinated plan.
  • Continuous Motion Tree Expansion: A sampling-based motion planner (similar to RRT) builds a "motion tree" in the robots' actual, continuous state space (including dynamics). This tree represents possible dynamically feasible trajectories.
  • Guided Expansion: The key is how these two are linked. The discrete paths found by multi-agent search are used as "routes" to guide the expansion of the continuous motion tree. The algorithm partitions the motion tree into "equivalence classes" based on where robots are in the discrete abstraction. It then selects an equivalence class and expands the motion tree along the corresponding discrete routes. If expansion along a route proves difficult (due to dynamics or obstacles), the route is "penalized," encouraging the planner to explore alternatives.

Datasets

Not discussed in the paper. The experiments use simulated vehicle models in various complex environments, illustrated in figures.

Key Insights and Ideas

  • Synergy of Discrete and Continuous Planning: The paper demonstrates that combining a high-level discrete search with a low-level continuous planner can overcome the limitations of each. The discrete search provides coordination, while the continuous planner ensures physical feasibility.
  • Heuristic Guidance for Sampling-Based Planners: Multi-agent search acts as a powerful heuristic for sampling-based motion planners. Instead of exploring the vast continuous state space randomly, the planner is guided towards promising regions identified by the discrete search, drastically improving efficiency.
  • Equivalence Classes for Structured Exploration: Partitioning the continuous state space (motion tree) into equivalence classes based on the discrete abstraction allows for a systematic and guided exploration strategy. This prevents the planner from getting lost in complex state spaces.
  • Dynamic Penalties for Robustness: The penalty mechanism for difficult routes is crucial. It prevents the planner from getting stuck on a single, potentially infeasible, discrete path and ensures it can find solutions even when dynamics or complex interactions make initial routes problematic.

Key Results

The proposed approach demonstrated significant speedups compared to existing methods like CRRT, pRRT, and pGUST.

  • In scenarios requiring cooperation, the new method achieved solutions in 1-3 seconds, whereas pGUST (a prioritized approach) failed within the time limit.
  • The method was able to solve complex scenarios (scenes 4, 5, 6) where other planners timed out.
  • In simpler, open environments where robot cooperation is less critical, pGUST was faster, highlighting that the overhead of the proposed method is beneficial for coordinated tasks.

Limitations and Future Work

  • Multi-Agent Search Efficiency: The paper notes that advances in multi-agent search could further improve the efficiency and scalability of the framework.
  • Route Quality: Future work could focus on improving the quality of routes generated by multi-agent search, for example, by maximizing robot separation or clearance from obstacles, which would make them easier to follow in the continuous space.
  • Complex Task Planning: Extending the framework to handle more complex tasks defined by formalisms like PDDL is suggested as a future direction.

Summary updated

BibTeX
@inproceedings{le2018multi,
  author = {Duong Le and Erion Plaku},
  title = {{Multi-Robot Motion Planning with Dynamics Guided by Multi-Agent Search}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/744},
}
Figure