Jump to: Course DescriptionTextbooksLecture and Recitation ScheduleAssignmentsScribingGradingLaTeX

Instructor

Kostas Bekris
Office Hours: Tuesday and Friday 10:30am – 11:30am @ Hill 277
Email: kostas.bekris/AT/cs.rutgers.edu

Lectures:
Tuesday, 12:00 PM – 1:20 PM @ SEC-118, Busch Campus
Friday, 12:00 PM – 1:20 PM @ SEC-118, Busch Campus

Teaching Assistants

Aravind Sivaramakrishnan
Office Hours: Wednesday 1:30pm – 3:30pm @ Hill 412
Email: comprobfall2018/AT/gmail.com

Guangzhi Tang
Office Hours: Tuesday 4:00pm – 6:0pm @ CBIM office 5
Email: comprobfall2018/AT/gmail.com

Rui Wang
Office Hours: Thursday 1:00pm – 3:00pm @ Hill 412
Email: comprobfall2018/AT/gmail.com

Recitations:
Section 1 – Friday 8:55 AM – 9:50 AM @ SEC-211, Busch Campus (Aravind)
Section 2 – Friday 10:35 AM – 11:30 AM @ SEC-206, Busch Campus (Aravind)
Section 3 – Thursday 8:55 AM – 9:50 AM @ SEC-220, Busch Campus (Rui)
Section 4 – Thursday 10:35 AM – 11:30 AM @ SEC-206, Busch Campus (Rui)

Grader

Rajanya Dhar
No office hours held
Email: comprobfall2018/AT/gmail.com

Online Information

The CS460/560 webpage will contain updated syllabus information as the semester progresses and a calendar of lectures and topics covered. Homework and project announcements, practice questions for exams and similar information will be available on the Sakai website of the course.

Course Description

This course provides a general introduction to robotics from a computational perspective with a focus on mobile robots. This includes the use of popular software for interacting with and simulating robots, such as the Robot Operating System (ROS). It will provide a view of robots as autonomous agents with a mechanical embodiment, which must observe and act upon their surroundings through the iterative execution of a sensing-planning-actuation loop. On the sensing and perception side, the course will cover state estimation challenges, such as robot localization, simultaneous localization and mapping (SLAM), as well as Bayesian solutions to these problems, such as Kalman and particle filters. For planning and decision making purposes, the course will introduce basic planning and replanning methods, such as A* and D*-like algorithms, the configuration space abstraction, sampling-based planners, and a toolbox of algorithms that solve problems by utilizing these principles. Extensions to multi-robot systems, online planning and handling uncertainty will be touched upon as well. On the control side, the course will offer an introductory coverage of robot kinematics and dynamics.

Prerequisite

CS 206 – Introduction to Discrete Structures II

Source Material

This course does not require the purchase of textbooks. It will draw upon material from multiple textbooks.

  • Principles of Robot Motion: Theory, Algorithms, and Implementations (PRM)
    by Howie Choset, Kevin M. Lynch, Seth Hutchinson, George A. Kantor, Wolfram Burgard, Lydia E. Kavraki, Sebastian Thrun
  • Probabilistic Robotics [ProRob]
    by Sebastian Thrun, Wolfram Burgard and Dieter Fox
  • Introduction to Autonomous Mobile Robots [IAMR]
    by Roland Siegwart, Illah Reza Nourbakhsh and Davide Scaramuzza
  • Planning Algorithms (PA) [book download]
    by Steve LaValle
  • AI: A Modern Approach (AIAMA)
    by Stuart Russell and Peter Norvig
  • Computational Geometry: Algorithms and Applications (CGAA)
    by Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars
  • Modern Robotics: Mechanics, Planning, and Control (MR) [book download]
    by Kevin M Lynch and Frank C. Park

When necessary, information will be provided on how to acquire legal digital copies of reference textbook material related to the sources above. Only portions of the above books will be used.

Schedule of CS460/560 - Fall 2018

