Process for preparing an area plan having a cellular structure and comprising a unit moving automatically and positioned in said area using sensors based on wave reflection

[0002] 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.

[0003] 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.

[0004] 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.

[0005] 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.

[0006] 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.

[0007] 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.

[0008] 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.

[0009] 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.

[0010] 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.

[0011] 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.

[0012] 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.

[0013] 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.

[0014] The invention is explained in greater detail below on the basis of the Figures. In this context, it should be reemphasized that the fundamentals for cellularly structured environment maps and methods for orientation in these environment maps that are recited in the above identified Prior Art are assumed for the rest of the specification.

[0015] The features of the present invention which are believed to be novel, are set forth with particularity in the appended claims. The invention, together with further objects and advantages, may best be understood by reference to the following description taken in conjunction with the accompanying drawings, in the several Figures of which like reference numerals identify like elements, and in which:

[0016] FIG. 1 shows an example of a cellularly structured environment map from the Prior Art.

[0017] FIG. 2 indicates an example for the determination of the sensor alignment within the cellularly structured environment map.

[0018] FIG. 3 indicates an example for sectors of measuring direction areas for assigning degree of occupancy values within a cell of the environment map.

[0019] FIG. 4 illustrates characteristic quantities given measurement with an ultrasound sensor.

[0020] FIG. 5 indicates an example of a measuring procedure improved by the inventive method.

[0021] FIG. 6 indicates a further example of a measuring procedure improved by the inventive method.

[0022] FIG. 1 indicates an example of the basic method for forming cellularly structured environment maps according to U.S. Pat. No. 5,006,988. A sensor S, which measures the distance to an obstacle H1, is supposed to assign degrees of occupancy for cells Z within an environment map U. The measuring area of the ultrasound sensor is established by the aperture angle Ψ_Sof the acoustic front. What position they assume in relationship to the sensor cannot be stated for objects detected within the cone; rather, only their distance can be determined. For the sake of simplicity, all degrees of occupancy of those cells that are located on the symmetry axis A of the measuring cone are modified. Corresponding to the measuring imprecision of the sensor S, the only thing known is that the object H1 must be located on the segment SEG. Since no further obstacles can be located between the object H1 and the sensor, the degrees of occupancy of the corresponding cells Z1, Z5, etc., are modified, for example, by a negative increment, whereas the degree of occupancy of the cell Z11 that is located on the segment SEG and on the axis A is incremented by +3. A maximum degree of occupancy of 15 and a minimum degree of occupancy of 0 can preferably be provided. Dependent on these degree of occupancy values, the probability of the occurrence of an obstacle is indicated for the respective cell. The route planning of the autonomous mobile unit can preferably be implemented according to the assigned degree of occupancy values. Despite the simplification that only the degrees of occupancy of cells on the axis A are modified, practice has shown that an adequately accurate map can thereby be constructed since many measurements from different positions are registered during the travel of the autonomous mobile unit. Since, due to the modification of only cells lying on the axis A, it is not all degree of occupancy values of a [. . . ] grid cells within the acoustic cone of the ultrasound sensor that have to be modified, this involves a considerable acceleration in the interpretation of measured results and entry of these measured results into the environment map, which in turn allows a very high measurement rate.

[0023] This method, however, has the disadvantage that the same cells are always modified given standstill of the unit, which would lead thereto that the content of the cell Z11 receives the maximum degree of occupancy and the degrees of occupancy of all other cells between the sensor and the cell Z11 on the axis A would be deleted. Further, this method has the disadvantage that the degrees of occupancy of cells that are not intersected by the beam axis A can no longer be reduced and thus block continued travel of an autonomous mobile unit in an inadmissible way. A further disadvantage of this method is comprised therein that what are referred to as timeout measurements are not employed for the interpretation and for updating the degrees occupancy. Timeout distances derived therefrom that, for example, one waits only a specific, maximum time until the arrival of an echo after the transmission of the measuring pulse of the sensor. The distance that sound can traverse in this time is referred to as the timeout distance. When no echo is received during the waiting time, then, for example, the timeout distance is supplied as a measured result. All degrees of occupancy of sectors of cells on the axis A are preferably reduced within the timeout distance by the inventive method.

[0024] FIG. 2 provides an example for determining the exact sensor alignment at an autonomous mobile unit AE that is referred to a coordinate system underlying the cellularly structured environment map. For acquiring the environs, the unit AE is preferably equipped with 24 commercially available ultrasound sensors. For example, the experimental robot was provided with n_S(=24) ultrasound sensors. The position and orientation of a sensor S in its own coordinate system K′ of the unit is established by

