An Expert Database System For The Overland Search Problem

This paper describes a heuristic expert database system to solve the overland search problem. The task in this problem is to find the best path between two points on a geographic map. In our system the map is represented by a set of disjoint adjacent polygons. The cost of moving between two points within the same polygon is proportional to the distance between the two points. The map is stored in an INGRES relational database.First, we present a basic system that performs a greedy path search to find the best path. The system is implemented in QUEL*, an extension of the INGRES query language QUEL that allows abstract data types and more sophisticated control structures for efficient rule processing. In particular, we make use of data types and operators for spatial objects and for program code.In order to speed up the path search we suggest to utilize knowledge about the area to perform a hierarchical decomposition of the given problem. We also propose to perform an initial coarsening of the given map. On a coarsened map, the system will be able to find an approximation of a solution path very quickly.