- Email: [email protected]

ScienceDirect IFAC-PapersOnLine 49-23 (2016) 121–126

Efficient Path Planning Algorithms Efficient Efficient Path Path Planning Planning Algorithms Algorithms Unmanned Surface Vehicle Unmanned Surface Unmanned Surface Vehicle Vehicle

for for for

Hanlin Niu, Yu Lu∗∗ , Al Savvaris, Antonios Tsourdos Hanlin Hanlin Niu, Niu, Yu Yu Lu Lu∗∗ ,,, Al Al Savvaris, Savvaris, Antonios Antonios Tsourdos Tsourdos Hanlin Niu, Yu Lu Al Savvaris, Antonios Tsourdos School of Aerospace, Transport and Manufacturing, Cranfield School of Aerospace, Aerospace, Transport Transport and and Manufacturing, Manufacturing, Cranfield Cranfield School University,Transport Cranfield,and United Kingdom Cranfield School of of Aerospace, Manufacturing, University, Cranfield, United Kingdom ∗ University, United [email protected] University, Cranfield, United Kingdom Kingdom ∗ Email:Cranfield, ∗ ∗ Email: Email: [email protected] [email protected] Email: [email protected] Abstract: The C-Enduro Unmanned Surface Vehicle (USV) is designed to operate at sea for Abstract: The Unmanned Surface Vehicle (USV) is to at sea Abstract: The C-Enduro C-Enduro Unmanned Surface Vehicle the (USV) is designed designed to operate operate atUSV, sea for for extended periods of time (up to 3 months). To increase endurance capability of theat an Abstract: The C-Enduro Unmanned Surface Vehicle (USV) is designed to operate sea for extended periods of time (up to 3 months). To increase the endurance capability of the USV, extended periodspath of time time (up to toalgorithm 3 months). months).isTo To increase the the endurance capability of the thealgorithm USV, an an energy efficient planning developed. Theendurance proposed capability path planning extended periods of (up 3 increase of USV, an energy efficient path planning algorithm is developed. The proposed path planning algorithm energy efficient path developed. The path algorithm integrates the Voronoi diagram,algorithm Visibilityis search algorithm and takes also energy efficient path planning planning algorithm isalgorithm, developed.Dijkstra The proposed proposed path planning planning algorithm integrates the Voronoi diagram, Visibility algorithm, Dijkstra search algorithm and takes also integrates the Voronoi diagram, Visibility algorithm, Dijkstra search algorithm and takes into account the sea current data. Ten USV simulated mission scenarios at different time of also day integrates the Voronoi diagram, Visibility algorithm, Dijkstra search algorithm and takes also into account sea data. USV simulated mission scenarios at different time of into account the the sea current current data. Ten TenThe USV simulated missionshows scenarios atthe different time of day day and start/end points were analysed. proposed approach thatat amount of energy into account the sea current data. Ten USV simulated mission scenarios different time of day and start/end points were analysed. The proposed approach shows that the amount energy and start/end points wereMoreover, analysed.the The proposed approachcan shows that to thecalculate amount aof ofcollision energy savedstart/end can be up to 21%. proposed algorithm be used and points were analysed. The proposed approach shows that the amount of energy saved can be up to 21%. Moreover, the proposed algorithm can be used to calculate a collision saved can be up to 21%. Moreover, can be used calculate aa collision free and energy efficient path to keepthe theproposed USV safealgorithm and improve the USVto capability. The safety saved can be up to 21%. Moreover, the proposed algorithm can be used to calculate collision free and energy efficient path to keep the USV safe and improve the USV capability. The safety free and energy path to keep the USV safe and the USV The safety distance betweenefficient the USV and the coastline can also beimprove configured by thecapability. user. free and energy efficient path to keep the USV safe and improve the USV capability. The safety distance distance between between the the USV USV and and the the coastline coastline can can also also be be configured configured by by the the user. user. distance between the USV and the coastline can also be configured by the user. © 2016, IFAC (International Federation of Automatic Control) Hosting by Elsevier Ltd. All rights reserved. Keywords: unmanned surface vehicles; collision avoidance; Voronoi diagram; Visibility graph; Keywords: unmanned Keywords: unmanned surface surface vehicles; vehicles; collision collision avoidance; avoidance; Voronoi Voronoi diagram; diagram; Visibility Visibility graph; graph; path planning Keywords: unmanned surface vehicles; collision avoidance; Voronoi diagram; Visibility graph; path planning path planning planning path 1. ASV VEHICLE DESCRIPTION Table 1. Technical specification of the C1. Table 1. 1. Technical specification specification of of the the C1. ASV ASV VEHICLE VEHICLE DESCRIPTION DESCRIPTION Table Enduro USV. 1. ASV VEHICLE DESCRIPTION Table 1. Technical Technical specification of the CCEnduro USV. Enduro Enduro USV. USV. The C-Enduro USV was developed under a UK GovernmentThe C-Enduro USV developed under UK Physical Specification The C-Enduro USV was wasResearch developed under a UK GovernmentGovernmentbacked Small Business Initiative (SBRI) initiated The C-Enduro USV was developed under aa(SBRI) UK GovernmentPhysical Specification backed Small Business Research Initiative initiated Physical Specification Physical Specification backed Small Business Research Initiative Initiative by the Small National Oceanography Centres (SBRI) (NOC) initiated requirelength 4.2 m backed Business Research (SBRI) initiated by the National Oceanography Centres (NOC) requirelength 4.2 m 2.4m transportable) beam by the National Oceanography Centres (NOC) requirelength 4.2 m ment forNational long endurance USVs forCentres environmental research. by the Oceanography (NOC) requirelength 4.2 m(road 2.4m (road transportable) beam ment for long endurance USVs for environmental research. 2.8m (including antenna) 2.4m (road transportable) beam ment for long endurance USVs for environmental research. The team behind the C-Enduro, led by ASV, includes 2.4m (road transportable) beam ment for long endurance USVs for environmental research. height 2.8m (including antenna) The team the C-Enduro, led ASV, includes 1.5m (mast off ) antenna) 2.8m (including height 2.8m (including The team behind behind the C-Enduro,motor led by by ASV,and includes Hyperdrive Ltd whothe investigated options power The team behind C-Enduro, led by ASV, includes height 1.5m (mast off ) antenna) height Hyperdrive Ltd who investigated motor options and power draft 0.4m (mast 1.5m (mast off off )) 1.5m Hyperdrive Ltd who investigated investigated motor options and and power managementLtd systems and Cranfield University whopower have Hyperdrive who motor options draft 0.4m weight 350kg (lightship) draft 0.4m management systems and Cranfield University who have draft 0.4m management systems and Cranfield University who have conducted research into various guidance algorithms for weight 350kg (lightship) management systemsinto andvarious Cranfield University who have primary 2 DC brushless weight propulsion 350kg (lightship)motors conducted research guidance algorithms for weight 350kg (lightship) conducted research into various guidance algorithms for primary propulsion 2 DC brushless motors USVs (Savvaris et al. (2014); Niuguidance et al. (2016); Lu et for al. conducted research into various algorithms primary propulsion 2 primary propulsion 2 DC DC brushless brushless motors motors USVs (Savvaris et al. (2014); Niu et al. (2016); Lu et al. USVs (Savvaris et al. al. (2014); Niu etdeveloped al. (2016); (2016);C-Enduro Lu et et al. al. (2016)). In Figure 1, (2014); we showNiu theet USVs (Savvaris et al. Lu command and control systems packaged in a rugged self(2016)). In Figure 1, we show the developed C-Enduro command and control systems packaged in self(2016)). In marine Figure 1, unmanned surface vehiclethe at developed sea during C-Enduro sea trials. righting (2016)). In Figure surface 1, we we show show the developed C-Enduro command and control control systems packaged in aaa rugged rugged selfvehicle, provides the greatest likelihood of meeting command and systems packaged in rugged selfunmanned marine vehicle at sea during sea trials. righting vehicle, provides the greatest likelihood of meeting unmanned marine surface vehicle at sea during sea trials. unmanned marine surface vehicle at sea during sea trials. righting vehicle, provides the greatest likelihood meeting the performance requirement. In Table 1, we of show the righting vehicle, provides the greatest likelihood of meeting the performance requirement. In Table 1, we show the the performance Table 1, we show the physical technical requirement. specification ofIn the vessel, while in Table the performance requirement. In Table 1, we show the physical technical specification of the vessel, while in Table technical specificationofof ofthe thewind vessel, while in in Table Table 2physical the technical specifications generator, diesel physical technical specification the vessel, while 22 the technical specifications of the wind generator, diesel the technical technical specifications ofare thegiven. wind generator, generator, diesel diesel and the solar panelof 2generator the specifications the wind generator and the solar panel are given. generator and the solar panel are given. generator and the solar panel are given. In terms of the power system hardware, the C-Enduro In terms of the power system hardware, the C-Enduro In terms of the system the USV meets long endurance characteristics and reIn terms of the the power power system hardware, hardware, the C-Enduro C-Enduro USV meets long endurance characteristics and reUSV meets the long and quirements required toendurance accomplishcharacteristics its mission. However, USV meets the long endurance characteristics and rerequirements required to accomplish its mission. However, quirements required to accomplish mission. to further improve the endurance its capacity anHowever, efficient quirements required to accomplish its mission. However, to improve the endurance capacity an to further further improve therequired. endurance capacity an efficient efficient path planning is also Since the C-Enduro is to further improve the endurance capacity an efficient path planning is also required. Since the C-Enduro is path planning is also required. Since the C-Enduro is designed to travel long distances and operate in various sea path planning is also required. Since the C-Enduro is designed to travel long distances and operate in various sea designed to travel long distances and operate in various sea and weather conditions, the efficient path planning plays designed to travel long distances and operate in various sea and weather the path plays andimportant weather conditions, conditions, the efficient efficientsuccessful path planning planning plays an role in accomplishing operations. and weather conditions, the efficient path planning plays an important role in accomplishing successful operations. an important important role in in aaccomplishing accomplishing successful operations. This paper presents new energy efficient path planning an role successful operations. This paper presents aa new energy efficient path planning This paper energy efficient path method thatpresents integrates Voronoi algoThis paper presents a new new energydiagram, efficientVisibility path planning planning method that integrates Voronoi diagram, Visibility algomethod that integrates Voronoi diagram, Visibility algorithm, Dijkstra search algorithm and energy consumption method that integrates Voronoi diagram, Visibility algorithm, Dijkstra search algorithm and energy consumption rithm, Dijkstra Dijkstra search algorithm and energy consumption weight. The energy efficiency of and the energy proposed algorithm rithm, search algorithm consumption Fig. 1. The C-Enduro Unmanned Surface Vehicle . weight. The energy of weight. The energyinefficiency efficiency of the the proposed proposed algorithm algorithm Fig. 1. 1. The C-Enduro C-Enduro Unmanned Surface Surface Vehicle .. has beenThe validated 10 USV missions. weight. energy efficiency of the proposed algorithm Fig. has been validated in 10 USV missions. Fig. 1. The The C-Enduro Unmanned Unmanned Surface Vehicle Vehicle . has been validated in 10 USV missions. has been validated in 10 USV missions. To improve long endurance capability, the C-Enduro veTo improve improve long long endurance endurance capability, capability, the the C-Enduro C-Enduro veve2. PATH PLANNING LITERATURE REVIEW To hicleimprove has a ”three pillar” energy system including solar To long endurance capability, theincluding C-Endurosolar ve2. hicle has a ”three pillar” energy system 2. PATH PATH PLANNING PLANNING LITERATURE LITERATURE REVIEW REVIEW hicle has ”three pillar” energy system including solar 2. PATH PLANNING LITERATURE REVIEW panels, a aawind generator and a diesel generator. Calcuhicle has ”three pillar” energy system including solar panels, a wind generator and a diesel generator. Calcupanels, wind generator and aa diesel generator. Calculations aaand tests show that this ”three pillar” energy Depending on the environment, four different path planpanels, wind generator and diesel generator. Calculations and and tests tests show show that that this this ”three ”three pillar” pillar” energy energy Depending on the environment, four different path planlations on four path system, and combined with efficient power management and Depending ning methods can environment, be used: roadmap-based lations tests show that this ”three pillar” energy Depending on the the environment, four different differentapproaches, path planplansystem, combined with efficient power management and ning methods can be used: roadmap-based approaches, system, system, combined combined with with efficient efficient power power management management and and ning ning methods methods can can be be used: used: roadmap-based roadmap-based approaches, approaches, Copyright © 2016, 2016 IFAC 121Hosting by Elsevier Ltd. All rights reserved. 2405-8963 © IFAC (International Federation of Automatic Control) Copyright 2016 responsibility IFAC 121Control. Peer review© of International Federation of Automatic Copyright © 2016 121 Copyright ©under 2016 IFAC IFAC 121 10.1016/j.ifacol.2016.10.331

2016 IFAC CAMS 122 Sept 13-16, 2016. Trondheim, Norway

Hanlin Niu et al. / IFAC-PapersOnLine 49-23 (2016) 121–126

Table 2. Power and Controls Technical Specification Power and controls

Specification

endurance solar panel system diesel generator system wind turbine system

Up to 3 months utilising solar/wind/diesel energy Generating a peak electrical power of 1200W Providing a peak charging power of 2.5kW Lightweight three blade system generating a peak output power of 720W

cell decomposition, potential fields, and bug algorithms. The goal of roadmap based approaches is to reduce the N-dimensional configuration space to a set of onedimensional paths, which are then searched. Two famous roadmap-based approaches are the visibility graph and the Voronoi diagram (Wein et al. (2007)). The efficiency of using visibility graphs for determining the shortest path ¯ et al. (2011), whereas the was demonstrated by Kaluder use of Voronoi diagrams for USV dynamic path planning was presented in the work of Wu et al. (2013). The advantage of Voronoi diagrams is the short computing time, although the disadvantages include the non-optimal nature of the Voronoi road map and the redundant waypoints. The advantage of the Visibility algorithm is that it can generate an optimal path, although a disadvantage is the increased computing time compared with that of the Voronoi diagram. Another planning method is cell decomposition approach, such as A∗ algorithm, and the approach could be either exact or approximate. It is used by Li et al. (2011) for UAV path planning. The application of A∗ for an USV that must avoid underwater obstacles was tested experimentally by Phanthong et al. (2014). The potential field method is another widely used planning method because the computational load required to generate the trajectory is small. In general, the trajectory can be generated in real-time and planning and control are merged into one function. Planning the potential field path can be coupled directly to a control algorithm. However, the approach may become trapped in local minima in the potential field (Koren and Borenstein (1991)). Due to this limitation, it has been mainly used for local path planning. Finally, bug algorithm is a limited-knowledge path planning approach. It assume only local knowledge of the environment and a global goal. Its efficiency for robot path planning using a range sensor was presented by Buniyamin et al. (2011), while its use for obstacle avoidance was presented by Loe (2008). Path planning under environmental disturbances and uncertainties are inevitable in USV path planning. Thus, ocean environmental effects should be properly considered in path planning on the ocean surface so as to achieve less energy consumption. Too little research has concerned this issue in their path planning approaches (Liu et al. (2016)). Generating energy-efficient paths presents new challenges for USV path planning, as it requires not only novel and realistic energy cost functions, but also powerful computational approaches due to the inherent problem complexity. 3. ENVIRONMENTAL DATASETS The traditional path planning method for the marine vehicles is either heading to the destination directly or 122

taking the shortest route, without taking into account the current data. The proposed path planning algorithm improves the USV endurance capability by analysing the sea current data. The development in ocean science and satellite remote sensing technology meant that ocean currents states can be predicted more accurately. The data used in this investigation is from TideTech Ltd. The sea current data is compiled in grib files. Grib file is a concise data format used to store historical and forecast weather data. The advantage of using the TideTech data is that we can get the forecast of the sea current and can therefore use this information to optimise the path before the C-Enduro USV starts its mission. The resolution of Singapore strait is 800 meters; The update time step is 1 hour. The forecast length is 48 hours. See TideTech Ltd. (2015). The coastline data was obtained from NCAR Research Data Archive. The coastline data used in this paper is of high resolution that consists of points about 200m apart. 4. EFFICIENT PATH PLANNING ALGORITHM The proposed efficient path planning algorithm consists of five parts: Voronoi diagram, USV energy consumption model implementation, Dijkstra search, Visibility algorithm and Dijkstra search. The advantage of using the Voronoi diagram rather than other methods, among which the Visibility Graph prevails, is its computing efficiency. The Voronoi diagram can be calculated out in O(nlog(n)) time, whereas the Visibility graph can take up to O(n2 ) time. However, the Voronoi road map is far from optimal. Although Visibility algorithm computing time is longer, its path is optimal. Therefore, in this paper the Voronoi diagram and the Visibility algorithm are integrated to calculate the optimal path in O(nlog(n)) time. The Voronoi diagram is first implemented to provide the USV collision free road map. USV energy consumption model provides the method to calculate the USV energy consumption weight under different sea current state. The Dijkstra search is implemented to generate the Voronoi energy efficient path. However, the path is not optimal and includes redundant waypoints. Therefore, the Visibility algorithm is applied to optimise the Voronoi energy efficient path. Finally, the Dijkstra search is used again to calculate out the Visibility-Voronoi energy efficient path. 4.1 Voronoi diagram implementation The first step of Voronoi diagram generation is to expand the coastline of each island. The expanded coastlines will keep the shape of the original coastline and the distance r meters between the original coastline and the expanded

2016 IFAC CAMS Sept 13-16, 2016. Trondheim, Norway

Hanlin Niu et al. / IFAC-PapersOnLine 49-23 (2016) 121–126

coastline can be configured by the users, which means the USV will be always kept r meters away from the islands coastlines. The reason to expand the island coastline is to keep the USV absolutely clear from the islands in the existing of uncertainty of the map data.

123

efficiency has been proven in many work about path planning published by other researchers. To find out the path that requires the minimum energy, the cost weight between the adjacent waypoints in needs to be calculated and filled into the waypoint sparse matrix M . By implementing Dijkstra’s algorithm, the energy efficient path is generated in Fig. 3.

Fig. 2. Croatia islands Voronoi road map. Then the Voronoi diagram can be calculated by processing the expanded islands coastline data using the voronin function in Matlab. The Voronoi road map of the processed islands of the coast of Croatia are shown in Fig. 2. The generated road paths that have intersections with the island coastlines were moved away. Furthermore, the roads path generated inside the island coastlines were also removed. All the road paths that were kept are collision free paths. In Fig. 2, the red districts represent the expanded islands coastlines and the blue lines represent all the potential road paths. The Voronoi vertices and path information are stored into a waypoint sparse matrix M . 4.2 USV energy consumption model For an USV that is commanded to travel from waypoint Ni to waypoint Ni+1 , the ground speed of the USV is → → denoted by − vg , the sea current speed is denoted by − vc , and − → the relative USV speed is denoted by vu . The parameters satisfy the following equation: → → − vc + − v→ (1) vg = − u The hydrodynamic drag Fd can be calculated by the following equation: equation: Fd = α|vu |2 (2) where α represents a USV constant drag parameters. The USV energy consumption weight E can be calculated by the following equation: |Ni Ni+1 | |Ni Ni+1 | = α|vu |3 · (3) E = |vu | · α|vu |2 · |vg | |vg | Therefore, when the USV path and the sea current data are given and the ground velocity of the USV is constant, the energy consumption weight of the path can be calculated. 4.3 Dijkstra search Dijkstra’s algorithm is an algorithm for finding paths that have the minimum weight between nodes in a graph. Its 123

Fig. 3. Voronoi energy efficient path. The USV is commanded to travel from location (14.45, 45.20) to location (14.50, 44.10). The map data is generated from high resolution coastline data made up of 115 islands off the coast of Croatia. The nearest nodes to the start point and the destination are calculated first. By processing the waypoint sparse matrix M , Dijkstra search generates the path that needs the minimum energy weight between the start point and the destination in the Voronoi road map. The green path in Fig. 3 represents the Voronoi energy efficient path from start point to the destination. The Voronoi road map is constructed in around 7 seconds using the Matlab simulation software. By contrast, when implementing the Visibility algorithm to generate the road map, more than 10 minutes is needed. As can be seen, the Voronoi diagram is computing efficiently. However, the green path is far from optimal due to the existing redundant nodes. Therefore, the Visibility algorithm will be implemented later to optimise the path. 4.4 Visibility algorithm As the energy efficient path generated from Voronoi diagram is not optimal, Visibility algorithm is implemented. Assuming the generated energy efficient path allows the USV to travel from waypoint Ni to waypoint Ni+2 via waypoint Ni+1 . The implementation of Visibility algorithm is to provide more possible paths. If the path from waypoint Ni to waypoint Ni+2 does not cross any islands, the path Ni − Ni+2 will be added. By processing the generated Voronoi efficient path using Visibility algorithm, more available paths will be generated and Dijkstra search algorithm will be used again to calculate the most efficient path among these possible paths.

2016 IFAC CAMS 124 Sept 13-16, 2016. Trondheim, Norway

Hanlin Niu et al. / IFAC-PapersOnLine 49-23 (2016) 121–126

Fig. 6. Voronoi energy efficient path based on the sea current data at 2:00 hours on the 11th June 2014.

Fig. 4. Visibility algorithm demonstration.

Fig. 5. Energy efficient path based on the simulated conditions at 12:00 hours on 14th June 2014. 4.5 Dijkstra search

Fig. 7. Voronoi shortest path generated based on the distance weight.

By implementing Dijkstra’s algorithm, the VisibilityVoronoi energy efficient path is calculated out, as shown in Fig. 5. The green path is the generated energy efficient path. The sea current state is also denoted by blue arrow in the figure. The simulated time was at 12:00am on 14/06/2014. 5. SIMULATION RESULT In the simulation, the USV was commanded to travel from location (103.68, 1.30) to location (103.90, 1.08). The simulation area used this time was the Singapore strait. The simulation time was at 2:00am on 11/06/2014. It was assumed that the sea current was time-invariant when the USV was travelling. The reference sea current data was measured at 2:00am on 11/06/2014. The USV commanded ground speed was 1 m/s. In Fig. 6, the green path represents the Voronoi energy efficient path. By changing the Voronoi path weight from the energy consumption weight to the distance weight and implementing Dijkstra’s algorithm, the new Voronoi shortest path is generated as shown in Fig. 7. It can be seen that the efficient path and the shortest path are obviously different. 124

Fig. 8. The Visibility-Voronoi energy efficient path. By implementing Visibility algorithm and Dijkstra’s search algorithm, the Visibility-Voronoi efficient path is shown in Fig. 8. The Visibility-Voronoi shortest path is shown in Fig. 9. It can be inferred that Visibility algorithm has optimised both the Voronoi energy efficient path and the Voronoi shortest path. Moreover, the paths are free

2016 IFAC CAMS Sept 13-16, 2016. Trondheim, Norway

Hanlin Niu et al. / IFAC-PapersOnLine 49-23 (2016) 121–126

Fig. 9. The Visibility-Voronoi shortest path.

125

Fig. 11. The Visibility-Voronoi energy efficient path.

from obstacles, which confirms the validity of the Voronoi diagram approach.

Fig. 12. Efficient paths at two different times w.r.t. shortest path. Fig. 10. Sea current state. By analysing the sea current state as shown in Fig. 10, it can be seen that the path generated in Fig. 8 is keeping the USV away from going into the opposite direction to the sea current, which is the aim in that case to avoid the increase in energy consumption. However, the path in Fig. 9 just takes the distance into account instead of the energy and the aim in this case is just to find the shorted path. The simulation’s power consumption records reveal that the VV efficient path has an energy cost of 0.3514α, whereas the VV shortest path has an energy cost of 0.4133α. Thus, the efficient path uses up to 14.98% less energy. Then, the proposed algorithm was also simulated in a different time of day to see the impact of time on planning the efficient path. The previous simulation time is at 2:00 am on 11/06/2014. This time, the simulation time is at 5:00 am on 11/06/2014. The total energy consumption of the efficient path is 0.3549α, whereas that of the shortest path is 0.4256α. Therefore, the VV efficient path conserves approximately 16.61% energy. The data in Figure 8, Figure 9 and Figure 11 are combined in Figure 12 to show the results of the proposed efficient path planning algorithm and the shortest paths at different times on the same day. 125

In Figure 12, the solid blue path represents the shortest path, the dashed line represents the efficient path at 5:00 am on 11/06/2014, and the path with dashes and circles represents the efficient path generated at 2:00 am on 11/06/2014. To increase the confidence level in the results and demonstrate the efficiency of the proposed efficient path planning algorithm, ten USV missions were simulated on 11/06/2014, and the results are shown in Table 3. The USV speed is set to 1 m/s. The variables of the missions include the starting point, destination and mission time; therefore, the sea current conditions are guaranteed to vary. The total energy consumption of the proposed efficient path planning algorithm was compared with the VV shortest path, and the energy savings were calculated and tabulated in the last column of Table 3. Table 3 shows that using the VV energy-efficient path can save 5.22% to 21.43% in energy compared with the Voronoi shortest path. The segment showing the highest amount of saved energy at approximately 21.4% had a start point at location (103.95, 1.20) and an endpoint at location (103.75, 1.08) at 0:00 am on 11/06/2014. The segment showing the lowest amount of saved energy at approximately 5.22% had a start point at location (103.74, 1.30) and an endpoint at location (103.8, 1.08) at 0:00 am on 11/06/2014.

2016 IFAC CAMS 126 13-16, 2016. Trondheim, Norway Sept

Hanlin Niu et al. / IFAC-PapersOnLine 49-23 (2016) 121–126

Table 3. Result of 10 USV missions. No

Start point

Destination

Mission time

1 2 3 4 5 6 7 8 9 10

(103.68, (103.68, (103.68, (103.68, (103.68, (103.74, (103.95, (103.95, (103.68, (103.68,

(103.90, (103.90, (103.90, (103.90, (103.90, (103.80, (103.75, (103.65, (103.90, (103.90,

00:00 01:00 02:00 03:00 04:00 00:00 00:00 00:00 00:00 02:00

1.30) 1.30) 1.30) 1.30) 1.30) 1.30) 1.20) 1.15) 1.30) 1.30)

1.08) 1.08 1.08) 1.08) 1.08) 1.08) 1.08) 1.25) 1.08) 1.08)

Efficient path length (km)

Shortest path length (km)

Efficient path energy

Shortest path energy

Energy saved

38.132 38.631 38.926 37.713 37.785 26.990 28.607 43.225 38.132 38.926

36.043 36.043 36.043 36.043 36.043 24.566 27.922 39.037 36.043 36.043

0.3415α 0.3494α 0.3514α 0.3324α 0.3394α 0.2195α 0.1362α 0.2678α 0.3415α 0.3514α

0.3856α 0.4080α 0.4133α 0.4064α 0.4086α 0.2316α 0.1734α 0.3249α 0.3856α 0.4133α

11.44% 14.37% 14.98% 18.22% 16.94% 5.22% 21.43% 17.57% 11.44% 14.99%

a.m. a.m. a.m. a.m. a.m. a.m. a.m. a.m. a.m. a.m.

The reason for the energy saving amount difference of these 10 missions is that when the sea current direction changes a lot with the locations change, the energy efficient path will be very different with the shortest path and the energy efficient path will save a lot amount of energy comparing to the shortest path. By contrast, if the sea current is uncorrelated with the locations, the energy current path will be the same with the shortest path. 6. CONCLUSION AND FUTURE WORK In this paper, the Voronoi diagram, Visibility algorithm and Dijkstra’s search algorithms were integrated to calculate the energy efficient path. The proposed efficient path planning algorithm not only provide collision free path, but also takes into account the sea current influence on the USV energy consumption. Ten USV missions were simulated. The results show that the amount of energy saved depends on the locations and the mission time. When the sea current state is uncorrelated with the locations, the difference in the energy consumption will be small. When the sea current state changes a lot with the location changing, the difference in energy consumption between the efficient path planning algorithm and the Visibility-Voronoi shortest algorithm will be high. In general, the proposed algorithm can be used to calculate a collision free and energy efficient path to keep the USV safe and improve the USV endurance capability. The safety distance r between the USV and the coastline can also be configured by the users, and the generated path always keeps the USV distance r away from the coastlines. For the future work, the efficient path planning algorithm will also take into account the solar energy and the wind energy generation to maximise the endurance and energy production of the USV. This is important, since the energy consumption is not only linked to the thrusters but also depend on the payload. Some equipment for example, the winch when operated will result in an increase in the amount of power consumed and will have to be taken into account. REFERENCES Buniyamin, N., Ngah, W.W., Sariff, N., and Mohamad, Z. (2011). A Simple Local Path Planning Algorithm for Autonomous Mobile Robots. International Journal of Systems Applications, Engineering & Development, 2(5), 151–159. 126

¯ Kaluder, H., Brezak, M., and Petrovi´c, I. (2011). A visibility graph based method for path planning in dynamic environments. In Proceedings of the 34th International Convention on Information and Communication Technology, Electronics and Microelectronics (MIPRO 2011), 717–721. IEEE. Koren, Y. and Borenstein, J. (1991). Potential Field Methods and Their Inherent Limitations for Mobile Robot Navigation. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA 1991), volume 2, 1398–1404. IEEE. Li, Y., Chen, H., Er, M.J., and Wang, X. (2011). Coverage path planning for uavs based on enhanced exact cellular decomposition method. Mechatronics, 21(5), 876–885. Liu, Z., Zhang, Y., Yu, X., and Yuan, C. (2016). Unmanned surface vehicles: An overview of developments and challenges. Annual Reviews in Control. doi: 10.1016/j.arcontrol.2016.04.018. Loe, O.A.G. (2008). Collision Avoidance for Unmanned Surface Vehicles. Master’s thesis, NTNU. Lu, Y., Niu, H., Savvaris, A., and Tsourdos, A. (2016). Verifying Collision Avoidance Behaviours for Unmanned Surface Vehicles using Probabilistic Model Checking. In Proceedings of 10th IFAC Conference on Control Applications in Marine Systems (CAMS 2016). IFAC. Niu, H., Lu, Y., Savvaris, A., and Tsourdos, A. (2016). Efficient Path Following Algorithm for Unmanned Surface Vehicle. In Proceedings of MTS/IEEE OCEANS 2016 Shanghai. IEEE. doi: 10.1109/OCEANSAP.2016.7485430. Phanthong, T., Maki, T., Ura, T., Sakamaki, T., and Aiyarak, P. (2014). Application of A∗ Algorithm for Real-time Path Re-planning of an Unmanned Surface Vehicle Avoiding Underwater Obstacles. Journal of Marine Science and Application, 13(1), 105–116. doi: 10.1007/s11804-014-1224-3. Savvaris, A., Niu, H., Oh, H., and Tsourdos, A. (2014). Development of Collision Avoidance Algorithms for the C-Enduro USV. In Proceedings of the 19th IFAC World Congress (IFAC 2014), volume 47 of IFAC Proceedings Volumes, 12174–12181. Elsevier. doi:10.3182/201408246-ZA-1003.02362. Wein, R., van den Berg, J.P., and Halperin, D. (2007). The visibility–Voronoi complex and its applications. Computational Geometry, 36(1), 66–87. Wu, B., Wen, Y., Huang, Y., and Zhu, M. (2013). Research of Unmanned Surface Vessel (USV) Path Planning Algorithm Based on ArcGIS. In Proceedings of ICTIS 2013, 2125–2134. ASCE.