System and method for determining optimal path arrangements for an infrastructure link with terrain slope consideration

Abstract

A method for determining optimal path arrangements for an infrastructure link between two geographic locations, in particular, in uneven terrain. The method includes modelling a geographic terrain containing the two geographic locations; optimizing an arrangement cost and a repair rate for two or more potential paths based on the modelled geographic terrain, an arrangement cost model, and a repair rate model, taking into account at least two design levels, wherein the arrangement cost model incorporates direction-dependent factor and direction-independent factor associated with the path arrangements; and determining the optimal path arrangements each including multiple path portions and respective design levels associated with the path portions based on the optimization.

Claims

1. A computer-implemented method for determining optimal path arrangements for a sub-marine cable between two geographic locations, comprising: modelling, using one or more processors, a geographic terrain containing the two geographic locations, the modelling including modelling the geographic terrain into a grid with multiple grid points such that each point on the model is denoted by a 3D coordinate including altitude of the geographic terrain; optimizing, using the one or more processors, an arrangement cost and a repair rate for two or more potential paths for the sub-marine cable based on the modelled geographic terrain, an arrangement cost model, and a repair rate model, taking into account at least one design level, wherein the arrangement cost model incorporates direction-dependent arrangement cost factors and direction-independent arrangement cost factors associated with path arrangements of the two or more potential paths, the direction-dependent arrangement cost factors being associated with a capsize risk of a remotely operated vehicle arranged to lay the sub-marine cable; determining, using the one or more processors, and based on the optimization, the optimal path arrangements each including multiple path portions and the at least one design level associated with the path portions; and displaying, at a display operably connected with the one or more processors, at least one of the optimized path arrangements on a map of the geographic terrain; wherein the optimization comprises: calculating a minimum weighted cost value over the at least one design level for each point on the modelled geographic terrain; transforming the optimization to a Hamilton-Jacobi-Bellman equation based on the calculated minimum weighted cost value; and applying Ordered Upwind Method to solve the Hamilton-Jacobi-Bellman equation for determining the optimal path arrangements; and wherein determining the optimal path arrangements comprises: determining a set of Pareto optimal solutions representing the optimal path arrangements, wherein the optimal path arrangements are optimal laying paths, wherein the arrangement cost model models the direction-dependent arrangement cost factors as
h.sub.1(x,a)=e.sup.q.sup.1.sup.(x,a)−θ.sup.1+e.sup.q.sup.2.sup.(x,a)−θ.sup.2, where wherein h.sub.1 is the direction dependent arrangement cost, x is the 3D coordinate of the grid point, a is a direction of the path, e is an exponential function, q.sub.1(x, a) is a slope parallel to the direction of the path as a function of x and a, q.sub.2(x, a) is a slope perpendicular to the direction of the path as a function of x and a, θ.sub.1 is a threshold representing an allowable maximum slope parallel to the direction of the path, and θ.sub.2 is a threshold representing an allowable maximum slope perpendicular to the direction of the path.

2. The computer-implemented method of claim 1, further comprising receiving input associated with dimensions of the grid points for modelling the geographic terrain.

3. The computer-implemented method of claim 1, further comprising receiving input associated with the two geographic locations.

4. The computer-implemented method of claim 1, wherein the direction-independent arrangement cost factors comprise arrangement costs associated with: labor, licenses, or protection level.

5. The computer-implemented method of claim 1, further comprising receiving input associated with the direction-dependent arrangement cost factors and the direction-independent arrangement cost factors.

6. The computer-implemented method of claim 1, wherein the direction-independent arrangement cost factors are associated with location and the design level of the path for each portion of a path, and wherein the arrangement cost model sums the arrangement cost per unit length of a path to determine an arrangement cost of the path.

7. The computer-implemented method of claim 1, wherein the repair rate model is based on spatially distributed ground motion intensity associated with the geographic terrain in which the path is arranged.

8. The computer-implemented method of claim 7, wherein the spatially distributed ground motion intensity comprises peak ground velocity.

9. The computer-implemented method of claim 1, wherein the repair rate model is based on spatially distributed ground motion intensity associated with the geographic terrain of each portion of a path and sums the repair rate per unit length of a path to determine a repair rate of the path.

10. The computer-implemented method of claim 1, wherein the sub-marine cable is a sub-marine optical cable.

11. An information handling system for determining optimal path arrangements for a sub-marine cable between two geographic locations, comprising: one or more processors arranged to: model a geographic terrain containing the two geographic locations, including modelling the geographic terrain into a grid with multiple grid points such that each point on the model is denoted by a 3D coordinate including altitude of the geographic terrain; optimize an arrangement cost and a repair rate for two or more potential paths based on the modelled geographic terrain, an arrangement cost model, and a repair rate model, taking into account at least one design level, wherein the arrangement cost model incorporates direction-dependent arrangement cost factors and direction-independent arrangement cost factors associated with path arrangements of the two or more potential paths, the direction-dependent arrangement cost factors being associated with a capsize risk of a remotely operated vehicle arranged to lay sub-marine cable; and determine, based on the optimization, the optimal path arrangements each including multiple path portions and the at least one design level associated with the path portions; a display operably connected with the one or more processors and arranged to display the determined optimal path arrangements on a map of the geographic terrain; wherein the one or more processors are arranged to perform the optimization by, at least: calculating a minimum weighted cost value over the at least one design level for each point on the modelled geographic terrain; transforming the optimization to a Hamilton-Jacobi-Bellman equation based on the calculated minimum weighted cost value; and applying Ordered Upwind Method to solve the Hamilton-Jacobi-Bellman equation for determining the optimal path arrangements; and wherein the one or more processors are arranged to determine the optimal path arrangements by, at least: determining a set of Pareto optimal solutions representing the optimal path arrangements, wherein the optimal path arrangements are optimal laying paths; wherein the arrangement cost model models the direction-dependent arrangement cost factors as
h.sub.1(x,a)=e.sup.q.sup.1.sup.(x,a)−θ.sup.1+e.sup.q.sup.2.sup.(x,a)−θ.sup.2, where wherein h.sub.1 is the arrangement cost model, x is the 3D coordinate of the grid point, a is a direction of the path, e is an exponential function, q.sub.1(x, a) is a slope parallel to the direction of the path as a function of x and a, q.sub.2(x, a) is a slope perpendicular to the direction of the path as a function of x and a, θ.sub.1 is a threshold representing an allowable maximum slope parallel to the direction of the path, and θ.sub.2 is a threshold representing an allowable maximum slope perpendicular to the direction of the path.

