everything.study
16.413

Principles of Autonomy and Decision Making

3-0-9 units · Graduate

Surveys decision making methods used to create highly autonomous systems and decision aids. Applies models, principles and algorithms taken from artificial intelligence and operations research. Focuses on planning as state-space search, including uninformed, informed and sampling-based search, activity and motion planning, probabilistic and adversarial planning, Markov models and decision processes, Bayesian filtering, reinforcement learning, and machine learning. Includes methods for satisfiability and optimization of logical and finite domain constraints, graphical models, and methods for search, inference, and conflict-learning. Students taking graduate version complete additional assignments.

Fall 2010

Topics

  • Introduction [BW]
  • Foundations I: state space search [BW]
  • Foundations II: complexity of state space search [BW]
  • Foundations III: soundness and completeness of search [SK]
  • Constraints I: constraint programming [BW]
  • Constraints II: constraint satisfaction [BW]
  • Planning II: graph plan [BW]
  • Planning III: plan termination and plan execution [BW]
  • Model-based reasoning I: propositional logic and satisfiability [BW]
  • Encoding planning problems as propositional logic satisfiability [SK]
  • Model-based reasoning II: diagnosis and mode estimation [BW]
  • Model-based reasoning III: OpSat and conflict-directed A* [BW]
  • Global path planning I: informed search [EF]
  • Global path planning II: sampling-based algorithms for motion planning [EF]
  • Mathematical programming I [EF]
  • Mathematical programming II: the simplex method [EF]
  • Mathematical programming III: (mixed-integer) linear programming for vehicle routing and motion planning [EF]
  • Reasoning in an uncertain world [BW]
  • Inferring state in an uncertain world I: introduction to hidden Markov models [EF]
  • Inferring state in an uncertain world II: hidden Markov models, the Baum-Welch algorithm [EF]
  • Dynamic programming and machine learning I: Markov decision processes [EF]
  • Dynamic programming and machine learning II: Markov decision processes, policy iteration [EF]
  • Game theory I: sequential games [EF]
  • Game theory II: differential games [SK]

Readings

  • [AIMA] = Russell, Stuart, and Peter Norvig. Artificial Intelligence: A Modern Approach . 3rd ed. Prentice Hall, 2009. ISBN: 9780136042594.
    Listed reading
  • [IOR] = Hillier, Frederick, and Gerald Lieberman. Introduction to Operations Research . 9th ed. McGraw-Hill, 2009. ISBN: 9780077298340.
    Listed reading
  • [PA] = LaValle, Steven. Planning Algorithms . Cambridge University Press, 2006. ISBN: 9780521862059.
    Listed reading
  • [JINS] = Flanagan, David. Java in a Nutshell . 5th ed. O’Reilly, 2005. ISBN: 9780596007737.
    Listed reading
  • [AIMA] Chapter 2
    Listed reading
  • [JINS] Chapters 1-3 and 5
    Listed reading
  • LEC #: 2 · TOPICS: Foundations I: state space search · READINGS: [AIMA] Chapter 3.1-4
    Reading assignment
  • Reading assignment
  • LEC #: 5 · TOPICS: Constraints I: constraint programming · READINGS: [AIMA] Chapter 6.1, chapter 24.3-5
    Reading assignment
  • LEC #: 6 · TOPICS: Constraints II: constraint satisfaction · READINGS: [AIMA] Chapters 6.2-6.5
    Reading assignment
  • [AIMA] Chapter 10
    Listed reading
  • Blum, Avrim, and Merrick Furst. “Fast Planning Through Planning Graph Analysis.” Artificial Intelligence 90 (1997): 281-300.
    Listed reading
  • LEC #: 8 · TOPICS: Planning II: graph plan · READINGS: [AIMA] Chapter 11
    Reading assignment
  • LEC #: 9 · TOPICS: Planning III: plan termination and plan execution · READINGS: Dechter, Rina, Itay Meiri, and Judea Pearl. “Temporal Constraint Networks.” Artificial Intelligence 49 (1991): 61-95.
    Reading assignment
  • LEC #: 10 · TOPICS: Model-based reasoning I: propositional logic and satisfiability · READINGS: [AIMA] Chapters 7-8
    Reading assignment
  • LEC #: 12 · TOPICS: Model-based reasoning II: diagnosis and mode estimation · READINGS: de Kleer, Johan, and Brian Williams. “Diagnosing Multiple Faults.” Artificial Intelligence 32 (1987): 100-117.
    Reading assignment
  • LEC #: 13 · TOPICS: Model-based reasoning III: OpSat and conflict-directed A* · READINGS: Williams, Brian, and Robert Ragno. “Conflict-directed A* and Its Role in Model-based Embedded Systems.” Discrete Applied Mathematics 155 (2007): 1562-1595.
    Reading assignment
  • [AIMA] Chapter 3.5-6
    Listed reading
  • [PA] Chapter 2.3
    Listed reading
  • [PA] Chapter 5
    Listed reading
  • Listed reading
  • [IOR] Chapters 2, 3, and 9.1-3
    Listed reading
  • [PA] Chapter 6.1-2
    Listed reading
  • LEC #: 17 · TOPICS: Mathematical programming II: the simplex method · READINGS: [IOR] Chapter 4
    Reading assignment
  • LEC #: 18 · TOPICS: Mathematical programming III: (mixed-integer) linear programming for vehicle routing and motion planning · READINGS: [IOR] Chapter 11
    Reading assignment
  • LEC #: 19 · TOPICS: Reasoning in an uncertain world · READINGS: [AIMA] Chapters 13 and 14.1-14.5
    Reading assignment
  • [AIMA] Chapters 15.1-3 and 20.3
    Listed reading
  • Rabiner, Lawrence. “A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition.” Proceedings of the IEEE 77 (1989): 257-286.
    Listed reading
  • LEC #: 22 · TOPICS: Dynamic programming and machine learning I: Markov decision processes · READINGS: [AIMA] Chapter 17.1-3
    Reading assignment
  • [AIMA] Chapters 5 and 17.5
    Listed reading
  • [PA] Chapters 9.3-4 and 10.5
    Listed reading
  • LEC #: 25 · TOPICS: Game theory II: differential games · READINGS: [AIMA] Chapter 17.6
    Reading assignment

Prerequisites & course information

Same subject as 6.4132J Subject meets with 6.4130J, 16.410[J] Prereq: 6.100B , 6.9080 , or permission of instructor G (Fall) 3-0-9 units

Sources