Sage Journals: Discover world-class research

Abstract

An autonomous underwater vehicle needs to possess a certain degree of autonomy for any particular underwater mission to fulfil the mission objectives successfully and ensure its safety in all stages of the mission in a large-scale operating field. In this article, a novel combinatorial conflict-free task assignment strategy, consisting of an interactive engagement of a local path planner and an adaptive global route planner, is introduced. The method takes advantage of the heuristic search potency of the particle swarm optimization algorithm to address the discrete nature of routing-task assignment approach and the complexity of nondeterministic polynomial-time-hard path planning problem. The proposed hybrid method is highly efficient as a consequence of its reactive guidance framework that guarantees successful completion of missions particularly in cluttered environments. To examine the performance of the method in a context of mission productivity, mission time management, and vehicle safety, a series of simulation studies are undertaken. The results of simulations declare that the proposed method is reliable and robust, particularly in dealing with uncertainties, and it can significantly enhance the level of a vehicle’s autonomy by relying on its reactive nature and capability of providing fast feasible solutions.

Keywords

Underwater vehicle path planning route planning autonomy evolutionary optimization

Introduction

Autonomous underwater vehicles (AUVs) are steadily becoming more widely used across a wide range of maritime applications. Recent breakthroughs in computer systems and sensor technologies have greatly expanded the range of missions that can be performed by AUVs. This widening operating range, however, is intertwined with the appearance of new complexities, for instance propagation of uncertainty and accumulation of data, transforming the underwater mission into a challenging scenario. Increasing the mission productivity and ensuring the vehicles safety are two main concepts that should be satisfied in all stages of the mission considering the changes in environment. Hence, a vehicle must be able to autonomously perform effective and safe operation in such a severe environment. An efficient path planning strategy is a requisite to reach a satisfactory level of autonomy toward accomplishing underwater mission objectives. Efficient routing strategy promotes a vehicle’s capability in task assignment, maneuver timing, and maneuver efficiency, while a real-time local path planner is capable of satisfying safe and optimal deployment in uncertain, dynamic, and cluttered ocean environments. Respectively, the prior investigations in this area can be considered along two distinct research fields; vehicle path planning, along with vehicle routing and task scheduling approaches.

The path planning strategies are known as efficient methods in vehicle guidance toward the destination encountering the local unexpected dynamic changes of the surroundings. Various strategies such as heuristic search algorithms^1

–4 and evolutionary and artificial intelligence-based strategies^{5

–14} have been applied to the AUV motion planning problem in recent years. The fast marching (FM) algorithm is a heuristic approach utilized by Petres et al.³ to solve the path planning problem, which is efficient but computationally expensive compared to the A* algorithm. Afterward, Petres et al.⁴ employed an upgraded version of FM called heuristically guided FM (FM*) that keeps the accuracy of the FM along with the efficiency of the A*, but it is restricted to use linear anisotropic cost to attain computational efficiency. In general, the heuristic search algorithms are appropriate for real-time applications due to their high time complexity, especially in large space problems. Evolution-based optimization algorithms are a computationally faster approach that have been applied successfully to the path planning problem.^5,6 It has been proven that evolutionary algorithms are efficient methods in dealing with path planning as a nondeterministic polynomial-time (NP) hard problem and are capable of satisfying the time restrictions of real-time applications.^5

–8 The particle swarm optimization (PSO),^6,7 genetic algorithm (GA),^9
–11 differential evolution,⁵ and quantum-based PSO^12,13 are some commonly used optimization algorithms that have been successfully applied in the context of the unmanned vehicle path planning problem. Although most of these path planning techniques can accurately guide a vehicle toward the predefined destination, AUV-oriented applications still face many challenges, especially across a large-scale operation area. In large-scale operations, accurate estimation of the next state of the operating field (e.g. obstacles’ behavior, etc.), far beyond a vehicle’s current position and sensor coverage, is computationally hard and experimentally impractical. On the other hand, in the case that the environment is populated with many waypoints and the vehicle is required to carry out a specific set of tasks (assigned to distance between waypoints in an operation network), a routing strategy would be more appropriate than a path planning strategy to prioritize tasks based on a global overview of the vehicles trajectory in the vast operating field.

Several research investigations have explored the problem of autonomous vehicle routing and task scheduling in a graph-like operation environment. For instance, in the work by Kwok et al.,¹⁴ a time-optimal conflict-free route, relying on a few waypoints, was generated by a kind of an adaptive GA for operating in a large terrain. The heuristic nature of the PSO and GA algorithms has been investigated for the AUV routing and task allocation problem in the context of an NP-hard graph search problem.¹⁵ The biogeography-based optimization and PSO-based route plan task assignment system is proposed in the study by Zadeh et al.¹⁶ for real-time AUV operation in a semi-dynamic network. The merit of the proposed solutions given in the studies by Mahmoudzadeh et al.¹⁵ and Zadeh et al.¹⁶ is that they are independent of the graph size which is not the case with most deterministic algorithms such as the proposed mixed integer linear programming applied for governing multiple AUVs in the study by Higgins.¹⁷ The aforementioned strategies are mostly focused on task/target assignment and routing problems without considering the dynamicity of the environment and quality of deployment. The vehicles’ routing strategies are dissimilar to path planning approach in terms of quality of deployment and are not able to handle rapid environmental changes.