12. The computer-implemented method of claim 1, wherein the optimizing of the two or more potential paths takes into account at least two design levels each corresponding to a respective level of shielding for the sub-marine cable, and wherein the multiple path portions of a corresponding optimal path arrangement define a shape of the corresponding optimal path arrangement and having the at least two design levels such that the corresponding optimal path arrangement is a non-homogenous path arrangement with different levels of shielding for at least some of the path portions.

13. The information handling system of claim 11, wherein the optimization of the two or more potential paths by the one or more processors takes into account at least two design levels each corresponding to a respective level of shielding for the sub-marine cable, and wherein the multiple path portions of a corresponding optimal path arrangement define a shape of the corresponding optimal path arrangement and having the at least two design levels such that the corresponding optimal path arrangement is a non-homogenous path arrangement with different levels of shielding for at least some of the path portions.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) The patent or application file contains at least one drawing executed in color. Copies of this patent or patent application publication with color drawing(s) will be provided by the Office upon request and payment of the necessary fee.

(2) Embodiments of the present invention will now be described, by way of example, with reference to the accompanying drawings in which:

(3) FIG. 1 a flow diagram illustrating a method for determining optimal path arrangement for an infrastructure link in one embodiment of the invention;

(4) FIG. 2 is a map showing an exemplary region D1, wherein the white line illustrates a stream watershed;

(5) FIG. 3A is a contour map of region D1, wherein the curve marked by pluses indicates the path obtained by the OUM-based algorithm, and the curve marked by circles indicates the path obtained by the FMM-based method;

(6) FIG. 3B is a slope map of region D1, wherein the curve marked by pluses indicates the path obtained by the OUM-based algorithm, and the curve marked by circles indicates the path obtained by the FMM-based method;

(7) FIG. 4 a map showing an exemplary region D2, wherein the blue rectangular indicate the region D2 and the white line illustrates a fault line;

(8) FIG. 5A is a slope map of region D2;

(9) FIG. 5B is a shaded surface map of Peak Ground Velocity (PGV) for region D2 in log scale;

(10) FIGS. 6A, 6B, 6C, 6D, 6E and 6F are Pareto optimal paths modelled on the PGV map of region D2, where the magenta lines indicate the cable or cable segments being adopted at a first design level, and the black lines indicate the cable or cable segments being adopted at a second design level;

(11) FIG. 7 is a graph showing non-dominated front for two objectives—total number of repairs and cable laying cost; and

(12) FIG. 8 is an information handling system that can be configured to operate the method in one embodiment of the invention.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

(13) Path Optimization for Infrastructure Links

(14) The invention relates to path optimization for an infrastructure link between two locations on the Earth's surface that crosses uneven terrain which hinders the stability of cable laying vehicle (or remotely operated vehicle) as it buries the cable.

(15) In one embodiment, the focus is on path optimization of infrastructure links, in particularly, submarine cables, where the terrain is having uneven slope. Preferably, the problem can be formulated as a multi-objective optimal control problem and the objective is to find the set of Pareto optimal paths for the infrastructure link with two objective functions—to minimize the laying cost associated with the laying of the infrastructure link and to minimize the number of potential failures (hence repairs) along the infrastructure link.

(16) FIG. 1 shows a method 100 for determining optimal path arrangements for an infrastructure link between two geographic locations. The method 100 comprises a step of modelling a geographic terrain containing the two geographic locations 102. The modelling of the geographic terrain in the present embodiment may be built on the state of the art in geographic information systems (GIS) for terrain approximation. GIS based path selection approaches digitize geographic data and represents the surface of the Earth by a graph. Multiple factors affecting cable path planning are considered through a summary cost which is a sum of the weighted costs of each of the factors.

(17) The method 100 further comprises a step 104 to optimize an arrangement cost and a repair rate for two or more potential paths based on the modelled geographic terrain in step 102, an arrangement cost model, and a repair rate model while taking into account of at least two design levels, where the arrangement cost model incorporates direction-dependent factor and direction-independent factor associated with the path arrangements. The direction-dependent factor may comprises direction of the path or slope of the geographic terrain in which the path is arranged, and the direction-independent factor may comprises labor, licenses, or protection level.

(18) In this embodiment, the two objective functions—arrangement cost and repair rate are considered. The first objective function may include the laying cost and the construction cost. For brevity, thereafter, the term arrangement cost used herein refers to mainly to laying cost. The laying cost is applicable to, for example, burying a submarine cable under the seabed. The second objective function is an index associated with the estimation of future number of repairs (or failures) of the link in a given time period (e.g., 100 years). Although the first objective is about cost incurred during construction, the second objective is about cost incurred in the (potentially, long term) future.

(19) Factors associated with the estimation of the arrangement cost include the length of the link, location (with different terrain slope), requirement for security arrangements, licensing, etc. As an example in this embodiment, the arrangement cost increases enormously when the ROY rolls over in uneven terrain. Whereas the repair rate (failure rate) indicates both potential costs of repairs, as well as link downtime that may have significant societal cost. To calculate the total number of repairs for a link, the term repair rate is used to indicate the predicted number of repairs per unit length of the link over a fixed time period into the future.

(20) While the capital cost of laying a cable is a crucial factor in the overall costs of cable networks, resilience to a range of risks is also important. Both natural hazards and human activities may damage submarine cables. Natural hazards that may damage cables include volcanic activities, tsunamis, landslides and turbidity currents, while human activities in the ocean, such as fishing, anchoring and resource exploration activities also pose a major threat to the safety of submarine cables. It is shown that over 65% of all cable faults occurring in water depths less than 200 m result from human activities.

