CS 673 - Computing Motion: Search, Planning, Control and Learning

Download the course Syllabus.

Description

Computing motion in an automated way is useful in many application domains, including robotics, manufacturing, medical devices, transportation challenges, cyber-physical systems, mobile computing, mobile sensor networks, computer simulation and animation, as well as computer games.

Given the importance of this problem, many different research communities have approached it from different perspectives and have proposed alternative methodologies for addressing such challenges. Examples include heuristic search, algorithmic motion planning, optimal control and reinforcement learning. Due to both technological and algorithmic progress, these fields, which were rather distinct in the past, are presently on a collision course. The focal point of this intersection is the development of efficient algorithms for computing motion in an automated and efficient way.

In robotics, the problem originally involved moving a free flying rigid body without collisions (e.g., think of moving a piano from one room to another in a house without hitting the walls). The field has grown, however, to include complications such as uncertainty, multiple bodies, and dynamics. In AI, planning originally meant a search for a sequence of actions that transform an initial state into a desired goal state, which can often be approached by heuristic search methods. Presently, planning extends beyond this to include many decision-theoretic ideas such as Markov Decision Processes, imperfect state information, and game-theory. Furthermore, reinforcement learning is increasingly gaining ground as the way to address challenges where the underlying model of the moving system is uncertain or inaccurate. Although control theory has traditionally been concerned with issues such as stability, feedback, and optimality, there has been growing interest in designing algorithms that find feasible open-loop trajectories for non-linear systems. In computer graphics the problem of physically realistic simulation of mechanisms is of increasing importance.

This course will aim to cover a variety of methods for computing motions that have been developed in the four research areas of discrete and heuristic search, algorithmic motion planning, optimal control and reinforcement learning. Emphasis will be given to problems that involve high-dimensional systems, such as manipulators, multi-agent systems, such as networks of moving systems, or systems with significant dynamics, such as flying or walking systems.

In particular, the course will be split into the following four modules:

  1. Discrete and Heuristic Search
    • Review of standard search-based methods
    • Applications in navigation and manipulation challenges
    • Recomputing paths given dynamic changes
  2. Algorithmic Motion Planning
    • Combinatorial solvers and potential functions
    • Sampling-based motion planners
    • Generalizations of the basic motion planning problem
  3. Dealing with Dynamics - Optimal Control
    • Optimal analytical control
    • (Iterative) Linear quadratic regulator (LQR), partial feedback linearization
    • Dynamic programming foundations, value iteration and policy search
    • Stochastic optimal control
  4. Reinforcement Learning
    • Stochastic gradient descent
    • Temporal difference learning
    • Function approximation
    • Policy improvement

Tentative Calendar

