CSCI 450
Artificial Intelligence

Coordinator: Stephanie Elzer

Credits: 4.0

Description

Introduction to artificial intelligence including problem solving, search, heuristic methods, machine learning, knowledge representation, natural language processing, computer vision, expert systems, theorem proving and current applications. Concepts illustrated through programs developed in LISP or Prolog. Offered periodically.

Prerequisites

C- or higher in CSCI 340 and CSCI 362.

Sample Textbooks

The Elements of Artificial Intelligence Using Common Lisp, Steven L. Tanimoto, Computer Science Press.

Course Outcomes

1. Familiar with classical AI problems and solution methodologies of AI
2. Proficient in programming in Lisp
3. Familiar with current research topics in AI
4. Aware of both the possibilities and the problems incumbent in AI research

Major Topics Covered

A. Introduction.

1. AI Terminology and definitions.
2. Brief History.
3. Research topics in AI.

B. Lisp and Prolog.

1. Basic functions.
2. Using the system and interpreter.
3. The structure of the languages.
4. List Processing.
5. Recursion.
6. When to use which language, advantages and
     shortcomings of each.

C. Searching and Problem Representation.

1. Hill climbing.
2. AND/OR trees.
3. Alpha/beta technique.
4. Means-ends analysis.
5. The A* algorithm.
6. Depth-first.
7. Breadth-first.
8. Best-first.
9. Heuristic search and evaluation functions.

D. Representing Knowledge.

1. Semantic nets.
2. Scripts.
3. Frames.
4. Logic and resolution.
5. Propositional calculus and predicate logic.
6. Predicate calculus

E. Expert systems.

1. Introduction and example systems - Mycin,
     Xcon/R1.
2. Prolog, logic programming, and expert systems.
3. Tools, Expert Systems Shells, and Programming.

F. Computer Vision.

1. Introduction - simple techniques.
2. Edges, Line and Point Processing.
3. Blocks World Heuristics.

G. Natural Language Processing.

1. Chomsky's grammars.
2. Syntax, semantics, pragmatics.
3. ATN's.
4. Machine translation.

H. Machine Learning.

1. Learning from examples.
2. When to apply productions.
3. Parallel processing.

I. Other Areas.

1. Robotics and Artificial Intelligence.
2. Speech Understanding.
3. Blackboard systems.
4. Neural Networks.

J. Future of artificial intelligence.
1. Current research areas.
2. Fifth generation computing.
3. Application areas.
4. Moral and social issues.

Sample Laboratory Projects