(21) In order to improve the survivability of submarine cables, various approaches include but not limit to designing the path of the cable to avoid high risk areas, adopting cables with strong protection, and burying the cable under the seabed. As an example, to protect a cable from being damaged by human activities, plough burial operation carried out by a remotely operated vehicle (ROV) is usually performed in water depths of less than 1000 m where seabed conditions allow.

(22) Path planning, a procedure of selecting the route for laying the cable, is an important part of constructing a submarine cable system. The path of a cable affects its construction cost, and the breakage risk of the cable is strongly related to the location of the cable. High slopes increase the propensity of the ROV to topple over as it buries the cable, and so the slope of the terrain needs to be considered during the path planning procedure. It is suggested by the International Cable Protection Committee (ICPC) that the planned path does not violate any of these conditions: ≤6° for side slopes (i.e., the slope in the direction of the path) in buried areas (depending on seabed composition) ≤15° for slopes perpendicular to the route in buried areas ≤25° for slopes perpendicular to the route in surface lay areas

(23) The present invention, therefore, also takes into consideration of the terrain slope for submarine cables as a multi-objective optimal control problem.

(24) The method 100 further comprises a step 106 to determine the optimal path arrangements each including multiple path portions and respective design levels associated with the path portions based on the optimization. In the present embodiment, the method 100 for determining the optimal path can be approached by converting the multi-objective optimal control problem into a single objective optimal control optimization problem by applying weights to each objective. Pareto optimal path can be obtained by solving the single objective optimal control problem using Ordered Upwind Method (OUM). The method 100 in the present invention also considers non-homogenous cables (i.e. segments of cables at more than one design levels) and the stability of remotely operated vehicle (ROV) in path planning as a function of both the side slope and the slope perpendicular to the path direction.

(25) Modelling

(26) Models are for designing the path and selecting the design level of each point on the path of a cable between the starting node and the destination along the Earth's surface or buried in shallow ground or under seabed. Three models are described below.

(27) In the below models, D denotes a closed and bounded path-connected region on the Earth's surface, and U denotes the set of possible design levels of the cable. The function u: D.fwdarw.U represents the design level: u(x) is the required design level at x∈D based on issues such as earthquake risk, etc. Without loss of generality, the set U of available design levels is assumed to be the same for any point x∈D. Path is designed to select the design level of each point on the path of a cable γ∈D between the Start Point A∈D and the End Point B∈D. Curves in D are assumed parameterized according to the natural parametrization, i.e., parameterizing a curve γ as a function of arc length denoted by s, so that a curve γ: [0; l (γ)] .fwdarw.D is a function from the interval [0; l (γ)], taking values in D, where l (γ) is the length of the curve. This apparently circuitous definition is not to be a problem in practice because of the method used to find such curves. A path (curve) and corresponding design levels are obtained such that γ (0)=A, γ (l(γ))=B. Below detailed the landform model, laying cost, and the expected number of potential required repairs.

(28) A. Earth's Surface Model

(29) In this embodiment, the Earth's surface is approximated by using a triangulated piecewise-linear two-dimensional manifold M in R.sup.3. Each point on M is represented by three-dimensional coordinates (x, y, z), where z=ξ(x, y) is the altitude of geographic location (x, y).

(30) B. Laying Cost Model

(31) As mentioned, the laying cost of submarine cables not only depends on the local site attributes (soil type, elevation, etc.), labor, licenses (e.g. right of way) and protection level, but also depends on the direction of the path. The laying cost consists of two components: (1) a direction-dependent laying cost that depends on the direction of the path and the slope of the terrain in order to account for instability risk of the ROV; (2) a direction-independent laying cost that encompasses all other costs, such as labor, licenses and protection level mentioned above. In this embodiment, let a:R+.fwdarw.A, where A={a∈T.sub.x(M)|∥a∥=1} define the direction in which the ROV is facing, where T.sub.x(M) is the tangent space of the manifold M at the point x ∈ M. Note that {dot over (γ)} (s)=a(s), s≥0 by our definition. The set of admissible controls describe the direction of a path is defined A={a(⋅):R+.fwdarw.A|a(⋅) is piecewise continuous}. Redefine u:R+.fwdarw.U by the natural parametrization of a path, where U is the set of the available design levels. The set of admissible design levels for a cable is defined U={u(⋅):R+.fwdarw.U|u(⋅) is piecewise constant}.

(32) For any point x=(x, y, z)∈M; z=ξ(x, y), we use h(x; a; u) to represent the laying cost per unit length, if the direction of the path is a=({dot over (x)}; {dot over (y)}; ż)∈A and the design level is u∈U. Note that +

(33) $\stackrel{.}{z}=\frac{\partial z}{\partial x}\stackrel{.}{x}+\frac{\partial z}{\partial y}\stackrel{.}{y}$
since x∈M, where

(34) $\frac{\partial z}{\partial x},\frac{\partial z}{\partial y}$
is the slope gradient vector at x.

(35) To consider instability risk to the ROV caused by terrain slope, the direction-dependent laying cost is modeled as follows. Let

(36) $n=\left(\frac{\partial z}{\partial x};\frac{\partial z}{\partial y};-1\right)$
denote the normal vector at the point x on the surface z=ξ(x, y). The slope in the direction of the path (i.e., side slope) is represented by

(37) $\begin{array}{cc}{q}_1\left(x,a\right)=\frac{.Math.\stackrel{.}{z}.Math.}{\sqrt{{\stackrel{.}{x}}^2+{\stackrel{.}{y}}^2}}.& \left(1\right)\end{array}$

(38) For the path direction a and the normal vector n at the point x, the slope perpendicular to the path is

