Stephen.woolcock

via http://www.reddit.com/

via http://www.flickr.com/photos/donsolo/2923272295/sizes/l/

(Copyright © AiGameDev.com, 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 » Click here to view this embedded content., » Click here to view this embedded content., » Click here to view this embedded content., 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.

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* » Click here to view this embedded content.» Click here to view this embedded content., 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.

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 » Click here to view this embedded content. 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, 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 line-of-sight. 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 line-of-sight to s. Unless, otherwise stated all algorithms use the straight line distances as h-values.

Lazy Theta*

Lazy Theta* is shown in Figure 4 (right)» Click here to view this embedded content. 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 » Click here to view this embedded content..

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 » Click here to view this embedded content. and from s to s' in a straight line » Click here to view this embedded content., 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) » Click here to view this embedded content. and from parent(s) to s' in a straight line » Click here to view this embedded content., 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 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 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 » Click here to view this embedded content..

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*» Click here to view this embedded content., 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, s_goal) 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 » Click here to view this embedded content..

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).

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 » Click here to view this embedded content.» Click here to view this embedded content.,» Click here to view this embedded content. 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* » Click here to view this embedded content., Block A* » Click here to view this embedded content. and Accelerated A* » Click here to view this embedded content..

If you have specific questions or comments regarding anything described in this article, please feel free to contact me.

Footnotes

^{» Click here to view this embedded content.} 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.

^{» Click here to view this embedded content.} 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
              » Click here to view this embedded content. 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
              » Click here to view this embedded content. 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
              » Click here to view this embedded content. A. Nash and S. Koenig and C. Tovey (Download PDF)
              (2010) Proceedings of the AAAI Conference on Artificial Intelligence
            

              Any-Angle Path Planning
              » Click here to view this embedded content. A. Nash (Download PDF)
              (2012) Dissertation
            

              Comparison of Different Grid Abstractions for Pathfinding on Maps
              » Click here to view this embedded content. 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
              » Click here to view this embedded content. P. Tozour
              (2004) Charles River Media, pp. 85-102
            

              Game Programming Gems: A* Aesthetic Optimizations
              » Click here to view this embedded content. S. Rabin
              (2000) Charles River Media, pp. 264-271
            

              Using Interpolation to Improve Path Planning: The Field D* Algorithm
              » Click here to view this embedded content. D. Ferguson and A. Stentz (Download FILE)
              (2006) Journal of Field Robotics, Volume 23, Issue 2, pp. 79-101
            

              Grid-Based Path-Finding
              » Click here to view this embedded content. 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
              » Click here to view this embedded content. 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
              » Click here to view this embedded content. (2000) A. Patel (View Online)
            

              Path Planning Using Lazy PRM
              » Click here to view this embedded content. 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
              » Click here to view this embedded content. 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
              » Click here to view this embedded content. R. Korf
              (1993) Journal of Artificial Intelligence
            

              Accelerated A* Path Planning
              » Click here to view this embedded content. D. Sislak and P. Volf and M. Pechoucek (Download FILE)
              (2009) Proceedings of AAMAS Conference on Autonomous Agents & Multiagent Systems