Position estimation services

[0002] This application claims the benefit of international application number PCT/NZ00/00076 filed May 15, 2000. The international application was published under PCT Article 21(2) in the English language.

[0003] This invention relates to a method and apparatus for a position estimation system and in particular, but not exclusively to a method and apparatus for an indoor position estimation system utilising the multipath-free component of signals received from an object.

[0004] There are a number of systems available which are used to identify the position of an object or track the movements of an object. These systems may be divided into indoor and outdoor systems.

[0005] In outdoor position estimation systems, probably the most widespread is the NAVSTAR Global Positioning System (GPS). This system operates by providing a plurality of satellites transmitting reference signals from which the GPS receiver must calculate its position. This requires the device to include relatively expensive timing and calculating devices which add to the size and expense of the device. Furthermore, the magnitude of error permissible in outdoor systems is typically much greater than the requirements for an indoor system. Although the accuracy of outdoor systems may be increased using methods such as relative and differential GPS, this adds additional expense and space requirements to the system. Other outdoor position determination techniques include LORAN and radar systems. However, these also require the use of relatively expensive and bulky equipment.

[0006] In indoor applications, control over the magnitude of errors must typically be much more stringent due in part to the reduced total area in which a product may be located and the high number of objects which may be located in any particular area. Also, the smaller size of the objects result in limitations in the power of signals which may be transmitted from the object, causing systems relying on such transmissions susceptible to errors due to noise.

[0007] One known method for determining the position of a object is to detect the time of arrival of signals transmitted by a transmitter located on the object or estimating the round trip time of a signal from a polling base station to the object and back again, see U.S. Pat. No. 5,526,357. The position of the object is then determined by spatial calculations.

[0008] A problem in wireless systems is the occurrence of interfering signals. These interfering signals typically originate from a number of sources including background noise, separate transmission sources and multipath effects. Background noise and separate transmission sources are often unavoidable, but can be filtered out or accommodated in system design in some circumstances. Interference due to multipath effects can be more problematic, especially where the timing and/or phase information contained in the signal is important.

[0009] It is an object of the present invention to overcome or at least alleviate problems in methods and apparatus for tracking systems at present, or at least to provide the public with a useful choice.

[0010] According to one aspect of the present invention, there is provided position estimation system for locating an object in a given volume, the system including:

[0011] a signal transmitter suitable for use with the object, the signal transmitter adapted to transmit an identifiable signal;

[0012] a plurality of receivers suitable for receiving signals from the signal transmitter, the receivers positioned at predetermined or determinable positions in relation to the given volume;

[0013] signal detector adapted to determine the difference in the time of arrival of the signal between at least two receivers; and

[0014] computation means to compute the position of the object in the given volume from said difference in the time of arrival;

[0015] wherein the difference in the time of arrival of the signal is determined by comparing the arrival time of substantially corresponding trigger portions, said trigger portions being at least a portion of the substantially multipath free component of the signal as received at each receiver.

[0016] Preferably, the system includes computation means adapted to determine a best fit model to the trigger portion of each received signal, and compute the time difference of arrival from the time delay between the best fit models.

[0017] Preferably, the tracking system further includes a storage means adapted to store a predetermined model of the object and/or given volume, the computation means adapted to determine a pre-estimate of the onset time of the first multipath component from the predetermined model.

[0018] According to another aspect of the present invention, there is provided a method of tracking an object in a given volume, the method including:

[0019] transmitting an identifiable signal from the object to be tracked;

[0020] receiving the transmitted signal at a plurality of receivers positioned at predetermined or determinable positions;

[0021] computing the difference in the time of arrival of the signal between at least one pair of receivers based on the arrival time of at least a portion of the substantially multipath free component of the signal as received at each receiver; and

[0022] computing the position of the object in the given volume from said difference in the time of arrival.

[0023] Preferably, the method further includes computing a best fit model to the substantially multipath free component of the signal, wherein the time difference of arrival of the received signals is determined by the time delay between the best fit models.

[0024] Preferably, the method further includes the step of determining a pre-estimate of the onset time of the first multipath signal from a predetermined model of the object and/or the given volume.

