CS 598, Section EA Logic in Artificial Intelligence University of Illinois, Urbana-Champaign Spring 2009 Course Syllabus

Session	Date	Topic	Readings	Sample Application Reading	Assignment
1	Jan 20	Logic in AI: Introduction and overview	Slides Lecture 1, [McCarthy '58]		Signup for paper presentations begins
2	Jan 22	Classical logic: review of FOL and Propositional Logic	Slides Lecture 2, Ch. 2-3 from [Genesereth & Nilsson '87]
3	Jan 27	Examples: Can Do with Situation Calculus	Slides Lecture 3, Ch. 3 of [Reiter '01]
-	Jan 29	CLASS CANCELLED
4	Feb 3	Logical-Probabilistic Inference in NLP	Slides Lecture 4 by Hannaneh Hajishirzi
5	Feb 5	Propositional Inference, Soundness, and Completeness	Slides Lecture 5 by Mahesh Viswanathan, Ch. 4-5 from [Genesereth & Nilsson '87]
6	Feb 10	Key Theorems: Compactness, Completeness, Incompleteness, Craig Interpolation, Beth Definability	Sec 2.1 in [Amir '98], Slides Lecture 6
7	Feb 12	Key Theorems: Compactness, Completeness, Incompleteness, Craig Interpolation	Sec 2.1.5 in [Amir '98], Slides Lecture 7
8	Feb 17	Key Theorems: Beth Definability; Applications	Sec 2.1.5 in [Amir '98], Slides Lecture 8	[Amir & McIlraith '05], [Ramachandran & Amir '05]
9	Feb 19	Project ideas; Applications	Slides Lecture 9
10	Feb 24	Nonmonotonic Logics	Sec 3.1 in [Amir '98], Slides Lecture 10
11	Feb 26	Demo Applications (short class)
12	Mar 3	Demo Applications	Sec 3.1 in [Amir '98], Slides Lecture 12,
13	Mar 5	Nonmonotonic Reasoning Application	Slides Lecture 13
14	Mar 10	Modal Logics	Sec 2.3 in [Amir '98], Slides Lecture 14
15	Mar 12	Modal Logics	Slides Lecture 15		Proposal 1 due;
16	Mar 17	Complexity and Decidable Fragments of FOL	Slides Lecture 16		Signup for paper presentations ends
17	Mar 19	Temporal reasoning formalisms; Description Logics	Slides Lecture 17
18	Mar 31	Paper Presentation: Nonmonotonic Reasoning	[Delgrande '07]	Lori Coulter	Proposal 2 due
19	Apr 2	Paper Presentation: Approximate Theories	[Doherty, Lukaszewicz & Szalas 2001]	Juan Mancilla
20	Apr 7	Paper Presentation: Model Counting	[Gomes, Sabharwal & Selman 2006]	Abner Guzman Rivera
21	Apr 9	Projects mid-semester review			5 min. presentations in class
22	Apr 14	Paper Presentation: NLP and Formal Languages	[Kate et al. 2005]	Dan Goldwasser
23	Apr 16	Paper Presentation: Belief Revision and Update	[Giunchiglia & Walsh 1992]	Jaesik Choi ()
24	Apr 21	Paper Presentation: Approximate Theories	[McGuinness, Shvaiko, Giunchiglia & da Silva 2004]	Juan Mancilla (Cheng Xiang Zhai)
25	Apr 23	Paper Presentation	[Michael & Valiant 2008]	Dan Goldwasser (Julia Hockenmaier)
26	Apr 28	Paper Presentation: Nonmonotonic Reasoning	[Doherty & Szalas 2008]	Abner Guzman Rivera
27	Apr 30	Paper Presentation: Logic and Probabilities	[Kumar 2005]	Jaesik Choi (Dan Roth)
28	May 5 (2pm-3:15pm)	Paper Presentation	[Delgrande 2008]	Lori Coulter
29	May 5 (5pm-7pm)	Posters session			final project submission

Papers for Presentations

 

Number	Topic ()	Paper/s	Sample Application Reading	Presenter
1	Data Structures	[Darwiche & Marquis 2002]	CFDs
2	Preferences; Nonmonotonic Reasoning	[Doherty & Szalas 2008]	CFDs	Abner Guzman Rivera
3	Learning and Knowledge Representation	[Michael & Valiant 2008]	CFDs	Dan Goldwasser
4	Belief Revision and Update	[Delgrande 2008]	CFDs	Lori Coulter
5	Data Structures	[Hunter & Delgrande 2007]	CFDs
6	Approximate Theories	[Doherty, Lukaszewicz & Szalas 2001]	CFDs	Juan Mancilla
7	Approximate Theories	[Giunchiglia & Walsh 1992]	CFDs	Jaesik Choi
8	Approximate Theories	[Ghidini & Giunchiglia 2004]	CFDs
9	Semantic Mapping and Description Logics	[McGuinness, Shvaiko, Giunchiglia & da Silva 2004]	CFDs	Juan Mancilla
10	Logic and Probabilities	[Kumar 2005]	CFDs	Jaesik Choi
11	Model Counting	[Gomes, Sabharwal & Selman 2006]	CFDs	Abner Guzman Rivera
12	Approximate Theories	[del Val 2004]	CFDs
13	Approximate Theories	[Selman & Kautz 2006]	CFDs
14	Nonmonotonic Reasoning	[Delgrande 2007]	CFDs	Lori Coulter
15	Connecting NLP and Formal Languages	[Kate et al. 2005]	CFDs	Dan Goldwasser

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
[Genesereth & Nilsson '87]	Michael R. Genesereth and Nils J. Nilsson	Logical Foundations for Artificial Intelligence
[Reiter '01]	Raymond Reiter	Knowledge in Action: Logical Foundations for Specifying and Implementing Dynamical Systems
[Amir & Maynard-Reid '99]	Eyal Amir and Pedrito Maynard-Reid II	Logic-Based Subsumption Architecture
[Ramachandran & Amir '05]	Deepak Ramachandran and Eyal Amir	Compact Propositional Encodings of First-Order Theories
[Russell & Norvig '03]	Stuart Russell and Peter Norvig	Artificial Intelligence, a Modern Approach
[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
[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 '05]	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
[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
[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
[Baumgartner '00]	Peter Baumgartner	FDPLL - A First-Order Davis-Putnam-Logeman-Loveland Procedure
[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
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.