旋翼无人机的多机协同自主探索决策技术综述

施晓航,徐勇勤

(1.95828部队,西安 710089; 2.上海机电工程研究所,上海 201109)

0 引言

随着社会的不断发展,无人机在其中的角色愈发重要,在载荷运输、摄影娱乐、战场侦察等各方面发挥着重要作用。目前,随着传感器技术以及同时定位与建图(simultaneous localization and mapping,SLAM)技术的发展,搭载了功能更高级、性能更先进的传感器后的无人机在室内室外未知环境中的自主探索工作具有巨大的潜力,被广泛应用于地形测绘、灾后救援、环境侦察等领域。

自主探索是指智能体,依靠自身传感器和机载处理器在未知环境中实时闭环地感知、决策并规划,获取未知地图的环境信息。本文中智能体指具有自主能力的旋翼无人机。而旋翼无人机凭借其较小和敏捷的特点,常被应用于复杂的小范围场景中,相比其他智能体平台,对自主探索的实时性与自主性有更高要求。在探索过程中,无人机感知局部环境信息自主决策下一观测点,并进行路径规划驱使无人机前往观测点获取环境信息。如何高效地进行自主探索并获取完整的地图信息一直以来都是无人机领域的热门研究问题。尽管自主探索技术在近年来取得了显著进展,但大多数的研究工作都只关注于单架无人机的探索。而随着探索场景的复杂化与探索任务的高效化,多机协同探索系统的优越性日渐凸显。多机系统[1]与单机相比,不仅能够极大提升探索效率,还能提升探索任务完成的成功率。

多机协同自主探索技术是一项系统工程,如图1所示。其可被划分为感知、决策(未知环境探索策略、多机任务分配策略)以及规划方法。感知主要解决“我在哪”的问题,指智能体以机载传感器的局部感知结果为输入,在线处理建模,输出定位以及周围环境信息。决策则是解决“我去哪”问题,指智能体根据当前环境信息,自主决定下一局部目标点,而在协同系统中,决策问题扩展为“谁去哪”问题,即需要考虑各智能体的任务分配。规划解决“怎么去”问题,指智能体根据当前定位、环境信息以及下一局部目标点,高效规划输出安全避碰的高质量航迹,从而能够被控制器真正执行。

图1 多机协同自主探索工作构成

决策作为多机协同自主探索系统中关键一环,其水平极大程度地影响了整个系统的效率。未知环境探索策略指设计未知地图表达方式以及观测点决策标准使无人机自主决策下一观测点获取环境信息。多机任务分配策略指针对已确定多个观测点的多机系统,进行合理的任务量分配,使最大限度发挥协同优势。

因此,以旋翼无人机为对象,重点从未知环境探索策略和多机任务分配策略详细回顾了多机协同自主探索技术的发展现状,系统性地总结了各策略方法的思路内涵。在此基础上,根据当前发展现状,对多机协同探索技术的未来研究重点进行展望,对本领域的研究工作具有一定的参考意义。

1 多机协同自主探索技术内涵

1.1 自主探索

如图2所示,自主探索的输入是机载传感器提供的当前定位结果以及周围局部环境信息,在提前给定的探索任务区域大小限制及牵引下,无人机通过自主决策,决定下一观测点并高效规划前往路径实现未知区域环境信息的获取,如此往复,不断扩充已知环境区域,直到完成任务。

自主探索则强调未知环境中的自主性,即要求无人机闭环、在线地完成探索任务,其评价指标可大致被分为两类:覆盖率和效率(路径长度和时间)。而根据探索环境表达方式不同,自主探索一般被划分为基于边界(Frontier-based)[2-3]、基于采样(Sampling-based)[4-6]2类,近年来,也涌现出了一批边界和采样结合[7-8]的方法。

1.2 多机协同自主探索系统

多机协同自主探索的核心是通过合理分配任务避免目标重复冲突,高效规划探索路径,使每个无人机同时探索不同的区域得到特定目标信息,最大程度发挥多机系统的优势。多机系统可根据控制决策机制的不同(见图3),被分为集中式或分布式2种协同体系。

