TECHNICAL FIELD OF THE INVENTION

The present invention relates to a method for managing an automatic warehouse and for locating a mobile target, such as a person or a manual guided vehicle.

TECHNICAL BACKGROUND

Typically, the localization of mobile targets in industrial areas is carried out by arranging a plurality of fixed reference nodes, indicated as anchor nodes (or anchors) and equipped with antennas.

The target sends signals or beacons to the anchors, which detect such signals and send them to a centralised controller that uses the signals received to estimate the position of the target, for example by means of triangulation algorithms.

Such system requires the installation of reference nodes in the environment, with at least one antenna per node, in different positions, resulting in high installation costs and computational complexity in the management of communications between the devices in the warehouse. To this end, it is possible to consider more advantageous an illustrative example wherein, in place of the anchors distributed in the environment, 4 nodes are positioned on an AGV (Automatic Guided Vehicle) and the localization of the mobile target is carried out on the basis of a TWR (Two-Way Ranging) method between each node and the target, i.e. using the distances between each node and the target. Such a solution is taught for example in US20160291597.

The use of Time Difference of Arrival (TDoA) distributed measurements is taught in U.S. Patent US 7 170 441, according to which the beacon from the target is received by a plurality of anchors and the target position is estimated by extracting TDoA information through the beacon. Also in this case all the measurements coming from the plurality of receiving elements are used in a localization algorithm. The use of localization using distributed measurement units is also taught in U.S. Patent US9623558B1 to inhibit robots working in the vicinity of localized human operators. This patent proposes to triangulate the TWR-based estimates from the distributed wireless measurement units and to determine a region of interest in which the human operator can be present and at the same time inhibit the robotic unit.

Since in the presence of a greater number of transmitting and receiving antennas the complexity of a localization algorithm can rapidly increase, the US patent application published with number US20070005292 explores the idea of breaking down the problem into a sequence of very small subproblems, each of them solved through a relaxed semi-defined programming approach of a geometric optimization model. Subproblems can be generated based on a set of sensors / anchors selection rules and a list of priorities.

OBJECTS OF THE INVENTION

An object of the present invention is to provide a new method for the localization of a mobile target inside an automatic warehouse, such as a person or a manual guided vehicle.

Another object of the present invention is to provide a method as mentioned above which guarantees to avoid collisions between an AGV and mobile targets.

Another object of the present invention is to provide a method which allows to reduce the estimate of the error, while guaranteeing a reduction of the computational complexity in the presence of a large number of targets and anchors.

According to one aspect of the invention a method according to claim 1 is provided.

The dependent claims refer to preferred and advantageous examples of embodiments of the invention.

BRIEF DESCRIPTION OF THE DRAWINGS

Other features and advantages of the invention will be more apparent from the description of an exemplary embodiment of a method according to the present invention, illustrated by way of example in the accompanying drawings, wherein: - figures 1 to 6 schematically illustrate an AGV, with an illustrative (but generalizable) number of 12 anchors on board, usable in a method according to the present invention with the anchors of a respective sub-unit highlighted;

- figure 7 illustrates an example with position estimates using a localization method which is based on different sub-units of anchors; and

- figure 8 is a graph that illustrates an estimate of the average position for various positions of a target, comparing a standard TDoA method with evaluations carried out on all twelve anchors present on an AGV and a method according to the present invention with evaluations carried out on sub-units of 7 anchors suitably selected from the 12 anchors available on the AGV.

In the accompanying drawings, identical parts or components are distinguished by the same reference numerals.

EXEMPLARY EMBODIMENTS OF THE INVENTION

The present invention relates to a method for the localization of a mobile target in an automatic warehouse or in any case for the localization of a mobile target, such as a person or a manual guided vehicle.

Such method first of all provides preparing in the warehouse a mobile target equipped with at least a signal emitter, as well as an automatic guided vehicle 1, such as an LGV (Laser Guided Vehicle) or an AGV equipped with a plurality of anchors 2 for receiving and, if desired, emitting signals.

More specifically, the automatic guided vehicle 1 has a frame 3 mounted on wheels or tracks, while the anchors 2 are mounted at respective points on the frame 3.

The anchors 2 are each equipped with at least one respective antenna designed to receive / emit signals.

In turn, the mobile target 4 is equipped with a marking, which marker includes at least one antenna capable of receiving / emitting signals. More specifically, the target 4 periodically emits, with a sufficiently small period, the signal or signals.

The emission / reception anchors 2 of the vehicle 1 and the marking of the mobile target 4 can use electromagnetic waves of the same type, for example ultra wide band , in the abbreviation UWB, or they can also use other types of transmission signals based on electromagnetic waves, for example Wi-Fi or Bluetooth (trademarks registered by their respective owners).

