
Accession Number : ADA133632
Title : Hypothesizing Channels through FreeSpace 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 freespace corresponding to the classes of paths within an environment. An implementation exploiting this global model of the connectivity of freespace has been able to solve 2dimensional findpath problems in several minutes which formerly took many hours. The author's algorithm is essentially a problemsolving 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 collisionfree 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 findpath 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 ComputerAided 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