图3 多机系统

在集中式的协同探索系统中,文献[9-11]使用迭代分配方法,根据距离和环境信息增益通过贪婪策略选取无人机与对应目标配对。然而,这种策略只给每个无人机分配一个目标,当多个无人机被分配到邻近的目标时,该策略产生冲突无法有效分配目标。为了解决该问题,文献[12-13]提出了基于分割的目标分配方法,将目标区域进行分割再分配。文献[12]使用Voronoi图将已侦察区域划分为若干部分。通过将无人机分配到不同的部分区域而不是单个目标,使无人机在环境中分布得更均匀。类似地,文献[13]使用广度优先探索的聚类算法对划分区域进行分组,并将它们分配给相应无人机。此外,文献[14-15]将目标分配问题建模为多旅行商问题(multiple travelling salesman problem,mTSP)。因为多旅行商问题实质上是NP-hard问题,因此使用子问题划分来求解得到近似最优解。文献[14]使用基于K-means的分类算法将所有目标进行分组并分配给各无人机。文献[15]通过求解一个离散的最优运输问题来找到所有目标对于各无人机的分配,而每个无人机的最优路径则建模为TSP问题求解。而文献[16]采用贪婪TSP算法,为每个无人机贪婪地分配一个侦察点集群。以上方法均是在集中式体系且假定通信完美的情况下成立的。

相比于集中式,分布式协同探索系统主要考虑通信质量,即通信范围和通信带宽的问题,在共享定位和局部地图的范围和大小方面重点优化。文献[17]提出了第一个分布式的协同探索系统,其中所有无人机共享地图信息并分别移动到对应最近的边界中,但由于多个无人机可能移动到同一位置,协同效果并不好。因此,文献[17-19]提出了基于拍卖机制的分布式协同方法。文献[17-18]使用分布式单独竞价本地拍卖策略解决无人机间的冲突。而为了考虑无人机间共同的多个目标的分配问题,文献[19]制定了组合拍卖策略。除了基于拍卖的方法,文献[20]将贪婪算法拓展应用于分布式协同上,然而该过程通常需要无人机间进行数轮通信。文献[21]在文献[20]的基础上讨论了不同目标函数对分布式协同的效果。文献[22]利用多无人机多目标势场将无人机分配到不同边界。文献[21]提出两两优化方案,即通过无人机两两交互重新分配目标。该方法由文献[21]演化而来,而文献[21]最初被用于解决无人机的协同控制问题。以上方法的一个共同缺点是需要多个无人机同时稳定连接,故容易受到网络不稳定或延迟的影响使侦察效率降低。为了简化对通信质量的要求,减少无人机交互共享的数量极为关键。

综上所述,从单机的自主探索发展到多机的协同探索,未知环境探索以及多机任务分配是研究的重点。本文将主要针对以上两部分对多无人机的协同探索工作进行介绍。

2 未知环境探索策略

2.1 基于边界的自主探索

边界是指未知区域与已知区域的边界。其概念首先由Yamauchi[24]提出。如图4所示,其基本思想是根据当前的局部环境信息生成对应的边界轮廓,根据边界生成一个或一系列的观测点,通过一定策略决定下一观测点并通过路径规划导航至该观测点。当到达该观测点后,边界信息更新,又更新生成新的观测点,如此往复驱动无人机完成整个环境的探索任务。早期的基于边界的自主探索方法具有一定的局限性,其不仅边界生成效率低,且通过边界生成观测点的策略不够完善导致观测点环境信息获取效率低下。

图4 基于边界的自主探索方法

文献[25]通过验证证明了边界生成速度过慢会直接导致自主探索效率变低,其原因是当边界更新速度跟不上无人机运动速度时,无人机仍向上一次决定的观测点移动,导致无人机可能会重复探索已知区域。为解决以上问题,出现了更多适用性更强的边界检测探索方法。文献[26]利用三维占据地图的八叉树数据结构提高边界检测效率。其本质是凭借八叉树叶子节点与根节点的连通性,将位于同一八叉树分支的边界视为一个簇,从而提高边界的聚类效率。

