Imperialist Competitive Algorithm for AUV Path Planning in a Variable Ocean

Abstract

An imperialist competitive algorithm (ICA) is introduced for solving the optimal path planning problem for autonomous underwater vehicles (AUVs) operating in turbulent, cluttered, and uncertain environments. ICA is a new sociopolitically inspired global search metaheuristic based on a form of competition between “imperialist” forces and opposing colonies. In this study, ICA is applied to optimize the coordinates of a set of control points for generating a curved spline path. The ICA-based path planner is tested to find an optimal trajectory for an AUV navigating through a variable ocean environment in the presence of an irregularly shaped underwater terrain. The genetic algorithm (GA) and quantum-behaved particle swarm optimization (QPSO) are described and evaluated with the ICA for the path optimization problem. Simulation results show that the proposed ICA approach is able to obtain a more optimized trajectory than the GA- or QPSO-based methods. Monte Carlo simulations demonstrate the robustness and superiority of the proposed ICA scheme compared with the GA and QPSO schemes.

INTRODUCTION

AUVs usually operate in dynamic, cluttered, and uncertain ocean environments. Real-time path planning is of primary importance to ensure safe and efficient operation of a vehicle in such environments. A path planner should be capable of rapidly reacting to fast changing environments and finding a trajectory that safely leads the AUV from its initial or current position to its destination with minimum energy/time cost. By choosing an appropriate trajectory, the path planner may enable an AUV to both bypass adverse currents as well as exploit favorable currents to achieve greater speeds, while substantially saving energy.

Path planning for AUVs has been widely researched in recent years. Grid search-based schemes such as Dijkstra’s algorithm or the A* algorithm can be applied for path optimization. Dijkstra’s algorithm computes every possible path from a starting point to a specified destination point (Dijkstra 1959). With its heuristic searching ability, the A* algorithm (Carroll et al. 1992) has proven to be more efficient. However, these grid search-based schemes are commonly criticized for their discrete state transitions, which unnaturally constrain the motion of a vehicle to limited directions. The Field D* algorithm uses a linear interpolation-based method to allow continuous heading directions, but it is computationally expensive to employ in high-dimensional problems (Ferguson and Stentz 2006). The fast marching (FM) algorithm, which is based on an assumption that the free space is isotropic, is more accurate but also more computationally expensive than A*. A heuristically guided version of FM, known as FM* (Pêtrès et al. 2007; Pêtrès et al. 2005), maintains the accuracy of the FM algorithm along with the efficiency of the A* algorithm, however it is limited in that it is applicable with only linear energy cost functions. An artificial potential field for global path planning based on a linear energy cost function was originally proposed by Warren (Warren 1990). Kruger et al. (2007) then replaced the single-term cost function with one that incorporates a mixture of various linear terms, including energy, obstacle regions, distance, time, and excess speed. Although the use of the artificial potential field cost terms allows fast convergence and is easy to apply to irregularly shaped obstacles, it is susceptible to local minima.

Several existing path planning schemes also make use of evolutionary algorithms for identifying the optimal path. The genetic algorithm (GA; Alvarez et al. 2004; Nikolos et al. 2003; Zheng et al. 2005) and the particle swarm optimization (PSO; Besada-Portas et al. 2013; Roberge et al. 2013) are two well-known forms of evolutionary algorithms that are generally recognized to be effective optimization techniques for solving path planning problems. Unlike other approaches, the computation complexity of GA and PSO only linearly relates to the dimension of the solution space. Their drawback is that they might converge to a suboptimal solution within a finite time. Quantum-behaved particle swarm optimization (QPSO) is recognized as an improved version of the original PSO (Zeng, Lammas, et al. 2012); it differs in that QPSO assumes that every particle in the swarm has quantum behavior instead of using the conventional position and velocity update rules employed in PSO. Fu et al. (2012) applied the QPSO for path planning and showed that it has superior performance compared to the standard PSO and GA algorithms. However, QPSO is sensitive to the tuning of its parameters and research is still in progress to reduce this sensitivity (Zeng, Lammas, et al. 2014).

