Motion planning of walking robots in environments with uncertainty

We present a general approach for coordinating the legs of a multi-legged statically stable walking machine on an uneven terrain. We are interested in an optimized motion plan for several “body-lengths” that specifies the footholds and the gait of the walking machine. We assume that a terrain map is available but that this map may be characterized by uncertainty. We also assume that the optimality of the motion plan can be measured by a suitable metric. The method of ordinal optimization is used to find a motion plan that is guaranteed to be in a desired percentile with a given confidence level. Depending on the available computational resources we can improve our confidence level and/or get closer to the optimal plan. Finally, our approach allows us to trade off speed with safety and speed with optimality.