PaperlayerView exact revision on arXiv

Source-linked AI summary

Theta*: Any-Angle Path Planning on Grids

Kenny Daniel, Alex Nash, Sven Koenig, Ariel Felner

arXiv:1401.3843v1cs.CGcs.AI

TL;DR

Grid-edge paths are fast but can be longer than true shortest paths because their headings are artificially constrained. The paper introduces Basic Theta* and Angle-Propagation Theta*, which retain grid-based propagation while allowing any-angle paths, and reports shorter paths than A* with post-smoothing and Field D* with runtime comparable to grid A*.

  • Problem

    Grid-edge paths can be longer than true shortest paths because their headings are artificially constrained.

  • Method

    The paper introduces Basic Theta* and Angle-Propagation Theta*, A* variants that propagate information along grid edges without constraining paths to grid edges.

  • Results

    Theta* finds shorter paths than A* with post-smoothed paths and Field D*, with runtime comparable to A* on grids.

  • Takeaways & Limitations

    Basic Theta* offers a favorable runtime–path-length tradeoff, producing paths almost as short as true shortest paths while remaining almost as fast as grid A*.

  • Takeaways & Limitations

    Basic Theta* is not guaranteed to find true shortest paths, and it can occasionally introduce unnecessary heading changes.

Abstract

from arXiv · show

Grids with blocked and unblocked cells are often used to represent terrain in robotics and video games. However, paths formed by grid edges can be longer than true shortest paths in the terrain since their headings are artificially constrained. We present two new correct and complete any-angle path-planning algorithms that avoid this shortcoming. Basic Theta* and Angle-Propagation Theta* are both variants of A* that propagate information along grid edges without constraining paths to grid edges. Basic Theta* is simple to understand and implement, fast and finds short paths. However, it is not guaranteed to find true shortest paths. Angle-Propagation Theta* achieves a better worst-case complexity per vertex expansion than Basic Theta* by propagating angle ranges when it expands vertices, but is more complex, not as fast and finds slightly longer paths. We refer to Basic Theta* and Angle-Propagation Theta* collectively as Theta*. Theta* has unique properties, which we analyze in detail. We show experimentally that it finds shorter paths than both A* with post-smoothed paths and Field D* (the only other version of A* we know of that propagates information along grid edges without constraining paths to grid edges) with a runtime comparable to that of A* on grids. Finally, we extend Theta* to grids that contain unblocked cells with non-uniform traversal costs and introduce variants of Theta* which provide different tradeoffs between path length and runtime.

1. Introduction

Grid-based path planning is fast and practical, but restricting paths to grid edges can make them longer than true shortest paths. Theta* addresses this by searching along grid edges while allowing paths with unrestricted headings.

  • Motivation: Grid paths can exceed true shortest paths because their headings are constrained to multiples of 45 degrees.Any-angle planning removes this artificial heading constraint.
  • Contribution: Basic Theta* and Angle-Propagation Theta* are correct and complete A*-based any-angle path-planning algorithms.Both propagate information along grid edges without constraining paths to grid edges.
  • Trade-offs: Basic Theta* is simple, fast, and produces short paths, but it is not guaranteed to find true shortest paths.AP Theta* instead uses angle-range propagation to obtain constant worst-case complexity per vertex expansion, at the cost of greater complexity, slower runtime, and slightly longer paths.

2. Path-Planning Problem and Notation

The paper studies path planning on eight-neighbor grids whose uniform cells are blocked or unblocked, using cell corners as vertices. A path is valid when every consecutive pair of vertices has line-of-sight under the paper’s obstacle-avoidance definition.

  • Problem setting: The problem uses eight-neighbor grids with uniform-size blocked and unblocked cells, and cell corners serve as vertices.The goal is an unblocked path between a specified start vertex and goal vertex.
  • Path validity: A path is unblocked when each vertex has line-of-sight to its successor.Line-of-sight excludes segments crossing blocked-cell interiors or passing between edge-sharing blocked cells.
  • Notation: The straight-line cost c(s, s′) is the distance between vertices, while nghbrsvis(s) contains visible neighbors in the eight compass directions.The visible-neighbor example for B4 includes A3, A4, A5, B3, B5, C3, and C4.

3. Existing Terrain Discretizations

