Research On Coordinated Task Planning Of Multiple Unmanned Vehicles In Multi-point Dynamic Aggregation Task

Coordination of multiple unmanned vehicles is a hot research topic in the field of artificial intelligence.Multiple unmanned vehicle systems(MUVSs)have great advantages on the suitability,robustness and expansibility for different tasks due to their distributed characteristics on time,space,and information.Therefore,the MUVSs are widely used in a lot of fields,such as military,traffic and transportation systems,industrial management and so on.This paper studies the task planning problem for MUVSs to cooperately execute complex tasks which can be formulated by a general model,namely,Multi-Point Dynamic Aggregation(MPDA)task.In the MPDA task,a number of task points are located in different places and their states change over time.Multiple unmanned vehicles aggregate to these task points and execute the tasks cooperatively to make the states of all the task points change to0.According to the characteristics of the task planning problem of MUVS in the MPDA task,a multi-permutation encoding/decoding strategy is designed to solve the task planning problem in this paper.In this strategy,firstly the solution of the task planning problem is represented as the access order of all the robots to visit all the task points.The order can be encoded as multiple permutations.Each perputation correspondings to a task execution process of each unmanned vehicle in the MPDA task.Therefore,the task planning problem in this paper is converted to a multi permutation combinatorial optimization problem which can be solved by heuristic methods,intelligent optimization methods,branch and bound,hybrid methods,and even enumeration methods if the problem scale is small.In this paper,a kind of decoding algorithm which is based on time sequences is proposed first,and each task planning coding can be decoded to the corresponding task execution process of MUVS.The computational experiment results show the feasibility and rapidity of the decoding algorithm.Considering the the demand on the rapidity and solution quality in the actual problem decision-making,three kinds of problem solving methods for solving the task planning problem of MUVS in MPDA task are then proposed by use of this decoding algorithm.For the purpose of ensuring the rapidity of problem solving,an ensemble algorithm that combines six rule-based heuristic algorithms to determine the satisfied task plans for any MPDA tasks is proposed.And in order to increase the solution quality of the task planning problem,tabu search(TS)algorithm and estimation of distribution algorithm(EDA)are then adopted to search for the optimal planning coding of the MPDA task.Tabu search algorithm is an efficient single-point search method,which can avoid repetitive search through taboo operation and can increase the probability of getting the global optimal solution.Estimation of distribution algorithm is a widely used population-based search method,which can to predict the optimal search area by sampling the search spaces and statistical learning.Thus EDA has strong global search ability.The implementability and efficiency of the three kinds of optimization algorithms are verified by a large number of computational experiments of MPDA benchmarks under different problem scales.Computational experiment results show that the three algorithms can generate feasible solutions for solving small scale problems.And with the increase of problem scale,each algorithm has its own advantage under different real-time requirements.The ensemble of rule-based heuristic algorithms has a big advantage in computation rapidity,and with the increase of the problem scale,this algorithm achieves a better balance between solution quality and computation cost.However,tabu search algorithm and estimation of distribution algorithm have more advantages in solution quality.And these two algorithms also have their own advantages to solve different task planning problems with different characteristics and scales.Therefore,the rule-based ensemble algorithm can be utilized to solve the task planning problems with higher rapidity requirement of the decision-making.And the tabu search algorithm and the estimation of distribution algorithm can be utilized to solve the task planning problem with higher solution quality requirement of the decision-making in the case of sufficient computation time.Based on the study of the task planning problems of MUVS in the MPDA task,this paper provides effective methods for MUVSs to execute MPDA tasks.