Path planning algorithms help robots decide how to move from a start location to a goal while avoiding obstacles. This cheat sheet summarizes the main ideas used in grid maps, graphs, and continuous spaces. Students need these tools to understand how autonomous vehicles, drones, and mobile robots choose safe and efficient routes.
It is designed as a quick reference for comparing algorithms and remembering key formulas.
Key Facts
- A path planner finds a sequence of valid states or positions from a start state to a goal state while avoiding obstacles.
- Dijkstra's algorithm expands the lowest total known cost first using g(n), where g(n) is the cost from the start node to node n.
- A* search uses f(n) = g(n) + h(n), where g(n) is cost from the start and h(n) is estimated cost to the goal.
- A heuristic h(n) is admissible if h(n) never overestimates the true remaining cost to the goal.
- On a square grid, Manhattan distance is h = abs(x2 - x1) + abs(y2 - y1) when movement is limited to four directions.
- On a plane, Euclidean distance is d = sqrt((x2 - x1)^2 + (y2 - y1)^2).
- A collision check tests whether a robot state, edge, or path segment intersects an obstacle or violates a safety clearance.
- RRT builds a tree by repeatedly sampling random points, connecting toward the sample, and keeping only collision-free extensions.
Vocabulary
- Configuration space
- The space of all possible robot positions and orientations, including which configurations are blocked by obstacles.
- Node
- A point or state in a graph that represents a possible robot position or configuration.
- Edge
- A connection between two nodes that represents a possible motion with an associated cost.
- Cost function
- A rule that assigns a numerical cost to motion, such as distance, time, energy, risk, or a weighted combination.
- Heuristic
- An estimate of the remaining cost from a current node to the goal used to guide search.
- Completeness
- A property of an algorithm that means it will find a valid path if one exists, under its stated assumptions.
Common Mistakes to Avoid
- Using a heuristic that overestimates the true cost is wrong because A* may no longer guarantee the shortest path.
- Ignoring robot size is wrong because a path that clears obstacles for a point may still cause a real robot to collide.
- Treating diagonal grid moves as cost 1 is wrong when horizontal and vertical moves also cost 1, because diagonal distance is usually sqrt(2).
- Stopping A* when the goal is first discovered is wrong because the goal must usually be selected for expansion before the optimal path is confirmed.
- Comparing algorithms only by path length is wrong because planning time, smoothness, safety margin, and dynamic obstacles can be just as important.
Practice Questions
- 1 A robot moves on a 4-direction grid from (2, 3) to (7, 11). What is the Manhattan distance heuristic h?
- 2 Find the Euclidean distance from point (1, 2) to point (5, 8), rounded to two decimal places.
- 3 In A*, a node has g(n) = 12 and h(n) = 7. What is f(n), and what does each part mean?
- 4 Why might RRT be a better choice than Dijkstra's algorithm for a robot arm moving in a high-dimensional continuous space?
Understanding Path Planning Algorithms Reference
A planner can only reason about the world through a model. In a grid model, each free square becomes a possible location and neighboring squares are connected by possible moves. The grid resolution matters.
Large squares make the search fast but can hide narrow gaps or create rough routes. Small squares give more detail but create many more nodes. For a real robot, a point on a map is not enough.
The robot has width, length, turning limits, and sometimes a direction of travel. Engineers often enlarge obstacles by the robot radius in the map. This turns the robot into a point for planning, while still leaving enough space to avoid contact.
Graph search methods differ mainly in the order they inspect choices. Dijkstra works reliably when every route cost is known, but it may spend time exploring in directions that clearly lead away from the destination. A star uses a goal estimate to focus the search.
Its estimate must match the allowed motions. Manhattan distance fits a grid with only horizontal and vertical moves. Straight line distance fits motion in any direction.
If the estimate is too optimistic, the search may examine extra nodes. If it is too large, it can choose a route that is not truly lowest cost.
A priority queue is commonly used to repeatedly select the most promising unvisited node. Students should track the cost to reach each node separately from the estimated remaining cost.
A route that looks clear between two checked points can still hit an obstacle halfway along the move. This is why collision checking applies to edges as well as locations. A simple program may test several points along each line segment.
More reliable systems use the full shape of the robot and test its swept area while it moves. Safety clearance is important because maps contain measurement error and robots do not follow commands perfectly. A shortest path that scrapes a wall is usually a poor path.
Cost functions can assign extra cost near obstacles, on steep ground, or in areas where people may walk. The result may be longer in distance but safer and easier for the robot to follow.
Rapidly exploring random trees are useful when motion has many possible positions, such as a robotic arm moving around shelves or a drone changing position in three dimensions. Each random sample pulls the tree toward a new part of the space. A collision-free connection is added, so the tree gradually spreads through reachable regions.
Random sampling can struggle with narrow doorways because few samples land in the useful opening. Sampling near the goal more often can help, though it does not guarantee the best route. The first route from a random tree is often jagged.
A later smoothing step tries to replace several short sections with one safe section. When comparing planners, pay attention to completeness, path quality, computing time, map accuracy, and the actual motion limits of the machine.