Motion Planning for Humanoid Robots

Preface
Contents
List of Contributors
1 Navigation and Gait Planning
	1.1 Introduction
		1.1.1 Navigation Planning
		1.1.2 Navigation and Legs
	1.2 Dimensionality Reductions
	1.3 Contact Forces and Hybrid Dynamics
	1.4 Stance Connectivity
	1.5 Terrain Evaluation
	1.6 A Simple Example
		1.6.1 Environment Representation
		1.6.2 The State Space
		1.6.3 The Action Model
		1.6.4 The State–Action Evaluation Function
			1.6.4.1 Location Metrics
			1.6.4.2 Step Cost
		1.6.5 Using the Simple Planner
	1.7 Estimated Cost Heuristic
	1.8 Limited-time and Tiered Planning
	1.9 Adaptive Actions
		1.9.1 Adaptation Algorithm
	1.10 Robot and Environment Dynamics
	1.11 Summary
	References
2 Compliant Control of Whole-body Multi-contact Behaviors in Humanoid Robots
	2.1 Introduction
	2.2 Modeling Humanoids Under Multi-contact Constraints
		2.2.1 Kinematic and Dynamic Models
		2.2.2 Task Kinematics and Dynamics Under Supporting Constraints
		2.2.3 Modeling of Contact Centers of Pressure, Internal Forces, and CoM Behavior
		2.2.4 Friction Boundaries for Planning CoM and Internal Force Behaviors
	2.3 Prioritized Whole-body Torque Control
		2.3.1 Representation of Whole-body Skills
		2.3.2 Prioritized Torque Control
		2.3.3 Real-time Handling of Dynamic Constraints
		2.3.4 Task Feasibility
		2.3.5 Control of Contact Centers of Pressure and Internal Tensions/Moments
	2.4 Simulation Results
		2.4.1 Multi-contact Behavior
		2.4.2 Real-time Response to Dynamic Constraints
		2.4.3 Dual Arm Manipulation
	2.5 Conclusion and Discussion
	References
3 Whole-body Motion Planning – Building Blocks for Intelligent Systems
	3.1 Introduction
	3.2 Models for Movement Control and Planning
		3.2.1 Control System
			3.2.1.1 Task Kinematics
			3.2.1.2 Null Space Control
		3.2.2 Trajectory Generation
		3.2.3 Task Relaxation: Displacement Intervals
	3.3 Stance Point Planning
	3.4 Prediction and Action Selection
		3.4.1 Visual Perception
		3.4.2 Behavior System
		3.4.3 Experiments
	3.5 Trajectory Optimization
	3.6 Planning Reaching and Grasping
		3.6.1 Acquisition of Task Maps for Grasping
		3.6.2 Integration into Optimization Procedure
		3.6.3 Experiments
	3.7 Conclusion
	References
4 Planning Whole-body Humanoid Locomotion, Reaching, and Manipulation
	4.1 Introduction
		4.1.1 Basic Motion Planning Methods
		4.1.2 Hardware and Software Platform
	4.2 Collision-free Locomotion: Iterative Two-stage Approach
		4.2.1 Two-stage Planning Framework
		4.2.2 Second Stage: Smooth Path Reshaping
	4.3 Reaching: Generalized Inverse Kinematic Approach
		4.3.1 Method Overview
		4.3.2 Generalized Inverse Kinematics for Whole-body Motion
			4.3.2.1 Inverse Kinematics for Prioritized Tasks
			4.3.2.2 Monitoring Task Execution Criteria
			4.3.2.3 Support Polygon Reshaping
		4.3.3 Results
	4.4 Manipulation: Pivoting a Large Object
		4.4.1 Pivoting and Small-time Controllability
		4.4.2 Collision-free pivoting sequence planning
		4.4.3 Whole-body Motion Generation and Experiments
		4.4.4 Regrasp Planning
	4.5 Motion in Real World: Integrating with Perception
		4.5.1 Object Recognition and Localization
		4.5.2 Coupling the Motion Planner with Perception
		4.5.3 Experiments
	4.6 Conclusion
	References
