Planning of unmanned underwater vehicle surfacing events

Abstract

Methods and systems are provided for planning locations to surface an unmanned underwater vehicle (UUV) to reset inertial navigation errors by obtaining a GPS fix. A spatial point process model for historical maritime traffic is used to quantify surfacing risk throughout an operational area. Accumulated navigation uncertainty for each candidate surfacing point of a feasible path is modeled and penalized. This allows autonomy to balance the tradeoff between surfacing risk, navigation performance and pathlength. The planning method results in minimizing the path length the UUV travels and the number of times the UUV surfaces, while satisfying a defined constraint on maximum allowable risk.

Claims

1. A method for navigating an unmanned underwater vehicle according to a mission path with surfacing locations along said mission path from a given ingress point to a given goal point within an operational area, said method comprising: mapping surface vessel traffic intensity onto said operational area; identifying candidate surfacing locations based on said surfacing locations on said mapping where a void probability that there are no surface vessels within a specified radius of said surfacing locations while said unmanned underwater vehicle is surfaced for a specified duration is not less than a specified minimum safety value; forming a directional graph of said candidate surfacing locations; for each leg of each possible path through said candidate surfacing locations, determining a displacement of said traffic intensity based on an uncertainty in a state of an internal navigation system of said unmanned underwater vehicle over a distance traveled in said each leg; for each said leg, determining a diminution in said void probability based on said displacement; for each said possible path, determining a cumulative cost of each said leg in said path based on said distance traveled and said diminution; determining an optimum path of all said possible paths based on said optimum path having a minimum cumulative cost; and navigating said unmanned underwater vehicle along the optimum path.

2. The method of claim 1, further comprising discarding a possible path when said void probability at one of said surfacing locations on said path is less than said minimum safety value.

3. The method of claim 1, wherein said mapping comprises estimating a Poisson intensity function based on a spatial point process of points in said operational area where said surface vessels are located.

4. The method of claim 1, wherein determining said optimum path further comprises discarding a possible path when a cumulative cost of said possible path exceeds a cumulative cost of a previous possible path.

5. The method of claim 1, wherein: said inertial navigation system state is characterized by a symmetric Gaussian; said uncertainty is characterized by a covariance matrix; and determining said displacement comprises using said Gaussian as a probability density to displace said traffic intensity as a function of accumulated uncertainty in said state.

6. The method of claim 5, wherein determining said cost comprises determining an edge weight of said directional graph with said displacement for traversing said each leg as a ratio between said distance traveled and said void probability based on said displaced traffic intensity.

7. The method of claim 6, further comprising discarding a possible path when said void probability at one of said surfacing locations on said path is less than said minimum safety value.

8. The method of claim 7, wherein said mapping comprises estimating a Poisson intensity function based on a spatial point process of points in said operational area where said surface vessels are located.

9. The method of claim 8, wherein determining said optimum path further comprises discarding a possible path when a cumulative cost of said possible path exceeds a cumulative cost of a previous possible path.

10. A method of navigating an unmanned underwater vehicle having an inertial navigation system in an operational area between an ingress point to a goal point, said method comprising: planning a path as a plurality of legs and surfacing locations between the ingress point and the goal point; iteratively accumulating navigation uncertainty in a state of the internal navigation system of said unmanned underwater vehicle over each leg of the path between the surfacing locations, wherein an increase in said navigation uncertainty increases a cost associated with a risk of surfacing at a location with an elevated risk of collision with surface vessels; specifying a safety radius about said unmanned underwater vehicle when surfaced; specifying a duration said unmanned underwater vehicle remains surfaced; defining a void probability as a probability that there are no surface vessels within said specified safety radius of a location while said unmanned underwater vehicle is surfaced for said specified duration, said void probability being inverse to said risk of surfacing; constraining said risk of surfacing to a specified maximum value; identifying candidate surfacing locations where said risk of surfacing is not greater than said specified maximum value, said all possible paths comprising each possible path through said candidate surfacing locations; determining an optimum path of said all possible paths as the path having the lowest cost associated with the risk of surfacing; and navigating said unmanned underwater vehicle along the optimum path.

11. The method of claim 10, wherein identifying candidate surfacing locations further comprises obtaining said void probability from an estimated Poisson function of traffic intensity over said operational area based on a spatial point process of points in said operational area where said surface vessels are located.

12. The method of claim 11, wherein iteratively accumulating further comprises: determining a displacement of said traffic intensity for each leg of said each possible path based on said navigation uncertainty over a distance traveled in said each leg; and for each said leg, determining said increase in said risk of surfacing based on said displacement.

