A counterexample to the Alexopoulos-Griffin path planning algorithm.
The planar stationary-obstacle path-planning problem for polygonal obstacles has been correctly and completely solved by T. Lozano-Perez and M. Wesley (1979), i.e., a global, optimal algorithm was provided which requires O(mu(2)logmu) computation time, where mu is the number of obstacle-faces in the scene. That algorithm is known as the VGRAPH algorithm. Two variants of VGRAPH have been developed to solve the same problem in O(mu(2)) computation time. Our paper discusses a recent algorithm proposed by C. Alexopoulos and P.M. Griffin (1992), called V*GRAPH, which also claims to provide an optimal solution. We demonstrate by counter-example that V*GRAPH is neither global nor optimal.
Conn
R A
RA
Data Fusion Lab., Drexel Univ., Philadelphia, PA.
Elenes
J
J
Kam
M
M