5 Efficient Motion and Grasp Planning for Humanoid Robots
	5.1 Introduction
		5.1.1 RRT-based Planning
		5.1.2 The Motion Planning Framework
	5.2 Collision Checks and Distance Calculations
	5.3 Weighted Sampling
	5.4 Planning Grasping Motions
		5.4.1 Predefined Grasps
		5.4.2 Randomized IK-solver
			5.4.2.1 Reachability Space
			5.4.2.2 A 10 DoF IK-solver for Armar-III
		5.4.3 RRT-based Planning of Grasping Motions with a Set of Grasps
			5.4.3.1 J+-RRT
			5.4.3.2 A Workspace Metric for the Nearest Neighbor Search
			5.4.3.3 IK-RRT
	5.5 Dual Arm Motion Planning for Re-grasping
		5.5.1 Dual Arm IK-solver
		5.5.2 Reachability Space
		5.5.3 Gradient Descent in Reachability Space
		5.5.4 Dual Arm J+-RRT
		5.5.5 Dual Arm IK-RRT
		5.5.6 Planning Hand-off Motions for Two Robots
		5.5.7 Experiment on ARMAR-III
	5.6 Adaptive Planning
		5.6.1 Adaptively Changing the Complexity for Planning
		5.6.2 A 3D Example
		5.6.3 Adaptive Planning for ARMAR-III
			5.6.3.1 Kinematic Subsystems
			5.6.3.2 The Approach
		5.6.4 Extensions to Improve the Planning Performance
			5.6.4.1 Randomly Extending Good Ranked Configurations
			5.6.4.2 Bi-planning
			5.6.4.3 Focusing the Search on the Area of Interest
		5.6.5 Experiments
			5.6.5.1 Unidirectional Planning
			5.6.5.2 Bi-directional Planning
	5.7 Conclusion
	References
6 Multi-contact Acyclic Motion Planning and Experiments on HRP-2 Humanoid
	6.1 Introduction
	6.2 Overview of the Planner
	6.3 Posture Generator
	6.4 Contact Planning
		6.4.1 Set of Contacts Generation
		6.4.2 Rough Trajectory
		6.4.3 Using Global Potential Field as Local Optimization Criterion
	6.5 Simulation Scenarios
	6.6 Experimentation on HRP-2
	6.7 Conclusion
	References
7 Motion Planning for a Humanoid Robot Based on a Biped Walking Pattern Generator
	7.1 Introduction
	7.2 Gait Generation Method
		7.2.1 Analytical-solution-based Approach
		7.2.2 Online Gait Generation
		7.2.3 Experiment
	7.3 Whole-body Motion Planning
		7.3.1 Definitions
		7.3.2 Walking Pattern Generation
		7.3.3 Collision-free Motion Planner
		7.3.4 Results
	7.4 Simultaneous Foot-place/Whole-body Motion Planning
		7.4.1 Definitions
		7.4.2 Gait Pattern Generation
		7.4.3 Overall Algorithm
		7.4.4 Experiment
	7.5 Whole-body Manipulation
		7.5.1 Motion Modification
		7.5.2 Force-controlled Pushing Manipulation
	7.6 Conclusion
	References
