This paper introduces a novel method for modelling the influence of likely autonomous sailing craft failure conditions into the route planning algorithm. The accuracy of the original route planning algorithm is quantified using numerical error estimation techniques. It was found that over the course of a Trans-Atlantic voyage a grid size of 36 km produced an error of ±2.1 hours over the course of a 703.25 hr voyage. The implementation of the failure model within the routing algorithm is verified using a control weather scenario. This verification is shown to be significant with respect to the method's numerical error. Future work will involve gathering evidence on failure criteria in order to update the failure model.
The Microtransat challenge is a competition undertaken by autonomous sailing craft (ASC) to complete an Atlantic crossing in the fastest time (Microtransat Challenge, 2018). To the authors knowledge, the Microtransat challenge has not been successfully completed as a consequence of competing vehicles failing before they complete the voyage. This paper seeks to address this problem through introducing a voyage failure model into a route planning algorithm, thereby identifying a route that manages the risk of failure. One use of this method is to assist with operational route planning with an existing craft. Another use could be to assist with the design process through modelling the influence of potential failure mechanisms.
Autonomous sailing craft are sailing robots which are designed to operate independently of human control or maintenance after their planned voyage has started. This independent operation requires that the reliability of the entire system must be extremely high. This reliability must be modelled based on the environmental conditions that are likely to be experienced. It is likely that through considering the reliability over the range of different environmental conditions experienced on a Trans-Atlantic voyage it will be possible to improve the likelihood of completing a voyage successfully.
The East-West Trans-Atlantic voyage between the Bay of Biscay and the Caribbean is one of the most travelled
maritime voyages in history. Consequently the common environmental conditions experienced are well known.
Research into the navigational challenges experienced for both directions of the MicroTransat competition
(EastWest, West-East) has identified that the only route that compares with the West-East leaves from the Canaries
and not the current start location of the MicroTransat challenge
Reliability engineering is the analysis of the different possible failure modes of an engineering artefact. Many
different methodologies exist to achieve this. A Fault Tree was used to model the different factors which may
cause a structural failure for a sailing craft
Bayesian belief networks (BBNs) have been used to model a complex network of empirical data and expert
opinion which calculated the probability of Autonomous Underwater Vehicle failure given a specific voyage
scenario
Sailing craft route planning uses environmental factors to determine the optimal route for a sailing craft to take
given its performance and the specific optimisation algorithm used. The most important environmental factor
considered is the wind vector, this can be generated using a wind model, reanalysis data or weather forecast.
The first research into solving the sailing craft route planning problem used a recursive dynamic programming
formulation which divided the domain into nodes over which the shortest path was calculated
The influence of different methods of modelling the ability for a sailing craft to sail upwind has been explored
This paper introduces a novel method for modelling the reliability of the sailing craft within the cost function used in the routing algorithm. This will allow the identification of routes which meet different sets of failure criteria. 2 2.1
The performance of the ASC can be specified in terms of its speed and failure mechanisms. The failure mechanisms may be estimated from structural analysis or empirical data on past failures. If no information exists then it is possible to specify different combination of environmental parameters which are likely to cause failure. Using these parameters it will be possible to avoid environmental conditions which are likely to cause failure.
Figure 1 illustrates an example of a BBN which relates environmental parameters describing the wind and the waves to the calculation of the probability of voyage failure. The top rank of nodes take the values of the environmental parameters as inputs. The middle rank accept the inputs and calculate the probability of craft failure if neither parameter will cause a failure, a single parameter causes failure or both will cause failure. It is possible to model three different failure levels in this manner, although due to the flexibility of the BBN it is possible to integrate different physical models into the calculation of failure probability.
Bayesian belief networks use Bayes rule, Equation 1, in order to relate the probability of a specific event occuring given that other events have already occured. P (A|B) is the probability of event A occuring given that event B is true, P (B|A) is the likelihood of B occuring given that A is true and P (A), P (B) are the likelihoods of A and B occuring independently of each other.
P (A|B) =
P (B|A)P (A)
P (B)
The failure model used in this paper relates two failure conditions based on the wave height and apparent direction to the probability of voyage failure. The joint probability distribution can be defined as being P (F, W D, W H) = P (F |W D, W H)P (W D)P (W H). The names of the model have been abbreviated as F = voyage failure (true/false), W D = apparent wave direction failure (true/false) and W H = wave height (true/false). Note that it is possible to use continuous distributions to model events rather than binary criteria.
If the criteria for the apparent wave direction failure are met then it is possible to calculate the likelihood of voyage failure using Equation 2. The weather conditions at a specific point determine whether the failure criteria are triggered. Table 1 defines the conditional probability table which enables the calculation of the probability of failure as a consequence of a single or either wave failure criteria being met. Note that it is possible to use continuous probability distributions within a BBN which would allow more realistic modelling of reliability.
P (F = T |W D = T ) =
P (F = T, W D = T )
P (F = T )
PW H∈T,F P (F = T, W H, W D = T ) = PW D,W H∈T,F P (W D, W H, F = T ) (1) (2)
T F T F T 0.1 0.1 1.0 0.0
0.9
0.9
0.0
1.0
The sailing craft routing algorithm used to identify the shortest path is the recursive dynamic program
formulation introduced in
To begin the process a great circle route is drawn between the start and finish location with the extents of the rectangular domain limited by the number of nodes in a rank and the distance between each node. The continuous domain is divided into discrete nodes as is illustrated in Figure 2. Each node is connected to all the nodes in the preceding and anteceding ranks to form a digraph connecting the start and the finish node.
For the position at any given node i the travel time between nodes i and a node on the next rank j along the arc (i, j) starting at time t is carc(i, j, t) = cseg(xi, xj , t). This function considers the wind speed and direction and course direction and calculates boat speed from known performance data. The wind speed and direction is a function of time and space and is retrieved from the wind scenario being used. cseg(xi, xj , t) is the time taken to sail the great circle joining location xi to location xj starting at time t.
The minimum time path is identified using a forward looking recursive algorithm which is described in Equation 3. f ∗(i, t) is the time taken for the optimal sequence of decisions from the node-time pair (i, t) to the finish node Wave height
Wave direction
True wind angle
True wind
speed Sea condition
Wind condition Probability of voyage failure minj∈Γi [carc(i, j, t) + f ∗(j, t + carc(i, j, t))], otherwise j∗(i, j) = arg min[carc(i, j, t) + f ∗(j, t + carc(i, j, t))], i 6= nfinish j∈Γi (3)
The failure model is introduced into the carc function, as shown in Algorithm 1. Extra variables such as the weather scenario and the acceptable probability of failure apf are introduced. VS is the speed for the particular set of weather conditions. If the failure model for a given segment at a given time exceeds a specified acceptable probability of failure then the time taken to complete the arc is set as infinite, otherwise the speed is interpolated from known performance data. When the shortest path is identified it naturally avoids these arcs and thus returns a route which is the minimum time route that meets the reliability requirement.
Algorithm 1 Cost function 1: function cseg( xi, xj , t, apf , Weather scenario) 2: WHi, WDi, TWAi, TWSi ← Weather scenario 3: pf ← BBN Failure(WHi, WDi, TWAi, TWSi, t) 4: if pf < apf then 5: V T = Distancecseg /VS (WHi, WDi, TWAi, TWSi)
7: V T = inf 8: end if
. Weather conditions 3
To verify whether the failure model is sensitive to the inclusion of failure the error generated as a result of the discretization of the domain must be calculated. The approach taken to calculate discretization error involves solving the shortest path for a control weather scenario over a range of grid sizes.
The simulation error estimated is used to inform the simulations used to demonstrate the efficacy of the failure model. In order to demonstrate the ability of the failure model, known weather conditions which trigger failure are modelled in the control weather scenario. Through specifying two different known failure conditions it will be possible to show whether and how the failure model informs the choice of route so as to avoid areas which will trigger failure. Code has been developed to support this analysis and a link is included in the acknowledgements. 3.1
The routing algorithm approximates the minimum voyaging time based on a discretization of a continuous
domain. Consequently there is an associated discretization error which must be quantified in order to give
credibility to the results. The route simulated is the East-West MicroTransat route using the performance of an
ASV, the Maribot Vane, to give context to the results. Although the Maribot Vane does not meet the rules of
the MicroTransat challenge it is a similar craft type has has experimentally validated performance data
To quantify the discretization error the Grid Convergence Index (GCI) was calculated
The grid size may be limited as soon as the voyaging time results have started to converge asymptotically as there will be little improvement in accuracy at the expense of large computational cost. Another limiting factor is the physical implication of the area enclosed in the cell, if the cell is too large it may not physically relate to the routing problem.
The results for routing simulations over a range of grid sizes can be seen in Figure 3. The control weather scenario used modelled the wind as being 15 knots from the North across the whole domain. The start location was 45o N and 12o W and the finish location was 17.5o N and 60.0 W. Relative to the scale of the simulation the error associated with a normalised grid height of 36327.16 is 0.298%, corresponding to ±2.1 hours. Over the course of route lasting roughly 870 hours an error of ±2.1 hours is acceptable.
·106 This section demonstrates the application of the novel reliability routing method using a control weather scenario. This weather scenario has been modified with patches of weather designed to activate the failure model. The control weather scenario encompasses the entire routing domain and has weather parameters which are independent of time. The simulations were run using a grid spacing of 36 km which corresponds to 160 nodes along a given edge, 25600 in total.
Two rectangular patches have been introduced into the domain with specific environmental conditions designed to trigger one and then both failure criteria. Area 2 is the larger patch with the co-ordinates ±5o about the central point at 40o W 33o N and has the wave height parameter set to 4m and is designed to provoke the single failure criteria. Area 1 has the wave direction set to 240 degrees, approximately the reciprocal bearing of the East-West Trans-Atlantic course and is a rectangular area with the points ±3o about the central point at 40o W 33o N. The combination of Areas 1 and 2 will provoke the double criteria failure model. The hypothesis is that without a failure model the shortest path will cross both areas, a double failure model will skirt Area 1 and the single failure model will skirt Area 2.
A challenge regarding the modelling of ASC failure is the lack of available data on their failure and potential failure modes, this is likely a consequence of the impracticality of their recovery on the event of voyage failure. A failure model is constructed using a BBN where the probability of failure is a consequence of different combination of environmental parameters being exceeded.
The failure model implemented has three discrete levels of failure. The initial level represents no failure criteria being exceeded, the second level represents a single failure criteria being exceeded and the final level represents routing despite any combination of failure criteria being exceeded. This model uses the structure of the BBN illustrated in Figure 1.
Two wave statistics are assumed to be significant with regards to causing the failure of an ASC, the wave direction and the wave height. For this control weather scenario the triggering failure criteria are when the wave height exceeds 4m and the apparent wave direction is under 60o. These parameters are selected in order to illustrate the ability for the BBN to avoid failure conditions rather than from any real performance data. Ship design uses mean wave height as part of the design process to estimate the motions that the ship will have to. Sailing directly into waves is known to be challenging, therefore it is useful to demonstrate an ability within the routing algorithm to avoid this occuring.
Three different simulations were run with the three different failure criteria. Figure 4 shows the shortest path where the failure model allows for two failure criteria to be met, it can be seen that the shortest path travels directly through both areas. The single failure criteria route avoids area 1 but travels through area 2, as shown in Figure 5. The double failure criteria route, shown in Figure 6, shows that the failure model is able to avoid both areas. The route takes 29 days and 7 hours ignoring any failure criteria, with the time taken increasing by 25 hours to avoid two failure criteria and by another 25 hours in order to avoid any failure criteria.
The results illustrated in Figures 4 to 6 illustrate the ability for the routing algorithm to avoid areas where the failure model calculates a probability which is unacceptable. Each routing result differs by an amount significantly over 2.1 hours, the estimated accuracy of the original routing algorithm, indicating that the variation in result is due to the failure model. 4
Autonomous sailing craft competing the MicroTransat competition have suffered some form of critical failure before they have been able to finish. To model this problem this paper has introduced a novel methodology by introducing a failure model within the sailing craft routing algorithm. In order to demonstrate the impact of the routing model the accuracy of the routing algorithm needed to be quantified.
Routing algorithms are generally based on a discretization of a continuous domain that results in an error. This error is reduced as the accuracy of the discretization process is increased but increases the computational cost of running the simulation. The error was calculated using the grid convergence index, a parameter borrowed from the discipline of Computational Fluid Dynamics and measures the difference between the simulated result and the actual result inferred based of a trend of previous results. The grid convergence index was calculated for a series of routing simulations which were solved for a range of different grid sizes. A balance between computational run time and accuracy was achieved through using an effective grid height of 36 km to discretize the domain. This corresponds to an error of ±2.1 hours over a voyage lasting 703.25 hours.
A failure model has been implemented that is able to model two levels of failure, thereby demonstrating the flexibility of the Bayesian Belief network with regards to modelling different combinations of failure causes. The levels of failure modelled are a function of the mean wave height and direction. This has modelled the difficulty for sailing craft to maintain a course when either sailing in heavy seas or sailing into the wave direction.
To demonstrate the ability of the failure model to avoid areas which exceed a specified probability of failure, simulations varying the probability of failure were conducted with a control weather scenario. In the centre of the domain two patches of failure-inducing weather were placed. The failure model routing algorithm was able to avoid these failure inducing patches according to different acceptable levels of failure. To the authors knowledge this is the first calculation and application of discretization error in the interpretation of routing algorithm simulation results. 4.1
Integrating empirical or modelled autonomous sailing craft failure data into the failure model would allow realistic route modelling to take place. This will involve collaboration with designers and users who have been able to model or record specific failure modes and their causes and to incoporate this information into an improved failure model. As the failure model has demonstrated an ability to avoid areas of risk, one extentsion could be to input the locations of common fishing areas, as a common cause of ASC failure is being caught by fishing vessels (Microtransat Challenge, 2018).
The routing algorithm does not account for the time cost associated with tacking or gybing. It is noted that the time taken for an ASV to recover speed is small with respect to the overall time of voyaging, however as the accuracy of the routing has been quantified it is now possible to test whether a significant difference is achieved through including such a manouevre model.
Another avenue of research could be into the use of Genetic Algorithms or Monte Carlo Tree Search method for the purpose of accelerating the solution optimisation time. 4.1.1
Thanks must go to the University of Southampton Sailing Robot team for their support and encouragement.
The code developed to produce the simulations in this report has been developed under the MIT licence and can be found online at https://github.com/TAJD/pyroute.
Helvacioglu, S. and Ozen, E. (2014). Fuzzy based failure modes and effect analysis for yacht system design.