Dissertation data driven derivation of skills for autonomous

DATA-DRIVEN DERIVATION OF SKILLS FOR AUTONOMOUS HUMANOID AGENTS by Odest Chadwicke Jenkins A Dissertation Presented to the FACULTY OF THE GRADUATE SCHOOL UNIVERSITY OF SOUTHERN CALIFORNIA In Partial Fulfillment of the Requirements for the Degree DOCTOR OF PHILOSOPHY (COMPUTER SCIENCE) December 2003 Copyright 2003 Odest Chadwicke Jenkins Acknowledgements My experiences leading to the completion of this dissertation have been extremely re- warding, but also a tremendous amount of work. Along the way, I have benefited from the guidance, support, and camaraderie of many individuals, whom I now acknowledge and thank. I would like to first thank my parents, Odest Charles Jenkins and Dr. Nadine Francis Jenkins, and family for raising me to be a conscientious individual and for being a con- tinual source of encouragement in my endeavors.

Thanks for being patient with me. It is difficult for me to imagine how I could have come this far without the help of my wife Sarah. She has been an invaluable companion and partner who has supported and tol- erated me throughout my time as a graduate student, especially near deadlines. Thanks for buffering me from the rigors of daily life.

I consider myself fortunate for having had Professor Maja Matarić serve as my advisor and collaborator over the past four years. I thank Maja for providing me with direction and inspiration in my research while remaining open to my ideas and encouraging me to speak my mind. I have appreciated Maja setting a high bar in her expectations of me, even when they are the source of our “discussions”. ii I am grateful to the members of my defense and proposal committees for their time, consideration, and constructive feedback towards developing my dissertation.

Specifically, I thank Professor Stefan Schaal for being an excellent teacher and exposing me to the benefits of machine learning, Professor Carolee Winstein for helping me relate my work to fields outside of robotics and computer science, Professor Ulrich Neumann for insights into evaluating my methodology, and Professor William Swartout for valuable comments on improving the presentation of my work and its relationship to computer animation. My time at USC would not have been the same without the various friends (and accomplices) that I have met along the way. While a plethora of great work is produced in our robotics lab, it would not be possible without the underappreciated and less glam- orous (if that is possible) work of our administrative staff, Kusum Shori, Angela Megert, and Aimee Barnard. I particularly thank Angie for sharing a common vision and the frustrations that come with trying to improve the status quo.

Thanks to a selfless friend, Monica Nicolescu, who has helped me throughout my time in the lab and shared in the work and frustrations of graduate student life. I appreciate that Monica has always been available for a spontaneous venting session. Thanks to Brian “Beef” Gerkey for all his help over the years as our de facto sys admin, for engaging conversations about the state of the world (keep fighting The Man, brother), and for giving me a reason to brave the west side. Thanks to Andrew Howard for being a continual source of valued criticism, a role model for me as a scientist, and a really smart dude.

Thanks to a great friend and my favorite sounding board for ideas, Gabriel Brostow, whose enthusiasm and drive has been infectious. Thanks to one of the most prepared people that I know, Dani Goldberg, for showing me how to be a successful iii Ph. student while maintaining a sense of fun. I am grateful to have collaborated with excellent humanoid robotics researchers in our lab, including: Stefan Weber whose free- spirited energy helped establish the fun atmosphere of the lab, Ajo Fod who was the other original inhabitant of the Beefy Lounge, Chi-Wei (Wayne) Chu who has braved the inner depths of my programming and survived, Evan Drumwright whose sense of humor is like multiple pieces of genius.

Thanks also to fellow humanoids Amit Ramesh and Marcelo Kallmann. I have benefited from my interactions with the faculty and postdocs in the USC Robotics Labs including Professor Gaurav Sukhatme, Richard Vaughan, Paolo Pirjanian, Ash Tews, and Torby Dahl. The Robotics Lab has been a fun environment to work in because of people such as Jacob Fredslund, Kasper Stoy, Esben Ostergaard, the ultimate hoop warrior Chris Vernon Jones, Jens Wawerla, Helen Yan, the always dapper, witty, and “rispiktfil” Dylan “Lord Flexington” Shell, Nate Koenig, Kale Harbick, and Gabe Sibley. I also thank Doug Fidaleo and the people of CGIT who showed me why an RV is not a good idea for going to conferences, Mircea Nicolescu for making soccer enjoyable, Alex Francois for introducing me to rugby, Kaz Okada for invaluable pointers to various dimension reduction techniques, and Didi Yao and other my colleagues in the CSGO.

