Welcome to CS 294-115 Algorithmic Foundations of Human-Robot Interaction, Fall 2017!

Instructor: Anca Dragan (anca at berkeley dot edu)

Lectures: TuThu, 12:30-2:00, Soda 310


As robot autonomy advances, it becomes more and more important to develop algorithms that are not solely functional, but also mindful of the end-user. How should the robot move differently when it's moving in the presence of a human? How should it learn from user feedback? How should it assist the user in accomplishing day to day tasks? These are the questions we will investigate in this course.

We will contrast existing algorithms in robotics with studies in human-robot interaction, discussing how to tackle interaction challenges in an algorithmic way, with the goal of enabling generalization across robots and tasks. We will also sharpen research skills: giving good talks, experimental design, statistical analysis, literature surveys.

Format: This course combines lectures with paper presentations by the students, encouraging both fundamental knowledge acquisition as well as open-ended discussions. Each student will also carry out an individual research project OR an in-depth literature survey.

Learning objectives: At the end of this course, you will have gained both knowledge/abilities related to human-robot interaction, as well as to research and presentation skills:

    [Human-robot interaction abilities]
  • articulate the challenges of developing algorithms that support HRI
  • apply optimization techniques to generate motion for HRI
  • contrast and relate model-based and model-free learning from demonstration
  • apply Bayesian inference and learning techniques to enhance coordination in collaborative tasks
  • develop a basic understanding of verbal and non-verbal communication
  • ground algorithmic HRI in the relvant psychology background
    [Research skills]
  • communicate scientific content to a peer audience
  • analyze and diagram the literature related to a particular topic
  • critique a scientific paper's experimental design and analysis

