CS 343: Artificial Intelligence

Fall 2007: MWF 11:00 - 12:00 in BIO 301 , Unique No. 56590.

Instructor: Gordon S. Novak Jr., TAY 4.140C; Office Hours: MWF 10:00 - 11:00.

TA: Ms. Archana Ganesan archana@cs.utexas.edu Office Hours: Monday 2:30 - 4:00, Thursday 12:30 - 2:00 in Taylor basement.

Text: Stuart Russell and Peter Norvig, Artificial Intelligence: A Modern Approach, 2nd ed..

Course Notes: Strongly recommended; obtain at WEL 2.228. Online by Contents or Index

Web Page: http://www.cs.utexas.edu/users/novak/cs343.html

Class Directory for Software: ftp.cs.utexas.edu /pub/novak/cs343/     or /projects/cs343/


Course Description:

I define intelligence by placing it in the context of biology:
Intelligence connects perception to action to help an organism survive.
Intelligence is computation in the service of life, just as metabolism is chemistry in the service of life. Many points on the spectrum of intelligence vs. cost are viable, from insects to humans.

Artificial intelligence (AI) is the study of the computations required for intelligent behavior and the attempt to implement such computations on computers. Strong AI posits that all aspects of the mind can in principle be described as computations and could be implemented on a computer, although it might not be practical or useful to implement all.

This course provides an introduction to fundamental techniques of AI. Our intent is that the student should not only hear about AI, but do AI: we will use AI techniques to write programs that do interesting things.

Lisp and Symbolic Computation are used to represent knowledge and to reason with that knowledge. No intelligent being can pre-compute the answers to every problem it will face; it must reason based on its stored knowledge and the facts of the moment to decide what to do. Symbolic structures are used to represent knowledge and to reason.

Search is used to find a solution to a problem by trying various sequences of actions to see if some sequence leads to the desired goal. For example, a computer can play chess by trying various sequences of moves (including possible opponent moves) to see whether one sequence will win the game. Trying every possible combination can take too long; heuristics can be used to guide search in the most promising directions. Although creativity has often been listed by critics as something that computers never could have, it turns out that creativity can be achieved by search.

Knowledge representation is the problem of storing accumulated knowledge about the world and using that knowledge to deal with novel situations. Predicate calculus represents both facts and rules as mathematical formulas; the knowledge is used by proving theorems from the formulas. Frames represent knowledge in structured taxonomies, with inheritance of facts (e.g. if we know Fido is a dog, we can inherit the fact that Fido has 4 legs) and attachment of procedures to data.

Natural languages are human languages such as English. Enabling computers to understand natural languages is a major goal, both for its intellectual challenges and for its practical applications. Natural language does not contain the message it conveys, but rather is a minimal code that allows an intelligent reader to construct the message from what the reader already knows. The minimality of natural language requires much knowledge to understand it. Ambiguity is a major problem; both the meanings of words and the intended structure of a sentence are often ambiguous. We will study techniques for parsing sentences and for semantics (meaning).

Expert systems use collections of rules to achieve expert-level performance in narrow domains such as medical diagnosis. These systems also encounter the need to reason probabilistically in order to act based upon insufficient data.

The human brain provides the best example of intelligence. AI and cognitive science have inspired and reinforced each other. We will briefly study how the brain works and some interesting results from neuroscience and cognitive science. Visual perception is complex; we will cover experimental and computational results. Neural networks simulate the operation of neurons, in particular the ability to learn.

The course will conclude by examining advanced AI applications, such as driving a car on the freeway, controlling a spacecraft far from earth, and understanding a machine from a movie of the machine in operation.

Course Topics:

  1. Introduction to Artificial Intelligence
  2. Lisp
  3. Search Methods
    1. State Space Search
    2. Problem Reduction Search
    3. Game Playing
    4. Means-Ends Analysis
  4. Knowledge Representation
    1. First-order Predicate Calculus
      1. Unification
      2. Resolution
      3. Question answering using Logic
      4. Problem solving using Logic
      5. Procedural Interpretation of Logic, Prolog
    2. Non-monotonic Reasoning
    3. Semantic Nets, Frames, Scripts
  5. Natural Language Understanding
  6. Expert Systems
  7. Perception, Neuroscience
  8. Advanced Applications of AI

Course grades are assigned on the scale A = 90-100, B = 80-90, etc. provided that the Final Exam grade is at least 65; if the Final Exam grade is below 65, a lower course grade may be assigned at the instructor's discretion. Grades are averaged using the following weights:
Midterm Exam 25% Monday, October 22, in class
Final Exam 35% Friday, December 14, 2-5 PM
Programming Assignments 40% (10% per day late penalty)

All students must complete all exams and programming assignments. Class attendance is expected. Failure to attend class is grounds for a reduced grade.

Programming projects must be individual work. Students may discuss concepts or help with specific problems in another student's code. However, sharing code constitutes plagiarism. Students may not work together on program design. All code that is given in the class directory may be used as part of your programs.

Programs are assigned letter grades, which are numerically averaged as A+ = 100, A = 95, A- = 93, B+ = 88, etc. A program that just satisfies the assignment and has no errors will typically be given a grade of A-; grades of A and A+ are given to programs that have something extra, such as extra work or especially nice code. Note, however, that a grade of A- is averaged several points higher than the bottom of the A range; for example, a student who made 88 on both exams and received A- on all programs would have an average of 90 and receive a grade of A-.