CN110488849A - 一种基于改进拍卖算法的围捕者决策方法 - Google Patents

Abstract

本发明属于多机器人任务分配领域，具体涉及一种基于改进拍卖算法的围捕者决策方法。本发明针对传统拍卖算法中拍卖者身份的缺陷和竞标值存在的不足导致围捕者的选定过程安全性差和决策效率低的问题提出了一种基于改进拍卖算法的围捕者决策方法，作为围捕者的决策方法，用来选定围捕者。本发明通过引入几何中心原理，改变了传统确定拍卖者身份的方式，进而加快了拍卖过程，提高了决策效率，增强了决策过程的安全性；通过改进竞标值函数，来确定最佳的围捕者身份，提高了整体的围捕效率。

Description

一种基于改进拍卖算法的围捕者决策方法

技术领域

本发明属于多机器人任务分配领域，具体涉及一种基于改进拍卖算法的围捕者决策方法。

背景技术

随着航海技术的发展，对海洋的投入和研究日渐加深。因水下机器人具有多方面优点，所以在海洋工程中越来越受欢迎。水下机器人可实现深海的科考勘探，救助打捞，数据采集，协助科研人员对深海生物的跟踪研究，以及有效围捕。然而单个水下自治机器人有着自身能力局限性，尤其是在复杂海域执行复杂任务时，例如工作时间限制，探索范围限制。为了更高效的执行任务，可以将多个机器人组成一个编队协作执行任务；这样就可以规避个体综合能力的不足，充分展现群体协作的好处。

基于市场机制的拍卖算法是任务分配的经典算法，往往有一个中心智能体全权负责整个系统的任务分配，存在以下三点不足：

(1)水下机器人拍卖者的选择上，遵循了“谁发现目标，谁是拍卖者”的原则。这带来的隐患是巨大的，因为通常发现目标的水下机器人也是距离目标最近的那个，这个原则适用的基础是，目标没有攻击能力。一旦目标是兼具侦察打击能力的，那么目标对发现者发起攻击，就会扰乱甚至破坏掉整个围捕任务的分配过程，进而无法选定围捕者。

(2)从通信效率的角度来考虑，拍卖者发布目标信息，接收竞标信息，发布竞标结果，经过了三次通信过程。在这三次通信过程中，拍卖者是通信中心节点。目标的发现者和最佳的通信中心节点之间是没有必然联系，甚至是发现者往往不是最佳的通信中心。那么，把目标的发现者默认为通信中心节点，来进行通信传输，从通信效率的角度来考虑，是不明智的。

(3)由传统拍卖过程可知，拍卖者是根据所有竞标者的标值从大到小，遴选围捕水下机器人。那么竞标的标值有什么确定，由哪些因素组成，是至关重要。改进这些因素将会对拍卖算法的效率产生巨大影响。

如何选择围捕者，确定最佳通信中心节点，决定机器人的竞标标值策略，对更快更好地完成多机器人任务分配有重要意义。

发明内容

本发明的目的在于针对传统拍卖算法中拍卖者身份的缺陷和竞标值存在的不足导致围捕者的选定过程安全性差和决策效率低的问题提供用来选定围捕者，作为围捕者的决策的一种基于改进拍卖算法的围捕者决策方法。

本发明的目的通过如下技术方案来实现，包括以下步骤：

步骤1：水下机器人编队搜索并发现目标后，目标发现者计算编队队形几何中心；

步骤2：目标发现者计算编队中所有水下机器人成员与几何中心之间的距离，并选择与几何中心距离最近的成员为拍卖者；

步骤3：目标发现者将目标位置、移动速度以及计算后确定的拍卖者身份信息打包发送给水下机器人编队的其他所有成员；

步骤4：拍卖者开始拍卖，持续时间周期T，竞标水下机器人分别计算自己的竞标值，然后将各自的竞标值分别发送给拍卖者；当时间超过时间周期T后，关闭拍卖市场；