The paper uses grids because they are simple, accessible, adaptable, and provide comprehensive terrain coverage, while alternative discretizations trade path quality, runtime, or robustness differently. Existing approaches include polygonal, hierarchical, randomized, visibility-based, and Voronoi representations.

  • Grids: Grids are simple data structures that support simple path-planning algorithms and easy terrain discretization by labeling obstructed cells as blocked.Grid resolution can be increased to improve planning precision.
  • Grids: Grids provide a comprehensive representation of traversable terrain, which supports decisions around temporary blockages in dynamic environments.Cells can also store auxiliary terrain information that is quickly accessed through random access.
  • Alternative discretizations: Polygonal discretization can find true shortest paths but may require superlinear time and space in the number of obstacle corners.The cited complexity is O(m5/3), where m is the number of corners of blocked polygons.
  • Alternative discretizations: Framed Quadtrees can produce unnecessary heading changes in free space, while Voronoi graphs can produce paths much longer than true shortest paths.These methods represent terrain differently but can compromise path quality.
  • Alternative discretizations: Probabilistic roadmaps and rapidly-exploring random trees require careful random-vertex placement because it affects runtime, path existence, and path length.Visibility graphs find true shortest paths but can have quadratically many edges and superlinear runtime.

4. Existing Path-Planning Algorithms

Existing A*-based planners trade off runtime against path length. Grid search is fast but heading-constrained; post-smoothing, Field D*, and visibility graphs relax this constraint with different guarantees and costs.

  • A* maintains g-values, h-values, f-values, parents, and open and closed lists to guide grid-based search and reconstruct paths.The f-value combines the estimated start and goal distances.
  • Grid-constrained A* is fast but can produce unrealistic paths with substantial deviations or many heading changes relative to true shortest paths.The experiments use octile distances as heuristic values.
  • A* with Post-Smoothed Paths (A* PS): A* with post-smoothing often shortens grid paths, but it is not guaranteed to find true shortest paths because search remains restricted to grid paths.Smoothing is applied after A* and increases runtime.
  • Field D* (FD*): Field D* propagates information along grid edges while allowing any-angle paths, but interpolation of perimeter g-values can misestimate true start distances.A one-step look-ahead reduces some unnecessary heading changes but does not eliminate them all.
  • A* on Visibility Graphs: Visibility-graph A* finds true shortest paths with heading changes only at blocked-cell corners, but its runtime can grow superlinearly as graph edges proliferate.The graph includes the start, goal, and corners of blocked cells.
  • Theta*: Basic Theta* is introduced as an A*-like any-angle algorithm that combines grid-edge information propagation with paths unconstrained by grid edges.Its paths are only slightly longer than true shortest paths and its runtime is only slightly slower than A* on grids.

5. Basic Theta*

Basic Theta* modifies A* to propagate information along grid edges while allowing any-angle paths, producing short paths without guaranteeing true optimality. It is correct and complete, and its parent-based updates explain both its operation and its occasional heading changes.

  • Operation of Basic Theta*: Theta* propagates information along grid edges without constraining paths to grid edges, while allowing a vertex’s parent to be any vertex.This combines the sparse connectivity of grid search with any-angle path construction.
  • Operation of Basic Theta*: Path 2 connects the parent of s directly to visible neighbor s′, enabling any-angle paths beyond A*’s Path 1 through s.Its length is g(parent(s)) + c(parent(s), s′), and the triangle inequality makes it no longer than Path 1.
  • Correctness and completeness: Basic Theta* is correct and complete: it returns only unblocked paths and finds one whenever an unblocked path exists.Parent chains remain unblocked, while every unblocked path implies an unblocked grid path that the search can use.
  • Optimality: Basic Theta* is not guaranteed to find true shortest paths because its parent candidates may exclude vertices required by an optimal path.In the cited examples, its paths are nevertheless less than a factor of 1.002 longer than true shortest paths.
  • Heading changes: Basic Theta* can produce unnecessary heading changes when expansion order prevents a later Path 2 update that would recover the true shortest path.In the example, the returned path is less than a factor of 1.027 longer than the true shortest path.

6. Angle-Propagation Theta* (AP Theta*)

AP Theta* improves Basic Theta*’s worst-case runtime per vertex expansion by propagating angle ranges that support constant-time line-of-sight checks, while retaining correctness and completeness. The tradeoff is greater complexity, slower experimental runtime, and slightly longer paths.

  • Angle-range propagation: AP Theta* reduces Basic Theta*’s worst-case runtime per vertex expansion from linear to constant by propagating angle ranges.It uses angle ranges to determine whether vertices have line-of-sight instead of performing each line-of-sight check directly.
  • Angle-range propagation: Angle ranges characterize contiguous regions with line-of-sight using lower and upper angle bounds measured from a vertex’s parent.The bounds are propagated along grid edges and calibrated relative to the parent vertex.
  • Tradeoffs: AP Theta* improves worst-case complexity but is slower and finds slightly longer paths than Basic Theta* in the experiments.The paper identifies this as the principal practical tradeoff of angle propagation.
  • Angle-range updates: AP Theta* constrains angle ranges using adjacent blocked cells and visible neighbors, sometimes conservatively when expansion order leaves insufficient information.The resulting bounds preserve the Visibility Property but can be more restrictive than necessary.
  • Angle-range updates: When a visible neighbor is evaluated, AP Theta* checks whether its heading lies within the maintained angle range instead of performing a line-of-sight call.This angle-range test is the primary algorithmic difference from Basic Theta*.
  • Properties: AP Theta* is correct and complete, but it is not guaranteed to find true shortest paths and can occasionally produce unnecessary heading changes.In one example, Basic Theta* finds the true shortest path while AP Theta* finds a longer unblocked path.

