A voronoi diagram‐visibility graph‐potential field compound algorithm for robot path planning
Ellips Masehian, Mohammad Reza Amin‐Naseri · Journal of Robotic Systems · 2004
Abstract Numerous methods have been developed to solve the motion planning problem, among which the Voronoi diagram, visibility graph, and potential fields are well‐known techniques. In this paper, a new path planning algorithm is presented where these three methods are integrated for the first time in a single architecture. After constructing the generalized Voronoi diagram of C‐space, we introduce a novel procedure for its abstraction, producing apruned generalized Voronoi diagram. A broad freeway net is then developed through a new α‐MID(maximal inscribed discs) concept. A potential function is assigned to the net to form an obstacle‐free network of valleys. Afterwards we take advantage of a bidirectional search, where the visibility graph and potential field modules execute alternately from both start and goal configurations. Asteepest descent mildest ascentsearch technique is used for local planning and avoiding local minima. The algorithm provides a parametric tradeoff between safest and shortest paths and generally yields shorter paths than the Voronoi and potential field methods, and faster than the visibility graph. It also performs well in complicated environments. © 2004 Wiley Periodicals, Inc.