Theta Star Planner

name: theta-star-planner description: 'Configure Nav2 Theta* planner. Use when generating any-angle smooth paths with line-of-sight optimization.'

Theta* Planner

Plugin

nav2_theta_star_planner::ThetaStarPlanner

Algorithm

Theta* is an any-angle path planning algorithm that extends A* with line-of-sight checks. In standard A*, paths are constrained to grid edges (4 or 8-connected neighbors), producing staircase-like paths on diagonal trajectories. Theta* removes this constraint: when a cell expansion occurs, it checks whether the parent of the current node has direct line-of-sight to the neighbor being expanded. If so, it updates the neighbor's parent to skip intermediate nodes, producing straighter paths with fewer unnecessary turns.

How Line-of-Sight Works

During expansion of node s:

1. For each neighbor s' of s, compute the tentative cost through s (standard A*).
2. Also check: does parent(s) have line-of-sight to s'? (Bresenham line check through the costmap.)
3. If yes, and if the path parent(s) → s' is cheaper than s → s', set parent(s') = parent(s).

This simple modification produces dramatically straighter paths because the planner can "see through" multiple cells at once.

Compared to A*

A* path (8-connected):        Theta* path:
  S─┐                          S
    └─┐                         \
      └─┐                        \
        └─G                       G

The A* path follows grid edges step by step. The Theta* path takes a direct diagonal if the line of sight is clear.

Key Parameters

Cost Function

The total cost for reaching a cell is:

f(s) = g(s) + h(s)
g(s) = parent_cost + w_euc_cost * euclidean_distance + w_traversal_cost * costmap_cost
h(s) = w_euc_cost * euclidean_distance_to_goal

Tuning w_euc_cost vs w_traversal_cost:

• w_euc_cost = 1.0, w_traversal_cost = 2.0 (default): Good balance. Paths avoid high-cost areas while remaining reasonably short.
• Increase w_traversal_cost to 5.0+: Paths strongly avoid costmap obstacles (stay far from walls), at the cost of longer paths.
• Increase w_euc_cost to 3.0+: Paths prioritize shortness over obstacle avoidance. May cut closer to walls.
• Both high: Slower planning (higher heuristic values cause more expansions).

Complete YAML Configuration

planner_server:
  ros__parameters:
    expected_planner_frequency: 20.0
    planner_plugins: ["GridBased"]
    GridBased:
      plugin: "nav2_theta_star_planner::ThetaStarPlanner"
      how_many_corners: 8
      w_euc_cost: 1.0
      w_traversal_cost: 2.0
      terminal_checking_interval: 5000
      allow_unknown: true

When To Use

Good fit:

• Want straighter paths than NavFn or SMAC 2D without the computational cost of Hybrid-A*.
• Indoor environments with open areas where diagonal and straight-line paths are natural.
• Robot kinematic constraints are handled by the controller, not the planner.
• Environments where grid-aligned staircase paths cause unnecessary controller oscillation.

Poor fit:

• Robots with non-holonomic constraints where kinematically feasible paths from the planner matter (use Hybrid-A*).
• Very cluttered environments where line-of-sight checks rarely succeed (Theta* degrades to A* with extra overhead).
• When you need guaranteed smoothness — Theta* paths have fewer turns but can still have abrupt direction changes at obstacle edges.

Comparison with Other Planners

Theta* sits between the simplicity of NavFn and the sophistication of SMAC Hybrid-A*. It produces naturally smoother paths without requiring a separate smoother, while remaining in the 2D planning space.

Path Smoothing

Theta* paths are smoother by construction than grid-based planners, but they still consist of straight-line segments with angular discontinuities. For additional smoothness, you can add the smoother server:

smoother_server:
  ros__parameters:
    smoother_plugins: ["simple_smoother"]
    simple_smoother:
      plugin: "nav2_smoother::SimpleSmoother"
      tolerance: 1.0e-10
      max_its: 1000
      do_refinement: true

However, the benefit of a separate smoother is less pronounced with Theta* than with NavFn because the line-of-sight shortcuts already eliminate most unnecessary turns.

Troubleshooting

• Paths still look grid-aligned: Check that how_many_corners: 8 is set. With how_many_corners: 4, line-of-sight checks are limited to cardinal directions.
• Planner is slower than expected: In very cluttered environments, most line-of-sight checks fail, adding overhead without benefit. Consider SMAC 2D or NavFn for such cases.
• Paths cut too close to obstacles: Increase w_traversal_cost to penalize cells near obstacles more. Or increase the costmap inflation radius.
• Planning fails for reachable goals: Check allow_unknown and ensure the goal isn't inside an inflated obstacle. The planner has no explicit tolerance parameter like NavFn — the goal cell itself must be reachable.
• Angular discontinuities at obstacle corners: This is inherent to Theta*. The path connects straight segments at obstacle edges. Use a downstream smoother if the controller struggles with sharp turns.

Implementation Notes

The line-of-sight check uses a Bresenham-like line drawing algorithm through the costmap. If any cell along the line has cost ≥ LETHAL_OBSTACLE, line-of-sight is blocked. This means inflated costs do NOT block line-of-sight — only lethal cells do. The cost of traversing through inflated cells is still accumulated in the path cost via w_traversal_cost.