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
    Commented Oct 12, 2021 at 7:15

2 Answers 2

2
$\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.

$\endgroup$
1
  • $\begingroup$ As running A* on the RRT discretized tree is mentioned, maybe RRT* should also be mentioned in the answer. $\endgroup$
    – 50k4
    Commented Nov 11, 2021 at 17:52
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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