曼哈顿无人飞机交通监控部署

1、曼哈顿无人飞机交通监控部署摘要本文讨论分析了曼哈顿城市MAV交通监控部署问题，分别在四种不同的情况下求解出了最优巡航方案。 在Task1中，首先选取区域交通路口为节点，给出MAV的监控路段和节点选择方法; 然后讨论在无续航里程约束条件下，将MAV监控问题转化为TSP问题，并运用模拟退火算法予以求解; 而在有续航里程约束条件下，运用 Kmeans聚类方法，将监控区域划分成若干子区，进而将该问题转化为无续航里程约束的MAV监控部署问题，最后对上城区的监控进行实证分析，给出了最优部署方案。 在Task2中，在Task 1的基础上求解在30%的MAV无法使用的情况下如何实现巡航监控。首先将正常监控区域

2、简化为其质心，比较无法正常巡航区域内的节点与各个质心的距离，对这些节点进行重新分配；然后在重新划分的区域内仍旧将问题转化为TSP问题；最后运用Task1中的模型进行求解。 在Task3中，首先根据与主干道相交道路的数量确定其权值；然后建立加权欧氏距离的K-means聚类模型进行聚类，对区域内的交通路口进行划分；最后在每一个监控子区内，又是一个TSP问题，同样用模拟退火算法可以求解最佳的巡航路径。在Task4中，根据题目要求参与MAV巡航部署的和没有参与的人都不能确切知道MAV的巡航方案，即MAV的巡航方案具有一定的动态性（随机性）。本文首先确定巡航应当满足的条件以及方案评价体系；然后通过随机贪

3、心算法求解足够多的可行静态解，最后引入时间切片叠加的思维，在静态解的基础上应用深度优先搜索算法，将求解动态巡航问题转化为在有向连通图中寻找使目标函数达到最大的约束环路问题，最终求得动态MAV巡航方案。关键词：MAV巡航 TSP问题 时间切片 加权K-means聚类1、 问题重述2、 模型假设1. 假设MAV的巡航速度100Km/h；2. 假设MAV可以急转弯；3、 模型建立与求解Task 1 基于旅行商模型的MAV监控部署1、 问题分析MAV需要对整个曼哈顿的交通进行监控，主要是对区域的路段进行监控，尤其是十字路口。根据监控历程是否超出飞机飞行距离，提出无人飞机在有无续航里程约束条件下的交通监

4、控部署方法。本文选取区域十字路口为节点，给出MAV的监控路段和节点的选择方法; 在无续航里程约束条件下，将无人飞机的交通监控问题转化为旅行商问题，并运用模拟退火算法予以求解; 在有续航里程约束条件下，运用 Kmeans聚类方法，将无人飞机的监控区域划分成若干子监控区，从而将该问题转化为无续航里程约束的无人飞机交通监控部署问题。2、 模型建立2.1 监控节点和监控路段的选择根据道路的交通安全水平评价，本文将MAV的交通监控对象分为节点和路段二类。目前，国内外对道路的交通安全状况进行了深入研究，得到了道路交通事故发生分布的一般特征。发现交通事故多发生于交通路口等地方。因此，本文选择交通路口作为监控

5、节点。监控路段的选择，区域内的所有交通道路均为监控路段，路段长度的计算采用定长法，即不考虑各个道路的交通量、限速、道路质量，仅考虑道路的实际长度。2.2无里程约束的无人飞机路线规划当无人飞机的飞行距离很长时可不考虑其飞行里程的约束，在确定其监控对象后，规划其飞行路线: 无人飞机从基地出发，遍历这些节点、路段，然后再飞回基地，在此过程中，无人飞机将实时监控图像传回交通监控中心。该问题类似 于旅行商问题，即无人飞机从基地出发，遍历每个节点、路段，且只经过一次，路径的选择目标是要求无人飞机的巡航路径最短。本文将路段抽象成为具有一定里程的节点，进行数学建模，如图1所示。监控路段 监控节点 MAV巡航路

