Information Technology Reference
In-Depth Information
Combining Uniform and Heuristic Search: Solving
DSSSP with Restricted Knowledge of Graph Topology
Sandro Castronovo
1
,Bjorn Kunz
1
, and Christian M uller
1
,
2
1
German Research Center for Artificial Intelligence (DFKI),
Campus D3.2, Saarbr ucken, Germany
2
Action Line Intelligent Transportation Systems, EIT ICT Labs, Germany
Abstract.
Shortest-path problems on graphs have been studied in depth in Arti-
ficial Intelligence and Computer Science. Search on dynamic graphs, i.e. graphs
that can change their layout while searching, receives plenty of attention today -
mostly in the planning domain. Approaches often assume global knowledge on
the dynamic graph, i.e. that topology and dynamic operations are known to the
algorithm. There exist use-cases however, where this assumption cannot be made.
In vehicular ad-hoc networks, for example, a vehicle is only able to recognize the
topology of the graph within wireless network transmission range. In this paper,
we propose a combined uniform and heuristic search algorithm, which maintains
shortest paths in highly dynamic graphs under the premise that graph operations
are not globally known.
1
Introduction
Shortest path problems on graphs have been thoroughly studied in Artificial Intelli-
gence and Computer Science literature. Single-source shortest path or all-pair shortest
path problems with positive edge weights can be solved using widely known algorithms,
such as Dijkstra [1] and A*. There are a large number of applications: modern naviga-
tion systems, for example, use implementations of these algorithms for route planning,
network protocols use them in order to route data packets from one physical location
to another and many planning systems in Artificial Intelligence use variants of these
algorithms.
The problem becomes significantly more challenging when we allow certain dy-
namic operations on the graph while searching, such as insertions or deletions of ver-
tices as well as changes of edge weights. This problem drew attention of research in
Artificial Intelligence and related Computer Science fields. Approaches by [2], [3], [4],
[5], [6], [7] among others assume global knowledge on the performed graph operations.
This means they are only applicable on graphs, for which the topology and all executed
operations are known at every point in time. [3], for example, assume that every ver-
tex stores its distance to a start vertex of a shortest path. They modify this information
on every graph operation and use the result for re-calculating. Work by [4] transfers
the problem into the domain of Learning Automata but also allows access to the entire
topology of the dynamic graph.
There exist applications, however, in which this knowledge can neither be assumed
nor derived. Consider a vehicular ad-hoc network, for example, where vertices are ve-
hicles, edges are wireless connections between two vehicles, the task is to send data