The Imperialist Competitive Algorithm (ICA) is a new evolutionary algorithm first proposed by Atashpaz-Gargari and Lucas (2007) for solving continuous optimization problems. Similar to other population-based algorithms, a candidate solution is called Countries (individuals in other evolutionary algorithms) in ICA. Inspired by the behavior of imperialist countries in their attempts to conquer colonies, ICA recursively applies the assimilation and competition operators among the countries until a stop condition is satisfied. During this process, the colonies gradually move toward the imperialists so that the population tends to converge to certain areas of the search space where the best solution found so far are located. Recently, ICA has been successfully utilized to solve optimization problems in many engineering applications such as control (Hoseini and Salehipoor 2012), power dispatch (Roche et al. 2012), and production management (Jolai et al. 2012) and has shown high performance in both global searching ability and convergence rate.

In this study, an ICA-based path planner is developed and simulated to find an optimal trajectory for an AUV under various scenarios. Moreover, a thorough robustness assessment is presented to compare the effectiveness of the proposed ICA method with the GA and QPSO methods using the travel time along the optimized path and the computation time as the evaluation metrics.

The rest of this article is organized as follows. “Problem Formulation” describes the path planning missions and formulates the optimization problem. Mathematical models describing the subsea terrain and behavior of variable current flow within an ocean environment are also provided together with a measure of estimated travel time consumed along a path. The section that follows introduces the GA, QPSO, and ICA methods as well as their integration into the path planner. The simulation tests and robustness assessment using Monte Carlo trials are presented in “Simulation Results” and ”Robustness Assessment.” Concluding remarks are then presented in “Conclusion.”

PROBLEM FORMULATION

The objective of a path planning system is to find the minimum path ^† among the set of all feasible paths that leads an AUV traveling through the ocean environment from its initial condition to its terminal condition . The ocean environment is modeled as a strong currents field cluttered with obstacles, , the position of which can be dynamic and uncertain. Therefore the path planning problem is formulated as the following optimization problem:

(1)

where is a waypoint along the path .

Terrain Avoidance

Autonomous underwater vehicles are usually used as survey platforms for high-resolution mapping and imaging of the sea floor. In general, AUVs perform the seabed surveys either by maintaining a constant depth or by following the bottom. Although the bottom-following survey enables AUVs to maintain a constant height off the seafloor, thus, in principle, to have a close proximity to the seafloor producing better accuracy, the constant depth survey ensures stable vehicle motion for the vehicle’s own safety consideration. This is essential in order to allow the vehicle to manage the presence of mountainous and rugged terrains along its path while maintaining a low height off the seafloor (Yoerger et al. 2007). For simulation purposes, an approximately realistic-looking terrain can be generated using fractional Brownian motion based on fractal generation algorithmic methods originated by Benoît Mandelbrot (Barnsley and Frame 2012). Assume that AUVs operate at constant altitude; if represents the space that is occupied by the terrain, a feasible path should avoid collision with the terrain.

(2)

Ocean Field Environment

Oceanographic environmental information can be obtained from remote observations, such as HF radar surface current measurements and satellite observations, or from in-situ moorings, or from numerical forecast models. An example of a predictive tool is the Regional Ocean Model System (ROMS) which is an open-source, ocean model that is widely accepted and supported throughout the oceanographic and modeling communities. ROMS was developed to study ocean processes along the western U.S. coast with increasing resolution ranging from 15 km down to 1 km resolutions (Smith et al. 2010). The currents field maps presented in this study use a 1 km resolution. The vertical profile of a static 2D turbulent ocean field environment is estimated by superposition of multiple located viscous Lamb vortices as described in previous work (Garau et al. 2006).

Path Formation

In this study, the potential AUV trajectories are defined in space by B-spline curves obtained from a set of control points . The fitness value of each path is measured by using uniform subdivision (Zeng, Sammut, et al. 2012) whereby the continuous spline curves are discretized by a sequence of waypoints along the path .

Path Evaluation

The fitness value of each path is evaluated by measuring the travel time consumed and the risk of collision with an obstacle.

The travel time F along a given path is the sum of time required to cover each of these segments constituting the path.

(3)

where are two adjacent internal knots along the path. In previous work (Garau et al. 2005), the vehicle’s thrust power is assumed to be constant, equivalently, the vehicle has constant water-referenced speed. The resultant ground velocity of the vehicle is resolved in a 2D horizon using the water-referenced speed of the vehicle in the geographical frame and the velocity of the water currents.

