Autonomous navigation of a humanoid over unknown rough terrain is realized by integrating online terrain-shape-map generation, online footstep planning, and robust walking control. Terrain shape is
measured by a scanning-type laser range sensor on the torso, and the terrain height map is generated with a few centi-meter accuracy. Sequence of footprints are decided by applying a search-based algorithm to the generated map. Online planning is realized by evaluating approx. 25000 candidates of stepping point in 800ms, which is approx. step cycle. Inclination, roghness, etc. are evaluated for each stepping position candidate so that feasibility of stepping on is judged and the cost of the stepping position is assigned. Map region under the transition of the free-leg foot is also evaluated for judging the feasibility of the transition and assigning cost of the transition. Walking control consists of repetitive pattern genearation of dynamically balanced pattern at such as 40-ms cycle, and 1-ms cycle ground reaction force control.Ground reaction force controller tries to realize desired ground reaction force which is given from the pattern generator. As the result of the control position trajectory of the robot diverges from the generated one. Actual motion of the robot is adopted for the initial condition of the each generation. This framework makes the walking controller robust to the error of the terrain shape from the suppoed.