CS 497, Section EA Reasoning in Artificial Intelligence Spring 2004 Tentative Course Syllabus 
Approximate Schedule 
Session  Date  Topic  Readings  Sample Application Reading 
Assignment 



Introduction: Knowledge Representation and Reasoning  Mobile Robotics: [Amir & MaynardReid '99] 
Signup for paper presentations begins  


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



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



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



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



Treewidthbased methods  Spatial reasoning: [MacCartney etal. '03] Planning: [Amir & Engelhardt '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] 



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] 



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] 



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



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] 



Logical filtering  Adventure games: TBA 



Logical Filtering, and projects  Adventure Games  Signup for paper presentations ends  


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

TBA  Bill Davis 


Paper presentation: logic: prime implicates/implicants and consequence finding  TBA  Proposal 1 due Alex Klementiev 



Paper presentation: (a) logic:
SAT via stochastic local search (b) logic & probabilities: equational reasoning 
Planning via SAT: (a) [Kautz etal '96], [Kautz & Selman '96] (b) Coreference resolution: TBD 
(a) Geoffrey Levine and (b) Arthur Kantor 



Paper presentation: probabilities: (a) Particle Filtering  Sensor Networks:
[Coates '04] Mobile Robots: [Fox etal '01] 
Presentation by Hanning Zhou  


Paper presentation: probabilities: (a) Loopy belief propagation  [McEliece, MacKay & Cheng '98]  Extended proposal due Presentation by Jakob Metzler 



Paper presentation: probabilities: (a) resolution with probabilistic relational models (b) logic & probabilities: equational reasoning  TBA  (a) Rodrigo Braz, (b) Arthur Kantor  


Paper presentation: probabilities: (a) Survey propagation  TBA  Hannaneh Hajishirzi  


Paper presentation: logic: (a) dynamic backtracking/ordering for SAT (b) clause/variable ratio in SAT 
TBA  (a) Phil Oertel (b) Xiaoxin Yin 



Projects midsemester review  
35 min. presentations in class  


Paper presentation: dynamic systems  SLAM: [Paskin '03] 
Shiau Hong Lim (if time permits: Phil Oertel) 



Paper presentation: probabilistic reasoning: (a) continuous variables, (b) Kalman filtering  SLAM (b) SLAM2.0 
(a) Michael Simon and (b) Joseph Tucek 



Paper presentation: constraint satisfaction problems  TBA  Kenton McHenry (if time permits: Phil Oertel) 



Paper presentation: dynamic probabilistic relational models  TBA  Anna Yershova  


Paper presentation: logic: decidable fragments of FOL  TBA  Deepak Ramachandran  


Paper presentation: logic: Binary Decision Diagrams  TBA  Afsaneh Shirazi  


Posters session (5pm7pm)  Biology:
[Xing etal '03] information retrieval: [Blai etal '02] 
Presentation by Vince Horrell final project submission 
Papers for Presentations 
Number  Topic  Paper/s  Sample Application Reading 
Presenter 


SAT via stochastic local search  Planning via SAT: [Kautz etal '96], [Kautz & Selman '96] 
Geoffrey Levine  

Binary Decision Diagrams  TBA TBA 
Afsaneh Shirazi  

Consequence finding  TBA TBA 


Prime implicates/implicants  TBA TBA 


Constraint satisfaction problems  TBA TBA 
Kenton McHenry  

Equational reasoning in FOL  Commonsense reasoning TBA 


DPLL in FOL  TBA TBA 


FOL: decidable fragments  Formal verification TBA 
Deepak Ramachandran  

Treewidthfinding algorithms  TBA TBA 


Probabilistic inference with continuous variables  TBA TBA 
Michael Simon  

MetropolisHastings: Theory and examples  TBA TBA 


Dynamic Probabilistic Relational Models  TBA TBA 
Anna Yershova  

Variational approximations for probabilistic inference  Biology:
[Xing etal '03] information retrieval: [Blai etal '02] 
Vince Horrell  

Loopy belief propagation  Turbo Coding [McEliece, MacKay & Cheng '98] 
Jakob Metzler  

Resolution in firstorder probabilistic models  TBA TBA 
Rodrigo Braz  

SAT via probabilistic reasoning  TBA TBA 
Hannaneh Hajishirzi  

Dynamic Bayes networks and particle filtering  Sensor Networks:
[Coates '04] Mobile Robots: [Fox etal '01] 
Hanning Zhou  

Kalman filtering  SLAM SLAM2.0 
Joseph Tucek  

Factored inference with DBNs  SLAM: [Paskin '03] 
Shiau Hong Lim  

Resolution strategies  TBD TBD 
Bill Davis  

Probabilistic equational reasoning  Coreference resolution TBD 
Arthur Kantor  

Dynamic backtracking for SAT  TBD TBD 
Phil Oertel  

Clauses/Variables ratio in SAT  TBD TBD 
Xiaoxin Yin  

Dynamic ordering strategies for SAT (*NOTE: SAME AS 21)  TBD TBD 
(taken)  

Decayed MCMC  Tracking [Khan etal. '03] 
Projects 
Number  Topic  Presenter 


Logical filtering with a firstorder language  Afsaneh Shirazi 

Combining logical filtering and stochastic filtering  Joseph Tucek 

A system for the control of a robotic arm  Anna Yershova 

Image segmentation using MCMC: Implementation  Vince Horrell 

Factored DBN for car tracking  Shiau Hong Lim 

Comparing CSP algorithms  Kenton McHenry 

Identity Uncertainty for NL Meaning  Arthur Kantor 

Kriegspiel  Jakob Metzler 

SAT search for stochastic planning  Geoffrey Levine 

Multirelational correlation analysis  Xiaoxin Yin/td> 

Poole's PRMs inference is correct  Rodrigo de Salvo Braz 

Interactive game observation and retention  Deepak Ramachandran 

Survey propagation for dynamic settings  Hannaneh Hajishirzi 

Commonsense knowledge retrieval  Phil Oertel 

PCFGs vs BNs  Michael Simon 

Orienting polygonal parts using filtering  Alexandre Klementiev 

Resolution on reconfigurable hardware  William B. Davis 

Inference with mixture of uniforms  Hanning Zhou 
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 