next up previous
Next: DESIGNING THE ROAD NETWORK Up: SHORTEST PATH ALGORITHMS Previous: Dijkstra's Algorithm

Knowledge-based Techniques

Knowledge-based problem solving[5] emphasizes the use of human problem solving strategies on a computer. It takes advantage of insight knowledge of the human on a particular problem solving domain, and tries to imitate the human problem solving process. This technology has been used to solve many real life problems.

For route finding, human beings use a complicated process of heuristic search. This process is, not at all understood. What appears to be clear is that human beings are good at using heuristic knowledge about the road network, and geographical knowledge about various places to isolate the part of the whole network that may contain solution. However, they are not good at searching for the best solution in the isolated area. Thus, it can be said that route finding by using human knowledge alone will not be efficient. It can efficiently isolate the part of the network containing the solution. After that, a search algorithm has to be used to find the best solution in the isolated area.

From the above discussion, it can be seen that each individual technique does not provide a good method for route finding. Each of them, however, has it's advantages in solving the problems. Analysis of the advantages and disadvantages shows that they can easily help each other. In order to use the knowledge about road network and the geographical knowledge we use object-oriented data model and store all the required knowledges in objects as responsibilities of each object.

next up previous
Next: DESIGNING THE ROAD NETWORK Up: SHORTEST PATH ALGORITHMS Previous: Dijkstra's Algorithm
M.Abaidullah ANWAR
1999-11-25