Author Topic: Avg speed filters and ETA estimation  (Read 2690 times)

Offline poutnikl

  • Padavan of Locus
  • ***
  • Posts: 381
  • Thanked: 27 times
    • View Profile
    • My Brouter Profiles
  • Device: Sony Xperia M DUAL / LocusMap Pro / A4.3
Avg speed filters and ETA estimation
« on: June 15, 2016, 08:33:25 »
This thread is meant as more proper place on ongoing helpdesk discussion.
http://help.locusmap.eu/topic/frequency-of-navigation-hints-settings-confusion
https://github.com/poutnikl/Brouter-profiles/wiki
When a user digs profiles up from the GitHub repositories,
they will be hopefully wrapped in some wiki knowledge....  :-)
 

Offline poutnikl

  • Padavan of Locus
  • ***
  • Posts: 381
  • Thanked: 27 times
    • View Profile
    • My Brouter Profiles
  • Device: Sony Xperia M DUAL / LocusMap Pro / A4.3
Re: Avg speed filters and ETA estimation
« Reply #1 on: June 15, 2016, 11:53:35 »
I have emulated 60 km long near 1 h lasting real travelling by a  car from my home to a village house of my parents.
There is listed summary of speed profiles of particular route segments and related Excel graph.

There are listied graphs for time constants of the exponential filters 100 s ( alfa 0.99 ), 200 s ( 0.995 ) and 500 s ( 0.998 )

Right axis is for current avgspeed provided by the filter  ( solid lines )
Left axis is predicted ETA in form of number of seconds since departure.( dashed lines )
Horizontal axis is time since departure in seconds.

It seems longer constants - comparable with trip length have general advantage for ETA estimation,
while shorter constants ( much shorter than trip length ) may take advantage if last miles are very different then average..

An idea hit me about an adaptive time constant of the filter,
when the filter response would get faster with approaching the destination.

Like e.g.
timeconstant = (RemaindingDistance/avgspeed) / 5 = Remainingtime / 5
  ( initially 12 min for 1 h trip,  2 min for last 10 min )

alfa = 1 - 1 / timeconstant

« Last Edit: June 15, 2016, 12:10:30 by poutnikl »
https://github.com/poutnikl/Brouter-profiles/wiki
When a user digs profiles up from the GitHub repositories,
they will be hopefully wrapped in some wiki knowledge....  :-)
 

Offline poutnikl

  • Padavan of Locus
  • ***
  • Posts: 381
  • Thanked: 27 times
    • View Profile
    • My Brouter Profiles
  • Device: Sony Xperia M DUAL / LocusMap Pro / A4.3
Re: Avg speed filters and ETA estimation
« Reply #2 on: June 15, 2016, 17:28:49 »
There was added to the graph an adaptive exponential filter, with timeconstant = 1/5 of estimated remaining time.
While it is hasitating to adapt at first, it adapts fast at the end, combining advantages of both big and small constants.

https://github.com/poutnikl/Brouter-profiles/wiki
When a user digs profiles up from the GitHub repositories,
they will be hopefully wrapped in some wiki knowledge....  :-)
 

Offline poutnikl

  • Padavan of Locus
  • ***
  • Posts: 381
  • Thanked: 27 times
    • View Profile
    • My Brouter Profiles
  • Device: Sony Xperia M DUAL / LocusMap Pro / A4.3
Re: Avg speed filters and ETA estimation
« Reply #3 on: June 17, 2016, 14:25:12 »
It seems the adaptive time constant  ( TC ) of the exponential filter is good choice for "hesitative adaption" in the early route stages and at the same time for fast adaption for the late route stages.

A good value seems to be TC = 1/5 of estimated remaining time.

Code: [Select]
TC = ( remaining_distance / avgspeed )  / 5
clipped between  100 and 1000 s like

Code: [Select]
TC = min( 1000, max(100, remaining_distance / avgspeed ))  / 5
alfa = 1 - 1 / TC

Code: [Select]
avgspeed(N) = alfa * avgspeed(n-1) + ( 1- alfa) * immediatespeed
can be written as well as

Code: [Select]
avgspeed(N) =  ((TC - 1) * avgspeed(n-1) +  immediatespeed )   / TC
--
for 0709 - context is there is no info about remaining route in advance but the distance. If there is such info, like highway class nominal speeds, or bicycle speed based on elevation profile, much better algorithms can be used.
https://github.com/poutnikl/Brouter-profiles/wiki
When a user digs profiles up from the GitHub repositories,
they will be hopefully wrapped in some wiki knowledge....  :-)
 

Offline Ulrich Kiermayr

  • Newbie
  • *
  • Posts: 1
    • View Profile
