GAIT ANIMATION AND ANALYSIS FOR BIOMECHANICALLY­ ARTICULATED SKELETONS by ERIC DAVID WILLS A DISSERTATION Presented to the Department of Computer and Information Science and the Graduate School of the University of Oregon in partial fulfillment of the requirements for the degree of Doctor of Philosophy March 2008 11 University of Oregon Graduate School Confirmation of Approval and Acceptance of Dissertation prepared by: Eric Wills Title: "Gait Animation and Analysis for Biomechanically-Articulated Skeletons" This dissertation has been accepted and approved in partial fulfillment of the requirements for the Doctor of Philosophy degree in the Department of Computer & Information Science by: Kent Stevens, Chairperson, Computer & Information Science Arthur Farley, Member, Computer & Information Science Christopher Wilson, Member, Computer & Information Science Gregory Retallack, Outside Member, Geological Sciences and Richard Linton, Vice President for Research and Graduate StudieslDean of the Graduate School for the University of Oregon. March 22, 2008 Original approval signatures are on file with the Graduate School and the University of Oregon Libraries. 111 © 2008 Eric David Wills IV An Abstract of the Dissertation of Eric David Wills for the degree of Doctor of Philosophy in the Department of Computer and Information Science to be taken March 2008 Title: GAIT ANIMATION AND ANALYSIS FOR BIOMECHANICALLY­ ARTICULATED SKELETONS Approved: Kent A. Stevens Digital three-dimensional (3D) models are useful for biomechanical analysis because they can be interactively visualized and manipulated. Synthesizing and analyzing animal locomotion with these models, however, is difficult due to the large number of joints in a fully articulated skeleton, the complexity of the individual joints, and the huge space of possible configurations, or poses, of the skeleton taken as a whole. A joint may be capable of several biological movements, each represented by a degree of freedom (DOF). A quadrupedal model may require up to 100 DOFs to represent the limbs and tnmk segments only, resulting in extremely large spaces of possible body configurations. New methods are presented here that allow limbs with any number of biomechanical DOFs to be kinematically exercised and mapped into a visualization space. The spaces corresponding to the ranges of motion of the left and right limbs are automatically intersected and pruned using biological and locomotion constraints. Hind v and fore spaces are similarly constrained so that Genetic Algorithms (GAs) can be used to quickly find smooth, and therefore plausible, kinematic quadrupedal locomotion paths through the spaces. Gaits generated for generic dog and reptile models are compared to published gait data to determine the viability of kinematics-only gait generation and analysis; gaits generated for Apatosaurus, Triceratops, and Tyrannosaurus dinosaur models are then compared to those generated for the extant animals. These methods are used for several case studies across the models including: isolating scapulothorax and shoulder joint functionality during locomotion, determining optimal ankle heights for locomotion, and evaluating the effect of limb phase parameters on quadrupedal locomotion. ..... .._------ VI _._ CURRICULUM VITAE NAME OF AUTHOR: Eric David Wills PLACE OF BIRTH: Santa Monica, CA, USA DATE OF BIRTH: November 19, 1977 GRADUATE AND UNDERGRADUATE SCHOOLS ATTENDED: University of Oregon, Eugene, OR USA DEGREES AWARDED: Doctor of Philosophy in Computer and Information Science, 2008, University of Oregon Master of Science in Computer and Information Science, 2002, University of Oregon Bachelor of Science in Computer and Information SciencelMathematics, 2000, University of Oregon AREAS OF SPECIAL INTEREST: Evolutionary Locomotion Synthesis Computational Biomechanics Computer Graphics and Animation Parallel and Distributed Computing PROFESSIONAL EXPERIENCE: Principal Engineer, Kaibridge, Inc., 5 years Software Engineer, Integrated Measurement Systems, 3 years Vll GRANTS, AWARDS AND HONORS: Graduate Teaching Fellow of the Year, Department of Computer and Information Science, University of Oregon, 2005 Inducted into Upsilon Pi Epsilon, International Honor Society for the Computer and Information Disciplines, 2003 Departmental Honors for completion of an honors thesis, Department of Computer and Information Science, University of Oregon, 2000 PUBLICATIONS: Stevens, K. A., Larson, P., Wills, E. D., & Andersen, A. (2008). Rex, sit: Digital modeling of Tyrannosaurus rex at rest. In P. Larson & K. Carpenter (Eds.), Tyrannosaurus rex: The tyrant king. Bloomington, IN: Indiana University Press. Stevens, K. A., & Wills, E. D. (2007). Kinematic constraints on the reconstruction of Dinosaur gaits. Proceedings of the Symposium on Vertebrate Paleontology and Comparative Anatomy, 55,54. Wills, E. D., & Stevens, K. A. (2007). Computational explorations of quadrupedal locomotion in Dinosaurs based on modem analogs. Proceedings of the American Society ofBiomechanics Northwest Symposium, 3, 18. Wills, E. D., & Stevens, K. A. (2007). Isolating functional degrees of freedom in limbs during locomotion. Proceedings of the Symposium on Vertebrate Paleontology and Comparative Anatomy, 55,46. Stevens, K. A., Wills, E. D., & Ernst, S. W. (2006). 3D Visualization of allometric changes in whole skeletons: Posture, proportion, and range of motion. Journal of Vertebrate Paleontology, 26(Suppl. 3A), 128. Stevens, K. A., Parrish, J. M., & Wills, E. D. (2005). Ontogenetic changes within the tyrannosaurid skeleton. In R. Scherer (Chair), Tyrannosaur Symposium 2005. Symposium conducted at the Burpee Museum of Natural History, Rockford, IL. Stevens, K. A., & Wills, E. D. (2001). Gracile versus robust cervical vertebral designs in sauropods. Journal of Vertebrate Paleontology, 21(Suppl. 3A), 104. Vlll ACKNOWLEDGEMENTS I would like to express my sincere appreciation to my family and friends for their support and advice throughout this process. Specifically, I would like to thank my caring parents Dr. David and Laurie Wills, my dedicated and entertaining sister Dr. Megan Wills Kullnat, and especially my loving, understanding, and beautiful wife Shelby Stair Wills. I would like to thank my committee for their guidance and expertise, especially Professor Kent A. Stevens, whose focused attention and patience over the last decade have shaped me into the professional that I am today. This work was supported in part by National Science Foundation grant 0093929. IX To my family and friends. ------ ._--------- x TABLE OF CONTENTS Chapter Page I. INTRODUCTION 1 II. BACKGROUND AND RELATED WORK 9 Automatic Character Animation 11 Global Optimization 11 Local Controllers 21 Fragment Composition 31 Evolutionary Algorithms 41 Evolutionary Locomotion 45 Controller Evolution 46 Artificial Life 59 Robotics 69 Computational Gait Analysis 76 Summary 92 III. METHODS AND MATERIALS 95 Functional Degrees ofFreedom 95 Limb Ranges ofMotion 97 Bipedal Gait Reconstruction 101 Constraints 101 Reconstruction 107 Pipeline 115 Quadrupedal Gait Reconstruction 117 Constraints 117 Reconstruction 120 Pipeline 124 Gait Refinement. 126 Trackway Visualization 128 Scaling Model Elements 129 Models 129 Dog 130 Xl Chapter Page Reptile 135 Apatosaurus 140 Triceratops 145 Tyrannosaurus 150 Summary 153 IV. RESULTS AND ANALySIS 156 Genetic Parameters 156 Parent Selection 157 Crossover Coefficient 159 Mutation Coefficient 162 Candidate Population Size 165 Convergence Comparison 167 Sensitivity Analysis 169 Space Exploration 170 Space Organization 175 Space Refinement 178 Fitness Function 181 Qualitative Gait Analysis 190 Dog 190 Reptile 196 Apatosaurus 202 Triceratops 205 Tyrannosaurus 208 Joint Functionality 210 Quantitative Gait Analysis 212 Scapulothorax/Shoulder Contributions 213 Optimal Ankle Height 218 Ipsilateral Phase 227 Summary 235 V. DISCUSSION 238 VI. CONCLUSIONS 245 xu Chapter Page APPENDICES 248 A. DOG MODEL DATA 248 B. REPTILE MODEL DATA 252 C. APATOSAURUS MODEL DATA 257 D. TRICERATOPS MODEL DATA 261 E. TYRANNOSAURUS MODEL DATA 265 F. FIXING ORIENTATION AND POSITION 268 G. GENETIC ALGORITHM STRUCTURE 270 H. EXAMPLE BIPEDAL CANDIDATE 272 1. GLOSSARY 278 BIBLIOGRAPHY 281 X111 LIST OF FIGURES Figure Page 1. The Luxo Jr. lamp jumping 13 2. SR-based walking 16 3. Key mass points 17 4. Walking on uneven terrain 20 5. Gait timeline 22 6. Gait state machine 24 7. Limit Cycle Control. 27 8. Controller graph 30 9. Minimum energy expenditure animation 32 10. PAR template 35 11. Sagittal elevation angles 38 12. Navigating a generated trackway 40 13. A typical neural network 44 14. Example SAN specification 47 15. Shark model using low-level controllers 49 16. The Luxo Jr. lamp limboing 51 17. Running gait evolved using GAs 54 18. Salamander trotting animation 56 19. Effect oflimiting knee extension on cost of travel. 58 20. Creatures evolved for walking 61 21. Virtual competition arena 63 XIV Figure Page 22. Exmnple evolved virtual pet. _ 64 23. L-system generated creatures 66 24. Ten creatures evaluated for locomotory efficiency 67 25. AlBO forelimb 70 26. Hip and pes trajectories during obstacle avoidance 74 27. Key pes locations 75 28. SlMM model ofthe pectoralis major muscle 79 29. Biomechanical model used for the stepup exercise 80 30. Knee represented using a sliding-axis joint. 82 31. Tyrannosaurus rex hindlimb musculoskeletal model. 83 32. Possible mid-stance configurations 86 33. Brachiosaurus trackway, COM, and Stability Triangle 88 34. Evolved gaits of various models 90 35. Flexion/extension movement of an Apatosaurus elbow 97 36. Apatosaurus elbow flexion/extension with fixed manus 99 37. Visualization of the Apatosaurus right forelimb LROM space 100 38. Exmnple bipedal duty vector 102 39. Events related to bipedal walking gaits 104 40. Relationships between discrete key events during forward locomotion 106 41. Pruned Apatosaurus forelimb LROM space 108 42. Apatosaurus forelimb LROM space before and after pruning 109 43. Back data and slice data organization 112 44. Apatosaurus forelimb walking animation 114 xv Figure Page 45. Bipedal gait pipeline 116 46. Quadrupedal Trunk Constraint from dorsal view 118 47. Example quadrupedal duty vector. 119 48. Forelimb RD selection based on a hindlimb RD-RLU pair 122 49. Apatosaurus quadrupedal walking animation 123 50. Quadrupedal gait pipeline 125 51. Dog hindlimb gait animation before and after refining 127 52. Example generated Apatosaurus trackway 128 53. Dog hindlimb joints 130 54. Dog forelimb joints 131 55. Dog hindlimb LROM space 132 56. Constrained dog hindlimb LROM space 132 57. Dog forelimb LROM space 133 58. Constrained dog forelimb LROM space 134 59. Dog trunk ROM space 134 60. Reptile hindlimb joints 135 61. Reptile forelimb joints 136 62. Reptile hindlimb LROM space 137 63. Constrained reptile hindlimb LROM space 137 64. Reptile forelimb LROM space 138 65. Constrained reptile forelimb LROM space 139 66. Reptile trunk ROM space 139 67. Apatosaurus hindlimb joints 140 XVI Figure Page 68. Apatosaurus forelimb joints 141 69. Apatosaurus hindlimb LROM space 142 70. Constrained Apatosaurus hindlimb LROM space 142 71. Apatosaurus forelimb LROM space 143 72. Constrained Apatosaurus forelimb LROM space 144 73. Apatosaurus trunk ROM space 144 74. Triceratops hindlimb joints 145 75. Triceratops forelimb joints 146 76. Triceratops hindlimb LROM space 147 77. Constrained Triceratops hindlimb LROM space 148 78. Triceratops forelimb LROM space 149 79. Constrained Triceratops forelimb LROM space 149 80. Triceratops trunk ROM space 150 81. Tyrannosaurus hindlimb joints 151 82. Tyrannosaurus hindlimb LROM space 152 83. Constrained Tyrannosaurus hindlimb LROM space 153 84. Effect of varying Tournament Selection coefficient.. 159 85. Effect of varying crossover coefficient with no mutation 160 86. Effect of varying crossover coefficient with fixed mutation 162 87. Effect of varying relative mutation coefficient with no crossover. 163 88. Effect of varying relative mutation coefficient with fixed crossover. 165 89. Effect of varying candidate population size 166 90. Comparison of GA/Hill Climbing convergence performance 169 XVll Figure Page 91. Apatosaurus forelimb sample counts 171 92. Effect ofvarying sampling resolution on walk fitness 173 93. Comparison oflow (top) and high (bottom) resolution sampling 174 94. Effect ofvarying box count on walk fitness 176 95. Comparison of low (top) and high (bottom) box counts 177 96. Effect of iterative refinement on candidate fitness 179 97. Walking gait before (top) and after (bottom) refinement. 180 98. Comparison oflow (top) and high (bottom) pitch error coefficient 183 99. Comparison oflow (top) and high (bottom) FDOF error coefficient.. 188 100. Comparison of GAGA (top) and Goslow (bottom) hind dog walk. 191 101. Comparison of GAGA (top) and Goslow (bottom) fore dog walk. 193 102. Comparison of Muybridge (left) and GAGA (right) dog walk. 195 103. Comparison of Komodo dragon (left) and GAGA reptile (right) walk. 197 104. Comparison of GAGA (top) and Reilly (bottom) reptile gait images 199 105. Reptile hindlimb stance phase 200 106. Reptile forelimb stance phase 201 107. Apatosaurus hindlimb stance phase 203 108. Apatosaurus forelimb stance phase 204 109. Triceratops hindlimb stance phase 206 110. Triceratops forelimb stance phase 207 111. Tyrannosaurus hindlimb stance phase 209 112. Comparison ofhigh (top) and low (bottom) Apatosaurus ankle heights 219 113. Comparison of high (top) and low (bottom) Tyrannosaurus ankle heights 224 XV111 Figure Page 114. Effect of varying ipsilateral phase on dog body yawing 229 115. Effect of varying ipsilateral phase on Apatosaurus body yawing 230 116. Effect of varying ipsilateral phase on Triceratops body yawing 232 117. Effect of varying ipsilateral phase on reptile body yawing 233 118. Comparison of 0.5 (top) and 0.0 (bottom) reptile ipsilateral phases 234 119. Planar but non-parasagittal Apatosaurus hindlimb LROM space 240 XIX LIST OF TABLES ~k p~ 1. Effect of varying Tournament Selection coefficient.. 158 2. Effect of varying crossover coefficient with no mutation 160 3. Effect of varying crossover coefficient with fixed mutation 161 4. Effect of varying relative mutation coefficient with no crossover 163 5. Effect ofvarying relative mutation coefficient with fixed crossover 164 6. Effect of varying candidate population size 166 7. Comparison of GAlHill Climbing convergence performance 168 8. Effect of varying sampling resolution on walk fitness 172 9. Effect of varying LROM space box count on walk fitness 175 10. Comparison of original and refined walk fitness 178 11. Effect ofvarying pitch fitness coefficient on fitness error terms 182 12. Effect ofvarying yaw fitness coefficient on fitness error terms 184 13. Effect ofvarying roll fitness coefficient on fitness error terms 185 14. Effect of varying lateral fitness coefficient on fitness error terms 186 15. Effect ofvarying vertical fitness coefficient on fitness error terms 187 16. Effect ofvarying FDOF fitness coefficient on fitness error terms 189 17. Effect ofremoving forelimb FDOFs on dog gait observables 214 18. Effect of removing forelimb FDOFs on Apatosaurus gait observables 215 19. Effect of removing forelimb FDOFs on Triceratops gait observables 216 20. Effect of varying ankle height on Apatosaurus gait observables 220 21. Effect ofvarying ankle height on Triceratops gait observables 221 xx Table Page 22. Effect of varying ankle height on dog gait observables 222 23. Effect of varying ankle height on Tyrannosaurus gait observables 223 24. Effect of removing pes FDOF on dog gait observables 225 25. Effect of removing pes FDOFs on Tyrannosaurus gait observables 226 26. Effect of varying ipsilateral phase on dog gait observables 228 27. Effect of varying ipsilateral phase on Apatosaurus gait observables 230 28. Effect of varying ipsilateral phase on Triceratops gait observables 231 29. Effect of varying ipsilateral phase on reptile gait observables 233 30. Dog FDOFs 248 31. Reptile FDOFs 252 32. Apatosaurus FDOFs 257 33. Triceratops FDOFs 261 34. Tyrannosaurus FDOFs 265 1 CHAPTER I INTRODUCTION Animation is the process of creating an illusion of movement through the presentation of a discrete sequence of images. The perceived movement of an animation is outlined by key images, or frames, that represent important events along the animation time1ine. In creating an animation of a moving animal, events such as feet touching or lifting off the ground are identified as keyframes. From the context of reconstructing locomotion for extinct animals, these hand and foot ground contact events can be correlated with fossilized trackway data to provide a basis for possible walk cycles. Hand/foot ground contact events, however, only constrain the animal's external interactions with the environment; it is the kinematics of the bones and joints that constrain, at least in part, the movements of the animal's body during locomotion. It is the goal of this dissertation to provide new methods for synthesizing and analyzing gait animations by exploring the kinematics of an animal's limbs while they are in contact with the ground. Animations that accurately depict animal locomotion are useful for gait analysis. Such animations provide a description of the movement of an animal's limb, trunk, neck, 2 head, and tail with respect to the gait cycle timeline. Muybridge (1887) was the first to investigate animal locomotion using photographic sequences of animals engaged in various gaits. Image sequences were created using a linear array of cameras to record the movements of a passing animal. These image sequences provide a visual description of limb movements and timings from the fixed viewpoint ofthe cameras. Photographic animations are ultimately limited for locomotion analysis purposes by the inability to directly manipulate the models, except by navigating along the gait cycle timeline. Two-dimensional (2D) animation sequences are further limited by their inherent fixed viewpoint; an investigator cannot view the model from an arbitrary perspective to best observe points of interest. One goal of the research presented in this paper is the exploration ofdinosaur locomotion, for which photographic sequences are of course not available. Digital three-dimensional (3D) skeletal models can be interactively manipulated and visualized, making them useful for locomotion analysis. Such models can be based on fossilized bones, allowing investigations regarding the movements of extinct animals. To provide confidence in the results of simulated movements, the models must be accurate and capture sufficient complexity of the joints and articular surfaces. The necessary complexity of these models dictates an enormous amount ofeffort in building and posing the models. Digital models can be animated by using motion capture data (Delaney, 1998) to pose the skeleton. While this is an important technique for creating animations ofextant animals for research and other purposes, motion capture is not an option for extinct animals. 3 Many joints are capable ofmore than one kind ofmovement. These movements are often given physiological terms such as flexion/extension and adduction/abduction. Each of these physiological movements will be regarded as a degree of freedom (DOF). The shoulder joint, for instance, has three such DOF, namely flexion/extension, adduction/abduction, and internal/external rotation (i.e., rotation about the long axis of the upper arm). An entire limb, therefore, may have ten or more DOFs, so a quadruped model may easily contain 100 or more DOFs distributed throughout the limbs, the girdles that attach the limbs to the trunk, and the trunk. While biological joints are capable ofeffectively continuous movements, it is a practical necessity to discretize the movements ofa digital model for computational analysis (e.g., into 100 steps for each DOF, or some other manageable sampling method). The space of discrete skeletal poses grows exponentially with the number ofDOFs and the number of samples per DOF; the sheer magnitude of these spaces makes posing a challenge and searching these spaces intractable. The space of all kinematic poses for a biologically-accurate skeletal model is very large and may contain poses that are not possible with respect to an animal's myology. For this reason, investigators often build musculoskeletal models that are limited in terms of posing by the muscles, ligaments, and tendons of the model (Hutchinson, Anderson, Blemker, and Delp, 2005; Sellers, Dennis, Wang, and Crompton, 2004; Sellers and Manning, 2007). Such musculoskeletal models are driven by specifying muscle activation values. These activation values are interpreted by physics simulations, in which muscle, gravitational, and contact moments are used to update joint angles. Searching the space of 4 possible muscle activation values is computationally intensive due to the necessary use of physics simulations for each evaluation. Construction of these musculoskeletal models is laborious, even more so than construction of the original model because several muscles, ligaments, and tendons affect each joint. Furthermore, musculoskeletal models are difficult to accurately reconstruct for extinct animals because muscle dimensions and other characteristics are largely unknown and must be based on modem analogues, if available (Hutchinson et al., 2005). Sequences ofposes representing plausible gaits can be presumed to exist somewhere within the posing spaces ofthe 3D skeletal models, assuming that joint Ranges of Motion (ROMs) are accurately represented. In this way, limb and trunk osteologies provide a template for movement upon which the musculature acts. Locomotion can therefore be studied using only the kinematics of the bones andjoints ofa skeleton, but methods are needed for navigating the massive kinematic search spaces. It is the purpose of this thesis to explore this hypothesis by presenting new methods that search kinematic posing spaces for plausible locomotion and presenting the results oflocomotion studies conducted using these methods. New techniques will be presented here that allow automatic gait generation and analysis ofbiomechanically-articulated skeletons using Genetic Algorithm Gait Analysis (GAGA) methods. GAGA methods allow each limb to be exercised to determine its potential contribution to locomotion. There is no theoretical limit to the number ofDOFs allowed per limb, or in the skeleton as a whole (although computer memory and processing power ultimately limit the fidelity of the limb explorations). All DOFs can be modeled to 5 represent any biologically possible movement at each joint (i.e., they are not limited to idealized primitives). In animals, limbs do not act in isolation; they function as part of a whole organism. As such, there are times during locomotion when a limb's pose is constrained by what is happening elsewhere in the body. During walking gaits, there is a time when both limbs of a bipedal system are in contact with the ground. With both limbs planted on the ground, there is a limited number of poses for each limb that do not cause the limbs to separate at their shared root. GAGA methods utilize this constraint, along with a bilateral symmetry constraint, to dramatically prune the size of the limb's posing space, leaving a space relevant to locomotion. Quadrupedal gaits are handled similarly, with an additional trunk constraint that further prunes hindlimb and forelimb spaces so that they are relevant to quadrupedal locomotion. Genetic Algorithms (GAs) are then used to find smooth and therefore plausible gaits through the constrained spaces. The GAs use a higWy-optimized candidate representation and fitness function that guarantees every generated gait will at least move the animal forward by a specified stride length. The GAs then search for gaits that are smooth in terms of body pitching, yawing, rolling, and lateral/vertical displacement. The GA also attempts to minimize unnecessary angular excursions at the joints. These fitness terms allow gaits to be analyzed in terms of the locomotion goals of real animals. Forward walking gaits were generated for two extant models (i.e., a generic dog and reptile) and for models of three dinosaurs (i.e., Apatosaurus, Triceratops, and Tyrannosaurus). The walking gaits generated for the extant models were compared 6 qualitatively with published data and serve as controls for verifYing that the gaits generated using GAGA methods match real-world animal gaits in terms ofjoint and limb functionality. The comparison of gaits generated using GAGA methods to real-world analogues provides confidence in the gaits generated for the extinct dinosaur models and the gait analysis ofthese models. The gait observables used by the fitness function to define an optimal gait can be used to quantitatively analyze gaits. The dog, Apatosaurus, and Triceratops models were analyzed to determine the contributions ofthe scapulothorax and shoulder joints to locomotion. Also, the dog, Apatosaurus, Triceratops, and Tyrannosaurus were analyzed to determine optimal ankle height based on pes flexibility. Finally, the dog, reptile, , Apatosaurus, and Triceratops, were analyzed to determine the effect ofgait phase parameters on quadrupedal locomotion. Due to the use ofkinematics only (i.e., no dynamic simulations are used) and the highly-optimized GAs, GAGA methods are able to automatically generate forward walking gaits for quadrupedal models in under five minutes on a consumer laptop (as of the time of this printing). Comparable methods use musculoskeletal models and dynamics simulation to automatically generate bipedal gaits, but the process can take weeks on supercomputer clusters (Sellers and Manning, 2007). Other methods are able to simulate quadrupedal locomotion, but only on simple spring-based models consisting of a rigid trunk, a hip/shoulder joint per limb, and the remainder of each limb modeled by a spring (Herr, Huang, and McMahon, 2002). In fairness, these methods are able to generate gaits with 7 aerial phases, while the GAGA methods are limited to walking gaits due to the lack of dynamics. The remainder of this dissertation is organized as follows: Chapter II contains a review ofmethods related to the automated generation and analysis oflocomotion. Automatic character animation techniques fIrst provided simple methods to automatically generate animation keyframes. Next, a review ofEvolutionary Algorithms (EAs) will be presented before a review of methods that utilize EAs to automatically generate locomotion. Next, a survey will enumerate current state-of-the-art methods for evaluating gaits, especially with respect to extinct animals. Chapter III will present the GAGA methods and techniques. Methods for defIning joints and DOFs will fIrst be presented. Next, limbs will be exercised to determine confIguration spaces and those spaces will be pruned based on biological and locomotion constraints so that they can be efficiently searched using GAs. Also, trunk-based constraints will be utilized to further prune the spaces for quadrupedal locomotion. The use of pipelines will be demonstrated to maximize the reuse ofdata between discrete operation for both bipedal and quadrupedal gait generation. Finally, specifIc data will be presented on the extant and extinct models used in later studies. Chapter IV will present data from sensitivity analyses and studies conducted using GAGA methods. First, an exploration ofthe GA genetic parameters will demonstrate the process of tuning the GAs and evaluate their performance. Sensitivity analyses will then show the robustness ofthe GAGA methods under changes to the parameters used to build confIguration spaces and generate gaits. Next, qualitative gait analysis will show that the gaits generated for extant animals closely match published gaits. Finally, quantitative gait 8 analysis will demonstrate that GAGA methods can be used for careful gait analysis and present the results ofthree specific case studies. Chapter V contains a discussion ofthe benefits and limitations ofthe GAGA methods. The significance ofthe case study results from Chapter IV will also be discussed. The paper will conclude with an ending summary in Chapter VI. The Appendices contain geometric data for the five models described in this paper, pseudocode for some of the presented algorithms, and a glossary of terms and acronyms used in this paper. Finally, the Bibliography lists all references cited in the body of this paper. 9 CHAPTER II BACKGROUND AND RELATED WORK In this chapter, background and related work will be presented that provide a foundation for the new methods and analysis presented in later chapters. These related works come from a variety of areas, including early methods for automatically generating character animation, the use of computational search techniques to evolve locomotion, and computational methods for analyzing gaits using digital 3D models. Ideas from each of these areas provided insight and inspiration for the new methods presented later in this paper. First, global optimization techniques allow automatic generation ofanimation by specifying high-level goals, but these techniques do not scale well to complex models. Techniques using localized controllers scale well to more complex models, but require a great amount ofmanual effort to coordinate joint activity. Finally, fragment composition techniques allow varied locomotion by blending simple locomotion sequences, but often compromise physical and biomechanical realism. 10 Next, a background of evolutionary search techniques (i.e., EA) and basic applications will be presented. EAs are particularly useful in determining good solutions for complex optimization and synchronization problems. EAs will not always find the optimal solution to a problem, but will almost always find a solution that is nearly optimal, as will be discussed. For locomotion synthesis, quicldy fmding near-optimal solutions allows a character to interactively respond to stimuli while maintaining biomechanical accuracy. Next, evolutionary locomotion synthesis techniques will be presented. These techniques combine automatic character animation and EA methods to produce locomotion. Successful applications from several areas will be presented. Methods for computationally evolving controllers have been used to coordinate joint behavior for locomotion of several human and animal models. Artificial Life (ALife) methods have been used to simultaneously evolve creature minds and bodies, creating strange new creatures capable ofunique methods oflocomotion. Also, robotics techniques have been utilized for robot locomotive learning. Next, modern digital 3D gait analysis methods and tools will be presented. Complex musculoskeletal models allow accurate biomechanical evaluation, but require laborious definition of the model and assumptions when modeling extinct animals. Static and dynamic constraints can be useful in pruning the space of limb configurations for locomotion. Finally, EA techniques can be used to find optimal gaits, providing insight into the limb movements and maximum speeds of extinct animals. 11 Automatic Character Animation Modem locomotion synthesis techniques are based on earlier ideas for automatically generating physically-accurate animation sequences. Early methods relied upon global optimization of an animation sequence to produce physically-accurate animation. These methods were the fIrst used to generate such animations, but did not scale well to complex models. Another approach involved defIning localized physical controllers to enforce the physically-accurate behavior of individual joints. These methods localized the force and torque optimization problems, increasing both scalability and the complexity needed to coordinate controllers. Finally, previously-generated animation sequences were blended and concatenated at animation time. The resulting motion sequences were generated inexpensively with no user interaction, but sometimes at the expense ofphysical and/or biomechanical accuracy. Global Optimization An animation sequence can be specifIed by defIning a set of objects and the forces and torques applied to those objects over time. By applying these forces and torques, a physical simulation can produce an animation sequence. Manually specifYing forces and torques to satisfY an animation goal is intractable for all but the simplest goals. The necessary forces and torques can, however, be automatically generated by optimizing the forces and torques required to satisfY high-level animation goals. As the number of animation nOFs grows, optimization soon becomes computationally prohibitive. 12 Optimization tractability can be maintained for complex models by varying time step resolution or reducing the number of animation DOFs, but physical and biomechanical accuracy may suffer as a result. Witkin and Kass (1988) introduced Spacetime Constraints as a new method for automatically generating high-level animation. Using this method, the animator specified high-level goals for what a character would do and how they would do it. Specifically, the animator would constrain what the character has to do, how the action should be performed, the physical structure of the character, and the resources available to the character. Optimization techniques and physical simulation were used to generate the low­ level animation details. The Spacetime Constraints for each physical object were specified by typing LISP expressions into a Graphical User Interface (GUI) function box. Expressions were required for the mass and inertial parameters, the optimization criteria, and kinetic energy with respect to linear and angular velocity. The kinetic energy expression was used during optimization to evaluate the effect of forces and torques on the object. Lines could be drawn between boxes to indicate hierarchical relationships between objects. The optimization process would then solve for the time-dependent force and torque functions that best satisfied the minimization and maximization criteria for each object. Spacetime Constraints were shown to effectively produce jumping animations for Pixar's Luxo, Jr. lamp. Three 1-DOF joints were used to control the posture and motion of the lamp. The authors were able to produce a variety of animations by adjusting the physical parameters and optimization criteria. For example, increasing the weight of the 13 lamp's base resulted in more vertical squash prior to and following ajump. Figure 1 shows frames of a jumping animation for the lamp, including the realistic squash and stretch that is automatically generated using these methods. Figure 1. The Luxo Jr. lamp jumping. Note. From "Spacetime constraints" by A. Witkin and M. Kass, 1988, Proceedings ofthe 15th annual conference on Computer graphics and interactive techniques, p. 167. Specifying the necessary constraint and kinetic expressions became prohibitively expensive as model complexity grew. The expressions required to describe the lamp's link segments were quite complex even though the lamp utilized only three I-DOF joints. The search space for optimal force and torque functions increases exponentially with the number of interacting objects, so optimization becomes prohibitively expensive as object hierarchies become more complex. 14 Another problem with the Spacetime Constraints method was that the animator had to specify the number of discrete time steps used to represent force and torque functions. This restriction could have led to functions that were undersampled and/or oversampled at places along the animation timeline. Undersampling of the function could have resulted in animations that did not satisfy constraints. Oversampling of the function would unnecessarily increase the complexity of the search space. Liu, Gortler, and Cohen (1994) suggested the use ofvariable-rate sampling for force and torque functions. A hierarchical wavelet was used to represent the torque function for each joint DOF. Hierarchical wavelets are similar to hierarchical B-splines in that segments of the spline can be adaptively refined to add or remove resolution. Hierarchical layers ofB-splines represent more detailed but redundant information. Hierarchical layers ofwavelets represent differences between layers, adding more detail to each layer without reproducing data. By using a wavelet to represent torque functions, few samples were needed during periods ofjoint inactivity. Conversely, more samples were allocated during high activity periods. The use ofwavelets dramatically reduced optimization time when compared to analogue runs using fixed sampling. The speedup suggests that, at least in their animations, there are significant periods of time when joint inactivity can be exploited to reduce the optimization search space. Variable-rate sampling increased the applicability of Spacetime Constraints only slightly; optimization ofmodels with a large number ofjoint DOFs remained intractable. 15 Ngo and Marks (1993) attempted to reduce user interaction with Spacetime Constraints by employing Genetic Programming (GP) to generate animation. GP will be discussed in more detail later in this paper. The primary benefit of the GP approach is that it eliminated the need for the animator to specify complex kinetic expressions for each body. Instead, trajectories were encoded as behaviors that were automatically evolved to satisfy animation constraints. Behaviors were represented as Stimulus Response (SR) pairs. Stimuli were triggered using input from a set of sensors. Four sensor types were utilized: angle sensors, tactile sensors that measured ground contact forces, kinesthetic sensors that measured vertical velocity of the Center ofMass (COM), and position sensors which monitored the vertical position of the COM. Each sensor was defined by its type, a stimulus center, and a stimulus extent. Responses consisted of a set of target joint angles and a duration parameter. A critically damped equation of motion was used to ensure smooth motion during response and when switching between SR pairs. Only one SR pair was active at a time. A new pair was selected during each simulation step. Pair selection was performed by first normalizing each stimulus input to within its stimulus extent range. The pair with the smallest sum difference between normalized sensor inputs and stimulus centers was selected for activation. The pair would remain active until another SR pair was identified with a smaller sum difference between normalized sensor inputs and stimulus centers. Sets of 10 SR pairs were evolved to produce 2D articulated figure motion. Motions were evolved for basic stick figure walking, skipping, shuffling, and jumping. Figure 2 16 shows an evolved walking motion. Criteria such as maximum horizontal distance and maximum vertical height were used to drive the evolution process. The global SR pairs worked well on a low-DOF stick figure, but would not easily scale to more complicated articulated figures. Similar to the Spacetime Constraints method, it would become increasingly difficult for the optimization scheme to satisfy animation goals by globally controlling all animation DOFs. Time J*HtI---------------~230 A B tlKigilt" Figure 2. SR-based walking. Note. From "Spacetime constraints revisited" by J. T. Ngo and J. Marks, 1993, Proceedings ofthe 20th annual conference on Computer graphics and interactive techniques, p. 348. Torkos and van de Panne (1998) used global trajectory optimization and trackway data to synthesize quadruped locomotion. To combat previous optimization complexity 17 problems, trajectory optimization was restricted to just two key mass points, one at the pelvic girdle and one between the shoulder girdles. Figure 3 shows these two key mass points. The trackway print locations and timings, along with a nominal limb length for the fore and hind limbs, provided enough data to optimize the motion of the animal's body. Motion of the cervical, dorsal, caudal, and limb joints were calculated based on the animal's trajectory. spIne virtual hip h2 ~~-----:;;;i" virtual legs Figure 3. Key mass points. Note. From "Footprint--based Quadruped Motion Synthesis" by N. Torkos and M. van de Panne, 1998, Graphics Interface, p. 156. 18 The animal's dorsal vertebral column was treated as a pair of springs, one spring between each key mass point and the animal's COM. The dorsal joints were configured using Inverse Kinematics (IK) such that they satisfied the spring constraints. The support phase of each limb was also configured using IK such that the manus (i.e., hand) and pes (i.e., foot) were located at the manus and pes print locations. For a review ofIK, specifically for anthropomorphic limbs, see Tolani, Goswami, and Badler (2000). The suspended phase of each limb was determined by optimizing the path of the end effecter (i.e., manus or pes) to seek the next print while avoiding collisions with the ground and other limbs. The cervical and caudal joints were handled independently for non­ locomotion purposes. The use of simple IK to determine limb joint configurations requires several assumptions. The primary assumption is that the joints must be simple hinge or ball and socket joints. These simple joints lend themselves well to IK due to their fixed centers of rotation, but are not biologically accurate. IK for biologically-accurate joints is an intractable problem that can only be handled by case-specific approximation. Also, IK is not intrinsically physically accurate, although pinning the end effectors with physically­ accurate constraints typically produces visually-acceptable results. These methods were used to successfully generate quadruped locomotion that followed a trackway. The body trajectories were preplanned and IK was used to keep the manus and pes coincident with trackway prints, so the limbs were not directly used to produce locomotion. This may have resulted in a "marionette" effect, in which the body is moving and the limbs appear to be along for the ride instead. The optimization process 19 may have also caused to body and limbs to enter configurations in which the animal would appear visually uncomfortable. The idea ofpath planning for trackway following is good, but the limbs should be controlled such that they at least appear to drive the animal along the path. Chung and Hahn (1999) used a similar IK approach to simulate human walking. Instead of utilizing trackway data, pes print locations were generated from a general path description. The print-planning algorithm compensated for turning, obstacles, and changes in grade by altering step length. Print locations were always planned two steps ahead so that the character would show anticipation. The print locations, along with a path for the pelvis to follow, pinned the origin and end effecter of the limb, leaving knee and hip configurations to be solved by IK. The path of the pelvis was described using a parametric spline. Two control points were used to describe pelvis motion during each step. The first control point represented the pelvis position when the supporting pes was directly under the pelvis. The height of the . pelvis at the time was determined by the amount of knee flexion in the supporting leg. The second control point represented the pelvis position when both limbs were supporting (called dual support). The pelvis position during dual support was determined by minimizing the angular accelerations caused by IK to achieve dual support. The clearance height of the swinging leg was also governed by a spline. Control points were initially placed at the pes print locations and at a height such that the pes would clear the ground. Additional control points were added so that the pes would clear obstacles or uneven terrain. Figure 4 shows a generated walk on uneven terrain. 20 Figure 4. Walking on uneven terrain. Note. From "Animation ofHuman Walking in Virtual Environments" by S. Chung and 1. K. Hahn, 1999, Proceedings o/Computer Animation, 99, p. 13. These methods produced forward locomotion on uneven terrain, but the limbs may again have had a "marionette" look due to the use ofIK. A hybrid of global and local optimization techniques were used for obstacle avoidance. The trackway print locations were precomputed to compensate for terrain and obstacles. The pelvis and pes optimizations, however, were run at animation time to determine walking behavior for the current step. The animation-time optimization ofthe pelvis location and pes clearance height is important for walking on uneven terrain. Global optimization is effective when planning paths for a small number ofobjects. As the number of objects, physical relationships between objects, and animation time increases, the optimization search space becomes prohibitively large. The size of the 21 search space can be reduced by using IK to remove optimization DOFs, but the animated figure may take on a "marionette" look. The techniques presented in this section did not generate higWy-realistic locomotion, but did provide valuable ideas and motivation for later locomotion systems. Local Controllers An alternative to global optimization involves the use oflocalized controllers to produce physically-accurate animation. These controllers drive joints towards goal configurations by applying forces and torques. The joint motion created by these controllers is not necessarily biomechanically accurate with respect to muscles, tendons, and ligaments, but it is physically accurate. The controllers require only a target configuration, so complex optimization schemes are not necessary to determine forces and torques. Generating locomotion using local controllers is then a problem of specifying target joint angles with respect to limb goals and synchronizing those limb goals. The KLAW (Keyframe-less Animation of Walking) system (Bruderlin and Calvert, 1989) represents one of the first uses oflocal physical controllers for animation. To produce walking animations, local controllers were used to drive limb joints toward key configurations. Joint torques were approximated using a model for the difference between current and target angle and the time remaining to reach the target angle. This type of controller is known as a Proportional Derivative (PD) controller. The key configurations were specified by a finite state machine that coordinated higher-level limb goals. Figure 5 - - - - - - - - - - -- -- - 22 illustrates the relationship between limb goals and the gait timeline. At the top level, a set of walking parameters were used to control the finite state machine. H5l HSR TOl HSl doLb19 single double single support support (Ief') support ,upport (right) ... .... Ish stance left swing -. -..... cooo- ... right swing fight stance ~ 0% 1 IIsp 50% 100% .......----------...... HSL = heel sulke lett HSR = heel slrike rjght ltR. 10e ofl right 1'Ol • toe ofl 1eJ\ Figure 5. Gait timeline. Note. From "Goal-directed, dynamic animation ofhuman walking" by A. Bruderlin and T. W. Calvert, 1989, Proceedings ofthe 16th annual conference on Computer graphics and interactive techniques, p. 235. Three locomotion parameters were used to describe basic walking animations: forward velocity, step length, and step frequency. Forward velocity equals the product of step length and step frequency, so only two of the three parameters needed to be specified. In addition, up to 28 locomotion attributes could be varied to customize the walk. These parameters included: lateral distance between the feet, toe clearance during swing phase, 23 and the maximum rotation and list of the pelvis. These parameters were used to determine key joint configurations during limb stance and swing phases and the timing for transitions between states. KLAW successfully generated lower-body walking animations using a simple (10 DOF) human model. The model could only walk forward, varying speed but not direction. Control of this simple walking scheme was intuitive. The animator could easily adjust walking speed and alter gait appearance by modifying the three primary locomotion parameters. For example, short stride length and high stride frequency resulted in short, quick steps. Long stride length and low stride frequency resulted in long, deliberate (but not leaping) strides. Raibert and Hodgins (1991) presented a more general framework for animating locomotion. Here again, local controllers were used to drive joints and [mite state machines were used to coordinate the controllers. Instead ofdriving joints toward key configurations, controllers acted as actuators to simulate the effect ofmuscles, ligaments, and tendons on joints. The finite state machine realized high-level limb goals by providing actuator subgoals to each joint controller. Limb activity was divided into five states: The thrust and unloading states handled the application of forward and upward forces by the limb, followed by relaxation of the limb after lift off. The flight state was responsible for the mid-air behavior of the limb, preparing it for landing. The loading and compression states dealt with manus or pes contact with the ground and subsequent compression of the limb. Figure 6 illustrates the gait state machine. Limb activities were coordinated to produce specific gaits. For 24 example, quadruped trotting was generated by synchronizing diagonal limbs; quadruped bounding was generated by synchronizing fore and hind limbs. Figure 6. Gait state machine. Note. From "Animation of dynamic legged locomotion" by M. H. Raibert and J. K. Hodgins, 1991, Proceedings ofthe 18th annual conference on Computer graphics and interactive techniques, p. 353. Additional control methods were used to maintain character balance during locomotion. In general, a character is considered to be balanced ifthe character's COM is above the manus or pes ofa supporting limb. Ifmultiple limbs are supporting the character, the character is considered balanced if the COM is over the convex region defined by the manus/pes ofall supporting limbs. This region is known as the support region or support polygon. Balance was maintained by applying forces and torques to the 25 character's COM to ensure the character remained upright and the COM stayed within the support region. This framework was used to successfully generate several forward gaits including: biped running and galloping, quadruped trotting, bounding, and galloping, and kangaroo hopping. The framework extended previous work by actively maintaining character balance and simulating biomechanically-accurate motions. Adding gaits to the framework was particularly difficult because new actuator goals had to be specified along with limb­ synchrony relationships. Hodgins, Wooten, Brogan, and O'Brien (1995) extended the work presented by Raibert and Hodgins (1991) to generate realistic animations of human running, cycling, and vaulting. Like previous work, actuators were used for low-level joint control and finite state machines were used to coordinate actuators. Localized actuator goals were hand tuned, so defining new behaviors was a difficult task. After tuning, behaviors could be easily controlled by modifYing high-level parameters. In addition to forward running, the state-specific control functions also handled arbitrary turning. Previous methods used target velocity and step length parameters to predict the forward position of the next pes print. Turning was achieved by incorporating a facing direction to predict the lateral displacement of the next pes print location (shortening the forward displacement). The lateral displacement of the next pes print location was a function of the facing direction, so this technique could be used to facilitate an arbitrary amount oflateral reaching during turning. Arm animations were coordinated with the leg 26 animations to produce full body animations. Balance was preserved during turning, allowing realistic-looking running animations that followed user-defined paths. Laszlo, van de Panne, and Fiume (1997) proposed a method for controlling human and robot walking by adding closed-loop control to periodic notions. Using a technique called Limit Cycle Control, periodic walking motions were automatically perturbed to maintain balance. Open-loop walking animation was generated using finite state machines and PD controllers. The open-loop walking of an upright character was considered the limit cycle. As a character began to lose balance, control methods would force the character back into the limit cycle. Figure 7 illustrates the Limit Cycle Control technique. 27 end of one cycle. "'\\ begi:ning of the next \ xn+1- g( xn' Uo+ ""un)L ol!l.X 1;:::: x ·1­n+ n+ xn+1 state space x~+1;:::: g{ x ' Uo}n Figure 7. Limit Cycle Control. Note. From "Control ofPhysically-based Simulated Walking" by 1. F. Laszlo, M. van de Panne, and E. Fiume, 1997, Proceedings ofIMAGINA, p. 234. The Limit Cycle Control method allowed an interesting and intuitive control method for simulated humans and robots. The forward speed ofthe character could be controlled by leaning the character forward or backward. As the character leaned forward, walking speed would increase to keep the character from falling over forward. Likewise, turning could be controlled by leaning the character to the side or turning the hips. Unfortunately, only one gait was supported. Ideally, a similar technique could be used to allow backward steps, sideways steps, and gait changes. 28 To increase behavior repertoire ofanimated characters, Badler et al. (1995) used Sense Control Action (SCA) loops to control virtual character animation. During the sense phase of the loop, information was collected from the environment using sensors. The sensors provided information such as the distance and orientation of important objects. The control phase used input from the sensors to determine whether the character should be attracted or repelled from the objects. Finally, the action phase used control methods to accomplish the goals set forth by the control phase. Locomotion was generated using a SCA loop and a Parallel Transition Network (paT-Net). The SCA loop defined the "body" ofthe character: sensing possible locations for the next pes print, determining ifthose locations were safe, and then acting to take the step. The PaT-Net represented the "mind" of the character, determining high-level path planning goals. PaT-Nets consisted ofhierarchical state machines that determined the behavior of the SCA loop. The PaT-Net architecture was designed to facilitate arbitrarily­ complex behaviors. To this end, PaT-Net nodes could spawn new networks, allowing parallel execution and communication between networks. In theory, a complex PaT-Net could produce and transition between many different gaits. The PaT-Net/SCA architecture was used to simulate a game ofhide and seek between virtual characters. The PaT-Nets were used to determine high-level goals such as where to hide and where to look. The SCA loop was used to generate low-level locomotion. In related work, characters could follow a user-defined path. Addition of the PaT-Net allowed automatic path planning at animation time. This decomposition into 29 character minds and bodies is a powerful paradigm, allowing arbitrarily-complex behaviors to be built on existing mind and body functionality. Faloutsos, van de Panne, and Terzopoulos (2001) proposed a standardized framework for physical controllers to drive character animation. By creating a controller module that met the specifications of a standard interface, animators could add their control modules to the behavior repertoire of an animated character. An initial network provided controllers that allowed a character to regain balance, take protective steps, and stand up in multiple ways after falling down. Each controller contained a set of preconditions, a set of postconditions, and an expected performance. The preconditions were ranges of values for each joint DOF. A controller could become active only if all character DOFs were within the ranges specified by the preconditions. The postconditions specified the target values ofeach joint DOF. Due to ground contact and obstacles, a controller may have been unable to reach a postcondition state. The expected performance defined the error tolerance for the controller. The controller would report a failure and become inactive if any of the character DOFs exceeded the ranges specified by the expected performance. Only one controller was active at a time. Active controllers were picked based on which controller's preconditions best matched the current state of the character. Figure 8 shows a sample set of controllers and their relationships. 30 success 1ailure user invoked Figure 8. Controller graph. Note. From "Composable controllers for physics-based character animation" by P. Faloutsos, M. van de Panne, and D. Terzopoulos, 2001, New York: ACM Press, p. 27. The standardized framework allowed behaviors to be specified without the necessary creation of complex state machines and/or control functions. However, determining appropriate preconditions for each behavior would be difficult, especially as the behaviors count grew. A character may begin to fall backward, only to match the preconditions of an undesired behavior. Perhaps a distinction between standard and recovery behaviors would alleviate this problem. A recovery behavior could be activated upon failure of a standard or recovery behavior. Using local controllers, the animation system can specify the target configuration for ajoint and rely on a controller to produce physically-accurate motion. Controllers can be tailored for a specific joint to produce biomechanically-accurate motion. To produce locomotion, proper joint configurations must be determined based on limb goals and limb 31 goals must be coordinated. These goals and relationships are typically specified using a large number of parameters. Later, work will be presented that utilized EAs to evolve such parameter sets. For more information on physical controllers, see van de Panne's (2000) review of control methods for animating articulated characters. Fragment Composition Global optimization and Local Controller techniques can produce physically­ accurate motion sequences but require a great amount of effort to specify complex character behavior. An alternative is to create complex animations by compositing existing simple motion sequences. For the purpose of generating locomotion, interactive acceleration and deceleration could be achieved by blending between a fast walking animation and a slow walking animation. The downside to this approach lies in the difficulty of creating motion transitions that are both physically and biomechanically accurate. Rose, Guenter, Bodenheimer, and Cohen (1996) used Spacetime Constraints and IK to generate smooth motion transitions. Spacetime Constraints techniques were used to minimize the metabolic energy used by the character during the transition. In general, natural movements conserve energy as much as possible, so animations that conserve energy tend to look natural. Minimal metabolic expenditure was achieved by minimizing the joint torques necessary to transition between motion sequences. Figure 9 shows an example of simple linear interpolation versus animation using minimal metabolic expenditure. 32 Figure 9. Minimum energy expenditure animation. Note. From "Efficient generation ofmotion transitions using spacetime constraints" by C. Rose, B. Guenter, B. Bodenheime, and M. F. Cohen, 1996, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p. 152. IK was used to keep supporting manus/pes stationary on the ground during transition. IK was propagated upward from the end effecters as necessary while forces and torques transformed joint configurations between motion sequences. Enforcing stationary end effecter constraints could have led to loss of character balance, which was not explicitly preserved. Natural-looking transition required the appropriate selection of motion sequences so that the transitions were short and did not require high-magnitude changes to joint configurations. The Spacetime Constraints and IK techniques were used to generate motion transitions for a 44 DOF human model. Transitions were generated using a basis library of soccer motions. Physical and biomechanical accuracy of the transition motions was not explicitly enforced, yet the motions appeared plausible due to relatively-short transition 33 times and the minimization ofmetabolic energy during transition. The visual plausibility oftransitions would likely falter in an interactive environment that required many unpredictable transitions. Improv (Perlin and Goldberg, 1996) was designed to be a flexible animation system capable ofautomatic transitions. The animation system consisted of two subsystems: an animation engine and a behavioral engine. The animation engine allowed basic motions to be stored as actions. Actions could be layered and transitioned between. Noise functions were applied to actions to ensure that actions looked slightly different each time they were run. The noise functions provided visual nondeterminism in the produced animations. The behavioral engine allowed linking of actions to greetings, responses, and gestures. Actions defined their constituent joint DOF values at the beginning and end of the action. Mutually-exclusive actions could be clustered into groups. If several such groups were defined, an action from each group could be performed simultaneously without oscillating a joint DOF. Two or more actions from a group could be animated simultaneously by applying a weighted average of the actions to the joint DOFs. Transitioning between mutually-exclusive actions was performed by varying the weighting values used in calculating the weighted sum of actions. Improv has been used to create virtual actors that respond to spoken commands by performing actions. The use ofa noise function during interpolation ofDOF allowed natural-looking motions similar those created by physical controllers. The interpolated motions were not physically correct, so care was needed to ensure that the motions looked physically correct. Intermediate joint configurations would likely be necessary to specify 34 actions that look physically correct. Locomotion would be difficult to generate with such a system because gaits would have to be manually specified. Badler et al. (1998) presented a Parameterized Action Representation (PAR) designed to link natural language with high-level animation goals. All actions available to a character were represented as PARs and stored in an Actionary. Agents were given natural language instructions, which were executed by initializing the appropriate PAR with context-specific information. For example, the command "Walk to your bicycle" might have initialized a walking PAR with information about the agent, the agent's current location, and the location of the bicycle. Low-level animation was driven by Motion Capture data or by SCA loops and PaT-Nets (Badler et aI., 1995). Figure 10 shows the PAR template. 35 PAR applicabiIi1)" conditions: CONDITION boolean-expression start: TIME/STATE result: TIME/STATE ~gent: AGENT I participanh: ~bject1i: OBJECT liS..:J reCOndi~i?U!i: CONDITION boOlean_expreSSiOiI1 core semautws: POlileODdltJonS: CONDITION boolean-expression motion: MOTION force: FORCEU J irection: DIRECTIOJ start: WCATIONpath: end: WCATION distance: LENGTH ~ Chieve: CONDITION boOlean-expreSSioJn pUJ'Pose: generate: PAR enable: PARG termination: CONDITION boolean -expression duration: LENGTH manner: MANNER subllctions: PAR conotraint-graph puent action: PAR previous aetion: PAR concurrent action: PAR next action: PAR Figure 10. PAR template. Note. From "A Parameterized Action Representation for Virtual Human Agents" by N. Badler, R. Bindiganavale, J.Bourne, M. Palmer,J. Shi, and W. Schuler, 1998, Workshop on Embodied Conversational Characters, p. 3. 36 Each active agent maintained a queue of initialized PARs. When no PAR was currently active, the applicability conditions of the PAR at the front ofthe queue were checked. The first applicable PAR then ran its preparatory actions. The preparatory actions transitioned the agent into a starting configuration for the execution steps. The execution steps were then run. Upon termination, the PAR ran its post actions, which depended on the success or failure ofthe execution steps. PARs could be nested in the preparatory, execution, and post action phases to specify complex actions. The PAR representation was used to control five agents in a simulated lodge. Four of the agents could be controlled from different geographical locations using natural language commands. Possible actions included: walking, sitting in a chair or on a bed, talking to others, climbing a ladder, opening doors, shaking hands, bowing, and drinking. The fifth agent was an autonomous waiter that would fill empty glasses with water from a pitcher. When the pitcher became empty, the waiter would return to the kitchen to fill the pitcher. The PAR representation was similar to the standardized controller framework presented by Faloutsos et al. (2001). Both methodologies utilized pre and post conditions and failure handling. The PAR framework was less reactive and more goal oriented, using existing motion sequences to accomplish high-level goals. Motion transitions were specified by the PARs, so physical accuracy was not guaranteed. PARs are well suited for controlling interactive characters in an environment where interaction has greater importance than the physical accuracy ofmotion. 37 Allbeck and Badler (2002) extended the PAR representation to incorporate personality and emotion into motions. Effort and shape parameters were used to automatically adjust motion captured or procedurally generated animation sequences. Effort parameters adjusted agent velocity, acceleration, and inertial parameters. Shape parameters changed the physical form of the agent's body as it moved through space. Using these methods, animation sequences were successfully modified to convey character personality and emotional traits. Sun and Metaxas (2001) introduced a method for blending motion-captured locomotion sequences. Motion sequences were generated and stored using sagittal elevation angles. The sagittal plane is defined as the plane that bisects the left and right side ofa character's body. To determine a sagittal elevation angle, a body segment was first projected onto the sagittal plane. The elevation angle for a segment was defined as the angle between the projected segment and the gravity vector. Figure 11 demonstrates the acquisition of sagittal elevation angles. A limb was represented using the elevation angles of four limb segments: the pes, the lower limb, the upper limb, and the pelvis. Sets oflimb elevation angles were stored as 4-Dimensional points. 38 Pelvis segment and y-axis Pelvis elevation angle Figure 11. Sagittal elevation angles. Note. From "Automating gait generation" by H. C. Sun and D. N. Metaxas, 2001, Proceedings ofthe 28th annual conference on Computer graphics and interactive techniques, p. 263. Locomotion datasets were lists of 4-Dimensionallimb configurations. For each dataset, a step length and height was computed and stored. While walking on even or uneven terrain, a pes print planner determined the reasonable pes print locations. For each step, the location of the next pes print determined an optimal step length and height for the current step. A new motion sequence was then selected such that the desired step length and height could be achieved by blending the current and next motion sequences. A user could also manually adjust the optimal step length and height. Additional parameters such as stance width and toe out angle were used to fine-tune gait appearance. Using these methods, characters successfully walked up and down hills and followed curved paths. Curved paths were followed by simply changing the orientation of the character's sagittal plane, so balance was not preserved during turning. Nor was balance preserved during acceleration and deceleration. The selection and interpolation 39 algorithms were computationally efficient enough to be run at animation time. Similar techniques are common in more recent video games, in which characters can tum, walk on uneven terrain, and change gaits using only a few motion sequences. Choi, Lee, and Shin (2003) introduced a method for automatically navigating a character through a virtual environment by blending motion captured sequences. Given a starting and ending location, a virtual trackway was generated and used to guide the character through the environment. Motion sequences were blended and concatenated to create an animation sequence that followed the trackway. A set ofpossible pes prints was created by randomly sampling pes location and orientations in the environment. Each possible pes print was tested to ensure the location was safe (i.e., not water, fIre), and that the orientation was reasonable considering to the local terrain. Safe pes prints were added to a directed graph, connected by edges that represented possible motion transitions. Edge weights were proportional to the step length between pes prints with a penalty based on the amount of motion clip degradation necessary to achieve the step. Path planning then consisted of fInding the lowest-cost path from starting node to ending node. The resulting sequence of motion clips was concatenated and smoothed to produce the fInal animation. Figure 12 shows a character navigating a generated trackway. 40 Figure 12. Navigating a generated trackway. Note. From "Planning biped locomotion using motion capture data and probabilistic roadmaps" by M. G. Choi, J. Lee, and S. Y. Shin, 2003, ACM Transactions on Graphics (TOG), 22(2), p. 196. Trackways were successfully created to guide characters through an uneven environment with obstacles. Input motion sequences included: starting walk, stopping walk, walking straight, turning left, turning right, running, and broad jumping. Even in a small environment, several thousand pes print nodes and tens of thousands of transition edges were required to generate natural-looking animation. Not surprisingly, construction of the trackway was computationally intensive and had to be performed offline. Breaking the planning task into smaller subgoals might allow this technique to be used interactively. Physically-accurate motion sequences are difficult to specify and generate. The flexibility and utility ofthese sequences can be increased by combining them with other physically-accurate sequences. It is difficult, however, to determine the appropriate 41 sequences to blend and the order in which to blend them. Fragment composition techniques are appropriate for applications that require blending between only a few motion sequences at the cost ofphysical and biomechanical accuracy, such as video games. Some of the ideas presented in the section, however, may be useful for generating locomotion, specifically in transitioning between gaits. Automatic character animation techniques have been presented that successfully produced character animation with varying degrees ofphysical and biological realism. Many of these techniques were used directly to generate locomotion. Ofthe presented techniques, the methods involving local controllers produced the best locomotion results. The architectures based on local controllers were highly extensible, but required the manual tuning oflarge parameter sets. In the next section, EAs will be presented that can be used to automatically tune large parameter sets. For a general review ofhigh-level animation methods, see the review presented by Giang, Mooney, Peters, and O'Sullivan (2000). Evolutionary Algorithms EAs encompass a class of search algorithms. These algorithms are typically used to find good solutions to problems that have large solution spaces (called fitness landscapes). An initial population of candidate solutions is created randomly or seeded using some heuristic. A fitness function is used to score the candidates based on how well they satisfy the optimization criteria. Each algorithm iteration involves mating and mutating the population, scoring the population using the fitness function, and selecting fit 42 candidates for the next generation. The highest-fitness candidate is returned after a set number of generations. GAs were introduced by Holland (1992). GAs provide a simple mechanism for searching large fitness landscapes. Candidates, called genotypes, are usually stored as fixed-length binary strings. Candidates typically specify boolean or integer values. Wright (1991) discussed the encoding of real value parameters as binary strings. Mating can be achieved by swapping data between two candidate strings. One or more crossover points determine where data swapping starts or stops. Mutation can be performed by flipping random bits. The evaluated genotypes represent possible problem solution and are called phenotypes. GP (Koza, 1990) allows the evolution of instruction sets to satisfy criteria. Programs can be evolved to efficiently solve problems, or to accomplish a task using sense/response pairs as demonstrated by Ngo and Marks (1993). Programs can be represented as fixed-length strings of operations or as variable-length parse trees. The mating of trees can be accomplished by swapping subtrees between two candidates. Mutation within a tree can be performed by randomly changing a node type or value to another valid type or value. Sims (1991) described how GP can be used to evolve images and textures. Images were evolved from scratch to meet aesthetic criteria or modified to add a stochastic element to textures. Both fixed-length strings and variable-length trees were used to specify image operators. Fixed-length strings were used to represent pairs consisting of an image parameter and a modification to that parameter. Variable-length trees were used to specify 43 image operations and parameters. Tree nodes consisted of functions such as vector transformations, procedural noise generators, and image processing functions. Tree leaves were used to specifY parameters for the operators. Similar techniques can be used to evolve 3D character morphologies. Artificial Neural Networks (ANNs) were introduced by Rosenblatt (1958). ANNs provide a mechanism for simulating a learning mind. Neural networks are typically directed graphs consisting of activation nodes and weighted links. Node activation is based on an activation function which uses the weights and activation status of incoming links as input. A simple activation function uses the sum of the activated link weights to determine activation; the node is activated if the sum exceeds a threshold. Animated characters can utilize ANNs as virtual brains to establish links between stimuli to responses. Figure 13 illustrates a typical neural network. 44 input layer 1 hidden layer output layer x =1 o .. Yr .. x p Figure 13. A typical neural network. Note. From "Neuroanimator: Fast neural network emulation and control of physics-based models" by R. Grzeszczuk, D. Terzopoulos, and G. Hinton, 1998, SIGGRAPH 98 Conference Proceedings. Annual Conference Series, p. 10. Neural networks are usually organized into three layers: an input layer, a hidden layer, and an output later. The input layer consists of nodes that are activated based on some stimulus. Upon activation of a node, all links outgoing from the node are activated. The hidden layer consists of a number of interconnected nodes. Inputs to hidden layer nodes are links from the input layer or other hidden nodes. Output links from hidden layer nodes lead to output nodes or other hidden layer nodes. The output layer contains nodes 45 that contribute to a decision made by the network. The number of input and output nodes depends on the desired network stimuli and responses. The hidden node count is often increased until satisfactory results are reached. ANNs are trained by adjusting link weights. Networks are typically trained by propagating changes throughout the system. For example, if the network responds correctly, activated link weights are increased. Conversely, activated links weights are reduced when the network responds incorrectly. Alternatively, EAs can be used to train networks by evolving a set of link weights. The fitness of a set of links weights is determined by network performance when using those weights. EAs provide an effective way to search large problem spaces. The primary difficulties in using these algorithms lie in determining the candidate representation and the definition of an appropriate fitness function. In the next section, techniques will be presented that evolve the minds and/or bodies of animated characters for locomotion. Evolutionary Locomotion Automatically generating locomotory ability is difficult due to the size and interconnectedness of gait parameter sets. EAs have been employed to evolve the parameter sets that govern Local Controller architectures. The parameter sets were typically evaluated based on their ability to generate forward locomotion. ALife methods have been used to create interesting new creatures capable of locomotion. ALife methods typically use EAs to evolve both creature morphologies and control architectures. Finally, EA and robotics techniques have been used to train and improve robot locomotion. The 46 robots typically used simple yet effective evolution methods that could be useful for simplifying animation architectures. Controller Evolution Physical controllers can be optimized for locomotion by evolving gait parameters sets or by evolving ANN weights. Controllers were evolved for creatures with fixed biological structures. Modifying the morphology of a creature would necessitate re­ evolution of the gait parameters or network weights. Controller fitness was typically determined by the creature's ability to achieve the desired gait. Such evolution schemes promoted the emergence of a single gait. van de Panne (1993) introduced Sensor Actuator Networks (SANs). SANs provide a framework for correlating sensors with character behaviors, similar to the SR pairs presented by Ngo and Marks (1993). Characters were defined by connecting rigid links and 1-DOF joints. Sensors and PD actuators were utilized to control joint motion. Sensor types included: angle sensors, touch sensors for determining ground contact, eye sensors for visual tracking, and length sensors to monitor the linear distance between points of interest. Angular actuators were used to drive joints and linear actuators were used to exert forces between body links. Figure 14 shows an example SAN specification. 47 sensor type link min max 51 touch L1 52 touch 53 angle 2 -180 -10A3,S6,S7 S4 angle 2 25 180L4L2 S5 angle 3 -180 -80 ,A4,S8 S6 angle 4 -180 42 ~, 87 angle 4 55 180L5 " S8 angle 5 -180 -105S2 L..--...J actuators:81 link mass (kg) 10cm act. min max ks kd Ai -20 30 0.4 0.01L1 1.0 A2 -85 -55 0.4 0.01L2 0.15 A3 40 55 0.4 0.01L3 0.10 A4 -110 -105 0.4 0.01L4 0.15 L5 0.10 Figure 14. Example SAN specification. Note. From "Sensor-actuator networks" by M. van de Panne and E. Fiume, 1993, Proceedings of SIGGRAPH, 93, p. 336. Relationships between sensors and actuators were defined using an ANN. The input layer of the network consisted of one node per sensor, the hidden layer contained one hidden node per sensor node, and the output layer contained one node per actuator. The input layer nodes were fully connected to the hidden and output layers. The hidden layer nodes were fully connected to the output layer. Incoming weight values were summed by the actuator nodes to determine both whether the actuator would activate/deactivate and the amount of force or torque to be applied by the actuator. A hysteresis function was used to avoid chattering effects that can be caused by rapidly switching an actuator on and off. 48 The neural networks weights were evolved to optimize the forward locomotion speed ofanimated characters. Optimization was performed without the use ofEA. Sets of neural network weights were fIrst randomly generated until a confIguration was found with satisfactory locomotion results. Stochastic Gradient Ascent and Simulated Annealing (two extensions of the Hill Climbing search technique) were then used to fIne tune the network weights. Both of these Hill Climbing techniques performed roughly equally well, one sometimes outperforming the other and vice versa. A single GA could have been used to accomplish the goals ofboth optimization phases. SANs were used to generate locomotion in 10 distinct creatures, including the Luxo, Jr. lamp. Each creature used only a few I-DOF joints. Creature simplicity allowed the optimization algorithms to quickly converge on effIcient gaits. The ANl'J paradigm allowed deterministic relationships to be established between sensors and actuators. Each evolved network was only capable ofone type of locomotion, so other techniques are needed to be incorporated to allow multiple gaits and gait transitions. Grzeszczuk and Terzopoulos (1995) presented a two-pass algorithm for evolving locomotion. Low-level controllers were fIrst evolved to maximize objective functions. Each low-level controller consisted of a set of time-dependent control functions, one per actuator. The control functions were represented in a discrete form using B-splines. Objective functions were based on locomotive goals, such as moving forward at a desired speed or turning towards a specifIc direction. Simulated Annealing was used to maximize the objective functions by varying spline parameters. 49 Controllers were optimized to perform basic low-level action such as walking forward, walking backward, and turning with different radii. The low-level controllers were then combined to create high-level controllers capable ofperforming more complex tasks. A greedy algorithm was shown to quickly select an appropriate sequence of low- level controllers to accomplish an animation goal. Low-level controllers were also sequenced using Simulated Annealing, which better achieved animation goals at the cost of animation-time performance. Figure 15 shows a shark model comprised oflow-Ievel controllers. lett back left center left front IIIL1scle pair muscle pair nmscle pair point masses 21 OOFs : 69 size of the state space: 138 actuators : 6 springs' stiffhess : 35.0 right back right center right front 1111L..<;c1e pair muscle pair 111 uscl e pair Figure 15. Shark model using low-level controllers. Note. From "Automated learning ofmuscle-actuated locomotion through control abstraction" by R. Grzeszczuk and D. Terzopoulos, 1995, Proceedings ofthe 22nd annual conference on Computer graphics and interactive techniques, p. 70. 50 The benefits and drawbacks of this method are similar to those related to the fragment composition techniques presented earlier. The sequencing of low-level controllers is particularly attractive because simple controllers can be easily evolved to meet animation criteria. Controller sequences must be generated at animation time for the creatures to behave in an interactive environment. Greedy algorithms present an interesting method to quickly sequence controllers. After sequence selection, motions must be carefully blended to prevent discontinuities. An approach to evolving controllers using GP was presented by Gritz and Hahn (1997). As input, the user specified a detailed character model and a fitness metric. Character details included bone dimensions, masses, moments of inertia, and joint limits. The fitness metric incorporated animation goals for the character. Using the fitness metric, a controller program was evolved that specified target joint angles as a function of animation time. PD methods were used to drive joints toward target angles. Controller programs were represented as LISP S-expressions. Candidate programs consisted of one expression per joint DOF. The expressions defined target joint angles as time-dependent functions. Programs were scored by the fitness metric based on how well a character completed the animation goals. Fitness metrics were usually in the form of a primary goal (e.g., "Move to location X.") and secondary goals (e.g., "Don't fall down."). Goal importance could be weighted to encourage the optimization ofprimary goals over others. Goals could also be phased in later during the evolution process to ensure that primary goals were satisfied first. 51 Evolved S-expression controllers were used to generate physically-accurate animations of the Lu:xo Jr. lamp. The lamp was "taught" to hop forward to a goal location and to limbo under a pole. To limbo, the lamp was given the primary goal of forward locomotion with a secondary goal of not hitting the pole. The use ofmultiple evolution objectives allows more complex animation goals. Complex goals would likely require more evolutionary iterations and/or a larger genetic population to satisfactorily evolve. Goals such as the limbo, however, would be difficult to achieve by blending and concatenating existing motion sequences. Figure 16 shows the Lu:xo Jr. lamp's limbo animation. Figure 16. The Luxo Jr. lamp limboing. Note. From "Genetic programming evolution of controllers for 3-D character animation" by L. Gritz and J. K. Hahn, 1997, Genetic Programming, 97, p. 143. 52 Grzeszczuk et al. (1998) introduced the NeuroAnimator framework. NeuroAnimators used ANNs to produce physically-accurate behavior instead ofthe standard numerical integration techniques. The neural networks were trained prior to animation using physical simulation time steps as inputs and outputs. The neural networks predicted the next state ofa physical system given the current state and a time step, so real­ time dynamics simulation could be performed with arbitrary time steps. Use of the neural networks greatly increased runtime efficiency because prediction was computationally inexpensive and there is no need for multiple integration steps between frame renderings. NeuroAnimators could be used to train physical controllers for optimized behavior. Neural network weights were not evolved because modifying the weights could invalidate their physically-accurate predictions. Instead, a controller was evolved for each animated DOF. Controllers were represented by time-dependent functions that modified the neural network inputs. Partial derivatives ofthe NeuroAnimator output states could be computed with respect to control inputs, so a gradient-based optimization was used to efficiently evolve the controllers. NeuroAnimators were used to evolve controllers for animation sequences such as: a pendulum trying to reach a goal state, a truck attempting to park at a specified location and orientation, a lunar lander attempting to land with a low descent velocity at a specified location and orientation, and a dolphin swimming with an optimized forward velocity. Using a neural network to replace numerical integration reduced the computational complexity ofdynamic simulation but required network training. Current computer hardware and numerical integration techniques are fast enough that training drawbacks 53 probably outweigh performance gains. However, the NeuroAnimator approach does provides an efficient means for optimizing controllers. Kang, Cho, and Lee (1999) extended the legged hopping model presented by Raibert and Hogins (1991) to evolve human running models. Two distinct hopping legs were effectively coordinated to produce running motions. A standing phase and a jumping phase were used to control the legs. During the standing phase, the leg first acted as a spring absorbing downward velocity. The leg then propelled the character forward and up. During the jumping phase, the limb was driven towards its landing configuration. The jumping phase was activated when the limb length exceeded a threshold. Upon activation of the jumping phase, a landing time was computed and used to activate the standing phase. To maintain character balance, the COM was driven towards a point over the character's stance-leg pes, similar to the balancing technique used by Raibert and Hogins (1991) .When no feet were in contact with the ground, the COM was driven towards a point over the mean location of the feet. Unlike previous work, the upper body was actively controlled to change the character's COM. A combination of arm and lower back movements were used to displace the character's COM towards its target location. The angular accelerations, maximum angles, spring constants, and nominal leg length were all editable parameters. GAs were used to evolve parameter sets. Running models were scored based on animation smoothness and energy consumption. Smoothness was evaluated by minimizing the difference in angular velocities between jumping and standing phases. This criterion promotes soft footfalls during running. Energy consumption was minimized by reducing the angular accelerations necessary to produce 54 the animation. By adjusting the target energy consumption, the run could be made to appear brisk or tired. In general, varying the amount ofenergy consumed by a character could result in animation that is not biologically accurate, especially ifjoint limits are not enforced. These methods were used to successfully generate human running animations at various speeds. Figure 17 shows a running gait evolved using the GA. The evolved parameter sets generated only forward locomotion. GA techniques alone are likely insufficient to prodllce locomotion along an arbitrary path. To follow an arbitrary path, the character must be able to modify their gait for turning, which requires a mapping between path stimulus and gait response. A method for varying gait parameters based on environmental and user stimulus is necessary for interactive characters. Figure 17. Running gait evolved using GAs. Note. From "An efficient control over human running animation with extension of planar hopper model" by Y. M. Kang, H. G. Cho, and E. T. Lee, 1999, Journal a/Visualization and Computer Animation, 10(4), p. 224. 55 Ijspeert and Arbib (2000) introduced a model to generate locomotion for simulated 3D salamanders. The model consisted of three control abstractions: a vision-based control circuit, an ANN, and a set ofmuscle actuators. The vision-based control circuit provided inputs to drive the speed and direction of the reptile. The vision circuit provided non­ oscillating input to each side of the body, alternating and symmetrical for forward locomotion or asymmetrical for turning. The vision circuit provided input for the ANN which generated motoneural outputs to drive simulated muscles. The body trunk and limbs were actuated using spring-based muscles. A leaky integrator neural network was used to simulate the salamander's central pattern generators. Leaky integrator neurons differed from traditional artificial neurons in that they used additional timing and bias parameters to determine activation. The timing and bias parameters helped reduced actuator oscillations by adding complexity to the activation model. A GA was used to train the neural network for optimal locomotive efficiency in three stages. First, the limb central pattern generator was trained to generate reaching and supporting movements which were shared by the limbs. The body central pattern generator was next trained to produce coupled contractions for body bending. Finally, the neural network was trained to coordinate limb and body movements. These methods were used to generate both swimming and trotting gaits. Figure 18 shows the generated salamander trotting animation. The ANN allowed brainstem-like control over locomotion, taking non-oscillating input from only four input nodes. The virtual salamanders could tum by bending their bodies and using asymmetric step lengths. The three-step evolution process provided a mechanism for training subnetworks of the 56 neural network with different goals. Subdivision of the evolutionary process affords quicker and more reliable convergence by the GA. Figure 18. Salamander trotting animation. Note. From "Visual tracking in simulated salamander locomotion" by A. J. Ijspeert, and M. Arbib, 2000, in J. A. Meyer and A. Berthoz (Eds.), Proceedings ofSAB'OO, From Animals to Animats 6, Paris, France, p.92. 57 Sellers et al. (2004) used GAs to explore possible gait strategies for Australopithecus afarensis. A 2D model consisting of only the hind limbs and pelvic girdle was used to evaluate the metabolic costs incurred by different gaits. By varying the maximum knee extension angle, the simulated hominid could be made to adopt a human­ like or chimpanzee-like walking gait. Considering the metabolic costs of these gait variations, inferences were made about the walking behavior ofAustralopithecus afarensis. A finite state machine was used to produce locomotion. The state machine utilized three states, each representing a key pose for a leg. Each state was mirrored across the sagittal plane to animate the contralateral limb. Muscle activation levels were used to simulate a muscle pair for each joint by applying torques about the joint. Each state contained seven parameters: duration, right hip activation level, right knee activation level, right ankle activation level, left hip activation level, left knee activation level, and left ankle activation level. The set of21 parameters was used as a linear genome for the GA. The GA optimized the parameters such that maximal forward distance was covered for a fixed metabolic cost. Simulation results showed that bent-knee gaits consumed significantly more metabolic energy than a human-like gait. Figure 19 shows the effect of limiting knee extension on the cost of travel between the two models. A Basic Metabolic Rate (BlIIR) was used to estimate metabolic costs not related to locomotion. The metabolic costs could have been overestimated due to the lack ofnatural energy-saving mechanisms such as spring elements and complex joint morphologies. 58 8-,r--------,-----------r ~ OQ 7+------r::;:;:::::l-+-------f1; ~ Oo;ncBMA .Y. 6 +-------1: T E 5 +----I%lj',tjl---::==:::J III 40Q l ~ [ill 40· iflcBMA 4 t- 3 +-----1"/,,,/ ~ 215 ii~~Q 1 O+--""""'''''''''''~ Lucy (human) Lucy (chimp) Figure 19. Effect oflimiting knee extension on cost of travel. Note. From "Evaluating alternative gait strategies using evolutionary robotics" by W. 1. Sellers, L. A. Dennis, W.-J. Wang, and R. H. Crompton, 2004, Journal ofAnatomy, 204(5), p. 349. Controllers have been devised to produce efficient locomotion in humans, fish, snakes, salamanders, and extinct hominids. Locomotion was generated by evolving controller parameters sets or by evolving neural weights for ANl\J"s. Parameter-based controllers are well suited for generating and studying a given type of gait, although parameter values could be varied to produce different gaits and gait transitions. Neural network controllers show promise in supporting gait variations by varying network inputs, but network training can be difficult and computationally expensive. 59 Artificial Life ALife techniques have been used to simultaneously evolve the bodies and control architectures of virtual creatures. Unlike other work that has attempted to recreate realistic locomotion for known creatures, work based in ALife has attempted to create interesting new creatures and new forms of locomotion. ALife provides an application for locomotion synthesis, but also introduces fresh perspectives on the evolution oflocomotion. Strange yet efficient gaits can be embraced when there are few preconceived notions about how a creature should move about. Sims (1994a) introduced a method for simultaneously evolving the bodies and control architectures of virtual creatures. Creature morphology was determined by a directed graph in which nodes represented bones and links represented joints. Each node contained bone dimension data and its parent link specified a joint type. Joint types included: rigid, revolute, twist, universal, bend-twist, twist-bend, and spherical. Substructures could be linked recursively to reproduce limb-like structures. A recursive limit prevented infinite recursion. Each joint owned an ANN which utilized sensors and effectors to determine the behavior of the joint. Sensors types included: joint angle, ground contact, and photosensors. Effectors operated as angular actuators to produce joint torques. Joint torque magnitude was based on neural input and a maximum strength value proportional to the cross-sectional areas of the adjacent bones. Neuron activation was based on evolvable expressions that derived output from input signals. Neural networks could be linked to adjacent joints (separated by one bone) to allow synchronization between joints. 60 GP was used to simultaneously evolve creature minds and bodies. An initial population of creatures was randomly generated. Each creature was then evaluated based on forward distance traveled in a set amount of time. Highly fit creatures were mated and mutated for the next generation. Mating and mutating modified both the morphologies of the creatures and their neural network structures and weights. Creatures were successfully evolved to walk, swim, jump, or follow a light source. For these experiments, energy consumption did not factor into creature fitness. Interesting forms of locomotion emerged during the later stages of evolution. Swimming creatures used many synchronized paddles or winding snake-like motions to propel themselves. Swimming creatures that followed a light source developed fins for steering. Walking creatures used lizard-like walks, rocking motions, and inchworm-like pushing and pulling motions for forward locomotion. The jumping creatures all used similar strategies involving the compression and expansion oflimb-like structures. Gait possibilities are interesting to explore, and perhaps give some insight into the origin of locomotion for certain animals. Figure 20 shows examples ofcreatures evolved for walking. 61 Figure 20. Creatures evolved for walking. Note. From "Evolving virtual creatures" by K. Sims, 1994, Proceedings ofthe 21st annual conference on Computer graphics and interactive techniques, p. 21. Sims (l994b) extended his earlier work by using competition to co-evolve populations of virtual creatures. Instead ofdetermining the fitness of a creature by its ability to achieve forward locomotion, fitness was based on a creature's ability to outperform its competitors. The co-evolution techniques closely resembled natural selection, in which there is no specific optimization criterion. Using a survival of the fittest 62 mentality, competition losers had a chance of being eliminated from the population. Co­ evolution produced competitive behaviors that would likely not have emerged using standard EA techniques. A competition was devised to encourage protective behaviors for creatures. Competitions took place in a virtual arena containing two virtual creatures and a cube. Before competition, the cube was place in the center of the arena with the creatures on opposite side of it. The starting distance between a creature and the cube was proportional to the creature's height, discouraging the evolution of creatures that simply fall onto the cube. Competition ended after one creature had been in contact with the cube for a set amount of time, or a maximum amount of time has elapsed. After competition ended, the distance was calculated between each creature and the cube. Creature fitness was based on a ratio of these distances, so creatures were encouraged to both reach the cube and keep it away from their opponent. Figure 21 shows the virtual competition arena. -- - 63 ~, , , , ,ere star1ingzone atnre #1 , I # • •~ ~ ; ~ starting z crl.'ature olle #2 , I cube ~ ; I ~ ".. - I~ ~~ I I I gnlUud plane • I Figure 21. Virtual competition arena. Note. From "Evolving 3D Morphology and Behavior by Competition" by K. Sims, 1994, Artificial Life, 1(4), p. 354. Co-evolution produced some interesting strategies for winning the competition. Some creatures used arm-like structure to block access to the cube, some curled up around the cube, and some moved the cube away from the center of the arena. These behaviors would not have emerged through individual evolution. If the competition had been a race, then results would likely have been similar to those produced using individual evolution. Co-evolution methods are well suited for evolving creatures to outperform competitors, especially when offensive and defensive mechanisms are necessary components of a successful strategy. Ray (2001) built upon Sims' framework by allowing the user to interact with the evolutionary process. An initial random population was first generated and displayed for the user. Still images and motion sequences could be viewed for each creature. Aesthetically pleasing creatures could then be selected for combination and/or further 64 evolution. Selected creatures could be evolved to perfonn behaviors such as: walking, jumping, swimming, and following. In this way, a user could evolve a virtual creature to his/her liking. Directed graphs were used to represent virtual creature minds and bodies using an approach similar to that of Sims (1994). Evolvable color attributes were included with the morphology parameters for added customizability. New sensor types were added to the joint control networks including: position, velocity, angular velocity, force, and color perception. A new type of effecter modified color attributes. The additional parameters, sensors, and effectors supported a larger range of behaviors and appearances for the virtual creatures. Figure 22 shows an example evolved virtual pet. Figure 22. Example evolved virtual pet. Note. From "Aesthetically Evolved Virtual Pets" by T. S. Ray, 2001, Leonardo, 34(4), p. 314. 65 i This framework provided a means for users to interactively evolve virtual pets. A natural extension would be a system for nurturing the virtual pets. The implementation did not use collision avoidance to prevent interpenetration ofbody segments. As a corollary, multiple interpenetrating (and therefore redundant) body segments may have been considered in contact with the ground or water. The additional ground contact may have caused unpredictable and possibly umealistic results during physical simulation of the creatures. Hornby and Pollack (200 1) used parametric Lindenmayer Systems (L-Systems) to generate creatures that exhibited morphological symmetries like those seen in natural creatures. L-systems consist ofgrammatical rewriting rules that are applied in parallel to an input string, resulting in an output string that is a variation ofthe input string. Lindenmayer (1968) first used such systems to model the development of cellular organisms. Later, Parametric L-system (Lindenmayer, 1974) extended "traditional" L- systems by using parameters and algebraic expressions when determining which production rule to use. The use ofparametric L-systems allows the evolution of creatures with hierarchies of similarities, such as limbs and vertebral structures. Creature behavior was controlled using an ANN. The networks were created by evaluating a string of commands outputted by the L-systems. The commands created, duplicated, and merged neurons and adjusted link weights. The neural network used a single input node, driven by either a sigmoid, linear, or oscillating function. Morphologies were constructed similarly by interpreting LOGO-style build commands. These commands allowed the creation and backtracking of rigid links and the creation of several joint types. 66 When a joint was created, an output neuron was also created in the neural network to drive the joint. The L-systems responsible for generating creature morphologies and neural controllers were evolved using GP. The production rules of the L-systems were evolved to maximize the distance traveled by a creature during a set period of time. Creatures were penalized for dragging contact, which encouraged the creatures to take steps. Experimental data showed that the creatures evolved using L-systems exhibited more regularity and greater fitness than creatures evolved using earlier approaches. These results were likely due to the emergence oflimb-like structures. Figure 23 shows two example L-system generated creatures. Figure 23. L-system generated creatures. Note. From "Body-brain co-evolution using L-systems as a generative encoding" by G. S. Hornby and 1. B. Pollack, 2001, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-200l), p.874. 67 The ALife work presented thus far has explored the simultaneous evolution of character minds and bodies. Bongard and Pfeifer (2002) presented a method for comparing the locomotive efficiency of creatures with different bodies but similar minds. Ten different legged creatures were created, each with unique size, masses, and body plans. Each creature was equipped with eight actuated I-DOF joints, four angle sensors at key joints, and four touch sensors at key body locations. The creatures were evaluated based on the forward distance they were able to travel during a fixed time interval. Figure 24 shows the ten creatures that were created and evaluated for locomotory efficiency. Figure 24. Ten creatures evaluated for locomotory efficiency. Note. From "A Method for Isolating Morphological Effects on Evolved Behaviour" by 1. C. Bongard and R. Pfeifer, 2002, Proceedings ofthe Seventh International Conference on the Simulation ofAdaptive Behavior, p. 306. 68 Creature behavior was generated using an ANN. Each creature's neural network consisted of an input node for each of the eight sensors, three hidden nodes, and an output node for each of the eight actuators. A simple threshold model was used to determine neuron activation based on input link weights. A GA was used to evolve the neural network weights. In this way, the creatures were able to learn how to use their neural networks, but not evolve the neural networks themselves. All 10 creatures were evolved to generate some form of forward locomotion. Quadrupedal and hexapedal creatures generated the fastest forward locomotion. Tripedal creatures also produced fast locomotion. Creatures with a greater number of limbs and long, snake-like creatures generated the slowest locomotion. This result was likely due to additional friction caused by having more body points in contact with the ground. Another possible explanation is that it was more difficult for the neural network to coordinate larger numbers of limbs. This theory was supported by showing that increasing the number of hidden layer neurons increased the forward locomotion speed achievable by the highly­ limbed and snake-like creatures. ALife techniques have been used to generate interesting new creatures with equally interesting new methods ofproducing locomotion. In all of the presented work, ANNs were utilized to control joints. Creatures have been evolved based on individual performance, by survival ofthe fittest, or by user interaction. Observing the successes and failures of a creature trying to walk or swim gives some insight into the advantages and disadvantages of certain gaits. For more information on ALife techniques for character animation, see Taylor's (2000) review ofthe area. 69 Robotics Robotics is a large research area unto itself. Over the past decade, researchers in the field of Evolutionary Robotics have developed techniques for self-learning and self­ designing robots. For the purpose of this review, current state-of-the-art work will be presented on methods for evolving locomotion in robots. Azevedo (2001) discussed correlations between the studies of human and robot locomotion. Azevedo argued that biomechanical observations can improve robot stability and reduce energy consumption. Similarly, robotics can be used to evaluate prosthetic limbs and test alternate joint configurations and gait strategies to aid in the study ofhuman locomotion. Golubovic and Hu (2002) used GAs to optimize locomotion for the Sony AlBO robot. The AlBO was a quadrupedal robotic pet intended to behave like a cat or dog. The robot had the ability to emulate instinct, emotion, and learning capabilities. Each AlBO learned from experience during a training phase, settling on a [mal set of behaviors when it reached virtual maturity. The locomotion engine for the AlBO was robust, allowing the robot to walk forward, tum, follow targets, and get back up after falling over. GAs were used to tune the AlBO locomotion engine for maximum speed and stability. The gait generator utilized a set of six parameters for the front limbs and six parameters for the hind limbs. These parameters were used to generate cyclic motions for each end effecter that roughly followed an elliptical path. The governing parameters were the width and height ofthe path, the x, Y, and z coordinates of the center of rotation for the path, and the angle of the paw relative to the ground. A thirteenth parameter was used to specify the forward velocity of the robot. The parameter set was evolved to maximize 70 forward velocity and stability. To measure stability, readings were taking from three gyro sensors during trial runs. Lower variance between readings indicated higher stability. Figure 25 shows the configuration of the AlBO forelimb. Figure 25. AlBO forelimb. Note. From "A hybrid evolutionary algorithm for gait generation of Sony legged robots" by D. Golubovic and H. Hu, 2002, Proceedings ofthe 28th Annual Conference ofthe IEEE Industrial Electronics Society, 4, p.2595. Locomotion evolution experiments were conducted in hardware on the AlBO itself. This approach diverged from the typical simulation approach. Golubovic and Hu admit 71 that running simulations would have been easier, but contend that simulation may miss important interactions between the robot and its environment. A good physics simulation should produce negligible errors ifmass, inertial, and environmental conditions are properly modeled. Simulation saves both time and hardware costs, but may neglect subtle physical effects. Wolff and Nordin (2003) utilized GP to evolve locomotion on a humanoid robot named Elvina. Elvina had 12 joint DOFs, three per limb. Locomotion was generated by interpolating a set ofwhole-body pose configurations. Locomotion was evaluated in both simulations and hardware. Balance was maintained during locomotion by keeping the projection of the COM onto the ground within the robot's support polygon. The robot's upper limbs were utilized to offset its COM while the lower limbs were used for locomotion. Genetic programs resembling assembly language were used to produce locomotion. The programs took the robot's current pose configuration as input and computed the robot's next pose configuration. Each genetic program consisted ofa maximum of 256 instructions. Instructions contained an operator (add, subtract, multiply, divide, and sin), source registers, and a destination register. The evolved sequence ofposes was cycled to produce continuous locomotion. Gaits were evaluated based on the robot's ability to remain upright and travel forward quickly. The fitness function was thus based on maximum distance covered in a set amount of time and minimal change in robot head height. 72 The approach successfully generated forward locomotion on both the physical and simulated robot. These experiments show the utility of the GP paradigm by evolving a complete locomotion program from scratch. The GP approach is well suited for evolving programs that can be run in hardware. Wolff and Nordin point out that while evolving on actual hardware is more accurate, it is time consuming and the hardware upkeep price can be high. Simulating early evolution followed by subsequent evolution of good programs on real hardware may be an economical compromise. Zhang and Vadakkepat (2003) used GAs to evolve locomotion for RoboSapien, a 12-DOF humanoid robot. RoboSapien could walk continuously on flat ground and climb stairs while avoiding obstacles. The robot used the Zero Moment Point (ZMP) method (Vukobratovic and Juricic, 1969) for maintaining balance. The ZMP is the point on the ground where the sum of all active force moments is zero. To maintain balance, the robot's ZMP must stay within the support region. This method is effectively equivalent to keeping a character's COM above the support region. Locomotion was generated by calculating hip and pes trajectories. The horizontal component of the hip was calculated using the support phase period, the swing phase period, and the total step period (implicitly giving the dual support period). The horizontal component of the swing leg trajectory was calculated by taking into account the swing phase period and the total step period. The height component ofthe hip and swing leg trajectories was determined by checking for obstacles in the leg's path. Trajectories were stored as cubic polynomials. The set ofparameters governing the hip and pes trajectory 73 calculation were evolved to maximize robot balance by minimizing the distance between the actual and optimal ZMP. The gait generation strategy was used to generate locomotion in hardware. The robot was able to maintain balance while walking forward and avoiding obstacles. The robot was also able to maintain balance while climbing stairs. The robot's motion was limited to forward movement, simplifying the motion equations but limiting the robot's usability. The approach to calculating hip trajectory was similar to that used by Chung and Hahn (1999). Figure 26 shows the hip and pes trajectories while avoiding an obstacle. Hip motion was decomposed into horizontal and vertical trajectories, so adding a lateral trajectory should be tractable. 74 . I : I . . . .- L -:8 • Figure 26. Hip and pes trajectories during obstacle avoidance. Note. From "An evolutionary algorithm for trajectory based gait generation ofbiped robot" by R. Zhang and P. Vadakkepat, 2003, Proceedings of the International Conference on Computational Intelligence, Robotics and Autonomous Systems, p. 3. Wyeth and Yik (2003) used the ZMP method, GAs, and multiple-DOF joints to produce locomotion for the GuRoo robot. GuRoo operated using 23 DOFs, 15 of which were used in producing locomotion. The hip joints used 3 DOFs, the knee joints used 1 DOF and the ankle joints used 2 DOFs. The remaining DOFs were used to drive the head, neck assembly, and the arms. The robot was capable of shifting its weight, walking, turning, shaking hands, and waving. 75 Locomotion was generated by evolving a set of key pes locations. Eight key locations were used to fully specify the walking motion of one leg (two swing phase locations, four support phase locations, and two transitional locations). The key locations were then mirrored and applied out ofphase to drive the contralateral leg. Figure 27 illustrates the key pes locations. A GA was then used to evolve a locomotion sequence that minimized the difference between actual and optimal ZMP trajectory. The key locations were normalized so that they could be scaled to adjust stride length and pes clearance height during locomotion. . \ . . I \ I . + \ . I ........~............'. ...~........... 7'" . \ ... 1 i2 1····~..···t"···..·..,·····""!·····~ •._. ··_···....·····_·1.··....... 3 6 5 4 Sagittal Plane Frontal Plane Figure 27. Key pes locations. Note. From "Evolving a locus based gait for a humanoid robot" by G. K. Wyeth and D. T. F. Yik, 2003, IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2003), p. 1640. 76 Experimental results showed that it is possible to evolve a stable forward walk by specifying only pes locations. By specifying pes locations and balancing the robot's body, the robot could have followed a trackway. Similar method could be used to evolve trackway-following motion sequences for virtual characters. IK was used to solve for knee and hip configurations, which was possible due to the use of simple hinge and ball and socket joints. The hip height was fixed; adding a hip height parameter would allow more variation in the evolved gaits. Recent methods for evolving robot locomotion have focused on the use of GA and GP. The robotics techniques presented use sensor input in determining phenotype fitness, but do not use sensor input to vary responses at execution time. To provide more complex behaviors, such as following, a sense and response system could be evolved using GP or ANNs. In this way, character animation techniques can be valuable to robotics. Similarly, stable walking techniques based on new genotype representations could be useful for character animation. Computational Gait Analysis Computational methods have aided the study of biomechanics by providing virtual 3D environments for conducting biomechanics experiments and visualizing results. 3D visualizations allow an investigator to arbitrarily rotate a model and zoom in on points of interest without comprising image quality, a vast improvement over previous 2D methods. Models are typically built from geometric primitives or bone shape data obtained from 3D scanners. Locations of articulation (i.e., joints) within the model are animated using simple 77 forward kinematics, Motion Capture data, or complex dynamic and/or musculoskeletal models. Biomechanical models and methods are particularly valuable for locomotion models in that they add biological and mechanical credibility. The Software for Interactive Musculoskeletal Modeling (SIMM) project was introduced by Delp and Loan (1995) and later revisited with an improved feature set (Delp and Loan, 2000). SIMM allowed user to visualize, edit, and experiment on 3D biomechanical skeletons. Models consisted of a bone file containing 3D bone shape information, a joint file specifying the kinematics of the model's joints, and a muscle file specifying muscle-tendon parameters. SIMM represented joint kinematics using three orthogonal translations and three rotations about arbitrary axes, providing six total DOFs. The order in which the rotations and translations were applied affected joint behavior and needed to be specified by the user. Specifying the order of 3D transformations can be unintuitive and should be consistent between models, and it is still an important issue in 3D modeling today. A generalized coordinate is a variable with some range ofvalues. SIMMjoints were assigned a number of generalized coordinates based on their behavior. A hinge joint used one generalized coordinate while a ball-and-socket joint utilized three generalized coordinates. A joint's six DOFs were controlled by manipulation of its generalized coordinates through the use ofkinematic functions, one function per DOF. These functions were defined by spline curves which could be edited using a graphical interface. An elbow, for example, had one generalized coordinate representing its flexion/extension movement. Kinematic functions mapped the elbow flexion/extension coordinate to rotation about an 78 oriented axis, translation in the x direction, and translation in the y direction (relative to the proximal bone). The basic idea of a generalized coordinate is widely used in animation to define hierarchies ofmovement. At the highest level, a generalized coordinate representing the animation timeline is used to drive all child animations. A drawback to the approach used by SIMM is that the user had to decide which DOFs should be controlled by each generalized coordinate. The number of generalized coordinates that could be associated with a joint was limited by the joint's six DOF; each joint DOF was controlled by at most one generalized coordinate. Due to this restriction, multiple generalized coordinates could not cause rotation about the same axis, potentially forcing non-biological orthogonality into the joint model. To avoid this limitation, users could have built compound joints by utilizing multiple individual joints with additive effects between bones. SIMM provided two important high-level functions. By specifying joint kinematics and a musculoskeletal model (including muscles, ligaments, and tendons), a user could build an animation timeline by providing muscle activation values as a function of animation time. SIMM would then simulate and animate the resulting joint kinematics. Inversely, given a skeletal animation (inputted directly using keyframes or from Motion Capture data), SIMM could compute the muscle forces and moments necessary to achieve the animation. Figure 28 illustrates a simulation of the human pectoralis major muscle, including the muscle lines ofaction. SIMM is now widely used in biomechanics laboratories around the world. 79 Figure 28. SIMM model ofthe pectoralis major muscle. Note. From "A computational framework for simulating and analyzing human and animal movement" by S. L. Delp and 1. P. Loan, 2000, Computing in Science & Engineering [see also IEEE Computational Science and Engineering}, 2(5), p. 48. SIMM has been applied to simulate the behavior ofknee implants during a stepup exercise (Piazza and De1p, 2001). Simulated motions of the implants were observed while manipulating of the tibiofemoral and patellofemoral knee joints. The simulation used recorded muscle activations as input and predicted joint kinematics using the forces and moments generated by the muscles, ligaments, tendons, and contact between implant surfaces. Implant surfaces were represented by polyhedral meshes obtained by exporting triangulated geometries from CAD representations. During the simulation, the number of contact points between articulating surfaces was allowed to vary, providing an accurate 80 estimation of the contact forces between surfaces. Figure 29 illustrates the biomechanical model used for evaluating the implants during the stepup exercise. y Figure 29. Biomechanical model used for the stepup exercise. Note. From "Three-Dimensional Dynamic Simulation of Total Knee Replacement Motion During a Step- Up Task" by S. J. Piazza and S. L. Delp, 2001, Journal ofBiomechanical Engineering, 123, p. 600. Complex musculoskeletal models are necessary for precision studies such as evaluating the effects ofprosthetic implants. Such models are useful for studying and generating locomotion, but construction of the model is often prohibitively laborious with respect to the application. Sufficient data for reconstruction ofa complete musculoskeletal 81 model of sometimes not even available, as can be the case with extinct species. Simple kinematic joints can, in principal, emulate the functionality of a complex musculoskeletal joint provided that the joint's ROM was constructed using appropriate biological and physiological constraints. Another system for modeling biological joints was introduced by Maciel, Nedel, and Dal Sasso Freitas (2002). In addition to standard planar, uniaxial, biaxial, and polyaxial, the system provided a sliding-axis joint. The sliding-axis joint allowed the instantaneous axis or a hinge joint to be moved along a parametric curve when rotating the joint. Joint motion was represented by specifying a minimum, neutral, and "comfortable" configuration for the joint. Final joint axes and angles were therefore interpolates of these input configurations. Figure 30 shows a knee modeled using a sliding-axis joint. 82 ~ r 2./I~O. r/' / , l\ ',/ __ "3 I I JI -­ , J t' \ Ire __ i I r 1 \ , - - 4 I I I \ " / ; J I \ / J I t \ , J [ \ , J I I Figure 30. Knee represented using a sliding-axis joint. Note. From "Anatomy-based joint models for virtual human skeletons" by A. Maciel, L. P. Nedel, and C. M. Dal Sasso Freitas, 2002, Proceedings ofComputer Animation, 2002, p. 224. Hutchinson et al. (2005) used SIMM to create a musculoskeletal model of the Tyrannosaurus rex hindlimbs. The model consisted often joint DOFs (i.e., flexion/extension, abduction/adduction, medial/lateral rotation) and 33 muscle groups crossing the hip, knee, ankle, and toe joints of each limb. Muscle groups were modeled using bone geometry data by specifying joint rotation axes, muscle attachment locations, and muscle-tendon geometry and paths. Figure 31 shows the Tyrannosaurus rex hindlimb musculoskeletal model. 83 Figure 31. Tyrannosaurus rex hindlimb musculoskeletal model. Note. From "Analysis of hindlimb muscle moment anns in Tyrannosaurus rex using a three-dimensional musculoskeletal computer model: implications for stance, gait, and speed" by J. R. Hutchinson, F. C. Anderson, S. S. Blemker, and S. L. Delp, 2005, Paleobiology, 31(4), p. 682. The hindlimb musculoskeletal model was used to determine and analyze the flexor and extensor muscle moments about the limb joints. Muscle moment arms were evaluated based on several static limb poses with varying sagittal elevation angles (i.e., flexion/extension of the hip). Results showed that more upright poses have significant 84 mechanical advantage of the joints when compared to less upright poses. This result seems intuitive because non-columnar limbs cause potentially unnecessary torques about the limb's joints. These torques are caused by ajoint's position being noncollinear with the Ground Reaction Force (GRF), which is related to the muscle moment arms necessary to stabilize an animal. Results also showed that the static moment arms are not ofthe magnitude expected from a proficient runner, providing further evidence that Tyrannosaurus rex was not a fast runner. These results provide insight into the necessary muscle mass to support Tyrannosaurus rex while standing, which is relatively small compared to the estimated muscle mass necessary for Tyrannosaurus rex to run quickly. The muscle-moment-arm and mass estimates are based on static poses, so are not based on a fully-dynamic musculoskeletal model. These methods do not recreate gaits, but allow an analysis of the muscle masses necessary for gaits. Hutchinson and Gatesy (2006) explored possible hindlimb configurations of Tyrannosaurus rex during locomotion and while standing. They identified a mid-stance configuration for the each limb based on the limb's GRF. Specifically, a limb's GRF points up and back as the limb makes contact with the ground and points up and forward as the limb accelerates the body; mid-stance is a limb joint configuration when the GRF is vertical. At mid-stance, there is a family of solution configurations based on the hip height of the animal. They observed that optimal hip height cannot be determined from bone osteology alone, because the animal has limbs flexible enough to allow the animal to lie down. 85 Once hip height has been determined, there is still a family of limb configuration solutions possible based on a fixed hip and toe positions. Given hip, knee, ankle, and main toe joints with 90° offlexionlextension (i.e., four DOFs) sampled at a 1° resolution, there are more than 65 million possible joint configurations. Figure 32 illustrates the families of possible hindlimb configurations. Hutchinson and Gatesy suggested the use ofGRF-based pruning criteria to remove unlikely joint configurations from the solution space. For example, configurations with the GRF in front of the knee were excluded. Configurations were also removed that contained any joint such that the GRF's moment arm about the joint exceeded a maximum value. The maximum moment arm value was based on the moment arm that could be generated if5% of the animal's body mass was dedicated to muscles crossing the joint. 86 Figure 32. Possible mid-stance configurations. Note. From "Beyond the bones" by J. R. Hutchinson and S. M. Gatesy, 2006, Nature(London), 440(7082), p.292. When exploring the space of all possible limb configurations, it is necessary to prune the space to make searching it tractable. Some animals have limbs that utilize up to eight discrete DOFs. In the above example, sampling four 90° DOFs (at a 1° resolution) creates more than 65 million limb configurations. Adding another 90° DOF increases the size of the space exponentially, expanding it to almost six billion configurations. Increasing the space to six 90° DOFs expands the space to over 530 billion configurations. Pruning the space using GRF-based constraints is intuitive, but requires dynamic simulation to accurately determine COM and GRF values. Dynamic 87 simulation is relatively-expensive computationally, so simulation oflarge numbers of configurations can be intractable. Henderson (2006) used trackway data to recreate quadrupedal gaits. Gait key poses were created by manually positioning joints. A system of partial differential equations was then used to derive the joint angles necessary to achieve joint positions (i.e., IK). Joints were positioned such that the manus and pes positions and orientations approximated the trackway data. The limbs were additionally constrained such that there was no vertical displacement of the body during locomotion. Due to the large masses of the dinosaur and elephant models, gaits were constrained based on the stability of the static poses. Specifically, only a single limb was allowed to be in the swing phase at a time. In addition, the COM was constrained to lie within a triangular region defined by the manus and pes positions of the three supporting limbs, called the Stability Triangle. Intuitively, wider-stance trackways provided a larger Stability Triangle than more narrow trackways. Results showed that the models with a centrally-located COM were most stable in wide trackways while models with a more posterior COM were most stable in narrow trackways. Figure 33 shows a Brachiosaurus model with its associated trackway, COM, and Stability Triangle. 88 o 7 8 9 10 11 12 13 14 15 16 Length (m) Figure 33. Brachiosaurus trackway, COM, and Stability Triangle. Note. From "Burly gaits: centers ofmass, stability, and the trackways of sauropod dinosaurs" by D. M. Henderson, 2006, Journal o/Vertebrate Paleontology, 26(4), p. 917. In a static pose, a quadruped will tip over if its COM is not within its Stability Triangle. As a corollary, maintaining balance with four supporting limbs is relatively easy. Maintaining balance with three supporting limbs is more difficult but still very plausible. Maintaining balance with two supporting limbs is only possible if the COM lies in the plane connecting the two supporting limbs (and perpendicular to the ground), implying that an animal is only statically stable on two supporting limbs if those limbs are diagonal (e.g., right hindlimb and left forelimb) and the animal exerts enormous effort to balance itself. 89 During locomotion, however, the animal is always moving and never statically posed. The positiQILQfthe COM and supporting manus/pes is therefore not enough information to determine stability; the dynamics of the COM (i.e., velocity and acceleration) must also be considered to prevent overly conservative stability estimates. For example, an animal's COM may be outside the animal's Stability Triangle but the COM's velocity might be such that the COM will be back within the Stability Triangle very quickly. Such a situation could be considered statically instable but dynamically stable. Sellers and Manning (2007) extended earlier work (Sellers et aI., 2004) by adding elastic elements (Hill, 1938) to their muscle model. In addition, several changes were made to their GA implementation (i.e., using the Opel?- Dynamics Engine in favor of Dynamechs) for improved computational performance and stability. These new methods were used to determine the maximum running speeds of five extinct bipeds (i.e., Compsognathus, Velociraptor, Dilophosaurus, Allosaurus, and Tyrannosaurus) and three extant bipeds (i.e., Dromaius, Struthio, and Homo). Figure 34 shows evolved gaits of the various models. 90 1.5 (a) 1.0 (b) 0.5 o -0.5 3 4 5 6 7 8 9 3 4 5 6 7 8 9 (c) 0.4 (d) 0.2 o 2.0 2.5 3.0 3.5 4.0 4.5 5.0 5.5 1.5 -0.2 '-'--__--' 1.0 2.0 -'­ 3.02.5 -'--__--'­ 0.8 (e) 0.6 0.4 0.2 0 -0.2 1.5 2.0 25 3.0 3.5 4.0 4.5 43 (f) 1.5 1.0 0.5 o -0.5 '---'-_~_ 56789 _'__-'---_~_ _____'___ __'___ 1.5 1.0 0.5 0 -0.5 (g) 3 4 5 6 7 8 9 3 2 1 0 (h) 4 6 8 10 12 14 16 Figure 34. Evolved gaits of various models. Note. From "Estimating dinosaur maximmn running speeds using evolutionary robotics" by W. I. Sellers and P. L. Manning, Proceedings o/the Royal Society B: Biological Sciences, 274(1626), p. 2713. Fixed-length candidates were used to represent 61 parameters: five activation levels for 12 muscles (i.e., six per limb) and a parameter representing the cycle time. The candidates represented ten key-frames during the stride; the left-right muscle activation values swapped for the second half (i.e., keyframes 6-10) of the stride. The GA fitness 91 function was based on maximum running speed achieved during a fixed simulation time interval. Therefore, candidates that produced fast running speeds were rewarded while candidates that caused the model to fall over were heavily penalized. GA populations consisting of 1000 candidates were evaluated for up to 1000 iterations. The GA loop was interrupted early if a steady maximum forward velocity was maintained between iterations. The GA process was repeated at least five times to ensure that a near-optimal candidate was found. Furthermore, the entire process was repeated at least 20 times with the fittest candidates from the previous run seeding the population for the next run. This process took between several days to several weeks to run on a modem parallel supercomputer (as of this printing). Results showed that top speeds achieved by the simulated extant models closely corresponded to published top speeds. This result indicates that the top speeds achieved by the extinct models are likely also accurate, depending on the accuracy of the musculoskeletal model. The uncertainty ofmuscle parameters was explored using a sensitivity analysis; muscle masses were varied over the range [2.5%, 7.5%], showing that total muscle mass has a linear effect ofmaximum velocity. The sensitivity ofmuscle contraction velocity parameters was also tested. This work demonstrates the possibility ofevolving gaits for a variety ofmodels using a fairly simple hindlimb muscle model; two summary muscle groups (i.e., flexor and extensor) were simulated for each limb's primary joints. The algorithm takes a considerable amount of CPU time to complete. This cost is due to the number of iterations and reseedings necessitated by the massive size of the search space (i.e., 488-bit candidates 92 assuming eight-bit floating point resolution for the 61 parameters). In addition, the algorithm is expensive because it requires a dynamic simulation for each candidate evaluation. Gait analysis techniques are valuable to both biomechanics and animation. Musculoskeletal models are laborious to construct but allow accurate reproduction of muscle forces and torques, provided the muscle parameters (i.e., muscle mass, contraction velocity, and elasticity) are represented realistically. Also, GRF-based and stability-based constraints can be used to prune the space ofpossible limb configurations for locomotion. In principal, these constraints could be used in conjunction with GA methods to reduce the computational cost associated with evolving optimal gaits. Summary Current state-of-the-art techniques for evolving locomotion are based GAs, GP, or ANNs. GAs are useful for evolving a fixed set of gait cycle parameters. Gait cycle parameters are typically used as input to pattern generators that produce periodic locomotion. The pattern generators produce forward walking animations, although the Limit Cycle Control method (Laszlo et al., 1997) allowed turning by perturbing open-cycle motions. GAs are well suited for cases where little user and environmental interaction is required, such as exploring alternative gait strategies. GP and A},lNs are useful for systems that require a character to respond based on input stimuli. AJ'lNs have been used predominately to link stimuli to responses. Genetic programs can also be used to directly modify character configurations based on input 93 criteria. It is important to note that neural networks and genetic programs can only be effectively evolved to perform one primary task. For example, a virtual creature can be trained to achieve a complex goal such following a light source with a specific gait, but it is unlikely that the creature would be able to change gaits or perform other tasks using the same neural network or genetic program. Musculoskeletal models can provide biologically-accurate representations ofjoint motion, depending on the complexity and accuracy of the models. Musculoskeletal models can be utilized by GAs to automatically create gait animations, but the creation ofmodels is difficult due to model complexity and availability of data. Evaluation of the models is computationally expensive due to the use ofphysics simulation to determine the fitness of each candidate gait and the extremely-large solution spaces needed to represent all possible combinations ofmuscle actions. GRF and trackway constraints can be used to prune the space of possible solutions, but evaluation of a limb's GRF also requires physical simulation. Constraining the space with respect to mid-stance limb configurations may seem intuitive, but mid stance may be the time during the stance phase that the limb is most osteologically underconstrained. At mid stance, limbs are capable of a number of leaning, bending, and squatting motions. Conversely, limbs are much more osteologically constrained as they reach forward and backward at the beginning and end of stance. In the next chapter, methods will be presented that utilize constraints derived from the biomechanics of tetrapod limb joints and gaits that involve more than one limb in contact with the ground to constrain the space ofpossible limb configurations at the 94 beginning and end of stance. A GA will then be utilized to quickly find smooth, and therefore plausible, paths through the constrained spaces to automatically generate gait animation sequences. The GA evaluates candidate fitness based on the overall smoothness oflimb movements, so no physical simulation is necessary. The result is a set of algorithms that generate plausible walking gait animations with very little computational cost. 95 CHAPTER III METHODS AND MATERIALS The GAGA techniques and methodologies are presented is this chapter. GAGA automatically generates forward bipedal and quadrupedal walking gaits using biomechanically-accurate skeletons. A representation for discrete joint movement is first presented. Next, joint movements are combined to explore the kinematic capabilities of a limb. The kinematic capabilities are then analyzed and constraints are applied to allow the use of GAs to find paths through the spaces of limb configurations. GA-based methods are then presented that quickly create efficient bipedal and quadrupedal forward walking gaits. The chapter concludes with descriptions of the models used for the investigations presented in the next chapter. Functional Degrees of Freedom In the absence of dynamics, the kinematics-only models are completely rigid until flexibility is added to the joints. Flexibility is added at joints by specifying ROMs. A ROM is categorized by the number of functional movements that its corresponding joint 96 is capable of performing. Each of these functional movements is represented by a Functional Degree ofFreedom (FDOF). A shoulder ROM, for example, has three FDOFs representing: flexion/extension, abduction/adduction, and medial/lateral rotation; a knee has one FDOF representing its flexion/extension movement. The FDOF framework is similar to the generalized coordinate framework used by SIMM (Delp and Loan, 1995). Each ROM manipulates all six of the joint's geometric DOFs (i.e., three orthogonal translations and three Euler angle rotations about fixed orthogonal axes). The geometric DOFs manipulated by the ROM are applied relative to the joint's parent joint in the model skeleton. Three 6-DOF keyframes are used to specify each FDOF. The three keyframes represent the extremes of movement and a neutral position for the movement, similar to Maciel (2002). All neutral FDOF configurations within a ROM must be coincident. Based on input FDOF values, a ROM uses cubic spline interpolation to determine intermediate configurations for each movement. The configurations are then combined to determine the final output ROM configuration. Figure 35 shows the flexion/extension movement of an Apatosaurus elbow from right-lateral view. 97 Figure 35. Flexion/extension movement of an Apatosaurus elbow. FDOFs are a powerful representation, allowing a continuum ofmovement granularity from simple, idealized hinge or universal joints to a movement path constrained by musculoskeletal lines of action. In the next section, techniques will be presented that combine all of a limb's FDOFs to determine a total ROM for that limb. Limb Ranges of Motion To determine the effect of FDOFs on locomotion, the manus and pes are first positioned and oriented on the ground based on trackways. All combinations of FDOFs are then evaluated at a resolution between 4° and 6°, depending on the number and complexity of the FDOFs. Translation-only FDOFs (e.g., scapulothorax elevation) are evaluated at an appropriate resolution based on each model's dimensions (e.g., 5cm for Apatosaurus). The position and orientation of the manus and pes are maintained fixed on the ground throughout the evaluation process (see Appendix F). 98 Thompson and Holmes (2007) used a similar approach to recreate a possible walking gait cycle for a Chasmosaurus forelimb. Polyester resin casts were made from fossilized bones, and those casts were articulated using thin, flexible wires. The manus was then held fixed on the ground while the limb was manually exercised to determine plausible limb configurations during the cycle. The body was not allowed to be displaced laterally or vertically and the scapula was not allowed to move on the rib cage during the cycle, which would have unnecessarily overconstrained the gait. Repositioning and reorienting a manus or pes on the ground to match its original position and orientation, similar to Sticky IK methods (McKenna and Zeltzer, 1990), causes all proximal elements to be repositioned and reoriented. Figure 36 demonstrates this effect by showing flexion/extension of the Apatosaurus forelimb while maintaining a fixed manus position and orientation. For each combination ofFDOF values, an element proximal to the forelimb or hindlimb system (e.g., the 3rd dorsal for the Apatosaurus forelimbs and the 1st sacral for the Apatosaurus hindlimbs) is monitored for position and orientation. This proximal element is referred to as the root element of the system. The set of all possible root element positions and orientations reachable by exercising the limb's FDOFs is called the Limb Range of Motion (LROM). 99 Figure 36. Apatosaurus elbow flexion/extension with fIxed manus. LROMs can be organized for convenient access by first determining the Axis­ Aligned Bounding Box (AABB) that contains all of the LROM samples (by position). The 3D space within the AABB is then subdivided into a number of boxes with constant dimensions. Each box is populated with all LROM samples such that the sample's position is inside the box. The 3D grid of boxes, in summary containing all LROM samples, is called the LROM space. An LROM space can be visually represented by finding the LROM sample in each LROM space box that requires the least Root Mean Square (RMS) orientation change to lie within the box's bounds. Figure 37 shows a visualization of the Apatosaurus right forelimb LROM space, with minimum RMS orientation change represented by color (i.e., 0° < green < 15° < purple < 30° < yellow < 45° < red). 100 Figure 37. Visualization of the Apatosaurus right forelimb LROM space. LROM spaces allow the representation and visualization of the total ROM that a limb is capable of operating within. Limbs do not act in isolation during locomotion; the LROM space that represents all possible root positions and orientations when both left and right limbs are in contact with the ground can be summarized as the intersection of the left and right LROM spaces. Methods for applying bipedal constraints with respect to locomotion will be presented in the next section. 101 Bipedal Gait Reconstruction The following three sections describe the algorithms used to automatically generate bipedal walking gaits: Constraints must first be applied to the LROM spaces to ensure that locomotion does not effectively pull the body apart. A GA then finds smooth, plausible paths through the constrained space. Finally, a pipeline architecture will be presented that maximizes reuse of precomputed data, minimizing unnecessary repeat computational operations. Constraints The responsibilities of each limb during locomotion can roughly be divided into two phases: the limb supports the animal's mass and propels the animal forward during the stance phase (also referred to as the support phase); the limb is off the ground preparing for the next stance phase during the swing phase (also referred to as the suspended phase or step phase). The relative amount of time that a limb spends in the stance phase is the limb's duty factor. The duty factor is a normalized term (on the range [0.0, 1.0)); a duty factor of 0.0 would indicate that the limb is never in contact with the ground while a duty factor of 1.0 would indicate that the limb never leaves the ground. Bipeds utilize two limbs for locomotion so therefore have two relevant duty factors. The two duty factors are related by a phase term, which represents, for each stride, the relative elapsed time between the right limb beginning its stance phase and the left limb beginning its stance phase. This phase term is called the contralateral phase 102 and can apply to either hindlimbs or forelimbs. Like the duty factor, the contralateral phase is a normalized term (on the range [0.0, 1.0]). Figure 38 illustrates a bipedal duty vector with a 0.6 duty factor for each limb and a 0.5 (i.e., 180°) contralateral phase. R .J:l • Stance E ::::i uSwing • Stance L USwing o 0.2 0.4 0.6 0.8 1 Phase Figure 38. Example bipedal duty vector. During walking gaits, limbs have a duty factor greater than 0.5 (i.e., limbs are in the stance phase for at least half of each stride). Each limb is in contact with the ground for more than half of the stride, so there must be periods of time during which both limbs are in contact with the ground. These periods of time are called dual support. In the absence of turning, the movements of each limb are assumed to be bilaterally symmetrical and out of phase. With a contralateral phase of 0.5, a walk cycle has two 103 dual support phases (i.e., one just after each limb begins its stance phase). These constraints provide a powerful mechanism for pruning the LROM spaces with respect to forward locomotion. To take advantage of the above constraints, discrete key events must be identified during the walk cycle. These events correspond to limbs beginning their stance or swing phases: "Right Down" (RD) represents the beginning of the right limb's stance phase. "Right Up" (RU) is the beginning of the right limb's swing phase. "Right when Left Down" (RLD) is the right limb's configuration when the left limb begins its stance phase. Similarly, "Right when Left Up" (RLU) is the right limb's configuration when the left limb begins its swing phase. Equivalent events are also identified for the left limb. Figure 39 illustrates the relationship between these events, with noted similarity to Figure 5 (Bruderlin and Calvert, 1989). 104 Limb Locomotion Events Jl LRU RU Jl LD RLD Duty Factor LU RLU h LRD RD Figure 39. Events related to bipedal walking gaits. During locomotion, but not dual support, the root element position and orientation is determined by the stance limb's LROM space. During'dual support, both limbs are in .the stance phase, so the root element positions and orientations predicted by the LROM spaces must be coincident. Otherwise, the body would be effectively pulled apart! The root element positions and orientations predicted by the LROM spaces must be coincident at RD and LRD. Likewise, the predictions for RLU and LU, RLD and LD, and RU and LRU must be coincident. 105 The left-and-right-side ROMs are bilaterally symmetrical, so the root element position and orientation caused by a right-limb FDOF configuration will be mirrored across the sagittal plane when the same FDOF configuration applied to the left limb. The limb movements are assumed to be bilaterally symmetrical during forward locomotion, so left-and-ride-side locomotion events that share an FDOF configuration (e.g., RD and LD) cause root element positions and orientations that are mirrored across the sagittal plane. The dual support constraint forces left-and-right-side events that occur at the same time to have coincident root element positions and orientations. The bilateral symmetry constraint forces left-and-right-side events that share an FDOF configuration to have root element positions and orientation that are mirrored across the sagittal plane. Combining these constraints, LD must have a root element position and orientation that is mirrored across the sagittal plane from RD's root element position and orientation. Furthermore, RLD must have a root element position and orientation that is coincident with LD's. The same relationships exist between LRU, RLU, and RU. Figure 40 illustrates these relationships. 106 Root Configuration During Right Stance z Initial Sagittal Plane x Figure 40. Relationships between discrete key events during forward locomotion. Amazingly, the dual support and bilateral symmetry constraints force the eight original key locomotion events to be described by only two unique FDOF configurations (e.g., the configurations responsible for RD and RLU). The two discrete FDOF configurations apply to only one of the two limbs, so one LROM space is sufficient to represent a walk cycle. Specification of a walk cycle therefore consists of selecting two samples from the LROM space. The distance along the direction of travel between events is known (e.g., the dual support distance in the case of RD and RLU), further 107 constraining the selection process. The next section will cover the selection of LROM space samples in more detail. Reconstruction Bipedal gaits are reconstructed from pairs of LROM space samples, specifically samples representing RD and RLU. Due to the dual support and bilateral symmetry constraints, an LROM space sample is eligible to be selected for RD if and only if there exists an LROM space sample for RLD that is mirrored across the sagittal plane and further along the direction of travel (see Figure 40). The distance along the direction of travel between RD and RLD is the forward distance traveled while the limb is in its swing phase (equal to step length - dual support length). Similarly, an LROM space sample is eligible to be selected for RLU if and only if there exists a suitable LROM space sample for RU. The set of all candidates for RD and RLU can be visualized by pruning the LROM space. All samples that do not have a suitable sibling sample (i.e., mirrored across the sagittal plane and properly forward along the direction of travel) are removed. The LROM space is populated with discrete samples, so the chance of exact matches (within floating point precision) is extremely low. For this reason, a minimum error term is used that aggregates position and orientation error between samples. Figure 41 shows a pruned Apatosaurus forelimb LROM space with blue representing samples that are siblings but not candidates. 108 Figure 41. Pruned Apatosaurus forelimb LROM space. For clarity, Figure 42 shows a comparison of the Apatosaurus forelimb LROM space before (left) and after (right) pruning. Recall that after pruning, the positions colored blue are not candidates eligible for selection as RD or RLU. In this example, the pruning process reduced the space from 5,221,125 samples to 406,377 candidate samples. 109 Figure 42. Apatosaurus forelimb LROM space before and after pruning. A GA is used to evaluate candidate solutions that represent bipedal walking gaits (see Appendix G). Each candidate consists of an LROM space sample and associated FDOF configuration for RD and an LROM space sample and associated FDOF configuration for RLU. The GA selects optimal candidates using an aggregate fitness function that penalizes pitching, rolling, and yawing of the body and large changes in FDOF values between the RD and RLU configurations. The fitness function also rewards the lateral and vertical smoothness of the gait. The lateral smoothness is relative to the initial sagittal plane; the vertical smoothness is relative to an adjustable target height parameter. The FDOF-value term discourages limbs from undergoing unnatural movements to achieve the kinematic-smoothness goals of the body. If a limb contains several redundant FDOFs (i.e., with near-coincident instantaneous axes of rotation), many solutions may result in a single root node position and orientation. In this case, RD and 110 RLU candidates may be selected that cause unwanted and unrealistic rotations between key configurations. For example, knee, ankle, and manus joints can counterrotate relative to each other through quite a large total angular excursion without causing much forward movement at the hip. Changes in FDOF values represent angular excursions (unless the FDOF is translation only), so discouraging large changes in FDOF values in effect discourages large angular excursions summated across all FDOFs. FDOF values are normalized on the range [-1.0, 1.0], so this representation prevents FDOFs with larger total angular excursions from being penalized proportionally more than FDOFs with less angular excursion. Unnatural limb movements could likely also be avoided by penalizing similar criteria such as sum angular acceleration (Raibert and Hogins, 1991; Chung and Hahn, 1999). The target height term encourages vertical smoothness and walking at an appropriate height. Imagine an animal walking with very bent limbs; without specific osteological support, excessive bending at a joint causes a torque about the joint (Hutchinson, 2005). This torque is caused by the position of the joint not being collinear with the GRF vector. Counteracting the torque is mechanically and energetically expensive and nominally avoided by animals. Rewarding candidate solutions proportionally based on the vertical height of the body encourages walking with straight limbs, which better approximates energetic constraints. Conversely, specifying lower target height values allows the evaluation of more-squat gaits. In this way, mammalian 111 models can walk with generally straight limbs without encouraging reptilian models to use an inappropriately-high walk. To reduce the total number of candidate solutions, the candidate LROM space samples are organized into two data structures. RD represents the start of the right limb's stance phase, so it must be at least a step length back from the front of the space so that the body can be moved forward by the step length during stance. All candidate samples that are at least a step length back from the front of the space are stored in a linear array called the back data. RLU is further along the direction of travel from RD by the dual support length, so there are a limited number of candidates that can be selected for RLU based on the selection of RD. The candidate LROM space samples are therefore also divided into coronal slices and stored in a two-dimensional array called the slice data. When the GA selects a sample for RD from the back data, RD's coronal slice is determined using a constant-time operation. RLU's slice is then computed using the dual support length and a sample is chosen for RLU within that slice. Figure 43 illustrates the back data and slice data and how they relate to the LROM space. 112 LROM Space Organiza~ion for GA ".­ .- ~ ...... - ........ - .. ..- 10"_ ..._." ,- -,t .... -. - .•. -...- • .. ~-..,..-,... --'~. ~ •. ., .,." •.' ••'?-- -.-,.. - --' ..... ,... "r"~".' --. - --r--', ­ .,.~. ~..". 1­ ~ __ . _. _+' __ !'_ ~ . ..- .•+-.. ~_. __ -.,0.- .......--. __ !- . ..,. -•.,.• .....,--.~~.. ~ -... t--,_.,. .-·"t"-r·,.-._·· ?-- ................ - ....... - ......-. -- _- ...- -,. Slice Data z z x x Figure 43. Back data and slice data organization. The back data and slice data organization provides two important advantages to the GA. First, any candidate solution will at least accomplish a stance phase that moves the body forward by the step length. Candidates then need only be evaluated on how well they move the body forward (i.e., minimum body roll, pitch, and yaw, and changes in FDOF values; maximum lateral and vertical smoothness), allowing the GA to converge much more quickly than it would if the solution space included candidate solutions incapable of accomplishing a successful stance phase. 113 The second important advantage of the back data and slice data organization (which is really a corollary ofthe first advantage) is that a candidate solution can be represented and encoded as two integer values: one value for the index of RD in the back data and one value for the index within RLU's slice in the slice data (the slice is determined by RD). Candidate solutions can therefore be represented by fixed-length linear binary strings. The number ofbits used to represent candidate solutions is determined dynamically by finding the next power of two bigger than the number ofback data samples and adding it to the next power of two bigger than the largest (in terms of sample count) coronal slice in the slice data. During GA iterations, each candidate in the population has a chance to be mutated and/or combined with another candidate. The probably of being mutated is based on a mutation coefficient; a coefficient of 1.0 indicates that on average every candidate will have one random bit flipped. The probability of a candidate being combined with another candidate is based on a crossover coefficient. A candidate is combined with another randomly-selected candidate using single-point crossover; an index is randomly selected before which the first candidate receives the second candidate's binary data and after which the second candidate receives the first candidate's binary data. The solution selected by the GA is used to reconstruct all eight of the key locomotion events. An additional FDOF configuration is selected to represent the midpoint of the swing phase. The mid-swing configuration is selected using an IK method that iteratively adjusts each FDOF to find a configuration that positions the manus or pes above its initial position by a specified step height. The right-side FDOF 114 configurations are used to specify the associated left-side events (e.g., RD to LD). The left-side events are then offset in animation time based on the contralateral phase. The dual support and bilateral symmetry constraints allow the LROM space to be significantly pruned, and ensure that the remaining samples do not pull the body and limbs apart during dual support. The back data and slice data organization allow the GA to search a space of candidate solutions which will at least move the body forward by the appropriate amount during the stance phase. The resulting implementation can automatically generate bipedal walk animations in less than one minute (7 FDOFs, 1000 candidate population, 10~000 GA iterations) on a consumer laptop (as of this printing). Figure 44 shows an example Apatosaurus forelimb walk animation created using these methods. Figure 44. Apatosaurus forelimb walking animation. The GA quickly finds smooth paths through the constrained LROM spaces. The LROM space exploration and organization operations, along with the GA operations, are 115 discrete operations that can be organized in terms of data flow such that input parameters can be modified at each of these stages without repeating earlier stages. The next section will cover the organization of this pipeline. Pipeline The process of automatically generating bipedal walking animations is divided into discrete operations. Between each operation, data is saved so that an operation need only be repeated if its input variables are modified. The Explore Space operation takes the model's FDOFs as input, along with angular and translational resolution parameters. The operation outputs the LROM space samples in unorganized form. The Organize Space operation takes the unorganized space data, organizes it into 3D boxes, and applies the bipedal constraints. The operation takes as input the unorganized space data, the duty factor, the constraint error tolerance, the step height, and the number of sample boxes along the primary locomotion axis. After the LROM space has been explored, organized, and pruned, the Find Path operation plots a path through the constrained space using standard GA parameters as input. The GA parameters include: crossover coefficient, mutation coefficient, candidate population size, and number of GA iterations. The Find Path operation also generates and outputs a complete bipedal animation file, which is visualized and interpolated using the Animate Path operation. The Animate Path operation utilizes an adjustable animation time parameter to vary the animation playback speed. Figure 45 illustrates the operations of the bipedal gait pipeline. 116 Bipedal Gait Pipeline FDOFs Angular Resolution .. l... Ex_p_lo_re_s_p_aoo ".,lTranslational Resolution t Duty Factor Constraint Error Tolerance Step Height .. l Organize Space ] Primary Locomotion Axis Boxes ""---------­ Crossover Coefficient Mutation Coefficient Candidate Population Size F_ind_pa_th .. l t __,.,l GA Iterations t Animation Time .. [ Animate Path ] ""---------­ Figure 45. Bipedal gait pipeline. The bipedal gait pipeline allows the computationally-efficient generation of bipedal walking gaits, even when changes to input parameters is necessary. Quadrupedal locomotion is significantly more complicated, requiring parallel bipedal pipelines and additional constraints for summarizing the ROM of the animal's trunk. The next section will present methods related to the generation of quadrupedal gaits. 117 Quadrupedal Gait Reconstruction The following three sections describe the algorithms used to automatically generate quadrupedal walking gaits. Constrained hindlimb and forelimb LROM spaces must first be generated. Those spaces must then be further constrained to simulate the ROM of the animal's trunk. A GA then finds smooth, plausible paths through the constrained hindlimb and forelimb space. Finally, an extension of the bipedal gait pipeline architecture maximizes reuse of the additional quadrupedal data. Constraints A quadrupedal gait can be represented as two independent bipedal gaits (i.e., fore and hind, each with duty factors and a contralateral phase), provided that additional constraints are satisfied. An animal's fore and hind limbs are connected by a trunk consisting of some number of vertebrae. Each vertebral joint has a ROM, so the trunk itself can be represented by a higher-level ROM that summarizes the movements of the individual vertebrae. The fore and hind gaits must be coordinated in such a way that they act as if they are connected by the trunk. The convention of representing quadrupedal locomotion with two bipedal gait systems is supported by Griffin, Main, and Farley (2004), who state that dog fore and hind quarters generally act like two independent bipeds. The trunk ROM can be exercised like any other ROM, allowing possible forelimb root element positions and orientations to be determined for each hindlimb LROM space 118 sample. For each hindlimb space sample, there are some number forelimb space samples that are reachable by the trunk. The forelimb and hindlimb LROM spaces can therefore be further pruned based on the trunk constraint; all hindlimb samples that cannot reach a single forelimb sample are removed, along with all forelimb samples that cannot be reached by any hindlimb samples. Figure 46 illustrates how the trunk constraint is applied to the fore and hind LROM spaces. Quadrupedal Trunk Constraint Forelimb Space Hindlimb Space z x Figure 46. Quadrupedal Trunk Constraint from dorsal view. 119 The forelimb and hindlimb gait components are related by a phase term called the ipsilateral phase. Like contralateral phase, the ipsilateral phase is a normalized term (on the range [0.0, 1.0]). The ipsilateral phase describes the relative elapsed stride time between the right hindlimb beginning its stance phase and the right forelimb beginning its stance phase. The two contralateral phases (fore and hind), the ipsilateral phase, and each limb's duty factor fully describe the quadrupedal duty vector. Figure 47 shows an example duty vector based on a 0.5 contralateral phase for both fore and hind limbs, a 0.55 ipsilateral phase, and 0.6 duty factors for all limbs. • Stance USwing • Stance U Swing o 0.2 0.4 0.6 0.8 1 Phase -----------~------------ Figure 47. Example quadrupedal duty vector. 120 The ipsilateral phase does not affect the trunk-constraint-based pruning process because discrete samples in the hindlimb space are compared to discrete samples in the forelimb space. When constructing a walking gait based on key locomotion events, however, the ipsilateral phase determines the relative delay between associated events with respect to the hindlimbs and forelimbs (e.g., hindlimb RD and forelimb RD). The algorithm for constructing quadrupedal gaits based on key locomotion events will be discussed in the next section. Reconstruction Forelimb and hindlimb animations can be generated in such a way that they obey the trunk constraint while achieving the same GA goals used for bipedal gaits (i.e., minimum body roll, pitch, and yaw, and changes in FDOF values; maximum lateral and vertical smoothness). The algorithm is straightforward with a constant ipsilateral phase of 0.0; associated fore and hind events occur at the same time, so the list ofpossible samples for the forelimb RD can be determined based only on the hindlimb RD sample (and likewise for the forelimb RLU with respect to the hindlimb RLU). Supporting an arbitrary ipsilateral phase complicates the algorithm. Given an ipsilateral phase ofp, the forelimb RD occurs at time p (the hindlimb RD always occurs at time 0.0). The complete hindlimb path can be determined by an RD and an RLU sample, so the hindlimb root element position and orientation at time p can be computed from the path. Therefore, the possible forelimb RD samples can be determined for a given ipsilateral phase, RD sample, and RLU sample (and likewise for 121 the forelimb RLU sample). The possible forelimb RD and RLU positions must be computed for each RD-RLU pair so that the GA will only consider forelimb samples that satisfy the trunk constraint. The process of finding satisfactory forelimb samples (within an error tolerance) is performed prior to the GA iterations to ensure that each RD-RLU pair is evaluated only once. There is one important corollary to the trunk-constraint satisfaction algorithm. The ipsilateral phase determines, in part, the z component (i.e., translation along the locomotion axis) of the hindlimb root element position at time p (along with the z component of the hindlimb RD sample position). The additional forward translation forces the selection of forelimb samples that are unnecessarily pushed towards the front of the fore LROM space. To compensate for this effect, the z component of the hindlimb root position at time p is set to the z component of the hindlimb RD sample position. Figure 48 illustrates the selection ofpossible forelimb RD samples based on the ipsilateral phase and an RD-RLU pair. 122 Quadrupedal Locomotion Events l-I -;-~.~ t;--; i-·;-:-~1~-r;t-'f i"+ ~_1 i H", W'l;,.f......."!lI!.. I.!!,!,FH~E~ RD.';Itj !r:l:flljll{lllii~ ... :: .:: ~ :: .; ::: Li in r; ;t±J~~i~i~;Adjusted Fore :Ii!:: ::;1j.j[fi Hi; jjli~~~,~ons z Figure 48. Forelimb RD selection based on a hindlimb RD-RLU pair. The computational speed of the possible-forelimb-sample selection algorithm benefits from the back data and slice data organization; the algorithm needs only to evaluate hindlimb RD-RLU pairs that are eligible for selection as pairs for a hindlimb gait. The back data and slice data organization therefore dramatically decreases the computational complexity of the selection algorithm (i.e., from O(n2) to O(n*m), where m is roughly the square root of n) and allows the GA candidate evaluation function to remain a constant-time operation. The resulting implementation is able to automatically 123 generate quadrupedal walking gaits in under three minutes (five hindlimb FDOFs, seven forelimb FDOFs, 1000 candidate population size, 10,000 GA iterations) on a consumer laptop (as of this printing). Figure 49 shows an Apatosaurus quadrupedal walking gait generated using these methods. Figure 49. Apatosaurus quadrupedal walking animation. The quadrupedal gait generation process involves a number of discrete operations, much like the bipedal gait generation process. Like the bipedal pipeline, the quadrupedal pipeline should also maximize reuse of computed data so that input variables can be changed for a pipeline stage without necessitating the reevaluation of earlier stages. The next section will cover the quadrupedal gait pipeline. 124 Pipeline The quadrupedal gait pipeline is similar to the bipedal gait pipeline, and utilizes the first two bipedal gait pipeline operations. The Quadrupedal Pipeline begins with three parallel sets of operations. Bipedal Explore Space and Organize Space operations are used to prepare the forelimb and hindlimb LROM spaces. In addition, an Explore Trunk Space operation is used to exercise the trunk ROMs and prepare the higher-level trunk ROM for the possible-forelimb-sample selection process. The Explore Trunk Space operation takes the trunk FDOFs as its only input. The Find Quad Path operation takes the forelimb and hindlimb LROM spaces and the trunk ROM as inputs. In addition, the Find Quad Path takes as input the standard GA parameters (i.e., crossover coefficient, mutation coefficient, candidate population size, number of GA iterations), the ipsilateral phase, and a constraint error tolerance for selecting possible forelimb samples. The Find Quad Path operation plots paths through the forelimb and hindlimb spaces while satisfying the trunk constraint. The Find Quad Path outputs two complete gait animations: one for the forelimbs and one for the hindlimbs. Finally, the Animate Path operation interpolates and visualizes the two input animations. The arbitrary ipsilateral phase causes the hindlimb and forelimb animations to loop at different times (i.e., with an ipsilateral phase ofp, the forelimb animation loops at time p while the hindlimb animation loops at time 1.0). The difference in looping times causes the forelimbs to return to their original position before the hindlimbs, so the 125 z component (i.e., translation along the locomotion axis) of the forelimb root element's position is adjusted to compensate. The fore and hind LROM spaces are based on discrete samples, so it is not possible to simultaneously animate the fore and hind limbs while maintaining contact with the ground and keeping the trunk perfectly intact. For this reason, the animal's trunk is representing by a self-adjusting, semi-translucent ribbon (see Figure 49). Figure 50 illustrates the quadrupedal gait pipeline. .Quadrupedal Gait Pipeline FDOFs ;i~;~:,I'!\C Angular Resolution Translational Resolution Duty Factor Constraint Error Tolerance Step Height altof Y;"Ci. Locomotion Axil; Boxes:' ,.-----....... 7' Find Quad Path Animation Time Figure 50. Quadrupedal gait pipeline. 126 The bipedal gait pipeline allows the computationally-efficient generation of quadrupedal walking gaits, even when changes to input parameters are necessary. Additional discrete operations refine walking gaits, visualize trackways, and allow the scaling ofmodel elements. The next few sections will present these operations. Gait Refinement LROMs are explored at a resolution ofbetween 4° and 6°. Gait animations resulting from the methods described in this chapter are not particularly sensitive to the LROM sampling resolution (see the sensitivity analysis in the next chapter), but the effective sampling resolution can be increased by refining gait animations. The sampling resolution is multiplicative across all FDOFs (i.e., doubling the sampling resolution of an LROM with 8 FDOFs causes the number ofLROM samples to increase by a factor of 21\8 = 256). However, the sampling resolution is additive if each FDOF is iteratively resampled without modifying the other FDOFs. Each FDOF is iteratively resampled at a higher resolution (i.e., typically 1°). Resampling the FDOF changes both the LROM and LROM space. A new gait animation is then created using the same GA fitness function that was used to create the original gait animation, but using the modified LROM space that represents each original animation keyframe with one highly-sampled FDOF. The refined gait animations vary little from their original counterparts in terms in terms of functional joint movements. They do, however, exhibit significantly-higher fitness values and are therefore generally smoother 127 in terms of body roll, pitch, yaw, and lateral/vertical error. Figure 51 shows a dog hindlimb gait before and after refinement. Figure 51. Dog hindlimb gait animation before and after refining. Gaits can be refined by iteratively resampling FDOFs the increase the resolution of the LROM spaces in certain locations found relevant to locomotion. It is often useful to visualize the positional relationships between generated trackway print locations, which are based on locomotion parameters such as the step length and step width. The next section will cover the visualization of generated trackways. 128 Trackway Visualization Trackways are generated by calculating the position of the manus/pes on the ground plane when the associated limb begins its stance phase. In this way, trackways are generated as a result of gaits; gaits are not generated based on trackway data as with Torkos and van de Panne (1998) and Henderson (2006). Manus prints are visualized as flattened spheres; pes prints are visualized as flattened cubes. Figure 52 shows an example generated Apatosaurus trackway. Figure 52. Example generated Apatosaurus trackway. Parameters such as step length and step width modify the constrained LROM space and therefore the generated walking gaits and trackways. Scaling elements of a model (i.e., the femur or crus) will also modify the LROM space, changing generated 129 walking gaits and trackways. The next section will cover the scaling of specific model elements. Scaling Model Elements Model elements can be arbitrarily scaled (i.e., either isotropically or anisotropically) by scaling the element's distal joint ROM. A ROM is scaled by multiplying its base translational components by the scale factor(s). The translational components of the ROM's constituent FDOFs are also multiplied by the scale factor(s). The ROM's rotational components are not affected by the scaling process. To visualize the change in element scale, the element's shape scale is multiplied by the scale factor(s). Models Five skeletal models are currently available for analysis: a generic dog, a generic reptile, and three dinosaurs. The available dinosaurs are an Apatosaurus, a Triceratops, and a Tyrannosaurus. Each model consists ofjoint ROMs and bone shapes for the animal's hindlimbs, forelimbs, and trunk. In this section, the joints, LROM spaces, and trunk ROMs (for quadrupeds only) will be presented for each model. 130 Dog The generic dog model proportions are based primarily on the standard German Shepherd (Shaw, 2007a, 2007b). Table 30 (see Appendix A) lists the six geometric OOFs for each of the dog model's FOOFs. The dog hindlimb utilizes six FOOFs at four joints: hip flexion/extension, abduction/adduction, and medial/lateral rotation; knee flexion/extension; ankle flexion/extension; pes flexion/extension. Figure 53 shows the dog hindlimb joints. Figure 53. Dog hindlimb joints. The dog forelimb has seven FOOFs at five joints: scapulothorax rotation; shoulder flexion/extension, abduction/adduction, and medial/lateral rotation; elbow 131 flexion/extension, wrist flexion/extension; manus flexion/extension. Figure 54 shows the dog forelimb joints. ~-) I r n.. Ii. l!!l [ [l ~ - = .­-­ - .. -I.J I l. l~CI [....1 Figure 54. Dog forelimb joints. The dog hindlimb LROM was sampled at 5° resolution creating 308,000 samples (4.41 MB, 24 bytes per sample). Figure 55 shows the dog hindlimb LROM space. The hindlimb LROM space is highly parasagittal (i.e., all LROM space root locations lie within, or close to, the animal's sagittal plane). The parasagitta1 LROM space is a result of the pes, ankle, knee, and hip flexion/extension FDOFs having instantaneous axes of rotation that are nearly coincident. Exercising any of these FDOFs causes the root to move and rotate along an arc (i.e., the pes FDOF having the largest radius because of the distance between the pes joint and the root, similarly the hip FDOF having the smallest radius). These flexion/extension FDOFs are therefore considered redundant. -- 132 \"... "'.•'.' , :d:lI,'''r»'', ., .... '.. !!!!!---;;;;;; -j-==~. ~ ~ . 11 11 11 II I• .­ Ii;r/! 1/)• ~ I.~ ~. __===_I 1- _. _ ..'-1=== ---~-­~ - - ------r-----I -I;;;;;;;;;;;;;;~-l. I U Figure 55. Dog hindlimb LROM space. The constrained dog hindlimb LROM space is based on a step length of 0.48 times the hip height. The space contains 10,795 samples. Figure 56 shows the constrained dog hindlimb LROM space. 11 I t r' J II .f. _~1I - ;:!J 1l1;2 IJ; -l ~ ~~ n Figure 56. Constrained dog hindlimb LROM space. 133 The dog forelimb LROM was sampled at 5° resolution creating 3,326,400 samples (76.1 MB, 24 bytes per sample). Figure 57 shows the dog forelimb LROM space. Like the hindlimb LROM space, the forelimb LROM space is highly parasagittal. Figure 57. Dog forelimb LROM space. The constrained dog forelimb LROM space is based on a step length 0.48 times the hip height. The space contains 4,122 samples. Figure 58 shows the constrained dog forelimb LROM space. 134 , f.J. .'. :-~"lil~ D" :!:II....... />. Il ((( '~(11'1 "'7­n ~1 IU\.. \lor­ \­ Figure 58. Constrained dog forelimb LROM space. The dog trunk ROM consists of 19 vertebral joints. The trunk ROM represents 21 mediolateral samples and 21 dorsoventral for a total of 44 1 samples. Figure 59 shows the dog trunl< ROM space. I. J ;r'­ ,-:' . - ,. I , ! J 1 •, f . <"'"' '" - Figure 59. Dog trunk ROM space. 135 Reptile The generic reptile model is based primarily on the Komodo dragon (Fotosearch, 2005). Table 31 (see Appendix B) lists the six geometric DOFs for each of the reptile model's FDOFs. The reptile hindlimb has eight FDOFs at five joints: hip flexion/extension, abduction/adduction, and inner/outer rotation; knee flexion/extension; crus pronation/supination; ankle flexion/extension; pes flexion/extension and medial/lateral rotation. Figure 60 shows the reptile hindlimb joints. Figure 60. Reptile hindlimb joints. The reptile forelimb uses eight FDOFs at five joints: shoulder flexion/extension, abduction/adduction, and inner/outer rotation; elbow flexion/extension, antibrachium 136 pronation/supination; wrist flexion/extension; manus flexion/extension and medial/lateral rotation. Figure 61 shows the reptile forelimb joints. Figure 61. Reptile forelimb joints. The reptile hindlimb LROM was sampled at 5.5 0 resolution creating 7,076,160 samples (161 MB, 24 bytes per sample). Figure 62 shows the dog hindlimb LROM space. The space is quite robust in pali because of the knee axis, which is almost parallel with the sagittal plane due to the reptile's sprawling stance (i.e., contrary to mammals, which have knee flexion/extension axes that are nearly perpendicular to the sagittal plane). The reptile also utilizes medial/lateral rotation at the foot and pronation/supination at the crus to move the root along arcs that are not parasagittal. 137 Figure 62. Reptile hindlimb LROM space. The constrained reptile hindlimb LROM space is based on a step length 2.2 times the hip height. The space contains 136,108 samples. Figure 63 shows the constrained reptile hindlimb LROM space. Figure 63. Constrained reptile hindlimb LROM space. 138 The reptile forelimb LROM was sampled at 5.5 0 resolution creating 2,857,680 samples (65.4 MB, 24 bytes per sample). Figure 64 shows the reptile forelimb LROM space. Like the hindlimb LROM space, the forelimb space is quite robust. Similar to the hindlimb, the robust nature of the space is largely due to the medial/lateral rotation at the manus, pronation/supination at the antibrachium, and flexion/extension at the knee that move the root along non-parasagittal arcs. Figure 64. Reptile forelimb LROM space. The constrained reptile forelimb LROM space is based on a step length 2.2 times the hip height. The space contains 19,431 samples. Figure 65 shows the constrained reptile forelimb LROM space. 139 Figure 65. Constrained reptile forelimb LROM space. The reptile tnmk ROM consists of six vertebral joints. The trunl< ROM represents 41 mediolateral samples and 41 dorsoventral for a total of 1681 samples. Figure 66 shows the reptile trunk ROM space. Figure 66. Reptile trunk ROM space. 140 Apatosaurus Apatosaurus was a sauropod dinosaur that lived approximately 140 million years ago during the Jurassic period. Apatosaurus was up to 23 meters long. The specific bone dimensions and morphologies are based on the Carnegie Mellon specimen CM 3018 (Stevens,2007a). Table 32 (see Appendix C) lists the six geometric OOFs for each of the Apatosaurus model's FOOFs. The Apatosaurus hindlimb utilizes five FOOFs at three joints: hip flexion/extension, abduction/adduction, and medial/lateral rotation; knee flexion/extension; ankle flexion/extension. Figure 67 shows the Apatosaurus hindlimb joints. Figure 67. Apatosaurus hindlimb joints. 141 The Apatosaurus forelimb utilizes seven FDOFs at fOUf joints: scapulothorax rotation and elevation; shoulder flexion/extension, abduction/adduction, and medial/lateral rotation; elbow flexion/extension, wrist flexion/extension. Figure 68 shows the Apatosaurus forelimb joints. Figure 68. Apatosaurus forelimb joints. The Apatosaurus hindlimb LROM was sampled at 4° resolution creating 87,975 samples (2.0 1MB, 24 bytes per sample). Figure 69 shows the Apatosaurus hindlimb LROM space. The hindlimb LROM space is highly parasagittal due to the nearly­ coincident ankle, knee, and hip flexion/extension FDOFs, similar to the dog hindlimb space. 142 Figure 69. Apatosaunls hindlimb LROM space. The constrained Apatosaurus hindlimb LROM space is based on a step length 0.34 times the hip height. The space contains 3,628 samples. Figure 70 shows the constrained Apatosaurus hindlimb LROM space. Figure 70. Constrained Apatosaurus hindlimb LROM space. 143 The Apatosaurus forelimb LROM was sampled at 4° resolution (5 cm resolution for scapulothorax elevation) creating 5,221,125 samples (119 MB, 24 bytes per sample). Figure 71 shows the Apatosaurus forelimb LROM space. The forelimb LROM space is considerably more robust than the hindlimb space, due to non-coincident wrist, elbow, and shoulder flexion/extension, and scapulothorax rotation FDOFaxes. Combinations of these FDOF values allow the root to both move along non-parasagittal arcs and change elevation. Figure 7/. Apatosaurus forelimb LROM space. The constrained Apatosaurus forelimb LROM space is based on a step length 0.34 times the hip height. The space contains 406,377 samples. Figure 72 shows the constrained Apatosaurus forelimb LROM space. 144 Figure 72. Constrained Apatosaurus forelimb LROM space. The Apatosaurus trunk ROM consists of nine vertebral joints. The trunk ROM represents 21 mediolateral samples and 21 dorsoventral for a total of 441 samples. Figure 73 shows the Apatosaurus tnmk ROM space. Figure 73. Apatosaurus trunk ROM space. 145 Triceratops Triceratops was a ceratopsid dinosaur that lived during the Late Cretaceous Period, approximately 68 to 65 million years ago. Triceratops was up to 9 meters in length. Bone dimensions and morphologies are based on the Black Hills Institute of Geological Research Triceratops horridus specimen TCM 2001.93.1, "Kelsey" (Stevens, 2007b). Table 33 (see Appendix 0) lists the six geometric OOFs for each of the Triceratops model's FOOFs. The Triceratops hindlimb utilizes five FOOFs at three joints: hip flexion/extension, abduction/adduction, and medial/lateral rotation; knee flexion/extension; ankle flexion/extension. Figure 74 shows the Triceratops hindlimb joints. Figure 74. Triceratops hindlimb joints. 146 The Triceratops forelimb utilizes seven FDOFs at four joints: scapulothorax rotation and elevation; shoulder flexion/extension, abduction/adduction, and medial/lateral rotation; elbow flexion/extension, wrist flexion/extension. Figure 75 shows the Triceratops forelimb joints. Figure 75. Triceratops forelimb joints. The Triceratops hindlimb LROM was sampled at 4° resolution creating 350,784 samples (8.02 MB, 24 bytes per sample). Figure 76 shows the Triceratops hindlimb LROM space. The hindlimb LROM space is nearly parasagittal, which is surprising considering that the knee and hip flexion/extension FDOFs are not coincident. The ankle and knee FDOFaxes are nearly coincident, however, allowing combinations of those FDOF values to move the root along a parasagittal arc. The distance between the hip 147 joint and root is small, so the hip FDOFs are capable of a large amount of root orientation change but little root position change. Figure 76. Triceratops hindlimb LROM space. The constrained Triceratops hindlimb LROM space is based on a step length 0.34 times the hip height. The space contains 6,086 samples. Figure 77 shows the constrained Triceratops hindlimb LROM space. 148 Figure 77. Constrained Triceratops hindlimb LROM space. The Triceratops forelimb LROM was sampled at 4° resolution (5 cm resolution for scapulothorax elevation) creating 1,272,960 samples (29.1 MB, 24 bytes per sample). Figure 78 shows the Triceratops forelimb LROM space. The non-coincident wrist, elbow, and shoulder flexion/extension, and scapulothorax rotation FDOFaxes produce a robust forelimb LROM space, similar to that of the Apatosaurus forelimb space. 149 Figure 78. Triceratops forelimb LROM space. The constrained Triceratops forelimb LROM space is based on a step length 0.34 times the hip height. The space contains 43,580 samples. Figure 79 shows the constrained Triceratops forelimb LROM space. Figure 79. Constrained Triceratops forelimb LROM space. 150 The Triceratops trunk ROM consists of 15 vertebral joints. The trunk ROM represents 21 mediolateral samples and 21 dorsoventral for a total of 441 samples. Figure 80 shows the Triceratops trunk ROM space. Figure 80. Triceratops trunk ROM space. Tyrannosaurus Tyrannosaurus was a theropod dinosaur that lived during the Late Cretaceous Period, approximately 68 to 65.5 million years ago. Tyrannosaurus was up to 13 meters in length. Bone dimensions and morphologies are based on the Black Hills Institute of Geological Research Tyrannosaurus specimen BHI-3033, "Stan" (Stevens, 2007c). 151 Table 34 (see Appendix E) lists the six geometric DOFs for each of the Tyrannosaurus model's FDOFs. The Tyrannosaurus hindlimb utilizes six FDOFs at four joints: hip flexion/extension, abduction/adduction, and medial/lateral rotation; knee flexion/extension; ankle flexion/extension; phalangeal flexion/extension. Figure 81 shows the Tyrannosaurus hindlimb joints. Figure 8/. Tyrannosaurus hindlimb joints. The Tyrannosaurus hindlimb LROM was sampled at 4° resolution creating 2,882,880 samples (65.9 MB, 24 bytes per sample). Figure 82 shows the Tyrannosaurus hindlimb LROM space. The space is highly parasagittal, which is not surprising considering the large number of redundant FDOFs; the phalangeal, ankle, knee, and hip flexion/extension FDOFs all have near-coincident axes. The large number of redundant 152 FDOFs creates an extremely large number ofLROM space samples (i.e., 2,882,880 samples, compared to 80,640 samples in the comparable dog hindlimb LROM space). A GA may have trouble selecting appropriate limb configurations with so many combinations of phalangeal, ankle, and knee FDOF values allowing similar root orientations and positions. Figure 82. Tyrannosaurus hindlimb LROM space. The constrained Tyrannosaurus hindlimb LROM space is based on a step length 0.98 times the hip height. The space contains 24,346 samples. Figure 83 shows the constrained Tyrannosaurus hindlimb LROM space. 153 Figure 83. Constrained Tyrannosaurus hindlimb LROM space. Summary The methods presented in this chapter allow the exploration and evaluation of a limb's summary range of motion. LROMs are created by evaluating all combinations of a limb's FDOFs at some angular resolution. LROMs are subsequently organized into LROM spaces for visualization and experimentation. LROM spaces provide an intuitive map of the positions and orientations reachable by the root of the limb system which is particularly useful for observing the behaviors of limb joints during locomotion. Bipedal constraints (i.e., dual support and bilateral) provide substantial pruning of LROM spaces, removing configurations with positions and orientations that are not possible during locomotion. The GA selects candidates from the LROM space corresponding to the beginning and ending of the stance phase. Compared to mid stance, 154 there are relatively-few ways that a limb can reach forward and back (i.e., given an adequately- long step length), so joint functionality is largely unambiguous. Limb movements are dependent on the limb's FDOFs, so limb movements and joint functionality can be analyzed in terms of the contributions made by each FDOF during locomotion. The GA utilizes a candidate representation which guarantees that all possible solutions at least cause the limbs to propel the root position forward by a specified step length. Therefore, the GA need only be concerned with finding a solution that is optimally smooth in terms of the fitness function, allowing fast convergence. The fitness function discourages body pitching, yawing, and rolling, as well as lateral swaying, vertical bobbing, and unnecessary angular excursions at the joints. A pipeline architecture connects the discrete operations necessary to automatically generate walking gaits, and allows maximum reuse of data between operations. Appendix H demonstrates the process of selecting and evaluating a bipedal candidate gait. Quadrupedal walking gaits can be automatically generated by utilizing two parallel bipedal gaits connected by a trunk region. Exercising the trunk's ROM allows further pruning of the fore and hind LROM spaces to remove configurations which cannot be connected by the trunk. Similar to the bipedal candidate representation, the quadrupedal candidate representation guarantees that all possible solutions at least propel the root position forward by a specified step length and ipsilateral phase. Again, a pipeline architecture connects the discrete quadrupedal operations, allowing reuse of data computed at earlier stages. -- - -_._--------- 155 Finally, five models were presented: two extant, three extinct; four quadrupedal, one bipedal. Resulting LROM spaces, both unconstrained and constrained, were presented along with visualizations of the trunk ROMs (for the quadrupeds only). In the next chapter, sensitivity analyses will be presented that use these models to determine the genetic parameters used by the GAs and for determining the impact of the LROM-space­ generation parameters on solution fitness. The models will also be evaluated qualitatively with respect to functional joint behavior during locomotion, and finally evaluated quantitatively to test specific hypotheses about FDOF behaviors. 156 CHAPTER IV RESULTS AND ANALYSIS In this chapter, data will be presented from sensitivity analyses of the parameters associated with the GAGA process and from studies carried out using GAGA methods. First, data will be presented related to the selection ofthe GA genetic parameters and parent selection method. Next, a sensitivity analysis will explore the effect of the parameters used to create and organize LROM spaces. Next, a qualitative analysis will compare walking gaits generated with GAGA to analogous real-world gaits. Finally, specific quantitative studies will test gait hypotheses using GAGA methods. Genetic Parameters The following sections provide the results of a sensitivity analysis for the genetic parameters used by the GA. The sensitivity analysis provides a means for tuning the GA and verifies that the chosen genetic parameters values are appropriate for the solution space. All test runs were based on the generation ofApatosaurus quadrupedal walking gaits using 39-bit binary candidates (i.e., 10 bits representing an index into the back data, 157 7 bits representing an index into the slice data, and two II-bit integers representing indices into the forelimb space based on the previous two hindlimb indices). Unless otherwise noted, all runs consist of 10,000 GA iterations with a candidate population size of 1000. All GA runs were executed ten times so that an accurate mean and standard deviation could be established. Parent Selection After each GA iteration (i.e., following crossover and mutation), parents are selected to populate the candidate population for the next GA iteration. To select parents, the GA compares each candidate solution with another randomly-selected candidate solution in the population. The candidate solution with the higher fitness value then has a fixed change ofbeing selected. This selection method is known as Tournament Selection. Tournament Selection has an advantage over other selection methods (e.g., Rank Selection or Fitness Proportional Selection) in that it does not require sorting of the population, therefore decreasing computation time. Table 1 shows the effect ofvarying the Tournament Selection higher-fitness-selection coefficient (0.5 crossover coefficient, 0.5 relative mutation coefficient). 158 Table 1. Effect o/varying Toumament Selection coefficient Tournament Selection coefficient Fitness (xlOI\3) 0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1:0 M 5.73 6.75 6.90 7.23 7.66 8.08 8.57 8.68 8.64 8.71 8.68 SD 0.15 0.08 0.20 0.28 0.32 0.26 0.16 0.19 0.24 0.37 0.32 Tournament Selection performed best with a selection coefficient between 0.6 and 1.0. A Tournament Selection coefficient of 0.9 was used for actual GA runs and for the remaining sensitivity analysis runs (see following sections). Always choosing the lower- fitness candidate (i.e., coefficient of 0.0) provides a fitness of 5.73 ± 0.15 (x 10-3), providing a good estimate of the worst-case solutions. Figure 84 shows a visual representation of Table 1. 159 10.0 9.5 -----------~--.-------------- ::~ ---.---.-.---------------.---!----~=t=_~ ~:~ ----.-- I-----t=!---------------------­ 7.0 ~ -----------­ ::~ J • ~~__ ~_--_~~~.~~__ __-_.--_-~_-- 5.0 h.---.----.--.---.-----rl------,----.---.---.-,-----, 0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 Tournament Selection coefficient Figure 84. Effect of varying Tournament Selection coefficient. Crossover Coefficient During each GA iteration, each candidate solution has a chance of being mated with another randomly-selected candidate solution based on the crossover coefficient. Candidates are mated by selecting a single crossover index; the first candidate receives the second candidate's genetic information up to a randomly-selected crossover index while the second candidate receives the first candidate's genetic information after the crossover index. Table 2 shows the effect of varying crossover coefficient in the absence of mutation. 160 Table 2. Effect of varying crossover coefficient with no mutation Crossover coefficient Fitness (x1Q/'3) 0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 M 6.13 7.79 8.26 8.59 8.52 8.77 8.69 8.71 8.90 8.83 8.71 SD 0.24 0.66 0.52 0.42 0.41 0.36 0.28 0.36 0.41 0.29 0.28 Without mutation, the GA depends on crossover to explore the space. Not surprisingly, the GA performed poorly with a crossover coefficient below 0.5. 0.8 is henceforth considered a high-performance crossover coefficient for the GA. Figure 85 shows the results of Table 2. 10.0 9.5 m :~ ~--~=t-+-t lrtrrc: o rl j~)( 7.5 ---.--.------.----------..-.---.---..-~-------- -VI (Ll '" 7.0 I------~~~~~~-----.~~-c .~ ..... 6.5 -~.-------.-----.---..--.-.. 6.0 -t--'T-~~----~~~-.-------- 5.5 ------------~-.-.-.--.--------- --------.­ 5.0 +-~-,---.--,-'--,_---r----,---,---,----,­ 0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 Crossover coefficient ---_.__ . __.._.~._-~~._------------_...._------------------------­ Figure 85. Effect of varying crossover coefficient with no mutation. 161 With mutation enabled, a tradeoff must be made between the crossover coefficient and the mutation coefficient; a great amount of combined mating and mutation will perturb too many high-fitness candidates and hinder the 'success of the GA. Table 3 shows the effect of varying crossover coefficient with a high-performance relative mutation coefficient of 0.5 (see next section). Table3. Effect ofvarying crossover coefficient with fixed mutation Crossover coefficient Fitness (xlO/\3) 0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 M 8.97 9.02 8.96 8.96 8.79 8.74 8.63 8.66 8.53 8.57 8.63 SD 0.35 0.41 0.33 0.35 0.37 0.32 0.27 0.31 0.06 0.11 0.21 As predicted, a high crossover coefficient hindered GA convergence performance when using a significant amount of mutation. Figure 86 shows a visual representation of Table 3. 162 10.0 -I 9.5 ----;------­ 9.0 +!---;I.,----->lk----->k-------,A--+-­ 8.5-I-+---+­~ o ... 8.0 x -VI 7.5 -----­ ------­ VI QI c: 7.0 ..~ .... 6.5 - 6.0 5.5 +---­ 5.0 0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 Crossover coefficient ------------------ ----------------~-- Figure 86. Effect ofvarying crossover coefficient with fixed mutation. Mutation Coefficient During each GA iteration, every bit in the solution space has a chance of being flipped, thus mutating some of the candidate solutions. The mutation coefficient is scaled by the inverse of the candidate size so that a relative mutation coefficient of 1.0 implies that one bit per candidate will be flipped on average. Table 4 shows the effect of varying the relative mutation coefficient in the absence of crossover. 163 Table 4. Effect ofvarying relative mutation coefficient with no crossover Relative mutation coefficient Fitness (xlQ!'3) 1/32 1/16 1/8 1/4 1/2 1 2 4 8 16 32 M 8.05 7.89 8.39 8.89 9.16 8.75 8.66 8.48 8.43 8.25 8.34 SD 0.63 0.58 0.58 0.52 0.35 0.20 0.14 0.25 0.35 0.27 0.38 The GA benefited most from a relative mutation coefficient of 0.5. Coefficients below 0.5 did not perturb the solution space enough to generate high-fitness candidates. Coefficients above 0.5 perturbed the space so much that too many high-fitness candidates were destroyed, impeding GA convergence performance. Figure 87 shows a visual representation of Table 4. .__._--_.._.._._._.._-----------, 1~:~ +---------------.--.-.-1- -..-.------.- - ..-. . 9.0 +-------J~T__• - 85 --f--l-----·-··-----.-·····-t-----·tI± <: o .... )( ­ M ~.~- -i====-'.--..-.---.. -.----.~=.---- ..-­II> (II '" c 7.0 .'1: .... 6.5 - ------.--------. ---_.~---_._.. _._-_._--­ --------------_._----~-_._._--6.0 +--- _.._--------_._.. _._-_.._._--_.5.5 5.0 +---'---"---'-'-'---,--,--,---,.---r 1/32 1/16 1/8 1/4 1/2 1 2 4 8 16 32 Relative mutation coefficient _._._-_..__._--------------_._---_. Figure 87. Effect of varying relative mutation coefficient with no crossover. 164 Table 5 shows the effect of varying relative mutation coefficient with a high- performance fixed crossover coefficient of 0.8 (see previous section). Table 5. Effect ofvarying relative mutation coefficient with fixed crossover Fitness (xl 0""3) M SD 1/32 8.66 0.32 1/16 8.64 0.31 1/8 8.67 0.34 Relative mutation coefficient 1/4 1/2 1 2 8.55 8.64 8.66 8.60 0.16 0.20 0.09 0.14 4 8.44 0.23 8 8.35 0.21 16 8.16 0.25 32 8.16 0.31 Similar to varying crossover coefficient with a high-performance relative mutation coefficient, higher relative mutation coefficients hindered GA convergence performance when a high-performance crossover coefficient was used. GA convergence performance was best when using a high performance relative mutation coefficient with a modest crossover coefficient, so a relative crossover coefficient of 0.5 was used with a crossover coefficient of 0.1 for actual GA runs. Figure 88 shows Table 5 in graph form. ------------------------------------------- ------------------ ------- 165 9.5 8.5 9.0 -+-t-=G! m 8.0 +---­ < 0 ...t ---------------------------­7.5 ~ III III e---­ C1J 7.0 l: .t:: u.. 6.5 f----­ 6.0 5.5 5.0 1/32 1/16 1/8 1/4 1/2 1 2 4 8 16 32 Relative mutation coefficient Figure 88. Effect of varying relative mutation coefficient with fixed crossover. Candidate Population Size The candidate population size determines the amount of initial randomness in the solution space; larger populations have a greater chance of generating initial candidates with high fitness. Larger populations also allow a greater amount of genetic material to be transferred between GA iterations, which provides more genetic diversity for mating and mutation. Table 6 shows the effect ofvarying candidate population size (0.1 crossover coefficient, 0.5 relative mutation coefficient). The GA was limited to 100 runs to exaggerate the effect of limiting population size. ----------- --- 166 Table 6. Effect ofvarying candidate population size Candidate population size Fitness (xlOI\3) 10 100 200 300 400 500 600 700 800 900 1000 M 6.80 8.39 8.35 8.54 8.61 8.71 8.90 8.79 8.80 8.91 8.96 SD 0.62 0.63 0.61 0.50 0.37 0.39 0.32 0.27 0.35 0.36 0.35 Maximum fitness grew almost monotonically with candidate population size, indicating that larger populations do improve GA convergence performance. The standard deviations also decreased significantly as population size increased, suggesting that larger populations allow more consistency in the candidate solutions found. Figure 89 shows a visual representation of Table 6. 10.0 l===----­ HF=.~~ r J- ~ +-. F 8.0 1t--~ - ­ ----­ 5.0 ---r­ -,------" --,-----, 10 100 200 300 400 500 600 700 800 900 1000 Candidate population size Figure 89. Effect of varying candidate population size. 167 Convergence Comparison The GA was run against a simulated Hill Climbing algorithm to determine the relative convergence performance of the GA. Hill Climbing was simulated by running the GA with no crossover, a relative mutation coefficient of 1.0, and Best Selection to select population parents (Le., the most-fit candidate in each population is used to populate the entire next population). In this way, the simulated Hill Climbing algorithm flipped one bit per candidate on average. The simulated Hill Climbing algorithm used a population size of39 (i.e., the same size as the solution candidates) so that each genotype bit is flipped once per iteration on average. The GA was run with a crossover coefficient of 0.1 and a relative mutation coefficient ofO.5 (see previous sections). The GA used a population size of39 to be consistent with the simulated Hill Climbing algorithm (at the cost of some GA convergence performance). With equal candidate solution and population sizes, the two algorithms should be approximately equal in terms of computational cost. Table 7 shows the results of the GA/Hill Climbing comparison. 168 Table 7. Comparison ofGAlHill Climbing convergence performance Number of iterations Fitness (xlO"'3) 10 100 200 300 400 500 600 700 800 900 1000 GA M 6.17 7.53 7.81 7.94 7.99 8.10 8.11 8.11 8.14 8.23 8.23 SD 0.39 0.49 0.48 0.51 0.53 0.59 0.60 0.60 0.64 0.58 0.57 Hill Climbing M 6.59 7.16 7.32 7.42 7.43 7.44 7.44 7.45 7.46 7.47 7.47 SD 0.53 0.58 0.54 0.65 0.65 0.67 0.67 0.68 0.68 0.68 0.68 Initially, the simulated Hill Climbing algorithm outperformed the GA. This is likely a result of the Hill Climbing algorithm's more aggressive rewarding of fit candidates; the GA sometimes selects less-fit candidates to maintain diversity in the candidate population. The GA outperformed the simulated Hill Climbing algorithm at 100 iterations and beyond. After 300 iterations, the simulated Hill Climbing algorithm improved very little in fitness because it likely converged on a local maximum. The GA continued to improve until at least 900 iterations. Figure 90 shows the results from Table 7 in graph form. 169 -GA --Hill climbing 1O.0 ~:~ E~----=-=-----_.------==--=--==--====-~-== 8.5 +---------------------------­ 8.0 +---.----=~---====~~~===- 7.5 £-~::::;;::;;;;;;;=iiiiiii='...........................................----~- 7.0 "" ---­ 6.5 _ / . . .. . ._.._. .__.6.0 5.5 ----_._--------------_._---------._-_ .._---------­ 5.0 +----,---,---,-----,----,----,-------,----,-----,-----,--,-----, 10 100 200 300 400 500 600 700 800 900 1000 Number of iterations -------_._-------------------------' Figure 90. Comparison of GA/Hill Climbing convergence performance. The data presented in this section demonstrates the process of tuning the GA for maximum convergence. With the GA tuned, the sensitivity of input parameters on GA performance must next be evaluated. The next section will present data related to the various input parameters for exploring and organizing LROM spaces and for finding smooth bipedal and quadrupedal walking gait paths. Sensitivity Analysis The LROM space representation allows the search for "optimal" walking gait paths through the space, but how sensitive are the generated gaits to variations in the parameters used to generate the space? In this section, the sensitivity of space 170 exploration and organization parameters will be analyzed. The effects of iteratively refining spaces will also be addressed. Finally, the aggregate fitness function coefficients were varied to determine their qualitative effects on the generated walking gaits. All data in this section is based on the Apatosaurus forelimb, which utilizes seven FDOFs with a wide variety of functionality. Data was collected across ten GA runs to determine a mean and standard deviation for each data point. Space Exploration Each LROM is sampled at a specified angular resolution. The exact resolution is typically selected such that a large number of samples are generated, but not so many that computer memory and execution time become limiting factors. The number of samples grows exponentially with the sampling resolution (i.e., double the sampling resolution increases the size ofthe space by a factor of2/'FDOF count). The exact number of samples depends on the angular sampling resolution and the sum angular excursion of a limb's FDOFs. Figure 91 shows how the number of samples and the number of constrained samples (i.e., using the dual support and bilateral symmetry constrained) relates to sampling resolution. 171 -Total --Constrained 6,000,000 4Il 5,000,000 (II C. 4,000,000E 1tI 4Il 1; 3,000,000 .. (II i.JJ E 2,000,000 :::J j Z 1,000,000 I !0 -r-­ 6 5.75 5.5 5.25 5 4.75 4.5 4.25 4 Exploration sampling resolution to) '--------------------~-~ Figure 91. Apatosaurus forelimb sample counts. The total number ofLROM samples grows exponentially, as expected. The number of constrained samples grows less quickly, but still increases from 7,719 samples at a 6° angular sampling resolution to 406,377 samples at a 4° sampling resolution. Fitness values were collected for sampling resolutions between 4° and 6° determine the effect of the angular sampling resolution on generated walking gait fitness. Table 8 shows the effect of varying angular sampling resolution. 172 Table 8. Effect ofvarying sampling resolution on walk fitness Exploration sampling resolution n Fitness (xlOA 3) 6 5.75 5.5 5.25 5 4.75 4.5 4.25 4 M 7.22 8.99 9.18 9.64 8.45 8.61 9.00 9.79 10.39 SD 0.84 0.00 0.34 1.08 1.03 1.13 0.89 1.64 1.04 The GA finds paths through the constrained LROM spaces, so it makes sense to evaluate fitness relative to the size of the constrained spaces. Table 8 shows that there is little variation in fitness based on sampling resolution, while Figure 91 shows that the size of the constrained spaces grows quickly as sampling resolution decreases (i.e., increasing the size of the space). This contrast indicates that the fitness of generated walking gaits is not dependent on the number of samples in the LROM space. Figure 92 shows a graphical representation of Table 8. ------------------------------------- 173 12.0 11.0 n 10.0 J<: .... 9.0 ..0 -+ ~ III III (II 8.0 s:: i M t=i t J~ .~ 1.1.. I7.0 6.0 J 5.0 ~--r-----,--,------,--,------,---,-------,-----, 6 5.75 5.5 5.25 5 4.75 4.5 4.25 4 Exploration sampling resolution (O) Figure 92. Effect of varying sampling resolution on walk fitness. Qualitatively, each FDOF accomplishes some functional purpose during locomotion. The functional purposes of the FDOFs must not be dependent on the space sampling or organization parameters, otherwise FDOF functionality could not be determined using the LROM space representation. Figure 93 shows stance frames from Apatosaurus forelimb walking gaits generated from LROM spaces sampled at 4° (i.e., 7,719 samples) and 6° (i.e., 406,377 samples) resolutions. The figure shows minor differences in some joint angles, but that the seven FDOFs accomplish similar goals in terms of body pitch, yaw, roll, vertical displacement, and forward travel. 174 Figure 93. Comparison of low (top) and high (bottom) resolution sampling. The angular sampling resolution of the sampling process does not have a significant effect on walking gait fitness. The sampling resolution also does not have a significant effect on the functional purpose of the animal's joints during locomotion. The next section will present data collected on the effect of varying space organization parameters on gait fitness. 175 Space Organization The samples of a constrained LROM space are sorted into a number of 3D boxes. The number of boxes along the direction of travel is specified and the number ofboxes along the other two axes (i.e., lateral and vertical) is computed such that the boxes are geometric cubes. Larger box counts improve the computational efficiency of the GA because each box contains relatively-few samples so fewer evaluations are necessary. However, very large box counts can create a space that is too sparsely populated for the GA to find high-fitness walking gaits. Fitness values were collected for spaces created with box counts between 30 and 60 to determine the effect of box count on gait fitness. Table 9 shows the effect of box count on walking gait fitness. Table 9. Effect ofvarying LROM space box count on walk fitness LROM space boxes along direction of travel Fitness (xlO"'3) 30 35 40 45 50 55 60 M 10.13 8.74 10.16 9.47 9.71 8.94 8.87 SD 1.34 1.02 1.61 0.69 1.45 1.23 0.85 Similar to the effect of exploration sampling resolution, the box count has little effect on the fitness of generated walks. The fitness data does show a trend towards lower fitness values with larger box counts, which is to be expected considering that 176 relatively-fewer samples are available to be evaluated by the GA. Figure 94 shows a graphical representation of the data from Table 9. 13.0 12.0 11.0 rtl <:) 10.0 - ..... c:: + ~~ ~ 9.0III ·Il ..~ III QI C 8.0 -1---------- ------------~-~---­±= .'!:: u. 7.0 6.0 5.0 30 35 40 45 50 55 60 LROM Space boxes along direction of travel ._~----------~ ._-~---------~-~~------- Figure 94. Effect of varying box count on walk fitness. Like sampling resolution, organization box count must not have an effect on the functional purposes of the FDOFs. Figure 95 shows stance frames from Apatosaurus forelimb walking gaits generated from LROM spaces organized with box counts of 30 and 60. Again, the figure shows small differences in joint angles and that the FDOFs accomplish the same high-level locomotion goals between the two walking gaits; analogous FDOFs are utilized for the same locomotion purposes by both gaits. 177 Figure 95. Comparison of low (top) and high (bottom) box counts. The LROM space box count does not have a significant effect on walking gait fitness. The box count also does not have a significant effect on the functional purpose of the animal's joints during locomotion. In the next section, data will be presented related to the iterative refinement ofFDOFs. The refinement process adds resolution to LROM spaces at locations found to be related to locomotion. --- ----------------------- 178 Space Refinement After generating a walking gait from an LROM space created with some angular sampling resolution and box count, the space can be iteratively refined to populate the LROM space with more samples in locations found to be related to locomotion. A new LROM space is created for a target FDOF using the existing walking gait keyframes to specify all other FDOF values. The target FDOF is then sampled at a higher resolution, a new walking gait is generated, and the new gait animation is used to resample the next FDOF. Table 10 shows a comparison of candidate fitness values before and after iterative refinement at a 10 angular resolution. Table 10. Comparison oforiginal and refined walk fitness Exploration sampling resolution CO) Fitness (xlOJ'3) 6 5.75 5.5 5.25 5 4.75 4.5 4.25 4 Original M 7.22 8.99 9.18 9.64 8.45 8.61 9.00 9.79 10.39 SD 0.84 0.00 0.34 1.08 1.03 1.13 0.89 1.64 1.04 Refmed M 130.61 23.98 41.54 29.65 101.00 83.30 96.54 123.17 61.45 SD 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 11.34 The refinement process substantially increases candidate fitness, in some cases by an order of magnitude or more. The iterative process allows each FDOF to be fine-tuned to better match the fitness criteria, explaining the large increase in candidate fitness. 179 Figure 96 shows a graphical representation of candidate fitness before and after the iterative refinement process. -Original -Refined ------------_.__._-----------_._---­140.0 120.0 m 100.0 <0 .... 80.0 ~ U'I - 1.50 .. t J" J" r· 1.00 t­ T ~ _..__.­0.50 +,-- -­ 0.00 L---r­ 0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 Ipsilateral Phase L­ ~ __' Figure 115. Effect of varying ipsilateral phase on Apatosaurus body yawing. 231 Like the Apatosaurus model, the Triceratops hindlimb LROM space is highly parasagittal and the forelimb LROM space is robust, but the model is capable of supporting smooth forward locomotion. Table 28 shows the effect ofvarying ipsilateral phase on Triceratops yaw and lateral displacement. Table 28. Effect ofvarying ipsilateral phase on Triceratops gait observables Ipsilateral phase Observable 0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 Yaw (") M 5.12 5.32 4.66 4.20 4.46 4.53 4.66 4.35 2.94 3.79 SD 1.71 1.62 1.56 1.53 1.26 1.11 2.74 1.81 1.37 0.75 Lateral displacement (cm) M 11.84 10.94 11.04 10.75 9.32 10.40 11.33 11.55 11.31 12.26 SD 3.06 1.48 2.69 2.76 1.69 1.71 2.61 2.03 2.22 1.45 Again, there is no obvious relationship between ipsilateral phase and the yaw and lateral displacement observables of the Triceratops model. Figure 116 shows a visual representation of the effect of ipsilateral phase on the Triceratops yaw and lateral displacement observables. ---- ------- ------------ 232 8.00 7.00 6.00 5.00 0 l - -~ 4.00 ~~.~ ~! ~=H--= ~---------i­ltl > 3.00 1---- -----­ f-----­2.00 1.00 ­ 0.00 f------,- --,--- ,I I I I I 0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 Ipsilateral Phase ----,-­ Figure 116. Effect of varying ipsilateral phase on Triceratops body yawing. Unlike the dog, Apatosaurus, and Triceratops models, the generic reptile model is not capable of either parasagittal hindlimb or forelimb movements due to its sprawling gait. Therefore, it seems intuitive that the reptile would likely not be capable of accomplishing the requested hind and fore step lengths for certain ipsilateral phase values. For example, an ipsilateral phase of 0.0 should give similar orientation for hind and fore roots because a 0.5 phase gives nearly opposite orientation due to sinuous trunk movements. Such similar orientation would only be possible if the orientations pointed the both roots nearly forward, otherwise the trunk would need to bend in unnatural ways with at least two inflection points. Table 29 shows the result of varying ipsilateral phase on the reptile yaw and lateral displacement observables. -- 233 Table 29. Effect ofvarying ipsilateral phase on reptile gait observables Ipsilateral phase Observable 0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 Yaw (") M 23.60 26.34 28.50 28.00 25.76 27.02 27.49 27.14 27.58 25.84 SD 2.36 2.97 3.41 4.40 5.17 2.37 3.27 3.32 2.35 1.19 Lateral displacement (cm) M 24.27 25.08 25.81 26.49 25.51 24.79 26.57 30.04 27.43 27.58 SD 1.07 2.24 4.12 2.57 2.86 5.56 5.81 3.76 2.82 3.43 Surprisingly, there does not seem to be a relationship between ipsilateral phase and body yaw or lateral displacement. Figure 117 shows a graphical representation of the effect of ipsilateral phase on reptile gait yawing and lateral displacement. 35.00 1:.-.;­ 30.00 ~~ ~~ 25.00 Tt~- - nu .. . 20.00 ~ ro 15.00 ­> 10.00 5.00 1 0.00 -----,------,---,--,-----,-------,---,--,.----,----, 0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 Ipsilateral Phase '------_._-_._-­ Figure 117. Effect of varying ipsilateral phase on reptile body yawing. 234 Upon further investigation, it became obvious that the reptile model's hindlimbs are kinematically capable of pointing the hindlimb root nearly forward, allowing quadrupedal gaits with any ipsilateral phase value. The ability to point the hindlimb root forward could be taken away by limiting the shoulder flexion/extension FDOF, but doing so would result in less-characteristic reptile gaits. Figure 118 compares reptile gaits with a 0.5 ipsilateral phase (top) and a 0.0 ipsilateral phase (bottom). Figure 118. Comparison of0.5 (top) and 0.0 (bottom) reptile ipsilateral phases. 235 Based on these results, ipsilateral phase seems to be a non-kinematic issue that cannot be resolved with this approach. Ipsilateral phase is more likely related to the issue of support; animals with a relatively-low COM will tend to use diagonal couplet (i.e., trotting) gaits because they can more easily keep their COM between supporting limbs. Hildebrand (1980) supports this argument by stating that tetrapods tend to avoid lateral couplet gaits at slow speeds in favor of lateral sequence and diagonal couplet gaits because of the increased support triangle area. Alexander (1983) reports that contralateral and ipsilateral gait phases observed in animals are related to limb lengths and velocity (i.e. Froude numbers). The data presented in the section confirm that the gait observables of quadrupedal models capable ofparasagittal gait movements (i.e., dog, Apatosaurus, Triceratops) are not significantly affected by ipsilateral phase. Surprisingly, the gait observables of the reptile model were also not significantly affected by ipsilateral phase. The latter result helps to confirm the observations of others that gait selection and ipsilateral phase are stability and dynamics issues, and not simple kinematic issues. Summary The data presented in this chapter confirms the utility of the LROM space representation and the use of efficient GAs to find gaits that smootWy move the animal through the space. Data related to the tuning of the GA was first presented. Parent selection parameters were varied, along with crossover and mutation coefficients to fmd optimal GA parameters. Candidate populate size was also varied to find a sufficient 236 population size parameter. A convergence comparison was then presented that showed the tuned GA's ability to outperform a simulated Hill Climbing algorithm. A sensitivity analysis of the parameters used to build the LROM spaces demonstrated that the angular sampling resolution used to initially exercise the limb did not significantly alter the fitness of generated gaits. Varying the number of LROM space boxes that the LROM root positions are sorted into also did not have a significant effect of generated gait fitness. Space refinement was shown to significantly increase gait fitness without changing functional joint behavior, indicating that joint behavior is not sensitive to isolated changes in fitness error values. Lastly, an analysis ofvariations to the fitness function coefficients showed that changes to the coefficients had an intuitive result on gait fitness (e.g., increasing the pitch error coefficient decreased the amount of observed pitching) without affecting functional joint behaviors. A qualitative gait analysis demonstrated that the hindlimb and forelimb movements of the generated quadrupedal dog gaits match closely to published data. Similarly, the hindlimb and forelimb movements of the generated quadrupedal reptile gaits matched closely to published data. Comparisons were then made between the hindlimb and forelimb movements of the dog and reptile to analogous movements of the Apatosaurus, Triceratops, and Tyrannosaurus dinosaurs. Observations were then presented on the similarities in joint functionality between animals. Finally, a quantitative analyses presented data on specific gait hypotheses: The dog model was shown to not utilize its shoulder abduction/adduction and medialllateral rotation FDOFs; the Apatosaurus and Triceratops models were shown to make use of 237 combinations of these FDOFs to achieve smooth forward locomotion. Next, animals without pes flexibility were shown to benefit from low ankle heights while animals with high ankle heights were shown to depend heavily on pes flexibility. Lastly, ipsilateral phase was shown to not have a significant effect on kinematically-generated gaits, indicating that ipsilateral phase selection is more an issue of stability and dynamics than kinematics. The data presented in this chapter demonstrates some of the capabilities and limitations of the GAGA methods presented in the previous chapter. These methods are capable of exploring an LROM, and sorting the results into an LROM space, pruning the space, and finding combinations of configurations in the space that represent smooth gaits. The next chapter will present an in-depth discussion of the capabilities and limitations of the GAGA approach and the significance ofthe data and results presented in this chapter. 238 CHAPTER V DISCUSSION 3D animations oflocomotion are particularly useful for gait analysis. The GAGA methods presented in earlier chapters allow such animations to be automatically generated using kinematic explorations of limb capabilities and GAs to find plausible locomotion paths through LROM spaces. Using these methods, generated walking gaits were compared to real-world analogues as controls to confirm the viability of a particular GA fitness function for locomotion synthesis. The same fitness function was then used to generate forward walking gaits for dinosaurs, about which relatively little is known. The methods and investigations presented in this paper have several interesting implications and corollaries, which will be discussed in this chapter. Limb biomechanics are usually described in proximal-to-distal order. For example, the hip and knee joints are generally considered to be responsible for moving the animal forward, while the ankle joint and pes flexibility are responsible for adjusting to uneven terrain (Daley, Felix, and Biewener, 2007). When describing joint behaviors with respect to LROM spaces, however, it is most intuitive to consider joints in distal-to­ proximal order. This distal-to-proximal ordering is more natural when considering 239 locomotion as a process of first constraining the location of the foot that is in contact with the ground, then considering the forward movement of the body as constrained by the kinematics of the limb and body above that foot. In general, the contribution that an FDOF makes to the LROM space increases with the 3D distance between the joint and the root position (i.e., exercising the FDOF in isolation causes the root to rotate on an arc about the joint). Of course the distance between a joint and the root will generally change during locomotion due to intermediate joints. Combinations ofFDOFs will move the root along paths which are largely within the animal's sagittal plane if the limb's FDOFs have axes of rotation that are nearly perpendicular to the sagittal plane. Conversely, a limb with divergent FDOFaxes will have a broader LROM space. It is therefore the distal-most joints (e.g., the ankle joint and pes flexibility) that have the greatest effect in moving the root joint forward, allowing the root to move on an arc long enough to move the animal forward by a step length. The mid-limb joints (i.e., knee and elbow) can contribute to the arc of the root to a lesser extent. The mid-limb joints can also alter the limb's length through flexion/extension, allowing less vertical displacement during locomotion. The proximal joints (e.g., hip, shoulder, and scapulothorax) are sufficiently close to the root position that their major contribution is to modify the root orientation such that body pitching, rolling, and yawing are minimized. The configurations of an LROM space are typically distributed along an animal's sagittal plane, with enough thickness in the space to allow many possible forward movements. When an LROM space is initially generated and visualized, it is sometimes 240 obvious that there are not enough parasagittal LROM space configurations to allow a reasonable step length. These situations typically occur when a generally-planar LROM space is not aligned with the animal's sagittal plane, either by rotation due to the manus/pes orientation parameter or lateral translation due to step width parameter. In these cases, the step width, manus/pes orientation and/or limb FDOFs must be modified to better align the LROM space with the animal's sagittal plane. Otherwise, not enough configurations will survive the contralateral constraint process and the GA will not be able to find forward paths through the constrained space. Figure 119 shows an example of a planar but non-parasagittal LROM space for the Apatosaurus hindlimb. Figure //9. Planar but non-parasagittal Apatosaurus hindlimb LROM space. Variations on FDOFs can quickly be evaluated due to the fast computational speed of the GAGA methods (i.e., automatically generating bipedal gaits in about one 241 minute and quadrupedal gaits in under five minutes on a laptop). For example, pronation/supination in the generic reptile model's crus and antibrachium can be turned off by changing a scripted parameter. The reptile would likely not be capable of its current step length 2.2 times the hip height, indicating that the animal requires crus/antibrachium pronation/supination to achieve that step length without twisting or squishing the manus/pes on the ground. If the reptile were able to achieve a step length 2.2 times the hip height without pronation/supination, the GA gait observables (e.g., body pitch, roll, and yaw, and lateral/vertical displacement) and visualization of the gait itself would give indications as to whether or not the gait would be realistic. The case studies presented in the last chapter show the utility ofthe GAGA methods for quantitative analysis. The studies varied scripted FDOF parameters to evaluate the functionality ofFDOFs, used scripted scaling values to vary ankle height, and varied phase parameters to determine the effect of ipsilateral phase on quadrupedal gaits across animals. These case studies yielded significant and publishable results. Due to the computational efficiency of the kinematics-only exploration, constraint, and GA algorithms, study data can be collected relatively quickly; roughly 100 quadrupedal data points can be collected (i.e., ten GA runs per data point) over a 24 hour period. The contributions of the scapulothorax and shoulder joint FDOFs were isolated for the dog, Apatosaurus, and Triceratops models. The investigation revealed that the dog model uses little shoulder abduction/adduction and mediaVlateral rotation, and utilizes scapulothorax rotation to minimize body pitching during locomotion. These results are intuitive given the highly-parasagittal nature of the dog forelimb LROM space. 242 The forelimbs ofApatosaurus and Triceratops, however, make extensive use of shoulder abduction/adduction and medial/lateral rotation to allow the limbs to navigate smoothly through their broader LROM spaces (i.e., which result from divergent limb FDOFaxes). Cursorial (i.e., specialized for running) animals typically exhibit high ankle heights while graviportal (i.e., specialized for bearing weight) animals typically have lower ankle heights (Coombs, 1978). The investigation into the significance of ankle height revealed that animals with lower ankle heights have a kinematic advantage over animals with higher ankle heights. Animals with higher ankle heights require additional flexibility in their manus and pes to be capable of long strides. Gaits were generated with varying ipsilateral phase values for all four quadrupedal models. The results of this investigation showed no discernible kinematic advantages for some phase values over others. These results were not surprising for the dog, Apatosaurus, and Triceratops models, as those models are capable of generally­ parasagittallimb movements that should allow locomotion without much lateral bending ofthe trunk. The reptile, however, utilizes extensive sinuous lateral trunk movements during locomotion (Reilly, 1997, 1998), so it was surprising that ipsilateral phase had little effect on the gait observables. The lack of change in trunk behavior was due to ROMs of the reptile hips; the ROMs needed to allow angular excursions sufficient for reptilian limb movements, but these ROMs then also allowed the hips to keep the body pointing relatively forward during locomotion (see Figure 118). These results indicate that gait phase is a complicated issue that requires more than kinematics to properly investigate. 243 A qualitative analysis was used to determine how well GAGA-generated gaits match those of real-world animals. Much thought was given to the possibility of a quantitative analysis to show these properties. Ultimately, there did not seem to be any reasonable quantitative means for comparison. Exact joint angles are difficult to determine reliably and are dependent on a large number of external factors. Froude numbers are often used to compare gaits, but usually in terms of relative velocities (which cannot be easily computed using kinematics-only models). For these reasons, a quantitative gait comparison study is left for future work. GAGA methods use kinematics only to analyze gaits; dynamics were omitted by design to allow an exploration of the viability ofkinematics-only gait analysis. Stability studies based on support triangles (Henderson, 2006) would be difficult because the system does not keep track of an animal's COM. COM tracking could be added, however, by scripting a mass parameter for each body segment and then computing the instantaneous overall COM during locomotion. Similarly, gaits with an aerial phase cannot be modeled with GAGA methods because the system has no way ofpredicting COM trajectories during aerial phases. These omissions have been largely strategic; adding terms to the fitness function that require dynamics simulation would increase the running time ofthe GAs by several orders of magnitude. Nonetheless, dynamics-based gait observables could be integrated into the GAGA methods at a future time. The GAGA methods have applications in any area that requires a quantitative analysis of changes to joint functionality or limb proportions. FDOFs can be based on any movement, so LROM spaces could theoretically be generated for a typical knee joint 244 and a knee joint with a prosthetic articular surface, similar to the study by Piazza and Delp (2001). The two spaces could be compared to determine how well the prosthetic approximates a typical knee joint. Gaits could also be generated from the two spaces so that the difference in movements could be viewed in terms of gait observables, but the fitness function and gait observables might need to be modified so that the biological knee model behavior matches closely to that of a real knee. Such fitness function changes are straightforward with respect to GAGA, but determining an appropriate fitness function in terms of the high-level goals of a joint or limb can be difficult. GAGA methods could also be used for limb-based studies other than locomotion. These methods could be used to investigate how an animal transitions from a sitting to standing posture and vice versa, similar to Stevens, Larson, Wills, and Anderson (2008). Such transitions are likely generally constrained by the osteology of an animal with the musculature acting on the bones and joints, much like with locomotion. Therefore, GAGA methods could be used for the kinematic synthesis and analysis of these movements. 245 CHAPTER VI CONCLUSIONS The LROM space representation provides intuitive visualizations ofLROMs consisting of discrete FDOFs. Changes in FDOFs can be easily detected by comparing resulting LROM spaces. LROM spaces are pruned using dual support and bilateral symmetry constraints so that only limb configurations relevant to bipedal locomotion are considered by the GAs. LROM spaces are further pruned by trunk: constraints for quadrupedal locomotion. Highly-optimized GAs find plausible paths through these large spaces with relatively-little computational effort, allowing the evaluation of many FDOF and gait parameter variations. Walking gaits are generated from only two key configurations, representing the RD and RLU gait events. These two key configurations are near the beginning of the right limb's support phase, when the limb is reaching forward. The RD and RLU gait events, the dual support constraint, and the bilateral symmetry constraint determine two additional key configurations, namely for RLD and RU. The RLD and RU configurations are near the end of the right limb's support phase, when the limb is reaching back. The limb is sent on a "pole vaulting" trajectory between RLU and RLD 246 which is detennined by all four right-side limb events. The four right-side events are bilaterally mirrored to the left side, specifying configurations for the four left-side events. In this way, configurations for a total of eight locomotion events are specified from the original two key configurations (i.e., RD and RLU). Limbs have relatively few ways of reaching forward and backwards, compared to a limb's many possible mid-stance configurations. The GAs are therefore able to search relatively-small spaces of possible configurations (i.e., pruned by the dual support and bilateral symmetry constraints). GA performance is additionally improved by a candidate representation and fitness function that guarantee that each candidate gait at least accomplishes a specified stride length. The GAs therefore focus entirely on reducing gait error values (i.e., body pitch, yaw, roll, lateral/vertical displacement, and angular excursions at the joints). The gaits generated using GAGA methods were shown to be stable with respect to changes in the LROM space parameters. Changes to the fitness function error tenns were shown to have intuitive effects on the generated gaits. Gaits can be refined to further increase fitness, but this process does not have a significant effect on joint functionality, indicating that limb movements are highly constrained by their limited ROMs near the beginning and end of their stance phase. By pruning LROM spaces such that only configurations during dual support are considered, GAGA methods are able to quickly and accurately reproduce complete gait cycles. Future work will likely involve further qualitative and quantitative studies on the animal models presented in this paper and on animals not yet modeled. There are 247 potentially a number of additional publishable results that could come out of future studies using these methods. A quantitative study may be devised to compare GAGA­ generated gaits to those of real-world animals. Such a study would likely require extensive collaboration with a laboratory capable of collecting large amounts of animal gait data. This type of study would provide more insight into the capabilities and limitations ofkinematic-only gait synthesis and analysis. 248 APPENDIX A DOG MODEL DATA Table 30. DogFDOFs Rotation (0) Position (em) FDOF x y z x y z Hip_Joint_R Base 0 0 0 -8 -9 -8 FDOF 1 Minimum -25 0 0 0 0 0 Neutral -12 0 0 0 0 0 Maximum 20 0 0 0 0 0 FDOF2 Minimum 0 -8 0 0 0 0 Neutral -12 0 0 0 0 0 Maximum 0 8 0 0 0 0 FDOF3 Minimum 0 0 -10 0 0 0 Neutral 0 0 0 0 0 0 Maximum 0 0 10 0 0 0 Knee Joint R Base 0 0 0 0 0 41 FDOF 1 Minimum -20 0 0 0 0 0 Neutral 0 0 0 0 0 0 Maximum 20 0 0 0 0 0 Ankle Joint R Base 0 0 0 0 0 47 FDOF 1 Minimum -20 0 0 0 0 0 Neutral 0 0 0 0 0 0 Maximum 15 0 0 0 0 0 249 Dog FDOFs (continued) Rotation CO) Position (ern) FDOF x y Z x y Z Pes Joint R Base 0 0 0 0 0 23 FDOF 1 Minimum -20 0 0 0 0 0 Neutral 0 0 0 0 0 0 Maximum 20 0 0 0 0 0 Hip_Joint_L Base 0 0 0 8 -9 -8 FDOF1 Minimum -25 0 0 0 0 0 Neutral -12 0 0 0 0 0 Maximum 20 0 0 0 0 0 FDOF2 Minimum 0 8 0 0 0 0 Neutral -12 0 0 0 0 0 Maximum 0 -8 0 0 0 0 FDOF3 Minimum 0 0 10 0 0 0 Neutral 0 0 0 0 0 0 Maximum 0 0 -10 0 0 0 Knee Joint L Base 0 0 0 0 0 41 FDOF1 Minimum -20 0 0 0 0 0 Neutral 0 0 0 0 0 0 Maximum 20 0 0 0 0 0 Ankle Joint L Base 0 0 0 0 0 47 FDOF 1 Minimum -20 0 0 0 0 0 Neutral 0 0 0 0 0 0 Maximum 20 0 0 0 0 0 Pes Joint L Base 0 0 0 0 0 23 FDOF 1 Minimum -20 0 0 0 0 0 Neutral 0 0 0 0 0 0 Maximum 20 0 0 0 0 0 Seapulothorax_Joint_R Base 0 0 0 -10 2 -5 FDOFI Minimum 8 0 0 0 0 0 Neutral 8 0 0 0 0 0 Maximum 36 0 0 0 0 0 250 Dog FDOFs (continued) Rotation (0) Position (em) FDOF x y z x y z Shoulder Joint R Base 0 0 0 0 0 18 FDOFI Minimum -26 0 0 0 0 0 Neutral 0 0 0 0 0 0 Maximum 20 0 0 0 0 0 FDOF2 Minimum 0 -8 0 0 0 0 Neutral 0 0 0 0 0 0 Maximum 0 8 0 0 0 0 FDOF3 Minimum 0 0 -10 0 0 0 Neutral 0 0 0 0 0 0 Maximum 0 0 10 0 0 0 Elbow Joint R Base 0 0 0 0 0 31 FDOF 1 Minimum -30 0 0 0 0 0 Neutral 0 0 0 0 0 0 Maximum 20 0 0 0 0 0 Wrist Joint R Base 0 0 0 0 0 39 FDOF 1 Minimum -25 0 0 0 0 0 Neutral 0 0 0 0 0 0 Maximum 35 0 0 0 0 0 Manus Joint R Base 0 0 0 0 0 17 FDOFI Minimum -25 0 0 0 0 0 Neutral 0 0 0 0 0 0 Maximum 25 0 0 0 0 0 Seapulothorax_Joint_L Base 0 0 0 10 2 -5 FDOF 1 Minimum 8 0 0 0 0 0 Neutral 8 0 0 0 0 0 Maximum 36 0 0 0 0 0 Shoulder Joint L Base 0 0 0 0 0 18 FDOF 1 Minimum -26 0 0 0 0 0 Neutral 0 0 0 0 0 0 Maximum 20 0 0 0 0 0 251 Dog FDOFs (continued) Rotation CO) Position (em) FDOF x y Z x y z FDOF2 Minimum 0 8 0 0 0 0 Neutral 0 0 0 0 0 0 Maximum 0 -8 0 0 0 0 FDOF3 Minimum 0 0 10 0 0 0 Neutral 0 0 0 0 0 0 Maximum 0 0 -10 0 0 0 Elbow Joint L Base 0 0 0 0 0 31 FDOF 1 Minimum -30 0 0 0 0 0 Neutral 0 0 0 0 0 0 Maximum 20 0 0 0 0 0 Wrist Joint L Base 0 0 0 0 0 39 FDOF 1 Minimum -25 0 0 0 0 0 Neutral 0 0 0 0 0 0 Maximum 35 0 0 0 0 0 Manus Joint L Base 0 0 0 0 0 17 FDOF 1 Minimum -25 0 0 0 0 0 Neutral 0 0 0 0 0 0 Maximum 25 0 0 0 0 0 252 APPENDIXB REPTILE MODEL DATA Table 31. Reptile FDOFs Rotation (0) Position (em) FDOF x y z x y z Hip_Joint_R Base 0 0 0 0 0 10 FDOF 1 Minimum 0 -50 0 0 0 0 Neutral 0 0 0 0 0 0 Maximum 0 10 0 0 0 0 FDOF2 Minimum -10 0 0 0 0 0 Neutral 0 0 0 0 0 0 Maximum 10 0 0 0 0 0 FDOF3 Minimum 0 0 -60 0 0 0 Neutral 0 0 0 0 0 0 Maximum 0 0 8 0 0 0 Knee Joint R Base 0 0 0 0 0 58 FDOF 1 Minimum -11 -26 2 0 0 0 Neutral 0 0 0 0 0 0 Maximum 9 21 2 0 0 0 Crus PS R Base 0 0 0 0 0 42 FDOFI Minimum 0 0 -60 0 0 0 Neutral 0 0 0 0 0 0 253 Reptile FDOFs (continued) Rotation (0) Position (em) FDOF x y z x y z Maximum 0 0 12 0 0 0 Ankle Joint R Base 0 0 0 0 0 50 FDOF1 Minimum -20 0 0 0 0 0 Neutral 0 0 0 0 0 0 Maximum 5 0 0 0 0 0 Pes Joint R Base 0 0 0 0 0 37 FDOF1 Minimum -30 0 0 0 0 0 Neutral 0 0 0 0 0 0 Maximum 5 0 0 0 0 0 FDOF2 Minimum 0 0 -20 0 0 0 Neutral 0 0 0 0 0 0 Maximum 0 0 20 0 0 0 Hip_Joint_L Base 0 0 0 0 0 10 FDOF1 Minimum 0 50 0 0 0 0 Neutral 0 0 0 0 0 0 Maximum 0 -10 0 0 0 0 FDOF2 Minimum -10 0 0 0 0 0 Neutral 0 0 0 0 0 0 Maximum 10 0 0 0 0 0 FDOF3 Minimum 0 0 60 0 0 0 Neutral 0 0 0 0 0 0 Maximum 0 0 -8 0 0 0 Knee Joint L Base 0 0 0 0 0 58 FDOF1 Minimum -11 26 -2 0 0 0 Neutral 0 0 0 0 0 0 Maximum 9 -21 -2 0 0 0 Crus PS L Base 0 0 0 0 0 42 FDOF 1 Minimum 0 0 60 0 0 0 Neutral 0 0 0 0 0 0 Maximum 0 0 -12 0 0 0 Ankle Joint L 254 Reptile FDOFs (continued) Rotation (0) Position (em) FDOF x y Z x y z Base 0 0 0 0 0 50 FDOF 1 Minimum -20 0 0 0 0 0 Neutral 0 0 0 0 0 0 Maximum 5 0 0 0 0 0 Pes Joint L Base 0 0 0 0 0 37 FDOF 1 Minimum -30 0 0 0 0 0 Neutral 0 0 0 0 0 0 Maximum 5 0 0 0 0 0 FDOF2 Minimum 0 0 20 0 0 0 Neutral 0 0 0 0 0 0 Maximum 0 0 -20 0 0 0 Shoulder Joint R Base 0 0 0 0 0 20 FDOF 1 Minimum 0 -40 0 0 0 0 Neutral 0 0 0 0 0 0 Maximum 0 10 0 0 0 0 FDOF2 Minimum -10 0 0 0 0 0 Neutral 0 0 0 0 0 0 Maximum 10 0 0 0 0 0 FDOF3 Minimum 0 0 -30 0 0 0 Neutral 0 0 0 0 0 0 Maximum 0 0 10 0 0 0 Elbow Joint R Base 0 0 0 0 0 63 FDOF 1 Minimum 12 -37 -3 0 0 0 Neutral 0 0 0 0 0 0 Maximum -4 15 -1 0 0 0 Antibrachium PS R Base 0 0 0 0 47 FDOF 1 Minimum 0 0 -25 0 0 0 Neutral 0 0 0 0 0 0 Maximum 0 0 30 0 0 0 Wrist Joint R Base 0 0 0 0 -1 45 FDOF 1 255 Reptile FDOFs (continued) Rotation CO) Position (em) FDOF x y Z x y Z Minimum -20 0 0 0 0 0 Neutral 0 0 0 0 0 0 Maximum 5 0 0 0 0 0 Manus Joint R Base 0 0 0 0 0 37 FDOF 1 Minimum -30 0 0 0 0 0 Neutral 0 0 0 0 0 0 Maximum 5 0 0 0 0 0 FDOF2 Minimum 0 0 -20 0 0 0 Neutral 0 0 0 0 0 0 Maximum 0 0 20 0 0 0 Shoulder Joint L Base 0 0 0 0 0 20 FDOF 1 Minimum 0 40 0 0 0 0 Neutral 0 0 0 0 0 0 Maximum 0 -10 0 0 0 0 FDOF2 Minimum -10 0 0 0 0 0 Neutral 0 0 0 0 0 0 Maximum 10 0 0 0 0 0 FDOF3 Minimum 0 0 30 0 0 0 Neutral 0 0 0 0 0 0 Maximum 0 0 -10 0 0 0 Elbow Joint L Base 0 0 0 0 0 63 FDOF 1 Minimum 12 37 3 0 0 0 Neutral 0 0 0 0 0 0 Maximum -4 -15 1 0 0 0 Antibrachium PS L Base 0 0 0 0 47 FDOF 1 Minimum 0 0 25 0 0 0 Neutral 0 0 0 0 0 0 Maximum 0 0 -30 0 0 0 Wrist Joint L Base 0 0 0 0 -1 45 FDOF 1 Minimum -20 0 0 0 0 0 Neutral 0 0 0 0 0 0 256 Reptile FDOFs (continued) Rotation (0) Position (em) FDOF x y Z x y z Maximum 5 0 0 0 0 0 Manus Joint L Base 0 0 0 0 0 37 FDOF 1 Minimum -30 0 0 0 0 0 Neutral 0 0 0 0 0 0 Maximum 5 0 0 0 0 0 FDOF2 Minimum 0 0 20 0 0 0 Neutral 0 0 0 0 0 0 Maximum 0 0 -20 0 0 0 257 .... APPENDIXC APATOSAURUS MODEL DATA Table 32. Apatosaurus FDOFs Rotation (0) Position (em) FDOF x y Z x y z Hip_JoineR Base 3 0 0 22 -13 11 FDOFI Minimum -21 0 1 0 0 0 Neutral 0 0 0 0 0 0 Maximum 18 0 -1 0 0 0 FDOF2 Minimum 0 -10 -1 0 0 0 Neutral 0 0 0 0 0 0 Maximum 0 13 1 0 0 0 FDOF3 Minimum 0 0 -10 0 0 0 Neutral 0 0 0 0 0 0 Maximum 0 0 10 0 0 0 Knee_JoineR Base -4 -2 -32 18 149 FDOFI Minimum -20 0 0 0 -3 0 Neutral 0 0 0 0 -5 0 Maximum 74 0 0 0 -14 0 Ankle_JoineR Base 0 0 0 6 7 128 FDOFI Minimum -19 -5 -28 0 2 1 Neutral 0 0 0 0 0 0 258 Apatosaurus FDOFs (continued) Rotation CO2 Position (em) FDOF x y z x y z Maximum 20 -5 29 0 0 0 Hip_Joint_L Base 3 0 0 -22 13 -11 FDOF 1 Minimum -21 0 1 0 0 0 Neutral 0 0 0 0 0 0 Maximum 18 0 -1 0 0 0 FDOF2 Minimum 0 -10 -1 0 0 0 Neutral 0 0 0 0 0 0 Maximum 0 13 1 0 0 0 FDOF3 Minimum 0 0 -10 0 0 0 Neutral 0 0 0 0 0 0 Maximum 0 0 10 0 0 0 Knee Joint L Base -4 -2 32 -18 -149 FDOF 1 Minimum -20 0 0 0 3 0 Neutral 0 0 0 0 5 1 Maximum 74 0 0 0 14 0 Ankle Joint L Base 0 0 0 -6 -7 -128 FDOF 1 Minimum -19 -5 -28 0 2 1 Neutral 0 0 0 0 0 0 Maximum 20 -5 29 0 0 0 Seapulothorax_Joint_R Base 2 -9 -13 -83 -16 53 FDOF 1 Minimum -17 5 -5 0 0 0 Neutral 0 0 0 0 0 0 Maximum 10 0 4 0 0 0 FDOF2 Minimum 0 0 0 0 15 0 Neutral 0 0 0 0 0 0 Maximum 0 0 0 0 -10 0 Shoulder Joint R Base 0 8 -20 -4 -2 29 FDOF1 Minimum -35 0 0 0 0 0 Neutral -4 -3 1 0 0 0 Maximum 35 0 0 0 0 0 FDOF2 259 Apatosaurus FDOFs (continued) Rotation (0) Position (em) FDOF x y Z x y z Minimum 0 -18 0 0 0 0 Neutral -4 -3 1 0 0 0 Maximum 0 18 0 0 0 0 FDOF3 Minimum 0 0 -10 0 0 0 Neutral 0 0 0 0 0 0 Maximum 0 0 10 0 0 0 Elbow Joint R Base 3 6 -40 -15 6 100 FDOF 1 Minimum -33 -15 2 1 2 0 Neutral 0 0 0 0 0 0 Maximum 25 2 4 0 0 0 Ulnoearpal_Joint_R Base -54 0 15 -6 2 88 FDOFI Minimum -10 -14 -3 0 0 0 Neutral 0 0 0 0 0 0 Maximum 24 27 13 0 0 0 Seapulothorax_Joint_L Base 2 -9 -13 -21 -16 97 FDOF 1 Minimum -17 5 -5 0 0 0 Neutral 0 0 0 0 0 0 Maximum 10 0 4 0 0 0 FDOF2 Minimum 0 0 0 0 15 0 Neutral 0 0 0 0 0 0 Maximum 0 0 0 0 -10 0 Shoulder Joint L Base 0 8 -20 4 2 -29 FDOFI Minimum -35 0 0 0 0 0 Neutral -4 -3 1 0 0 0 Maximum 35 0 0 0 0 0 FDOF2 Minimum 0 -18 0 0 0 0 Neutral -4 -3 1 0 0 0 Maximum 0 18 0 0 0 0 FDOF3 Minimum 0 0 -10 0 0 0 Neutral 0 0 0 0 0 0 Maximum 0 0 10 0 0 0 Elbow Joint L 260 Apatosaurus FDOFs (continued) Rotation (0) Position (em) FDOF x y Z x Y z Base 3 6 -40 15 -6 -100 FDOF1 Minimum -33 -15 2 1 2 0 Neutral 0 0 0 0 0 0 Maximum 25 2 4 0 0 0 Ulnoearpal_Joint_L Base -54 0 15 6 -2 -88 FDOF 1 Minimum -10 -14 -3 0 0 0 Neutral 0 0 0 0 0 0 Maximum 24 27 13 0 0 0 261 APPENDIXD TRICERATOPS MODEL DATA Table 33. Triceratops FDOFs Rotation C) Position (em) FDOF x y Z x y Z Hip_JoinCR Base 0 0 0 8 -11 -29 FDOFI Minimum 8 20 16 0 0 0 Neutral 0 2 -3 0 0 0 Maximum -1 -31 -22 0 0 0 FDOF2 Minimum -3 -8 13 0 0 0 Neutral 0 2 -3 0 0 0 Maximum 1 6 -8 0 0 0 FDOF3 Minimum -12 3 0 0 0 0 Neutral 0 0 0 0 0 0 Maximum 15 -3 0 0 0 0 Knee_JoinCR Base 0 0 0 91 21 12 FDOFI Minimum -20 4 -24 0 0 0 Neutral -23 4 -1 0 0 0 Maximum -19 0 63 0 0 0 Ankle_JoinCR Base 4 -20 -1 77 -1 0 FDOFI Minimum -58 -1 9 3 0 0 Neutral -4 10 0 0 -1 -1 262 Triceratops FDOFs (continued) Rotation CO) Position (em) FDOF x y Z x y z Maximum 56 20 0 3 -1 -3 Hip_Joint_L Base 0 0 0 8 -11 29 FDOF 1 Minimum -8 -20 16 0 0 0 Neutral -4 -2 -3 0 0 0 Maximum -1 31 -22 0 0 0 FDOF2 Minimum 3 8 13 0 0 0 Neutral -4 -2 -3 0 0 0 Maximum -1 -6 -8 0 0 0 FDOF3 Minimum 12 -3 0 0 0 0 Neutral 0 0 0 0 0 0 Maximum -15 3 0 0 0 0 Knee Joint L Base 0 0 0 91 21 -12 FDOF 1 Minimum 20 -4 -24 0 0 0 Neutral 23 -4 -1 0 0 0 Maximum 19 0 63 0 0 0 Ankle Joint L Base -4 20 -1 77 -1 0 FDOF 1 Minimum 58 1 9 3 0 0 Neutral 4 -10 0 0 -1 1 Maximum -56 -20 0 3 -1 3 Seapu1othorax_Joint_R Base 0 0 0 72 27 -5 FDOF 1 Minimum 9 4 -2 0 0 0 Neutral 0 0 0 0 0 0 Maximum -17 -3 -2 0 0 0 FDOF2 Minimum 0 0 0 1 10 1 Neutral 0 0 0 0 0 0 Maximum 0 0 0 -2 -13 -2 Shoulder Joint R Base 0 0 0 13 -4 14 FDOF 1 Minimum 3 2 -23 0 0 0 Neutral 0 0 0 0 0 0 Maximum -5 0 39 -4 -2 -5 FDOF2 263 Triceratops FDOFs (continued) Rotation (0) Position (em) FDOF x y z x y z Minimum 0 7 0 0 0 0 Neutral 0 0 0 0 0 0 Maximum 0 -12 0 0 0 0 FDOF3 Minimum -8 0 0 0 0 0 Neutral 0 0 0 0 0 0 Maximum 8 0 0 0 0 0 Elbow Joint R Base 0 0 0 66 -5 -8 FDOF 1 Minimum 6 28 39 1 -4 -2 Neutral 0 0 0 0 0 0 Maximum 6 -16 -13 0 0 0 Wrist Joint R Base 0 0 0 48 0 0 FDOF 1 Minimum 1 1 20 0 0 0 Neutral 0 0 0 0 0 0 Maximum -1 -3 -32 3 1 0 Seapulothorax_Joint_L Base 0 0 0 40 27 -60 FDOF 1 Minimum -9 -3 -3 0 0 0 Neutral 0 0 0 0 0 0 Maximum 17 3 -2 0 0 0 FDOF2 Minimum 0 0 0 1 10 1 Neutral 0 0 0 0 0 0 Maximum 0 0 0 -2 -13 -2 Shoulder Joint L Base 0 0 0 13 -4 -14 FDOF1 Minimum 1 -3 -23 0 0 0 Neutral 0 0 0 0 0 0 Maximum 5 -3 41 -3 -4 2 FDOF2 Minimum 0 -7 0 0 0 0 Neutral 0 0 0 0 0 0 Maximum 0 12 0 0 0 0 FDOF3 Minimum 8 0 0 0 0 0 Neutral 0 0 0 0 0 0 Maximum -8 0 0 0 0 0 Elbow Joint L 264 Triceratops FDOFs (continued) Rotation CO) Position (em) FDOF x y z x y z Base 2 0 0 67 -5 8 FDOF 1 Minimum -4 -26 40 0 -4 1 Neutral 0 0 0 0 0 0 Maximum -6 16 -13 0 1 0 Wrist Joint L Base 0 0 0 48 0 0 FDOF 1 Minimum -2 -1 20 0 0 0 Neutral 0 0 0 0 0 0 Maximum 0 1 -32 4 1 0 265 APPENDIXE TYRANNOSAURUS MODEL DATA Table 34. Tyrannosaurus FDOFs Rotation CO) Position (em) FDOF x y Z x Y z Hip_JoineR Base 0 0 0 4 5 -6 FDOF1 Minimum 0 -10 -35 0 0 0 Neutral 0 0 0 0 0 0 Maximum 0 0 20 0 0 0 FDOF2 Minimum 0 -10 0 0 0 0 Neutral 0 0 0 0 0 0 Maximum 0 5 0 0 0 0 FDOF3 Minimum -10 0 0 0 0 0 Neutral 0 0 0 0 0 0 Maximum 10 0 0 0 0 0 Knee_JoineR Base 0 0 0 114 7 23 FDOF1 Minimum 0 0 -20 0 0 0 Neutral 0 0 0 0 0 0 Maximum 0 0 25 0 0 0 Ankle_JoineR Base 0 0 0 115 -4 0 FDOFI Minimum 0 0 -25 0 0 0 Neutral 0 0 0 0 0 0 266 Tyrannosaurus FDOFs (continued) Rotation CO) Position (em) FDOF x y Z x y z Maximum 0 0 30 0 0 0 Pes Joint R Base 0 0 0 60 -10 FDOF 1 Minimum 0 0 -20 0 0 0 Neutral 0 0 0 0 0 0 Maximum 0 0 30 0 0 0 Phalangeal_Joint_R Base 0 0 0 21 0 FDOF 1 Minimum 0 0 -5 0 0 0 Neutral 0 0 0 0 0 0 Maximum 0 0 30 0 0 0 Hip_Joint_L Base 0 0 0 -4 -5 6 FDOF 1 Minimum 0 -10 -35 0 0 0 Neutral 0 0 0 0 0 0 Maximum 0 0 20 0 0 0 FDOF2 Minimum 0 -10 0 0 0 0 Neutral 0 0 0 0 0 0 Maximum 0 5 0 0 0 0 FDOF3 Minimum -10 0 0 0 0 0 Neutral 0 0 0 0 0 0 Maximum 10 0 0 0 0 0 Knee Joint L Base 0 0 0 -113 -6 -20 FDOF 1 Minimum 0 0 -20 0 0 0 Neutral 0 0 0 0 0 0 Maximum 0 0 20 0 0 0 Ankle Joint L Base 0 0 0 -115 4 0 FDOF 1 Minimum 0 0 -25 0 0 0 Neutral 0 0 0 0 0 0 Maximum 0 0 30 0 0 0 Pes Joint L Base 0 0 0 -60 10 -1 FDOF 1 Minimum 0 0 -20 0 0 0 Neutral 0 0 0 0 0 0 267 Tyrannosaurus FDOFs (continued) Rotation CO) Position (em) FDOF x y Z x y z Maximum 0 0 30 0 0 0 Pha1angea1_Joint_L Base 0 2 0 -21 -1 0 FDOF 1 Minimum 0 0 -5 0 0 0 Neutral 0 0 0 0 0 0 Maximum 0 0 30 0 0 0 268 APPENDIXF FIXING ORIENTATION AND POSITION 1. Store the initial y axis of the end effector as initialYAxis 2. Store the initial z axis of the end effector as initialZAxis 3. Store the initial quatemion rotation state of the root as initialRotation 4. Store the initial position of the end effector as initiaLEndPosition 5. Store the initial position of the root as initialRootPosition 6. For each frame rendered following a limb configuration change: a. Store the current y axis of the end effector as yAxis b. Store the current z axis of the end effector as zAxis c. Calculate the quatemion that rotates yAxis into initialYAxis and store as yRotation d. Multiply zAxis by yRotation e. Calculate the quateniion that rotates zAxis into initialZAxis and store as zRotation f. Set the root orientation to zRotation*yRotation*initialRotation 269 g. Store the current end effector position as position h. Calculate the vector that moves position to initialEndPosition and store as translation 1. Set the root position to initialRootPosition + translation 270 APPENDIXG GENETIC ALGORITHM STRUCTlTRE 1. Create an initial population consisting of randomly-generated, fixed-length binary strings and store as population 2. Create a binary string to hold the overall best (i.e., highest fitness) candidate solution and store as globalBest 3. For each genetic algorithm iteration: a. Apply crossover to the population by potentially combining each candidate with another randomly-selected binary string b. Apply mutation to the population by potentially flipping bits in each binary string c. Evaluate the fitness of the population, storing the fitness of each candidate d. If any candidate has a fitness higher than that ofglobalBest, store that candidate as globalBest 271 e. Select new parents for the next iteration by comparing each candidate to another randomly-selected candidate and usually selecting (i.e., based on a probability coefficient) the higher-fitness candidate f. Store the new parents as population 4. Report and handle the highest-fitness candidate, globalBest 272 APPENDIXH EXAMPLE BIPEDAL CANDIDATE 1. An LROM space for the right Tyrannosaurus hindlimb is generated by exploring all possible combinations of the limb's six FDOFs (see Appendix E) at a 5° angular resolution while keeping the pes position/orientation fixed on the ground (see Appendix F); the space contains 2,882,880 total samples 2. Each sample in the LROM space contains 12 floating point values: the FDOF values that specify the joint configurations of the limb (i.e., one float per FDOF, six total floats), the 3D position of the sample (i.e., 3 floats), and the pitch, yaw, and roll of the root element necessary to reach the sample position using the associated FDOF values 3. The LROM space is organized into 3D boxes, with 50 boxes along the direction oftravel (i.e., the number of boxes along the direction oftravel is an input parameter): a. The LROM space measures 5.03 meters along the directionoftravel, so each box is 10 cm x 10 cm x 10 cm 273 b. The space is 0.57 meters wide along the lateral axis, so there are 6 boxes along the lateral axis c. The space is 2.76 meters tall along the vertical axis, so there are 28 boxes along the vertical axis d. The space contains 6 x 50 x 28 boxes for a total of 8,400 boxes e. Each LROM space sample is sorted into the 3D box that surrounds the sample's 3D position, resulting in a list of samples for each 3D box 4. The LROM space is pruned based on the dual support and bilateral symmetry constraints; a suitable sibling sample is attempted to be found for each sample in the LROM space: a. The three indices of the sample's 3D box are determined based on the sample's 3D position, the bounds of the LROM space, and the 3D box dimensions b. The forward index ofthe sibling 3D box is determined by subtracting the dual support length from the step length (i.e., the step length is an input parameter, the dual support length is a function of the step length and the duty factor), then dividing by the box dimensions to determine the number of boxes that the animal will move forward through between the RD and RLD events c. The sibling lateral index is determined by reflecting the original index across the sagittal plane (i.e., using the lateral index of the sagittal plane) d. The vertical sibling index is equal to the original vertical index 274 e. If the sibling 3D box contains a sample with an RMS angular offset (i.e., the absolute value of the sibling sample angles minus the original sample angles) less than the specified epsilon error, store that sample as a sibling match for the original sample; if multiple sibling samples are found with less than the epsilon angular offset, use the sibling sample with the smallest angular offset f. Remove all samples from the space that do not have a sibling match, ensuring that all remaining samples satisfy the dual support and bilateral symmetry constraints g. The constrained space contains 80,640 total samples (i.e., including sibling samples) 5. The size of the linear binary candidates is computed: a. The size of the back data is computed as the number of non-sibling samples in the constrained space that are at least a step length back from the front ofthe space (i.e., so selections for the RD event will be able to complete a step of the specified length); the back data contains 11,145 samples, so 14 bits are required to index all back data samples b. The size of the largest slice in the slice data is computed by looking for the largest number of samples in any plane of 3D boxes perpendicular to the direction of travel; the largest slice contains 3,665 samples, so 12 bits are needed to address all slice data samples 275 c. Each candidate is a 14-bit index into the back data representing a sample for the RD event and a 12-bit index into a slice in the slice data representing a sample for the RLU event (i.e. the specific slice for the RLU event sample is determined by the slice of the RD event sample and the forward distance that the animal must travel during dual support); each candidate is represented by a 26-bit binary string 6. The GA is run for 10,000 iterations with a population of 1000 candidates (see Appendix G), each iteration: a. Each candidate is potentially combined with another randomly-selected candidate using single-point crossover and a crossover probability of 0.1 b. Each candidate is potentially mutated with a probability of 0.5 per candidate (i.e., on average one bit is flipped for half ofthe candidates in the population) c. The fitness of each candidate is calculated as 1.0 I (1.0 + e), where e is the weighted sum of terms stored in the RD and RLU event samples (i.e., from the 12 values stored in each sample): 5.0 times the sum body pitch caused by the RD and RLU events, 2.0 times the sum body yaw cause by these events, the sum body roll caused by these events, the sum vertical displacement between the event sample positions and the target vertical height, the sum lateral displacement between the event sample positions and the initial sagittal plane position, and the sum differences between the FDOF values of the RD and RLU events; the body roll/pitch/yaw and sum 276 FDOF difference terms are multiplied by the step length so that these angular terms can be related to the translational terms d. If any candidate has higher fitness than the highest-fitness candidate found thus far, store that candidate as the highest-fitness candidate e. Select new parents for the next GA iteration using Tournament Selection with a 0.9 probability of selecting the higher-fitness candidate (i.e., compare each candidate in the population with another randomly-selected candidate and select the higher-fitness candidate 90% of the time) 7. The highest-fitness candidate after the 10,000 GA iterations is 0 0 1 0 0 0 1 1 0 0 1 1 0 0 1 1 1 0 1 0 1 0 1 1 1 0, which corresponds to 1,531st entry in the back data (i.e., specified by the 14 highest-order bits), which is in the 6th slice (i.e., determined by the forward 3D position ofthe sample), and the 3,362nd entry (i.e. determined by the 12 lowest-order bits) in the 12th slice (i.e., determined by the slice of the RD sample and the number of slices the animal must travel through during dual support to achieve the specified step length); the fitness of this candidate is 1.67642 x 101\-3 8. The stored sibling samples for the RD and RLU event samples are retrieved and used as the RLD and RU event samples, respectively 9. Animate the highest-fitness candidate by creating an animation curve for each FDOF of the right limb; each curve has six key frames: the FDOF values at RD, RLU, RLD, RU, a FDOF value for mid swing phase to get the pes off the ground 277 (i.e., detennined by simple IK and/or direct posing), and the FDOF value at RD to ensure that the animation is cyclical 10. Create animation curves for the left limb using the same key frames as the right limb but advanced along the animation timeline by 0.5 times the animation time to ensure a 0.5 ipsilateral phase 11. During animation, fix the position/orientation ofthe right pes on the ground between the RD and RLD events and fix the position/orientation of the left pes on the ground between the LD and LRD (i.e., between the RLD and RD) events (see Appendix F) 278 APPENDIX I GLOSSARY 2D: Two Dimensional 3D: Three Dimensional ALife: Artificial Life ANN: Artificial Neural Network BMR: Basic Metabolic Rate COM: Center of Mass DOF: Degree ofFreedom EA: Evolutionary Algorithm FDOF: Functional Degree of Freedom GA: Genetic Algorithm GAGA: Genetic Algorithms Gait Analysis GP: Genetic Programming GRF: Ground Reaction Force 279 GUI: Graphical User Interface IK: Inverse Kinematics KLAW: Keyframe-less Animation of Walking. L-Systems: Lindenmayer Systems LD: Left Down LRD: Left when Right Down LROM: Limb Range of Motion LRU: Left when Right UP LU: Left Up M: Mean PAR: Parameterized Action Representation PD: Proportional Derivative RD: Right Down RLD: Right when Left Down RLU: Right when Left Up RMS: Root Mean Square ROM: Range of Motion RU: Right Up SAN: Sensor Actuator Network SCA: Sense Control Action SD: Standard Deviation 280 SIMM: Software for Interactive Musculoskeletal Modeling SR: Stimulus Response ZMP: Zero Moment Point 281 BIBLIOGRAPHY Alexander, R. M., & Jayes, A. S. (1983). A dynamic similarity hypothesis for the gaits of quadrupedal mammals. Journal ofZoology, London, 201, 135-152. Allbeck, J., & Badler, N. (2002). Toward Representing Agent Behaviors Modified by Personality and Emotion. Proceedings of the First Annual Joint Conference on Autonomous Agents and Multiagent Systems, 202-207. Azevedo, C. (2001). On the Interaction between the Human and The Robot in Bipedal Walking. Proceedings of International Symposium on Mobile, Climbing and Walking Robots-Karlsrhue-Germany. Badler, N., Bindiganavale, R., Bourne, J., Palmer, M., Shi, J., & Schuler, W. (1998). A Parameterized Action Representation for Virtual Human Agents. Workshop on Embodied Conversational Characters. Badler, N., Webber, B., Becket, W., Geib, C., Moore, M., Pelachaud, c., et al. (1995). Planning and parallel transition networks: Animation's new frontiers. Computer Graphics and Applications: Proc. Pacific Graphics, 95, 101-117. Bongard, J. C., & Pfeifer, R. (2002).- A Method for Isolating Morphological Effects on Evolved Behaviour. Proceedings of the Seventh International Conference on the Simulation ofAdaptive Behavior, 305-311. Bruderlin, A., & Calvert, T. W. (1989). Goal-directed, dynamic animation ofhuman walking. Proceedings of the 16th annual conference on Computer graphics and interactive techniques, 233-242. Choi, M. G., Lee, J., & Shin, S. Y. (2003). Planning biped locomotion using motion capture data and probabilistic roadmaps. ACM Transactions on Graphics (TOG), 22(2), 182-203. 282 Chung, S., & Hahn, J. K. (1999). Animation of Human Walking in Virtual Environments. Proceedings ofComputer Animation, 99,4-15. Coombs Jr, W. P. (1978). Theoretical Aspects of Cursorial Adaptations in Dinosaurs. The Quarterly Review ofBiology, 53(4),393-418. Delaney, B. (1998). On the trail of the shadow woman: the mystery of motion capture. Computer Graphics and Applications, IEEE, 18(5), 14-19. Daley, M. A., Felix, G., & Biewener, A. A. (2007). Running stability is enhanced by a proximo-distal gradient in joint neuromechanical control. Journal ofExperimental Biology, 210(Pt 3), 383-394. Delp, S. L., & Loan, 1. P. (1995). A graphics-based software system to develop and analyze models of musculoskeletal structures. Computers in Biology and Medicine, 25(1),21-34. Delp, S. L., & Loan, 1. P. (2000). A computational framework for simulating and analyzing human and animal movement. Computing in Science &Engineering [see also IEEE Computational Science and Engineering}, 2(5), 46-55. Faloutsos, P., van de Panne, M., & Terzopoulos, D. (2001). Composable controllersfor physics-based character animation. New York: ACM Press. Farley, C. T. (1997). Mechanics oflocomotion in lizards. Journal ofExperimental Biology, 200(16),2177-2188. Fotosearch. (2005, May 14). Komodo dragon stock photos and images. Retrieved November 13,2007, from http://www.fotosearch.com/photos-images/komodo­ dragon.htm!. Fotosearch. (2007, March 12). Komodo dragon walking on ground. Retrieved November 21,2007, from http://www.fotosearch.com/DVA002/006-0044. Giang, T., Mooney, R., Peters, C., & O'Sullivan, C. (2000). Real-Time Character Animation Techniques. Image Synthesis Group Trinity College Dublin, Technical Report TCD-CS-2000-06. Golubovic, D., & Hu, H. (2002). A hybrid evolutionary algorithm for gait generation of Sony legged robots. Proceedings of the 28th Annual Conference of the IEEE Industrial Electronics Society, 4,2593- 2598. Goslow, G. E. (1981). Electrical activity and relative length changes of dog limb muscles as a function of speed and gait. Journal ofExperimental Biology, 94(1), 15-42. 283 Griffin, T. M., Main, R. P., & Farley, C. T. (2004). Biomechanics of quadrupedal walking: how do four-legged animals achieve inverted pendulum-like movements? Journal ofExperimental Biology, 207(20), 3545-3558 Gritz, L., & Hahn, J. K. (1997). Genetic Programming Evolution of Controllers for 3-D Character Animation. Genetic Programming 1997: Proceedings of the 2nd Annual Conference, 139-146. Grzeszczuk, R., & Terzopoulos, D. (1995). Automated learning ofmuscle-actuated locomotion through control abstraction. Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, 63-70. Grzeszczuk, R., Terzopoulos, D., & Hinton, G. (1998). Neuroanimator: Fast neural network emulation and control ofphysics-based models. SIGGRAPH 98 Conference Proceedings. Annual Conference Series, 9-20. Henderson, D. M. (2006). Burly gaits: centers ofmass, stability, and the trackways of sauropod dinosaurs. Journal of Vertebrate Paleontology, 26(4),907-921. Herr, H. M., Huang, G. T., & McMahon, T. A. (2002). A model of scale effects in mammalian quadrupedal running. Journal ofExperimental Biology, 205(7),959­ 967. Hildebrand, M. (1980). The Adaptive Significance ofTetrapod Gait Selection. American Zoologist, 20(1),255-267. Hill, A. V. (1938). The Heat of Shortening and the Dynamic Constants ofMuscle. Proceedings of the Royal Society ofLondon. Series B, Biological Sciences, 126(843), 136-195. Hodgins, J. K., Wooten, W. L., Brogan, D. C., & O'Brien, J. F. (1995). Animating human athletics. New York: ACM Press. Holland, 1. H. (1992). Adaptation in natural and artificial systems. Cambridge, MA: MIT Press. Hornby, G. S., & Pollack, J. B. (2001). Body-brain co-evolution using L-systems as a generative encoding. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-200l), 868-875. Hutchinson, 1. R., Anderson, F. C., Blemker, S. S., & Delp, S. L. (2005). Analysis of hindlimb muscle moment arms in Tyrannosaurus rex using a three-dimensional musculoskeletal computer model: implications for stance, gait, and speed. Paleobiology, 31(4),676-701. 284 Hutchinson, J. R., & Gatesy, S. M. (2006). Beyond the bones. Nature(London), 440(7082), 292-294. Ijspeert, A. J., & Arbib, M. (2000). Visual tracking in simulated salamander locomotion. Proceedings ofSAB'OO, From Animals to Animats 6,88-97. Kang, Y. M., Cho, H. G., & Lee, E. T. (1999). An efficient control over human running animation with extension of planar hopper model. Journal ofVisualization and Computer Animation, 10(4),215-224. Koza, J. R. (1990). Genetically breeding populations of computer programs to solveproblems in artificial intelligence. Proceedings of the Second International Conference on Tools for Artificial Intelligence, 819-827. Laszlo, J. F., van de Panne, M., & Fiume, E. (1997). Control of Physically-based Simulated Walking. Proceedings ofIMAGINA, 231-241. Lindenmayer, A. (1968). Mathematical models for cellular interaction in development, Parts I and II. Journal ofTheoretical Biology, 18,280-315. Lindenmayer, A. (1974). Adding Continuous Components to L-Systems. Lecture Notes In Computer Science, 14,53-68. Liu, Z., Gortler, S. J., & Cohen, M. F. (1994). Hierarchical spacetime control. Proceedings of the 21 st annual conference on Computer graphics and interactive techniques, 35-42. Maciel, A., Nedel, L. P., & Dal Sasso Freitas, C. M. (2002). Anatomy-based joint models for virtual human skeletons. Proceedings ofComputer Animation, 2002, 220-224. McKenna, M., & Zeltzer, D. (1990). Dynamic simulation of autonomous legged locomotion. Proceedings of the 17th annual conference on Computer graphics and interactive techniques, 29-38. Muybridge, E. (1887). Animals in motion [1957 reprint). New York: Dover. Ngo, J. T., & Marks, J. (1993). Spacetime constraints revisited. Proceedings of the 20th annual conference on Computer graphics and interactive techniques, 343-350. Perlin, K., & Goldberg, A. (1996). Improv: a system for scripting interactive actors in virtual worlds. Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, 205-216. 285 Piazza, S. 1., & Delp, S. L. (2001). Three-Dimensional Dynamic Simulation ofTotal Knee Replacement Motion During a Step-Up Task. Journal ofBiomechanical Engineering, 123,599-606. Pike, A. V. L., & Alexander, R. M. N. (2002). The relationship between limb-segment proportions and joint kinematics for the hind limbs of quadrupedal mammals. Journal ofZoology, 258(4),427-433. Raibert, M. H., & Hodgins, J. K. (1991). Animation of dynamic legged locomotion. Proceedings ofthe 18th annual conference on Computer graphics and interactive techniques, 349-358. Ray, T. S. (2001). Aesthetically Evolved Virtual Pets. Leonardo, 34(4), 313-316. Reilly, S. M. (1997). Sprawling locomotion in the lizard Sceloporus clarkii: quantitative kinematics ofa walking trot. Journal ofExperimental Biology, 200(4), 753-765. Reilly, S. M. (1998). Locomotion in Alligator mississippiensis: kinematic effects of speed and posture and their relevance to the sprawling-to-erect paradigm. Journal of Experimental Biology, 201(18),2559-2574. Rose, C., Guenter, B., Bodenheimer, B., & Cohen, M. F. (1996). Efficient generation of motion transitions using spacetime constraints. Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, 147-154. Rosenblatt, F. (1958). The perceptron: a probabilistic model for information storage and organization in the brain. Psychological Review, 65(6), 386-408. Sellers, W. 1., Dennis, L. A., Wang, W.-J., & Crompton, R. H. (2004). Evaluating alternative gait strategies using evolutionary robotics. Journal ofAnatomy, 204(5),343-351. Sellers, W. 1., & Manning, P. L. (2007). Estimating dinosaur maximum running speeds using evolutionary robotics. Proceedings ofthe Royal Society B: Biological Sciences, 274(1626),2711-2716. Shaw, L. (2007, July 2). Illustrated Standard of the German Sheppard Dog, The Forehand. Retrieved October 17,2007, from http://www.shawlein.com/The_Standard/02_The_Forehand/The_Forehand.html Shaw, L. (2007, July 2). Illustrated Standard of the German Sheppard Dog, The Hindquarters. Retrieved October 17,2007, from http://www.shawlein.com/The_Standard/05_The_Hindquarters/The_Hindquarters .html 286 Sims, K. (1991). Artificial Evolution for Computer Graphics. Computer Graphics, 253(4),319-328. Sims, K. (1994a). Evolving 3D Morphology and Behavior by Competition. Artificial Life, 1(4),353-372. Sims, K. (1994b). Evolving virtual creatures. Proceedings of the 21st annual conference on Computer graphics and interactive techniques, 15-22. Stevens, K. (2007, November 25). Apatosaurus. Retrieved November 28, 2007, from http://www.cs.uoregon.edu/~kent/paleontology /Apatosaurus/2005/index.html Stevens, K. (2007, November 25). Triceratops. Retrieved November 28,2007, from http://www.cs.uoregon.edu/~kent/paleontology/Triceratops/index.html Stevens, K. (2007, November 25). Tyrannosaurus. Retrieved November 28, 2007, from http://www.cs.uoregon.edu/~kent/paleontology/Tyrannosaurus/index.html Stevens, K. A., Larson, P., Wills, E. D., & Andersen, A. (2008). Rex, sit: Digital modeling of Tyrannosaurus rex at rest. In P. Larson & K. Carpenter (Eds.), Tyrannosaurus rex: The tyrant king. Bloomington, IN: Indiana University Press. Sun, H. C., & Metaxas, D. N. (2001). Automating gait generation. Proceedings of the 28th annual conference on Computer graphics and interactive techniques, 261­ 270. Taylor, T. (2000). Artificial life techniques for generating controllers for physically modelled characters. Proceedings of the First International Conference on Intelligent Games and Simulation (GAME-ON 2000). . Thompson, S., & Holmes, R. (2007). Forelime stance and step cycle in Chasmosaurus Irvinensis (Dinosaurua: Neoceratopsia). Palaeo-Electronica(10.1.5A). Tolani, D., Goswami, A., & Badler, N. 1. (2000). Real-time inverse kinematics techniques for anthropomorphic limbs. Graphical Models, 62(5),353-388. Torkos, N., & van de Panne, M. (1998). Footprint--based Quadruped Motion Synthesis. Graphics Interface, 151-160. van de Panne, M. (2000). Control for simulated human and animal motion. IFAC Annual Reviews in Control(24), 189-199. van de Panne, M., & Fiume, E. (1993). Sensor-actuator networks. Proceedings of SIGGRAPH, 93, 335-342. 287 Vukobratovic, M., & Juricic, D. (1969). Contribution to the synthesis of biped gait. IEEE Trans Biomed Eng, 16(1), 1-6. Witkin, A., & Kass, M. (1988). Spacetime constraints. Proceedings of the 15th annual conference on Computer graphics and interactive techniques, 159-168. Wolff, K., & Nordin, P. (2003). Learning biped locomotion from first principles on a simulated humanoid robot using linear genetic programming. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2003), 12-16. Wright, A. H. (1991). Genetic algorithms for real parameter optimization. Foundations of Genetic Algorithms, 1, 205-218. Wyeth, G. K., & Yik, D. T. F. (2003). Evolving a locus based gait for a humanoid robot. IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2003), 2, 1638-1643. Zhang, R., & Vadakkepat, P. (2003). An evolutionary algorithm for trajectory based gait generation of biped robot. Proceedings of the International Conference on Computational Intelligence, Robotics and Autonomous Systems.