CS 44

Artificial Intelligence

Computer Science Department
Dartmouth College
Winter, 1998

Announcements

• Course Materials.

  • The course homepage is http://www.cs.dartmouth.edu/~brd/Teaching/AI/
  • Course Information.
  • Course Software
  • Course staff
  • Recitations
  • TA Consulting Hours
  • Problem Sets
  • Exams
  • Lectures
    • AI Fundamentals
    • Dylan and AI Programming
      • X-Hour Lectures
  • Handouts

Course Staff

• Professor Bruce Randall Donald
• Sanjay Khanna, Graduate TA
  • 223 Sudikoff; tel: 6-1639 (W); 603-448-6306 (H)
• Susanna Leng, Undergrad TA
• Mintcho Petkov, Undergrad TA
• Alik S. Widge, Undergrad TA

Recitation Sections

Because of room availability, Section hours may change. Check here for changes and updates.


Tuesday	Susanna Leng	Rm 005	4:30pm - 6:00pm.
Wednesday	Mintcho Petkov	Rm 005	4:30pm - 6:00pm.
Thursday	Sanjay Khanna	Rm 115	1:00pm - 1:50 PM (X-hour).

If Professor Donald uses the X-hour for a lecture, then Sanjay's recitation will move to 4:30PM in room 005.

We urge you to go to recitation sections to learn the supplementary material that will be presented there, to ask questions, and to get assistance with the homework!

---

TA Consulting Hours

Come to see a TA, discuss questions, and get help with homework assignments in a one-on-one format.
• Sunday 5-7 PM, 005 Sudikoff, Alik S. Widge.
• Tuesday 9-11 PM, 005 Sudikoff, Alik S. Widge,
• Thursday 8-10 PM, 005 Sudikoff, Alik S. Widge,

---

Problem Sets.

Unless otherwise stated, problem sets should be turned in (on paper), in class.
• Easy. Due: Friday, January 9.
• Language assignment: PS 1: Introduction to Dylan. Due: Friday, January 16.
  • Code for PS1.
  • Solutions.
• PS2: Search and Genetic Algorithms. Due: Friday, January 23.
  • Solutions..
• PS3: RSA and A* Search. Due: Monday, Feb 2.
  • The deadline for PS3 has been extended from Friday 1/30 to Monday 2/2.
  • Please read this clarification to the assignment!
  • Code for PS3.
    • Here is a tail-recursive version of the Code for PS3.
  • Solutions to PS3.
    • Gold Stars
      • Ryan and Lauren.
      • Ron.
      • Virantha.
• 1-page essay on Brooks' subsumption architecture. Due Weds Feb 11.
• PS4: Graphs, Automata, Search, and Robot Motion Planning. Due: Friday, February 13.
  • Code for PS4.
  • Code library for the Visibility Graph project.
    • Basic Code library V1.0 for the Visibility Graph project, handed out with the assignment.

       (load cs44-lib)

    • Improved Code library V1.1 for the Visibility Graph project, with better comments and some redundancy removed.

       (load cs44-lib-v1-1)

    • Code library V2.0 for the Visibility Graph project, rewritten to use classes. This is probably the library of choice to use for future code development.

       (load cs44-lib-v2-0)

  • Solutions to PS4.
    • Gold Stars
      • Amar & Marty.
      • Will & Tim.
      • Ryan & Lauren.
• PS5: AI Programming Project. Due: Monday, March 9.
  • Solutions to PS5.
    • Written assignment. [gzipped PostScript]
    • Gold Stars
      • Computer Poetry
        • Haiku: Tim and Will.
          Sample Haiku
        • Shakespearean Sonnets: Benjamin.
          Sample Sonnet
      • Implementing a Non-Linear Planner
        • An Implementation of TWEAK: Ryan.
      • Synthesizing Robot Motion Plans
        • Ned and Virantha.
        • Ron and Veyssel.
        • Amar and Marty.
  • Comments and highpoints

Exams

• Midterm: Weds Feb 18, 7-9 PM 115 Sudikoff
  • The Midterm will cover up through 2/11, that is, up through the lecture on subsumptionism and the discussion afterwards over pizza.
  • The Dylan Cheat Sheet will be available in the exam.
  • Review Session: Rm 115 Sudikoff, 5:30pm on Monday 2/16.
    • Last year's Midterm (practice exam). [gzipped PostScript]
    • Practice questions on Dylan and AI Programming. [gzipped PostScript]
  • Solutions to midterm. [gzipped PostScript]
• Final Exam: Fri March 13, 1:30-3:30 PM, 102 Bradley.
  • The Dylan Cheat Sheet will be available in the exam.
  • Review Sesssion: Th Mar 12 1:00-2:30 PM in 115 Sudikoff.
  • Last year's Final. [gzipped PostScript]
  • Study Guides:
    • Search.
    • Planning.
    • Learning.
    • Robotics.
    • Vision.

