Key Concepts in Motion Planning Algorithms

Why This Matters

Motion planning sits at the intersection of computational geometry's most powerful ideas: space decomposition, graph search, randomized algorithms, and geometric representation. When you're tested on these concepts, you're really being asked to demonstrate understanding of how algorithms trade off completeness, optimality, and computational efficiency in geometric spaces. The choice between a graph-based method and a sampling-based method isn't arbitrary—it reflects fundamental decisions about how to represent and explore configuration space.

These algorithms appear throughout robotics, game AI, autonomous vehicles, and any system that must navigate physical or abstract spaces. You're being tested on your ability to match algorithmic approaches to problem constraints: When do you need guaranteed optimality? When is probabilistic completeness sufficient? How does dimensionality affect your choice? Don't just memorize algorithm names—know what geometric principle each one exploits and when that principle breaks down.

---

Graph-Based Search Methods

These algorithms operate on explicit graph representations of the environment, guaranteeing optimal or near-optimal paths by systematically exploring nodes. The key tradeoff is between exploration completeness and computational cost.

Dijkstra's Algorithm

• Guarantees shortest path from a source to all reachable nodes in a weighted graph—the gold standard for optimality
• Priority queue exploration processes nodes in order of cumulative cost, ensuring no shorter path exists when a node is finalized
• Complexity of $O(V^2)$ (or $O(E \log V)$ with a min-heap) makes it impractical for large state spaces without optimization

A* Search Algorithm

• Heuristic-guided search uses $f(n) = g(n) + h(n)$, combining actual cost $g(n)$ with estimated remaining cost $h(n)$
• Admissible heuristics (never overestimating) guarantee optimality while dramatically reducing explored nodes compared to Dijkstra's
• Grid and map pathfinding is the classic application—Manhattan distance or Euclidean distance heuristics guide exploration toward the goal

---

Sampling-Based Methods

When explicit graph construction is infeasible—especially in high-dimensional configuration spaces—sampling-based methods build implicit representations through random exploration. These methods offer probabilistic completeness: the probability of finding a solution approaches 1 as samples increase.

Rapidly-exploring Random Tree (RRT)

• Incremental tree construction grows from the start configuration by sampling random points and extending toward them
• Voronoi bias naturally drives exploration toward unexplored regions, making RRT excellent for high-dimensional spaces
• Real-time robotics applications benefit from RRT's ability to handle dynamic obstacles and produce feasible (though not optimal) paths quickly

Probabilistic Roadmap (PRM)

• Two-phase approach: learning phase samples and connects configurations, query phase searches the resulting roadmap
• Multi-query efficiency shines when the same environment requires planning between many different start-goal pairs
• Roadmap reusability amortizes preprocessing cost—construct once, query many times for different configurations

---

Space Decomposition Methods

These approaches simplify motion planning by partitioning the environment into geometric primitives that are easier to analyze. The fundamental insight is that complex spaces become tractable when broken into simple, well-understood regions.

Cell Decomposition

• Environment partitioning divides free space into cells (exact or approximate), reducing path planning to cell-to-cell navigation
• Adjacency graph construction connects neighboring cells, transforming geometric planning into graph search
• Preprocessing tradeoff—complex decomposition enables fast queries but requires significant upfront computation

Visibility Graph

• Obstacle vertex connections form edges wherever two vertices have unobstructed line-of-sight
• Optimal paths for polygonal obstacles follow obstacle edges, making visibility graphs ideal for 2D environments with convex polygons
• Complexity scaling of $O(n^2)$ edges for $n$ vertices becomes prohibitive in cluttered environments with many obstacles

Voronoi Diagram-based Planning

• Maximum clearance paths follow Voronoi edges, which are equidistant from nearest obstacles
• Safety-first navigation naturally avoids collisions by keeping maximum distance from all obstacles
• Construction cost can be high for complex obstacle geometries, but the resulting paths are inherently conservative

---

Force-Based and Reactive Methods

Rather than planning complete paths, these methods compute local motion decisions based on immediate environmental feedback. The geometric insight is treating navigation as gradient descent in a potential field.

Potential Field Methods

• Attractive-repulsive force model pulls the agent toward goals while pushing away from obstacles
• Gradient descent navigation follows the negative gradient of the combined potential function
• Local minima problem is the critical weakness—agents can get trapped in configurations where forces balance but the goal isn't reached

---

Foundational Representations

These aren't algorithms themselves but geometric frameworks that enable all motion planning methods. Understanding configuration space transforms physical robot motion into abstract geometric search.

Configuration Space (C-space) Representation

• Complete state encoding represents every possible robot configuration (position, orientation, joint angles) as a point in multi-dimensional space
• Obstacle transformation maps physical obstacles into C-space obstacles, where collision detection becomes point containment
• Dimensionality challenge—a robot with $n$ degrees of freedom requires $n$-dimensional C-space, making explicit representation infeasible for complex robots

---

Quick Reference Table

---

Self-Check Questions

1. Both RRT and PRM are sampling-based methods—what problem characteristic would make you choose PRM over RRT?

2. A* and Dijkstra's both guarantee optimal paths. Under what conditions does A* reduce to Dijkstra's algorithm, and why?

3. Compare and contrast Visibility Graph and Voronoi Diagram approaches: which optimizes for path length, which for safety, and what geometric structures does each exploit?

4. If a robot gets stuck while using potential field navigation, what geometric phenomenon is occurring, and what class of algorithms could provide a global solution?

5. Why does increasing the dimensionality of configuration space make cell decomposition impractical while sampling-based methods remain viable?