cool stuff for teaching AI

About this web page

This web page contains several project assignments in Artificial Intelligence for use by anyone teaching a course in AI at the college level. Each project has been used in teaching AI at the University of Southern California and has been vetted a little. The author for each project is T. Nathan Mundhenk, Laurent Itti and Michael Arbib

For each project, we have attempted to include all the material one would need to use the project in a course. Additionally, we have included a difficulty level for each project based upon how students performed on each project. In general, these projects should be reasonable for senior level undergraduate and introductory graduate level courses. It is of course up to the instructor to decide if the project is appropriate for their class.

Most projects require programming in C++ or C. In general, we advise using GNU C++ for the projects since this is what the students used. Using other programming languages may be fine, but we cannot comment on how compatible it will be with each project. 

Most projects contains three parts. The first part is a question and answer section to help prime the students on the project they will perform. The second part is the actual programming part itself. Then there is a second question part to make sure the students understand the concepts they should have learned in the programming parts. Since each project is editable, it is at the instructors discretion what to add, delete or otherwise change. Please note the GNU notice on usage of each document if you wish to change and distribute the project. In general distribution and usage is free so long as credit is given to the original authors. 

1. Uninformed Search

Depth First and Breadth First Search Acrobat Version
Word Version
Supporting Material

Difficulty: Easy
Original Course Used In: CS460, CS561
Instructor: Laurent Itti

This is a basic project in which students will create a depth first and breadth first search algorithm. The basic idea is to help Homer Simpson get from different places in Springfield to other places in Springfield. This project is not to difficult to complete. However, students seem to get confused on the matter of complexity in computing DFS vs. BFS. 

Uninformed Search Cover Art

2. Gradient Decent and Simulated Annealing

Simulated Annealing to solve an NP-Complete problem Acrobat Version
Word Version
Supporting Material

Difficulty: Intermediate
Original Course Used In: CS460, CS561
Instructor: Laurent Itti

Students are asked to solve an NP-complete problem similar to the N-Queens problem using simulated annealing and must answer questions about gradient decent algorithms. This assignment is good for introducing students to the notion that a program may never completely converge to the correct solution. As such, students must learn when to stop the program. 

The basic story with the homework is that students must figure out how to arrange baby lizards in a nursery in a way that prevents the lizards from eating each other. 

Simulated Annealing Cover Art

3. Logic Reasoning

First Order Logic Backward Chaining Acrobat Version
Word Version
Supporting Material

Difficulty: Easy
Original Course Used In: CS460, CS561
Instructor: Laurent Itti

Students use backwards chaining to attempt to answer simple queries posed in first order logic. In this homework, everything is kept in horn clauses which is why this homework is easy. Students sometimes get tripped up on the if/then concept that if A then B and not A, you can still have B. As such this is a good trick to place in this homework. 

Logic Chaining Cover Art

Lecture Notes on Logic and Chaining Acrobat or Power Point
Lecture Notes on Logic and Inference Acrobat or Power Point

4. Fuzzy Logic and Robotics

Use Fuzzy Logic to control a robot fly Acrobat Version
Word Version
Supporting Material

Difficulty: Hard
Original Course Used In: CS460, CS561
Instructor: Laurent Itti

This is a difficult homework due to the fact that students must understand basic kinematics in mobile robotics as well as fuzzy logic. The students will create a fuzzy logic controller to move a robotic fly through simple courses comprised of goal posts. One drawback to this homework is that students can "solve" the problem using other methods since the homework does not require dynamics. As such, some students try to get away with simply drawing lines. Other students will design non-fuzzy PD controllers, which is also not correct. In order to be sure students implement a fuzzy controller, we check each students code visually to make sure they did what was required. 

Logic Chaining Cover Art

Lecture Notes on Fuzzy Logic Acrobat or Power Point
Lecture Notes on Fuzzy Logic and Robotic Control Acrobat or Power Point

5. Bayesian Reasoning

Creating a basic Bayesian Classifier Acrobat Version
Word Version
Supporting Material

Difficulty: Intermediate
Original Course Used In: CS561
Instructor: Laurent Itti

