Open AccessLate line‐of‐sight check and partially updating for faster any‐angle path planning on grid maps
Author(s) -
Zhang Changwu,
Tang Yuchen,
Liu Hengzhu
Publication year - 2019
Publication title -
electronics letters
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.375
H-Index - 146
eISSN - 1350-911X
pISSN - 0013-5194
DOI - 10.1049/el.2019.0553
Subject(s) - motion planning , path (computing) , grid , any angle path planning , successor cardinal , computer science , line (geometry) , longest path problem , shortest path problem , path length , mathematical optimization , fast path , space (punctuation) , line segment , algorithm , mathematics , artificial intelligence , theoretical computer science , robot , geometry , mathematical analysis , graph , computer network , programming language , operating system
Path planning is a classic decision problem in computer games and robotics. It is common to discretise the continuous planning space into grids with blocked cells to represent obstacles. Any‐angle path planning methods, such as Theta* and Lazy Theta*, use line‐of‐sight check (LoS‐Check) to find the nearly shortest path because the path will not be constrained to grid edges. The authors propose a new method called Late LoS‐Check A* (LLA*), which contains two parts: employing the delayed LoS‐Check to reduce the collision detection amount ( late LoS‐Check ) and partially updating the path cost of the successor vertexes based on A* ( partially updating ). The experiment results show that LLA* costs less execution time than Lazy Theta* and retains even shorter path length. Through reducing the LoS‐Check amount, the planning will be faster, but the path length will hardly be shorter. Therefore, it is the discriminatory updating strategy that makes both the path length and execution time of LLA* shorter than those of Lazy Theta*.