Motion Planning for Humanoid Robots (eBook)

Kensuke Harada received M.E. and Ph.D degrees in Mechanical Engineering from the Graduate School of Engineering, Kyoto University, in 1994 and 1997, respectively. After being employed as a research associate at Hiroshima University, he joined the National Institute of Advanced Industrial Science and Technology (AIST) in 2002. He spent a year, from November 2005 to November 2006, as a visiting scholar at Stanford University's Computer Science Department. In 2001 he was awarded the IEEE ISATP Outstanding Paper Award and in 2004 he received the IEEE ICRA Best Video Award. Eiichi Yoshida received M.E and Ph.D degrees in Precision Machinery Engineering from the Graduate School of Engineering, the University of Tokyo in 1993 and 1996, respectively. In 1996 he joined the former Mechanical Engineering Laboratory, now the National Institute of Advanced Industrial Science and Technology (AIST), Tsukuba, Japan. From 1990 to 1991, he was a visiting research associate at the Swiss Federal Institute of Technology at Lausanne (EPFL). He served as co-director of AIST/IS-CNRS/ST2I Joint French-Japanese Robotics Laboratory (JRL) at LAAS-CNRS, Toulouse, France, from 2004 to 2008. He is currently co-director of CNRS-AIST JRL (Joint Robotics Laboratory), UMI3218/CRT, AIST, Japan, since 2009. His research interests include robot task and motion planning, modular robotic systems, and humanoid robots. Kazuhito Yokoi is the leader of the Humanoid Research Group and deputy director of the Intelligent Systems Research Institute at AIST. He received his BE degree in Mechanical Engineering from the Nagoya Institute of Technology in 1984, and his ME and PhD degrees in Mechanical Engineering Science from the Tokyo Institute of Technology in 1986 and 1994, respectively. In 1986, he joined the Mechanical Engineering Laboratory, Ministry of International Trade and Industry. He is also a member of CNRS-AIST JRL, UMI3218/CRT and an adjunct professor at the Cooperative Graduate School of the University of Tsukuba. From November 1994 to October 1995, he was a visiting scholar at the Robotics Laboratory in Stanford University's Computer Science Department. His research interests include humanoids and human-centered robotics.

