Premium
On‐line algorithm for optimal 3D path planning
Author(s) -
Hun ChienWan,
Chen HunChen,
Hwang MingFung
Publication year - 2012
Publication title -
computer applications in engineering education
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.478
H-Index - 29
eISSN - 1099-0542
pISSN - 1061-3773
DOI - 10.1002/cae.20441
Subject(s) - terrain , algorithm , computer science , visibility graph , backtracking , motion planning , visibility , graph , path (computing) , point (geometry) , line segment , convergence (economics) , line (geometry) , computer vision , regular polygon , artificial intelligence , mathematics , robot , theoretical computer science , ecology , physics , geometry , optics , economics , biology , programming language , economic growth
The issues of automatic car operation aiming at in an unknown complex terrain are the most effective path planning and the obstacles avoiding in this complex terrain. For that, an on‐line algorithm for guiding a mobile object in an unexplored terrain filled with convex polygonal obstacles is presented. The mobile object was taken as a point‐size auto equipped with a sensor system, which is used to detect previously all visible parts of the obstacles surrounding it. Both the visibility and the tangent graph were modified and used in this algorithm to construct the basic concept. At each stage, the next subgoal was selected from local information provided by the sensor. Furthermore, in order to expand the algorithm to handle nonconvex polygonal obstacles and mazes, it was modified by adding backtracking and by removing visited vertices. The algorithm was implemented in MATLAB language, and several numerical examples are shown to evaluate its feasibility. Moreover, the convergence of the algorithm was examined using the visibility graph, and the performance of the algorithm was evaluated by simply comparing with other algorithms for both the length of the path and the traveling time from the initial point to the target point. © 2010 Wiley Periodicals, Inc. Comput Appl Eng Educ 20: 713–720, 2012