Biped Navigation Planning

Planning footsteps though interesting terrain.

As humanoid robots continue to advance and gain new capabilities, software for high-level control and autonomous motion generation will be required. One important area of research involves the design of algorithms to compute robust navigation strategies for humanoids in complex human environments. For indoor environments, this includes dealing with furniture, walls, stairs, doors, and possible objects on the floor. For outdoor environments, this includes the ability to navigate on rough terrain and uneven surfaces. Because legged robots have the ability to step over and onto obstacles in their path, they are uniquely suited to overcoming these difficulties.

We have developed a planner which allows the humanoid to take advantage of its bipedal capabilities and navigate through difficult environments where conventional 2D planning algorithms designed for wheeled robots would be unable to find a solution. Heuristics designed to minimize the number and complexity of the step motions are used to encode cost functions used for searching a footstep transition graph. If successful, the planner returns an optimal sequence of footstep locations according to the cost functions and plausible sets of footstep locations.