[0025] a′_s=(x′_s,y′_s,α′_s)  (0.1)

[0026] The exact sensor positions, for example, can be predetermined. Given a global configuration of the unit {overscore (x)}_r(K)=(x(K),Y(K),θ(k)) at time k, the global sensor position a_s(k)

[0027] a_s(k)=x_s(k),y_s(K),α_s(k))  (0.2)

[0028] of a sensor s can be determined by a coordinate transformation

[0029] x_s(k)=x(k)+x′_scos(θ(k))−y′_ssin(θ(k)) _s(k)=y(k)+x′_ssin(θ(K))+y′_xcos(θ(k)) α_s(K)=θ(k)+α′_s  (0.3)

[0030] Definition of the sensor positions, thereby, globally: a_x(k), and locally: a′_s. Since the global sensor position a′_s(k) is obviously dependent on the global configuration of the unit and, thus, on the time, the time index k is usually omitted below for reasons of clarity.

[0031] As an example, FIG. 3 shows a cell Z that is divided into sectors SEK with sectors for assigning directionally dependent, specific degree of occupancy values BEL. The height of the degrees of occupancy assigned is indicated here by the gray coloration of the corresponding sectors 1 through 6. According to the inventive method, such areas in the form of sectors are provided for all cells of the cellularly structured environment map. This procedure particularly plays a part when a plurality of sensors at the autonomous mobile unit are provided and these assign degree of occupancy values for cells of the environment map at different times. Each such areas, i.e. sectors, are indicated in FIG. 3 for assigning degree of occupancy values; however, an arbitrary plurality of such areas greater than or equal to 2 is conceivable. The plurality of sectors to be selected is thereby preferably based on the desired resolution for the cellularly structured environment map and based on the means available for the evaluation and for the route planning of the autonomous mobile unit. It is advantageously assured by the inventive method that, with the assistance of these direction-dependent sectors for degree of occupancy values, degree of occupancy values of individual cells that are modified by different sensors can only be modified in chronological succession in such form that all sensors are made equivalent with respect to their measuring direction in the cellularly structured environment map and the modification of the degrees of occupancy values for the respective sectors. For example, one can thus prevent that a timeout measurement that arises in that a sensor measures an obstacle obliquely, whereby the sound is then completely reflected thereat, this leading thereto that an echo may potentially arrive tardy at the sensor, does not relate to the same sensor as that which was modified by a different sensor for assigning the degree of occupancy of the same cell. What is thus avoided is that obstacles that are present and that were reliably detected by a sensor can in turn be deleted from the map due to the incorrect measurement of another sensor. What is likewise achieved is that dynamic obstacles that move through the measuring cone of a sensor can quickly be deleted from the cellularly structured map because the degree of occupancy is preferably immediately reduced in turn where the same sensor no longer encounters an obstacle in this sector in its mixed measurement.

[0032] Inventively, a polar histogram for the obstacle representation exists for every grid cell Z(i, j). This has an arbitrary angular resolution ψ_o, so that a whole number n=360/ψ_oderives for the plurality of sectors. For example, ψ_o=22.5 (n=16) was selected in the experiments. Every sector κ thereby corresponds to a discrete angle δ

[0033] δ=κψ_o,κε{0,1 . . . ,n−1}  (b 0.4)

[0034] that is a multiple of ψ. The sector κ is then calculated from the angle β_sfrom which the corresponding grid cell Z(i, j) was seen by the sensor s, as

[0035] κ=floor(β_s/ψ_o)  (0.5)

[0036] An occupancy degree BEL

[0037] BEL_K(i,j)ε{0,. . . ,BEL_max}  (0.6)

[0038] with, for example, BEL_mas=15 exists per sector κ for each grid cell Z(i,j). The entire occupancy degree GBEL of a grid cell is preferably calculated from the sum of all occupancy degrees BEL. When the sum exceeds the maximum value BEL_max, then the sum is preferably limited to BEL_max $\begin{array}{cc}\mathrm{BEL}\left(i,j\right)=\min \left(\sum _{k=0}^n{\mathrm{BEL}}_k\left(i,j\right),{\mathrm{BEL}}_{\max }\right)& \left(0.7\right)\end{array}$

