January 13 (Tue), 2015 HW1 assigned (exercises 1.1 and 1.3 [P]), due Tuesday, January 20, 2015. Reading assigned: article by Brian Hayes linked to the course home page. Administrative information: textbook and syllabus. Please read handout with the grading policy for the course. Definitions of AI.
January 15 (Thu), 2015 Q1. More on definitions of AI. The definition of AI in the textbook. Disussion of Brian Hayes's paper, "The Manifest Destiny of Artificial Intelligence." (See elsewhere on web site for full reference.) The Church-Turing Thesis and the (Newell-Simon) Physical Symbol System Hypothesis. John Searle's Chinese Room argument and Hector Levesque's Summation Room counterexample. Agents. Examples of agents (started): Robot, Teacher, Medical Doctor, User Interface.
January 20 (Tue), 2015 Q2. HW1 collected. Chapter 1 completed, with emphasis on: Knowledge representation (1.4[P]); Computational limits (1.5.8 [P]).
January 23 (Thu), 2015 Assigned reading: Chapters 1 and 2 [P]. Q3. Graded HW1 returned. Causal transductions. Belief states. Discussion of the robot applet at aispace.com. Brief demonstration of its use. Chapter 2 almost completed.
January 27 (Tue), 2015 Chapter 2 completed. Detailed discussion of qualitative vs. quantitative reasoning. Chapter 3 (States and Search) stated.
January 29 (Thu), 2014 Ch.3 continued: blind (uninformed, non-heuristic) search algorithms. Slides from AIMA used: they are on the course website.
February 3 (Tue), 2015 Dijkstra's algorithm with detailed example and proof that it does not need to reopen closed nodes. Definition of heuristic function. Best-first search.
February 5 (Tue), 2015 A* with and without monotone heuristics. Detailed discussion of the difference between Dijkstra's algorithm and A*. Run-through of the Prolog code for A*; this code makes restrictive assumptions that are described in the comments. Use of the code to solve the Farmer, Wolf, Goat, and Cabbage problem. Proof of the admissibility of A* (proposition 3.1 [P]).
February 10 (Tue), 2015 Q5. Examples of use of A*. Admissibility of A*. Proof that monotonicity allows A* to avoid re-expanding closed nodes. DFS vs. backtracking. Dynamio programming (started).
February 12 (Thu), 2015 HW2 assigned: exercise 3.3[P], due 2015-02-19. Please use multiple-path pruning in all cases. Q6-Q9: exercises with DFS, heuristic DFS, BFS, and DP. Where do heuristics come from? Very often, the solution of simplified (relaxed) problems. Properties of heuristics computed by problem relaxation: admissibility and monotonicity.
February 17 (Tue), 2015 HW3 assigned: exercise 3.4[P], due 2015-02-24. The midterm exam originally scheduled for next week will be on March 3. Reminder: HW2 due on 2015-02-19. Please use the grids that are on the course web site and be neat. Example of A* search on the eight (sliding tile) puzzle using the "number of misplaced tiles" heuristic. Ertel's empirical results of A* on the 8-puzzle (Ertel). Proof that heuristics computed by problem relaxation are monotone. Chapter 4 ("Features and Constraints") started.
February 19 (Thu), 2015 HW2 collected. Q11. Ch.4 [P] ("Features and Constraints") continued. Definitions (4.1 and 4.2). Generate and test (4.3). Solving CSPs (Constraint Satisfaction Problems) Using Search (4.4). Introduction to consistency algorithms (4.5, through page 121).
February 24 (Tue), 2015 HW2 returned and discussed in great detail. HW3 collected. Reminder: midterm will be in one week. Note: exam will be closed book and include the first three chapters of the textbook.
February 26 (Thu), 2015 HW3 returned and discussed in great detail. Ch.4 [P] ("Features and Constraints") continued. The general arc consistency algorithm, with examples 4.15 and 4.19 in full detail. Reminder: midterm will be in on Tuesday, March 3. Note: exam will be closed book and include the first three chapters of the textbook.
March 3 (Tue), 2015 Midterm 1 (MT1).
March 5 (Thu), 2015 MT1 returned and discussed. Graduate and honors student presentations assigned. Chapter 4 [P] ("Features and Constraints") through Section 4.6.1 ("Exploiting Propositional Structure"), with a presentation of the DPLL (Davis-Putnam, Logemann, and Loveland) algorithm based on Rina Dechter's.
March 17 (Tue), 2015 HW4 assigned: exercise 4.1 [P], due on 2015-03-24. You are allowed to use the CSP applet in AISpace, but you must in any case turn in your work as a paper. Review of DPLL. The original DP (Davis-Putnam, 1960) algorithm for propositional satisfiability, which is a kind of variable-elimination algorithm customized for the Boolean formulas (in concjunctive normal form) case. The presentation is based on Irina Rish and Rina Dechter. "Resolution Versus Search: Two Strategies for SAT." Report R-80, Department of Information and Computer Science, University of California, Irvine, undated. Published under the same title in: Journal of Automated Reasoning. Volume 24, Issue 1/2 (special issue on SAT), pp. 225-275, January, 2000. Most of the material appears in various places (especially, pp. 152-153, 228-229, 272-273) in: Rina Dechter. Constraint Processing. Morgan-Kauffman, 2003. Variable elimination (section 4.7 [P]) started, with preliminaries on relational algebra from section A.3 [P}.
March 19 (Thu), 2015 Q12 on the (original, 1960) Davis-Putnam (DP) algorithm. Variable elimination, with simple examples (section 4.7 [P]).
March 24 (Tue), 2015 HW5 assigned: exercise 4.11 due on 2015-03-26. HW4 collected. Presentation on A* (BF*) with non-additive cost functions by Neema Kanapala and Andrey Balabokhin. Good discussion with questions and answers at the end. Bellman's principle of optimality. Non-serial dynamic programming (NSDP).
March 26 (Thu), 2015 HW4 parts (a)-(c) discussed. HW5 collected and discussed. Detailed discussion of the difference between constraint network and interaction graph (also called domain graph). The domain graph is a weaker representation that does not distinguish, for example, between the set of relations {r1(A,B), r2(B,C), r3(A,C)} and the the single relation r123{A,B,C). In general, r123{A,B,C} cannot be represented by the relations in set {r1(A,B), r2(B,C), r3(A,C)}. Presentation by Md Modassir and Sharmin Rahman on Abstraction Transformations, Valtorta's Theorem, and Hierarchical A*.
March 31 (Tue), 2015 HW4 and HW5 returned (at the end of class; most students did not collect HW4). Presentation by Shawn Dohery and Mingxian Zhu on the method of solution criticism for improvement of heuristics derived from relaxed models. Further discussion of NSDP, especially touching on complexity issues: the secondary optimization problem, min-degree and min-deficiency (a.k.a. min-fill).
April 2 (Thu), 2015 HW6 assigned: Exercise 4.4, due on 2015-04-09, with the following changes: (1) solve the crossword puzzle of Exercise 4.1 (3x3 puzzle), instead of the puzzle of Exercise 4.3; (2) start from the initial configuration, not from the arc-consistent network. Presentation by Li Wang and Haoroi Wu on Pattern Databases. Local search (Section 4.8 [H]) through Section 4.8.1 [H], with detailed presentation of Example 4.8.1 [H].
April 7 (Tue), 2015 Propositions and Inference (Ch.5 [P]) through Example 5.5 [P].
April 9 (Thu), 2015 HW6 collected; several algorithm and parameter choices tried in class with the AISpace Stochastic Local Search applet. The students are asked to install the SWI-Prolog compiler. A link to the SWI code for download is given under "Prolog Information" in the CSCE 330 fall 2014 web site: http://www.cse.sc.edu/~mgv/csce330f14/prolog/index.html. (A link to SWI Prolog is also given on the AILog page http://www.cs.ubc.ca/~poole/aibook/code/ailog/ailog_man_1.html. Propositions and Inference (Ch.5 [P]) through most of section 5.2. (Example of use of the top-down definite clause proof procedure still needs to be done.)
April 14 (Tue), 2015 HW7 assigned: Exercises 5.3 and 5.4 [P] due on Thursday, April 16. HW8 assigned: Exercise 5.6 [P] sue on Tuesday, April 21. HW9 assigned: Exercises 5.7, 5.8, and 5.9 [P], due on Thursday, April 23. Fifth student presentation: Karl Schobert and Kang Zheng on Genetic Algorithms. Section 5.2 [P] completed. Section 5.3 [P] ("Knowledge Representation Issues").
April 16 (Thu), 2015 HW7 collected. HW6 returned (to students who had not collected it at the end of last class). Section 5.3 [P] completed. Section 5.4 [P] ("Proving by Contradictions") with an example of consistency-based diagnosis.
April 21 (Tue), 2015 HW7 returned and discussed. HW8 collected. Section 5.5 [P] ("Complete Knowledge Assumption") completed. (Note that the CKA is more commonly called the Closed World Assumption, CWA.) Example 5.26 using ailog2 and file elect_naf.aif. Bottom-up negation as failure proof procedure (figure 5.11) with example 5.28; important observation: either-or in the pseudocode is ordered: first use "either" part. Section 5.8 [P] ("Abduction").
April 23 (Thu), 2015 Late and incorrect homework may be turned in for partial credit until just before the exam for partial (extra) credit. If you are resubmitting homework, please attach your improved work to the original graded paper(s). Exception: if you resubmit HW9 and have not collected the original graded paper, you may resubmit without the original graded submission. HW8 returned and discussed. HW9 collected and discussed. Presentation on David Poole's "Normality and Faults in Logic-Based Diagnosis" (IJCAI-91) by Kelly Benson and Mouiad Al-Wahah. Discussion of format of the final exam, which will be closed book and notes and cover almost exclusively chapters 3, 4, and 5 of the textbook. Student Evaluation. End of Course.