Class Project "Multi-Agent Path Finding" (using Heuristic Search)

Wolfgang Hoenig, University of Southern California (now at Caltech)
Jiaoyang Li, University of Southern California
Sven Koenig, University of Southern California

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.

This project was chosen as a Model AI Assignment by the Symposium on Educational Advances in Artificial Intelligence in 2020. If you are using it in your class or have any questions, comments or corrections, please send us an email at skoenig@usc.edu. We will use this webpage to post updates, errata and supporting material. We have teaching material available for teachers at accredited colleges and universities, including sample solutions and code. You can find many other Model AI Assignments in the Model AI Assignment Project Archive and might also be interested in our computer games in the classroom projects.

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 MAPF and lecture slides for the teacher. It also 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 missing parts in the provided commented code, which might prevent them from understanding all technical details of the MAPF algorithms.

Prerequisites

The students need to have basic knowledge of informed search (for example, A*) and Python 3 (for example, functions, classes, and lists). A lecture on MAPF (for example, with the provided slides) is helpful.

Requirements

The students need to have access to computers with Python 3. The project has been tested on Macs, Windows PCs, and Linux PCs.

Variants

The project includes several tasks from which the teacher can pick and choose. The students could also implement A* prior to this project and experiment with additional MAPF algorithms, such as M*, afterward.

Project Material

Available Teacher Material (contact skoenig@usc.edu)

Some of this material is based upon work supported by the National Science Foundation and Amazon. Any opinions, findings, and conclusions or recomendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the sponsoring organizations. We tested parts of this project at the Third Summer School on Cognitive Robotics, which was held from July 17 to July 21, 2019 at the University of Southern California, and the undergraduate "Introduction to Artificial Intelligence" class (CS360), which was held in Fall 2019 at the University of Southern California.

If you have comments on this project, please send me an email! Also, please send me your papers if we have common interests.

This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.


Project "Multi-Agent Path Planning (MAPF)"

Home Page of Sven Koenig