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