Csep-590A-Lec-6

Path Planning

• Slides link

• Inherent uncertainty, e.g.:

  • Environment
  • Execution
  • Sensing
  • Pose

• Approach

  • Deterministic planning:
    • assume some most likely env, exec, pose
    • plan a single least-cost trajectory under this assumption
    • re-plan when new info arrives
  • Planning under uncertainty:
    • Associate probabilities with the above elements
    • Plan policy for each outcome of sensing/action, minimizing cost
    • Re-plan if unaccounted events happen
    • This is much more computationally expensive.

• A * Search:

  • algorithm to return least cost path from start to goal
  • incurs the provably minimal number of state expansions required for optimality
  • however for large problems, you can run out of memory

• Weighted A * Search:

  • Weight $h$ by an $\epsilon > 1$ to expand states closer to the goal first. Solution is $\epsilon$-suboptimal but more efficient to compute.