GA, QPSO, AND ICA ALGORITHMS

GA, QPSO, and ICA algorithms all belong to the class of evolutionary computation that use iterative progress, such as growth or development in a population. This population is then selected through a heuristic search to achieve the desired solution. In this study, the state of the ith individual, swarm, or country at iteration is represented as

(4)

where m is the dimension of the problem space (equivalent to the number of path nodes).

GA Based Path Planner

Figure 1 provides an overview of the GA-based path planner. Emulating the evolution process found in nature, children solutions are created from the following operators: A fraction of the individuals in the current generation with the best fitness values are called elite children. These individuals automatically survive to the next generation. A roulette-wheel selection mechanism is applied to stochastically select from one generation to create the basis of the next generation. This ensures that fitter individuals will tend to have a better probability of survival and will go forward to form the pool for crossover. The crossover operator serves to create the children by combining the vectors of their parents and mutating them to introduce random variations to the remaining population. Finally, the parent generation is replaced by the children generation. This evolution cycle continues for a maximum number of generations or until the stop criterion has been met. The detailed implementation of the GA algorithm for path planning can be found in our previous paper (Zeng, Sammut, et al. 2012).

FIGURE 1 Flowchart of the GA-based path planner.

Selection

A roulette-wheel selection mechanism is applied to stochastically select from one generation to create the mating pool for the next generation. The fitness value of each individual is associated with its probability of being selected:

(5)

Crossover

Children are created by combining the vectors of their parents. A heuristic crossover scheme is applied to the selected chromosomes from the previous step. Assuming that , the new individual is generated by linear combination of their parents, defined as

(6)

(7)

where is a preset ratio.

Mutation

Mutation creates a random variation of a single parent. The uniform mutation scheme is applied to the remaining individuals; for each mutated individual, a proportion of genes are randomly selected and replaced by new genes from the constrained bounds. Let and be the upper and lower bounds, be a random number within the interval (0, 1), and be one of the genes selected to be replaced by

(8)

QPSO-Based Path Planner

Figure 2 provides an overview of the QPSO-based path planning mechanism. Every particle in the swarm represents a potential path, and the parameters of each particle correspond to the coordinates of control points generating the path. As the QPSO algorithm iterates, every particle is attracted toward its respective local attractor based on the outcome of the particle’s individual search as well as the particle swarm’s search results.

FIGURE 2 Flowchart of the QPSO-based path planner.

• Compute the mean best position: Set to be the state with the best fitness found so far at iteration for the ith particle. Evaluate the mbest, which is defined as the mean of the best states of all particles:

  (9)

• Position update: Update the state of the particle using the following Equations (10)–(12):

  (10)
  (11)
  (12)
  where , are two random numbers uniformly distributed within the interval , and is the parameter that determines the convergence speed of the algorithm.

ICA-Based Path Planner

ICA is inspired by the concepts of imperialism and imperialistic competition process. ICA starts with an initial population consisting of countries that are the counterpart of chromosomes in GAs and particles in QPSO. This population is divided into two groups. The ones with the best objective function values are selected to be the imperialists, whereas the remaining ones are their colonies according to each imperialist’s power (objective function value). The more powerful an imperialist is, the more colonies it will possess. An imperialist country together with its colonies is termed an empire.

In the main loop, the formative empires undergo a recursive assimilation and imperialistic competition process until a terminate condition is satisfied (Atashpaz-Gargari and Lucas 2007). Assimilation is implemented by moving the colonies toward their corresponding imperialist country. In this process there is the possibility that a colony may become more powerful than its imperialist owner. In this case, the colony will replace the imperialist country and take control of the entire empire. During imperialistic competition, the most powerful empires tend to grow while the weaker ones collapse. These two mechanisms lead the algorithm to finally converge into just one remaining empire.

Table

