UP | HOME

Belief State Planner

The belief state planner is a method for planning in the maze where the robot keeps track of all possible positions that it could be in, and narrows those positions down through movement. When the robot is given a movement command that is not possible, the robot remains in it's current position.

Setup

  1. The robot can initially be anywhere in the maze
bstate1.svg
Figure 1: The Goal is the red square. The robot (purple circle) can be anywhere. Obstacles are Black, free space is white.

Move North

  1. The robot is commanded to move North.
  2. The locations where the robot could be have been narrowed down.
bstate2.svg
Figure 2: State after the first step.

Move North

  1. The robot is commanded to move North.
  2. The locations where the robot could be have been narrowed down.
bstate3.svg
Figure 3: State after second step to the North

Move North

  1. The robot is commanded to move North.
  2. The locations where the robot could be have been narrowed down.
bstate4.svg
Figure 4: State after third step to the North

Move North

  1. The robot is commanded to move North.
  2. The locations where the robot can be are not narrowed down. Try a new direction
bstate4.svg
Figure 5: State after third step to the North

Move East

  1. The robot is commanded to move East.
  2. The locations where the robot could be have been narrowed down.
bstate5.svg
Figure 6: State after a step to the East.

Move North

  1. The robot is commanded to move North.
  2. The locations where the robot can be are not narrowed down. Try a new direction.
bstate6.svg
Figure 7: State after third step to the North

Move North

  1. The robot is commanded to move North.
  2. The locations where the robot can be are not narrowed down. Try a new direction.
bstate7.svg
Figure 8: State after third step to the North

Move North

  1. The robot is commanded to move North.
  2. The locations where the robot can be are not narrowed down. Try a new direction.
bstate8.svg
Figure 9: State after third step to the North

Continue Moving

  1. In this scenario, the robot will enter a cycle:
    • Move North
    • Notice no change in possible locations
    • Move East, narrow down locations by one spot
  2. Eventually there will be two locations for the robot
bstate9.svg
Figure 10: State after several North and East Movements

More Movement

  1. Continue issuing movements, while avoiding visited states, until there is only one possible robot location.
  2. Once the robot is in a single location, another planning method can be used.

Author: Matthew Elwin.