在生成边界后,观测点的评估策略对探索效率亦十分重要。观测点评估是指根据边界信息决策一个或一系列观测点,这些观测点往往作为路径规划的局部目标点。

传统的基于边界的自主探索方法[24]最早贪婪地选择边界中距离当前无人机位置欧氏距离最近的点作为下一观测点。在此基础上,文献[27-29]考虑地图的不确定性因素,提出采用欧氏距离和观测点处可获得的期望环境信息量组合作为观测点的评估指标。观测点处可获得的期望环境信息量实质上是无人机在观测点位置在传感器视角限制下能够覆盖的边界数量。但是,该策略由于使用的是欧式距离来表示代价,容易产生不正确的代价估计,因此在复杂环境中不太适用,尤其是当无人机与观测点之间存在较多障碍物时。因此,如图5所示,文献[26]采用A*算法规划无人机当前位置到观测点的近似最优无碰路径,以此路径长度作为距离惩罚项。在此基础上,文献[25]引入了方向改变代价惩罚项,使无人机尽量保持连续飞行,进而提高探索效率。

除此之外,文献[24]采用基于随机微分方程的策略,实现了在三维空间中的边界搜寻。与文献[24]不同,文献[25]选择传感器视场范围(field of view,FOV)内的局部边界信息而并非直接选择最近的边界作为观测点。该策略的目的是使无人机的速度变化最小,即使因为重规划频率太高亦能使无人机一直保持较高的飞行速度。文献[23]等对多无人机的协同探索问题进行了深入研究,其基本思想是:首先通过构建边界的距离与角度的吸引函数,然后构建无人机间距离的分散函数,优化了探索环境的效率,改进了边界的自主探索算法。

2.2 基于采样的自主探索

基于采样的自主探索方法通过随机采样产生候选侦察点,并评估其信息增益。其与下一最佳观测点(next best view,NBV)思想类似,关键都在于通过重复计算获得观测点来获取场景中的环境信息。

如图6所示,该方法通常采用基于快速扩展随机树(rapidly-exploring random tree,RRT)原理的算法在探索空间进行采样。利用RRT本身的节点扩展特性进行观测点采样,在随机采样确定节点的过程中,各节点之间的路径也随之确定,这些路径还能被用作后续的规划路径。文献[5]首先将NBV的概念引入三维环境的探索工作中,使用RRT算法以无人机当前位置作为树的根节点,通过随机采样进行支的随机扩展,在此同时,计算采样观测点处的信息增益。预先设定采样次数阈值,当采样次数达到最大次数后停止采样,并对各分支的信息增益进行评估,选择增益最大的分支作为被使用的探索路径。而在真正执行中,当无人机执行完探索路径的第一段后,将其他分段上的采样观测点作为种子重新进行以上随机采样扩展过程,如此往复,直到覆盖整个探索空间。由于整个过程与控制领域中的滚动时域理论相似,以上策略方法被称为滚动时域NBV规划器(receding horizon next best view planner,RH-NBVP)。在此基础上,文献[31]考虑了定位的不确定性,文献[32]考虑了视觉感知限制,文献[33]考虑了检测的不稳定性。

图6 基于采样的自主探索方法

RH-NBVP方法相比基于边界的自主探索方法效率更高,但是,随机采样的思路难以获得最佳偏航角导致遍历偏航角的方法算力要求大且运行速度慢。此外,RH-NBVP本质上仍是RRT随机采样不断重复构建分支的思路,这使其在狭窄空间中易陷入局部最优而在大范围空间中扩展效率较低。

针对RH-NBVP方法观测点评估效率低的问题,文献[30]通过降采样方法减少信息增益计算需遍历的体素数量,由此加速观测点的评估速度。针对RH-NBVP方法偏航角采样效率低的问题。

