Faster route: part 1

[VysotskiVadim]

Description

This PR introduces experimental "faster route" feature. For the first step I handled a case when the SDK receives an alternative which is faster than primary route, the SDK suggests the alternative as a faster route. But the SDK shouldn't suggest faster alternative if it's very similar to the alternative that was already rejected.

Test case

I used route from Munich to Nuremberg for testing. You will find recorded routes update with this route in unit tests.

You have two options: via Ingolstadt (faster) and Regensburg (slower).

If user picks the slower route via Regensburg and passes the fork point, the Navigation SDK generates a new alternative: turn around and go to the Nuremberg via Ingolstard, which is faster than primary route and has new alternative id.

The new alternative has a very similar geometry, so FasterRouteTracker rejects it as very similar to existing alternative.

Next steps

I won't handle all the cases in this PR because I prefer moving with small steps. I'm going to handle following things in the upcoming PRs:

1. ETA changes caused by route refresh. In theory, if traffic changes, rejected alternative can become even faster so it makes sense to suggest them again.

Routs similarity

I considered a few ways to calculate how similar routes are.

1. Calculate overlap of their geometry (the one I use in the PR)
2. Compare Route leg object summary using levinstein distance (iOS uses this)
3. Compare Route leg object summary, but parsing it and find shared roads names

I tested 3 of them.

I didn't like calculating Levinstein distance between leg's summaries like iOS does. For example if one route has "Maddison Avenue" the other has "Maddison Garden" their leveinstein distance is 6, what makes them pretty similar despite the fact that they're not. I liked the result of comparing parsed summary + looking for how many roads name they have in common. See calculateDescriptionSimilarity. The problem is that Directions API doesn't guarantee stability of summary, it's design to be read by humans. So I ended up comparing geometries.

Note for reviewers

The faster route feature isn't as clean as the rest of the SDK. But TBH I don't see much value in keeping experimental feature super clean as I don't know yet if we need it in the future. We will try to use it and then decide if it makes sense to have it at all. But if you see something very dirty that you won't accept even in experimental features, please comment and I will fix it.

[codecov[bot]]

Codecov Report

Merging #6434 (8ad9c71) into main (a72f9ce) will increase coverage by 0.00%. The diff coverage is 69.46%.

:exclamation: Current head 8ad9c71 differs from pull request most recent head 8feade5. Consider uploading reports for the commit 8feade5 to get more accurate results

@@            Coverage Diff             @@
##               main    #6434    +/-   ##
==========================================
  Coverage     69.30%   69.30%            
- Complexity     4718     4752    +34     
==========================================
  Files           702      710     +8     
  Lines         27704    27966   +262     
  Branches       3269     3295    +26     
==========================================
+ Hits          19199    19381   +182     
- Misses         7216     7290    +74     
- Partials       1289     1295     +6     

Impacted Files	Coverage Δ
...ava/com/mapbox/navigation/core/MapboxNavigation.kt	65.93% <0.00%> (-1.48%)	:arrow_down:
...java/com/mapbox/navigation/core/fasterroute/Log.kt	0.00% <0.00%> (ø)
...internal/fasterroute/RecordRouteObserverResults.kt	10.41% <10.41%> (ø)
.../navigation/core/fasterroute/FasterRouteOptions.kt	66.66% <66.66%> (ø)
...navigation/core/fasterroute/FasterRoutesTracker.kt	69.56% <69.56%> (ø)
...apbox/navigation/core/fasterroute/SimilarRoutes.kt	93.93% <93.93%> (ø)
...vigation/core/fasterroute/RejectedRoutesTracker.kt	96.00% <96.00%> (ø)
...igation/core/fasterroute/FasterRouteTrackerCore.kt	96.34% <96.34%> (ø)
...igation/core/fasterroute/NewFasterRouteObserver.kt	100.00% <100.00%> (ø)

[dzinad]

I think it can be tested in instrumentation tests.

1. setRoutes(listOf(a));
2. setRoutes(listOf(a, b)) where b is faster than a. It would trigger FasterRoutesObserver, wouldn't it? We can also add cases with rejected routes.

[VysotskiVadim]

2. setRoutes(listOf(a, b)) where b is faster than a. It would trigger FasterRoutesObserver, wouldn't it?

This is one of the goals: handle the case when users pick slower route on purpose. The SDK shouldn't bother users with the faster route if it has been already rejected by user.

[dzinad]

This is one of the goals: handle the case when users pick slower route on purpose. The SDK shouldn't bother users with the faster route if it has been already rejected by user.

But you only add rejected routes for reasons "new" and "reroute". In the case I provided it's "alternative".

[kmadsen]

Late suggestion here but I think you should consider building these experimental features outside of MapboxNavigation. Faster route is now an experience that does not need to be built into MapboxNavigation. For example, you will not need to add the fasterRoutesInstance state into MapboxNavigation at this time. You will be free to iterate on something that is not changing any core code.

If you were to define a MapboxNavigationObserver, the feature is opt in with little setup.

class FasterRouteProvider(options: FasterRouteOptions) : MapboxNavigationObserver {
   private val currentLetIndex: Int -1
   private val previousRouteLeg: RouteLeg
   // anything you find necessary or want to experiment with
  ..

  companion object {
     private const val MIN_THRESHOLD_METERS = 120L
     ..
  }
}

MapboxNavigationApp.registerObserver(fasterRouteProvider)

fasterRouteProvider.state.collect { fasterRoute ->
  ...
}

It can also be disabled with clear expectations.

MapboxNavigationApp.unregisterObserver(fasterRouteProvider)