EECS 591: Advanced Artificial Intelligence

Fall 2006, Prof. Michael Branicky

General Information

Lecture Hours: TR 10-11:15am, Olin 314

Course Instructor: Michael Branicky, mb@case.edu, Glennan 517B, x6430

Instructor's Office Hours: W 2-5pm

Course Website: http://dora.case.edu/msb/591   dora/msb/591

Grading (roughly):
1/3: homework (will involve programming)
1/3: participation (presenting papers, discussion leading/contributing, ...)
1/3: final project (midterm proposal, in-class presentation, conf.-style report)

A Recommended AI Reference:

• Stuart Russell and Peter Norvig. Artificial Intelligence: A Modern Approach. 2nd Ed. Prentice Hall, 2003. ISBN: 0137903952
  Buy it for $88.66 from bn.com: AI: A Modern Approach

Other Resources:

• Richard S. Sutton and Andrew G. Barto. Introduction to Reinforcement Learning. MIT Press, 1998. ISBN: 0262193981
  On-line Version
  Buy it for $58.00 from bn.com: Reinforcement Learning

• Steven M. LaValle. Planning Algorithms. Cambridge University Press, 2006. ISBN: 0521862051
  On-line Version
  Buy it for $48.00 from bn.com: Planning Algorithms

Class Blog

Lecture Notes / Handouts

29 AUG: Introduction  

Handout: AI State of Art [Source: Russell & Norvig]

Handout: Basic Evaluation Criteria (due for UC in April): pp. 14-15, Rules document, http://www.darpa.mil/grandchallenge/rules.asp

31 AUG: Discussion Paper: Stanley Overview [Presentation Slides by Nathan Wedge]

---

05 SEP: Agent Architectures

07 SEP: Agent Architectures [Presentation Slides by Philip Thomas]

• Brooks' Behavior Architecture
• Gat's 3-Layer Architecture

---

12 SEP: Intro. to Motion Planning I [REF.: Lavalle, Ch. 1 and various]

14 SEP: Intro. to Motion Planning II [REF.: Lavalle, Ch. 1 and various]

---

19 SEP: Discrete Planning [led by MSB] Handout 1 Handout 2

• Chapter 2 of LaValle's book [Read before class]

21 SEP: Sampling-Based Planning [Presentation Slides by Ashwin Deo]

• Kavraki and Latombe's early PRM paper
• LaValle and Kuffner's RRT survey

---

26 SEP: Sensor-Based Planning [Presentation Slides by Andrew Allen]

• Lumelsky and Stepanov's Bug Algorithms paper

28 SEP: Planning in Practice

---

03 OCT: Sampling-Based Reachability; HW#1 due

05 OCT: Motion Planning in a Dynamic Environment [Presentation Slides by David Buckmaster]

• Chapter 6 of Frazzoli's PhD Thesis

---

10 OCT: Collision Avoidance with Quasi-Static Obstacles [led by MSB]

• Reflex Control

12 OCT: Collision Avoidance with Moving Obstacles [Presentation Slides by Camelia Al-Najjar]

• Kosecka et al.'s on Air Traffic Management
• Leitman and Skowronski's Avoidance Control

---

17 OCT: Sensors and Information Spaces 1

• LaValle's Book: 11.1-3
• Russell & Norvig: 15.1-2 (15.3 is optional)

19 OCT: Sensors and Information Spaces 2

• LaValle's Book: 11.4-6
• Russell & Norvig: 15.4

---

24 OCT: FALL BREAK (No Class)

26 OCT: Planning Under Sensing Uncertainty 1; Project Proposals Due

• LaValle's Book: 12.1-2
• Russell & Norvig: 25.3

---

31 OCT: Planning Under Sensing Uncertainty 2

• LaValle's Book: 12.3 (except 12.3.4) and 12.5
• Russell & Norvig: 25.5

02 NOV: Robotic Localization Methods [Presentation Slides by Amaury Rolin]

• Particle Filters in Robotics (Thrun)
• An Experimental Comparison of Localization Methods (Gutmann et al.)
• An Experimental Comparison of Localization Methods Continued (Gutmann & Fox)

