Backtrack router

This router shall find the farthest route possible beginning at sampling point Start.

Basically, it does so by successively routing from one sampling point to the next with its underlying candidate_router.

But if it at any point is not able to find a valid navigation route, it is able to go back to previous sampling points in history (up to the configured maximum, maxCandidateBacktrackingDistance) and re-route from other candidates. That means it tries out other routes that were not considered optimal in the first place.

If it is able to route farther, the backtracking is considered successful and it continues as usual. It then may start a new backtracking session, if necessary.

When backtracking is not successful, the router returns the route before the last backtracking session has begun.

Example

In this example the driver takes a freeway exit ramp, but the GPS tracker has poor signal and does not catch the turn fast enough. As a consequence the best candidates are sitting next to the main freeway lane, as illustrated below.

Freeway exit ramp example

Fig. 25 Freeway exit ramp example

As a consequence the routers will route on the main freeway lane and will not be able to continue at some point. Then backtracking starts.

Needs backtracking

Fig. 26 Needs backtracking

While backtracking, already passed sampling points are considered again while choosing different candidates. In the following three images we see the algorithm going back and trying out other candidates.

Backtracking trial 1 failed

Fig. 27 Backtracking trial 1 failed

Backtracking trial 2 failed

Fig. 28 Backtracking trial 2 failed

Backtracking trial 3 failed

Fig. 29 Backtracking trial 3 failed

As you see in the next image, the router finally finds a valid navigation route by choosing a different candidate for the southernmost sampling point.

Backtracking successful

Fig. 30 Backtracking successful

In this simple example, the router has found a route by just trying out the next best candidate for the previous sampling points.

Here are some not yet mentioned features:

  • While backtracking, the router may go back beyond already backtracked passages, but will not try out already visited routes.

  • While backtracking, the router may go back beyond the Start sampling point.

  • It may go beyond skipped sampling points (we will discuss this later in Skip router).

  • It may not go beyond the current route (which could be in the middle of the track, we will discuss this later in Piecewise router).