In path finding, A*like algorithms rely on a discrete navigation representation such as grids or navigation meshes [5], [6], [9], which then requires path smoothing as a postprocess. Anyangle path planning algorithms tackle both these tasks at the same time, for instance the Theta* algorithm that selectively performs lineofsight calculations while path finding. This article digs into optimizations of Theta* reducing the number of lineofsight checks required and optimizing the algorithm.
Figure 1: Grid Paths: Square Grid (left), Navigation Mesh adapted from [5] (center) and Cubic Grid (right)
Figure 2: AnyAngle Paths: Square Grid (left), Navigation Mesh adapted from [5] (center) and Cubic Grid (right)
Anyangle path planning algoirthms propagate information along graph edges (to achieve short runtimes), but do not constrain paths to be formed by graph edges (to ﬁnd short "anyangle" paths). This can be seen by comparing Figure 1, which depicts grid paths, with Figure 2, which depicts anyangle paths. One such algorithm, Theta* [1][2], that we discussed in our previous article, finds short and realistic looking paths (the author suggests you take a quick look at the Theta* article before reading this one). Theta* can be slower than A* and A* with a post processing technique because it performs a lineofsight check for each unexpanded visible neighbor of each expanded vertex. As a result, on large grids, Theta* can perform lots of lineofsight checks and lineofsight checks can be time consuming.
Figure 3: Lineofsight checks performed by Theta* (left) and Lazy Theta* (right)
Luckily, it turns out that Theta* performs more lineofsight checks than it has to. If Theta* performs a lineofsight check between a vertex s and its parent, and vertex s is never expanded, then it is wasted computation. Given that that is the case, Theta* might be a little too eager to perform linesight checks because it peforms a lineofsight check for each unexpanded visible neighbor of each expanded vertex even though many of those vertices may never be expanded. Therefore, the question is, how can Theta* take a more laid back approach to performing lineofsight checks while still finding short and realistic looking paths?
This was the topic of a recent paper [3] that I cowrote with Sven Koenig and Craig Tovey and which was presented at AAAI'10. In the paper, we presented a new anyangle path planning algorithm, called Lazy Theta*. Lazy Theta* is a variant of Theta* and thus it propagates information along graph edges (to achieve a short runtime) without constraining the paths to graph edges (to find "anyangle" paths). Like Theta*, Lazy Theta* is simple (to understand and to implement), fast and finds short and realistic looking paths. In fact, the pseudo code for Lazy Theta* has only four more lines than the pseudo code for A* (red lines in Figure 4). Lazy Theta* is faster than Theta* because it takes a much more laid back approach as to when it peforms lineofsight checks and yet it still finds short and realistic looking paths. We show experimentally that Lazy Theta* ﬁnds paths faster than Theta*, with significantly fewer lineofsightchecks than Theta* and without an increase in path length. For example, in the simple search depicted in Figure 3, both Theta* and Lazy Theta* find the same path, but Theta* performs 15 lineofsight checks while Lazy Theta* performs only 4 lineofsight checks. We also introduce Lazy Theta* with Optimizations. Lazy Theta* with Optimizations finds paths whose lengths are similar to those found by Lazy Theta*, however it often performs more than one order of magnitude fewer lineofsight checks (and vertex expansions).
For simplicity, this article will focus on square grids in which a twodimensional continuous environment is discretized into square cells that are either blocked (grey) or unblocked (white). Furthermore, we map vertices to the corners of cells as opposed to the centers of cells. Neither of these two assumptions is required for Theta*, Lazy Theta* or Lazy Theta* with Optimizations to function correctly. Our goal is to find a short and realistic looking path from the start location to the goal location (both at the corners of cells) that does not pass through blocked cells, as shown in Figure 2 (left).
We assume an eightneighbor grid throughout this article, where V is the set of all grid vertices, s_{start} in V is the start vertex of the search, and s_{goal} in V is the goal vertex of the search. c(s,s') is the straight line distance between vertices s and s', and lineofsight(s,s') is true if and only if they have lineofsight. Psuedo code for lineofsight can be found here. nghbr_{vis}(s) in V is the set of neighbors of vertex s in V that have lineofsight to s. Unless, otherwise stated all algorithms use the straight line distances as hvalues.
Lazy Theta*
Lazy Theta* is shown in Figure 4 (right)[*] along with Theta* (center) and A* (left). Our inspiration is provided by probabilistic road maps (PRMs), where lazy evaluation has been used to reduce the number of lineofsight checks (collision checks) by delaying them until they are absolutely necessary [12].
Theta* updates the gvalue and parent of an unexpanded visible neighbor s′ of a vertex s in procedure ComputeCost by considering Path 1 and Path 2:

Path 1: As done by A*, Theta* considers the path from the start vertex to s [= g(s)] and from s to s' in a straight line [= c(s,s')], resulting in a length of g(s) + c(s,s') (Line 34 (center)).

Path 2: To allow for anyangle paths, Theta* also considers the path from the start vertex to parent(s) [= g(parent(s))] and from parent(s) to s' in a straight line [= c(parent(s),s')], resulting in a length of g(parent(s)) + c(parent(s),s') if s' has lineofsight to parent(s) (Line 28 (center)). The idea behind considering Path 2 is that Path 2 is no longer than Path 1 due to the triangle inequality if s' has lineofsight to parent(s).
It considers Path 2 if s′ and parent(s) have lineofsight. Otherwise, it considers Path 1. Lazy Theta* optimistically assumes that s′ and parent(s) have lineofsight without performing a lineofsight check (Line 30 (right)). Thus, it delays the lineofsight check and considers only Path 2. This assumption may of course be incorrect (Figure 5 (right)). Therefore, Lazy Theta* performs the lineofsight check in procedure SetVertex immediately before expanding vertex s′. If s′ and parent(s′) indeed have lineofsight (Line 35 (right)), then the assumption was correct and Lazy Theta* does not change the gvalue and parent of s′. If s′ and parent(s′) do not have lineofsight, then Lazy Theta* updates the gvalue and parent of s′ according to Path 1 by considering the path from s_{start} to each expanded visible neighbor s′′ of s′ and from s′′ to s′ in a straight line and choosing the shortest such path (Lines 37 and 38 (right)). We know that s′ has at least one expanded visible neighbor because s′ was added to the open list when Lazy Theta* expanded such a neighbor.
Figure 5: Lazy Theta* updates a vertex according to Path 2 without a lineofsight check.
Figure 6: Example Trace of Lazy Theta*
Figure 6 shows a complete trace of Lazy Theta*. Each vertex is labeled with an arrow pointing to its parent vertex. The hollow red circle indicates which vertex is currently being expanded. When B3 with parent A4 is being expanded, B2 is an unexpanded visible neighbor of B3. Lazy Theta* optimistically assumes that B2 has lineofsight to A4. B2 is expanded next. Since B2 and A4 do not have lineofsight, Lazy Theta* updates the gvalue and parent of B2 according to Path 1 by considering the paths from the start vertex to B3 to each expanded visible neighbor s′′ of B2 (namely, B3) and from s′′ to B2 in a straight line. Lazy Theta* sets the parent of B2 to B3 since the path from A4 to B3 and from B3 to B2 in a straight line is the shortest such path. In this example, Lazy Theta* and Theta* ﬁnd the same path from the start vertex A4 to the goal vertex C1, but Lazy Theta* performs 4 lineofsight checks, while Theta* performs 13 lineofsight checks.
While, Lazy Theta* provides a better tradeoff with respect to path length and runtime than Theta* it can still be slower than A* with Post Smoothing because it can perform more vertex expansions and more lineofsight checks. To address this shortcoming we introduced Lazy Theta* with Optimizations. Lazy Theta* with Optimizations was covered in my dissertation [4].
Lazy Theta* with Optimizations
So far, Theta* and Lazy Theta* have used consistent hvalues (that is, hvalues that obey the triangle inequality), namely the straight line distances. A* with consistent hvalues ﬁnds paths of the same length no matter how small or large the hvalues are. A* with inconsistent hvalues is able to ﬁnd longer paths at a decrease in runtime by using weighted hvalues with weights greater than one. We therefore now discuss a variant of Lazy Theta*[**], Lazy Theta* with Optimizations, that can ﬁnd longer paths at a decrease in runtime by using weighted hvalues with weights greater than one. Lazy Theta* with Optimizations uses the hvalues h(s) = w * c(s, s_{goal}) for a given weight w > 1 and thus is similar to Weighted A*. Weighted A* with w > 1 can signiﬁcantly reduce runtimes without a signiﬁcant increase in path lengths [14].
In this section, we show that, by using weighted hvalues with weights greater than one, Lazy Theta* can ﬁnd paths faster without a signiﬁcant increase in the lengths of the resulting paths. A* searches with inconsistent hvalues typically expand fewer vertices, but often ﬁnd longer paths because every vertex omitted from a search explicitly omits a potential path. If a vertex s is not expanded during a search then a visible neighbor s′ of vertex s cannot have vertex s as its parent and thus vertex s cannot be on any path. For Lazy Theta*, the effect of not expanding a vertex during the search is different because Lazy Theta* considers both Path 1 and Path 2. If a vertex s is not expanded during a search, then a visible neighbor s′ of vertex s cannot have vertex s as its parent, but vertex s′ can still potentially have parent parent(s) (that is, the parent that vertex s would have had if vertex s had been expanded) due to Path 2. In fact, it is likely that several other vertices have parent parent(s) from which vertex s′ can inherit parent parent(s). In other words, Lazy Theta* with Optimizations may be able to find short paths while performing many fewer vertex expansions (and thus many fewer lineofsight checks).
Figure 7: Lazy Theta* with w=1 (left) and Lazy Theta* with w=1.1 (right)
Figure 7 shows an example in which Lazy Theta* with Optimizations provides a far better tradeoff with respect to path length and runtime. In Figure 7 (left), a Lazy Theta* search with w=1 was performed and a purple dot was placed on every expanded vertex. Similarly, in Figure 7 (right), a Lazy Theta* search with w=1.1 was performed and a purple dot was placed on every expanded vertex. The Lazy Theta* search with w=1 performed more than one order of magnitude more lineofsight checks AND vertex expansions than the Lazy Theta* search with w=1.1. However, the ratio of the path lengths is only 1.002 (not depicted in the figure). While there are environments, such those with a culdesac, in which the tradeoff with respect to path length and runtime is not quite as good for Lazy Theta* with Optimizations, there are many environments in which it provides an excellent tradeoff with respect to path length and runtime.
Analysis
While Theta* found paths whose lengths were nearly identical to the lengths of the truly shortest paths (see our previous article) it did so with a longer runtime than A* and A* with Post Smoothing. This was because Theta* performed both more vertex expansions and more lineofsight checks than A* and A* with Post Smoothing, respectively. To address this shortcoming we introduced Lazy Theta* and Lazy Theta* with Optimizations. We performed an extensive analysis using both small and large square grids from Bioware's popular RPG Baldur’s Gate (game maps) and square grids with given percentages of randomly blocked cells (random maps). We found that on average the ratio of the lengths of the paths found by Theta* and Lazy Theta* was 1.002 on random maps, however Lazy Theta* peformed one third the number of lineofsight checks that Theta* performed. As the number of lineofsight checks and the runtime of lineofsight checks increases so does the runtime advantage of Lazy Theta* over Theta*. For example, on 26neighbor cubic grids Lazy Theta* performs one order of magnitude fewer lineofsight checks than Theta* and can be nearly twice as fast. Lazy Theta* with Optimizations can provide and even better tradeoff with respect to the runtime of the search and the length of the resulting path. We found that on average the ratio of the lengths of the paths found by Theta* and Lazy Theta* with Optimizations was 1.006 on random maps, however Lazy Theta* with Optimizations peformed two orders of magnitude fewer lineofsight checks and more than one order of magnitude fewer vertex expansions. In fact, in certain environments, Lazy Theta* with Optimizations performed the same number of vertex expansions as A* with the octile heuristic (a version of A* that can be extremely efficient) and the same number of lineofsight checks as A* with Post Smoothing, while finding paths that were 2% shorter and more realistic looking.
Concluding Remarks
I hope this article will serve to highlight the usefulness of anyangle path planning methods for efficiently finding short and realistic looking paths. For more information on Theta*, Lazy Theta* and Lazy Theta* with Optimizations I suggest taking a look at the original papers [1][2],[3] or visiting our anyangle path planning web page. If you like Theta*, Lazy Theta* and Lazy Theta* with Optimizations, you may also like Field D* [8], Block A* [13] and Accelerated A* [15].
If you have specific questions or comments regarding anything described in this article, please feel free to contact me.
Footnotes
^{[*] }open.Insert(s,x) inserts vertex s with key x into open. open.Remove(s) removes vertex s from open. open.Pop() removes a vertex with the smallest key from open and returns it.
^{[**] }These same optimizations can be used for Theta* as well, however they are less effective because Theta* performs many more lineofsight checks per vertex expansion.
References
Theta*: AnyAngle Path Planning on Grids [1] A. Nash, K. Daniel, S. Koenig and A. Felner (Download PDF) (2007) Proceedings of the AAAI Conference on Artificial Intelligence
Theta*: AnyAngle Path Planning on Grids [2] A. Nash, K. Daniel, S. Koenig and A. Felner (Download PDF) (2010) Journal of Artificial Intelligence Research
Lazy Theta*: AnyAngle Path Planning and Path Length Analysis in 3D [3] A. Nash and S. Koenig and C. Tovey (Download PDF) (2010) Proceedings of the AAAI Conference on Artificial Intelligence
AnyAngle Path Planning [4] A. Nash (Download PDF) (2012) Dissertation
Comparison of Different Grid Abstractions for Pathfinding on Maps [5] Y. Bjornsson, M. Enzenberger, R. Holte, J. Schaeffer and P. Yap (Download PDF) (2003) Proceedings of the International Joint Conference on Artificial Intelligence
AI Game Programming Wisdom 2: Search Space Representations [6] P. Tozour (2004) Charles River Media, pp. 85102
Game Programming Gems: A* Aesthetic Optimizations [7] S. Rabin (2000) Charles River Media, pp. 264271
Using Interpolation to Improve Path Planning: The Field D* Algorithm [8] D. Ferguson and A. Stentz (Download FILE) (2006) Journal of Field Robotics, Volume 23, Issue 2, pp. 79101
GridBased PathFinding [9] P. Yap (Download FILE) (2002) Proceedings of the Canadian Conference on Artificial Intelligence, pp. 4455
Formal Basis for the Heuristic Determination of Minimum Cost Paths [10] P.E. Hart, N.J Nilsson, B. Raphael (Download FILE) (1968) IEEE Transactions on Systems Science and Cybernetics, Volume 4, Issue 2
Amit's Game Programming Information [11] (2000) A. Patel (View Online)
Path Planning Using Lazy PRM [12] R. Bohlin and L.Kavraki (Download FILE) (2000) Proceedings of the IEEE Transactions on Robotics and Automation
Block A*: DatabaseDriven Search with Applications in Anyangle PathPlanning [13] P. Yap and N. Burch and R. Holte and J. Schaeffer (Download PDF) (2011) Proceedings of the AAAI Conference on Artificial Intelligence
Linearspace bestfirst searc [14] R. Korf (1993) Journal of Artificial Intelligence
Accelerated A* Path Planning [15] D. Sislak and P. Volf and M. Pechoucek (Download FILE) (2009) Proceedings of AAMAS Conference on Autonomous Agents & Multiagent Systems
Discussion 1 Comments
I cannot decipher lines 37 and 38 of the Lazy Theta* pseudo code. What do they do? What is S'? It is not defined in that subroutine. What are min and argmin? What does the small text say? If I understand the difference between Lazy and ordinary Theta*, then Theta* always does line of sight checks for new nodes and splits a segment into two if necessary before adding it to the open set. I gather that Lazy Theta* optimistically assumes that the line of sight is unbroken for new nodes added to the open list and only checks if it necessary to split a segment when it is popped from the open set. The difference is that lazy evaluation eliminates up to 7 line of sight checks when you don't need to backtrack at a dead end. Can you explain why A* explores fewer nodes? I thought the opposite would be true because Theta*'s heuristic has less symmetry. Don't they also have the same worst case amounts? Finally, what would happen if a grid had variable travel costs? How much slower would it be to make the line drawing function return the travel cost instead of a boolean?