The Complexity of Routing Few Robots in a Crowded Network

Das Steuern von Robotern in einer Umgebung unter Vermeidung von Kollisionen ist ein häufiges Problem in der Industrie. Einige natürliche Formalisierungen dieses Problems modellieren Roboter als zweidimensionale Quadrate oder Scheiben, die sich durch einen „Raum“ in der Ebene bewegen. Diese Arbeit betrachtet ein abstrakteres, graphentheoretisches Modell, bei dem die Roboter die Knoten eines Graphen einnehmen und sich entlang seiner Kanten bewegen. Wir entwickeln den Stand der Technik von zwei gängigen Problemformalisierung namens GCMP und GCMP1 weiter. Wir untersuchen das Problem unter dem Gesichtspunkt der parametrisierten Komplexität und führen zwei neue Parametrisierungen ein: eine, die einen W[1]-Härtebeweis liefert, und eine andere, die die Einbettung in FPT festlegt.