Homotopic particle motion planning for humanoid robotics

Exploiting structure is essential to an understanding of motion planning. Here, we exploit the topology of the environment to discover connected components. Inside a connected component, instead of planning one trajectory in configuration space, motion planning can be seen as optimizing a set of homotopically equivalent particle trajectories. In this paper, we will concentrate on the problem of motion planning for a humanoid robot. Our contributions are: i) finding the homotopy classes of a single footstep trajectory in an environment, ii) finding a single footstep trajectory in a single homotopy class formulated as a convex optimization problem, and iii) finding a feasible upper body trajectory given a footstep trajectory, formulated as a set of convex optimization problems. This view provides us with important insights into the difficulty of motion planning, and – under some assumptions – allows us to provide the number of local minima of a given motion planning problem. We demonstrate our approach on a real humanoid platform with 36-dof in a highly restricted environment.