UIUC CS 598, Section EA
Decision Making Under Uncertainty
University of Illinois, Urbana-Champaign
Spring 2007
Tentative Course Syllabus
Approximate Schedule (updated 1/31/2007)

 
Session Date Topic Readings Sample Application
Reading		 Assignment
1
Jan 17
Modeling Knowledge in Scrabble   Signup for paper presentations begins
2
Jan 19
Introduction to Decision Making and Uncertainty    
3
Jan 24
Bayesian Networks: Representation    
4
Jan 26
Bayesian Networks: Representation    
5
Jan 31
Bayesian Networks: Inference    
6
Feb 2
Bayesian Networks: Inference    
7
Feb 7
Bayesian Networks: Inference Complexity    
8
Feb 9
Treewidth Algorithms    
9
Feb 14
Classes CANCELED
 
   
10
Feb 16
Hidden Markov Models (HMMs) and Dynamic Bayesian Networks (DBNs)    
11
Feb 21
Inference in DBNs    
12
Feb 23
Markov Decision Processes (MDPs)    
13
Feb 28
Partially Observable MDPs (POMDPs)
[Littman; Brown U. thesis 1996] ch. 6-7, Slides lec.10 (using slides by Craig Boutilier)
   
14
Mar 2
Partially Observable MDPs (POMDPs)
[Littman; Brown U. thesis 1996] ch. 6-7, Slides lec.10 (using slides by Craig Boutilier)
  Signup for paper presentations ends; Proposal 1 due;
15
Mar 7
Partially Observable MDPs (POMDPs)
[Littman; Brown U. thesis 1996] ch. 6-7, Slides lec.10 (using slides by Craig Boutilier)
   
16
Mar 9
POMDPs
 
   
17
Mar 14
POMDPs
 
   
18
Mar 16
POMDPs
 
   
19
Mar 28
MOVED TO APRIL 2      
19
Mar 30
Paper Presentation: Reward Shaping in MDPs [Ng, Harada, & Russell; ICML '99]   Abdullah Muzahid; Extended proposal due
20
Apr 2
Paper Presentation: The challenge of poker   Aniruddh Nath
21
Apr 4
Paper Presentation: Stochastic Local Search for POMDP Controllers   Mark Sammons
22
Apr 6
Projects mid-semester review
 
  5 min. presentations in class
23
Apr 11
Paper Presentation: A probabilistic Approach to Solving Crossword Puzzles
[Littman, Keim, & Shazeer, AIJ 134 (1-2), 2002]

  		Quang X. Do
24
Apr 13
Paper Presentation: Planning with Sensing
[Bonet & Geffner; AIPS 2000]
  Yu Ru (Robin)
25
Apr 18
Paper Presentation: Hierarchical Reinforcement Learning
[Dietterich; ICML 1998]
  Jehanzeb Abbas
26
Apr 20
Paper Presentation: OPEN
 
TBA
TBA 		 
27
Apr 25
Paper Presentation: Planning with Sensing   Lih-Ching Chou
28
Apr 27
Paper Presentation: OPEN
   
   
29
May 2
Posters session (5pm-7pm)
 
  final project submission

Papers for Presentations

 
Number Topic (PO = Partially Observable; PL = Planning; ST = Stochastic; SM = Semantics; RL = Reinforcement Learning) Paper/s Sample Application
Reading		 Presenter
7
POMDPs (RL;ST) TBA
TBA 		 
8
Exploration (ST) TBA
TBA 		 
9
Utility elicitation and POMDPs (PL;ST) TBA
TBA 		 
10
POMDPs models customers TBA
TBA 		 
11
POMDP approximation TBA
TBA 		 
13
POMDP approximation TBA
TBA 		 
14
POMDP approximation    
15
First-Order MDPs    
16
Factored MDPs    
17
Monitoring POMDPs    
18
MDPs    
19
MDPs    
20
MDPs (survey)    
23
Programmable RL agents    
24
Inverse Reinforcement Learning    
25
Function Approximation in MDPs    
26
Reward Shaping in MDPs    
27
Factored MDPs    
28
POMDPs as DBNs    
29
Relational MDPs    
30
Approximating POMDPs    
31
POMDPs    
32
Approximating POMDPs    
33
Approximating POMDPs    
34
Approximating POMDPs    
35
Planning with Nondeterminism and Sensing    
36
Planning with Sensing    
37
Planning with Sensing    
38
Planning with Sensing: unifying view    
39
Risk-sensitive planning    
40
Poker Playing    
41
Solving Crossword Puzzles    
42
k-arm Bandit Problems    
43
Developmental Reinforcement Learning    

Possible Projects

Number Topic Presenter
1
Automatic Adventure-game player  
2
First-Order POMDPs  
3
Exact Factored MDPs  
4
Position Estimation for an autonomous car  
5
Stochastic Filtering via Logical Filtering  
6
Localization and Mapping with many world features  
7
Poker Playing  
8
Bridge Player  
9
First-Order Factored Planning  
10
Adventure-Game Exploration using Commonsense knowledge  
11
Approximate Deterministic POMDPs via Logical Filtering  
12
Relational Probabilistic Resolution in Dynamic Bayesian Networks  
13
POMDPs approximated via DBNs  
14
Robot control using a POMDP  
15
First-Order Reinforcement Learning  
16
Reshaping rewards using commonsense knowledge  
17
Partially observable LSA-based robot control architecture  
18
Reinforcement learning in deterministic domains  
19
POMDP model of a stock in the stock market  
20
Comparison of Approximation techniques for probabilistic inference  
21
LSA-based control system for a robotic arm  
21
Reward shaping for POMDPs  

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
[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
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
[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
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