Visual Path Planning by a Mobile Robot

1. INTRODUCTION

Sensor-based navigation of mobile robots in un­ structured environments has been extensively studied as one of key problems of artificial in­ telligence research. Most robots plan paths to the destinations using 2-0 maps, given a priori or built by themse 1 ves, represented in the abso 1 ute coordinate system [Moravec 83, Gi ra lt et a 1. 84, Tsuji 85, Elfes 86]. Drawbacks of such maps were pointed out by Brooks [Brooks 85 ], who presented an interesting idea to use a rubbery and stretchy relational map, making the spatial reasoning robust to errors in estimating positions of ob­ jects and robots in the absolute coordinate sys­ tem. Realization of the idea, however, has not been reported yet.

The authors' group has been a 1 so studying a vision-based robot wandering about and accom­ plishing the specified task in an indoor environ­ ment. We follow the above-mentioned idea in the sense that use the local coordinate systems with relative transforms and error estimates. Rather than to use the conventional 2-0 maps for spatial reasoning, a flexible relational model of the global world can be built with local maps suited for each function of robots, such as path planning or manipulation. For the path planning, this paper presents a new scheme, based on the properties of

This work is supported in part by Grant-In-Aid for Scientific Research from Ministry of Education, Science and Culture, Japanese Government.

VISUAL PAllf PI.NflliKi BY A l\.llBILE ~'--- - --

Saburo Tsuji and Jiang Yu Zheng Department of Control Engineering Osaka University Toyonaka, Osaka 560, japan

vision, for representing the local world and using it for planning. Investigating the merits-and demerits of transforming the visual data into the conventional 2-0 map, we use a perspective repre­ sentation of world, the image on which the scene interpretation is mapped, for planning promising paths to the goal (or sub-goals). Using world constraints and sensory information of camera orientation, a stereo-image analyzer determines vertical projections of edge points onto the floor in the image. A method for planning of promising paths to the specified goal using this representa­ tion is presented.

2. WRLD fi)()EL

World Model with Local Maps

Vision of intelligent robots play the most impor­ tant role among their sensors in building and maintaining models of their environments. For the effective usage of the models, their structures should be carefully designed so· as to be suited for the functions of the robots. A mobile robot wandering around in an unstructured environment needs functions as follows: (1) It plans a route .to the specified destination, (2) navigates safely ~long the planned ·route and (3) performs the given JOb such as manipulation or monitoring at the destination. We do not need a world model of a unified structure and thus same performance through the entire task, but models with different structures and different grain sizes, which repre­ sent facts about the world needed for each fun­ ction, are more reasonable.

For example, the planning needs coarse representa­ tion of free spaces relative to some landmarks and the robot, but the detailed structures and shapes of objects in scene, in most cases, do not provide important information. Navigation uses the local world model describing the approximate direction and distance it will move, obstacles along the route and the landmarks by which the sub-goal is spec~fied. Manipulation needs, on the contrary, prec1se 3-0 models of objects located in a limited ar~a such as a workbench. We can, therefore, bu1ld a global world model covering a wide en­ vironment by combining the different representa­ tions of the local worlds with coarse geometrical relations between them.

2-0 Euclidean Map or Perspective Model

Let us consider how the local world is repre­ sented for planning paths to the destination. Precise estimate of the free space geometry is, in general, difficult because of the limited resolu­ tion of visual sensors and, if possible, they are often not so meaningful at the planning stage. Robots can not always find the route to the desti­ nations from single view. In many cases, when they have not enough experiences of wandering about the routes, these robots plan promising routes and next observation points where the pos­ sibilities of further navigation are examined. Representation of the local worlds should be se­ lected so as to be convenient for such planning.

Vision-based robots analyze input images taken by TV cameras and yield 2-D maps in the absolute coordinated system by transforming positions of obstacles found in the images into an Euclidean representation. The maps, on which the robots are located, are then labelled with free, occupied, or unknown regions, and the routes to the destination are planned on it. The 2-D maps have been used because (1) we can easily understand them and, therefore, ~2) integration of 3-0 data acquired from images taken at different positions seems straight forward (but not so easy because of un­ certainties in camera locations and orientations, and much research has been done [Faugeras et al. 86, Lin et al. 86]).

