This project seeks to develop adaptive techniques for high performance graph-based reasoning systems that allow users to control the tradeoffs between computational resources and solution quality. The main thrust of this project is to introduce adaptability and scalability in algorithms for constraint optimization, probabilistic inference, and decision making under uncertainty. The project is structured into subprojects that study: (1) iterative belief propagation for graphical models; (2) hybrids of stochastic local search and inference; (3) search guided by partition-based heuristics; and (4) mixed probabilistic and deterministic (constraint) networks. These subprojects are tied together by the PI's ongoing research on the unifying framework of "parameterized bounded inference" that combines the two paradigms of search and structure-based inference. Endowing graph-based algorithms with increased adaptability and scalability is important not only to progress in AI and computer science but also to application in many domains. An additional goal of this project is to package the developed algorithms in one software reasoning and evaluation shell (REES) to allow uniform empirical evaluation and to facilitate dissemination of the project's results by researchers, educators and application builders.