6、径图1 监控路段抽象为节点示意图 假设监控网络中有个交通监控对象，是第个和第个监控对象之间的距离，无人飞机的巡航路线规划模型为:其中： 目标函数是使MAV的总巡航距离最短，公式(1)保证无人飞机仅到达监控对象一次; 公式（2）保证无人飞机仅离开监控对象一次。无里程约束的无人飞机路线规划问题类似于旅行商问题，该问题属于NP完全问题。2.3 有里程约束的监控小区划分当无人飞机的飞行距离有限且监控范围较大时，所需的无人飞机巡航里程可能超过其最大飞行里程，且监控时间较长，此时需要考虑无人飞机监控小区的划分，配置多架无人飞机进行交通监控。通过监控小区的划分，一方面可满足无人飞机的最大飞行里程要求，另一方

7、面可缩小单架次无人飞机的监控范围，提高交通监控的响应速度，从而将有里程约束的问题转换成为无里程约束问题。无人飞机监控小区划分的方法为: 根据无人飞机监控点、路段的空间分布，对监控对象进行聚类，实现监控小区划分。在监控小区划分的过程中，不断增加监控小区数量，保证每一监控小区有一架无人飞机进行交通监控.设有监控对象其中每个监控对象有2个空间坐标，即:；引入K means方法将监控对象划入若干小区内。考虑到曼哈顿地区道路交通监控对象在空间上的分布特征，以及无人飞机的最大飞行里程的限制，监控小区数量的划分上限设，其中表示向上取整。2.4部署方案的评价将无人飞机监控区域划分成为不同的侦察子区域，并在每个

8、子区域部署一架无人飞机，则不同的子区域划分对应着不同的无人飞机侦察代价，因此，本文提出2个指标评价无人飞机的部署效果。（1） 总巡航距离：（2） 监控时间标准差：其中；为划分的子区域数量; 为无人飞机在第个子区域的巡航距离;为无人飞机在第个子区域的巡航时间。指标1表示所有的无人飞机巡航距离之和; 指标2表示所有无人飞机巡航时间的标准差; 这2个指标用于衡量部署无人飞机的成本和使用协同性。从直观上讲，无人飞机的数量越多，则平均监控时间变短，交通监控的响应速度就越快，同时无人飞机的购置成本也在增加。另一方面，部署多架无人飞机后，总巡航距离和监控时间的协调性会发生动态的变化，此时需要根据交通监控的需

9、求做出权衡。3、 模型求解 经查阅，整个曼哈顿地区属于有续航差约束的情景，由于总巡航距离较长，监控时间将会较长，且超出许多无人飞机的最大飞行距离，因此可进行监控小区的划分，在此，本文以曼哈顿上城区进行实证分析。 上城区的交通道路如图2，其中代表城市的交通道路，代表交通路口。图2 曼哈顿上城区城市交通图结合该区域交通道路特征，建立平面直角坐标系。读取各个节点的坐标。运用Kmeans聚类方法将该路网划分为27 个监控小区。表1给出了划分结果。表1 运用Kmeans聚类方法将该路网划分为27 个监控小区数目12345678910111213141516171819202122232425262728

10、293031234567 运用Kmeans聚类方法将该路网划分为27 个监控小区每个小区配置一架无人飞机(假设巡航速度为100 km/h，则最大续航里程为500 km) ，每个小区内的无人飞机监控问题转化为无续航里程约束的TSP 问题，并用模拟退火算法求解，不同UAV 监控小区的无人飞机总巡航距离、监控时间对比情况如图3所示。图3不同MAV监控小区监控时间（单位：h）与总的巡航距离对比图（单位Km）由图3可知，随着无人飞机监控小区数量的增多，总巡航距离呈动态变化，划分为1个监控小区时总巡航距离最小，为760 km; 划分为6个监控小区时总巡航距离最大，为881 km。由图3可知，平均监控时间随

11、着小区数量的增加而下降，划分为2个监控小区时平均监控时间为1.8 h，划分为7 个监控小区时平均监控时间为0.3 h，监控的响应速度大为提高。同时通过计算得到，监控时间的标准差随着小区数量的增加而动态变化，划分为3个监控小区时标准差最大，为0. 74 h，各小区的无人飞机监控协调最差，划分为6 个监控小区时标准差最小，为0. 13 h，此时各小区的无人飞机监控协调最好。 综合以上分析，在曼哈顿上城区划分6个监控子区域最为合适，满足题中所要求城市每个角落保持在15分钟内被监控，同时监控时间的标准差最小，所有MAV的协调性最高。至此，在各个子区域则转化成为一个TSP（旅行商）问题。在MATLAB

