wavefront

Wavefront-propagation path-planner. More...

Wavefront-propagation path-planner.

The wavefront driver implements a global path planner for a planar mobile robot.

This driver works in the following way: upon receiving a new planner target, a path is planned from the robot's current pose, as reported by the underlying localize device. The waypoints in this path are handed down, in sequence, to the underlying position2d device, which should be capable of local navigation (the vfh driver is a great candidate). By tying everything together in this way, this driver offers the mythical "global goto" for your robot.

The planner first creates a configuration space of grid cells from the map that is given, treating both occupied and unknown cells as occupied. The planner assigns a cost to each of the free cells based on their distance to the nearest obstacle. The nearer the obstacle, the higher the cost. Beyond the max_radius given by the user, the cost in the c-space cells is zero.

When the planner is given a new goal, it finds a path by working its way outwards from the goal cell, assigning plan costs to the cells as it expands (like a wavefront expanding outwards in water). The plan cost in each cell is dependant on its distance from the goal, as well as the obstacle cost assigned in the configuration space step. Once the plan costs for all the cells have been evaluated, the robot can simply follow the gradient of each lowest adjacent cell all the way to the goal.

In order to function effectively with an underlying obstacle avoidance algorithm, such as Vector Field Histogram (the vfh driver), the planner only hands off waypoints, not the entire path. The wavefront planner finds the longest straight-line distances that don't cross obstacles between cells that are on the path. The endpoints of these straight lines become sequential goal locations for the underlying device driving the robot.

For help in using this driver, try the playernav utility.

Compile-time dependencies

• none

Provides

• planner

Requires

This driver controls two named position2d devices: one for input and one for output. That way you can read poses from a localization or SLAM system and send commands directly to the robot. The input and output devices may be the same.

• "input" position2d : source of current pose information (usually you would use the amcl driver)
• "output" position2d : robot to be controlled; this device must be capable of position control (usually you would use the vfh driver)
• map : the map to plan paths in

Configuration requests

• PLAYER_PLANNER_REQ_GET_WAYPOINTS

Configuration file options

Note that the various thresholds should be set to GREATER than the underlying position device; otherwise the planner could wait indefinitely for the position device to achieve a target, when the position device thinks it has already achieved it.

• safety_dist (length)
  • Default: 0.25 m
  • Don't plan a path any closer than this distance to any obstacle. Set this to be GREATER than the corresponding threshold of the underlying position device!
• max_radius (length)
  • Default: 1.0 m
  • For planning purposes, all cells that are at least this far from any obstacle are equally good (save CPU cycles).
• dist_penalty (float)
  • Default: 1.0
  • Extra cost to discourage cutting corners
• distance_epsilon (length)
  • Default: 0.5 m
  • Planar distance from the target position that will be considered acceptable. Set this to be GREATER than the corresponding threshold of the underlying position device!
• angle_epsilon (angle)
  • Default: 10 deg
  • Angular difference from target angle that will considered acceptable. Set this to be GREATER than the corresponding threshold of the underlying position device!
• replan_dist_thresh (length)
  • Default: 2.0 m
  • Change in robot's position (in localization space) that will trigger replanning. Set to -1 for no replanning (i.e, make a plan one time and then stick with it until the goal is reached). Replanning is pretty cheap computationally and can really help in dynamic environments. Note that no changes are made to the map in order to replan; support is forthcoming for explicitly replanning around obstacles that were not in the map. See also replan_min_time.
• replan_min_time (float)
  • Default: 2.0
  • Minimum time in seconds between replanning. Set to -1 for no replanning. See also replan_dist_thresh;
• cspace_file (filename)
  • Default: "player.cspace"
  • Use this file to cache the configuration space (c-space) data. At startup, if this file can be read and if the metadata (e.g., size, scale) in it matches the current map, then the c-space data is read from the file. Otherwise, the c-space data is computed. In either case, the c-space data will be cached to this file for use next time. C-space computation can be expensive and so caching can save a lot of time, especially when the planner is frequently stopped and started. This feature requires md5 hashing functions in libcrypto.
• add_rotational_waypoints (integer)
  • Default: 1
  • If non-zero, add an in-place rotational waypoint before the next waypoint if the difference between the robot's current heading and the heading to the next waypoint is greater than 45 degrees. Generally helps the low-level position controller, but sacrifices speed.
• force_map_refresh (integer)
  • Default: 0
  • If non-zero, map is updated from subscribed map device whenever new goal is set
• update_rate (integer)
  • Default: 10
  • How many times a second the driver should attempt to run its main loop

Example

This example shows how to use the wavefront driver to plan and execute paths on a laser-equipped Pioneer.

driver
(
  name "p2os"
  provides ["odometry:::position2d:0"]
  port "/dev/ttyS0"
)
driver
(
  name "sicklms200"
  provides ["laser:0"]
  port "/dev/ttyS1"
)
driver
(
  name "mapfile"
  provides ["map:0"]
  filename "mymap.pgm"
  resolution 0.1
)
driver
(
  name "amcl"
  provides ["position2d:2"]
  requires ["odometry:::position2d:1" "laser:0" "laser:::map:0"]
)
driver
(
  name "vfh"
  provides ["position2d:1"]
  requires ["position2d:0" "laser:0"]
  safety_dist 0.1
  distance_epsilon 0.3
  angle_epsilon 5
)
driver
(
  name "wavefront"
  provides ["planner:0" "offline:::planner:1"]
  requires ["output:::position2d:1" "input:::position2d:2" "map:0"]
  safety_dist 0.15
  distance_epsilon 0.5
  angle_epsilon 10
)

Author

Brian Gerkey, Andrew Howard