Multi-Objective Optimization Based Collision Avoidance Algorithm for an Intelligence Marine Navigation

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 generation’s 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, X₁ solution dominates over X₂ solution if and only if, firstly, X₁ is not worse than X₂ in all objectives and secondly at least in one objective function X₁ is better than X₂. The solutions of first front are the final set of optimal solutions.

Modeling the algorithm: Modeling the problem into algorithm’s 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 ship’s 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 that’s called redirection point. For presenting and modeling the route of the ship can use the coordinates of redirection points besides speed and direction of ship’s 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 problem’s 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 algorithm’s 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 d_i, n is the size of obtained NDS and f_kⁱ is the function value of the k-th objective function for solution i. The lower values of the SM are preferable (Schott, 1995).

(1)

Where:

The SM metric is calculated for all runs of the algorithm. Table 2 shows the SM values for each run of the algorithm. Regarding the Table 2, all runs have acceptable values.

Table 2:	Values of spacing metrics for the algorithm’s 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.

CONCLUSION

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.