Motion planning of walking robots in environments with uncertainty

We present a general approach for coordinating the legs of a multi-legged s tatically stable walking machine on an uneven terrain. We are interested in an optimized motion plan for several "body-lengths" that specifies the foo tholds 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 a ssume 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 th at is guaranteed to be in a desired percentile with a given confidence leve l. Depending on the available computational resources we can improve our co nfidence level and/or get closer to the optimal plan. Finally, our approach allows us to trade off speed with safety and speed with optimality. (C) 19 99 John Wiley & Sons, Inc.