|
|
|
A Revised Scatter Search Algorithm for Path Planning of Multiple UAVs
|
BAI Jie1,YANG Genke1,PAN Changchun1,SUN Kai2
|
(1.Automation Department, Shanghai Jiaotong University, Shanghai 200240, China; 2.School of Electronic Information and Control Engineering, Shandong Light Industry College, Ji’nan 250353, China)
|
|
|
|
Abstract The unmanned aerial vehicle (UAV) path planning problem in uncertain and adversarial environment is modeled as a vehicle routing problem (VRP). After that a revised hybrid algorithm based on scatter search optimization was proposed. First，with the prior surveillance and experiential evaluation, Bayes rule is used to compute the probability of threats of flight across each pair of neighboring points, and then a weighted graph can be generated based on the threat probability map in the given planning area．The original problem is transformed to be a VRP. Then, a hybrid routing algorithm is adopted to solve the VRP problem. The proposed algorithm incorporates simulated annealing (SA) method into scatter search (SS), such that it can take advantages of both the global search ability of SS and the local optimization capability of SA in order to get good paths. The proposed method can improve the quality of solutions while not incurring additional time. Finally, computational experiments were conducted to verify the method.
|
|
Received: 15 July 2010
Published: 28 February 2011
|
|
|
|
|
|
|
|
|
