Solving Hard Computational Problems Through Collections (Portfolios) of Cooperative Heterogeneous Algorithms

Eugene Santos Jr., University of Connecticut; Solomon Eyal Shimony, Ben Gurion University of the Negev; Edward Michael Williams, Air Force Information Warfare

Numerous artificial intelligence schemes and applications require, at their core, a solution to intractable computational problems, such as probabilistic reasoning. Conditions for theorems guaranteeing polynomial time algorithms for special cases, do not hold for many real-world problem instances. While there are a number of highly specialized algorithms / heuristics that can solve specific problem subclasses, a great variance exists between algorithm performance over the spectrum of different problem instances. However, matching the best algorithm to a problem instance is a difficult proposition at best. Unfortunately, this is also assuming that such an individual algorithm exists which can actually solve the given problem in a reasonable amount of time and space. Harnessing several different problem-solving algorithms / methods together into a cooperative system (or portfolio) has been observed to have the potential for solving these NP-hard problems. The need exists for an intelligent controller that is able to effectively combine radically different problem-solving techniques into a distributed, cooperative environment. In this paper, we describe the OVERMIND system which provides a framework and approach for developing such controllers. By modeling the performance / behavior of the component algorithms, especially how they cooperate and interact, this provides the means for developing a controller to select the most appropriate algorithm mix (portfolio). We applied this approach to belief revision in Bayesian networks.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.