Subdimensional expansion method for multi-agent path finding with long narrow corridors

Multi-agent path finding, a problem largely related to the field of robotics, has been proven to be an NP-Hard problem and computationally heavy. Experience-based planning method is a sample-based method that uses a pre-computed database to reduce the planning time. We propose an algorithm that extends based on a prior experience-based framework to target specifically multi-agent path planning problems with long narrow corridors. By leveraging graph homomorphism, we expand a database for doorway problems to cover corridors with various shapes and sizes. The algorithm can find solutions for MAPF problems with a consistent 60-70% higher success rate compared to multiple baselines in environments with multiple narrow corridors without sacrificing performance. The proposed algorithm shows the ability to plan the paths for about a hundred robots in congested simulated environments with and without narrow corridors within a few seconds.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Electrical & Computer Engr

Grantor

University of Illinois Urbana-Champaign

Year dc:date

2025

Author dc:creator

• You, Haoyuan

Contributors dc:contributor

• Driggs-Campbell, Katie

• Multi-agent Path Finding
• Robotics

Statement dc:rights

• Copyright 2025 Haoyuan You

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/130069

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F130069