This research contributes a reactive combinatorial conflict-free task assignment scheme encompassing an adaptive global route and local path planning to cover the shortcomings associated with each of the aforementioned approaches. The route planner, in this context, is capable of generating a time-efficient route with appropriate task assignment to ensure that AUV has a productive journey and ends the mission on time, while the local path planner is responsible to generate an appropriate local path at a smaller scale to handle changes in the environment. In fact the local path planner and global route planner operate concurrently in parallel, while a constant interaction and information sharing is carried out between them. Their parallel execution accelerates the computation process and reduces unnecessary computation that would otherwise be caused by updates of whole terrain. A route replanning capability is also incorporated to improve mission timing and improve the reactive ability of the AUV to environmental changes. The REMUS-100 vehicle is considered as the reference vehicle for this work. Referring to the kinematic and hydrodynamic model of the REMUS-100 and the corresponding constraints of the vehicle as given in the article by Prestero,¹⁸ the problem formulation can then be developed. The constraints in the optimization problem reflect the natural constraints of the vehicle, and therefore, the solution obtained is realistic and applicable for real-word implementation.

The article is structured as follows. In “Problem formulation” section, the problem formulation is demonstrated. The PSO paradigm and its application for global route planning and local path planning are provided in “Overview of PSO” section. The simulation environment is presented in “Simulation results and discussion” section and the results are analyzed. In “Conclusion” section the conclusions for this research are presented.

Problem formulation of the AUV routing and local path planning problem

The presented framework, in essence, is a decentralized model of a high-level route planner that searches for an appropriate set of tasks that can be accomplished in a limited time, and a low-level local path planner, in which the model involves a decision maker core for determining the continuation of the path planning or need of the re-assignment of new tasks. This process ensures that the vehicle executes as many tasks as possible and provides a secure adaptive deployment toward the destination without unnecessary time expenditure. Therefore, the problem is formulated in two steps as follows.

AUV routing problem

Using a priori information about the underwater environment, first of all, the problem space should be transformed to a graph-like environment (depicted in Figure 2) in which all tasks are assigned to edges of the graph. The AUV starts its mission from one of the nodes called starting position WP^s :(x_s, y_s, z_s ) and tries to accomplish the maximum number of jobs (tasks along the graph edges) before reaching the predefined destination position WP^D :(x_D, y_D, z_D ) in a limited time. The positions of waypoints in the graph are initialized randomly using uniform distribution in three-dimensional (3-D) volume of 10000(x) × 10000(y) × 100(z) and connected by arbitrary edges q_ij . Each edge is assigned with a task and weighted by the priority of the corresponding task Task_ij : w_Tij . The goal is to find the best route through the given waypoints with maximum weight in a limited time that the AUV’s battery’s capacity allows; this is a form of multi-objective optimization problem similar to the Knapsack-Travelling Salesman Problem (TSP). In the proceeding research, the AUV’s route planning problem in 3-D environment is formulated as follows

