基于拍卖机制的图节点任务分配方法、装置和设备

摘要

本申请涉及一种基于拍卖机制的图节点任务分配方法、装置和设备，该方法实施于任务授权平台以及多台无人机之间，任务授权平台配置有节点图，所述方法包括：任务授权平台作为拍卖者，将节点图发送至各所述无人机，各无人机接收到节点图后，作为竞标者对节点图中所有目标任务发起竞拍，其中发起竞拍的无人机均具备拍卖权限，针对同一目标任务，多个无人机向任务授权平台发送竞标价格，竞拍价格由该目标任务的当前价格以及各无人机执行该目标任务后所获得的总收益决定，其中总收益由无人机依据对应的任务信息计算得到，最后任务授权平台将各节点的目标任务分别分配至竞拍价格最高的无人机执行。采用本方法能够解决传统无人及任务分配方法不能适应多往返的任务规划的问题。

说明书

技术领域

本申请涉及无人机集群控制技术领域，特别是涉及一种基于拍卖机制的图节点任务分配方法、装置和设备。

背景技术

随着无人机的广泛应用，其面对的应用场景也越来越复杂，执行的任务也越来越多样，单架无人机执行任务的局限越来越明显。在此背景下，无人机逐渐从单架次的方式向多架次集群的方式发展，无人机的任务规划成为无人机集群执行复杂任务的重要组成部分。

而针对一些特殊的应用场景，无人机需要在一个地点和多个不同的任务地点往返作业。不同于一般任务分配问题，目标任务被执行者执行一次就可被完成，并且求解的是执行者执行的目标任务序列，在这种情况下处理动态情况会比较麻烦，不具有统一性。目前，解决此类问题仍存在不少挑战，包括传统的无人机协同任务规划模型不能很好的适应多往返的任务规划问题，任务规划算法的时效性不强，动态环境下算法的适应性不强。

发明内容

基于此，有必要针对上述技术问题，提供一种能够解决传统无人及任务分配方法不能适应多往返的任务规划问题的基于拍卖机制的图节点任务分配方法、装置和设备。

本申请提供了一种基于拍卖机制的图节点任务分配方法，所述方法实施于任务授权平台以及多台无人机之间，所述任务授权平台配置有节点图，所述节点图用于表示整个任务区域，其中一部分节点分别对应一个目标任务，且各所述目标任务均包含相关的任务信息，两所述节点之间的边为无人机执行任务时的移动路径；

所述图节点任务分配方法包括：

所述任务授权平台作为拍卖者，将所述节点图发送至各所述无人机；

各所述无人机接收到节点图后，作为竞标者对所述节点图中所有目标任务发起竞拍，其中发起竞拍的无人机均具备拍卖权限；

针对同一目标任务，多个无人机向所述任务授权平台发送竞标价格，所述竞拍价格由该目标任务的当前价格以及各无人机执行该目标任务后所获得的总收益决定，其中所述总收益由所述无人机依据对应的任务信息计算得到；

所述任务授权平台将各节点的目标任务分别分配至竞拍价格最高的无人机执行。

在其中一实施例中，各所述目标任务对应的任务信息包括：目标任务在整个任务区域中对应的地理坐标、所需物资的数量、紧急程度以及当前价格。

在其中一实施例中，所述目标任务的紧急程度的计算公式为：

其中，

在其中一实施例中，所述无人机是否具备拍卖权限，由拍卖权限公式体现：

其中，u

当

在其中一实施例中，所述总收益由所述无人机依据节点图根据收益函数计算得到，所述收益函数为：

其中，

在其中一实施例中，当所述无人机具备拍卖权限后通过所述收益函数计算出整个任务区域中所有目标任务的收益向量，所述收益向量为：

其中，

在其中一实施例中，所述方法还包括根据价格更新规则对目标任务的价格进行动态更新。

在其中一实施例中，所述价格更新规则包括：在对目标任务进行竞拍过程中，对目标任务的价格进行动态更新，针对一个目标任务，根据各所述无人机发送的竞拍价格对该目标任务的价格进行时时更新。

在其中一实施例中，所述价格更新规则包括：在所述无人机完成分配到的目标任务后，该目标任务的价格更新为初始值。

