Path planning and the topology of configuration space
Date
1994
Authors
Maciejewski, Anthony A., author
Fox, John J., author
IEEE, publisher
Journal Title
Journal ISSN
Volume Title
Abstract
This work considers the path planning problem for planar revolute manipulators operating in a workspace of polygonal obstacles. This problem is solved by determining the topological characteristics of obstacles in configuration space, thereby determining where feasible paths can be found. A collision-free path is then calculated by using the mathematical description of the boundaries of only those configuration space obstacles with which collisions are possible. The key to this technique is a simple test for determining whether two disjoint obstacles are connected in configuration space. This test allows the path planner to restrict its calculations to regions in which collision-free paths are guaranteed a priori, thus avoiding unnecessary computations and resulting in an efficient implementation. Typical timing results for environments consisting of four polyhedral obstacles comprising a total of 27 vertices are of the order of 22 ms on a SPARC-IPC workstation.
Description
Rights Access
Subject
manipulators
path planning
topology