Reliability informed routing for Autonomous Sailing Craft Thomas Dickson James Blake Fluid Structure Interactions Fluid Structure Interactions B176, Boldrewood Campus, S016 7QF B176, Boldrewood Campus, S016 7QF thomas.dickson@soton.ac.uk J.I.R.Blake@soton.ac.uk David Sear Geography and Environment Highfield Campus, SO17 1BJ D.Sear@soton.ac.uk University of Southampton Abstract This paper introduces a novel method for modelling the influence of likely autonomous sailing craft failure conditions into the route plan- ning 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. Fu- ture work will involve gathering evidence on failure criteria in order to update the failure model. 1 Introduction 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 Copyright c by the paper’s authors. Copying permitted for private and academic purposes. In: S. M. Schillai, N. Townsend (eds.): Proceedings of the International Robotic Sailing Conference 2018, Southampton, United Kingdom, 31-08-2018 71 ROBOTIC SAILING 2018 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 (East- West, 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 (Schlaefer and Blaurock, 2011). (Schlaefer and Blaurock, 2011) presented analysis that used failure frequency to estimate the likelihood of completeing a voyage, although wasn’t able to relate this to the environmental conditions encountered. The East-West Microtransat route appears to be the most challenging route as participating ASCs fail earlier on this voyage relative to the other direction (Microtransat Challenge, 2018). Through modelling different failure modes within the routing algorithm it will be possible to understand why failure occurs earlier on the East-West route and to improve the design process. 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 (Auboin, L., Blake, J. I. R. and Turnock, 2010). A failure mode and effect analysis (FMEA) using fuzzy based failure modes was shown to be effectively applied to a yacht fire system design (Helvacioglu and Ozen, 2014). This paper demonstrated how it was possible to flexibly model expert opinion on the efficacy of a system through ranking hazards and then using fuzzy logic to model the influence of the lack of knowledge. 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 (Brito and Griffiths, 2016). Various different reliability engineering and design problems have been shown to be capably modelled using BBNs (Friis-Hansen, 2000). Given the lack of data on sailing craft design the flexibility to incorporate different failure mechanisms and sources of information mean that BBNs offer the most suitable framework to model the reliability of an ASC. The output of a BBN is a probability of some event occuring given a range of input factors which can be structural or environmental. 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 (Philpott and Mason, 2001). Different wind models (Philpott et al., 2004; Dalang et al., 2014) or race strategy and opponent models (Spenkuch, 2014; Tagliaferri and Viola, 2017) have been used to improve the accuracy of sailing routing models. The influence of different methods of modelling the ability for a sailing craft to sail upwind has been explored (Stelzer and Pröll, 2008) along with modelling the time taken to complete course changes (Ladany and Levi, 2017). The chief drawback of these methods is that they become unwieldy when applied to the long course route modelling problem. Full scale sailing craft race modelling has typically minimised either the time taken to complete a course (Ferretti and Festa, 2018), or the risk of losing to an opponent (Tagliaferri et al., 2014). To the authors knowledge, the consideration of reliability as a constraining factor in the sailing craft routing algorithm is a novel one. 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 Method 2.1 Voyage failure model The performance of the ASC can be specified in terms of its speed and failure mechanisms. The failure mech- anisms 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 72 Manoeuvre & Route Planning 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 (B|A)P (A) P (A|B) = (1) P (B) The failure model used in this paper relates two failure conditions based on the wave height and appar- ent 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 = voy- age 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 P (F = T, W D = T ) W H∈T,F P (F = T, W H, W D = T ) P (F = T |W D = T ) = = P (2) P (F = T ) W D,W H∈T,F P (W D, W H, F = T ) WD Criteria WD Criteria Pass Fail T F 0.1 0.9 F T 0.1 0.9 F F 1.0 0.0 T T 0.0 1.0 Table 1: Conditional probability table relating failure criteria combination to the probability of failure. 2.2 Route modelling The sailing craft routing algorithm used to identify the shortest path is the recursive dynamic program formu- lation introduced in (Philpott and Mason, 2001). The advantage of using the dynamic programming paradigm is that it is able to guarantee that the identified route is the best candidate of all possible routes in the domain, according to Bellmans principle of optimality (Bellman, 1957). The chief drawback is the large computational cost incurred through checking all possible solutions. 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 73 ROBOTIC SAILING 2018 Wave True wind True wind Wave height angle speed direction Sea con- Wind dition condition Probability of voyage failure Figure 2: The continuous domain between Figure 1: A Bayesian Belief Network to the start and finish is discretized into points model the relationship between environmen- as a function of the distance between each tal conditions and the probability of voyage point. failure. and j ∗ (i, t) is the successor of i on the optimal path when in state t. Γi is the set of all nodes on the graph. ( 0, i = nf inish f ∗ (i, t) = ∗ minj∈Γi [carc (i, j, t) + f (j, t + carc (i, j, t))], otherwise (3) ∗ ∗ j (i, j) = arg min[carc (i, j, t) + f (j, t + ca rc(i, j, t))], i 6= nf inish j∈Γi 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 . Weather conditions 3: pf ← BBN Failure(WHi , WDi , TWAi , TWSi , t) 4: if pf < apf then 5: V T = Distancecseg /VS (WHi , WDi , TWAi , TWSi ) 6: else 7: V T = inf 8: end if 9: end function 3 Application 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. 74 Manoeuvre & Route Planning 3.1 Solution accuracy 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 (Dhomè, 2017). The wind condition across the domain has been set at 15 knots from the North. This isolates the source of any variation in voyaging time to the variation in grid size. To quantify the discretization error the Grid Convergence Index (GCI) was calculated (Roache, 1997; Celik et al., 2008). The GCI index calculates the difference between the estimated result and the extrapolated result calculated as a function of the trend of the previous grid sizes. This index is often used in Computational Fluid Dynamics to calculate a 95% confidence region. As it has previously not been used to interpret routing algorithm results this index can only be used to guide the interpretation of whether the grid size used is fine enough for purpose. 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 2.55 Voyaging time (s) 2.54 2.53 2.52 104 104.2 104.4 104.6 104.8 105 Effective grid height (m) Figure 3: Grid discretization size study 3.2 Influence of failure model on routing time This section demonstrates the application of the novel reliability routing method using a control weather sce- nario. 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 75 ROBOTIC SAILING 2018 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. Figure 4: Shortest path avoiding Figure 5: Shortest path avoiding Figure 6: Shortest path avoiding any failures. two failures. one failure. 76 Manoeuvre & Route Planning 4 Conclusions 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 Future work 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 Acknowledgements 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. References Auboin, L., Blake, J. I. R. and Turnock, S. R. (2010). A fault tree based investigation of the reliability of ocean racing yachts incorporating human performance and canting keel impacts. In 2nd International Conference on Innovation in High Performance Sailing Yachts. Bellman, R. (1957). Dynamic Programming. Princeton University Press, Princeton, NJ, republishe edition. Brito, M. and Griffiths, G. (2016). A Bayesian approach for predicting risk of autonomous underwater vehicle loss during their missions. Reliability Engineering & System Safety, 146:55–67. 77 ROBOTIC SAILING 2018 Celik, I. B., Ghia, U., Roache, P. J., Freitas, C. J., Coleman, H., and Raad, P. E. (2008). Procedure for Estimation and Reporting of Uncertainty Due to Discretization in CFD Applications. Journal of Fluids Engineering, 130(7):078001. Dalang, R. C., Dumas, F., Sardy, S., Morgenthaler, S., and Vila, J. (2014). Stochastic optimization of sailing trajectories in an upwind regatta. Journal of the Operational Research Society, pages 1–15. Dhomè, U. (2017). Further development and performance evaluation of the autonomous sailing boat Maribot Vane. Technical report, KTH, Royal Institute of Technology 2017. Ferretti, R. and Festa, A. (2018). A Hybrid control approach to the route planning problem for sailing boats. http://arxiv.org/abs/1707.08103, pages 1–27. Friis-Hansen, A. (2000). Bayesian networks as a decision support tool in marine applications. Phd, Technical University of Denmark. Helvacioglu, S. and Ozen, E. (2014). Fuzzy based failure modes and effect analysis for yacht system design. Ladany, S. P. and Levi, O. (2017). Search for optimal sailing policy. European Journal of Operational Research, 260(1):222–231. Microtransat Challenge (2018). Microtransat Challenge. Philpott, A. and Mason, A. (2001). Optimising yacht routes under uncertainty. In Proc. of the 15th Chesapeake Sailing Yacht Symposium, Annapolis, MD, pages 1–8. Philpott, A. B., Henderson, S. G., and Teirney, D. (2004). A Simulation Model for Predicting Yacht Match Race Outcomes. Operations Research, 52(1):1–16. Roache, P. J. (1997). Quantification of Uncertainty in Computational Fluid Dynamics. Annual Review of Fluid Mechanics, 29(1):123–160. Schlaefer, A. and Blaurock, O. (2011). Route Planning for a Micro-transat Voyage. In Schlaefer, A. and Blaurock, O., editors, Robotic Sailing: Proceedings of the 4th International Robotic Sailing Conference. Springer. Spenkuch, T. B. (2014). A Bayesian Belief Network Approach for Modelling Tactical Decision-Making in a Multiple Yacht Race Simulator. PhD thesis, University of Southampton. Stelzer, R. and Pröll, T. (2008). Autonomous sailboat navigation for short course racing. Robotics and Au- tonomous Systems, 56(7):604–614. Tagliaferri, F., Philpott, A. B., Viola, I. M., and Flay, R. G. J. (2014). On risk attitude and optimal yacht racing tactics. Ocean Engineering, 90:149–154. Tagliaferri, F. and Viola, I. M. (2017). A real-time strategy-decision program for sailing yacht races. Ocean Engineering, 134(February):129–139. 78