12、中运用模拟退火算法求解无人飞机最短巡航距离。模拟退火算法的参数设置为: 初始温度为10000 ，冷却速度为0. 99，最大迭代次数为10000 次。此时的监控小区划分及无人飞机的飞行路径如图4所示。当需要进一步提高无人飞机的监控响应速度时，则需要继续增加无人飞机的监控小区并配置更多的无人飞机。图4 6 监控小区及无人飞机飞行路径 基于此，本文求解出了曼哈顿上城区飞机监控部署方案，用同样的方法可以确定其他区域的MAV部署。其他区域的监控部署见附录1。Task 2 基于最短距离的节点划分模型1、 问题分析在Task 1中将城市交通的有历程约束的巡航转化为无里程约束巡航，本文继续以上城区进行实证分析

13、，求解在30%的MAV无法使用过的情况下如何实现巡航监控。将正常监控区域简化一点，即其质心，比较无法正常巡航区域内的交点与各个质心的距离，对于某一节点而言，将其划入与质心的距离最短的质心所代表的区域，对于距离相等的节点，先将该节点归入对应的多个区域，通过计算多个区域的巡航时间，若存在某一加入该节点后的某一区域巡航时间比其他区域巡航时间段，则该节点应该归入巡航时间短的区域。本文以区域3、区域4无法正常巡航进行实证分析。2、模型建立与求解设可以正常巡航的的区域为,将该区域简化为质点记，记无法正常巡航区域内的各个节点的坐标，。计算得到质心、节点坐标如图5。图5 正常巡航区域的质心坐标与无法正常巡航区

14、域内的节点坐标根据已知条件，可以计算出这些无法正常巡航区域内的各个节点与正常巡航区域中心坐标的距离 根据中计算的各个节点到质心的距离，各个节点的划分区域如表2所示。表2 无法正常巡航区域内的各节点重新划分后的所属区域情况区域编号所包含节点11,12,13,148，9,1018,17,22，15,16,24,23根据表2中各正常巡航区域重新划入的节点，将问题再次转化为旅行商问题，在各个重新划分的子区域内运用模拟退火算法求解出MAV的最佳巡航路径。如图6所示。图6 重新规划后的监控小区及无人飞机飞行路径 最后可以得出当区域3、区域4无法正常巡航时剩余的MAV巡航范围及路径。当遇到某一个节点到多个质

15、心的距离相等时，先将该节点划分到各个质心所代表的区域，然后用同样的方法求出解，最后比较巡航时间，将节点归入巡航时间最短的质心所代表的区域。 同理，可以用同样的方法确定曼哈顿其他区域的交通在紧急状况下MAV的部署方案。根据不用的紧急情况确定不同的部署方案，进而可以确定在此情况下MAV的巡航监控范围。Task 3 基于交通道路加权的MAV巡航改进模型1、 问题分析尽管所有地区都是平等的，但是有些地区更为重要。城市的交通主干道总是和一些较小的道路纵横交错，一条主干道与其他道路相交的越多则一定程度上表明该条主干道上的交通量越大，即具有较高密度的乱穿马路的人，因此这些地区应该加强巡逻，同时对于一些交通量

16、少的交通主干道，则可以适当减少巡航监控的频率。由此可以根据与主干道相交道路的数量确定其权值，在确定权值以后，建立加权欧几里得距离K-means聚类模型进行聚类对区域内的交通路口进行划分，在每一个监控子区内，则又是一个旅行商的问题，同样用模拟退火算法可以求解最佳的巡航路径。2、 模型建立于求解2.1 基于加权的欧氏距离K-means聚类模型交通道路的加权根据上文分析，本文将主干道与其相交的道路数目作为该条道路的权，如图7，与主干道相交的道路有，由此确定主干道的权为7。 表示交通路口，表示主干道图7 道路的加权示意图 以此方法可以得到其他道路的权值。本文选取上城区的交通道路进行实证分析，以此阐明如

