A counterexample to the Alexopoulos-Griffin path planning algorithm

Robert A. Conn; Javier Elenes; Moshe Kam

doi:10.1109/3477.604118

A counterexample to the Alexopoulos-Griffin path planning algorithm

Robert A. Conn, Javier Elenes, Moshe Kam

Research output: Contribution to journal › Article › peer-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(μ²log μ) 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(μ²) 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 language	English (US)
Pages (from-to)	721-723
Number of pages	3
Journal	IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics
Volume	27
Issue number	4
DOIs	https://doi.org/10.1109/3477.604118
State	Published - 1997
Externally published	Yes

All Science Journal Classification (ASJC) codes

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

Access to Document

10.1109/3477.604118

Cite this

@article{81b2bfec6c1f455d92c7650510f8205e,

title = "A counterexample to the Alexopoulos-Griffin path planning algorithm",

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.",

author = "Conn, {Robert A.} and Javier Elenes and Moshe Kam",

year = "1997",

doi = "10.1109/3477.604118",

language = "English (US)",

volume = "27",

pages = "721--723",

journal = "IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics",

issn = "1083-4419",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "4",

}

TY - JOUR

T1 - A counterexample to the Alexopoulos-Griffin path planning algorithm

AU - Conn, Robert A.

AU - Elenes, Javier

AU - Kam, Moshe

PY - 1997

Y1 - 1997

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0031212329&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0031212329&partnerID=8YFLogxK

U2 - 10.1109/3477.604118

DO - 10.1109/3477.604118

M3 - Article

C2 - 18255912

AN - SCOPUS:0031212329

SN - 1083-4419

VL - 27

SP - 721

EP - 723

JO - IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics

JF - IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics

IS - 4

ER -

A counterexample to the Alexopoulos-Griffin path planning algorithm

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this