\begin{array}{l} \forall {\begin{cases} W P^{i} : (x_{i}, y_{i}, z_{i}) \\ W P^{j} : (x_{j}, y_{j}, z_{j}) \end{cases} \to \exists q_{i j} \\ : {\begin{cases} d_{i j} = \sqrt{{(x_{j} - x_{i})}^{2} + {(y_{j} - y_{i})}^{2} + {(z_{j} - z_{i})}^{2}} \\ t_{i j} = \frac{d_{i j}}{V_{AUV}} \\ w_{T_{i j}} \end{cases} \end{array}

T_{Route} = \sum_{\begin{matrix} i = 0 \\ j \neq i \end{matrix}}^{n} l q_{i j} t_{i j} = \sum_{\begin{array}{l} i = 0 \\ j \neq i \end{array}}^{n} l q_{i j} (\frac{d_{i j}}{V_{AUV}}), l \in {0, 1}

\begin{array}{l} \max (\sum_{\begin{array}{l} i = 0 \\ j \neq i \end{array}}^{n} l q_{i j} w_{T_{i j}}), l \in {0, 1} \\ \min (| T_{Available} - T_{Route} |) \end{array}

where T _Route is the required time to pass the route, T _Available is the total existing time, l is the selection variable for any edge q_ij , and t_ij is the time to pass the distance d_ij that includes weight w_Tij of the corresponding task Task_ij . After a global route is generated, the path planner starts its operation of generating the optimum safe path among the existing waypoints in the global route.

AUV local path planning problem

In this section, the path planner aims to find the quickest collision-free path between waypoints. The dynamicity of the 3-D operation field captures the motion of various static and freely suspended obstacles Θ with uncertain position and velocity, where the suspended obstacles are driven by current flow. An obstacle’s velocity and uncertain position is modeled with a Gaussian distribution. Three different obstacles are modelled in this study to validate the efficiency of the path planner as follows:

1. Static object: The position is initialized once in advance using normal distribution and does not change during the operation

\begin{array}{l} \forall Θ_{i} \exists Θ_{p}^{i}, Θ_{r}^{i} \\ Θ_{p}^{i} \sim N (0, σ^{2}), σ^{2} \approx Θ_{r}^{i} \\ Θ_{p}^{i} \in (W P_{x, y, z}^{i}, W P_{x, y, z}^{i + 1}) \end{array}

where, Θ _p is obstacle position that should be referenced to the location of start and target waypoints and Θ _r is its radius and initialized with a value in range of (0, 100).

2. Static uncertain objects: The radius of the position uncertainty for these objects changes with time within a specified boundary and its value in any time step is independent of its previous value

Θ_{r}^{i} \sim N (Θ_{p}^{i}, σ^{2})

3. Moving uncertain obstacles: These objects move along a direction motivated by current velocity, hence their radius and position change iteratively according to equation (6)

\begin{array}{l} Θ_{p} (t) = Θ_{p} (t - 1) \pm U (Θ_{p_{0}}, σ) \\ Θ_{r} (t) = B_{1} Θ_{r} (t - 1) + B_{2} \times N (0, σ) + B_{3} \\ B_{1} = [\begin{matrix} 1 & U_{R}^{C} (t) & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}], B_{2} = [\begin{array}{l} 0 \\ 1 \\ 1 \end{array}], B_{3} = [\begin{array}{l} 0 \\ 0 \\ U_{R}^{C} (t) \end{array}] \\ U_{R}^{C} = | V_{c} | \sim N (0, 0.3) \end{array}

where V_C is the current velocity and U_R ^C is the defined uncertainty on objects motion.

Path construction using B-spline method

To describe the corresponding B-spline for local path generation, first the AUV model is demonstrated. An AUV has six degrees of freedom in its translational and rotational motion in earth-fixed and body-fixed coordinates,¹⁹ presented in Figure 1. The vehicle’s earth-fixed state variables is presented in equation (7)

Figure 1.

Quadratic two-dimensional B-spline curve by control points, where in (a) K = 3.5 and in (b) K = 6.

η : (X, Y, Z, φ, θ, ψ)

where X, Y, and Z are the AUV’s position in the earth-fixed coordinates; and φ, θ, and ψ are the Euler angles of roll, pitch, and yaw. The path planner in the proceeding research generates the potential trajectories ℘_i = {℘ ₁, ℘ ₂,…} using B-spline curves shaped according to placement of number of control points ϑ = {ϑ ₁, ϑ ₂, …, ϑ_i , …, ϑ _n } in the specified operation window. Placement of these points plays a substantial role in optimality of the path. Location of the control points ϑⁱ :(xⁱ, yⁱ, zⁱ ) in 3-D space should be confined to predefined upper Uⁱ _ϑ and lower Lⁱ _ϑ bounds in the Cartesian coordinates as given below

\begin{array}{l} \begin{array}{l} L_{ϑ (x, y, z)} = [(x_{0}, y_{0}, z_{0}), (x_{1}, y_{1}, z_{1}), ..., (x_{i - 1}, y_{i - 1}, z_{i - 1}), ..., (x_{n - 1}, y_{n - 1}, z_{n - 1})] \\ U_{ϑ (x, y, z)} = [(x_{1}, y_{1}, z_{1}), (x_{2}, y_{2}, z_{2}), ..., (x_{i}, y_{i}, z_{i}), ..., (x_{n}, y_{n}, z_{n})] \end{array} \\ x^{i} (t) = L_{ϑ (x)}^{i} + R a n d_{i}^{x} (U_{ϑ (x)}^{i} - L_{ϑ (x)}^{i}) \\ y^{i} (t) = L_{ϑ (y)}^{i} + R a n d_{i}^{y} (U_{ϑ (y)}^{i} - L_{ϑ (y)}^{i}) \\ z^{i} (t) = L_{ϑ (z)}^{i} + R a n d_{i}^{z} (U_{ϑ (z)}^{i} - L_{ϑ (z)}^{i}) \end{array}

\begin{array}{l} X (t) = \sum_{i = 1}^{n} x^{_{i}} B_{i, K} (t) \\ Y (t) = \sum_{i = 1}^{n} y^{_{i}} B_{i, K} (t) \\ Z (t) = \sum_{i = 1}^{n} z^{_{i}} B_{i, K} (t) \\ ℘_{x, y, z}^{i} = \sum_{x_{s}, y_{s}, z_{s}}^{| ℘ |} \sqrt{{(x^{_{i + 1}} - x^{_{i}})}^{2} + {(y^{_{i + 1}} - y^{_{i}})}^{2} + {(z^{_{i + 1}} - z^{_{i}})}^{2}} \end{array}

Equation (9) gives the mathematical presentation of the B-spline curve⁹ generation in which a blending function of B_{i, K} (t) and smoothness parameter of K are utilized to generate path curve coordinates X, Y, and Z for the AUV position at time step t along the generated potential path ℘.

PSO and its application to AUV routing and path planning

The PSO is a popular optimization algorithm that offers a fast computation for solving different complex and multi objective problems. Its process starts with a population of particles in which each particle is characterized with position χ_i and velocity υ_i that is updated iteratively. Particles correspond to candidate solutions in the search space and should be evaluated iteratively according to predefined cost functions. Particles memorize their previous state value χ(t − 1), their experienced best position of χ^P-best , and also the global best χ^G-best positions in the population. More detail can be found in the article by Kennedy and Eberhart.²⁰ Particle velocity and position are updated as follows

\begin{array}{l} υ_{i} (t) = ω υ_{i} (t - 1) + c_{1} r_{1} [χ_{i}^{P - b e s t} (t - 1) - χ_{i} (t - 1)] + c_{2} r_{2} [χ_{i}^{G - b e s t} (t - 1) - χ_{i} (t - 1)] \\ χ_{i} (t) = χ_{i} (t - 1) + υ_{i} (t) \end{array}

where c ₁, c ₂ and r ₁, r ₂ are acceleration coefficients and independent random numbers, respectively. The ω is the inertia weight and balances the local and global search. The PSO is used here for both AUV routing and path planning purpose as it is a strong algorithm for handling complex scaling and multi-objective problems. As this algorithm was developed to operate in a continuous space, it is appropriate for solving the path planning problem that is a continuous-natured problem. Furthermore, to adapt this algorithm for solving discrete problems such as knapsack or vehicle routing problem, this research proposes a priority-based feasible route generation approach on the underlying search space (provided in “Particle swarm optimization on AUV’s task assign-routing problem” section). These modifications increase the speed of the algorithm in finding optimum solution and prevent trapping in a local optima.

PSO and path planning approach

The path planning aims to generate the fastest collision-free path between two points. This research takes the advantages of the B-spline method and the PSO algorithm to generate desirable path curves, where each particle in the swarm is assigned by coordinates of a potential path. The position and velocity of the particles are assigned with the coordinates of the control points ϑ of the B-spline. As the PSO iterates, particles move toward their respective local attractor according to their individual and swarm search. The process of PSO-based path generation is provided in Figure 2. After candidate paths (solutions) are generated their cost/fitness should be evaluated, where in this study path cost function is defined proportional to the path time T_path-flight as follows

\begin{array}{l} \forall ℘, ℘ \approx \sum_{1}^{| ℘ |} ϑ_{j + 1}^{} - ϑ_{j}^{} \\ ℘_{x, y, z}^{j} = \sum_{x_{s}, y_{s}, z_{s}}^{| ℘ |} \sqrt{{(ϑ_{x (j + 1)}^{} - ϑ_{x (j)}^{})}^{2} + {(ϑ_{y (j + 1)}^{} - ϑ_{y (j)}^{})}^{2} + {(ϑ_{z (j + 1)}^{} - ϑ_{z (j)}^{})}^{2}} \end{array}

T_{path - flight} = \sum_{1}^{n} t_{i} = \sum_{1}^{| ℘ |} Γ_{3 D} {ϑ_{t_{i}}^{i}} = \sum_{1}^{| ℘ |} \frac{| ϑ_{i + 1}^{t_{i + 1}} - ϑ_{i}^{t_{i}} |}{| V_{AUV} |}

\begin{array}{l} \begin{array}{l} {Cost}_{℘} \approx min (T_{path - flight}) \\ s . t . \end{array} \\ \forall j \in {0, ..., | ℘ |} \Rightarrow ϑ_{j}^{t_{i}} \notin Θ (t_{j}) \cup Γ_{3 D} and j \notin \underset{N Θ}{\cup} Θ (Θ_{p}, Θ_{r}) \end{array}

where cost_℘ is the path cost function. It is assumed that the vehicle moves with constant linear velocity V_AUV . The generated ℘ is penalized for colliding with any obstacle Θ₍ _N _Θ ₎, where N_Θ is the number of obstacles. This process in general motivates particles toward the feasible solution space.

Figure 2.

PSO optimal path planning pseudo code. PSO: particle swarm optimization.

PSO and AUV routing

Regarding the combinatorial nature, AUV’s routing problem which is a combination of TSP and Knapsack problems, there should be a compromise between remaining time, maximizing number of higher weighted tasks, and guaranteeing on time completion of the mission. The AUV route planner simultaneously tends to determine the appropriate route in graph-like terrain while trading-off between maximizing the total collected weights along the route and satisfying available time threshold. The solution by the route planner generally contains optimum set of jobs/waypoints, in which the tasks are prioritized according to their weight. A general overview of the PSO mechanism on AUV routing is provided in Figure 3. Suitable coding of the particles by route solutions is the most critical factor affecting the algorithm’s efficiency and optimality of the generated solutions.

Figure 3.

The process of PSO on AUV route planning. PSO: particle swarm optimization; AUV: autonomous underwater vehicle.

Particle encoding (initialization phase of PSO route generation)

A particle in the proposed method corresponds to a feasible route vector including a sequence of jobs/waypoints. The solution vectors take a variable length with maximum size equal to the total number of existing waypoints in the graph. A feasible route must meet the following criteria:

It should be started and ended with the index of the predefined start and target waypoints.

It should not include connections (edges) that are not given in the graph.

It should not visit the same waypoint multiple times.

It should not visit an edge more than once.

It should not take longer than the maximum available time.

A priority-adjacency-based method has been applied in this study to produce feasible initial solutions/routes, in which guiding information is added to each waypoint of the graph at the initial phase. Waypoints are selected according to their corresponding adjacency relations in the graph and their priority value (the adjacency matrix (Ad) represents relations and edges in a graph) and to keep the solutions feasible some modifications have been done as follows:

The priority vector is initialized with random uniform value approximately U(−100, 100) and each waypoint in the graph takes a priority value from priority vector.

Visited waypoints in a route are assigned with a large negative priority value to ignore visited nodes.

The included edges in the route are excluded from the Ad.

Adjacency connections are used for adding waypoints to route, so that non-existing edges will be excluded in the route.

An example of the proposed feasible route generation process is proposed in Figure 4 using a sample graph with 18 waypoints and its corresponding Ad and priority array. In this process, the first waypoint is added to the route as the start position. Then the priority of the connected nodes to the first waypoint is considered (using Ad matrix), which in the example sample graph is the sequence of {2,3,4,5}, and the highest priority node is added to the sequence. This procedure is repeated until visiting the destination node (node 18 in this graph).

Figure 4.

Process of feasible route generation by topological information of a sample.

Termination of the PSO operation is defined according to completion of the iterations or when fitness of the generations get reduced iteratively. The important step in fitness evaluation is defining an efficient cost function, so that the algorithm tends to compute the cost value for each route to find the best fitted route with the minimum cost (given in “Global route optimality evaluation” section).

Adaptive route replanning

The local path planner operates inside the global route planner and concurrently tends to safely guide the vehicle through the waypoints. If the local path time (T_path-flight ) takes longer than the expected time for traversing the edge q_ij (T_Expected ) due to encountering unexpected changes in the environment, the initial route loses its optimality because of the wasted time and battery consumption; so the T_Avaliable is updated and route replanning is carried out to compute a new optimum route according to mission updates. In the replanning process, the visited edges are omitted from the graph and the search space shrinks. Then the current node is considered as the new starting waypoint for both planners.

Using such an adaptive route replanning compensates the time dissipation and improves the reactive ability of the vehicle considering the environmental changes. The replanning process is presented in Figure 5. To clarify this combinational process an example is provided in Figure 6. Considering the initial optimum route as the sequence {S-1-7-3-4-5-6-9-10-13-17-19-D} in Figure 6, the path planner tends to generate a trajectory to safely guide the AUV through the waypoints. The replanning condition (given in Figure 5) is investigated after each process of local path planner and in the case that replanning is required, the mentioned updates presented in Figure 5 are applied and the route planner is recalled to find a new optimum route considering mission updates (e.g. new optimum route:{9-8-10-16-D}). This process repeats until vehicle reaches the required waypoint.

Figure 5.

Proposed route replanning process.

Figure 6.

The process of route-path planning and replanning process in a sample operation network.

Global route optimality evaluation

The route cost is directly influenced by the cost of the generated local path Cost_℘. The route planner searches for an appropriate solution in the sense of the best composition of path, route, and task cost defined as follows

{Cost}_{Route} = | T_{Available} - \sum_{\begin{matrix} i = 0 \\ j \neq i \end{matrix}}^{n} l q_{i j} (C o s t_{℘ i j}) | + \sum_{\begin{matrix} i = 0 \\ j \neq i \end{matrix}}^{n} l q_{i j} \times w_{T_{i j}}, l \in {0, 1}

where, Cost_Route is the route cost that is defined as a function of Cost_℘.

Simulation

The main purpose of the simulation experiments in this article is evaluating the performance of entire combinational model in terms of increasing mission productivity (task assignment and time management) and guaranteeing safe maneuver during the mission. To validate the proposed strategy, first the efficiency of the local path planner is individually assessed; afterward, its performance in context of the global route planner is investigated.

Simulation results for PSO-based local path planner

During transition between two points, the local path plan effectiveness can be compromised by dynamic changes of the environment. The purpose of path planner is to minimize the path time, and to avoid collision. It is assumed the vehicles are moving with constant speed of 3 m/s. The operating environment is modeled as a realistic underwater volume covered by several uncertain static and suspended obstacles. Three different scenarios are simulated for evaluating the efficiency of the local path planner. In the first one, the AUV starts its operation in a static environment and it is required to pass the shortest collision-free distance. In the second scenario, the robustness of the method is tested in an environment covered by uncertain static obstacles. Finally, the terrain becomes more complicated by adding the floating objects into account. The complexity of the terrain is increased gradually to test the path planner’s performance in all probable conditions. The PSO is configured to run 100 iterations and 80 particles, with expansion–contraction coefficients of 1.5 and 2. The number of control points is set on 6. The performance of the algorithm for all scenarios proposed is shown in Figures 7 to 9 for different number of obstacles, where each obstacle is generated randomly according to the equations presented in “Path planning problem formulation” section.

Figure 7.

(a) The path planning performance in avoiding known static obstacles in the 1st scenario. (b) Iterative variation of the collision violation. (c) Iterative variation of path time. (d) Iterative variation of path cost.

Figure 8.

(a) The path planning performance in avoiding uncertain static objects in the 2nd scenario. (b) Iterative variation of the collision violation. (c) Iterative variation of path time. (d) Iterative variation of path cost.

Figure 9.

(a) The path planning performance in avoiding uncertain suspended objects in the 3rd scenario. (b) Iterative variation of the collision violation. (c) Iterative variation of path time. (d) Iterative variation of path cost.

The gradual growth of collision edges of each uncertain object is shown in Figures 8(a) and 9(a), in which the uncertainty growth is assumed linear with each iteration. As presented in Figures 7(b), 8(b), and 9(b), the algorithm efficiently manages the trajectory to eliminate the collision penalty within 100 iterations. It is evident from Figures 7(a), 8(a), and 9(a) that the algorithm accurately satisfies the collision constraints encountering all types of obstacles. The path travel time is an important performance index that is proportional to path cost and should be minimized. It is inferable from Figures 7(c, d), 8(c, d), and 9(c, d), the algorithm accurately tends to minimize path travel time and path cost over 100 iterations, while the performance of the algorithm is almost stable against the increasing complexity of the environment.

Simulation results for reactive global route planner

The main goal is to make maximum use of the mission time, increase the mission performance by optimum routing, ensure on time ending of the mission, and concurrently provide safe motion to the final destination. The route, as a sequence of arranged tasks, provides an overview of the operation area that an AUV should fly through. On the other hand, dynamic changes of the environment is covered by the path planner, which operates concurrently in an inner layer. The local path planner operates as an inner layer of the global route planner and the output of each planner concurrently feeds to the other one. The entire combinational scheme should be fast enough to cope with dynamic changes, handle environmental updates, and carry out prompt replanning to compute new order of tasks according to new updates. To this end, some performance factors of total violation, cost, CPU time, mission time, and remained time are investigated through six individual experiments to evaluate the performance and stability of the model in providing safe motion and beneficent task assignment. The operation graph is configured with 30 nodes and 985 edges involving a fixed set of 10 tasks specified with their priority and randomly distributed in 10 × 10 km² (x–y), 100 m (z) space. The total available time is set by T _Available = 9000 s = 2.5 h. The AUV starts its operation at point WP¹ and ends its operation at WP³⁰ . The terrain is modelled to be randomly covered by various uncertain objects. The PSO configured with the same initial conditions of the local path planner. This simulation is implemented on a desktop PC with an Intel i7 3.40 GHz quad-core processor using MATLAB® R2014a. The full process of one experiment out of the six separate missions (given by Figures 10 to 12) is explained in Table 1 (A and B) to clarify the operation flow of the proposed combinational strategy across all stages of a particular mission toward addressing the mentioned objectives.

Figure 10.

Performance of the combinational model in mission time management.

Figure 11.

Stability of the global route planner’s cost variation of and variation of total obtained weights in 6 individual experiments.

Figure 12.

Stability of the Global route and local path planner in computational time variation.

Table 1.

An overview of the process of the combinational model in one mission scenario.

A	Global route planner	Call no.	WP^S	WP^D	Task no	Route weight	Route cost	CPU time	T _Available	T _Route	Valid	Route sequence
		1	1	30	7	18	2.2097	76.15	9000	8597	Yes	1-23-16-28-3-15-17-30
		2	28	30	7	21	1.9647	68.61	6472.2	6118	Yes	28-18-9-3-24-7-29-30
		3	18	30	5	23	2.3386	70.81	5952.3	5612	Yes	18-5-25-21-8-30
		4	8	30	3	20	1.8659	67.16	1871.6	1693	Yes	8-20-7-30
		5	20	30	1	7	1.4903	59.07	884.5	819	Yes	20-30
B	Local path planner	Route ID	PP call	Edges		Violation	Path cost	CPU time	T _path	T _Expected		T _Available	Replan flag	PP flag
		Route-1	1	1-23		0.00000	0.328	36.31	1476	1514.3		7524	0	1
			2	23-16		0.00028	0.287	31.25	565	683		6959	0	1
			3	16-28		0.00000	0.743	44.38	486.7	333.8		6472.2	1	0
		Route-2	1	28-18		0.00000	0.109	39.6	519.6	376.3		5952.3	1	0
		Route-3	1	18-5		0.00000	0.120	39.60	1406	1492.3		4546.1	0	1
			2	5-25		0.00000	0.101	44.49	394.6	486.3		4151.5	0	1
			3	25-21		0.00000	0.360	41.45	1192.6	1345.3		2959.3	0	1
			4	21-8		0.00000	0.416	40.56	1087.3	900.3		1871.6	1	0
		Route-4	1	8-20		0.00000	0.319	53.93	986.8	847.8		884.5	1	0
		Route-5	1	20-30		0.00000	0.233	42.19	796.4	818.6		87.8	0	0

The mission commences with operation of the global route planner to produces a valid optimum route in order to take maximum use of available time (T _Route ≤ T _Available). Considering Table 1 (A), the initial global route includes seven tasks, weight of 18, and cost of 2.2097 with mission time of T _Route = 8597 (s); then, the local path planner generated shortest and safest path between the set of nodes listed in the initial route. Considering Table 1 (B), the local path planner generated a trajectory between the first pair of nodes (1-23) with total cost of the 0.328, and time of T _path = 1476, which is smaller than expected travel time T _Expected ₌ 1514.3. When T _path is smaller than T _Expected, the replanning flag is zero, which means that the initial route is still valid and optimum, so the vehicle is allowed to follow the next pair of waypoints included in initial optimum route. The T _Available gets updated after each operation of the local path planner. The second pair of waypoints (23-16) is shifted to the local path planner and the same process is repeated. However, path planning in (16-28) took longer than T _Expected, so the replanning flag turned on, the T _Available is updated and visited edges (1-12, and 23-16) are deleted from the graph. Afterward, the global route planner is recalled to produce a new optimum route from the current waypoint WP²⁸ to the WP³⁰ according to new updates. In the results shown in Table 1, the local path planner is called 10 times within five optimum routes. This synchronization among the global and local motion planners continues until vehicle reaches its destination (success) or T _Available gets a minus value (failure: vehicle runs out of battery). The final route passed by the vehicle in this mission through the 5 route replanning and 10 path planning is the sequence of waypoints including {1-23-16-28-18-5-25-21-8-20-30} with total cost of 1.878, total weight of 22, and total time of 8912. From simulation results in Table 1 (A), it is noted that in all cases route travelling time obtained by the PSO is smaller than total available time and the violation value for all solutions is equal to zero thus confirming feasibility of the produced route and that the model respects the defined constraints.

The best result for the model is completion of the mission with the minimum remained time (T _Remained) that means maximizing the use of available time. The results provided in Table 1 (A) confirm that the model acts efficiently in terms of maximizing mission productivity by making maximum use of the available time as T _Route approaches T _Available. Referring to Table 1 (B), the remaining time is 87.8 s out of the total mission time available T_Available = 2.5 h, which is considerably approached to zero. Considering that reaching the destination is the biggest concern for a vehicle’s safety, it is more important than maximizing the vehicle’s productivity, a big penalty value is assigned to the global route planner to strictly prevent generating routes with T_Route bigger than T_Available .

In this research, the computational time is another important performance factor that should be investigated for the path-route planner because they operate concurrently, thus a large computational time for either of them is detrimental to the routine flow of the whole system. The robustness of the model in satisfying the addressed objectives is evaluated by testing six missions through six individual simulations all with equivalent initial conditions based on realistic underwater mission scenarios. These results are presented in Figures 10 to 12.

From the simulation results given in Figure 10, it can be seen that the proposed architecture is capable of making maximum use of available mission time as apparently the mission time in all experiments approaches the T _Available and meets the above constraints denoted by the upper bound of 2.5 h, which presents the stability of the model in mission time management. It is evident from Figure 11 that the average cost variation of the global route planner in each experiment is centralized over the total cost of the final route produced in the corresponding mission. It is also noteworthy to mention from analyzing the results in Table 1 (A and B) that the proposed methodology takes a very short computational time which makes it highly suitable for real-time application. The stability of the variability of computational time for both global and local planners as shown in Figure 12 also confirms the applicability of the model for real-time implementation. More importantly, the violation percentage for both planners presented in Table 1 reveals the robustness of the model to the variations of the operation network parameters and environmental conditions, so that the vehicle can meet the dynamic challenges of the environment and guarantee safe deployment and on time completion of the mission.

Conclusion

This article focuses on developing a reactive combinational conflict-free task assignment method based on reactive global route planning and collision-free local path planning that ensures the consistent situational awareness of the environment and guarantees a real-time implementation. Exploiting a priori knowledge of the underwater environment, the global route planner generates a time-efficient route with best sequence of tasks to be carried out to ensure that AUV has a successful operation and reaches its destination on time as it is an obligatory requirement for vehicles safety. Along with an efficient route planner, a local path planner is produced in smaller scale to safely guide the vehicle through the specified waypoints in the global route with minimum time/energy cost. The employed PSO-based local path planner is efficient and fast enough to rapidly react to changes of the environment and generate a collision-free optimum path. Route replanning, meanwhile, is performed to reduce wasted time in dealing with unexpected changes of the environment and consequently promote robustness and reactive ability of the AUV. On the other hand, stability of the hybrid planner in time management is the most critical factor representing robustness of the method. The value of the remaining time upon completing the mission should be minimal but should not be equal to zero. Minimizing the remaining time maximizes the mission productivity. The results obtained from analyzing the six different missions, demonstrates the inherent robustness and effectiveness of the proposed scheme in enhancing a vehicle’s mission productivity and mission time management.

Footnotes

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) received no financial support for the research, authorship, and/or publication of this article.

