Does any-angle mean obstacle-free?

No. Every accepted segment must satisfy the chosen collision rules.

Is Theta* a learning algorithm?

Basic Theta* is a search algorithm; it does not need model training.

Is a shorter path always faster to travel?

No. Turns, speed limits, terrain, and controller behavior can change travel time.

AI Glossary / Graphs and symbolic AI / Intermediate

Theta*

Definition

Theta* is a path-planning algorithm that searches a grid while allowing the resulting route to contain straight segments at arbitrary angles. It extends the A* search approach by checking whether a new point can connect directly to an earlier point on the route. This can avoid unnecessary bends imposed by grid edges, although Basic Theta* does not guarantee the shortest possible continuous-space path.

What it means

A grid is convenient for recording obstacles, but restricting movement to horizontal, vertical, and diagonal edges can make a route longer than necessary. A destination may lie along a clear straight line whose slope is neither zero nor one.

Theta* separates the neighborhood used to expand search from the segments used to reconstruct a route. Its search still examines nearby grid vertices, while parent links may span several cells. “Any-angle” describes these allowed segment directions; it does not mean that a moving vehicle can instantly turn through any angle.

How it works

Maintain an estimated route cost and a parent for each discovered vertex, along with an A*-style priority queue. When expanding a vertex, examine its reachable neighbors.

For a neighbor, test whether the expanded vertex's parent has unobstructed line of sight to that neighbor. If so, consider the route through that parent, bypassing the expanded vertex. Otherwise, consider the ordinary route through the expanded vertex. Update a neighbor when the candidate improves its recorded cost.

At the goal, follow parent links to recover the route. Segment legality must use the same obstacle and corner-crossing conventions as the map. The basic geometric version uses straight-line distances; different terrain costs require corresponding cost calculations and algorithmic care.

Three practical examples

1. A game character crosses an open courtyard without following a staircase-shaped sequence of grid headings. Obstacle checks still prevent its route from cutting through walls.

2. A robot simulation compares candidate routes through a static floor map. The route is subsequently checked against robot size, turning limits, and the motion controller.

3. A planning demonstration shows why two algorithms using the same occupancy grid can return different route lengths: one confines every segment to neighboring grid edges, while the other allows visible shortcuts.

Think of it this way

Think of planning a walk using a tiled floor. You can inspect nearby tile corners to understand the space without insisting that every step follow a tile edge. The analogy captures geometric freedom. It leaves out the search queue, and it does not account for a real walker's width or inability to pass through a narrow gap.

Worked example

Consider an obstacle-free unit grid. Let the start P be (0,0), the current vertex S be (1,1), and its neighbor N be (2,1). Suppose S has parent P and recorded cost g(S) = square root of 2, approximately 1.414. P has cost zero.

The route through S has candidate length g(S) + distance(S,N) = 1.414 + 1 = 2.414. A line-of-sight test from P to N succeeds because the example contains no obstacles. Connecting N directly to P gives length square root of 5, approximately 2.236. If N's previous cost is larger, the shortcut can update its parent to P and its cost to 2.236.

The local difference is approximately 0.178 distance units. This is a single update illustration, not an executed full search or a claim about average savings. It also shows why the eight-neighbor grid distance of 2.414 can overestimate the permitted any-angle distance. Straight-line distance is the appropriate lower-bound intuition for this uniform-cost example.

Now imagine a blocking region crossing segment P - N but leaving P - S and S - N clear. The shortcut is invalid even though its arithmetic length is shorter. The ordinary candidate remains available under the stated visibility conditions.

Illustrative case study

Fictional case: Birch Studio notices that simulated delivery carts zigzag through a large open loading area. Its team evaluates Theta* using a fixed collection of maps, keeping obstacle definitions and start - goal pairs identical across planners.

One attractive route clips a cart's outer edge against a shelf because the first map treated the cart as a point. The team revises the clearance representation before comparing length and planning time. It also tests whether the controller can follow the returned bends. The case illustrates why a shorter geometric path is only one part of usable navigation, without claiming a measured deployment result.

Common misconceptions and mistakes

Do not assume that inheriting ideas from A* transfers every A* optimality guarantee. Basic Theta* is not an exact continuous shortest-path solver.

Do not confuse a clear line for a point with adequate clearance for a physical object. Corner touching, obstacle boundaries, and floating-point tolerances need explicit handling.

Theta* is also different from merely smoothing an already completed A* path: shortcuts affect parent choices during search. Finally, an occupancy grid describing a static scene does not by itself resolve moving obstacles or interactions between several agents.

Business use

Evaluate Theta* when geometric route quality matters and grid-based maps are already available. Compare path length, planning latency, line-of-sight workload, and failure cases on representative layouts rather than assuming a universal advantage.

Define the downstream acceptance test before choosing a planner. A warehouse route might require clearance margins and feasible turns; a game might prioritize visual movement and frame budgets. Keep map revision and planner settings with test results so a change in obstacle interpretation is not mistaken for an algorithmic improvement.

Check your understanding

In the worked update, should the planner accept length 2.236 if the direct segment crosses an obstacle?

Answer: No. Visibility is a feasibility condition. A shorter numerical distance does not make the segment legal.

Related terms

Heuristic
Occupancy grid
Motion planning
A* search
any-angle path planning
line of sight
visibility graph
path smoothing

Learn next

Study A* and admissible heuristics next. Draw the worked coordinates and compare grid distance with Euclidean distance. Then add an obstacle and separately identify which segments are feasible and which candidate is shortest.

Euclidean distance

Sources

Primary reference: Nash, Daniel, Koenig and Felner, “Theta*: Any-Angle Path Planning on Grids,” https://idm-lab.org/bib/abstracts/papers/aaai07a.pdf. The paper was opened for grid assumptions, parent shortcuts and the lack of a shortest-path guarantee. Coordinates and the fictional case are original hand-checked illustrations.

Previous: Thesaurus (information retrieval) Next: Theta-join