CS 4649/7649: Robot Intelligence - Planning
Tue/Thur, 12:05-1:25, Van Leer C457
Fall 2014
Instructor: Sungmoon Joo
( sungmoon.joo@cc.gatech.edu smjoo@kaeri.re.kr)
Office hours: By email or appointment (Office: College of Computing Rm222).
WIKI For Group Building and Collaboration on HWs and Project: Course Wiki
Piazza for Q&A: Piazza
Summary:
This course covers the introductory material of the robot intelligence, especially from the planning perspective.
We discuss algorithms for robots and other complex systems that make intelligent decisions in high dimensional or continuous spaces of options.
Intelligent decisions take into account both present and future constraints on the system.
The course will cover methods for planning with symbolic, numerical, geometric and physical constraints.
Topics will range from classical and stochastic planning to continuous robot domains and hybrid control of dynamic systems.
Optional Readings:
Specific chapters directly relevant to the course will be posted on the website. The readings are not required but they may help you get better background and deeper understanding into the course topics. In fact, if you have time over breaks etc. these are excellent books to read to get a broad appreciation for planning as a field:
- "Artificial Intelligence: A New Synthesis," Nilsson
- "Artificial Intelligence: A Modern Approach," Russel, Norvig
- "Reinforcement Learning" Sutton, Barto
- "Principles of Robot Motion", Howie Choset et. al
- "Planning Algorithms", Steve LaValle
- "Robot Motion Planning", Jean-Claude Latombe
- "Automated Planning", Malik Ghallab, Dana S. Nay, and Paolo Traverso
- "Introduction to Robotics: Mechanics and Control", John J. Craig
Additional readings from papers will also be posted on the course website when they become relevant.
Tentative Schedule (PDFs of lecture slides will be posted during course)
Classical Planning
- Aug. 19: Introduction, Logic, Situation Calculus: [PDF]
- Aug. 21: Advantages and Disadvantages of Sit. Calculus: [PDF]
- Ch. 21-22.1 "Artificial Intelligence: A New Synthesis," Nilsson
- Ch. 7.1-7.5, 8.1-9.3, 10.1-10.3 "Artificial Intelligence: A Modern Approach," Russel, Norvig
- H. Enderton, "A Mathematical Introduction to Logic," (If you are really curious)
- Aug. 26: STRIPS, Properties of Planners: [PDF]
- Aug. 28: Approaches to Classical Planning(State Space vs. Plan Space): [PDF]
- Ch. 22.2 "Artificial Intelligence: A New Synthesis," Nilsson
- Ch. 11.1-11.3 "Artificial Intelligence: A Modern Approach," Russel, Norvig
- Daniel Weld, An introduction to least-commitment planning. Artificial I ntelligence Magazine, 27--61, Winter 1994.
- Sept. 2: Partial Order Planning, Graphplan, Modern Action Representations : [PDF]
- Ch. 11.4 "Artificial Intelligence: A Modern Approach," Russel, Norvig
- A. Blum and M. Furst, "Fast Planning Through Planning Graph Analysis", Artificial Intelligence, 90:281--300 (1997).
- GraphPlan Web Page
- Corin R. Anderson et. al. Conditional Effects in GraphPlan In Proceedings of the 4th International Conference of AI Planning Systems, 1998.
- Sept. 4: Heuristics & Search : [PDF]
- Ch. 8 "Artificial Intelligence: A New Synthesis," Nilsson
- Ch. 3 "Artificial Intelligence: A Modern Approach," Russel, Norvig
- Sept. 9: Efficient Planning, SAT-Plan & PDDL : [PDF]
- B. Bonet and H. Geffner. Planning as Heuristic Search, Artificial Intelligence, Special issue on Heuristic Search. Vol 129 (1-2) 2001.
- J. Hoffmann, FF: The Fast-Forward Planning System, AI Magazine, Volume 22, Number 3, 2001
- H. Kautz and B. Selman. Unifying SAT-based and Graph-based Planning. IJCAI 1999.
- S. Richter and B. Westphal. The LAMA Planner: Using Landmark Counting in Heuristic Search. IPC 2009.
- ICAPS (planning competition)
- PDDL tutorial
- Sept. 11: Hierarchical Planning [PDF]
- Ch. 11.2 "Artifical Intelligence: A Modern Approach," Russel, Norvig
- Sept. 16: Final Project Information Session [PDF]
- Sept. 18: Classical Planning Summary: [PDF]
Motion Planning
- Sept. 23: Motion Planning: Introduction. Reactive Strategies : [PDF]
- Sept. 25: Roadmap Planning: Visibility Graphs, Configuration Space : [PDF]
- Ch. 5.1-5.4 "Principles of Robot Motion," Choset et. al.
- Ch. 6.2.3 - 6.2.4 "Planning Algorithms," LaValle
- Some Links to Voronoi Construction:
F. Aurenhammer Voronoi diagrams: A survey of a fundamental geometric data structure ACM Computing Surveys, V.23 N.3, 1991.
D. Kirkpatrick Efficient Computation of Continuous Skeletons Symposium on Foundations of Computer Science, 1979.
- Sept. 30: Roadmap Planning - Voroni Diagram and Cell Decomposition : [PDF]
- Ch. 6 "Principles of Robot Motion," Choset et. al.
- Ch. 6.1 - 6.3 "Planning Algorithms," LaValle
- S. Koenig, M. Likhachev: D*Lite. AAAI/IAAI 2002: 476-483
- Oct.2: Potential Field and Kinematics(Ridig body coordinate transformation) : [PDF]
- O. Khatib, Real-Time Obstale Avoidane for Manipulators and Mobile Robots. IJRR 1986
- Ch. 3.2-3.4 "Planning Algorithms," LaValle
- Wiegley, Lee and Goldberg's configuration space applet
- Ch. 2-3 "Introduction to Robotics: Mechanics and Control," J. Craig
- Oct. 7: Differential Kinematics, Sampling-based, Probabilistic Roadmaps : [PDF]
- Ch. 3 "Planning Algorithms," LaValle
- Ch. 7.1 "Principles of Robot Motion," Choset et. al.
- Ch. 2-3 "Introduction to Robotics: Mechanics and Control," J. Craig
- Oct. 9: Probabilistic Roadmaps, RRT : [PDF]
- Ch. 3 "Planning Algorithms," LaValle
- Ch. 7.1 "Principles of Robot Motion," Choset et. al.
- Lin & Manocha's UNC Collision Detectors
- P. Jimenez, F. Thomas, C. Torras Collision Detection Algorithms for Motion Planning Robot Motion Planning and Control, J.P.Laumonnd Ed.
- S Trenkel, R Weller, G Zachmann, A Benchmarking suite for static collision detection algorithms Proc of the Int. Conf. Computer Graphics 2007.
- S. LaValle, J. Kuffner Randomized Kinodynamic Planning International Journal of Robotics Research, 20(5):378-400, 2001.
- Oct. 14: No Class (Fall Recess)
- Oct. 16: More Coverage of RRTs and Properties : [PDF]
- M. Stilman Task Constrained Motion Planning in Robot Joint Space IROS 2007
- T. Kunz, U. Reiser, M. Stilman, A. Verl. Real-Time Path Planning for a Robot Arm in Changing Environments . IROS 2010.
- T. Kunz, M. Stilman, Manipulation Planning with Soft Task Constraint . IROS 2012.
- M. Likachev: Search Based Planning
- L. Kavraki: Open Motion Planning Library
Uncertainty and Dynamics
- Oct. 21: Reality, MDP : [PDF]
- "Dynamic Programming and Optimal Control" D. P. Bertsekas
- How to learn a model: "Machine Learning" T. Mitchell
- Useful reference for next week: "Reinforcement Learning" Sutton, Barto
- Oct. 23: Probability Primer: [PDF]
- Oct. 28: MDP - Applications and Algorithms [PDF]
- Ch. 1,3 "Reinforcement Learning" Sutton, Barto (Introduction)
- Ch. 4 "Reinforcement Learning" Sutton, Barto (Value Iteration, Policy Iteration)
- D. Poole's Value Iteration Applet [Website]
- Oct. 30: Reinforcement Learning [PDF]
- Ch. 4 "Reinforcement Learning" Sutton, Barto (Value Iteration, Policy Iteration)
- Ch. 6 "Reinforcement Learning" Sutton, Barto (Direct Evaluation, Temporal Difference, Q-Learning)
- Nov. 4: Linear Control [PDF]
- Ch. 13.2 "Planning Algorithms," LaValle (Planning Book describes Linear Control)
- Great Book: A. Mutambara, Design and Analysis of Control Systems
- More detail: "Introduction to Robotics: Mechanics and Control," J. Craig
- Also: "A Mathematical Introduction to Robotic Manipulation," R. Murray, Z. Li & S. Sastry
- Nov. 6: Linear Optimal Regulator[PDF], Linearized Control[PDF]
- "Introduction to Robotics: Mechanics and Control," J. Craig
- Khatib, O. "Inertial Properties in Robotic Manipulation: An Object-Level Framework"
- Khatib, O. "Motion/Force Redundancy of Manipulators," Symposium on Flexible Automation
(Observe the distinction between gravity & full dynamic compensation)
- Ch. 8 "Mathematical Control Theory," E. Sontag
- Ch. 3 "Artificial Intelligence: A Modern Approach," Russel, Norvig
- Nov. 11: DP revisited [PDF], Estimation Basic [PDF]
- Ch. 8 "Mathematical Control Theory," E. Sontag
- Ch. 3 "Artificial Intelligence: A Modern Approach," Russel, Norvig
- Mayne, David H. and Jacobson, David Q. (1970). Differential dynamic programming. New York: American Elsevier Pub. Co.
- Nov. 13: Kalman Filter [PDF]
- A. D'Souza Probabilistic Derivation of the Basic Kalman Filter
- P. Maybeck. "Stochastic Models Estimation and Control V.1" Ch. 1: Introduction
- Ch. 8.1-8.2 "Principles of Robot Motion," Choset et. al.
- Nov. 18: POMDP
- Nov. 20: Guest Lecture: Manipulation & NAMO (Saul Reynolds-Haertle)
- Nov. 25: POMDP[PDF]
- L. Kaelbling, M. Littman, A. Cassandra, Planning and Acting in Partially Observable Stochastic Domains Artificial Intelligence, Volume 101, pp. 99-134, 1998.
- A. Cassandra, A Survey of POMDP Applications. Presented at the AAAI Fall Symposium, 1998.
- Tony Cassandra's POMDPs for Dummies
- Nov. 27: No Class (Thanksgiving Break)
Extending Planning and Control
- Dec. 2: Linguistic, Hybrid Planning and Control
- Dec. 4: Wrap up
Assignments and Project
- Assignment #1: Classical Planning [PDF] (Group: maximum 5 students), Due: 11:59pm Oct. 6(Extended), 2014
- Assignment #2: Motion Planning [PDF] (Group: maximum 5 students), Due: 11:59pm Nov. 11 (extended)
- Final Project
- General Information [PDF]
- IEEE LaTeX Styles and Sample Documents and Page Requirements
- Project Examples
- Schedule
- Topic Selection & Teaming: Oct. 23
- Reviewer selection: Oct. 28
- Proposal: Due 11:59pm Oct. 30. (3page-long proposal would be ideal. Max 5pages.)
- Proposal Review Report: Due 11:59pm Nov. 6 [proposal guide]
- Final Report: Due 11:59pm Dec. 5 (extended)
- Final Project Review Report & Presentation: Dec. 11th, 11:30am ~ 14:20pm, Presentation evaluation form [PDF]
Grading/Requirements:
This course has undergraduate (4649) and graduate (7649) sections. Both sections will participate in two group programming projects related to the two covered aspects of planning. The projects will be graded on algorithm implmementation, analysis and results for a total of 60% of the course grade.
- Classical Planning (30%)
- Motion Planning (30%)
In order to expose students to research in planning, the course will also have a final project that makes up 40% of the grade. This project will involve the design, implementation and validation of a planning algorithm resulting in a conference-style paper and presentation.
7649 Graduate Projects:
Graduate students will work in groups on a project that is relevant to their research goals. The instructor will support this work. Students are welcome to expand on active projects in their own research labs. Final decisions on topics will be made through discussion with the instructor.
4649 Undegraduate Reviews:
Undergraduates can take the role of reviewers for the projects. They will be exposed to research in planning and the peer-review process. Undergrads will be required to review project proposals, final projects, suggest alternative algorithms and find references that back up their claims. They will be graded based on the thoroughness of their reviews, understanding of the project topics and relevance of located references. Undergraduates are given the option to participate in the projects directly and be graded as graduate students.
Late Policy:
We will not accept late home works or final report for full credit. Submit what you have on time.