Go home now Header Background Image
Submission Procedure
share: |
Follow us
Volume 8 / Issue 8

available in:   HTML (34 kB) PDF (190 kB) PS (266 kB)
Similar Docs BibTeX   Write a comment
Links into Future
DOI:   10.3217/jucs-008-08-0739


An Architecture for a Three-Tier Path-Finder

Michael Barley (University of Auckland, New Zealand)

Hans W. Guesgen (University of Auckland, New Zealand)

Gareth Karl

Abstract: This paper describes the architecture of a route finding system that computes an optimal route between two given locations efficiently and that considers user preferences when doing so. The basis of the system is an A* algorithm that applies heuristics such as the air distance heuristic or the Manhattan heuristic to compute the shortest path between the two locations. Since A* is not tractable in general, island search is used to divide the problem into smaller problems, which can be solved more easily. In addition to that, search control rules are introduced to express user preferences about the routes to be considered during the search.

Keywords: A* search, island search, route finding, search control rules

Categories: I.2.8