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.