Skip to content

Planning

Planning involves determining a path from a start position to a goal position while avoiding obstacles. There are several algorithms available for this task. On this page, we will discuss two popular ones: A* (A-star) algorithm and the RRT (Rapidly-exploring Random Tree) algorithm.

Basics

Imagine you are standing in a maze and your task is to find a way out. The easiest way would be to just start walking and figure things out on the go. However, in robotics, this isn’t always efficient or safe. Instead, robots often employ a systematic strategy to navigate, using path planning algorithms.

A* Algorithm

A* is a widely used graph traversal and pathfinding algorithm that finds the path from a given initial node to a given final node while minimizing the total cost (distance plus any other costs). It uses a combination of Best First Search and Dijkstra’s algorithm.

Demo

See this Jupyter notebook for an example of A* in action:

colab

Basics of A*

  • \(g(n)\): the exact cost of the path from the starting point to any vertex \(n\).
  • \(h(n)\): the estimated cost from vertex \(n\) to the goal. This is the heuristic part of the algorithm.
  • \(f(n)\): the estimated total cost of the cheapest path from the start to the goal that goes through \(n\). It's computed as: \(f(n) = g(n) + h(n)\)

How A* works:

  1. Initialize the open list with the starting node.

  2. While the open list is not empty:

    • Find the node with the lowest \(f(n)\) in the open list.
    • Pop the node from the open list.
    • Generate the node's successors and set their parents to the current node.
    • For each successor:
      • If successor is the goal, reconstruct and return the path.
      • Else, compute its \(f(n)\) value and place it in the open list.

  3. If the open list is empty and we haven't found the goal, a path doesn't exist.

RRT Algorithm (Rapidly-exploring Random Tree)

Demo

See this Jupyter notebook for an example of RRT in action:

colab

RRT is a sampling-based method used often in high-dimensional spaces. It's particularly useful in cases where the exact representation of obstacles is unknown or hard to compute.

Basics of RRT

  1. Initialize the tree with a starting node.
  2. For a predetermined number of iterations:
    • Select a random point in the space.
    • Find the closest node in the tree to the random point.
    • Add a new node to the tree that's a set distance towards the random point from the closest node.
    • If the new node is close enough to the goal, connect it and terminate.