Check Rutgers' Key Dates.

  • Lecture 1 - Sept. 4: Motivation, examples, applications, high-level planning concepts, feasible and optimal planning

  • Lecture 2 - Sept. 9: Discrete Search: Uninformed and Informed Optimal Search (A*), Variants of A*
  • Lecture 3 - Sept. 11: Roadmaps and Combinatorial Planners: Visibility graph, Generalized Voronoi Diagram and Trapezoidal Decomposition

  • Lecture 4 - Sept. 16: Sampling-based Motion Planning: Roadmap and Tree-based approaches, Probabilistic Completeness and Asymptotic Optimality (first project deliverable due)
  • Lecture 5 - Sept. 18: Optimal Control: Definition of Optimal Control Problems, Bang-bang control for the double integrator, Pontryagin's Minimum Principle (quiz for lectures 2-4)
  • Lecture 6 - Sept. 20: The Reinforcement Learning Problem, The Markov Property, Markov Decision Processes, Value Functions

  • Lecture 7 - Sept. 23: Configuration Space Abstraction I: Dimensionality, Topology, Manifolds and their embeddings, Parametrizations (quiz for lectures 5-6)
  • Lecture 8 - Sept. 25: Configuration Space Abstraction II: Dimensionality, Topology, Manifolds and their embeddings, Parametrizations

  • Lecture 9 - Sept. 30: Configuration Space Abstraction III: Dimensionality, Topology, Manifolds and their embeddings, Parametrizations
  • Lecture 10 - Oct. 2: Piano Mover's Problem: Application of Sampling-based Motion Planning Methods to Rigid Body Motion Planning (quiz for lectures 7-8-9)
  • Lecture 11 - Oct. 4: Time varying problems, Dynamic obstacles, Velocity tuning, Coverage planning, Multi-robot and assembly planning (second project deliverable due)

  • Lecture 12 - Oct. 7: Multi-robot planning, Assembly planning, Fixed path and roadmap coordination, Pareto Optimality
  • Lecture 13 - Oct. 9: Replanning, Incremental and Anytime A* Searches (D* Lite, Anytime Dynamic A*), Anytime RRT*

  • Lecture 14 - Oct. 14: Hybrid systems, Manipulation planning, Closed chains, Protein folding, Unknotting (quiz for lectures 10-11-12-13)
  • Lecture 15 - Oct. 16: Forward and Inverse Kinematics, Velocity Kinematics, The Jacobian Matrix, Singularities (third project deliverable due)

  • Lecture 16 - Oct. 21: Feedback Motion Planning: Potential and Navigation Functions, Planning via Vector Fields, Nominal Trajectories vs. Feedback and Policies
  • Lecture 17 - Oct. 23: Policy Evaluation, Policy Improvement, Policy Iteration, Value Iteration, Asynchronous Dynamic Programming (quiz for lectures 14-15-16)

  • Oct. 28: No lecture
  • Lecture 18 - Oct. 30: Dynamic Programming in Control, Linear Quadratic Regulators (LQR) and Hamilton-Jacobi-Bellman equation (fourth project deliverable due)

  • No lectures during the week of Nov. 4-8.

  • Lecture 19 - Nov. 13: Equations of motion for a 2-link arm, Feedback Linearization, General Expression for Manipulators with dynamics (quiz for lectures 17-18)
  • Nov. 15 (fifth project deliverable due)

  • Invited Lecture - Nov. 18: Talk by Visitor, Dr. Ani Hsieh from Drexel University
  • Lecture 20 - Nov. 20: Trajectory Planning: Decoupled (Optimal Time Scaling) and Direct (Grid-based Search, Optimization)

  • Lecture 21 - Nov. 25: Nonholonomic and Underactuated Systems, Unicycle example, Lie Algebras, Controllability (quiz for lectures 19-20 & Invited lecture)
  • Lecture 22 - Nov. 27: Lie Algebras and Controllability

  • Lecture 23 - Dec. 2: Acrobot and Cart-Pole Examples, Partial Feedback Linearization (quiz for lectures 21-22)
  • Lecture 24 - Dec. 4: Trajectory Optimization via Policy Search (sixth project deliverable due)

  • Lecture 25 - Dec. 9: Linear Time-Varying LQR, Iterative Differential Dynamic Programming, Feedback Motion Planning with LQR trees(quiz for lectures 23-24)

  • Lecture 26 - Dec. 11: Stochastic Optimal Control, Linear Quadratic Regulator with Gaussian Noise (LQG), Planning under Uncertainty

  • Exam period:
    Dec 16: (quiz for lectures 25-26)
    or 3hr exam over entire material for those who want to replace their project with a final exam
    Dec. 18: (final project presentation)
    Dec. 19: (final project report)

Text and Reading Material

No textbook is required. Students are expected to take notes during the lectures and study them. Regular attendance is highly recommended. If you miss a lecture, you are responsible for all material covered or assigned in class.

The class will draw upon material that is covered by the following books:

  • "Principles of Robot Motion: Theory, Algorithms, and Implementations" by H. Choset, K. M. Lynch, S. Hutchinson, G. Kantor, W. Burgard, L. E. Kavraki and S. Thrun; MIT Press, Boston, 2005.
  • "Planning Algorithms" by Steve LaValle; Cambridge University Press, 2006 (Available Online).
  • "Dynamic Programming and Optimal Control", by Dimitri P. Bertsekas; Athena Scientific, 3rd ed. Vols. I and II, 2007.
  • "Reinforcement Learning: An Introduction" by Richard S. Sutton and Andrew G. Barto; MIT Press, Cambridge, MA, 1998.
  • "Heuristic Search: Theory and Applications" by Stefan Edelkamp, Stefan Schroedl; Morgan Kaufmann. 1 edition, 2011.
  • "Robot Modeling and Control" by Mark W. Spong, Seth Hutchinson, M. Vidyasagar; Wiley, 1st edition, November 18, 2005.

Deliverable

Each student will work on an individual semester-long project corresponding to half of the course's grade. Students are encouraged to identify topics that are related to their research efforts. Nevertheless, the project must also be related to the course material (i.e., computing motion).

In-class short quizzes reviewing material covered in class will be frequently taking place. These will be in the order of 10 to 15 minutes long in duration. They will often contain multiple choice questions or questions that can be briefly answered in a couple of lines. There are expected to be about 10 quizzes during the entire semester. The grade from the best 8 of these quizzes for each student will be used towards the final grade.

Students will also be evaluated based on the level of their participation and performance during the lectures, which primarily involves answering questions during the lecture.

Semester-Long Project