7. Experimental Results

Experiments compare Theta* variants with grid-based, smoothed, interpolated, and visibility-graph planners across random grids and game maps. Basic Theta* achieves the strongest reported runtime–path-length tradeoff, producing near-shortest paths at near-grid-A* speed.

  • Experimental setup: Experiments compare path length, vertex expansions, runtime, and heading changes across A*, Basic Theta*, AP Theta*, A* PS, FD*, and visibility-graph A*.The evaluation uses 100 × 100 and 500 × 500 random grids with different blockage rates and scaled Baldur’s Gate II maps.
  • Path length: Basic Theta* finds shorter paths than AP Theta*, FD*, A* PS, and grid A* on random 500 × 500 grids with 20 percent blocked cells in 70, 97, 94, and 99 percent of cases, respectively.The reported ordering from shortest to longest is visibility-graph A*, Basic Theta*, AP Theta*, FD*, A* PS, and grid A*.
  • Path length: Paths from Basic Theta* and AP Theta* are on average less than a factor of 1.003 longer than true shortest paths on 100 × 100 grids.This remains true despite AP Theta* sometimes constraining angle ranges more than necessary.
  • Runtime: Basic Theta* is faster than AP Theta*, A* PS, and FD* with confidence level α = 0.01, while grid A* tends to have the shortest runtime overall.Visibility-graph A* is omitted on 500 × 500 grids because its runtime is too long.
  • Overall comparison: Basic Theta* dominates AP Theta*, A* PS, and FD* in the tradeoff between runtime and path length, combining near-shortest paths with speed close to grid A*.The paper also reports that Basic Theta* is simpler to implement than AP Theta*.

8. Extensions of Theta*

The paper extends Basic Theta* to single-source planning and to grids with non-uniform traversal costs, while also examining implementation variants and their runtime–path-cost tradeoffs.

  • Single-source paths: A single-source version of Basic Theta* finds paths from one start vertex to all other vertices by terminating only when the open list is empty.This setup expands the same number of vertices for all planners, reducing the influence of heuristic values on runtime comparisons.
  • Single-source paths: Post-processing affects A* PS and FD* more than Basic Theta* and AP Theta* in single-source planning because the former require processing many extracted paths.Without post-processing, Basic Theta*’s runtime per vertex expansion is similar to A* PS and shorter than AP Theta* and FD*.
  • Non-uniform traversal costs: The non-uniform-cost extension computes path costs by splitting straight-line paths at cell boundaries and weighting each segment by its cell’s traversal cost.This adapts Basic Theta* from uniform geometric distances to traversal-cost comparisons.
  • Implementation variant: Changing one Basic Theta* comparison from strictly less than to less than or equal to slightly reduces runtime because one candidate path usually has fewer line segments to evaluate.The change concerns the relative cost of two alternative paths.
  • Non-uniform traversal costs: The non-uniform-cost experiments compare Basic Theta*, grid A*, and FD* on 1000 × 1000 grids with cell traversal costs from 1 to 15 or infinity.Finite values represent unblocked cells, while infinity represents blocked cells.

9. Trading Off Runtime and Path Length: Exploiting h-Values

Basic Theta* variants trade runtime for shorter paths by changing heuristic weights, tie-breaking, or allowing vertex re-expansions. These strategies can improve path length, but their effects differ across methods and settings.

  • Tradeoff strategies: Basic Theta* shares runtime–path-length tradeoffs with A* on grids, but its behavior can differ despite similar pseudocode.The discussed variants target shorter paths by accepting additional computation.
  • Weighted h-Values: Weights below one increase Basic Theta* expansions and can produce shorter paths, unlike A* with consistent h-values, whose path lengths remain unchanged.The weighted heuristic is h(s) = w × c(s, sgoal), with w less than one.
  • Weighted h-Values: On random 500 × 500 grids with 20 percent blocked cells, decreasing the weight reduced path length while increasing vertex expansions and runtime for Basic Theta* and AP Theta*.AP Theta* benefited more in path length because expanding more vertices can constrain its angle ranges more effectively.
  • Limits: Neither Basic Theta* nor AP Theta* is guaranteed to find true shortest paths, even when weighted heuristics use weight zero.This limits the tradeoff strategies to approximate any-angle path planning rather than guaranteed optimality.
  • Tie-breaking: Breaking ties toward smaller g-values changed Basic Theta* and AP Theta* path length, expansions, and runtime insignificantly on random 500 × 500 grids with 20 percent blocked cells.The effect is small because these algorithms have fewer equal-f-value vertices than A* on grids.
  • Vertex re-expansions: Vertex re-expansions decrease Basic Theta* path length slightly while increasing vertex expansions and runtime.Theorem 3 states that the re-expansion variant terminates and returns an unblocked path whenever one exists.

