UIUC CS 498, Section EA
Knowledge Representation and Reasoning in Artificial Intelligence
Autumn 2004
Tentative Course Syllabus

Approximate Schedule

Session Date Topic Readings Optional Reading and Applications Assignment
1
Aug 31
Background: Knowledge Representation paradigm in AI [McCarthy '58]
Mobile Robotics:
[Amir & Maynard-Reid '99]
 
2
Sep 2
Propositional reasoning: Resolution [Rish & Dechter '00]
Formal Verification:
[McFarland '93] [Barrett '03]
 
3
Sep 7
Prime implicates/implicants and consequence finding [Slagle etal '70]  
4
Sep 9
Binary Decision Diagrams [Groote & Zantema '00],
BDDs in FOL:
[Groote & Tveretina '03]
Homework #1 out
5
Sep 14
First-Order Logic [Genesereth & Nilsson '87], ch. 3
Temporal reasoning:
[RN '03], ch. 10
 
6
Sep 16
First-Order Logic [Genesereth & Nilsson '87], ch. 3
Temporal reasoning:
[RN '03], ch. 10
 
7
Sep 21
Resolution in First-Order Logic [Genesereth & Nilsson '87], ch. 4
Temporal reasoning:
[RN '03], ch. 10
 
8
Sep 23
Resolution in First-Order Logic [Genesereth & Nilsson '87], ch. 4
Temporal reasoning:
[RN '03], ch. 10
Homework #1 due
9
Sep 28
Resolution in First-Order Logic [Genesereth & Nilsson '87], ch. 4
Temporal reasoning:
[RN '03], ch. 10
 
10
Sep 30
Resolution strategies
[RN '03] ch. 9, slides lec. 10, based on slides by Alex Klementiev, Daniel Lehmann, and Leo Joskowicz
[Genesereth & Nilsson '87], ch. 5
 
11
Oct 5
Partitioning and Treewidth-based methods [Dechter '99]
Spatial reasoning:
[MacCartney etal. '03]
Planning:
[Amir & Engelhardt '03]
 
12
Oct 7
Resolution with equality [Chang & Lee '73] ch. 8, [NieRub '01] Homework #2 out
Project Proposal due
13
Oct 12
Probabilistic Graphical Models and Inference
[RN '03], pp. 462-510 (ch. 13-14.4), Slides lec. 13 by Deepak Ramachandran, and also Slides from last year (based on slides by Lise Getoor), and
Alternate slides (based on AIMA2e slides from Stuart Russell)
[Pearl '88] ch. 3
Sensor Networks:
[Crick & Pfeffer '03]
Presented by Deepak Ramachandran
14
Oct 14
Variational Approximate Inference
[Wainwright & Jordan '03],
Slides lec. 14 by Afsaneh Shirazi, and alternateSlides of Martin Wainwright
Tutorial Slides of Tommi Jaakola Presented by Afsaneh Shirazi
15
Oct 19
Sampling & Monte Carlo Methods Vision:
[Tu & Zhu '02]
Medical Diagnosis:
[Wei & Altman '97] Molecular Biology:
[Segal etal. '03]
 
16
Oct 21
Sampling & Monte Carlo Methods Vision:
[Tu & Zhu '02]
Medical Diagnosis:
[Wei & Altman '97] Molecular Biology:
[Segal etal. '03]
 
17
Oct 26
Multi-variate Gaussians SLAM
SLAM2.0
Homework #2 due
18
Oct 28
Review of logic and logical reasoning     Extended Project Proposal due
--
Nov 1
 
midterm 6pm-8pm
Siebel Center 2124  
19
Nov 2
Hybrid Bayes Networks; Bayesian machine learning SLAM
SLAM2.0
 
20
Nov 4
Representation of Time: Situation Calculus Temporal reasoning  
21
Nov 9
Situation Calculus: Representation and inference with FOL Temporal reasoning Homework #3 out
22
Nov 11
Continuous time, ramifications, concurrent events, nondeterministic effects [Reiter '96], [Boutilier, Reiter, Price '01]
 
23
Nov 16
Dynamic Bayesian Networks
[RN '03], ch. 15 or [Murphy '02] (given in class), slides lec. 23 (based on AIMA2e slides on DBNs from Stuart Russell),
Speech recognition:
[Rabiner '89]
 
24
Nov 18
Approximate inference in DBNs
[Boyen & Koller '98] [Doucet etal '00], [Doucet etal '00b], slides lec. 24 (based on slides by X. Boyen and D. Koller),
Sensor Networks: [Coates '04]
Mobile Robots: [Fox etal '01]
SLAM:
[Paskin '03]
Review of project progress
--
Nov 23, Nov 25
-- Thanksgiving Recess -- --
25
Nov 30
Approximate inference in DBNs
[Boyen & Koller '98] [Doucet etal '00], [Doucet etal '00b], slides lec. 25 (based on slides by X. Boyen, D. Koller, A. Doucet, N. de Freitas, K. Murphy, S. Russell, and S.H. Lim and H. Zhou),
Sensor Networks: [Coates '04]
Mobile Robots: [Fox etal '01]
SLAM:
[Paskin '03]
Homework #3 due
26
Dec 2
Logical filtering Adventure games:
[Hlubocky & Amir '04]
Homework #4 out
27
Dec 7
First-order probabilistic models Citation matching:
[Pasula & Russell '01], [Pasula etal. '02]
 
28
Dec 9
Restricted language: description logics Medical informatics: [OpenGalen '03] NLP/NLG and Adventure Games:
[Gadsil, Koller, & Striegnitz '01]
Semantic Web: [Horrocks '02]
 
29
Dec 16, 1:30pm-4:30pm
 
 
  Final Exam
Final project submission
Homework #5 due

Possible Projects

Number Topic Presenter
1
extension of lock resolution using craig's interpolation theorem  
2
hybrid reasoning of logic and probabilities via partitioning (requires knowledge of FOPL, at least Halpern's work)  
3
logical filtering with a first-order language  
4
logical filtering with BDDs  
5
activity detection using filtering (any method)  
6
SLAM2.0 improved and applied to a mobile robot  
7
Combining logical filtering and stochastic filtering  
8
Survey propagation for dynamic settings (e.g., planning via SAT)  
9
Approximation algorithm for hyper-treewidth  
10
Implementation of an algorithm for planar treewidth  
11
Filtering in an adventure/strategy game  
12
Labeling image segments with words (using a probabilistic graphical model)  
13
Implementation of Message-Passing as a restriction strategy for reasoning in FOL  
14
Complete ``holes'' in Poole's paper on resolution in first-order probabilistic models  
15
Equational reasoning in first-order probabilistic models  
16
First-Order DPLL with equality  
17
LSA-like robot control architecture with probabilities  
18
Learning action models via filtering  
19
MCMC for image segmentation  
20
Robot localization for a basketball game  
21
LSA-based control system for a robotic arm  

Bibliography
Key Authors
Title
[McCarthy '58] John McCarthy
Programs with Common Sense
[Amir & Maynard-Reid '99] Eyal Amir and Pedrito Maynard-Reid II
Logic-Based Subsumption Architecture
[RN '03] Stuart Russell and Peter Norvig
Artificial Intelligence, a Modern Approach
[Genesereth & Nilsson '87] Michael R. Genesereth and Nils J. Nilsson
Logical Foundations for Artificial Intelligence
[McFarland '93] Michael C. McFarland
Formal verification of sequential hardware: a tutorial
[Biere etal. '99] A. Biere, A. Cimatti, E.M. Clarke, M. Fujita, Y. Zhu
Symbolic model checking using SAT procedures instead of BDDs
[Barrett '03] Clark Barrett
Logic in Computer Science, NYU, Fall 2003
[OpenGalen '03] OpenGALEN, by Kermanog
GALEN common reference model, version 1.02, and software
[Baader & Nutt '03] Franz Baader & Werner Nutt
Basic Description Logics, Ch.2 in the Description Logic Handbook
[Franconi '03] Enrico Franconi
Natural Language Processing, Ch.15 in the Description Logic Handbook
[Gadsil, Koller, & Striegnitz '01] M. Gabsdil, A. Koller, and K. Striegnitz
Building a Text Adventure on Description Logic
[Horrocks '02] Ian Horrocks
DAML+OIL: a Description Logic for the Semantic Web
[Amir & McIlraith '03] Eyal Amir and Sheila McIlraith
Partition-Based Reasoning for First-Order and Propositional Theories
[MacCartney etal. '03] B. MacCartney, S. McIlraith, E. Amir, & T. Uribe
Practical Partition-Based Theorem Proving for Large Knowledge Bases
[Amir & Engelhardt '03] Eyal Amir and Barbara Engelhardt
Factored Planning
[Rish & Dechter '00] Irina Rish and Rina Dechter
Resolution versus Search: Two Strategies for SAT
[Doucet etal '00] Arnaud Doucet, Nando de Freitas, Kevin Murphy, Stuart Russell
Rao-Blackwellised Particle Filtering for Dynamic Bayesian Networks, Tutorial, and slides
[Doucet etal '00b] Arnaud Doucet, Simon Godsill, and Christophe Andrieu
On sequential Monte-Carlo sampling methods for Bayesian filtering
[Coates '04] Mark Coates
Distributed particle filters for sensor networks
[Fox etal '01] Dieter Fox, Sebastian Thrun, Wolfram Burgard, Frank Dellaert
Particle Filters for Mobile Robot Localization
[Moskewicz etal '01] M. W. Moskewicz, C. F. Madigan, Y. Zhao, L. Zhang, and S. Malik
Chaff: engineering an efficient SAT solver
[Ginsberg and McAllester '94] M. Ginsberg and D. McAllester
GSAT and Dynamic Backtracking
[Selman, Mitchell, and Levesque '97] B. Selman, D. Mitchell, and H. Levesque
Generating hard satisfiability problems
[MacKay '98] David MacKay
Introduction to Monte Carlo methods
[Crick & Pfeffer '03] Christopher Crick and Avi Pfeffer
Loopy belief propagation as a basis for communication in sensor networks
[Yedidia etal. '03] J.S. Yedidia, W.T. Freeman and Y. Weiss
Bethe free energy, Kikuchi approximations and belief propagation algorithms
[McEliece, MacKay & Cheng '98] R.J. McEliece, D. J. C. MacKay, and J. F. Cheng
Turbo decoding as an instance of Pearl's `belief propagation
[Poole '03] David Poole
First-order probabilistic inference
[Braunstein etal '03] A. Braunstein, M. Mezard, R. Zecchina
Survey propagation: an algorithm for satisfiability
[Amir & Russell '03] E. Amir and S. Russell
Logical Filtering
[Jaakola '00] T. Jaakola
Tutorial on variational approximation methods (slides)
[El-Hay & Friedman '01] T. El-Hay and N. Friedman
Incorporating Expressive Graphical Models in Variational Approximations: Chain-Graphs and Hidden Variables
[Tu & Zhu '02] Zhuowen Tu and Song-Chun Zhu
Image Segmentation by Data-Driven Markov Chain Monte Carlo
[Wei & Altman '97] L. Wei and R. B. Altman
An Automated System for Generating Comparative Disease Profiles and Making Diagnoses
[Segal etal. '03] E. Segal and R. Yelensky and D. Koller
Genome-wide Discovery of Transcriptional Modules from DNA Sequence and Gene Expression
[Baumgartner '00] Peter Baumgartner
FDPLL - A First-Order Davis-Putnam-Logeman-Loveland Procedure
[Khan etal. '03] Z. Khan, T. Balch, and F. Dellaert
An MCMC-based Particle Filter for Tracking Multiple Interacting Targets
[Marthi etal. '03] B. Marthi, H. Pasula, and S. Russell
Decayed MCMC Filtering
[Pfeffer '00] A. Pfeffer
Probabilistic Reasoning for Complex Systems
[Pasula & Russell '00] H. Pasula and S. Russell
Approximate Inference For First-Order Probabilistic Languages
[Pasula etal. '02] H. Pasula, B. Marthi, B. Milch, S. Russell, I. Shpitser
Identity Uncertainty and Citation Matching
[del Val '99] A. del Val
A New Method for Consequence Finding and Compilation for Restricted Languages
[de Kleer '92] J. de Kleer
An Improved Incremental Algorithm for Generating Prime Implicates
[Slagle etal. '70] J.R. Slagle, C.-L. Chang and R. Lee
A new algorithm for generating prime implicants
[Bryant '92] Randal Bryant
Symbolic Boolean manipulation with Ordered Binary-Decision Diagrams
[Andersen '92] Henrik Reif Andersen
An introduction to Binary Decision Diagrams
[Groote & Zantema '00] J.F. Groote and H. Zantema
Resolution and binary decision diagrams cannot simulate each other polynomially
[Groote & Tveretina '03] J.F. Groote and O. Tveretina
Binary decision diagrams for first-order predicate logic
[Sanghai, Domingo, & Weld '03] S. Sanghai, P. Domingo, and D. Weld
Dynamic Probabilistic Relational Models
[Rabiner '89] L.R. Rabiner
A tutorial on hidden Markov models and selected applications in speech recognition
[Lerner & Parr '01] U. Lerner and R. Parr
Inference in Hybrid Networks: Theoretical Limits and Practical Algorithms
[Bachmair & Ganzinger '95] L. Bachmair and H. Ganzinger
Basic Paramodulation
[NieRub '01] R. Nieuwenhuis and A. Rubio
Paramodulation-based theorem proving
[Dechter '99] R. Dechter
Bucket Elimination: A Unifying Framework for Reasoning
[Pearl '88] J. Pearl
Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference
[Jordan '04] M. Jordan
An Introduction to Probabilistic Graphical Models
[Wainwright & Jordan '03] M. Wainwright and M. Jordan
Graphical models, exponential families, and variational inference
Key Authors
Title
Key Authors
Title

Viewing PostScript and PDF

Depending on the computer you are using, you may be able to download a PostScript viewer or PDF viewer for it if you don't already have one.


Comments to Eyal Amir