Algorithm 1. Imperialist Competitive Algorithm
Initialization
a) Choose appropriate parameters for the population size, (equivalent to the number of candidate paths), the dimension of the problem space, (equivalent to the number of control points used to generate the B-spline path), and the maximum number of iterations, . Input the ocean field information.
b) Generate an initial group of countries with random states representing the candidate paths.
c) Nld powerful countries are selected to be imperialists, and the remaining Nrp countries are allocated to different empires based on their imperialists’ normalized power, . The number of countries that form an empire is
(13)
where , and with being the cost of nth imperialists, which is the same as the fitness value in GA, and being its normalized cost.
Main Loop
d) while Stop condition is not satisfied do
e) for i = 1,2, … , Nimp do
f) Countries in each colony move toward their respective imperialist following the assimilation policy:
(14)
where d is the distance between the colony and its imperialist, γ is called the assimilation coefficient (γ > 1), and θ adjusts the deviation from the original direction and enables searching around the imperialist.
g) if there is a colony in an empire that has a lower cost than the imperialist, then switch the positions of that colony and the imperialist;
end if
h) Compute the total cost of all empires: the total cost of each empire is defined by the cost of its imperialist plus its average colonies’ cost, as expressed by (15):
(15)
where is the power of ith empire, and is a parameter to adjust colonies’ effects on determining the power of their empires.
i) Imperialistic competition: all empires try to take possession of the colonies of other empires and to control them. This imperialistic competition is modeled by picking the weakest colonies from the weakest empires and giving them to the empire that has the highest likelihood to possess them. To start the competition, the possession probability of each empire is defined as
(16)
where . The total cost and the normalized total cost of the nth empire, respectively, are and .

(Continued)

Table

Algorithm 1. (Continued)
To divide the colonies among empires based on their possession probability, a vector is formed:
(17)
Then, a vector with the same size as , filled with random numbers, is created:
(18)
where are random numbers between 0 and 1. Vector is formed by subtracting from P.
(19)
Referring to vector , the mentioned colonies are assigned to an empire whose relevant index in is maximum.
j) if there is an empire with no colony, then eliminate this empire
end if
k) end for
l) end while

SIMULATION RESULTS

Simulation Setup

The GA, QPSO, and ICA mechanisms were integrated into the path planner and implemented in MATLAB. Two scenarios were tested to compare the performances of the GA-, QPSO-, and ICA-based path planner in the presence of different ocean environments. The first scenario is to generate a trajectory avoiding irregularly shaped terrains. Two cases, one which uses a single island-shaped terrain and the other, which uses a cluttered terrain, are tested in this scenario. The second scenario is to safely navigate the AUV through a narrow harbor entrance for recovery.

In this section, the simulations are performed on a 100-runs basis for every scenario. The performances of the GA, QPSO, and ICA schemes are compared based on two factors: searching ability and computation time. The searching ability is reflected in the quality of the solution as given by the minimum, maximum, mean best fitness values, and the stability. Because the proposed optimization is a minimization problem, the smaller the mean value is, the stronger the searching ability. The stability is evaluated from the standard deviation. Execution time is the mean CPU time consumed over 100 runs for each strategy.

As mentioned in “Ocean Field Environment,” the current field for the scenario reported in this study, within a 2D spatial domain, is generated from a random distribution of 80 Lamb vortexes represented by a 100 × 100 grid. The distance between nearest neighbor grid points corresponds to 1000m. The strength and radius η of each vortex are set as 15 m/s and 2 m, respectively. The water-referenced speed of the vehicle in the geographical frame is set at 1.5m/s. Each individual B-spline path is formed by 12 control points and is uniformly subdivided by 1152 internal knots.

The experimentally optimized settings of the GA-, QPSO-, and ICA-based path planners are given in Table 1.

TABLE 1 Parameter Values

Parameters		Value
Population size		200
Iterations		100
GA	Selection rate	0.1
	Crossover rate	0.8
	Mutation rate	0.1
QPSO	Coefficient
ICA	Assimilation coefficient γ	1.2
	Assimilation angle coefficient	0.5
	Coefficient	0.1

Current Field with Irregularly Shaped Terrains

Figure 3 displays the result of Scenario 1: trajectory optimization in an environment containing a single island-shaped terrain within a current field. The optimal path projections generated by the proposed schemes: GA, QPSO, ICA, are shown in Figure 3(a). The convergence curves showing the best fitness values for each method with the corresponding numbers of iterations is shown in Figure 3(b). As can be seen from Figure 3(a), all optimized trajectories are formed by following the direction of the currents. This procedure allows the vehicle to ride the currents toward its destination, hence, attaining increased speed and reducing overall travel time. It is worth noting that the best trajectory generated by ICA is able to follow the current much better than those produced by GA and QPSO, even though the length of the path is relatively extended.