Preface 5
Contents 7
List of Contributors 13
1 Navigation and Gait Planning 16
1.1 Introduction 16
1.1.1 Navigation Planning 17
1.1.2 Navigation and Legs 18
1.2 Dimensionality Reductions 19
1.3 Contact Forces and Hybrid Dynamics 20
1.4 Stance Connectivity 22
1.5 Terrain Evaluation 23
1.6 A Simple Example 24
1.6.1 Environment Representation 25
1.6.2 The State Space 25
1.6.3 The Action Model 26
1.6.4 The State–Action Evaluation Function 26
1.6.4.1 Location Metrics 27
1.6.4.2 Step Cost 30
1.6.5 Using the Simple Planner 31
1.7 Estimated Cost Heuristic 34
1.8 Limited-time and Tiered Planning 37
1.9 Adaptive Actions 38
1.9.1 Adaptation Algorithm 40
1.10 Robot and Environment Dynamics 42
1.11 Summary 42
References 43
2 Compliant Control of Whole-body Multi-contact Behaviors in Humanoid Robots 44
2.1 Introduction 44
2.2 Modeling Humanoids Under Multi-contact Constraints 46
2.2.1 Kinematic and Dynamic Models 47
2.2.2 Task Kinematics and Dynamics Under Supporting Constraints 51
2.2.3 Modeling of Contact Centers of Pressure, Internal Forces, and CoM Behavior 53
2.2.4 Friction Boundaries for Planning CoM and Internal Force Behaviors 57
2.3 Prioritized Whole-body Torque Control 59
2.3.1 Representation of Whole-body Skills 60
2.3.2 Prioritized Torque Control 61
2.3.3 Real-time Handling of Dynamic Constraints 63
2.3.4 Task Feasibility 67
2.3.5 Control of Contact Centers of Pressure and Internal Tensions/Moments 67
2.4 Simulation Results 70
2.4.1 Multi-contact Behavior 70
2.4.2 Real-time Response to Dynamic Constraints 73
2.4.3 Dual Arm Manipulation 74
2.5 Conclusion and Discussion 77
References 78
3 Whole-body Motion Planning – Building Blocks for Intelligent Systems 82
3.1 Introduction 82
3.2 Models for Movement Control and Planning 83
3.2.1 Control System 84
3.2.1.1 Task Kinematics 85
3.2.1.2 Null Space Control 88
3.2.2 Trajectory Generation 90
3.2.3 Task Relaxation: Displacement Intervals 91
3.3 Stance Point Planning 93
3.4 Prediction and Action Selection 95
3.4.1 Visual Perception 96
3.4.2 Behavior System 96
3.4.3 Experiments 98
3.5 Trajectory Optimization 98
3.6 Planning Reaching and Grasping 101
3.6.1 Acquisition of Task Maps for Grasping 104
3.6.2 Integration into Optimization Procedure 105
3.6.3 Experiments 107
3.7 Conclusion 109
References 110
4 Planning Whole-body Humanoid Locomotion, Reaching, and Manipulation 114
4.1 Introduction 114
4.1.1 Basic Motion Planning Methods 115
4.1.2 Hardware and Software Platform 116
4.2 Collision-free Locomotion: Iterative Two-stage Approach 117
4.2.1 Two-stage Planning Framework 118
4.2.2 Second Stage: Smooth Path Reshaping 119
4.3 Reaching: Generalized Inverse Kinematic Approach 121
4.3.1 Method Overview 123
4.3.2 Generalized Inverse Kinematics for Whole-body Motion 125
4.3.2.1 Inverse Kinematics for Prioritized Tasks 125
4.3.2.2 Monitoring Task Execution Criteria 125
4.3.2.3 Support Polygon Reshaping 126
4.3.3 Results 126
4.4 Manipulation: Pivoting a Large Object 127
4.4.1 Pivoting and Small-time Controllability 128
4.4.2 Collision-free pivoting sequence planning 129
4.4.3 Whole-body Motion Generation and Experiments 131
4.4.4 Regrasp Planning 134
4.5 Motion in Real World: Integrating with Perception 136
4.5.1 Object Recognition and Localization 136
4.5.2 Coupling the Motion Planner with Perception 137
4.5.3 Experiments 139
4.6 Conclusion 141
References 141
5 Efficient Motion and Grasp Planning for Humanoid Robots 144
5.1 Introduction 144
5.1.1 RRT-based Planning 145
5.1.2 The Motion Planning Framework 145
5.2 Collision Checks and Distance Calculations 146
5.3 Weighted Sampling 147
5.4 Planning Grasping Motions 149
5.4.1 Predefined Grasps 150
5.4.2 Randomized IK-solver 150
5.4.2.1 Reachability Space 151
5.4.2.2 A 10 DoF IK-solver for Armar-III 152
5.4.3 RRT-based Planning of Grasping Motions with a Set of Grasps 153
5.4.3.1 J+-RRT 153
5.4.3.2 A Workspace Metric for the Nearest Neighbor Search 155
5.4.3.3 IK-RRT 156
5.5 Dual Arm Motion Planning for Re-grasping 158
5.5.1 Dual Arm IK-solver 158
5.5.2 Reachability Space 158
5.5.3 Gradient Descent in Reachability Space 158
5.5.4 Dual Arm J+-RRT 160
5.5.5 Dual Arm IK-RRT 161
5.5.6 Planning Hand-off Motions for Two Robots 162
5.5.7 Experiment on ARMAR-III 163
5.6 Adaptive Planning 163
5.6.1 Adaptively Changing the Complexity for Planning 164
5.6.2 A 3D Example 164
5.6.3 Adaptive Planning for ARMAR-III 165
5.6.3.1 Kinematic Subsystems 165
5.6.3.2 The Approach 166
5.6.4 Extensions to Improve the Planning Performance 168
5.6.4.1 Randomly Extending Good Ranked Configurations 168
5.6.4.2 Bi-planning 168
5.6.4.3 Focusing the Search on the Area of Interest 169
5.6.5 Experiments 169
5.6.5.1 Unidirectional Planning 170
5.6.5.2 Bi-directional Planning 172
5.7 Conclusion 172
References 174
6 Multi-contact Acyclic Motion Planning and Experiments on HRP-2 Humanoid 176
6.1 Introduction 176
6.2 Overview of the Planner 178
6.3 Posture Generator 179
6.4 Contact Planning 182
6.4.1 Set of Contacts Generation 183
6.4.2 Rough Trajectory 184
6.4.3 Using Global Potential Field as Local Optimization Criterion 186
6.5 Simulation Scenarios 187
6.6 Experimentation on HRP-2 191
6.7 Conclusion 192
References 193
7 Motion Planning for a Humanoid Robot Based on a Biped Walking Pattern Generator 196
7.1 Introduction 196
7.2 Gait Generation Method 197
7.2.1 Analytical-solution-based Approach 198
7.2.2 Online Gait Generation 199
7.2.3 Experiment 201
7.3 Whole-body Motion Planning 202
7.3.1 Definitions 202
7.3.2 Walking Pattern Generation 203
7.3.3 Collision-free Motion Planner 203
7.3.4 Results 205
7.4 Simultaneous Foot-place/Whole-body Motion Planning 207
7.4.1 Definitions 208
7.4.2 Gait Pattern Generation 209
7.4.3 Overall Algorithm 209
7.4.4 Experiment 211
7.5 Whole-body Manipulation 212
7.5.1 Motion Modification 213
7.5.2 Force-controlled Pushing Manipulation 214
7.6 Conclusion 215
References 216
8 Autonomous Manipulation of Movable Obstacles 220
8.1 Introduction 220
8.1.1 Planning Challenges 221
8.1.2 Operators 222
8.1.3 Action Spaces 222
8.1.4 Complexity of Search 224
8.2 NAMO Planning 226
8.2.1 Overview 226
8.2.2 Configuration Space 226
8.2.3 Goals for Navigation 228
8.2.4 Goals for Manipulation 229
8.2.5 Planning as Graph Search 230
8.2.5.1 Linear Problems 231
8.2.5.2 Local Manipulation Search 232
8.2.5.3 Connecting Free Space 232
8.2.5.4 Analysis 233
8.2.5.5 Challenges of CONNECTFS 235
8.2.6 Planner Prototype 235
8.2.6.1 Relaxed Constraint Heuristic 236
8.2.6.2 High-level Planner 238
8.2.6.3 Examples and Experimental Results 238
8.2.6.4 Analysis 240
8.2.7 Summary 243
8.3 Humanoid Manipulation 243
8.3.1 Background 244
8.3.2 Biped Control with External Forces 245
8.3.2.1 Decoupled Positioning 245
8.3.2.2 Trajectory Generation 246
8.3.2.3 Online Feedback 248
8.3.3 Modeling Object Dynamics 248
8.3.3.1 Motivation for Learning Models 248
8.3.3.2 Modeling Method 249
8.3.4 Experiments and Results 250
8.3.4.1 Prediction Accuracy 251
8.3.4.2 System Stability 251
8.3.5 Summary 252
8.4 System Integration 253
8.4.1 From Planning to Execution 253
8.4.2 Measurement 255
8.4.2.1 Object Mesh Modeling 255
8.4.2.2 Recognition and Localization 255
8.4.3 Planning 257
8.4.3.1 Configuration Space 257
8.4.3.2 Contact Selection 258
8.4.3.3 Action Spaces 259
8.4.4 Uncertainty 260
8.4.4.1 Impedance Control 260
8.4.4.2 Replanning Walking Paths 261
8.4.4.3 Guarded Grasping 261
8.4.5 Results 262
References 262
9 Multi-modal Motion Planning for Precision Pushing on a Humanoid Robot 266
9.1 Introduction 266
9.2 Background 268
9.2.1 Pushing 268
9.2.2 Multi-modal Planning 269
9.2.3 Complexity and Completeness 270
9.3 Problem Definition 271
9.3.1 Configuration Space 271
9.3.2 Modes 272
9.3.3 Transitions 273
9.4 Single-mode Motion Planning 274
9.4.1 Collision Checking 274
9.4.2 Walk Planning 274
9.4.3 Reach Planning 275
9.4.4 Push Planning 275
9.4.4.1 Stable Push Dynamics 275
9.4.4.2 Inverse Kinematics 276
9.5 Multi-modal Planning with Random-MMP 278
9.5.1 Effects of the Expansion Strategy 279
9.5.2 Blind Expansion 280
9.5.3 Utility computation 280
9.5.4 Utility-centered Expansion 282
9.5.5 Experimental Comparison of Expansion Strategies 282
9.6 Postprocessing and System Integration 283
9.6.1 Visual Sensing 283
9.6.2 Execution of Walking Trajectories 284
9.6.3 Smooth Execution of Reach Trajectories 284
9.6.3.1 Time-optimal Joint Trajectories 285
9.6.3.2 Univariate Time-optimal Trajectories 285
9.6.3.3 Acceleration-optimal Trajectories 286
9.7 Experiments 287
9.7.1 Simulation Experiments 287
9.7.2 Experiments on ASIMO 288
9.8 Conclusion 289
References 289
10 A Motion Planning Framework for Skill Coordination and Learning 292
10.1 Introduction 292
10.1.1 Related Work 294
10.1.1.1 Multi-modal Planning 295
10.1.1.2 Learning for Motion Planning 295
10.1.2 Framework Overview 296
10.2 Motion Skills 297
10.2.1 Reaching Skill 299
10.2.2 Stepping Skill 300
10.2.3 Balance Skill 301
10.2.4 Other Skills and Extensions 301
10.3 Multi-skill Planning 302
10.3.1 Algorithm Details 303
10.3.2 Results and Discussion 305
10.4 Learning 307
10.4.1 A Similarity Metric for Reaching Tasks 308
10.4.2 Learning Reaching Strategies 309
10.4.3 Learning Constraints from Imitation 310
10.4.3.1 Detection of Instantaneous Constraints 313
10.4.3.2 Merging Transformations 314
10.4.3.3 Computing the Thresholds 314
10.4.3.4 Reusing Detected Constraints in New Tasks 315
10.4.4 Results and Discussion 316
10.5 Conclusion 317
References 317