Difficulties arise in such representation from inherent error due to measuring in imag~ Meas­ urements of ranges to objects suffer from the minimal spatial resolution of vision sensors used. Thus, the error in depth measurement increases with proportional to the squared distance of the object from the camera. As a result, estimates of far object points, back projected from the images to the 2-0 map, are very uncertain. Such uncer­ tainty must be added as a feature of each point in the maps. Another difficulty is that the observed points are sparse in far areas in the 2-D maps; the density is inverse 1 y proportion a 1 to the squared distance from the camera. If a cellular representation of the 2-D map [Elfes 86] is used, we need to interpolate features between the ob­ served points to fill in blank cells.

We propose to map the scene interpretation onto a perspective world, the image itself, rather than transform the image data into the 2-D maps. We assume our robot moves on an almost flat floor, and the projection of the infinite plane con­ taining the floor onto the image is used as a representation of the local world. This represen­ tation is natural in the sense that (1) its spa­ tial resolution is same as that available from the sensors and (2) any interpolation and transforma­ tion is not needed while we deal with single image. We argue human beings without maps also plan the route in the field of vision rather than make reasoning in a top-view of the world.

Integration of information available from the local perspective worlds at different points is possible by estimating transformation matrices between them. A different approach, however, is proposed. We use a simple principle that an ob­ servation from a closer point yields more reliable results. Promising paths to the next observation point, where more reliable estimates will be ob­ tained, are generated in each perspective world.

l. IMAGE ANALYSIS AND PATH PLANNING

Hardware Syste·

We have been doing experiments with a HERO ROBOT, on which two small CCD cameras (NEC TI-22AI) sepa­ rated from each other by 0.2m are mounted at a height of ~7m. Pitch and roll angles of a camera are measured by orientation sensors (Watson flux­ gate magnetometer). Images are converted into 256 by 256 8 bit digital pictures (the appoximate equivalent focal length is 300 pixel) and their edge points are found by a TOSPIX-2 image pro­ cessor connected to a SUN3 workstation, which analyzes the stereo imagery and plans the pro­ mising routes. The results are fed back to the robot through a control computer MC6808. The number of rotations and steering angle of the front wheel are sent to the control computer, from which a coarse estimate of its motion is available.

Stereo Match;ng and Scene Interpretat;on

An image analyzer in the SUN3, which receives stereo images and their edge pictures obtained by a 3x3 Sobel operator, finds 3-D structure of the viewed world and, then, determines the floor boun­ daries. Most indoor scenes are rich in straight edges which give important cues for scene inter­ pretation. For segment-based stereo matching, the analyzer fits lines to edge segments of consider­ able lengths found by tracking edge points. We use a competitive matrix between line segments of the stereo pai~ and find correspondence of lines in the images, by examining the similarity of edge strengths, locations and directions of segments and the consistency in matching. Fig.l shows an example of input left images and Figs.2 display the results of matching of the stereo pair (bold and thin lines represent matched and non-matched segments, respectively). Thus we can determine the 3-0 structure of most portions of the scene.

In order to find free spaces for the navigation, we need information of height of edge points. We assume the optical axes of two cameras are paral1 e 1 and hori zonta 1. Let the coordinate system X,Y,Z be fixed at the center of the two lens centers of cameras with Z axis parallel to the optical axes. Suppose a point P at (X,Y,Z) in space is projected on an image plane of camera at (x,y), assuming the central projection. Using the camera geometry, we have the following simple equations for y~O [Tsuji et al. 86].

where d is the disparity between corresponding image points, f is the focal length of the camera, L is the distance between two camera centers, and H and H are heights of P and the lens center from the flogr, respectively. Thus, the disparity of a point in space is determined from the camera para­ meters (Land H 0 ) and its heights in image and in space.

