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.

基于联盟链的双向拍卖碳交易

碳交易是降低温室气体排放、发展低碳经济的重要方式。在传统碳交易过程中主要存在主体分布广、数据互通性差和效率低等问题,而通过带有准入机制的联盟链作为碳交易的基础设施,可确保交易数据的安全性与可溯源性。因此,提出一种基于联盟链的双向拍卖交易算法。所提算法考虑用户满意度,分2个阶段执行。在第1阶段,所有节点提出报价范围,符合条件的节点将在该阶段立刻达成交易;剩余交易节点进入第2阶段,计算交易量匹配度,以用户整体满意度为优化目标进行匹配,从而输出最大整体满意度的结果。所提算法与匈牙利算法、GS(GaleShapley)算法的对比实验结果表明,所提算法提高了用户满意度,且让平均匹配时间分别降低了26.2%和36.0%。所提算法利用HLF(HyperLedger Fabric)部署双向拍卖算法智能合约,自动计算和处理用户交易请求,并把交易的结果经过共识记录在联盟链的通道账本,在不同的区块大小和交易请求数下实现了稳定的交易吞吐量。

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

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

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

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

基于神经网络剩余时间估计的导弹-目标动态分配方法

针对防空导弹动态目标分配问题,设计了一种基于神经网络的剩余飞行时间预测方法,该方法在计算中不仅考虑了弹目相对距离和导弹运动状态,还考虑了敌方目标的运动状态对预测结果的影响,提升了预测精度;结合该方法建立了综合考虑距离优势、角度优势和剩余飞行时间优势的目标分配模型,采用拍卖算法对该模型进行求解,给出整体最优的目标分配方案。仿真结果表明:神经网络模型的测试集预测误差在1 s以内,低于经典算法,拍卖算法的重分配计算用时能够满足系统的实时性要求。

多智能物资运送小车协同控制的任务分配

针对进一步提升物资运送智能车的使用效率及多智能体协作任务分配不合理问题,提出一种基于区域划分拍卖算法的多车协同控制的任务分配策略。首先,对已知环境根据任务的密集程度进行区域划分,实现全局环境的任务处理。其次,按任务类型划分不同的处理方式,即局部任务通过使用优化的拍卖算法处理任务,进而提高多车协同的使用效率;全局跨区域任务使用二层框架完成点对点任务处理。最后,在全局已知的环境下进一步仿真算法,对比打击类型无人机的任务分配算法。结果表明,该算法的性能对智能车使用效率更高、任务的承载能力更强、任务分配策略更合理,在对多车协同控制解决任务分配的问题上能高效实施,简化复杂的任务分配过程。

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

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

最短路径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)求解优化模型,通过两阶段交互迭代以寻找恶劣场景,并得到该恶劣场景下微电网间的交易策略以及各设备功率调度计划。仿真结果验证了所提策略的有效性。

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

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

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

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