Genetic Algorithm Based Combinatorial Auction Method for Multi-Robot Task Allocation

An improved genetic algorithm is proposed to solve the problem of bad real-time performance or inability to get a global optimal/better solution when applying single-item auction （SIA） method or combinatorial auction method to multi-robot task allocation. The genetic algorithm based combinatorial auction （GACA） method which combines the basic-genetic algorithm with a new concept of ringed chromosome is used to solve the winner determination problem （WDP） of combinatorial auction. The simulation experiments are conducted in OpenSim, a multi-robot simulator. The results show that GACA can get a satisfying solution in a reasonable shot time, and compared with SIA or parthenogenesis algorithm combinatorial auction （PGACA） method, it is the simplest and has higher search efficiency, also, GACA can get a global better/optimal solution and satisfy the high real-time requirement of multi-robot task allocation.

基于改进拍卖算法灾后救援多无人机任务分配

为提高灾后无人机(UAV)救援的效率,本文研究多无人机灾后侦察任务分配问题。考虑无人机续航时间、灾区地形以及是否遇到飞行障碍等因素,以无人机执行任务总时间最小为优化目标建立多无人机侦察任务分配模型,设计了混合动态规划的改进拍卖算法(hybrid dynamic programming auction, HDPA)求解模型。首先将无人机执行任务所需时间价值化,以单无人机执行任务所获收益最大为优化目标,设计动态规划算法获得单无人机执行任务最优序列作为初始投标方案,以防止拍卖算法陷入局部最优、提高算法的收敛速度;其次设计价格更新机制,解决投标任务之间的冲突,最终获得多无人机侦察任务分配最佳方案。实验结果表明,各无人机执行任务较为均衡,完成任务的总时间与传统的拍卖算法、遗传算法、海洋捕食者算法(marine predators algorithm, MPA)相比平均缩短了3.5%、5.6%、4.75%。

通信约束下UAV集群协同拦截任务分配算法

针对多无人机协同拦截多机动目标的任务分配问题,同时考虑到真实战场环境中存在的通信约束以及探测范围约束条件,本文提出了分步一致性拍卖算法(SCBAA)。首先,对真实战场环境中存在的通信约束以及探测范围约束等问题进行了描述分析,构建了多无人机协同拦截任务分配模型,设计了综合效能函数以及相应约束条件。其次,为解决多无人机协同打击单一目标的不平衡任务分配以及冲突消解问题,将原任务分配过程分为主要任务分配以及次要任务分配两部分,通过多次拍卖以及冲突消解实现多无人机对单一目标的任务分配。仿真结果表明,该算法可有效解决通信约束条件下的分布式多无人机协同拦截问题,并适应动态环境中任务分配对实时性的要求。

基于目标威胁评估的传感器调度方法

提出了一种基于目标威胁评估的传感器调度方法。基于现有可获得的目标参量,利用先验知识和目标属性获得隶属度,构建贝叶斯动态模型,实现对不同目标威胁评估。在目标威胁评估结果的基础上,综合任务最后执行时间、任务执行窗口等信息,根据最大收益理论建立多目标探测框架下的传感器调度模型。针对不同场景,采用改进的拍卖算法进行传感器调度仿真,通过任务调度成功率、平均时间偏移、算法效率等评估指标验证了模型可行性和调度算法的有效性。

Multiple targets vector miss distance measurement accuracy based on 2-D assignment algorithms

An extension of 2-D assignment approach is proposed for measurement-to-target association for improving multiple targets vector miss distance measurement accuracy. When the multiple targets move so closely, the measurements can not be fully resolved due to finite resolution. The proposed method adopts an auction algorithm to compute the feasible measurement-to-target assignment with unresolved measurements for solving this 2-D assignment problem. Computer simulation results demonstrate the effectiveness and feasibility of this method.

基于DQN出价策略的多无人机目标分配拍卖算法

