Method for Determining the Positions of a Plurality of Anonymous Fixed Reference Objects for Mobile Surface Transportation and a Device for Determining Said Positions

The present invention relates to a method and apparatus for determining the positions of a plurality of anonymous fixed reference objects for controlling the movement of surface transportation units.

The traditional technology for automatic control of vehicles AGV by means of following control loops in the surface has increasingly been replaced by more sophisticated control systems, such as systems which search for fixed reference points in a room. By knowing the position of the reference points and by measuring a plurality of angles to these objects, the position of the AGV can be determined and used for controlling the AGV to predetermined positions. U.S. Pat. No. 4,811,228 discloses a rotating laser which searches an area in which fixed reflecting objects are positioned, and measuring a plurality of angles between the AGV and the different objects, the position of the AGV can be determined.

When installing a new AGV system the positions of the fixed reference objects must be determined. Until now, this has, to a significant extent, been carried out manually by measuring the positions of the reference objects and entering these in a coordinate system which represents an area in which the AGV system is to be installed. To be more precise, the coordinate system generally represents a plane which extends parallel to the surface on which the vehicle AGV is intended to move. Determining the positions has therefore generally been carried out by physically measuring the position of the reference objects relative to the axes of the coordinate system, after which their coordinates have been entered into a computerized control system. The measurement is, however, time-consuming, and difficult to carry out in practice, since most rooms in which the AGV system has been installed also house large objects, such as storage shelves, machinery, and the like.

In accordance with the present invention, these and other objects have now been accomplished by providing a method for determining the position of at least one fixed reference object for use in controlling the movement of mobile surface transportation units over a surface comprising providing a mobile apparatus including a measuring point, detecting bearings from the measuring point to the at least one fixed reference object at a predetermined time associated with movement of the mobile apparatus over the surface, storing the bearings along with the predetermined time associated therewith, and continuously computing the position of the at least one fixed reference object and the degree of uncertainty associated with the position from the bearings whereby the degree of uncertainty is reduced as the mobile apparatus moves over the surface.

In accordance with one embodiment of the method of the present invention, the detecting of the bearings is carried out sequentially in time.

In accordance with another embodiment of the method of the present invention, the detecting of the bearings comprises detecting a plurality of the bearings for each value of time.

In accordance with another embodiment of the method of the present invention, detecting of the bearings comprises emitting, reflecting, and detecting an electromagnetic signal, preferably a light signal. In a preferred embodiment, the electromagnetic signal comprises a rotating laser beam extending substantially parallel to the surface from the measuring point.

In accordance with the apparatus of the present invention, apparatus has been provided for determining the position of at least one fixed reference object for use in controlling the movement of mobile surface transportation units over a surface comprising a mobile apparatus including a measuring point, a bearing detector mounted at the measuring point for detecting bearings from the measuring point to the at least one fixed reference object at a predetermined time associated with movement of the mobile apparatus over the surface, storage means for storing the bearings along with the predetermined time associated therewith, computational means for tracking the at least one fixed reference object as the mobile apparatus moves over the surface, and continuous computing means for continuously computing the position of the at least one fixed reference object and the degree of uncertainty associated with the position whereby the degree of uncertainty is reduced as the mobile apparatus moves over the surface.

In accordance with one embodiment of the apparatus of the present invention, the bearing detector comprises laser scanning means and angular detector means for sequentially detecting the bearing over time.

In accordance with another embodiment of the apparatus of the present invention, the bearing detector comprises camera means for detecting a plurality of the bearings for each value of time, the camera means including flash means.

In accordance with another embodiment of the apparatus of the present invention, the computational means includes prediction shelters.

In accordance with another embodiment of the apparatus of the present invention, the at least one fixed reference object comprises a plurality of reflector means.

In accordance with both the method and apparatus of the present invention, manual measuring can now be eliminated.

The present invention will be more fully understood with reference to the following detailed description, which itself makes reference to the appended drawings, in which:

FIG. 1 is a schematic representation of a room in which the AGV is to be installed for use in accordance with the present invention;

FIG. 2 is a diagram showing measured time-angle pairs for use in accordance with the present invention; and

FIG. 3 is a flow chart showing the method according to the present invention.