13. The method of claim 12, further comprising defining said cost as a ratio between a distance traveled in said each leg and a displaced void probability of said displaced traffic density at an end of said each leg.

14. The method of claim 13, further comprising discarding a possible path when said void probability at one of said surfacing locations on said path exceeds said maximum value for said risk.

15. The method of claim 13, wherein the step of determining an optimum path of all possible paths is further based on said optimum path satisfying specified constraints on said risk and minimizing said cost, wherein minimizing said cost minimizes a number of said surfacing locations and minimizes a distance traveled between said ingress point and said goal point.

16. The method of claim 15, wherein determining said optimum path further comprises discarding a possible path when said void probability at one of said surfacing locations on said path exceeds said maximum value for said risk.

17. The method of claim 1 wherein the step of navigating further comprises the steps of: moving the unmanned underwater vehicle along said optimum path; surfacing the unmanned underwater vehicle at the identified candidate surfacing location along said optimum path; obtaining a global positioning system fix while surfaced; and resetting inertial navigation errors according to the obtained global positioning system fix.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) A more complete understanding of the invention and many of the attendant advantages thereto will be readily appreciated as the same becomes better understood by reference to the following detailed description when considered in conjunction with the accompanying drawings wherein like references numerals and symbols designate identical or corresponding parts throughout the several views and wherein:

(2) FIG. 1 is a simplified illustration of an operational area for an unmanned underwater vehicle (UUV);

(3) FIG. 2 is a simplified illustration of the operational area of FIG. 1 showing surface traffic intensity;

(4) FIG. 3 illustrates a schematic block diagram of a method for planning surfacing locations along a route for an UUV;

(5) FIG. 4A and FIG. 4B are simplified illustrations of the operational area of FIG. 2 showing planned paths using the method of FIG. 3 with varying parameters; and

(6) FIG. 5 illustrates a schematic block diagram of an alternate method for planning surfacing locations along a route for an UUV.

DESCRIPTION OF THE INVENTION

(7) Referring now to FIG. 1, there is shown a simplified illustration of operational area S for unmanned underwater vehicle (UUV) 12. Area S is a fully navigable area with spatially varying maritime traffic. UUV 12 is tasked to transit from ingress point p.sub.1 to a goal p.sub.G. UUV 12 state uncertainty accumulates when submerged and vehicle 12 must surface along the way to goal p.sub.G to reset any localization error. Surfacing should occur in locations with minimal collision risk and account for UUV 12 state uncertainty to minimize the discrepancy between planned and actual surfacing locations, as any discrepancy may potentially result in surfacing in a high-risk region.

(8) Referring now also to FIG. 2, there is shown surface traffic intensity mapped onto area S. The mapping of maritime traffic intensity can be created by collecting vessel counts in S for a user-specified time interval T.sub.int (e.g., day, month, year). Datasets of historical maritime traffic are readily available from the Automatic Identification System (AIS), which monitors automatic identification and location messages of vessels. Vessels located at sS are the points of our spatial process that are used to estimate the Poisson intensity function :S.fwdarw.[0,). For simplification, but not limitation, only five different intensities are shown in FIG. 2. It will be understood by those in the art that the mapping will result in a continuous gradient of all intensities. Tools for fitting estimated intensities are well known in the art.

(9) The expected number of vessels on a (Euclidian) neighborhood BS in unit-time is

(10) $\begin{array}{cc}{N}_B=\frac{1}{T}{}_B\left(s\right)ds.& \left(1\right)\end{array}$
A Poisson process is characterized with the property that the probability of N.sub.B=n, for n{0}, is Poisson distributed

(11) $\begin{array}{cc}Pr\left[N_B=n\right]=\frac{{\left(N_B\right)}^n}{n!}{e}^{-N_B}.& \left(2\right)\end{array}$

(12) Assuming UUV 12 will remain surfaced for a duration T<<T.sub.int, the probability that there are no vessels in B for duration T is the so-called void probability
v(B,T)=Pr[N.sub.B,T=0]=e.sup.N.sup.B.sup.T.(3)
The probability of colliding with a vessel when surfaced in B is proportional to the number of vessels in B. Therefore, equation (3) is adopted to quantifying the safety (inverse risk) of surfacing in any given neighborhood. A value of v(.,T)=1 corresponds to the minimum risk at the surface and v(.,T)=0 corresponds to the highest risk.

