
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.



2. Gradient Decent and Simulated Annealing

Simulated Annealing to solve an NPComplete problem 
Acrobat
Version 

Word
Version 

Supporting Material 

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

Students are asked to solve an NPcomplete
problem similar to the NQueens 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.



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.





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
nonfuzzy 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.





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.





6. Neural Networks and Action/Perception

Basic backpropagation 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 feedforward neural networks trained using basic
backpropagation.
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.





7. Adversarial Search and Minimax

Minimax and AlphaBeta search in game playing 
Acrobat
Version 

Word
Version 

Supporting Material 

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

Students use Minimax and AlphaBeta
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 AlphaBeta pruning.
Some city boards favor a deeper search, so alphabeta has an advantage.
Thus, the AlphaBeta 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.



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

 NSL Homepage  Neural
Simulation Language
 Rarlab  To open supporting
material
 Online course material from
Laurent Itti
 Artificial Intelligence: A Modern Approach
by Stuart Russell and Peter Norvig
ISBN 0131038052, Prentice Hall (2nd edition).
 Neural Networks for Pattern Recognition
by Christopher M. Bishop
ISBN 0198538642, Oxford University Press.
 Statistics
by William L. Hayes
ISBN 0030744679, Harcourt Brace College Publishers (5th edition).
 C++ Black Book
by Steven Holzner
ISBN 1576107779, The Coriolis Group.

Other Cool Links

 iLab at the University of Southern
California
 Nerdcam.com
 Cinnic.org

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