Jump to: Course Description – Textbooks – Lecture and Recitation Schedule – Assignments – Scribing – Grading – LaTeX

#### 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

Date | Lecture Topic | Reading |
---|---|---|

T 9/4 | 0. Syllabus & Introduction | |

F 9/7 | 1. Path Planning over Grids: Discrete search | AIAMA Ch. 3.4, 3.5 |

T 9/11 | 2. Combinatorial Planners: Visibility Graph, Generalized Voronoi Diagram and Trapezoidal Decomposition | PRM 5.1, 5.2, 6.1 - PA 6.2 - CGAA 15.1, 15.2, 13.2 |

F 9/14 | 3. Robots with Geometry: the Configuration Space Abstraction | PRM 3 - PA 4 |

T 9/18 | 4. Sampling-based Motion Planning | PRM 3 & 7.1 |

F 9/21 | 5. Sampling-based Motion Planning & Potential Functions | PRM 7.1, 7.2 & 7.4, PRM Ch. 4 |

T 9/25 | 6. Trajectory Planning for Fully Actuated Systems: Decoupled case & Trajectory Optimization | PRM 11.2, 11.3 |

F 9/28 | 7. Wheel Kinematics, Non-holonomic Constraints and Underactuated Systems | PRM 12, IAMR 2.3 & 3 |

T 10/2 | 8. Controllability and Maneuverability (TA) | PRM 12, IAMR 2.3 & 3 |

F 10/5 | Test 1 on Path Planning Foundations | |

T 10/9 | 9. Types of Sensors, Representing Uncertainty | IAMR 4 |

F 10/12 | 10. Basic Concepts in Probability & Bayesian Reasoning | ProRob 2 |

T 10/16 | 11. Kalman Filtering | ProRob 3.1-3.3, PRM 8 |

F 10/19 | 12. Particle Filtering (TA) | ProRob 4.1-4.3, |

T 10/23 | 13. Mobile Robot Localization | ProRob 5-8, PRM 9.1 |

F 10/26 | 14. Mobile Robot Localization | ProRob 5-8, PRM 9.1 |

T 10/30 | 15. Mapping (TA) | ProRob 9, PRM 9.2 |

F 11/2 | 16. Simultaneous Localization & Mapping | ProRob 10, PRM 9.2 |

T 11/6 | Test 2 on Sensing & State Estimation | |

F 11/9 | 17. Dealing with Partial Observability & Time Varying Problems: Anytime Path Planning and Replanning | Research papers, PA 7 |

T 11/13 | 18. Dealing with Uncertain Actions: Intro to Markov Decision Processes | ProRob 14 |

F 11/16 | 19. Markov Decision Processes (TA) | ProRob 14, PA 10 |

W 11/21 | 20. Partially Observable Markov Decision Processes | ProRob 15, PA 11 |

T 11/27 | Invited Lecture: Prof. Peter Allen from Columbia University | |

F 11/30 | 21. Approximate Partially Observable Markov Decision Processes | ProRob 16, PA 11 |

T 12/4 | 22. Extension I: Multi-robot Problems | PA 7, PRM 7.5 |

F 12/7 | 23. Extension II: Robotic Arms & Manipulation Planning | PA 7, PRM 7.5 |

T 12/11 | Review for Final Exam (TAs) |

## Recitations - CS 460/560 Fall 2018

Date | Topic |
---|---|

09/6-7 | Installation Guide for ROS and Gazebo |

09/13-14 | Software Infrastructure for Assignment 1: Loading a Turtlebot and Discretizing Control Space |

09/20-21 | Hints for Implementing A* and a Combinatorial Planner |

09/27-28 | Software Infrastructure for Assignment 2: Collision checking and nearest neighbor search |

10/4-5 | TAs available for questions related to the Midterm 1 |

10/11-12 | Hints for Implementing a Sampling-based Motion Planner |

10/18-19 | Review of Probabilistic & Bayesian Reasoning |

10/25-26 | Software Infrastructure for Assignment 3: Receiving Sensing Input from Gazebo |

11/1-2 | TAs available for questions related to the Midterm 2 |

11/8-9 | Hints for Bayesian filter implementation |

11/15-16 | Hints for Map representations |

11/20-21 | Software Infrastructure for Assignment 4: Loading Transition Model and Defining Robust Policy |

11/29-30 | Hints for value/policy iteration implementation |

12/6-7 | Review 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

- September 11 – September 28: Path planning for a holonomic, disk robot (A* search and visibility graph)
- October 2 – October 19: Path planning for a rigid body and a car-like system (Sampling-based Motion Planning: PRM and RRT)
- October 23 – November 16: Localization and Mapping using noisy sensors for a holonomic robot
- 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

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