CSE494: Introduction to Mobile Robotics

Updates

2015.11.04

  • Late submission policy explicitly stated
2015.09.09 
  • Optional final exam policy 
  • Broken links on main textbooks
  • Added links to robot simulators


 
Multi-iRobot scenario
 
NAO driving a BMW

 
NAO Robosoc team

Introduction

These days anyone can get their hands on an inexpensive robot like AR Drone, iRobot Create, Arduino Robot, Lego Mindstorm and many more. Moreover, there are multiple robotics kits for DIY projects from companies like SparkFun or DFRobots. But how can you make the robot of your dreams operate autonomously? 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 term 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.


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.


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 (of mainly graduate level) courses that cover all the aforementioned topics in detail.


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

  • Class: Tuesday and Thursday 12:00pm-1:15am, BYENG 510
  • Instructor: Georgios Fainekos (fainekos at asu)
  • Office hours: By appointment or check my scheduled office hours on my calendar.
  • Office: Centerpoint 203-17
  • Teaching assistant: No one (currently) 
  • Announcements will only be posted on blackboard (sometimes also in class on the slides).
  • On-line discussions will take place at Piazza.
  • 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 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

Recommended prerequisites

Even though I plan to provide primers in the following topics, this is a list of courses which if you have not taken before you may have hard time keeping up with the material in this course:
  1. Probability and statistics
  2. Calculus 
  3. Data structures
  4. Linear algebra
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. The more courses you have taken from the following list, the easier this course will be. In no particular order: graph algorithms, computational geometry, ordinary differential equations, artificial intelligence, machine learning, linear and non-linear control systems and optimal control.

Textbooks & Readings

We will closely follow the main textbooks below, usually, in complementary ways. Sensors, feedback control and embedded systems topics will be covered using the textbook by Lee & Seshia. 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 45% 
      • You may form discussion groups for the HW problems of up to 3 members. However, the HW submission will be individual and you must mention the members of the discussion group on your submission. You can join a HW group on Blackboard. The HW groups are not monitored.
    2. Class project or final exam 45%
      • You have the choice of proposing and implementing an open ended project or 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 continuing activity throughout the semester.
  • 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, a penalty of -min(50,5*days) percentage points will be applied to your score. Here, days is the number of days the assignment is late. The deadline to submit late work or re-submit 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 during my office hours before you submit your proposal.

Project ideas:

  • Take the Mission On Mars Robot Challenge. The files are provided on Blackboard.
  • 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
    • 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.

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.   

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 through SafeAssign on Blackboard 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 through SafeAssign on Blackboard.
  • A project presentation or poster in class towards the end of the semester.
    • Your talk is going to be graded by the instructor (30%) and by your peers (70%) 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 Blackboard.

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 Blackboard.

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 Blackboard 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.

Plagiarism Policy

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 friends is easily detectable and not permitted. 


If such copying is detected, then a zero grade is applied to the respective assignment, -5% to the final grade and a formal report will be filed! 


Do not forget that if you can find an answer online, then so can we! Actually, if there is an answer on-line, then we download 10 versions and we check your answers for copying. Use on-line sources for the homework and project only when explicitly allowed.

Special Needs

If you are entitled to extra accommodation for any reason (such as a disability), I will make every reasonable attempt to accommodate you. However, it is your responsibility to discuss this with the instructor at the beginning of the course. For further information, please visit the website of the ASU Disability Resource Center at

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

Title IX

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 

http://sexualviolenceprevention.asu.edu/faqs/students.