Computing a configuration skeleton for motion planning of two round robots on a metric graph

Kurlin, Vitaliy; Safi-Samghabadi, Marjan

doi:10.1109/icrom.2014.6990989

Computing a configuration skeleton for motion planning of two round robots on a metric graph

Kurlin, Vitaliy; Safi-Samghabadi, Marjan

Authors

Vitaliy Kurlin

Marjan Safi-Samghabadi

Abstract

A connected metric graph G with n vertices and without loops and multiple edges is given as an n × n-matrix whose entry aij is the length of a single edge between vertices i ≠ j. A robot in the metric graph G is the metric ball with a center x ϵ G and a radius r > 0. The configuration space OC(G, r) of 2 ordered robots in G is the set of all centers (x, y)ϵ G×G such that x, y are at least 2r away from each other. We introduce the configuration skeleton CS(G, r) ⊂ OC(G, r) that captures all connectivity information of the larger space OC(G, r). We design an algorithm of time complexity O(n2) to find all connected components of OC(G, r) that are maximal subsets of all safe positions (x, y) connectable by collision-free motions of the two round robots.

Citation

Kurlin, V., & Safi-Samghabadi, M. (2014). Computing a configuration skeleton for motion planning of two round robots on a metric graph. In International Conference on Robotics and Mechatronics Conference (ICROM 2014) : digest book : October 15-17, 2014, Khajeh Nasir Toosi University, Tehran, Iran (723-729). https://doi.org/10.1109/icrom.2014.6990989

Conference Name	2014 Second RSI/ISM International Conference on Robotics and Mechatronics (ICRoM)
Conference Location	Tehran
Acceptance Date	Aug 11, 2014
Publication Date	Oct 17, 2014
Deposit Date	Sep 18, 2015
Publicly Available Date	Sep 24, 2015
Publisher	Institute of Electrical and Electronics Engineers
Pages	723-729
Series Title	Conference Publications: Robotics and Mechatronics (ICRoM)
Book Title	International Conference on Robotics and Mechatronics Conference (ICROM 2014) : digest book : October 15-17, 2014, Khajeh Nasir Toosi University, Tehran, Iran.
DOI	https://doi.org/10.1109/icrom.2014.6990989
Keywords	Collision avoidance, Computational complexity, Graph theory, Mobile robots, Motion control.
Additional Information	October 15-17, 2014, Tehran, Iran,

Files

Accepted Conference Proceeding (314 Kb)
PDF

Copyright Statement
© 2014 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.