References

Likhachev

Ferguson

Gordon

Stentz

Thrun

. Anytime dynamic A*: an anytime, replanning algorithm. In: ICAPS 2005 - Proceedings of the 15th International Conference on Automated Planning and Scheduling, 2005, pp. 262–271.

Carsten

Ferguson

Stentz

. 3D field D*: improved path planning and replanning in three dimensions. In: IEEE/RSJ International Conference on Intelligent Robots and Systems, 2006, pp. 3381–3386. DOI: 10.1109/IROS.2006.282516.

Petres

Pailhas

Evans

. Underwater path planning using fast marching algorithms. Oceans Europe Conf 2005; 2: 814–819.

Petres

Pailhas

Patron

. Path planning for autonomous underwater vehicles. IEEE Trans Robot 2007; 23(2): 331–341.

Zadeh

Powers

DMW

Sammut

. Differential evolution for efficient AUV path planning in time variant uncertain underwater environment. Robotics (cs.RO) arXiv:1604.02523.

Zadeh

Yazdani

Sammut

. AUV rendezvous online path planning in a highly cluttered undersea environment using evolutionary algorithms. Robotics (cs.RO). arXiv 2016:1604.07002.

Roberge

Tarbouchi

Labonte

. Comparison of parallel genetic algorithm and particle swarm optimization for real-time UAV path planning. IEEE Trans Ind Inform 2013; 9(1): 132–141.

