Moving robots efficiently using the combinatorics of CAT(0) cubical complexes

DOI10.1137/120898115MaRDI QIDQ3192175zbMATH OpenOpenAlexFDO

Authors Federico Ardila, Tia Baker, Rika Yatchak

Publication date 26 September 2014

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1211.1442

zbMATH Keywords

CAT(0) spacescubical complexdistributive latticesevent structuresposetsrobots

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Combinatorics of partially ordered sets (06A07) Global geometric and topological methods (à la Gromov); differential geometric analysis on metric spaces (53C23) General topology of complexes (57Q05) Artificial intelligence for robotics (68T40)

Abstract: Given a reconfigurable system X, such as a robot moving on a grid or a set of particles traversing a graph without colliding, the possible positions of X naturally form a cubical complex S(X). When S(X) is a CAT(0) space, we can explicitly construct the shortest path between any two points, for any of the four most natural metrics: distance, time, number of moves, and number of steps of simultaneous moves. CAT(0) cubical complexes are in correspondence with posets with inconsistent pairs (PIPs), so we can prove that a state complex S(X) is CAT(0) by identifying the corresponding PIP. We illustrate this very general strategy with one known and one new example: Abrams and Ghrist's positive robotic arm on a square grid, and the robotic arm in a strip. We then use the PIP as a combinatorial "remote control" to move these robots efficiently from one position to another.

Recommendations

• The combinatorics of \(\mathrm{CAT}(0)\) cubical complexes
• The configuration space of a robotic arm in a tunnel of width 2
• The geometry and topology of reconfiguration
• Geodesics in CAT(0) cubical complexes
• The configuration space of a robotic arm in a tunnel

Cited in

(14)

• Dual equivalence graphs and CAT(0) combinatorics
• Relating CAT(0) cubical complexes and flag simplicial complexes
• The configuration space of a robotic arm in a tunnel
• The configuration space of a robotic arm in a tunnel of width 2
• scientific article; zbMATH DE number 6405363 (Why is no real title available?)
• Convexity in tree spaces
• The combinatorics of \(\mathrm{CAT}(0)\) cubical complexes
• Old and new challenges in Hadamard spaces
• The configuration space of a robotic arm over a graph
• Block symmetries in graph coloring reconfiguration systems
• Geodesics in CAT(0) cubical complexes
• Towards control, learning and intelligence in reconfigurable systems
• Markov chains, CAT(0) cube complexes, and enumeration: monotone paths in a strip mix slowly
• Recognizing weighted means in geodesic spaces

This page was built for publication: Moving robots efficiently using the combinatorics of CAT(0) cubical complexes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3192175)