Methods for optimization in geolocation using electronic distance measurement equipment

Abstract

A method of determining a new position for a node. The node having a distance measuring radio. A list of positions of a plurality of neighboring nodes is obtained. The geometric relationship of the positions in the list and the predicted position of node is analyzed. A subset of the nodes is selected from the list that is less than the total number of modes in the list. Electronic distance measurements from the node to each of the subset of nodes are performed. A new position of the node is determined utilizing the measured distances.

Claims

1. A method of determining a new position for a node, the node having a distance measuring radio, the method comprising: a) obtaining a list of positions of a plurality of neighboring nodes; b) analyzing a geometric relationship of the positions in the list and a predicted position of node; c) selecting a subset of nodes from the list that is less than a total number of nodes in the list; d) performing electronic distance measurements from the node to each of the subset of nodes; and e) determining a new position of the node utilizing the electronic distance measurements obtained in step d).

2. The method of claim 1, wherein the selection of the subset is based on a most favorable geometric relationship of nodes in the list to the predicted position of node.

3. The method of claim 1, further comprising obtaining corresponding confidence metrics for each position in the list; and wherein the selection of the subset is based at least in part on the confidence metrics.

4. The method of claim 1, wherein a maximum number of nodes in the subset is 3.

5. The method of claim 1, further comprising transmitting the electronic distance measurements to the subset of nodes.

6. The method of claim 1, further comprising receiving a previously measured distance from at least one among the plurality of neighboring nodes; wherein the electronic distance measurements are performed from the node to each of the subset of nodes for which the previously measured distance was not received therefrom.

7. The method of claim 1, wherein if the node is moving, performing the steps a) to e), otherwise if the node is not moving, taking no measurements and using the predicted position of node as the new position of node.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) The present invention is described herein with reference to the following drawings:

(2) FIG. 1 shows the major functional blocks of an illustrative embodiment, and the data flow between them;

(3) FIG. 2 is a diagrammatic illustration of an embodiment of the methods of the present invention;

(4) FIG. 3 illustrates the ambiguity of distance measurement with only one available reference node resulting in infinite number of candidate positions along the circumference of the circle;

(5) FIG. 4 shows reduction in ambiguity with two available reference nodes with favorable geometry, resulting in two candidate positions at Circle-Circle intersections; and

(6) FIG. 5 shows further reduction in ambiguity to a single candidate position when three reference nodes with favorable geometry are available.

DETAILED DESCRIPTION OF AN EMBODIMENT OF THE INVENTION

(7) The illustrative embodiment presented herein utilizes in part the methods disclosed in the above referenced co-pending application, in particular the methods for selecting a subset of Nodes based on geometry and Confidence, and the methods for determining the Position of Node n having two or three distance measurements to other Nodes. These methods are included in the following description for reference, however they are outside the scope of the present invention.

(8) The scope of the present invention pertains specifically to the sequence of first selecting a subset of Nodes from a plurality of available Nodes, by any known or future method, subsequently performing distance measurements only to the selected nodes, and then determining a Node's Position based on said measurements, by any known or future method.

(9) FIG. 1 is a diagram of the overall data flow for an illustrative embodiment of the present invention.

(10) In order to determine a node's Position, information is gathered from a variety of sensors. In the context of the illustrated embodiment, the position data of neighboring nodes and the measured distances to such nodes are considered sensor inputs. Other typical sensors include inertial measurement unit (IMU), magnetometer, altimeter and the like.

(11) In the illustrated embodiment, the IMU and altimeter are contained within the hardware portion of a node.

(12) Information about the locations of neighboring nodes is transmitted to the node via a data radio. In some embodiments, a single node will be designated as the Neighborhood Manager responsible for periodically collecting and disseminating this information among the nodes. In other embodiments, this information may be transferred collaboratively peer-to-peer. Many methods for transferring information among a plurality of nodes are known. The details of such methods are outside the scope of the present invention.

(13) Distance measurements between nodes are performed by means of a distance measuring radio. A number of such methods are known. The illustrated embodiment utilizes Decawave DW1000 distance measuring radios, but a number of others are readily available.

(14) Sensors:

(15) Altimeter provides relative altitude.

(16) IMU: The Inertial Measurement Unit such as the BNO080 consists of 3 axis accelerometer, gyroscope and magnetometer. These are typically fused (internally in most modern IMUs) to provide virtual sensors such as linear acceleration and step counter along with a rotation vector to transform the linear acceleration with magnetic North.

(17) Distance measurement: The Distance measurement module (such as an UWB radio) provides the distances from the current Node to nearby Nodes.

(18) Neighborhood: In the context of the illustrated embodiment, Neighborhood is a set of Nodes managed by a Node functioning as the Neighborhood Manager (NHM). Each Node broadcasts its position information via XNet. The NHM maintains a Neighborhood Database (NHDB) of the Nodes in its neighborhood. Each Node in the neighborhood receives the position information for each of its neighbors. This information includes:

(19) X, Y, Z coordinates where: X is the West (negative) and East (positive) axis, Y is the North (positive) and South (negative) axis, Z is elevation.

