Hypothesizing Channels through Free-Space in Solving the Findpath Problem.
MASSACHUSETTS INST OF TECH CAMBRIDGE ARTIFICIAL INTELLIGENCE LAB
Pagination or Media Count:
Channels are an encoding of free-space corresponding to the classes of paths within an environment. An implementation exploiting this global model of the connectivity of free-space has been able to solve 2-dimensional find-path problems in several minutes which formerly took many hours. The authors algorithm is essentially a problem-solving strategy using a homeomorphic reduction of the search space. Given a polyhedral environment, a technique is presented for hypothesizing a channel volume through the free space containing a class of successful collision-free paths. A set of geometric constructions between obstacle faces is proposed, and defined is a mapping from a field of view analysis to a direct local construction of free space. The algorithm has the control structure of a search which propagates construction of a connected channel towards a goal along a frontier of exterior free faces. Thus a channel volume starts out by surrounding the moving object in the initial configuration and grows towards the goal. Finally, techniques for analyzing the channel decomposition of free space and suggesting a path are shown. This paper addresses issues in the find-path or piano movers problem in robotics and spatial planning the problem involves finding a path for a solid object in an environment containing obstacles. In robotics we are typically interested in motion planning for a mobile robot or manipulator. In Computer-Aided Design, the problem of automated structural design for n structural members is also an instance of the most general form of the movers problem.
- Numerical Mathematics
- Computer Programming and Software