The Mobile Robot Programming Toolkit

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 CPathPlanningCircularRobot.

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 CPathPlanningCircularRobot object, setting the robot radius, and invoking CPathPlanningCircularRobot::computePath(). The following code fragment is taken from the example MRPT/samples/pathPlanning.

{syntaxhighlighter brush:cpp}
// 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"
// ....

{/syntaxhighlighter}

3. Result

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

(Click to see larger)

References

• [1] Value iteration algorithm (Wikipedia) - http://en.wikipedia.org/wiki/Markov_decision_process#Value_iteration.

‹ Obstacle avoidance up GUI windows and 3D OpenGL graphics ›