8 Autonomous Manipulation of Movable Obstacles
	8.1 Introduction
		8.1.1 Planning Challenges
		8.1.2 Operators
		8.1.3 Action Spaces
		8.1.4 Complexity of Search
	8.2 NAMO Planning
		8.2.1 Overview
		8.2.2 Configuration Space
		8.2.3 Goals for Navigation
		8.2.4 Goals for Manipulation
		8.2.5 Planning as Graph Search
			8.2.5.1 Linear Problems
			8.2.5.2 Local Manipulation Search
			8.2.5.3 Connecting Free Space
			8.2.5.4 Analysis
			8.2.5.5 Challenges of CONNECTFS
		8.2.6 Planner Prototype
			8.2.6.1 Relaxed Constraint Heuristic
			8.2.6.2 High-level Planner
			8.2.6.3 Examples and Experimental Results
			8.2.6.4 Analysis
		8.2.7 Summary
	8.3 Humanoid Manipulation
		8.3.1 Background
		8.3.2 Biped Control with External Forces
			8.3.2.1 Decoupled Positioning
			8.3.2.2 Trajectory Generation
			8.3.2.3 Online Feedback
		8.3.3 Modeling Object Dynamics
			8.3.3.1 Motivation for Learning Models
			8.3.3.2 Modeling Method
		8.3.4 Experiments and Results
			8.3.4.1 Prediction Accuracy
			8.3.4.2 System Stability
		8.3.5 Summary
	8.4 System Integration
		8.4.1 From Planning to Execution
		8.4.2 Measurement
			8.4.2.1 Object Mesh Modeling
			8.4.2.2 Recognition and Localization
		8.4.3 Planning
			8.4.3.1 Configuration Space
			8.4.3.2 Contact Selection
			8.4.3.3 Action Spaces
		8.4.4 Uncertainty
			8.4.4.1 Impedance Control
			8.4.4.2 Replanning Walking Paths
			8.4.4.3 Guarded Grasping
		8.4.5 Results
	References
9 Multi-modal Motion Planning for Precision Pushing on a Humanoid Robot
	9.1 Introduction
	9.2 Background
		9.2.1 Pushing
		9.2.2 Multi-modal Planning
		9.2.3 Complexity and Completeness
	9.3 Problem Definition
		9.3.1 Configuration Space
		9.3.2 Modes
		9.3.3 Transitions
	9.4 Single-mode Motion Planning
		9.4.1 Collision Checking
		9.4.2 Walk Planning
		9.4.3 Reach Planning
		9.4.4 Push Planning
			9.4.4.1 Stable Push Dynamics
			9.4.4.2 Inverse Kinematics
	9.5 Multi-modal Planning with Random-MMP
		9.5.1 Effects of the Expansion Strategy
		9.5.2 Blind Expansion
		9.5.3 Utility computation
		9.5.4 Utility-centered Expansion
		9.5.5 Experimental Comparison of Expansion Strategies
	9.6 Postprocessing and System Integration
		9.6.1 Visual Sensing
		9.6.2 Execution of Walking Trajectories
		9.6.3 Smooth Execution of Reach Trajectories
			9.6.3.1 Time-optimal Joint Trajectories
			9.6.3.2 Univariate Time-optimal Trajectories
			9.6.3.3 Acceleration-optimal Trajectories
	9.7 Experiments
		9.7.1 Simulation Experiments
		9.7.2 Experiments on ASIMO
	9.8 Conclusion
	References
10 A Motion Planning Framework for Skill Coordination and Learning
	10.1 Introduction
		10.1.1 Related Work
			10.1.1.1 Multi-modal Planning
			10.1.1.2 Learning for Motion Planning
		10.1.2 Framework Overview
	10.2 Motion Skills
		10.2.1 Reaching Skill
		10.2.2 Stepping Skill
		10.2.3 Balance Skill
		10.2.4 Other Skills and Extensions
	10.3 Multi-skill Planning
		10.3.1 Algorithm Details
		10.3.2 Results and Discussion
	10.4 Learning
		10.4.1 A Similarity Metric for Reaching Tasks
		10.4.2 Learning Reaching Strategies
		10.4.3 Learning Constraints from Imitation
			10.4.3.1 Detection of Instantaneous Constraints
			10.4.3.2 Merging Transformations
			10.4.3.3 Computing the Thresholds
			10.4.3.4 Reusing Detected Constraints in New Tasks
		10.4.4 Results and Discussion
	10.5 Conclusion
	References