基于采样的自主探索方法因其单次查询特性,导致该方法在探索大范围复杂空间时易陷入局部最优问题。针对该问题,文献[34]提出保存已采样获得的节点并构成历史图,在无人机进行探索时亦实时维护更新该历史图,当无人机在狭窄区域中陷入局部最优时,可通过历史节点作为种子“跳出”局部最优。但是,随着地图的不断扩大,尤其在大范围场景中进行探索任务时,维护历史图的更新将会消耗巨大算力。因此,文献[34]又通过构建欧式有向距离场(Euclidean signed distance field,ESDF)[35-36]将节点向障碍物之间的空闲区域推进,由此将位置相近的类似节点融合,在减少树节点规模的同时也保留了环境的骨架结构。

除了使用RRT进行采样,文献[37]提出将概率路线图(probabilistic roadmap,PRM)用于基于采样的自主探索工作中。其思路是在无人机传感器范围内的区域进行随机采样以实现增量式扩展全局路线图的生成,进而构建出能够表达环境特征的三维拓扑结构图,以此快速找到未知区域。在此基础上,文献[38]通过局部-全局相结合的采样策略,增量式地构建概率路线图,能够在具有简单动态障碍物的环境中实现高效探索覆盖。为了使飞行速度更快,文献[39]提出对动态可行的运动语义进行随机采样的策略,首次将运动语义应用于自主探索工作中。

2.3 基于边界和采样组合的自主探索

基于边界的方法简单直接,但其必须首先生成完边界后再通过评估决策观测点,效率较低。而基于采样的方法通过随机采样产生候选观测点再评估其信息增益筛选,该方法可显式地量化每个候选观测点的信息增益,但缺点是算力要求较高。因此,诸多研究者提出了将边界和采样方法相结合的自主探索思路。

文献[40]提出基于边界生成全局路径再通过路径采样需探索局部区域的方法。文献[41]讨论了一种对边界周围进行采样来生成观测点的方法,该方法能够找到全局最短探索路径。文献[42]通过采样方法找到能够完全覆盖边界的探索路径。

3 多机任务分配策略

相比于单机执行任务,多无人机系统由于执行任务的智能体数量提升以及共享机制的加入,增加了最能体现多机协同优势的任务分配环节。

在多无人机协同探索未知环境任务中,各无人机获取周围环境信息并更新迭代观测点,再通过各无人机之间的协调策略将一系列观测点统筹再分配给系统中特定的成员,使探索效率最大化。该问题常被建模为多机任务分配问题(multi-robot task allocation,MRTA)。

MRTA问题的实质是解决系统中哪个无人机去执行哪个特定任务效率最高的问题,是发挥系统协同效率的关键[43]随着探索任务难度的升级、协同智能体数目的增加以及通信限制等各类因素,解决多机协同任务分配问题的关键在于如何对问题进行准确的建模。

3.1 基于物流模型的任务分配

在任务分配中,任务即为输入,是各无人机已初步确定的对应观测点;分配即为输出,是共享信息后重分配的各无人机对应观测点。此外,一些研究工作还关注无人机探索路途中能够获得的环境增益[44],各无人机初步确定的观测点不止一个,于是还涉及这一系列观测点按照何种顺序前往的问题。该问题常被建模为多旅行商问题[45],其原理为约束每一个无人机至少分配一个目标点,并使得总成本最小化,成本可以被设计为距离或时间。如图7所示,多旅行商问题的目标是找到一组路径,使得所有旅行商(各无人机)访问各自的城市(观测点)集合,并且每个城市只被一个旅行商访问一次,并且最小化总路径长度或最小化最长路径长度。这个问题在实际应用中具有很高的复杂性,因为在多个旅行商之间需要合理地分配城市,并且需要考虑到各个旅行商的路径长度。

图7 多旅行商问题示意

