AI Notes
Learn path planning. Algorithms, obstacles, RRT. Robotics 2024.
What is Path Planning?
Path planning is the computational problem of finding a collision-free path from a start configuration to a goal configuration in a robot's workspace. It is one of the most fundamental problems in robotics—before a robot can accomplish any physical task, it must first determine how to move there safely.
The challenge extends beyond simple point-to-point navigation. Real robots have physical dimensions (they can't pass through walls), kinematic constraints (cars can't move sideways), dynamic constraints (arms have joint limits), and must plan in real-time as the environment changes. Path planning algorithms must balance optimality (shortest/fastest path), completeness (finding a path if one exists), and computational efficiency (planning fast enough to be useful).
Configuration Space
The key abstraction in path planning is configuration space (C-space):
| Configuration | Complete specification of robot's position |
| Point robot | (x, y) — 2D position |
| Mobile robot | (x, y, θ) — position + heading angle |
| Robot arm | (θ₁, θ₂, ..., θₙ) — joint angles |
| Physical robot in workspace | point in configuration space |
| Obstacles in workspace | C-space obstacles (expanded by robot shape) |
| Path planning | finding curve in free C-space |
| Example | Circular robot (radius r) in 2D |
Classical Planning Algorithms
Potential Fields
Attractive potential toward goal
U_att(q) = ½ × k_att × ||q - q_goal||²
Repulsive potential away from obstacles
U_rep(q) = ½ × k_rep × (1/d(q) - 1/d₀)² if d(q) < d₀
= 0 if d(q) ≥ d₀
Robot follows negative gradient
F(q) = -∇U(q) = F_att + F_rep
Simple implementation
while not at goal:
force = attractive_force(pos, goal) + repulsive_forces(pos, obstacles)
pos = pos + step_size × normalize(force)
Problem: Local minima! Robot can get stuck where attractive and repulsive forces balance (not at goal). Solutions: random perturbation, navigation functions, or switch to sampling-based methods.
A* on Grid/Graph
| Pros | Complete, optimal on grid, simple |
| Cons | Exponential in dimensions (curse of dimensionality) |
| 2D grid | feasible (1000×1000 = 1M cells) |
| 6D robot arm | infeasible (1000⁶ = 10¹⁸ cells!) |
Sampling-Based Planning
RRT (Rapidly-exploring Random Trees)
function RRT(start, goal, obstacles, max_iter):
tree.add(start)
for i = 1 to max_iter:
q_rand = random_configuration()
q_near = nearest_node(tree, q_rand)
q_new = extend(q_near, q_rand, step_size)
if collision_free(q_near, q_new):
tree.add_edge(q_near, q_new)
if distance(q_new, goal) < threshold:
return path(start → ... → q_new → goal)
return failure
Properties:
- Probabilistically complete (finds path eventually)
- NOT optimal (paths are jagged)
- Works in high-dimensional spaces (6+ DOF)
- Fast exploration of large spacesRRT* (Optimal RRT)
PRM (Probabilistic Roadmap)
| 1. Construction | Sample N random free configurations |
| 2. Query | Connect start and goal to roadmap |
| Best for | Multiple queries in same environment |
| Example | Robot arm in fixed workspace |
| Pre-compute roadmap | answer any reach query in milliseconds |
Motion Planning for Different Robots
Mobile Robots (Wheeled)
| Non-holonomic constraints | Car-like robots can't move sideways |
| Dubins paths | Shortest path for car (no reverse) |
| Composed of | arcs (turn left/right) + straight lines |
| Optimal path | always one of 6 patterns (LSL, RSR, LSR, RSL, RLR, LRL) |
| Reeds-Shepp paths | Allow forward and reverse |
| More options | shorter paths through tight spaces |
Robot Arms (Manipulators)
| Inverse kinematics | Given desired end-effector pose, |
| Minimize | time, energy, jerk (smoothness) |
| Subject to | joint limits, velocity limits, collision avoidance |
| Methods | CHOMP, TrajOpt, STOMP |
Drones (Aerial Robots)
Dynamic Path Planning
| D* (Dynamic A*) | Incrementally repairs path when costs change |
| Velocity obstacles | Plan in position-velocity space |
| Receding horizon | Plan short segment, execute, replan |
Interview Questions
Q: Why are sampling-based methods preferred for high-dimensional planning? A: Grid-based methods scale exponentially with dimensions (O(n^d) cells). A 6-DOF arm with 360° per joint at 1° resolution needs 360⁶ ≈ 2×10¹⁵ cells—impossible. Sampling-based methods (RRT, PRM) explore C-space without exhaustive discretization, scaling gracefully to high dimensions while probabilistically guaranteeing completeness.
Q: What is the difference between path planning and motion planning? A: Path planning finds a geometric curve (sequence of configurations) from start to goal. Motion planning adds time—it assigns velocities and timings to the path, respecting dynamic constraints (acceleration limits, motor torques). A path says WHERE to go; a motion plan says HOW FAST to go there.
Q: How do self-driving cars plan paths in real-time? A: They use a hierarchical approach: (1) Route planning (A* on road graph, seconds-scale), (2) Behavior planning (state machine: follow lane, change lane, stop—sub-second), (3) Motion planning (generate candidate trajectories as polynomials, evaluate cost functions, select best—50-100ms). The hierarchy ensures fast response while considering long-term goals.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Path Planning - Robot Navigation.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Artificial Intelligence topic.
Search Terms
artificial-intelligence, artificial intelligence, artificial, intelligence, robotics, path, planning, path planning - robot navigation
Related Artificial Intelligence Topics