Robot Study/Planning Algorithm

Information

I plan to study a motion planning algorithm. I will refer to the famous course from USC.

This is course information. Instructor: Professor Nora Ayanian Course: Coordinated Mobile Robotics

Reference

Book: Planning Algorithm Course: CSCI 599

Note

Week 1

Read Chapter 2

Discrete Planning

• All models are completely known and predictable
• Problem Solving and Planning are used as synonym

Introduction to Discrete Feasible Planning

Problem Formulation

• State Space Model
  • State = Distinct Situation for the world (x)
  • Set of all possible states = State space (X) -> Countable
• State Transition Equation

  x' = f(x, u)

• • x : current state
  • x': new state
  • u : each action
• Set U of all possible actions over all states

  U = set of U(x), x ∈ X

• • U(x): action space for each state x
  • For distinct x, x' ∈ X, U(x) and U(x') are not necessarily disjoint
• Xg: a set of goal states
• Formulation 2.1 = Discrete Feasible Planning

1. 1. A nonempty state space X, which is a finite or countably infinite set of states.
   2. For each state x ∈ X, a finite action space U(x).
   3. A state transition function f that produces a state f(x,u) ∈ X for every x ∈ X and u ∈ U(x). The state transition equation is derived from f as x′ =f(x,u).
   4. An initial state x1 ∈ X.
   5. A goal set Xg ⊂ X.

  => Express as a "Directed State Transition Graph"

• • • set of vertices = state space X
    • directed edge from x ∈ X to x′ ∈ X exists <=> exists an action u ∈ U(x) such that x′ = f(x,u)
    • initial state and goal set are designated as special vertices in the graph

Examples of Discrete Planning

• Moving on a 2D Grid
• Rubik’s Cube Puzzle

Back page

• Robot_Study