M3-T5 — Any-Angle and Fast Search

Learning objectives

After this lesson, you should be able to:

• Explain why grid paths zig-zag and can be longer than the straight line.
• Describe how Theta* uses line of sight to shorten paths during the search.
• Describe what jump point search prunes, and on which maps it helps.
• Explain bidirectional search, and why it cannot stop at the first meeting point.

The intuition

A grid forces the path to travel between cell centres in eight directions. Between two points in an empty room the shortest path is a straight line, but a grid path has to approximate it with a staircase of moves, and there are many staircases of the same length. A* picks one of them, and that one may zig-zag. The robot then has to follow a path with many small turns that no one needed.

The fixes come from three different questions. Could the path be straighter? Let the path join any two cells that can see each other, not only neighbours. Could the search skip most of the work? On an open grid, most of the cells A* looks at are reached by interchangeable routes: jump along a line until something interesting happens. Could we search from both ends? Two small searches that meet in the middle explore less than one big search.

The mathematics

Any-angle search: Theta*

Theta* is A* with one change in how a neighbour's parent is chosen. When the node s is expanded and a neighbour s′ is generated, A* sets parent(s′) = s. Theta* first asks whether s′ can be seen from the parent of s: if the straight segment from parent(s) to s′ crosses only free cells (a line-of-sight check), then the path can skip s.

for each neighbour s′ of s:
  if lineOfSight(parent(s), s′):
      candidate: parent(s′) = parent(s),  g = g(parent(s)) + dist(parent(s), s′)
  else:
      candidate: parent(s′) = s,          g = g(s) + dist(s, s′)
  keep the candidate if it lowers g(s′)

The cost of an edge is the straight-line distance, so paths are made of segments in any direction. Theta* does not always find the true shortest path in the plane, because it only considers parents that were expanded, but its paths are close to it and far shorter than the grid's. The line-of-sight test walks the cells under the segment (a Bresenham-style line, as in lesson M2-T4), which costs time proportional to the segment length. Lazy Theta* delays the test until a node is expanded, saving many of them. Field D* instead interpolates costs along cell edges, which also lets paths leave cells at any angle.

Fast search: jump point search

On a uniform-cost 8-connected grid, a path from a to b has many equivalent forms: moving right then diagonally gives the same cost as moving diagonally then right. A* tries all of them. Jump point search (JPS) prunes the symmetric ones: from a cell, it jumps in a direction without generating the cells in between, until it reaches the goal, a wall, or a cell with a forced neighbour, a free cell that can be reached optimally only from there. Only these jump points enter the open list. The paths JPS returns have the same cost as A*'s on the same grid, and the search can be an order of magnitude faster on open maps. It needs uniform costs: with a costmap, equal-cost routes are rare and there is nothing to prune.

Bidirectional search

Run one search from the start and one backwards from the goal, each expanding in turn, and stop when they meet. In open space the region explored by a search to distance d is a disc (or, on a 4-connected grid, a diamond) whose area grows with d². Two searches of radius d/2 cover half as much as one of radius d.

4-connected grid, open space:

The subtle part is the stopping rule. The first node reached by both searches is on a path, not necessarily the cheapest. The searches must continue until the smallest key in the forward queue plus the smallest key in the backward queue is at least the best total cost found so far. Pohl introduced the method in 1971, and later work showed it does not always win: on maps where the two search balls grow in directions that do not help each other, it can expand more nodes.

A worked example

Staircase against straight line. Take a goal 12 columns right and 5 rows up. Any path with 5 diagonal and 7 straight moves costs the same on the grid, in any order.

The most zig-zag order (as in the figure) turns ten times: the sequence R D R D R R D R D R D R changes between straight and diagonal at each boundary between runs. The straight line has no turns. If a column of cells is free along the line, Theta* finds it: when it expands the cell next to the start and generates a cell further along, the start can see that cell, so the parent becomes the start itself, and the intermediate cells drop out of the path.

What a wall does. If a wall corner sits near the line, Theta* returns a short path in two or three segments with a bend at the corner, and the segments stay one cell away from it only if the costmap inflation says so (lesson M2-T2). The line-of-sight check uses the same inflated costmap as the search, so the straight segments it accepts are those in which every cell is free for the robot's centre.

Bidirectional saving. For a route 40 steps long in an open 4-connected area, a single search expands the diamond of radius 40: 3281 cells. Two searches of radius 20 expand 2 × 841 = 1682 cells, about half. In a corridor with branches the saving can be much larger or vanish, depending on where the branches are.

Engineering implications and limitations

Do you need a shorter path or a smoother path?

Any-angle search shortens the path by up to 8% against an 8-connected grid and removes useless turns. It does not make the path smooth: the segments meet at sharp corners, and the controller still needs a smoothing step and a velocity profile (module M5). If smoothness is what you are after, smoothing a grid path afterwards may do as well, and is simple.

Line-of-sight must match the footprint

A line of sight over free cells is safe for a point robot. For a real footprint, run the check on a costmap inflated by the inscribed radius so that the centre line leaves room for the body, and reject segments that cross cells with cost 253 or more. A segment that passes through two cells touching at a corner must be rejected as well (lab M3-L3).

Pick the speed-up by map type

Measure on your maps

Published speed-ups are for particular benchmarks, usually game maps with binary obstacles. A hospital costmap with graded costs behaves differently. Count expansions and run time on your own maps before changing planner.

Common misconceptions

Engineering takeaways

1. Eight-connected grid paths are up to 8.2% longer than a straight line and can zig-zag among many equal-cost orderings.
2. Theta* lets a node take its parent's parent when the two can see each other, giving shorter and straighter paths.
3. Jump point search prunes symmetric routes on uniform-cost grids and returns the same path cost as A* with far fewer expansions.
4. Bidirectional search halves the explored area in open space but must stop only when the queue minima sum to the best cost.
5. Check line of sight against the inflated costmap, and measure every speed-up on your own maps.

References and further reading

The papers that introduced the methods in this lesson.

• A. Nash, K. Daniel, S. Koenig and A. Felner, “Theta*: Any-Angle Path Planning on Grids”, AAAI Conference on Artificial Intelligence, 2007.
• K. Daniel, A. Nash, S. Koenig and A. Felner, “Theta*: Any-Angle Path Planning on Grids”, Journal of Artificial Intelligence Research, 39, 533-579, 2010.
• D. Harabor and A. Grastien, “Online Graph Pruning for Pathfinding on Grid Maps”, AAAI Conference on Artificial Intelligence, 2011.
• I. Pohl, “Bi-directional Search”, Machine Intelligence 6, Edinburgh University Press, 127-140, 1971.
• D. Ferguson and A. Stentz, “Using Interpolation to Improve Path Planning: The Field D* Algorithm”, Journal of Field Robotics, 23(2), 79-101, 2006.

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

What’s next

Next: replanning with D* Lite and LPA*, which reuse earlier search when a door closes.

Related content

Nothing below is required to finish this lesson.

• Before
  M3-T4: Heuristics: Admissible, Consistent, Informed

  Choose Manhattan, octile or Euclidean distance for a grid, break ties well, and trade optimality for speed with weighted A*.