CSC 244/444 Fall 2010 Calendar of Classes and Assignments

2. Knowledge representation and reasoning

B&L Ch 1

2. Read B&L Ch 2.1-2.4. Respond:
- What is the difference between a "logical symbol" and a "non-logical symbol"?
- What is an "interpretation" of logic?
- What does it mean for a FOL sentence A to be a logical consequence of another sentence B?
- Write two specific sentences such that one is a logical consequence of the other, and explain in detail (using the definition of logical consequence) why that is the case.
Due by 10pm Monday Sept 13.

3. Read B&L Ch 2.5. Respond:
- Describe the relationship between logical consequence, unsatisfiability, and validity.
- What is the relationship between the entailment symbol "|=" and the logical connective "=>"?
Due by 10pm Wednesday Sept 15.

3. The language of first-order logic

B&L Ch 2

4. The language of first-order logic, continued

Read B&L Ch 3. Free-form response.
Due by 10pm Monday Sept 20.

Exercise Set 1: Interpretations & Models
Due (hardcopy) start of class Tuesday Sept 28.

5. Expressing Knowledge

B&L Ch 3

4. Read B&L Ch 4. Respond:
- What is the important different between an empty clausal formula and a formula containing the empty clause?
- What is a resolution derivation?
- What does it mean to say resolution is "refutation complete"?
Due by 10pm Monday Sept 27

6. Resolution

B&L Ch 5

7. Resolution, continued

Exercise Set 2: Resolution Proofs
Due (hardcopy) start of class Thursday Oct 7

5. Reading: B&L Ch 4 Exercises 5 and 6 (don't solve them, just read them); also Section 2.3 of the paper by Gomes et al., Satisfiability Solvers, 2008 (See course reserves).
Respond:
- Create an example, different from the one in the text, of using the "big dot" operator defined in Exercise 5.
- Answer 6(a): show how you could modify the pseudo-code for DP to return a satisfying assignment (set of literals).
- What might be the relationship between your modified DP algorithm and the "tree of partial interpretations" that I presented in the proof of completeness of resolution in class today?
- If you consider DP and Walksat to be search algorithms, what is the difference between the state space searched by DP and the state space searched by Walksat?
Due by 10pm Wednesday Oct 6th.

8. Resolution, continued

9. Resolution, continued

10. Basic satisfiability algorithms

B&L Ch 5 exercises 5 and 6

Section 2.3 of C. P. Gomes, H. Kautz, A. Sabharwal, & B. Selman, Satisfiability Solvers, in F. van Harmelen, V. Lifschitz, & B. Porter, Eds., Handbook of Knowledge Representation, in the series Foundations of Artificial Intelligence, Vol. 3, Elsevier, 2008. (See course reserves)

11. Planning as satisfiability

A. Blum and M. Furst, Fast Planning Through Planning Graph Analysis, Artificial Intelligence, 90:281-300 (1997).

Henry Kautz and Bart Selman, Pushing the Envelope: Planning, Propositional Logic, and Stochastic Search, Proc. AAAI-96.

12. Modern satisfiability algorithms

C. P. Gomes, H. Kautz, A. Sabharwal, & B. Selman, Satisfiability Solvers, in F. van Harmelen, V. Lifschitz, & B. Porter, Eds., Handbook of Knowledge Representation, in the series Foundations of Artificial Intelligence, Vol. 3, Elsevier, 2008. (See course reserves)

Midterm Review Sheet

13. Horn Clauses

B&L Ch 5

14. Prolog

B&L Ch 6

ancestor.pl

genesi.pl

happy.pl

list.pl

Reading: B&L Ch 11, Sections 11.1, 11.2.1-11.2.4, and 11.4. Respond:
- What is the connection between "negation as failure" (Sec. 6.7) and the closed world assumption?
- Is the closed world assumption always consistent when applied to a Horn theory?
- How can the closed world assumption be written in Default Logic?
Due: Monday Nov 1, 10:00pm by Blackboard Turn In (NOT email)

15. More Prolog

schema.pl

magi.pl

minizebra.pl

simpleio.pl

16. Default Reasoning

Quasigroup Demo

B&L Ch 11

Programming Assignment 2: Problem Solving in Prolog
Due by Blackboard Turn In 11:59pm on Thursday December 9th.

Reading: B&L Ch 13. Respond:
- Is every abductive diagnosis also a consistency based diagnosis? What about the reverse? Why?
- Describe a real life example where you would be happy to accept a consistency-based diagnosis, and one where you would insist on an abductive diagnosis.
Due: Monday Nov 8, 10:10pm by Blackboard Turn In (NOT email)

16. Explanation and diagnosis

B&L Ch 13

17. SAT-modulo theories

C. Barrett, R. Sebastiani, S. A. Seshia, & C. Tinelli, Satisfiability Modulo Theories, in A. Biere, H. van Maaren, M. Heule and Toby Walsh, Eds., Handbook of Satisfiability, IOS Press, 2009.(See course reserves)

Example of eager encoding

Homework (due Nov 18 in class)

TDPLL Online Schema.pdf

19. Reasoning about the knowledge of multiple agents

J. Halpern, Reasoning about knowledge: a survey, in D. Gabbay, C. J. Hogger, and J. A. Robinson, Eds.,Handbook of Logic in Artificial Intelligence and Logic Programming, Vol. 4, Oxford University Press, 1995.

20. Limited and approximate inference

Liu, Y., Lakemeyer, G., and Levesque, H., A logic of limited belief for reasoning with disjunctive information, Proc. of the KR-2004 Conference, Whistler, BC, 2004.

H. Kautz and B. Selman, A General Framework for Knowledge Compilation, Proceedings of the First World Conference on the. Fundamentals of Artificial Intelligence, Paris, 1991.

21. Bayesian networks

B&L 12.1-12.4; R&N 14.5

22. Bayesian reasoning using MAX-SAT and model-counting

J. D. Park, Using Weighted MAX-SAT Engines to Solve MPE, Proceedings of the Eighteenth National Conference on Artificial Intelligence (AAAI-02), Edmonton, Alberta, 2002, pages 682-687.

T. Sang, P. Beame, & H. Kautz., Solving Bayesian Networks by Weighted Model Counting, Proceedings of the Twentieth National Conference on Artificial Intelligence (AAAI-05), Pittsburgh, PA, 2005.

Slide deck 1

Slide deck 2

Homework - due in class Dec 7

23. Markov logic

P. Domingos & D. Lowd, Markov Logic: An Interface Layer for Artificial Intelligence, Synthesis Lectures on Artificial Intelligence and Machine Learning, Morgan & Claypool, 2009. (See course reserves)

Homework - due in class Dec 9

24. Markov logic, continued (additional slides)

25. Review of course since midterm and limits of logic

pdf version of slides