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 



Background: Knowledge Representation paradigm in AI  [McCarthy '58] Mobile Robotics: [Amir & MaynardReid '99] 



Propositional reasoning: Resolution  [Rish & Dechter '00] Formal Verification: [McFarland '93] [Barrett '03] 



Prime implicates/implicants and consequence finding  [Slagle etal '70]  


Binary Decision Diagrams 
[Groote & Zantema '00], BDDs in FOL: [Groote & Tveretina '03] 
Homework #1 out  


FirstOrder Logic  [Genesereth & Nilsson '87], ch. 3 Temporal reasoning: [RN '03], ch. 10 



FirstOrder Logic  [Genesereth & Nilsson '87], ch. 3 Temporal reasoning: [RN '03], ch. 10 



Resolution in FirstOrder Logic  [Genesereth & Nilsson '87], ch. 4 Temporal reasoning: [RN '03], ch. 10 



Resolution in FirstOrder Logic  [Genesereth & Nilsson '87], ch. 4 Temporal reasoning: [RN '03], ch. 10 
Homework #1 due  


Resolution in FirstOrder Logic  [Genesereth & Nilsson '87], ch. 4 Temporal reasoning: [RN '03], ch. 10 



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  


Partitioning and Treewidthbased methods 
[Dechter '99] Spatial reasoning: [MacCartney etal. '03] Planning: [Amir & Engelhardt '03] 



Resolution with equality  [Chang & Lee '73] ch. 8, [NieRub '01]  Homework #2 out Project Proposal due 



Probabilistic Graphical Models and Inference 
[RN '03], pp. 462510 (ch. 1314.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 


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 


Sampling & Monte Carlo Methods 
[RN '03] pp. 511519 (ch. 14.5),
[MacKay '98] and demo,
Slides lec. 15 (based on slides by Gal Elidan)

Vision: [Tu & Zhu '02] Medical Diagnosis: [Wei & Altman '97] Molecular Biology: [Segal etal. '03] 



Sampling & Monte Carlo Methods 
[RN '03] pp. 511519 (ch. 14.5),
[MacKay '98] and demo,
Slides lec. 15 (based on slides by Gal Elidan)

Vision: [Tu & Zhu '02] Medical Diagnosis: [Wei & Altman '97] Molecular Biology: [Segal etal. '03] 



Multivariate Gaussians 
[Jordan '04] ch. 13 (given in class),
[Lerner & Parr '01],
Slides lec. 17 (based on slides by Michael Simon)

SLAM SLAM2.0 
Homework #2 due 


Review of logic and logical reasoning  Extended Project Proposal due  


midterm 6pm8pm

Siebel Center 2124  


Hybrid Bayes Networks; Bayesian machine learning 
[Jordan '04] ch. 13 (given in class),
[Lerner & Parr '01],
Slides lec. 17 (based on slides by Michael Simon)

SLAM SLAM2.0 



Representation of Time: Situation Calculus  Temporal reasoning  


Situation Calculus: Representation and inference with FOL  Temporal reasoning  Homework #3 out  


Continuous time, ramifications, concurrent events, nondeterministic effects  [Reiter '96], [Boutilier, Reiter, Price '01]




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] 



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 


  Thanksgiving Recess     


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 


Logical filtering  Adventure games: [Hlubocky & Amir '04] 
Homework #4 out  


Firstorder probabilistic models  Citation matching: [Pasula & Russell '01], [Pasula etal. '02] 
 


Restricted language: description logics 
Medical informatics:
[OpenGalen '03]
NLP/NLG and Adventure Games: [Gadsil, Koller, & Striegnitz '01] Semantic Web: [Horrocks '02] 



Final Exam Final project submission Homework #5 due 
Possible Projects 
Number  Topic  Presenter 


extension of lock resolution using craig's interpolation theorem  

hybrid reasoning of logic and probabilities via partitioning (requires knowledge of FOPL, at least Halpern's work)  

logical filtering with a firstorder language  

logical filtering with BDDs  

activity detection using filtering (any method)  

SLAM2.0 improved and applied to a mobile robot  

Combining logical filtering and stochastic filtering  

Survey propagation for dynamic settings (e.g., planning via SAT)  

Approximation algorithm for hypertreewidth  

Implementation of an algorithm for planar treewidth  

Filtering in an adventure/strategy game  

Labeling image segments with words (using a probabilistic graphical model)  

Implementation of MessagePassing as a restriction strategy for reasoning in FOL  

Complete ``holes'' in Poole's paper on resolution in firstorder probabilistic models  

Equational reasoning in firstorder probabilistic models  

FirstOrder DPLL with equality  

LSAlike robot control architecture with probabilities  

Learning action models via filtering  

MCMC for image segmentation  

Robot localization for a basketball game  

LSAbased control system for a robotic arm 
Bibliography 
Key  Authors  Title 

[McCarthy '58]  John McCarthy  Programs with Common Sense 
[Amir & MaynardReid '99]  Eyal Amir and Pedrito MaynardReid II  LogicBased 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  PartitionBased Reasoning for FirstOrder and Propositional Theories 
[MacCartney etal. '03]  B. MacCartney, S. McIlraith, E. Amir, & T. Uribe  Practical PartitionBased 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  RaoBlackwellised Particle Filtering for Dynamic Bayesian Networks, Tutorial, and slides 
[Doucet etal '00b]  Arnaud Doucet, Simon Godsill, and Christophe Andrieu  On sequential MonteCarlo 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  Firstorder 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) 
[ElHay & Friedman '01]  T. ElHay and N. Friedman  Incorporating Expressive Graphical Models in Variational Approximations: ChainGraphs and Hidden Variables 
[Tu & Zhu '02]  Zhuowen Tu and SongChun Zhu  Image Segmentation by DataDriven 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  Genomewide Discovery of Transcriptional Modules from DNA Sequence and Gene Expression 
[Baumgartner '00]  Peter Baumgartner  FDPLL  A FirstOrder DavisPutnamLogemanLoveland Procedure 
[Khan etal. '03]  Z. Khan, T. Balch, and F. Dellaert  An MCMCbased 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 FirstOrder 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 BinaryDecision 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 firstorder 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  Paramodulationbased 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 