**E28: Mobile Robotics**
**ENGR 028/CPSC 082**
**Fall 2019**
**[Matt Zucker](http://swarthmore.edu/NatSci/mzucker1)**
| Lecture: | Tue/Thu 11:20-12:35PM, Singer 346 |
|-----------------|--------------------------------------------|
| Office Hours: | Wed 10:30AM-12:00PM, Singer 235 |
| Lab kickoffs: | Tue 4:00-4:15PM, Thu 1:00-1:15, Singer 224 |
| Wizard session: | Wed 7:00, Singer 222 |
This course addresses the problems of guiding robots to act
intelligently in dynamic, unpredictable environments. Major topics
will include robot design, perception, kinematics, navigation and
control, optimization and learning, and robot simulation
techniques. To demonstrate these concepts, we will examine mobile
robots, manipulators and positioning devices, and virtual
agents. Projects will focus on programming both real and simulated
robots to execute tasks and to explore and interact with their
environment.
# Requirements
**Prerequisites:** ENGR 019 or CPSC 035. MATH 027 or 028(S) is strongly
recommended.
**Skills:** In practice, I expect you to understand elementary
programming concepts, including basic loops, functions, and array
processing. You should also be familiar with the process of converting
a set of mathematical equations into a working computer program.
Familiarity with Python is useful but not necessary.
I also expect you to be comfortable with
[linear algebra concepts](http://www.swarthmore.edu/NatSci/mzucker1/linalg-reintroduction.pdf)
such as matrices, linear transformations, transposes, and inverses. We
will also be using related geometric concepts such as the dot product
and vector norms.
**Time:** I expect students to spend approximately 8 hours per
week on this class (4 classes × 8 hours per class +
[8 hours for paid student work](https://www.swarthmore.edu/student-employment/employment-faqs)
= 40 hours). Although this figure will vary from individual to
individual and week to week, you should plan to commit several hours
outside of class to homework, reading, and projects each week.
# Resources
There is no textbook for the course; however, there will be assigned
readings, and notes and pointers to external resources will be
provided by student scribes and researchers ([see below](#toc4)). This
course webpage at http://swarthmore.edu/NatSci/mzucker1/e28_f2019/
will be regularly updated with assignments, scribe notes, and reading,
so please keep aware of the materials posted here.
We will use the Piazza group at
https://piazza.com/swarthmore/fall2019/engr028cpsc082
throughout the semester to communicate course announcements and answer
questions. Please use Piazza for all course-related communications --
this allows students to see common problems and to engage in
discussions about course material.
# Assignments
Homework consisting of math, short answer questions, and small
programming exercises will be assigned roughly weekly. Less
frequently, we will have in-class quizzes, which will be announced in
advance. There will be several regularly scheduled projects involving
hands-on programming of real and simulated robots, as well as an
open-ended, self-directed final project.
Projects will be conducted in small groups, typically pairs of
students. Due to frequent scheduling conflicts with other courses,
there is no regular lab time; however, during the first week, we will
form groups and arrange times to meet for short (~15 minutes)
"kickoff" tutorials at the start of each new project. Other than those
tutorials, project work will be self-scheduled.
Grading will follow approximately the divisions shown below:
* Homework/quizzes: 45%
* Regular projects: 35%
* Final project: 15%
* Class participation: 5%
Your participation grade encompasses involvement in class discussions,
preparing thorough and readable scribe notes/researcher links, and posting
constructively on Piazza.
## Collaboration and attribution
* Feel free to collaborate with your classmates on homework; however,
you must submit your own work. Duplicating others’ assignments
verbatim (especially code!) is prohibited.
* If you do discuss homework with your classmates, I expect you to
disclose any such collaboration clearly in your submitted work. Err
on the side of caution – it’s the best way to avoid awkward
conversations about suspicious similarities between assignments.
* Cite any external sources used, including the textbook, internet,
discussions with other professors, etc.
* Aside from raising technical and procedural questions on the course
Piazza, do not collaborate on projects with others outside your
group.
* Do not post homework or project solutions on Piazza. Questions or
answers that discuss solutions too closely will be deleted.
Aside from the course-specific policies above, you are expected to
understand and abide by the college's
[policy on academic misconduct](https://www.swarthmore.edu/student-handbook/academic-policies#academic_misconduct).
## Late policy
Homework will generally be assigned on Thursday, and due at the start
of class the following Thursday. Homework assignments may be turned
in up to a week late for half credit. Students get one free late
homework turn-in without penalty. In contrast to homework, late
projects or absences from quizzes which have not been excused in
advance may be strongly penalized.
I will try to accommodate you in extraordinary circumstances,
*especially if you contact me ahead of time*.
# Scribes/researchers
Each week we will have two assigned scribes. Student scribe notes
should capture all of the material from the lecture, ideally including
questions and answers. We will aim to have two independent sets of
notes per week. Please type your scribe notes so we can furnish
accessible PDFs for students who use screen readers. It is OK to include
*neatly* scanned diagrams and/or equations, but I encourage you to try
out tools for digitally typesetting equations like [LaTex](https://www.latex-project.org) or even
just the [Google Docs](https://docs.google.com/) equation editor.
A third student each week will serve as a researcher whose job it is
to find outside links to material related to the week's lecture
topics. This material could be slides from a course at a different institution,
YouTube videos, or another type of online learning resource. Please
avoid Wikipedia. Researchers will produce approx. 5 links each week, along
with 1 or 2 complete sentences for each item explaining why it was
selected.
Scribes should email me PDFs to post to the course webpage by 9AM
every Monday; researchers can include links and descriptions in an
email to me (no attachment needed).
You will be able to find links to sign up for scribe and researcher slots
on our [Piazza page](https://piazza.com/swarthmore/fall2019/engr028cpsc082).
# Accommodations
If you believe you need accommodations for a disability or a chronic medical condition, please email Student Disability Services at studentdisabilityservices@swarthmore.edu to arrange an appointment to discuss your needs. As appropriate, the office will issue students with documented disabilities or medical conditions a formal Accommodations Letter. Since accommodations require early planning and are not retroactive, please contact Student Disability Services as soon as possible. For details about the accommodations process, [visit the Student Disability Services website](http://www.swarthmore.edu/academic-advising-support/welcome-to-student-disability-service). You are also welcome to contact me the faculty member privately to discuss your academic needs. However, all disability-related accommodations must be arranged, in advance, through Student Disability Services.
# Schedule
September 3, 2019: Introduction; Math review
Topics:
* Syllabus, labs, Piazza
* Math review
* Orthogonal & rigid transformations
Resources/assignments:
* [A practical (re-)introduction to linear algeba](http://www.swarthmore.edu/NatSci/mzucker1/linalg-reintroduction.pdf)
* [Robotics key points timeline](../robotics-history.html)
* [Python/numpy/matplotlib tutorial](http://cs231n.github.io/python-numpy-tutorial/)
* In-class coding examples from [Sep 3](https://github.swarthmore.edu/gist/mzucker1/7c59d1dc28038ed6e6a5ca997b7e1829) and [Sep 5](https://github.swarthmore.edu/gist/mzucker1/ed9eb53e2ba2908a75e89d5e244a6416)
* [Homework 1](homework1.pdf)
September 10, 2019: Robot motion basics; Control strategies
Topics:
* Relating coordinate frames
* Differential drive
* Integrating equations of motion
* State machines
Resources/assignments:
* [Project 1](project1.pdf)
* [Project 1 turnin instructions](project1_addendum.pdf)
* [*Vehicles*, Braitenberg 1986](reading/vehicles.pdf)
* [Braitenberg vehicles demo](braitenberg.html)
* [Homework 2](homework2.pdf)
* Scribe notes: [Ma](notes/notes_week2_ma.pdf) and [Moed](notes/notes_week2_moed.pdf)
Researcher links (Imada):
* [Explanation](http://tutorial.math.lamar.edu/Classes/DE/EulersMethod.aspx) of Euler's method we used in class to approximate our robot locations using small dt.
* [Description](http://www.cs.cmu.edu/~rasc/Download/AMRobots3.pdf) of the theory and linear algebra behind robot motion given their wheel velocities.
* [This](http://kovan.ceng.metu.edu.tr/software/Braitenberg/BraitenbergEN/Vehicles.html) gives a thorough explanation of Braitenberg machines and has a nice simulator that couples it (I have not tested the simulation).
* [Pros and cons](https://groups.csail.mit.edu/drl/courses/cs54-2001s/diffdrive.html) for differential drives, and [a similar explanation](http://planning.cs.uiuc.edu/node659.html) of what we did in class.
* [A deep dive](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-01sc-introduction-to-electrical-engineering-and-computer-science-i-spring-2011/unit-1-software-engineering/state-machines/MIT6_01SCS11_chap04.pdf) into state machines. I chose this link because we have used state machines in the context of robot behavior and I wanted to highlight that state machines can do so much more.
September 17, 2019: Sensors & actuators
Topics:
* Passive vs. active sensors
* Cameras, Kinect, and other 3D sensors
* Types of actuators
* Brushed DC motor analysis
Resources/assignments:
* [Sensors (Jones et al. 1998)](reading/mobilerobotics-ch5.pdf)
* [Motors (Jones et al. 1998)](reading/mobilerobotics-ch7.pdf)
* [Motor diagram from class](motor_diagram.pdf)
* [Homework 3](homework3.pdf)
* Scribe notes: [Martinez](notes/notes_week3_martinez.pdf)
September 19, 2019: In-class quiz: ROS Tutorials
September 24, 2019: Kinematics & dynamics
Topics:
* Kinematics of wheeled systems
* Configuration space
* Integrating equations of motion
Resources/assignments:
* [Project 1 turnin instructions](project1_addendum.pdf)
* [Homework 4](homework4.pdf)
* Scribe notes: [Eberle](notes/notes_week4_eberle.pdf) [Webb](notes/notes_week4_webb.pdf)
Researcher links (Ehlers):
* [This page](http://msl.cs.uiuc.edu/~lavalle/cs497_2001/book/diff/node4.html) has links to four different wheeled system scenarios, which include state transition equations and diagrams for two of them. I thought having a few different examples might be helpful.
* [Forward and inverse kinematics equations](http://www8.cs.umu.se/kurser/5DV122/HT13/material/Hellstrom-ForwardKinematics.pdf) for a robot, including some figures to help with the explanation. It shows the process to develop equations of motion.
* [A chapter](http://planning.cs.uiuc.edu/ch4.pdf) from the textbook "Planning Algorithms" that talks about configuration space. It's a very detailed explanation if anyone wants that much info.
* [Some slides](https://www.cs.cmu.edu/~motionplanning/lecture/Chap3-Config-Space_howie.pdf) about configuration space directly regarding robot motion. This link helps apply the idea of the configuration space directly to how it would be used regarding a robot.
* This discusses [deriving equations of motion](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-832-underactuated-robotics-spring-2009/readings/MIT6_832s09_read_appA.pdf) using Lagrange's equations. It has an example of a double pendulum and shows the mathematical process clearly.
* [Again, deriving equations of motion](https://web.stanford.edu/class/me328/lectures/lecture5-dynamics.pdf) for the double pendulum example. It expands on the example by trying to make it seem more realistic as a robot.
October 1, 2019: Control
Topics:
* Kinematics, continued
* Feedback controllers
* Pure pursuit
Reading/resources:
* [Tricycle kinematics worksheet](worksheet1.pdf)
* Scribe notes: [Covitz](notes/notes_week5_covitz.pdf) [Zhang](notes/notes_week5_zhang.pdf)
* [Pure pursuit code](https://github.swarthmore.edu/gist/mzucker1/2d46507fd45754814481e7125c436a45)
October 8, 2019: Control and dynamics
Topics:
* Proportional control
* Dynamics simulations
* PD and PID
Reading/resources:
* [AUV heading control: pseudo-kinematic demo](https://github.swarthmore.edu/gist/mzucker1/2f7354f14b0ffd2d6441c6afc0a3cb56)
* [AUV dynamics day 1 code](https://github.swarthmore.edu/gist/mzucker1/f11832975409f3f1575c55eb53f09196)
* [AUV dynamics day 2 code](https://github.swarthmore.edu/gist/mzucker1/af63e3e2e5b02345c7b2983d713dcc59)
* [AUV dynamics final](auv_dynamics.py)
* [Homework 6](homework6.pdf)
* Scribe notes: [Berg](notes/notes_week6_berg.pdf)
(October 15, 2019): Fall break
October 22, 2019: Control, cont'd; Navigation
Topics:
* PD and PID
* Map representations
* Navigation via graph search
* Dijkstra's algorithm & A*
Reading/resources:
* [Project 2](project2.pdf)
* [Homework 7](homework7.pdf)
* [iceblock.py](iceblock.py)
* Scribe notes: [Li](notes/notes_week7_li.pdf), [Morales Solorzano](notes/notes_week7_morales_solorzano.pdf)
October 29, 2019: Introduction to probabilistic robotics
Topics:
* Probability basics & Bayes' rule
* Localization & probabilistic filtering
* Bayes filter
Reading/resources:
* [Bayes filter demo](bayes_filter_demo.py)
* Scribe notes: [Springer](notes/notes_week8_springer.pdf)
November 5, 2019: Probability cont'd; Particle filter
Topics:
* Continuous random variables
* Sampling from distributions
* Introduction to particle filter
Reading/resources:
* [Homework 9](homework9.pdf)
* [Starter code](homework9.zip)
* [Particle filter demo](particle_filter_demo.py)
* Scribe notes: [Cheng](notes/notes_week9_cheng.pdf), [Solomon](notes/notes_week9_solomon.pdf)
November 12, 2019: Real-world localization; more probability fundamentals
Topics:
* Range sensor models
* Expected value
* Variance & covariance
* Kalman filter
Reading/resources:
* [Beam model slides (Burgard et al.) ](http://ais.informatik.uni-freiburg.de/teaching/ss10/robotics/slides/07-sensor-models.pdf)
* [Kalman filter slides](kalman.pdf)
* [Homework 10 - project proposal](homework10.pdf)
November 19, 2019: Kalman filter & EKF
Topics:
* Kalman Filter, cont'd.
* Extended Kalman Filter
* Grid mapping and SLAM
* ROS/Gmapping
Reading/resources:
* [Kalman filter demo](kalman_filter_demo.py)
* [Fairfield et al. paper](fairfield2007grid.pdf)
* [Grisetti et al. tutorial](grisetti2007tutorial.pdf)
* Scribe notes: [Kussmaul (KF)](notes/notes_week11_kussmaul.pdf), [Rutledge (mapping)](notes/notes_week11_rutledge.pdf)
* [Homework 12](homework12.pdf), [starter code](homework12.zip)
Researcher links (Dorji):
* **Good old Khan Academy.** These two sets of video serve as a
good starting point to understanding and getting intuitive sense
about Probability Density Functions and Normal Distribution:
* [Probability Density Functions](https://www.khanacademy.org/math/statistics-probability/random-variables-stats-library/random-variables-continuous/v/probability-density-functions)
* [Normal Distribution](https://www.khanacademy.org/math/statistics-probability/modeling-distributions-of-data/more-on-normal-distributions/v/introduction-to-the-normal-distribution)
* [This video](https://www.youtube.com/watch?v=cTyPuZ9-JZ0) and
[this article](https://web.sonoma.edu/users/w/wilsonst/papers/Normal/default.html)
derives the equation of normal distribution in a more or less
formal manner. The video is really long but it does explain all
the math involved really well. Watching is at 2x might be more
time efficient.
* A
[quick overview](https://support.minitab.com/en-us/minitab-express/1/help-and-how-to/basic-statistics/probability-distributions/how-to/inverse-cumulative-distribution-function-icdf/methods-and-formulas/methods-and-formulas/)
of different distribution functions, including inverse
cumulative distribution function.
* [This document](http://web.mit.edu/16.412j/www/html/Advanced%20lectures/Slides/Hsaio_plinval_miller_ParticleFiltersPrint.pdf)
from MIT gives detailed introduction to particle filter, a quick
comparison of particle filter with Kalman filters and some
applications of particle filter. It explains how particle filter
is used in SLAM.
* This article explains
[Kalman Filter](https://towardsdatascience.com/kalman-filter-an-algorithm-for-making-sense-from-the-insights-of-various-sensors-fused-together-ddf67597f35e) by considering how GPS systems predict the state of the vehicle even when no signal can be reached i.e. inside a tunnel. The article starts by considering the 1-D case of K filter and then scaling up to higher dimension where matrices are necessary.
* [Kalman Filter algorithm](https://medium.com/@jaems33/understanding-kalman-filters-with-python-2310e87b8f48)
with example code in python at the end. The article author
explains that the information is extracted from a lecture series
video on youtube. The lecture videos can be found
[here](https://www.youtube.com/watch?v=CaCcOwJPytQ&feature=youtu.be).
find the next video, go to the description section of the
video. It's a long series and I haven't watched all but if
anyone is interested.
November 26, 2019: Robotics and society
Topics:
* Automation and its beneficiaries
* Consumer models of robotics
* Startup culture
Reading/resources:
* [Slides from Tuesday's lecture](https://docs.google.com/presentation/d/11JmkW2O1xc2h7oAyNJ2BWnSoaVMrxQPRN_z_BwBA7l0/edit?usp=sharing)
(November 28, 2019): Thanksgiving
December 3, 2019: Mapping & SLAM; Manip. kinematics
Topics:
* SLAM approaches
* Dense & sparse maps
* Scan matching
* Nonlinear least squares
* Introdution to kinematics of serial manipulators
* Forward kinematics
Reading/resources:
* ICP videos: [first](https://www.youtube.com/watch?v=uzOCS_gdZuM), [second](https://www.youtube.com/watch?v=LcghboLgTiA)
* [Point cloud SLAM example](https://www.youtube.com/watch?v=08GTGfNneCI)
* [Introducing Ceres solver](https://opensource.googleblog.com/2012/05/introducing-ceres-solver-nonlinear.html)
* Scribe notes: [Line](notes/notes_week12_line.pdf)
December 10, 2019: Manipulator kinematics, cont'd.
Topics:
* Workspace
* Inverse kinematics
* Differential kinematics
(December 10, 2019): Last day of classes
(December 15, 2019): Final presentations, 9AM-noon, Singer 346