Data processing: vehicles – navigation – and relative location – Vehicle control – guidance – operation – or indication – Automatic route guidance vehicle
Reexamination Certificate
2002-08-23
2004-04-27
Zanelli, Michael J. (Department: 3661)
Data processing: vehicles, navigation, and relative location
Vehicle control, guidance, operation, or indication
Automatic route guidance vehicle
C701S223000, C342S070000, C180S169000
Reexamination Certificate
active
06728608
ABSTRACT:
FIELD OF THE INVENTION
This invention is related to the field of robotics, and, in particular to the autonomous navigation of mobile robots over terrain with unknown characteristics, including elevation and obstacles.
BACKGROUND OF THE INVENTION
The problem of allowing a mobile robotic device to autonomously and successfully navigate through an area defined by unknown terrain, based on the output of on-board sensors to sense characteristics of the terrain in the field of navigation is relatively well known. Several attempts have been made, using various strategies, to allow autonomous navigation. For example, U.S. Pat. No. 4,751,658 (Kadonoff, et al.) discloses a system wherein a robot's field of view is divided into sectors and a plurality of sensors is used to detect the distance of objects within each sector. U.S. Pat. No. 5,525,882 (Asaka, et al.) discloses a method wherein data from a sensor is combined with image data to identify objects in the robot's path. The data is compared to a table containing profiles of known objects. U.S. Pat. No. 5,684,695 (Bauer) discloses the use of a cellular map which contains information regarding the “occupancy degree” of each cell in the map. Finally, U.S. Pat. No. 6,124,694 (Bancroft, et al.) outlines a method whereby a cleaning robot establishes the boundaries of the area to be cleaned using sonar and a laser range finder.
These inventions of these patents are effective in providing obstacle detection and avoidance in open terrain and with discrete objects that must be detected and avoided.
However, no known method is currently effective in environments that are more complex and wherein obvious obstacle-free paths for the robot to traverse are not available. An outdoors, off-road environment is an example of a complex environment in which the known methods would not work effectively.
The reason for the difficulty in navigating complex environments is the inherent ambiguity in the types of obstacles which may be encountered. For example, a thick stand of meadow grass, while traversable by a robot, may appear to be an obstacle when detected using the present technology. On the other hand, a chain link fence may appear clear and therefore give the erroneous impressions that the robot could traverse a path through the fence.
While it is true that existing obstacle detection algorithms could be made to work for specific cases, it would be desirable to have a more generalized approach that could make decisions independent of specific types of obstacles.
SUMMARY OF THE INVENTION
For robust autonomous off-road vehicle operation, it is necessary to provide, in addition to object detection, terrain classification. To this end, the invention disclosed herein provides a method whereby a density map, which provides measurements of the physical density of various locations, is created. The density map representation of the world provides a continuous measure of terrain traversability, as well as serving as a powerful structural discriminator for the terrain classification task.
To establish the density map, a plurality of sensors of various types are employed and an approach based on penetrability is used. Penetrability is defined as the degree to which a sensor reading passes through or stops in a particular geometric area. After penetrability measures have been computed for each sensor, our method combines them into a single density reading for each location in the density map, using sensor-specific rules.
The density map, once computed, can be used to provide terrain classification, which is a more generalized form of obstacle detection. However, whereas in obstacle detection the goal is to assess only the traversability of a particular location, the terrain classification task seeks to also determine other more specific physical properties, like vegetation (bush or tree trunk) or ground (dry dirt or mud) type. Therefore, the density map provides novel features when compared to existing techniques for this terrain classification. The density map provides an orthogonal, structural measure of terrain type that can be used to better classify objects in the environment. Furthermore, because density is a physical characteristic, it can be more easily interpreted and used by planning and navigation modules to control robot actions. Finally, because density is invariant to lighting conditions and temperature it is possible to provide reliable terrain classification information across a wider range of operating conditions.
REFERENCES:
patent: 4751658 (1988-06-01), Kadonoff et al.
patent: 5525882 (1996-06-01), Asaka et al.
patent: 5684695 (1997-11-01), Bauer
patent: 5771310 (1998-06-01), Vannah
patent: 5819016 (1998-10-01), Watanabe et al.
patent: 5943476 (1999-08-01), Dougherty et al.
patent: 5988862 (1999-11-01), Kacyra et al.
patent: 6009359 (1999-12-01), El-Hakim et al.
patent: 6018497 (2000-01-01), Gunasekera
patent: 6124694 (2000-09-01), Bancroft et al.
patent: 6195922 (2001-03-01), Stump
patent: 6205380 (2001-03-01), Bauer et al.
patent: 6345235 (2002-02-01), Edgecombe et al.
patent: 6373612 (2002-04-01), Hoffman et al.
patent: 6396492 (2002-05-01), Frisken et al.
patent: 6420698 (2002-07-01), Dimsdale
patent: 6470271 (2002-10-01), Matsunaga
Fregene et al.; Incremental Multiagent Robotic Mapping of Outdoor Terrains; IEEE-Intl. Conf. on Robotics & Automation; May 2002; pp. 1339-1346.*
Najjaran et al.; Map Building for a Terrain Scanning Robot; IEEE-Intl. Conf. on Robotics & Automation ; May 2001; pp. 3728-3733.*
Kweon et al.; High Resolution Terrain Map from Multiple Sensor Data; IEEE-Intelligent Robots and Systems '90; Jul. 1990; vol. 1, pp. 127-134.*
Shen et al.; Autonomous Navigation to Provide Long-distance Surface Traverses for Mars Rover Sample Return Mission; IEEE-Intelligent Control, 1989; Sep. 1989; pp. 362-367.
Jochem Todd
Ollis Mark
Applied Perception, Inc.
Buchanan Ingersoll
Carleton Dennis M.
Zanelli Michael J.
LandOfFree
System and method for the creation of a terrain density model does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for the creation of a terrain density model, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for the creation of a terrain density model will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3243214