time or distance-optimal route plans have poor runtime performance

[robfitzgerald]

after a monster refactor to support parameterized cost models, we were getting normal energy-optimal runtimes from the EnergyTraversalModel, but time and distance-optimal routes are still taking long, suggesting that the a* heuristic is not correctly calculated for those objectives. see table here.

to reproduce, use this test case on our internal tomtom-based denver scenario:

{
  "model_name": "2017_CHEVROLET_Bolt",
  "starting_soc_percent": 100,
  "destination_y": 39.62627481432341,
  "destination_x": -104.99460207519721,
  "origin_y": 39.798311884359094,
  "origin_x": -104.86796368632217,
  "state_variable_coefficients": {
    "distance": 0,
    "time": 0,
    "energy_electric": 0
  }
}

[nreinicke]

Did a bit of digging into this today. It appears that we might be able to gain some runtime improvements by tweaking the heuristic functions a bit.

TLDR;

It could make sense to expose some control of the heuristic function to the configuration so we can adjust based on the desired results and runtimes.

For example, if we consider the distance heuristic as the haversine distance between the search point and the target point, we're guaranteed to never overestimate that cost, but, in reality the network will likely display some circuity. So we could try to bit a bit less optimistic for our distance heuristic and apply a circuity factor. Here's are a couple of examples of using a circuity of 1.0 (baseline) and 1.2:

circuity of 1.0

Routes

Distance Tree

Time Tree

Energy Tree

circuity of 1.2

Routes

Distance Tree

Time Tree

Energy Tree

The tradeoff here is that applying the circuity factor of 1.2 results in smaller tree and improved runtime (with the exception of the energy only case, what the heck is happening there??) but the circuity factor of 1.0 finds marginal improvements to the distance and energy shortest paths.

[robfitzgerald]

So we could try to bit a bit less optimistic for our distance heuristic and apply a circuity factor. Here's are a couple of examples of using a circuity of 1.0 (baseline) and 1.2:

are you multiplying the cost estimate by the circuitry factor? i assume that this would tighten the estimate for this exact instance of the best distance and time routes, since they in fact are bowed out (circuitous). but i'm guessing it didn't help the energy case, since the actual optimal path there is fairly diagonal (has a low circuity that we may be over-estimating with a value of 1.2). my instinct is that this would not generalize to cases where the opposite is true, but i honestly haven't done my homework on improvements to a-star heuristics to be certain.

speaking of, if you are content that the code seems correct, then maybe our next step here is to look at how people go "beyond the basics" with a-star to address performance for more complex cost functions, or to investigate how inconsistent our energy-optimal cost function becomes.

with the exception of the energy only case, what the heck is happening there??

i would love to nod in agreement here, but, it appears that time + energy maps for the 1.2 case are the same map. guessing it's the time map just got uploaded twice? 😅

[nreinicke]

guessing it's the time map just got uploaded twice?

🤦 yep, just fixed, that's what I get for moving fast.

The weirdness I'm commenting on is that in the first case, the energy tree is 140k with a runtime of 23 seconds but then in the second case, the energy tree is less than half the size, about 65k but the runtime goes up to 63 seconds...

are you multiplying the cost estimate by the circuitry factor?

In this case, I was multiplying the raw distance estimate by the circuity factor which gets propagated to the cost estimates for time and energy. It is a good point that this heuristic adjustment might be best suited to the time case since both energy and distance optimal routes likely take a route similar to the straight line distance.

then maybe our next step here is to look at how people go "beyond the basics" with a-star to address performance for more complex cost functions,

Yeah that seems like a good idea.

[robfitzgerald]

in the first case, the energy tree is 140k with a runtime of 23 seconds but then in the second case, the energy tree is less than half the size, about 65k but the runtime goes up to 63 seconds...

i think we are missing an important metric here to make sense of it, which is the number of search iterations. as opposed to dijkstra's, it is possible for a-star to revisit the same link multiple times to update the cost value. so, with the 63 second run, it is likely revisiting links many many times. something we should probably add to the traversal summary, as well as the average link visits value (iterations / tree_size).

I was multiplying the raw distance estimate by the circuity factor which gets propagated to the cost estimates for time and energy

right. but while this circuity distance heuristic is helpful for demonstration, we can't really use it, right? it would require knowing the circuity of the route we are searching for ahead of time, or the average circuity of the network that will be used for a given search. in our case, where we often have the whole nation loaded, we can't easily pre-compute this value for incoming searches, and the national average value would be wrong in many places (like, in phoenix vs boston, that value would be drastically different because of the differences in topology).

edit: back to your original idea:

So we could try to bit a bit less optimistic for our distance heuristic and apply a circuity factor.

using any incorrectly-set circuity factors may lead to over-estimation, which would make the heuristic un-admissable. but our current solution using the haversine distance should be admissible, because it will never over-estimate distances. so this 1.2 value, while it helps speed up particular instances of routing problems, may not be generally applicable.

more from wikipedia, the other issue we have is that (BEV) energy changes are not monotonic. to avoid making the heuristic inconsistent we apply a lower limit to cost that is a strictly positive small value, something like 0.000001 or whatever, so it doesn't compete with dollar costs but it enforces monotonicity. maybe this limit value is causing issues in a way i'm not realizing?

one more edit: thank you for sharing all of the plots here and your process!

[nreinicke]

i think we are missing an important metric here to make sense of it, which is the number of search iterations. as opposed to dijkstra's, it is possible for a-star to revisit the same link multiple times to update the cost value.

right, that's a really good point and it would be great to see why this is happening, maybe related to zero cost links?

while this circuity distance heuristic is helpful for demonstration, we can't really use it, right?

yeah I think I agree with that since, as you describe, we can't actually guarantee that it will be admissible for all cases.

maybe this [bev zero energy] limit value is causing issues in a way i'm not realizing?

yeah that's a good question that probably merits further digging...

Thanks for the thoughtful response here! I've been focusing on an idea to speed up the energy prediction model that is a bit more robust than caching values. I'll share more next week! Have a great weekend!

[robfitzgerald]

i have a hunch that (#111) may have, or (#115) might fix this, since both will standardize CPU + allocations around cost modeling and state updates, respectively.

[nreinicke]

I just re-ran the sample query that I shared above:

Based on our previous runs, it looks like runtime has come down about 10x which is exciting.