(13) As is known in the art, points in S can be randomly displaced on S to form a new, valid intensity function if the displacement of each point is independent and identically distributed (IID). Specifically, let (s|s) be the IID probability distribution characterizing the stochastic displacement for a point at s. The new point process is Poisson with intensity
(s)=.sub.s(s)(s|s)ds.(4)

(14) Intensity displacement is used herein to establish functional dependence between UUV 12 state uncertainty and v(B,T) to model the degradation of position information in the environment and penalize repeated deferred surfacing. Safety is distinguished with respect to a displaced intensity function as {tilde over (v)}(.,T). In choosing candidate locations for surfacing UUV 12, redundant/inefficient surfacing is penalized so as to minimize the number of times a vehicle must surface. Additionally and jointly, repeatedly deferred surfacing leading to undesired navigation performance also is penalized.

(15) Referring now also to FIG. 3, there is illustrated a schematic block diagram of method 100 for planning surfacing locations along a route for UUV 12. Method 100 begins at block 110 with the user specifying the parameters for the route mapping. The parameters will include operational and performance standards for UUV 12, such as the time T spent at a surfacing location and safety standards for the route to be chosen. These inputs are described further hereinafter. With the parameters set, block 112 of method 100 maps the intensity onto the operational area S as discussed hereinbefore. A location p.sub.iS, i, is a candidate surfacing location (CSL) if the void probability in the neighborhood of radius r around it, B.sub.i, satisfies
v(B.sub.i,T),(5)
for user-specified r, >0, as input at block 110. Using Eq. 5, block 114 determines all the CSLs throughout area S. It is noted that the intensity for identifying candidate surfacing points in Eq. (5) is with respect to the original, un-displaced intensity. The collection of all candidate surfacing points, including the ingress and goal, are defined as the nodes of a directional graph G at block 116.

(16) As noted hereinbefore, method 100 incorporates navigation uncertainty in determining the optimal path and surfacing locations for UUV 12. To do so, it is recognized that UUV 12 is equipped with an inertial navigation system (INS) that incorporates information from various sensors such as accelerometers, gyros and velocity to estimate the vehicle state (i.e., position, velocity, attitude) and uncertainty while submerged. The performance of an INS can be typically expressed by the circular error probability (CEP) rating that specifies the radius of a circle where the probability of UUV 12 being in the circle is 50%.

(17) The CEP for submerged rectilinear transits at a constant velocity grows linearly with the distance from the last surfacing and can be written as a percentage of distance traveled. Accordingly, the CEP radius for a traverse of km is .Math.. The value of in sub-sea applications is typically near 0.1% but can exceed 2%. Thus , as input at block 110, is significantly dependent on the quality of inertial sensors and whether velocity measurements are taken relative to the sea floor.

(18) The CEP radius for traversing a path-segment between candidate surfacing point p.sub.i to the next surfacing point p.sub.i+1, is .Math.d(p.sub.i, p.sub.i+1), where d(,) is the distance between the two locations. The known conversion from CEP radius to standard deviation is .sub.i,i+1 (0.849.Math.d(p.sub.i,p.sub.i+1)). It is taken that the belief in the state of UUV 12 is characterized by a symmetric Gaussian. Thus, the uncertainty when surfacing at p.sub.i+1 is characterized by the covariance matrix
=diag[.sub.i,i+1.sup.2,.sub.i,i+1.sup.2].(6)

(19) The approximated Gaussian is used as the probability density to iteratively displace the intensity as in Eq. (4) as a function of accumulated state uncertainty. Hence, it can be taken that (s|s)N(s,|s). In doing so, method 100 influences the surfacing risk as a function of state uncertainty.

(20) The cost (edge weight) for traversing from a surfacing point p.sub.i to the next surfacing point p.sub.i+1 is defined as the ratio between distance-traveled and void probability of the displaced intensity at the resulting surfacing node, d(p.sub.i,p.sub.i+1)/{tilde over (v)}(B.sub.i+1,T). The void probability in the cost of method 100 is dependent on the distance, hence, accumulated uncertainty from the source node, i.e., {tilde over (v)}(B.sub.i+1,T)={tilde over (v)}(B.sub.i+1,T|p.sub.i). For simplicity, but not limitation, dependence on the specific p.sub.i is omitted.

(21) This cost assignment for the edge weights of G is chosen since the cost for equidistant path-segments is dependent on the diffused intensity around the subsequent surfacing location. It can be noted that the cost function herein can be interpreted as the ratio between accumulated state uncertainty and uncertainty-conditioned safety because uncertainty is proportional to distance-traveled.