本申请还提供了一种基于拍卖机制的图节点任务分配装置，包括任务授权平台以及多台无人机，所述任务授权平台配置有节点图，所述节点图用于表示整个任务区域，其中一部分节点分别对应一个目标任务，且各所述目标任务均包含相关的任务信息，两所述节点之间的边为无人机执行任务时的移动路径；

所述任务授权平台以及多台无人机均包括存储器处理器，存储器中存储有计算程序，该处理器执行计算机程序时，实现上述的基于拍卖机制的图节点任务分配方法。

本申请还提供了一种计算机设备，包括存储器和处理器，所述存储器存储有计算机程序，所述处理器执行所述计算机程序时实现上述的基于拍卖机制的图节点任务分配方法。

上述基于拍卖机制的图节点任务分配方法，通过利用节点图中各目标任务的任务信息，结合优化的拍卖机制对目标任务根据任务区域环境变化，动态的将任务分配至合适的无人机，更好的适用于目标需多次执行的动态任务的分配，且有利于推广应用。

附图说明

图1为一个实施例中任务授权平台和各无人机之间的竞拍流程示意图；

图2为一个实施例中任务授权平台侧数据处理梳理流程示意图；

图3为一个实施例中无人机侧数据处理流程示意图；

图4为一个实施例中计算机设备的内部结构图。

具体实施方式

为了使本申请的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本申请进行进一步详细说明。应当理解，此处描述的具体实施例仅仅用以解释本申请，并不用于限定本申请。

如图1所示，提供了一种基于拍卖机制的图节点任务分配方法，所述方法实施于任务授权平台以及多台无人机之间，任务授权平台配置有节点图，节点图用于表示整个任务区域，其中一部分节点分别对应一个目标任务，且各目标任务均包含相关的任务信息，两节点之间的边为无人机执行任务时的移动路径；

图节点任务分配方法包括：

任务授权平台作为拍卖者，将节点图发送至各无人机；

各无人机接收到节点图后，作为竞标者对节点图中所有目标任务发起竞拍，其中发起竞拍的无人机均具备拍卖权限；

针对同一目标任务，多个无人机向任务授权平台发送竞标价格，竞拍价格由该目标任务的当前价格以及各无人机执行该目标任务后所获得的总收益决定，其中总收益由无人机依据对应的任务信息计算得到；

任务授权平台将各节点的目标任务分别分配至竞拍价格最高的无人机执行。

本申请中的图节点任务分配方法可运用在需要无人机在多地往返执行任务，为了使得本方法更为清楚，接下来以无人机集群执行对地震灾区的物资投送任务为例，对本方法中各步骤进行阐述。

在该任务背景下，无人机需要不断往返物资集散中心填充物资后再到投送节点进行投送。在灾区环境中，投送节点属性是动态变化的，无人机执行任务的过程中也可能会出现功能故障的情况，并且每架无人机所装载的物资量是有限的，这就要求动态任务规划方法具有较强的自适应和实时性能力。

用于表示整个任务区域的节点图可采用将整个灾区环境进行建模的无向图，而无人机在图中移动执行任务。

具体的，用G是表示灾区环境的一个无向图，G＝(V，E)，其中V表示空间中节点的坐标集合，节点包括目标节点v

而各目标节点均包含有对应的任务信息，任务信息包括：目标任务在整个任务区域中对应的地理坐标、所需物资的数量、紧急程度以及当前投标价。

其中，地理坐标为(x，y)表示灾区环境下的目标节点所在的位置。

其中，所需物资的数量为

其中，紧急程度为

在其中一实施例中，目标任务的紧急程度的计算公式为：

在公式(1)中，a，b是常量参数。

需要说明的是，在本文出现的各公式中，t表示连续时间，无人机运动是在连续时间下描述的。

进一步的，从公式(1)中可以看出目标节点的紧急程度值

在本申请中，是基于优化后的拍卖机制进行任务分配的，如图1所示，任务授权平台作为拍卖者，而各无人机作为竞标者对各目标任务进行分配。