In particular, the automatic guided vehicle can have a plurality of anchors, for example 5, 6, 7, 10, 12 or more anchors managed by a centralised processing unit on board of the LGV or of the AGV itself, which anchors on board of the vehicle 1 perform the function of fixed anchors which are mutually integral.

In any case, a method according to the present invention, after the steps of preparing at least one automatic guided vehicle 1 and of at least one mobile target 4, provides:

- to emit a signal by the emitter of the mobile target 4,

- to receive the signal emitted by the mobile target 4 by the anchors 2,

- to classify (for example by means of a UWB transmitter as described below), by each of the anchors 2, the signal emitted by the mobile target 4 and received by the anchors 2,

- to make a first rough estimation of the position of the mobile target 4 so as to establish or select the area or quadrant of warehouse around the AGV in which it is located, after defining a suitable number and conformation of such areas,

- to establish or select one or more sub-units or subsets of anchors 2 for the calculation of the accurate position (obtained starting from the signals received through the TDoA method) of a mobile target 4.

In this regard, the subdivision of the warehouse area around the LGV or AGV can be carried out by dividing it into two, three, four or more areas and establishing for each of these areas which list of anchors is more reliable (for example the anchors visible with respect to the mobile target) when receiving the signal emitted by the mobile target 4.

More specifically, supposing to divide the warehouse area around the LGV or AGV into four zones or quadrants, for each of these areas it would be established which list of anchors, for example 5, 6, 7 or 8 out of a total of 10, 12 or 14, it is the most visible in each area or quadrant.

To evaluate the area of the warehouse around the AGV or LGV in which the mobile target 4 is arranged, a first rough estimation of its position is carried out, or rather is carried out by the centralised processing unit. The first rough estimation is carried out by the centralised processing unit by means of the signals received from all or part of the anchors.

The centralised processing unit, once established, the warehouse area around the AGV or LGV where the mobile target 4 is located based on the rough estimate, identifies one or more sub-units of anchors to carry out a second accurate estimation of the position of the latter. The anchors 2 of each of the sub-units or subsets suitable for estimating the accurate position of the mobile target 4 can have an asymmetrical distribution on the automatic guided vehicle 1, i.e., as a whole.

Regarding to this aspect, in a possible realization of the asymmetry requirement, "asymmetric distribution" means that the anchors are not symmetrical to each other with respect to at least one plane of symmetry which could be a plane of symmetry of the vehicle.

More specifically, considering the vehicle equipped with front, rear and two sides, and identifying a first plane of symmetry, in use, vertical of the vehicle and in which lies the front-rear direction of the vehicle 1 and a second plane of symmetry, in use, vertical and orthogonal to the front-rear direction, the anchors are not symmetrically distributed with respect to the first and / or second plane.

This asymmetry could also or only be assessed with reference to a plane of symmetry of the vehicle in use, vertical and substantially oblique or inclined with respect to the front-rear direction and from one side to the other and / or with reference to a horizontal plane, in particular a horizontal plane of symmetry of the vehicle.

In this regard, assuming the vehicle 1 is equipped with twelve anchors 2, the vehicle can be equipped (see figure 1) with the following anchors: one at an upper right front corner, one at an upper left front corner, one at a lower right front comer, one at a lower left front comer, one at a upper right rear corner, one at an upper left rear corner, one at a lower right rear corner, one at a lower left rear corner, one at a lower central rear position, one at a central upper rear position, one at an intermediate left rear position and one at an intermediate right rear position. If desired, to maintain the above mentioned asymmetry requirements, each anchor can be translated along the corresponding corner.

In this case, sub-units of usable anchors may include the anchors as illustrated in figures from 2 to 6.

The evaluation of the aforementioned sub-units can be carried out by means of a simulation method, an experimental estimate or an analytical method, on the basis of the accuracy of the localization of the mobile target obtainable by adopting the anchors belonging to each sub-unit.

With reference to the above, the inventors of the present patent application have been able to experimentally and simulatively verify that the position estimation obtained by using sub-units of anchors, in particular sub-units of asymmetrical anchors, is more accurate and reliable of the estimation obtainable using all the anchors. See in this regard the test results shown in figure 8.

These sub-units of anchors are defined by considering the list of anchors 2 assessed or established during the step aimed at establishing or selecting a specific visibility list of anchors 2 best positioned to receive a signal emitted by a mobile target in each zone. If desired, an accurate estimate can be carried out by realizing a weighted average of the values obtained by means of several sub-units of anchors. In this regard, considering N _s sub-units S1, S2, ... , SN _s of anchors that provide estimates of the positions the final estimate of the position can be

obtained as the center of gravity (see figure 7) of these positions

