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

May 1999

Proceedings of the Twelfth International Florida Artificial Intelligence Research Society Conference (FLAIRS 1999)

Volume

Proceedings of the Twelfth International Florida Artificial Intelligence Research Society Conference (FLAIRS 1999)

All Papers

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.