步骤5：拍卖者根据收到的竞标值和围捕任务需求，将每个竞标水下机器人的竞标值与围捕任务需求相比较，满足条件的留下成为准围捕者；将准围捕者的竞标值从大到小排列，筛选确定竞标值前n大的为围捕水下机器人；n为设定满足围捕任务的最小机器人数；

步骤6：如果满足条件的竞标者数量小于n，则返回步骤4，拍卖者开启新一轮的拍卖市场，重新计算竞标值；如果合格的竞标者数量大于等于n，则围捕者决策结束；

步骤7：进入围捕状态，如果超过围捕成功时间阈值还未围捕成功，则放弃围捕；围捕成功后水下机器人编队回到巡航模式。

本发明还可以包括：

所述的步骤1中计算编队队形几何中心的方法为：根据实际环境中水下机器人的经纬度确定平面坐标，根据参考水深确定纵向坐标，编队中每个水下机器人成员坐标记为(x_i,y_i,z_i)，则编队队形几何中心的计算公式为：

其中m为编队中水下机器人成员的数量，点为编队队形几何中心；编队中水下机器人P_i与几何中心之间距离的计算公式为：

所述的步骤4中竞标水下机器人的竞标值的计算方法为：

步骤4.1：计算竞标水下机器人相对于目标的能力g；

g(v,l)＝λ₃v+μ₃l

其中v为竞标水下机器人相对于目标的移动速度优势比，v₁为竞标水下机器人的速度，v₂为目标的速度；l为竞标水下机器人相对于目标的间距；λ₃和μ₃为调节系数，且λ₃+μ₃＝1；

步骤4.2：计算竞标水下机器人当前状态p；

p＝λ₂E+μ₂σ

其中E为竞标水下机器人的能量剩余，σ为竞标水下机器人的攻击能力；λ₂和μ₂为调节系数，且λ₂+μ₂＝1；

步骤4.3：计算竞标水下机器人的代价c；

c(E,v,l)＝ρ₁E+ρ₂v+ρ₃l；

其中ρ₁、ρ₂和ρ₃分别为E、v和l在代价函数中的权重，且取值范围为区间(0,1)之间的实数；

步骤4.4：计算竞标水下机器人的理论收益τ；

τ＝ε-c(E,v,l)；

其中ε为竞标水下机器人在成功完成围捕任务后所得奖励值；

步骤4.5：计算竞标水下机器人的能力值f；

f(τ,p)＝λ₁τ+μ₁p；

其中λ₁和μ₁为调节系数，且λ₁+μ₁＝1；

步骤4.6：计算竞标水下机器人的竞标值b_i；

b_i＝αf(τ,p)+βg(v,l)

其中α和β为系数，且α+β＝1。

本发明的有益效果在于：

本发明针对传统拍卖算法中拍卖者身份的缺陷和竞标值存在的不足导致围捕者的选定过程安全性差和决策效率低的问题提出了一种基于改进拍卖算法的围捕者决策方法，作为围捕者的决策方法，用来选定围捕者。本发明通过引入几何中心原理，改变了传统确定拍卖者身份的方式，进而加快了拍卖过程，提高了决策效率，增强了决策过程的安全性；通过改进竞标值函数，来确定最佳的围捕者身份，提高了整体的围捕效率。

附图说明

图1是本发明中确定拍卖者的流程图。

图2为本发明中围捕过程的流程图。

具体实施方式

下面结合附图对本发明做进一步描述。

在围捕者的决策方法中，基于市场机制的传统拍卖算法深受青睐。本发明针对传统拍卖算法中，拍卖者身份的缺陷和竞标值存在的不足，导致围捕者的选定过程安全性差和决策效率低的问题，提出了改进拍卖算法，作为围捕者的决策方法，用来选定围捕者。改进后的拍卖算法，通过引入几何中心原理，改变了传统确定拍卖者身份的方式，进而加快了拍卖过程，提高了决策效率，增强了决策过程的安全性；通过改进竞标值函数，来确定最佳的围捕者身份，提高了整体的围捕效率。