[0039] As an example Figure [. . . ] shows a single grid cell of an environment map with, for example, 8 sectors. The sectors 3, 4 and 6 thereby exhibit an occupancy degree unequal to zero. The different gray scale tones thereby indicate the level of the respective occupancy degree. The entire sector information is preferably stored once per grid cell.

[0040] FIG. 4 shows an example of a sensor that measures an obstacle H1 in the environment. The sensor S, the obstacle H1, the measuring imprecision MG, the symmetry axis of the propagation cone A, the aperture angle of the acoustic tone ψ_sand a blind zone BZ of the sensor are shown. Further, a clearance FR between the blind zone and the obstacle H1 is shown. Cells of the environment map that are located within the blind zone BZ are preferably not modified in terms of their occupancy degrees as a result of the inventive method.

[0041] The minimum physical measuring distance S_blindis mainly defined by the transmission power of the sensor. When an object is located within the blind zone and within the acoustic lobe of the ultrasound sensor, the sound is multiply reflected back and forth between the sensor and the object before the sensor is ready to measure after the decay of the membrane [sic]. As measured result, one obtains a value in the proximity of S_blind, whereby the returned measure value can also easily lie a few centimeters above this. The minimum measuring distance S_min

[0042] S_min=Sblind+δ_b  (0.8)

[0043] is therefore defined beginning with which an ultrasound sensor is sure to supply exact distance values. Given a blind zone expansion δ_bof 3 cm, the minimum measuring distance in trials amounted to 12 cm. It can be stated as a result that no precise statement about the distance of an object within the blind zone can be made given measuring values less than S_min. An object can potentially already be very close to the sensor or at the limit of the blind zone as well.

[0044] Given the ultrasound system employed, the maximum measuring distance S_max(“timeout distance”) is set by software within the predetermined limits. For example, a sensor thus maximally waits for the time T_usbefore the maximum distance S_maxis returned as measured result. When no ultrasound echo was received, timeout measurements in interiors generally indicate mirror reflections wherein the emitted sound no longer returned to the sensor. Accordingly, such measurements are preferably as reflections. When a measured value is situated between S_minand S_max, two information can preferably be acquired from this one measurement. First, the reflecting measured object lies somewhere in the region of acoustic cone at a distance d_sfrom the sensor. Second, no object visible for ultrasound is located in the acoustic cone region between S_minand d_ssince the distance thereof would otherwise have been measured.

[0045] There are at least two possible interpretations in the interpretation of the unoccupied information. First, it can be a matter of a mirror reflection, whereby the emitted ultrasound signal no longer returns to the sensor. Second, free space can actually be located in front of the sensor, so that no echo can be received. A third possibility is comprised therein that a sought object such as, for example, a cushion completely absorbs the ultrasound. This, however, cannot be recognized solely with ultrasound sensors. However, the case of complete absorption practically never occurs. When mirror reflections are fundamentally assumed given a timeout measurement, the measurement is simply ignored and the obstacle occupation of the cells within the acoustic lobe will not be deleted or lowered since, of course, value occupied information could be deleted. Given a real mirror reflection wherein an obstacle is located in the proximity of the sensor, this procedure is definitely correct. When, however, actual free space is located in front of the sensor, the unoccupied information acquired by the sensor measurement is not interpreted. Ignoring unoccupied information can raise great problems when grid cells had previously been incorrectly occupied with obstacles. Faulty occupations of grid cells, for example, ensue constantly due to the directional uncertainty of a measurement caused by the broad acoustic lobe. Serious faulty occupations can also be caused by dynamic obstacles. When a dynamic obstacle is visibly located in the measuring area of a sensor, then the occupied condition of the grid cell lying on the acoustic axis at the measuring distance d_sis correctly incremented according to the sensor model. The occupied condition, however, is only correct for a short time span as long as the obstacle is located in the proximity of this grid cell. When this obstacle continues to move, occupied obstacle cells—incorrectly—remain in the map and these could prevent continued travel of the robot. When another visible obstacle is located behind the incorrectly occupied cells, this is not a problem since it would be very quickly deleted by obstacle measurements. When, however, free space such as, for example a corridor is located behind these cells, then only timeout measurements would ensue and these would not delete the incorrectly occupied cells due to non-interpretation of the free information. The occupied cells would certainly block continued travel. Preferably, ultrasound distance measurements are entered as follows in the cellularly structured environment map. The fundamental idea of Borenstein [1] is thereby essentially applied. A high degree of occupancy of a cell therein denotes that there is great plausibility that an obstacle is located in the corresponding cell of the environment map. Only the cell content of a single cell is preferably incremented per sensor measurement. In ultrasound measurements, this is preferably that cell that is located on the beam A and on which the sensor measurement comes to lie. All further cell contents along the beam axis are preferably de-incremented in the free space FR. This simple method requires only a little calculating time and can therefor be applied during travel. Movement of the robot as autonomous mobile unit thereby is more likely to have a positive effect on the map construction. Due to the entry of different measurements from different positions, the orientation uncertainty of a measurement caused by the aperture angle of the acoustic cone is very well compensated. According to the inventive method, however, the entry of an ultrasound measurement into the cellularly structured environment map is preferably undertaken on the basis of two cells. The one is the starting cell and the other is the ending cell. The starting cell is thereby the cell that is intersected first by the measuring axis A outside the blind area and the ending cell is that cell on which the object is located. I.e., the cell that is located at obstacle distance in the distance from the sensor on the axis A. Further details about this can be derived from German Patent 44 08 729 E2. The cells that lie between the starting and the ending cell in the free space FR are preferably de-incremented. The de-incrementation preferably begins outside the blind zone, since it has been shown after many tests with objects within the blind zone that measuring distances not only in the proximity of the blind zone but also between S_minand S_maxwere sometimes returned by the sensor system. It can thus occur that the measured object is located within the blind zone given a measured result between S_minand S_max. When, however, cell contents within the blind zone are never deleted, this leads to a significantly better collision avoidance behavior in very tight use environments.

