August 18 (Fri), 2011 HW1 assigned, due Tuesday, August 30, 2011. Administrative information: textbook, syllabus, grading policy. Definitions of AI.
August 23 (Tue), 2011 HW1 collected, Ch.1 [P], with emphasis on desiderata of representations. Issues from Ch.1 [P]: Succinctness (conciseness) of representations: state-space, features or propositions, objects and relations; Bounded rationality and anytime algorithms; complexity of some representational frameworks.
August 25 (Thu), 2011 Ch.1 concluded. Four application domains: autonomous delivery robot, diagnostic assistant, trading agent, intelligent tutoring systems, listing example inputs (prior knowledge, past experience, goals, ond bservations) and sample activities. (15-minute break to attend the reception for Jewel Rogers's retirement; Ms. Rogers was graduate secretary at the time of her retirement.) Ch.2 [P] started. Example of trading agent. Percept and command traces. Causal transductions. Belief states.
August 30 (Tue), 2011 HW1 collected. Ch.2 [P] ("Agent Architectures and Hierarchical Control") completed. The state-space approach to problem solving. Uninformed (blind) search: DFS, BFS, Dijkstra's algorithms (first part of Ch.3 [P]). Iterative deepening DFS. Heuristic search, started.
September 1 (Thu), 2011 HW1 returned. Presentation of blind search from [AIMA-2]. Dijkstra's algorithm (the uniform-cost method) described with OPEN and CLOSED lists (Nilsson-style). Proof that when a node is placed in the CLOSED list by Dijkstra's algorithm, the algorithm found a least-cost solution to it.
September 6 (Tue), 2011 HW2 assigned: exercises 3.3 and 3.4 [P], due September 15. More properties of Dijkstra's algorithm. A*. Completeteness and admissibility of A*.
September 8 (Thu), 2011 Properties of A* in detail, with proofs from the original Hart-Nilsson-Raphael paper of 1968 (and correction of 1972) for Lemma 1 and Pearl' 1984 _Heuristics_. Monotonicity (consistency) of heuristics. Properties of A* with monotone (consistent) heuristics. Local copies of HNR-68 and HNR-72 placed on web site. Notes placed on website also.
September 13 (Tue), 2011 Computation of heuristics by problem relaxation. Example: towers of Hanoi. Heuristics computed by problem relaxation are consistent (monotone).
September 15 (Thu), 2011 HW2 collected. Valtorta's theorem.
September 20 (Tue), 2011 Features and constraints (Ch.4 [P]) through section 4.2. Board used, text followed closely.
September 22 (Thu), 2011 HW3: Exercises 4.1 and 4.3, due Tuesday, October 4. Midterm is expected to be on Thursday, October 6. Features and constraints (Ch.4 [P]) through most of section 4.5. Board used, text followed closely.
September 27 (Tue), 2011 HW2 returned. First part (exercise 3.3 [P]) corrected in detail, with good Q&A.
September 29 (Tue), 2011 HW3 due date is changed to Thursday, October 6. Midterm will also be on Thursday, October 6. Second part of HW2 (exercise 3.4 [P]) corrected in detail. Proofs of consistency or monotonicity of the second and third heuristic would result in extra credit. Handwritten journal notes for exercises 3.3 and 3.4 are in the blackboard site for this course. Please review them and make sure you understand! Features and constraints: section 4.5 (consistency algorithms) completed.
October 4 (Tue), 2011 Midterm (MT1) will be on Thursday, October 6. Features and constraints: more examples of consistency algorithms (4.5), domain splitting, Boolean satisfiability, and the DPLL algorithm (4.6), relational algebra (A.3), variable elimination (basics; 4.7).
October 6 (Thu), 2011 MT1.
October 11 (Tue), 2011 MT1 returned and corrected. Discussion of HW3. Variable elimination, ctd. Bellman's principle of optimality. Shortest paths in staged networks found with dynamic programming. Non-serial dynamic programming. Bertele' and Brioschi's formulation: definition of minimization problem, example.
October 13 (Thu), 2011 HW3 delayed to Tuesday, October 25. HW4 assigned: exercises 4.2, 4.4, 4.11, due October 27. More on non-serial dynamic programming, including the use of interaction graphs, fill-ins, statement of the theorem that an elimination ordering with no fill-ins exists if and only if a graph is triangulated (chordal) and the secondary optimization problem. Stochastic local search (SLS). Videos describing the SLS applet at aispace.org. (I cannot connect to the internet :-( )
October 18 (Tue), 2011 PR1 assigned: exercises 1, 4, 6: state-space search programs in Java, from handout by Luger and Stubblefield, due on Tuesday, November 8, 2011. Jingsong Wang presents the design and implementation of several search algorithm (depth-first, breadth-first, best-first) in Java.
October 25 (Tue), 2011
HW3 collected.
Modified assignments:
Homework 4: Enter the crosswork problem of 4.3(a) and 4.1(c) [P] in the CSP
applet at AISpace. Solve with the generalized arc consistency algorithm.
Turn in a printout of the netwok after the GAC algorithm stops. (This will not be a unique solution.) This homework is due on Thursday, October 27.
Homework 5: Exercises 4.2, 4.4, and 4.11 [P], due November 1, 2011.
Correction of HW3 emphasizing variable elimination.
October 27 (Thu), 2011 HW4 collected. Chapter 5 (Propositions and Inference) started. Lecture ended early to allow attendance at colloquium: Stan Birchfield (Dept. of ECE, Clemson U.), "Monocular Vision Modules for Mobile Robotics Applications."
November 1 (Tue), 2011 Graduate student presentation requirements. A proposal from the students is requested for Thursday, November 3, 2011. HW4 returned. HW5 collected; discussion of exercises 4.3 and 4.11. Interpretations and models. Definite clauses. Proofs. Soundness and completeness. The bottom-up proof procedure; its soundness; consequence sets; fixpoint; minimal model; completeness of the bottom-up proof procedure.
November 3 (Thu), 2011 PR1 due date changed to 2011-11-08. HW5 returned. Discussion of student presentations---see "Student Presentations" page on course website. The top-down proof procedure for definite clauses; SLD resolution.
November 8 (Tue), 2011 Student presentations assigned. Knowledge representation issues (section 5.3 [P]), with AILog examples.
November 10 (Thu), 2011 PR1 collected---it should be submitted to the dropbox. Section 5.4 [P] (Proving by Contradictions).
November 15(Tue), 2011 Review of consistency-based diagnosis, using Ray Reiter's original (1987) formulation. Section 5.5 [P] (Complete Knowledge Assumption).
November 17 (Thu), 2011 PR2 assigned: exercise 5.13 [P], due Tuesday, November 22. HW6 assigned: exercises 5.7 and 5.8 [P], due Tuesday, November 22. Section 5.6 [P] (Abduction). Section 5.7 [P] (Causal Models). Chapter 5 completed.
November 22 (Tue), 2011 Presentation times assigned. (Presentations will be on November 29 and December 1.) HW 7 assigned: Exercise 6.2 [P], due Thursday, December 1. PR2 and HW6 collected and discussed. Ch.6 [P]: Reasoning under uncertainty, through section 6.3.
November 29 (Tue), 2011 First two presentations (Fahim and Simin on IDA*, SMA*, and IE; Atluri and Velumapalli on inconsistent heuristics and IDA*).
December 1 (Thu), 2011 PR2 and HW6 returned. HW7 collected and discussed. Presentations: Conklin and Lemasters on Davis-Putnam (-Logeman-Loveland), Han and Liu on Bayesian networks for human motion analysis, Parsons and Salvi on Emotion Representation, Guo on MRI image processing. Doe and Lam still need to present.
December 6 (Tue), 2011 Optional review session. HW7 returned. (Semi-)formal definition of Bayesian networks (Neapolitan, 1990). D-separation. HW7 corrected in detail using d-separation. Some Q&A. Final will be closed book. Students are encouraged to study Part II of Poole and Mackworth's book, and especially the examples and exercises. Presentation by Doe and Lam on video games.