COMPUTING BRAID GROUPS OF GRAPHS WITH APPLICATIONS TO ROBOT MOTION PLANNING

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. ISSN 1532-0073, 1532-0081

Text graph-braid-groups.pdf - Author Accepted Manuscript Download (449kB)

Abstract

An algorithm is designed to write down presentations of graph braid groups. Generators are represented in terms of actual motions of robots moving without collisions on a given connected graph. A key ingredient is a new motion planning algorithm whose complexity is linear in the number of edges and is 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. © 2012, International Press.

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:	22 May 2026 17:23
DOI:	10.4310/HHA.2012.v14.n1.a8
Related Websites:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3004875
Disclaimer:	The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate.