Extending CBS to efficiently solve MAPFW

Extending CBS to efficiently solve MAPFW

Jadoenathmisier, Noah (TU Delft Electrical Engineering, Mathematics and Computer Science)

de Weerdt, M.M. (mentor)
Mulderij, J. (mentor)

Delft University of Technology

Computer Science and Engineering

Algorithmic Comparison for the Multi-Agent Path Finding Problem with Waypoints

2020-06-22

Multi-Agent Path Finding with Way-points (MAPFW) is the problem of routing agents through a graph past a set of waypoint to a goal location, without agents colliding, with the shortest combined path length. This problem has to the authors knowledge not been investigated yet even though it has implications in train scheduling problems and video game artificial intelligence. In this paper an extension to Conflict Based Search (CBS), an algorithm that solves Multi-Agent Path Finding problems without waypoints, is proposed to solve MAPFW problems, named CBSW.
The effect of extending the Bypass optimization and the Prioritizing conflicts optimization for CBS to CBSW is investigated and a new optimization that improves the performance of CBSW in corridors is proposed.
CBSW is compared with other MAPFW solvers that have been developed made simultaneously, and experimental result show a large speed up using CBSW on benchmarks with large maps or many waypoints.

Path Finding
Multi-Agent Path Finding
optimal
python

http://resolver.tudelft.nl/uuid:7b6ed42f-ded8-4256-821b-735cbfe1ea62

Student theses

bachelor thesis

© 2020 Noah Jadoenathmisier