Abstract
G. Mouratidis, B. Nebel and S. Koenig. Fools Rush in Where Angles Fear to Tread in Multi-Goal CBS. In Symposium on Combinatorial Search (SoCS), pages (in print), 2024.Abstract: Research on multi-agent pathfinding (MAPF) has recently shifted towards problem variants that are closer to actual applications. Such variants often include the assignment of multiple goals to agents. To solve them, researchers have extended the Conflict Based Search (CBS) algorithm to multiple goals. This extension might look straightforward at first sight but it is tricky and this has already led to the development of algorithms that despite claiming to be optimal, return suboptimal solutions for some MAPF instances. In this paper, we provide a detailed analysis of the issue to raise awareness among the search community so that this mistake will not be perpetuated. Furthermore, a first evaluation against an optimal implementation is conducted which shows why this issue might have been difficult to spot. In only one of the randomly generated instances, the suboptimal behavior emerged.
Many publishers do not want authors to make their papers available electronically after the papers have been published. Please use the electronic versions provided here only if hardcopies are not yet available. If you have comments on any of these papers, 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.