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

DOI10.1137/120898115zbMATH Open1339.68251arXiv1211.1442OpenAlexW2963724636MaRDI QIDQ3192175FDOQ3192175

Tia Baker, Rika Yatchak, Federico Ardila

Publication date: 26 September 2014

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

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.

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

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

zbMATH Keywords

CAT(0) spacesdistributive latticesposetsevent structurescubical complexrobots

Mathematics Subject Classification ID

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

Cited In (10)

• Title not available (Why is that?)
• Block symmetries in graph coloring reconfiguration systems
• Dual equivalence graphs and CAT(0) combinatorics
• Old and new challenges in Hadamard spaces
• The configuration space of a robotic arm over a graph
• Convexity in Tree Spaces
• Towards control, learning and intelligence in reconfigurable systems
• Title not available (Why is that?)
• Relating CAT(0) cubical complexes and flag simplicial complexes
• The Configuration Space of a Robotic Arm in a Tunnel

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)