在各无人机接收到任务授权平台发送的节点图后，先需要对自身是否具备拍卖权限进行判断，只有具备拍卖权限才能进行竞拍。

各无人机接收到任务信息后，作为竞标者对节点图中所有目标任务发起竞拍，其中发起竞拍的无人机均具备拍卖权限。而拍卖权限是为了限定无人机进行拍卖的时机，以及应对动态环境下新节点的出现对原有的任务分配产生影响，造成一些计算资源的浪费、得不到全局最优解的情况。

而拍卖权限的具体思路为无人机每次只竞标一个目标节点，在执行任务的过程中不参与拍卖过程。当完成任务之后，再参与第二次拍卖。这种拍卖机制下可以更好的面对节点的动态变化，不会因为新节点的产生重新运用该算法重新计算。

基于上述拍卖权限的思路，无人机是否具备拍卖权限，由下述拍卖权限公式体现：

在公式(2)中，u

当

具体的，当

具体的，当当

在无人机确认自身具备拍卖权限后，应向任务授权平台发送所有目标节点相应的竞拍价格，而各竞拍价格与无人机执行各目标任务后所获得的总收益相关。

总收益由无人机依据节点图根据收益函数计算得到，收益函数基于无人机执行某一个目标节点所获得的收益，并由目标节点v

在公示(3)中，

进一步的，则各无人机基于上述收益函数计算出整个任务区域中所有目标任务的收益向量，所述收益向量为：

在公式(4)中，

进一步的，各无人机的竞拍价格还与目标节点的当前价格相关，而目标节点的当前价格是根据价格更新规则进行动态更新。

其中，价格更新规则包括：在对目标任务进行竞拍过程中，对目标节点的当前价格进行动态更新，针对一个目标任务，根据各所述无人机发送的竞拍价格对该目标任务的价格进行时时更新。

进一步的，无人机针对一目标节点任务的竞标价格还与完成该目标节点任务后的最大净收益相关。

具体的，定义t时刻目标节点v

则计算无人机u

对应目标节点

为了进一步确定无人机u

如果除了

综上可得无人机u

在公式(9)中，ε为松弛因子，在每一价格更新时需要额外增加一个价格小量，防止在拍卖循环的过程中价格抬升过慢，而造成拍卖效率低下。

在各无人机均向任务授权平台发送对所有目标节点的竞拍价格后，任务授权平台根据收到来自各无人机的竞拍价格将会生成所有目标节点的标价矩阵P′(t)，即

在公式(9)中，

其中，在初始时刻没有无人机出竞拍价格，设价格为-∞，即

将目标节点v

任务授权平台将目标节点v

其中，

一旦T

在其中一实施例中，价格更新规则还包括，在无人机完成分配到的目标节点对应的任务后，将该目标节点的投标价更新为初始值，例如，0。

如图2-3所示，在另一实施例中，分别提供了在任务授权平台一侧以及无人机一侧的图节点任务分配方法。

如图2所示，在任务授权平台一侧包括：

向各无人机发送节点图；

获取无人机发送的竞标价格，根据接收到的竞标价格以及对应的无人机更新标价矩阵；

在标价矩阵中选出被标中的目标节点的最大竞标价格以及对应的无人机；

将目标节点授权给对应的无人机；

根据最大竞标价格更新目标节点的价格。

如图3所示，在无人机一侧包括：

获取所述节点图；

判断自身是否具备拍卖权限；

若具备，则根据所述任务信息计算各目标节点的竞标价格(其中计算过程上文中已限定，则不再赘述)；

向任务授权平台提交竞标价格。

上述基于拍卖机制的图节点任务分配方法，能够在复杂多变的情况下更好的实现对无人机集群的任务规划。可以统一处理正常情况下的任务分配和新情况发生时(例如新的目标节点产生、目标节点属性发生变化、目标节点的消失、部分无人机损毁以及增加部分无人机)的任务分配，而不需要对整体方案进行重分配。本方法可以更好的是适用于目标需多次执行的动态任务分配问题，有利于推广应用。

