Robuste Multi-Roboter Aktive Zielverfolgung gegen Sensor- und Kommunikationsangriffe

Das Problem der Multi-Roboter-Zielverfolgung verlangt eine aktive Planung der gemeinsamen Bewegung von Robotern zur Verfolgung von Zielen. In diesem Artikel konzentrieren wir uns auf solche Zielverfolgungsprobleme in feindlichen Umgebungen, in denen Angriffe oder Ausfälle die Sensoren und Kommunikationen der Roboter deaktivieren können. Im Gegensatz zu den vorherigen Arbeiten, die keine Angriffe oder nur Sensorangriffe betrachten, formalisieren wir das erste robuste Multi-Roboter-Verfolgungsframework, das eine feste Anzahl von schlimmstenfalls sensorischen und kommunikativen Angriffen berücksichtigt. Um uns gegen solche Angriffe abzusichern, entwerfen wir den ersten robusten Planungsalgorithmus, genannt Robust Active Target Tracking (RATT), der die Kommunikationsangriffe als äquivalente sensorische Angriffe annähert und dann gegen die angenäherten und ursprünglichen sensorischen Angriffe optimiert. Wir zeigen, dass RATT provable suboptimalitätsgrenzen hinsichtlich der Verfolgungsqualität für jede nicht abnehmende Zielfunktion bietet. Unsere Analyse nutzt die Notationen der Krümmung für Mengenfunktionen, die in der kombinatorischen Optimierung eingeführt wurden. Darüber hinaus läuft RATT in polynomialer Zeit und beendet sich mit der gleichen Laufzeit wie aktuelle Algorithmen für (nicht-robuste) Zielverfolgung. Schließlich evaluieren wir RATT sowohl mit qualitativen als auch quantitativen Simulationen in verschiedenen Szenarien. In den Bewertungen zeigt RATT eine Verfolgungsqualität, die nahezu optimal und überlegen gegenüber variierenden nicht-robusten Heuristiken ist. Wir demonstrieren auch RATTs Überlegenheit und Robustheit gegenüber variierenden Angriffsmodellen (z.B. schlimmstenfalls und begrenzten rationalen Angriffen) und mit über- und untergeschätzten Angriffszahlen.