基于改进蚁群算法的多机器人任务分配方法

研究了动态环境下多机器人对多目标点的探测;针对通常采用的是单物品拍卖的方法进行任务分配但是无法得到全局最优解的缺点,提出了用组合拍卖的方法来解决多机器人的任务分配问题;由于组合拍卖(WDP)本身是一个NP-hard的问题,所以文中通过对蚁群算法进行改进,成功地解决了此类任务分配问题;实验表明,该算法有效地缓解了容易出现的早熟停滞现象,达到较好的最优解,收敛速度快且求解质量稳定,满足了多机器人动态任务分配的要求。     

基于组合拍卖的多机器人任务死锁解决方法

针对多机器人搜集任务中可能出现的任务死锁现象,采用基于组合拍卖的方法来解决这一问题。提出了一种拍卖树方法,用来解决组合拍卖计算量过大的问题。仿真实验结果表明该方法不仅能够消除多机器人的任务死锁,而且能够在解决死锁问题的同时优化多机器人任务分配结果。     

基于线性结构的逆向组合拍卖算法研究

对逆向组合拍卖的拍卖模型和WDP问题进行了研究,报告了当前逆向组合拍卖的研究现状,分析了对称关联价值模型的基本性质.结合对称关联价值模型分析了WDP的形式化描述,在此基础上提出了基于线性结构的饱和分割区近似算法(LISAPA).该算法避免了项目组合树的建立,并且可以在构造过程中直接由局部最优解扩展到全局最优解,从而显著的提高构造效率.实验结果表明,当拍卖项目组合数大于拍卖项目数时,该算法能够解决中标者确定问题,并且有较好的达优率.     

基于效用函数的多机器人系统任务分配

目前所采用的多机器人系统任务分配方法大多都忽略了任务分配的解质量问题。从定量的角度出发,提出了一种基于效用函数的多机器人系统任务分配策略,在机器人能力向量和子任务要求的能力向量基础上,建立了效用函数的数学模型,根据效用函数大小进行任务分配。仿真实验在足球机器人仿真比赛平台上进行,结果表明该任务分配算法对异构多机器人系统合作具有很好的通用性,且算法快速简单,能够实现任务到机器人的最优映射。     

基于拍卖的多智能体任务分配算法

任务分配是多智能体系统协作关键问题,对此提出一种基于拍卖的多智能体任务分配算法.在限定时间内,利用拍卖算法综合考虑完成任务的效益及各智能体完成任务需付出的代价,得到接近最优的任务分配方案.动态的环境会造成方案滞后,通过动态调整,重要任务可吸引到更多智能体.为减轻动态调整过程的通信负担,引入令牌的概念,由令牌控制智能体发送信息的权利.通过在机器人救援仿真系统中的成功应用,验证了本算法的有效性.     

基于NSGA-II算法的认知无线电频谱分配

认知无线电中,频谱拍卖是解决动态频谱分配的有效方法,其主要目的是最大化所有主用户的收益。然而,主用户间的收益是存在冲突的,给拍卖算法的优化带来了困难。为此,提出一种新的拍卖方案,来解决获胜者确定问题(Winner Determination Problem, WDP)。在该方案中,动态频谱拍卖问题被建模成多背包问题,并通过非支配排序遗传算法II (NSGA-II)得到最终的解决方案。最后,仿真实验结果表明,就解决WDP问题而言,与贪心算法相比,NSGA-II算法有更好的表现。     

多机器人任务分配的研究与进展

从多机器人任务分配的类型、任务分配方法、任务的死锁与解除以及各种任务分配算法的对比等4个方面,对多机器人任务分配的最新研究进展进行了概述.分析了多机器人任务分配的发展趋势,指出动态环境和未知环境下大规模异构机器人任务分配问题的研究是必然趋势,在众多研究方法中,群体智能方法是解决该类问题的未来研究方向.     

面向多机器人动态任务分配的事件驱动免疫网络算法