FIGURE 3 Scenario 1: Comparison of results produced by the GA-, QPSO-, and ICA-based path planners: (a) path projections with a single island-shaped terrain, (b) convergence curve of best fitness values.

The corresponding Monte Carlo simulation time for Scenario 1 is recorded in Table 2, from which it can be observed that the mean cost value and the corresponding standard deviation of the ICA are both less than those of the GA and QPSO algorithms. Because the mean fitness value and the standard deviation value reflect the searching ability and stability, it can be concluded that the ICA achieves better searching ability and robustness than the other two algorithms. Meanwhile, it is clear to see from Table 2 that ICA has the fastest and most stable execution time among the three methods.

TABLE 2 Performance Comparison of GA-, QPSO-, and ICA-Based Path Planners with Scenario 1

Algorithm	Min cost	Max cost	Mean cost	Std cost	Mean execution time (sec)	Std execution time (sec)
GA	63466.26	71843.74	66030.88	1665.859	11.83204	0.256305
QPSO	64304.05	68489.32	65970.09	905.7815	7.711888	0.395954
ICA	63489.49	70923.63	65304.8	1154.551	7.684062	0.149027

Similar experiments are also performed in Scenario 2, which includes a turbulent current field containing cluttered, irregularly shaped terrains. The results are shown in Figure 4. By comparing the convergence curves shown in Figure 3(b) and Figure 4(b), it can be noted that the performance of the GA scheme on both scenarios is relatively poor; it has the highest cost value relative to the QPSO and ICA schemes. The main reason for this is that GA has a slower convergence, resulting in the path solution still being suboptimal after the maximum number of iterations. It is also evident that the convergence curve of QPSO drops rapidly in the first 20 iterations but shows very little improvement afterward; such a feature indicates that QPSO may lead to premature convergence and become stuck at a local minimum. In contrast, the proposed ICA scheme achieves better results than the GA and QPSO schemes in both scenarios. The reason can be found from Figures 3(b) and 4(b); the convergence curve of the proposed ICA scheme drops both rapidly and steadily, which testifies that the ICA has a well-balanced and flexible mechanism to enhance the global and local exploration and exploitation abilities.

FIGURE 4 Scenario 2: Comparison of results produced by the GA-, QPSO-, and ICA-based path planners: (a) path projections with cluttered, irregularly shaped terrains, (b) convergence curve of best fitness values.

From the statistical results shown in Table 3, the ICA-based path planner offers the solution with the lowest mean best fitness value and standard deviation compared with those of the other two methods. This result further demonstrates the high performance and robustness of the proposed ICA method.

TABLE 3 Performance Comparison of GA-, QPSO-, and ICA-Based Path Planners with Scenario 2

Algorithm	Min cost	Max cost	Mean cost	Std cost	Mean execution time (sec)	Std execution time (sec)
GA	58530.94	96172.61	63731.37	6425.079	11.9224	0.348494
QPSO	58636.96	63667.64	60907.6	1083.373	7.438417	0.105888
ICA	57840.03	66918.52	60563.29	1700.495	6.981611	0.089451

Harbor Recovery in the Presence of a Current Field

Figure 5 displays the simulation results for Scenario 3 in which the AUV is navigated through a narrow harbor for recovery. With the current environment and other conditions being equal, the problem becomes more challenging because a large population of the candidate paths will become invalid if they fail to go through the narrow harbor entrance. Therefore, it is more difficult for all three algorithms to find the global optimal solution. By comparing the convergence curves shown in Figure 5(b), it is evident that as the scenario becomes increasingly difficult, the convergence speeds of the GA and QPSO slow down. However, the same situation will only slightly affect the performance of ICA. The ICA-based path planner still outperforms the other two planners and eventually finds a better trajectory with less time consumption.

FIGURE 5 Scenario 3: Comparison of results produced by the GA-, QPSO-, and ICA-based path planners: (a) path projections through a narrow harbor for recovery, (b) convergence curve of best fitness values.

