What is it about?
Path planning is an interesting problem in computer games and robotics. It is common to discretize the continuous planning space into grids with blocked cells to represent obstacles. However, the path based on grids will be constrained to the grid edges, which is not the truly shortest path. Line-of-sight check (LoS-Check) is an efficient method to relax the constraint of grid edges via checking whether there is a straight line between two non-adjacent vertexes. If the shortcut exists, the updated path will be shorter according to the triangle inequality. We present Late LoS-Check A* (LLA*), which further delays the LoS-Check and updates the g values of different successors with discriminatory principles.
Featured Image
Photo by Curtis MacNewton on Unsplash
Why is it important?
Line-of-sight check (LoS-Check) is effective in any-angle path planning, but too much check will slow down the planning speed. Late LoS-Check can speed up the planning and partially updating can propagate the optimal direction for the planning process. The experiments show that Late LoS-Check A* (LLA*) can generates shorter paths with less time.
Perspectives
We hope that the delayed LoS-Check and discriminatory updating policy will give more inspirations to those who are researching on the path planning.
Changwu Zhang
National University of Defense Technology
Read the Original
This page is a summary of: Late Line-of-Sight Check and Partially Updating for Faster Any-Angle Path Planning on Grid Maps, Electronics Letters, March 2019, the Institution of Engineering and Technology (the IET),
DOI: 10.1049/el.2019.0553.
You can read the full text:
Contributors
The following have contributed to this page