• Fundamentals of AI: Theory and Algorithms.

  • 

    Lectures and Reading.

    "R&N" = Russell and Norvig.
    "CLR" = Cormen, Leiserson, & Rivest.
    
    • 1/5. Introduction: History, Agents, Environments. Read Russell and Norvig ("R&N") Ch. 1, skip 1.2.
    • 1/7. Search: Search spaces, uninformed search. Read R&N Ch. 3, skip 3.7.
    • 1/12. Informed Search. A* search and Best-First Search Read R&N Ch. 4, skip 4-3, 4.4
    • 1/14. Informed Search (continued). Hill-climbing search and Simulated Annealing Read R&N Ch. 4.4.
      Read Cormen, Leiserson, & Rivest ("CLR") on Traveling Salesman Problem, pp. 959-960, 969-974.
    • 1/19. Martin Luther King Day. No Class.
    • 1/21. Game Playing. Alpha-Beta Search. Read R&N 5.1-5.4
    • 1/23. Game Playing (Continued). Consipracy Numbers. Read R&N 5.5-5.7.
    • 1/26. Intro to Robotics. Read R&N 25.1-25.5.
    • 1/28. Planning for Robots. Read R&N 25.5-25.6;
      Read CLR on Convex Hull, pp. 898-908.
      • Real-Time Robot Motion Planning Using Rasterizing Computer Graphics Hardware, (J. Lengyel, M. Reichert, B. Donald, and D. Greenberg), Proc. SIGGRAPH '90, Dallas, TX (Aug 1990), pp. 327-336.
        • [gzipped PostScript]
    • 1/30. Planning under uncertainty. Read R&N 25.1-25.5.
    • 2/2
      Machine vision (introduction). [gzipped PostScript] Read: handouts, R&N Ch. 24.
      • Lecture notes on low-level vision. [gzipped PostScript]
    • 2/4
      Machine vision (continued). Read: Handout on low-level vision.
      • Handouts today: 2 papers by Rodney Brooks,
        1. "A Robust, Layered Control System for Mobile Robots", and
        2. "Intelligence without Reason."
    • 2/6
      Machine Vision (continued). Object recognition using the Hausdorff Distance. Reading (handout): article by Dan Huttenlocher in Symbolic and Numerical Computation for Artificial Intelligence, Academic Press, Harcourt Jovanovich, (London: 1992) (Ed. Donald at al.).
  • 2/9 No Class.
  • 2/11.
    Discussion of subsumptionism and On-Line Algorithms.
    Read: R&N Ch. 25.6, Brooks papers.
    

    • Assignment:

      Before this class, read the two papers by Rodney Brooks on subsumptionism. Write one page comparing and contrasting subsumptionism with the robot planning approaches we have discussed so far in class. Be prepared to discuss your ideas. In this class, we will discuss the papers over pizza. Be prepared to participate and bring your ideas! Hint: Read R&N, Ch. 25.6 on "On-Line Algorithms for Motion Planning." How do these algorithms compare with Subsumptionism?
  • 2/13. Winter carnival! No Class!
  • 2/16.
    Introduction to Knowledge representation and Modal Logic.
    • Read the paper (handout) by David Chapman, "Planning for Conjunctive Goals", Artificial Intelligence 32 (1987) pp. 333-377.
      • Lecture notes on Chapman's paper. [gzipped PostScript]
      • Read R&N Ch. 6.
    • 2/18
      Introduction to Non-linear Planning.
      • Finish reading Chapman paper.
      • Read R&N Ch. 7.
      • Here is code for a non-linear planner called UCPOP. It is written in CommonLisp which is a Lisp-like language similar to Dylan. A C++ version is also available.
        • Lecture notes on planning and UCPOP.
    • 2/20
      Non-linear Planning (TWEAK), continued.
      • Study notes on planning.
    • 2/23
      Wrap up: Complexity and completeness of Planning.
      Begin lectures on Learning, Neural Networks.
      • Paper handout: Matlab Neural Network Toolbox.
      Read R&N ch. 18.
      Read the handouts on Neural networks.
      • Lecture notes on Neural Networks:
        • Part 1 (Intro). Part 2.
    • 2/25
      Artificial Neural Networks. Perceptrons. Learning. Read R&N ch. 19.
      • Lecture notes on Neural Networks:
        • Part 3. Part 4.
    • 2/27
      Neural Networks (continued). Backpropagation. Read handout of 2/23, R&N ch. 20.
      • Lecture notes on Neural Networks:
        • Part 5. Part 6.
    • 3/2
      Learning and Neural Networks (continued).
      • Lecture notes on Neural Networks:
        • Part 6. Part 7. Part 10 (Summary).
      • Additional Reading (Optional) on Neural Networks:
        • Part 8. Part 9.
    • 3/5 No Class.
    • 3/7 No Class.
    • 3/9
      Last day of class. Research in AI and Robotics:
      (lecture on MEMS).

