Lecture Slides

W5L2 - Lecture 9 - Planning.pdf

Path Planning

• Also known as the "Piano Movers Problem":
  • Finds an optimal path from start to goal states
    • path consists of successive, collision free states.

State Spaces

• State spaces are n-dimensional

• For now, we use 2D: (x, y, θ)

  <aside> 🧠

  SE(2) vs. SE(3). vs. SO(3)

  SE(2)- Special Euclidean Group in 2D.

  • It combines translations (x, y) and rotations (θ) in 2D
  • State representation: (x, y, θ)
  • This is used for 2D path planning

  ---

  SE(3) - Special Euclidean Group in 3D.

  • Combines translations and rotations in 3D space
  • Used for: drones, robotic arms, underwater robots
  • State: (x, y, z, θ, φ, ψ), this provides full 6-DOF motion
    • Position: x, y, z
    • Orientation: θ, φ, ψ (roll, pitch, yaw)

  ---

  SO(3) - Special Orthogonal Group in 3D.

  • Handles only 3D rotations. This is common in: robot arms, drone attitude control, cameras
  • For rotation-only planning (e.g., satellite orientation) Represented as:
    • 3×3 rotation matrix (R∈ℝ³ˣ³, where RRᵀ = I)
    • Quaternion (q = w, x, y, z) </aside>

What Path Planning actually does

• path planning requires
  • start state
  • goal state
  • state space
• What path planning does
  • optimizes path length
  • avoids collisions
  • make robots autonomous

Hard vs. Soft Constraints

• Hard Constraints:
  • Absolute requirements that cannot be violated
  • Physical obstacles and walls that the robot cannot pass through
  • Joint limits and kinematic constraints of the robot
  • Safety critical boundaries
• Soft Constraints:
  • Preferences that can be violated if necessary
  • Preferred distance from obstacles
  • Energy efficiency considerations
  • Smoothness of the path

When planning paths, hard constraints must always be satisfied, while soft constraints are used to optimize the quality of the solution. The planner will try to satisfy soft constraints when possible but may violate them to find a valid path that meets all hard constraints.

Global vs. Local Planning

Global Planning (High-Level Control)

Global planning generates a high-level route through the environment. Key characteristics:

• Focuses on position planning (typically without orientation)
• Implemented in ROS using nav_msgs/Path

The basic algorithm follows these steps: