Share to EffectHub.com

You can earn money or coins from your share:)

Tips: you can use Sparticle for uploading away3D effects.

Tips: you can download Sparticle for uploading effects.

Tips: The ActionScript editor is supporting Away3D, Starling, Dragonbones and Flex frameworks.

Tips: paste the web page URL then click button:)

EffectHub.com: Your Best Source for Gaming
Login    or

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

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 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 openopen.Remove(s)removes vertex s from openopen.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.

1860 views    0 comments

You must Sign up as a member of Effecthub to join the conversation.

Join Effecthub.com


Or Login with Your Email Address:

Or Sign Up with Your Email Address:
This field must contain a valid email
Password should be at least 1 character