Topological constraints in search-based robot path planning

There are many applications in motion planning where it is important to consider and distinguish between different topological classes of trajectories. The two important, but related, topological concepts for classifying manifolds that are of importance to us are those of homotopy and homology . In...

Full description

Saved in:
Bibliographic Details
Published in:Autonomous robots 2012-10, Vol.33 (3), p.273-290
Main Authors: Bhattacharya, S., Likhachev, M., Kumar, V.
Format: Article
Language:English
Subjects:
Artificial Intelligence
Classification
Computer Imaging
Control
Engineering
Exploration
Homology
Manifolds
Mechatronics
Pattern Recognition and Graphics
Robotics
Robotics and Automation
Robots
Topology
Trajectories
Vision
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:There are many applications in motion planning where it is important to consider and distinguish between different topological classes of trajectories. The two important, but related, topological concepts for classifying manifolds that are of importance to us are those of homotopy and homology . In this paper we consider the problem of robot exploration and planning in Euclidean configuration spaces with obstaclees to (a) identify and represent different homology classes of trajectories; (b) plan trajectories constrained to certain homology classes or avoiding specified homology classes; and (c) explore different homotopy classes of trajectories in an environment and determine the least cost trajectories in each class. We exploit theorems from complex analysis and the theory of electromagnetism to solve the problem 2-dimensional and 3-dimensional configuration spaces respectively. Finally, we describe the extension of these ideas to arbitrary D -dimensional configuration spaces. We incorporate these basic concepts to develop a practical graph-search based planning tool with theoretical guarantees by combining integration theory with search techniques, and illustrate it with several examples.
ISSN:0929-5593
1573-7527
DOI:10.1007/s10514-012-9304-1