home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / ai / 4247 < prev    next >
Encoding:
Text File  |  1992-11-11  |  1.8 KB  |  43 lines

  1. Newsgroups: comp.ai
  2. Path: sparky!uunet!mcsun!sun4nl!tnofel!huyh7
  3. From: huyh7@fel.tno.nl (Huy)
  4. Subject: efficient calculation of path distances in temporal databases.
  5. Message-ID: <1992Nov10.144034.2380@fel.tno.nl>
  6. Keywords: Temporal reasoning, path distance, backtracking
  7. Organization: TNO Physics and Electronics Laboratory
  8. Date: Tue, 10 Nov 1992 14:40:34 GMT
  9. Lines: 32
  10.  
  11. Fellow travelers,
  12.  
  13. We are searching for an efficient path distance calculation algorithm,
  14. applicable to temporal databases. The temporal database is virtually a graph of
  15. timepoints connected by edges. The timepoints mark beginnings and endings of
  16. events. Each edge is labeled by a pair of integers defining respectively the minimum and maximum duration between the connected timepoints. For instance,
  17. 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.
  18.  
  19. Currently, we have implemented an algorithm (in Prolog, for a planning system)
  20. using backtracking over the distances already known and an aggregation on top
  21. of this that determines the best path, given a start and endpoint. We have
  22. further applied several heuristics to "cut" search options, however, the 
  23. result is not satisfactory as yet.
  24.  
  25. We would very much appreciate suggestions that could set us on the right track.
  26. Mind you, algorithms such as A*, simulated annealing, etc. are not the answer
  27. due to the fact that most of the distances (graph connections) are not known.
  28. A transitive closure is not the answer either, because this would result
  29. in a tremendously large database, only enlarging the problem.
  30.  
  31. Thanks in advance,
  32.  
  33. regards,
  34.  
  35. Kees d'Huy and Arjan Keene
  36. TNO Physics and Electronics Laboratory, The Hague, The Netherlands.
  37.  
  38. @@@@@@@@@@@@@@@@@@@@@@@@@@
  39. Are we going to die,Sir?
  40. Not now, Baldrick.
  41. @@@@@@@@@@@@@@@@@@@@@@@@@@
  42.  
  43.