DateLecture TopicReading
Final Exam - Dec. 20 8am - 11am
T 9/40. Syllabus & Introduction
F 9/71. Path Planning over Grids: Discrete search AIAMA Ch. 3.4, 3.5
T 9/112. Combinatorial Planners: Visibility Graph, Generalized Voronoi Diagram and Trapezoidal DecompositionPRM 5.1, 5.2, 6.1 - PA 6.2 - CGAA 15.1, 15.2, 13.2
F 9/143. Robots with Geometry: the Configuration Space AbstractionPRM 3 - PA 4
T 9/184. Sampling-based Motion PlanningPRM 3 & 7.1
F 9/215. Sampling-based Motion Planning & Potential FunctionsPRM 7.1, 7.2 & 7.4, PRM Ch. 4
T 9/256. Trajectory Planning for Fully Actuated Systems: Decoupled case & Trajectory OptimizationPRM 11.2, 11.3
F 9/287. Wheel Kinematics, Non-holonomic Constraints and Underactuated SystemsPRM 12, IAMR 2.3 & 3
T 10/28. Controllability and Maneuverability (TA)PRM 12, IAMR 2.3 & 3
F 10/5Test 1 on Path Planning Foundations
T 10/99. Types of Sensors, Representing UncertaintyIAMR 4
F 10/1210. Basic Concepts in Probability & Bayesian ReasoningProRob 2
T 10/1611. Kalman FilteringProRob 3.1-3.3, PRM 8
F 10/1912. Particle Filtering (TA)ProRob 4.1-4.3,
T 10/2313. Mobile Robot LocalizationProRob 5-8, PRM 9.1
F 10/2614. Mobile Robot LocalizationProRob 5-8, PRM 9.1
T 10/3015. Mapping (TA)ProRob 9, PRM 9.2
F 11/216. Simultaneous Localization & MappingProRob 10, PRM 9.2
T 11/6Test 2 on Sensing & State Estimation
F 11/917. Dealing with Partial Observability & Time Varying Problems: Anytime Path Planning and ReplanningResearch papers, PA 7
T 11/1318. Dealing with Uncertain Actions: Intro to Markov Decision ProcessesProRob 14
F 11/1619. Markov Decision Processes (TA)ProRob 14, PA 10
W 11/2120. Partially Observable Markov Decision ProcessesProRob 15, PA 11
T 11/27Invited Lecture: Prof. Peter Allen from Columbia University
F 11/3021. Approximate Partially Observable Markov Decision ProcessesProRob 16, PA 11
T 12/422. Extension I: Multi-robot ProblemsPA 7, PRM 7.5
F 12/723. Extension II: Robotic Arms & Manipulation PlanningPA 7, PRM 7.5
T 12/11Review for Final Exam (TAs)

Recitations - CS 460/560 Fall 2018

DateTopic
09/6-7Installation Guide for ROS and Gazebo
09/13-14Software Infrastructure for Assignment 1: Loading a Turtlebot and Discretizing Control Space
09/20-21Hints for Implementing A* and a Combinatorial Planner
09/27-28Software Infrastructure for Assignment 2: Collision checking and nearest neighbor search
10/4-5TAs available for questions related to the Midterm 1
10/11-12Hints for Implementing a Sampling-based Motion Planner
10/18-19Review of Probabilistic & Bayesian Reasoning
10/25-26Software Infrastructure for Assignment 3: Receiving Sensing Input from Gazebo
11/1-2TAs available for questions related to the Midterm 2
11/8-9Hints for Bayesian filter implementation
11/15-16Hints for Map representations
11/20-21Software Infrastructure for Assignment 4: Loading Transition Model and Defining Robust Policy
11/29-30Hints for value/policy iteration implementation
12/6-7Review of material for final

Exams

There will be 3 exams, two midterms and one final:

  • The first exam will cover material on path planning corresponding to the first component of the course (Lectures 1 to 7 or 8),
  • The second exam will cover material on perception and state estimation corresponding to the second component of the course (Lectures 8 or 9 to 15 or 16),
  • while the final exam will cover the entire material of the course

Students following CS560 will have to answer one or two additional questions in each exam relative to students following CS460 in order to be awarded a perfect grade.

The tentative schedule on the course website indicates the planned date of the midterms. All exams are in-class exams. A missed exam draws zero credit. Emergencies will be considered upon submitting a University-issued written verification to the Instructor; for assistance contact your Dean’s Office. Also, check the definition of Final Exam Conflicts by SAS and Rutgers.

Assignments

There will be multiple assignments (either 4 or 5). You will be informed in advance when an assignment is due. Typically, each assignment will include opportunities for extra credit for CS460. Some of these extra credit problems will be required for students taking CS560.

The assignments will primarily involve programming robot planning and perception algorithms and evaluating their efficiency in simulation. Typically you will be asked to submit an electronic version of your code, test runs, a typeset report and demo your project to the teaching assistants. The assignments may also include practice theoretical questions which are intended to assist the student in mastering the course content.

Assignments should be completed by teams of students – three at most for CS460 students and at most two for CS560 (please do not mix teams between the two groups). No additional credit will be given for students that complete a homework individually or CS460 students that complete an assignment as a pair.

Please inform the TAs about the members of your team as soon as an assignment is announced. Students can switch teams between assignments but they are not required to do so. The students need to inform the TAs about their team membership.

Students will receive 10% extra credit if they typeset (in LaTeX) or 5% extra credit if they typewrite their answers e.g., if a team was to receive a score of 62/100 and they provide a typesetted homework, then their score will be 68/100, i.e,. +10% of 62 points. Resources on how to use LaTeX are available on the course’s website.

