Date of Award

9-1997

Document Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Department

Department of Electrical and Computer Engineering

First Advisor

Eugene Santos, PhD

Abstract

The ability to harness different problem-solving methods together into a cooperative system has the potential for significantly improving the performance of systems for solving NP-hard problems. The need exists for an intelligent controller that is able to effectively combine radically different problem-solving techniques with anytime and anywhere properties into a distributed cooperative environment. This controller requires models of the component algorithms in conjunction with feedback from those algorithms during run-time to manage a dynamic combination of tasks effectively. This research develops a domain-independent method for creating these models as well as a model for the controller itself. These models provide the means for the controller to select the most appropriate algorithms, both initially and during run-time. We utilize the algorithm performance knowledge contained in the algorithm models to aid in the selection process. This methodology is applicable to many NP-hard problems; applicability is only limited by the availability of anytime and anywhere algorithms for that domain. We demonstrate the capabilities of this methodology by applying it to a known NP-hard problem: uncertain inference over Bayesian Networks. Experiments using a collection of randomly generated networks and some common inference algorithms showed very promising results. Future directions for this research could involve the analysis of the impact of the accuracy of the algorithm models on the performance of the controller; the issue is whether the increased model accuracy would cause excessive system overhead, counteracting the potential increase in performance due to better algorithm selection.

AFIT Designator

AFIT-DS-ENG-97-03

DTIC Accession Number

ADA329350

Download

Share

COinS