(39) $\begin{array}{cc}{q}_2\left(x,a\right)=\frac{.Math.{\left(n\times a\right)}_3.Math.}{.Math.{\left(n\times a\right)}_{12}.Math.}=\frac{.Math.\frac{\partial z}{\partial x}\stackrel{.}{y}-\frac{\partial z}{\partial y}\stackrel{.}{x}.Math.}{\sqrt{{\left(\frac{\partial z}{\partial y}\stackrel{.}{z}+\stackrel{.}{y}\right)}^2+{\left(\frac{\partial z}{\partial x}\stackrel{.}{z}+\stackrel{.}{x}\right)}^2}},& \left(2\right)\end{array}$

(40) where x represents cross product, (⋅).sub.3 and (⋅).sub.1a represent the third component and the first two components of the resulting vector, respectively.

(41) To incorporate the two considerations of the side slope and the slope perpendicular to the path, an exponential function is used to model the direction-dependent part of the cable laying cost related to terrain slopes which is defined as follows,

(42) $\begin{array}{cc}{h}_1\left(x,a\right)=e^{q_1\left(x,a\right)-{\theta }_1}+e^{q_2\left(x,a\right)-{\theta }_2},& \left(3\right)\end{array}$

(43) where θ.sub.1∈R.sub.+, θ.sub.2∈R.sub.+ are two thresholds represent the allowable maximum side slope and the slope perpendicular to the path. The use of the exponential function provides a steep penalty for failure to remain within the bounds prescribed for slopes. An alternative may be to have a sharp cut-off penalty but the present approach using (3) appears to work well.

(44) Inclusion of the direction-independent component h.sub.2(x, u) gives the unit-length laying cost function h(x, a, u) as
h(x,a,u)=h.sub.1(x,a)h.sub.2(x,u).  (4)

(45) Observe that this cost function depends both on location of the path and on the direction of the path. The unit-length laying cost function h(x, a, u) is assumed to be continuous and that it satisfies h(x, a, u)>0 for all x∈M, a∈A and u∈U, the non-continuous case of h is discussed later.

(46) As discussed, a cable is to be laid, represented by a Lipschitz continuous curve γ to connect Start Point A and End Point B in M. The total laying cost of the cable γ with the controls of path direction a(⋅)∈ A and design levels u(⋅)∈ U is represented by H(γ, a(⋅), u(⋅)). Applying the additive assumption of the laying cost, H(γ, a(⋅), u(⋅)) can be written as
(γ,a(⋅),u(⋅))=∫.sub.0.sup.l(γ)h(γ(s),a(s),u(s))ds,  (5)

(47) where l(γ) is the total length of the cable γ.

(48) C. Cable Repair Model

(49) The term repair rate is used to indicate the predicted number of repairs per unit length of the cable over a fixed time period into the future, which is then extended to include design level variable u. The repair rate at location x=(x, y, z)∈M; z=ξ(x, y) is defined as g (x, u); u ∈ U. For the same location x on the cable, the repair rate caused by a disaster is lower if a higher-level design is adopted, and vice versa. The repair rate function g (x, u) is also assumed to be continuous and satisfies g (x, u)>0 for all x∈M and u∈U.