1. Lab 1: (2 weeks)
   1. Write a Lisp function that takes two integers and returns their greatest common divisor. (Hint: the built-in function integerp tests whether or not a number is an integer.) Call your function mygcd.

   2. Write a Lisp function that takes a list and an element e, and returns the list with all occurrences of e deleted. Call your function delete_elem For example:
   (delete_elem �(1 2 3 1 3 1) 1)
   returns (2 3 3).
   
   3. Write a Lisp function flatten that takes a list of lists and returns a simple list. For example,
   (flatten �(1 (2 3 (3 4)) 5))
   returns (1 2 3 3 4 5).
   
   4. Write a Lisp function del_if that takes a list and a function pred as arguments. Function pred should take one argument and return Boolean (t or nil). The result of a call to del_if should be the argument list with all elements that make pred true removed. For example:
   (del_if �(1 4 3 0 6 2) #�(lambda (x) (< x 3)))
   returns (4 3 6).
   
   5. Write a function that takes an integer n and returns a one-argument function. The function returned should compute its argument to the nth power. Call your function myexp. For example, (funcall (myexp 3) 2) should return 8. Note that this is an example of function currying � here�s a brief explanation of currying (more links are on the course website, for those who are interested!). With currying, all functions �really� take exactly one argument. So, in the above example, myexp is a function returning a function, so the way we supply two arguments is:
   � invoke the function (myexp), get a function back
   � then invoke the returned function passing the second argument.
   � Our final value is returned.
   � (funcall (myexp 3) 2) is an inlined version of this where the function returned by myexp 3 is not put in any variable
    

2. Lab 2: (1 week)
   In this lab, you will write several Lisp functions that will serve as the foundation for your next several assignments. We will be working with a classic AI search problem called the �8-puzzle.� We will be using the 8-puzzle program to examine and compare different search algorithms and heuristics. However, to get started, we need some to write some Lisp code. Note that at the end of this lab assignment, you won�t actually have a working 8-puzzle program yet, but you will have many of the functions that you will need to complete the 8 puzzle program.
    

3. Lab 3: (5 week)
   This lab is designed to introduce you to the concept of �state space search.� In this lab, you will implement several search algorithms in Lisp, utilizing the �helper� functions that you implemented in the previous lab. Note that there is a solution set for the first lab available on the course website, which you should use if some of your functions from the last lab aren�t working correctly. Note that at the end of this lab assignment, you will actually have a working 8-puzzle program.
    

4. Lab 4: (2 weeks)
   This lab assignment is designed to give you some experience with learning via decision trees. We�re going to be using the algorithms and code provided in our book, with some modifications that I�ve made. The source file for building a decision tree is in dectree.lisp and is provided on the course website. I am also providing a file called readdata.lisp with code that reads in data files and constructs some of the necessary data structures for building a decision tree. The data files are available on the website, and in a directory on cs -- ~elzer/450/decision/data.
    

5. Lab 5: (2 weeks)
   In this homework assignment, we will be working on planning problems. We will be using a planning program called SHOP (Simple Hierarchical Ordered Planner) that has been developed at University of Maryland. You can download your own version of SHOP (it�s Lisp code, of course!) at http://www.cs.umd.edu/projects/shop. There is also a version in my directories at ~elzer/450/Shop. The pdf version of the documentation is also available on the course website. Additional papers and references can be found on the Shop website.
   
   This initial assignment is just part of the planning problems that we will be doing. The initial problems are aimed at getting you familiar with Shop, and with planning problems in general.
   
   Using the blocks domain (in the ~elzer/450/Shop/shop2-110/examples/blocks directory), set up the following problem. Block2.lisp is the domain file. The other files provide example problem sets. You will see in the test.lisp file, I set up the simple problem on p.314 (figure 7.8) of our book. I was getting stack overflows with some of their examples � I will continue to look at this problem. Your initial state looks like this:
   
   F E C
   A B D
   
   You want the end state to look like this:
   
   D A
   E B
   F C
   
   Use SHOP and the blocks-world domain to solve the problem. Set up the problem as a problem set, even though there�s only one problem in the set. Be sure that the parameters are set to display the plan that was developed.
    

6. Lab 6: (2 weeks)
   In part 2 of our planning homework, we will continue to work on planning problems. This time around, you will need to develop your own SHOP planning domain and solve several problems in that domain.
   The domain
   (This is taken from Russell & Norvig, p. 414) The original STRIPS program was designed to control Shakey the robot. The attached figure shows a version of Shakey�s world consisting of four rooms lined up along a corridor, where each room has a door and a light switch.
   
   The actions in Shakey�s world include moving from place to place, pushing movable objects (such as boxes), climbing onto and down from rigid objects (such as boxes), and turning light switches on and off. The robot itself was never dexterous enough to climb on a box or toggle a switch, but the STRIPS planner was capable of finding and printing out plans that were beyond the robot�s abilities. Shakey�s six actions are the following:
   � Go(x, y), which requires that Shakey be at x and that x and y are locations in the same room. By convention a door between rooms is in both of them.
   � Push a box b from location x to location y within the same room.
   � Climb onto a box (will need a predicate On and a constant Floor here)
   � Climb down from a box
   � Turn a light switch on *
   � Turn a light switch off * To turn a light on or off, Shakey must be on top of a box at the light switch�s location
   
   Your mission
   1. (50 pts) Define a SHOP planning domain for Shakey�s world.
   2. Define a problem set that includes the following:
   o (10 pts) Using the initial state shown in the diagram, construct a problem where the goal is for Shakey to get Box2 into Room2
   o (15 pts) Using the initial state shown in the diagram, construct a problem where the goal is for the light in room3 to be on, and all of the boxes to be in room1.
   Be sure that your parameters are set so that the plans are displayed when the problem set is run. Note that the grading of the domain will depend on the correctness of the plans generated by the problems � so everything is rather interdependent! I tried to give you the point values as approximate weights.

7. Lab 7: (2 weeks)
   In this assignment, you will be using Netica, a Bayesian network software package, to become more familiar with probabilistic modeling using Bayesian Networks. Netica has been installed on the lab machines. You can download your own free (limited size network) version from http://www.norsys.com/netica.html. You should develop a separate network for each of the questions below, and submit the .dne files created by Netica. You will also need to turn in the requested probability calculations separately (as a .txt file as lab probabilities). Note � in the last two problems the values will be different from other students� depending on the network that you�ve designed� that doesn�t make them wrong.

Return to course directory.