1
$\begingroup$

Let me define a volatile graph first:

It is an undirected graph in which the weight of each edge varies every time we query it. That is, when we request the weight w(e) of edge e, we obtain an approximate value ˆw(e) defined as follows: wˆ(e) = w(e) + η, where η ∼ N (0, σ). Here, N (0, σ) is a Gaussian distribution with mean zero and standard deviation σ.

How to obtain a shortest path for such a graph. Let it be denoted as (G, u, v, p). Find the correct shortest path between vertices u and v on a volatile graph G with confidence p. We can define p in any manner we want as long as it is consistent to the fact that as p grows, the probability that our algorithm returns the true shortest path should also grow

$\endgroup$
1
$\begingroup$

Here is a rough sketch of an iteratively improving algorithm that I believe should work pretty well while minimizing the number of queries we do. It can also immediately start finding paths and slowly improve the paths it finds as it goes.

The first step is to evaluate every edge (if you wish to improve initial accuracy, evaluate every edge $k$ times) and use Dijkstra's to find the shortest distance $d_v$ from every vertex $v$ to the target vertex. This forms our initial belief of the graph.

Our goal is to find an accurate $\mu_e$ average weight for each vertex, but we want to be most certain about our precision "near" what we believe to be the optimal path(s). We do this by repeatedly finding a path from the start vertex to the target, in a probabilistic fashion, by repeating the following procedure:

If we are currently at vertex $v$ we have a choice from some edges. We currently believe that each edge has weight $\mu_e$, and when we take that edge we would get to vertex $w$ with remaining (believed) distance $d_w$. We consider this a multi-armed bandit problem, where choosing edge $e$ going to vertex $w$ would have cost $\mu_e + d_w$, and we want to minimize cost. We use this to probabilistically choose an edge, we query its weight, we update $\mu_e$ and $d$ with this new weight and then move to $w$.

As we keep repeating the above process we will balance exploration of the graph with exploitation automatically due to the multi-armed bandit.

$\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.