7.2 Sampling-based and optimization-based planning methods

Sampling-based and optimization-based planning methods are two key approaches in robotics. Sampling methods randomly explore the configuration space, building graphs or trees without explicit obstacle representation. Optimization methods formulate planning as a mathematical problem, finding optimal solutions with explicit obstacle representation.

Sampling-based methods like PRMs and RRTs are probabilistically complete and efficient in high-dimensional spaces. Optimization-based methods, including gradient descent and convex optimization, produce smooth, optimal trajectories and easily incorporate dynamic constraints. Each approach has unique strengths and limitations in robotic path planning.

Sampling-Based and Optimization-Based Planning Methods

Sampling vs optimization planning methods

• Sampling-based methods randomly explore configuration space building graph or tree structures without explicit obstacle representation (PRMs, RRTs)
• Optimization-based methods formulate planning as mathematical optimization problem finding optimal solutions often requiring explicit obstacle representation (gradient descent, convex optimization)

Principles of sampling-based planning

• Probabilistic Roadmaps (PRM)
  • Sampling phase randomly generates free space configurations connecting nearby ones with local planners
  • Query phase connects start and goal to roadmap searching for path using graph algorithms (A*, Dijkstra's)
• Rapidly-exploring Random Trees (RRT)
  • Incremental tree growth starts from initial configuration iteratively expanding towards random samples
  • Biased exploration tends to explore large unexplored areas efficiently
  • Variants include RRT-Connect growing trees from both start and goal and RRT* providing asymptotic optimality

Concepts in optimization-based planning

• Gradient descent iteratively optimizes by following negative gradient of objective function for local optimization
• Convex optimization solves problems with convex objective function and constraints guaranteeing global optimum if exists
• Trajectory optimization represents path as waypoint sequence minimizing cost function (smoothness, obstacle avoidance)
• Model Predictive Control (MPC) uses receding horizon planning optimizing short time horizons executing first control input then replanning

Comparison of planning method applications

• Sampling-based advantages
  • Probabilistically complete ensuring solution if one exists
  • Efficient in high-dimensional spaces (robotic arms, multi-robot systems)
  • Handle complex geometric constraints well (narrow passages, cluttered environments)
• Sampling-based limitations
  • May produce non-optimal paths requiring post-processing
  • Performance degrades in narrow passages needing specialized sampling strategies
  • Difficulty incorporating dynamic constraints (velocity limits, acceleration bounds)
• Optimization-based advantages
  • Produce smooth optimal trajectories considering multiple objectives
  • Easily incorporate dynamic constraints (joint limits, energy consumption)
  • Handle time-varying objectives and constraints (moving obstacles, changing goals)
• Optimization-based limitations
  • May get stuck in local optima requiring multiple initializations
  • Computationally expensive for complex problems with many variables
  • Sensitive to initial conditions affecting solution quality