应该理解的是，虽然图2-3的流程图中的各个步骤按照箭头的指示依次显示，但是这些步骤并不是必然按照箭头指示的顺序依次执行。除非本文中有明确的说明，这些步骤的执行并没有严格的顺序限制，这些步骤可以以其它的顺序执行。而且，图2-3中的至少一部分步骤可以包括多个子步骤或者多个阶段，这些子步骤或者阶段并不必然是在同一时刻执行完成，而是可以在不同的时刻执行，这些子步骤或者阶段的执行顺序也不必然是依次进行，而是可以与其它步骤或者其它步骤的子步骤或者阶段的至少一部分轮流或者交替地执行。

在一个实施例中，提供了一种计算机设备，即一种基于拍卖机制的图节点任务分配系统，该计算机设备可以是终端，其内部结构图可以如图4所示。该计算机设备包括通过系统总线连接的处理器、存储器、网络接口、显示屏和输入装置。其中，该计算机设备的处理器用于提供计算和控制能力。该计算机设备的存储器包括非易失性存储介质、内存储器。该非易失性存储介质存储有操作系统和计算机程序。该内存储器为非易失性存储介质中的操作系统和计算机程序的运行提供环境。该计算机设备的网络接口用于与外部的终端通过网络连接通信。该计算机程序被处理器执行时以实现上述基于拍卖机制的图节点任务分配系统方法。该计算机设备的显示屏可以是液晶显示屏或者电子墨水显示屏，该计算机设备的输入装置可以是显示屏上覆盖的触摸层，也可以是计算机设备外壳上设置的按键、轨迹球或触控板，还可以是外接的键盘、触控板或鼠标等。

本领域技术人员可以理解，图4中示出的结构，仅仅是与本申请方案相关的部分结构的框图，并不构成对本申请方案所应用于其上的计算机设备的限定，具体的计算机设备可以包括比图中所示更多或更少的部件，或者组合某些部件，或者具有不同的部件布置。

在其中一实施例中，提供了一种基于拍卖机制的图节点任务分配装置，图节点任务分配系统包括任务授权平台以及多台无人机，任务授权平台配置有节点图，节点图用于表示整个任务区域，其中一部分节点分别对应一个目标任务，且各目标任务均包含相关的任务信息，两节点之间的边为无人机执行任务时的移动路径；

所述任务授权平台以及多台无人机均包括存储器处理器，存储器中存储有计算程序，该处理器执行计算机程序时，实现上述的基于拍卖机制的图节点任务分配方法。

本领域普通技术人员可以理解实现上述实施例方法中的全部或部分流程，是可以通过计算机程序来指令相关的硬件来完成，所述的计算机程序可存储于一非易失性计算机可读取存储介质中，该计算机程序在执行时，可包括如上述各方法的实施例的流程。其中，本申请所提供的各实施例中所使用的对存储器、存储、数据库或其它介质的任何引用，均可包括非易失性和/或易失性存储器。非易失性存储器可包括只读存储器(ROM)、可编程ROM(PROM)、电可编程ROM(EPROM)、电可擦除可编程ROM(EEPROM)或闪存。易失性存储器可包括随机存取存储器(RAM)或者外部高速缓冲存储器。作为说明而非局限，RAM以多种形式可得，诸如静态RAM(SRAM)、动态RAM(DRAM)、同步DRAM(SDRAM)、双数据率SDRAM(DDRSDRAM)、增强型SDRAM(ESDRAM)、同步链路(Synchlink)DRAM(SLDRAM)、存储器总线(Rambus)直接RAM(RDRAM)、直接存储器总线动态RAM(DRDRAM)、以及存储器总线动态RAM(RDRAM)等。

以上实施例的各技术特征可以进行任意的组合，为使描述简洁，未对上述实施例中的各个技术特征所有可能的组合都进行描述，然而，只要这些技术特征的组合不存在矛盾，都应当认为是本说明书记载的范围。

以上所述实施例仅表达了本申请的几种实施方式，其描述较为具体和详细，但并不能因此而理解为对发明专利范围的限制。应当指出的是，对于本领域的普通技术人员来说，在不脱离本申请构思的前提下，还可以做出若干变形和改进，这些都属于本申请的保护范围。因此，本申请专利的保护范围应以所附权利要求为准。