Method for updating in a wheeled vehicle steered by dead reckoning.

In our Swedish patent application 7900993-2 there is demonstrated the possibility of steering a vehicle to follow a certain trajectory which does not need to be marked on the supporting surface, by allowing the vehicle to be moved from a starting position with roll-off measurement of its movement as regards distance and direction. Making an analogy with the age-old principle of navigation on the open seas where there are no fixed points of reference, this method of steering has been called dead reckoning steering, and further information is to be found in this application.

As was mentioned in the application, it is not possible to steer a vehicle according to this principle indefinitely because it is unavoidable that errors in following the intended path will gradually accumulate. It is true that in the tests we achieved errors of the order of only 10 cm after travelling 100 m with several turns, but it is still apparent that there is a need for updating. This is especially true if the vehicle is to function in a transport system with narrow warehouse aisles, where an accumulated error can cause collisions.

Thus the invention relates to a method of arranging updating in a vehicle steered by dead reckoning, with the aid of markings arranged on the floor, there being in the vehicle a unit continuously updated by rolling-off means, said unit registering position and attitude of the vehicle computed by dead reckoning.

The purpose of the invention is to achieve such updating with means which are as simple as possible. According to the invention, a linear detector is used, fixed securely to the vehicle and detecting a linear track or a marking on the floor. It can be suitable to arrange one or more such markings in such a manner that the vehicle will pass over one with acceptable frequency. A linear detector suited to this purpose must be able to determine its position in relation to the marking, in a form of a lateral deviation.

The use of an optical linear detector is primarily intended. Such detectors are known which comprise a row of light-sensitive detectors each of which can determine the presence or absence of a marking in an image of a portion of the supporting surface, preferably consisting of a narrow strip or slot transverse to the vehicle. In such a device it is suitable to carry out the measurement as a repeated sampling operation, whereby each time the distance is determined between the image of the line and the midpoint of the linear detector. It is also suitable to use some type of recognition operation to determine with high probability that the marking observed actually is the one intended and not a branch or refuse on the floor. For this purpose it is suitable to give the marking the shape of a recognizable line. An example of this is a marking consisting of two parallel stripes of different width, which are suitably recognized by a correlation method.

It is also possible to use a linear detector which is based on electromagnetic principles and detects markings designed for such sensing. A known type of such markings consists of an electric conductor placed in the floor, which conducts alternating current. The linear conductor can then consist of two detector coils, each of which measures an electromagnetic signal from the conductor. If the conductor lies directly beneath the centre of this linear detector, the two detector coils will receive signals of equal size, but the signals will differ if there is a lateral deviation. It is thus possible to obtain a measure of the lateral deviation,albeit as a rule with somewhat poorer precision than with said optical means.

The special advantages and characteristics achieved according to the inventive method for updating are obtained according to the invention by virtue of the fact that the supporting surface is provided with a marking of limited extent, comprising at least one straight line; that the vehicle has a linear detector arranged transversely thereto and that the vehicle is near the marking, an intersection of the linear detector with the marking being determined at least twice; that the distance between the two determined intersections is taken as.a first distance; that the distance measured on the linear detector between the two points of intersection is taken as a second distance; and that from the two said distances, the angle is calculated between the vehicle and said straight line of the marking.

In accordance with a second aspect of the invention, the lateral deviation of the vehicle in relation to the straight line is measured by means of the linear detector. If such a lateral deviation is first measured in relation to a first line of the marking and thereafter, preferably after the vehicle has swung 90° from its position at the first measurement, a second measurement is made of the lateral deviation there, one can.determine where the vehicle is in a system of coordinates. In general, the essential feature of the method is that by means of the markings which are read by a linear detector, it is possible to determine the actual position of the vehicle.

