A counterexample to the Alexopoulos-Griffin path planning algorithm

Robert A. Conn, Javier Elenes, Moshe Kam

Research output: Contribution to journalArticlepeer-review

Abstract

The planar stationary-obstacle path-planning problem for polygonal obstacles has been correctly and completely solved by Lozano-Perez and Wesley [3], i.e., a global, optimal algorithm was provided which requires O(μ2log μ) computation time, where μ 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(μ2) computation time [2], [5]. Our paper discusses a recent algorithm proposed by Alexopoulos and Griffin [1], called V* GRAPH, which also claims to provide an optimal solution. We demonstrate by counter-example that V* GRAPH is neither global nor optimal.

Original languageEnglish (US)
Pages (from-to)721-723
Number of pages3
JournalIEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics
Volume27
Issue number4
DOIs
StatePublished - 1997
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Software
  • Information Systems
  • Human-Computer Interaction
  • Computer Science Applications
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'A counterexample to the Alexopoulos-Griffin path planning algorithm'. Together they form a unique fingerprint.

Cite this