Moreover, in accordance with a method according to the present invention, the signal or signals emitted by the emitter of the mobile target 4 contains / contain a time marking, which allows to evaluate, during the receiving step and assuming that the receiver is perfectly synchronized with the emitter, how long the signal(s) has / have been emitted. In this case, an anchor or first node that receives the signal(s) from this emitter is able to calculate the corresponding time of flight, after an error due to the lack of synchronization between the anchor and the emitter, by the time marking in the emitted signal or in the emitted signals, which time of flight (or its modified version of a quantity proportional to the synchronization error between the anchor and the emitter) is sent to the centralised processing unit on the automatic guided vehicle 1.

If desired, the centralised processing unit uses multilateration units and carries out the following calculation

Dt _i = t _i - t'

in which t' is the time of arrival at a reference anchor, such as the first one receiving the signal, and the time of arrival relative to i-but still different from the reference anchor. On a practical level, the quantity Dt _i can be calculated, after perfect synchronization between the anchors, as the difference between the instants of reception of the emitter signal by the anchors themselves. In this case, it is no longer necessary for a time marking to be introduced in the emitted signal as described in the previous paragraph.

As an alternative to multilateration units, using trilateration units, the signal emitted by the at least one emitter contains a time marking that allows to evaluate how long the signal has been emitted. In this case, the anchor receives the signal from the emitter and calculates the corresponding time of flight from the time marking in the emitted signal, which time of flight is sent to a processing unit on the automatic guided vehicle.

Moreover, in a method according to the present invention, the position of the mobile target is estimated, during the first rough estimation and / or during the second accurate estimation by means of the solution of the following system of equations

Es = b wherein the matrix E and the vector b contain the coordinates of the anchors 2 and the estimates of the differences of the time of arrivals of the signal emitted by the mobile target received by the various anchors taken into account.

In this regard, the solution of the above system of equations can be written as

ŝ = E ⁺ b

wherein E ⁺ represents the pseudoinverse matrix obtained by means of the Moore- Penrose pseudoinverse, and wherein ŝ represents a solution to the least squares of the system of equations taken into account.

In this case, E it cannot be a square matrix, as better detailed by the formalization in the following paragraph.

The system of equations Es = b it can be solved, for example, by the following methods: Linear Hyperbolic Positioning System (LinHPS), Two-Stage Maximum- Likelihood (TSML) or Plane Intersection (PI).

Also, assuming N the available number of anchors 2 on board the vehicle 1 and assuming, purely by way of example, to use the method called LinHPS, E can be a matrix with size and b a vector with size respectively

defined as:

wherein T it is a transposition

operator;

with the general terms given by

wherein a _i represents the vector of the coordinates of the i-th still receiving, assuming a ₁ the anchor that is the first to receive the signal transmitted by the mobile target 4.

Possible developments or examples of realization of the steps of a method according to the present invention based on UWB technology will now be described in detail.

In this regard, relating to data collection or reception of the signal issued by the mobile target 4, the same are obtained from a number of anchors N' £ N that receive the signal sent by the target.

The unit of receiving anchors is referred to as A _rx. For the k- th still receiving a _k Î A _rx with k = 1, 2, the time marking information received t _k (with appropriate correction determined by the synchronization algorithm) is stored, as well as information relating to the received power.

From a UWB transmitter it is possible to derive the following information, as done for example through the UWB DecaWave chip technology:

- an estimate of the power in the first path signal (in dBm), referred to as

- an estimate of the received power level (in dBm), indicated as

If an anchor has direct visibility to the target, the communication link or connection is referred to as Line-of-Sight (LOS), otherwise as Non-LOS (NLOS).

In addition, the communication connection between the target and the anchor can be assessed as LOS if the difference it is small

enough, i.e. if most of the received energy is concentrated on the first signal repetition received. If instead DP is sufficiently large, the link is referred to as NLOS, since the power of both the first signal and the repetitions is lower. If DP is not small enough, but not too large, the channel quality cannot be assessed with sufficient accuracy: this situation is indicated as almost LOS or Almost LOS (ALOS).

In other words

• LOS connection if DP < b ₁

• ALOS connection if b ₁ < DP < b ₂

• NLOS connection if DP > b ₂

wherein the following values were identified in the experiments conducted: b ₁ = 5.5 dB and b ₂ = 8.5 dB. After this procedure, the set of anchors with LOS, ALOS, and NLOS links to the target are obtained and referred to as

For simplification purposes, anchors A _rx will be assumed as classified and sorted according to the growing parameter DP, i.e.

wherein

