4
$\begingroup$

I'm working on a research project which involves iterative pathfinding over a space whose cells have danger values that change over time.

More specifically, the danger values represent bad weather, and the program uses ten days of weather predictions to find the best route across a section of the earth.

Formalized: We're given a graph where, for each edge $e$, the cost on that edge when starting at time t is $c_e(t)$. Each edge takes one unit of time to traverse. Find the min-cost route from $u$ to $v$.

Up until now we've been using a modified A* search, however it is extremely inefficient and has become almost exhaustive.

Is there a better algorithm already out there for such a problem?

I've started to take a look at D* lite, but I don't believe it's the best solution, because we already know what the cost at time t.

Any advice is much appreciated.

Cheers,

Arek Sredzki

$\endgroup$
  • $\begingroup$ Can you formalize the problem? How's this: We're given a graph where, for each edge $e$, the cost on that edge when starting at time $t$ is $c_e(t)$. Each edge takes one unit of time to traverse. Find the min-cost route from $u$ to $v$. $\endgroup$ – usul Oct 1 '15 at 13:50
2
$\begingroup$

In general, finding least-cost paths with arbitrary time-dependent edge costs is NP-hard, assuming that either (a) waiting at nodes is forbidden and your costs are not FIFO-preserving (e.g., see here for brief discussion on this complexity, as well as others: https://www.cs.ucsb.edu/~suri/psdir/soda11.pdf) or (b) the cost you are trying to optimize is not simply pure travel time itself (e.g., see http://algo2.iti.kit.edu/download/gen_obj_func_tch.pdf).

As an illustrative example of this latter situation (which seems most similar to yours) and continuing with your suggested notation, it is shown in the second paper above that it is NP-hard for the case in which the time-dependent edge cost is defined in the form $c_e(t) = f_e(t) + d_e$, where $f_e$ is the (typical) time-dependent travel-time function that returns the travel time along the edge for a particular time of day $t$ and $d_e$ is some arbitrary time-neutral cost function. It is not hard to show that similar hardness results for other such cases as well, where, e.g., the function uses a multiplier instead of addition (i.e., $c_e(t) = f_e(t) \cdot d_e$), and so on.

Regardless, one can derive pseudo-polynomial time bounds on such cases if, e.g., you are representing your time instants as integer values and assuming there are only a finite number of possible time instants bounded by $T$. In this way, you only need to maintain a single least-cost path per time instant $t$ for any given node in the graph, which would give you the running time of $O(T(m + nlogn))$, assuming non-negative cost functions. Taking this idea a step further, since your particular use case assumes that "each edge takes one unit of time to traverse", then this automatically gives you a strongly-polynomial-time algorithm since, in your case, $T \in O(n)$ (because each such path contains $\leq n-1$ edges).

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.