For the project, the students will be asked to work during the entire semester by preparing and frequently submitting intermediate reports and demos during the semester. A final project presentation and demo will take place during the exam week in front of the entire class. The objective of the project is to result in a final report that will be equivalent in quality to a paper ready for submission to an academic conference. The presentation should also be equivalent to a conference presentation and accompanied by a working demo. Each student will work on a separate project. The topic should be decided after coordinating with the instructor.

The students need to submit typesetted reports using LaTeX. Resources on using LaTeX are available below. You are expected to use IEEE RAS' double column format for conferences.

The following project components and deadlines for submissions will be used to guide your work during the entire
semester:

  1. September 16: Project Proposal
    • Provide a short abstract for the project
    • Then in more detail describe the general topic, provide motivation for the work and application area, emphasize the significance and the difficulty of the challenge, highlight the state-of-the-art and the main idea behind the approach you are considering, justify why your project will be novel
    • 2 to 3 pages, corresponding to the Abstract and Introduction sections of the final report
  2. September 30: Literature Search
    • Improve upon the Introduction section given better knowledge of the related literature and feedback from the instructor
    • Provide a comprehensive coverage of the related literature on the topic, make sure to cover efforts from different research communities and perspectives, do not just describe related work but try to point out the similarities and differences between existing efforts, identify key contributions in the field as well as limitations of existing work, conclude with the set of open-problems given the state-of-the-art, specify which of the existing contributions your project will be building upon and which open problems it will be addressing
    • 2 to 3 pages, corresponding to the Related Work section of the final report, references are excluded from the page count
  3. October 14: Problem Setup, Experimental Setup and Infrastructure
    • Improve upon your assessment of the related literature given initial experimentation and feedback from the instructor
    • Work on providing the software/hardware platform that you will employ for your work, describe the experimental setup for your evaluation, demonstrate to the instructor the capability to run experiments or simulations on the proposed research topic using naive solutions (even if your project is more theoretical in nature, you need to provide some form of simulation that evaluates or confirms your analysis)
    • 1 to 2 pages, corresponding to the Problem and Experimental Setup sections of the final report
  4. October 28: Algorithmic Methodology and Mathematical Foundations
    • Improve upon your experimental platform given implementation of methods and evaluation, as well as feedback from the instructor
    • Describe in detail the novel algorithmic or mathematical process that you are proposing in order to address the project's challenge, start from the foundations of the solution in existing work and progress in emphasizing the new aspects of the approach, provide an initial implementation of the corresponding solution on the experimental platform that you have available and perform initial evaluation - no need to describe data at this point but you should be getting initial indications on how the method is performing
    • 2 to 4 pages, corresponding to the Proposed Methodology sections of the final report
  5. November 11: Analysis of Properties and Comparison Solutions
    • Improve upon the algorithmic solution given the observed experimental performance and analysis of the solution's properties - notice that no feedback will be provided on the previous report and you need to show the capability of improving upon your proposed solution given additional study and experimentation
    • Evaluate the properties of the proposed methodology (e.g., in terms of metrics such as safety, completeness, optimality, computational performance and complexity, scalability, information requirements, etc.), theoretical and mathematically study of the underlying properties is highly encouraged if it makes sense for the project, describe alternative methodologies that need to be evaluated in order to show the relative performance of the proposed approach, provide initial implementations of the alternative methodologies and initial evaluations
    • 2 to 4 pages, corresponding to the Properties and/or Comparison Solutions sections of the final report - note that more theoretical projects will be focusing more on ``properties'', while more experimental ones will be focusing more on evaluating performance against ``comparison solutions''
  6. November 25: Experimental Evaluation
    • Improve upon the analysis of the proposed method, as well as better identify appropriate comparison points given additional study, experimentation and feedback from the instructor
    • Perform a comprehensive experimental evaluation of the proposed methodology in appropriate benchmarks that you have identified and described in detail, the evaluation will include running experiments with competitive methods and providing the corresponding graphs that show the differences between the performance of different algorithms, study experimentally the performance of the studied methods in terms of the appropriate metrics (e.g., safety, completeness, optimality, computational performance and complexity, scalability, information requirements, etc.)
    • 2 to 5 pages, corresponding to the Results section of the final report, even theoretical projects need to evaluate methods using some form of simulation
  7. December 16: Final Report and Presentation - Discussion of Performance, Improvement of Methodology and Revisions
    • Improve upon the experimental evaluation given a study of the resulting graphs and feedback from the instructor
    • Provide a detailed discussion of the observations during the experimental evaluation, based on your conclusions, revise and improve the proposed methodology, run additional experiments and show potential improvements against alternatives or versus prior performance, study in terms of theoretical properties the effects of your revisions in the underlying algorithm, update the introductory part of the paper given observations and the potentially shifted focus of the project, prepare the reader of the report about the
      actual contribution of the project and identify the important future steps
    • 2 to 3 pages, corresponding to the Discussion section of the final report, as well as revisions and extensions in the entire paper given observations, further study and changes in the underlying methods - at this point you should have an initial version of the complete report ranging between 13 to 24 pages excluding references.
    • Improve upon the entire paper and tighten up description. The final report will no longer need to describe
      in detail the process with which you ended up in the best performing solution (i.e., the initial approach you were considering and how you ended up improving upon it). It needs to directly inform the reader about the final contribution and observations that will be the result of your entire effort. It still important, however, to provide key comparisons with alternatives in your experimental setup and justify the algorithmic choices made in the final solution.