17、何基于交通道路加权的MAV巡航改进模型。图8给出了曼哈顿上城区的各条道路的加权值。图8 曼哈顿上城区的各条道路加权值交通路口的加权欧几里得距离在图论中通常二点之间的距离进行比较，一般情况下欧氏距离计算式为：其中的坐标。而本题涉及到加权，即对每个变量赋予权重，那么加权的欧几里得距离为其中是节点所连接道路的权。在进行聚类时合理地运用加权欧氏距离，对改进聚类结果能起到较好的效果。 一下是基于加权欧几里得距离的K-means聚类算法的一般过程： 算法输入：聚类个数，以及个节点集合； 算法输出：满足方差最小的标准的个聚类； 算法步骤：（1） 从个节点对象中任意选择个对象作为初始聚类中心；（2） 根据每个

18、聚类中所有对象的均值（中心对象），计算样本集中每个对象与这些中心对象的加权欧几里得距离，病根据最小的加权欧氏距离重新对相应对象进行划分；（3） 重新计算每个（有变化）聚类的均值（中心对象）；（4） 循环执行（2），（3），直到每个聚类不再发生变化为止。 根据以上对算法的设计和对曼哈顿城市交通图的分析，借助MATLAB进行计算，最终求的在加权情况下，上城区监控区域的划分。表9给出了输出的监控区域划分结果。表3 基于加权欧氏距离的K-means节点聚类划分数目12345678910111213141516171819202122232425262728293031234562.2 基于TSP的MA

19、V巡航部署模型运用Kmeans聚类方法将该路网划分为26 个监控小区每个小区配置一架无人飞机(假设巡航速度为100 km/h，则最大续航里程为500 km) ，每个小区内的无人飞机监控问题转化为无续航里程约束的TSP 问题，并用模拟退火算法求解，得到在各个子区的巡航轨迹。在得到各个子区巡航轨迹只有，根据中提出的对不同巡航路径的评价指标，即无人飞机总巡航距离、监控时间，对各个不同情况进行评价分析，以找出最为合理地子区划分。表给出了相关结果。表10不同监控子区的的评价分析监控子区数目23456最大巡航时间1.8h1.6h0.66h0.66h0.31h最小巡航时间1.6h0.66h0.42h0.08

20、h0.07h总巡航距离760Km820Km 820Km800Km860Km监控时间标准差0.58h0.74h0.44h0.29h0.15h根据题目要求，城市的部分地区有较高密度的乱穿马路者，这些地区应该在每5分钟巡航一次，而另一些地区则只需要每隔20分钟巡航一次，因此各个监控子区的最大巡航时间应该小于20分钟，最小巡航时间应该小于5分钟，由表3可以看出，符合这一条件至少需要将上城区划分为6个子监控区，而且在划分为6个子区时所有MAV的总巡航距离最大，这意味着MAV监视的范围就越大，同时6个子区的监控时间标准差最小，也就是说在此情况下，所有MAV的协调性最好，综合分析，将监控区域划分为6个子区已

21、经符合题目要求，如果再多划分一个子区势必增加一架MAV，继而增加监控成本。图9给出了，上城区6个子监控区的划分以及各个子区域的MAV巡航轨迹。图9 6个子监控区的划分以及各个子区域的MAV巡航轨迹最后，运用同样的方法可以将整个曼哈顿进行监控子区的划分，在各个子区均看做是TSP问题。TASK 4 基于时间切片叠加的MAV动态部署模型1 问题分析题目要求从MAV的角度考虑，做到对每个人都公平，即参与MAV巡航部署的和没有参与的人都不能确切知道MAV的巡航方案，这就要求MAV的巡航方案具有一定的随机性。使所有人都无法掌握MAV的巡航规律。该问题可以理解为求解MAV的动态巡航方案问题。本文通过一些必要