A precondition for obtaining a reliable and complete updating by means of a single-line marking on the floor is that it be possible to determine not only the lateral deviation and direction, but also obtain a measure along the length of the marking line. In accordance with a preferred embodiment, this can be done by arranging an additional line element, which forms an angle with the first. It is then possible by two successive measurements of the two line elements, which vary in the distance between them as the vehicle moves, to determine for example where the vehicle is located in relation to a point of intersection between these two lines. It is not necessary that either of the lines physically extend to the point of intersection. It is also possible to arrange two intersecting lines in the form of a triangle point and in an analogous manner determine where the vehicle is by having the linear detector measure at two successive times the intersection of the two lines with the line detector, which one will find will provide an unambiguous statement of the location of the vehicle.

It is known to arrange dead reckoning steering in such a manner that the vehicle is normally steered along some type of path, e.g. a curved loop, from which the vehicle deviates under dead reckoning steering, and then returns to the curved loop. What happens here is -not actual updating, but approach steering. The essential feature of the invention however is the obtaining of new coordinate values, and the steps taken therefore need not necessarily consist of steering into a marked path; rather, correction can be done gradually or by making a subsequent turn earlier or later. This has the advantage that the markings according to the invention can be relatively short or limited, since the intention here is not steering-in but updating.

Although according to a presently preferred embodiment it is suitable to arrange a single-linear detector in the vehicle and make two successive measurements while the vehicle is in motion, it is also possible to arrange two different parallel linear detectors, each making a measurement and where the distance between them is known.

Although it is presently preferred to obtain the complete coordinates of the vehicle for updating by merely taking measurements to line markings by means of a one- dimensional linear detector, or alternatively two parallel linear detectors, it is also possible to obtain a distance reading along a line by special distance markings. These can of course consist of the beginning or end of the marking, but if one wishes to work witha sampling linear detector, which only takes "momentary pictures" at certain intervals, this would produce a possible longitudinal error corresponding to the distance between two samplings; and therefore it can be suitable to arrange a separate longitudinal sensing, e.g. in the form of ferromagnetic markings. This can be done in many different ways, and is dependent on local conditions. In many cases the floor may contain iron objects placed there for other purposes, and a steel threshold in a door can often serve as a distance marker if it is sensed with magnetic means. It is also possible to arrange a separate marking, e.g. small permanent magnets laid in the floor, which when passed over trigger a marking signal, which supplements the measurements of lateral deviation with a linear detector. It will thus be understood that there are enumerable variations possible within the scope of the present inventive idea.'

The invention will now be described in more detail with reference to an example. <ul id="ul0001" list-style="none"><li>Fig. 1 shows a vehicle for applying the invention.</li><li>Fig. 2 shows a block diagram and wave patterns.</li><li>Fig. 3 shows an example with intersecting markings.</li><li>Fig. 4 shows schematically with reference to Fig. 3 how the intersection of the markings can be determined.</li></ul>

Fig. 2 shows schematically an example of a device for recognizing the position on the floor of a line pattern. A video camera 1 is directed towards the floor, which displays the linear pattern P transverse to the camera. The video camera 1 is suitably a single-row photodiode matrix, e.g. manufactured by Reticon, and divides a line into 256 elements. A video signal is emitted, consisting of an analog signal for each element. The video signals are conducted to a threshold detector 2, which emits binary signals; i.e. 256 bits are emitted, which are 0 or 1 depending on whether the intensity is sufficient to indicate the presence of the marking in the photo-element. 3 represents a video signal prior to digitalization, with the threshold value T drawn in, and 4 shows the resulting binary video signal. This signal, designated BV, is read in via a gate system into a binary shift register 5 with 256 bits. An ideal pattern, corresponding to the expected configuration (here two lines of different width) is read into a pattern memory 7. To determine lateral deviation, a correlation operation is now carried out.

If the pattern of the video signal is "centered" in the camera, shift register 5 and shift register 7 should in principle contain identical bit series. Through a special comparison which will be described, a lateral deviation can be determined.

