2
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ You should clarify if you mean path planning or generally planning. $\endgroup$
    – 50k4
    Oct 12 at 7:15
0
$\begingroup$

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.

New contributor
FirefoxMetzger is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.