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