Path planning with occupancy grid maps

Contents

1. Description

The basic value iteration [1] algorithm for searching shortest paths is implemented in the MRPT for occupancy grids, and circular robots, in the class mrpt::nav::PlannerSimple2D.

The method comprises two steps:

  • Growth of the obstacles by the robot radius. This assure that just one single free cell is enough for the robot to move without collision.
  • The value iteration algorithm, starting at the source position, increase iteratively the area covered by shortest paths until the target cell is reached.

Note that this is a very simple method, not suitable for robots with shapes very different from circular and/or moving in cluttered environmnets. For those cases, see the obstacle avoidance methods.

 

 

2. Usage

The basic usage requires declaring the gridmap, the mrpt::nav::PlannerSimple2D object, setting the robot radius, and invoking mrpt::nav::PlannerSimple2D::computePath(). The following code fragment is taken from the example MRPT/samples/pathPlanning.

// Load,create,... the grid map:
COccupancyGridMap2D gridmap;
// ...

// Find path:
CPathPlanningCircularRobot pathPlanning;
pathPlanning.robotRadius = 0.30f;

std::deque
thePath;
bool notFound;

CPoint2D origin( 20, -110 );
CPoint2D target( 90, 40 );

pathPlanning.computePath( &gridmap, &origin, &target, thePath, notFound, 100.0f /* Max. distance */ );

// Process the output path in "thePath"
// ....

 

 

3. Result

Click on the thumb to see full-resolution image. This is the output from the example pathPlanning:

Circular_path_planning

References