Motion planning for digital actors Mylène Campana To cite this version: Mylène Campana. Motion planning for digital actors. Robotics [cs.RO]. Université Paul Sabatier - Toulouse III, 2017. English. ￿NNT: 2017TOU30097￿. ￿tel-01591472v2￿ HAL Id: tel-01591472 https://hal.laas.fr/tel-01591472v2 Submitted on 23 Oct 2018 HAL is a multi-disciplinary open access L’archive ouverte pluridisciplinaire HAL, est archive for the deposit and dissemination of sci- destinée au dépôt et à la diffusion de documents entific research documents, whether they are pub- scientifiques de niveau recherche, publiés ou non, lished or not. The documents may come from émanant des établissements d’enseignement et de teaching and research institutions in France or recherche français ou étrangers, des laboratoires abroad, or from public or private research centers. publics ou privés. TTHHÈÈSSEE En vue de l’obtention du DOCTORAT DE L’UNIVERSITÉ FÉDÉRALE TOULOUSE MIDI-PYRÉNÉES Délivré par : l’Université Toulouse 3 Paul Sabatier (UT3 Paul Sabatier) Discipline ou Spécialité : Robotique Présentée et soutenue le 07/07/2017 par : Mylène CAMPANA MOTION PLANNING FOR DIGITAL ACTORS JURY Jean-Paul LAUMOND Directeur de recherche Directeur de thèse Katsu YAMANE Senior Researcher Rapporteur Lionel REVERET Directeur de Recherche Rapporteur Marilena VENDITTELLI Associate Professor Membre du jury Juan CORTÉS Directeur de Recherche Président du jury École doctorale et spécialité : EDSYS : Robotique 4200046 Unité de Recherche : Laboratoire d’analyse et d’architecture des systèmes (LAAS) Directeur de Thèse : Jean-Paul LAUMOND Rapporteurs : Katsu YAMANE et Lionel REVERET i Acknowledgement Firstly,IwouldliketothankmythesisdirectorJean-PaulLaumondwhohasguided andadvisedmeallalongthethesis. Hissupport,rigorandteachingskillshelpedme to discover multiple problems and to address them in a pleasant way. I also thank the people who worked with me and made us achieve our publications: Florent Lamiraux, Pierre Fernbach, Steve Tonneau and Michel Taïx. Secondly, I thank all my mates of Gepetto who really cheered me up during these three years: Maximilien, Mathieu, Alexis, Christian, François, Kevin, Nemo, Galo, Joseph, Guilhem, Naoko, Ganesh, Robert, Justin, Andrea, Dinesh, Rohan, Céline and the Barbus. Finally,Ithankmyfamilyfortrustingmetoachievethisdegree,andparticularly my partner Gurvan for advising me and sharing my life while making this work possible. Contents 1 Introduction 1 1.1 Context . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Plan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.4 Related publications . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2 Problem statement and notations 5 2.1 Problem statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Sampling-based motion planning . . . . . . . . . . . . . . . . . . . . 6 2.3 Numerical path optimization techniques . . . . . . . . . . . . . . . . 7 2.4 Path planner software . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.5 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.5.1 Kinematic chain . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.5.2 Operations on configurations and vectors . . . . . . . . . . . 10 2.5.3 Straight interpolation . . . . . . . . . . . . . . . . . . . . . . 11 3 A gradient-based path optimization method for motion planning 13 3.1 Motivations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.2 Problem definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.2.1 Optimization variables . . . . . . . . . . . . . . . . . . . . . . 16 3.2.2 Cost . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.3 Unconstrained resolution . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.4 Linear constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.4.1 New constraint . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.4.2 Linearized constraint computation . . . . . . . . . . . . . . . 20 3.5 Convergence analysis and algorithm refinement . . . . . . . . . . . . 20 3.5.1 Geometrical representation of the dependency between linear constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.5.2 Algorithm refinement . . . . . . . . . . . . . . . . . . . . . . 23 3.6 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.7 Results. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.7.1 From 2D basic examples . . . . . . . . . . . . . . . . . . . . . 26 3.7.2 To 3D complex problems . . . . . . . . . . . . . . . . . . . . 27 3.8 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4 Jumping in robotics and computer animation 37 4.1 Jumping robots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.2 Motion planning techniques and data driven animation . . . . . . . . 38 4.3 Physics-based motion synthesis . . . . . . . . . . . . . . . . . . . . . 40 4.4 Related work analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 42 iv Contents 5 Ballistic motion planning for a point-mass 43 5.1 Problem statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 5.2 Unconstrained ballistic motion . . . . . . . . . . . . . . . . . . . . . 44 5.2.1 Accessible space of ballistic motion . . . . . . . . . . . . . . . 44 5.2.2 Goal-oriented ballistic motion . . . . . . . . . . . . . . . . . . 46 5.3 Ballistic motion with constraints . . . . . . . . . . . . . . . . . . . . 47 5.3.1 Non-sliding constraints . . . . . . . . . . . . . . . . . . . . . . 47 5.3.2 Constraint formulation . . . . . . . . . . . . . . . . . . . . . . 50 5.3.3 Velocity constraints . . . . . . . . . . . . . . . . . . . . . . . 50 5.3.4 Constraint collection and solution existence . . . . . . . . . . 51 5.4 Motion planning algorithm . . . . . . . . . . . . . . . . . . . . . . . 53 5.4.1 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 5.4.2 Probabilistic convergence study . . . . . . . . . . . . . . . . . 55 5.5 Results. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 5.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 6 Ballistic motion planning for jumping superheroes 61 6.1 Problem statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 6.2 Non-slipping constraint for an arbitrary number of contacts . . . . . 62 6.3 A reduced character model for contact location estimation . . . . . . 64 6.4 Motion planning algorithm for the reduced model . . . . . . . . . . . 66 6.5 Motion synthesis for wholebody animation . . . . . . . . . . . . . . . 69 6.5.1 Computation of wholebody contact configurations, and iden- tification of takeoff and landing phases . . . . . . . . . . . . . 70 6.5.2 Wholebody animation of the jump trajectory . . . . . . . . . 72 6.6 Simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 6.6.1 Qualitative results . . . . . . . . . . . . . . . . . . . . . . . . 74 6.6.2 Time performances . . . . . . . . . . . . . . . . . . . . . . . . 78 6.7 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 7 Conclusion 81 7.1 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 7.2 Limits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 7.3 Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 A Appendix: Computation details of intersections 85 A.1 Intersection between a cone and a vertical plane . . . . . . . . . . . 85 A.2 Intersection between a convex sum of cones and a vertical plane . . . 88 B Appendix: Rotation effect 94 C Preliminary work: angular momentum feasibility study 97 Bibliography 99 Chapter 1 Introduction 1.1 Context For six decades, robotics methods have improved the automation of motion gener- ation [Chapuis 1949]. Robots are able to repeatably execute motions requiring an important accuracy. Besides, depending on their design, their motions can surpass the average human limits. Due to the complexity of tasks and environments, robot motions have initially been manually generated by human operators. However, the riseoftheartificialintelligenceandoptimizationtoolshasinvertedthistrendinthe thirty last years. Planning offers the possibility of returning a trajectory reaching a desired configuration and complying with constraints. Most planners now only require some user-defined specifications and modeling of the environment to avoid collisions. In these specifications, optimization criteria can be provided to improve thetrajectory, duringplanningorafterwards. Thisthesisexposes, forinstance, how the length of a planned path can be reduced while avoiding collisions. Computer graphics has also benefited from the advances of artificial intelligence and automation. Large sets of motion capabilities are necessary to autonomously evolve in various environments: walking, running, climbing, jumping, falling etc. Instead of designing character trajectories by hand (see Figure 1.1), or relying on motion capture systems (as commonly seen for animation movies or video games), new possibilities have appeared to synthesize them. Physics-based assumptions or motion capture poses bring the necessary constraints to guide motions and make them plausible to the user. If a motion appears as unrealistic or if collisions occur, the immersion in the animation is altered. Combining the autonomy of motion planning and animation-based constraints constitutes the heart of the second con- tribution of this thesis. Figure 1.1: Example of a manually designed trajectory for animation, with key-postures. c Autodesk Maya (cid:13) 2 Chapter 1. Introduction 1.2 Contributions This thesis provides two main contributions to motion planning applications in arbitrary environments: Contribution 1: We propose a path-optimization method that reduces the path length of random planner outputs. The method lies in a trade-off between simplic- ity, computation efficiency and adaptation to the environment modeling. Without neither prior knowledge nor pre-processing of both robot and environment, the method optimizes path length with a gradient-based algorithm while constraining the path with constraints defined in the task space. We demonstrate that this method is more efficient to improve paths in some situations compared to random shortcuts. Contribution 2: We present an original method that returns ballistic motions for a jumping character in an arbitrary environment. For computational efficiency, the character shape is simplified during the planning step. There is no air drag assumption so the ballistic path is supported by a parabola. Physics-based con- straints are considered to make the ballistic trajectory realistic. Then, the sequence of jumps is built with a probabilistic planner. Based on the simplified character shape,contactgenerationbetweenjumpsisconducted. Finally,key-framespostures guide the wholebody motion interpolation and re-planning toward a plausible and collision-free motion. 1.3 Plan The thesis firstly addresses the path optimization contribution. Brief motion plan- ning and path optimization states of the art are given in Chapter 2. We also introduce there the motion planning library in which our algorithms were imple- mented. Then, Chapter 3 presents the path-optimizer motivations, framework and results. Focus is made on convergence analysis and parameter tuning. The manuscript secondly tackles the ballistic motion planner contribution. Re- lated works on jumping in robotics and computer animation are discussed in Chap- ter 4. Then the planner is described in two steps, corresponding respectively to Chapters 5 and 6. First, we address the notion of constrained ballistic path for a point-mass. We implement it in a basic motion planner and provide simulations. Next, we extend this planner to a wholebody ballistic motion planner, considering contact phases and flight animations. We conclude on simulations with various characters and environments. Discussions on the thesis contributions are reminded and perspectives for future work are finally given in Chapter 7. 1.4. Related publications 3 1.4 Related publications Journal article: - Mylène Campana, Florent Lamiraux and Jean-Paul Laumond, A gradient- based path optimization method for motion planning, Advanced Robotics Journal, Special Issue on Recent Advancements on Industrial Robot Technology, 2016. International conference proceedings with review committee: - Mylène Campana and Jean-Paul Laumond, Ballistic motion planning, IEEE/RSJIntelligentRobotsandSystemsConference(IROS),2016. Finalist of the Best Paper Award on Safety Security and Rescue in Robotics. - Mylène Campana, Pierre Fernbach, Steve Tonneau, Michel Taïx and Jean- Paul Laumond, Ballistic motion planning for jumping superheroes, Motion in Games Conference (MIG), 2016. - Joseph Mirabel, Steve Tonneau, Pierre Fernbach, Anna-Kaarina Seppälä, Mylène Campana, Nicolas Mansard and Florent Lamiraux, HPP: a new software for constrained motion planning,IEEE/RSJIntelligentRobots and Systems Conference (IROS), 2016.