CS 498, Section EA Introduction to Knowledge Representation and Reasoning Autumn 2004 Tentative Course Syllabus 
Approximate Schedule 
Session  Date  Topic  Readings  Sample Application Reading 
Assignment 



Knowledge Representation and Reasoning  Mobile Robotics: [Amir & MaynardReid '99] 
Homework #0 out  


Propositional logic: DPLL & Resolution  Formal Verification: [McFarland '93] [Barrett '03] 



Prime implicates/implicants and consequence finding  TBA  Homework #0 due  


Binary Decision Diagrams  TBA  Homework #1 out  


FirstOrder Logic  Temporal reasoning: [Russell & Norvig '03], ch. 10 



Resolution in FirstOrder Logic  Temporal reasoning: [Russell & Norvig '03], ch. 10 
Homework #1 due  


Resolution strategies 
[Genesereth & Nilsson '87] ch.45,
slides lec. 14, based on slides by Daniel Lehmann and Leo Joskowicz

TBA  


Resolution with equality  TBA  


Partitioning and Treewidthbased methods  Spatial reasoning: [MacCartney etal. '03] Planning: [Amir & Engelhardt '03] 
Homework #2 out  


Probabilistic Graphical Models 
[Russell & Norvig '03], pp. 462510 (ch. 1314),
Slides lec. 6 (revised) (based on slides by Lise Getoor), and
alternate slides (based on AIMA2e slides from Stuart Russell),

Sensor Networks: [Crick & Pfeffer '03] 



Probabilistic inference 
[Russell & Norvig '03], pp. 462510 (ch. 1314),
Slides lec. 6 (revised) (based on slides by Lise Getoor), and
alternate slides (based on AIMA2e slides from Stuart Russell),

Sensor Networks: [Crick & Pfeffer '03] 
Homework #2 due 


Exact and Approximate Inference 
[Russell & Norvig '03], pp. 511528, [MacKay '98] and demo, Slides lec.6 (based on slides by Lise Getoor) Slides lec.7 (based on slides by Gal Elidan) 
Vision: [Tu & Zhu '02] Medical Diagnosis: [Wei & Altman '97] Molecular Biology: [Segal etal. '03] 



Sampling & Monte Carlo Methods 
[Russell & Norvig '03], pp. 511528, [MacKay '98] and demo, Slides lec.7 (based on slides by Gal Elidan) 
Vision: [Tu & Zhu '02] 



BN Inference: hybrid networks, local structure 
[Russell & Norvig '03], pp. 511528, [MacKay '98] and demo, Slides lec.6 (based on slides by Lise Getoor) Slides lec.7 (based on slides by Gal Elidan) 
Vision: [Tu & Zhu '02] Medical Diagnosis: [Wei & Altman '97] Molecular Biology: [Segal etal. '03] 
Homework #3 out 


Representation of Time: Situation Calculus  Temporal reasoning  


Representation of Time: Event Calculus and Action Languages  Temporal reasoning  Homework #3 due  


Situation Calculus: continuous time, ramifications, concurrent events, nondeterministic effects  Temporal reasoning  


Decision making with situation calculus  Temporal reasoning  Homework #4 out  


Dynamic Bayesian Networks 
[Russell & Norvig '03], ch. 15 or
[Jordan '04] ch. 20 (available next to my office door (Siebel 3314)),
slides lec. 9 (based on AIMA2e slides on DBNs from Stuart Russell),

Speech recognition: [Rabiner '89] 



Approximate inference in DBNs  Sensor Networks:
[Coates '04] Mobile Robots: [Fox etal '01] SLAM: [Paskin '03] 
Homework #4 due  


Logical filtering  Adventure games: TBA 
Homework #5 out  


Logical Representation of Space: RCC8 and others  Spatial reasoning  


Probabilistic Representation of Shape  Spatial reasoning  Homework #5 due  


Shape and Time  Spatial reasoning  Homework #6 out  


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



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


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



(a) Resolution with probabilistic relational models (b) probabilistic equational reasoning  TBA  Homework #7 out  


Modal Logics: Knowledge and Belief  Adventure Games   


Sensing and Knowledge Posters session (5pm7pm) 
Biology:
[Xing etal '03] information retrieval: [Blai etal '02] 
Homework #7 due Final project submission 



Final Exam 
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 
[Russell & Norvig '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 
[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 
Key  Authors  Title 
Key  Authors  Title 
Key  Authors  Title 
Key  Authors  Title 
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 