As can be seen from Fig. 2, there are two different clock signals, namely the signal CL coming from the camera 1 and synchronized with the video signal, and a fast clock signal FCL which is used for transferring and coordinating purposes. For reading the video signal BV into the shift register 5, the signal CL is used, which is introduced via the switch 9, and under the control of a shift-pulse counter 11, which shuts off when all of the 256 bits have been read in, and under the control of a control signal R.

For comparison, the fast clock signal FCL is led under the control of the shift-pulse counter 11 to the clock input on the shift register 5 and under the control of the shift-pulse counter 10 to the clock input on the shift register 6. The signals coming from the shift registers each go to an individual input of a comparator 8, and are also recirculated under the control of a recirculating signal RC, so as to circulate the respective shift registers. For each bit pair, the comparator sends a signal upon agreement, and the agreement signals are counted in a counter 12, which is provided with parallel outputs coupled to a comparator 14, which is also coupled to a memory 13.

Due to the fact that the shift-pulse counter 10 has the division factor (256+1), it will send an out-signal one pulse later, so that the shift register 6 will be shifted one pulse for each circulation. This pulse number 257 continues to a pulse counter which counts the number of sepa- __ rate comparisons, and after 256 cycles sends a stop signal.

For each loop, the number of agreements signalled from the comparator 8 is counted, and if the number of agreements exceeds the number stored in the memory 13, the circuit 14 will bring the higher number to the memory 13. At the same time,the number in the counter 15 is taken into the memory 16. When the pulse counter 15 is full, when 256 comparisons have been made, there will be a number in the memory 16 which corresponds to the displacement between the shift registers 5 and 6 which produces the best agreement. It is then known how the pattern P lies in relation to the scanning field of the camera 1, at the same time as a ready-signal N is emitted from the pulse counter 15.

It is obvious that the control signals must be taken from a separate control unit which determines the operational sequence by sending signals R and LP at the beginning of each sampling sequence and then requesting a comparison by the signal RC. The sampling result can then be taken from the memory 16 as a measure of the lateral error; for example so that the number 128 designates that the camera/vehicle is directly over the marking (the position of the index point), a lower number indicating a lateral deviation to the left and a higher number a lateral deviation to the right of the index point.

Although this description of the sequence is quite schematic, it will enable the electronics engineer familiar with microcircuits to construct with standard components a suitable apparatus.

After explaining how a lateral deviation is measured in relation to the linear detector 1 and thus to the vehicle, it will now be explained how the position of the vehicle in the direction of motion is measured according to a special aspect of the invention.

Fig. 3 shows an example with two different line patterns A and B. Pattern A is assumed to fall along the path of the vehicle, while pattern B forms an angle with pattern A. Fig. 3 shows schematically at lines 30 and 31 how the video signals appear when the camera is directed at them. Two patterns A and B appear side by side.. Referring to what was said with respect to Fig. 2, if pattern A is the pattern stored in the pattern memory 7, then this pattern will provide the best correlation, thus providing a value of the lateral deviation for the pattern A, with the existence of pattern B at most resulting in a certain reduction of the highest number of correspondences in the comparator 8.

In the measurement to be made according to Fig. 3, a corresponding lateral deviation must be obtained for pattern B. Although this can be done in another operation with the same apparatus, it is preferable to duplicate the apparatus in Fig. 2 and to store pattern B in the memory 7 of the duplicate apparatus. After,a-completed loop, the lateral deviation for pattern B will be stored in the corresponding memory 16 in the form of a number between 0 and 256.

For each sampling, such as the samplings 30,31 in Fig. 3, the distance between the patterns A and B is computed, and this number is obtained by taking the difference between the numbers in the two memories corresponding to memory 16 in Fig. 2. Successive values are stored together with the values of the distance on the floor between the samplings.