为实现多机器人系统的动态任务分配与协作,提出了一种面向多机器人动态任务分配的事件驱动免疫网络算法。将生物免疫网络的工作机理应用到多机器人动态任务分配算法中,借鉴Jerne的独特型免疫网络假说和Farmer提出的抗体激励动态方程,设计了多机器人任务分配与自主协作模型;基于事件驱动机制,设计了多机器人动态任务分配算法,并引入焦躁模型来解决任务死锁问题。仿真和实际多机器人系统实验结果表明,基于本文算法的多机器人系统在动态任务场景中具有较强的适应性和自主规划协调能力。     

一种基于近场子集划分的多机器人任务分配算法

针对医护人员重复、机械地配送医疗物资工作效率低的问题,使用了多机器人进行替代,并提出了一种基于"任务地点"近场子集划分的多机器人群体智能任务分配算法.首先采用蚁群算法对任务集进行有序排列,形成一条近场相关的任务链.然后根据任务完成的时间和机器人的路径成本设计目标优化函数,利用遗传算法对该任务链进行子集划分,再将任务子集分配给机器人个体.最后模拟了医院病房的应用场景,设计并搭建了一套多机器人医疗物资运输分配系统.用户在该系统的操作平台上,通过可视化界面能够实时发布新任务,查看已发布任务的分配情况,以及查看机器人的路径.基于该模拟实验平台,对3种不同的任务分配算法进行对比分析,结果是本文算法的分配结果最为合理,所有任务都在规定的时间内完成,机器人的行驶距离大幅缩短.所提出的多机器人任务分配算法可有效解决医疗环境中医疗物资的配送问题,提高了系统的工作效率.     

一种多机器人任务规划算法及其系统实现

针对多机器人任务规划问题,提出了一种蚁群集中式规划方法,建立了任务分配和路由规划的蚁群算法描述模型,并利用局部搜索策略改进了蚁群算法分配效果,实现了多机器人集中任务规划系统.利用该系统平台,进行了大量的实验分析.结果表明,蚁群算法能有效解决多机器人任务规划问题,为多机器人协作机制提供了新思路.     

CPU时间片组合拍卖遗传算法

提出一种综合考虑Agent时间片和执行截止期限要求的CPU时间片组合拍卖遗传算法。该算法定义了问题模型,采用可以去除不具备竞争力标的预选择策略,减少遗传算法的计算复杂度。在遗传算法求解过程中,设计适合该问题的变长染色体编码方式、交叉算子、换序算子和换标算子。仿真实验结果表明,该算法取得了符合要求的最优解。     

基于积极团队情感基调的情感机器人协作任务分配拍卖算法

多机器人系统(Multi Robot System,MRS)通过引入机器人个体情感因素,可以有效提高个体的自主协作能力、决策能力以及多机器人系统的整体智能化水平。然而,以往研究主要集中于个体情感状态(情绪、个性等),缺乏从团队情感层面来探索积极团队情感基调(Positive Group Affective Tone,PGAT)对团队协作能力和团队有效性的影响。为了发挥PGAT在任务分配中的积极作用,降低因为团队成员情绪衰减而导致团队解散的风险,并增加团队协作能力和团队有效性,提出了基于PGAT的情感机器人协作任务分配拍卖算法。仿真追捕对比实验表明,相对于基于焦虑情感模型的改进合同网协议多机器人任务分配算法和基于自主意识的分布式情感机器人任务分配算法,基于PGAT的情感机器人协作任务分配拍卖算法的追捕成功率分别提高了269.3%和6.5%,任务分配成功率分别提高了138.7%和5.1%,平均追捕时间分别缩短了14.5%和26.3%,并且在150场追捕对比实验中,追捕时间小于对比算法的场次占比分别达到87.3%和90.7%。     

混沌优化算法及其在组合优化问题中的应用

