Organization: TNO Physics and Electronics Laboratory
Date: Tue, 10 Nov 1992 14:40:34 GMT
Lines: 32
Fellow travelers,
We are searching for an efficient path distance calculation algorithm,
applicable to temporal databases. The temporal database is virtually a graph of
timepoints connected by edges. The timepoints mark beginnings and endings of
events. Each edge is labeled by a pair of integers defining respectively the minimum and maximum duration between the connected timepoints. For instance,
if point A and point B are connected by an edge labeled with [3,6], the duration of the edge lies within 3 to 6 time units.
Currently, we have implemented an algorithm (in Prolog, for a planning system)
using backtracking over the distances already known and an aggregation on top
of this that determines the best path, given a start and endpoint. We have
further applied several heuristics to "cut" search options, however, the
result is not satisfactory as yet.
We would very much appreciate suggestions that could set us on the right track.
Mind you, algorithms such as A*, simulated annealing, etc. are not the answer
due to the fact that most of the distances (graph connections) are not known.
A transitive closure is not the answer either, because this would result
in a tremendously large database, only enlarging the problem.
Thanks in advance,
regards,
Kees d'Huy and Arjan Keene
TNO Physics and Electronics Laboratory, The Hague, The Netherlands.