李 岩， 邢胜伟， 张英俊

(大连海事大学 航海学院，辽宁 大连 116026)

海上搜救行动是保障海上生命和财产安全的最后一道防线，建立高效的海上搜救决策系统能够极大地减少海上人员伤亡和财产损失。执行海上搜救行动包括确定海上搜寻区域和分配海上搜寻任务两个关键技术。其中，海上搜寻任务分配问题就是利用确定的搜寻区域去优化分配搜寻资源，制定搜寻计划，使得在最短的时间内，动用最少的搜寻资源确定遇险人员或船舶的位置。

海上搜寻任务分配问题一直是海上搜救方面的研究重点。KOOPMAN[1]提出的搜索论是最早的关于海上搜寻资源优化分配的理论，对指导海上搜救行动影响深远。文献[2]通过对海上船舶遇险形式及可能造成的后果进行分类及分析，提出了海上救助船舶的择优选取原则与方法。文献[3]通过BP(Back Propagation)神经网络训练获得海上搜救中救助船优选决策因素权重值，从而确定合适的救助船。文献[4]通过建立0～1规划数学模型，通过分析不同船舶总量限制条件下的最优值与搜寻成本之间的关系，得出经济、可行的搜寻方案。文献[5]采用3种多目标优化选择方法解决海上搜寻救助船舶的优选问题并且证明了3种方法的可行性。海上搜寻是一个动态的过程，搜寻资源和时间有限，搜寻区域和参与搜寻的搜救力量的状态变化多端，上述文献大部分采用过于理想化的数学模型，不能完全适用于实际的海上搜寻环境。

近年来，随着人工智能的发展，多智能体系统(Multi-Agent System, MAS)的应用研究也越来越广泛，基于MAS的任务分配问题也逐渐成为当前的研究热点[6]。拍卖是一种快速和有效的资源分配方法，具有较强的可操作性，自从金涬等[7]提出将拍卖机制引进MAS后，随之而来对基于拍卖规则的MAS任务分配问题研究的也越来越多。文献[8]分别提出了基于拍卖的多智能体任务分配算法并在机器人救火中进行仿真，验证了算法的有效性。文献[9]和文献[10]设计一个基于拍卖的任务分配系统MURDOCH，指导机器人协同工作。

由上述研究可看出，基于拍卖规则的多智能体任务分配方法在多个领域具有广泛的应用，但是，目前将其应用于海上搜寻任务分配的研究较少。因此，本文提出将拍卖规则算法应用于解决海上搜寻任务分配问题，设计一种基于改进拍卖规则的多智能体海上搜寻任务分配方法。该方法满足目前海上搜寻任务分配问题的实际情况，能够适应动态变化的海上搜寻环境，能够利用有限的搜寻资源，为决策人员提供最优的问题解决方案，具有较强的实用性。

1 拍卖规则模型

拍卖是人类社会中的一种经济现象，卖方和买方根据规定的拍卖规则达成交易，实现资源的合理分配。对传统的拍卖模型进行适当改进可以使其适用于多智能体的任务分配，基本的模型如下：

Auc=

(1)

(2)

由上述模型可以看出，在拍卖过程中存在两种智能体：拍卖智能体A和竞拍智能体B。A可以通过规定的选择标准决定竞拍的优胜者，这些优胜者将共同协作完成任务。

2 海上搜寻任务分配

基于上述研究表明，拍卖规则可以实现最优的任务分配问题。针对海上搜寻任务分配问题的特点，对拍卖规则进行适当的改进可使其满足海上搜寻任务分配的需求。

2.1 海上搜寻任务分配的拍卖模型

以我国海上搜救组织形式为例，我国海上搜救指挥机构分为3级，即中国海上搜救中心、省级海上搜救中心和市级海上搜救中心[11]。各级海上搜救中心统一负责协调辖区内海上搜救任务，因此，各级海上搜救中心即为拍卖智能体。事故区域附近的过往船舶和专业的救助船舶即为竞拍智能体。各智能体之间关系见图1。

2.1.1拍卖智能体

当海上搜救中心接到海上搜寻任务T后，着手对该任务进行拍卖，海上搜救中心智能体即为拍卖智能体A。海上搜救中心需要向过往船舶及专业救助船舶等搜救力量发布搜寻任务信息，即向其他智能体公布拍卖信息，并等待它们对任务T进行竞拍。因为需要在实时环境中进行快速的任务分配，所以规定每一轮拍卖的时间限制，当一轮拍卖结束后，拍卖智能体A根据竞价标准选择出价最高的N个智能体为竞标成功智能体，竞拍成功智能体将共同协作完成该任务，至此，竞拍活动结束。拍卖智能体的拍卖流程见图2。

2.1.2竞拍智能体

当过往船舶或专业救助船舶等接收到海上搜救中心发布的搜寻任务信息，即拍卖智能体A发布的拍卖信息，如果同意参与搜寻任务即同意竞拍，则该搜救力量智能体即成为竞拍智能体B。计算投标价格，向拍卖智能体A发送竞标消息。若竞标成功，则该智能体将与其他竞标成功智能体协作完成该任务。竞拍智能体的竞拍流程见图3。

2.2 海上搜寻任务分配的改进拍卖规则

2.2.1限制拍卖信息发布范围

当海上搜救中心确定了搜寻区域后，需要选择合适的搜寻力量进行任务分配。由于海上搜寻任务的特殊性，搜寻设施选择应掌握以下几个原则：

(1) 优先指派专业搜寻力量原则;

(2) 就近指派搜寻力量原则;

(3) 搜寻力量足够原则。

牛皮糖瞟了一眼保安，那个保安十分年轻，还像一个毛都没有长全的雏鸡。他倒真没有把他当回事。就说，我找镇长。

