2
$\begingroup$

I'm looking for a version of path planning that is able to find paths in a graph where edge costs depend on the state of the moving entity. In such cases, it is required to also consider trade-offs, i.e. accepting drawbacks on sub-paths if this leads to a better overall rating of the full path from A to Z.

I know a problem is that it is impossible to determine whether a path is the best one or if there are better ones without expanding every single possible path. But maybe there are algorithms around that can handle such problems. Ideally one can define a threshold in time or rate of cost improvement for a solution to control runtime and optimality as required. Maybe I need a metaheuristical approach?

Background:

As I started with a much simpler problem, that could be easily solved by A* I will outline my thoughts from there on. A* is able to find the best path only if every sub-path is optimal itself. But in some circumstances, the best path may contain parts that are not optimal if examined stand-alone. This can be the case if edge costs are dependent on the state of a moving entity. As a practical example I tried to simplify my application as good as possible. In reality it is much more complex in space and state.

A vehicle travels from A to Z, the cost function depends on the fuel burnt. At some node the following edge has additional costs depending on the weight (say a bridge). The higher the vehicle's mass, the higher the costs. A* will find the path with fewest fuel consumption from start to the node before the bridge. But it may be better to use a path on which more fuel will be consumed to lower the vehicle's mass and thus the cost to travel over the bridge which will in turn reduce the overall costs.

This little graph visualizes such a problem.

(A) -- 1 -- (B) -- 1 -- (C) -- 1 + c -- (Z)
  \                     /
   \-------- 1 --------/

c = 10 * m
m(t) = max(0, 10 - t)

m represents the mass of the vehicle and t the time, which is 0 at the beginning and increases by 1 after each step. As one can see, the best path from A to D must contain C. So while A* will find the path A-C-Z with costs of 92 (A -- 1 --> C -- 1 + 10*9 --> Z), a better one would be A-B-C-Z with costs of 83. If loops are allowed it even can be reduced to 20 (A-B-C-B-A-B-C-A-B-C-Z)

$\endgroup$
  • $\begingroup$ You will need to specify how the state of the vehicle can vary (what can it depend on? the path followed thus far? its cost? anything else? some random process?) and how exactly cost can depend on that state. $\endgroup$ – reinierpost Jun 21 '16 at 16:51
  • $\begingroup$ I am interested in similar problems: path finding where the cost of an edge depends on the upstream costs. Have you found any optimal algorithm for that ? I seems like RRT* cannot work as it does not re-compute the cost downstream if the path is modified in between 2 nodes that are not at the end of the so far computed tree. So Dijkstra and A* seem to best to me up to know. Any opinion about that ? Thank you. Quentin $\endgroup$ – user42439 Sep 8 '16 at 1:27

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.