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.|
|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.|