An efficient algorithm for finding a collision‐free path among polyhedral obstacles | Zendy

Fu LiChen | Zendy; Liu DongYueh | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

An efficient algorithm for finding a collision‐free path among polyhedral obstacles

Author(s) -

Fu LiChen,

Liu DongYueh

Publication year - 1990

Publication title -

journal of robotic systems

Language(s) - English

Resource type - Journals

eISSN - 1097-4563

pISSN - 0741-2223

DOI - 10.1002/rob.4620070107

Subject(s) - visibility graph , shortest path problem , graph , path (computing) , computer science , algorithm , collision , widest path problem , focus (optics) , visibility , distance , graph algorithms , bidirectional search , theoretical computer science , dijkstra's algorithm , search algorithm , mathematics , best first search , geography , regular polygon , meteorology , optics , programming language , physics , geometry , computer security , beam search

The use of graph search algorithms on a so called “visibility graph” is a common approach to finding a minimum‐distance collision‐free path among polyhedral obstacles in a 2D environment. Complexity of the search can be greatly reduced by reducing the size of the graph. The focus of this article is to provide an algorithm aimed at constructing a subvisibility graph using only “necessary” obstacles, i.e., excluding as many obstacles as possible whose vertices are never via points of the shortest collision‐free path.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research