Referring to the drawings, FIG. 1 shows a schematic plan view of a space in which an AGV system has been installed. In the example shown, the system is based on U.S. Pat. No. 4,811,228, the disclosure of which is incorporated by reference herein, which describes the use of a rotating laser beam, which searches a plane which, for example, extends horizontally and essentially parallel to the floor on which an automatically controlled vehicle AGV is intended to move. The rotation thus principally takes place around a generally vertical axis. In the example shown, the room in question has been drawn as a square room 1 with four walls, 2, 3, 4 and 5, on which a plurality of anonymous fixed reference objects 6-16 have been positioned at such a height that they are within the search area of the laser beam. In practice, the reference objects extend vertically to such an extent that it is always possible for the object and the beam to coincide. In the system in question where the issued signal is an electromagnetic signal, such as light, for example a laser beam, the reference objects are reflector organs which are arranged to reflect an incident beam back to the laser unit where it is detected, together with information about its bearing, i.e., the angle in the plane of rotation relative to a chosen reference-angle, for example, the longitudinal axis of the vehicle. The reflector organs are preferably such that the incident beam is reflected in the same direction as the incident direction, that is so-called retro-reflectors. The reflector organs are positioned at fixed positions, which can be chose arbitrarily. In the simplified case shown in FIG. 1, the reflection organs are, however, arranged along four planes, i.e., the walls, but in practice the reflection organs can be positioned irregularly and arbitrarily in the room.

Essentially the same equipment as discussed above can be used for determining the positions of reflectors, in the simplest case, comprising a vehicle with a rotating laser. Reference numeral 17 represents the measuring point, normal to the plane of the paper, around which, for example, the search beam rotates in the measuring room 1. According to the present invention, the positions of the fixed reference objects 6-16 are determined and possibly also directions in a plane by searching the plane by means of a sweeping search-signal while detecting returned echo-signals together with the detection of information with respect to the bearing of the echo-signal. Detection takes place during movement of the measuring point 17 in the room 1, whereby a plurality of further measuring points 18 is obtained, which in principle are arbitrarily distributed across the room. In practice, the simplest way of achieving this is by moving or driving the equipment or vehicle around in the room during repeated measurement, the application of a technique called "multilinear constraints in continuous time" makes it possible to make the measurements while the vehicle with the rotation laser detector is moving.

During continuous movement a number of angles or bearings fixed in time can thus be obtained. These time-angle pairs can be illustrated in a diagram, as shown in FIG. 2, where each point of coordinates (t,.alpha.) corresponds to a measured angle .alpha. with a time t. The gaps shown times when, for example, an obstacle has been within the line of sight when it was to make a measurement. False reflections are shown by small dots which do not form a regular pattern.

The present invention further describes an analysis of the angle material measured, which results in determining the coordinates of all the reflector organs. In order to obtain this, the following steps are carried out:

A. Automatic association of bearings to anonymous objects:

First, those angles are identified which have been measured to the same, anonymous reflector organ. This is effected by extrapolating earlier angle measurements and checking which of the subsequent angle measurements matches with this extrapolation. It also allows correct identification even if the reflector is temporarily hidden from the laser beam. The result is that part of the angle measurements can be grouped into subsets of the time identity, while other, spurious measurements can be sorted out.

B. Calculation of reflector positions and position uncertainties:

Starting from a crude estimation of reflector positions and a corresponding high degree of uncertainty, as the vehicle moves along and the bearings to the reflectors become available from a larger area of the floor, the position estimations are refined and the position uncertainties correspondingly reduced by application of the "continuous trilinear constraint" technique (as described in "INVARIANCY METHODS FOR POINTS, CURVES AND SURFACES IN COMPUTATIONAL VISION" by Kalle .ANG.strom, Lund Tekniska Hogskola, May 30, 1996, ISBN 91-628-2022-2, ISSN 0347-8475, ISRN LUTFD2TFMA-96/1006-SE, ISRN LUTFD2TFMA-96/5002-SE) involving complex matrix calculations using e.g. the Newton-Raphson method. The above reference is hereby incorporated in the present application by reference thereto.

In accordance with the present invention, the relative motion of the vehicle can be calculated without odometry or any prior knowledge of its motion. The relative motion is thus calculated from the bearing measurements only, using multilinear constraints in continuous and discrete time.

Assuming that the bearing measurements have thus been placed in groups corresponding to the same reflector, it is possible to interpolate and find the bearing and the first two derivatives of the bearing with respect to time. Equation 1 below relates these measured quantities with the unknown relative motion of the vehicle. In this equation u.sup.(0) is the unit vector describing the direction of the bearing, u.sub.(1) represents the first and u.sup.(2) the second order derivatives of this direction (the bearing) with respect to time. Using Algorithm 3.4.1 (see below) it is possible to calculate the velocity vector (v1, v2) and the acceleration vector of the vehicle (a1, a2) as well as the angular velocity of the vehicle (r1). The bearings to at least five different reflectors are needed to calculate the unknown parameters. These motion parameters are thus obtained from image measurements only. Neither odometry, nor the reflector positions are required. In fact, by using this method odometry data is obtained form the bearing measurements alone.

