CSCI 460 - Introduction to Artificial Intelligence
CSCI 460
Introduction to Artificial Intelligence
|
If you are enrolled in this class, please check this page regularly to
find new or updated information. Not all dates are final; assignments
are not final until the date they are assigned.
Contact
Office : SAL 228
Phone : (213) 740-4520
Email : mataric@cs.usc.edu
WWW : http://robotics.ucs.edu/~maja
Office Hours: Monday 3:30-5:30pm
and by appointment
Office : SAL 319
Phone : (213) 740-6503/4495
Email : junpark@cs.usc.edu
WWW : http://tracker.usc.edu/~junp
Office Hours: Thursday 12:45-2:45pm
and by appointment
Back to top
Syllabus
Course objective
This course is an introduction to the basic concepts of Artificial
Intelligence, with illustrations of current state of the art research
and applications. The course will cover a broad spectrum of AI
concepts and methods, and apply some of them in programming
assignments.
Course description
The course is organized around the textbook, and
will cover about half of the book. Additionally, we will be
introducing the Lisp programming
language as it will be used for example programs and you will need to
use it for the programming assignments and the project. The following
topics will be covered as permitted by time (with corresponding
chapters, sections, and marked pages of the textbook):
INTRODUCTION
1 Introduction
1.1 What Is AI?
1.2 The Foundations Of Artificial Intelligence
1.3 The History Of Artificial Intelligence
1.4 The State Of The Art
2 Intelligent Agents
2.1 Introduction
2.2 How Agents Should Act
2.3 Structure Of Intelligent Agents
2.4 Environments
PROBLEM SOLVING
3 Solving Problems By Searching
3.1 Problem-Solving Agents
3.2 Formulating Problems
3.3 Example Problems
3.4 Searching For Solutions
3.5 Search Strategies
3.6 Avoiding Repeated States
3.7 Constraint Satisfaction Search
4 Informed Search Methods
4.1 Best-First Search
4.2 Heuristic Functions
4.3 Memory Bounded Search
4.4 Iterative Improvement Algorithms
LOGIC
6 Agents That Reason Logically
6.1 A Knowledge-Based Agent
6.2 The Wumpus World Environment
6.3 Representation, Reasoning, And Logic
6.4 Propositional Logic: A Very Simple Logic
6.5 An Agent For The Wumpus World
7 First-Order Logic
7.1 Syntax And Semantics
7.2 Extensions And Notational Variations
7.3 Using First-Order Logic
7.4 Logical Agents For The Wumpus World
7.5 A Simple Reflex Agent
7.6 Representing Change In The World
7.7 Deducing Hidden Properties Of The World
7.8 Preferences Among Actions
7.9 Toward A Goal-Based Agent
9 Inference In First-Order Logic
9.1 Inference Rules Involving Quantifiers
9.2 An Example Proof
9.3 Generalized Modus Ponens
9.4 Forward And Backward Chaining
9.5 Completeness
9.6 Resolution: A Complete Inference Procedure
PLANNING
11 Planning
11.1 A Simple Planning Agent
11.2 From Problem Solving To Planning
11.3 Planning In Situation Calculus
11.4 Basic Representations For Planning
11.5 A Partial-Order Planning Example
11.6 A Partial-Order Planning Algorithm
11.7 Planning With Partially Instantiated Operators
11.8 Knowledge Engineering For Planning
12 Practical Planning
12.1 Practical Planners
12.2 Hierarchical Decomposition
12.3 Analysis of Hierarchical Decomposition
13 Planning and Acting
13.1 Conditional Planning
13.2 A Simple Replanning Agent
13.3 Fully Integrated Planning and Execution
14 Uncertainty
14.1 Acting Under Uncertainty
14.2 Basic Probability Notation
14.3 The Axioms Of Probability
14.4 Bayes' Rule And Its Use
14.5 Where Do Probabilities Come From?
15 Probabilistic Reasoning Systems
15.1 Representing Knowledge in an Uncertain Domain
15.2 The Semantics of Belief Networks
15.3 Inference in Belief Networks (up to page 447)
15.6 Fuzzy sets and fuzzy logic
(pages 463-464 only)
LEARNING
18 Learning From Observations
18.1 A General Model Of Learning Agents
18.2 Inductive Learning
18.3 Learning Decision Trees
18.5 Learning General Logical Descriptions
19 Learning in Neural Netowrks
19.1 How the Brain Works
19.2 Neural Networks
19.3 Perceptrons
19.4 Multilayer Feed-Forward Networks
19.5 Applications of Neural Networks
20 Reinforcement Learning
20.1 Introduction
20.2 Passive Learning in a Known Environment
20.3 Passive Learning in an Unknown Environment
20.4 Active Learning in an Unknown Environment
20.5 Exploration
20.6 Learning in an Action-Value Function
20.7 Generalization in Reinforcement Learning
20.8 Genetic Algorithms and Evolutionary Computation
24 Perception
24.1 Introduction
24.4 Extracting 3-D Information Using Vision
(pages 734-735 only)
24.5 Using Vision for Manipulation and Navigation
24.6 Object Representation and Recognition
24.7 Speech Recognition
25 Robotics
25.1 Introduction
25.2 Tasks: What are robots for?
25.3 Parts: What are robots made of?
25.4 Architectures
25.5 Configuration Spaces
25.6 Navigation and Motion Planning
DISCUSSION ON AI
27 AI: Present And Future
27.1 Have We Succeeded Yet?
27.2 What Exactly Are We Trying To Do?
27.3 What If We Do Succeed?
Examinations
- One in-class midterm on 10/29/97
- One out-of-class final on 12/12/97
Both exams will be closed book, closed notes, no computers.
Assignments
There will be eight homeworks in
this course, all of which are mandatory. Their handout and due dates
are specified in the class schedule below.
When to turn in your assignments
For
any assignment, "Due on a given date" means that the
assignment must be given to Prof. Mataric at the beginning of
lecture on the specified date. Turning the assignment in at
the end of class will be discounted as late and automatically lose
20% of the grade. Partial solutions are much better than no solutions.
Turning the homework in one day late loses 33% of the grade, two days
late 66%, 3 days late 99%; no homework will be accepted more than 3
days late. If you have a really good reason to be late (e.g., illness
or death) you must talk to the instructor before the homework
due date. Solutions to each homework will be made available on the
Web page 3 days after the due date or after the point when no
more late homeworks will be accepted.
Format of your assignments
All
assignments must be typed (no handwriting will be accepted), single
sided, labeled with your full name in the right hand corner of each
page you turn in, with separate problems on separate pages (to make
distributed grading easier). Have all pages stapled together and turn
it all in at the beginning of class on the due date. Programming
assignments will be implemented in Lisp, and due in hardcopy at the
beginning of class, just like the rest of the homeworks. Some
programming assignments will also be submitted by email, and the
deadline will be the same: the beginning of class. Anything you email
us, you must also turn in in hardcopy in class.
Cheating
All homeworks must be
solved and written independently, or you will be penalized for
cheating. See information on academic integrity below for more
details.
Grading
The homewors will count for 35% of your grade, the
midterm exam for 30% and the final exam for 35%. All percentages are
approximate.
None of the assignments or exams is optional. Failure to turn in
without discussion with the professor beforehand will result in an
F in the class.
Academic integrity
The USC
Student Conduct Code
prohibits
plagiarism. All USC students are responsible for
reading and following the
Student Conduct Code, which appears on pp. 83-97 of the 1996-1997 SCampus.
In this course we encourage students to study together. This includes
discussing general strategies to be used on individual
assignments. However, all work submitted for the class is to be done
individually.
Some examples of what is not allowed by the conduct code: copying all
or part of someone else's work (by hand or by looking at others'
files, either secretly or if shown), and submitting it as your own;
giving another student in the class a copy of your assignment
solution; consulting with another student during an exam. If you have
questions about what is allowed, please discuss it with the
instructor.
Students who violate University standards of academic integrity are
subject to disciplinary sanctions, including failure in the course and
suspension from the University. Since dishonesty in any form harms
the individual, other students, and the University, policies on
academic integrity will be strictly enforced. We expect you to
familiarize yourself with the Academic Integrity guidelines found in
the current SCampus.
Violations of the Student Conduct Code will be filed with the Office
of Student Conduct, and
appropriate sanctions will be given.
Pre-requisite CSCI 102. Plus familiarity with C or
C++ or Lisp programming.
Courses of Instruction - Computer Science (CSCI)
Back to top
Class material
Textbooks:
Artificial Intelligence: A Modern Approach by S. Russell
and P. Norvig
"ANSI Common Lisp" by P. Graham
Back to top
Schedule of lectures
Lectures are on Mondays and Wednesdays, from 2:00PM to 3:30PM in Olin
406.
Chapter numbers refer to the Russell & Norvig textbook, unless
it is specified
that they refer to the Lisp book.
| Date
| Topic
| Assigned
| Due
|
| Wed 08/27
| Welcome / Introduction
| Ch 1
|
|
| Wed 09/03
| Introduction to Lisp
| Ch 1-3 of Lisp book
|
|
|
| Mon 09/08
| A bit more on Lisp
Intelligent Agents
| Ch 3 (trees) & 4 of Lisp book, Ch 2
Homework 1 (Lisp)
|
|
| Wed 09/10
| Lisp tutorial by Jun Park, 12:30-2pm, SAL 322
Search
| Ch 3
|
|
| Mon 09/15
| Informed Search I
| Ch 3 and 4
Homework 2 (Ch 2,3,4)
| Homework 1
|
| Wed 09/17
| Informed Search II
| Ch 4
HW 1 Solution
|
|
| Mon 09/22
| Logical Reasoning
| Ch 6
|
|
| Wed 09/24
| Reasoning and FOL
| Ch 6 and 7
Homework 3 (Ch 6,7)
| Homework 2
|
|
|
| Mon 09/29
| First Order Logic (FOL)
| Ch 7
HW 2 Solution
|
|
|
| Wed 10/01
| Inference in FOL
| Ch 9 (except 9.7)
|
|
| Mon 10/06
| Inference and Planning
| Ch 9 and 11
Homework 4 (Ch 9,11)
| Homework 3
|
| Wed 10/8
| Planning
| Ch 11
HW 3 Solution
|
|
| Mon 10/13
| Practical Planning
| Ch 12.1-12.3
|
|
| Wed 10/15
| Planning and Acting
| Ch 13
Homework 5 (Ch 12,13)
| Homework 4
|
| Mon 10/20
| Planning and Acting
| Ch 13
|
| Wed 10/22
| Uncertainty
| Ch 14
HW 4 Solution
|
| Mon 10/27
| Review
| Ch 1,2,3,4,6,7,9,11,12,13
HW 5 Solution
| Homework 5
|
| Wed 10/29
| In-Class Midterm
| Covers Ch 1,2,3,4,6,7,9,11,12,13
|
| Mon 11/03
| Uncertainty and Probability
| Ch 14+15 (436-447+462-464 only)
Homework 6 (Ch 14,15)
|
|
| Wed 11/05
| Probabilistic Reasoning
| Ch 15: pp. 436-447, 462-464
|
|
| Mon 11/10
| Learning from Observation
| Ch 18.1-18.3+18.5
|
|
| Wed 11/12
| Neural Networks
| Ch 19.1-19.3
Homework 7 (Ch 18,19,20)
HW 6 Solution
| Homework 6
|
| Mon 11/17
| Networks and Rein-
forcement Learning
| Ch 19.3-19.5 and 20
|
|
| Wed 11/19
| Reinforcement Learning
| Ch 20
|
|
| Mon 11/24
| Perception
| Ch 24.1+734-5+24.5-24.7
Homework 8 (Ch 24,26)
HW 7 Solution
| Homework 7
|
| Wed 11/26
| Robotics
| Ch 25
|
| Mon 12/01
| AI: Present and Future
| Ch 27
|
|
| Wed 12/03
| Review
| Ch 14,15,18,19,20,24,25,27
| Homework 8
|
| | | | |
|
Friday
12/12/97
2-4pm
| FINAL
| Covers material from the entire semester
|
|
See schedule of Computer Science classes for Spring'97
Back to top
Assignments
We will be using Lisp for the programming assignments. Lisp is best
run under emacs. Directions to Run
Lisp under Emacs. Many code examples (e.g., fully implemented general
search programs) are available from the authors of the book. These are
available locally. For general references to
Lisp, including two versions of complete hypertext manuals, go to Lisp
References. The lecture notes on Lisp are also available. These notes
contain the class presentations and also other details that may not be
presented in class.
Back to top
Related web sites
The authors of the textbook maintain a very nice Web page at:
http://HTTP.CS.Berkeley.EDU/~russell/aima.html
You are strongly encouraged to explore and use this site and the useful links it provides.
Directory of AI on the Web
organised by chapter of the textbook.
U.S.C. Computer Science Department
U.S.C.
Back to top
Hits since 01/03/97
Maja Mataric