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?