Currently, the collision avoidance algorithm is considered as an essential part of the marine navigation systems. The collision avoidance algorithm determines and decides to change the speed and direction of a ship in the presence of obstacles. Avoidance of collision problem can be considered as a spatial multi objective problem due to it needs to handle with different objectives by searching a space of possible routes and find a set of optimal routes. Solving collision avoidance problem in ships routing is a complicated problem because of different objectives, inconsistency between them and presence of dynamic and static obstacles in sea. In this study, the Multi-Objective Evolutionary Algorithm (MOEA) as an optimization technique has been used for solving the problem in the context of GIS. Two objectives, highest safety and lowest deviation from main route, have been considered for simulating and solving the problem. The proposed algorithm has been implemented for solving the problem in five simulated situations, including various modes of dynamic and static obstacles. The results have been analytically and numerically evaluated. Determination of the optimal routes set, suitable rapidity of the algorithm (about 40 sec), efficient convergence trend and repeatability of results (80%) are the positive and promising consequences of evaluating the algorithms results.
PDF Abstract XML References Citation
How to cite this article
About 70% of the earth is covered by water being part of the high seas that are connected together. Accessibility to high seas is so important for countries because of strategic advantages like financial, military, political and etc. Since 1940 by inventing and developing radar, the ways of management and controlling the sea problems have been changed and modern shipping is established based on this equipment. Issues facing modern shipping can be divided into three groups: Large-scale ships with low maneuverability, traffic barriers in ports and harming environment. The Vessel Traffic Service (VTS) is established for solving this problems and limitations in modern shipping that consists of equipment in port and ships. Services of VTS are messaging the location of obstacles, dangers, weather cautions and managing the transport of ships. Helping ships to navigate and routing is one of the most important purposes of VTS that is done by sending information to ships like route and speed of other ships, relative location of important points of route, location of large and small scale of other ships (Nuriye et al., 2015).
Sea routing is more complicated than road routing due to no specified network of edges and vertexes, weather and storm factors and presence of obstacles in sea. Sea routing as a kind of routing is a spatial problem. As Roger Dangermond (Baylon and Santos, 2013) (founder of the ESRI, the maker of ArcGIS) has said, "The applicability of GIS is limited only by the imagination of those who use it". GIS simply can be considered as science and technology of understanding, modeling and analyzing spatial problems. Frequent tasks of GIS are mapping and visualization; also main tasks of GIS are analyzing and solving spatial problems. The GIS applications in marine issues can be divided into three groups of marine transportations, management and operations in ports and designing sustainable marine environment. Ship routing problem is placed in marine transportation that can be solved by GIS tools. Using meta-heuristic algorithms in the context of GIS for solving complex and multi-objective spatial problems is the innovative way to optimal decision making.
An intelligence marine navigation is one of the modern issues in a domain of marine transportation. Marine navigation is a routing problem in sea that can be affected by many factors and can be considered as a multi-objective making decision problem. Determine a specific route for a ship is like searching in large space of possible routes and choose one of them. In multi-objective routing, a set of optimal routes are chosen instead of an optimal route. A sea routing can be considered as an optimization problem due to nature of routing problem. One of the issues in intelligence marine navigation is collision avoidance and how redirects the ship in facing to obstacles (Yuliando et al., 2013). The nature of the collision avoidance problem is like a nature of routing and optimization problems. This problem should be solved in a minimum possible time and present a set of optimal routes to navigators of ship for determining the best possible route. The collision with obstacles in sea has been historically considered as the cardinal problem of marine navigation and now in 21st century is time to solve this problem using intelligence algorithm and available GIS context, GIS has applications in different marine issues that are presented by Baylon and Santos (2013), through providing intelligence marine navigation systems.
The collision avoidance problem has been concerned in last decades. Also, it has been solved with various algorithms which are almost deterministic algorithms that capable to solve the problem in a single objective mode. A number of significant researches which use optimization algorithms, in this field of marine navigation are mentioned in the following lines. First, collision avoidance problem is introduced as a single-objective optimization problem by considering the static obstacles (islands and forbidden area) and the dynamic obstacles (ships and weather parameters) and possibility of using optimization algorithms in the study of Smierzchalski (1997). In addition, numbers of evolutionary algorithms are examined for solving the single-objective mode of the problem (Michalewicz, 1996; Xiao et al., 1997) which isnt consistent with nature of collision avoidance as a multi-objective problem. Distributed Evolutionary Algorithm (DGA) as a multi-population genetic algorithm is used for solving the problem, in a simple circumstance and the results are compared with the results of single-population genetic algorithm that shows the better performance of DGA (Smierzchalski et al., 2013; Kadhim and Abdulrazzaq, 2014). In this study, an essential part of the modern and intelligence marine navigation system is examined and solved by a meta-heuristic optimization algorithm. The marine collision avoidance problem is solved in presence of dynamic and static obstacles using a multi-objective evolutionary algorithm. Maximum safety and minimum deviation from main route are considered as the objectives of the problem. The algorithm is modeled and used for solving the problem in five simulated environments, including diverse (dynamic and statics) obstacles. The results of implementing the algorithm are analytically and numerically evaluated.
MATERIALS AND METHODS
In this section, it was tried to clearly describe the methodology in three parts. Firstly, the concepts of the proposed algorithm is described. Then, the way of modeling the algorithm in the problem is explained. At the last part of this section, the simulating environments for implementing the algorithm and solving the problem is described.
MOEA: Evolutionary algorithms are inspired from evolution of animal species in nature that have lots of applications in solving various and complex problems. Generally, in optimization problems, a main process searches the large space of possible solutions and choosing the one or a set of optimal solutions according to one or numbers of objective functions. In evolutionary algorithm (Deb et al., 2002), a chromosome conception is used for presenting each solution. Each chromosome consists of independent units called gen. Firstly, in multi-objective evolutionary algorithm, the set of possible solutions are produced randomly that are used as inputs of main loop in the algorithm. In the main loop of the algorithm, the inputted solutions, as a generation, are changed by operators and are converted to next generation. The main loop is continued until the stop criteria of iteration are satisfied. The algorithm can be divided into three main steps that are presented in Fig. 1.
In first step of the algorithm, some parameter must be initialized which are counted of each generations members, cross over rate, mutation rate and stop criteria. According to count of members in each generation and conditions of the problem, first generation is produced randomly and is considered as input of operators. In each repetition of main loop, the algorithm accepts a generation as input and a new generation is produced as output. Competence determination operator specifies a competence value based on values of objective functions for each solution. Selection operator selects the pairs of chromosome for cross over operator based on each solution competence and randomly according to pre-specified cross over rate. Cross over operator produce pair of new solutions from selected chromosomes in selection operator. The new chromosomes will replace the selected solutions. The cross over operator combines based on joint gen of each parent (selected chromosomes). A mutation operator randomly changes the gen of some of the chromosomes, based on mutation rate and according to conditions of the problem. The mutation operator is the last operator in each repetition to produce a new generation. The last step of each repetition verifies the stop criteria that led to make a decision of whether repeat the loop or end it.
|Fig. 1:||Multi-objective evolutionary algorithm steps|
|Fig. 2:||Modeling of the problem|
|Fig. 3:||Chromosome of ship route|
Common stop criteria for main loop are consisted of two factors, first is a maximum number of iteration and second is minimum differences between competencies of two consecutive generations. A Pareto front concept is used for determination of an optimal set of solution in multi-objective problems. Based on Pareto front, each solution is placed in specific front that dominates solutions in lower fronts and defeats solutions in upper fronts. The solutions in each front not dominated each other. According to definition, X1 solution dominates over X2 solution if and only if, firstly, X1 is not worse than X2 in all objectives and secondly at least in one objective function X1 is better than X2. The solutions of first front are the final set of optimal solutions.
Modeling the algorithm: Modeling the problem into algorithms space is needed to solving collision avoidance by the multi-objective evolutionary algorithm. In this problem, a ship moves from one specific point to another specific point, start and end points, through a particular route that there is some obstacle in its route. The ship is modeled according to its central coordinates and such as a point that moves from start to end through a specific set of coordinates. The ship has the constant speed and constant direction for a move between the two points. The static obstacles are modeled as a specific range of coordinates. If the movement coordinates of ship is same as the static obstacles coordinate, at least in one point, then the collision happens. The dynamic obstacles are modeled as a moving point with constant speed and constant direction. The dynamic obstacles coordinate will be calculated dynamically according to ships position. The steps of modeling the problem in the algorithm are shown in Fig. 2.
The ship for avoiding the collision will change the speed and/or the direction of its movement in one point thats called redirection point. For presenting and modeling the route of the ship can use the coordinates of redirection points besides speed and direction of ships movement in chromosome and genes. A chromosome with three redirection points is shown in Fig. 3. The selection operator chooses the pair of parents for combination based on competence and random using proportional roulette. Cross over operator combines each pair of chromosome based on joint redirection points and produce a new pair of chromosomes that are replaced the parents chromosomes. The mutation operator randomly chooses numbers of chromosomes and changes the direction and/or the speed of the ship in one of the redirection points according to the problems circumstances. These loops are continued till the stop criteria are satisfied.
The collision avoidance is considered as a two-objective problem, assuming that all other influenced parameters such as weather are constant. A maximum safety and minimum deviation from main route are considered as an optimal mode. Safe distance to avoid the collision in medium-sized ship is 5-8 m in front of the ship and 2-4 m in back of the ship (Smierzchalski, 1997) that can be changed for different size of ships. A rotation angle of the ship in redirection points is used for calculating the deviation from main route.
|Fig. 4:||Decision making flowchart|
|Fig. 5:||Simulated environments|
The total route safety is equal to the sum of minimum distances between barriers and ship. The integral deviation is calculated based on the sum of all the rotation angles. A decision making flowchart in facing of each obstacle is shown in Fig. 4.
Simulating the problem: For implementing the algorithm, five environments have been simulated that three of them are based on Smierzchalski et al. (2013) theory and the two others are a combination of these three modes. The two combined environments are more complicated than the others. An initial speed of ship is 20 knots and speed of dynamic obstacles is 15 knots. The five simulated environments are shown in Fig. 5.
RESULTS AND DISCUSSION
After the problem is modeled into the algorithms space, preparing data and simulating environments, the turn is initializing the parameters of the algorithm. Count of each generation members 30, mutation rate 0.15, cross over rate 0.2, maximum iteration for stop the loop 200 and the minimum difference between two consecutive generations is epsilon are initialized (Smierzchalski et al., 2013). A proportional speed between ship and dynamic obstacle is calculated for determining comparative position of ship relative to the obstacle. A two-dimensional coordinate system has been considered for positioning the dynamic objects. The results of running the algorithms for five simulated environments are shown in Fig. 6. The optimal routes are drawn in the figure and properties of them are described in Table 1. The optimum mode is the maximum total distance from barriers and the minimum total rotation angle in redirection points.
Running time of the algorithm for different scenarios has changed in the interval 38-52 sec that is increased by more complex scenarios with more numbers of obstacles. The convergence test is needed for assessing how the convergence results of the algorithm.
|Fig. 6:||Results of the algorithm|
|Fig. 7(a-b):||Convergence chart of (a) Safety and (b) Deviation|
|Table 1:||Properties of optimal routes|
The convergence test examines modifications of the objective functions values during running the algorithm. Convergence charts of the algorithm for each five environments are shown in Fig. 7 separately for each objective function. Each chart is drawn based on the minimum value of related objective function in the related iteration. The routes with at least one redirection points are considered in the charts.
In both convergence charts, simultaneously together the charts move to efficient values with decreasing slope smoothly. The results of evolutionary algorithms that first generation of them is produced randomly need to examine stability and repeatability capability. The repeatability test examines the differences between runs of the algorithm with same initialize parameters. The fifth environment is considered for this test because of complexity. The algorithm runs ten times with same parameters. Eight of ten runs approximately have the equivalent results in case of objective functions values that mean an 80% repeatability capability.
The diversity metrics evaluate the scatter of solutions in the final population on the Pareto front. Like the convergence metrics, many metrics for measuring the diversity of a set of approximation NDS towards the Pareto front have been proposed. We select the Spacing Metric (SM), was introduced by Schott (1995), to evaluate the applied algorithms. The spacing metric provides a measure of uniformity of the spread of approximation NDS. In Eq. 1 the metric is given, where, d- is the mean of all di, n is the size of obtained NDS and fki is the function value of the k-th objective function for solution i. The lower values of the SM are preferable (Schott, 1995).
|Table 2:||Values of spacing metrics for the algorithms runs|
As it is obvious, the algorithm has a better performance in respect of SM values at the more complicated circumstance of the problem. Run number 5 has the minimum quantity of SM which means the best value of diversity metrics.
In this study, the collision avoidance problem in presence of dynamic and static obstacles has been solved by the multi-objective evolutionary algorithm that is applicable for intelligence marine navigation systems. The problem has been simulated by different scenarios (include various modes of dynamic and static obstacles) besides the two objective functions (the safety and the deviation from main route). The results of implementation the algorithm are evaluated numerically and analytically. Evaluation denouements show the capability of the algorithm for using in the marine navigation systems.
Uniquely, we have simulated the collision avoidance problem in such a complicated circumstances (various obstacles) with optimizing two incompatible objective functions. However, the results and evaluation, generally, show the efficient use of the evolutionary algorithms in solving the collision avoidance problems as it was shown previously (Smierzchalski et al., 2013; Michalewicz, 1996; Xiao et al., 1997).
Developing intelligence and multi-objective routing algorithms, such as MOEA, as the main core of navigations systems will change the future of the navigation systems. The most dangerous problem in marine transportation is collision with obstacles which are invisible during night and fog. There is an obvious necessity for marine navigation system to provide intelligence and optimal routes for avoiding collision with obstacles. The result of the paper may be used for developing and establishing new and intelligence marine navigation systems.
It is recommended to use a real data of collisions and analyze the algorithm performance in real conditions. Developing the radar approaches and GPS equipment, the marine navigation using the algorithm can be completely intelligent and in a near future will be led to a new field of the marine transportation as called ubiquitous marine transportations.
- Baylon, A.M. and E.M.R. Santos, 2013. Introducing GIS to TransNav and its extensive maritime application: An innovative tool for intelligent decision making. Int. J. Mar. Navig. Saf. Sea Trans., 7: 557-566.
- Kadhim, A.A. and M.W. Abdulrazzaq, 2014. Efﬁcient routing techniques for wireless sensor networks. J. Applied Sci., Res., 14: 3479-3485.
- Smierzchalski, R., L. Kuczkowski, P. Kolendo and B. Jaworski, 2013. Distributed evolutionary algorithm for path planning in navigation situation. Int. J. Mar. Navig. Saf. Sea Trans., 7: 293-300.
- Xiao, J., Z. Michalewicz, L. Zhang and K. Trojanowski, 1997. Adaptive evolutionary planner/navigator for mobile robots. IEEE Trans. Evol. Comput., 1: 18-28.