22、简化首先确定巡航发难应当满足的条件以及方案的评价体系，通过随机贪心算法求解足够多的可行静态解，并引入时间片叠加的思维在静态解的基础上应用深度优先搜索算法，将求解动态巡航问题转化为在有向连通图中寻找使目标函数达到最大的约束环路问题，最终求得动态MAV巡航方案。2 模型建立于求解2 模型建立于求解2.1 MAV巡航方案评价体系的建立为了巡航方案的优化选择，本文定义4个评价巡航方案的指标，分别为抵达第个交通路口的平均时间，最大巡航死角时间，巡航合理性，整个巡航方案的巡航总里程。MAV抵达交通路口的平均时间：假设在所有交通路口为，现在要求向派遣一架MAV，距离该点最近的MAV设为，之间的距离为，MAV

23、赶往该节点的速度为，则平均时间可以表示为；最大巡航死角时间：本文定义某个节点的巡航死角时间为在巡航过程中没有处在监控范围内的时间之和，则最大巡航死角时间从整体上体现了MAV对城市内各条街道的覆盖情况，为了避免出现巡航死角时间，应该是巡航的尽可能地寻遍城市的各个交通路口，以体现巡航的全面性和整体性。巡航合理性：在不同权重的地区，MAV的配置应该与权重相适应，第个交通路口的权为，记整个巡航方案中单位时间内第个交通路口出现MAV数量的平均值为故有：则的定义为其中，。 总巡航距离：某一部署方案所有MAV巡航距离的总和。记单个MAV巡航距离为则总巡航里程为：将上述四个指标分别用如下方法进行标准化：最后将

24、四个指标综合，得到综合评价指标为2.2MAV巡航静态方案求解 MAV巡航可以分为静态巡航和动态巡航二种情况，静态方案可以理解为MAV在各自的监控区域进行监控，即可以认为负责监控该区域的MAV绕着该区域的质心进行监控，而动态监控是指所有MAV按照一定的计划在城市内动态的巡航。动态巡航方案可以看做是由一个时间序列上多个静态巡航方案组成的。本文引入时间片段叠加模型来从静态方案构造动态方案。模型的主要思想为：求解出一系列的满足基本条件的静态解，将这些静态解看做是一个一个的切片，通过构建合理地组合模型将这些切片堆砌起来形成最终的动态解。 首先定义：若在城市交通图中节点上空有MAV，则记，否则为0，若MA

25、V可以再要求时间内从节点到节点则记，否则为0，若点在某一MAV监控范围内，则，否则为0.之间的关系可以表示为：即若巡航方案要求达到的覆盖率为，交通路口数为，则静态模型可以表示为：这是一个0-1规划问题，可以使用随机贪心算法求解。2.3 时间切片叠加算法的MAV动态巡航求解 事实上，MAV的动态巡航过程可以看做是连续时间点上静态方案的叠加，即动态巡航的MAV部署在每一刻都可以看作是一个满足基本条件的静态配置，而动态巡航过程正是由这些时间切片堆叠起来的，因此，我们引入时间片度叠加的思想，利用大量满足基本条件的静态解为基础，以评价指标函数为目标函数求动态部署方案。图10是该思想的示意图，每一层代表一

26、个时间点MAV的配置情况。图10 时间切片叠加算法示意图在用之前所述的静态求解模型生成大量可行解的基础上，时间切片叠加模型的核心问题是要在备选的静态中选择正确的时间切片并给出正确的时间叠加顺序。 首先，对于给定的两个静态解，本文给出一个标准来确定他们之间是否能够作为相邻的时间切片，为了描述静态解之间的差异程度，本文定义了两个静态解之间的距离，如果两个静态解具有相同的节点数和MAV数，同一个MAV在两个方案之间会有一定的距离，即定义为所有MAV的距离中的最大值，可以确定出一个阈值，当时，认为对应的两个方案是可以作为连续时间片的。在此基础上，我们可以建立一个加权的无向连通图模型来描述动态巡航方案求