Besada-Portas

DeLaTorre

DeLaCruz

. Evolutionary trajectory planner for multiple UAVs in realistic scenarios. IEEE Trans Robot 2010; 26(4): 619–634.

Nikolos

Valavanis

Tsourveloudis

. Evolutionary algorithm based offline/online path planner for UAV navigation. IEEE Trans Syst Man Cybern B Cybern 2003; 33(6): 898–912.

10.

Alvarez

Caiti

Onken

. Evolutionary path planning for autonomous underwater vehicles in a variable ocean. IEEE J Ocean Eng 2004; 29(2): 418–429.

11.

Kumar

. Exploring genetic algorithm for shortest path optimization in data networks. Global J Comput Sci Technol (GJCST) 2010; 10(11): 8–12.

12.

Zeng

Sammut

Lammas

Tang

. Efficient path re-planning for AUVs operating in spatiotemporal currents. J Intell Robot Syst 2015; 79: 135–153. DOI: 10.1007/s10846-014-0104-z.

13.

Zeng

Lammas

Sammut

. Shell space decomposition based path planning for AUVs operating in a variable environment. Ocean Eng 2014; 91: 181–195.

14.

Kwok

Driessen

Phillips

. Analyzing the multiple-target-multiple-agent scenario using optimal assignment algorithms. J Intell Robot Syst 2002; 35(1): 111–122.

