Path Planner

Sven Köhler
Maze.jpg (78299 bytes)

Path Planner

The Path planner is the object that plans a series of moves to get from one position to another. In order to calculate a path, obviously it needs to know data about the environment, via map data. One other important aspect it needs to know is which types of moves a given vehicle can make. The reason is because some vehicles can negotiate sharper turns than others, as shown in the map below. Once it has map data and vehicle constraints, it performs some sort of search algorithm to find the shortest route.

There are many different ways the PathPlanner can "ask" which moves a vehicle can make:

  • By checking which interfaces the MoveController implements (currently this is how our API "asks" what moves a MoveController can make)
  • By explicitly asking which moves the vehicle can make via a get method in MoveController (perhaps something to consider for post 1.0 architecture)

The PathPlanner can return a path as an ordered collection of Points/Poses. Lawrie has been calling these way-points.

Example of Turning Radius Differences

The turning radius of a vehicle affects the paths that a Path planner can plan for it. Consider the following example which shows a maze with tight corridors that are about the same width as the vehicle. A vehicle with a zero turn radius (all differential vehicles) can easily navigate through the tight maze to find the shortest path from start to end. However, a steering vehicle starting at the same Pose can't turn sharp enough, so the shortest path is around the maze using a series of moves (arcs and straight lines) from point to point, shown in red below.

Notes on Requirements

The path formulated by the PathPlanner (composed of points connected by moves) is only valid if the vehicle can drive each segment perfectly. However, no vehicle can drive a move perfectly to a point, nor will the estimate of Pose be perfect. Therefore it is important that the path planning can reevaluate and adjust after each move, or evaluate and adjust constantly while on the move. This means it should seek out each Point/Pose, and then once it gets there reevaluate the next move required to get to the next Pose from the current Pose. For example, if it overshoots P3, the move it previously had in mind is no longer valid. To get to P4, it will need to recalculate the move required, meaning perhaps it will need to have a shorter move, or it may need to arc slightly to get back into the proper direction/heading. So the Poses/Points remain valid for a calculated path, but the Moves between points are not always going to be valid.

There are two different data sets PathPlanner can pass to a PoseController (aka Navigator):

  • Points/Poses AND the Moves in between
  • Only Points/Poses

So the question is, how can we get our movement to "recalibrate" at each new Point (i.e. avoid building up error by attempting one move after another)? The problem is that the PoseController doesn't have access to map data, so it can't really tell on its own that it should drive an arc around a corner to get to the second point. So I believe the PathPlanner must pass both Points/Poses and Moves. However, when driving straight segments (see map above) it would be perfectly valid to ask the PoseController to drive straight from one point to another because a straight segment should not encounter any major obstacles, therefore it does not require map data.

So it appears that number 1. above is appropriate, and that PathPlanner should pass both waypoints and move data. Only the arc moves will be used in practice, however, and the straight segments can be generated by PoseController.

Steering requirements

When steering vehicles negotiate turns (arcs) they may need to adjust while the turn is in motion, either steering sharper or wider. If the PathPlanner always plans a path using minRadius turns then it will leave no room for making sharper adjustments. It might be beneficial for the PathPlanner to plan paths for steering vehicles that allow some room for adjustment.


NXT Wiki: Movement feedback mechanism
NXT Wiki: Queued Navigation Architecture

Get latest updates about Open Source Projects, Conferences and News.

Sign up for the SourceForge newsletter:

JavaScript is required for this form.

No, thanks