Optimale und begrenzt suboptimale Any-Angle Multi-Agenten Pfadsuche (Erweiterter Abstract)

Die Multi-Agenten-Pfadsuche (MAPF) ist das Problem, eine Reihe konfliktfreier Pfade für eine Menge von Agenten zu finden. Wir untersuchen, wie man MAPF-Probleme löst, wenn jeder Agent sich zwischen beliebigen Paaren möglicher Standorte bewegen kann, solange das Überqueren des Liniensegments, das sie verbindet, nicht zu einer Kollision mit den Hindernissen führt. Dies wird als Any-Angle-Pfadsuche bezeichnet. Wir präsentieren den ersten optimalen Any-Angle-Multi-Agenten-Pfadsuchalgorithmus. Unser Planer basiert auf dem Continuous Conflict-based Search (CCBS)-Algorithmus und einer optimalen Any-Angle-Variante der Safe Interval Path Planning (TO-AA-SIPP). Die unkomplizierte Kombination dieser Ansätze skaliert jedoch schlecht. Um dies zu mildern, passen wir zwei Techniken aus der klassischen MAPF an das Any-Angle-Setting an, nämlich Disjoint Splitting und Multi-Constraints. Experimentelle Ergebnisse zu verschiedenen Kombinationen dieser Techniken zeigen, dass sie es ermöglichen, über 30% mehr Probleme zu lösen als die normale Kombination aus CCBS und TO-AA-SIPP. Darüber hinaus präsentieren wir eine begrenzt suboptimale Variante unseres Algorithmus, die es ermöglicht, Laufzeit gegen Lösungskosten in kontrollierter Weise zu tauschen.