An efficient algorithm for finding a collision‐free path among polyhedral obstacles
Li‐Chen Fu, Dong‐Yueh Liu · Journal of Robotic Systems · 1990
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 asubvisibilitygraph using only “necessary” obstacles, i.e., excluding as many obstacles as possible whose vertices are never via points of the shortest collision‐free path.