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

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.

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

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.

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 Koenigand 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 Vis 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*

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) tos' in a straight line [= c(parent(s),s')], resulting in a length ofg(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 toparent(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 neighbors′′ 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 5: Lazy Theta* updates a vertex according to Path 2 without a line-of-sight check.

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

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