Principles of Autonomy and Decision Making
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.
- [IOR] = Hillier, Frederick, and Gerald Lieberman. Introduction to Operations Research . 9th ed. McGraw-Hill, 2009. ISBN: 9780077298340.
- [PA] = LaValle, Steven. Planning Algorithms . Cambridge University Press, 2006. ISBN: 9780521862059.
- [JINS] = Flanagan, David. Java in a Nutshell . 5th ed. O’Reilly, 2005. ISBN: 9780596007737.
- [AIMA] Chapter 2
- [JINS] Chapters 1-3 and 5
- LEC #: 2 · TOPICS: Foundations I: state space search · READINGS: [AIMA] Chapter 3.1-4
- LEC #: 5 · TOPICS: Constraints I: constraint programming · READINGS: [AIMA] Chapter 6.1, chapter 24.3-5
- LEC #: 6 · TOPICS: Constraints II: constraint satisfaction · READINGS: [AIMA] Chapters 6.2-6.5
- [AIMA] Chapter 10
- Blum, Avrim, and Merrick Furst. “Fast Planning Through Planning Graph Analysis.” Artificial Intelligence 90 (1997): 281-300.
- LEC #: 8 · TOPICS: Planning II: graph plan · READINGS: [AIMA] Chapter 11
- 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.
- LEC #: 10 · TOPICS: Model-based reasoning I: propositional logic and satisfiability · READINGS: [AIMA] Chapters 7-8
- 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.
- 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.
- [AIMA] Chapter 3.5-6
- [PA] Chapter 2.3
- [PA] Chapter 5
- [IOR] Chapters 2, 3, and 9.1-3
- [PA] Chapter 6.1-2
- LEC #: 17 · TOPICS: Mathematical programming II: the simplex method · READINGS: [IOR] Chapter 4
- LEC #: 18 · TOPICS: Mathematical programming III: (mixed-integer) linear programming for vehicle routing and motion planning · READINGS: [IOR] Chapter 11
- LEC #: 19 · TOPICS: Reasoning in an uncertain world · READINGS: [AIMA] Chapters 13 and 14.1-14.5
- [AIMA] Chapters 15.1-3 and 20.3
- Rabiner, Lawrence. “A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition.” Proceedings of the IEEE 77 (1989): 257-286.
- LEC #: 22 · TOPICS: Dynamic programming and machine learning I: Markov decision processes · READINGS: [AIMA] Chapter 17.1-3
- [AIMA] Chapters 5 and 17.5
- [PA] Chapters 9.3-4 and 10.5
- LEC #: 25 · TOPICS: Game theory II: differential games · READINGS: [AIMA] Chapter 17.6
Prerequisites & course information
Same subject as 6.4130J Subject meets with 6.4132J, 16.413[J] Prereq: 6.100B , 6.1010 , 6.9080 , or permission of instructor U (Fall) 4-0-8 units
Sources
- Course catalogue ↗2026–2027
- MIT OpenCourseWare ↗Fall 2010
- MIT OCW calendar ↗
- MIT OCW syllabus ↗
- MIT OCW readings ↗
- Historical MIT OpenCourseWare offering. Named reading entries and schedule topics are automatically extracted from the linked source pages.