| Lec # | TOPICS | READINGS |
|---|---|---|
| 1 | Introduction to Cognitive Robotics Learning Objectives, Remote Explorers, Model-based Programming | Muscettola, N., P. Nayak, B. Pell, and B. Williams. "Remote Agent: To Boldly Go Where No AI System Has Gone Before." Artificial Intelligence 103 (1998): 5-47. Bohlin, R., and L. Kavraki. "Path Planning Using Lazy PRM." Intl Conf on Robotics and Automation (ICRA) 1 (2000): 521-528. Hsu, D., R. Kindel, J. C. Latombe, and S. Rock. "Randomized Kinodynamic Motion Planning with Moving Obstacles." Fourth International Workshop on Algorithmic Foundations of Robotics, 2000. (PDF) LaValle, Steven M. "Rapidly-Exploring Random Trees: A New Tool for Path Planning." Technical Report No. 98-11, Dept. of Computer Science, Iowa State University, October 1998. |
| Robots that Deftly Navigate | ||
| 2 | Kinodynamic and Randomized Path Planning Review of Configuration Spaces, Visibility Graphs, Voronoi Diagrams, Potential Fields, and Cell Decomposition Kino-dynamic Planning, Planning with Moving Obstacles, Probabilistic Roadmaps (PRMs), Rapidly Exploring Random Trees (RRTs) | |
| 3 | Introduction to Simultaneous Localization and Mapping (SLAM) (Guest: Paul Robertson) Localization, SLAM, Kalman Filter, Large Scale SLAM | Leonard, J., and P. Newman. "Consistent, Convergent, and Constant-Time SLAM." In 18th International Joint Conference on Artificial Intelligence. Acapulco, Mexico, August 2003. (PDF) Eliazar, Austin, and Ronald Parr. "DP-SLAM: Fast, Robust Simultaneous Localization and Mapping Without Predetermined Landmarks." In 18th International Joint Conference on Artificial Intelligence. Acapulco, Mexico, August 2003. (PDF) |
| 4 | Vision Based SLAM (Guest: Paul Robertson) Topological Maps, Hidden Markov Models (HMM), SIFT, Vision-based Localization | |
| Deducing State and Diagnosing Failure | ||
| 5 | Model-based Diagnosis and Mode Estimation Consistency-based Diagnosis: Candidates, Conflicts, Diagnoses, and Kernel Diagnoses Conflict Extraction and Candidate Generation, Mode Estimation and Probabilistic Diagnosis, Active Probing | De Kleer, Johan, Alan K. Mackworth, and Raymond Reiter. "Characterizing Diagnoses and Systems." Artificial Intelligence 56 (1992). |
| 6 | Solving Optimal CSPs through Conflict-Learning Optimal Constraint Satisfaction Problems, Constraint-based A*, Conflict-directed A*, Conflict Extraction | Williams, Brian C., and Robert Ragno. "Conflict-directed A* and its Role in Model-based Embedded Systems." Journal of Discrete Applied Math (January 2003). (Appears in the Special Issue on Theory and Applications of Satisfiability Testing.) |
| Reasoning About Soft Constraints | ||
| 7 | Soft Constraint Satisfaction Problems (SCSPs) (Guest: Martin Sachenbacher) Valued Constraint Satisfaction Problems (VCSPs), Branch-and-bound Search for Soft Constraints, Variable Elimination for Soft Constraints, Tree Decomposition, Dynamic Programming | Schiex, J. T., H. Fargier, and G. Verfaillie. "Valued Constraint Satisfaction Problems: Hard and easy problems." In Proceedings of the International Joint Conference in AI (IJCAI-95). Montreal, Canada, 1995. Dechter, Rina. "Tree Decomposition Methods," and "Constraint Optimization." Chapter 9 and 13 in Constraint Processing. San Francisco, CA: Morgan Kaufmann Publishers, 2003. ISBN: 1558608907. |
| 8 | Solving CSPs and SCSPS via Decomposition and Abstraction (Guest: Martin Sachenbacher) Reduced Ordered Binary Decision Diagrams (ROBDDs), Representing and Manipulating Soft Constraints using Algebraic Decision Diagrams (ADDs) | Bryant, Randal E. "Graph-Based Algorithms for Boolean Function Manipulation." IEEE Transactions on Computers C-35, no. 8 (1986): 677-691. (PDF) Bahar, R. I., E. A. Frohm, C. M. Gaona, G. D. Hachtel, E. Macii, A. Pardo, and F. Somenzi. "Algebraic decision diagrams and their applications." In Proceedings of the International Conference on Computer-Aided Design. 1993, pp. 188-191. |
| Planning Complex Missions | ||
| 9 | Mission-level Task Planning (Guest: Robert Tappan Morris) Partial Order Planning, Constraint-based Interval Planning, and Simple Temporal Networks (STNs) | Smith, David E., Jeremy Frank, and Ari Jonsson. "Bridging the Gap between Planning and Scheduling." Knowledge Engineering Review 15, no. 1 (2000). Kim, P., B. Williams, and M. Abramson. "Executing Reactive, Model-based Programs through Graph-based Temporal Planning." In International Joint Conference on Artificial Intelligence. 2001, pp. 487-493. Morris, Paul, Robert Morris, Lina Khatib, Sailesh Ramakrishnan, and Andrew Bachmann. "Strategies for Global Optimization of Temporal Preferences." Proceedings of the 10th International Conference on Principles and Practice of Constraint Programming, CP 2004, Toronto, Canada. |
| 10 | Dynamic Plan Execution Under Uncertainty STNS, Dispatchable Networks and Dispatching Execution, STNUs, Strong and Dynamic Controllability | Dechter, R., I. Meiri, and J. Pearl. "Temporal Constraint Networks" Artificial Intelligence (1991). Muscettola, N., and P. Morris. "Execution of Temporal Plans with Uncertainty." (PDF) |
| 11 | Mixed Human Robotic Exploration (Guest: Jeff Hoffman) | |
| Robots that Plan on the Fly | ||
| 12 | Hidden State and Model-based Reactive Planning Universal Planning, Structure Decomposition for Model-based Reactive Planning (MRP), Binary Decision Diagrams, Symbolic MRP | Ingham, Ragno, and Williams. "A Reactive Planner for a Model-based Executive." In Proceedings of the 15th International Joint Conference on Artificial Intelligence (IJCAI-97). |
| 13 | Continuous, Incremental Path Planning and Exploration Single Source Shortest Path, D*, LRTA* | Koenig, S., and M. Likhachev. "Incremental A*." In Advances in Neural Information Processing Systems 14. Cambridge, MA: MIT Press, 2002. ISBN: 0262042088. (NIPS) Stentz, A. "Optimal and Efficient Path Planning for Partially-Known Environments." In Proceedings of IEEE International Conference on Robotics and Automation, May 1994. (PDF) |
| 14 | Planning with POMDPs (Student Presenters: Brian Bairstow, Tony Jimenez, and Larry Bush) An Introduction to the Fundamentals of POMDPs, State of the Art in POMDP Research, A Pedagogical Explanation of the Respective Algorithm | Theocharous, Georgios, and Leslie Pack Kaelbling. "Approximate Planning in POMDPS with Macro-Actions." In Advances in Neural Information Processing Systems 16. Cambridge, MA: MIT Press, 2004. ISBN: 0262201526. Vancouver, (NIPS-03). Roy, N., G. Gordon and S. Thrun. "Finding Approximate POMDP solutions Through Belief Compression." Journal of Artificial Intelligence Research 23 (2005): 1-40. Roy, N. "PhD Thesis: Finding Approximate POMDP Solutions Through Belief Compression." Robotics Institute, Carnegie Mellon University, 2003. Russell, Stuart, and Peter Norvig. Artificial Intelligence: A Modern Approach. 2nd ed. New York, NY: Prentice Hall, 2002. ISBN: 0137903952.Kaelbling, Leslie Pack, Michael L. Littman, and Anthony R. Cassandra. "Planning and Acting in Partially Observable Stochastic Domains." Artificial Intelligence 101 (1998). Hiller, F., and G. Lieberman. Introduction to Operations Research. 7th ed. New York, NY: McGraw Hill, 2002. ISBN: 0072535105. Jaakkola, T., S. Singh, and M. Jordan. "Reinforcement Learning Algorithm for Partially Observable Markov Decision Problems." Advances In Neural Information Processing Systems. Cambridge, MA: MIT Press, 1995. ISBN: 0262201046. (PDF)Theocharous, Georgios, Kevin Murphy, and Leslie Pack Kaelbling. "Representing hierarchical POMDPs as DBNs for multi-scale robot localization." In International Conference on Robotics and Automation, 2004. |
| 15 | Model-based, Multi-Agent Reasoning in Texas Hold'em Poker (Student Presenters: Brian Edward Mihok and Michael Terry) Leading Techniques in Games Reasoning, Emphasis on Uncertainty Techniques Hidden Markov Models and Bayesian Inference, Neural Networks | Rabiner, L. R. "A tutorial on Hidden Markov Models and selected applications in speech recognition." Proceedings of the IEEE 77, no. 2 (1989): 257-286. (PDF) Friedman, N., I. Nachman, and D. Pe'er. "Learning bayes network structure from massive datasets: The "sparse candidate" algorithm." Uncertainty in Artificial Intelligence 15 (1999): 206-215. Ennis, M., G. Hinton, D. Naylor, M. Revow, and R. Tibshirani. "A comparison of statistical learning methods on the GUSTO database." Stat Med 17, no. 21 (1998): 2501-2508. Moore, Andrew. "Tutorial on Bayes Nets." (Microsoft® PowerPoint® lecture.) (PDF) Dietterich, T. G. "Machine Learning for Sequential Data: A Review." In Structural, Syntactic, and Statistical Pattern Recognition; Lecture Notes in Computer Science. Vol. 2396. Edited by T. Caelli. New York, NY: Springer, 2002, pp. 15-30. ISBN: 3540440119. (PDF)Bilmes, Jeff. "What HMMs Can Do." UWEE Technical Report Number UWEETR-2002-0003. January 2002. |
| 16 | Cognitive Game Theory (Student Presenters: Justin Fox, Jeremie Pouly, and Jennifer Novosad) Alpha-Beta and its Extensions An Evolutionary Algorithm Applied to Chess Inductive Adversary Modeler | Gross, R., K. Albrecht, W. Kantschik, and W. Banzhaf. "Evolving Chess Playing Programs." Proceedings of the Genetic and Evolutionary Computation Conference, 2002. Walczak, Steven. "Knowledge-Based Search in Competitive Domains." IEEE Transactions on Knowledge and Data Engineering 15, no. 3 (May/June 2003). Banzhaf, W., P. Nordin, R. E. Keller, and F. D. Francone. Genetic Programming - An Introduction On The Automatic Evolution of Computer Programs and its Applications>. San Francisco, CA: Morgan Kaufman, 1997. ISBN: 155860510X.Schaeffer, J. "The History Heuristic and Alpha-Beta Search Enhancements in Practice." IEEE Transactions on Pattern Analysis and Machine Intelligence 11, no. 11 (1989): 1203-1212. Schwefel, H. P. Evolution and Optimum Seeking. New York, NY: John Wiley and Sons, Inc., 1996. ISBN: 0471571482.Walczak, Steven. "Improving Opening Book Performance Through Modeling of Chess Opponents." ACM Annual Computer Science Conference, 1996. |
| 17 | Mode Estimation for Hybrid Discrete/Continuous Systems (Student Presenters: Lars Blackmore) Trajectory Tracking for Constraint-based HMMs, Gaussian Filtering for Hybrid HMMs (K-Best and Rao-Blackwell Particle Filtering) | |
| 18 | Particle Filters and their Applications (Student Presenters: Kaijen Hsiao, Jason Miller, and Henry Lefebvre de Plinval-Salgues) Particle Filters in SLAM in Fault Diagnosis | Verma, Vandi, Geoff Gordon, Reid Simmons, and Sebastian Thrun. "Particle Filters for Rover Fault Diagnosis." IEEE Robotics and Automation Magazine special issue on Human Centered Robotics and Dependability. June 2004. (PDF) Thrun, Sebastian. "A Probabilistic Online Mapping Algorithm for Teams of Mobile Robots." International Journal of Robotics Research 20 (2001). (PDF) Montemerlo, Michael, Sebastian Thrun, Daphne Koller, and Ben Wegbreit. "FastSLAM: A Factored Solution to the Simultaneous Localization and Mapping Problem." Proceedings of the AAAI National Conference on Artificial Intelligence, 2002. Stachniss, Cyrill, Giorgio Grisetti, and Wolfram Burgard. "Recovering Particle Diversity in a Rao-Blackwellized Particle Filter for SLAM After Actively Closing Loops." Proceedings of the IEEE International Conference on Robotics and Automation, 2005. (PDF) Thrun, Sebastian, John Langford, and Vandi Verma. "Risk Sensitive Particle Filters." Proceedings of Neural Information Processing Systems (NIPS), December, 2001. Dearden, Richard, Frank Hutter, Reid Simmons, Sebastian Thrun, Vandi Verma, and Thomas Willeke. "Real-time Fault Detection and Situational Awareness for Rovers: Report on the Mars Technology Program Task." To appear in the Proceedings of IEEE Aerospace Conference, March 2004. (PDF) |
| 19 | Hello Computer? (Student Presenters: Shuonan Dong, Shen Qu, and Thomas Coffee) SharedPlan, Plan Recognition, and COLLAGEN | Blaylock, Nate, and James Allen. "Statistical goal parameter recognition." 14th International Conference on Automated Planning and Scheduling (ICAPS'04). British Columbia, Whistler. June 3-7, 2004. ———. "Corpus-based, statistical goal recognition." Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence (IJCAI-2003). Acapulco, Mexico, August 9-15, 2003, pp. 1303-1308. Rich, C., C. L. Sidner. "COLLAGEN: A Collaboration Manager for Software Interface Agents." An International Journal: User Modeling and User-Adapted Interaction 8, no. 3/4 (1998): 315-350. (PDF) Lesh, N., C. Rich, Charles, and C. Sidner. "Using Plan Recognition in Human-Computer Collaboration." In Proceedings of the Seventh Int Conf on User Modelling. Banff, Canada, July 1999. (PDF) Grosz, Barbara, and Sarit Kraus. "The Evolution of SharedPlans." In Foundations and Theories of Rational Agencies. Edited by A. Rao and M. Wooldridge. New York, NY: Springer, 1999, pp. 227-262. ISBN: 0792356012. (PDF) |
| 20 | Advanced Topics in Bayesian Networks (Student Presenters: Tom Temple, Ethan Howe, and James Lenfestey) Dynamic Bayes Networks, Exact Inference, Approximate Inference (PF), Learning, Probabilistic Relational Models, Parameter/Structure Estimation | Ghahramani, Z. "Learning Dynamic Bayesian Networks." In Adaptive Processing of Sequences and Data Structures. Edited by C. L. Giles and M. Gori. Lecture Notes in Artificial Intelligence. Berlin, Germany: Springer-Verlag, pp. 168-197. ISBN: 3540643419. Friedman, Nir, Lise Getoor, Daphne Koller, Avi Pfeffer. Learning Probabilistic Relational Models. 14th International Joint Conference on Artificial Intelligence. Montreal, Canada, August 1995. Russell, Stuart, and Peter Norvig. "Intro to Bayesian networks. Probabilistic inference. PRM primer." and "Temporal Bayesian models. HMMs and DBNs." Chapter 14 and 15 in Artifical Intelligence, A Modern Approach. New York, NY: Prentice Hall, 2002. ISBN: 0137903952.Myers, James, Kathryn Laskey, and Tod Levitt. "Learning Bayesian Networks from Incomplete Data with Stochastic Search Algorithms." Fifteenth Conference on Uncertainty in Artificial Intelligence, 1999. (PDF) Sanghai, Sumit, Pedro Domingos, and Daniel Weld. "Dynamic Probabilistic Relational Models." 18th International Joint Conference on Artificial Intelligence. Acapulco, Mexico, August 2003. (PDF) Zweig, G., and S. Russell. "Speech Recognition with Dynamic Bayesian Networks." In Proceedings of the AAAI-98. Madison, Wisconsin: AAAI Press, 1998. ISBN: 0262510987. |
| Sensing and Manipulating at the Cognitive Level | ||
| 21 | Visual Interpretation using Probabilistic Grammars (Guest: Paul Robertson) Statistical Parsing, Image Segmentation, Monte Carlo Methods, Language Learning | |
| 22 | Safe Execution of Bipedal Walking Tasks (Guest: Andreas Hoffman) Motivation and Requirements, Bipedal Balance Control Strategies, Common Control Approaches (and their Failings), Task-level Control using Model-based Executives, Whole-body Control | Hofmann, A. G., M. B. Popovic, and H. M. Herr. "A Sliding Controller for Bipedal Balancing Using Integrated Movement of Contact and Non-Contact Limbs." Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS04). Sendai, Japan. ———. "Angular Momentum Regulation During Human Walking." International Conference on Robotics and Automation, 2004. |
| Human - Robot Interaction | ||
| 23 | Working with and Learning from Humans as Partners (Guest: Cynthia Breazeal) Multi-modal Communication, Human-robot Teamwork, Socially Guided Learning | Lockerd, A., and C. Breazeal. "Tutelage and Socially Guided Robot Learning." Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS04). Sendai, Japan, 2004. Breazeal, C., A. Brooks, D. Chilongo, J. Gray, G. Hoffman, C. Kidd, H. Lee, J. Lieberman, and A. Lockerd. "Working Collaboratively with Humanoid Robots." Proceedings of Humanoids, Los Angeles, CA, 2004. |
| 24 | Nursebot: Dialogue as a Decision Making Process (Guest: Nick Roy) Model-based Dialog Management, Hierarchical Planning under Uncertainty, Reinforcement Learning for Human Interaction | Pineau, J., M. Montemerlo, M. Pollack, N. Roy, and S. Thrun. "Towards robotic assistants in nursing homes: challenges and results." Robotics and Autonomous Systems 42, no. 3-4 (March 31, 2003): 271-281. Singh, Satinder, Diane Litman, Michael Kearns, and Marilyn Walker. "Optimizing Dialogue Management with Reinforcement Learning: Experiments with the NJFun System." Journal of Artificial Intelligence Research (JAIR) 16 (2002): 105-133. (PDF) |
| 25 | Project Demonstrations | |
| 26 | Project Demonstrations (cont.) | |
Table of Contents
Study Materials
Readings
| When you click the Amazon logo to the left of any citation and purchase the book (or other media) from Amazon.com, MIT OpenCourseWare will receive up to 10% of this purchase and any other purchases you make during that visit. This will not increase the cost of your purchase. Links provided are to the US Amazon site, but you can also support OCW through Amazon sites in other regions. Learn more. |
The readings from the class are provided in the table below, along with the following list of supplemental readings, which are recent papers in cognitive robotics recommended by many of the key researchers in the field. (PDF)