Re: Avg speed filters and ETA estimation
« Reply #4 on: October 15, 2016, 20:29:07 »
A remark on that: during our vacation (cycling) the ETA often was not really usable. Reason: the topography of the route has a huge influence on the speed you are able to ride. Consider a tour where you go uphill the first half and downhill on the second. Just considering the current average speed, would result in unusable results,because it would estimate going up the whole tour. But this is wrong, since the second half will be faster because it is downhill.
I think the ETA algorithm (for cycling and probably also for hiking) should work somewhat like the algorithm to estimate the time for a track. The current avg speed could\should be used to set the parameters for that estimate (like piking the best profile in the trip time estimate).


 

Offline Andrew Heard

  • Padavan of Locus
  • ***
  • Posts: 427
  • Thanked: 13 times
    • View Profile
Re: Avg speed filters and ETA estimation
« Reply #5 on: October 16, 2016, 00:12:26 »
A remark on that: during our vacation (cycling) the ETA often was not really usable. Reason: the topography of the route has a huge influence on the speed you are able to ride. Consider a tour where you go uphill the first half and downhill on the second. Just considering the current average speed, would result in unusable results,because it would estimate going up the whole tour. But this is wrong, since the second half will be faster because it is downhill.
I think the ETA algorithm (for cycling and probably also for hiking) should work somewhat like the algorithm to estimate the time for a track. The current avg speed could\should be used to set the parameters for that estimate (like piking the best profile in the trip time estimate).
@Ulrich Kiermayr - I recall the ETA calculation did something like what you propose a long time ago. At the time I made suggestion for opposite of what you now propose to return to i.e. "considering the current average speed" - help topic http://help.locusmap.eu/topic/why-was-time-to-target-so-wrong. No algorithm, unless it takes into account topography and history of your speeds in similar circumstance is going to be accurate, when there are range of gradients along the route, but in your example when cycling faster in second half, even after a few minutes of downhill your "current average speed" will of course quickly rise, and as a consequence the estimated ETA will indeed become more and more accurate? Didn't you observe that? Say you select a profile where the nominal speed is 18km/h, and on your route you cycle uphill all day, how is the profile speed any use to ETA calculation?
Sony Z1, Samsung Galaxy Note 8
 

Offline poutnikl

  • Padavan of Locus
  • ***
  • Posts: 381
  • Thanked: 27 times
    • View Profile
    • My Brouter Profiles
  • Device: Sony Xperia M DUAL / LocusMap Pro / A4.3
Re: Avg speed filters and ETA estimation
« Reply #6 on: October 16, 2016, 20:26:13 »
A remark on that: during our vacation (cycling) the ETA often was not really usable. Reason: the topography of the route has a huge influence on the speed you are able to ride. Consider a tour where you go uphill the first half and downhill on the second. Just considering the current average speed, would result in unusable results,because it would estimate going up the whole tour. But this is wrong, since the second half will be faster because it is downhill.
I think the ETA algorithm (for cycling and probably also for hiking) should work somewhat like the algorithm to estimate the time for a track. The current avg speed could\should be used to set the parameters for that estimate (like piking the best profile in the trip time estimate).
Sure, I am well aware of that.  But it is possible only if elevation profile is available.

As I have mentioned before on one of Locus forums,ideal would be if BRouter ( or Locus during the import ) would calculate the route nominal time profile estimation based on elevation profile. Then ratio of nominal and real speed for a particular route section would be used for the correcttion of  the nominal remaining time.

E.g. if you passed some distance in 9 minutes instead of nominal 10 minutes, based on nominal time profile,
than if nominal remaining time was 60 minutes, the corrected prediction would be 54 minutes.
« Last Edit: October 16, 2016, 20:30:05 by poutnikl »
https://github.com/poutnikl/Brouter-profiles/wiki
When a user digs profiles up from the GitHub repositories,
they will be hopefully wrapped in some wiki knowledge....  :-)
 

Offline Andrew Heard

  • Padavan of Locus
  • ***
  • Posts: 427
  • Thanked: 13 times
    • View Profile
Re: Avg speed filters and ETA estimation
« Reply #7 on: October 16, 2016, 23:46:30 »
Sure, I am well aware of that.  But it is possible only if elevation profile is available.

As I have mentioned before on one of Locus forums,ideal would be if BRouter ( or Locus during the import ) would calculate the route nominal time profile estimation based on elevation profile. Then ratio of nominal and real speed for a particular route section would be used for the correcttion of  the nominal remaining time.

E.g. if you passed some distance in 9 minutes instead of nominal 10 minutes, based on nominal time profile,
than if nominal remaining time was 60 minutes, the corrected prediction would be 54 minutes.
@poutnikl nice proposal - maybe new help topic? The algorithm "logic" is simple enough for explanation in documentation. Seems to me lots of developer work for single ETA value when I think current algorithm is mostly OK, but people can vote.
Sony Z1, Samsung Galaxy Note 8