为实现多无人机监测目标分配任务匹配度、成功率等收益最大化及路径长度、障碍物碰撞风险等代价最小化,基于数据样本驱动的强化学习方法,提出了一种融合深度Q网络(Deep Q-network,DQN)出价策略的自主进化拍卖算法。首先,构建了多无人机任务目标拍卖的马尔科夫决策模型,并且分别以竞拍者剩余竞拍容量为环境,输出增价因子为动作,前后两轮拍卖收益增幅为回报。其次,构建了新型的DQN出价和竞拍决策神经网络模型。该模型通过构建包含拍卖环境、增价因子、回报等元素的强化学习训练样本库,在拍卖过程中以一种离线学习模式不断训练DQN神经网络,使其按照DQN策略在拍卖过程中,根据拍卖环境输出增价因子,实现拍卖结果收益的优化。最后,通过多无人机多监测目标分配仿真,验证了所提出基于DQN拍卖机制的目标分配方法的有效性。通过与传统拍卖算法结果相比,方法获得的拍卖收益提升21.4%。

基于拍卖多智能体深度确定性策略梯度的多无人车分散策略研究

多无人车(multi-UGV)分散在军事作战任务中应用非常广泛,现有方法较为复杂,规划时间较长,且适用性不强。针对此问题,该文提出一种基于拍卖多智能体深度确定性策略梯度(AU-MADDPG)算法的多无人车分散策略。在单无人车模型的基础上,建立基于深度强化学习的多无人车分散模型。对MADDPG结构进行优化,采用拍卖算法计算总路径最短时各无人车所对应的分散点,降低分散点分配的随机性,结合MADDPG算法规划路径,提高训练效率及运行效率;优化奖励函数,考虑训练过程中及结束两个阶段,全面考虑约束,将多约束问题转化为奖励函数设计问题,实现奖励函数最大化。仿真结果表明:与传统MADDPG算法相比,所提算法在训练时间上缩短了3.96%,路径总长度减少14.50%,解决分散问题时更为有效,可作为此类问题的通用解决方案。

基于线性波门改进拍卖算法的航迹关联算法研究

针对分布式探测系统中多源传感器航迹关联问题,常用的基于距离统计构建关联代价矩阵,拍卖算法求解关联结果的流程在面临探测区域中目标数量大,目标航迹分布密集的场景时,会出现关联准确率下降及关联时间长的问题。提出了一种基于线性波门改进的拍卖算法来改进现有关联算法在面临上述场景时的关联性能。考虑传感器的测量偏差对距传感器远的目标航迹数据影响大于距离近的目标,因此设计了与距离有关的线性波门对可能关联的目标航迹筛选。仿真数据结果表明,提出的线性波门能够对传统拍卖算法在大批次目标下提升关联准确率和降低关联时间,证明了线性波门的有效性,对实际多源传感器航迹关联问题具有重要意义。

最短路径Auction算法及其在路径诱导中的应用

通过采用C#语言程序,对比传统路径算法,并在实际道路网络和随机网络中进行了试验,测试了算法在求解网络"一对一"最短路径问题时的运算性能.结果表明,Auction算法在求解此类问题时,体现算法自身原理的优势,虽然整体性能表现不及经典的路径算法,即迭代步骤略多,但仍有改进的余地.

最短路问题的Auction算法在无圈网络中的改进

提出了Auction算法在无圈网络中的一种改进。在改进的新算法中,采取了新的推进(extension)方式,从而成功地降低了算法的复杂性。改进后算法的复杂性为O(m),此处m是图的弧数。

计及购电需求不确定性的微电网能源竞价交易模型

微电网可以将发电高峰期盈余的可再生能源出售来促进可再生能源消纳并获取最大收益。采用拍卖机制确定交易价格,但交易过程中购电需求的变化也会对可再生能源消纳及微电网收益产生影响,为此,提出一种计及购电需求不确定性的微电网能源竞价交易模型。首先采用统一价格同步向上叫价拍卖机制进行定价,并提出了拍卖机制的改进方案来平衡用能消费者的对不同时段的拍卖需求;考虑到用能消费者的购电需求不确定性,采用鲁棒线性优化算法来规避不确定性参数对最优解的影响。最后通过MATLAB软件仿真分析,证明了该模型能够最大限度地提高可再生能源的出售率及微电网的收益。

