CS4610/CS5335: L5 - 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

• origial paper: Lumelsky and Stepanov, “Path-planning strategies for a point mobile automaton moving amidst unknown obstacles of arbitrary shape”, 1987
• a simple local navigation algorithm that guarantees the goal will be reached if possible (completeness), in theory
• if the goal cannot be reached, the algorithm will terminate
• 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, stop if the goal is reached
  2.  stop when an obstacle is encountered and mark that location the *hit point*
  3.  turn left or right and follow the obstacle boundary
  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.  if driving towards goal would lead to immediate collision with obstacle, abort
  8.  goto 1

• choice of left or right turn does not matter, since obstacle will be completely circumnavigated in any case
• details of precisely how to make the turn depend on the bump sensor and mobility system implementations
• in practice, the completeness guarantee is compromised by imperfections in sensing and control

• video

Bug2

• same original paper as Bug1
• a variation on the basic bug algorithm often performs better in practice (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, stop if the goal is reached
  3.  stop when an obstacle is encountered and mark that location the *hit point*
  4.  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
  5.  if the most recent hit point is reached again without finding a new leave point, abort
  6.  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 (optional)

• original paper: Kamon and Rivlin, “Sensory-based motion planning with global proofs”, 1997
• mostly the same requirements as Bug1, but additionally requires a sensor that measures free space distance from current location in the direction of the goal
• also complete in theory, and may perform better than Bug2

• algorithm:

  1.  drive straight towards goal, stop if the goal is reached
  2.  stop when an obstacle is encountered and mark that location the *hit point*;
      also mark a (modified from Bug2) *M line* from the hit point to the goal
  3.  turn left or right and follow the boundary, keeping track of the *closest point*
      to the goal so far along this obstacle, until a *leave point* is reached
      where any of the following hold (check them in order)
      a.   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)
      b.   the total distance to the goal minus the free space towards the goal is
           less than or equal to the distance from the closest point to the goal
           so far along this obstacle minus a minimum step distance; i.e.
           if the robot were to leave from this point, it could get at least
           the minimum step distance to the goal, and it could also get at least
           as close to the goal as it would if it had left from any point yet
           encountered on this obstacle
      c.   a point on the M line is reached that is closer to the goal than the hit point
  4.  goto 1

• the first leave condition can enable driving towards the goal sooner than e.g. would happen in Bug2
• the second leave condition helps ensure forward progress when the goal is not visible from any point on the current obstacle boundary
  • the minimum step distance constraint is to improve immunity to sensor noise — the obstace will be left only if significant progress can be made
  • tracking the closest point to the goal along the obstacle ensures that the next hit point will not be a point already traversed on this obstacle (and thus potentially causing an infinite loop)
  • TBD diagram showing radii (mindist-step) and (dist-free) from goal

• the third leave condition ensures completeness in case neither of the first two leave conditions ever triggers

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; 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
• Lectures
• Policies
• OHMM Wiki
• Piazza