AIRCC PUBLISHING CORPORATION
Task Allocation and Path Planning for Network of Autonomous Underwater Vehicles
Bychkov Igor, Kenzin Maksim and Maksimkin Nikolay
Matrosov Institute for System Dynamics and Control Theory,
Siberian Branch of the Russian Academy of Science,
Cooperative multi-objective missions for connected heterogeneous groups of autonomous underwater vehicles are highly complex operations and it is an important and challenging problem to effectively route these vehicles in the dynamic environment under given communication constraints. We propose a solution for the task allocation and path planning problems based on the evolutionary algorithms that allows one to obtain feasible group routes ensuring well-timed accomplishment of all objectives.
autonomous underwater vehicle; mission planning; heterogeneous group routing; evolutionary algorithm.
The rapid evolution of the subsea technologies in recent years has significantly expanded the scope of autonomous underwater vehicles (AUV) implementation, which includes the usage of distributed groups of underwater robots to perform multi-objective missions, as simultaneous use of multiple vehicles can improve performance and reduce mission time. During such large-scale missions, a number of different underwater works and operations should be accomplished collaboratively by AUVs within specified water area. In this regard, the effective coordination of AUVs network is crucial for the likelihood of mission success. Thus, the upper level of the group control system that is responsible for the allocating tasks between robots and both route- and path- planning is coming to the fore.
In general, the problem of task allocation and path planning is vehicle routing problem (VRP) under specific spatiotemporal constraints imposed by the uncertain dynamic nature of water environment and by the inaccuracy of the measuring devices. In many real cases, like patrolling and guarding, taking samples and measurements, etc., certain underwater tasks require not the single but the series of periodic attendances by AUVs at scheduled intervals. The mission-planning problem in such complex cases obtains features of such VRP variations as routing with time windows and periodic routing with new complex requirements and restrictions, which are aimed to a more accurate simulation of real-world problems .
Indeed, in real underwater missions vehicles in the fleet may differ not only by their dynamic characteristics but also by their functionality (onboard equipment) which make them able to perform only specific sub-sets of tasks among all tasks of the mission. The factor of the vehicle fleet heterogeneity, while making the mission planning more challenging, at the same time gives more flexibility to the group performance capabilities with different combinations of vehicles being able to accomplish the mission. In addition, communication is a critical aspect of vehicle cooperation, especially in the dynamic and uncertain environment, and must not be trivialized, as underwater communication is difficult, slow and limited in the range .
Currently, the state of the art in mission planning is dominated by single AUV operations using preplanned trajectories with offline post-processing of the data collected during the mission. Multiple cooperative vehicle systems hold great promise for use in large-scale oceanographic surveys and it is a problem of considerable practical interest to effectively route the heterogeneous group of AUVs in multi-objective missions of long-duration .
In this paper, we propose an approach to task allocation and path planning for the heterogeneous group of AUVs to solve the complex-mission planning problem as a new variation of vehicle routing problem, which is to find a feasible and efficient group route under specific spatiotemporal constraints. To do this, we combine the work of genetic algorithms with newly specialized heuristics and advanced techniques
In general, the complex multi-objective mission of AUVs group is to visit and accomplish (perform some underwater works) the set of tasks (objectives) under scheduling requirements. Each task has its own recommended periodicity for visiting by AUVs and requires a certain set of instrumentations like sonars, sensors, manipulators etc. to be accomplished. The vehicles in the group have a different onboard equipment, making each AUV available for attending only a certain subset of mission objectives. In addition, the regular communication sessions within the entire group are required to answer the dynamic nature of mission in order to permanently maximize the group efficiency in ever-changing conditions. The mission-planning problem here is to find a group route ensuring, as far as a possible, regular and well-timed accomplishment of the majority of mission tasks . It is formally defined as follows.
Fig.1. Schematic representation of the multi-objective misson for the heterogeneus group of three AUVs with four different kinds of tasks.
Fig.2. AUVs group functioning during a single period of planning
sessions within the entire group. Communication stability requirement arises due to the dynamic nature of underwater missions: some unexpected changes may occur in real time, making it necessary to adjust the current route (re-plan) in order to maximize the group efficiency in new conditions. Among the events that require route re-planning are adding new tasks or removing existing ones; change of task’s equipment requirements or periodicity; adding new vehicles; equipment functional loss or even full AUVs breakdowns.
The effectiveness of the group work is determined, in the first place, by the regularity of scheduled tasks accomplishments. Situations, when AUV arrives too late and delays performing of corresponded works are undesirable and should be penalized via efficiency criteria. Thus, the routing problem is to find a feasible group route that provides the minimum time of AUVs late attendances up to the end of the mission.
To solve the group routing problem in described conditions the following features has to be considered:
Given these features, we suggest the following decomposition approach: to divide the process of mission implementation on finite time periods (periods of planning) with communication sessions at the end of each period. In this case, the AUVs group operational sequence on a single period of planning can be represented as the block scheme on Fig. 2.
According to this scheme, each vehicle computes to find the best group route for the next period of planning while following their previously planned routes on the current period. Full data alignment at the end of each period allows vehicles to receive all information obtained by other AUVs, to update the actual state of the group and to exchange their best-found solutions. Then, the most effective route among suggested is selected to become current on the new planning period for the whole group. This approach also allows to parallelizing all calculations among the vehicles in a natural way.
Now we define a penalty for the single delay of the task accomplishment:
Function (3) insufficiency is what it considers penalties on only those tasks that are being included in the group route and only at the moments of AUVs attendances if any. For this reason, it is needed to consider an additional function, which would care not about well-timed accomplishment of tasks within the route as (3), but would estimate the level of “completeness” of all tasks at the end of group movement:
Fig.3. Graphical representation of the “hotness” function
Where is the end of current planning period. Function (4) also indirectly normalizes all single vehicle routes durations.
The final efficiency criteria for the group route is:
Where is the set of all feasible (in terms of equipment requirements) and communicatively stable group routes.
The timestamps sequent required in (1) and (4) cannot be calculated explicitly since the idle time for each AUV on each task of its route depends not only on previous actions of this specific vehicle, but also on actions of all other vehicles of the group up to that moments. To unravel all timestamps of AUVs actions on their route we use special time-line table (Table I) that is algorithmically filled using following scheme.
Set «Current order number» = 1 for all AUVs;
Fill «Current task» according to the current group state;
While (Route is not finished)
Define i as AUV with minimal «Expected time»;
Work with i-th String;
Define j = «Current order number»;
Define m as j-th task in the route of i-th AUV;
If («Action» = Move)
Write: Action = Work;
Write: «Expected time» = «Expected time» + s(m);
If («Action» = Work)
t(m) = «Expected time»;
Save t(m) as the Timestamp to the Sequence list;
j = j + 1;
Write: «Current order number» = j;
Define m as j-th task in the route of i-th AUV;
Write: «Task number» = m;
Write: Action = Move;
Define d as path length from i-th AUV to task m;
Define t1 = d/v(i) as i-th AUV travel time;
Define t1 = «Expected time» + t1;
Define t2 = t(m)+p(m) as next schedule time for m;
Define t = max(t1, t2);
Write: «Expected time» = t;
Define t(r) = max (all «Expected time») as Period end time;
It is also should be noted that the function (1) is constructed in such way, that “hotness” of tasks with lesser periodicity grows faster. In that way, delaying of attendance would happen preferably with tasks of the biggest periodicity.
Now that we have the final criteria (5) in the explicit form, we can use it as the objective function to compare the efficiency of different group routes.
Table 1.Example of The Time-Line Table In Process
For a broad combinatorial class of vehicle routing problems, there are no algorithms solving it in polynomial time, which leads us to the class of approximation algorithms allowing to obtain rational sub-optimal solutions in low computational time. Evolutionary methods have proven to be efficient on the standard VRP and on a number of other variants like VRP with time windows . Noteworthy is the contribution of Prins , who introduced an important methodological element, namely the solution representation for the VRP as a Travelling salesman problem (TSP) tour without delimiters .
Their main advantage of evolutionary algorithms (EAs) is the ability to find solutions for poorly structured problems and problems with complex constraints, as EAs require a relatively small amount of information about the nature of the problem. An Essential drawback of evolutionary methods is very strong speed and efficiency dependence on the construction and improvement heuristics being used.
Another layer of complexity is implied by a “bad” neighborhood structure of the described multi-objective routing problem, making it difficult to allocate and find qualitative and feasible solutions, as they may not be in the neighborhood of other feasible high-quality solutions in the search space. Until recently, however, the most successful contributions to this class of problems were based on the serial explorations of neighborhoods .
We propose a hybrid evolutionary approach featuring specialized genetic operators, advanced local search heuristics and solution improvement techniques to address both the expectable large-size of the problem and complex spatiotemporal constraints that primarily arise from the AUVs heterogeneity. The block diagram for the proposed evolutionary hybrid algorithm is shown on Fig.4.
Fig. 4. The block diagram of hybrid evolutionary approach with colored blocks of advanced procedures and author’s modifications.
The construction of the initial population of solutions is the first and crucial step to achieve good rational solutions rapidly. The aim of this step is to construct a set of feasible only chromosomes ensuring both covering a significant portion of the search space and containing a variety of good solutions. We propose to achieve this requirement by use of three different construction heuristics: random sequential insertion and two parallel insertions in the rate of 40/30/30.
The first heuristic is “random insertion with no duplicates” and it generates AUVs routes sequentially: at first, the full route for the first vehicle, then for the second, etc. The starting task for each vehicle is randomly selected from the entire set of affordable tasks. All subsequent tasks are selected in the same manner but with the additional requirement to be different, if possible, from the previous task of this vehicle.
The next two constructive heuristics are based on the time-oriented nearest-neighbor insertion heuristic by Solomon  and are parallel, i.e. they build routes for all robots in the group simultaneously. Both parallel heuristics use the “ultimate” schedule without any delays to form the ordered list of tasks to pick and insert into routes of different vehicles. For the first heuristic of “time-greedy insertion“, the probability to select each AUV for the current task is inversely proportional to the number of tasks already assigned to this vehicle, while for the second “quality-greedy insertion” this probability depends also on the distance between current task and the last task in the route of each AUV. The use of two parallel heuristics here provides the population diversity not only among the solutions built with the random insertion, but also within the set of more qualitative solutions. It should be noted, that on each iteration of construction heuristics only those AUVs are considered, which has all the required onboard equipment.
The constructed populations are evaluated then with the objective function (5). According to the results of ranking, the tournament selection chooses a set of solutions for procreation and mutations. We suggest using a number of specialized genetic operators that guarantee the ultimate feasibility of offspring solution in terms of equipment requirement: two different variants of crossover and a multimode mutation.
The first crossover is called “one-plus-one-point” and it is a modification of the standard two-point crossover with the additional rule to choose randomly only the first point: the second one has then defined automatically within the route of the same vehicle as the first point.
The second crossover is “focused on inheritance” and it is based on the “adaptive memory” crossover proposed in . The proposed crossover identifies the common characteristics of the parental individuals and copies them to the offspring-solution, which is a kind of adaptive memory procedure. Initially, the two solutions are selected. If there are common parts between the solutions, then these common parts are inherited to the offspring; all parts left empty inherit the values from the best solutions in the adaptive memory or from some random solutions in the population. In each iteration, the adaptive memory is updated based on the best solutions found. The structure of this crossover also ensures the feasibility of all resulting chromosomes.
The proposed multimode mutations consist of four operators: add a new task into the route, remove the task from the route, change the task within the rote to another task, swap two tasks within the route of the same AUV. When mutation operators are implied, all changes are also verified on admissibility. Group communication stability is also guaranteed by the special verifying procedure. If it is necessary, some virtual tasks can be added to the mission automatically to assist group gathering at the end of the planning period.
The mechanisms of parallel populations with migration (island model) and elitism provide faster algorithm convergence rate while preventing premature convergence to local optima. The procedure of clone removal allows preserving the diversity of new populations on each iteration of the algorithm.
In order to further improve our newly received individuals, the deterministic heuristic search techniques of 2-opt exchange and 𝜆-interchange are applied periodically to the whole population for a deeper exploitation.
To improve the efficiency of a population creation procedure, all probabilistic genetic parameters are changed constantly at the end of each iteration of EA. Being determined by the current efficiency of the genetic operators these changes allow algorithm to adapt to the different situations on different steps of processing. In general, the adaptation mechanism is to keep track of the paths, which lead to the solution improving more often than others, and to increase their probabilities for the next generation of solutions. The scheme of the ant colony optimization algorithm allows to implement such an adaptation in a natural way. The implementation of the adaptation mechanism may significantly increase the speed of computing in those cases when some genetic operators begin to work significantly better than others do .
The high efficiency of the suggested approach is shown through a series of simulation studies in the modeling framework “AUV Mission Planner”. To do this we have expanded our simulation framework “AUV Mission Planner” to test and work out our newly proposed heterogeneous group routing problem with new complex constraints and restrictions. We have also updated our path-planning algorithms for “AUV Mission Planner” to a near-optimal hierarchical path finding (HPA*)  to achieve almost 30% improvement on the computational speed when generating AUVs trajectories.
The described evolutionary algorithm has demonstrated the ability to generate rapidly a high-quality set of rational and feasible solutions and to effectively improve the whole population to meet the required conditions. The algorithm is proved to be used for efficient multi scale routing of various automated vehicles as a high-level control algorithm. Its structure and new heuristics can be used not only to efficiently route the heterogeneous robot groups during multi-objective missions, but also to address other complex statements of VRP and its modern variations.
We have evaluated the impact of each of the embedded heuristic and procedures on the rate and quality of the algorithm convergence (Table II).
Table.2. Average impact of different heuristics (in %)
Due to the complex and non-polynomial nature of the problem, we have been able to find global solutions only for a group of small sized (with a number of permutations not exceeding ) experimental problems that have been generated randomly. For this series of experiments, our hybrid evolutionary algorithm has obtained the global solution in 42% of launches with a 2.34% average deviation of resulted solutions from optimal ones.
The problem is still open to be expanded with new entities, parameters and constraints, such as new various types of objectives, a necessity in battery charging etc.
The research is supported by the Russian Science Foundation (project no. 16-11-00053).
 M.Yu. Kenzin, I.V. Bychkov, and N.N. Maksimkin, “Hybrid evolutionary approach to multi-objective mission planning for group of underwater robots,” Communications in Computer and Information Science, Vol. 549: Mathematical Modeling of Technological Processes, pp. 73-84, 2015.
 M. Sozer, M. Stojanovic, and J. G. Proakis, “Underwater acoustic networks,” IEEE Journal of Oceanic Engineering, vol. 25(1), pp. 72–83, 2000.
 Y. Deng; P.-P. Beaujean, E. An, and E. Carlson, “Task allocation and path planning for collaborative AUVs operating through an underwater acoustic network,” Journal of Robotics, Vol. 2013(483095), pp. 1-15, 2003.
 M.Yu. Kenzin, I.V. Bychkov, and N.N. Maksimkin, “A hybrid approach to solve the dynamic patrol routing problem for group of underwater robots,” 39th International Convention on Information and Communication Technology, Electronics and Microelectronics (MIPRO), pp. 1114-1119, 2016.
 O. Braysy, and M. Gendreau, “Vehicle routing problem with time windows, part I: route construction and local search algorithms,” Transportation science, Vol. 39, No.1, pp. 104–118, 2005.
 C. Prins, “A simple and effective evolutionary algorithm for the Vehicle Routing Problem,” Computers & Operations Research, Vol. 31(12), pp. 1985-2002, 2004.
 T. Vidal, T.G. Crainic, M. Gendreau, N. Lahrichi, and W. Rei, “A hybrid genetic algorithm for multidepot and periodic vehicle routing problems,” Operations Research, Vol. 60(3), pp. 611-624, 2012.
 M.M. Solomon, “Algorithms for the vehicle routing and scheduling problems with time windows constraints,” Operations Research, Vol. 35(2), pp. 254–265, 1987.
 M. Yong, “Solving vehicle routing problem with time windows with hybrid evolutionary algorithm,” In proceeding of Intelligent Systems (GCIS), 2010 Second WRI Global Congress on, Vol. 1, pp. 335-339, 2010.
 A. Botea, M. Müller, and J. Schaeffer, “Near optimal hierarchical path-finding,” Journal of Game Development, Vol. 1(1), pp. 7–28, 2004.