With particular reference to an example of a first rough estimation, the system can carry out a preliminary rough localization using the LinHPS algorithm to determine the angular zone or sector wherein the target is likely to be. In fact, it has been found that although the distance from the target can be inaccurate, the angular error with respect to the real position is always sufficiently accurate. To this end, localization is conducted using information deriving from a subset of cardinality anchors 4 £ C _cl £ N', indicated as A _cl established as follows, by way of example:

Therefore, the number of anchors used for rough localization is:

The position estimate obtained with this rough localization is referred as ŝ _cl .

The estimated sector Ŝ _cl it is such that ŝ _cl belongs to that angular sector. The corresponding predetermined list of visible anchors discussed above is referred to

A _vis .

With regard to the estimate of the accurate position, it can for example be checked whether one or more anchors belonging to A _los are not present in A _vis , since this would mean that an anchor is declared as LOS according to the above formula, but from geometric considerations it should be NLOS for that specific sector estimated by the rough localization. If this happens, that anchor is removed from the anchors available for estimating the position, since the corresponding measurement is assumed to be too "noisy".

Removed anchors can be collected in the following sub-unit:

Therefore, The unit of

anchors that have received the beacon and are useful for localization becomes:

Hence, N _s (e.g. 1, 2, 3 or more) sub-units or subsets of are defined according to a heuristic rule, where with C _s is referred the cardinality of the sub- units, with 4 £ C _s £ N" . In particular, by way of example, in the examples N _S = 3 have been considered cardinality sub-units C _s = 7 o 8. At this point, considering the unit of anchors ordered assuming C _s < N", the 3 sub-units are formed according to the following logic:

Finally, with regard to accurate localization, the LinHPS algorithm can be applied to each subset, thus obtaining the estimates ŝ _i i = 1,2, ... , N _s .

At this point, the anomalies are removed and the estimates obtained with the remaining subsets M £ N _s are averaged, thereby obtaining the final estimate

The abnormal values are identified in several ways. First, the sectors to which the estimates belong are calculated and will be referred as The following heuristic strategies are proposed to validate the estimates obtained with these subsets and eliminate those that are not consistent with the others.

1. Assuming the preliminary localization produced by the coarse step is valid, the estimate of a subset is considered for the calculation of the position of the mobile target 4 if it falls in the sector Ŝ _cl or in those adjacent to it. For example, if Ŝ _cl = 53, the estimate obtained with the i-th subset is valid if is such that s varies from 2 to 4.

2. The validity of the preliminary localization by the rough step is judged by verifying its location outside the polytope defined by the anchors.

In fact, in reality the mobile device 4 is always outside this polytope.

To eliminate the anomalies for the calculation of the accurate estimate, the process follows these 3 sub-cases:

- if the preliminary estimate is valid, the same rule of case 1 is

applied; - if the preliminary estimate is not valid, the estimates of the subsets are considered for the calculation of the position of the mobile target 4 if they all fall into a single sector, regardless of whether or not this sector is Ŝ _cl ;

- if the preliminary estimate is not valid, the estimate of a subset is considered for the calculation of the position of the mobile target 4 if it falls within the sector Ŝ _cl or in those with a maximum distance of 2 sectors (from left or right). For example, if Ŝ _cl = S3, the estimate obtained with the i-th subset is valid if it is such that s varies from 1 to 5. This condition is more relaxed than that of case

1 to deal with the greater noise of this situation.

3. All estimates are considered valid.

In the first two strategies it may happen that none of the subunits provide an estimate consistent with the angular sector obtained from the rough localization, thus leading to a lack of localization. However, discarding subsets with poor performance ensures greater accuracy of the final estimate. On the other hand, the third strategy always localizes as soon as N _s subsets are available. In this sense, the performance with the third strategy can be considered as a reference point, since no missing localization occurs at the price of (possibly) reduced positioning accuracy.

The obj ect of the present invention is also an automatic guided vehicle 1 for estimating the position of a mobile target 4 in a warehouse, the vehicle 1 comprising a centralised processing unit, as well as at least 5, 6, 7, 10, 12 or more anchors managed by such centralised processing unit, which anchors 2 being equipped with respective antennas designed to detect a signal emitted by a signal emitter of a mobile target.

In this case, the centralised processing unit is designated for carrying out the above indicated steps.

As it will be confirmed, thanks to a method according to the present invention, it is possible to locate the position of a mobile target more accurately and by reducing the estimation error, such as a person or a manual guided vehicle, avoiding among other things collisions between an AGV and those targets.

This in particular can be achieved thanks to a "two-steps estimation" procedure, according to which after a "rough" estimate between the anchors system and the target, which is used to decide the quadrant or area around the AGV or LGV wherein are found the target and the corresponding list of visible anchors, a choice of the sub-unit or sub-units which allows / allow to make a "fine" estimate of the position is carried out.

Modifications and variants of the invention are possible within the scope of protection defined by the claims.