The configuration space of a robotic arm over a graph

DOI

10.1142/S1793830922501506

Document Type

Journal Article

Publication Date

1-1-2022

Publication Title

Discrete Mathematics, Algorithms and Applications

ISSN

17938309

Keywords

combinatorial optimization, configuration space, distance in graphs, Robotic arm

Abstract

In this paper, we investigate the configuration space G,b,associated with the movement of a robotic arm of length on a grid over an underlying graph G, anchored at a vertex b G. We study an associated poset with inconsistent pairs (PIP) IPG,b,consisting of indexed paths on G. This PIP acts as a combinatorial model for the robotic arm, and we use IPG,b,to show that the space G,b,is a CAT(0) cubical complex, generalizing work of Ardila, Bastidas, Ceballos, and Guo. This establishes that geodesics exist within the configuration space, and yields explicit algorithms for moving the robotic arm between different configurations in an optimal fashion. We also give a tight bound on the diameter of the robotic arm transition graph - the maximal number of moves necessary to change from one configuration to another - and compute this diameter for a large family of underlying graphs G.

Open Access

Green Accepted

Link to Full Text

Share

COinS