[0025] Further aspects of the present invention may become apparent from the following description, which is given by way of example and in which reference is made to the accompanying drawings.

[0026] !

[0027] The present invention provides a method and apparatus for position determination and/or tracking of an object in a given volume. The method and apparatus are particularly suited to indoor applications, for example in a factory in which objects need to be located. Although the following description is given specifically in relation to the use of the method and apparatus in a factory environment, it will be appreciated by those skilled in the art that the present invention may find application in any indoor environment and may be extended to outdoor environments if required.

[0028] A common method of position determination involves transmitting a signal from an object to be tracked and detecting that signal at two or more receivers. The time difference of arrival of the signal at each receiver can then be used to determine the position of the object in relation to the receivers. If the position of the receivers are known, or at least are determinable, then subsequently the location of the object is known or more specifically, the location of the transmitter on the object is known. The present invention uses the time difference of arrival of substantially corresponding portions of the received signal at pairs of receivers. However, only the substantially multipath free component of the signal is used, thereby avoiding the interfering and often error creating multipath signals from the determination of position. This multipath free component is the initial portion of the received signal.

[0029] In order to allow multiple measurements of position of one or more objects, it is thus necessary to measure multiple initial portions of the signal, implying pulsed signals. Therefore, the technique of the present invention may be referred to as partial pulse positioning, as it uses a portion of a pulse to determine the position of an object.

[0030] Partial pulse positioning preferably employs band-passed RF pulses transmitted or relayed by a transmitter located on or within an object. Referring to FIG. 1, an object which is to have its position determined and/or tracked is referenced 1. The object 1 has a transmitter tag (not shown) mounted on it, which emits a band-passed RF pulse at a predetermined frequency. The RF pulse is observed, pre-conditioned and recorded at spatially separated receivers 2 located around the search volume. For any given receiver 2 pair, the difference between the time of arrival of the pulse at each receiver 2 is proportional to the difference in the range from the tag to the receivers 2 and constrains the tag to lie on a hyperbolic surface of position (SOP). By combining the SOP from three or more independent receiver 2 pairs it is possible to determine the tag position in three dimensions. If prior knowledge such as the tag height is available, only two independent receiver 2 pairs are necessary and in some cases, the combination of a prior model and one SOP may still provide useful estimates. These concepts are common to all time delay based position estimation methods and thus will not be detailed herein. Also, subsequent position estimation from time difference of arrival information is well documented in the literature and well known to those skilled in the art.

[0031] FIG. 2 illustrates one example of a preferred form of a transmitter tag for use in the present invention. The tag includes a transmit antenna 4 suitable for transmitting RF pulses and a mixer 5 to form the RF signal from a carrier generated by a carrier signal generator 6 and a pulse signal generated by a pulse generator 7. A pulse trigger 8 controls the timing and duration of the pulsed signals. The transmitted signal may include an information stream, for example, to aid in the identification of the tag or the object to which it is attached or to indicate the status of the tag, the object to which it is attached, or the environment in which it is located. It will be appreciated by those skilled in the art that any measurable pulsed signal may be transmitted by the tag, the transmission of an electromagnetic signal, in particular a RF pulse being preferred.

[0032] There are many forms in which the tag could be implemented depending on the requirements of the system and/or of the object to be tracked. A low cost, small tag that can be mounted on work in progress during production in a factory is one example. This tag could be removed prior to shipping for re-use or permanently built into the product and thereby essentially ‘discarded’ once production is complete. The second form is a larger (and possibly higher unit cost) unit that could be mounted on Automated Guided Vehicles (AGV) or other items of greater value.

[0033] A power source (not shown) may be co-located with the transmitter or external to the tag to supply power to the active components of the tag. Increased power improves position estimate accuracy by increasing the observed Signal to Noise Ratio (SNR), thus reducing the occurrence and magnitude of position estimation errors due to non-multipath interfering signals. The characteristics that dictate ‘onboard’ power sources are the expected life of the tag, the required cost as well as the physical application.

