Open Tutorial
lazy_trace

Lazy Theta*: Faster Any-Angle Path Planning

Alex J. Champandard on July 16, 2013

This article was written by Alex Nash, a software engineer at Northrop Grumman with a Ph.D. from the University of Southern California, specializing in path planning for video games and robotics. You can contact him by email <alexwnash at gmail.com>.

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 post-process. Any-angle path planning algorithms tackle both these tasks at the same time, for instance the Theta* algorithm that selectively performs line-of-sight calculations while path finding. This article digs into optimizations of Theta* reducing the number of line-of-sight checks required and optimizing the algorithm.

Grid Paths

Figure 1: Grid Paths: Square Grid (left), Navigation Mesh adapted from [5] (center) and Cubic Grid (right)

Any-Angle Paths

Figure 2: Any-Angle Paths: Square Grid (left), Navigation Mesh adapted from [5] (center) and Cubic Grid (right)

Any-angle path planning algoirthms propagate information along graph edges (to achieve short runtimes), but do not constrain paths to be formed by graph edges (to find short "any-angle" paths). This can be seen by comparing Figure 1, which depicts grid paths, with Figure 2, which depicts any-angle 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 line-of-sight check for each unexpanded visible neighbor of each expanded vertex. As a result, on large grids, Theta* can perform lots of line-of-sight checks and line-of-sight checks can be time consuming.

Many Line-of-sight Checks

Figure 3: Line-of-sight checks performed by Theta* (left) and Lazy Theta* (right)

Luckily, it turns out that Theta* performs more line-of-sight checks than it has to. If Theta* performs a line-of-sight 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 line-sight checks because it peforms a line-of-sight 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 line-of-sight checks while still finding short and realistic looking paths?

This was the topic of a recent paper [3] that I co-wrote with Sven Koenig and Craig Tovey and which was presented at AAAI'10. In the paper, we presented a new any-angle 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 "any-angle" 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 line-of-sight checks and yet it still finds short and realistic looking paths. We show experimentally that Lazy Theta* finds paths faster than Theta*, with significantly fewer line-of-sight-checks 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 line-of-sight checks while Lazy Theta* performs only 4 line-of-sight 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 line-of-sight checks (and vertex expansions).

For simplicity, this article will focus on square grids in which a two-dimensional 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 eight-neighbor grid throughout this article, where V is the set of all grid vertices, sstart in V is the start vertex of the search, and sgoal 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 line-of-sight. Psuedo code for lineofsight can be found here. nghbrvis(s) in V is the set of neighbors of vertex s in V that have line-of-sight to s. Unless, otherwise stated all algorithms use the straight line distances as h-values.

Lazy Theta*

Lazy Theta* psuedo code

Figure 4: Pseudo Code of A* (left), Theta* (center) and Lazy Theta* (right)

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 line-of-sight checks (collision checks) by delaying them until they are absolutely necessary [12].

Theta* updates the g-value 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 any-angle 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 line-of-sight 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 line-of-sight to parent(s).

It considers Path 2 if s′ and parent(s) have line-of-sight. Otherwise, it considers Path 1. Lazy Theta* optimistically assumes that s′ and parent(s) have line-of-sight without performing a line-of-sight check (Line 30 (right)). Thus, it delays the line-of-sight check and considers only Path 2. This assumption may of course be incorrect (Figure 5 (right)). Therefore, Lazy Theta* performs the line-of-sight check in procedure SetVertex immediately before expanding vertex s′. If s′ and parent(s′) indeed have line-of-sight (Line 35 (right)), then the assumption was correct and Lazy Theta* does not change the g-value and parent of s′. If s′ and parent(s′) do not have line-of-sight, then Lazy Theta* updates the g-value and parent of s′ according to Path 1 by considering the path from sstart 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.

Lazy Theta* example

Figure 5: Lazy Theta* updates a vertex according to Path 2 without a line-of-sight check.

Lazy Theta* trace 1

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 line-of-sight to A4. B2 is expanded next. Since B2 and A4 do not have line-of-sight, Lazy Theta* updates the g-value 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* find the same path from the start vertex A4 to the goal vertex C1, but Lazy Theta* performs 4 line-of-sight checks, while Theta* performs 13 line-of-sight 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 line-of-sight 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 h-values (that is, h-values that obey the triangle inequality), namely the straight line distances. A* with consistent h-values finds paths of the same length no matter how small or large the h-values are. A* with inconsistent h-values is able to find longer paths at a decrease in runtime by using weighted h-values with weights greater than one. We therefore now discuss a variant of Lazy Theta*[**], Lazy Theta* with Optimizations, that can find longer paths at a decrease in runtime by using weighted h-values with weights greater than one. Lazy Theta* with Optimizations uses the h-values h(s) = w * c(s, sgoal) for a given weight w > 1 and thus is similar to Weighted A*. Weighted A* with w > 1 can significantly reduce runtimes without a significant increase in path lengths [14].

In this section, we show that, by using weighted h-values with weights greater than one, Lazy Theta* can find paths faster without a significant increase in the lengths of the resulting paths. A* searches with inconsistent h-values typically expand fewer vertices, but often find 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 line-of-sight checks).

Lazy Theta* Optimizations

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 line-of-sight 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 cul-de-sac, 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 line-of-sight 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 line-of-sight checks that Theta* performed. As the number of line-of-sight checks and the runtime of line-of-sight checks increases so does the runtime advantage of Lazy Theta* over Theta*. For example, on 26-neighbor cubic grids Lazy Theta* performs one order of magnitude fewer line-of-sight 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 line-of-sight 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 line-of-sight 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 any-angle 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 any-angle 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 line-of-sight checks per vertex expansion.

References

              Theta*: Any-Angle 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*: Any-Angle Path Planning on Grids
              [2] A. Nash, K. Daniel, S. Koenig and A. Felner (Download PDF)
              (2010) Journal of Artificial Intelligence Research
            
              Lazy Theta*: Any-Angle 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
            
              Any-Angle 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. 85-102
            
              Game Programming Gems: A* Aesthetic Optimizations
              [7] S. Rabin
              (2000) Charles River Media, pp. 264-271
            
              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. 79-101
            
              Grid-Based Path-Finding
              [9] P. Yap (Download FILE)
              (2002) Proceedings of the Canadian Conference on Artificial Intelligence, pp. 44-55
            
              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*: Database-Driven Search with Applications in Any-angle Path-Planning
              [13] P. Yap and N. Burch and R. Holte and J. Schaeffer (Download PDF)
              (2011) Proceedings of the AAAI Conference on Artificial Intelligence
            
              Linear-space best-first 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

cc_f9909 on July 19th, 2013

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?

If you'd like to add a comment or question on this page, simply log-in to the site. You can create an account from the sign-up page if necessary... It takes less than a minute!