I am grateful to Jessica Hodgins for giving me my start as a robotics researcher in the Animation Lab while at Georgia Tech and providing motion data that were critical in evaluating my work. Thanks to the Mathematics and Computer Science Department at Alma College for the personal attention and interest in my academic development as an undergraduate and for giving me the confidence to pursue graduate studies. While iv at Alma, I was fortunate to have met my friend James Blum, whose constant drive for innovation and finding solutions has been an example for my direction as a computer scientist and a leader. Big ups to Roger the Sealion.

The research reported in this dissertation was conducted at the Robotics Research Laboratory in the Computer Science Department at the University of Southern California and supported in part by the USC All-University Predoctoral Fellowship, DARPA MARS Program grants DABT63-99-1-0015 and NAG9-1444 and ONR MURI grants N00014-01- 1-0354 and SA3319. v Contents Acknowledgements ii List Of Tables ix List Of Figures x Abstract xvi 1 Introduction 1 1.1 Aims and Motivation .2 General Approach to Autonomous Humanoid Control .3 Issues in Developing Humanoid Capabilities .1 Modularity for Autonomous Humanoid Control .2 Representing Motion Capabilities .2 Hidden Markov Models .3 Linear Dimension Reduction .4 Nonlinear Dimension Reduction .4 Motivation from Neuroscience .5 Acquisition of Human Motion. 43 3 Spatio-temporal Isomap 44 3.1 Linear Dimension Reduction .1 Principal Components Analysis .2 Independent Components Analysis .2 Nonlinear Dimension Reduction .2 Principal Curves and Piecewise PCA .4 Local Spectral Dimension Reduction .5 Multidimensional Scaling and Global Spectral Dimension Reduction .3 Spatio-Temporal Isomap .1 The Extendability of Isomap .2 Issues in Applying and Extending Isomap .3 Incorporating Temporal Dependencies .1 Common Temporal Neighbors .4 Sequentially Continuous Spatio-temporal Isomap .5 Sequentially Segmented Spatio-temporal Isomap. 71 4 Performance-Derived Behavior Vocabularies 73 4.1 What is a Behavior Vocabulary? .2 Motion Performance Preprocessing .3 Kinematic Centroid Segmentation .3 Grouping Primitive Behavior Exemplars .4 Generalizing Primitive Feature Groups .5 Deriving Meta-level Behaviors .1 Input Motion Descriptions .2 Behavior Vocabulary Derivation Results .1 Grouping Exemplars into Features .2 Primitive Eager Evaulation .3 Meta-level Convergence .3 Individual Activity Isolation .4 Humanoid Agent Control .5 Synthesized Motion Feedback .1 Consistency and Sensibility in Motion Preprocessing .2 Parameter Tuning for ST-Isomap and Exemplar Grouping .3 Splitting and Merging of Feature Groups .4 Temporal Neighbors vs.5 Primitive Behavior Generalization .1 Support Volume Coverage for Primitive Flowfields .7 When is PCA or Spatial Isomap Appropriate For Motion Data?.

142 6 Applying Behavior Vocabularies to Movement Imitation 144 6.1 Motion Synthesis from a Vocabulary .2 Classification of Motion into a Vocabulary .1 Imitation through Trajectory Encoding .2 Imitation through Controller Encoding .1 Avenues for Further Research. 159 Reference List 160 Appendix A Collecting Natural Human Performance .1 Kinematic Model and Motion Capture .1 Volume Sequence Capture .2 Nonlinear Spherical Shells .3 Model and Motion Capture .4 Results and Observations .5 Extensions for Continuing Work .2 Embedded Motion Capture from Sensor Networks. 183 Appendix B Applying Spatio-temporal Isomap to Robonaut Sensory Data. 191 viii List Of Tables 2.1 Script of performed activities for Input Motion 1.

