Research on a Task Planning Method for Multi-Ship Cooperative Driving

doi:10.1007/s12204-019-2057-7

Abstract

Abstract: A new method for a cooperative multi-task allocation problem (CMTAP) is proposed in this paper, taking into account the multi-ship, multi-target, multi-task and multi-constraint characteristics in a multi-ship cooperative driving (MCD) system. On the basis of the general CMTAP model, an MCD task assignment model is established. Furthermore, a genetic ant colony hybrid algorithm (GACHA) is proposed for this model using constraints, including timing constraints, multi-ship collaboration constraints and ship capacity constraints. This algorithm uses a genetic algorithm (GA) based on a task sequence, while the crossover and mutation operators are based on similar tasks. In order to reduce the dependence of the GA on the initial population, an ant colony algorithm (ACA) is used to produce the initial population. In order to meet the environmental constraints of ship navigation, the results of the task allocation and path planning are combined to generate an MCD task planning scheme. The results of a simulated experiment using simulated data show that the proposed method can make the assignment more optimized on the basis of satisfying the task assignment constraints and the ship navigation environment constraints. Moreover, the experimental results using real data also indicate that the proposed method can find the optimal solution rapidly, and thus improve the task allocation efficiency.

Key words: multi-ship cooperative task allocation| path planning| multi-task| multi-objective| genetic ant colony hybrid algorithm (GACHA)

摘要： A new method for a cooperative multi-task allocation problem (CMTAP) is proposed in this paper, taking into account the multi-ship, multi-target, multi-task and multi-constraint characteristics in a multi-ship cooperative driving (MCD) system. On the basis of the general CMTAP model, an MCD task assignment model is established. Furthermore, a genetic ant colony hybrid algorithm (GACHA) is proposed for this model using constraints, including timing constraints, multi-ship collaboration constraints and ship capacity constraints. This algorithm uses a genetic algorithm (GA) based on a task sequence, while the crossover and mutation operators are based on similar tasks. In order to reduce the dependence of the GA on the initial population, an ant colony algorithm (ACA) is used to produce the initial population. In order to meet the environmental constraints of ship navigation, the results of the task allocation and path planning are combined to generate an MCD task planning scheme. The results of a simulated experiment using simulated data show that the proposed method can make the assignment more optimized on the basis of satisfying the task assignment constraints and the ship navigation environment constraints. Moreover, the experimental results using real data also indicate that the proposed method can find the optimal solution rapidly, and thus improve the task allocation efficiency.

关键词: multi-ship cooperative task allocation| path planning| multi-task| multi-objective| genetic ant colony hybrid algorithm (GACHA)

CLC Number:

TP 301

CHEN Yaojie* (陈姚节), XIANG Shanshan (项珊珊), CHEN Feixiang (陈飞翔). Research on a Task Planning Method for Multi-Ship Cooperative Driving[J]. Journal of Shanghai Jiao Tong University (Science), 2019, 24(2): 233-242.

References 31