混沌优化方法(COA)是针对数值优化问题提出的,在解决数值优化问题上具有一定的普遍性,能够很快地搜索到全局最优解,而利用COA解决组合优化问题存在一定的难度,该文提出了混沌优化算法解决组合优化问题的方法,该方法先产生组合优化问题的初始解,再利用混沌变量产生新解或对原解进行混沌扰动,产生新解,然后在解空间中进行最优搜索。将该方法应用到2个典型的组合优化问题(TSP问题,0/1背包问题)的求解中,仿真实验表明了该方法的有效性。     

一种考虑Agent截止期限的CPU时间片分配算法

提出了一种综合考虑移动Agent执行时间片和执行截止期限要求的CPU时间片组合拍卖混沌遗传算法。该算法在定义了问题模型的基础上,设计了可减少遗传算法计算复杂度的预选择策略,以及变长的染色体编码方式、基于混沌优化技术的两种交叉算子（同父交叉算子和标准交叉算子）,同时设计了基于混沌优化技术的换序算子和换标算子。实验仿真结果表明,该算法可取得优质的最优解。     

0-1背包问题的两种扩展形式及其解法

0-1背包问题是经典的NP-HARD组合优化问题之一,由于其难解性,该问题在信息密码学和数论研究中具有极其重要的应用。首先对01背包问题及其解法进行了分析,然后提出01背包问题的两种扩展形式,并给出了基于动态规划和贪心算法的两种有效算法来解决这两类问题。实验结果验证了所提出方法的有效性。     

基于组合逻辑最小化技术的时序逻辑综合方法

介绍一种以组合逻辑最小化工具为基础，提出按满足压缩状态表约束关系进行状态分配的新思想，通过一系列的转换，可完成从描述时序逻辑的原始状态表到满足该状态表状态转换要求的由ＰＬＡ作为组合逻辑部件的时序逻辑电路的转换。由于该时序逻辑综合新方法在处理过程中要涉及解大型覆盖表的问题，为此提出满足压缩状态表约束关系的状态分配的简化算法。文中用一些实例说明简化算法的具体运算过程。结果表明简化算法可导出满足原始状态表的较简化的时序逻辑表达式。     

Generation of efficient and user-friendly queries for helper robots to detect target objects

We are developing a helper robot that carries out tasks ordered by users through speech. The robot needs a vision system to recognize the objects appearing in the orders. However, conventional vision systems cannot recognize objects in complex scenes. They may find many objects and cannot determine which is the target. This paper proposes a method of using a conversation with the user to solve this problem. The robot asks a question to which the user can easily answer and whose answer can efficiently reduce the number of candidate objects. It considers the characteristics of features used for object identification such as the ease for humans to specify them by word, generating a user-friendly and efficient sequence of questions. Experimental results show that the robot can detect target objects by asking the questions generated by the method.     

基于组合拍卖机制的移动Agent投标策略

针对Agent系统资源分配需求提出一种兼顾Agent时间片数量要求和执行截止期限要求的投标策略。定义CPU时间片组合拍卖问题模型,设计Agent各种投标信息处理方法,包括适合组合拍卖CPU时间片机制的Agent零智能投标算法和NZIPca投标算法。仿真结果表明NZIPca策略具有较强的竞标能力。     

LBAS: An effective pricing mechanism towards video migration in cloud-assisted VoD system

Migrating video instances to cloud to form a cloud-assisted VoD system is an efficient way to solve the problem of increasing costs in the traditional VoD system. In this paper, we focus on further decreasing the costs in this system. We propose a pricing mechanism named LBAS to allocate video instances from VoD provider’s local servers to cloud platforms. First, a pricing algorithm which conforms to the principle of market is presented to determine the price of each video instance. Then, an auction algorithm which is based on low bid and replaceable instances is proposed to determine the allocation and payment of video instances. At last, in order to avoid the collusion among bidders in low-bid auction, the AEM algorithm is improved. The simulation results demonstrate that the proposed mechanism makes the VoD provider decrease 10% of the costs compared with the VMC strategy.