因此，为尽量缩短搜救反应时间，避免不必要的通信资源浪费，搜救中心智能体应该将拍卖信息优先发布给专业的搜救力量智能体，并设定初始反应时限tl，计算事故周围船舶到达事故现场的时间ta，可以向ta≤tl的船舶发送拍卖信息，如果满足条件的船舶数量过少，可以适当调高tl，以满足搜寻设施足够原则。

2.2.2调整竞拍价格计算方法

原始的拍卖机制是，拍卖智能体从参与竞拍的n个竞拍智能体中选择竞拍价格从高到低的N个竞拍智能体为竞拍成功智能体。因此，竞拍价格是决定最后选择智能体质量的关键。在海上搜寻任务中，搜寻力量的选择应该是满足到达事故现场时间短、搜寻速度快等条件的船舶。因此，应该首先确定船舶效益型属性(例如船舶类型、搜寻速度等)和成本型属性(例如到达搜救现场的时间等)。船舶效益型和成本型属性的确定可根据现场情况调整。竞拍价格应为总效益值与总成本值的差值为

Gi=ω1×Yi+ω2×Vi

(3)

Ci=ω3×ti

(4)

Pi=Gi-Ci+ε

(5)

式(3)～式(5)中:i为正整数，i∈[1,n]，P为各搜寻力量所出的竞拍价格；Y、V、t分别为船舶类型值，船舶搜寻速度值和船舶到达事故现场时间值；ε为调整系数，以防止竞拍价格为负值；ω1、ω2、ω3分别对应着上述3种属性值所占权重值，各权重值的确定可以根据海上搜寻专家知识库或者海上搜寻经验获得，也可以根据各任务情况的不同做出适当的调整。同时,为防止各属性值在评价中被不适当的放大，采用文献[12]中的归一化方法对各属性值进行处理。其计算为

(5)

2.2.3任务分配的动态调整

海上搜寻目标其位置因风和流的作用而随时间变化，因此，搜寻行动如果时间跨度较大，则需要分阶段调整搜寻区域，使搜寻目标始终处于搜寻区域之内。并且,如果获得了新的遇险信息或者搜寻设施的状态发生改变，也需要调整搜寻区域和任务分配。海上搜寻任务分配的动态调整规则如下：

(1) 任务开始执行后，如果有搜寻力量智能体由于自身原因中途退出，则搜救中心智能体对该退出搜寻力量智能体执行的任务进行重新拍卖，正在参与搜寻任务的搜寻力量智能体如任务完成可参与竞拍，如任务未完成则不可参与竞拍;

(2) 初始搜寻行动结束后，如未找到搜寻目标，则对搜寻区域进行调整，搜救中心对出现的新任务进行拍卖，此时，完成搜寻任务的搜寻力量智能体均可参与竞拍;

(3) 如未调整区域之前，搜寻力量智能体已完成搜寻任务，并且此时还有区域没有被搜寻，则可单独向搜救中心智能体申请竞拍新搜寻任务。

2.3 海上搜寻任务分配流程

3 仿真试验

假设某一海上搜寻任务，搜寻目标是一落水人员，待搜寻区域面积为300 (n mile)2，海上搜救中心智能体确定搜寻区域后，着手对搜寻任务进行分配，即进行拍卖。为了快速开始搜寻行动，需要限制拍卖信息发布范围，将初始反应时限设置为2 h，则满足条件的搜寻力量见表1。船舶类型属性值可以根据文献[12]中的方法确定，专业型救助船舶的船舶类型属性值设为5，其他船舶设为2。

表1 满足拍卖条件的船舶信息

上述船舶接收到搜救中心智能体发送的拍卖信息后，全部决定参与竞拍，这6艘船舶都为竞拍智能体，通过向专家咨询及相关海上搜救经验设置权重系数ω1=0.3,ω2=0.2,ω3=0.5,ε=1，对竞拍智能体的属性值进行归一化处理并给出各自的竞拍价格见表2。

表2 归一化属性值及竞拍价格表

按照竞拍价格高低顺序船舶序号依次为1,2,3,5,6,4。4号船舶到达现场时间过长且搜寻速度不快，不利于搜救行动；6号船舶虽然搜寻速度较快，但是到达现场的时间没有3号和5号船舶短。结合竞拍价格高低，选择1,2,3,5号船舶共同参与搜救行动，选择结果符合实际情况。结合搜寻船舶进入搜寻现场的切入点，考虑搜寻船舶的搜寻速度等因素分别为各搜寻船舶分配不同大小的搜寻区域搜寻行动区域分配见图5。

如果现场持续搜寻时间4 h过后仍然没有搜寻到落水人员，则搜救中心智能体需要对搜寻区域进行调整，这时将会有新的搜寻任务出现，需要更多的智能体参与搜救，则搜救中心智能体将对新任务进行拍卖，并从参与竞拍的智能体中选出最后的竞拍成功智能体。如果完成搜救任务的船舶愿意接着参与搜寻行动，也可参与新任务的竞拍。调整后的搜寻行动区域分配见图6。

从上述仿真结果可知，基于拍卖规则的海上搜寻任务分配中，选择竞拍价格最高的搜寻力量是满足任务分配模型的最优解，并且能够动态调整任务分配模型，具有较高的鲁棒性。

4 结束语

本文提出了一种基于改进拍卖规则的多智能体海上搜寻任务分配方法，该方法能够针对海上搜寻现场实际情况选择最优的搜救力量参与搜寻行动并能够在搜寻现场环境发生变化时动态调整搜寻任务分配，提高海上搜寻效率，具有较强的实用性。但是，本文计算竞拍价格时只考虑了船舶类型等几个属性，实际应用中可以针对不同的海上搜寻任务场景选择不同的属性值以及调整权重系数。