Das Aufweckproblem: Mobiles Scheduling für einen Roboterschwarm

Wir betrachten das folgende Optmierungsproblem: Gegeben eine Menge mobiler Roboter, von denen einer ``wach'' ist. Das Ziel ist es, einen optimalen Ablaufplan zu finden, bei dem alle Roboter frühestmöglich ``aufgeweckt'' sind; dabei kann jeder wache Roboter andere schlafende Roboter aufwecken, indem er zu ihnen fährt. Dieses Problem hat einige Gemeinsamkeiten mit sogennanten ``Broadcasting-Problemen'', bei denen Information zwischen verschiedenen Teilnehmern übermittelt werden muss. Allerdings gibt es wichtige Unterschiede, da nicht nur die Informationen, sondern auch die Teilnehmer selbst bewegt werden müssen.

Wir betrachten sowohl Szenarien auf Graphen, als auch geometrische Versionen. Im Graphkontext befinden sich Roboter an Knoten und die Reisezeit entlang Kanten ist durch nichtnegative Kantengewichte gegeben. Während Braodcastingprobleme auf Bäumen polynomiell gelöst werden können, zeigen wir, dass das Aufweckproblem selbst auf gewichteten Sternen NP-schwer ist. Eine Approximation innerhalb eines Faktors 5/3 ist auch auf Graphen mit begrenztem Maximalgrad NP-schwer. Als Gegenstücke zu diesen negativen Ergebnissen entwickeln wir eine Reihe von Approximationsalgorithmen für unterschiedliche Szenarien. Dazu gehören eine scharfe Schranke von 7/3 für Greedy-Strategien und ein polynomielles Aproximationsschema auf Sterngraphen, eine 2^O(sqrt(log log n))-Approximation für Ultrametriken, ein Approximationsschema für geometrische Instanzen und eine einfache On-line-Strategie für Graphen mit begrenztem Maximalgrad.

Diese Arbeit entstand in Kooperation mit Estie Arkin, Michael Bender, Joe Mitchell (SUNY Stony Brook) und Martin Skutella (TU Berlin).

B.Hammer