This scripts lists manu- ally assigned descriptions of activities, interval of performance, and number of segments from manual segmentation.2 Statistics about the segments produced by each segmentation method for each input motion without global position and orientation. The statistics for each segmentation specify the number of segments produced, mean seg- ment length, standard deviation of the segment lengths, minimum segment length, and maximum segment length.3 Number of primitives derived for each input motion and each segmentation procedure. 126 ix List Of Figures 1.1 Humanoid agents can be physically embodied, as with the NASA Robo- nauts [1] (left), or virtually embodied in physical simulations, as with Ado- nis [91] (center) and Zordan’s boxing simulation [148] (right).2 Our general approach to autonomous humanoid control consists of: i) an agent plant as the embodied interface to the world, ii) motor level sens- ing and actuation for achieving desired static configurations, iii) skill level capabilities for setting configurations over time according to a motor pro- gram, and iv) task level controllers for directing skills to achieve the ob- jectives of the agent.3 Examples of functionality modes for interfacing with a vocabulary of skill level capabilities. These modes include abstracting motor level functions, supporting task level functions, and encoding skill level interactions.

Re- gardless of functionality, the underlying skill behaviors should not change.1 Performance-Derived Behavior Vocabularies consist of four main steps: preprocessing, exemplar grouping, behavior generalization, and meta-level behavior grouping. Preprocessing produces a data set of motion segments from real-world human performance. Exemplar grouping uses spatio-temporal Isomap to cluster motion variations of the same underlying behavior. Ex- emplars of a behavior are generalized through interpolation and eager eval- uation.

Compositions of primitive behaviors are found as meta-level be- haviors by iteratively using spatio-temporal Isomap.2 Z-function segmentation of a motion stream. The value of the z-function is plotted over time. Horizontal lines are various thresholds considered based on proportions of the maximum, mean, and median value of the function. The thick line, representing 2 times the mean of the function, was used as the threshold.

Dots indicate segment boundaries based on this threshold.3 Kinematic centroid segmentation for one segment of a motion stream. (a) A visualization of the motion being segmented with the spheres indicating the trajectories of the shoulders (blue), kinematic centroids (red), and end-effectors (magenta) of the right and left arms. (b-d) Plots of the offset distance for the kinematic centroid of the right arm for three motion segments. The points on these plots indicate the beginning of the current segment, passing of the “large motion” threshold, and placement of the next segment boundary, respectively.4 A primitive flowfield for a horizonal arm waving behavior.

The flowfield moves forward from black to red, with exemplars in blue. Motion for selected exemplars of this primitive are shown.1 (a) A snapshot of the human performer instrumented with reflective mark- ers during the execution of a demonstration motion stream. (b) A visual- ization of the human performer’s kinematics at the time of the snapshot using the post-processed motion stream.2 Results of first (left column) and second (right column) level exemplar grouping for Input Motion 1. (a,b) Distance matrices produced by ST- Isomap.

(c,d) Embeddings produced (blue line) and feature groups (color coded spheres) found by ST-Isomap. (e,f) Transition probabilities between pairs feature groups.3 Results of first (left column) and second (right column) level exemplar grouping for Input Motion 2. (a,b) Distance matrices produced by ST- Isomap. (c,d) Embeddings produced (blue line) and feature groups (color coded spheres) found by ST-Isomap.

(e,f) Transition probabilities between pairs feature groups.4 Results of first (left column) and second (right column) level exemplar grouping for Input Motion 3. (a,b) Distance matrices produced by ST- Isomap. (c,d) Embeddings produced (blue line) and feature groups (color coded spheres) found by ST-Isomap. (e,f) Transition probabilities between pairs feature groups.5 3D embeddings of Input Motion 1 and 3 using (a,b) PCA, (c,d) spatial Isomap, and (e,f) spatio-temporal Isomap.

Distances matrices for (g,h) the disconnected components of spatial Isomap and (i,j) the single connected component of spatio-temporal Isomap.