Tutorial to be presented at IJCAI-05: Principles of AI Problem Solving Adnan Darwiche, UCLA (University of California, LA) Rina Dechter, UCI (University of California, Irvine) Hector Geffner, ICREA -- Universitat Pompeu Fabra (Barcelona) Short Description: Most of the AI techniques that have been found useful in a wide range of areas including Search, Planning, SAT, Constraints, Bayesian Neworks, and Markov Decision Processes, can be understood along a few dimensions, and are expressions of a small core of concepts and principles. In this tutorial, we articulate this basic core of ideas aiming at a coherent, comprehensive, and modern view of AI Problem Solving. We focus on optimal problem solving over various state and variable-based (graphical) models used in AI, and classify current techniques in two classes: those based on search and inference, and those based on pure inference and no search. In the former class, we analyze the notions of branching and pruning (either with lower bounds or constraint propagation), along with the notions of learning (in both SAT/CSPs and State Models), decomposition, and caching. In the latter class, we consider the concepts of variable elimination, join tree decomposition, and compilation. We also analyze the relation among these notions, their time and space complexity, and how they are currently used for solving various tasks of interest in AI. - Target Audience: Researchers and students who have taken a basic AI class, and practitioners interested in the foundations, achievements, and challenges in AI Problem Solving, and the relations among the different subfields. - Why the tutorial topic may be of interest? Because knowledge of AI problem solving currently fragmented in a number of subfields, yet it is increasingly clear that there is an underlying unity that should be exposed and exploited. - Presenters Adnan Darwiche Computer Science Department 4532D Boelter Hall University of California Los Angeles, CA 90095-1596, USA http://www.cs.ucla.edu/~darwiche Background: Automated Reasoning; Probabilistic and Deductive Reasoning; Compilation, Diagnosis Rina Dechter Information and Computer Sciences Dept. University of California, Irvine 444 Computer Science Building Irvine, CA 92697-3425, USA http://www.ics.uci.edu/~dechter Background: Constraint Processing, Reasoning with Graphical Models Hector Geffner Universitat Pompeu Fabra Paseo de Circunvalacion 8 08003 Barcelona, SPAIN http://www.tecn.upf.es/~hgeffner Background: Planning, Knowledge Representation ---- Outline (tentative 11/2004) 1. Models, languages, and tasks: WHAT is to be solved Models based on states: Basic state models: Determinism and Full Information Modeling Uncertainty and Feedback, MDPs Factored Specification of state models; Strips Planning and variations Models based on variables (Graphical Models) Constraint Satisfacion Models, SAT Bayesian Networks, Influence Diagrams Tasks over these models: satisfaction, optimization (e.g, constraint optimization, most probable explanation), enumeration (model counting, probabilistic inference, etc) Translations and Correspondences; Complexity Issues 2. Solving problems with Search and Inference: - Search in state models: [Basic Algorithms] Heuristic Search: A*, IDA*, Depth-First Branch and Bound [Pruning: Lower Bounds] Getting the Heuristics, Relaxations in Planning and elsewhere [Branching] Problems with high branching factors; Branching with commitments, Branching in the TSP and Partial Order Planning [Learning] Improving the heuristics and solving problems by means of Bellman Updates; LRTA* and beyond - Search in variable-based models (Graphical Models) [Basic Algorithms] Backtracking [Pruning: Constraint Propagation] Constraint Propagation as Inference in Relaxed Model: Arc-Consistency; other local-consistency notions [Branching:] Branching by posting constraints (equalities, inequalities, precedences, etc); Heuristics for Selecting Branching points Relations between Variable and State models [Learning and Backjumping]: Taking advantage of structure for analyzing failure and finding culprits. [Decomposition and Caching:] Taking advantage of structure for decomposing problem into subproblems, and storing solutions for avoiding repeated searches. Relations; Complexity Results 3. Solving problems with pure inference and no search - Variable Elimination: projecting a variable away from a problem and recovering the solution by extending solution to projected problem. The induced Graph. Complexity. Approximations. - Join tree Algorithms: Trees are easy: Converting Graphs into Trees by Clustering Variables. Relation to Variable Elimination. Complexity. - Compilation: Converting a theory into an equivalent theory with better computational properties. Compilation in Variable Elimination and Join Tree Algorithms. Compilation of Propositional Representations into OBDDs, DNNFs, and other target languages. Complexity of various operations, and succintness of languages. Applications. 4. Wrap up