本发明针对传统拍卖算法中拍卖者身份的缺陷和竞标值存在的不足导致围捕者的选定过程安全性差和决策效率低的问题提出了改进拍卖算法，作为围捕者的决策方法，用来选定围捕者。

水下机器人编队成员数量记为m个，各成员坐标记为(x_i，y_i，z_i)，在实际的海洋环境中，平面坐标可参考经纬度，纵向可参考水深。

步骤001.水下机器人编队搜索并发现目标后，目标发现者计算编队队形几何中心。

步骤001具体包括：

步骤00101.初始化数据。水下机器人编队成员数量记为m个，各成员坐标记为(x_i，y_i，z_i)，在实际的海洋环境中，平面坐标可参考经纬度，纵向可参考水深。

步骤00102.编队中各个成员坐标是(x_i，y_i，z_i)

步骤00103.发现目标后计算编队队形几何中心也就是m是编队机器人数量：

步骤002.目标发现者计算距离几何中心坐标最近的水下机器成员，并确定该成员为拍卖者。

步骤002具体包括：

步骤00201.编队中的水下机器人与几何中心最小距离为

步骤00202.确定具有最小距离的水下机器人为拍卖者。

步骤003.目标发现者将目标的坐标位置，移动速度，以及计算后确定的拍卖者身份信息、拍卖者的坐标打包发送给水下机器人编队的其他所有成员。

步骤004.拍卖者开始拍卖，持续时间周期T。竞标水下机器人分别计算自己的竞标值，然后将各自的竞标值分别发送给拍卖者。

步骤004具体包括：

步骤00401.竞争者收到数据后开始按如下步骤计算竞标值；

步骤00402.计算竞标机器人相对目标的能力g；

g(v,l)＝λ₃v+μ₃l

v为竞标水下机器人相对于目标的移动速度优势比，v₁为竞标水下机器人的速度，v₂为目标的速度；l为竞标水下机器人相对于目标的间距；λ₃和μ₃为调节系数，且λ₃+μ₃＝1；

步骤00403.计算竞标机器人当前状态p；

p＝λ₂E+μ₂σ

其中E为竞标水下机器人的能量剩余，σ为竞标水下机器人的攻击能力；λ₂和μ₂为调节系数，且λ₂+μ₂＝1；

步骤00404.计算竞标机器人的代价c；

c(E,v,l)＝ρ₁E+ρ₂v+ρ₃l

ρ₁、ρ₂和ρ₃分别为E、v和l在代价函数中的权重，且取值范围为区间(0,1)之间的实数；

步骤00405.计算竞标机器人的理论收益τ；

τ＝ε-c(E,v,l)

ε为竞标水下机器人在成功完成围捕任务后所得奖励值；

步骤00406.计算竞标机器人能力值f；

f(τ,p)＝λ₁τ+μ₁p

λ₁和μ₁为调节系数，且λ₁+μ₁＝1；

步骤00407.计算竞标机器人竞标值b_i；

b_i＝αf(τ,p)+βg(v,l)

α和β为系数，且α+β＝1；

步骤00408.各个竞标机器人将竞标值发送给拍卖者；

步骤00409.当时间超过时间周期T后，关闭拍卖市场。

步骤005.拍卖者根据收到的竞标值和围捕任务需求，对收到的竞标值按从大到小的顺序进行排序筛选确定竞标值前n大的为围捕水下机器人，n为满足围捕任务的最小机器人数。

步骤005具体包括：

步骤00501.将每个竞标者的竞标值与围捕任务需求相比较，满足条件的留下成为准围捕者。

步骤00502.将准围捕者的竞标值从大到小排列，留下前n个，不足n个就全部留下。

步骤006.步骤00601.如果合格的竞标者数量小于n，那么返回步骤004，开启新一轮的拍卖市场，重新计算竞标值。如果合格的竞标者数量大于等于n，那么围捕者决策结束。