In principle it is possible to know the position of the vehicle after two samplings. If the difference between the numbers according to the sampling 30 in Fig. 3 is called a₃₀ and the corresponding number for the sampling 31 is called a31, and the rolled-off distance in the direction of motion of the vehicle is called s₃₁, the elementary geometrical relation of two similar triangles reveals that<maths id="math0001"><img file="EP0050101A1_D0001.tif" /></maths>which when solved for y gives<maths id="math0002"><img file="EP0050101A1_D0002.tif" /></maths>where y is the distance between the point of intersection M and the sampling position 31 in Figs. 3 and 4. It is thus possible to determine the actual position of the vehicle, if y and the lateral error for the pattern A at sampling 31 are known, and it is thus possible to update the value which the vehicle "believes" is its position as calculated by rolled-off measurements according to the dead reckoning method.

After having described the principle method for recognition of markings, a few words should be said concerning redundance methods. It is obvious that the pattern may be misread at some time; sometimes because something else is mistaken for the pattern. One should note, however, that in the circulation according to Fig. 2, after comparison between the pattern in the memory 7 and the image in the memory 5, a number will be stored in the counter 13, which will be a sort of quality factor number. It is then possible to reject or accept measurements depending on whether this quality factor number exceeds a certain threshold value. In a compensation method based on the least-squares method, it is also possible to use the quality factor numbers as weighting numbers.

Instead of using successively incoming measured values, it is also possible to use sliding averages, both for determining the lateral deviation of the vehicle and its attitude. A person skilled in statistical methods will be able using such principles to formulate suitable computer programs without difficulty, when he has knowledge of the principle of the invention. The principle chosen depends largely on the computer capacity which one wishes to incorporate into the apparatus. Significant savings can be achieved in this respect by taking sliding averages. We will now describe the detailed interaction with the dead reckoning method with reference to an example. It is assumed that a truck steered by dead reckoning, e.g. a truck described in the patent application mentioned in the introduction, is started from a known position with the attitude angle ϕ and coordinates x and y all set at 0. The assumed coordinate system here is not a Cartesian system but a path-centered system, where x denotes the lateral deviation of the truck from'a trajectory and y is a measure of the rolled-off distance along said imaginary, non-physical trajectory.

Dead reckoning will now provide the truck at each instant with computed values of f, x and y. These values will gradually become less reliable because of the cumulative errors. Therefore markings are arranged somewhere along the path, for example those revealed in Fig. 3.

When dead reckoning produces a value, especially the value of rolled-off distance y, which corresponds to the position of the marking, the recognition and updating sequence is initiated. As stated above, a value of the distance travelled, corresponding to y, and a value of the lateral error x are obtained.

At least two lateral error values in combination with intermediate short travelled distances will provide a value of the attitude

These values can now replace the values obtained by dead reckoning.

It is also possible to compute and save for later correction the difference between the dead reckoning position and the updated position. From a series, of such differences it is possible to compute systematic errors. For example, the rolled-off values can be erroneous because the effective wheel circumference is less than calculated, either because of wear or due to the effect of the load. Such errors can then be compensated for.

As was mentioned in the introduction, it is also possible to carry out the updating without the use of angled markings, if the lateral error is measured relative to two different markings with, for example, a 90° turn between them. If the first update is for x and ϕ, the lateral error measured after the turn will correspond to the actual longitudinal error in the path, and this measurement can be used for correcting y.

Fig. 1 shows a fork-lift truck which is steered according to the invention. A pair of lines L is painted on the floor, and a linear detector 1 is directed at it. For'dead reckoning navigation, the two supporting wheels 30 and 31 are provided with sensors 32 which emit signals when the teeth of gears fixed to the wheels pass by said sensors, to give a measure of the rolled-off distance. As described in the above-mentioned Swedish patent application, dead reckoning can be done on the basis of signals from these sensors 32 (of which only one is shown), and steering is normally accomplished via the steering wheel 33, which is coupled via a connector member 34 to a steering means 35, which sets a steering angle δ. In accordance with the invention, the steering angle 6 can now be set via the steering means 35, based on the values ϕ Δx taken from dead reckoning, when the vehicle is functioning according to the dead reckoning method. The dead reckoning variables can now be replaced according to the invention with fresh or updated values obtained from passage over a marking.