Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Design and optimization of control primitives for simulated characters Shen, Shuo 2013

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata


24-ubc_2014_spring_shen_shuo.pdf [ 2.19MB ]
JSON: 24-1.0165691.json
JSON-LD: 24-1.0165691-ld.json
RDF/XML (Pretty): 24-1.0165691-rdf.xml
RDF/JSON: 24-1.0165691-rdf.json
Turtle: 24-1.0165691-turtle.txt
N-Triples: 24-1.0165691-rdf-ntriples.txt
Original Record: 24-1.0165691-source.json
Full Text

Full Text

Design and Optimization of Control Primitives forSimulated CharactersbyShuo ShenDual B. S. in Computer Science, Zhejiang University and Simon FraserUniversity, 2011A THESIS SUBMITTED IN PARTIAL FULFILLMENTOF THE REQUIREMENTS FOR THE DEGREE OFMaster of ScienceinTHE FACULTY OF GRADUATE AND POSTDOCTORALSTUDIES(Computer Science)The University Of British Columbia(Vancouver)December 2013c? Shuo Shen, 2013AbstractPhysics-based character motion has the potential of achieving realistic motionswithout laborious work from artists and without needing to use motion capturedata. It has potential applications in film, games and humanoid robotics. However,designing a controller for physics motions is a difficult task. It requires expertisein software engineering and understanding of control methods. Researchers typ-ically develop their own dedicated software framework and invent their own setsof control rules to control physics-based characters. This creates an impedimentto the non-expert who wants to create interesting motions and others who want toshare and revise motions. In this thesis, we demonstrate that a set of motion prim-itives that have been developed in recent years constitute effective building blocksfor authoring physics-based character motions. These motion primitives are madeaccessible using an expressive and flexible motion scripting language. The motionlanguage allows a motion designer to create controllers in a text file that can beloaded at runtime. This is intended to simplify motion design, debugging, under-standing and sharing. We use this framework to create several interesting 2D planarmotions. An optimization framework is integrated that allows the hand-designedmotion controller to be optimized for more interesting behaviors, such as a fastprone-to-standing motion.We also develop a state-action compatibility model for adaping controllers tonew situations. The state-action compatibility model maintains a hypervolume ofcompatible states (?situations?) and actions (controllers). It allows queries for com-patible actions given a state.iiPrefaceThe CMA-ES algorithm described in Chapter 5 was originally developed by N.Hansen and A. Ostermeier [19], and further explained in [1, 3]. In Chapter 6, thequery algorithm is based on the diversity optimization algorithm developed by S.Agrawal, S. Shen and M. van de Panne [7]. Several figures and part of texts fromthis thesis are copyright and are reused in this thesis by permission. Figure 1.1 isrecreated from [6]. Figure 5.1 is adapted from Wikepedia [1]. Figures with thephrase ?used with permission? in the caption are used with permission from theauthors of the cited papers. The rest of the work is original and it was developedby the author Shuo Shen who discussed with Dr. Michiel van de Panne.iiiTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiAcknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.2 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.3 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.1 Inverse Dynamics Based Methods . . . . . . . . . . . . . . . . . 62.2 Finite State Machine (FSM) Based Controllers . . . . . . . . . . . 83 Motion Primitives . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103.1 PD Control on Joints . . . . . . . . . . . . . . . . . . . . . . . . 113.2 Virtual Force . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133.3 Gravity Compensation . . . . . . . . . . . . . . . . . . . . . . . 153.4 Quiescent Stance Balance Feedback . . . . . . . . . . . . . . . . 16iv3.5 Inverse Kinematics . . . . . . . . . . . . . . . . . . . . . . . . . 163.6 Phase Transition Models . . . . . . . . . . . . . . . . . . . . . . 184 Simple Controller Language (SCL) Framework . . . . . . . . . . . 194.1 Character Definition . . . . . . . . . . . . . . . . . . . . . . . . . 204.2 Specification of Phases and Phase Transitions . . . . . . . . . . . 224.3 Motion Primitive Specifications . . . . . . . . . . . . . . . . . . 254.4 Motion Design Workflow . . . . . . . . . . . . . . . . . . . . . . 284.5 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294.5.1 Kip-up Motion . . . . . . . . . . . . . . . . . . . . . . . 304.5.2 Sit to Stand Motion . . . . . . . . . . . . . . . . . . . . . 354.5.3 Walk Motion . . . . . . . . . . . . . . . . . . . . . . . . 354.5.4 Prone to Stand . . . . . . . . . . . . . . . . . . . . . . . 385 Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 425.1 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . 425.2 CMA-ES Optimization . . . . . . . . . . . . . . . . . . . . . . . 445.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 455.3.1 Kip-up Motion . . . . . . . . . . . . . . . . . . . . . . . 465.3.2 Prone-to-Stand Motion . . . . . . . . . . . . . . . . . . . 486 State-Action Compatibility Model . . . . . . . . . . . . . . . . . . . 526.1 Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 546.2 Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 576.3 Querying . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 576.4 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 587 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 647.1 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 657.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67vList of TablesTable 4.1 Body parts specifications taken from Wooten et al. [40] . . . . 21Table 4.2 Body joints specifications . . . . . . . . . . . . . . . . . . . . 21Table 4.3 Transition types . . . . . . . . . . . . . . . . . . . . . . . . . 25Table 4.4 Motion primitive types . . . . . . . . . . . . . . . . . . . . . . 26viList of FiguresFigure 1.1 Big Dog robot developed by Boston Dynamics . . . . . . . . 2Figure 1.2 Walking gait from SIMBICON [41]. Used with permissionfrom van de Panne. . . . . . . . . . . . . . . . . . . . . . . . 3Figure 1.3 The overall architecture of the system (Chapters 3-5) . . . . . 5Figure 2.1 A side kick motion produced using inverse dynamics approach[27]. Used with permission from Macchietto. . . . . . . . . . 7Figure 2.2 A walk motion produced by trajectory optimization [29]. Usedwith permission from Wang. . . . . . . . . . . . . . . . . . . 7Figure 2.3 Biped walker stepping over a sequence of obstacles [12]. Usedwith permission from van de Panne. . . . . . . . . . . . . . . 9Figure 3.1 Phase diagram . . . . . . . . . . . . . . . . . . . . . . . . . 11Figure 3.2 Motion primitives and high level controller structure . . . . . 11Figure 3.3 PD control tracking a child?s angle in world coordinate frame.The desired angle of the child ?dchild in world coordinate frameis converted to the desired local joint angle ?d in local coordi-nate frame. . . . . . . . . . . . . . . . . . . . . . . . . . . . 12Figure 3.4 Virtual force of on a three-link arm . . . . . . . . . . . . . . 14Figure 3.5 Gravity compensation on physics-based character . . . . . . . 15Figure 3.6 Sagittal view of inverse kinematics of two-link arm. Given thetarget position of c as input, IK finds the angle ?1 in worldframe, ?2 for joint a and b. . . . . . . . . . . . . . . . . . . . 17viiFigure 4.1 Character Anatomy. Left-right symmetric structures have onlyone-half of the body annotated. The plural name of the sym-metrical structures are given in parentheses. . . . . . . . . . 20Figure 4.2 An illustration of the zero pose. In this figure, the head pointsto the positive direction of the horizontal axis and limbs pointto the negative direction of the horizontal axis. The zero posedefines the zero angle for each link in the world coordinateframe as well as the zero angle for each joint in the local jointcoordinate frame. Note that the zero pose cannot be actuallyachieved due to the joint limit of the ankles as defined in Ta-ble 4.2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22Figure 4.3 The virtual force primitive. The left foot is the base link andthe right forearm is the link of application. . . . . . . . . . . 27Figure 4.4 Kip-up Phases 1-3 . . . . . . . . . . . . . . . . . . . . . . . 31Figure 4.5 Kip-up Phases 4-5 . . . . . . . . . . . . . . . . . . . . . . . 32Figure 4.6 Sit to stand motion sequence . . . . . . . . . . . . . . . . . . 36Figure 4.7 Walk motion sequence . . . . . . . . . . . . . . . . . . . . . 38Figure 4.8 Prone-to-stand motion sequence . . . . . . . . . . . . . . . . 41Figure 5.1 An illustration of CMA-ES running on a simple 2D problem.The value of the function is depicted by the white contourswith brighter regions representing a better value. The blackdots are individual solutions in a generation and orange dashedboundaries represent the Gaussian distributionN (?,?2?). Adaptedfrom Wikipedia [1]. . . . . . . . . . . . . . . . . . . . . . . 45Figure 5.2 More athletic kip-up motion achieved after 1000 iterations ofoptimization . . . . . . . . . . . . . . . . . . . . . . . . . . 49Figure 5.3 More efficient prone-to-stand motion achieved after 1000 iter-ations of optimization . . . . . . . . . . . . . . . . . . . . . . 51Figure 6.1 Abstract view of state-action compatibility model . . . . . . . 53viiiFigure 6.2 Abstract view of sampling algorithm. There are three sam-pling paths. The evolution of Gaussian distribution along onesampling path is illustrated. . . . . . . . . . . . . . . . . . . 55Figure 6.3 State-action parameterization of the sit-to-stand problem. Thestate parameter is the height of the chair h, the action param-eters are the target waist angle ?waist , and the target shoulderangles ?shoulders. . . . . . . . . . . . . . . . . . . . . . . . . 59Figure 6.4 Input motion (s,a) = (0.45,30,20) . . . . . . . . . . . . . . 60Figure 6.5 Three motions are queried from state-action model with thesame height as the initial chair height, h = 0.45. Motion 1 hasa highly flexed waist; motion 2 does not bend the waist; motion3 uses hands to push the chair. . . . . . . . . . . . . . . . . . 61Figure 6.6 Three motions are queried from state-action model with the adifferent chair height h = 0.16. Motion 1 has a small bend onwaist; motion 2 has a highly flexed waist and pushes the chair;motion 3 also has a highly flexed waist but pushes the ground. 62Figure 6.7 Three motions are queried from state-action with the heighth = 0.65. The human character?s feet are hanging in the air atthe beginning. Motions 2 and 3 look very similar and motion1 failed. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63ixAcknowledgmentsThis thesis could not have been written without my supervisor Michiel van dePanne, who encouraged and guided me through my entire academic program. Iwould like to express my sincerest gratitude to Michiel, for his patience, inspirationand resourcefulness. Thank you!I would also like to thank the second reader of my thesis, Ian Mitchell, forproviding valuable feedback on the writing of this thesis.Many thanks to my friends and colleagues, Brian Xu, Chuan Zhu, Matt Dirks,C. Albert Thompson, Sarwar Alam, Lan Wei, Shu Yang, Yufeng Zhu, Lei Xiao andAndrew Smith for helping out with my study and thesis writing. That means a lotto me.Lastly, a heartfelt thanks goes out to my parents and my girlfriend Lina Miao,for all their love and support.xChapter 1IntroductionTraditional computer animation relies on keyframing. In this technique, animatorsfirst draw characters in a number of key frames at relatively large time intervalsand fill in the rest of frames using ?in-between? frames to get a full animation. Thework of finding appropriate key frames and filling in the rest of the frames is artisticand laborious. The keyframing technique is extended for use in kinematics-basedcharacter animation techniques by using splines to define the values of the degreesof freedom as a function of time. These interpolate the keyframes and thus fullyspecify the in-between frames. This process automates some of the artists? workbut it is difficult for this technique to maintain plausible physics, such as motiondue to gravity and contact forces.Physics-based character animation, on the other hand, models character mo-tion from first principles by using internal forces and physics-based simulation.Consequently the physical plausibility of the motions comes as a byproduct of thesimulation. With simulation, less input is potentially required from human ex-perts to author a physically-plausible character motion. Compared to kinematics-based animation, physics-based character animation can be extended more easilyby changing a character?s dimensions and weights or adjusting its environment. Ithas seen use in film and video-game industry, although to date this has most of-ten been used for ?passive ragdoll? simulations. It remains challenging to designthe control solutions that are needed to emulate the muscle-based motor skills thatdrive human and animal motions in reality.1Figure 1.1: Big Dog robot developed by Boston DynamicsRobotics research has also seen considerable ongoing efforts towards mod-eling motor skills for human and animal-like movements that can be instanti-ated on robots. Locomotion skills have been developed for humanoid robots, andquadrupeds such as the Big Dog robot [37] (Figure 1.1) and the Wildcat robot [9].One general approach to developing motor skills is to develop fundamentalbuilding blocks of motions, or motion primitives. Motion primitives are rules thatcompute torques and can be composed in parallel or sequentially to build up controlstrategies for interesting robotic movements. However, there exist a multitude ofchallenges in developing motion primitives: what is a proper set of motion prim-itives, and when should they be invoked? The problem space consists of highdimensional states and actions and can contain discontinuities caused by contacts.Also, human movement is usually underactuated. Due to these reasons, seeminglysimple problems are very difficult to solve and still remain open today. For exam-ple, it is still unclear how to a develop a robust rising controller, i.e., a controllerthat enables a humanoid character to stand up from various situations.There have been a number of demonstrated successes in learning motor con-trols in physics-based character animation. Muscle models have been developedto simulate joint behaviors that have produced natural locomotions. These mod-els range from simple proportional-derivative (PD) control to detailed simulationswith biological actuators. Motor learning helps robots and physics-based char-acters improve on movements over time by trial-and-errors on the gathered feed-backs. Locomotion controllers have been developed successfully for humanoid and2Figure 1.2: Walking gait from SIMBICON [41]. Used with permission fromvan de Panne.animal-like characters, e.g., walking (Figure 1.2), running, rolling, galloping, etc.Among these, walking is one of the most heavily studied and the most successfulskills. Physics-based characters are able to walk on different slopes at various ve-locities. They are robust to perturbations such as pushes and can adapt to differentground models including sloped terrains and terrains with steps.1.1 GoalsA primary motivation for our work arises from the current inefficiency of researchin controller development for physics-based character animation. Much ongoingeffort has been devoted to authoring motions for rigid-body humanoid or animalcharacters. Researchers have developed a variety of ways of implementing motioncontrols using conceptually similar control primitives. However, it is difficult forthem to share motions with each other. There is an inevitable demand for a unifiedtool that allows researchers to design motions using a well-known set of motionprimitives, and to share and improve on other people?s work with a small amount ofeffort. Well defined languages have significant impacts on other fields that greatlybenefit from end-user development and design, such as Renderman [38] for render-ing shaders and OpenFab [34] for 3D printing. A principle goal of our work is todevelop a motion authoring framework that exposes a good set of primitives usinga simple controller language.Another motivation of the work in this thesis arises from the need to producediverse and adaptive physics-based motions. Motions that work only in one fixedstyle or in the same situation, e.g. jump in same height or walking on a fixed-sloped terrain, are not that interesting. The potential of being able to generate aparticular motion task in different styles and in different situations is part of the3promises of physics-based motion synthesis techniques. We propose a method formodelling the space of all possible feasible actions for a given situation, using anovel state-action compatibility model.1.2 ContributionsThe main contributions of this thesis are as follows:? We create a flexible, scriptable implementation of the motion primitives thathave recently been developed. This potentially allows non-expert users toauthor a wide range of motions without needing to develop or edit sourcecode.? We create several motions using a simple motion-scripting language, includ-ing kip-up, sit-to-stand, walk and prone-to-stand.? We develop an approach that allows motion scripts to be parameterized andoptimized. This is demonstrated for an optimization of a kip-up and a prone-to-stand motion for agility.? We develop a new method for modelling the subspace of motions that ac-complish a given task, which we refer to as the state-action compatibilitymodel.1.3 OverviewThe remainder of this thesis is organized in the following structure. The compo-nents developed from Chapter 3 to Chapter 5 are visualized in Figure 1.3.? Chapter 2 reviews the related work in physics-based character animation.? Chapter 3 introduces motion primitives and the related control strategiesthat will be used by the scriptable framework.? Chapter 4 describes the scripting language and the development of severalmotions using this language.4Figure 1.3: The overall architecture of the system (Chapters 3-5)? Chapter 5 describes the parameterization and optimization of scriptable mo-tions.? Chapter 6 introduces the state-action compatibility model and presents re-lated results.? Chapter 7 concludes and discusses directions of future work.5Chapter 2Related WorkPhysics-based character animations can be achieved by using ?inverse dynamics?methods or using controllers based on finite state machines along with forward dy-namics simulation. Most research on physics-based character animation falls intoone of these two categories of methods. In this chapter, we will discuss the workfrom these two categories that are similar in spirit to ours, with a focus on recentlydeveloped methods. A complete survey on physics-based character animation isoutside the scope of this thesis. Such a survey can be found in [16].2.1 Inverse Dynamics Based MethodsInverse dynamics methods solve the equation of motion (EOM) for torques at ev-ery time step in order to achieve desired kinematic properties, normally the desiredjoint accelerations. This then produces a trajectory that is physically plausible. Ifdesired, the torques can also then be fed into physics simulation in order to re-generate a trajectory. This is fully consistent with frictional effects, collisions, andother limits that are not directly captured by desired accelerations. This methodcan be viewed as planning the motion one time step at a time. Lee et al. [25] de-sign controllers that regulate desired joint accelerations based on reference motionand balance requirements, and use inverse dynamics to produce motions that con-form to captured motion sequences. Macchietto et al. [27] optimizes the desiredjoint accelerations in order to satisfy several balance feedback laws. They use in-6Figure 2.1: A side kick motion produced using inverse dynamics approach[27]. Used with permission from Macchietto.Figure 2.2: A walk motion produced by trajectory optimization [29]. Usedwith permission from Wang.verse dynamics to compute torques that help bipedal and single-legged charactersmaintain balance while doing various in-place movements, such as the kick motionillustrated in Figure 2.1.Trajectory optimization techniques, also known as space-time constraints [39]are similar to inverse dynamics methods, but they plan an optimal motion over alarger time horizon. This approach finds an entire motion sequence and torquesequence using optimization. The produced trajectory is physics plausible becauseit is required to satisfy the EOM constraints. The trajectory optimization techniqueallows a user to specify a set of additional constraints for the motion, e.g. a certainpose must be achieved at a certain time. It further allows the specification of anobjective function, e.g. one that rewards the motion for being energy efficient. Anoptimization then solves for a motion trajectory that satisfies the constraints whileminimizing the objective. Mordatch et al. [28, 29] use this method to generatevarious human motions including walk. The walk motion is shown in Figure 2.2.The trajectory optimization technique can be seen as a variation of the inversedynamics method, with the difference that it plans once for all the steps in theentire motion. The optimization of an entire motion is typically an offline process.Online trajectory optimization over a fixed finite horizon, also known as Model7Predictive Control (MPC), works in a similar fashion as trajectory optimization.However, instead of planning the motion once, this method re-plans at each timestep, and only over a shorter time window, typically 0.5-1.5 seconds for motions in-volving human dynamics. This method lies somewhere between inverse dynamicsmethods and trajectory optimization methods. It is a tradeoff between the requiredcomputations and the time span of the motion planning window. It can be used asan online method but can produce motions slower than realtime. This method isused by Tassa et al. [32] to synthesize rise-up motions at a rate 7x slower than re-altime. Al Borno et al. [8] use an offline implementation of this method to developa wider range of human motions with simple task-specific objectives.2.2 Finite State Machine (FSM) Based ControllersFSM-based controllers compute torques based on control goals, and feed the torquesinto a forward dynamics simulator. With the development of forward simulationengines, FSM-based methods do not require the direct knowledge of equations ofmotion [16] and allow interactive control of the motions [24, 42]. FSM basedcontrollers have been used to produce physics-based character animations over thelast two decades [31, 33]. Variations of FSM based controllers are applied inrobotics [15, 30].Several components are used for FSM based controllers, such as PD controlsfor pose tracking in joint angle space, inverse kinematics for controlling end effec-tor position in Cartesian space, virtual forces applied via a Jacobian transpose andfoot placement for balance, etc. Coros et al. [12] use PD controls, inverse kinemat-ics, virtual forces, gravity compensation and inverted pendulum models to creategeneralized biped walking controllers for a variety of character morphologies invarious environments (Figure 2.3). These are the fundamental components of thisthesis work.A considerable amount of work has focused on locomotion skills. Yin etal. [41] develop robust locomotion skills including walking and running for bipedcharacters using an FSM-based controller with simple feedback mechanisms. Kwonet al. [22] use an inverse pendulum model to regulate balance for running steps.Coros et al. [13] create quadrupedal locomotions using a gait control graph and8Figure 2.3: Biped walker stepping over a sequence of obstacles [12]. Usedwith permission from van de Panne.various virtual model control primitives. Specific control goals are allowed forwalking controllers such as speed and direction control [11, 23]. Other workhave focused on different types of non-locomotions. Jain et al. [21] demon-strate controllers for object dodging and balancing through the use of external sup-port. Faloutsos et al. [14] develop controllers for various rising up motions suchas prone-to-stand, supine-to-stand, kip-up, etc. Ha et al. [18] develop falling andlanding controllers for a human character.FSM-based controllers can be refined with offline optimization. Wang et al. [35]extend the work of [41] and optimize the controller for various objectives includ-ing energy and style. This creates a more natural walk controller. Geijtenbeeket al. [17] use offline optimization to produce motions that track motion capturedata. Optimization can also be used to discover new motion styles that are hard todevelop manually. Agrawal et al. [7] used diverse optimization techniques to syn-thesize a range of motions in the same family but with noticeably different styles.Our work uses the FSM-based approach. It is closest in spirit to [7, 12, 41].While most previous work on FSM-based methods focus on a family of closelyrelated motion controllers, our work produces a wide range of different motions,including kip-up, walk, sit-to-stand, prone-to-stand.9Chapter 3Motion PrimitivesIn this chapter we describe the control strategy used in this thesis. It belongs to theclass of finite state machine controls schemes used in [12, 41], i.e., we use phase-based control scheme to author the motions of physics-based characters. Eachphase carries out a portion of the motion, e.g. the support phase of a walk cycle.The phase-based control structure is illustrated in Figure 3.1. A phase remainsactive until some interesting event has happened, and it then transitions to the nextphase. Scheduled timeouts or new contacts with the environment typically resultin a transition to a new phase.Within each phase, several motion control primitives can be used in combi-nation to achieve the desired goal. Our system integrates several motion controlprimitives that were demonstrated to work well in [12, 17, 18]. Figure 3.2 givesan overview of the control structure and motion primitives used within each phase.The remainder of this chapter will cover all the motion primitives used in this the-sis as well as the phase transition model. The primitives collectively produce a nettorque for each joint. The torque is given by? = ?PD + ?V F + ?GC + ?QB (3.1)where VF represents the desired virtual force, GC represents the gravity compen-sation force, QB represents the quiescent balance.10Figure 3.1: Phase diagramFigure 3.2: Motion primitives and high level controller structure3.1 PD Control on JointsProportional-derivative (PD) controls are a basic method to track desired joint an-gle trajectories. At every simulation step, a PD controller computes the torque foreach joint based on the desired joint angle ?d , the current joint angle ? and thejoint?s angular velocity ?? :?PD = kp(?d??)? kd ?? (3.2)11Figure 3.3: PD control tracking a child?s angle in world coordinate frame.The desired angle of the child ?dchild in world coordinate frame is con-verted to the desired local joint angle ?d in local coordinate frame.where kp and kd are proportional gain and derivative gain parameters that governthe responsiveness and stiffness of the joint motions. We allow for different kp andkd gains for each joint. Most joints use low-gain PD controllers in order to achievecompliant motions that are less stiff and therefore more natural.PD controls are used to track the desired angle of joints in either the localjoint coordinate frame or in the world coordinate frame. In the case of trackingin the world coordinate frame, a desired angle of the joint?s child or parent can bespecified in the world coordinate frame. This is then converted to a desired angle ofthat joint in local coordinate frame, and a joint-local PD control is used to drive thejoint to that angle. An example is shown in Figure 3.3 that tracks the child link?sangle in world coordinate frame.In practice, the joint angles do not exactly follow the desired joint angle tra-jectories because the dynamics of the joint can be affected by the other parts ofthe body system. PD controls by themselves also do not take external forces intoaccount such as gravity. Joints that support significant weight or that support largecontact forces are prone to large errors. In order to alleviate the errors, we need thehelp of virtual force and gravity compensation. These ?feed-forward? mechanisms12will be discussed in the next two sections.3.2 Virtual ForceVirtual forces allow joints to be abstracted away and instead allow for motions tobe controlled in Cartesian space. They help counter external forces, and can helpin achieving desired end-effector trajectories. The virtual force technique worksby generating a set of joint torques along a chain of links that effectively resultsin a desired force on one end of the chain. To apply a virtual force to a bodylink, a desired force is specified on that link of application, and one of the links isselected to serve as the root or ?base? of the kinematic chain. Along the chain oflinks between the link of application and the base link, torques are automaticallycomputed for all these joints. The virtual force technique can be used to acceleratethe body, to compensate for gravity, and to achieve given forces on an end effector.At any given time, a force, F , applied on a given point on a kinematic chainproduces a power, P, given byP = F> ? vwhere F> is the transpose of the force, and v is the velocity of the point of appli-cation. To produce the same power by using internal torques, the internal torquesalong the kinematic chain to the base link also has to satisfyP = ?> ??where ? and ? are the joint torques and angular velocity along all the joints. Thevariables v and ? are furthermore related by the Jacobian matrix:v = J ??Therefore we haveF> ? v = ?> ??Substituting v with J ?? we get :F> ? J = ?>13Figure 3.4: Virtual force of on a three-link armand equivalently,? = J> ?F (3.3)For the 2-D three link chain illustrated in Figure 3.4, the Jacobian is defined asfollowing:J =[?vx/??a ?vx/??b ?vx/??c?vy/??a ?vy/??b ?vy/??c]where vx and vy are the horizontal and vertical velocity of the point of interestand ?a, ?b and ?c are the angular velocities of the three joints. For this specificexample, this can be reduced toJ =[ya? yA yb? yA yc? yAxA? xa xA? xb xA? xc]This yields the torque as? = J> ?F =???(ya? yA) fvx +(xA? xa) fvy(yb? yA) fvx +(xA? xb) fvy(yc? yA) fvx +(xA? xc) fvy???The implementation of virtual forces in our framework allow for the application14Figure 3.5: Gravity compensation on physics-based characterof virtual forces on arbitrary chains of our planar character model.3.3 Gravity CompensationGravity compensation (GC) is one application of virtual force. It works by produc-ing joint torques to help body links cancel the impact of gravity. This allows simplePD control to achieve more accurate joint angle tracking, and is therefore helpfulin a variety of situations. When using GC on a humanoid character, it is assumedthat one of the foot is firmly planted on ground and that the corresponding foot thusserves as the base link. A virtual force Fi = ?mig is applied to every body link,bi, as shown in Figure 3.5. The resulting joint torques from these virtual forces areaggregated for each joint. In the case where two feet are both well planted on theground, we choose to distribute the virtual forces arising from upper bodies evenlyto the two base links, i.e. both feet.In practice, it is sometimes useful to use an approximation when computinggravity compensation for the support limbs. We can apply a virtual force of ?Mg15to the CoM of the torso, where M is the total mass of the entire body. This allowsfor better PD control over the lower body, and also makes the task of balance easier.3.4 Quiescent Stance Balance FeedbackThis type of feedback helps the character remain statically balanced while standingon the ground. The mechanism uses a feedback rule to compute a horizontal virtualforce that regulates the CoM position in order to maintain balance. The goal is tokeep the CoM right above the middle of the supporting foot span. The virtual forceis computed by a horizontal PD controller:f = kp(xd? xcom)? kd x?com (3.4)where xd is the middle point of foot span, xcom is the horizontal projection of thefull body CoM, x?com is full body CoM?s velocity and kp and kd are the adjustableproportional and derivative parameters that have been seen in the PD controllers.3.5 Inverse KinematicsInverse Kinematics (IK) is a method to determine joint angles required to achievea desired end effector position in Cartesian coordinates. Certain motions are moreeasily controlled in Cartesian space, e.g., reaching a location with the hand. For ourplanar humanoid character, IK is made available for the two-link limb structures,i.e. arms and legs. A user can specify the reaching target of the end effector,i.e. wrists and ankles, in Cartesian coordinates. The angle of the first joint alongthe link will be computed in the world coordinate frame and that of the secondjoint will be computed in the local coordinate frame. These two joints are thentracked by the PD controllers to the computed desired angles in their correspondingcoordinate frames.There are two solutions for two link planar IK. One of them represents thecase where middle joint bends forward and the other solution represents backwardbending. These are typically referred to as the ?elbow up? and ?elbow down?solutions in robotics. Since the elbow joint for a human figure only bends one way,its IK has a unique solution. The computation of IK for the arms is illustrated in16Figure 3.6: Sagittal view of inverse kinematics of two-link arm. Given thetarget position of c as input, IK finds the angle ?1 in world frame, ?2 forjoint a and b.Figure 3.6. The position of the wrist, c, is specified by the user. The position of theshoulder, a, is obtained at run time from the simulation. The lengths of two linkslab and lbc are predefined in the character specification. Therefore, for the giventwo link case, the analytical solution can be easily derived using the cosine law:l2bc = l2ab + l2bc?2lablaccos? (3.5)? cos? = (l2ab + l2ac? l2bc)/2lablac (3.6)The joint angle of the first joint ?1 in world frame is given by?1 = acos((cx?ax)/lac)?? (3.7)Likewise, we can find angle cos? using the cosine law, and therefore find theangle ? :cos? = (l2ab + l2ab? l2ac)/2lablbc (3.8)17Lastly ?2 is given by?2 = pi?? (3.9)IK for the legs is computed in an analogous fashion.3.6 Phase Transition ModelsAll the planar physics-based character motions are authored using a phase-basedfinite state machine. Each phase is concerned with a specific task and uses a setof motion primitives to accomplish that task. Each phase will transition to thenext phase unless it is the final phase of a non-cyclic motion. A phase transitiontakes place upon the occurence of a predefined transition event. These events fallinto two categories: timeout events and contact change events. A timeout eventhappens whenever a specified duration has elapsed since the start of the phase. Acontact change event happens whenever one of a specified set of links has a changein contact, i.e. a body link has just established contact or has just lost contact withits surrounding environment. With these simple transition models, many motionscan be easily divided into distinct phases. In the next chapter we further discussspecific implementation details.18Chapter 4Simple Controller Language(SCL) FrameworkIn this work, we build a simple controller language (SCL) framework that is capa-ble of loading a motion script at runtime and produce a physics-based motion thatis simulated in realtime. The scripts are written in a SCL, and they are interpretedby a scripting engine. Once a motion script is interpreted, it is loaded into theapplication runtime and is represented as a phase-based motion controller whereeach phase consists of the motion primitives described in the previous chapter. Thecontroller is then applied on a 2D planar humanoid model for dynamics simulation.The initial state of the simulation can be specified by the animator: a predefinedinitial pose and a predefined static environment can be selected together to formthe initial state of the simulation. The physics simulation then produces a motionin realtime.The scripting framework allows users to use a text-based language for au-thoring motions using an expressive and flexible syntax. The language providesa built-in set of primitives that are mentioned in the previous chapter. With such alanguage, our framework opens a window for non-programmers to create physics-based motions and for animators to share motions with each other. It also poten-tially shortens the test cycle of motion design by allowing modifying and re-loadinga motion at runtime in a semi-interactive manner.In this chapter, we will describe the SCL in detail and show some motions19Figure 4.1: Character Anatomy. Left-right symmetric structures have onlyone-half of the body annotated. The plural name of the symmetricalstructures are given in parentheses.authored using the SCL including kip-up, sit-to-stand, walk and prone-to-stand.4.1 Character DefinitionThe character has predefined link dimensions, masses, joint angle limits and jointPD parameters that are held fixed across all simulations. A controller author needsto know the names of the joints and links in order to apply motion primitives tothe intended joints and links using the SCL. The character anatomy is illustratedin Figure 4.1. The character is a 2D model in the sagittal plane, consisting of 16rigid links, 15 one-DOF joints, and a total mass of 89.49kg. Each body part ismodelled as a trapezoid with two semi-circular end caps. The simulation neglectsself collisions within the body. The specification of all body parts can be foundin Table 4.1. A joint angle is defined as a child link?s orientation relative tothe orientation of its parent. The head is the root link. For each joint, the parentlink is the one that is proximal to the head. The zero pose is defined as a stiffstraight pose with hands and feet pointing to the left, and head pointing to the20Body Part Length (cm) Tip Thickness (cm) Mass (kg)head 35 26, 22 5.89neck 2 12, 12 1.1trunk 50 30, 20 29.27pelvis 25 24, 27 16.61arm 32 16, 8 2.79forearm 32 8.4, 8.4 1.12hand 17 5, 4 0.55thigh 50 28, 10 8.35shank 48 10, 7 4.16foot 22.6 8, 5.2 1.34Table 4.1: Body parts specifications taken from Wooten et al. [40]Body Joint Angle Range (?) kp ( Nmrad ), kd (N?m?srad ) Max Torque (Nm)neckTop -30, 90 170, 5 60neckBottom -30, 30 171, 18 122waist -40, 90 674, 61 250shoulder -90, 180 386, 33 180elbow 0, 160 300, 20 180wrist -90, 90 156, 11 120hip -30, 100 500, 70 300knee -160, 0 600, 70 300ankle 30, 150 500, 60 300Table 4.2: Body joints specificationsright. This is illustrated in Figure 4.2. When the character is in the zero pose, theworld orientation of each link as well as each local joint angle is defined to be zero.The rotation of a link is defined as positive when it turns counter-clockwise. Therotation of a joint is positive when the its child link rotates in the positive direction.The kp parameter is set to be positively correlated with the strength of joints andkd is set to be approximately 0.1kp. One exception is that kp is relatively low forneckTop in order to avoid motion instabilities for the neck and head for our chosensimulation time steps. The joint limits, torque limits, and kp kd parameters of eachjoint are empirically tuned and they are given in Table 4.2.21Figure 4.2: An illustration of the zero pose. In this figure, the head pointsto the positive direction of the horizontal axis and limbs point to thenegative direction of the horizontal axis. The zero pose defines the zeroangle for each link in the world coordinate frame as well as the zeroangle for each joint in the local joint coordinate frame. Note that thezero pose cannot be actually achieved due to the joint limit of the anklesas defined in Table Specification of Phases and Phase TransitionsThe controller framework reads in controller description that are defined in theSCL syntax that we will describe in the following two sections. In this section wefocus on the specification of phase and phase transitions.The controllers have a phase-based structure. A motion and its correspondingcontroller consist of several phases. In the introductory example shown in List-ing 4.1, a two-phase motion is scripted. The first phase attempts to drive the leftshoulder to 180?, which is followed 2 seconds later by a second phase that mimicsthe same behaviour for the right shoulder. Note that the two shoulder joints arenamed as ?leftShoulder? and ?rightShoulder? in the SCL. A full list of joint namesand link names can be found in Figure 4.1.Listing 4.1: A Simple Motion Script1 {2 (left_shoulder_raise)3 [leftShoulder 180]4 }5 after 2226 {7 (right_shoulder_raise)8 [rightShoulder 180]9 }Each motion phase is specified within a pair of brackets ?{ }? as seen in theexample. Within each phase specification, one can define an optional phase namebetween ?( )?, as seen in line 2 and 7. A phase name can be used to describe itspurpose, and can also serve as a unique label that can be referred to later. Theremainder of each phase specification consists of one or more motion primitives.In Listing 4.1, the two motion primitives are the PD controllers on the left andright shoulder, which drive the shoulders to 180? relative to the torso. The detailsfor control primitive specifications including PD control will be further describedin the next section.Every phase must be followed by a transition rule with the exception of the lastphase. The rule states the condition of the transition and is followed by the nextphase that it transitions into. In the above example, the transition rule between thetwo phases is a simple time-based rule that deactivates the left shoulder run phaseand activates the right shoulder run phase after 2 seconds spent in the first phase.In Listing 4.1, the second phase is not followed by another phase, and therefore itis the last phase. The last phase remains active thereafter.A transition rule following the last phase makes the motion cyclic. For exam-ple, in Listing 4.2, the last phase (phase 4) is followed by a transition specified online 19 and line 20. This transition is prefixed with a ?finally? keyword and fol-lowed by a special ?backto? syntax that refers to a previously defined phase name.This instructs the motion to transition back to phase 1 after phase 4 is finished.Therefore, the motion control phases repeat in a cyclic fashion.In addition to being used to build a cyclic motion, a previously defined phasename can also be used to define a symmetric phase. On line 17 of Listing 4.2,phase 4 is designated as a symmetric duplicate of phase 3, using the ?(phasename):(existing phase)? syntax.Phase transitions fall into two main categories as described in Chapter 3, i.e.time based and contact based. In addition, the SCL also allows another type of23transition using the conjunction of these two main types. A complete list of transi-tion types are shown in Table 4.3.Listing 4.2: A Simple Script Illustrating the Transition Models1 {2 (phase_1)3 [shoulders 120]4 }5 after 26 {7 (phase_2)8 [shoulders 0, elbows 0, wrists -40]9 }10 when contact hands11 {12 (phase_3)13 [leftElbow 90]14 }15 after 216 {17 (phase_4) : (phase_3)18 }19 finally after 320 backto phase_1The two main types of transitions are both demonstrated in Listing 4.2. Timebased transitions are used on line 5, 15 and 19. Line 10 specifies a contact-basedtransition. It states that phase 2 should transition into phase 3 when the handsmake contact with the environment. The third transition type will be presentedlater in the chapter.24Transition Type Specification Syntax CommentTime based after n Transition happens after n sec-ondsContact based when contact (changed | es-tablished | lost)? (any | all)?body link(s)Transition happens when any (orall) of the specified body link(s)has just changed its contact state.Contact and Time based and contact based transitiontime based transitionTransition happens when bothconditions are satisfiedTable 4.3: Transition types4.3 Motion Primitive SpecificationsA phase can contain zero or more motion primitives. Each motion primitive isspecified in a pair of square brackets ?[]?. A motion primitive normally starts witha keyword that represents its type. There are 6 types of motion primitives. Theyare briefly listed in Table 4.4.PD Controller. Each PD controller primitive specification defines the PD con-troller for one or more joints and it does not require a keyword. Its syntax isdemonstrated in Listing 4.3. On line 1, PD controllers are applied on three jointswith different target angles. The target angle of each joint moves from its currentangle to the specified target angle.Listing 4.3: PD control primitive1 [joint_1 90, joint_2 50, joint_3 40 time: 1.2]2 [joint_1 90 child, joint_2 50 parent]At each time step, the actual target angle is linearly interpolated between the twoangles over a duration of ?time: 1.2?, i.e. 1.2 seconds. ?time? keyword is optional:when it?s not specified, PD control tracks to the specified target angle instantly.On line 2, PD controllers are used to track the child and parent links of the twospecified joints respectively in world coordinate frame.When not explicitly specified, a default PD controller is active on each joint.The default PD controller tracks the joint to a desired angle that is inherited fromthe previous phase or to its starting pose when there is no previous phase. There-fore, when a phase contains no explicitly specified motion primitives, all the joint25Type Keyword DescriptionPD Controller Not needed Applies a PD control a set of jointsVirtual Force vf Applies a virtual force on a body partStance Balance Feedback sb Applies a balance feedback force to the torsoIK ik Computes joint target angles using IK and appliesPD controls on those jointsRelax Joints relax Reduces the torques produced by PD Controller tomake behave more passivelySymmetric primitive symm Duplicate the last motion primitive and apply it onthe symmetric structureTable 4.4: Motion primitive typestorques are computed from these default PD controllers. The default PD controlleris overridden when the relative joint has a explicit PD controller, or the joint is con-trolled by the inverse kinematics or the relax primitive as we will describe shortly.Virtual Force. A virtual force primitive begins with the keyword ?vf?. Itspecifies a force, a link of application, and the joint that is connected to what isconsidered to be the base link for the virtual force. In Listing 4.4, the demonstratedvirtual force primitive applies a force, F = (300N,300N) to body 1, with joint 1being the first joint from the base link. Figure 4.3 shows the virtual force primitivewith the right forearm specified as body 1 and the left ankle specified as joint 1.Thus the base link is the left foot.Listing 4.4: Virtual force primitive1 [vf (300, 300) on: body_1, by: joint_1]Quiescent Stance Balance. A quiescent stance balance feedback primitive isused within a virtual force primitive, and it is denoted by the keyword ?sb?. Itscommon usage is illustrated in Listing 4.5.Listing 4.5: Virtual force with stance balance primitive1 [vf sb(300, 30) on: trunk, by: leftAnkle]The quiescent stance balance feedback primitive computes a desired virtual forceusing Equation 3.4. The parameters kp and kd is chosen to be 300 and 30 respec-26Figure 4.3: The virtual force primitive. The left foot is the base link and theright forearm is the link of application.tively in Listing 4.5. The desired virtual force is applied to the trunk in order tohave a large impact on the full body CoM. When a foot is chosen as the base link,the corresponding ankle will be used as the first joint from the base.Inverse Kinematics. The inverse kinematics primitive begins with the ?ik?keyword. It needs to specify a sequence of target positions for the end effectorpositions to reach. In Listing 4.6, the IK primitive instructs the right ankle tosequentially reach two positions relative to the position in world coordinates thatthe left ankle occupied at the beginning of the phase. In our framework, the IKprimitive are designed for two-link chains. Therefore, in Listing 4.6 the base of theIK chain is the right hip. Similar to PD, the IK primitive tracks the end effectortarget locations in a piecewise linear fashion. The intermediate target locations areassumed to be equally spaced in time. The IK primitive overrides the target angleof the relevant joints specified by the default PD controllers.Listing 4.6: Virtual force with stance balance primitive271 [ik (0.25, 0.30), (0.20, -0.05) on: rightAnkle rel:leftAnkle time: 0.35]Relax Primitive. The relax primitive sets the target joint angle of PD controllerto its current joint angle at each simulation time step, and scales down the jointtorques produced by the PD controller, using the strength parameter to denote thescale factor between 0 and 1, as shown in Equation 4.1 and 4.2.?d = ? (4.1)?pd = cscale ? (kp(?d??)? kd ??) =?cscale ? kd ?? (4.2)where ?d is the desired joint angle and is set to the current joint angle ? . Thiseffectively eliminates the proportional term from the PD controller, leaving onlythe scaled derivative term which serves as a damper (Equation 4.2). The syntax ofthe relax primitive is shown in Listing 4.7.Listing 4.7: Virtual force with stance balance primitive1 [relax joint strength scale]Symmetric Primitive. The symmetric primitive is used as ?[symm]? and itdoes not need extra parameters. It is required to follow another primitive, and thisclones the previous primitive to a symmetric counterpart of the body. For example,using this primitive, a virtual force that affects a chain containing the left leg canbe duplicated to the symmetric chain containing the right leg.4.4 Motion Design WorkflowIn general, authoring a controller requires knowledge of the phases useful for struc-turing a motion and a qualitative understanding of the physics of the motion. Amotion needs to be divided into a proper sequence of phases. For example, a sit-to-stand motion can consist of two phases: the first phase shifts the CoM of bodyforward, and the second raises the CoM. A well chosen phase structure often sim-plifies the motion design. It is also important for the author to understand the goalof each phase. This aids in the incremental design of a motion. A useful motion28design strategy is to test all the previous phases and ensure they end in an approxi-mate state, before designing the next phase. In the previous example of sit-to-standmotion, before an author designs the second phase, it is important to ensure that thegoal of shifting CoM of body out of the chair is achieved at the end of first phase.The author can then proceed to the design of the second phase. Knowledge of thequalitative physics is important as it helps the author to select the suitable motionprimitives to achieve the desired goal of a phase. For example, to gain angularmomentum, one might need to rapidly swing extended arms instead of keeping theelbows flexed.Motion design is a trial-and-error process. Guidelines for authoring a motioncan be summarized as follows:1. define the motion phases, with a clear understanding of what each phaseshould accomplish. A reference motion or motion tutorial for the real humanmotion can be helpful in achieving this.2. beginning with the first phase, select a set of primitives that would be usefulin accomplishing the desired goal. Test these primitives and use the simu-lation results to refine the motion primitive parameters. Test with differentparameters until the desired end state is achieved.3. select a transition condition for moving to the next phase.4. Repeat steps 2-3 until the motion is successfully completed.With practice, a motion can typically be authored in minutes or hours if a goodreference motion is available. In the remainder of the chapter, we will presentmotions that are authored using the scripting framework and outline the intuitionbehind choosing the respective motion primitives.4.5 ResultsWe present a number of motions scripted using the SCL including statically-balancedmotions and highly dynamic and acrobatic motions. The robustness of motioncontrollers can largely depend on the nature of the motion. As can be expected,29controllers that deal with static-balance tasks are more robust than those dealingwith more dynamic motions. For example, sit-to-stand is more robust than kip-up.However, we note that the robustness of controllers is not the primary concern ofthis framework. Instead, we focus on how to quickly create a successful motionthat looks physically plausible and could be easily reused and adapted by others.We use JBox2D [4] as the physics simulation engine with a simulation timestep of 0.25ms. The position iterations and velocity iterations per physics stepsare 3 and 8 respectively. Ground contact is modelled in JBox2D using impulsiveforces and unilateral constraints.4.5.1 Kip-up MotionIn this section we explore the authoring of a kip up motion. In a kip up motion, ahumanoid character makes an acrobatic move from a supine position to a standingposition by propelling the body away from the ground using leg swings and a pushof the hands. It is a highly-dynamic motion with swift momentum change andcontact relocation. It also requires careful balance maintenance during the landingand rising up phases. The motion that we develop has five phases. The first twophases prepare for the dynamic leg and arm motion. The third phase does thrustand the fourth phase performs the landing. The last phase takes care of standing upwhile maintaining balance. Figure 4.4 and Figure 4.5 show the motion with thesefive phases.Listing 4.8: Kip up motion script1 {2 (roll_back)3 [shoulders 120, elbows 130, wrists 50 time: 0.3]4 [hips 80, waist 80, knees -170 time: 0.5]5 }6 after 0.6 // The motion will transition to the next phaseafter 0.6 seconds7 {8 (straighten)9 [waist 90, hips 50, knees 0 time: 0]10 [vf (0, 200) on: leftFoot, by: waist]30(a) Phase 1: Rollback(b) Phase 2: Straighten Legs(c) Phase 3: PropelFigure 4.4: Kip-up Phases 1-311 [symm]12 }13 after 0.314 {15 (propel)16 // thrust with hips and waist17 [hips 0, waist -20 time: 0]18 [vf (300, 0) on: leftShank, by: waist]19 [symm]2031(a) Phase 4: Landing(b) Phase 5: Standing upFigure 4.5: Kip-up Phases 4-521 // knees and ankles are folded22 [knees -180 time: 0.45]23 [ankles 150 time: 0]2425 // hands push the ground, relax to turn down pd control26 [relax shoulders, elbows strength 0.1]27 [vf (0, -200) on: leftHand, by: leftShoulder]28 [symm]29 }30 when contact all feet31 {32 (land)33 // virtual force to strengthen the legs34 [vf (-100, -500) on: leftFoot, by: leftKnee]3235 [symm]36 [relax knees, ankles strength 0.4]37 // rotate the upperbody forward38 [hips 80, waist 40 time: 0.0]39 [necks 10 time: 0.3]4041 // reduce moment of inertia by folding arms42 [shoulders 20, elbows 160, wrists 0 time: 0.3]43 }44 after 0.645 {46 (stand)47 [vf sb(1000, 300) on: trunk, by: leftAnkle]48 [symm]49 [vf (0, 200) on: trunk, by: leftAnkle]50 [symm]51 [knees 0, hips 0, waist 0 time: 1.2]52 [relax ankles, shoulders, elbows, wrists strength 0.1]53 [necks 0]54 }The script for the entire motion is shown in Listing 4.8. The motion is looselybased on a kip up tutorial [5]. The following section briefly describes the designintuition of each phase.? Rolling back. (line 1-5) The first phase starts from the initial supine po-sition. At the end of this phase, it is desired that the legs are flexed backtowards the torso and hands curled towards the neck while the shoulders re-main close to the ground. These are achieved by applying PD controls onthe relevant joints as on line 3 and 4, i.e. waists, hips, knees, shoulders, el-bows and wrists. This phase is relatively easy to get correct. An importantpoint to note is that the knees need to bend at a sharp angle to prevent theupper body from being pivoted upwards by the lower body movement. Thetransition from the phase is time based (line 6), and the transition time waschosen empirically. The intuition for the transition point is that this phaseshould end when the back is not too high above the ground and there is some33upward momentum for the whole body.? Straighten up legs. (line 7-12) The goal of the second phase is to gainupwards momentum. This is done by applying a PD control to straighten upthe legs and point the feet upwards (line 9). An upward virtual force (line 10)is applied on the foot in order to gain momentum more rapidly. The timeoutis chosen by intuition similar to the previous phase.? Propelling the body (line 13-29). This phase aims to gain linear and angularmomentum for the whole body. It does so by thrusting the legs away fromthe body and down to the ground (line 17-19) in coordination with handspushing off the ground using a virtual force (line 26-28). Notice that in orderfor the hand push to work well, we ?relaxed? the upper limbs (line 26) so thattorques generated by the virtual force dominate the upper limb joints. Kneesand ankles are flexed (line 22-23) in order to prevent unexpected contact withthe ground and to prepare for a better landing where the approaching angleof the foot with respect to the ground is almost 0.? Landing. The landing phase starts right after both feet are in contact withthe ground, and the goal is to bring CoM above the support of the feet spanand also to make sure the character ends in a statically balanced crouchingpose. A virtual force (line 34-35) that pushes the feet downwards is neededto make the knees and ankles strong enough to absorb the landing impact.The upper body?s moment of inertia is reduced by folding arms (line 42).The angular momentum gained from the previous phase helps to rotate upperbody forward (line 38-39).? Standing up. At the beginning of this phase, the CoM of the body has fallenwithin the support of the foot span, and the goal is for the character to risewith feet on the ground. The stance balance feedback primitive is turnedon (line 47-48) to keep the horizontal position of CoM within character?ssupporting polygon given by the span of its feet. Stand-up motion is achievedby tracking the knees, hips to their zero configuration as on line 51. Anupward virtual force is applied on the torso to approximately compensatefor gravity as on line 49-50. The ankles are ?relaxed? (line 52) and thus the34rotations of these two joints are dominated by the torques from the balancevirtual force and the constant upward virtual force.4.5.2 Sit to Stand MotionIn this section, we demonstrate a sit-to-stand motion. The initial state of the motionsees a character sitting in a chair. The motion scripts consists of two phases. Inthe first phase, the character leans its body forward so that the CoM is eventuallyabove the support region of the feet. In the second phase, the character stands upin the same way as in the last phase of kip motion. This motion is fairly easy toauthor. It can take less than 10 minutes when the user has a basic understanding ofa stand up motion. The motion is illustrated in Figure 4.6.Listing 4.9: Sit To Stand Script1 {2 (lean)3 [waist 20, hips 120 time: 0.3]4 }5 after 0.46 {7 (standup)8 [vf sb(400, 300) on: trunk, by:leftAnkle]9 [symm]1011 [vf (0, 400) on: trunk, by:leftAnkle]12 [symm]13 [knees 0, hips 0, waist 0, necks 0 time: 0.9]14 [relax ankles, shoulders, elbows, wrists strength 0.1]15 }4.5.3 Walk MotionThe walk motion given in Listing 4.10 consists of two symmetric phases. Withour framework, it is possible to author just one phase and then to use symmetryto define the other phase. Reuse of the phase definition makes it easier to test35Figure 4.6: Sit to stand motion sequencethe script because it reduces the chance of subtle human-made errors that comesfrom inconsistent parameters of the two symmetric phases. Each phase makes thetransition using the conjunction of a time based and contact based rule. These twoconditions prevent a transition from occurring before the swing foot has left theground. Each of the phases is composed of four parts: pose of the upper body,pose of the swing leg, pose of the stance leg, and virtual forces that assists themovement. For the upper body poses, on line 5, it tracks the head and trunk?s angleto 90 degrees, i.e. up-right in world space. Lines 6 and 7 takes care of arm swingsby tracking shoulders and relaxing elbows and wrists to make them more passive.Line 10 and 11 controls the swing foot. The IK on line 10 instructs left wrist toreach two sequential target positions relative to right ankle?s starting position at thebeginning of the phase. This affects the joint angles of swing knee and swing hip.For the stance foot, line 14 uses left hip to track the world orientation of the pelvis,and it also sets knee to flex. Line 15 ?relaxes? the stance ankle from PD controller.The torque for this ankle will be mainly determined by virtual forces. The virtualforce primitives (lines 18 to 20) contains both vertical and horizontal components,and therefore help the character to propel itself forward and to compensate forthe gravity. Line 18 does gravity compensation for the swing leg. This helpsthe IK mechanism to be more accurate. Although an accurate full-body gravitycompensation will result in a more accurate pose tracking, it is sufficient to apply anapproximate gravity compensation force to the trunk. Line 19 uses the stance kneeas the base joint to partially compensate the gravity for the entire body (600N) andto propel the body forward (150N). The stance ankle?s torque is critical to control36the ground reaction force. Line 20 uses the stance ankle as the base joint to pushswing leg, and it effectively causes the stance foot to obtain a ground reaction forcethat has a horizontal component that pushes the body forward, i.e., to the right.A complete cycle of the walk motion is illustrated in Figure 4.7. The walkingmotion is not yet very natural and is included here in order to illustrate how walkingcan be authored in our framework. As with other walking simulations, we expectthat the motion could be refined with optimization. In the following chapter, wedescribe how motions can be optimized.Listing 4.10: Walk Motion1 {2 (right_swing)34 // upperbody pose5 [neckTop 90 parent, waist 90 parent]6 [leftShoulder 30, rightShoulder -25 time: 0.4]7 [relax elbows, wrists strength 0.05]89 // swing foot10 [ik (0.25, 0.30), (0.20, -0.05) on: rightAnkle rel:leftAnkle time: 0.35]11 [rightAnkle 180 child]1213 // stance foot14 [leftHip 90 parent, leftKnee -30]15 [relax leftAnkle strength 0.4]1617 // virtual forces and gravity compensations18 [vf (0, 110) on: rightShank, by: rightHip]19 [vf (150, 400) on: trunk, by: leftKnee]20 [vf (60, 0) on: leftThigh, by: leftAnkle]21 }22 and when contact rightFoot after 0.323 {24 (left_swing) : (right_swing)25 }37(a) Phase 1: right leg swing(b) Phase 2: left leg swingFigure 4.7: Walk motion sequence26 finally and when contact leftFoot after 0.327 backto right_swing4.5.4 Prone to StandWe also demonstrate a seven-phase prone-to-stand motion in which the characterrises from a prone position and ends in a stand position. The script is shown in4.11. All the transition rules and motion primitives used in this script have beenreviewed in the previous results. Therefore, we will leave out the details on themotion authoring. The resulting motion can be seen in Figure 4.8.Listing 4.11: Prone to Stand1 {2 (place_hands)3 [ik ( 0.05, 0.15), ( 0.20, -0.14)384 on: wrists rel: leftHip time: 0.5]5 [wrists 180 child time: 0.2]6 }7 and when contact any hands after 0.28 {9 (shoulder_rise)10 [waist -40, knees -30 time: 0.6]11 [relax shoulders, elbows, wrists strength 0.3]12 [vf ( -50, 300) on: trunk, by: leftWrist ]13 [symm]14 }15 after 0.816 {17 (hip_move_back)18 [knees -110, hips 40, waist 80,19 elbows 60, wrists 180 child time: 0.5]20 [relax shoulders strength 0.4]21 [vf ( -100, 300) on: trunk, by: leftWrist ]22 [symm]23 }24 after 0.625 {26 (push)27 [waist 90 parent, hips 100 parent, knees -130 time: 0.4]28 [relax shoulders, elbows strength 0.1]29 [vf ( 200, -300) on: leftHand, by: waist]30 [symm]31 }32 after 1.033 {34 (right_foot_relo)35 [ik ( 0.10, 0.3), ( 0.28, -0.15)36 on: rightAnkle rel: leftAnkle time: 0.5]37 [vf ( 0, 500) on: trunk, by: leftKnee]38 [rightAnkle 180 child time: 0.4]39 [leftHip 90 parent, waist 90 parent, necks 90 parenttime: 0.0]3940 [shoulders 0, necks 0 time: 0.0]41 [relax shoulders, elbows, wrists strength 0.2]42 }43 and when contact rightFoot after 0.544 {45 (left_foot_relo)46 [vf sb( 1000, 800) on: trunk, by: rightAnkle]47 [vf ( 0, 800) on: trunk, by: rightAnkle]48 [rightKnee 0, rightHip 0, waist 0, leftHip 0 time: 1.5]49 [leftAnkle 180 child time: 0.5]50 [ik ( 0.0, -0.08) on:leftAnkle rel: rightAnkle time: 0.5]51 [relax rightAnkle strength 0.2]52 [relax shoulders, elbows, wrists strength 0.2]53 }54 and when contact leftFoot after 1.055 {56 (rise)57 [vf sb( 400, 400) on: trunk, by: leftAnkle]58 [symm]59 [vf ( 0, 500) on: trunk, by: leftAnkle]60 [symm]61 [relax ankles strength 0.2]62 [relax shoulders, elbows, wrists strength 0.2]63 [knees 0, hips 0, waist 0, necks 0 time: 1.5]64 }40Figure 4.8: Prone-to-stand motion sequence41Chapter 5OptimizationWe have shown that many motions can be authored from the instantiation of sev-eral simple primitives using the Simple Scripting Language (SCL). However, anauthored motion only exhibits one particular style. It is common that animatorswant to create different styles of the same motion. For example, given a kip-upmotion, they may also wish to develop a faster kip-up. This can be achieved by aparameterized motion controller. Variations of the same motion can be producedby making appropriate choices for the parameter values. In order to produce a par-ticular desired variation of a motion, one can define an objective function to modelhow well a motion achieves a desired style, and optimize the control parametersfor the given objective function. In this chapter, we develop a parameterization andoptimization framework that allows animators to specify the parameterization of ascripted motion that is then optimized for a custom defined objective function.5.1 Problem DefinitionWe define pix as a motion control policy parameterized by a vector x ? RN . Theoptimization problem can be defined as minimizing the objective function:x? = argminxJ(pix)The objective function J is defined by the user and its value is observed duringa simulation. The value returned by the objective function can range from a de-42sired kinematic property at a particular instance in time, e.g., maximum height of ahuman body CoM, to an aggregation of a dynamic property over the course of theentire simulation e.g., total energy used by the motion.Given the state of physics world st at time t, the dynamics simulation producesthe world state at the next step t +? t:st+? t = S(st ,? t,pix)where st ,st+? t ? S are vectors in a high dimensional space of all plausible states ofthe simulated world; ? t is the time of each simulation step. The entire motion of du-ration T is then defined as the sequence {s0,s1,, ...,sn}, where si = Si(s0,? t,pix)and n ?? t = T . In order to obtain information for each simulation step, an evalua-tion function is defined according tof (s), f : S? Rkthat maps a state to a vector of dimension k. The objective function can then berewritten asJ(pix) = aggni=0( f (Si(s0,? t,pix))) (5.1)where agg is an aggregation function that collects all the evaluated values for all thesimulation steps, aggregates them using a user-defined rule, typically a weightedsummation, and returns a scaler value.In Equation 5.1, the free variables of optimization are x. The other variablesremain fixed during optimization; ? t = 0.25ms in all simulations; Si is a determin-istic function representing the dynamic simulation. The remaining componentsthat need to be defined by a user are:? s0, the initial state as designed by users using a pre-populated list of posesand environments. For example, an initial state can be one with the characterstanding on ground, lying on ground, sitting on a chair, etc.? pix is the parameterization of motion that is defined by the user in the motionscript. A user can select the numerical fields in a script and prefix them witha ?@? annotation to make them free optimization variables.43? f (s) is a user-defined function that maps the state of the current simulationstep to a desired custom-sized vector. For example, a user can define f (s) toreturn the CoM position of the current simulation step.? agg is also a user-defined function. It aggregates the custom-sized vectorsreturned by f (s) for all simulation steps, and returns a scalar value that willbe used by optimization as the objective.? n is the number of simulation steps needed for a simulation episode, givenby n = T/? t, where T is the desired duration of simulation. T is set by theuser empirically.Once all these components are specified by a user, J(pix) can be treated as ablack-box function. An invocation on this function will result in a physics simula-tion for T seconds. During the simulation certain conditions need to be satisfied inorder for the motion to be feasible, e.g., a kip-up motion needs to successfully endin a standing position. Feasibility can only be evaluated after a motion is simulated.It is the user?s responsibility to define f (s) and agg to implement feasibility as asoft constraints, i.e., J(pix) should return a large penalty value when the motion isinfeasible.5.2 CMA-ES OptimizationThe objective function J(pix) does not have a well-defined gradient or Hessian be-cause of its unrestricted nature. Therefore, we choose a derivative-free optimiza-tion algorithm. Recent studies [8, 26, 36] have shown that Covariance MatrixAdaptation Evolution Strategy (CMA-ES) [3, 20] is an optimization techniquethat is well suited for solving non-convex and discontinuous problems. CMA-ESis a stochastic and derivative-free algorithm. It falls into the family of evolutionaryoptimization strategies. In each iteration, new generation of candidate solutions aregenerated by variation of its ancestors, i.e. solutions from previous iteration, andsome solutions are selected according to fitnesses, i.e. objective function values,from the new generation to inform creation of the next generation. This processrepeats until a good solution is found or the number of iterations exceeds a limit.In CMA-ES, a Gaussian distribution with mean ? , covariance matrix ? and step44Figure 5.1: An illustration of CMA-ES running on a simple 2D problem. Thevalue of the function is depicted by the white contours with brighter re-gions representing a better value. The black dots are individual solutionsin a generation and orange dashed boundaries represent the Gaussiandistribution N (?,?2?). Adapted from Wikipedia [1].size ? is used to sample every new generation, where the covariance matrix de-cides the shape of the distribution and the step size decides its magnitude. Uponthe sampling of a new generation, the fitness of each candidate is used to updatethe mean, the covariance matrix and the step size. An intuition is that when the fit-ness increases along one particular direction, the step size becomes larger and theshape of covariance matrix gets thinner in the direction orthogonal to the increasingdirection, thus accelerating the convergence speed.5.3 ResultsFor the CMA-ES algorithm, we use the freely Java implementation [2]. The op-timization is performed offline. The most expensive operation in the algorithm isto evaluate the fitness of each sampled solution. Fortunately, performance can be45boosted if the evaluation of sampled solutions are done concurrently. After sam-pling for each generation, the fitness evaluations for each individual candidate canbe made independently from each other. This makes it possible to modify theCMA-ES algorithm to do parallel evaluation of fitness for all the sampled solu-tions within one generation. As discussed later, we use a multithreaded multicoreimplementation.5.3.1 Kip-up MotionWe optimize the kip-up motion for a more athletic style, namely, a kip-up mo-tion in which the character thrusts higher and stays longer in air but ends up in astanding position more quickly. The motion script that we used is taken from thekip-up motion from previous chapter, and we modified the script to add parameter-ization by adding a ?@? annotation before every numerical field to make them freeparameters for optimization. This makes for a vector of 50 free parameters.The goal of the optimization is to minimize an objective J(pix) that is definedas the weighted sum of five terms:J(pix) =?iwiJi(pix) (5.2)where i ? {time,height,airborne,energy,skid, f inal state} is the index of thesedifferent terms. We will describe each term in further details.The time objective captures the total time used to reach a stand position. Itsevaluation function ftime(s) is given by:ftime(s) = ? t ?H(yhead?1.8)where ? t is the simulation time step that can be accessed by the f (s) functions,H(x) is a step function, yhead is the current height of character?s head, and 1.8meters is the approximate height of the head when the character is standing up-right. The aggtime function is a summation of the values { ftime(si)}. Thus Jtime(pix)returns the total duration for which the character?s head is lower than 1.8 meters.The height term describes the maximum height reached by the character?spelvis during the airborne phase. While we want to maximize the actual height46value, the optimization performs a minimization by default. Therefore, we negatethe height value in this objective term, as defined in fheight :fheight =????ypelvis if airborne0 otherwisewhere ypelvis is the height of the pelvis. The aggheight function is defined as the minoperation, indicating Jheight returns the height that has the largest absolute value.The airborne term captures the duration of the airborne phase. Similarly to theheight term, we negate the actual time. Its evaluation function fairborne(s) is givenby:fairborne =????? t if airborne0 otherwiseThe energy term is used to calculate the effort spent during the motion. Theeffort is approximated as the sum of ?2i . We want to minimize the effort defined byfenergy(s) as the follows:fenergy = ? tjoints?i?2iwhere ?i is the torque of each joint.The skid term is to penalize the foot sliding behaviour. fskid is defined as:fskid =???? t?feeti |?i?pi|2 ?H(|?i?pi|? 19pi) if foot in contact0 otherwisewhere H(x) is the step function, ?i is the orientation of foot in radian, and pi isthe foot orientation when it is well planted on ground. It penalizes foot sliding byintroducing a quadratic penalty on a foot that tilts for larger than 20 degrees ( 19pirad) when it is in contact with the ground. The aggi function for airborne, energyand skid terms are all defined as sum operators.Lastly, the final state term defines the constraint forcing the character to be in astanding position at the end of motion. It simply returns a very large positive valueif the head position is lower than 1.8 meters at the last simulation step, meaning47the character should not fall onto the ground.We set the weight for each term as the follows: wtime = 1, wheight = 10, wairborne =10, wenergy = 150000 , wskid = 10 and w f inal state = 1. This scales each objective termto approximately the same magnitude. The height term and the airborne term havea bit larger weight in an attempt to produce motions with a more easily identifiedairborne style. The simulation is set to run for 5 seconds before returning the ob-jective value. The motion is simulated using JBox2D [4]. The initial state s0 ischosen to have the character lying on the ground. ? t is set to 0.25ms. The CMA-ESalgorithm samples 19 candidates per generation and optimization runs on a clus-ter with 20 cores. Each simulation (J(pix)) finishes in about 3 seconds, and onegeneration of optimization takes about 4 seconds. It takes around an hour to gener-ate 1000 iterations. After 1000 iterations the objective function decreased in valuefrom ?0.336 to ?13.921. The rise up time is reduced from 2.962s to 2.577s, themaximum height increases from 0.586m to 1.253m, and the airborne time increasesfrom 0.170s to 0.846s, yielding a 17% decrease in kip-up time, 114% and 398% ofincrease in maximum height and airborne time respectively. The energy term re-mains the almost the same: 210142.719(Nm)2 v.s. 215812.203(Nm)2 before andafter optimization. However, it is clear that with the same energy, the optimizedmotion shown in Figure 5.2 is noticeably more athletic than the original motion asseen in Figure 4.4 and Figure Prone-to-Stand MotionWe also optimize the prone-to-stand motion for a quicker and more efficient mo-tion. The objective function takes the same form as in Equation 5.2. We use aslightly different selection of terms, where i?{time,energy,contactless,skid, f inal state}.time, energy and final state are same as in the previous section. We made a changeto the skid term and added a contactless term. For the skid term, we modifiedfskid(s) as follows:fskid =???? t?feeti |?i?pi|2 ?H(|?i?pi|? 19pi) if foot in contact and yhead > 1.5m0 otherwise48(a)(b)(c)(d)Figure 5.2: More athletic kip-up motion achieved after 1000 iterations of op-timization49The only change made to the fskid term is that it now only evaluates the skid termwhen the character?s head rises above 1.5m. This ensures that the feet orientationsin the early phases are not accounted into the objective. The contactless term pe-nalizes the time for which the character has no contact with the ground. It is anegation of fairborne:fcontactless =???? t if character has no contact with ground0 otherwiseThe weight of each term is set to: wtime = 1, wenergy = 1/50000, wcontactless =10000, wskid = 100. Each simulation runs for 6 seconds in JBox2D. The characterhas an initial prone pose on the ground. ? t is set to 0.25ms. The motion con-troller has 45 free parameters. The CMA-ES algorithms samples 16 candidates pergeneration. We use 17 cores to run the optimization. It takes around 40 minutesto finish 1000 iterations of optimization. The objective function value of the op-timized motion decreases from 498.5 to 6.1. Consequently, the optimized motionlooks more efficient and more natural than the input motion. Noticeably, the energyterm has decreased from 206414.4(Nm)2 to 83262.1(Nm)2, and the rising time hasdecreased from 4.4s to 1.9s. The values of both terms have decreased by around57%, resulting in a much faster and more efficient motion as seen in Figure 5.3.50(a)(b)Figure 5.3: More efficient prone-to-stand motion achieved after 1000 itera-tions of optimization51Chapter 6State-Action Compatibility ModelFor many motions, there are often a multitude of actions that can be used to per-form a given motion task, or a multitude of situations in which we wish to performthe motion. In this chapter we introduce a framework for modeling the space of allpossible ways that a motion can be achieved within a predefined space of actions.We call this a space-action compatibility model because it consists of learning anenclosed hypervolume in the state-action space. This hypervolume will be mod-elled using a Support Vector Machine (SVM). Any point inside the hypervolumemeans that the state (the ?situation?) and the action are compatible, i.e., that thegiven action applied in the given situation will lead to the successful completion ofthe task. The model thus attempts to capture all possible valid actions for a givensituation, and conversely all possible situations (or states) in which a given actionleads to successful motions. As an illustrative example, consider the task of risingup from a chair. In this task, the state can be described as the dimensions of thechair, and action can be described as the controller that attempts to perform therise-up motion. The state-action compatibility model then maintains a hypervol-ume that contains compatible points, each point meaning the chair dimension iscompatible with controller, i.e., the controller can perform a successful sit-to-standmotion from that chair.Given a ds-dimensional state or situation instance s, s?Rds , and a da-dimensionalaction parameterization a, a ? Rda , a state-action point is denoted as: (s,a) and52Figure 6.1: Abstract view of state-action compatibility modelcompatibility function is then defined as:J((s,a)) =???1 if s and a are compatible0 otherwisewhich is evaluated through the process of physics simulation.We propose to learn a corresponding state-action compatibility model:J?((s,a))? J((s,a))where J?((s,a)) is an approximate model of J((s,a)) but can be evaluated in sig-nificantly less time.The concept of state-action compatibility model is illustrated in Figure 6.1. Theprocess to acquire J? is defined by two steps:1. Sampling: given an initial point of compatible state-action (s0,a0), whereJ((s0,a0)) = 1, we explore the compatibility and incompatibility regions53within the state-action spaceR(ds+da) by sampling points starting from (s0,a0)and gradually moving towards more distant regions.2. Learning: a classification model J?((s,a)) is learned from the sampled pointsthat can be used to predict compatibility.Once the classification model J?((s,a)) is acquired, it can be used to performdifferent operations. For example, it can be used directly, i.e., given (s,a), it deter-mines if the they are compatible. Alternatively, it can be used indirectly as part ofa query engine to get compatible actions or states: given s, it returns {ai}, i.e., a setof actions that are compatible with s; or given a, return {si}, i.e., a set of situationscompatible with a.The query engine takes as input the desired state s or the desired action a, andformulates a diverse optimization problem [7] that finds a diverse set of points thatare compatible with the input, i.e., a set of actions {ai} for state input s or a set ofstates {si} for action input a.In the remainder of this chapter, we will go through each step and demonstratethe results of state-action compatibility for the sit-to-stand motion.6.1 SamplingIn order to build the state-action compatibility model, we need to generate state-action data and use this data to learn a classification model. Each of these datapoints is a trial of a specific action for a specific state. It is performed by a physics-based simulation and evaluated by the function J((s,a)) to indicate whether state-action point is compatible. The sampled data points should ideally cover as muchof the compatible regions as possible. The sampling algorithm should also clearlymodel the boundary between compatible and incompatible regions by samplingpoints close to the actual boundary.We develop an iterative algorithm for probabilistically sampling points alongdifferent paths. An abstract view of this method is illustrated in Figure 6.2. Eachsampling path maintains a multivariate Gaussian distribution, N (?,?), i.e. a co-variance matrix, ?, and a location point ? , from which all the samples are drawn.The Gaussian distributions are updated at each iteration using the sampled points.54Figure 6.2: Abstract view of sampling algorithm. There are three samplingpaths. The evolution of Gaussian distribution along one sampling pathis illustrated.The sampling path is loosely defined as the iterative evolution of location points,{? :}. Over repeated iterations, we update the Gaussian distribution so that thelocation point ? along each sampling path remains in the compatible region, but itis pushed further away from ? in the other sampling paths. This helps samplingpaths go to different directions and thus makes sure that the algorithm explores dif-ferent regions that are distant from each other. The covariance matrix ? is updatedto adjust its shape along the dimensions orthogonal to the direction of the samplingpath. Intuitively, these orthogonal dimensions in the covariance matrix are shapedwide enough so that points at a certain distance from ? , i.e. incompatible points,can be sampled with a non-trivial probability, but not so wide that points close to? , i.e. compatible points, have too little probability to be sampled.We use a round-robin CMA algorithm for the purpose of maintaining Gaussiandistributions and sampling points. For a state-action problem with n? 1 dimen-sions, we use n sampling paths. Each sampling path maintains a CMA algorithm.55The n sampling paths all start with the same initial state-action point. For each iter-ation, CMA of each sampling path samples a new generation of points and updatesthe internal Gaussian distribution using these points. This process is repeated untilit reaches a specified number of iterations. All the points sampled using CMA arekept as training data.Each path?s CMA optimization attempts to maximize an objective functionwhich we will define shortly. The objective function is designed with two purposesin mind: depth, i.e., a path?s location point ? should reach to distant regions, andbreadth, i.e., the covariance matrix ? should adapt to the orthogonal dimensions ofeach path?s direction. Let p = (s,a) be a state-action point. Every sampled pointalong the sampling path m is initially assigned an objective value ofdi =n?j 6=m??pi? pbest j??+Kminj 6=m??pi? pbest j???C ? (1? J(pi)) (6.1)where {pi} are the sampled points within the iteration, pbest j is the point with thebest objective in another sampling path j, and J(p) = J((s,a)) returns 1 if the state-action point is compatible and 0 otherwise. The first two terms on the right handside of Equation 6.1 represents the sum of distances and the minimum distancefrom the current sampled point to the best points in other paths. We set K = 5to reward a large minimum distance. C is set to a very large positive numberto penalize an incompatible point. We can then find the best point pk from thisgeneration:pbest = pk , k = argmaxidiThis can be seen as finding the point with the best depth objective. The objec-tive value of the non-best points are further updated with both depth and breadthobjectives. We approximate the direction of the current path using the line:(plast , pbest)where plast is the point in the last generation that had the best objective or simplythe initial point for the first generation. For every sampled point pi, its orthogo-nal projection onto the line (plast , pbest) is denoted by ppro ji . The two quantities56??pi? ppro ji?? and??ppro ji? pbesti?? are then related to the breadth and depth respec-tively. We then use the updated objective value ji, written as:ji =?????????di if i = kmax(0,di +K2(??pi? ppro ji??)???ppro ji? pbesti??2) if i 6= k,J(pi) > 0?|pi? pbesti | if J(pi) = 0(6.2)where K2 is the parameter to reward point in large breadth, and we choose 2 asits value. The underlying CMA algorithms then iteratively updates its Gaussiandistribution by trying to maximize this objective value.6.2 LearningFrom the sampling stage, we get a set of training data of the formD ={((s,a)i,yi) | (s,a)i ? Rds+da , yi ? {0,1}}ni=1We use a support vector machine (SVM) with a Gaussian radial basis kernelto train a classification model that predicts the compatibility of any point in thestate-action space. An SVM finds a set of support vectors among the input data setthat divides the entire space into two regions by maximizing the smallest distanceof a training point to its predicted boundary.6.3 QueryingOnce the classification model J?(s,a) is learned, we can use it to query for actions.The query problem is defined as follows: given a state s0, and the number of pointsn, we want to return {a}n, i.e., n different actions that are likely to be compatiblewith the given state.The algorithm starts by randomly selecting a support vector (sinit ,ainit) fromthe learned SVM that is known to lie in a compatible region and sinit is close to s0:|sinit ? s0| < ? . We use sinit as the seed point and optimize (s,a) to minimize thefollowing objective:|s? s0|+C((s,a))57where C(s,a) is a penalty function that evaluates to positive infinity for incompati-ble points of state-actions.The optimization problem returns a point (s0,a0). From this point, we for-mulate a diversity optimization problemto find a set of n action parameters thatminimize the diversity objective similar to [7]:D =?n?i=0(C(s0,ai)?n?j=0(??ai?a j??+Kdmin(ai)))where {ai} denotes the set of n action parameters, C(s,a) is the same penalty func-tion described earlier. The parameter K rewards a point ai that has a large distanceto the closest neighbour in set {ai}. We use K = 5. A round-robin CMA algorithmis used to minimize D. One generation of CMA optimization is applied to each ofthe n action parameters in turn, before moving on to the next generation of CMAoptimization for each of the action parameters.6.4 ResultsWe experiment with the state-action model on a sit-to-stand motion for a planarhuman character. The input motion is a modification of the sit-to-stand motion inthe previous motion, with arm movements added in phase 1. The motion script isgiven in Listing 6.1:Listing 6.1: Sit To Stand Script1 {2 (lean)3 [waist @30, hips 120 time: 0.3]4 [shoulders @20, elbows 40 time: 0.3]5 }6 after 0.47 {8 (standup)9 [vf sb(400, 300) on: trunk, by:leftAnkle]10 [symm]1112 [vf (0, 400) on: trunk, by:leftAnkle]58Figure 6.3: State-action parameterization of the sit-to-stand problem. Thestate parameter is the height of the chair h, the action parameters are thetarget waist angle ?waist , and the target shoulder angles ?shoulders.13 [symm]14 [knees 0, hips 0, waist 0, necks 0 time: 1.9]15 [relax ankles, shoulders, elbows, wrists strength 0.1]16 }The action parameters are ?waist , i.e., the target waist angle in the ?lean? phase,and ?shoulders, i.e., the target shoulder angles in the ?lean? phase: x =(?waist ,?shoulders).They are parameterized in line 3 and 4 in Listing 6.1, and can be visualized in Fig-ure 6.3. The state parameter is the height of chair s = (h). We thus have a 3-Dstate-action space in which each point is in the form of p = (h,?waist ,?shoulders).We limit the sampling range on each dimension: 0.15 < h < 0.75, 0 < ?waist < 90,and 0 < ?shoulders < 180. Every point outside this range is deemed as infeasible.Sampling starts with the compatible point (0.45,30,20), and keeps n = 4 pathsof CMA. For the purpose of distance measurement, we scaled the state-actionpoints with the vector (10,1/40,1/40) in order to compensate for the dimensionsthat have smaller magnitudes. Each generation of a single CMA direction sam-ples 7 points, each point requires a simulation of 2.5 physics seconds with 0.25mstime step, and it takes around 2 seconds to finish simulation. The sampling is doneoffline. In 6 hours, 359 iterations are sampled with a total 10052 points, among59Figure 6.4: Input motion (s,a) = (0.45,30,20)which 1323 are incompatible points and 8729 are compatible points.These 10052 points are used as the training data set for the SVM. We uselibsvm [10] to train the data sets. The slack parameter c is set to 64 and kernel pa-rameter g is set to 4. We assign compatible points a weight of 1 and incompatiblepoints a weight of 4, because the numbers of compatible and incompatible pointsare not balanced. The training process takes less than 1 s. The 5-fold cross valida-tion rate is 96.5778%, and in the result model the SVM prediction model consistsof 176 support vectors. The SVM predict operation has complexity of O(N) whereN is the number of support vectors.The query engine first runs CMA optimization to get the initial action pointainit , and then run the diverse optimization for 50 iterations. The number of iter-ation is picked empirically so that it is not too small such that resulting motionslook very similar but not too big that returned points are very close to the boundaryof state-action model. For each query, we set n = 3, i.e. querying for 3 differentactions. We test the query for three given states s = (0.45),s = (0.16),s = (0.65)respectively.The input motion uses a chair height of h = 0.45 and it is shown in Figure 6.4.We use the state action model to query for three motions with the different heightsh = 0.45, h = 0.16 and h = 0.65. Running the three queries requires 831ms inaverage for this problem. The result is shown in Figures 6.5, 6.6 and 6.7. Thecharacter is capable of standing from a chair which is significantly lower than theoriginal chair as shown in Figure 6.6. It also shows the ability to jump out of ahigher chair and finally stands on ground shown in Figure 6.7. The state-action60(a) motion 1(b) motion 2(c) motion 3Figure 6.5: Three motions are queried from state-action model with the sameheight as the initial chair height, h = 0.45. Motion 1 has a highly flexedwaist; motion 2 does not bend the waist; motion 3 uses hands to pushthe chair.compatibility model does not guarantee all queires can perform actions success-fully. This is shown in the motion 1 of Figure 6.7.61(a) motion 1(b) motion 2(c) motion 3Figure 6.6: Three motions are queried from state-action model with the a dif-ferent chair height h = 0.16. Motion 1 has a small bend on waist; mo-tion 2 has a highly flexed waist and pushes the chair; motion 3 also hasa highly flexed waist but pushes the ground.62(a) motion 1(b) motion 2(c) motion 3Figure 6.7: Three motions are queried from state-action with the height h =0.65. The human character?s feet are hanging in the air at the beginning.Motions 2 and 3 look very similar and motion 1 failed.63Chapter 7ConclusionWe have presented a framework for creating physics-based character animationsusing a flexible simple controller language (SCL) that has several useful built-inmotion primitives. The language has a simple syntax and does not require anima-tor?s expertise in programming. It provides animators with a semi-interactive en-vironment to debug the motion, thus potentially help designing and tuning physicsmotions more efficiently. This also opens a window for sharing of motion con-trollers and reproducible animation research. We demonstrate several motions pro-duced using the SCL including kip-up, sit-to-stand, walk and prone-to-stand. Anoptimization framework makes it easier to refine and stylize motions. We showthat the optimization tool has automatically produced a more energetic variation ofa kip motion that is produced by an hand-engineered motion script.To synthesis a wide family of motions given varied environments, we exploredthe state-action compatibility model, which is built offline and enables animatorsto query online a number of different motions given a changed environment. Thisadds to the toolset of physics animators the capability of designing one motion andgeneralizing it to various scenarios. Using the state-action compatibility model,we show various sit-to-stand motion variations that can perform on different chairheights.647.1 DiscussionWhen using FSM-based controllers to create physics motions, it is useful to havea set of control primitives. The primitives that we use in this thesis include PDcontrol, virtual force, inverse kinematics and simple quiescent stance feedbacks.In many cases, these primitives can be used qualitatively to create a rich set ofmotions. However, it is yet unclear how we can directly arrive at a specific robustcontroller for a given motion. For example, for a walk motion, how can we relate avirtual force?s magnitude to the walk speed? Due to this reason, manual tuning, op-timization or more complex feedback rules may need to be employed in designinga motion.While the existing set of control primitives constitute a powerful set of controllanguage, it can also be useful to think at a higher level of abstractions. For ex-ample, virtual force in general can be applied to a character to potentially movethe CoM of the whole body in a desired direction, but it does not yet work wellwith a situation where the two stance feet are not colocated. It would be helpfulto have a higher level of abstraction that regulates the exact position of CoM yetautomatically takes care of other constraints such as balance. Another potentialhigher level primitive could be one that relocates a stance foot contact positionwhile maintaining the upper body pose.7.2 Future WorkThe motions produced for this thesis are all planar motions. An immediate futurework direction is to extend all the current motions to 3D characters. This willrequire introducing more degrees of freedom for the joint angle space as well asthe Cartesian space. The SCL will likely remain almost the same except a mostnoticeable change is that joints will likely need to be specified by quaternions. Thecontrols strategies will also need to consider lateral balance.One limitation of this work is that it requires motion authors to tweak controlparameters in order to get a proper motion. This can require a significant amount ofwork for complicated motions. A helpful improvement on the system would be touse online optimization to achieve desired goals of a motion phase. For example,at the end of kip-up motion?s phase 4, the character requires a large momentum to65propel itself off the ground. It is rather difficult and time consuming to manuallyfind the right parameters to achieve larger momentum. An online optimization toolcan help the author to refine the parameters of this phase, while freeing the authorto start designing the next phase. This makes a motion design easier and quicker.A trade-off needs to be made between the conciseness of the SCL and its ver-satility. The more built-in primitives the language provides, the more powerful itis, but also the less readable it becomes. It currently provides a single feedbackprimitive that helps maintain balance while in stance. It is clear that more feed-back rules will make it easier to create a greater variety of motions. For example,a built-in feedback rule for foot placement based on an inverse pendulum modelcan help the user create walking and running locomotion more easily, but this ruleis very specific to the semantics of a walk, and does not make too much sense toauthors who want to develop rising controllers.66Bibliography[1] CMA-ES. ? pages iii, viii, 45[2] CMA-ES source code. inmatlab.html. ?pages 45[3] The CMA evolution strategy. ?pages iii, 44[4] jbox2d. ? pages 30, 48[5] Tutorial - kip up / kick up. pages 33[6] Valley of the dogbots of war. ? pages iii[7] Shailen Agrawal, Shuo Shen, and Michiel van de Panne. Diverse motionvariations for physics-based character animation. In Proceedings of the 12thACM SIGGRAPH/Eurographics Symposium on Computer Animation, pages37?44. ACM, 2013. ? pages iii, 9, 54, 58[8] Mazen Al Borno, Martin de Lasa, and Aaron Hertzmann. Trajectoryoptimization for full-body movements with complex contacts. IEEETransactions on Visualization and Computer Graphics (TVCG), 2012. ?pages 8, 44[9] BBC. ?wildcat? robot put through its paces, 2013. ? pages 2[10] Chih-chung Chang and Chih-Jen Lin. Libsvm ? a library for support vectormachines. ? pages 6067[11] Stelian Coros, Philippe Beaudoin, and Michiel van de Panne. Robusttask-based control policies for physics-based characters. In ACMTransactions on Graphics (TOG), volume 28, page 170. ACM, 2009. ?pages 9[12] Stelian Coros, Philippe Beaudoin, and Michiel van de Panne. Generalizedbiped walking control. ACM Transactions on Graphics (TOG), 29(4):130,2010. ? pages vii, 8, 9, 10[13] Stelian Coros, Andrej Karpathy, Ben Jones, Lionel Reveret, and Michiel VanDe Panne. Locomotion skills for simulated quadrupeds. ACM Transactionson Graphics (TOG), 30(4):59, 2011. ? pages 8[14] Petros Faloutsos, Michiel Van de Panne, and Demetri Terzopoulos.Composable controllers for physics-based character animation. InProceedings of the 28th annual conference on Computer graphics andinteractive techniques, pages 251?260. ACM, 2001. ? pages 9[15] Christian Gehring, Stelian Coros, Marco Hutter, Michael Bloesch, Markus AHoepflinger, and Roland Siegwart. Control of dynamic gaits for aquadrupedal robot. In IEEE International Conference on Robotics andAutomation (ICRA), 2013. ? pages 8[16] Thomas Geijtenbeek and Nicolas Pronost. Interactive character animationusing simulated physics: A state-of-the-art review. In Computer GraphicsForum, volume 31, pages 2492?2515. Wiley Online Library, 2012. ? pages6, 8[17] Thomas Geijtenbeek, Nicolas Pronost, and Frank van der Stappen. Simpledata-driven control for simulated bipeds. In Proceedings of the ACMSIGGRAPH/Eurographics Symposium on Computer Animation, pages211?219. Eurographics Association, 2012. ? pages 9, 10[18] Sehoon Ha, Yuting Ye, and C Karen Liu. Falling and landing motion controlfor character animation. ACM Transactions on Graphics (TOG), 31(6):155,2012. ? pages 9, 10[19] N. Hansen and A. Ostermeier. Completely derandomized self-adaptation inevolution strategies. Evolutionary Computation, 9(2):159?195, 2001. ?pages iii[20] Nikolaus Hansen and Andreas Ostermeier. Completely derandomizedself-adaptation in evolution strategies. Evolutionary computation,9(2):159?195, 2001. ? pages 4468[21] Sumit Jain, Yuting Ye, and C Karen Liu. Optimization-based interactivemotion synthesis. ACM Transactions on Graphics (TOG), 28(1):10, 2009.? pages 9[22] Taesoo Kwon and Jessica Hodgins. Control systems for human runningusing an inverted pendulum model and a reference motion capture sequence.In Proceedings of the 2010 ACM SIGGRAPH/Eurographics Symposium onComputer Animation, pages 129?138. Eurographics Association, 2010. ?pages 8[23] Joseph Laszlo, Michiel van de Panne, and Eugene Fiume. Limit cyclecontrol and its application to the animation of balancing and walking. InProceedings of the 23rd annual conference on Computer graphics andinteractive techniques, pages 155?162. ACM, 1996. ? pages 9[24] Joseph Laszlo, Michiel van de Panne, and Eugene Fiume. Interactive controlfor physically-based animation. In Proceedings of the 27th annualconference on Computer graphics and interactive techniques, pages201?208. ACM Press/Addison-Wesley Publishing Co., 2000. ? pages 8[25] Yoonsang Lee, Sungeun Kim, and Jehee Lee. Data-driven biped control.ACM Transactions on Graphics (TOG), 29(4):129, 2010. ? pages 6[26] Libin Liu, KangKang Yin, Michiel van de Panne, and Baining Guo. Terrainrunner: control, parameterization, composition, and planning for highlydynamic motions. ACM Transactions on Graphics (TOG), 31(6):154, 2012.? pages 44[27] Adriano Macchietto, Victor Zordan, and Christian R Shelton. Momentumcontrol for balance. In ACM Transactions on Graphics (TOG), volume 28,page 80. ACM, 2009. ? pages vii, 6, 7[28] Igor Mordatch, Emanuel Todorov, and Zoran Popovic?. Discovery ofcomplex behaviors through contact-invariant optimization. ACMTransactions on Graphics (TOG), 31(4):43, 2012. ? pages 7[29] Igor Mordatch, Jack M Wang, Emanuel Todorov, and Vladlen Koltun.Animating human lower limbs using contact-invariant optimization. ACMTransactions on Graphics (TOG), 32(6):203, 2013. ? pages vii, 7[30] Jerry Pratt, Chee-Meng Chew, Ann Torres, Peter Dilworth, and Gill Pratt.Virtual model control: An intuitive approach for bipedal locomotion. TheInternational Journal of Robotics Research, 20(2):129?143, 2001. ? pages869[31] Marc H Raibert and Jessica K Hodgins. Animation of dynamic leggedlocomotion. In ACM SIGGRAPH Computer Graphics, volume 25, pages349?358. ACM, 1991. ? pages 8[32] Yuval Tassa, Tom Erez, and Emanuel Todorov. Synthesis and stabilization ofcomplex behaviors through online trajectory optimization. In IntelligentRobots and Systems (IROS), 2012 IEEE/RSJ International Conference on,pages 4906?4913. IEEE, 2012. ? pages 8[33] Michiel Van de Panne, Ryan Kim, and Eugene Fiume. Virtual wind-up toysfor animation. In Graphics Interface, pages 208?208. Citeseer, 1994. ?pages 8[34] Kiril Vidimc?e, Szu-Po Wang, Jonathan Ragan-Kelley, and WojciechMatusik. Openfab: A programmable pipeline for multi-material fabrication.ACM Transactions on Graphics, 32, July 2013. ? pages 3[35] Jack M Wang, David J Fleet, and Aaron Hertzmann. Optimizing walkingcontrollers. In ACM Transactions on Graphics (TOG), volume 28, page 168.ACM, 2009. ? pages 9[36] Jack M Wang, Samuel R Hamner, Scott L Delp, and Vladlen Koltun.Optimizing locomotion controllers using biologically-based actuators andobjectives. ACM Transactions on Graphics (TOG), 31(4):25, 2012. ? pages44[37] Wikipedia. Bigdog, 2013. ? pages 2[38] Wikipedia. Renderman, 2013. ?pages 3[39] Andrew Witkin and Michael Kass. Spacetime constraints. In ACM SiggraphComputer Graphics, volume 22, pages 159?168. ACM, 1988. ? pages 7[40] Wayne L Wooten and Jessica K Hodgins. Animation of human diving. InComputer Graphics Forum, volume 15, pages 3?13. Wiley Online Library,1996. ? pages vi, 21[41] KangKang Yin, Kevin Loken, and Michiel van de Panne. Simbicon: Simplebiped locomotion control. In ACM Transactions on Graphics (TOG),volume 26, page 105. ACM, 2007. ? pages vii, 3, 8, 9, 10[42] Peng Zhao and Michiel van de Panne. User interfaces for interactive controlof physics-based 3d characters. In Proceedings of the 2005 symposium onInteractive 3D graphics and games, pages 87?94. ACM, 2005. ? pages 870


Citation Scheme:


Citations by CSL (citeproc-js)

Usage Statistics



Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            async >
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:


Related Items