15.

MahmoudZadeh

Sammut

Powers

Lammas

Yazdani

. Optimal route planning with prioritized task scheduling for AUV missions. In: IEEE International Symposium on Robotics and Intelligent Sensors, 2015, pp. 7–15.

16.

Zadeh

Powers

DMW,

Yazdani

. A novel efficient task-assign route planning method for AUV guidance in a dynamic cluttered environment. Robotics (cs.RO). arXiv 2016: 1604.02524.

17.

Higgins

. A dynamic tabu search for large-scale generalised assignment problems. Comput Oper Res 2001; 28(10): 1039–1048.

18.

Prestero

TTJ

. Verification of a six-degree of freedom simulation model for the REMUS autonomous underwater vehicle. MSc Thesis, Massachusetts institute of technology, Cambridge MA, 2001.

19.

Fossen

. Marine control systems: guidance, navigation and control of ships, rigs and underwater vehicles. Norway: Marine Cybernetics Trondheim, 2002.

20.

Kennedy

Eberhart

. Particle swarm optimization. In: IEEE International Conference on Neural Networks, Piscataway, 1995, pp. 1942–1948.

Toward efficient task assignment and motion planning for large-scale underwater missions

Abstract

Keywords

Introduction

Problem formulation of the AUV routing and local path planning problem

AUV routing problem

AUV local path planning problem

Path construction using B-spline method

PSO and its application to AUV routing and path planning

PSO and path planning approach

PSO and AUV routing

Particle encoding (initialization phase of PSO route generation)

Adaptive route replanning

Global route optimality evaluation

Simulation

Simulation results for PSO-based local path planner

Simulation results for reactive global route planner

Conclusion

Footnotes

Declaration of conflicting interests

Funding

References