Submissions will be processed through Sakai. Late project report will not be accepted. Final project presentations cannot be easily rescheduled. Unless there are unprecedented circumstances, no incomplete grade will be awarded and students will be graded based on the submitted reports and presentations up to the exam week.

Extra credit can be awarded for impressive effort and performance in the project. Such projects would correspond to reports and demos that can be easily submitted to an academic conference.

Grading System

The final grade will be computed according to the following rule (this is tentative):

  • Project Proposal (relevance, significance, interest, novelty and level of difficulty of proposed project): 5 points
  • Literature Search (comprehensiveness, capability to classify previous work, ability to identify relations and open problems): 5 points
  • Problem and Experimental Setup (appropriateness of platform, benchmarks and capability to evaluate the correct metrics for the challenge and the methodologies): 5 points
  • Algorithmic Methodology (formal and rigorous description, appropriateness of solution, clarity of presentation, novelty of ideas): 5 points
  • Analysis of Properties (proper identification of comparison points, mathematical capabilities in analyzing proposed methods): 5 points
  • Experimental Evaluation (comprehensiveness of evaluation, study of appropriate metrics and informative presentation of data): 5 points
  • Final Report (ability to communicate message and progress the state-of-the-art, novelty, significance, difficulty, success in objectives): 10 points
  • Final Presentation/Demo (clear explanation of objectives, methods and results, ability to maintain interest, use of visual assistance, success of demonstration - feedback from all the students will be used to grade the presentation): 10 points
  • In-class quizzes (the best 8 out of 10): 40 points
  • In-class participation: 10 points

The total number of available points excluding extra credit is 100.

As a rough guide, the following rule may be used for the final grade (this is tentative):

  • A: >= 86
  • B+: 77-85
  • B: 68-76
  • C+: 59-67
  • C: 50-58
  • D: 41-49
  • F: less than 40

Academic Standards

Discussions on the class material, on project challenges and programming practices are highly encouraged. Furthermore, students should try to exchange feedback on drafts of their project reports. Nevertheless, each student needs to eventually independently develop one's proposed methodology, code the corresponding solution and execute the corresponding experiments.

Quizzes are strictly individual efforts and no collaboration is allowed.

You should carefully study the website of Rutgers University on Academic Integrity and the corresponding policy, as well as the corresponding policy from the department of Computer Science. Your continued enrollment in this course implies that you have read these policies, and that you subscribe to the principles stated therein.

Latex Resources

General info on what you can do with LaTeX:
Getting Started with Latex
The Not So Short Introduction to Latex
Comprehensive List of Latex Symbols
Latex for Logicians

Mac
Tex on Mac OS X
MacTex

The first link describes many alternatives that are available for installing Tex on a Mac. The second link forwards to the MacTex package, one of the alternatives mentioned in the first website. MaxTex provides everythink that you need to use Latex on Mac except from a text editor. It is, however, compatible with a wide variety of popular editors (e.g., Alpha, BBEdit, Emacs, VIM, iTeXMac, TeXShop). Note that MaxTex is a large package.

Carbon Emacs has been succesfully tested with MacTex. After installing MacTex, it is possible to directly compile and view *.tex files from Carbon Emacs's UI.

Note for Mac users: You will probably have problems previewing your PDF output when using the postscript images provided by the instructor for developing the notes. Nevertheless, the PDF file can be printed properly. Prepare your document without the images and then add them. You will probably still be able to preview the intermediate .dvi output file with the "xdvi" program.

Linux (Ubuntu)
Latex on Ubuntu
Tex Live

You just have to download and install the proper packages described above (e.g., through apt-get), use your favorite editor (e.g., emacs) to prepare a *.tex file and then you compile (run at least two times: "latex filename.tex") to get the *.dvi output. You can go from dvi to postscript with the command "dvips" and you can convert postscript to pdf with the command "ps2pdf".

Windows
Latex for Windows help
MikTex (Latex for Windows)

If you follow the instructions on the first link you should be able to get it working on a Windows system.

Below you can find Windows executables (32 bit) for the following programs (follow the order when installing):
MiKTeX
Ghostscript
Ghostview
WinEdt