PDF《Sony Corporation, Tokyo, Japan》

3 Navigation Map and Collision Checking Collision checking is one of the crucial factors in path plan- ning. Cylinder models of robots allow to perform this check in constant time if the distance to the nearest obstacle is known;

the distance is simply compared to the radius of the cylinder. Our two cylinder model allows to check for colli- sion in the same amount of time. For ef?cient collision checking we make the following as- sumptions about the world the robot is navigating in: 1. The world is partitioned into ?oor and obstacles. 2. Floor is planar and horizontal (else it is an obstacle). 3. There are no multiple ?oor levels at the same location. 4. The robot is able to distinguish between ?oor and ob- stacles and can can estimate their relative position and height using its sensors. Assumption

1 is general,

2 rules out inclined surfaces and treats them like obstacles,

3 is true for most but a few envi- ronments and enables the use of a 2.5D map for representing forward turn sideways Figure 3: Space required for performing an action. Enlarged upper cylinders approximate the additional space needed. the world. Finally, assumption

4 is a practical consideration and can be achieved e.g. by plane extraction from range data.1 Under these assumptions, the robot is able to build a ?oor and obstacle height map FOG of its environment. We ........