A* as a planning algorithm

Question

Researchers refer to A* as the planning method but: how does A* work as a path planning algorithm, instead of a graph search method? And how does it compare to RRT?

Answer 1

A* is a graph search method, so there is no real difference from the general family. It is different from the standard depth-first search and breadth-first search in that the search order differs.

How it works and how it differs from DFS and BFS becomes quite clear when looking at pseudo-code:

root_node = ...
cost = 0  # distance

target_node = ...

# a function that estimates the remaining
# distance to target_node
distance_heuristic = lambda x: ...


@dataclass(order=True)
class QueueItem:
    expected_total_cost:float
    cost_so_far:float=field(compare=False)
    node:Node=field(comare=False)
    path:List[Node]=field(compare=False)
    
# if we do pruning
visited:List[Node] = []

queue = PriorityQueue()
queue.put(QueueItem(0, cost, root_node, []))

while not queue.empty():
    item = queue.get()

    if item.node is target_node:
        break

    cost:float  # the cost of moving from node to child
    for cost, child in item.node.children:
        # sometimes we skip/prune nodes we have already seen
        if child in visited:
            continue


        child_cost_so_far = item.cost_so_far + cost
        cost_to_go = distance_heuristic(child)

        expected_total_cost = child_cost_so_far + cost_to_go

        queue.put(QueueItem(
            expected_total_cost,
            child_cost_so_far,
            child,
            path + [node])
        )

return item.cost_so_far, item.path

As you can see, this looks rather similar to a standard tree-search / graph search method. The main difference is that we introduce a distance_heuristic that gives us a hint on how far the target is. If the metric is good (e.g., if it is always exact) then we will only visit the nodes that are along a shortest path (there can be multiple) between the root and the target node (can you see why?). If the metric is inexact, i.e., it always overestimates, then we may visit more nodes than we have to, but - assuming the metric is half-decent - we will still visit fewer nodes than BFS does; especially when the graph/tree has high branching factor.

Another noteworthy aspect of the above is that your choice of cost metric + heuristic will influence the behavior of the search. In particular:

• cost(parent,child)=1 + distance_heuristic(x) = 0 --> BFS
• cost(parent,child)=0 + distance_heuristic(x) = 1/len(path) --> DFS
• cost(parent,child)=distance + distance_heuristic(x) = 0 --> Djikstra
• cost(parent,child)=distance + distance_heuristic(x) = something smart --> A*

RRT and A* are different algorithms in that RRT is a method of discretizing a continuous planning space into a tree-like structure, whereas A* is a method of searching within a graph (or tree-like structure). You could actually use A* to find a path after you have discretized your space using RRT; however, this is overkill as your structure is a tree (a special graph) and hence simpler methods to finding a shortest path exist.

Answer 2

You discretize your continuous workspace and that becomes the graph. The simplest way to do this is to put an evenly spaced grid on top of your workspace. The search graph is now a graph where grid positions are nodes and adjacent grid positions share an edge. Any graph search algorithm should work for this setting. There are various problems with this approach which is why roboticists tend to use RRT or sampling-based algorithms for path/motion planning.