An efficient algorithm for finding a collision‐free path among polyhedral obstacles

Abstract

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.