Evolutionary Techniques for Reverse Auctions

Winner determination is one of the main challenges in combinatorial auctions. However, not much work has been done to solve this problem in the case of reverse auctions using evolutionary techniques. This has motivated us to propose an improvement of a genetic algorithm based method, we have previously proposed, to address two important issues in the context of combinatorial reverse auctions: determining the winner(s) in a reasonable processing time, and reducing the procurement cost. In order to evaluate the performance of our proposed method in practice, we conduct several experiments on combinatorial reverse auctions instances. The results we report in this paper clearly demonstrate the efficiency of our new method in terms of processing time and procurement cost.

面向反导预警作战的多传感器任务分配拍卖方法

针对在多方向多波次反导预警作战中,由于预警资源有限甚至不足,无法有效保障弹道导弹目标搜索、跟踪、识别的问题,提出一种面向反导预警作战的多传感器任务分配拍卖方法。首先,根据反导预警作战任务分配的特点,提出了一种任务分解策略,实现对反导预警作战的分解;接着,针对预警资源有限甚至不足情况下弹道目标探测的问题,考虑时间资源、预警资源分配和任务连续性等约束,建立以高任务完成度、低传感器交换次数和低有效时间资源消耗为目标函数的多约束多目标传感器分配优化模型;然后,结合多约束多目标多传感器分配优化模型和拍卖算法,提出多传感器任务分配策略求解反导预警作战任务分配问题;最后,通过数值仿真验证分解策略、多约束多目标传感器分配优化模型和多传感器任务分配拍卖方案的有效性。

基于改进蛙跳算法的多无人机协同任务分配研究

针对多无人机协同任务分配问题,提出了一种基于Levy飞行的改进随机蛙跳算法用于解决多无人机的协同任务预分配问题,通过引入动态跳跃步长、Levy飞行因子和族群认知因子有效改进了算法的搜索性能,提高了搜索效率。针对多无人机协同执行任务时可能遭遇的突发任务,通过引入市场拍卖机制提高了算法的计算收敛效率。通过仿真算例分析,验证了改进的随机蛙跳算法解决多无人机协同任务分配问题的有效性。

考虑源荷不确定性的多微电网鲁棒优化调度与VCG机制竞价策略

现代微电网集群新能源就地消纳的高效性和调度策略规避风险的能力日益受到关注,其与源荷不确定性和微电网之间的交互模式密切相关。为此,基于维克瑞–克拉克–格罗夫斯交易机制(Vickrey-Clarke-Groves,VCG)和鲁棒优化理论,提出了多微电网两阶段鲁棒优化调度模型,第1阶段:“新能源互补交易–净负荷波动平抑–余负荷功率平衡”优化调度模型,首先直接针对微电网间余缺新能源进行互补竞争性交易,引入VCG机制应对微电网谎报估值的行为,合理匹配余缺新能源,实现新能源高效就地消纳;再基于储能平抑拍卖之后的净负荷功率波动,综合考虑净负荷均方差和储能成本最小,优化储能充放电策略;最后通过可控机组以及与配电网交互实现余负荷功率平衡。第2阶段:不确定性决策校正模型,根据不确定性实际出现的情况对第1阶段的优化决策进行校正。采用列约束生成算法(columnand constraint generation algorithm,C&CG)求解优化模型,通过两阶段交互迭代以寻找恶劣场景,并得到该恶劣场景下微电网间的交易策略以及各设备功率调度计划。仿真结果验证了所提策略的有效性。

面向多机器人环境中动态异构任务的细粒度动作分配与调度方法

