The Complexity of Routing Few Robots in a Crowded Network

Abstract

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.

Routing robots in an environment while avoiding collisions is a common problem inindustry. Some natural formalizations of this problem model robots as two-dimensional squares or discs that navigate through a “room” in the plane. This thesis considers a more abstract, graph-theoretic model, where the robots occupy the vertices of a graph and move around along its edges. We advance the state of the art of a common problem formalization, called GCMP and GCMP1. We study the problem through the lens of parameterized complexity and introduce two new parameterizations: one yielding a W[1]-hardness proof, and the other establishing inclusion in FPT.