• AI Programming.

  Be sure to read the handouts, many of which cover or elaborate the material in the AI Programming lectures.

  During the X-hours, we will meet to learn how to program in a functional, scheme-like language (Dylan).

  • 

    X-hour Lectures and Reading

    • 1/8
      The Study of Computation, and an Introduction to Dylan
      • heron.dyl
      • Section Notes. (About Dylan, the meaning of ()'s, substitution model, special forms, code generalization)
      
      Function Abstraction and the Substitution Model of Evaluation
      • Section Notes. (More generalizations, binding forms, tail recursion, induction (Towers of Hanoi, strong induction))
    • 1/9
      Procedures and Processes: Iteration, Recursion and Induction
      Higher Order Procedures: Functional Arguments and Values
      • Section Notes. (Program cohesion, higher-order functions, deriv, repeated in three incarnations, a hard RSM example)
      • Section Notes. (Four versions of nth-deriv)
    • 1/15
      Data Abstraction and Compound Data Types.
      Lists! Map!
      • Section Notes. A review of how to do complexity analysis in a functional language. Some of you may know this already.
    • 1/16
      Symbolic Differentiation and Classes.
      • symdd.dyl
      • Section Notes. (Append, List functions, reverse)
    • 1/22
      Generic Operations.
      • complex.dyl
      • Section Notes.
    • 1/29
      Generic Operations, coercion, and symbolic manipulation (polynomials).
      • generic.dyl
      • Section Notes: OOP examples and generic functions
    • 2/5
      Reasoning About Lists: Program verification, formal methods for proving programs are correct.
    • 2/12
      Side Effects. Assignment and the Environment Model of Evaluation
      • Warning: The students on this list may use set! and side effects (eg 'setter' functions) in their Dylan code. All other students should not use set! or any side effects (eg 'setter' functions) in their Dylan code. Code with side-effects will get no credit.

      • Side-effects are not necessary for our assignments. However, you may wish to experiment with them on your own. After proper instruction and training, side-effects can be used in a safe, efficient, and elegant manner. The following lectures show how.
    • 2/19
      Local State. Assignment and Local State Variables
    • 2/26
      Object Oriented Programming. Objects with State and Object Oriented Programming.
      • bismark.dyl
    • 3/5
      More Object Oriented Programming. Object Oriented Programming and Inheritance

    • More on Dylan, Functional Programming, and AI Programming

      • Some of the notes below use side-effects. Warning: Students should not use set! or any side effects (eg 'setter' functions) in their Dylan code. Code with side-effects will get no credit.

      1. Still More Object Oriented Programming. Multimethods and More About Object Oriented Programming
      2. Stacks, Queues, Mutable Data.
      3. Priority queues.
         • prioq.dyl
      4. Evalling Expressions.
      5. Compiler.
      6. Garbage Collection.
      7. Streams.
      8. Infinite Streams.
      9. Patterns And Rules.
         • pattern.dyl
      10. Quicksort.
      11. Computability (the Halting Problem).

    ---

  • Handouts.

    • Notes on Dylan
      • For the curious (Optional reading):
        Comparison of Dylan with C++
    • Dylan Cheat Sheet
    • Tips, Frequently Asked Questions
      • Alik Widge's Dylan Tips
    • The Substitution Model
    • Using Induction to Prove Recursive Programs are Correct
    • Data Abstraction in Dylan
    • Lists in Dylan
    • Reasoning about resources: Asymptotic analysis in Dylan.
    • Neural Networks
      • Handout 0 (Introduction) to Neural networks.
      • Handout 1 on Neural networks.
      • Handout 2 on Neural networks.

    ---

    

    Dylan Interpreter

    • Warning: NOODLLE's operation in Internet Explorer (IE) is unsupported and unreliable. It is highly recommended that you use Netscape.
    • Dylan Interpreter (NOODLLE).
      • Dylan Interpreter (V 1.03).
        • Beta-test versions
          • Dylan Interpreter V 1.04
            
            • Includes inverse trig functions, tangent, and pi, plus set-color.
              • Here is a complete list of changes and differences.
          • Dylan Interpreter V 1.05
            
            • This version of Noodlle fixes the bug wherein methods manipulating new classes derived from <object> will not work properly when (add-method)ed to (=). Includes V 1.04 fixes.
    • Course Software