Back to search

University of Kent,

A Novel Online Any-Angle Path Planning Algorithm

Abstract

dc:description.abstract

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.

Degree

thesis:*
Name dc:type.qualificationname
phd
Level dc:type.qualificationlevel
doctoral
Grantor dc:publisher.institution
University of Kent,
Year dc:date.issued
2017

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Oprea, Paul
Advisor dc:contributor.advisor
  • Sirlantzis, Konstantinos

Subjects

dc:subject × 1

Rights

Language dc:language
en

Chain of custody

source
Harvested from
University of Kent
Base URL
kar.kent.ac.uk/cgi/oai2
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Oprea, Paul. A Novel Online Any-Angle Path Planning Algorithm. doctoral thesis, University of Kent,, 2017.