Lazy Theta*: Faster Any-Angle Path Planning (2)

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, 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 [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 vertexs 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 vertexs 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 shad 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 parentparent(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: 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 magnitudefewer 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

You must Sign up as a member of Effecthub to view the content.