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.

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:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3004875