Theta*: Any-Angle Path Planning for Smoother Trajectories in Continuous Environments
Alex Nash [2010]
A* is commonly used algorithm that involves searching the shortest path in a given grid. Although this works well, it has some problems, one of them is the unrealistic looking paths that it creates. This happens because it is restricted to the actual grid. There are several aesthetic optimization that can be done to the algorithm, but they can make the process slow or create a sub-optimal path.
To solve this problem, Nash developed Theta*, which considers paths that are not constrained to grid edges. The main difference is that Theta* allows the parent of a vertex to be any vertex, unlike A* where the parent must be a visible neighbor.
A* Path (Red) vs Theta* Path (Blue)They tested the Theta* algorithm with a square grid in several different maps (game-based and random) and they found that on average, the ratio of the lengths of the paths found by Theta* were 1.007 on game maps and 1.002 on random maps, which were better than the 1.04 ratio of A* paths. In other words (their own words, actually), Theta* is orders of magnitude faster than standard implementations of A* searches.
Theta* is a good alternative when A* is not enough for a realistic "shortest-path".
Nash, A. (2010, September 8). Theta*: Any-Angle Path Planning for Smoother Trajectories in Continuous Environments. Retrieved February 28, 2011, from AiGameDev.com: http://aigamedev.com/open/tutorials/theta-star-any-angle-paths/
0 comentarios:
Publicar un comentario