A Project on Multi-Agent Path Finding

Wolfgang Hönig, California Institute of Technology (formerly University of Southern California)
Jiaoyang Li, University of Southern California
Sven Koenig, University of Southern California
Summary

We provide project material for the emerging topic of multi-agent path finding (MAPF), where agents (typically: robots) operate in a known environment and are tasked with moving from their current locations to their respective goal locations without colliding with the environment or each other. MAPF is a key task for autonomous warehousing and just-in-time manufacturing. Traditional search algorithms in the joint location space, such as A*, scale poorly in the number of agents. Therefore, one needs to develop search algorithms that exploit the problem structure better to gain efficiency. We provide project material for two such search algorithms, namely the incomplete and suboptimal prioritized planning and the complete and optimal (but slower) conflict-based search.

The project material is designed for undergraduate and graduate students with prior knowledge of A* and working knowledge of Python. We provide a textbook-style overview of MAPF for the teacher and students that describes the MAPF problem and two solution approaches; lecture slides for the teacher; a code framework that includes result visualization; a handout for the students that guides them to finish the implementations with a focus on single-agent path finding, constraint generation and resolution; and sample solutions for the teacher.

Topics Informed Search (including A* and best-first search), path planning, motion planning, and multi-agent/multi-robot coordination.
Audience Undergraduate and graduate students in “introduction to artificial intelligence” and more advanced artificial intelligence classes.
Difficulty Easy to moderate difficulty. Space-time A* and prioritized planning can be finished in 2 hours each. Conflict-based search requires an additional 2 hours. Longer open-ended task assignments are included as well.
Strengths
  • The project includes a textbook-style introduction to important concepts of multi-robot path planning and lecture slides for the teacher.
  • The project includes an extensible framework that provides a foundation for more advanced MAPF algorithms.
Weaknesses The project requires working knowledge of Python 3. Students only have to fill in gaps in the provided source code, which might prevent them from understanding all technical details of the MAPF algorithms.
Dependencies Knowledge:
  • Informed search (for example, A*)
  • Python 3 (functions, classes, list comprehension)
  • A lecture prior the assignment is useful
Requirements:
  • Computer with Python 3 (Mac/Windows/Linux tested)
Variants
  • The project includes several tasks from which the teacher can pick and choose.
  • The students could also implement A* prior to this project.
  • The students could also experiment with additional MAPF algorithms, such as M*.

Teaching Material