Tentative Schedule for Assignments

  1. September 11 – September 28: Path planning for a holonomic, disk robot (A* search and visibility graph)
  2. October 2 – October 19: Path planning for a rigid body and a car-like system (Sampling-based Motion Planning: PRM and RRT)
  3. October 23 – November 16: Localization and Mapping using noisy sensors for a holonomic robot
  4. November 20 – December 7: Robust Policy for a holonomic robot with noisy actuation

Software Platform for Assignments

The programming assignments will be developed on two key software packages in robotics:

  • Robot Operating System (ROS): A robotics middleware (i.e. collection of software frameworks for robot software development). ROS is not an actual operating system. It provides services designed for a heterogeneous computer setup, such as hardware abstraction, low-level device control, implementation of commonly used functionality, message-passing between processes, and package management. We will primarily use it as a message-passing system.
  • Gazebo robot simulation: Gazebo includes a robust physics engine, high-quality graphics, and convenient programmatic and graphical interfaces. Simulation is an essential tool for a roboticist as it allows to rapidly test algorithms, design robots, perform regression testing, and train AI systems in realistic scenarios. Gazebo offers the ability to accurately and efficiently simulate populations of robots in complex indoor and outdoor environments. Gazebo is compatible with the ROS message-passing infrastructure.

Useful links regarding ROS and Gazebo:

Assignment Submission Rules

No late submission is allowed. If you don’t submit an assignment on time, you get 0 points for that assignment. Students can submit their assignments electronically via Sakai. Programming results must be demonstrated during pre-scheduled demo appointments. The project report must be forwarded in advance of the demo.

Scribing

As there is no single textbook that covers the material of this course, students are encouraged to participate in an optional note scribing activity for extra credit (regardless if they are CS460 or CS560 students). In particular, each class up to 3 students will be the designated as “scribes”, who must take careful notes during class, typeset them in LaTeX, and forward them to the TAs and the instructor for posting them on Sakai.

This is the process to follow:

  • If you have been designated as a scribe for the lecture, take careful notes.
  • Get together with your teammates within 2 days of the lecture and prepare your notes into a report. The report should be written out in complete prose sentences that would be understandable even by a student who might have missed class, not merely a transcription of the telegraphic notes that you jotted down during class.
  • Feel free to utilize any material from the slides that you have find useful, such as figures. Do not include administrative information (such as due dates for assignments) in your scribe notes. Feel free to contact the TAs or the instructor if you have questions about the material covered.
  • Prepare the notes into a LaTeX document, including figures, where appropriate, using the template provided. If you are new to LaTeX, check the information on the course’s website.
  • Email the TAs both the source files (including figures) and the final PDF of your scribe notes before the next lecture for which you were scribing.
  • The TAs will make a (very) quick pass and post the scribe notes on Sakai, marked as a “draft” to indicate that they have not been reviewed.
  • In many cases, we may request revisions to the notes and you will be asked to forward an updated version.
  • There will be a binary grading for scribing: satisfactory or unsatisfactory. In the first case, the draft notes will be posted and the team will receive full credit for them.

In order to serve as a scribe, you can indicate your interest and availability to the TAs. If no one has signed up ahead of a lecture, the instructor may request for volunteers at the beginning of a class.

Grading System

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

  • Assignments: 50 points total (approx. 8 to 12 points each depending on difficulty)
  • Midterms and Exam: 50 points (12.5 points for each midterm and 25 for the final)
  • Scribing: 5 bonus points per lecture (if the notes are graded as “satisfactory”)
  • Participation: up to 5 bonus points (this is up to the discretion of the instructors and the TAs)

By default your participation grade is 0, i.e., if you frequently come to the lectures/recitations but you rarely answer questions during the lectures or the recitations, your participation grade will be 0. Positive participation grades will be given to students that actively participate in lectures and recitations.

The mapping of scores to letter grades will be determined at the end of the semester. As a rough guide, the following rule may be used for the final grade (it will be adapted close to the end of the semester):

  • A: > 89
  • B+: 80-89
  • B: 70-79
  • C+: 60-69
  • C: 50-59
  • D: 40-49
  • F: less than 40

Students interested in a recommendation letter by the instructor will be offered one only if they achieve a score above 95 after the completion of the course.

Learning Goals

The objective is for students at the conclusion of the course to have a good understanding of the classical computational tools employed in robotics research and applications that relate to perception, decision making and control. On the perception side, students will be able to identify proper models for robot localization tasks and put together implementations that realize these models. For planning, students will be able to build geometric models of simple motion planning problems for mobile robots and apply deterministic and sampling-based search algorithms to solve them. Lastly, students will experience tools relating to simulation of mobile robots and middleware for interactive with robots. In addition, students should have an understanding on how these general algorithmic frameworks can lead to solutions of more complex problems involving flying machines, human-robot interaction, mobile manipulators, and multi-robot systems.

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.

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