(22) Let ={.sub.1, . . . , .sub.|.sub.|} be the collection of all feasible paths, where .sub.i is comprised of a sequence of candidate surfacing locations on the way to the goal. Starting with the first path in the set (block 118) and at the ingress, or first point of each path (block 120), the cumulative cost CCOST is initialized (block 122). Using Eq. 6, method 100 computes the covariance matrix (block 124) for the next leg of the path. At block 126, intensity displacement is computed for this leg or pair of sequential candidate locations by convolving the intensity with a Gaussian kernel with uncertainty as in Eq. (6). Block 128 uses the approximated Gaussian as the probability density to displace the intensity as in Eq. (4).

(23) At block 130, the cost (edge weight of the displaced directional graph G) for traversing from a surfacing point p.sub.i to the next surfacing point p.sub.i+1 is obtained as described hereinbefore. This cost (COST) is added to the cumulative cost (CCOST) to obtain a new cumulative cost (CCOST) at block 132. If, at block 134, for p.sub.i, {tilde over (v)}(B,T)<, then the path .sub.i is discarded (block 136).

(24) Method 100 then checks if all paths have been completed (block 138). If not, method 100 proceeds to the next path in the set (block 140), returning to block 120 to begin at the first point of the next path. If the path is not discarded, block 142 checks if all legs of the path are completed. If not, method 100 proceeds to the next leg (block 144) and returns to determine the covariance at block 124. If the path is complete, method 100 adds the completed path to a list of completed paths (block 146) and then returns to block 138 to determine if all paths have been completed. If all paths are complete, then the optimal path is determined at block 148 from

(25) $\begin{array}{cc}{}^{*}=\underset{}{\min }\left(.Math..Math.-1\right){.Math.}_{i=1}^{.Math..Math.-1}\frac{d\left(p_i,p_{i+1}\right)}{\stackrel{}{v}\left(B_{i+1},T\right)},& \left(7\right)\end{array}$
based on all possible paths from the list of paths and method 100 ends.

(26) Eq. (7) chooses the path that minimizes the number of surfacings and travel distance that satisfies the user constraint on risk from Eq. 5. Non-optimal paths may have less overall risk but would have more surfacings and longer travel distance. It is noted that more surfacings inherently increases the odds of collision. Redundant/inefficient surfacing and repeatedly deferred surfacing are jointly penalized in Eq. (7). Appending an additional surfacing point to the optimal path results in a longer-duration path, which increases risk exposure and potentially increases cost. Likewise, removing a surfacing point from the optimal path decreases the void probability (safety) of the surfacing point following the removed point via displacement, resulting in a (potentially significant) higher cost path.

(27) Referring now to FIG. 4A, there is shown a simplified illustration of the use of method 100 to plan a path through a 150 km150 km operational area S. The ingress location p.sub.1 and goal location p.sub.G of FIG. 1, as well as the surface traffic intensity of FIG. 2 are also indicated in FIG. 4A. The planned path, designated as dotted line , includes three surfacing locations, designated by triangles SL.

(28) As ingress p.sub.1 and goal location p.sub.G are somewhat close, a typical high-end INS with a CEP of 0.1% would surface at most once. Accordingly, much higher values of can be chosen for illustration purposes. For the illustration of FIG. 4A, the input parameters were as follows:

(29) TABLE-US-00001 PARAMETER VALUE Neighborhood radius r = 0.5 A minimum safe distance to any vessel (km) Void probability = 0.7 Threshold on maximum allowable threshold surfacing risk Navigation CEP = 5% Inertial Navigation System performance specification Surface time T = 5 Expected time duration on the surface (minutes)

(30) The void probability =0.7 corresponds to an expected 0.36 vessels in the neighborhood for the T=5-minute duration at the surface.

(31) The effect of the circular error probability (CEP), , on the planned route is shown in comparing FIG. 4A and FIG. 4B. FIG. 4B illustrates two planned routes shown by dotted line R2 with surfacing locations designated by rectangles, and dash-dot line R3 with surfacing locations designated by pentagons. For clarity, only one of each of R2 and R3 surfacing points is labeled in FIG. 4B, as SL2 and SL3, respectively. The path characteristics for each path are as follows:

(32) TABLE-US-00002 Number of Distance Route Surfacings Traveled (km) 5% 3 136.40 R2 10% 3 143.87 R3 20% 7 159.69

