Accession Number : ADA133632

Title :   Hypothesizing Channels through Free-Space in Solving the Findpath Problem.

Descriptive Note : Memorandum rept.,

Corporate Author : MASSACHUSETTS INST OF TECH CAMBRIDGE ARTIFICIAL INTELLIGENCE LAB

Personal Author(s) : Donald, Bruce R

PDF Url : ADA133632

Report Date : Jun 1983

Pagination or Media Count : 60

Abstract : 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 author's 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 mover's 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 mover's problem.

Descriptors :   *ALGORITHMS, *COMPUTER GRAPHICS, CHANNELS, PATHS, PROBLEM SOLVING, TWO DIMENSIONAL, ARTIFICIAL INTELLIGENCE, TOPOLOGY, INTERPOLATION, GEOMETRY, ROBOTICS, HEURISTIC METHODS, HYPOTHESES, COMPUTER AIDED DESIGN

Subject Categories : Numerical Mathematics
      Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE