Introduction

Our goal is to provide a system which allows existing and future legged robots to achieve navigation autonomy. There are many components to a completely autonomous walking or running robot, and many problems to be solved. These challenges include actuator and mechanism design, balance control and robustness to disturbances, sensing of the environment, and the ability for the robot to choose intelligent and appropriate actions for traversing terrain. The focus of the work on this site is in the area of intelligently choosing actions to safely and efficiently traverse a given terrain. We build on top of existing balance controllers to safely navigate a robot through complicated environments. Some examples of the type of problem this work attempts to solve can be seen in the videos. For complex indoor environments designed for humans, this includes dealing with furniture, walls, stairs, doors, and previously unknown obstacles 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. However, existing navigation planning methods fail to consider these additional capabilities, because they were primarily designed for wheeled mobile robots.

A cluttered environment in which the robot must choose foot placements carefully.

Due to the many degrees of freedom present on legged robots, we focus on methods to reduce the dimensionality of the search space in order to find plans in a reasonable amount of time, while still retaining the capabilities that make legged robots interesting. This dimensionality reduction is accomplished by reasoning about the foot placement of the robot, discretizing our search along the discrete changes in the hybrid dynamics of the legged systems. This provides a natural way of breaking up the problem, allowing us to apply discrete planners to find a safe sequence of foot placements through the environment. The robot's locomotion controller can then take the robot through each stage of support, bringing the robot from its start configuration to the goal.

Algorithm

NOTE: These sections are still being written. For details on the algorithms and results, please see the publications.

Footstep planning works primarily by determining which places in the environment are safe to step to, and then searching within the capabilities of the robot and its controller to find a path through those safe footholds which can take the robot from its starting state to a goal. We use discrete planning techniques, such as A* search, to quickly evaluate potential steps and paths through the environment and determine the best possible path through the environment, as determined by some pre-selected criteria. In order to perform this search, we need a compact representation of what the capabilities of the underlying robot and controller are. We need to know what sorts of terrain it can handle, what kind of motions it can make, and what aspects of its locomotion can be adjusted to cope with the environment the robot finds itself in. This "action model" provides us with a way to efficiently find paths which make use of existing controllers, and allow the robot to use its legs to step over and onto various features of its environment, while ensuring that its path will be safe to execute and not exceed the capabilites of the robot or its controller.

A Simple Action Model

To understand how the planning process works, let's begin with a very simple action model for a biped robot. In this simple model, given the location of the stance foot, the robot has a region that of the world that it can step to with its next step. In our simple model, we will say that this region has a constant shape (although mirrored for each foot), and we will choose a fixed number of candidate steps from that region as a representative set of actions for the robot.

With this simple action model, we can build a search tree over the environment. From the initial stance of the robot, we can test each of our actions, to determine which of them represent valid steps. From those valid steps, we can apply our action model again, generating new step locations further out in the world. As we continue to grow this tree, eventually it will reach the goal location we have specified. Tracing back in the tree will provide us a path through the environment which is sure to be safe to execute (we have validated all the stepping motions), and is within the capabilities of the robot and its walking controller (the action model never generates steps outside of the robot's capabilites).

This simple model was used successfully on the robots H7 and HRP-2. For more information and details, including how steps are determined to be valid and the representations and models used, see here.

Dynamic Constraints

Adaptive Action Models

Quadruped Action Models

Results

H7 Humanoid Robot

The first trials of this work on a real robot were performed on the H7 humanoid robot at the University of Tokyo. The robot used onboard stereo cameras to reconstruct the shape of the terrain. For these early experiments, this data was categorized as areas that belonged to the floor, and areas that belonged to obstacles. The planner then used that map along with a fixed set of possible actions to plan a path through the environment. In later trials, the robot would replan while walking, generating a new path every two steps it took.

Brief videos of H7 planning through various environments can be found here.

Honda ASIMO

HRP-2

LittleDog