10. Trading Off Runtime and Path Length: Other Approaches

The paper explores additional Basic Theta* variants that examine more potential paths or neighbors to seek shorter routes at increased runtime. Some extensions provide little benefit, while larger branching factors offer more candidate parents.

  • Other approaches: Basic Theta* can examine parent-of-parent paths, key vertices, or more visible neighbors to trade increased runtime for potentially shorter paths.These variants expand the set of paths considered during vertex updates.
  • Three Paths: Adding a third path through a vertex’s parent’s parent does not significantly decrease path length in the reported experiments.The original algorithm already makes such a parent-of-parent line of sight unlikely.
  • Key vertices: Cached key vertices provide additional candidate routes from the start to an unexpanded vertex, addressing parent choices that may not occur on true shortest paths.The extension considers straight-line connections from cached key vertices to the target vertex.
  • Evaluation: Figure 24 evaluates Basic Theta* on random 500 × 500 grids with 20 percent blocked cells.The supplied figure label identifies the evaluation setting but does not state an outcome.
  • Branching factors: Branching factors of 4, 8, and 16 change the visible-neighbor set, with larger factors offering more potential parents at increased runtime.The paper studies this extension using grids with different numbers of neighbors.

11. Conclusions

Theta* provides correct and complete any-angle path planning by propagating information along grid edges without restricting paths to those edges. Basic Theta* is fast and simple, while AP Theta* improves worst-case expansion complexity at the cost of complexity, speed, and path length.

  • Conclusions: Basic Theta* and AP Theta* are correct and complete A* variants that find any-angle paths without constraining paths to grid edges.They propagate information along grid edges to retain short runtime.
  • Conclusions: Basic Theta* is simple, fast, and finds short paths, but it is not guaranteed to find true shortest paths.AP Theta* is more complex, slower, and finds slightly longer paths.
  • Conclusions: AP Theta* has constant worst-case complexity per vertex expansion, unlike Basic Theta*, whose worst-case complexity is linear in the number of cells.AP Theta* achieves this by propagating angle ranges when expanding vertices.
  • Comparisons: Basic Theta* dominates AP Theta*, A* PS, and FD* in runtime–path-length tradeoffs, producing paths almost as short as true shortest paths and nearly as fast as A* on grids.A* on visibility graphs finds true shortest paths but is slow.
  • Extensions and future work: The paper extends Basic Theta* to all-destination planning and grids with non-uniform traversal costs, and develops variants that trade path length against runtime.The paper also identifies future work on worst-case path-length bounds and faster AP Theta* line-of-sight checks.

Appendix A. Checking Line-of-Sight

The appendix implements line-of-sight checks by rasterizing the segment between two vertices and testing the traversed cells. Basic Theta* can perform these checks with Bresenham’s integer-based line-drawing algorithm.

  • Line-of-sight procedure: Line-of-sight checks rasterize the segment between two vertices and inspect the cells through which the line passes.The algorithm uses vertex coordinates, grid occupancy, and directional increments.
  • Implementation: The pseudocode initializes endpoints, coordinate differences, and an error term before applying directional blocked-cell tests and returning true when the segment is clear.The displayed steps include checks for blocked cells and blocked-cell boundaries.
  • Line-of-sight criterion: Two vertices have line-of-sight when none of the rasterized points corresponds to a blocked cell.The paper also allows straight lines to pass between diagonally touching blocked cells.
  • Implementation: Bresenham’s line-drawing algorithm enables fast line-of-sight checks using logical and integer operations instead of floating-point operations.Algorithm 6 provides the resulting implementation.

Appendix B. AP Theta* Returns Unblocked Paths

AP Theta* is proven never to return blocked paths by showing that its parent assignments avoid both blocked-cell interiors and forbidden passages between edge-sharing blocked cells.

  • Boundary vertices form an infinite path that repeatedly moves south or east in the relevant quadrant.The proof analyzes these vertices and their neighbors to propagate sufficient constraints through the shadow boundary.
  • A vertex is sufficiently constrained when its geometric angle relative to the blocked-cell shadow is no greater than its lower angle bound.Once sufficient constraint holds, AP Theta* operations cannot decrease the lower angle bound.
  • The proof first rules out path segments passing through the interiors of blocked cells.It uses boundary vertices and sufficient angle constraints to establish this property inductively over vertex expansions.
  • AP Theta* never returns a blocked path.A path is blocked when a segment crosses a blocked-cell interior or passes between edge-sharing blocked cells.
Loading 1401.3843v1…