CS4610: Lecture 5 - Obstacle Avoidance and Local Navigation

Local Navigation and Obstacle Avoidance

• it is very practical to consider how to safely locomote in an environment with obstacles, without knowing where they are a-priori (beforehand)
  • for example, an office floor contains traversable hallways, doorways, and rooms, but also obstacles such as walls, closed doors, furniture, people, and stairwell “cliffs”
  • another example is natural terrain, which could contain hazards including large rocks, holes, cliffs, mud, sand, vegetation, etc.
• in general, traversability depends on the capabilities and scale of the robot mobility system “crusher” video
• in most cases we consider using various types of exteroceptive sensors to detect obstacles and traversable areas near the robot
  • these could include bump sensors, distance sensors, cameras, etc
  • we’ll study these kinds of sensors in more detail next time
• it is also possible, and sometimes practical, to consider how to navigate when a global map is known; we’ll study that case later in the course (global navigation)
• a large number of local navigation algorithms have been developed; here we’ll look at the details of three variants in the Bug algorithm family, which are mainly used in 2D (flat) environments, and the GESTALT algorithm used for 3D terrain on the Mars Exploration Rover

Bug1

• a simple local navigation algorithm that guarantees the goal will be reached if possible (completeness), in theory
• not necessarily optimal — there may be a shorter path
• requires: odometry (robot pose estimate in world frame); goal location (in world frame); bump sensor(s)
• algorithm:
  1. drive straight towards goal
  2. stop when an obstacle is encountered and mark that location the hit point
  3. turn left or right and follow the obstacle boundary (details of how to do this depend on the bump sensor implementation; choice of left or right does not matter)
  4. compute distance to goal at all points while traversing boundary, record point with minimum distance as leave point
  5. continue following boundary until hit point is re-encountered
  6. return (again, either clockwise or counterclockwise) to leave point
  7. goto 1
• in practice, the completeness guarantee is compromised by imperfections in sensing and control
• video

Bug2

• a variation on the basic bug algorithm often performs better in practices (i.e. finds a shorter path), but is still complete in theory
• requirements are the same as Bug1
• algorithm:
  1. mark the “M line” directly connecting the start and goal points
  2. drive straight towards the goal
  3. when an obstacle is encountered (hit point), turn left or right and follow the boundary until a leave point on the M line is reached that is closer to the goal than the hit point
  4. goto 2
• here turning left or right may make a difference in terms of total path length; without global information it is not possible to always make an optimal choice, but heruistics could be applied (e.g. choose direction that points closest towards goal)

DistBug

• another variation that maintains completeness
• this version also will terminate if the goal is not reachable (e.g. is totally surrounded by obstacles)
• additionally requires a sensor that measures free space distance from current location in the direction of the goal
• algorithm:
  1. drive straight towards goal
  2. when an obstacle is encountered (hit point), turn left or right and follow the boundary until a leave point on is reached where the goal is visible (i.e. the free space distance towards the goal is at least as large as the total distance to the goal) or there is at least some minimum distance (a configurable threshold) of free space towards goal
  3. goto 1

GESTALT

• local navigation algorithms also exist for the 3D case, i.e. where the robot may move on a non-flat terrain
• one famous example is GESTALT: Grid-based Estimation of Surface Traversability Applied to Local Terrain
  • this is the algorithm that runs on the Mars Exploration Rover (MER) vehicles Spirit and Opportunity, allowing them to drive safely among obstacles including rocks and holes
  • it is based on an earlier system developed at CMU called Morphin
• Spirit and Opportunity have six wheels and a number of stereo vision cameras which return information about nearby terrain in the form of 3D point clouds
• the rovers can drive straight or in arcs, either forward or backward
• they can also turn in place
• avaliable computation is constrained
  • the onboard processor, an R6000, is a special model that is “radiation hardened”, i.e. designed with components that resist the effect of radiation, such as cosmic rays, that are normally shielded by Earth’s atmosphere (Mars has only a very thin atmosphere)
  • an unfortunate consequence is that rad hardened processors are typically much slower than their contemporary commercial counterparts
  • available power on the rover is also a major constraint
  • it is possible to radio data to Earth for analysis, and to then radio action commands back to the rover; however the effective cycle time for these communications is about 1 day, counting not only the light-travel time (typically some minutes) but also more importantly many logistical scheduling and visibility constraints
• the overall approach of GESTALT is
  1. take a 3D picture of the terrain with a forward facing stereo camera
  2. analyze this to produce a set of 3D point samples of that terrain, and transform those to the coordinate frame of the rover
  3. using the rover’s current estimated position in a local 3D map, transform the new terrain data to the map coordinate frame
  4. (re)assign equal-sized grid cells in the map, scaled at approximately the wheel footprint size; every terrain point is assigned to one cell
  5. (re)compute average statistics of the points within each cell (called moments), and then discard the actual points
  6. (re)assign a traversability goodness rating to each cell based on how safe it would be for the rover center to be at that cell (step, roughness, pitch, border)
  7. heruistically consider a discrete set of possible forward and backward arcs; e.g. evenly sample 7 forward and 7 backward arcs relative to the current rover pose, with the arc distance set to a fraction of the rover length
  8. rate the traversability of each arc based on the goodness of the cells it intersects
  9. rate the utility of each arc for moving towards the next waypoint (i.e. the local goal point expressed in map coordinates)
  10. merge the traversability and utility ratings, and then select the highest rated arc
  11. blindly traverse the selected arc, then go to step 1
• video

• Home
• Schedule
• Assignments
• References
• Linux Notes
• Lectures
• Policies
• FAQ