Teamkoordination auf Graphen: Problem, Analyse und Algorithmen

Die Teamkoordination auf Graphen mit riskanten Kanten (TCGRE) ist ein kürzlich aufgetretenes Problem, bei dem ein Roboterteam die Traversierungskosten von Graphen kollektiv verringert, indem ein Roboter einen anderen unterstützt, wenn dieser eine riskante Kante überquert. Ähnlich wie das traditionelle Problem des Multi-Agenten-Pfadfindens (MAPF) wurden sowohl klassische als auch lernbasierte Methoden vorgeschlagen, um TCGRE zu lösen, jedoch mangelte es ihnen entweder an Recheneffizienz oder an der Garantie für Optimalität. In diesem Papier reformulieren wir TCGRE als eine beschränkte Optimierung und führen eine rigorose mathematische Analyse durch. Unsere theoretische Analyse zeigt die NP-Härte von TCGRE durch Reduktion vom Maximum 3D Matching Problem und dass eine effiziente Zerlegung der Schlüssel zur Bewältigung dieses kombinatorischen Optimierungsproblems ist. Darüber hinaus entwerfen wir drei Klassen von Algorithmen zur Lösung von TCGRE, d.h. Lösungen basierend auf Joint State Graph (JSG), koordinationsbasierten und sub-team-basierten Lösungen mit zurückblickendem Horizont. Jeder dieser vorgeschlagenen Algorithmen bietet unterschiedliche nachweisbare Optimalitäts- und Effizienzmerkmale, die in unseren umfassenden Experimenten demonstriert werden.