基于加权k-均值聚类与粒子群优化的多航迹规划

摘要

For the problem of unmanned aerial vehicle's multiple routes planning in complex environment, a new method which combines particle swarm optimization (PSO) with weighted k-means clustering is proposed. Each particle represents a route. A weighted k-means clustering algorithm is used to classify the particles to several subgroups. Each subgroup carries out a feasible route optimization. Ultimately multiple different feasible routes are obtained. The traditional k-means clustering algorithm is improved by an exclusion mechanism which generates the initial cluster centers. In order to describe the diversity of unexpected threats distribution in actual environment, route nodes are weighted by the probability of unexpected threat. The weighted k-means clustering algorithm is proposed. Simulation results show that the proposed method can effectively obtain multiple feasible routes.%针对复杂环境下的无人机多航迹规划问题,提出了将粒子群优化(particle swarm optimization,PSO)算法与加权k均值聚类算法相结合的规划方法.每个粒子表示一条航迹,采用加权k-均值聚类算法对粒子进行分类,得到多个粒子子群,在每个子群内部进行一条可行航迹的优化,最终得到多条不同的可行航迹.对传统k-均值聚类算法进行改进,采用排挤机制产生初始聚类中心,针对实际环境中突发威胁的分布不均性,在聚类过程中,对航迹节点按照所在区域突发威胁的出现概率进行加权,提出了加权k-均值聚类算法.仿真实验表明,所提出的方法能够有效地得到无人机的多条可行航迹.