在多机器人环境中,具有不同能力的机器人相互协作以完成任务需求。现实情况下,这些任务动态发布,且具有不同的目标和紧急程度,因此需要为每个任务分解出的细粒度动作分配和调度合适的机器人来负责执行这些动作。现有的方法大多适用于静态和同构的任务分配场景,而针对动态异构任务的分配则大多采用独占式的分配策略,导致机器人频繁进入等待状态(即机器人处于被分配了任务到真正开始执行任务之间的闲置阶段)。由于任务存在不同的紧急程度和发布时间,这种分配方式将降低对更紧急任务的响应效率,同时导致更多的等待时间和更长的任务完成时间。针对该问题,提出了一种面向多机器人环境中动态异构任务的细粒度动作分配与调度方法。其中,分配与调度的对象是任务所分解出的细粒度的动作,且一个动作能够由机器人的一种能力承担。面对任务分解出的一组细粒度动作集合,本方法借鉴拍卖算法过程,根据机器人能力、状态及任务信息计算出机器人承担特定动作的最优分配方案。另外,在每一次新任务发布或某一机器人执行完动作时执行分配和调度过程,可以将处于普通任务等待状态的机器人调度至紧急任务,以保证紧急任务优先完成,且缩短机器人的总体等待时间。基于本方法,扩展实现了机器人执行框架(ROSPlan)的执行模块。围绕一组多机器人动态异构任务的模拟实验表明,所提方法相较于采用贪心策略的方法可得到更优的分配方案。

考虑子系统执行能力的多无人机协同任务规划

任务分配是提高无人机运维效率的关键技术之一。针对子系统执行能力约束条件下的无人机蜂群协同任务分配问题,提出一种融合拍卖机制的改进狼群算法。首先,定义子系统能力矩阵以实现无人机异构性和任务执行能力的统一描述。其次,对个体狼采用矩阵编码,针对违反攻击次数的非可行解,提出基于拍卖机制的修正策略,以进行处理。然后,在个体狼位置更新过程中融入遗传算法思想,在探索阶段和围捕阶段分别进行相邻行交换操作和间隔列交叉操作,以实现快速寻优。最后,将第三优狼引入到狼群更新过程中,从而增强种群的多样性。仿真实验结果表明,所提方法能够有效求解子系统执行能力约束下无人机蜂群协同任务规划问题;且相比于其他改进进化算法,所提方法具有更好的寻优性与收敛速度。

面向雷达多目标跟踪应用的专用片上系统设计

针对雷达多目标跟踪应用对于计算平台的浮点算力和实时性要求,设计一种基于主处理器加专用加速器架构的低延迟片上系统。通过对多目标跟踪算法各个步骤的深入分析,分别以通道加速器和自定义扩展指令两种形式实现了面向该算法的专用加速器,在FPGA平台上进行专用片上系统原型验证。采用典型数据集测试的结果表明,两种加速器能够有效提升计算平台的整体算力,提高系统的实时性。

基于市场机制的无人集群任务分配研究综述

市场机制的方法数学推导严谨,理论解释清晰,算法计算量小,对网络规模和拓扑结构限制少,适合未来军事领域大规模无人集群任务规划问题。围绕基于市场机制的无人集群任务分配的拍卖法和合同网法两类方法,详细梳理了该研究领域的经典文献和近年来的相关研究;从该方法的基本原理、改进研究进展、应用背景和使用局限性等方面进行了详细介绍和全面总结;最后提出了基于市场机制任务分配研究中的关键问题和未来研究趋势。

分布式卫星集群博弈任务均衡分配方法

针对分布式卫星集群博弈任务中的分配不均衡问题,提出了一种基于偏好联盟博弈(hedonic coalition game, HCG)的任务分配方法。首先,在考虑燃料和时间最优的卫星集群任务分配模型的基础上,引入对敌毁伤概率以适应集群博弈背景;其次,为保证分配结果的均衡性,引入HCG设计个体联盟特征函数;最后,考虑卫量集群的一对多作战分配方式难以保证局部兵力优势,在一致性拍卖算法(consensus based auction algorithm, CBAA)结构上拓展性地提出了一种多对一任务分配算法。仿真结果表明,该算法在全局效益接近经典集中式算法全局效益98%的前提下,时间约为经典算法的70%,且该算法具有一定的问题规模拓展性。