[0034] The requirements for a coin size tag will typically be more exacting that those of an AGV, as the power supply is constrained due to the size of the tag or object 1 ,limiting the energy of transmitted signals. Furthermore, a tag may be attached to only one of many small objects located in a single area. It is possible to power the tag externally using emerging Inductive Power Transfer (IPT) technologies or by connecting it to the onboard power supply of the ‘host’.

[0035] The transmit antenna 4 preferably has a radiation pattern that maximises pulse energy in the direction of the receiver 2. For example, for ceiling mounted receive antennas 2, the transmit antenna 4 preferably, for obvious reasons, directs the transmitted energy generally upwards and minimises energy transmitted towards the floor. Techniques for achieving this are well known to those skilled in the art.

[0036] The receive antennas of receivers 2 may be omni-directional or alternatively receive preferentially in one or more directions. Receivers 2 having directional gain offer many benefits. At one extreme, directional antennas can provide angle-of-arrival information on the transmitter by employing pencil beam antennas as used by radar systems, therefore providing further information for the purposes of establishing or verifying the position of the object 1. One method of providing such direction gain involves physically guiding an antenna having a fixed radiation pattern. An intuitively attractive example of this is the constantly rotating radar antennas seen at most airports. A second method involves electronically steering the beam in the desired direction. Electronic beam steering employs adaptive phased array antennas that are commonly referred to as Smart Antennas.

[0037] The ability of an antenna to receive energy preferentially from a certain direction has, besides any available angle-of-arrival information, three further primary benefits for partial pulse positioning. The first is the increased number of transmitters that can use any given time slot. The mechanism for providing this benefit is referred to as Space Division Multiple Access (SDMA) and is one of the key tools in efficient resource use in cellular communications. SDMA permits multiple users to co-exist in the same frequency band or time-slot. The antennas are located to minimise the geometric dilution of precision.

[0038] The second concerns the received line-of-sight energy. Receivers 2 with higher gain receive antennas will increase the energy of the line-of-sight pulse, directly impacting upon the SNR and accordingly the accuracy and reliability of the partial pulse positioning system.

[0039] The third benefit is that the antenna gain pattern can increase the line-of-sight to multipath energy ratio. This is done by ensuring that multipath components fall upon nulls in the radiation pattern. This will have the benefit of increasing the length of the partial pulse and accordingly the integrated SNR of the partial pulse.

[0040] FIG. 3 shows a typical receiver 2 antenna radiation pattern. The line of sight path between the transmit antenna 4 and the receive antenna of the receiver 2 is indicated by arrow A. Three interfering signals in the form of multipath components are indicated by arrows B. In order to maximise the benefit of directional gain, it is preferable that the highest gain direction corresponds to the angle of the line of sight signal. In this case, prior knowledge of the factory may be used to dictate the direction of the receive antenna of each receiver 2. For example, if a component is known to travel along a conveyor belt, this immediately constrains the areas where it is likely to be located and the antenna can be directed towards that area. Furthermore, if the factory geometry is known as well as probable locations of the object 1, then the largest and most likely multipath components may be known. Therefore, each receiver 2 may have a receive antenna which has a null at one or more of these predetermined multipath component angles.

[0041] In the preferred embodiment, to allow tracking of multiple tags, time slots are used to differentiate the tags through the use of Time Division Multiple Access (TDMA). Synchronisation of the time slots between tags can be achieved by either ensuring that all tags have accurate clocks on-board or alternatively by providing an externally generated synchronisation or polling message. Such a message can be transmitted using a variety of possible mediums including but not limited to RF, optical and acoustic. Synchronisation approaches are well known and the specific synchronisation approach taken will depend on the application as well as existing and emerging technology.

[0042] Alternatively, the tag may simply relay a pulse originating from another source, which may be the same as one or more receivers 2. In this case, the receiver 2 would measure the round trip time of the signal. However, it is preferred that each object generates and transmits its own signal to allow easier identification of individual objects using TDMA.