(50) Let G (γ, u(⋅)) denote the total number of repairs of a cable γ with the selection (or control) of design levels u(⋅) E U. Again, we assume that G (γ, u(⋅)) is additive. That is, G (γ, u(⋅)) can be rewritten as
(γ,u(⋅)=∫.sub.0.sup.l(γ)(γ(s);u(s))ds.  (6)

(51) As discussed, a higher design level results in a greater direction-independent laying cost and a reduced number of repairs. In other words, h.sub.2(x, u.sub.1)≤h.sub.2(x, u.sub.2) and g(x, u.sub.1) g(x, u.sub.2) if u.sub.1<u.sub.2, if x∈M.

(52) Ground motion intensities, such as Peak Ground Velocity (PGV) may be used to calculate the repair rate g taking into consideration the risk caused by earthquakes. Other natural hazards (e.g. landslides, debris flows, volcanoes, storms, hurricanes) that may damage cables can be dealt with in the same way using the laying cost model and cable repair model provided that they are local and additive in nature.

(53) Problem Formulation and Solution

(54) The following provides the detailed mathematical formulation of the link path planning problem and then introduced the methodology of this embodiment. Based on the models of landforms, construction cost, and the potential required repairs, the multi-objective optimization problem of minimizing the construction cost and the total number of repairs is as follows:

(55) $\begin{array}{cc}\underset{a(.Math.),u(.Math.)}{\min }\Phi \left(\gamma ,a(.Math.),u(.Math.)\right),s.t.\gamma \left(0\right)=A,\gamma \left(l\left(\gamma \right)\right)=B,& \left(\mathrm{Problem}1\right)\end{array}$

(56) where γ is the cable that connects Start Point A and End Point B.

(57) In general, the two objectives, the laying cost and the total number of repairs are conflicting, so it is impossible to simultaneously minimize both. Therefore, a set of Pareto optimal solutions have to be sought.

(58) A common approach to solve multi-objective optimization problem is to reduce it to a single-objective optimization problem, which operates by minimizing a weighted sum of the objectives to recover Pareto optimal solutions. By the weighted sum approach, Problem 1 is converted into a single-objective path planning problem, namely,

(59) $\begin{array}{cc}\underset{a(.Math.),u(.Math.)}{\min }{\Phi }^{\prime }\left(\gamma ,a(.Math.),u(.Math.)\right)={\int }_0^{l\left(\gamma \right)}f\left(\gamma \left(s\right),a\left(s\right),u\left(s\right)\right)\mathrm{ds},s.t.\gamma \left(0\right)=A,\gamma \left(l\left(\gamma \right)\right)=B,& \left(\mathrm{Problem}2\right)\end{array}$

(60) where ƒ(γ(s), a(s), u(s))=h(γ(s), a(s), u(s))+c.Math.g(γ(s), u(s)) and c∈R.sub.+.sup.1 ∪{o}. The assumptions of continuity and non-negativity made for h and g render the weighted cost function ƒ(γ(s), a(s), u(s)) continuous and non-negative. Since M×A×U is a compact set, there exists 0<F.sub.min, F.sub.max<∞.
F.sub.min<ƒ.sub.min(X)≤ƒ(X,a,u)≤ƒ.sub.max(X)<F.sub.max  (7)

(61) For every (x, a, u)∈M×A×U, where

(62) $f_{\min }\left(x\right)=\underset{a\in A,u\in U}{\min }f\left(x,a,u\right),f_{\max }\left(x\right)=\underset{a\in A,u\in U}{\max }f\left(x,a,u\right).$

(63) The following theorem shows that a set of Pareto optimal solutions of Problem 1 can be obtained by solving Problem 2.

(64) Theorem 1

(65) If (γ*; a*(⋅), u*(⋅)) is an optimal solution for Problem 2, then it is Pareto optimal for the laying cost H and the total number of repairs G.

(66) For any point x∈M, controls a(⋅)∈ A and u(⋅)∈U, a cost function is defined φ:M×A×U.fwdarw.R.sub.+ that represents the cumulative weighted cost to travel from the point x to End Point B of a cable β as
φ(β,a(⋅),u(⋅)=∫.sub.0.sup.l(β)ƒ(β(s),a(s),u(s))ds,  (8)

(67) where β ∈Lip([0, +∞); M) is a Lipschitz continuous curve parameterized by its length,

(68) 0$.Math.{\beta }^{\prime }\left(x\right).Math.=.Math.\frac{d\beta \left(s\right)}{\mathrm{ds}}.Math.=1,$
β(0)=x, and β (l(β))=B.

(69) Given the definition of the cost function φ, the value function Φ(x): M.fwdarw.R+ that represents the minimal cumulative weighted cost to travel from the point x to End Point B is

(70) $\begin{array}{cc}\varphi \left(x\right)=\underset{a(.Math.),u(.Math.)}{\min }\phi \left(\beta ,a(.Math.),u(.Math.)\right)=\phi \left({\beta }^{*},a^{*}(.Math.),u^{*}(.Math.)\right),& \left(9\right)\end{array}$

(71) where β*∈ M, a*(⋅)ε A and u*(⋅)∈U are optimal solutions for minimizing φ(β, a(⋅), u(⋅)). Evidently, Φ(B)=0.

(72) Regarded as the function that achieves the lowest cost for x∈M to reach End Point B, the value function Φ satisfies the following continuous Dynamic Programming Principle (DPP).

(73) Theorem 2

(74) For every s>0, t≥0, such that 0≤s s+t≤l(β*),

(75) $\begin{array}{cc}\varphi \left(\beta \left(s\right)\right)=\underset{a(.Math.),u(.Math.)}{\min }\left\{{\int }_s^{s+t}f\left(\beta \left(\tau \right),a\left(\tau \right),u\left(\tau \right)\right)d\tau +\varphi \left(\beta \left(s+t\right)\right)\right\}.& \left(10\right)\end{array}$

(76) That is, controls a*(⋅) and u(⋅) are optimal between two points if and only if the same controls are optimal over all intermediate points along the curve.

(77) Next, a partial differential equation, namely the Hamilton-Jacobi-Bellman (HJB) equation can be derived from Equation (10) by applying DPP. Let the controls a*(⋅), u*(⋅) and the curve γ be optimal for Problem 2. From Theorem 2,
ϕ(γ*(s))=∫.sub.s.sup.s+tƒ(γ*(T),a*(T),u*(T))d.sub.T+ϕ(γ*(s+t)).  (11)

(78) Dividing Equation (11) by t and rearranging, with t tending to 0, gives

(79) $\begin{array}{cc}f\left({\gamma }^{*}\left(s\right),a^{*}\left(s\right),u^{*}\left(s\right)\right)+\frac{\varphi \left({\gamma }^{*}\left(s+t\right)\right)-\varphi \left({\gamma }^{*}\left(s\right)\right)}{t}\approx 0.& \left(12\right)\end{array}$

(80) Letting t.fwdarw.0, the following static HJB equation is obtained,

(81) $\begin{array}{cc}\underset{a\in A;u\in U}{\min }\left\{\left(\nabla \varphi \left(x\right).Math.a\right)+f\left(x,a,u\right)\right\}=0,x\in M,\varphi \left(B\right)=0,& \left(13\right)\end{array}$

(82) where ⋅ in the above equation denotes the dot product in R.sub.3. Once deriving the value function Φ, the optimal controls a* and u* can be calculated by
(a*,u*)=arg min.sub.a∈A,u∈M{∇ϕ(γ(s)).Math.a+ƒ(γ(s),a,u)}γ(0)=A.  (14)

(83) Note that if ƒ(x, a, u)=ƒ(x), the weighted cost function ƒ is isotropic and the cable is homogeneous. The optimal control a* is the direction of steepest descent of Φ, given by

(84) $\begin{array}{cc}{a}^{*}\left(x\right)=-\frac{\nabla \varphi \left(x\right)}{.Math.\nabla \varphi \left(x\right).Math.}.& \left(15\right)\end{array}$

(85) As a result, the HJB equation (13) simplifies to the following well known Eikonal equation.
∥∇ϕ(x)∥=ƒ(x),ϕ(B)=0.  (16)

(86) In this case, the cable path planning Problem 1 has been described as a multi-objective variational optimization problem and solved by Fast Marching Method (FMM).

(87) If ƒ(x, a, u)=ƒ(x, u); that is, the weighted cost function is isotropic but the cable is nonhomogeneous, the optimal control a* is still the direction of steepest descent of Φ and the HJB equation (13) is reduced to the following extended Eikonal equation.

(88) $\begin{array}{cc}.Math.\nabla \varphi \left(x\right).Math.=\underset{u}{\min }f\left(x,u\right),\varphi \left(B\right)=0.& \left(17\right)\end{array}$

(89) In this case, the cable path planning Problem 1 is solved by a FMM-based method.

(90) On the one hand, the classical solution of Equation (13) that is continuous and differentiable (i.e., C.sup.1) everywhere in the entire domain M may not exist even when the weighted cost function, is smooth. On the other hand, weak solutions of Equation (13), which satisfy Equation (13) except for finitely many points in M are known to be non-unique in most cases. Viscosity solutions, that intuitively are almost classical solutions whenever they are regular enough, are defined as weak solutions for which the maximum principle holds when they are compared with smooth functions. Classical solutions are always viscosity solutions. As a natural solution concept to use for many HJB equations representing physical problems, viscosity solutions always exist and are unique and stable. Accordingly, the viscosity solution of Equation (13) is precisely the value function of Equation (10). Generally, the analytic viscosity solution of the HJB equation (13) is difficult to obtain, so a numerical method has to be sought to compute an approximate solution.

(91) In the present invention, Ordered Upwind Method (OUM) is adopted to solve the HJB Equation (13); that is, to obtain an approximation ϕ of Φ on the vertices of M. Recall that a triangulated piecewise-linear two-dimensional manifold M is used, consisting of faces, edges, and vertices, in R.sub.3 to approximate the Earth's surface. It is further assumed that the triangulated manifold model is complete.

(92) Similar to FMM, the solution based on OUM is built outwards from B with ϕ (B)=0. The vertices on M are classified into three categories, “Far, Considered, and Accepted”. In the procedure of OUM, the status of vertices can only change from Far to Considered or from Considered to Accepted. In addition, AcceptedFront is defined to be the set of frontier Accepted vertices that neighbor some Considered vertices. For each pair of neighboring vertices x.sub.j and x.sub.k on the AcceptedFront, if there is a Considered vertex x.sub.i neighboring both x.sub.j and x.sub.k, then the line segment x.sub.ix.sub.k belongs to the set called AF. The near front (NF) with respect to each Considered vertex x is defined as
NF(x)={x.sub.jx.sub.k∈AF|∃{tilde over (x)}onx.sub.jx.sub.ks.t.∥{tilde over (x)}−x∥≤νY},  (18)

(93) where ν is the diameter of the triangulated mesh (i.e., if the vertices x.sub.j and x.sub.k are adjacent, then ∥x.sub.j−x.sub.k∥≤υ), and

(94) $\gamma =\frac{\max f\left(x,a,u\right)}{\min f\left(x,a,u\right)}.$

(95) The OUM uses a semi-Lagrangian scheme where the control is assumed to be held constant within each triangle. To update the value function ϕ of the considered point x, let x.sub.j, x.sub.k∈NF(x) be two adjacent vertices, whose value functions ϕ (x.sub.j), ϕ (x.sub.k) are known. Based on the first-order approximation of Equation (10), the upwinding approximation for Φ(x) from a “virtual triangle” X.sub.jXX.sub.k can be defined as:

(96) $\begin{array}{cc}{\varphi }_{\mathrm{xj},\mathrm{xk}}^{\prime }\left(x\right)=\underset{\zeta \in \left[0,1\right];u\in U}{\min }\left\{\tau \left(\zeta \right)f\left(x,a_{\zeta },u\right)+\zeta \stackrel{\_}{\varphi }\left(x_j\right)+\left(1-\zeta \right)\stackrel{\mathrm{.Math.}}{\varphi }\left(x_k\right)\right\},& \left(19\right)\end{array}$

(97) where τ(ζ)=∥(ζx.sub.j+(1−ζ)x.sub.k)−x∥ is the distance between vertex x and the interpolation point ζx.sub.j+(1−ζ)x.sub.k, and the direction vector

(98) $a\zeta =\frac{\zeta \mathrm{xj}+\left(1-\zeta \right)\mathrm{xk}-x}{\tau \zeta }.$
Golden Section Search can be used to solve the minimization problem 6 in Equation (19). The value function ϕ(x) at x is then obtained by

(99) 0$\begin{array}{cc}\stackrel{\_}{\varphi }\left(x\right)=\underset{x_j{x}_k\in \mathrm{NF}\left(x\right)}{\min }{\varphi }_{\mathrm{xj},x_k}^{\prime }\left(x\right).& \left(20\right)\end{array}$

(100) Note that ΦX.sub.j, X.sub.k (X) is defined even when X.sub.j and X.sub.k are not adjacent to X. The OUM-based algorithm for Problem 2 is summarized as Algorithm 1. As discussed above, by setting different values of c in Problem 2, different Pareto optimal solutions of the laying cost and the total number of repairs can be obtained. An approximate Pareto front can be generated from the set of obtained Pareto optimal solutions.

(101) TABLE-US-00001 ALGORITHM 1 Algorithm 1 - Algorithm for path planning in the region of interest . Input: Region  (modeled as ), laying cost model h and repair rate model g on , mesh size Δ.sub.x, Δ.sub.y, Start Point A, End Point B, c, step size ; Output: Path γ with minimum weighted cost; 1: Discretize  rectangularly with Δ.sub.x in x and Δ.sub.y in y, and denote the set of points on the grid by Γ; 2: Create edges, faces and obtain a complete triangulation (i.e., ) of  based on Γ; 3: Initialize the labels of all the vertices in Γ except Start Point A as Far. Label Start Point A as Accepted; 4: Label all the vertices x ∈ Γ adjacent to Start Point A as Considered and update their values by Equation ; Let x = argmin.sub.x∈Γ,x is Considered ϕ(x). 5: Label x as Accepted and update the AcceptedFront. 6: Label the Far vertices neighbouring to x as Considered and update their values by Equation . 7: For each other Considered x such that x ∈ NF(x), update its value by $\begin{array}{cc}\stackrel{\_}{\varphi }\left(x\right)\stackrel{△}{=}\min \left\{\stackrel{\_}{\varphi }\left(x\right),\underset{\stackrel{\_}{x}{x}_i\in \mathrm{NF}\left(x\right)}{\min }{\stackrel{\_}{\varphi }}_{\stackrel{\_}{x},x_i}\left(x\right)\right\}.& \left(21\right)\end{array}$ 8: If there is Considered vertex, then go to Step 5. 9: Let γ(0) = B and k = 0. 10: while ∥γ(k) −A∥.sup.2 > ε do 11: Compute the gradient ∇ϕ(γ(k)) using finite-difference from the obtained value function ϕ; 12: Compute the optimal controls a* and u* by solving Equation ; 13: Compute γ(k + 1) = γ(k) − T∇ϕ(γ(k)), where γ(k) is an approximation of γ(t) at time t = k . 14: end while 15: return γ.

(102) The solution ϕ, produced by the above OUM-based algorithm, is proved to converge to the viscosity solution 4, of the HJB equation (13) as the grid step size tends to zero given the assumption of continuity of the laying cost function h and the cable repair rate function g. Note that when the laying cost function h and the cable repair rate function g are not continuous (for example, the design level u is a discrete variable), no proof of convergence currently exists. Nonetheless, OUM still appears to work correctly in examples and apparently also in the result.

(103) To obtain an approximate optimal path, a minimization problem (14) is solved for a* and u* (replacing Φ with ϕ computed by the OUM) each time the path exits its current triangle and enters a new adjacent triangle. The path is not restricted to the edges of the mesh and is found from γ(0)=A, and is completed when End Point B is reached. The computational complexity of OUM is

(104) $O\left(\frac{F\max }{F\min }N\log N\right),$
where N is the number of vertices in the mesh M.
Applications

(105) This section illustrates the applications of Algorithm 1 to two 3D realistic scenarios. To explicitly show how the instability risk affects the path of a cable, in the first scenario, only the minimization of laying cost is considered when designing the path of the cable between two nodes. It is assumed that there is only one design level in the first scenario. Additionally, the resulted path of the OUM-based algorithm is compared with that of the FMM-based algorithm.

(106) In the second scenario, both the laying cost and the total number of repairs are minimized taking into account instability risk. Without loss of generality, it is assumed that there are two design levels in this scenario: Level 1 (low level)—without any protection and Level 2 (high level)—with protection by cable shielding. In the second scenario, considering the tradeoff between the laying cost and the total number of repairs, the Pareto optimal solutions are obtained and the corresponding approximate Pareto front is generated.

(107) A. The First Scenario

(108) FIG. 2 shows a map of an exemplary region D1, which is located in central Taiwan from northwest (23:900° N, 120.850° E) to southeast (23:500′N, 121.000° E). The red white line illustrates the Chenyoulan Stream Watershed. A cable is laid to connect Start Point (23:897° N, 120.975° E) with End Point (23:501° N, 120.851° E) as shown in FIG. 2.

(109) FIGS. 3A and 3B are a contour map and a slope map of region D1 respectively, and are calculated using elevation data of the region D1 from FIG. 1. The elevation data of the region D1 were downloaded from the NASA Shuttle Radar Topographic Mission (SRTM). The resolution of the elevation data is 3 arc-second (approximate 90 m) in both longitude and latitude.

(110) In this scenario, the thresholds for the side slope and the slope perpendicular to the path are set to be 6° and 15°, respectively. As mentioned above, only the laying cost of the path is minimized and there is only one design level in this scenario.

(111) Alternatively,
g(x,u)=0,h(x,a,u)=e.sup.q.sup.1.sup.(x,a)−θ.sup.1+e.sup.q.sup.2.sup.(x,a)−θ.sup.2+h.sub.2(x,u).
where θ1=tan 6° and θ2=tan 15°. Without loss of generality, we set h.sub.2(x, u)=1.

(112) In FIG. 3A, the curve marked by pluses indicates the path obtained by the OUM-based algorithm, and the curve marked by circles indicates the path obtained by the FMM-based method. The laying costs corresponding to the two paths are 142.569 and 150.479 while their lengths are 49.992 km and 47.752 km, respectively. Notice that although the path obtained by OUM-based algorithm is longer, it traverses the watershed to avoid the areas with high slope as much as possible, and therefore it incurs lower laying cost than the path obtained by the FMM-based method.

(113) B. The Second Scenario

(114) FIG. 4 shows a map of an exemplary region D2 as indicated by the blue rectangular, which is located in State of California and Nevada, from northwest (38:000° N, −119:000° E) to southeast (35:500° N, −117:700° E). The white line illustrates the San Andreas fault line. A cable is laid from Start Point (37:900° N, −118:900° E) to End Point (35:600° N, −117:950° E) as shown in FIG. 4. In this scenario, θ1 is set to be 6° and θ2 is set to be 11°.

(115) FIG. 5A shows a slope map of region D2, and FIG. 5b shows a shaded surface map of Peak Ground Velocity (PGV) for region D2 in log scale. Again, the elevation data (with 3 arc-second resolution) of the region D2 were downloaded from SRTM. To evaluate the earthquake induced breakage risk of the cable, Peak Ground Acceleration (PGA) data of the region D2 were downloaded from United States Geological Survey (USGS). The spatial resolution of the PGA data is 180 arc-second. The elevation data was downsampled and the PGA data interpolated to generate the same spatial resolution: 30 arc-second elevation data and PGA data. For calculating the total number of repairs of the cable, PGA can be converted to PGV as follows,
log.sub.10(υ)=1.0548 log.sub.10(PGA)−1.5566,  (22)

(116) where υ(cm/s) represents the PGV value.

(117) FIGS. 6A, 6B, 6C, 6D, 6E and 6F are Pareto optimal paths modelled on the PGV map of region D2 obtained by the OUM-based algorithm, where H(γ*, a(⋅), u*(⋅)) and G(γ*, u*(⋅)) denote the laying cost and total number of repairs, respectively. In each of the FIGS. 6A-6F, the logarithmic PGV map is shown on the left and the slope map is shown on the right, where magenta lines indicate the cable or cable segments adopting Level 1 and the black lines indicate the cable or cable segments adopting Level 2.

(118) The corresponding data collected from each of the Pareto optimal paths in FIGS. 6A-6F, including the laying cost H(γ*, a(⋅) u*(⋅)) and total number of repairs G(γ*, u*(⋅)) are shown in Table I.

(119) TABLE-US-00002 TABLE I c (γ*, a(.Math.), u*(.Math.)) (γ*, u*(.Math.)) a 0 772.4504 46.6757 b 3.2 806.3512 31.3214 c 11 900.1517 20.9815 d 22 1082.1358 9.3630 e 45 1146.4565 6.1245 f 570 1200.7766 5.0165

(120) Table I shows the trade-off between the laying cost and the total number of repairs. In order to obtain the approximate Pareto front of the two objectives, the weighting value c may be varied from 0 to 900. As the weight value c increases, the laying cost also increases and total number of repairs decreases.

(121) From FIGS. 6A-6F, it is evident that the greater the laying cost, the less the total number of repairs. There are two means to reduce the total number of repairs, either by adding segments with protection (see the black lines in FIG. 6C), or by increasing the length of the cable to avoid the high risk areas shown by FIG. 6B. In FIG. 6A, the weight value c=0, so that only the laying cost is considered, and the cable tends to avoid the high slope areas but passes through the high PGV areas. With increasing weight value c, as shown by FIGS. 6B and 6C, the path of the cable is designed to keep away from the high PGV areas or add segments deployed in the high PGV areas with protection to reduce the total number of repairs.

(122) FIG. 7 is a graph showing non-dominated front for two objectives—total number of repairs and cable laying cost, obtained from FIGS. 6A-6F and Table I. It is shown that avoiding the high PGV regions and adopting a higher design level in high PGV regions are effective in reducing the total number of repairs.

(123) Advantage

(124) The method in the embodiment has provided a solution to address the problem of path and shielding level optimization for a cable connecting two points on Earth's surface while taking into account of high risk areas (including earthquake prone areas) as well as risk of ROV instability.

(125) Advantageously, the ROV stability risk has been incorporated in the laying cost to discourage the path from traversing areas with high slopes. By including the instability risk of ROV depending on the direction of the path and the slope of the terrain, the present invention is effective in minimizing the arrangement cost in laying an infrastructure link, for example, by reducing the likelihood of capsize of a ROV as it buries the cable in an uneven terrain.

(126) Using laying cost and total number of repairs of the cable as the two objectives, the problem is formulated as a multi-objective optimal control problem, and subsequently converted into a single objective optimal control problem by the weighted sum method. By applying DPP, a variant of the HJB equation was derived for the single objective optimal control problem. Ordered Upwind Method (OUM) is used to solve the HJB equation, and thereby produces high quality cable path solutions. The present invention obtained approximate Pareto fronts for the two objectives, the laying cost and the total number of repairs, and provides insight and guidance to design tradeoffs between cost effectiveness and seismic resilience.

(127) Exemplary System

(128) Referring to FIG. 8, there is shown a schematic diagram of an exemplary information handling system 1100 that can be used as a server or other information processing systems in one embodiment of the invention for performing the method in the invention. Preferably, the server 800 may have different configurations, and it generally comprises suitable components necessary to receive, store and execute appropriate computer instructions or codes. The main components of the server 800 are a processing unit 802 and a memory unit 804. The processing unit 802 is a processor such as a CPU, an MCU, etc. The memory unit 804 may include a volatile memory unit (such as RAM), a non-volatile unit (such as ROM, EPROM, EEPROM and flash memory) or both. Preferably, the server Boo further includes one or more input devices 806 such as a keyboard, a mouse, a stylus, a microphone, a tactile input device (e.g., touch sensitive screen) and a video input device (e.g., camera), The server 800 may further include one or more output devices 808 such as one or more displays, speakers, disk drives, and printers. The displays may be a liquid crystal display, a light emitting display or any other suitable display that may or may not be touch sensitive. The server 800 may further include one or more disk drives 812 which may encompass solid state drives, hard disk drives, optical drives and/or magnetic tape drives. A suitable operating system may be installed in the server 800, e.g., on the disk drive 812 or in the memory unit 804 of the server 800. The memory unit 804 and the disk drive 812 may be operated by the processing unit 802. The server 800 also preferably includes a communication module 810 for establishing one or more communication links (not shown) with one or more other computing devices such as a server, personal computers, terminals, wireless or handheld computing devices. The communication module 810 may be a modem, a Network Interface Card (NIC), an integrated network interface, a radio frequency transceiver, an optical port, an infrared port, a USB connection, or other interfaces. The communication links may be wired or wireless for communicating commands, instructions, information and/or data. Preferably, the processing unit 802, the memory unit 804, and optionally the input devices 806, the output devices 808, the communication module 810 and the disk drives 812 are connected with each other through a bus, a Peripheral Component Interconnect (PCI) such as PCI Express, a Universal Serial Bus (USB), and/or an optical bus structure. In one embodiment, some of these components may be connected through a network such as the Internet or a cloud computing network. A person skilled in the art would appreciate that the server 800 shown in FIG. 8 is merely exemplary, and that different servers 800 may have different configurations and still be applicable in the invention.

(129) Although not required, the embodiments described with reference to the Figures can be implemented as an application programming interface (API) or as a series of libraries for use by a developer or can be included within another software application, such as a terminal or personal computer operating system or a portable computing device operating system. Generally, as program modules include routines, programs, objects, components and data files assisting in the performance of particular functions, the skilled person will understand that the functionality of the software application may be distributed across a number of routines, objects or components to achieve the same functionality desired herein.

(130) It will also be appreciated that where the methods and systems of the invention are either wholly implemented by computing system or partly implemented by computing systems then any appropriate computing system architecture may be utilized. This will include stand-alone computers, network computers and dedicated hardware devices. Where the terms “computing system” and “computing device” are used, these terms are intended to cover any appropriate arrangement of computer hardware capable of implementing the function described.

(131) It will be appreciated by persons skilled in the art that numerous variations and/or modifications may be made to the invention as shown in the specific embodiments without departing from the spirit or scope of the invention as broadly described. For example, the method can be applied to determine optimal laying arrangement of any infrastructure link, including fluid pipeline (e.g., oil, water, and gas pipes), electric power cables, electric data cables, optical cables, etc. The present embodiments are to be considered in all respects as illustrative, not restrictive.