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.