# 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):

# Report Date:

## 1983-06-01

# Pagination or Media Count:

## 60.0

# 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 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.

# Descriptors:

# Subject Categories:

- Numerical Mathematics
- Computer Programming and Software