(33) The behavior of method 100 is shown to increase the traverse distance to the first surfacing point for higher values of in order to surface in a region with lower maritime traffic. Furthermore, the =20% implementation of method 100 is seen to select successive surfacings prior to a traverse through and near regions with high maritime traffic intensity. The successive surfacings reduce the uncertainty when surfacing at subsequent locations that are surrounded by high-risk regions. As seen in FIG. 4B, the pattern of successive surfacings is repeated as UUV 12 approaches goal p.sub.G.

(34) Also, for UUVs with inertial navigation systems having high values of the CEP, method 100 may fail to find a path. Options for such a case are to decrease the safety threshold , reduce the neighborhood radius r over which surfacing risk is evaluated or any combination of both. Reducing the parameters increases the number of candidate surfacing locations and reduces the number of discarded feasible paths.

(35) When compared to method 100, previous surfacing location route planning methods are shown to select conservative paths to goal p.sub.G and to avoid traversing through regions with elevated risk. This conservative tendency of previous methods may result in on-average lower risk paths when compared to method 100. However, the maximum risk of previous methods exceeds that of method 100 since surfacing locations need not satisfy a threshold on risk/safety. Likewise, path length and number of surfacings of previous methods are generally higher than that of method 100, and sometimes significantly higher.

(36) What has thus been described are methods and systems for planning an UUV mission path from a given ingress point to a given goal point. The methods and systems include planning locations along the planned path for the UUV to surface to obtain a GPS fix to reset inertial navigation system errors. In choosing surfacing locations, the methods and systems mitigate the risk of a collision with surface vessels when surfacing. Additionally, the methods and systems provide for incorporating the uncertainty in the state of the INS such that localization uncertainty induced risk is minimized when surfacing near high-intensity surface traffic regions.

(37) The intensity on surface ship traffic is mapped onto the operational area S using a spatial point process model for historical maritime traffic to quantify surfacing risk throughout the operational area. Candidate surfacing locations (CSLs) are determined based on a location exceeding a specified safety threshold for surfacing risk. The collection of all CSLs is defined as the nodes of a directional graph G.

(38) For each leg of each possible path through the CSLs an intensity displacement is determined based on the uncertainty in the state of the INS for that leg. The displaced intensity is mapped onto the operational area and the cost in terms of decreased safety in surfacing is computed. If for any leg the surfacing risk falls beneath the safety threshold, the current possible path is discarded and the next path is investigated. When all paths have been investigated, the optimal path is chosen based on Eq. 7.

(39) Obviously, many modifications and variations of the present invention may become apparent in light of the above teachings. For example, an exhaustive search can be used to find the optimal path when the operational area is sufficiently small. Other methods known in the art can be used for determining the optimal path given the determination of edge weights described herein.

(40) As another example, the configuration of blocks in method 100 can be changed to suit processing capabilities used in executing method 100. Referring now also to FIG. 5, there is illustrated a block diagram of alternative method 100 for determining the optimum path for UUV 12. Blocks in method 100 corresponding to like blocks in method 100 are shown as primed, e.g., block 122 (Initialize CCOST) of FIG. 5 corresponds to block 122 (Initialize CCOST) of FIG. 3.

(41) Method 100 proceeds through blocks 110-138 as described with respect to method 100 apart from block 116A between block 116 and block 118. After forming directional graph G (block 116), block 116A of method 100 sets an initial maximum cumulative cost (MCOST) to MCOST=1, corresponding to a least acceptable path. Method 100 then proceeds to block 118 to start with the first path in the set.

(42) At block 142, method 100 checks if all legs of the current path have been completed. If not, block 144 proceeds to the next leg of the current path, corresponding to block 144 of method 100. If the current path is complete, block 144A checks if the cumulative cost (CCOST) is less than the maximum cumulative cost (MCOST). If so, this would indicate the current path is more acceptable or more optimum than a previously found acceptable or optimum path, i.e., the current path minimizes the number of surfacings and travel distance compared to the previous acceptable path, while still satisfying the constraint on risk. Thus, the optimum path can be set to the current path (block 144B) and MCOST is set to the cumulative cost (CCOST) of the current path (block 144C). If CCOST is greater than MCOST, this indicates the current path is less optimum than the previously determined optimum path and can be discarded (returning to block 136). Proceeding through all paths in this manner, method 100 ends with the optimum path.

(43) It will be understood that many additional changes in details, materials and arrangements of parts which have been described herein and illustrated in order to explain the nature of the invention, may be made by those skilled in the art within the principle and scope of the invention as expressed in the appended claims.