Students will create a simple Bayesian classifier by taking in sample training sets and learning the best probabilistic decision boundary. In general this homework is not hard, but some students run into conceptual difficulties with probabilities. It is interesting to demonstrate that a large enough prior for a given class can allow it to squash other classes which might seem like a more reasonable decision at first glance. 

Bayesian Decision Cover Art

Lecture Notes Bayesian Classification from Sampling Acrobat or Power Point
Lecture Notes on Bayesian Inference Acrobat or Power Point
Lecture Notes on Bayesian Inference and Election Prediction Acrobat or Power Point

6. Neural Networks and Action/Perception

Basic back-propagation neural network classifier Acrobat Version
Word Version
Supporting Material 1
Supporting Material 2

Difficulty: Intermediate
Original Course Used In: CS564
Instructor: Michael Arbib

Using the training data and NSL, students train a simulated robot to react properly to a visitor based on its features. Students must learn both two and three layer designs for feed-forward neural networks trained using basic back-propagation. 

With this homework, students must train a robot to learn the difference between werewolves, vampires, adults and children in order to protect valuables in ones mansion. The input features drive actions by the robots. For instance, vampire features should produce an impaling action by the robot. 

Neural Networks Cover Art

Lecture Notes on Neural Networks Acrobat or Power Point
Wikiversity Page on Neural Networks Here

7. Adversarial Search and Minimax

Minimax and Alpha-Beta search in game playing Acrobat Version
Word Version
Supporting Material

Difficulty: Intermediate
Original Course Used In: CS460
Instructor: Laurent Itti

Students use Minimax and Alpha-Beta pruning in a simulated combat game. The assignment also includes creating an elementary GUI using Curses. Students create two dueling AI's which stomp on little cities. AI one uses Minimax and AI two uses Alpha-Beta pruning.

Some city boards favor a deeper search, so alpha-beta has an advantage. Thus, the Alpha-Beta AI will be able to search deeper and take the example city, Punxsutawney every time. Students can see that in some cases however this does not hold true. Some city boards are strictly order dependant (The first player always wins). In addition to learning to program game playing AI's, students must also learn about optimization in order to allow the AI's to search enough of the space to be competitive.

Adversarial Search Cover Art

Supporting Material

1. Auto grading with "stubby"

Most of these projects have been designed for large courses with many students. To speed up grading, we use a grading Perl script called stubby. The students are given a basic copy of the grading script in order to make sure that the project they turn in is compatible with the script the graders use. 

To make sure the students comply, approximately 5% of the project grade is based on the grading script working properly on the code the student hands in. Additionally, its all or nothing for the points for working with the script since any deviation slows down grading. In general, after the first project, student learn compliance and this becomes an easy 5 points. Additionally, grading becomes easy and far less time consuming. This is somewhat anal, but it seems to really work. In smaller classes one should just skip this to foster creativity.

2. Included grading sheet

Most projects include a grade sheet with a suggestion for grading each project. Ideally, we should take a certain amount of points for each mistake, but weight this by the severity of each mistake made. However, this is of course optional and again just a suggestion.

3. Catching cheaters

We have had success using Moss to catch students cheating on the projects programming components. It should be noted that many students understand how Moss works and will attempt to circumvent it. Thus, cheating will not usually show up as a 100% match. It seems that Moss is good for bringing code to ones attention and from there the instructor should inspect the code to look for patterns.

4. Supporting books and web pages

  1. NSL Homepage - Neural Simulation Language
  2. Rarlab - To open supporting material
  3. Online course material from Laurent Itti
  4. Artificial Intelligence: A Modern Approach
    by Stuart Russell and Peter Norvig
    ISBN 0-13-103805-2, Prentice Hall (2nd edition).
  5. Neural Networks for Pattern Recognition
    by Christopher M. Bishop
    ISBN 0-19-853864-2, Oxford University Press.
  6. Statistics
    by William L. Hayes
    ISBN 0-03-074467-9, Harcourt Brace College Publishers (5th edition).
  7. C++ Black Book
    by Steven Holzner
    ISBN 1-57610-777-9, The Coriolis Group.

Other Cool Links

  1. iLab at the University of Southern California

All material Copyright 2008, T. Nathan Mundhenk, iLab and the University of Southern California