1. 引言
随着无人机(Unmanned Aerial Vehicle, UAV)技术的迅速发展,其在民用和军事应用中的重要性日益增加,包括环境监测、无线通信、安全搜救等领域 [1] 。其中,使用无人机进行城市巡检任务具有成本低廉、操作简单、机动灵活、安全高效、视野良好等优点,而且无人机更容易与人工巡检相融合,成为了日常巡检手段 [2] [3] 。在城市巡检任务中,如何提升无人机路径规划能力,已然成为学界和业界关注的热点问题 [4] 。
在无人机巡检路径规划的现有研究中,研究者们提出的算法可以大致归纳为优化算法和智能算法两大类,以解决效率优化 [5] 、避障处理 [6] 、任务调度 [7] 以及动态适应性 [8] 等关键问题。其中,优化算法依据特定的优化策略,搜索最优或者次优路径,如遗传算法 [9] 、人工蜂群算法 [10] 和粒子群优化 [11] 等,这些方法在处理大规模问题时可能会遇到局部最优和计算复杂性的问题。而智能算法,尤其是深度学习 [12] 和强化学习 [13] [14] [15] ,在路径优化中展示了独特优势,其能够通过与环境的交互学习实现优化路径选择,从而满足巡检无人机对自主决策和适应性的需求。
然而,上述方法都没有涉及巡检点的风险等级冲突性和风险损失动态性的分析:一方面,当多个风险等级较高(涉及大量的人员安全和经济价值损失)的巡检点同时具有较高的安全事件发生概率时,存在巡检冲突问题;另一方面,巡检点的人员数量和经济价值随着时间变化(例如办公楼巡检点的人员数量会不同时段会不同,仓库巡检点的货物储备不同时段也不同),因此具有风险损失动态性,这给实时巡检决策的风险动态规避带来挑战。
为此,本文设计了一种基于风险损失分析的多无人机路径规划方法,旨在提升多无人机在巡检中的协同作业效率和动态风险规避能力。具体的,首先,该方法定义了巡检点的风险等级和损失计算方法;然后,该方法设计了一种巡检点聚类算法,根据巡检点之间的风险等级相异性和地理位置相近性对巡检点进行聚类,将不同的聚类分配给不同的无人机,避免风险等级相同的巡检点的访问冲突问题,并优化巡检路径长度;最后,该方法提出了一种基于强化学习的路径规划算法,根据实时的风险损失和巡检开销来计算奖励函数,以引导无人机的实时巡检路径规划,兼顾了动态风险规避和巡检效率。
2. 无人机巡检系统模型
2.1. 问题描述及假设
本文考虑一种多无人机城市巡检的场景,巡检范围为Z,在巡检范围内有N个位置固定的待巡检点,所有巡检点的集合为,其中,巡检点
有以下属性:位置坐标
、人员数量
、经济价值
以及安全事件发生概率
。系统中有M台无人机,所有无人机的集合为
。多台无人机从同一基地出发,基地用
表示,依次访问所有巡检点,完成对每个巡检点实际情况的数据采集,最终返回基地。
在该系统模型中,将一天划分为K个等长的时段,所有时段的集合为
。在本文中,将无人机完成一次完整的巡检任务的总时长控制在一个时段内。在一个时段
内,巡检点
的人员数量和经济价值分别为该时段下的人员数量和经济价值的预测值,分别用
和
表示,安全事件发生概率为该时段下每个时刻的预测值,用
表示,其中
。
为便于问题分析建模,本文针对研究问题做出以下合理假设:1) 假设每台无人机始终在同一高度飞行与悬停,其高度由H表示。2) 假设每台无人机在飞行过程中的飞行速度为常数
。3) 假设整个巡检过程中无人机能量充足,即不考虑无人机充电情况。
2.2. 问题定义
本文采用四维矩阵
记录无人机在巡检时段
内的飞行路径,其中,
的值表示
时刻
是否从
飞到
,如果该巡检路径存在,则
,否则
,表示为:
(1)
本文对系统中的相关风险损失值作出以下定义,用
表示
在巡检时段
内的风险等级,即巡检综合价值,其计算方式表示为:
(2)
其中,和
为权重参数,
和
分别为对
和
归一化之后的值。
在
时刻的风险损失值用
表示,其计算方式表示为:
(3)
系统在
时刻的风险损失值用
表示,其定义为当前时刻系统中未被访问的巡检点风险损失值之和,用
表示
时刻未被访问的巡检点的下标集合,
的计算方式表示为:
(4)
系统的总风险损失值用
表示,其定义为系统在巡检过程中各时刻的风险损失值累计之和,其计算方式表示为:
(5)
由于环境中各巡检点是分开的,因此采用
行
列矩阵
来记录每两个点之间的距离。用
表示无人机
从
飞到
的时间成本,其计算方式表示为:
(6)
用
表示
飞往已分配的所有巡检点花费的时间,其计算方式表示为:
(7)
本文的研究目标是为无人机巡检规划出一条能够及时发现安全隐患以最小化系统的总风险损失值的路径,并且在此过程中使得完成任务的总耗时尽可能少。因此,本文将系统总风险损失与巡检总时长的加权和作为多无人机执行巡检任务的系统总成本,最小化系统总成本以实现研究目标,用
表示系统总成本,其计算方式表示为:
(8)
其中,
和
为权重参数,
和
分别为对
和
归一化之后的值。
表示巡检的总时长,由于多台无人机同时进行巡检,使用系统中无人机完成任务耗时最大的时长作为巡检总时长。
巡检任务的条件约束相关公式描述如下:
1) 巡检点访问冲突约束。多台无人机应避免同时对同一巡检点进行访问,即对于任意给定的巡检点,同一时刻只有一台无人机可以飞到该点并从该点起飞,表示为:
(9)
2) 无人机数量约束。选择执行巡检任务的无人机数量不大于无人机总数,其中无人机从同一基地起飞,表示为:
(10)
3) 访问顺序约束。在任务执行的过程中,每台无人机都应该对巡检点按顺序逐一访问。用数组
来记录每个点的访问顺序,每个元素的值
表示
访问
顺序的索引值。由于无人机直接从同一基地起飞,每台无人机的索引顺序
为1,即
。对于其他巡检点,如果
从
飞到
,则
的访问顺序比
多一个,即
。由于分配给每台无人机的巡检点数量都不大于总巡检点个数,因此每个巡检点的顺序索引值都小于或等于N + 1,表示为:
(11)
本文所涉及到的主要变量符号及含义如表1所示。
3. 基于聚类和强化学习的多无人机路径规划算法
本文的多无人机路径规划算法分为两个阶段,分别为聚类划分阶段和路径规划阶段,算法的整体架构如图1所示。首先,通过聚类算法解决多个高风险巡检点同时访问冲突的问题。然后,通过强化学习算法解决无人机实时路径规划问题。通过本文算法的设计,实现降低多无人机执行巡检任务的系统总成本的目的。
3.1. 聚类划分阶段
聚类划分阶段,为了解决多个高风险巡检点被同时访问冲突的问题,本文在设计聚类算法时考虑将风险等级较高的巡检点划分在不同的群组中,实现同一群组内的各巡检点风险等级差异化。同时,为了降低巡检时间成本,需要均衡每台无人机访问群组的时间,本文在设计聚类算法时考虑将距离相近的巡检点划分在同一群组。
为了兼顾上述两个目标,本文设计了一个综合考虑巡检点之间的风险等级差异和距离相似的巡检相关性函数,基于该函数实现对巡检点的聚类划分。具体地,巡检点
和
之间的巡检相关性函数
表示为:
(12)
其中,
和
为权重参数,
和
分别为
和
归一化之后的值。具体来说,
表示集群聚类中心点
和非中心点
之间的风险等级的差异值,
表示聚类中心点
和非中心点
之间的距离。
的计算方式表示为:
(13)
其中,将巡检点
的巡检综合价值
作为巡检点的风险等级值,
表示聚类中心
对应集群内所有巡检点综合价值的平均值。
的计算公式表示为:
(14)
其中,
和
分别为
和
的位置坐标。
本文的聚类算法计算流程如表2所示。
Table 2. Clustering algorithm based on inspection correlation function
表2. 基于巡检相关性的聚类算法
3.2. 路径规划阶段
经过聚类划分阶段后,将为每一个聚类群组分配一台无人机进行后续巡检任务,例如,为群组
分配无人机
进行后续巡检任务。本文根据环境中动态变化的风险损失值设计了强化学习算法模型的奖励函数,为无人机规划每个时刻的巡检点访问顺序,实现及时发现安全隐患的效果,同时尽可能降低巡检时长,以最大限度地降低系统总成本。
3.2.1. 无人机巡检路径规划强化学习模型
在本文的无人机巡检任务场景中,需要为每台无人机训练路径规划策略,因此无人机可以被视为强化学习模型中的智能体。在无人机巡检的场景中,由于环境中的风险损失信息随时间变化,很难获取状态转移概率矩阵,因此本文考虑采用无模型的强化学习。假设无人机
负责群组
的巡检任务,群组
中巡检点的数量为
,满足
,其中关于状态、动作和奖励函数的定义如下:
1) 状态
:无人机
只知道其自身位置信息以及其被分配的群组
的信息,包括群组中各巡检点的位置、风险损失值以及访问状态。将这些环境中的动态信息设置在状态中,t时刻的状态
定义为:
(15)
其中,
为无人机t时刻所在位置的向量,
,其中无人机的高度为常数
,即
;
为无人机在t时刻与集群内各巡检点的距离向量,本文用无人机当前的位置坐标的
和
分量与巡检点之间的欧氏距离作为无人机与巡检点的距离,即
,其中
表示无人机在t时刻与巡检点
之间的距离;
为t时刻集群内每个巡检点的风险损失值的向量,即
,其中
表示t时刻巡检点
的风险损失值;
为t时刻集群内每个巡检点的访问状态的向量,用0表示未被访问过,1表示已被访问,即
。
2) 动作
:无人机的动作为选择集群中的巡检点,定义为:
(16)
对于时刻
,无人机根据状态
执行动作
表示无人机从当前位置以速度
向指定的目标巡检点直线飞行。
3) 奖励函数
:为了最小化系统总成本,需要对无人机的动作进行价值评估。基于优化目标,本文提出了即时奖励函数,表示为:
(17)
其中,
表示
时刻无人机执行完动作之后的奖励,
表示
时刻系统风险损失值,
表示
时刻无人机路径飞行的总耗时,
和
分别表示风险损失和时长的权重参数,
和
为正整数,分别用于对无人机完成巡检任务给予奖励和对巡检点重复访问给予惩罚。通过以上奖励函数的设计,引导无人机快速完成巡检任务,并且在此期间实现最小化系统总成本的目的。
3.2.2. AM-DQN算法
由于本文设计的无人机巡检路径规划强化学习模型的动作空间为离散动作,并且是一种无模型的强化学习。因此本文通过对DQN进行改进,提出了一种基于AM-DQN (Action Masking Deep Q-learning Network)的无人机路径规划算法。算法的架构如图2所示。
为了使无人机尽快完成一次巡检任务,本文在强化学习模型的奖励函数中设计了对重复访问动作的惩罚。此设计在一定程度上避免了无人机对刚刚访问巡检点的重复访问,但是在实际操作中,由于无人机的动作空间为聚类群组中所有的巡检点,导致其在进行动作选择时不可避免地对已经访问的点进行选择。因此本文将动作掩码机制加入到强化学习的动作选择中 [16] ,过滤掉不可用的动作,避免无人机对环境采用无效的动作。AM-DQN通过对当前状态下网络Q值进行掩码操作,将无效动作的Q值修改为趋于无穷小的值,在通过argmax进行动作选取时,这些被掩码屏蔽的动作将不会被选中。
Figure 2. AM-DQN algorithm architecture diagram
图2. AM-DQN算法架构图
算法包含两个神经网络,即估计值网络和目标值网络。用
表示t时刻的目标值网络参数,则t时刻目标值
的计算方式如下:
(18)
算法的动作选择采用
策略,用
表示最小探索因子,
表示探索因子衰减速率,
表示训练周期,其中探索因子衰减更新公式如下:
(19)
AMDQN算法训练过程如表3所示。
Table 3. AM-DQN based path planning algorithm for UAV inspection
表3. 基于AM-DQN的无人机巡检路径规划算法
4. 实验与结果分析
4.1. 实验参数设置和目的
4.1.1. 实验参数设置
本文的模拟实验从一个真实的无人机巡检场景迁移,考虑一个5 km × 5 km的城市巡检范围,在该城市范围中随机分布若干个位置固定的巡检点,系统由一个无人机基地、多台无人机以及多个巡检点组成。实验所用服务器的CPU为英特尔酷睿i5-13490F,内存为32GB,GPU为NVIDIA GeForce TRX 4060 Ti,利用PyTorch深度学习框架实现算法中的神经网络部分,利用Python语言实现强化学习环境部分的编写。详细的实验参数设置如表4所示。
4.1.2. 实验目的
本文的实验目的包括以下三个方面:
1) 为了验证本文在路径规划阶段所提出的AM-DQN算法具有更高的收敛性与学习效率,我们对所提出的算法和传统的DQN算法 [13] 对无人机执行城市巡检任务的路径规划进行了训练。其中设定当前单个无人机负责的巡检点数量为10,模型参数
和
分别取0.7和0.3,对于参数选取的实验过程下文将给出详细过程。具体的,对于这两种算法,我们都进行了一万个训练周期,并且这两种算法都被执行了十次训练,以便我们能获取奖励值的平均值作为最终效果指标。
2) 为了寻找模型最优参数
和
的值,平衡系统总风险损失和系统总时长之间的关系,以实现本文研究目标。本文设置了不同权重参数下算法的系统总风险损失值和系统总时长情况对比,在当前无人机任务规模为10的场景下,对不同权重参数进行了实验数据对比并选取最优参数值,后续实验都是基于此权重参数值进行。
3) 为了验证本文所提算法的性能优越性,我们对所提出的算法和聚类 + DQN、MADQN [14] 以及MADDPG [15] 对任务规模为30、无人机数量为3的场景下执行任务的不同性能指标数据进行对比,其中聚类 + DQN算法中的聚类阶段使用本文所提出的聚类算法。我们在相同的测试环境下,对不同算法进行了100次实验模拟,最终取其结果的平均值进行比较,从而更客观的展示算法的应用效果。
4.2. 结果分析
4.2.1. 强化学习算法收敛性分析
两种算法的奖励收敛情况如图3所示,由图3可知,所提出的AM-DQN算法的奖励值在开始训练后维持在较高水平,随着训练周期的增加奖励值持续快速增长并最终收敛,而DQN算法的奖励值长时间维持在较低水平,波动较大并且收敛速度较慢。上述比较说明了相比于DQN算法,本文所提算法的训练过程更加稳定和高效。
Figure 3. Convergence comparison of algorithms
图3. 算法的收敛性对比
4.2.2. 不同权重参数的指标数据分析
图4为不同权重下训练出的算法模型的系统总风险损失和系统总时长情况,其中模型参数
和
之和为1,将
的值范围设置为[0-1],由图4可知,随着
的值增加,系统总风险损失的占比增加,模型学习时优先考虑降低系统总风险损失,在
取值为0.7时,系统总风险损失值趋于稳定,与此同时系统总时长持续增加,所以本文取
为0.7作为模型参数。
Figure 4. Indicator data with different weight parameters
图4. 不同权重参数的指标数据
4.2.3. 不同算法的指标数据分析
由于本文算法分为两个阶段,我们首先对30个巡检点进行聚类划分为3组,然后将聚类群组分别分配给每台无人机,每台无人机将运行各自的AM-DQN算法进行路径规划。聚类分配过程如图5所示,其中巡检的颜色深浅表示巡检点风险等级的高低,颜色越深表示等级越高。
Figure 5. Clustering and allocation process
图5. 聚类和分配过程
表5为四种算法在巡检点规模为30时执行任务的指标数据,由表5可以看出,本文算法能够保证任务的有效完成,并且拥有更低的系统总成本,在各项指标数据上都拥有较高的性能表现。
Table 5. Indicator data for tasks performed by the four algorithms
表5. 四种算法执行任务的指标数据
最后,为了验证本文算法的可扩展性,我们对任务规模分别为
下的场景进行模拟实验。图6为四种算法在不同巡检点数量下的系统总成本对比,由图6可知,随着巡检点数量的增加,四种算法的系统总成本均在上升,本文算法在不同规模的任务场景下性能表现稳定。其中,在任务规模为60以上时,其他三种算法的性能出现了明显的下降,这是因为随着任务规模的增加,算法的动作空间变大,导致其他三种算法难以完成给定的任务。通过综合分析,在多无人机巡检场景下,本文所提算法拥有比对比算法更好的表现,是综合性应用的最佳选择。
Figure 6. Comparison of total system cost for four algorithms with different number of inspection points
图6. 四种算法在不同巡检点数量下的系统总成本对比
5. 总结
本文研究了城市巡检场景下的多无人机路径规划问题,针对巡检场景进行建模,量化环境中的风险损失,将路径规划的目标设计为最小化系统总风险损失与系统总时长的加权和。本文提出的基于风险损失分析的多无人机巡检协同路径规划方法,通过聚类划分阶段和路径规划阶段,分别解决了巡检点风险等级冲突性问题和无人机路径规划风险损失动态适应性问题。该方法兼顾了路径动态风险规避和巡检效率,能够有效降低巡检的系统总成本。实验结果表明,本文所提出的方法能够有效解决多无人机巡检路径规划问题,并且相比于现有算法,巡检规划出的路径具有更低的系统总风险损失,在巡检任务中具有更优的综合性能表现。
基金项目
国家自然科学基金资助项目(61602305,61802257);上海市自然科学基金资助项目(18ZR1426000,19ZR1477600)。