Computing and Information Technology Interactive Digital Educational Library


Syllabus Collection >
Syllabus >

Please use this identifier to cite or link to this item:

Title: AI Planning and Decision Making
Issue Date: 
Abstract: CS 397: AI Planning and Decision Making Spring 2002 12:30-1:45 TuTh 203 Transportation Registration: 3 hours, or 3/4 unit or 1 unit, 01666 LECT SML Instructor: Prof. Steve LaValle, 2107 DCL, Index A. General Information and Motivation B. Topics C. Lectures D. Assignments E. Related Web Pages A. General Information and Motivation * Throughout many aspects of AI, there is a recurring need to automate sequences of decisions. Whether the goal is to construct agents, bots, decision makers, game players, problem solvers, robots, controllers, or e-traders, many core issues remain the same. This course is designed to cover the core concepts that can be applied in a variety of applications, and remain important over time, even as the latest terminology and research directions change. This course is intended to serve as a sequel to the introductory AI course, and can be considered as complementary to machine learning (which would make another possible sequel to an introductory AI course). The level of coverage is on the border between advanced undergraduate and beginning graduate; students from either group are welcome. In the Spring 2002, it is offered as an experimental course, with the intention of becoming a permanent course in future semesters. * Prerequisites: CS 348 or equivalent * Text: There is no single textbook that covers all of the topics of this course. Material will be drawn from book chapters, recent papers, and notes. * Office hours: Room 2107 DCL Tu 1:45-2:45, Wed. 1:30-2:30, or whenever you can find me. * Course policies, grading, etc. * FINAL EXAM: Wednesday, May 8, 7pm-9pm (the usual place) * GRADES: [ascii] B. Topics (tentative) * Single-Stage Decision Making o optimal decisions o statistical decision theory o Bayesian classification and parameter estimation o utility theory o criticisms of Bayesian analysis o multiobjective optimality * Planning: Sequential Decision Making o search algorithms o decision trees o Markov decision processes o value functions o reinforcement learning o dynamic programming approaches * Integrating Planning, Sensing, and Acting o conditional plans o reactive planning/feedback o connections to control theory o a Bayesian framework o information spaces * Game Theory: Multiple Decision Makers o single and multi-stage games o equilibrium concepts o pure and mixed strategies o noncooperative, cooperative, and bargaining models o communication issues * Logic-Based Concepts o temporal logic o partial order planning, refinement o abstraction, coercion o hierarchial planning * Other Possible Topics o hybrid systems o financial decision making o robotics issues o scheduling o issues in large-scale planning systems C. Lectures Date Topics Materials Jan 15 course overview, single-stage decision making, loss, deterministic vs. randomized decisions Handout: course syllabus Jan 17 continuous choice sets, uncertainty, games against nature, observation spaces, Bayes and minimax decision rules . Jan 22 classification, OCR example . Jan 24 parameter estimation, utility theory . Jan 29 criticisms of decision theory, frequentist vs. Bayesian, obtaining priors . Jan 31 multiobjective decision making . Feb 5 multi-stage decision making, state spaces, additive loss, termination actions . Feb 7 representations (STRIPS, decision-theoretic, graph), cost-to-come, cost-to-go . Feb 12 forward and backwards dynamic programming, relation to Dijkstra . Feb 14 multiple-stage games against nature, Markovian models Handout: Dynamic programming notes: [pdf] [ps] Feb 19 feedback strategies, forward projections . Feb 21 dynamic programming . Feb 26 infinite horizon problems . Feb 28 policy iteration, reinforcement learning Surveys: [Dean] [Kaebling et al.] [Harmon et al.] Mar 5 reinforcement learning, imperfect information . Mar 7 observations, information states . Mar 12 MIDTERM EXAM . Mar 26 information space representations . Mar 28 information space representations . Apr 2 examples of informations spaces . Apr 4 Class was cancelled . Apr 9 Solving imperfect state information problems . Apr 11 Two-person zero-sum games . Apr 16 Two-person zero-sum games . Apr 18 Two-person zero-sum games . Apr 23 N-person nonzero-sum games . Apr 25 N-person nonzero-sum games . Apr 30 Perspective . D. Assignments * Homework 1: [pdf] [ps] (due Jan. 31 in class) * Homework 2: [pdf] [ps] (due Feb. 21 in class) * Homework 3: [pdf] [ps] (due Mar. 15 by 5pm) -- correction made on 2/27 * Homework 4: [pdf] [ps] (due Apr. 16 in class) * Homework 5: [pdf] [ps] (due Apr. 25 in class) E. Related Web Pages General: * AAAI Planning & Scheduling pages * AIAI Planning pages (U. of Edinburgh) * A planning course at Arizona State University * AI Planning and Scheduling Conference Single-Stage Decision Making: * Thomas Bayes * Pierre-Simon Laplace * Utility theory * Bayesians vs. frequentists in physics * Bayesians vs. frequentists in medicine * Why someone is not a Bayesian * Statistical decision theory (Google) * Pattern recognition (Google) * Bayesian statistics and parameter estimation * Free book on classification * OCR overview * Multiobjective optimization notes * Vilfredo Pareto Sequential Decision Making: * An MDP tutorial * POMDP information page * Andrei Andreyevich Markov Game Theory: * A Beautiful Mind * John Nash * John von Neumann * Play the Prisoner's Dilemma game * Outline of the history of game theory
Appears in Collections:Syllabus

Files in This Item:

File SizeFormat

All items in DSpace are protected by copyright, with all rights reserved.


Valid XHTML 1.0! DSpace Software Copyright © 2002-2006 MIT and Hewlett-Packard - Feedback