Year

1995

Degree Name

Doctor of Philosophy

Department

Department of Business Systems

Abstract

The topic of graph-search techniques is of common interest for both Operations Research (OR) and Artificial Intelligence (AT) communities. Solutions found by OR techniques are optimal and precise but may be obtained at the price of high computation time. On the other hand, those found by AI techniques have no guarantee of being optimal but are usually achieved quickly. In this research, these techniques of AI and OR are investigated and a learning search method integrating the features of both fields is presented. The main characteristics of this method are its capacity to learn along the search process and its ability to trade speed with precision to whatever degree desired.

In order to develop this method, we utilise a technique developed by Korf (1990) and expand its learning capability to generate optimal solutions. Then, by the use of a threshold parameter, the features of Korf's AI algorithm and this new OR method are integrated to represent a new learning technique. Through an intensive programming task, the correctness of this integrating method is presented by testing it on three different graphs with different characteristics. A mathematical proof is also developed to show that solutions found by this method are always guaranteed to be within a prescribed range of the optimal solution. This range is determined by the user and can be any positive real number.

The generality of this method allows its application to all graph-search problems including all such combinatorial problems. To show how efficiently combinatorial problems can be solved by this method, it is applied to the problem of Project Scheduling Under Multiple Resource Constraints, which is one of the hardest types in the scheduling area. It is shown that the method is able to solve a benchmark problem of this type manually and that it requires only 25 backtracks to find its optimal solution and only 1 backtrack to find a solution guaranteed to be within the range of 3 units of the optimal one. It is emphasised that this method is superior to all previous techniques which required tens of seconds of computer time to solve the benchmark problem.

Share

COinS