CSE591: Introduction to Algorithmic Robotics

Introduction

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 provides
a principled and mathematically sound approach to the design of algorithms for robots rather than ad-hoc and hacking development approaches. The students in this course will acquire the mathematical foundations that are required for the design and analysis of algorithms for robotic applications. Among the course goals is the development of the vocabulary and mathematical background so the students can follow the related cutting edge research literature.

In particular, we will study:
  1. Complexity Analysis of Algorithms (brief introduction/review): What is an algorithm? Is an algorithm that you have developed efficient and correct? 
  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. Workspace and configuration space: What are the workspace and configuration spaces of a robot? How can we create discrete abstractions and cell decompositions for motion planning, sensor placement, coverage etc?
  4. Continuous planning (using sampling based methods): How do we move a robot with complex kinematic and dynamic constraints in an environment with obstacles? What is the theoretical complexity of motion planning?
  5. Sensing and localization: How do we model uncertainty in sensing? How does the robot know where it is?
  6. Planning under uncertainty: Given the sensor inaccuracies and localization uncertainty, how do we plan the actions of our robots?
  7. Topics in algorithmic robotics: (1) temporal logic motion planning and re-planning, (2) multi-robot issues: decentralized control, consensus, etc, (3) warehouse robotics and automation, (4) software quality assurance in robotics, (5) other topics based on the research interests of the students attending the class.

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


What this course is not about: This course does not cover electromechanical design of robots, computer vision, natural language processing, human-machine interaction and real-time embedded system/programming issues. The course only partially touches upon some topics that relate to feedback control, machine learning and artificial intelligence. Actually, ASU offers a variety of courses that cover all the aforementioned topics in detail and you are advised to take these courses as well.


Disclaimer


This is a live web-page so please check it frequently. Moreover, the course is currently under development. Therefore, it is recommended only to adventurous students who can excel within non-fully structured environments. On the other hand, the students who take the class will be introduced to advanced concepts in algorithmic robotics.

Logistics

  • Class: Tuesday and Thursday 09:00am-10:15am, BYENG M1-09
  • Instructor: Georgios Fainekos (fainekos at asu)
  • Office hours: By appointment or check my scheduled office hours on my calendar.
  • Office: BYENG M1-12
  • Teaching assistant TBD. 
  • Announcements will only be posted on blackboard (sometimes also in class on the slides).

Prerequisites


You must have taken a course on probability theory and calculus. An introductory course in algorithms is recommended, but it is not necessary. We are going to provide a brief review of the concepts needed in order to understand and analyze simple algorithms.

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 textbooks by Choset et. al and by LaValle, usually, in complementary ways. Furthermore, research papers will be recommended for cutting edge research topics.
  • Additional References:
    • [R1] Ghallab, Nau and Traverso, "Automated Planning", Elsevier, 2004
    • [R2] Cassandras and Lafortune, "Introduction to Discrete Event Systems, Springer 2007
    • [R3] Thrun, Burgard and Fox, "Probabilistic Robotics", The MIT Press, 2005
    • [R4] de Berg, et. al., "Computational Geometry: Algorithms and Applications", Springer-Verlag, 2000
    • [R5] Murray, Li, and Sastry, "A mathematical introduction to robotic manipulation", CRC Press, 1994.
    • [R6] Astrom and Murray, "Feedback Systems: An Introduction for Scientists and Engineers", Princeton University Press, 2008; 

Grading

Grades will be based on:

  • The following grading scheme will be used for the in class section: 
    1. 3-6 homeworks 40% 
      • 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.
      • No homework assignments will be accepted after the due date/time!
    2. Class project 40%
      • See below for details
    3. Cutting edge literature review and presentation 20%
      • See below for details
    4. Class participation
      • If you are within 1% point of moving to a higher letter grade, then class participation can help you. 
      • 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 the discussion board
        • Active discussion in class on the lecture material
      • 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.

Project description

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. The project option can be used by MCS students for their project portfolio. No group projects will be allowed unless you have a provide a detailed work plan for each group member and I approve it.

Project ideas:

  • Literature review from last WAFR, RSS, ICRA, IROS. For the literature review you will have to select 3 papers, summarize them and then compare the advantages and disadvantages of each approach. If the papers contain experimental results, then it will be appropriate to validate their results with an implementation of your own. Simply copying or permutating the text of the original papers is not acceptable and it will be considered plagiarism!
  • Modeling/Simulation/Analysis/Synthesis of algorithms we covered in class or more advanced follow-up work from a conference.
  • Implementing some of the algorithms we did in class on a real robot (either in my lab or with your own equipment).
  • A theoretical problem which could lead to publication
    • Please schedule a meeting with me if you are interested in a project along these lines
  • Something related to your own research/work
    • You must demonstrate that you are using at least 2 topics from the list in the Introduction above. 
    • This must not be previously published work of yours (this is going to be automatically verified) or unpublished on-going research effort (this is going to be checked with your research adviser).

Remarks:

  • More detailed project ideas and instructions will be posted on Blackboard.
  • 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 your project than 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 you prior or current research 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.
  • A 2 page midterm progress review (due date posted on schedule).
  • 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
  • 6-10 page paper in IEEE conference format
    • The report is going to be checked for plagiarism through SafeAssign on Blackboard.

Paper review and presentation

Since this is a research seminar level course, you will have to read and present a cutting edge research paper. You will have to choose a paper from the most recent conferences (in no particular order):

  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. InternationalConference on Intelligent Robots and Systems (IROS)

or 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

and give a presentation in class. 

Some useful resources:

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.

Plagiarism Policy

Your work for this course must be the result of your own individual effort. 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. If the latter copying is detected the worst credit will be split among the perpetrators, or worse! Also, if you can find an answer online, then so can I!

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.