CSE494: Introduction to Mobile Robotics Fall 2018

[https://sites.google.com/a/asu.edu/cse494-robotics-fall-2018/]

Major updates on the class website

  1. 2018-09-19: Change of office hours for G. Fainekos

Any major updates on the website will be announced here! Any information in this syllabus (other than grading and absence policies) may be subject to change with reasonable advance notice.


 
Multi-iRobot scenario
 
NAO driving a BMW

 
Vehicle Perception

Introduction (Course Objectives and Expected Learning Outcomes)

Most of you must have seen the Waymo cars autonomously driving in the Phoenix Metropolitan Area. But how do these vehicles perceive their environment, plan their navigation, and drive around while obeying all the traffic rules? This courses provides the foundations to analyze, develop and implement algorithms for autonomous mobile robots. The best description for the focus of this course is provided by the following excerpt from the International Workshop on the Algorithmic Foundations of Robotics (WAFR) (for example see WAFR 2012):

"Robot algorithms are a fundamental component of robotic systems. These algorithms process inputs from sensors that provide noisy and partial data, build geometric and physical models of the world, plan high-and low-level actions at different time horizons, and execute these actions on actuators with limited precision. The design and analysis of robot algorithms raise a unique combination of questions from many fields, including control theory, computational geometry and topology, geometrical and physical modeling, reasoning under uncertainty, probabilistic algorithms, game theory, and theoretical computer science."

This course aims to make accessible to undergraduate students 
a principled and mathematically sound approach to the design of algorithms for robots. The students in this course will acquire the mathematical foundations that are required for the implementation and analysis of algorithms for robotic applications through homework problems and a final project. Among the course goals is the development of the vocabulary and mathematical background so that the students can follow the current research and development trends in the robotics industry.

In particular, we will study:
  1. Modelling mobile robots and their workspace: What are the workspace and configuration spaces of a robot? How can we create discrete abstractions (graphs) for motion planning, sensor placement, coverage, etc?
  2. Discrete planning: Many robotic tasks can be represented using discrete abstractions, e.g., graphs. How can we efficiently search a graph to find a desired goal state (node)? 
  3. Continuous planning and control: How do we move a robot with complex kinematic and dynamic constraints in an environment with obstacles? 
  4. Sensing and localization: What are typical sensors for robots? How do we detect objects? How do we model uncertainty in sensing? How does the robot know where it is? How can a robot construct a map of its environment?
  5. Planning under uncertainty: Given the sensor inaccuracies and localization uncertainty, how do we plan the actions of our robots?
  6. Social implications: What may be the implications to our society of fully autonomous cars and trucks? What if there is a service robot in each home?
  7. Other topics in mobile robotics (time permitting): 
    1. Multi-robot issues: decentralized control, consensus, flocking, etc;
    2. Warehouse robotics and automation;
    3. Software quality assurance in robotics.

The course emphasizes rigorous thinking and mathematical foundations. Before registering for the course please make sure that you feel comfortable with the level of mathematical presentation in Prof. LaValle's textbook. The course also assumes that you have good programming skills.


Learning outcomes: By the end of this course, you will know how to implement algorithms for motion and path planning, perception, and robot localization. In addition, you will be familiar with the robotics literature and how to find information relevant to this fast moving market and research field. Finally, you will attain a solid background in order to pursue an honor thesis or graduate level studies on robotics.


Relation to other courses: This courses focuses on the application of graph algorithms, feedback control, machine learning, artificial intelligence, computer vision and real-time embedded system/programming issues to mobile robotics. In addition, ASU offers a variety of courses that cover all the aforementioned topics in detail (without targeting robotics) and you are advised to take these courses as well. In detail, the following courses can provide complementary material that can strengthen your credentials as a robotics engineer: algorithms (CSE 450)artificial intelligence (CSE 471), embedded systems (CSE 325 or CSE 438), software engineering (CSE 446, CSE 460, or CSE 464), automata theory (CSE 355), and computational linguistics (CSE 476)


What this course is not about: This course does not cover electromechanical design of robots, industrial robotics, natural language processing and human-machine interaction. Actually, ASU offers a variety of (mainly graduate level) courses that cover all the aforementioned topics in detail. Finally, this course does not cover the challenges that you will encounter when programming embedded systems for robotics applications since this is typically the focus of CSE325 or CSE 438.


Disclaimer


This is a live web-page so please check it frequently: The current course web site reflects my current plans for the course. This course is currently under development and it will be modified based on the number of students and their background. Therefore, it is recommended only to adventurous students who can excel within non-fully structured environments. 

Logistics (Contact Information and Office hours)

  • Class: Monday and Wednesday 15:05-16:20, SCOB 150 
  • Instructor: Georgios Fainekos (fainekos at asu)
  • Office hours: By appointment or check my scheduled office hours on my calendar. Tentatively, the office hours are scheduled for M 1-2pm & F 11:30am-12:30pm.
  • Office: Centerpoint 203-17
  • Teaching assistant: Erkan Tuncali  
  • Announcements will only be posted on Canvas (sometimes also in class on the slides).
  • On-line discussions will take place at Piazza (this is the only allowed discussion platform for assignments and projects).
  • Electronic communication policy:
    • I do not respond to emails or to on-line discussions over the weekend.
    • If you have any question that is not related to personal issues, then you MUST first post it on the discussion board on Piazza under the most relevant topic.
      • If you would like to participate to on-line discussions, on-line polls etc you must enroll to Piazza.
    • We will be responding to any questions on Piazza after 1 business day. This will let your classmates enough time to attempt to answer your question for class participation credit.
    • If you think you must send me an email due to the personal nature of your question or you think that your question might not be interesting\relevant to the rest of the class, then send me an email.
    • Before sending an email please follow the excellent advice here: 
      http://www.wikihow.com/Email-a-Professor

Prerequisites

Robotics is a fundamentally multi/inter-disciplinary area. Even by focusing on algorithmic robotics, there is still a long list of courses that can help you better understand the topics under study. You must be currently enrolled or you must have taken in the past, the following courses:
  1. Probability and statistics (IEE 380)
    • needed for localization, perception, and mapping: the world is uncertain and the senors are noisy
  2. Calculus (MAT 265 & MAT 266; Recommended MAT 267)
    • needed for modeling in order to predict and plan the robot motion
  3. Data structures (CSE 310)
    • needed for algorithm implementation 
  4. Linear algebra (MAT 343)
    • needed for vision, localization, motion planning, etc
Review material from the aforementioned classes and primers will be provided as needed.

Textbooks & Readings

We will closely follow the main textbook below. Furthermore, research papers will be recommended for cutting edge research topics.

Remark: Do not print any on-line book using university printers. Even on-line published textbooks offer hard copy versions through various printing companies.


  • Recommended textbooks for more advanced readers:
    • [Choset et al 2005] H. Choset et. al., "Principles of Robot Motion: Theory, Algorithms, and Implementations", MIT Press, 2005. 
    • [Thrun et al 2005] Thrun, Burgard and Fox, "Probabilistic Robotics", The MIT Press, 2005
      • The absolute reference on probabilistic methods in robotics.

  • We will also be using material from:

  • Additional References: 
    • [LaValle 2006] S. M. LaValle, "Planning algorithms", Cambridge University Press, 2006.
    • [Siegwart et al 2011Siegwart, Nourbakhsh, and Scaramuzza, "Introduction to Autonomous Mobile Robots", MIT Press, 2011

Grading

Grades will be based on:

  • The following grading scheme will be used for the in class section: 
    1. Homework assignments 50% 
      • Almost all the homework problems will be programming assignments. Hence, all homework problems will be individual effort (no group submissions are allowed). Even though collaborative work is not allowed, classroom Piazza discussions are permitted. Note that all code development must be individual effort. Copying code from any source or your classmates is considered violation of academic integrity.
    2. Class project or final exam 40%
      • You have the following choices: (1) proposing and implementing an open ended project, (2) working on a project defined by the instructors, or (3) taking an in-class final exam. See below for more information on the term project or the final exam.
      • The only possibility for A+ in the course is excellence throughout the semester and an impressive term project of conference publication quality. See below for conferences.
    3. Class participation 10%
      • Class participation consists of:
        • Finding typos, bugs, etc in the book, slides, lecture notes, homework problems etc
        • Answering questions (correctly) in the class
        • Answering questions (correctly) on-line on the discussion board
        • Active discussion in class or on-line on the lecture material
        • Responding to surveys
      • Class participation is not an one time contribution. It must be a continuing activity throughout the semester. It is assigned as a percentage of the participation in the electronic class activities (more weight) and in-class discussions (less weight). 
  • Grading scale:

A+

>100%

B-

[75-80)%

A

[95-100]%

C+

[70-75)%

A-

[90-95)%

C

[65-70)%

B+

[85-90)%

D

[55-65)%

B

[80-85)%

F

<55%


Note: The above might still change depending on the number of students and the available resources. For example, it is possible that a lab component might be introduced, if resources become available.

Late Homework/Project (re-)submission policy

In case of late submission (or re-submission in case you are not proud of your earlier submission), a penalty of min(60,5*days) percentage points will be applied to your score. Here, days is the number of days the assignment is late. The deadline to (re-)submit late work is the last day of classes.

Project description (Choose between a term project and a final exam)

Comments:
  • A perfect project will be graded 100pt. An exceptional project, i.e., new results that can lead to publication, will receive grade more than 100pt. 
  • No group projects will be allowed unless you have a provide a detailed work plan for each group member and I approve it. If you decide to go forward with a group project, then each member must be responsible for a technical challenge. 
  • You may want to see me or the TA during office hours before you submit your proposal.
  • The instructor defined project will be a project on developing basic autonomous vehicle functionality in a simulation environment.

Project ideas (beyond the structured project that we will provide):

  • Implementing some of the algorithms we did in class on a real robot (either in my lab or with your own equipment) or in a physics accurate robotics simulator. 
    • Possible ideas (of variable difficulty):
      • 3 on 3 robot soccer games using the Nao humanoids
        • Or specific modules, e.g., approach the ball as fast as possible to kick it in the right direction.
      • Person following and collision avoidance using a parrot quadcopter
      • Multi robot path planning and/or formation control using iRobots 
      • Picking using a robotic arm and coordination with a ground robot
      • A semi-autonomous remote presence robot
      • Driving autonomously while obeying traffic rules
      • Make a Nao or iRobot dance
      • "Lightsaber" fight between two iRobots or dogfight between two quadrotors
      • Mapping and localization using a Lego Mindstorm kit and a camera
      • Warehouse robotics (carrying packages in a warehouse environment)
      • A guard robot that throws foam balls on intruders
      • Agricultural robotics, e.g., fly a drone to take pictures of tomatoes, leafs, etc.
    • If you have your own robot, then you may propose something that you would like your robot to achieve autonomously. 
    • Cool ideas from other related courses:
  • Modeling/Simulation/Analysis/Synthesis of algorithms we covered in class, but were not part of the homework problems. In this case a physics accurate simulator is not necessary.
  • Reproduction of recently published results from recent (up to 5 years) conferences: WAFR, RSS, ICRA, IROS, DARS or AAMAS (see below for acronyms). 
  • A theoretical problem which could lead to publication.
    • Please schedule a meeting with me if you are interested in a project along these lines.
  • Build your own robot and perform motion planning and collision avoidance: These days anyone can get their hands on an inexpensive robot like AR DroneiRobot CreateArduino RobotLego Mindstorm and many more. Moreover, there are multiple robotics kits for DIY projects from companies like SparkFun or DFRobots

Remarks:

  • If your project involves implementation (simulation or a physical system), then the final product must be a working one.
  • If you decide to work on the something related to another project of yours, e.g., honors thesis, competition, etc., then you must demonstrate that this is something new that you have not be looking at. I will not accept projects which are just a rewriting of your prior or your current work. If such a submission is detected, then this is a violation of the academic integrity policy.

Project deliverables:

  • 1-2 page project proposal (due date posted on schedule). The proposal should include the following:
    • Introduction to general topic area that you are going to look into with a few bibliographic references on the background.
    • A precise problem description which also indicates which aspects of the course are relevant / will be used to solve the problem. Recall that that you need to demonstrate that at least 2 modules from the course will be relevant to your project.
    • An outline of what you plan to do to solve the problem and a schedule with the expected milestones. This section does not have to be very detailed since some of the topics are going to be covered later in the course.
    • The expected deliverables of the project.
  • An up to 2 page midterm progress report (due date posted on schedule). The progress report should discuss the following two items:
    1. What has been accomplished so far based on your initial plan.
    2. What are going to be your next steps. If there is a substantial change in your plans from your initial proposal, then the changes should be summarized and explained.
  • Any software developed (if applicable)
    • The code is going to be checked for plagiarism on Canvas and Moss (the latter is able to check structural similarities in code).
    • Note that you are allowed to use existing code as long as
      1. this is used as a library or a component in your system
      2. you clearly state your sources in your report
  • 4-10 page paper in IEEE conference format
    • The report is going to be checked for plagiarism on Canvas.
  • A project presentation using a poster in class on the final exam date.
    • Your presentation is going to be graded by the instructor (70%) and by your peers (30%) in terms of presentation according to the following criteria (organization, understanding of the material, visual quality of the slides and engagement of the audience). Further details on the criteria will be provided on Canvas.

Final Exam Policy (Choose between a term project and a final exam)

In class, closed book and closed notes. A cheat sheet may be allowed which must be hand written (the final decision on whether a cheat sheet will be permitted will be made one week before the final exam). Nothing else must be on your desks besides your pen and/or pencil. Not even scrap paper. For scrap paper you can use space on the exam booklet. Detailed instructions will be included in the Final Exam Review Notes. The final exam is cumulative. Topics and types of questions will be distributed on Canvas.

Some useful resources

Major robotics conferences:

  1. International Workshop on the Algorithmic Foundations of Robotics (WAFR)
  2. Robotics Science and Systems (RSS)
  3. International Conference on Robotics and Automation (ICRA)
  4. International Conference on Intelligent Robots and Systems (IROS)
  5. International Symposium on Distributed Autonomous Robotic Systems (DARS)
  6. International Conference on Autonomous Agents and Multiagent Systems (AAMAS)

Major journals and magazines (in no particular order):

  1. IEEE Robotics and Automation Magazine (This is a good source of papers which are authored for more general audiences).
  2. IEEE Transactions on Robotics (T-RO) 
  3. IEEE Transactions on Automation Science and Engineering 
  4. International Journal of Robotics Research
  5. Autonomous Robots

Useful tips:

Related robotics competitions:
Robot Simulators:
  • Webots : They offer a trial version for 30 days; I have some academic licenses if you would like to do your project in Webots.
  • Gazebo : The ultimate open source research grade 3D multiple robot simulator with dynamics
  • Stage : An open source 2D multiple robot simulator

Class evaluations and feedback

I take very seriously class evaluations and feedback. During the semester, I will be posting surveys on Canvas for feedback on both the course organization and the course content. I will appreciate it if you respond to these surveys. Ideally, the changes I implement will help you better succeed in the course. Responding to surveys counts toward to your class participation grade.

Finally, it is extremely important that you respond in the final anonymous survey solicited by the university at the end of the school year. The overall feedback helps me make changes for the next year.

Classroom Behavior

Cellphones, tablets and laptops are allowed in the class for enhanced classroom experience. However, all electronic devices must be muted during class to avoid causing distractions. In addition, if you have to arrive late or leave early from the class, then please make sure that you do not cause any distractions: Do not use the door near the instructor and choose a seat as close as possible to the door.

The use of recording devices is not permitted during class.  

Standard disclaimer: Any violent or threatening conduct by an ASU student in this class will be reported to the ASU Police Department and the Office of the Dean of Students.  

Academic Integrity

All students in this class are subject to ASU’s Academic Integrity Policy (http://provost.asu.edu/academicintegrity) and should acquaint themselves with its content and requirements, including a strict prohibition against plagiarism. All violations will be reported to the Dean’s office, who maintain records of all offenses. Students are expected to abide by the FSE Honor Code (http://engineering.asu.edu/integrity/).  


All your work for this course must be the result of your own individual effort or - when permitted - the result of your group. Having said that, you are allowed to discuss problems with your classmates or me, but you must not blatantly copy others' solutions. 


Copying (or slightly changing) solutions from online sources, other books or your classmates is easily detectable and not permitted. If such copying is detected, then a zero grade is applied to the respective assignment, a 6% penalty to the final grade for each violation, and a formal report will be filed! 


Do not forget that if you can find an answer online, then so can we! Use on-line sources for the homework and project only when explicitly allowed.

Attendance Policy & Makeup Exam Policy

I do not have an attendance policy. Come to class only if you like. Most of the material are available (or will be available) on-line. In theory, we only have to see each other during the final presentation.

However, if you skip classes, you do miss the chance for class-participation bonus.

If you cannot come to an exam, then I will need some back-up documentation from a third party, e.g., a doctor, to schedule a make-up exam. Accommodations will be made for religious observances provided that students notify me at the beginning of the semester concerning those dates. Students who expect to miss class due to officially university-sanctioned activities should inform me early in the semester.  Alternative arrangements will generally be made for any examinations and other graded in-class work affected by such absences, or other medical or personal emergency reasons. 

The preceding policies are based on ACD 304–04, “Accommodation for Religious Practices” and ACD 304–02, “Missed Classes Due to University-Sanctioned Activities.”

Grade Appeal Policy 

Any regrading appeal request must be initiated within 10 business days of receiving back your graded work by sending an email to the instructor and cc'ing the TA. We will not entertain any appeal right before, during or right after the class time since appeals are a time consuming process. 

Further details:

Sending the email is an important part of the process: Since we will be mostly grading the homework assignments algorithmically, if you think that your program is correct and that the autograder assigned a wrong grade, then in your email you must provide a brief explanation on why you think your program is correct. In that case, we will manually review your code. If your code is partially correct, but you received an unreasonably low grade when compared to the grading criteria posted on the homework instructions, then let us know so we can review your case. It may very well be the case that we have missed some partial credit cases and the autograder defaulted to the lowest possible partial credit value. 

General guidelines:

  1. If you need to understand the technical reasons on why points were reduced on homework problems, then please see the TA first. If you are not satisfied with the answer, then make an appointment with the instructor.  
  2. If you need to understand the technical reasons on why points were reduced on exams, then you may visit the instructor first. 
  3. For all other issues, please contact the instructor first.

Grievances 

If any issues arise with the course during the semester, then please follow these steps:

  1. See the instructor during office hours or by making an appointment
  2. If not satisfied with the proposed solution, then please make an appointment with the advising office
  3. If not satisfied with the proposed solution, then make an appointment with the CIDSE director

Disability Accommodations

Suitable accommodations will be made for students having disabilities. Students should notify the instructor as early as possible if they will require same. The students must be registered with the Disability Resource Center and provide documentation to that effect. 

For further information, please visit the website of the ASU Disability Resource Center at

https://eoss.asu.edu/drc/

Sexual Discrimination

Title IX is a federal law that provides that no person be excluded on the basis of sex from participation in, be denied benefits of, or be subjected to discrimination under any education program or activity.  Both Title IX and university policy make clear that sexual violence and harassment based on sex is prohibited.  An individual who believes they have been subjected to sexual violence or harassed on the basis of sex can seek support, including counseling and academic support, from the university.  If you or someone you know has been harassed on the basis of sex or sexually assaulted, you can find information and resources at 

https://sexualviolenceprevention.asu.edu/faqs

As a mandated reporter, I am obligated to report any information I become aware of regarding alleged acts of sexual discrimination, including sexual violence and dating violence. ASU Counseling Services, 

https://eoss.asu.edu/counseling

is available if you wish discuss any concerns confidentially and privately.

Copyright

All contents of these lectures, including written materials distributed to the class, are under copyright protection. Notes based on these materials may not be sold or commercialized without the express permission of the instructor. You may want to review ACD 304-06.