Search research articles

ABOUT JoVE

Overview Leadership Blog JoVE Help Center

AUTHORS

Publishing Process Editorial Board Scope & Policies Peer Review FAQ Submit

LIBRARIANS

Testimonials Subscriptions Access Resources Library Advisory Board FAQ

RESEARCH

JoVE Journal Methods Collections JoVE Encyclopedia of Experiments Archive

EDUCATION

JoVE Core JoVE Business JoVE Science Education JoVE Lab Manual Faculty Resource Center Faculty Site

Terms & Conditions of Use

Search research articles

Related Experiment Videos

A counterexample to the Alexopoulos-Griffin path planning algorithm.

R A Conn¹, J Elenes, M Kam

¹Data Fusion Lab., Drexel Univ., Philadelphia, PA.

IEEE Transactions on Systems, Man, and Cybernetics. Part B, Cybernetics : a Publication of the IEEE Systems, Man, and Cybernetics Society

|January 1, 1997

Summary

This summary is machine-generated.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by

Same author

Testosterone concentration coincides with distance travelled in the free-ranging male Saharan sand-viper, Cerastes vipera.

General and comparative endocrinology·2025

Same author

Autonomous robotic laparoscopic surgery for intestinal anastomosis.

Science robotics·2022

Same author

Semi-autonomous Robotic Anastomoses of Vaginal Cuffs Using Marker Enhanced 3D Imaging and Path Planning.

Medical image computing and computer-assisted intervention : MICCAI ... International Conference on Medical Image Computing and Computer-Assisted Intervention·2021

Same author

Supervised Autonomous Electrosurgery via Biocompatible Near-Infrared Tissue Tracking Techniques.

IEEE transactions on medical robotics and bionics·2021

Same author

The prognostic value of the fracture level in the treatment of Gartland type III supracondylar humeral fracture in children.

The bone & joint journal·2015

Same author

Dosimetric advantages and superior treatment delivery efficiency of RapidArc over conventional intensity-modulated radiotherapy in high-risk prostate cancer involving seminal vesicles and pelvic nodes.

Clinical oncology (Royal College of Radiologists (Great Britain))·2013

Same journal

Strategic Ability Updating in Concurrent Games by Coalitional Commitment.

IEEE transactions on systems, man, and cybernetics. Part B, Cybernetics : a publication of the IEEE Systems, Man, and Cybernetics Society·2015

Same journal

Meta-Analysis of the First Facial Expression Recognition Challenge.

IEEE transactions on systems, man, and cybernetics. Part B, Cybernetics : a publication of the IEEE Systems, Man, and Cybernetics Society·2012

Same journal

Adjustable model-based fusion method for multispectral and panchromatic images.

IEEE transactions on systems, man, and cybernetics. Part B, Cybernetics : a publication of the IEEE Systems, Man, and Cybernetics Society·2012

Same journal

Face Feature Weighted Fusion Based on Fuzzy Membership Degree for Video Face Recognition.

IEEE transactions on systems, man, and cybernetics. Part B, Cybernetics : a publication of the IEEE Systems, Man, and Cybernetics Society·2012

Same journal

A New Adaptive Fast Cellular Automaton Neighborhood Detection and Rule Identification Algorithm.

IEEE transactions on systems, man, and cybernetics. Part B, Cybernetics : a publication of the IEEE Systems, Man, and Cybernetics Society·2012

Same journal

Human-arm-and-hand-dynamic model with variability analyses for a stylus-based haptic interface.

IEEE transactions on systems, man, and cybernetics. Part B, Cybernetics : a publication of the IEEE Systems, Man, and Cybernetics Society·2012

See all related articles

The V*GRAPH algorithm for path planning with polygonal obstacles is neither global nor optimal, contrary to its claims. This study demonstrates its limitations through counter-examples, impacting robotic navigation research.

Area of Science:

Robotics
Computational Geometry
Artificial Intelligence

Background:

The VGRAPH algorithm provides a complete and optimal solution for planar stationary-obstacle path planning.
Existing VGRAPH variants achieve O(mu(2)) computation time for path planning.
The V*GRAPH algorithm was recently proposed, claiming optimal path planning solutions.

Purpose of the Study:

To evaluate the V*GRAPH algorithm's claims of global optimality.
To identify and demonstrate the limitations of the V*GRAPH algorithm.

Main Methods:

Analysis of the V*GRAPH algorithm's path planning methodology.
Development of counter-examples to disprove V*GRAPH's optimality and global properties.

Main Results:

Related Experiment Videos

Demonstration that V*GRAPH fails to provide a global path.
Proof that V*GRAPH does not guarantee an optimal path.
Identification of specific scenarios where V*GRAPH produces suboptimal or no paths.

Conclusions:

The V*GRAPH algorithm is not a globally optimal solution for the stationary-obstacle path-planning problem.
The findings necessitate a re-evaluation of V*GRAPH for practical applications in robotics and autonomous systems.
Further research is needed to develop or refine algorithms that guarantee global optimality in path planning.