The Robotics Primer Workbook Developed by  USC, iRobot® and Microsoft® Robotics Studio

Categories: Exercise | Player Exercise | Player | Stage

Navigation:Exercise1-Path Planning

trocge

Contents 1 Occupancy Grid 2 Player and Stage Files 3 Part 1: Path Planning 4 Part 2: Path Execution

Occupancy Grid

An occupancy grid is a way of representing 2-D environments using an image. In such an image, each pixel represents a small area of the scene as observed from top down. For the purposes of this exercise, we will assume that a black square represents occupied space, and a white square represents free space. Gray squares can be used to represent space that is uncertain. The running example that we use is shown below:

To use this maze in your experiments (using a simulator), download the above file as maze.png.

Player and Stage Files

Due to the complex nature of maze construction, we will not be using the roomba to demonstrate this project. We will, instead, be using the stage simulator designed to work with player.

We use the following stage world file. This file will create a model of a pioneer robot with a sonar ring of 16 sensors arranged around the robot. It will also load the maze file as a model of the environment and put the robot at the start of the maze. Save this file as maze.world:

# the size of a pixel in Stage's underlying raytrace model in meters
resolution     0.02

interval_sim 100  # milliseconds per update step
interval_real 100 # real-time milliseconds per update step

# defines Pioneer-like robots
include "pioneer.inc" 
   
# defines 'map' object used for floorplans
include "map.inc"
     
# defines the laser model `sick_laser' configured like a Sick LMS-200
include "sick.inc" 
      
size [38 49.5]
  
gui_disable 0
gui_interval 100
gui_menu_interval 20

window( 
  size [ 800 800.000 ]  
  center [0 0 ]
  scale 0.025 
)   
          
map(      
  bitmap "maze.png" 
  map_resolution 0.123333
  size [28.5 37.15]
  name "hospital"
)

# extend the pioneer2dx definition from pioneer.inc
#

define trickedoutpioneer pioneer2dx
(
  sick_laser(
    pose [0.030 0.000 0.000 ]
    fiducialfinder( range_max 8 range_max_id 5 )

    ptz(
      blobfinder(
        channel_count 6
        channels [ "red" "blue" "green" "cyan" "yellow" "magenta" ]
      )
    )
  )

  fiducial_return 1
  gripper_return 0

  localization "gps"
  localization_origin [ 0 0 0 ]

  bumper( bcount 3
    blength 0.2
          bpose[0] [0 -0.165  90]
          bpose[1] [0  0.165 -90]
          bpose[2] [-0.26  0 0]

    blength[2] 0.1 # set the length of a single bumper

        )
)

trickedoutpioneer
(
  name "robot1"
  pose [ 0 -11.32 0 ]

)

We use the following player config file. This file starts an instance of stage, then starts a player server instance to connect to. This can be used much like the player server used on the gumstix. Save this file as maze.cfg:

driver
(
  name "stage"
  provides ["simulation:0"]
  plugin "libstageplugin"
  worldfile "maze.world"
)

driver( name "stage" provides ["map:0" ] model "hospital" )

# robot 0 
driver(
 name "stage"
 provides [ "position2d:0" "sonar:0" "laser:0" "ptz:0" "blobfinder:0" "fiducial:0" "graphics2d:0" "bumper:0" ] 
 model "robot1"
)

driver( name "vfh" requires [ "position2d:0" "laser:0" ] provides [ "position2d:1" ] )

Start player by typing:

player maze.cfg

Following that, a stage window should pop up as so:

This window shows

Part 1: Path Planning

The main novel aspect of this exercise is in planning a path through a known environment.

For this exercise, we will be using the wavefront algorithm for path planning (see wavefront lab example). The wavefront algorithm involves a breadth first search of the graph beginning at the destination point until it reaches the start point. As the search moves to a new node, the neighbors of that node are added to the search. The search terminates when one of those neighbors is the start node. Once this is complete, you can simply follow the numbers in reverse order until to reach the goal, avoiding any square that is a wall. This algorithm can work with the robot moving in only 4 directions, or diagonally as well.

The answer provided in the exercises section of the workbook code uses the planning code used in the wavefront planner driver in the player server. This is a very fast implementation of the above algorithm that also has code to do replanning as the robot moves through the scene. It is recommended that you at least look over this code to see how the wavefront algorithm can be used

Part 2: Path Execution

Executing a path is somewhat easier than planning the path, assuming we re-use some code. Let's take, for example, the obstacle avoidance example from the Behavior-Based Control section (Behavior:Exercise1-Obstacle Avoidance). In this exercise, we used behaviors to make a robot go to a goal location while avoiding obstacles. Well, since we already have the plan from Part 1 as a series of goal points, we can make a goal behavior that goes to a list of goal points instead of one single goal. Re-use the linear and angular safety behaviors that were constrcuted from before, and redesign the goal behavior to use a list of points instead of a single point.

Consider the following algorithm for this new behavior:

1. Dequeue the first item from the list of points as G
2. Set goal to the point G
3. Wait until at G
4. Repeat from (#1)