CEC Theses and Dissertations

Title

An Investigation of a Distributed Search Mechanism Consisting of a Set of Cooperative Agents Implemented With Different Heuristics Schemes

Date of Award

2002

Document Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Department

Graduate School of Computer and Information Sciences

Advisor

Lee J. Leitner

Committee Member

Sumitra Mukherjee

Committee Member

Gregory Simco

Abstract

The purpose of this research is to investigate a model for designing distributed search algorithm based on the use of a distributed system of cooperating agents who communicate only through messages. This model does not require any form of synchronization among the agents as required in most models of distributed algorithms. Each message contains both the state of the computation and eventually the solution to the problem. For a solution to be complete, all the agents within the domain must process the message. This form of processing is termed as "assembly-line processing". This model is not dependent on the ordering of messages but the arrival of each message presents a unique solution to the problem. To demonstrate the usefulness of this model, this research had selected the Traveling Salesman Problem (TSP). It is not the intent of this research to find a faster method for solving the TSP. By making use of various known schemes for solving the TSP to be implemented within the framework of this model demonstrates the usefulness of this computational model to build distributed search algorithms fairly easily without having to worry about synchronization issues. The known schemes for solving TSP ranges from the brute-force method to the ant colony scheme. The heuristic schemes use some evaluation functions to remove "not-so-good" solutions fairly early in the processing. This has the advantage of decreasing the number of messages being relayed. The results from these schemes demonstrate the feasibility of this model for solving problems like the TSP. This research also demonstrates that without having to worry about synchronization issues allows changes to be made to schemes more manageable. More work is required to determine the operational characteristics of this model and the type of problems it can handle.

This document is currently not available here.

  Link to NovaCat

Share

COinS