Technical note | Speeding Up Phi*: Refined Foundations for Dynamic Path Planning at Any Angle

Abstract

'Any-angled' planning has emerged as a promising approach to finding short paths through a terrain that has obstacles. Phi* (2009) is the foundation of Incremental Phi* which handles terrains where obstacles are not known ahead of time and therefore have to be discovered during the path planning process (dynamic single pair shortest path). This technical note explores the following refinements to speed up Phi*: Bounds Known, Integer operations only, Expensive Last testing, Lazy evaluation and Angle Propagation. Expensive Last reduces runtime by roughly 5 percent. Expensive Last with Angle Propagation performs line-of-sight testing in constant time and reduces runtime by roughly 15–30 percent. Integer avoids floating point errors that could compromise the paths found by Phi*. The findings will be useful to developers and users of dynamic path planning algorithms in two-dimensional terrains.

Executive Summary

The work in this report is part of an investigation into a new approach to finding short paths through a terrain that has obstacles. These so-called any-angled pathfinding algorithms could be used to guide aircraft or watercraft through anti-access/area-denied environments. While the algorithms typically do not obtain the shortest (optimal) path, they can obtain good (nearoptimal) results, quite quickly, on computers that are cheap and widely available. Moreover the entry cost to learning and developing the algorithms is low: when undergraduate students first study pathfinding it is through the A* algorithm, and the first any-angled algorithm differs from A* by less than 10 lines of code. Finally the algorithms are still in their early phases of development and thus there is considerable potential for growth. The nearer term applications of any-angled path finding include algorithms for navigating entities in simulated environments, and for navigation of robotic and uninhabited vehicles.

The report focusses on improvements to the algorithm Phi*. The heritage of Phi* is as follows: A* finds a shortest path from a start to a goal through a terrain in which the obstacles are known ahead of time. The terrain is typically modelled as a two-dimensional array of cells that are either accessible or blocked as this model is supported by readily-available data sets. But the textbook application of A* under this terrain model causes ‘digitization bias’ in which the path is artificially constrained to following the edges of a cell or stepping diagonally across them. Basic Theta* introduces a clever trick that significantly reduces ‘digitization bias’ with at-most a small increase in runtime. Phi* extends from Basic Theta* by recording information so that if new obstacles are discovered then the previously-planned paths can be reused to find paths around those obstacles. The overall framework for planning the paths as the terrain changes is Incremental Phi* where Phi* is invoked whenever obstacles are discovered.

The extensions to Phi* that were explored are Bounds Known, Integer operations only, Expensive Last testing, Lazy evaluation and Angle Propagation. Prior to the investigation, each extension was hypothesized to improve the performance of Phi* but whether this was true, and the magnitude of improvement, were both unknown. The investigation found that Expensive Last reduces runtime by roughly 5 percent. Expensive Last with Angle Propagation performs line-of-sight testing in constant time and reduces runtime by roughly 15–30 percent. Integer avoids floating point errors that could compromise the paths found by Phi*.

Overall the performance gain from the proposed improvements is disappointing, and not of the magnitude that was anticipated or that would make new implementations of Phi* worthwhile. The report is being released so that the approach is documented and the results are available