In order to test whether or not the segments are on the floor, we examine each point in the seg­ ments that the corresponding segments contain an image point with a disparity of -Ly/H 0 · If most part (more than 80%) of a non-horizontal line segments contains such image points, the 1 i ne segments are considered as on the floor. For a pair of horizontal line segments, we determine whether or not the lines are on the floor by examining the disparities of their end points. Fig.3 shows the line segments on which edge points are labelled as floor edge points. Note that boundaries of shadows casted on the floor are labelled as the floor edge points, while the bot­ tom edge of an object appearing in the right lower part in Fig.l is interpreted as floating above the floor (the object is supported by wheels). Thus all edge points in the image are labelled as the floor or non-floor.

Most path planning of mobile robot uses 2-D maps without height information. As a result, the planned routes may be very dangerous for collision with objects overhanged to the path. Therefore, we need 3-D information to find free paths in the world. Since the shape of our robot is simple (approximated by a cylinder) and it cannot change its shape to avoid collision, we use rather simple 3-D information that each point on the floor has an overhanged object or no~ We, therefore, pro­ ject dangerous non-floor edge points onto the floor in the imag~ We have the following simple relation between the image point (x,y) and its vertical projection (x,y') onto the floor.

Thus, we can easily project these edge points onto the floor in the image, and label the projection as obstacle edge points. Thus, the edge points have three labels; floo~ obstacle and non-floo~

The above discussion assumes the invariance in height and tilt of the cameras through execution of the task. The floor on which our robot moves is almost flat and, as a result, we can consider the height is invariant. Small uneveness of the floor, however, causes the cameras to shake, and results in a considerable amount of movements of images. In order to solve the problem, we use the information from the orientation sensors of the camera, and can compensate for the movements less than one pixel.

Planning Paths

As mentioned before, the system searches the local map for promising paths to the goal or the next observation point. At first, we label the per­ spective world as free, dangerous, uncertain, and invisible. We move the projection of robot onto the floor in the perspective world (therefore the shape and size of the projected area change) and examine the possibility of collision. For simpli­ city of computation, we approximate the robot's projection by a square.

We start with the bottom row of the image assuming that it belongs to the free area, and move the robot's projection until its any part collides with edge points (see Fig.4). Then, we change the direction of movement, and continue to move it until it cannot move further. By iterating the procedure, we can find a 11 poss i b 1 e movement of the projection, and areas covered by the center of the projection are labelled as free. Fig.5 shows the free area found in Fig.1. The proposed pro­ cedure is robust to the errors in finding edge segments, because missing of small portions of edge segments results in very little effects to the labelling.

We also label the narrow regions between the free areas and the obstacle edges as dangerous regions, and those between the free areas and non-floor edge as uncertain regions. The rest parts in the perspective world are considered as invisible regions.

Now let us consider how we can find possible routes to the goal if its approximate location is given in the perspective world. Route finding seems easy if routes to the goal exist in the free region. Objects in scene, however, often occ 1 ude parts of the routes or the goal, and we need to search the perspective world for promising routes to the goal. If the labels are correct, the routes from the free region must exist across the uncertain regions toward the goal as pointed in Fig.4, and we can determine the most promising route by using a heuristic function to estimate the possibility and cost of attaining to the goal, and set observation points along the route where the uncertain regions are easily observable.

We should note that the labels are not reliable if areas are far from the cameras, because of the limitation of sensor resolution. For example, free paths sometimes exist in far areas labelled as dangerous because of the uncertainty in estimate of 3-D distance between edge points. The uncertainty in hight estimate results in labelling of edges of low obstacles as floor edges. Therefore, a good policy for path planning is to plan promising or possible paths to the destination, and moves a 1 ong a rou·te to obtain a closer view of the path. We propose that pro­ mising paths are generated in each perspective world and portions with more reliable estimates are merged together with a graph structure of which arcs give the approximate geometrical rela­ tions between them.

4.. CONCLUSION

In this paper, we examine prob 1 ems of wor 1 d modelling and path planning which must be solved by a mobile robot exploring an unknown environ­ men~ In particular, we introduce the perspective model of the local world for planning promising paths to the destination. Image analysis and spatial reasoning based on this representation are also described. The major parts of the system have been already implemented and tested, and the whole system will be built in near future.

ACKNOWLEDGMENT

The authors wish to express their hearty thanks to Minoru Asada, Osaka University for his kind discussions on this work.