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

Kurlin, Vitaliy; Safi-Samghabadi, Marjan

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, October). Computing a configuration skeleton for motion planning of two round robots on a metric graph. Presented at 2014 Second RSI/ISM International Conference on Robotics and Mechatronics (ICRoM), Tehran

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 2014 Second RSI/ISM International Conference on Robotics and Mechatronics (ICRoM)
• 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.
• Public URL: https://durham-repository.worktribe.com/output/1152606
• Additional Information: October 15-17, 2014, Tehran, Iran,