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

#### Instructor

Kostas Bekris, Associate Professor

Office: 1 Spring street, New Brunswick, NJ, 08901 – Third floor – office #304

Office Hours: Monday 2:00pm – 3:00pm (first day: Sept. 13)/ available in person at this time slot or on Zoom:

Link for Kostas Bekris’ Office Hours

Email: kostas.bekris/AT/cs.rutgers.edu

Lectures:

Tuesday 1:00pm – 2:20pm – available online under the following Zoom link

Thursday 1:00pm – 2:20pm – available online under the following Zoom link

#### Teaching Assistant

Yinglong Miao

Office: Core 246, Busch campus

Office Hours: 3-5 pm Wednesdays

Link for Yinglong’s Office Hours

Email: ym420/AT/scarletmail.rutgers.edu

Recitations:

Section 1 – Tuesday 9:00 AM – 9:55 AM @ PH 111 – William Levine Hall – Ernest Mario School of Pharmacy on

Busch campus

Available online under the following Zoom link

Section 2 – Thursday 11:00 AM – 11:55 AM @ TIL 257 – Tillett Hall on Livingston campus

Available online under the following Zoom link

#### Grader

TBA

No office hours held

#### 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 covering AI foundations of mobile robots and robotic arms. 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 |
---|---|

T 9/2 | 0. Syllabus & Introduction |

F 9/7 | 1. Path Planning for Points/Disk Robots in Planar Setups Reading: Chapter 15 of the Computational Geometry book, Chapter 3 of the AI book, Chapter 2.2 of the Planning Algorithms book |

T 9/9 | 2. Review of Search Methods and Intro to Visibility Graphs Reading: Chapter 3 of the AI book, Chapter 2.2 of the Planning Algorithms book, Chapter 5.1 of the Principles of Robot Motion book, Chapter, Chapter 15 of the Computational Geometry book |

F 9/14 | 3. Combinatorial Planners Reading: Chapters 5.1-2-3 and 6.1 of the Principles of Robot Motion book, Chapter 15 of the Computational Geometry book |

T 9/16 | 4. Robots with Geometry: Configuration Space Abstraction Reading: Chapter 13 of the Computational Geometry book, Chapter 3 of the Principles of Robot Motion book, Chapters 3 and 4 of the Planning Algorithms Book, Chapter 2 of the Modern Robotics Book |

F 9/21 | 5. Review of C-space - Intro to Sampling-based Motion Planning Reading: Chapter 3 of the Principles of Robot Motion book, Chapter 2 of the Modern Robotics Book, Chapters 3 and 4 of the Planning Algorithms Book |

T 9/23 | 6. Sampling-based Planning Reading: Chapters 7.1 and 7.2 of the Principles of Robot Motion |

F 9/28 | 7. Sampling-based Planning II Reading: Chapters 7.1 and 7.2 of the Principles of Robot Motion - "effective_sampling_3d.pdf" under Resources/Reading Material on Sakai |

T 9/30 | 8. Properties of Sampling-based Motion Planners – Potential Functions Reading: Chapter 7.4 of the Principles of Robot Motion book - "asympt_optimal_SBMPs.pdf" under Resources/Reading Material on Sakai - Chapters 4.1-4.2-4.4-4.6 of Principles of Robot Motion book |

F 10/5 | 9. Gradient-based Approaches & Trajectory Planning Chapters 4.1-4.2-4.4-4.6 of Principles of Robot Motion book - "CHOMP_IJRR.pdf" under Resources/Reading Material on Sakai - Chapters 10.1 and 11.2 of the Principles of Robot Motion book |

T 10/7 | 10. Trajectory Planning Chapters 11.2 and 11.3 of the Principles of Robot Motion book |

F 10/12 | 11. Planning for Non-holonomic and Underactuated Systems Chapters 12.1-12.2-12.3 of the Principles of Robot Motion book |

T 10/14 | 12. Planning for Non-holonomic and Underactuated Systems 2 + Review of Path/Trajectory Planning Chapters 12.1-12.2-12.3 of the Principles of Robot Motion book |

F 10/19 | Midterm |

T 10/21 | 13. Intro to Sensing and Basic Concepts in Probability and Bayesian Reasoning |

F 10/26 | 14. Bayesian Filtering |

T 10/28 | 15. Kalman Filtering |

F 11/2 | 16. Particle Filtering |

F 11/9 | 17. Sensor Models |

T 11/11 | 18. Motion Models |

F 11/16 | 19. Intro to Simultaneous Localization and Mapping (SLAM) |

W 11/18 | 20. SLAM |

F 11/30 | 21. Least Squares for SLAM |

T 12/2 | 22. Planning under Uncertainty |

F 12/7 | 23. Highlights of Reinforcement Learning |

T 12/9 | Review for Final Exam |

#### Exams

There will be 2 online exams, one midterm and one final:

- The first exam will cover material on path planning corresponding to the first component of the course (Lectures 1 to 11),
- The second, final exam will cover material on perception and state estimation corresponding to the second component of the course (Lectures 12 to 22).

Students following CS560 will have to answer 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 midterm, which will take place during the regular lecture time. All exams are online this semester. 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, which will include a mix of homework questions and programming challenges. 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 programming 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 and a typeset report. The assignments may also include practice theoretical questions, which are intended to assist the student in mastering the course content.

Assignments should be completed individually by students.

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

#### Grading System

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

- Assignments: 50 points total (ranging from 5 to 20 points each depending on difficulty)
- Midterm and Exam: 50 points (25 for each)

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: > 90
- B+: 81-90
- B: 71-80
- C+: 61-70
- C: 51-60
- D: 41-50
- F: less than or equal to 40

Students interested in a recommendation letter by the instructor after the completion of the course 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