Discrete Mathematics & Theoretical Computer Science |

- 1 Department of Mathematics [San Francisco]
- 2 San Francisco State University

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 $\mathcal{S}(X)$. When $\mathcal{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 $\mathcal{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.

Source: HAL:hal-01229663v1

Volume: DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013)

Section: Proceedings

Published on: January 1, 2013

Imported on: November 21, 2016

Keywords: cubical complexes,combinatorial optimization,posets,reconfigurable systems,state complexes,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Funding:

- Source : OpenAIRE Graph
*CAREER: Matroids, polytopes, and their valuations in algebra and geometry*; Funder: National Science Foundation; Code: 0956178*Creating Momentum through Communicating Mathematics*; Funder: National Science Foundation; Code: 0841164

This page has been seen 258 times.

This article's PDF has been downloaded 298 times.