ROB 599: Programming for Robotics | Fall 2019

Instructor: Acshi Haggenmiller (acshikh), PhD Candidate
Tu/We 1:30-4:30pm
1620 Bob and Betty Beyster Building (CAEN lab in the hallway to DOW)

This whole site is a living document and subject to change.

Introduction

This class is designed for engineering students who have a basic understanding of programming but haven’t majored in computer science or taken a dedicated sequence of programming courses. The goal of this class is for students to learn how to 1) write programs from scratch that meet robotic system requirements; 2) organize programs into logical sections; 3) critique program design and implementation choices; 4) use appropriate debugging tools and methodology to efficiently understand and correct program behavior; and 5) use the command line to work with git and other relevant utilities and scripts.

As it is titled Programming for Robotics, we have tried to design the in-class problems and homework assignments to be relevant to common robotics situations and algorithms, with the greater goal of demystifying programming and avoiding black-box magic. To be relevant and exciting, we designed the homework assignments around building a robotics simulation environment. While there are many excellent libraries and tools available for this (ROS among them), we will figure it out for ourselves! The best way to learn programming is by programming, so there will not be any quizzes or exams, and algorithms and necessary math will be provided so you can focus on implementation and not derivation.

The class uses the C programming language. C is a relatively simple language that will help us understand the fundamentals of how computer programs works, without the language letting us take complicated features for granted. Although most robotics programming is done in languages like Python and C++, the fundamentals you learn in C will help you to better understand what is happening in those more complicated languages.

Most class sessions will follow a “labture” format. We will start with a series of segments containing a short lecture, an instructor demo, individual work on a self-contained problem, and finally class solution evaluation. Students are encouraged to ask each other and the instructor for help, but only students who have finished a problem should be looking at other students’ code. In the evaluation, we will review several anonymous solutions and talk about their relative strengths.

Some class sessions will not have any formally scheduled instruction or problems. Instead, topics will be addressed on an as-needed basis, with the remaining time open for working on the homework assignments with instructor help. The homework assignments are intended to require about 4 hours per class session. In general, they will be due 1 week after the end of the topic section they were assigned in. For example, the first homework will be due before class session 5.

Class Schedule

Classes 1-3: Data representation

• Goals: 1) Inspect abstract data (e.g. pictures, text, plans) at the byte and bit level, and understand how changing low-level numbers affects high-level meaning. 2) Use the command line with git and the class submission system to get feedback.
• Class 1: Using Linux and bash
• Class 2: Using git to commit and submit code; expressing logic
• Class 3: Arrays, ASCII, bytes, and GDB
• Homework 1: Polygonal collision detection, cryptogram
• There are variety of C concepts that will not be explicitly covered in class! We are providing a tutorial document to help explain the necessary syntax and basic ideas so we can delve right into the good stuff!
• For an even gentler introduction to C, I highly recommend Harvard’s CS50 lectures. Although the whole lectures can be long, they have good tables of contents on each lecture on YouTube, and work well at 2X playing speed. This clip focuses on compiling C, on using make, and on common compiler errors. This one is on the compilation process.
  If you want to follow along with their examples, you will need to use their sandbox.

Classes 4-7: Memory concepts and debugging

• Goals: 1) Determine when dynamic memory is appropriate and how to prevent and detect memory leaks. 2) Determine when pointers are necessary and reason about when they are valid. 3) Use feedback from GDB, Valgrind, and AddressSanitizer to fix memory and other bugs.
• Class 4: Addresses, pointers
• Class 5: Malloc/free, debugging errors, and dynamic arrays
• Class 6: Linked lists
• Class 7: As needed
• Homework 2: Rasterizing bitmaps, Braitenberg vehicles
• This clip talks about how data is stored in memory. This one talks about pointers. This one talks about malloc and free. This one talks about memory addresses and hexadecimal. This one is on stack overflows.

Classes 8-10: Recursion and Search

• Goals: 1) Reason about and write recursive algorithms. 2) Use search algorithms with forward simulation to choose robot actions.
• Class 8: Bisection search, midpoint method, recursion vs iteration
• Class 9: Tree search
• Class 10: As needed
• This clip gives an overview of recursion and how the computer’s stack is used to hold multiple versions of the same function in memory.
• Homework 3: Equation parsing, robot chase

Classes 11-13: Object abstractions

• Goals: 1) Analyze algorithmic complexity and determine when it matters. 2) Choose data structures based on algorithm needs. 3) Separate and hide implementation from specification.
• Class 11: Complexity/Big-O Notation
• Class 12: Hash tables
• Class 13: As needed
• Homework 4: Bigrams

Classes 14-17: Threading

