Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Using segment cost instead of distance when processing bicycle kinematic model. #704

Open
alex-the-new-guy opened this issue May 29, 2024 · 22 comments

Comments

@alex-the-new-guy
Copy link

I have noticed that travel time estimates BRouter produces are sometimes several (2-2.5x consistently) times lower than actual travel time. At least partially the reason for this is that my commute is partially offroad, which kinematic model just does not handle at all, as far as I understand.
(I'm on an ~1-2 month old version which I use for my personal project though)

What I have done is:

  • added boolean "cost_kinematic" into profile in global routing context so that this can be turned on and off on the fly by editing the profile and same in RoutingContext class
  • pass extra parameter called "cost_factor" to computeKinematic which is just a total cost factor for the segment (EL / L)
  • if using cost_kinematic, when computing trip time and energy, tire rolling resistance is multiplied by said factor, emulating the sort of constant "this segment is harder" and decreasing speed instead of increasing distance, thus not messing with aero calculation later on, otherwise it is ignored

Honestly, took me a whole lot of 15 minutes to implement (I don't know Java) and the results are looking great. Within 2-5 minutes on ~45min mixed-terrain bicycle commute.

@devemux86
Copy link
Contributor

The same problem exists with the driving profiles when we change the vmax parameter.
Similar routes with just different vmax can have completely different duration.

It seems the vmax influences not only the kinematic model,
but also the route duration, often with no reasonable results.

@alex-the-new-guy
Copy link
Author

Similar routes with just different vmax can have completely different duration.

Haven't looked into car profiles, but it could it be due to how the engine handles urban speed limit? A quick search of the codebase didn't land any clues as to how it is converted into an actual value or gets used tbh. Probably somewhere around ProcessWaySection, which has two implementations: in StdPath and in KinematicPath.

@afischerdev
Copy link
Collaborator

@alex-the-new-guy
Thanks for your idea.
Do you have also some code for us and some sample to check that?

@afischerdev
Copy link
Collaborator

@ALL
And a question to everyone: should this move to the ongoing version 1.7.5 or is more time needed for testing?

@alex-the-new-guy
Copy link
Author

alex-the-new-guy commented May 29, 2024

@alex-the-new-guy Thanks for your idea. Do you have also some code for us and some sample to check that?

https://github.com/alex-the-new-guy/brouter_kc
Also pls fix gitignore at least, which I did too. It included binaries and test output data which certainly don't belong on git.
And gradlew /clean didn't delete those so I guess it's not working as intended too?

You can spin up it as usual, just add assign cost_kinematic = true to any default profile in global context. I just use trekking

More or less my test route. Segment is E35_N55

cost_kinematic.csv
no_cost_kinematic.csv

profile.txt

@afischerdev
Copy link
Collaborator

@alex-the-new-guy
Thanks for the data. I played around a bit with it, but I could not generate a similar route. I used the start and end point from the csv files but I guess you had other points to get your route.
Anyway, as you can see in the picture, it works - blue is the old calculation. The speed decreases significantly in the green area. I can't say if 'only' 5kmh is a reasonable speed reduction in his real world, but the CostPerKm from the csv file goes to ~5000 in this area.

timing

Something to the car profiles: the logic used here is already done when sectionCost is calculated.

@alex-the-new-guy
Copy link
Author

alex-the-new-guy commented May 29, 2024

@afischerdev

I used the start and end point from the csv files but I guess you had other points to get your route

Yes, I had waypoints somewhere in the middle for reasons explained below. Apparently waypoints aren't exported to CSV and github doesn't like GeoJSON

I can't say if 'only' 5kmh is a reasonable speed reduction in his real world

Reduction to 5kph is probably due to paths being treated as designated for walking by the profile, thus the extra cost is enormous and 5kph is very consistent.

What serves as a "gravity well" for your route is I think, this part:
image
The area in the black circle is actually paved, thus very "attractive".

I've tried to avoid both of those types (designated for walking and paved where I want the track to go through unpaved) of segments in my route for a more "realistic" outcome of how I would ride it and time estimate roughly matches my experience.

Some time, (maybe today, maybe tomorrow), I'll be bothered enough to compare speed estimate with some tracks I've recorded. Won't be sharing the tracks themselves for privacy reasons, but can share graphs.

So far with a sample size of one, looking good:
image
(same route, same gpx track, kinematic cost on the left, regular on the right)

So, about why using segment cost isn't the best of ideas

Thing is, the profile describes a cost function for the A* algorithm, which says how much a user would like to avoid this segment (higher costPerKm = more likely), which doesn't exactly translate to segment being slower or faster.

But there certainly is a correlation, which is good enough for this option to provide a better time estimate than just ignoring it. With this particular profile at this particular place and so on.

There very much are scenarios where this wouldn't really work out, which is why this option can be turned off by changing a variable in a profile.

A good idea might be to perform separate cf estimation using a subset of tags or separate profile variable that might influence how "fast" or "hard" the segment being processed is instead of it's cost, calculated with profile, but this is an imperfect solution too.

Rn writing up a python script that would "de-compile" the profile, compare tracks, built with it to real gpx and adjust parameters based on that, but I don't plan on making it "production - ready" any time soon.

@poutnikl
Copy link
Contributor

poutnikl commented May 30, 2024

I assume there would be many scenarios where ETA based on/involving CF would be (much) worse than it is now.

If such a profile would rather use CF based on assumed speed to address it, it would prioritize speed as decisive parameter for routing. That would be great if it is the intention, like road bikes or commuting. But it would be bad for leisure/long distance scenarios.

Imagine as illustration 10 km long cases:

  • Primary, asphalt, real speed 25 km/h, CF 3, real ETA 24 min
  • Tertiary, asphalt, real speed 20 km/h, CF 1, real ETA 30 min
  • Track, grade 5, no surface info, real speed 15 km/h, CF 2, real ETA 40 min

Based on OSM data, how would using CF affect calculated ETA of each of these segnents?


Personally, for long distance travelling routes (60-140 km), when the kinematic model is adjusted (mass, power) on known routes to match their known ETA (technical, biological and cultural pauses included) and estimated ETA, I get consistently very good ETA with current ETA model.

I often do not believe the provided ETA when on the route, but realising in the end that it was much closer to real value than my own gut estimation.

I assume that for short routes, few way segments and any algorithm, there will be many random ETA variations for particular cases, that are rather well averaged for long routes.

@alex-the-new-guy
Copy link
Author

@poutnikl

Sorry I don't have the clarity of mind to answer you properly rn, but here is something hopefully helpful.

Thing is, the current algorithm would think that the three choices you've provided would take the same time, since speed calculation is just distance based.

Basically what I'm proposing would calculate speed as max_speed/CF.
But also not really.

Since it affects tire roll resistance, CF actually as fairly limited influence, especially at lower values and higher speeds. At 15 kph, your energy probably goes 50/50 into overcoming rolling resistance, which kinematic CF influences and overcoming air resistance, which kinematic CF does not influence.

Also, CF that's being fed into the kinematic model for time estimation is not sort of segment CF you build in your profile, but total segment CF which also includes initial cost, turn cost and so on.

Things like same surface and so on, but different CF due to road class, is a problem, yes. Can be solved with calculating kinematic CF separately based on a set of surface quality tags or something, preferably configurable with profile. For implementing which I don't have time rn. Dunno.

Regarding that, the whole "CF stack" calculation should be considered. From my experience, what influences them most is surface quality and so on, not so much road classes, which means they correlate with speed halfway decently.

@quaelnix
Copy link
Collaborator

Here is a patch that introduces the ability to dynamically scale rolling resistance based on the properties of the way segment: quaelnix@7ba2f14

@afischerdev
Copy link
Collaborator

@quaelnix
good point.

I made some test with both logics using an old track as sample (green line, the track has some stop points, routes don't have):

track_routes

You find three parts where the two routings differ - the parts with unpaved areas.
As you see on the green line, the speed wasn't so much reduced.

track_routes_cf

This has a cf level 1 and cf level 2. And it comes more to the origin speed.

@alex-the-new-guy
Copy link
Author

@afischerdev while we're at it, speed in computeKinematic is just set to max_speed. It can be computed from route and kinematic model parameters, see:

see https://www.desmos.com/calculator/sewl51eeag

It's an equation and a half, but I guess nothing that can't be implemented

@quaelnix
Copy link
Collaborator

quaelnix commented Jun 3, 2024

@alex-the-new-guy, that is not true:

speed = solveCubic(rc.S_C_x, f_roll, rc.bikerPower);
speed = Math.min(speed, maxSpeed);

@alex-the-new-guy
Copy link
Author

alex-the-new-guy commented Jun 3, 2024 via email

@quaelnix
Copy link
Collaborator

quaelnix commented Jun 6, 2024

I have noticed that travel time estimates BRouter produces are sometimes several (2-2.5x consistently) times lower than actual travel time.

A reasonably good estimate can only be expected if the parameters of the kinematic model are well tuned with regard to personal fitness (bikerPower and totalMass), driving skills (maxSpeed and S_C_x) and material (S_C_x and C_r):

# +++ Kinematic model parameters (travel time computation)
assign totalMass = 90 # %totalMass% | Mass (kg) of the bike + biker | number
assign maxSpeed = 35 # %maxSpeed% | Absolute maximum speed (km/h) | number
assign S_C_x = 0.300 # %S_C_x% | Drag coefficient times reference area (m^2) times half air density (kg/m^3)
assign C_r = 0.005 # %C_r% | Rolling resistance coefficient (dimensionless)
assign bikerPower = 150 # %bikerPower% | Average power (W) provided by the biker | number

Within 2-5 minutes on ~45min mixed-terrain bicycle commute.

My mixed-terrain bicycle commute is at least 30 km long and the travel time estimate is basically always closer than 1 minute to the true time if I enter somewhat proper values for above parameters.

@alex-the-new-guy
Copy link
Author

alex-the-new-guy commented Jun 6, 2024

@quaelnix

A reasonably good estimate can only be expected if the parameters of the kinematic model are well tuned with regard to personal fitness (bikerPower and totalMass), driving skills (maxSpeed and S_C_x) and material (S_C_x and C_r):

Ok, so don't get me wrong, but I think I have some data to prove you wrong.
IMO this is the case Poutnic mentionted. The error more or less just averages out on a long enough route. I've written some horrible python code that basically runs the kinematic function in reverse, which allows me to more precisely compare how I go through routes.

Also, sorry for labels in russian, it's for my thesis, and I don't have time to fuss with labels

I can throw the code to github next week, but it still needs quite a bit of tweaking
doesn't account for height since where I live it's real flat and I didn't have much time to implement it

image

This graph shows expected (orange), real (blue) and expected (adjusted for power)
Theoretically, expected speed adjusted for power should more or less match real, but it doesn't, which indicates the difference between the real and expected rolling resistance force

image

Rolling resistance force should be constant independent of your speed and what not, it only depends on segment characteristics and your tyres and what not

Now, this is using my custom profile and cf for kinematic
Here is how the standard one looks

image

image

Basically, rolling resistance actually should be near zero in "good" segments (and basically everywhere if you're not using the mod), which are also prioritized by the routing engine. You not noticing the issue could be the routing actively avoiding segments where effective rolling resistance should be high.

@quaelnix
Copy link
Collaborator

quaelnix commented Jun 7, 2024

The error more or less just averages out on a long enough route.

Yes, but the error will only average out if the parameters are well chosen.

I've written some horrible python code that basically runs the kinematic function in reverse, which allows me to more precisely compare how I go through routes.

So did I:

Route 1 (50 % paved) Route 2 (100 % paved)
brouter-cycling-speed-raw-r1 brouter-cycling-speed-raw-r2
brouter-cycling-speed-power-adjusted-r1 brouter-cycling-speed-power-adjusted-r2

Theoretically, expected speed adjusted for power should more or less match real, but it doesn't, which indicates the difference between the real and expected rolling resistance force

If there is no wind and the road is flat and you never touch the brakes.

@alex-the-new-guy
Copy link
Author

alex-the-new-guy commented Jun 7, 2024

@quaelnix

Your data indeed looks really good, but it lacks the parts where

According to this, rolling resistance has about as much power as air resistance at speeds around 15kph.
While on your track 1 there are some spots where it drops below that, but not much, and it looks like it happens due to inclines which the current implementation of kinematic model can handle.
So, you're probably riding some hard-packed road where rolling resistance isn't actually all that different from asphalt, at least not enough to slow you down much.

In my case, I was going up to 30kph@300w on a paved road, then hit wet mud and speed dropped to below 10kph@150w with no incline. So 5kph section between 4 and 7 km is me going trough a swamp basically.
image

And even if it's dry, I get consistently lower speed than brouter predicts there, since the ground there is soft and even a 2.25 xc tire feels like it's sinking into it a bit.

This is very much an extreme case, but would be nice to be able to set up the profile to handle it.

And if brouter uses your implementation with a separate rolling resistance modifier variable, which I think I've stated is very much superior to mine, it wold probably be the case of "better have it not need it, than need it not have it". I think people who would care about more or less detailed accounting for rolling resistance would probably also care enough to adjust their power and drag coefficient.
And it can be tuned for different setups by having profile variables that would account for tolerance to such conditions.

Speaking of touching brakes and what not:
KinematicPath looks like it's processing slowdowns due to taking turns and breaking/acceleration. Maybe feeding data from there into ComputeKinematic would be a good idea? Though I haven't studied KinematicPath's code all that much.

Or maybe compute time with KinematicPath?

Speaking of calculating speed from road conditions
The equation I've provided can be modified to account for incline.
And that would probably speed stuff up since as far as I remember Newton method solves an equation by continuously approaching where it's value zeroes out by computing it at different locations and looking at it's derivative.

Not that it matters much for overall performance IMO, though I obviously haven't done any profiling proper.

And also maybe probably would be a simpler piece of code than Newton method implementation

Also, I have a gut feeling I might have offended you somehow. If that is true, I would like to apologize and this was never my intention.

@quaelnix
Copy link
Collaborator

quaelnix commented Jun 8, 2024

While on your track 1 there are some spots where it drops below that, but not much, and it looks like it happens due to inclines which the current implementation of kinematic model can handle.

The reason why the estimated speed is below the actual speed on climbs and above the actual speed on decends is that BRouter assumes a constant power over the entire length of the route, whereas the actual power output was as follows:

Route 1 (50 % paved) Route 2 (100 % paved)
brouter-cycling-speed-raw-r1 brouter-cycling-speed-raw-r2

The lag between the estimated speed and the true speed when the incline changes is caused by this exponential filter:

double decayFactor = Math.exp(-dist / 100.);
float new_elevation_buffer = (float) ((elevation_buffer + shift) * decayFactor - shift);

it looks like it happens due to inclines which the current implementation of kinematic model can handle.

The current implementation does take the downhill force into account, but it is somewhat hidden:

double f_roll = rc.totalMass * GRAVITY * (rc.defaultC_r + incline);

rc.defaultC_r + incline is an approximation of cos(incline) * rc.defaultC_r + sin(incline).

So, you're probably riding some hard-packed road where rolling resistance isn't actually all that different from asphalt

Correct.

This is very much an extreme case, but would be nice to be able to set up the profile to handle it.

If you add this into the way context of the profile text:

assign maxspeed switch surface=mud 7 maxspeed

the speed will be limited to 7 kph on muddy segments.

Also, I have a gut feeling I might have offended you somehow.

Not at all. I think this is a very worthwhile discussion, and I am not against adding the possibility of dynamic adjustment of rolling resistance. I just do not think there should be an inherent coupling between rolling resistance and segment cost. It should be up to the profile creator to decide whether or not to link segment cost and rolling resistance.

Repository owner deleted a comment Jun 8, 2024
@alex-the-new-guy
Copy link
Author

alex-the-new-guy commented Jun 8, 2024

@quaelnix

I just do not think there should be an inherent coupling between rolling resistance and segment cost. It should be up to the profile creator to decide whether or not to link segment cost and rolling resistance.

And if brouter uses your implementation with a separate rolling resistance modifier variable, which I think I've stated is very much superior to mine, it wold probably be the case of "better have it not need it, than need it not have it".

I think we agree on that. I had to get something to work for my thesis in a very limited amount of time. This is an ass-backwards solution, but I didn't want to mess with profile interpreter.

Now, for the other stuff.

image

This is your route 1 adjusted for power
I was talking about specifically these segments, as the lower your speed is, the greater the influence of rolling resistance on it. But those are due to incline, which kinematic model can take into account, which is why brouter and real speed matches.

Basically, you don't have any places on your route where rolling resistance contributes to resistance power significantly, slow speed is always due to air or incline, which is why I don't think your results are conclusive.

Simply put, coefficient of rolling resistance is about 0.01 in most cases, and at decent speed or decent incline, the forces generated by those are huge compared to it, which is why your data matches.

In my data, elevation difference is maybe 5m over the whole route, so incline is not a significant factor.

assign maxspeed switch surface=mud 7 maxspeed

I have a rather elaborate profile which takes the grading of how wet it is out there, which does a way better job of calculating speed than just limiting it to 7. It gives decently accurate results

BTW speaking of route comparing scripts, I do think those would be worthwhile additions to the package, maybe we could combine ours and turn them into something?

But here again comes the question of link between cost factor and rolling resistance linking, since the way route is built is using section cost, which is not something related to speed.

Would something like this work when tuning profile for building route with lowest travel time?

assign c_roll = // effective rolling resistance
  multiply 
  C_r                 // preset rolling resistance from global context
  add
    costfactor
    turncost

@poutnikl
Copy link
Contributor

poutnikl commented Jun 8, 2024

I think it would be very tricky to estimate the rolling resistance from available surface related OSM data, especially as using smoothness is rare and the mapping is incomplete. Real state is very variable for the same or similar mapping, and is further weather dependent. It would have its own random errors, different to the errors of current ETA.

Saying that, it is indeed interesting option and can be good to have it in the sleave.

@quaelnix
Copy link
Collaborator

But those are due to incline, which kinematic model can take into account, which is why brouter and real speed matches.

Yes, but on a negative incline the kinematic model no longer works, because every time the max speed exceeds the limit:

speed = solveCubic(rc.S_C_x, f_roll, rc.bikerPower);
speed = Math.min(speed, maxSpeed);

you effectively lower the average power below the value that was set in bikerPower. On the first route the difference between the bikerPower and the actual average power used in the kinematic model is as high as 18 %.

Basically, you don't have any places on your route where rolling resistance contributes to resistance power significantly, slow speed is always due to air or incline, which is why I don't think your results are conclusive.

I agree, but it shows that it works well unless you are driving on sand or mud or going down steep hills and that - aside from that - not knowing the momentary power is the most significant contributor to the speed difference.

since the way route is built is using section cost, which is not something related to speed.

It is possible to set the cost based on the estimated speed, see this profile: https://github.com/simdens/brouter_profile/blob/master/longdistance.brf

Would something like this work when tuning profile

Aside from the fact that I do not think it makes sense to model turning costs as rolling resistance, it is also not possible with the current code, as you can not access the turncost inside of the profile.

for building route with lowest travel time?

I do not think it is possible to accurately predict the route with the shortest ride time without taking into account that you are not pedaling at a constant power. And even if you do take this into account, as Best Bike Split does, you are still usually going to fail on MTB trails.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

5 participants