PDF《Sony Corporation, Tokyo, Japan》

s in that we do not plan be- haviors but select the behavior depending on the environment when following a found path, e.g. stair-climbing over a sill. We also maintain only one obstacle space and show how to perform collision checking ef?ciently. Last but not least, our system is demonstrated on a real robot where stereo range data incrementally updates a representation of the world. Our approximations of con?guration space and actions are presented in the next section. Section

3 brie?y describes our approach for generating a navigation map for collision check- ing. Section

4 details our application of the A* algorithm for path searching. Experimental results on Sony'

s humanoid robot QRIO are described in Section 5. Finally, we discuss limitations and extensions of our approach in Section 6.

2 Con?guration Space and Actions The robot moves in a

2 dimensional world. Obstacles, differ- ent ?oor levels and stairs are projected onto one plane. We do not neglect the orientation of the non-holonomic robot, thus the con?gurations space C is

3 dimensional. For allowing ef?cient search we discretize C into a regular grid of evenly spaced cells using

8 different orientations: C = X * Y * Φ X, Y = {i ・ cs |

0 ≤ i <

n} (1) Φ = {i ・ 45? |

0 ≤ i <

8} where cs de?nes the cell size and n the number of cells. We restrict the movement of the robot'

s body center to the following six actions A = { forward, backward, turn-left, turn-right, side-left, side-right}. For each action the transi- tion in C is given for orientations 0? and 45? in Figure 1. For other orientations the transitions are analogous. When concatenating turn-left (or turn-right) actions, the resulting trajectory describes a curve, see Figure 2(a). The turn actions thus model the non-holonomicconstraint of a hu- manoid where changing the orientation requires extra space for turning. If we approximate this curve with an arc of a cir- cle, we ?nd that the cell size cs coincides with the turn radius of the robot and therefore cs should be chosen as such. The shape of the robot is approximated by two cylinders sharing the same axis as shown in Figure 2(b). Cylinders allow for fast collision checking and the smaller cylinder for the legs enables the robot to pass close to low obstacles where upper body and arms are above the obstacle. The cylinders are a tight ?t to the shape of the robot stand- ing still. When the robot moves, however, additional space is needed for the transition in C as body and legs are swinging while walking. Figure

3 shows snapshots of the robot when moving forward, turning left and stepping sideways. We ac- count for the additional space by enlarging the cylinders at the start and end con?gurations depending on the action. Both, upper and lower, cylinders are enlarged by the same amount. Only when walking sideways, no additional space is needed. As we will see in Section

5 this enables the robot to pass through narrow space by choosing the sideways walk. It is worth noting that the humanoid robot does not neces- sarily need to be able to exactly perform the

6 actions de?ned in this section. For example, the robot could well use several foot steps for performing the 45? rotation in our turn actions. The only requirement is that the enlarged cylinders cover all the space the robot requires for completing the 45? turn. forward backward turn-left turn-right side-left side-right Figure 1: Change in con?guration for our

6 actions. hu hl h ru rl (a) (b) Figure 2: (a) Turn around by concatenating

4 turn-left actions. (b) Multi-cylinder model for approximating robot shape. One might think of our approach to be speci?cally tailored to humanoids as the proposed actions and the cell size match- ing the turn radius are probably only found for this kind of robot. While this seems to be true, the contribution of this work is to demonstrate the abilities of such a system in a com- plex real-world environment. We will discuss the limitations and possible extensions of our approach in Section 6.