**E28: Mobile Robotics**
**ENGR 028/CPSC 082**
**Fall 2018**
**[Matt Zucker](http://swarthmore.edu/NatSci/mzucker1)**
| Lecture: | Tue/Thu 2:40-3:55PM, Hicks 211 |
|---------------|-------------------------------------------|
| Office Hours: | Wed 10:30AM-12:00PM, Hicks 202 |
| Lab hours: | Tue 4:00-5:00PM, Thu 1:00-2:00, Hicks 301 |
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_f2018/
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/fall2018/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 four 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-30 minute)
"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. 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
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. These may be either typeset
or *neatly* handwritten and scanned (*not photographed*).
Alternatively, two scribes may collaborate to produce a single set of
notes for the class, which is expected to be both typeset and more
comprehensive than an individual's notes.
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 or high-resolution scan images to post on
the course webpage by 9AM every Monday; researchers can include links
and descriptions in an email to me (no attachment needed).
You can find links to sign up for scribe and researcher slots
on our [Piazza page](https://piazza.com/swarthmore/fall2018/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 privately to discuss your academic
needs. However, all disability-related accommodations must be
arranged, in advance, through Student Disability Services.
# Schedule
September 4, 2018: 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)
* [Homework 1](homework1.pdf)
* Notes:
* [Hoang](notes/notes_week1_hoang.pdf)
* [Ridder](notes/notes_week1_ridder.pdf)
* Researcher links (Studier):
* [This Khan Academy video](https://www.khanacademy.org/math/linear-algebra/alternate-bases/orthonormal-basis/v/lin-alg-orthogonal-matrices-preserve-angles-and-lengths) explains conceptually what an orthonormal transformation does, and how it preserves length and angle. Other videos in this chain may be helpful as well.
* [Wolfram Mathworld](http://mathworld.wolfram.com/BlockMatrix.html) gives a simple example of block matrix multiplication.
* [Mathbitsnotebook.com](https://mathbitsnotebook.com/Geometry/Transformations/TRRigidTransformations.html) gives an overview of Rigid Transformations (although don’t pay attention to reflections for our class!)
September 11, 2018: Robot motion basics; Control strategies
Topics:
* Relating coordinate frames
* Differential drive
* Integrating equations of motion
* State machines
Resources/assignments:
* [Project 1](project1.pdf)
* [Homework 2](homework2.pdf)
* Notes:
* [Emmons](notes/notes_week2_emmons.pdf)
* [Xie](notes/notes_week2_xie.pdf)
* Researcher links (Candey):
* **Coordinate Frames** -- [Robotics blog of Paul Furgale](http://paulfurgale.info/news/2014/6/9/representing-robot-pose-the-good-the-bad-and-the-ugly).
A discussion of standardized coordinate frame explanation in
robotics for a library called Kindr, includes a conversion of
Kindr to ROS calls. Probably not needed for lab, but the
article has good advice on how to do write ups involving
different frames.
* **Differential Drive** --
[RobotPlatform](http://www.robotplatform.com/knowledge/Classification_of_Robots/wheel_control_theory.html).
Differential drive is one of many drive designs for robots,
which are described on RobotPlatform. There are pros and cons
for differential drives compared to the other designs, not
that we have a choice in our drive design.
* **Journal article** -- [Int'l. J. Science, Engineering and Technology Research](http://ijsetr.org/wp-content/uploads/2016/09/IJSETR-VOL-5-ISSUE-9-2849-2855.pdf).
This is an extensive engineering analysis of our specific two
wheeled case focused on finding position error from the
International Journal of Science, Engineering and Technology
Research. The kinematics equations we saw in class appear,
along with familiar and unfamiliar matrices.
* **Integrating Equations of Motion** --
[Professor Cheever’s Linear Physical Systems](http://lpsa.swarthmore.edu/NumInt/NumIntIntro.html).
Euler’s method and Runge-Kutta approximate the solutions of
differential equations in the style of the in-class pseudo
code. There is extensive MATLAB pseudo code at the bottom of
each page for Euler’s and first, second and fourth order
Runge-Kutta solutions. This is specifically for differential
equations found in engineering, but the general explanation is
very good.
* **State Machines** --
[Professor Kafura from Virginia Tech](http://people.cs.vt.edu/~kafura/ComputationalThinking/Class-Notes/FSM.pdf).
Explanation of candy dispenser state machine by Professor
Dennis Kafura at Virginia Tech, including a nice diagram of
the machine from inserting coins to dispensing candy. There
are also definitions of state and behavior with regards to
this example.
September 18, 2018: Sensors & actuators
Topics:
* Passive vs. active sensors
* Cameras, Kinect, and other 3D sensors
* Types of actuators
* Brushed DC motor analysis
Resources/Assignments:
* [Mobile Robotics: Motors (Jones et al.)](mobilerobotics-ch7.pdf)
* [Homework 3](homework3.pdf)
* Notes:
* [Padilla](notes/notes_week3_padilla.pdf)
* [Nguyen](notes/notes_week3_nguyen.pdf)
* Researcher links (Yang):
* **[Flow rate of a Stream](https://www.youtube.com/watch?v=4uS9oOTa4PI)**:
This is a video about how real researchers estimate the flow
rate of a stream. It is quite similar to how we did it.
* **[Colored Blob Detection](https://www.learnopencv.com/blob-detection-using-opencv-python-c/)**:
This tutorial talks about how to implement colored blob
detection function in Open CV, including different parameters
you can tweak to find the size, shape, and other
characteristics of the blob you want.
* **[PID Controller](https://www.youtube.com/watch?v=UR0hOmjaHp0)**:
The control we used in class for line following is called a
proportional controller. This short lecture gave good
explanations and examples of the proportional controller, as
well as two other common controllers—integral controller and
derivative controller. They are together called PID
controllers.
* **[Sensors](http://www.robotplatform.com/knowledge/sensors/types_of_robot_sensors.html)**:
This website gives a list of sensors commonly used in
robotics. And this
[shopping website](http://www.robotplatform.com/knowledge/sensors/types_of_robot_sensors.html)
gives us an idea of their market prices.
* **[Analog to Digital Converter](http://hyperphysics.phy-astr.gsu.edu/hbase/Electronic/adc.html#c2)**:
This short article illustrates a few other kinds of ADC that
is different from the Flash ADC we talked about in class.
* **[DC motors](https://www.youtube.com/watch?v=Gzca2CbZ6EM)**:
This video shows the working of a brushed DC motor. A more
popular design of DC motors (in electric vehicles and drones)
are called brushless DC motors(BLDC). How they work is
illustrated in
[this video](https://www.youtube.com/watch?v=bCEiOnuODac).
September 20, 2018: In-class quiz: ROS Tutorials
September 25, 2018: Kinematics & dynamics
Topics:
* Kinematics of wheeled systems
* Configuration space
* Integrating equations of motion
Resources/Assignments:
* [Project 2](project2.pdf)
* [ROS livecoding examples](https://github.com/swatbotics/ros_examples_inclass)
* [Homework 4](homework4.pdf)
* [Worksheet 1](worksheet1.pdf)
* Notes:
* [Keane](notes/notes_week4_keane.pdf)
* [Greco](notes/notes_week4_greco.pdf)
* Researcher links (Thompson):
* **Closures:** These articles and comments give great examples
and explanation about what a closure is and how they can be
used. It also gives a good overview of vocabulary.
* https://stackoverflow.com/questions/36636/what-is-a-closure
* https://www.gnu.org/software/emacs/manual/html_node/elisp/Closures.html
* **Lambda functions and first class types:** These articles give in depth applications for lambda, or anonymous functions.
* https://www.mathworks.com/help/matlab/matlab_prog/anonymous-functions.html
* https://en.wikipedia.org/wiki/First-class_function
* **ROS documentation:**
A good resource for finding the function with the capability you need. Gives necessary parameters and also some examples.
* http://wiki.ros.org/
* **Wheel Vehicles Kinematics Article:**
Overview of the kinematics of wheeled vehicles including the Directional Drive and Tricycle examples from class.
* http://users.isr.ist.utl.pt/~mir/cadeiras/robmovel/Kinematics.pdf
October 2, 2018: Control
Topics:
* Feedback controllers
* PD and PID control
Resources/Assignments:
* [Homework 5](homework5.pdf)
* [PID control Python code](pid.py)
* [Pure pursuit code](https://github.com/swatbotics/pure_pursuit_inclass)
* [Original paper introducing pure pursuit (Coulter, 1992)](https://www.ri.cmu.edu/pub_files/pub3/coulter_r_craig_1992_1/coulter_r_craig_1992_1.pdf)
* Notes:
* [Boshkoff](notes/notes_week5_boshkoff.pdf)
* [Luciano](notes/notes_week5_luciano.pdf)
* Researcher links (Belkin):
* [A nice pedagogical introduction to PID](http://www.ent.mrt.ac.lk/~rohan/teaching/EN5001/Lectures/ch8%20pid.pdf), which also briefly introduces some tuning methods.
* [A more detailed explanation of the Ziegler-Nichols tuning method](http://www.mstarlabs.com/control/znrule.html)
* A 2-part series discussing PID systems with automatic parameter tuning: [Part 1](https://www.controleng.com/single-article/pros-and-cons-of-autotuning-control-part-1/) [Part 2](https://www.controleng.com/single-article/pros-and-cons-of-autotuning-control-part-2/)
* [An academic paper discussing PID in some depth.](https://ravt.files.wordpress.com/2013/11/prihodnostpid.pdf) I found the stability diagrams (figures 2 and 3) and the discussion of alternative methods in Section 7 quite interesting.
October 9, 2018: Optimal control & LQR
Topics:
* Discrete-time linear systems
* LQR problem statement & proof
* Implementing LQR
Resources/Assignments:
* Oh no, I forgot to assign Homework 6!
* [In-class coding examples](https://github.com/swatbotics/lqr_inclass_demos)
Notes:
* [Hernandez](notes/notes_week6_hernandez.pdf)
Researcher links (Chang):
* [Another derivation of LQR and how to design it](https://www.cds.caltech.edu/~murray/courses/cds110/wi06/lqr.pdf)
* [Cool use of LQR](https://www.youtube.com/watch?v=BgGslwu8Bec)
* Lengthy numpy
[tutorial](http://cs231n.github.io/python-numpy-tutorial/) and
[reference](https://docs.scipy.org/doc/numpy-1.15.1/reference/)
* [LQG (Linear quadratic guassian)](http://www.engr.uconn.edu/~xchen/Teaching/ME233Sp2014/_static/UCB_ME233_6_LQG.pdf) when there is noise and the system is not fully observable
(October 16, 2018): Fall break
October 23, 2018: Navigation
Topics:
* Map representations
* Navigation via graph search
* Dijkstra's algorithm & A*
Resources/Assignments:
* [Homework 7](homework7.pdf)
* [Dijkstra's algorithm worksheet](worksheet2.pdf)
* [Footstep planning slides](footstep-planning-astar.pdf)
Notes:
* [Vik](notes/notes_week7_vik.pdf)
* [Gilchrist](notes/notes_week7_gilchrist.pdf)
Researcher links (Meyer-Lee):
* ***[Amit Patel's Introduction to A star.](http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html)*** This post reviews most
of what we covered this past week, including Dijkstra's, A*, and
map representations, but goes into a lot more detail about
implementation and includes a number of examples. The main
caveat to this is that this article is discussing these
algorithms in the context of game programming, not robotics,
however the post is general enough that there is fairly little
that does not have some relevance, and most of the
game-programming specific material is in the last few pages of
the post. This is a good resource for students who want source
code or interactive examples of these algorithms.
* ***[University of Tennessee Knoxville Lecture Slides.](http://web.eecs.utk.edu/~leparker/Courses/CS594-fall08/Lectures/Oct-2-Path-Planning-I.pdf)*** This
is also a fairly general overview of the information discussed
over the past week. Good for a reference for the pros and cons
of different map representations and a very simple and
straightforward overview of A*. The major upside of these slides
over the above blog is that they are focused on the field of
robotics, so robotics-relevant concepts like configuration space
and object growing are discussed.
* ***[A Formal Basis for the Heuristic Determination of Minimum Cost Paths by Peter Hart, Nils Nilsson, and Bertram Raphael.](https://www.cs.auckland.ac.nz/courses/compsci709s2c/resources/Mike.d/astarNilsson.pdf)***
It seemed like there were a number of questions in class about
A*, so I thought it would be prudent to include the original A*
paper. The two main uses out of reading this paper I see as
being 1) getting insight into the context and reasoning behind
developing A* and 2) the proof offered as to why A*, properly
formulated, will find the optimal path.
* ***[Generalized Best-First Strategies and the Optimality of A star by Rina Dechter and Judea
Perl.](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.89.3090&rep=rep1&type=pdf)***
I chose this article because some questions emerged regarding
how and why A* could be considered optimal, and I didn't think
the original A* paper satisfactorily discussed why A* could be
considered optimal with regards to other heuristic search
algorithms. This piece does a fantastic and thorough job of
discussing and proving the optimality of A*, although it isn't
exactly light reading. For students interested in this question
but not fully committed to really digging into the math, [this
presentation](https://cse.sc.edu/~mgv/csce580f08/gradPres/clevelandWaggonerAstar080915.pdf) provides an overview of the content in an easier to
read format.
* ***[One of Matt's papers.](http://lairlab.org/wp-content/uploads/2009/09/ld-systems.pdf)***
As we spent a decent amount of class discussing
quadruped-robotics footstep planning, I thought it would make
sense to include a CHOMP paper. Although the original CHOMP
conference paper is your most cited work, and the CHOMP journal
paper is the most thorough review of CHOMP and your second-most
cited work, I actually found this paper to reflect most the
topics we discussed in class. Specifically, we actually
discussed the problem you were working on in general more than
we did CHOMP and I found this paper did a great job of providing
more technical information about the different parts of your
approach to this problem you described in class.
October 30, 2018: Introduction to probabilistic robotics
Topics:
* Probability basics & Bayes' rule
* Localization & probabilistic filtering
* Bayes filter
Resources:
* [Probability cheatsheet](probability_cheatsheet.pdf)
* [`bayes_filter_demo.py`](bayes_filter_demo.py)
* [Homework 8](homework8.pdf)
* [Project 3](project3.pdf)
* Notes:
* [Jobson](notes_week8_jobson.pdf)
* Researcher links (Nerurkar):
1. [Self-Driving Cars Estimation/Reasoning](https://www.youtube.com/watch?v=tiwVMrTLUWg): (7:45) this TedTalk shows how a car views the world in more detail than we saw in class. You can see how much is deep learning and how much is based on stored data.
2. [Autonomous Cars and the Trolley Problem](https://www.theatlantic.com/technology/archive/2018/03/got-99-problems-but-a-trolley-aint-one/556805/): an interesting article on why the trolley problem is irrelevant to the prospect of autonomous vehicles. Not a very scientific article, but raises some good points.
3. [Ethical Rules for Autonomous Vehicles](https://www.bmvi.de/SharedDocs/DE/Pressemitteilungen/2017/128-dobrindt-massnahmenplan-ethikregeln-fahrcomputer.html): (need to translate from German) This link gives an overview of the rules adopted by Germany to allow self-driving cars to be legally driven.
4. [Bayes Theorem](https://www.youtube.com/watch?v=Zxm4Xxvzohk): a simple visual explanation of Bayes Theorem.
5. [Bayes Filter](https://www.youtube.com/watch?v=w1u6-_2jQJo): this link helped me compare the hypothesized distribution with the data side by side. We can also see how the probability of the data varies with the initial hypothesis.
November 6, 2018: Probability cont'd; Particle filter
Topics:
* Continuous random variables
* Sampling from distributions
* Introduction to particule filter
Resources:
* [`particle_filter_demo.py`](particle_filter_demo.py)
* [`tent_starter.py`](tent_starter.py)
* [Homework 9](homework9.pdf)
* [Notes (Beilinson)](notes/notes_week9_beilinson.pdf)
* Researcher links (Kim):
* [A more technical description of how Kinect is used in ROS](http://wiki.ros.org/kinect_calibration/technical)
* [Comprehensive review of continuous random variables](https://onlinecourses.science.psu.edu/stat414/node/88/)
* [Review of normal distributions](http://mathworld.wolfram.com/NormalDistribution.html)
* [Review of CDF and PDF](https://www.itl.nist.gov/div898/handbook/eda/section3/eda362.htm)
* [This website](https://rse-lab.cs.washington.edu/projects/mcl/) demonstrates the uses of particle filters.
November 13, 2018: Real-world localization examples
Topics:
* Range sensor models
November 20, 2018: Kalman filter & EKF
Topics:
* Expected value
* Variance & covariance
* KF and EKF
* Final project ideas
(November 22, 2018): Thanksgiving
November 27, 2018: TBA
December 4, 2018: TBA
December 11, 2018: Wrapping up
(December 11, 2018): Last day of classes