AN EFFICIENT ALGORITHM FOR FINDING A COLLISION-FREE PATH AMONG POLYHEDRAL OBSTACLES

The use of graph search algorithms on a so called “visibility graph” is a common approach to finding a minimum‐distance collision‐free path among polyhedral obstacles in a 2D environment. Complexity of the search can be greatly reduced by reducing the size of the graph. The focus of this article is to provide an algorithm aimed at constructing a subvisibility graph using only “necessary” obstacles, i.e., excluding as many obstacles as possible whose vertices are never via points of the shortest collision‐free path. Copyright © 1990 Wiley Periodicals, Inc., A Wiley Company