• Goals: 1) Understand when threading is necessary and how to avoid using it unnecessarily. 2) Determine when variables may be subject to race conditions and how to prevent them. 3) Use threading for terminal input control.
• Class 14: Basic threading
• Class 15: Race conditions, deadlock, mutexes
• Class 16: Terminal settings, I/O threading, manual robot control
• Class 17: As needed
• Homework 5: Live-tuning potential fields

Classes 18-20: Message passing and networking

• Goals: 1) Divide robotic systems into independent parts. 2) Coordinate program communication across network nodes. 3) Use logging and playback features to debug specific modules.
• Class 18: LCM/ROS basics, hybrid architectures
• Class 19: Networking
• Class 20: As needed
• Homework 6: Split project into communicating processes

Classes 21-23: Special topics

• Class 21: Coding interviews
• Class 22: Code reviews
• Class 23: Introduction to Python

Grading

Grades will be 5% course feedback assignments, 5% participation, 30% in-class assignments, and 60% homework assignments (evenly split between all the homework assignments, including the final project). In-class assignments will be 50% correctness and 50% participation (awarded for at least 50% correctness). Assignments will report their percentage completion through the auto-grader, with points given for completing objectives and points taken away for things like memory errors or inconsistent style. Final grades will be curved if necessary.

Course feedback

Several times over the semester, we will ask students to submit their anonymous feedback on the course. As a completely new course, we want to gauge the effectiveness of the course setup, assignments, and teaching style.

Participation

During every class session we will have some “clicker”-type question to verify attendance. We want everyone to come to class so that you can support the other people at your table/group. Although assignments are individual and you shouldn’t write code for anyone else, the class will be better for everyone if we can give advice and support and aid to each other. Also, if you get ahead of the in-class assignments, please start working on the homework!

Late Policy

For in-class work, the two lowest scores for individual in-class assignment problems will be dropped. If you anticipate missing a class day, you are encouraged to complete that day’s assignments beforehand.

For homework, over all the homework assignment problems, 48 total cumulative hours of tardiness are “free”. After this, each hour an assignment is late (rounded up by ceiling) will reduce its maximum score by one percentage point (so 80% completion of an assignment 10 hours late would be 80% * 90% = 72%). The auto-grader will report these percentage calculations and keep your highest final score from any submission. The 48 free hours of allowed homework tardiness will be applied at the end of the semester to maximize your final grade.

At any point, run p4r-check in a problem folder to see the highest score the auto-grader has recorded for you.

Accessing CAEN Computers

To have a consistent development environment for all users, we will be using the CAEN computers in our classroom space. No matter which computer you log into, you will have access to your files. You are free to also use a personal computer if you like, although it may or may not be as easy to setup as the CAEN computers.

You can also access the CAEN computers remotely from your own computer through the ssh tool:

• While on campus run the following with your uniqid and enter your password and DuoMobile 2-factor authentication:

  ssh -X uniqid@oncampus-course.engin.umich.edu
  

• When off campus, instead use:

  ssh -X uniqid@login-course.engin.umich.edu
  

• The -X option enables X11 Forwarding, which lets you open graphical programs over ssh and have them appear on your host computer. If you are running Windows as your host computer, you will then also need to install an X11 server to actually manage these windows. I recommend xming. If you don’t need to use a gui over ssh, you can omit this option. X11 Forwarding is pretty slow, though, so I don’t recommend it for general work.

Academic Honesty

The programs you submit, for both in-class and homework assignments, must be your own work, and significant similarity to other submissions will be considered highly suspect. Ultimately, though, the basic guideline is to be reasonable.

While working on problems, you are encouraged to search the internet to learn how to perform specific functions or techniques. In general, if you find a trivial one-liner on StackOverflow, you do not need to cite this. If you are copying a full algorithm, say for quicksort, you would need to cite this (or just use the standard library function qsort!). If that algorithm is a core objective of the assignment, however, then this would not be appropriate regardless of citation. Especially when you implement trickier algorithms or mathematical calculations that you found somewhere online, it can be wise to include a link to the original description of that method in a comment. This makes it easier to check or resume your work later.

You are especially encouraged to get help from your peers! This means that after trying to figure out a problem or fix your code, please talk to other students. If you want them to look at your code, make sure they have already finished that section. Ask them for pointers about where the error is or what concepts or techniques to review, especially debugging techniques. Keep the conversation high-level and don’t give or receive guided instructions on exactly what code to write. The most useful thing would be to point out flawed logic and allow the other student to come up with the fix themselves. For earlier brainstorming of problem solutions, discuss problems using a whiteboard or a sheet of paper so that everyone can still write their code for themselves. You should not show your own working code to another student who is struggling to complete theirs.

If on the homework you get significant help from your peers, please consider adding a comment in your code at the top of the file saying who you collaborated with and what information was shared. This may help avoid potential confusion in similar solutions. However, since sharing of code is not permitted, we still expect the small details to be significantly different.

If it has been determined that students have flagrantly violated this policy, we reserve the right to respond severely.