A Novel Online Any-Angle Path Planning Algorithm

Any-angle path planning algorithms are a popular topic of research in the fields of robotics and video games with a key focus in finding true shortest paths. Most online grid-constrained path-planning algorithms find suboptimal solutions that present as unrealistic paths, a shortcoming which the any-angle class of algorithms attempt to address. While they do provide improvements in finding shorter paths, it generally comes in the form of a trade-off, by sacrificing runtime performance. The lack of a robust solution, that does not compromise on any of the desirable properties – online, reduced search-space, low runtime, short paths – of an any-angle path-planning algorithm, is a prime motivator for the current research. A novel any-angle algorithm for 2-dimensional uniform-cost octile grids is introduced that operates purely online and reduces the search-space and runtime without sacrificing path-length. The methodology presents an atypical any-angle path-planning algorithm which employs a best first search that races individual paths towards a target with a free-space assumption. The paths exhibit bug-like properties in that they either move towards a target or wall-follow, but are allowed to terminate early. Wall following determines points on the boundary that are candidate heading changes in the path. At each step, the path is analysed and pruned in order to maintain its tautness at all times. Together with a purely heuristic cost based on the assumption of free-space between heading changes, the algorithm drives the search towards expanding the most promising path first. Once a path has reached the goal, it checks the free-space assumption between its heading changes and updates its cost accordingly. The shortest-path is determined when the cost estimate of any remaining paths is longer than the solution path. The proposed algorithm is shown experimentally to be competitive on a number of performance metrics with state-of-the-art any-angle algorithms. It also presents desirable properties that allow it to have a reduced search space and make it suitable for providing multiple solutions.