[1]	LI J, SUN Q R, ZHOU M C, et al. A new multipletraveling salesman problem and its genetic algorithmbasedsolution [C]//IEEE International Conference onSystems, Man, and Cybernetics. [s.l.]: IEEE, 2013:627-632.
[2]	NECULA R, BREABAN M, RASCHIP M. Tacklingthe bi-criteria facet of multiple traveling salesmanproblem with ant colony systems [C]//IEEE InternationalConference on Tools with Artificial Intelligence.Vietri sul Mare, Italy: IEEE, 2015: 873-880.
[3]	CHIN T J, KEE Y H, ERIKSSON A, et al. Guaranteedoutlier removal with mixed integer linear programs[C]//IEEE International Conference on ComputerVision and Pattern Recognition. Las Vegas, NV,USA: IEEE, 2016: 5858-5866.
[4]	VIELMA J P. Mixed integer linear programming formulationtechniques [J]. SIAM Review, 2015, 57(1):3-57.
[5]	WANG X Y, CHOI T M, LIU H K, et al. Novelant colony optimization methods for simplifying solutionconstruction in vehicle routing problems [J].IEEE Transactions on Intelligent Transportation Systems,2016, 17(11): 3132-3141.
[6]	KUMAR S N, PANNEERSELVAM R. A survey on thevehicle routing problem and its variants [J]. IntelligentInformation Management, 2012, 4(3): 66-74.
[7]	MORADY R, DAL D. A multi-population based parallelgenetic algorithm for multiprocessor task schedulingwith communication costs [C]//IEEE Symposiumon Computers and Communication. Messina, Italy:IEEE, 2016: 766-772.
[8]	ZANDIEH M, KHATAMI A R, RAHMATI S H A.Flexible job shop scheduling under condition-basedmaintenance: Improved version of imperialist competitivealgorithm [J]. Applied Soft Computing, 2017, 58:449-464.
[9]	BARONI M D V, VAREJ?AO F M. A shuffled complexevolution algorithm for the multidimensional knapsackproblem using core concept [C]//IEEE Congresson Evolutionary Computation. Vancouver, Canada:IEEE, 2016: 2718-2723.
[10]	SAVI′C A, TOˇSI′C D, MARI′C M, et al. Genetic algorithmapproach for solving the task assignment problem[J].Serdica Journal of Computing, 2008, 2(2): 267-276.
[11]	ALGETHAMI H, PINHEIRO R L, LANDA-SILVA D.A genetic algorithm for a workforce scheduling androuting problem [C]//IEEE Congress on EvolutionaryComputation. Vancouver, Canada: IEEE, 2016: 927-934.
[12]	GUO L Z, SHAO G J, ZHAO S G. Multi-objective taskassignment in cloud computing by particle swarm optimization[C]//International Conference on WirelessCommunications, Networking and Mobile Computing.Shanghai, China: IEEE, 2012: 1-4.
[13]	SUN C L, JIN Y C, CHENG R, et al. Surrogateassistedcooperative swarm optimization of highdimensionalexpensive problems [J]. IEEE Transactionson Evolutionary Computation, 2017, 21(4): 644-660.
[14]	ALAYA I, SOLNON C, GH′EDIRA K. Ant colony optimizationfor multi-objective optimization problems[C]//IEEE International Conference on Tools with ArtificialIntelligence. Washington, USA: IEEE, 2007:450-457.
[15]	WANG Z N, LI S, WANG Y, et al. The researchof task assignment based on ant colony algorithm[C]//International Conference on Mechatronics andAutomation. Changchun, China: IEEE, 2009: 2334-2339.
[16]	QIN L S, WANG J W, LI H X, et al. An approachto improve the performance of simulated annealing algorithmutilizing the variable universe adaptive fuzzylogic system [J]. IEEE Access, 2017, 5(99): 18155-18165.
[17]	LIN Q Z, CHEN J Y, ZHAN Z H, et al. A hybrid evolutionaryimmune algorithm for multiobjective optimizationproblems [J]. IEEE Transactions on EvolutionaryComputation, 2016, 20(5): 711-29.
[18]	QIAN Y P, XIA J, LIU T Y. Task assignment schemebased on contract net [J]. Journal of System Simulation,2011, 23(8): 1672-1676 (in Chinese).
[19]	ZHANG T, LIU Y, ZHANG Y J, et al. PSO-ACSmixed algorithm for vehicle routing problem withsimultaneous pick-up and delivery [J]. Journal of SystemSimulation, 2010, 22(3): 777-782 (in Chinese).
[20]	PREMALATHA K, NATARAJAN A M. Hybrid PSOand GA for global maximization [J]. InternationalJournal of Open Problems in Computer Science andMathematics, 2009, 2(4): 597-608.
[21]	LIN L, SUN Q B, WANG S G, et al. Researchon PSO based multiple UAVs real-time task assignment[C]//Chinese Control and Decision Conference.Guiyang, China: IEEE, 2013: 1530-1536.
[22]	SUI Z Z, PU Z Q, YI J Q. Optimal UAVs formationtransformation strategy based on task assignment andparticle swarm optimization [C]//IEEE InternationalConference on Mechatronics and Automation. Takamatsu,Japan: IEEE, 2017: 1804-1809.
[23]	WANG Q, ZHANG A, SONG Z J. Simulation studyon improved discrete particle swarm optimization algorithmfor multiple UAV cooperation task assignment[J]. Journal of System Simulation, 2014, 26(5): 1149-1155 (in Chinese).
[24]	DU J Y, ZHANG F M, YANG J, et al. Cooperativetask assignment for multiple UCAV using particleswarm optimization [J]. Control and Decision, 2012,27(11): 1751-1755 (in Chinese).
[25]	LI W, ZHANG W. Method of tasks allocation of multi-UAVs based on particles swarm optimization [J]. Controland Decision, 2010, 25(9): 1359-1363 (in Chinese).
[26]	SU F, CHEN Y, SHEN L C. UAV cooperative multitaskassignment based on ant colony algorithm [J].ActaAeronautica Et Astronautica Sinica, 2008, 29(Sup 1):184-191 (in Chinese).
[27]	SHIMA T, RASMUSSEN S J, SPARKS A G, et al.Multiple task assignments for cooperating uninhabitedaerial vehicles using genetic algorithms [J]. Computers& Operations Research, 2006, 33(11): 3252-3269.
[28]	EDISON E, SHIMA T. Integrated task assignment andpath optimization for cooperating uninhabited aerialvehicles using genetic algorithms [J]. Computers & OperationsResearch, 2011, 38(1): 340-356.
[29]	YAO M, WANG X Z, ZHAO M. Cooperative combattask assignment optimization design for unmannedaerial vehicles cluster [J]. Journal of University of ElectronicScience and Technology of China, 2013, 42(5):723-727 (in Chinese).
[30]	OZCAN C Y, HACIOMEROGLU M. A path-basedmulti-agent navigation model [J]. Visual Computer,2015, 31(6/7/8): 863-872.
[31]	CHEN Y J, HUANG L W. An automatic multiobjectivecollision avoiding approach [C]//IEEE 11thConference on Industrial Electronics and Applications.Hefei, China: IEEE, 2016: 134-139.