[0043] One method of establishing the difference in the time of arrival of a portion of a signal which does not include multipath components is to use an initial portion of the signal. By using the initial portion of the signal, none or very few interfering multipath components have been received by the antenna. By using the first peak, first zero crossing or any other identifiable feature in the initial portion of the signal as a trigger for each receiver 2, then the time difference of arrival may be computed by calculating the delay between receipt of corresponding triggers at each receiver. This method allows a system which has minimal processing requirements but may be subject to errors due to interfering signals creating false trigger points, particularly background noise signals and signals from sources other than the transmitter on the object 1. These interfering signals are typically present in all portions of the received signal and thus cannot be alleviated by using the initial portion of the received signal.

[0044] In order to achieve a more reliable and accurate system, a larger proportion of the received signal may be used as the trigger for each receiver 2. By comparing a larger portion of the signal with an expected received signal more certainty can be achieved that the reference signal is genuine and not due to background noise or other signal transmission sources. However, as portions of the signal further from the initial portion are used, there is an increased probability that there are multipath components in the signal, which can create errors in the determination of the position of an object 1, especially when the signal to noise ratio is low.

[0045] Therefore, the method and apparatus of the present invention pre-estimates both the onset time of the received pulse and the time of arrival of the first multipath component. The pre-estimation process uses information from a model of the factory and/or objects 1 within the factory and/or signal information to determine these pre-estimates. FIG. 4 shows a flow chart of the overall process for computing the position of an object based on a received pulse signal transmitted from the object 1.

[0046] The tag placed on the object 1 transmits the pulsed signal which is received at at least two receivers 2. Partial pulse pre-estimation is then performed to pre-estimate the onset time of the signal received by each receiver 2 and the onset time of the first multipath component, thereby identifying the substantially multipath free component of the received pulse. The pre-estimations are then used to find a best estimate for onset time of the signal at each receiver 2 and the difference between these onset times is the estimated delay between the time of arrival of the two signals. This estimation of the time delay is then used to estimate the position of the tag and thus the position of the object 1.

[0047] Each step of the system process will now be described in more detail. The tag first transmits an RF pulse to be received by at least two receivers 2. The pulse may be of any shape, with FIG. 8 showing a preferred pulse in the form of a raised cosine RF pulse. Referring now to FIG. 5, the pulse is observed at at least two receivers 2. The following description is given in reference to calculating the position of an object 1 based on a signal received at two receivers 2. It will be appreciated by those skilled in the art that the process can be repeated for three or more spatially independent, non-colinear receiver pairs to determine the position of an object 1 in three-dimensional space.

[0048] To enable a digital processor to analyse the signals, the received signal is converted into digital form. An analogue-to-digital receiver may be used to carry out this task. However, the inclusion of analogue-to-digital receivers in each unit comes at a high cost due to duplication of equipment. To overcome this, the partial pulse positioning system examines antenna pairs sequentially, effectively employing a time division multiple access strategy and therefore requiring only two analogue-to-digital receivers for each antenna “cluster”. A multiplexer is used to cycle through the receivers 2 in a predetermined cycle or in a manner as defined by a prior model of the required multiplexing operation. A suitable time synchronisation between the two analogue-to-digital receivers is provided. Of course, the accuracy of the synchronisation will be dependent on the accuracy requirements of the partial pulse positioning system.

[0049] Antennas are co-located with signal conditioning equipment, for example a low pass filter and amplifier. The resulting amplified and filtered pulse is communicated to the analogue-to-digital receiver through the multiplexer and a suitable transmission medium, for example a co-axial cable. The selection of the pairs of receivers 2 over time is influenced by a dynamic prior probability model. For example, specific areas of the factory may have more stringent tracking requirements than others, requiring that antennas directed towards that location are sampled more often.

[0050] To increase the sampling rate, each antenna of each receiver may be switched between multiple analogue to digital converters. A prior model, as part of the dynamic prior probability model of the sampling requirements of each object, or area(s) within the volume may be used to dictate which antennas are sampled at which rate.

[0051] The dynamic prior probability model dictates receiver selection according to the requirements of the system and the available system resources. In a preferred embodiment, the model may define a tuning process, whereby the system resources are varied depending on the characteristics of the factory, object 1, and any restrictions in place. Suitable system resources may include the sampling rate and frequency, bandwidth of the transmitted signal, the radiation pattern and orientation of receiving antennas, the transmission power and the sampling frequency.

