Date of Award

Fall 2000

Document Type

Thesis - Restricted

Degree Name

Master of Science (MS)

Department

Electrical and Computer Engineering

First Advisor

Reidel, Susan

Second Advisor

Barnard, Mark

Third Advisor

Feng, Xin

Abstract

Artificial intelligence (Al) has been an ongoing research area since the advent of computers. There are many different aspects to AI including speech synthesis, image recognition, and problem solving. There are also many different algorithms that can be used to solve these problems. Some are complex and attempt to use AI techniques to solve the problem. Others search all possible states until the solution is reached. The set of all possible configurations of the problem is called the solution space. In order to search the solution space in an organized fashion, it must be represented by a data structure. A tree is one common way to represent the solution space of a problem. There are many possible ways to search a tree. Computer algorithms to search trees have been developed, refined and optimized by many researchers and much has been published on this topic. With the advent of object-oriented design and the development of object-oriented languages, new programming techniques have emerged. One of the big advantages these new programming languages promote is reusable code. Although the aforementioned topics, object-oriented design and tree searching, have received much attention separately, there has been little effort to use these techniques together. Previously, a tree based AI problem was solved by selecting an algorithm and then tweaking the algorithm to fit the problem at hand. Then, when another problem was presented, the algorithm would again have to be developed from the beginning since the previous algorithm was customized around the specific problem. This is a large waste of time and increases the amount of new code that must be developed. This thesis asks the question, "is it possible to code the algorithm once, in a generalized way, using object oriented techniques, so that the same code could be used again for another problem." This question is answered in the affirmative by describing an application programmer's interface (API) which can be used to solve any tree based AI problem without having to write or customize any algorithm code. The API contains generalized versions of four popular tree search algorithms. The only code required of the programmer that wishes to use this API is two or three functions which describe the characteristics of the problem. This API can speed development of solutions to tree-based problems and can be used to quickly compare the effectiveness of different algorithms in different circumstances.

Share

COinS

Restricted Access Item

Having trouble?