---

07 NOV: Model-based Tracking [Presentation Slides by Kati Daltorio]

• Identification of Decision Rules in a Human-controlled System: Vehicls at a Traffic Intersection (Walton et al.)
• What are the Ants Doing? Vision-based Tracking and Reconstruction of Control Programs (Egerstedt et al.)

09 NOV: Urban Challenge Sensing/Observation Overview (Guests: Scott McHmichael, Case UC Observers & Sensors Team Lead, and Bradley Farnsworth, LIDAR Sensing) [Presentation Slides by Scott McMichael]

---

Last major topic is Reinforcement Learning (with papers on TD- and Q-learning, Learning with Behaviors, Policy-Search Methods, ...)

14 NOV: Reinforment Learning Intro.; HW#2 due

• Sutton & Barto: Chapter 1; Sections 2.0-3, 2.7, 3.0-3

16 NOV: Reinforcement Learning 1

• Kaelbling, Littman, and Moore's Survey Paper, Sections 1-4

---

21 NOV: Reinforcement Learning 2

• Kaelbling, Littman, and Moore's Survey Paper, Sections 5-9

23 NOV: THANKSGIVING HOLIDAYS (No Class)

---

28 NOV: Learning and Games [led by MSB]

• Shannon's chess paper: pdf | txt
• Samuel's checkers paper: pdf
• Tesauro's backgammon paper pdf | html

30 NOV: Macro-Actions / Options [led by David Buckmaster]

• Roles of Macro-Actions in Accelerating Reinforcement Learning (McGovern, Sutton, Fagg)
• Between MDPs and Semi-MDPs: A Framework for Temporal Abstraction in Reinforcement Learning (Sutton, Precup, Singh)

---

05 DEC: Robot Learning [led by Christopher Hesse]

• Task-Level Learning: Experiments and Extensions (Branicky)
• Learning from Demonstration (Schaal)
• Is Imitation Learning the Route to Humanoid Robots? (Schaal)

07 DEC: Policy Search Methods [led by Jeremy Marvel]; HW#3 due (not late by 5PM, Monday, 11 DEC)

• Gradient Descent for General Reinforcement Learning (Baird and Moore)
• Robot Weightlifting by Direct Policy Search (Rosenstein and Barto)
• Autonomous Helicopter Flight via Reinforcement Learning (Ng et al.)

---

11 DEC: Last day to turn in HW#3 w/o penalty [5PM; 10%/day thereafter]

18 DEC: Last day to turn in Final Project papers (hardcopy & .pdf) w/o penalty [12 noon; 25%/day thereafter]

19 DEC: *** Project Presentations: FINAL EXAM PERIOD (12:30-3:30PM) ***

20 DEC: Last day to email Final Project Presentations (.ppt & .pdf) w/o penalty [12 noon; 50%/day thereafter]

Homeworks

Homework #1 (Due 10/03)

Homework #2 (Due 11/14)

Homework #3 (Due 12/07; Late after 5PM, 12/11)

Gridworld Data (obstacle i,j pairs): gridworld.dat, 
C++ file (reads gridworld.dat): gridworld.cc, 
Matlab file (standalone): gridworld.m, 
pdf of Matlab output

Final Projects

Information Sheet  

Final Project List from Spring 2003

Format will be the IEEE conference style, submitted in hardcopy and PDF

• LaTeX: Class File   Sample Document   Support/FAQ
• MS-Word: Template   Sample Document   Support/FAQ
• PDF: Support/FAQ

Useful Links

Nova Program: The Great Robot Race

Nova Extras: Meet the Teams | Outtakes | What Robots See

Wikipedia: DARPA Grand Challenge

DARPA: official Urban Challenge site

Stanford Racing team site

Numerical Recipes in C: Chapter 7.2, "Transformation Method: Exponential and Normal Deviates"

EM Handouts/Links

• EM section from Nilsson's AI book
• EM section from Mitchell's AI book
• Motion Segmentation using EM - A Short Tutorial