-------------

605.452: Artificial Intelligence Programming, Spring 1998

-------------
Lecturer:
Paul McNamee

Textbooks:

Objectives:
This course focuses on implementing AI techniques using Common Lisp. As such, it has two main themes: the algorithms need to implement AI techniques efficiently, and the Lisp techniques needed to put the algorithms into practice. The course consists primarily of programming projects. There will be no exams. AI Programming techniques may include a deeper look at heuristic search and efficiency issues in search programs, natural language parsing, object-oriented representations, rule-based expert systems, and neural networks, etc... Lisp topics include programming methods as well as Lisp functions and data structures. Programming methods may include symbolic programming, lexical closures, memoization, and a review of recursive techniques. Lisp functions and data structures to be covered include the Common Lisp Object System (CLOS), hash tables, functions as first-class objects, macros, structures and lists. Prerequisite: 605.451 Principles of Artificial Intelligence.
Schedule of Topics:
January20 Lisp Review
January27
February3 Higher Order Functions, Loop, Format
February10 Data Structures and Heuristic Search
February17 Structures, Macros, A*/IDA*
February24 A*/IDA*
March3 Common Lisp Object System (CLOS)
March10 Object-Oriented Programming with CLOS
March17 Spring Break: No Class
March24 Closures, Optimization Issues
March31 Unsupervised Neural Networks, Destructive Operations
April7 Automated Memoization, Supervised Neural Networks
April14 Reasoning Under Uncertainty
April21 Garbage Collection, Project Help
April28 Game Playing: Tournament
Coursework:
Grades will be based on 6 - 7 homework assignments and short programming projects. There will be several Lisp programming assignments covering Lisp material from class and several multi-week programming projects involving the various topics in AI that we cover, such as writing a natural language front-end, writing an object-oriented simulation or creating a computer player for a medium complexity strategy game. Previous courses have held a game-playing tournament, where one lab session is devoted to hosting a tournament where each student's computer program competes in a game like connect-four, mancala, or othello. The final programming project will be will be an independant project in an area of your choice. In general, late work will not be accepted unless I am contacted before the material is due. You are primarily responsible the material covered during lectures but should also read the chapters in the text and any assigned handouts.
Ethics:
Work for this class is expected to be the result of individual effort. It is perfectly acceptable to make use of published examples and code in the literature with attribution. Furthermore, while it is permissible to discuss the general nature of lecture material and assignments with your peers, this does not extend to revealing solutions or source code. Students are expected to uphold the academic integrity of the university. Individuals found using without reference, published material or copying another's work will result in an `F' for the assignment and the matter will be referred to the dean. If you have any questions about this policy or any other questions about an assignment, contact me for a clarification.

Assignments:

  1. Homework Policy homework-policy.ps
  2. Homework 1: Common Lisp Review hw1.ps
  3. Homework 2: Sequence Functions and Data Structures hw2.ps
  4. Homework 3: Implementing Heuristic Search Algorithms hw3.ps
  5. Game Playing Project:Mancala game-project.ps
    (For a description of the rules for the game playing tournament, see mancala-rules.html)
    (Precycling node lisp code is available, see precycling.lisp)
  6. Homework 4: CLOS: A Featureful Object System in Common Lisp
    7. hw4.ps
  7. Homework 5: Machine Learning: Error Backpropagation
    8. hw5.ps
  8. Homework 6: Rule-Based Expert Systems
    9. hw6.ps
    (The souce for Paul Graham's inference code is at rule-system.lisp)
Lisp Resources:
AI Sites:

AI Handouts:

Lisp Handouts:
  1. Lisp Overview lisp-overview.ps
  2. Higher Order Functions higher-order.ps
  3. Conditional Expressions conditionals.ps
  4. Let, Let*, and Prog forms let-progn.ps
  5. Equality Predicates equality.ps
  6. Input and Output io.ps
  7. Structures structures.ps
  8. Iteration (Loop) loop.ps
Lisp Code Examples:
  1. Structures and Search structure-search-example.lisp
  2. A* Search example of Word Ladders word-ladders.lisp
  3. Deftable: Peter Norvig's example of data abstraction using macros. From ACM Lisp Pointers article. deftable.lisp
  4. Gates.lisp: Example by Marty Hall using digital logic gates to illustrate basic CLOS principles.
  5. method-combination.lisp A Simple example of using :method-combination in defgeneric to specify a different behavior than simply calling the most specific applicable method.
  6. blocks.lisp Blocks-World example using CLOS with methods for manipulating blocks.
  7. Source code for Function Call Counting using first class functions, Simple-Metering.lisp
  8. Simple error backpropagation with momentum, backprop.lisp. Sample run.

JHU on-line resources

Paul McNamee