Kurlin, Vitaliy ORCID: 0000-0001-5328-5351
(2012)
COMPUTING BRAID GROUPS OF GRAPHS WITH APPLICATIONS TO ROBOT MOTION PLANNING.
HOMOLOGY HOMOTOPY AND APPLICATIONS, 14 (1).
pp. 159-180.
Text
graph-braid-groups.pdf - Author Accepted Manuscript Download (449kB) |
Abstract
We design an algorithm writing down presentations of graph braid groups. Generators are represented in terms of actual motions of robots moving without collisions on a given graph. A key ingredient is a new motion planning algorithm whose complexity is linear in the number of edges and quadratic in the number of robots. The computing algorithm implies that 2-point braid groups of all light planar graphs have presentations where all relators are commutators.
Item Type: | Article |
---|---|
Additional Information: | 16 pages, 10 figures |
Uncontrolled Keywords: | graph, braid group, configuration space, fundamental group, homotopy type, deformation retraction, collision free motion, planning algorithm, complexity, robotics |
Depositing User: | Symplectic Admin |
Date Deposited: | 14 Dec 2016 16:23 |
Last Modified: | 19 Jan 2023 07:24 |
DOI: | 10.4310/HHA.2012.v14.n1.a8 |
Related URLs: | |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3004875 |