[0052] The result of the multiplexing operation is that for any given pulse transmission, only two times series need to be recorded for position estimation. The remaining estimation on the tag position must come from another source, for example other antenna clusters, previous delay estimates from spatially independent antennas or any other prior knowledge. Should higher accuracy be required, additional analogue-to-digital receivers can be connected to a cluster.

[0053] Referring now to FIG. 6, a flow chart of the steps involved in pre-estimation and delay estimation are shown. The pre-estimation process uses a signal detection means and information contained in the dynamic prior probability model to estimate the onset time of the received pulse and the onset time of the first multipath component for each received signal. The onset time of the pulse is pre-estimated by detecting a singular characteristic of the received signal. Detecting the characteristic may involve one or more amplitude threshold tests, peak or zero crossing detection, or any other technique from the field of statistical hypothesis testing suitable for detecting a trigger portion of the substantially multipath free component of the received signal.

[0054] An initial estimation of the onset time of the signal can be computed from the time of detection of the trigger portion and the expected time difference between the actual onset time and the measured trigger portion, assuming the absence of interfering signals.

[0055] Determining the onset time of the first multipath component requires information from the dynamic prior probability model, which may include antenna characteristics, the propagation characteristics of the received transmission frequency and factory geometry. Alternatively, signal characteristics may be analysed either in combination with the model or alone to determine the onset time of the first multipath component. For example, the phase of the received signal may be analysed for changes identifying the onset of multipath components. The directional gain of the antenna may block out some multipath components, allowing a longer portion of a pulse to be used. The wavelength of the transmitted frequency may have an effect on the onset time of the first multipath component. Physical characteristics of the factory geometry such as the location of walls and materials within the factory and expected movements of the object 1 and any other objects may also be included. This information and any further appropriate information is used to establish a pre-estimate of the onset time of the first multipath component given the pre-estimate of the onset time of the received signal. The portion of the received signal up until the pre-estimated onset time of the first multipath component is represented by the continuous (non-dashed) section of the signal in FIG. 8.

[0056] Now referring to FIG. 9A, a typical discrete impulse response for the transmission channel between the tag on the object 1 and a receiver 2 is shown. The line of sight component is represented by arrow C and the first multipath component by arrow D. The portion of the pulse used for establishing the time difference of arrival of the signals between receivers is shown by arrow E.

[0057] FIG. 9B shows a representation of the line of sight signal observed at a receiver 2. The effect of multipath components are not shown in FIG. 9B. The time of arrival or onset time of the pulse in the window is defined as t=τ_0i. The arrival time of the first multipath component is defined as t=T_{obs i}. Of interest for further analysis is the section of the time series between the arrival time of the line-of-sight component at time t=τ_0iand the arrival time of the first multipath component at time t=T_{obs i}. By box car windowing the signal in time over the interval (0,T_{obs i}), all multipath energy as well as some line-of-sight energy is eliminated. The box car window data is highlighted in bold in FIG. 9B.

[0058] In reality the impulse response for each antenna will be unknown and therefore the onset time of the pulse and first multipath component have to be pre-estimated using the method described herein above.

[0059] Referring again to FIG. 6, the system after pre-estimation the onset time of the pulse and first multipath component then detects the signal to noise ratio of the received signal is above or below a certain threshold. This threshold is selected according to the signal to noise ratio which gives a certain percentage error rate. If the signal to noise ratio is above the threshold, the received signal at each antenna is fitted to a signal model. This signal model is the expected received signal without interference from noise, multipath signals, or other sources of interference. The signal model may be a parametric model. A best fit model is computed for the received signal, for example by performing a least squares error computation. It will be appreciated by those skilled in the art that any error minimisation technique (or equivalently probability maximisation technique) may be used for this purpose. Once the best fit model is found, the onset time of the pulse according to that model is also known for each receives.

[0060] For signals received having a signal to noise ratio below the threshold, the resulting computations become dominated by cycle errors. The cycle errors can however be eliminated if there is sufficient a priori knowledge of the true delay. The system selects a signal, signal i, which is preferably the signal with the highest signal to noise ratio and determines the onset time for that signal using the process for signals with a signal to noise ratio above the threshold. Information from the prior probability model is used to formulate an a priori probability density function of the onset time of the remaining signal j.

[0061] This information may be used in combination with the estimated onset time computed for signal i to determine the onset time of signal j. As the signal is periodic, the error function or probability function for the onset time given the received signal is also cyclic. This probability function, which is the probability of the onset time conditional on the received data is defined as the conditional density function. This is represented in FIG. 10. By multiplying the conditional probability density function with the a priori probability density function a posterior density function results. The correct maximum of the posterior density function gives the onset time of the received signal. Thus, the onset time of signal j is then determined and the difference between the estimated arrival times can be computed. To avoid unneccessary biasing due to the a priori density function, the conditional probability density is discretised before multiplying. It will be appreciated to those skilled in the art that substantially equivalent computations may be performed using the techniques of regression analysis rather than probability analysis.

[0062] In addition, the system may become susceptible to errors due to fitting the best fit model to the incorrect integer cycle of the signal. This problem is overcome through the use of the prior probability model, which selects the correct integer cycle according the probability of its occurrence. The probability model may be given more weight in the case of low signal to noise ratio than if the signal has a high signal to noise ratio.

[0063] The delay estimate is computed as the time difference of arrival of the estimated onset times of the best fit models and is sent to a central computer for position estimation processing. It will be appreciated by those skilled in the art, that the central computer may be replaced with any suitable computing means located anywhere.

[0064] Information from the model of the factory or object 1 is used to verify the position calculation and/or to correct minor errors in the position estimation. For example, it is known that objects travel along a conveyor belt, and the position estimation system computes the position of the object to be just off the conveyor, prior knowledge may correct the position to place it on the conveyor. Of course, further information in the model may provide that if an object remains stationary, then it may in fact not be on the conveyor. There are many possibilities of circumstances in which the prior model could be used to determine the actual position of the object from the position estimation. The position estimate is then sent to a central database where it may be retrieved when required. The previous position estimates computed for an object may be included in the dynamic prior probability model for future calculations.

[0065] FIG. 8 shows a block diagram representation of the architecture of the system of the present invention according to one embodiment. In the system shown in FIG. 8, the use of pre-estimation of the onset time of the pulse and first multipath component is used. Where the system uses only a singular trigger point, or a number or trigger points, which may for example be averaged, the pre-estimation of the onset time of the pulse would be the actual estimation of the onset time and would be used for the delay calculation.

[0066] A cluster of receivers 2 are multiplexed through a multiplexer 9 to two analogue-to-digital converters 10. The signals are conditioned by an amplifier 11 prior to receipt by the analogue-to-digital receiver if required. This creates two data streams {tilde over (y)}_iand {tilde over (Y)}_jwhich are used for pre-estimation, using the dynamic prior probability model (DPPM) and available signal information. The pre-estimation process identifies the relevant portion of the signals {tilde over (y)}_iand {tilde over (y)}_jto compute {tilde over (y)}_iand {tilde over (y)}_j. These are fitted to parametric models to obtain the estimate of the onset time of the pulses. While the pre-estimation and model fitting steps are represented separately in the block diagram of FIG. 8, they may be performed by a single computation means. The difference between the estimated onset times is then computed and a position estimate is calculated from the delay times and any relevant information from the dynamic prior probability model.

[0067] In an ideal environment, for highest accuracy, the receivers 2 should be positioned so that there is always a direct line of sight from the object 1 to the receivers 2. In reality, this may not be possible, especially where a number of large objects are moving around the factory. If a direct line of sight does not exist, then the signal analysed by the receiver will be the first signal to arrive at the receiver.

[0068] Where in the foregoing description, reference has been made to specific components or integers of the invention having known equivalents then such equivalents are herein incorporated as if individually set forth.

[0069] Although this invention has been described by way of example and with reference to possible embodiments thereof, it is to be understood that modifications or improvements may be made thereto without departing from the scope of the appended claims.