Skip to main content

A Novel Online Any-Angle Path Planning Algorithm

Oprea, Paul (2017) A Novel Online Any-Angle Path Planning Algorithm. Doctor of Philosophy (PhD) thesis, University of Kent,. (KAR id:71757)

Language: English
Download (4MB) Preview
[thumbnail of 108thesis_Paul_Oprea.pdf]
This file may not be suitable for users of assistive technology.
Request an accessible format


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.

Item Type: Thesis (Doctor of Philosophy (PhD))
Thesis advisor: Sirlantzis, Konstantinos
Uncontrolled keywords: Any-angle path planning
Subjects: T Technology > TA Engineering (General). Civil engineering (General)
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Engineering and Digital Arts
SWORD Depositor: System Moodle
Depositing User: System Moodle
Date Deposited: 21 Jan 2019 17:10 UTC
Last Modified: 01 Apr 2022 08:35 UTC
Resource URI: (The current URI for this page, for reference purposes)
  • Depositors only (login required):


Downloads per month over past year