The angular and positional velocity of the vehicle is used to calculate the motion of the vehicle using traditional dead-reckoning. Once the relative motion of the vehicle is known, the coordinates of the reflectors are calculated using triangulation. The measured bearings to a reflector from two different locations are used to find the coordinates of the reflector.

The calibrated continuous trilinear constraint is disclosed in .ANG.strom, mentioned above, as follows:

Consider the time dependent calibrated camera matrix P(t)=(R(t) c(t)).

Choose object coordinate system so that P(0)=(I 0). Let the taylor expansion of the rotation matrix R(t) and the vector c(t) be

the following continuous calibrated trilinear constraint must hold for every image point u(t) with taylor expansion u(t)=u.sup.(0) +tu.sup.(1) +u.sup.(2) R.sup.(2) +o(t.sup.3) ##EQU1## Since R is a rotation matrix its first derivative is of the form ##EQU2## and the second part of the taylor expansion is of the form ##EQU3## By subtracting r.sub.2 of the fourth column to the second, we see that the constraint does not involve R.sup.(2). The constraint will now be studied in a little more detail. Introduce variables according to ##EQU4## The determinant is of the form ##EQU5## where ##EQU6## Introduce w=(v.sub.1 v.sub.2 a.sub.1 a.sub.2) and z=(1 r.sub.1).sup.T. Two tentative algorithms to find have been tried.

Algorithm 3.4.1.

1. it might be possible to get a rough idea of the rotational velocity r.sub.1. Usually it is quite low.

2. For all image directions u.sup.1 (t) calculate corresponding T matrix, here denoted noted T.sup.1. The vector w should be orthogonal to every vector T.sup.1.sub.z. Given r.sub.1, w can be found as the left null space of matrix

The vector w is found by singular value decomposition of the above matrix.

3. Similarity once w is known approximately, z can be found as the right null space of ##EQU7##

4. Repeat steps 2 and 3 and hope that the process converges.

The above idea has only been tried experimentally, but it has been succesful so far. Further research is needed.

Algorithm 3.4.2.

Another approach is to estimate

S.sub.1 =v.sub.1, S.sub.2 =v.sub.1 r.sub.1, S.sub.3 =v.sub.2, S.sub.4 =v.sub.2 r.sub.1,

S.sub.5 =a.sub.1, S.sub.6 =a.sub.1 r.sub.1, S.sub.7 =a.sub.2, S.sub.8 =a.sub.2 r.sub.1,

as the right null space of ##EQU8## and then impose the additional constraints that ##EQU9## The motion parameters (r.sub.1,v.sub.1,v.sub.2,a.sub.1,a.sub.2) can then be found by singular value decomposition.

The two principal steps A and B discussed above can then be applied sequentially in an outer and an inner loop, in accordance with FIG. 3.

The flow chart of FIG. 3 further shows how these above-mentioned steps can be applied. Thus, in the inner loop the bearing and time values are sorted and associated with the reflectors. The prediction filters used take into account the movement that is continuously imposed on the vehicle. The outer loop is performed when a sufficiently high number of measurements and/or a sufficiently high number of additional reflectors has been added. First, the already known reflector positions are refined, and these new values then constitute the basis for calculating the positions, and uncertainties, of the additional reflectors. When the position of all reflectors has been calculated and the position uncertainties have been reduced to the required level, the reflector map is complete and the measurements finished.

In the example in question the reflector organs 6-16 have a limited are of reflection, within which detection can be obtained, which may be used for determining the direction of the reflector organs 9 and thereby also whether a received reflex has been received form a certain reflector organ. The measurement equipment comprises a computer for collecting measuring data relating to received reflexes and their bearing.

Although embodiments of the present invention have been described in detail with reference to the appended figures, it should be realized that the present invention is not limited to these specific embodiments, and that different changes or modifications can be made by a person skilled in the field without deviating from the scope defined by the appended claims. The reference objects can, for example, be natural objects in any environment.

Furthermore, for each time value, more than one bearing may be registered, e.g., by detecting a plurality of object bearings simultaneously with the aid of a matrix detector (e.g., a camera/flash system).