Prerequisites: There are no official prerequisites but a knowledge of probability and multivariate calculus is expected.


  • Student Presentations (30%): Each student will get the opportunity to present multiple times. You will be graded based on your level of insight into the material (including how well you answer questions from us and the rest of the class), how well you relate the paper to other papers and lecture material, as well as how well you present the material to the class. There will be 2 presenters for each paper: a PRO presenter and a CON presenter. We will have 2-3 papers per lecture.
  • Quizzes (20%): We will have a short (10 min) quiz before each lecture/set of presentations, to test the understanding of the material. These quizzes are not meant to be onerous, but are meant to ensure that you read carefully through the papers. They are graded with a check, a minus, or a plus for particularly good answers.
  • Final Project (35%): You have a choice between a research project, and an in-depth literature survey (~50 relevant papers, organized by different features, identifying gaps in the state of the art). You will have a final presentation, and submit a proposal along the way (1 page) and a report (up to 5 pages) at the end.
  • Participation (15%): Be engaged! Ask and answer questions!
  • Scribing (5% extra credit): You will compile PDFs of lecture notes. The scribe template is here. Send an email to anca at berkeley dot edu with the tex and pdf.
  • Important: Despite these percentages, you will not pass this class if you don't submit a proposal and a final report for your project, if you don't present your final project, or if you don't show up for class regularly (even if your computed final score is above passing).
  • Expectations: You can expect me to start and end class on time, devise quizzes that adequately cover the material, and grade your quizzes and send you feedback on your presentations in a timely manner. In turn, I can expect you to come to class on time, be attentive and engaged in class, and refrain from using laptops, cell phones and other electronic devices during class. Please take notes, and ask questions when something is not clear. I also expect you to spend an adequate amount of time on the readings each week (at least 3 hours), and spend 60 hours on your final project.

    Important dates:

  • 1 Nov - 1 Page Proposal (by this time you should have a clear idea of what you want to do and what your key insight is in the case of a project, and how you will select and classify papers in the case of a literature survey); Feel free to email me to discuss project ideas! We will also have office hours dedicated to this.
  • 28 & 30 Nov - Final Presentations
  • 10 Dec - Final Reports (start gearing up for a paper submission)
  • Project Proposal Instructions: They should be 1 page (+ references).
    If you are doing a research project:

    • motivate the problem
    • briefly describe how state of the art tackles it and what is missing
    • state your key insight
    • scope your project to be what you would do for 1 paper; you don't have to have all results for the project, you can have just preliminary result at the end of the semester, but choose a problem that is not trivial and not a PhD thesis either

    If you are doing a literature survey:
    • describe the topic
    • describe how you will find papers -- what proceedings will you search, what keywords on google scholar, what starting papers;
    • what are the inclusion criteria -- how are you going to decide whether to include a paper or not
    • provide 5-10 initial papers
    • provide the groups/axes/independent variables you want to use to categorize the field

    Possible venues for projects:

  • Conference Papers: RSS, IROS, Ro-Man
  • Short Papers: CHI Late Breaking Report, HRI Late Breaking Report
  • Schedule: Find a tentative schedule below. This is subject to change.

    # Day Date Topic Reading Comments Notes
    1 Th 24 Aug The What, Why, and How of Algorithmic HRI no mandatory reading
    2 Tu Aug 29 Motion Planning 1 (lecture) no mandatory reading, but read these after Motion Planning is done if interested:
  • Lozano-Perez "Spatial Planning: A Configuration Space Approach"
  • Kavraki "Analysis of Probabilistic Roadmaps for Path Planning"
  • Lavalle "Randomized Kinodynamic Planning"
  • Hsu "Path Planning in Expansive Configuration Spaces"
  • notes
    3 Th Aug 31 Motion Planning 2 (lecture) more on graph search here and here notes
    4 Tu Sep 5 Motion Planning 3 (lecture) more on randomzied sampling:
  • RRT Connect
  • (Epsilon,Alpha,Beta)-Expansiveness
  • constraints
  • notes
    5 Th Sep 7 Trajectory Optimization 1 (lecture) no mandatory reading notes
    6 Tu Sep 12 Trajectory Optimization 2 (lecture) no reading notes
    7 Th Sep 14 Trajectory Optimization 3 (lecture) no mandatory reading,
  • Zucker "CHOMP: Covariant Hamiltonian Optimization for Motion Planning"
  • notes
    8 Tu Sep 19 Optimal Motion Algorithms (papers)
  • "Elastic Bands: Connecting Path Planning and Control" (1993) pdf [Liting Sun]
  • "Finding Locally Optimal, Collision Free Trajectories with Sequentional Qadratic Programming" (2014) pdf[Jason Zhang]
  • 9 Th Sept 21 Optimal Motion in HRI (papers)
  • "Planning human-aware motions using a sampling-based costmap planner" (2011) link[David Chan]
  • "Generating Human-Like Motion for Robots" (2013) pdf[Bala]
  • [Tools of HRI]
    10 Tu Sept 26 Experimental Design (lecture) no reading notes
    11 Th Sept 28 Experimental Design Ctd. (lecture) no reading notes
    12 Tu Oct 3 Experimental Design Ctd (lecture) no mandatory reading
  • "Evaluating Fluency in Human-Robot Collaboration" (2013) pdf
  • notes
    [Learning from Demonstration]
    13 Th Oct 5 Inverse Reinforcement Learning (lecture) no mandatory reading
  • "Maximum Margin Planning" (2006) link
  • "Maximum Entropy IRL" (2010) pdf
  • "Learning Attractor Landscapes for Learning Motor Primitives" (2003) pdf
  • "Movement Primitives via Optimization" (2015) pdf
  • notes
    14 Tu Oct 10 LfD in Psychology (papers)
  • "Understanding Intentions of Others" (1995) pdf [Monica Gates]
  • 2 short papers: "Infant Imitation After a 1-Week Delay" (1988) pdf1 ; "Rational Imitation in Preverbal Infants" (2002) pdf2[JIachen Wang]
  • 15 Th Oct 12 LfD Algorithms (papers)
  • "Socially Compliant Navigation via IRL" pdf[Xuan Chen]
  • "Predicting Human Reaching Motion" (2015) pdf[Andrew Barkan]
  • 16 Tu Oct 17 LfD in HRI (papers)
  • "Trajectories and Keyframes for Kinesthetic Teaching" (2012) pdf[Ravi Pandya]
  • "Designing Robot Learners that Ask Good Questions" (2012)pdf[Samee Ibraheen]
  • further reading:
  • "Using Perspective Taking to Learn from Ambiguous Demonstrations" (2006) pdf
  • 17 Th Oct 19 No Class
    18 Tu Oct 24 Intent Inference (lecture) no mandatory reading
  • "Planning Based Prediction for Pedestrians" (2009)pdf
  • "Goal Inference as Invese Planning" (2007) pdf
  • "Obsessed with Goals" (2007) pdf
  • 19 Th Oct 26 Recap
    20 Tu Oct 31 Intent Inference Algorithms (papers)
  • "Shared Autonomy via Hidsight Optimization" (2015) link[Jianlan Luo]
  • "Intention-Aware Motion Planning" (2013) pdf[Roshan]
  • 21 Th Nov 2 Intent Expression (papers)
  • "Anticipation in Robot Motion" (2011) pdf[McKane]
  • "Manipulating Mental States through Physical Action" (2014) pdf[Vijay]
  • 22 Tu Nov 7 Intent in HRI (papers)
  • "Improving Robot Readability" (2011) pdf [?]
  • "Communication of Intent in Assistive Free Flyers" (2014) pdf[Jae Pil]
  • [Coordination]
    23 Th Nov 9 Interaction as a Game (lecture) no madatory reading
  • formalism and examples
  • 24 Tu Nov 14 Human-Robot Collaborative Learning (papers)
  • Cooperative IRL (2016) link[Andy]
  • "CrossTraining" (2013) pdf [Isabella]
  • 25 Th Nov 16 Robot Influence on Human Actions (papers)
  • Influence-aware planning (2016) link[Ellis Ratner]
  • "Mutual Adaptation" (2016) pdf[Ashish Kumar]
  • 26 Tu Nov 21 Communication beyond Motion or Intent (papers)
  • "Learning Behavior Styles" (2010) pdf[Corten Singer]
  • "Asking for Help Using Inverse Semantics" (2014) pdf [Stepher Hansen]
  • further reading:
  • "Knowledge and Implicature" (2013) pdf
  • "Coordination Mechanisms for Human-Robot Collaboration" (2013) pdf
  • "Conversational Gaze Aversion" (2009) link
  • "Robot Deictics" (2014) pdf
  • 27 Th 23 Nov Thanksgiving
    28 Tu 28 Nov Project Presentations
    29 Th 30 Nov Project Presentations

    For more readings, check out a few other class websites (this is by no means a comprehensive list):

  • Cooperative Machines (MIT)
  • Human-Robot Interaction (GaTech)
  • Human-Robot Interaction (UW)
  • Manipulation Algorithms (CMU)