Universal Solvability for Robot Motion Planning on Graphs

Autonomousmulti-robotsystemsinmodernwarehousesoftenneed robots to be rearranged for efficient task execution. A key question is whether the underlying layout allows transformation between any two configurations without collisions. We model the layout as a graph𝐺(𝑉, 𝐸), with vertices as locations and edges as paths, and study the Universal Solvability of Robot Motion Planning on Graphs (USolR) problem: given𝐺 and 𝑝 robots, does𝐺 allow any configuration to be transformed into any other via valid moves? For this, we design a linear-time randomized algorithm with onesided error that always correctly identifies universally solvable graphs and may fail only on non-universally solvable instances; derandomization incurs a factor-𝑝 overhead, giving deterministic running times of 𝑂(𝑝(|𝑉| + |𝐸|)) for sparse and 𝑂(|𝑉| + |𝐸|) for dense graphs. Finally, we consider the Graph Edge Augmentation for Universal Solvability (EAUS) problem: given a connected graph𝐺 notuniversallysolvablefor𝑝 robots, canatmost𝛽 edgesbe added to make it universally solvable? We show an upper bound of 𝑝−2on𝛽 forgeneralgraphsandgiveexamplesrequiringΘ(𝑝) edge additions. WethenstudyGraphVertexandEdgeAugmentation forUniversalSolvability(VEAUS), where𝛼 verticesand𝛽 edges may be added, and provide lower bounds on these parameters.

Authors

• Anubhav Dhar Max Planck Institute for Informatics, Saarbrücken
• Pranav Nyati Indian Institute of Technology
• Tanishq Prasad Indian Institute of Technology
• Ashlesha Hota IIT Kharagpur
• Sudeshna Kolay IIT Kharagpur

Keywords

• Robot Motion Planning
• Equivalence classes
• Randomized Algorithms
• Universal Solvability