PDF《Sony Corporation, Tokyo, Japan》

Real-Time Path Planning for Humanoid Robot Navigation Jens-Steffen Gutmann Masaki Fukuchi Masahiro Fujita Intelligent Systems Research Laboratory Sony Corporation, Tokyo, Japan {steffen,fukuchi,mfujita}@pdp.

crl.sony.co.jp Abstract We present a data structure and an algorithm for real-time path planning of a humanoid robot. Due to the many degrees of freedom, the robots shape and available actions are approximated for ?nding solutions ef?ciently. The resulting

3 dimensional con?guration space is searched by the A* algo- rithm ?nding solutions in tenths of a second on low- performance, embedded hardware. Experimental results demonstrate our solution for a robot in a world containing obstacles with different heights, stairs and a higher-level platform.

1 Introduction Path-planning is one of the fundamental problems in mobile robot navigation. It has been shown long before that the prob- lem of moving an object through space is PSPACE-hard with a time complexity exponential in the degrees of freedom of the object [Latombe, 1991]. In mobile robots the degrees of freedom are usually small (three or less) which opens the ap- plication of a range of search techniques speci?cally tailored to the problem. If one can neglect orientation, e.g. a cylin- drical holonomic system, the resulting

2 dimensional con?g- uration space can be searched ef?ciently by A*, D* [Stentz, 1995], or dynamic programming [Buhmann et al., 1995]. Humanoid robots while being mobile allow for more than the usual three degrees of freedom. Their feet can be placed with a greater choice and the change of body posture allows to overcome obstacles where wheeled robots fail in pass- ing through. This enables humanoids to step onto objects [Kuffner et al., 2002], climb up and down stairs [Hirai et al., 1998;

Gutmann et al., 2004], step over obstacles [Guan et al., 2004], or crawl underneath objects [Shiller et al., 2001;

Kanehiro et al., 2004]. The higher degrees of freedom can be tackled e.g. by prob- abilistic roadmaps [Kavraki et al., 1996]. However, if one can employ a non-probabilistic approach by ?nding a suitable ap- proximation then the solution can be seen preferable due to its deterministic nature. One possible approximation is to model the robot as a cylinder or by its convex hull which allows for ef?cient collision checking [Okada et al., 2003]. Care should be taken though not to over-simplify the prob- lem. Humanoid robots are non-holonomic, i.e. they cannot turn in place without requiring additional space. The trajec- tory of the body center describes a curve similar to a car-like robot, although the turn radius is generally quite small. It is possible to account for the extra turning space in a cylinder model of the robot enlarged by twice the turn radius [Li et al., 2003;

Sabe et al., 2004]. However such an approxima- tion is overly pessimistic and prevents the robot from passing through narrow space as we will show. Discretizing the possible actions of the robot into a small set of well-chosen actions, e.g. different foot placements, leads to another way for ?nding solutions ef?ciently. The induced search graph grows exponentially with the number of steps and thus, only a small number of foot steps can be explored in a real-time system [Lorch et al., 2002]. Such a foot-step planning system is nevertheless a valuable tool in a hybrid system where a higher level planner provides way- points for this sub-system [Chestnutt and Kuffner, 2004]. Shiller et al. [2001] discretize the actions and orientations of a digital ?gure that can walk forward, sideways, turn and crawl. They maintain an obstacle space for each combination of action and orientation and ?nd solutions ef?ciently for tra- jectories of several ten steps. We compute a trajectory for the body-center of a humanoid robot by approximating the shape of the robot using multiple cylinders and discretizing con?gurations into a set of orienta- tions. When following this trajectory, the next few foot steps are computed using an analytical method. This enables a hu- manoid robot to ?nd paths of up to a few meters in real-time and includes actions such as sideways walking through nar- row space and climbing up and down stairs. Our work differs from Shiller'