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. Check out the graduate list of courses:

https://ras.engineering.asu.edu/courses/

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 CSE 325 or CSE 438.

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.

Current & Previous course offerings

This may change between different class offerings. The following is a potential list of textbooks.

• [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.
• [LaValle 2006] S. M. LaValle, "Planning algorithms", Cambridge University Press, 2006.
• [Siegwart et al 2011] Siegwart, Nourbakhsh, and Scaramuzza, "Introduction to Autonomous Mobile Robots", MIT Press, 2011

• [Lee & Seshia] Lee & Seshia, "Introduction to embedded systems", on-line
• [Astrom & Murray 2008] Astrom and Murray, "Feedback Systems: An Introduction for Scientists and Engineers", Princeton University Press, 2008;

Some useful resources

Major robotics conferences:

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

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.

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

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:

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.

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.