Data processing: vehicles – navigation – and relative location – Vehicle control – guidance – operation – or indication – Automatic route guidance vehicle
Reexamination Certificate
1998-12-18
2001-03-20
Cuchlinski, Jr., William A. (Department: 3661)
Data processing: vehicles, navigation, and relative location
Vehicle control, guidance, operation, or indication
Automatic route guidance vehicle
C180S169000, C318S568160
Reexamination Certificate
active
06205380
ABSTRACT:
BACKGROUND OF THE INVENTION
In the orientation of autonomous mobile units like, for example, remote exploration probes, units that operate in danger zones, self-propelled industrial vacuum cleaners, transport vehicles and self-propelled robots, the problem arises that they must get their own impression of their environment. To that end, such an apparatus must construct a reliable map or its work environment and be simultaneously able to localize itself at any time on the basis of this map. It is thereby to be noted that an optimally fast evaluation and an optimally fast construction of this map can be required dependent on the speed of movement of such an apparatus. A practical method for the construction of such a map and for orientation of such a self-propelled mobile unit in an unknown environment is comprised therein that the unit constructs a two-dimensional grid of its environs and provides individual cells of this grid with degree of occupancy values. The degree of occupancy values assigned to a grid cell represent the occurrence of obstacles in the environment. Methods of this species are known from the Prior Art and shall form the basis for the present invention.
U.S. Pat. No. 5,006,788 discloses a basic method for the construction of cellularly structured environment maps that are provided with degree of occupancy values for representing obstacles. German Patent 44 08 329 C2 discloses recites a method with which the orientation of such a mobile unit within such a grid map can be improved, in that a coordinate reference point under the discretization provided by the map is defined in that a specific point of an autonomous mobile unit within an initial cell is defined as coordinate reference point. German Patent 4408 328 A1 recites another orientation method for autonomous mobile units within a grid raster wherein sensor properties such as blind areas and maximum distances to obstacles are co-involved for the evaluation of the map.
SUMMARY OF THE INVENTION
The object underlying the invention is comprised in specifying an improved method for the construction of a cellularly structured environment map by an autonomous mobile unit, whereby, in particular, the assigning of the degree of occupancy values and the deletion of the degree of occupancy values should be improved by the method.
A particular advantage of the inventive method is comprised therein that the measuring direction of the sensor from which an obstacle is measured is also taken into consideration in the storing of the degree of occupancy values per individual cell of the grid-shaped environment map. In this way, it can be assured that obstacles that are covered by different sensors over the course of time can only be deleted from the map when the sensors have acquired the respective obstacle from the same direction with reference to the cellularly structured environment map. What can thereby be particularly avoided is that existing obstacles are deleted due to mirror reflections of ultrasound echos via a timeout condition for the arrival of acoustic echos at the sensor, which can occur in that, for example, the unit moves along a smooth wall and following sensors whose measuring direction proceeds obliquely relative to the wall receive no reflections from the wall but only mirror reflections. This can lead thereto that a timeout condition for the arrival of echos makes the sensor think that the area in front of it is unoccupied because the wall is not registered due to the long running time of the echos of mirror reflections. As a result thereof, a cell that was marked “occupied” by a sensor that measures perpendicular to the wall can in turn be characterized as “free” by a following sensor that measures obliquely relative to the wall since this reduces its degree of occupancy due to the mismeasurement.
It is especially advantageously assured by the inventive method that the degrees of occupancy of cells that are located within the blind zone of an ultrasound sensor cannot be modified. The collision avoidance in the route planning of autonomous mobile units is thereby considerably improved in the near range, particularly in the blind area of the respective sensors. Otherwise, global incrementation and deincrementation strategies of the degree of occupancy values would lead thereto that the degrees of occupancy of cells that are located in the blind area of the unit but cannot be measured would likewise be modified.
Particularly advantageously, a maximum sensor range is defined by the inventive method in that a maximum signal running time that derives from the point in time the measuring pulse is output until the point in time of the arrival of the ultrasound echo is prescribed for the arrival of the ultrasound echos. A distance can be derived from this signal running time via the speed of sound. Objects in the environment that lie outside this maximum measuring distance are preferably no longer entered in appertaining cells of the environment map since reliably false measured results that derive from multiple echos or that depend on measuring pulses of other ultrasound sensors can thereby be avoided in the construction of the map. Degrees of occupancy of segments of cells that are located within an area between the measured object and the blind zone are especially advantageously deincremented according to the inventive method, since it is known for these cells that no obstacle can be located on them. The inventive method also advantageously provides that only those degrees of occupancy of cells that are located on the measuring beam be modified, so that the calculating outlay for the calculation of the degree of occupancy values of individual cells can be considerably reduced, and a good approximation for the results found in practice is achieved.
The degree of occupancy of a cell that is located on the circular arc segment that is established by the aperture angle of the measuring cone and by the distance of the obstacle is especially advantageously positively incremented, since it is known that the obstacle must be located on one of these cells.
A maximum value is especially advantageously defined for the degrees of occupancy of cells, since the calculating outlay in the determination of the respective degrees of occupancy of a cell can thus be kept constant, and an estimatable time outlay for the planning and evaluation of an environment map can thus be assured.
The increment can be especially advantageously varied dependent of the distance from the obstacle in the environment, since specific obstacles can thus be weighted higher or lower dependent on the speed with which the unit moves and on the distance from the unit.
The increment can thereby also be advantageously made dependent on the motion speed, in order to thus be able to take into consideration that the unit would more quickly collide with an obstacle given faster travel.
The autonomous mobile unit localizes itself especially advantageously on the basis of a coordinate reference point that is established by the exact position within an originating cell of the cellularly structured environment map. What is thus achieved is that the discretization that is prescribed by the cell size in the grid need not be employed for the coordinate origin; rather, finer resolution can be carried out therefor. This particularly plays a part when, dependent on measured distances from obstacles, that cell whose degree of occupancy or, respectively, whose degree of sector occupancy is to be incremented is to be determined.
In order to optimize the calculating outlay in the interpretation of the environment map and accelerate the route planning for an autonomous mobile unit, it is advantageously provide to employ different cell sizes for the cellularly structured environment map in the application of the inventive method; thus, cells at a farther distance from the unit can preferably be selected larger and cells lying closer to the unit can be selected smaller.
The invention is explained in greater detail below on the basis of the Figures. In this context, it shou
Bauer Rudolf
Wienkop Uwe
Cuchlinski Jr. William A.
Pipala Edward
Schiff & Hardin & Waite
Siemens Aktiengesellschaft
LandOfFree
Process for preparing an area plan having a cellular... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Process for preparing an area plan having a cellular..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Process for preparing an area plan having a cellular... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2536216