(20) Role: Anchor: stationary Node with accurately measured position. Tag: moving or stationary Node whose position is calculated via Positioning. A stationary Tag is referred to as a Breadcrumb.

(21) State: Moving or Stationary,

(22) Confidence.

(23) Confidence: Key positioning values such as the coordinates and distances have an associated confidence value with a range of 0.0 to 1.0 where 0.0 indicates no confidence and 1.0 indicates absolute confidence. Other numeric scales can be used in different embodiments. Whenever positioning chooses among Node data for calculating a position estimate, it uses the confidence of the data to choose the best (most confident) data.

(24) Only anchors have a pre-assigned and constant confidence, set to 1.0. A tag's confidence is calculated based on the confidence of the data is receives from sensors, distance measurement and neighbor Nodes used to calculate a tag's position.

(25) A tag's Position confidence can decrease over time due to data errors, lack of Precision, and time lag between data updates; confidence decreases with data age. As mentioned above, the confidence never increases on its own, it can only increase if the confidence of incoming new data is higher than currently available data.

(26) Modules:

(27) Positioning consists of the following modules:

(28) Inertial Navigation System (INS): Given a starting position, the INS module takes inertial inputs from the IMU and converts them X and Y offsets to compute a predicted Position.

(29) Geometry: Given neighbor Node's positions and distances, the Geometry module computes one or more candidate Positions of the local Node.

(30) Motion: Given inertial inputs, the Motion module computes whether the local Node is in motion and it computes the direction of travel.

(31) Geometry Module (GEO): GEO uses neighbor Node positions and distances to compute one or more candidate Positions for the local Node. Neighbor positions are provided by the NHM and distances to nearby Nodes are provided by Distance measurement; both are delivered as sensor readings. These are combined into a list of Neighbor Descriptors (ND).

(32) GEO recalculates the estimated position at the same rate as Distance measurement is able to provide distances updates. Each Node implementation may have different Distance measurement technology and thus the update rates vary by Node.

(33) GEO's position calculation is shown in the flow chart shown in FIG. 2 and summarized below:

(34) 1. Remove unsuitable neighbors from the ND List. Desirable neighbors are those with high confidence, recent position and distance data, and are positioned favorably.

(35) 2. Calculate interpolated position of Tag neighbors.

(36) 3. Sort ND List by confidence.

(37) 4. Select up to three best neighbors based on role (preferring Anchors over non-moving Tags over moving Tags) and Confidence.

(38) 5. Perform distance measurements only to the selected Nodes.

(39) 6. If there are only two neighbors, attempt to use Bilateration to calculate two candidate Positions.

(40) 7. If there are three neighbors, attempt to use Trilateration to calculate a single candidate Position. If Trilateration fails, attempt to use to Bilateration on each neighbor pair combination to calculate several pairs of candidate Positions.

(41) 8. Report the list of candidate Positions to the INS module. Each of the above steps may end the calculation due to an insufficient number of usable neighbors. In such cases GEO will report the previously calculated position with a reduced confidence. Thus, as time passes without enough neighbors, GEO's reported position confidence decreases.

Trilateration/Bilateration

(42) Given one Anchor and a Tag and a distance between them of d1 all that is possible is to say that the Tag lies somewhere on the circle with it center at Anchor 1 with radius d1 (cf. FIG. 3). This information is not sufficient to calculate a finite list of candidate Positions. However, having the predicted Position pP from the INS module, it is possible to adjust the associated Confidence. If pP lies on the circle or near it, its Confidence can be increased. If pP is far from the circle, its confidence can be decreased.

(43) Given two Anchors and a Tag and the distances to the Anchors d1 and d2, we can calculate two possible candidate Positions cP1 and cP2 at the intersections of the two circles around the Anchors as shown in FIG. 4. Having a predicted Position pP from the INS module, the closer candidate Position can be chosen over the other (cP2 in the illustrated case). As in the previous example, the magnitude of the distance between cP2 and pP can be used as the basis for adjusting Confidence.

(44) With three anchors it is possible to calculate a single candidate Position cP of the tag to be at the center of the intersection of all three circles. This scenario is illustrated in FIG. 5. Like in previous examples, the magnitude of the distance between cP and pP, especially as it compares to the inherent Precision of the distance measuring technology being used, can be evaluated to adjust Confidence.

Inertial Navigation Module (INS)

(45) INS takes inertial inputs from the IMU and converts them X and Y offsets and adds them to the previous position to compute a new predicted Position and associated Confidence. A large amount of inertial activity will reduce Confidence, while little or no detected inertial activity will, in some embodiments, increase Confidence.

(46) A second function of the INS is to receive a list of geometric candidate Positions from the GEO module, and select among them based on distance from predicted Position and relative Confidence. In some scenarios, the predicted Position may be selected over all candidate Positions. In other scenarios, a new position may be calculated that is a weighted average of the closest candidate Position and predicted Position, with weights being at least in part proportional to respective Confidence.

Motion Module (MOT)

(47) MOT takes inertial inputs from INS and computes whether the local Node is in motion and it computes the direction of travel (bearing). The result of motion computation may be used to adjust Confidence of the node's Position and also may be used to switch node roles between Anchor, Breadcrumb and Tag. Node roles are used by the GEO module as criteria for selecting most favorable sets of distance measurements, with the highest preference being given to Anchors, then Breadcrumbs, then Tags. A Breadcrumb, within the context of the illustrated embodiment, is a Tag that has been stationary for an extended period of time. The primary difference between an Anchor and a Breadcrumb, in the illustrated embodiment, is that an Anchor's position is explicitly known and assigned when the Anchor is placed. A Breadcrumb's position was calculated when it was moving as a Tag, but has higher Confidence than that of a moving Tag due to having been stationary and having the benefit of a number of repetitive measurements being considered over time to reduce error.

(48) According to a particular embodiment, the method of determining a new Position for a Node n, said Node having a distance measuring radio, said method comprising the steps of:

(49) a) Starting with a previously determined previous Position P, said previous Position having a previously determined Confidence C, calculating a predicted Position pP, and an associated predicted Confidence pC, said calculations utilizing data from at least a 3-axis Inertial sensor,

(50) b) If said data from inertial sensor indicated that Node n has not moved, taking the previous Position as the new Position and skipping all subsequent steps,

(51) c) Obtaining a list of available neighboring Nodes, their associated Positions, and the associated Confidence metrics,

(52) d) For each pair of available neighboring Nodes in the list, evaluating the geometric relationship between Pn1, Pn2, and pP,

(53) e) If the evaluation of step d) shows favorable geometry, adding nodes N1 and N2 to the selected subset of Nodes,

(54) f) From the selected subset of Nodes in step e) choosing three Nodes with the highest Confidence associated with their Position,

(55) g) Electronically measuring at least a first distance Dn1 to at least a first other Node n1, at least a second distance Dn2 to at least a second other Node n2, and at least a third distance Dn3 to at least a second other Node n3,

(56) h) Transmitting the value of Dn1 to node N1, the value of Dn2 to node N2 and the value of Dn3 to node N3,

(57) i) Obtaining the current Position Pn1 of at said first other Node, Position Pn2 of said second other Node, and Position Pn3 of said third other Node, said Position comprising at least X, Y, Z coordinates and a Confidence metric Cn1, Cn2 and Cn3,

(58) j) Using trilateration with positions Pn1, Pn2 and Pn3 and corresponding measured distances Dn1, Dn2 and Dn3 to determine at least a candidate Position cP,

(59) k) Determining a candidate Confidence cC as the lesser of Cn1, Cn2 and Cn3, then adjusting said Confidence cC based on geometric conditions of the calculations in step d),

(60) l) If confidence cC is greater than pC, choosing candidate position cP as new position P and taking cC as the new confidence C, otherwise choosing predicted position pP as new position P and predicted confidence pC as new confidence C.

(61) According to another particular embodiment, the method of determining a new Position for a Node n, said Node having a distance measuring radio, said method comprising the steps of:

(62) a) Starting with a previously determined previous Position P, said previous Position having a previously determined Confidence C, calculating a predicted Position pP, and an associated predicted Confidence pC, said calculations utilizing data from at least a 3-axis Inertial sensor,

(63) b) If said data from inertial sensor indicated that Node n has not moved, taking the previous Position as the new Position and skipping all subsequent steps,

(64) c) Obtaining a list of available neighboring Nodes, their associated Positions, and the associated Confidence metrics,

(65) d) For each pair of available neighboring Nodes in the list, evaluating the geometric relationship between Pn1, Pn2, and pP,

(66) e) If the evaluation of step d) shows favorable geometry, adding nodes N1 and N2 to the selected subset of Nodes,

(67) f) From the selected subset of Nodes in step e) choosing two Nodes with the highest Confidence associated with their Position,

(68) g) Electronically measuring at least a first distance Dn1 to at least a first other Node n1, and at least a second distance Dn2 to at least a second other Node n2,

(69) h) Transmitting the value of Dn1 to node N1 and the value of Dn2 to node N2,

(70) i) Geometrically projecting the distances Dn1 and Dn2 onto a common horizontal plane, to determine projected distances pDn1 and pDn2,

(71) j) Calculating Circle-Circle Intersections of said projected distances to determine two candidate Positions cPa and cPb,

(72) k) Determining a candidate Confidence cC as the lesser of Cn1 and Cn2, then adjusting said Confidence cC based on geometric conditions of the calculations in step e),

(73) l) Determining the error distance eDa between pP and cPa, and error distance eDb between pP and cPb, m) Choosing the candidate Position with the lesser error distance as the candidate Position cP and the corresponding error distance as the error distance eD, n) Calculating new position P as a weighted interpolation between at least the predicted position pP and candidate position cP, and o) Calculating new confidence C as a weighted interpolation of predicted confidence pC and candidate confidence cC.

(74) The embodiments disclosed herein are illustrative and not limiting; other embodiments shall be readily apparent to those skilled in the art based upon the disclosures made herein, without departing from the scope of the present invention.