在此基础上,如图8所示,通过考虑各无人机的工作量使任务负载分配更为合理,文献[46]将多无人机协同探索中的任务分配问题建模为负载车辆运送问题(capacitated vehicle routing problem,CVRP)以使系统中各无人机任务量平衡。相比mTSP问题,CVRP的建模思路可以将负载即工作量纳入到约束中。

图8 负载车辆运送问题示意

近年来,任务分配算法发展迅速,大体上可被分为基于市场的方法和基于优化的方法。在此基础上,针对目前热点研究问题和关注应用实际,本文还将单独讨论考虑通讯限制的任务分配。

3.2 基于市场模型的任务分配

受经济学理论中重要的拍卖机制启发,基于市场的任务分配方法是协同系统中各无人机根据自身“处境”进行竞标参与拍卖。“拍卖商品”是各任务,“竞价价格”通常由“收益”和“成本”共同衡量,而“收益”和“成本”通过制定的“拍卖标准”决定。在拍卖市场理论指导下,整体系统通过优化目标函数以实现“利润”的最大化。合同网协议[53]以及Trader-Bots方法[54]是拍卖方法中重要的两类方法。

1) 基于合同网协议的拍卖算法

合同网协议(contract net protocal,CNP)是多智能体系统中的一种任务共享协议,其确定了系统中各无人机间进行“谈判竞标”时共同遵守的准则。基于合同网的拍卖算法的过程一般被划分为以下4个阶段:

a.招标:其中至少一个无人机担任“拍卖商”,对其他无人机发布被竞标的任务。

b.投标:其他无人机接收到发布的任务信息后,担任“投标者”,根据目标函数求得可出“竞价”,并将此价格发送回“拍卖商”。

c.评价:“拍卖商”接收各“投标者”的出价后,根据优化策略对各投标者进行评价,最终确定“中标者”。

d.履行:“中标者”即为被选定的该任务分配的无人机,接收任务并履行。重复以上过程,直到没有新任务产生。

基于拍卖的任务分配方法在集中式和分布式系统中均适用。在集中式系统中,中央处理器作为“拍卖商”协调整个系统,该系统具有全局优势但稳定性不好,若中央处理器故障,那整个拍卖机制就整个瘫痪。因此,集中式的方法仅适合于小型环境的协同探索任务分配。而分布式系统中,每一个成员既能担任“拍卖商”又能担任“投标者”,对环境变化和故障问题有较好的容错能力,但局部优化不一定能够实现全局较优解。因此,分布式的方法一般适用于大型环境的协同探索任务分配。

2) 基于Trader-Bots方法的拍卖算法

Trader-Bots方法借鉴了市场经济中个体能够自由交换商品或服务并自由签订合同的核心思想,将整个无人机系统看作是一个经济体,系统中各智能体都被建模为“自由交易者”。在本方法中,目标函数一方面要保证团队能够顺利完成所有任务,并使“总利润”最大化,另一方面各无人机间要保证自己的“个人利润”最大化。

因此,整个系统需要在整体和个人之间寻求平衡,即“自由交易者”之间能够相互协商进而产生最终的任务分配结果。协商的方法一般为分包和转移2种。分包指“招标者”向“投标者”发放任务,并在任务完成后向“投标者”发放对应酬劳。转让指“投标者”主动以一定价格出售任务执行代价,在签订合同之时,“招标者”即向投标者“付款”支付报酬。协商和分包行为的实质是允许了无人机在任务执行过程中将无法处理或不便处理的任务再次进行拍卖,实现任务迁移,提升任务分配结果的质量。

相比于合同网协议,Trader-Bots方法具有更强的适应性与鲁棒性,其允许协商过程中发生分包或转让行为的机制能够更加明确任务优先级以及提升任务容错性。

3.3 考虑通讯限制的任务分配

通讯在协同系统中具有重要地位,其作用于协同探索工作的整个过程,尤其对任务分配的决策具有重要影响。