It should be noted that the performances of GA for both Scenario 1 and Scenario 2 are all relatively poor. As illustrated in Tables 2–4, the maximum cost, mean cost, and its standard deviation, as well as the mean execution time of GA are all the largest among the three algorithms. Worse still, as can be seen from Table 4, the maximum cost of GA is infinity, which means it failed to generate a collision-free path.

TABLE 4 Performance Comparison of GA-, QPSO-, and ICA-Based Path Planners with Scenario 3

Algorithm	Min cost	Max cost	Mean cost	Std cost	Mean execution time (sec)	Std execution time (sec)
GA	64010.07	+inf	—	—	11.23892	0.250706
QPSO	64122.04	74147.86	67985.8	2480.08	7.205081	0.337451
ICA	64779.06	72195.69	67593.52	1721.423	7.142228	0.056162

Therefore, it is concluded that despite the increasing problem complexity, the ICA-based path planner continues producing more optimal and robust solutions relative to the GA- and QPSO-based path planners.

ROBUSTNESS ASSESSMENT

One thousand Monte Carlo simulation runs, each with a random generated start and destination positions, current fields, and obstacles, were performed to compare the relative robustness of the GA, QPSO, and ICA schemes. For all the 1000 simulation runs, the scheme that returned the minimum fitness value for each run was counted as having a “win,” whereas that with the maximum fitness value was counted as having a “loss.” The results are presented in Table 5. The ICA scheme has a significantly higher chance (over 70%) of obtaining a better trajectory and is much less likely (less than 5%) to return a worse trajectory than the QPSO and GA methods. It should also be noted that in most of these runs, the performance of the GA method is poor and far from perfect.

TABLE 5 Comparison of Relative Performance of GA-, QPSO-, and ICA-Based Path Planners

Algorithms	Number of Wins	Number of Losses
GA	89	486
QPSO	190	479
ICA	721	35

Figure 6 shows the difference of fitness values between GA-ICA and QPSO-ICA across the corresponding simulation runs. It can be noted that across the 1000 simulation runs, the differences of fitness values are mostly above 0, which implies that the ICA scheme returns the smallest fitness value compare to the QPSO and GA schemes. In fact, even for those few simulation runs, the ICA scheme generates a bigger fitness value than those of QPSO or GA schemes; their fitness value differences are relatively small, as shown in Figure 6. The fitness value difference can be about six times larger when the ICA scheme achieves a win.

FIGURE 6 Performance comparison of the GA-, QPSO-, and ICA-based path planners showing difference of fitness values with the corresponding simulation runs.

In summary, these Monte Carlo tests of the path planning system demonstrate the improved performance and robustness of the proposed ICA method.

CONCLUSION

This article presents a novel ICA-based path planner. Simulation tests have been performed to generate an optimal trajectory with minimum time consumption for an AUV traveling through turbulent ocean fields in the presence of various irregularly shaped terrains. Based on the results of these tests, the ICA scheme is shown to be more capable of finding an optimized trajectory, with less computation time than the GA and QPSO methods. In addition, Monte Carlo simulations demonstrate the robustness of the proposed ICA scheme compared with the previous methods.

The next stage in this work is to apply realistic ocean environment data information to the proposed path planner and compare the time savings gained using the different optimization schemes discussed in this article. One main limitation of the work completed thus far is that the path planner is suitable only for an AUV operating in an ocean environment where the currents are assumed to remain consistent during the mission period. However, real currents vary over time in both direction and strength. As a natural extension of the above work, the path planner is being developed to incorporate current forecasts information to allow mission planning over long time periods during which the currents can change. Another extension of this work is to develop an online-based ICA scheme that can be incorporated into a vehicle’s guidance system to allow it to regenerate the trajectory during the course of the mission using continuously updated current profiles from on-board sensors (Zeng, Sammut, et al. 2014), such as a Horizontal Acoustic Doppler Velocity Logger.

FUNDING

Zheng Zeng is funded by postgraduate funding from the China Scholarship Council (CSC)-Flinders University scholarship program. The research is funded through a CSIRO Wealth from Oceans program.

Additional information

Funding

Zheng Zeng is funded by postgraduate funding from the China Scholarship Council (CSC)-Flinders University scholarship program. The research is funded through a CSIRO Wealth from Oceans program.