[0046] FIG. 5 shows a measuring procedure that is improved by the inventive method. The autonomous mobile unit AE moves along a travel direction RF in a corridor, which is represented here by a wall W. This extremely smooth wall reflects ultrasound very well. The cells Z50, Z60, Z100 and Z500 from the environment map of the unit are shown here. During the motion event along the travel direction RF, the unit and its sensors S1 and S2 measure the wall and sectors are provided with degree of occupancy values according to the inventive method. Since the sensor S1 resides perpendicular to the wall, the ultrasound signal is reflected extremely well and is also received by it extremely well. In the region of the cell Z100, the sector SEK8, which corresponds to the perpendicular measuring direction in this case, is allocated to the sensor S1 in FIG. 5 as a result of the corresponding measuring direction. i.e., when this sensor detects obstacles in this measuring direction, then they are entered in this sector SEK8. When the wall W is extremely long, then the sector SEK8 will be constantly provided with an incremented degree of occupancy during travel. This derives therefrom that the sensor S1 constantly measures the wall and preferably increments the degree of occupancy of SEK8 with every echo. During continuation of the motion, however, the same sector or, respectively, the same cell Z100 is likewise measured by the sensor S2 of the autonomous mobile unit AE, this sensor S2 measuring obliquely relative to the wall. This situation is shown with reference to the cell Z500. It can be clearly seen that the axis or, respectively, the beam course STR of the wave front from the sensor is smoothly reflected by the wall, this leading to a timeout measurement given the distance S_max. According to the inventive method, however, this timeout measurement does not to the occupancy degree of the sector SEK being modified since this measurement ensues at an angle that, for example, is allocated to the sector SEK7. In this way, the inventive method avoids having correct measured results from cells of the environment map provided with degree of occupancy values being erroneously deleted due to mismeasurements.

[0047] FIG. 6 shows an applied instance wherein the inventive method leads to further advantages in the interpretation. In this case, for example, an obstacle HD has moved from left to right through the observation space of the sensor S4. This lead to the fact that the sensor S4 of the autonomous mobile unit, which moves along in the direction RF in the cell Z1000, occupied the sector SEK with a degree of occupancy that arose due to a distance measurement when the obstacle HD moved passed. In a further measurement following thereupon with the sensor S4, this obstacle can in turn be removed from the map with the assistance of a timeout measurement S_max, in that the degree of occupancy in the sector SEK8 of the cell Z1000 is de-incremented. The obstacle he rapidly moving past subsequently produces an elevated occupancy degree in the sector SEK7 of the cell Z2000 as a result of a distance measurement by the sensor S5.

[0048] The invention is not limited to the particular details of the method depicted and other modifications and applications are contemplated. Certain other changes may be made in the above described method without departing from the true spirit and scope of the invention herein involved. It is intended, therefore, that the subject matter in the above depiction shall be interpreted as illustrative and not in a limiting sense.