3
$\begingroup$

In a geographical graph, where each edge's cost is equal to the physical distance between its nodes, one can be tempted to manipulate the cost of some of the edges, to make it a bit lower, in order to introduce preferred paths.

So that, in the following graph, the final route would be the one in green instead of the one in grey:

Euclidean shortest route versus preferred route

The issue with this approach is that using euclidean distance makes the heuristic not admissible anymore. As an example, if we're at point A on the graph above, the euclidean distance from A to Finish can be higher than the eventual cost from A to B to Finish, considering the lowered cost between AB.

As a result, when putting many preferred routes on a much more complex graph than the one above, then the optimality of the solution is not guaranteed anymore and $A^*$ can sometimes give very erratic results.

Final objective

The final objective for this question is to come up with a way to make some paths slightly preferred over the absolute, euclidean shortest paths, when trying to predict routes, in order to model non-geographical constraints, like density of traffic or tolls.

I can think of two main ways of avoiding the exposed issue:

  • change the heuristic to make it admissible again (but then, how?)
  • use a different strategy to deal with preferred path

Any help would be appreciated.

$\endgroup$
  • $\begingroup$ What about AB makes it preferable to the shortest path? Is it possible to add distance to the non-preferred paths rather than remove distance from the preferred one? $\endgroup$ – BlueRaja - Danny Pflughoeft Mar 5 '18 at 10:37
  • 1
    $\begingroup$ As a "quick fix": (1) Determine the maximum value of $d_{xy}/w_{xy}$ over all edges $(x, y)$, where $d_{xy}$ is the Euclidean distance between them and $w_{xy}$ is the weight of the edge connecting them; (2) Divide all heuristic values by this maximum value. What's good is that your heuristic is now once again admissible, what's bad is that a single "highly preferred" edge (in terms of this ratio) can make the heuristic very loose across the entire graph. $\endgroup$ – j_random_hacker Mar 5 '18 at 10:40
  • $\begingroup$ @BlueRaja-DannyPflughoeft one example is if all edges in the graph allow for a speed of 50mph, but this particular AB edge allows for 90mph. $\endgroup$ – Jivan Mar 5 '18 at 10:43
  • 1
    $\begingroup$ @Jivan: In that case the edges on your graph should represent "time to drive between these points", not "physical distance". Then your heuristic could be "time to drive between these points at the fastest speed limit". $\endgroup$ – BlueRaja - Danny Pflughoeft Mar 5 '18 at 10:45
  • 1
    $\begingroup$ @Jivan: If the heuristic is taking a straight-line path driving at the fastest speed on your graph, it can never overestimate the true time unless your car can teleport. $\endgroup$ – BlueRaja - Danny Pflughoeft Mar 5 '18 at 10:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.