在美国国防部高级研究计划局(defense advanced research projects agency,DARPA)举办的地下挑战赛(subterranean challenge competition,SubT)中,研究人员使用多种异构机器人(包括无人机、地面机器人等)[51]进行了地下极端环境的协同探索。然而,这些系统现大多数仍旧属于集中式方法,即依赖于某一台中央处理器进行任务分配,任务分配方式也一般采用贪婪算法进行简单处理。可见,在实际应用中,因通讯限制,有许多问题仍待解决。

如图9所示,通常将通讯限制具体划分为以下两类:(1)带宽限制,即系统内无人机间无法对占用空间较大的数据进行瞬时传输,造成数据延迟甚至丢包的问题;(2)距离限制,即系统内无人机间只能在一定物理范围内进行通讯。针对以上两大限制,各种方法从不同角度努力改善探索系统的稳定性。

图9 协同探索系统面临的通讯限制问题

文献[52]通过各无人机与中心处理器建立通信树的回归策略提升任务分配的稳定性。文献[54]采用高斯混合模型建立全局地图,使地图共享占用内存缩小。文献[55]使用基于群体梯度信息的bug算法,采用沿墙飞行和实时接收信号强度的策略来避免碰撞,但其效率较低无法获得准确且全面的地图信息。以上算法均属于集中式的任务分配方法,在实际应用中往往受通讯限制而导致效果不佳。

文献[50]在通信带宽限制方面,对包含局部地图、已探索区域以及定位等共享信息进行优化压缩,降低内存占用。而针对通信距离限制,文献[50]通过预先设定下一汇合点使无人机分散再集合,确保通信共享的稳定性。而文献[46]通过限制并减少同时共享无人机的数量降低通讯要求,即通过设计请求-响应的任务分配方案,仅支持无人机之间成对进行交互实现信息共享。

综上所述,考虑通讯限制的任务分配方法在实际应用中具有重要意义,也越来越受到学者们的关注。

4 结论

未知环境探索策略和多机任务分配策略是多机协同自主探索工作中的重点,影响着整体探索效率。本文中详细介绍了未知环境探索策略以及多机任务分配策略,并对当前工作进行了分析评价。

当前未知环境探索策略可分为基于边界、采样以及两者结合的方法。其中,基于边界的方法简单易用,但效率较低,而基于采样的方法效率高但较易陷入局部最优,且在大场景中较费算力。而两者结合的方法取长补短,具有较高的研究意义与价值。

当前多机任务分配策略可分为基于物流和市场模型的方法。其中,基于物流的方法是将一系列观测当作旅行商问题中的城市,意在求取访问城市的先后顺序从而决策各无人机的下一观测点。而基于市场的方法参考人类社会中的拍卖机制,通过投标、竞标、中标的方式进行任务分配。需要注意的是,在本文中特别讨论了通讯限制下的任务分配方法研究,意在强调通讯在现实世界协同探索工作的重要影响,这也是协同探索当前急需考虑的问题之一。

综上所述,多机协同自主探索系统仍存在较多待改进和扩展之处:

1) 多机协同优势的提升

当前的多无人机协同探索系统,一般仅共享各智能体之间的局部地图和定位信息,协同优势还未完全发挥。在后续的研究工作中,可尝试在无人机之间加入其他更智能的协同约束,进一步发挥多无人机的协同优势,提高探索效率。

2) 分布式协同探索系统的优化

当前实际应用的多机协同探索系统大多数仍是集中式结构。随着个体智能化、无人化水平的日渐提升,分布式协同探索系统的优势将会日益凸显。因此,在当前研究基础上,需研究更适用于当前个体智能化水平的分布式系统,发挥个体无人化优势,提升整体系统效率。

3) 考虑实际应用的协同探索方法设计

在本文中以现实世界中的通信限制作为典型讨论了协同探索在实际应用中需考虑的问题。除此之外,为了使协同探索方法能够真正在现实生活中应用落地,还需对诸如协同定位建图误差、智能体工作时长限制、故障鲁棒性(抗毁能力)等问题加以考虑,设计出实际应用价值更高的协同探索系统。