步骤007.进入围捕状态，捕捉目标。在围捕成功时间阈值内围捕成功围捕成功，恢复巡航模式。当时间超过围捕成功时间阈值，放弃围捕，恢复巡航状态。

以上所述仅为本发明的优选实施例而已，并不用于限制本发明，对于本领域的技术人员来说，本发明可以有各种更改和变化。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。

Claims (3)

1.一种基于改进拍卖算法的围捕者决策方法，其特征在于，包括以下步骤：

步骤1：水下机器人编队搜索并发现目标后，目标发现者计算编队队形几何中心；

步骤2：目标发现者计算编队中所有水下机器人成员与几何中心之间的距离，并选择与几何中心距离最近的成员为拍卖者；

步骤3：目标发现者将目标位置、移动速度以及计算后确定的拍卖者身份信息打包发送给水下机器人编队的其他所有成员；

步骤4：拍卖者开始拍卖，持续时间周期T，竞标水下机器人分别计算自己的竞标值，然后将各自的竞标值分别发送给拍卖者；当时间超过时间周期T后，关闭拍卖市场；

步骤5：拍卖者根据收到的竞标值和围捕任务需求，将每个竞标水下机器人的竞标值与围捕任务需求相比较，满足条件的留下成为准围捕者；将准围捕者的竞标值从大到小排列，筛选确定竞标值前n大的为围捕水下机器人；n为设定满足围捕任务的最小机器人数；

步骤6：如果满足条件的竞标者数量小于n，则返回步骤4，拍卖者开启新一轮的拍卖市场，重新计算竞标值；如果合格的竞标者数量大于等于n，则围捕者决策结束；

步骤7：进入围捕状态，如果超过围捕成功时间阈值还未围捕成功，则放弃围捕；围捕成功后水下机器人编队回到巡航模式。

2.根据权利要求1所述的一种基于改进拍卖算法的围捕者决策方法，其特征在于：所述的步骤1中计算编队队形几何中心的方法为：根据实际环境中水下机器人的经纬度确定平面坐标，根据参考水深确定纵向坐标，编队中每个水下机器人成员坐标记为(x_i,y_i,z_i)，则编队队形几何中心的计算公式为：

其中m为编队中水下机器人成员的数量，点为编队队形几何中心；编队中水下机器人P_i与几何中心之间距离的计算公式为：

3.根据权利要求1或2所述的一种基于改进拍卖算法的围捕者决策方法，其特征在于：所述的步骤4中竞标水下机器人的竞标值的计算方法为：

步骤4.1：计算竞标水下机器人相对于目标的能力g；

g(v,l)＝λ₃v+μ₃l

其中v为竞标水下机器人相对于目标的移动速度优势比，v₁为竞标水下机器人的速度，v₂为目标的速度；l为竞标水下机器人相对于目标的间距；λ₃和μ₃为调节系数，且λ₃+μ₃＝1；

步骤4.2：计算竞标水下机器人当前状态p；

p＝λ₂E+μ₂σ

其中E为竞标水下机器人的能量剩余，σ为竞标水下机器人的攻击能力；λ₂和μ₂为调节系数，且λ₂+μ₂＝1；

步骤4.3：计算竞标水下机器人的代价c；

c(E,v,l)＝ρ₁E+ρ₂v+ρ₃l；

其中ρ₁、ρ₂和ρ₃分别为E、v和l在代价函数中的权重，且取值范围为区间(0,1)之间的实数；

步骤4.4：计算竞标水下机器人的理论收益τ；

τ＝ε-c(E,v,l)；

其中ε为竞标水下机器人在成功完成围捕任务后所得奖励值；

步骤4.5：计算竞标水下机器人的能力值f；

f(τ,p)＝λ₁τ+μ₁p；

其中λ₁和μ₁为调节系数，且λ₁+μ₁＝1；

步骤4.6：计算竞标水下机器人的竞标值b_i；

b_i＝αf(τ,p)+βg(v,l)

其中α和β为系数，且α+β＝1。