1. 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

2. Reference

3. Note

3.1. Week 1

Read Chapter 2

3.1.1. 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. 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


5. Back page

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-16 14:07:44
Processing time 0.0223 sec