Computing braid groups of graphs with applications to robot motion planning

DOI10.4310/HHA.2012.V14.N1.A8MaRDI QIDQ424856zbMATH OpenFDO

Authors Vitaliy Kurlin

Publication date 6 June 2012

Published in Homology, Homotopy and Applications (Search for Journal in Brave)

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

zbMATH Keywords

braid groupconfiguration spacemotion planning algorithm

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Braid groups; Artin groups (20F36) Discriminantal varieties and configuration spaces in algebraic topology (55R80) Fundamental group, presentations, free differential calculus (57M05) Kinematics of mechanisms and robots (70B15) Control of mechanical systems (70Q05) Automated systems (robots, etc.) in control theory (93C85)

Abstract: Let $X$ be a simplicial complex with a piecewise linear function $f:XomathbbR$. The Reeb graph $Reeb(f,X)$ is the quotient of $X$, where we collapse each connected component of $f^{-1}(t)$ to a single point. Let the nodes of $Reeb(f,X)$ be all homologically critical points where any homology of the corresponding component of the level set $f^{-1}(t)$ changes. Then we can label every arc of $Reeb(f,X)$ with the Betti numbers $$ of the corresponding $d$-dimensional component of a level set. The homology labels give more information about the original complex $X$ than the classical Reeb graph. We describe a canonical embedding of a Reeb graph into a multi-page book (a star cross a line) and give a unique linear code of this book embedding.

Review text

The author describes an algorithm producing presentations of graph braid groups (the fundamental groups of configuration spaces associated to graphs). The paper also suggests a motion planning algorithm for many particles (robots) moving along a graph avoiding collisions; the complexity of this algorithm is linear in the number of edges and is quadratic in the number of robots. The author also shows that the 2-point braid groups associated to \textit{light} planar graphs admit presentations where all relations are commutators. A graph \(G\) is said to be \textit{light} if any cycle \(C\) of \(G\) contains an open edge \(h\) such that any cycle of \(G-\bar h\) is disjoint from \(C\).

Recommendations

• Presentations of graph braid groups.
• scientific article; zbMATH DE number 1744021
• Characteristics of graph braid groups
• Discrete Morse theory and graph braid groups.
• Planar graphs and presentations of braid groups

Cited in

(7)

• Characteristics of graph braid groups
• Geometric presentations of braid groups for particles on a graph
• Presentations of graph braid groups.
• scientific article; zbMATH DE number 1744021 (Why is no real title available?)
• Negative curvature in graph braid groups
• Extending the planar theory of anyons to quantum wire networks
• Homotopy-aware multi-agent path planning on plane

This page was built for publication: Computing braid groups of graphs with applications to robot motion planning

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