27、解问题如图11所示。其中每个节点表示一个由之前模型生成的备选静态方案，另一条边的权重表示对应两个方案之间的距离，如果能从图中找到一个有向回路，且回路中每两个相邻节点都满足时，即找到了一个可行的动态方案，也就是说，所有可行的方案均可以为该连通图中的一个“连续”的回路所表示.例如, 假如为100m，下图中有4个备选静态方案构成的连通图, 则下图中红色回路即表示一个动态解方案, 在该方案中, 所有车辆依次在静态方案中的对应位置上。图11 由静态方案求解动态方案示意图对于可行的动态方案, 显然综合评价指标的值越大, 该巡逻方案越优秀. 因此我们以综合评价指标为目标函数, 根据以上思想, 时间片叠加算法

28、可以转化为在一个有向图中寻找一个带约束回路使综合评价指标函数达到最大的组合模型, 描述如下：给定阈值和无向图，为顶点集,为边集, 每个顶点用"表示, 含义为一个静态解，表示两个静态解之间的距离, 则有，表示从到转移的评价值(此处为两静态解内所有MAV移动距离之和).经过定性分析可以发现, 若使得评价函数达到最大, 则在求解过程中需要满足方案中所有MAV移动距离之和尽可能大. 则间题可以转化为: 求解中较大回路，其中，且最大化。综合上述分析，求求解动态解过程已经转化为无向图求最大(较大) 环的问题.广泛使用的图的深度优先遍历即可在很短的时间内求得间题的解,这里我们采用之前部分提出的综合

29、评价指标作为目标函数.该算法思想描述如下: 假设给定图的初态是所有顶点均未曾访问过. 在中任选一顶点为初始出发点(源点), 则深度优先遍历可定义如下:首先访问出发点,并将其标记为已访问过;然后依次从出发搜索的每个邻接点。若未曾访问过, 则以为新的出发点继续进行深度优先遍历, 直至图中所有和源点有路径相通的顶点(亦称为从源点可达的顶点) 均已被访问为止;若曾被访问过, 则找到一个环, 这个环由和在遍历树中的公共祖先出发分别到和路径上所有的边以及边组成.若此时图中仍有未访问的顶点, 则另选一个尚未访问的顶点作为新的源点重复上述过程, 直至图中所有顶点均已被访问为止。 2.4 模型检验与评价本文继续

30、选取曼哈顿上城区的交通图进行实证分析。设方案满足的设方案需满足的条件为在任一时刻, 地图上90%的区域必须分别在最近的MAV控制区内,控制区的范围为附近MAV15分钟内能够到达. 我们使用时间片叠加算法求出了巡逻方案,结果显示, 该地区巡逻需要5架MAV。 同理，运用时间切片叠加法可以求解出曼哈顿其他地区的MAV动态部署方案。4、 模型优缺点分析在Task1中，本文选取区域十字路口为节点，给出MAV的监控路段和节点的选择方法; 在无续航里程约束条件下，将无人飞机的交通监控问题转化为旅行商问题，并运用模拟退火算法予以求解; 在有续航里程约束条件下，运用 Kmeans聚类方法，将无人飞机的监控区域

31、划分成若干子监控区，从而将该问题转化为无续航里程约束的无人飞机交通监控部署问题。但是本文仅实现了对各个交通路口进行监控，而对交通道路的监控有待进一步完善。在Task2中，本文基于Task 1中将城市交通的有历程约束的巡航转化为无里程约束巡航的方法，继续以上城区进行实证分析，求解在30%的MAV无法使用过的情况下如何实现巡航监控。将正常监控区域简化一点，即其质心，比较无法正常巡航区域内的交点与各个质心的距离，对于某一节点而言，将其划入与质心的距离最短的质心所代表的区域，对于距离相等的节点，先将该节点归入对应的多个区域，通过计算多个区域的巡航时间，若存在某一加入该节点后的某一区域巡航时间比其他区域巡航时间段，则该节点应该归入巡航时间短的区域。模型缺点在于本文将所有正常巡航的区域简化为质心，从而导致模型结果误差较大；在转化为TSP问题求解时认为每个节点都是等权的，存在一定的不合理性。在Task3中，根据与主干道相交道路的数量确定其权值，在确定权值以后，建立加权欧几里得距离K-means聚类模型进行聚类，对区域内的交通路口进行划分，在每一个监控子区内，则又是一个旅行商的问题，同样用模拟退火算法可以求解最佳的巡航路径。但是同样仅实现了对各个交通路