没有合适的资源?快使用搜索试试~ 我知道了~
0认知机器人1(2021)197-2040内容列表可在ScienceDirect上找到0认知机器人0期刊主页:http://www.k eaipublishing.com/en/journals/cogniti ve-robotics/0在多智能体系统中使用GDL谈判进行分散式任务分配0邹辉,席燕0a 阳州海洋电子仪器研究所,中国江苏扬州 b 江苏科技大学计算机系,中国江苏镇江0文章信息0关键词:多智能体系统分配问题谈判游戏描述语言分散式算法0摘要0在大型分布式系统中,任务调度的优化算法可能无法满足领域控制机制的特殊要求,即在有限通信条件下的鲁棒性、最优性、解决方案的及时性和计算处理的便利性。为了满足这些要求,提出了一种基于游戏描述语言(GDL)和博弈论的新型分散式智能体调度方法,用于动态任务分配问题。具体地,我们将任务分配问题定义为随机博弈模型,在该模型中,智能体的效用来自边际效用,然后证明了全局最优任务分配方案存在于非合作博弈的纳什均衡集中。为了生成最优解,我们定义了多智能体谈判博弈(MNG),在其中智能体之间进行谈判,决定下一步要执行哪些任务。在此基础上,我们对GDL进行了简单扩展,使其更适合谈判,并建议使用它来模拟这种谈判场景。最后,我们使用一个谈判示例来表明我们的方法比集中式任务调度程序更适合自主智能体的自动处理,并具有很强的实用性。01. 引言0在大型分布式人工智能系统中,任务调度问题一直非常重要。多智能体系统在这方面也被广泛应用,例如救援任务的分配、紧急调度等。所谓的任务调度问题可以简单概括为使用一致的策略将不同的智能体分配给相应的任务,以优化给定任务和智能体的特定目标[1,2]。由于地理分布和智能体能力的差异,不同的调度方案在任务完成时消耗不同的资源,决策者可以制定最优调度方案,以最小化资源消耗[3,4]。此外,在一些特殊场景中,决策的及时性非常重要。为了解决这些挑战,多智能体系统(MAS)——一个通过由多个个体智能体组成的交互式群体来解决大型复杂问题的框架是一种广泛研究的方法。具体来说,智能体使用分布式知识调整系统变量,实现系统变量的配置,从而实现特定的全局目标,共享计算负担,消除系统的脆弱性或其他风险。在MAS中,智能体通常被认为有两种类型:合作或非合作(即自私)。在本文中,我们使用非合作智能体来设计基于MAS的动态任务分配和调度控制机制,即,智能体基于其对系统的局部知识和少数邻居的行动来行动。他们通过遵循自己的利益来协调他们的行动,以实现最优的全局解决方案。我们相信非合作智能体可以满足大规模分布式系统所需的鲁棒性和灵活性。当用于实现控制机制的配置发生变化或出现基础控制问题时,控制机制仍然是鲁棒和灵活的,因为智能体只需要局部信息0�通讯作者。邮箱地址:just_yxc@qq.com(Y.Xi)。0https://doi.org/10.1016/j.cogr.2021.07.003 收到日期:2020年12月15日; 2021年7月24日收到修订稿; 2021年7月24日接受 在线发布日期:2021年9月8日2667-2413/© 2021 The Authors. Publishing Services by Elsevier B.V. on behalf of KeAi Communications Co. Ltd. 本是根据CCBY-NC-ND许可证(http://creativecommons.org/licenses/by-nc-nd/4.0/)的开放获取文章。H. Zou and Y. Xi Cognitive Robotics 1 (2021) 197–204 𝑆( 𝑤 ) = 𝑡𝑟𝑢𝑒 ( 𝑔𝑟𝑖𝑑(3 , 1 , 𝑂)) , 𝑡𝑟𝑢𝑒 ( 𝑔𝑟𝑖𝑑(2 , 2 , 𝑋)) (1) 198 0以及系统状态或代理行为的所有信息。通过这种方式,重新计算现有控制方案的通信、时间和计算成本可以显著减少,以满足控制机制的需求,即决策的鲁棒性、灵活性和及时性。在这种情况下,本文涉及的具体问题包括一组代理通过协商而不使用集中式管理器分配给一组动态任务。每个任务都有严格的截止日期。例如,在灾难救援环境中,伤亡者必须在上午11:30之前送往医院,需要60分钟。此外,任务集是动态的,新任务将随时间出现,这意味着我们需要一种方法及时处理这种变化。我们假设代理可以参与任何任务,但一次只能执行一个任务,并以固定的处理速率执行任务。因此,单个代理在截止日期之前无法独自执行某些任务,因此一些任务可以由团队一起执行。例如,如果两名消防员一起扑灭燃烧的建筑物,他们可以一起工作以减少所需的时间。由于一开始有一个未知的完整任务集,代理必须继续与其他代理协商要执行的任务顺序,以便在生成当前解决方案时可以考虑所有任务。协商是以代理尽可能在最短时间内完成尽可能多的任务的方式执行的,并且可以包括代理重新提交任务,以便在出现新任务时最大化总任务数。为了满足灵活性、鲁棒性和及时性这三个要求,并生成最佳解决方案,我们提出了一种基于游戏描述语言(GDL)和博弈论的新方法,其中计划是通过代理之间的协商实施的。本文组织如下:在下一节中,我们简要介绍GDL并进行简单扩展以使其更适合协商。在第3节中,我们定义了我们应用的多代理环境模型,然后展示了代理的效用函数是如何导出的,以便代理的行动可以导致纳什均衡。在第4节中,我们定义了多代理协商游戏(MNG),并在此基础上,在第5节中,我们使用一个示例说明了如何应用它来使用GDL+分配任务给代理。在第6节中,我们回顾了其他分散式动态调度的方法和关于GDL的研究,然后总结。02. GDL的简单扩展0在本节中,我们简要介绍了游戏描述语言(GDL)。具体来说,游戏描述语言是一种逻辑语言,旨在描述游戏,并定义和使用以下基本符号:role,init,true,next,legal,goal,terminal,does[5]。在GDL中,我们将一组原子公式表示为S(w),其中w表示游戏的状态。这些原子公式被写成true(p)的形式,其中p可以是游戏中的任何基本术语。例如,在井字棋游戏中,右上方的格子被标记为O,而中心格子被标记为X的状态可以被公式化为:0我们定义的规则GDL具有以下形式:0���1∧�2∧...�n(2)0其中每个s i是一个正项或负项,h是一个正项。原子公式h称为规则的头部,si称为规则的子项,子项的合取是规则的主体。请注意,规则的主体可以是一个空的合取,这种情况下规则被称为事实,我们表示为h�,即0����(�)�(3)0这意味着在初始状态w1中,我们有true(p)∈S(w1)的事实。假设游戏描述采用以下规则:0����(�)�����(�,�)∧����(�)(4)0这意味着对于状态w,其中true(p)为真且玩家�采取行动a,那么游戏将处于状态w',其中true(q)S(w')在下一轮中为真。类似地:0��� min �������(�)(5)0表示true(p)仍然为真的状态是一个终端状态。GDL只能描述没有任何随机性的完全信息游戏[6],这意味着负项p将被推导为真,只要没有任何规则可以导致真tremp。因此,GDL-II对GDL进行了扩展,称为,它允许游戏中存在不完全信息和随机性。我们对GDL进行了简单的扩展,可以表示涉及与时间相关事件的游戏,在这些事件中,行动的精确时刻是相关的。更改总结如上表。未列出的关键字:role,legal,goal,terminal,does,保持不变。与当前持有的事实F相关的参数T R +编码了这个事实的生命周期,即这个事实将保持真实的时间。我们称它为GDL +。0表1-3。在第5节中,我们还说明了GDL可理解为大型多智能体环境的标准语言。我们建议使用游戏描述语言(GDL)来定义谈判领域,并建议使用它来实现谈判The task scheduling problem we require to address is that we have to devise utility functions for agents. To begin, the task utility function is de𝑢 𝑥 𝑖 ( 𝑠 ) =𝑢 𝐺 = 𝑥 𝑖 ∈𝑋 𝑢 𝑥 𝑖 ( 𝑠 ) (7) 199 0H.邹和Y.希认知机器人学1(2021)197-2040表1 GDL关键字0role(R)init(F)R是玩家F在初始状态下为真true(F)legal(R,M)does(R,M)next(F)在当前状态下F为真R可以执行移动M在当前状态中R执行移动M为真在上一个状态中F将在下一个状态为真终端目标(R,N)当前状态为终端R获得报酬N0表2 GDL-II添加的关键字0sees(R,P)随机R可以在下一个状态中感知P随机事件0表3 修改后的GDL关键字0init(F,T)在时间T的初始状态下F为真true(F,T)next(F,T)在当前时间T的状态下F为真F将在下一个时间T的状态下为真0代理。我们研究了GDL在谈判中的应用范围,并比较了其优缺点。我们相信可以用GDL描述谈判领域,但可能需要一些修改使GDL更适合谈判。03. 任务分配模型0在本节中,我们定义了我们应用的多智能体环境模型,然后展示了代理的效用函数是如何推导出来的,以便代理的行动可以导致纳什均衡。我们通过使用随机博弈模型来定义我们的任务调度问题来开始本节。随机博弈是非合作博弈向重复交互过程的扩展,在这个过程中,代理在每个时间步上玩游戏,并且游戏随着前一轮的状态和策略选择的函数以概率方式改变[7]。0引理1. 多智能体环境E是一个元组,其中:0- X是一组任务:� = { � 1 , � 2 , ..., � � , ... } . - t d是截止日期:. � � = { � � � 1 , � � � 2 , ..., � � �� , ... } - u x是任务效用函数:u x i ( s): � → � . - N是一组代理:N = 1 , 2 , ..., j, ..., n . - S j是每个代理的策略空间,其元素s j由一系列任务组成。 - u ( s j ,s − j ): S → R是代理效用函数,其中s − j是s j的补集。 - u G是全局效用函数:u G ( s ): S → R.0我们需要解决的任务调度问题是为代理设计效用函数。首先,任务效用函数被定义为代表完成任务的收益,即:0假设代理的策略s,t c ( s )是完成任务所需的时间,t d ( s )是完成任务的严格截止日期,0 < �1是计算提前完成任务的任何收益的折现因子。任务效用函数在我们的设置中显示了两个重要的特性。首先,在一些灾难设置中,未在截止日期前完成的任务等同于未完成的任务,甚至更糟,这是非常重要的。其次,如果我们增加的代理数量超过了在截止日期前完成任务所需的数量,它可以修改完成任务所需的时间,从而增加任务的收益。考虑到这一点,全局效用函数是所有任务效用的总和,并且它对任务的总分配计划起着主导作用。它保留了任务效用函数的理想特性,并可以表述为:0我们的问题已经为任务效用函数和全局效用函数进行了定义。如果我们直接使用这个随机博弈模型,代理的效用函数将被定义。然而,在上述模型中,代理的策略空间是任务的所有排列的集合H. Zou and Y. Xi Cognitive Robotics 1 (2021) 197–204 𝑢 𝑡,𝜃𝐺 = ∑𝑥 𝑖 ∈𝑋 𝑢 𝑥 𝑖 ( 𝑠 ) (8) 𝑚 𝑢 𝑥 𝑖 ( 𝑠 𝑗 , 𝑠 − 𝑗 ) = 𝑢 𝑥 𝑖 ( 𝑠 𝑗 , 𝑠 − 𝑗 ) − 𝑢 𝑥 𝑖 ( 𝑠 0 , 𝑠 − 𝑗 ) (9) 𝑢 𝑗 ( 𝑠 𝑗 , 𝑠 − 𝑗 ) = ∑𝑥 𝑖 ∈𝑠 𝑗 𝑚 𝑢 𝑥 𝑖 ( 𝑠 𝑗 , 𝑠 − 𝑗 ) (10) 𝑢 𝑥 𝑖 (𝑠 𝑗 , 𝑠 − 𝑗 ) − 𝑢 𝑥 𝑖 (𝑠 ′𝑗 , 𝑠 − 𝑗 )= ∑𝑥 𝑖 ∈𝑠 𝑗 [𝑢 𝑥 𝑖 ( 𝑠 𝑗 , 𝑠 − 𝑗 ) − 𝑢 𝑥 𝑖 ( 𝑠 0 , 𝑠 − 𝑗 ) ]− ∑𝑥 𝑖 ∈𝑠 ′𝑗 [𝑢 𝑥 𝑖 ( 𝑠 ′𝑗 , 𝑠 − 𝑗 ) − 𝑢 𝑥 𝑖 ( 𝑠 0 , 𝑠 − 𝑗 ) ]= ∑𝑥 𝑖 ∈𝑋 [𝑢 𝑥 𝑖 ( 𝑠 ′𝑗 , 𝑠 − 𝑗 ) − 𝑢 𝑥 𝑖 ( 𝑠 0 , 𝑠 − 𝑗 ) ]− 𝑢 𝑥 𝑖 ( 𝑠 ′𝑗 , 𝑠 − 𝑗 ) + 𝑢 𝑥 𝑖 ( 𝑠 0 , 𝑠 − 𝑗 ) = 𝑢 𝑡,𝜃𝐺 ( 𝑠 ′𝑗 , 𝑠 − 𝑗 ) − 𝑢 𝑡,𝜃𝐺 ( 𝑠 ′𝑗 , 𝑠 − 𝑗 ) (11) 𝑢 𝑥 𝑖 ( 𝑠 ∗ 𝑗 , 𝑠 ∗ − 𝑗 ) − 𝑢 𝑥 𝑖 ( 𝑠 𝑗 , 𝑠 ∗ − 𝑗 ) 0 , ∀𝑠 𝑗 , ∀𝑗 (12) 0在每个时间步长分配的任务。代理策略规定了世界上每个偶然状态的每个时间步长的动作。因此,代理的策略是一组动作向量,其中一个被应用于世界的每个状态。考虑到可能的状态数量很大和动作向量的最大大小,评估和协商一组联合策略是一个非常高的计算成本过程,可能需要很长时间。此外,我们的目标是在需要在短时间内做出决策的大型系统中分配我们的代理,几乎不可能为所有可能的结果构建这样的策略,因为未来的可能性很大。出于这些原因,我们从定义的全局效用函数的近似中导出了一个易于使用的效用函数。我们不是直接尝试使用上述随机博弈模型,而是使用一系列具有完整信息的静态博弈来近似它。通过这种方式,我们直接解决了我们的要求,以便处理。具体地,全局效用函数的近似使用了类似于应用于MDP的前瞻策略的方法。我们假设所有状态都是静态的,这意味着世界条件的变化不会对代理的长期收益产生重大影响。全局效用被具体近似如下。构建一个游戏,其中每个代理在每个时间步长的策略在未来�个时间步长内的固定决策窗口上被定义。代理的策略由一系列任务组成,这些任务在时间间隔[ t,t + � ]内采取行动,s i = xt,x t + 1,...,x t +�在这些游戏中的每一个。通过这种方式,我们使用具有完整信息的静态博弈来近似我们上面提到的随机博弈模型,在接下来的�个时间步长内。然后,该模型的全局效用函数由以下给出:0我们注意到它与方程7中的形式相同,除了计算任务效用被限制在一个固定的区间[t,t +�]。考虑到我们模型的全局效用函数的上述定义,代理的回报被设计成这样一种方式,即代理的效用变化对应于u t,�的影响。这使得我们的模型能够通过应用由非合作代理组成的控制方法生成高质量的解决方案。然而,为了满足鲁棒性需求,这些效用不能仅仅等同于全局目标函数,因为那样将意味着每个代理需要完整的系统信息来评估和确定他们的策略。我们尝试通过边际贡献来推导代理的效用函数,因为全局效用是任务效用的总和。代理对全局效用的边际贡献可以通过其对单个任务的贡献之和来定义。这可以描述为代理在贡献任务时获得的任务效用的差异。在Groves机制中,组中的代理被支付与其对组效率的边际贡献相当。这类似于我们的设计,但在我们的设置中,因为系统设计者可以直接指定每个代理的效用函数,我们可以避免机制设计中的显式效用转移,并且可以通过使用边际效用将代理的效力与其行为对全局效用的影响具体地等同起来。代理j对任务x i的边际贡献如下:0其中s 0是空策略,表示代理不选择任何任务参与。我们定义最优解将最小化系统在整个过程中遭受的总损失。这可以表示为整数规划,公式如下:0请注意,对于j没有参与的所有任务,mu x i ( s j , s − j )都为零。考虑到j改变从s j到s'j的效用的差异。然后我们发现,代理的任何策略变化增加效用总是等同于其全局效用的提升,这受限于固定的决策窗口[t,t + �]:0在非合作游戏中,代理的目标是最大化其回报。我们得出结论,在这样的系统中,稳定点的特征之一是它保持在纳什均衡集中,以及一个联合策略s�,没有一个单独的代理是纳什均衡的,它有动机改变为一个不同的策略[8],即:0具有上述效用函数的代理之间的游戏是一个非合作游戏。我们假设最优点不是纳什均衡,那么一些代理必须能够改变他们当前的状态以获得更多的效用,从而修改全局效用,但这与最优观点不是纳什均衡的假设不一致。因此,任务分配给代理的全局最优解总是存在于纳什均衡集中。H. Zou and Y. Xi Cognitive Robotics 1 (2021) 197–204 d 201 04. 多智能体协商游戏0我们使用GDL对代理任务分配场景中的自动化协商进行建模。提出了一种自动化协商框架。通用游戏的主要思想是设计与领域无关的游戏玩家,他们可以参与任何用GDL描述的游戏。我们还希望设计这样的通用框架,允许我们设计与领域和协议无关的代理,以参与各种协商场景,而无需离开和重新编程。基于GGP,使用GDL来描述代理任务分配协商允许我们充分利用许多当前的GGP技术,这可以加速该领域的发展。根据一些GDL和自动化协商的研究,我们最初将代理任务分配自动化协商的框架定义如下:0- Ag = a1,a2,,an是参与协商的代理集。协商主机不包括在Ag中。Ac =(Ac1,Ac2,...,Acn)是一个元组,其中Aci表示协商代理i∈Ag的行动集。W是一个非空状态集。w0∈W是协商的初始状态。0T�W是终端状态w∈W的集合。0- L=(L1,L2,...,Ln)是一个元组,其中每个Li:W\T→2Ai是ai的法定函数。它确定了ai在某个状态下可以采取的行动。所谓的状态更新函数被定义为u:W∆ciW,表示在什么条件下,状态将改变为另一个。Agr是所有可能的协商协议的集合。函数Q:TAgr将每个终端状态映射到一个协议。0这种协商的定义是统一的GGP,它允许我们使用GDL来描述代理任务分配中的自动化协商场景。在下一节中,针对本文提出的任务,我们设计一个协商协议和策略,然后用GDL表示它们。0引理2. 多智能体协商游戏MNG是一个元组,其中E是多智能体环境,Np是协商协议,其中:0- 对于每个代理,我们将A视为它希望在每个时间步骤接受的任务集,即,Aj=Sj。-初始状态w1被定义为任务和代理的未分配状态。- 终端状态T被定义为所有任务都被分配执行。-效用函数被定义为E中的uj。0现在我们准备使用GDL+来描述协商,通过定义多智能体协商游戏的形式。在下一节中,我们将使用上述定义来展示如何进行完整的正式协商。05. 将协商应用于调度问题0我们将使用一个示例来说明如何将其应用于在大型分布式系统中为代理分配任务。在此之前,我们需要将MNG的定义与GDL+语义进行匹配。0引理3. 让元组成为多智能体协商游戏,那么任何有效的GDL子句集都是MNG的公理描述,如果它在逻辑上等价于以下内容,其中:0- 角色(r)�对于每个r∈Ag。- init(p,t)�在时间步骤t中p∈W的初始状态为真。-true(p,t)�对于每个p∈W在时间步骤t中为真。-next(p,t)�对于每个p∈W将在时间步骤t的下一个状态中为真。-legal(p,a)�对于每个a∈L中的p∈W。-goal(r,u)�对于每个r∈Ag获得支付u。- does(a)�对于每个a∈L。-terminal�对于每个T∈W。- sees(r,p)�对于每个r∈Ag在下一个状态中感知p。-random�新任务将被随机生成。0到目前为止,我们已经说明了如何应用一种通用的分散方法来解决动态任务调度问题。我们应用了一种基于协商和GDL的方法来模拟第3节中的模型,并提出了一个简单的示例,以展示如何使用这种方法。0定义1。假设我们有两个代理,Ag1和Ag2,根据MNG协商如何分配任务,对于每个任务xi,td为30分钟。可能的协议是两组任务,可以导致纳什均衡。代理的行动要么是提出分配方案,要么是接受先前的提议,要么是什么都不做。0���� ( �� 1) � (13)0���� ( �� 2) � (14)0���� ( ����, 0) � (15)202 0H. Zou and Y. Xi Cognitive Robotics 1 (2021) 197–2040���� ( ����, 0) � (16)0��� min �� � (17)0���� ( � max �� 1 , � ) ∧ ���� ( � max �� 2 , � ) (18)0∧ ���� ( � max � , � ) ∧ ���� ( � � 30 , � ) (19)0��� min �� � (20)0���� ( �, � ) ∧ ���� ( � � 30 , � ) (21)0� ���� ( �� 1 , � �� 1 ) � (22)0¬ ��� min �� ∧ ¬ ������ ∧ ���� ( � max �� 1 , � ) (23)0∧ ���� ( � � 30 , � ) (24)0� ���� ( �� 1 , � �� 2 ) � (25)0¬ ��� min �� ∧ ¬ ������ ∧ ���� ( � max �� 2 , � ) (26)0∧ ���� ( � � 30 , � ) (27)0���� ( � �� 1 , � ) � (28)0���� ( � �� 1 ) ∧ ���� ( � � 30 , � ) ∧ ���� ( � �� 1 , � ) (29)0���� ( � �� 2 , � ) � (30)0���� ( � �� 1 ) ∧ ���� ( � � 30 , � ) ∧ ���� ( � �� 1 , � ) (31)0� ��� ( �� 1 , � � �� 1 �� ) � (32)0��� min �� ∧ ���� ( �� 1) ∧ ���� ( � �� 1 , � ) (33)0∧ ���� ( � � 30 , � ) (34)0� ��� ( �� 2 , � � �� 2 �� ) � (35)0��� min �� ∧ ���� ( �� 2) ∧ ���� ( � �� 2 , � ) (36)0∧ ���� ( � � 30 , � ) (37)0方程280上述是多智能体谈判游戏的完整、正式描述。我们将其应用于一般的分配问题。GDL本质上是描述谈判场景的一个很好的选择。然而,未来推理存在一些不足,而GDL-II和我们的扩展弥补了这一不足,我们要求评估提议的价值需要提前考虑未来行为和对手的未来行动。203 0H. Zou and Y. Xi Cognitive Robotics 1 (2021) 197–20406.相关工作和结论0回顾了可以应用于调度问题和动态任务分配的一些控制方法。到目前为止,动态任务分配的主要方法包括领域特定的启发式算法,将调度建模为约束程序并用集中式或分散式算法解决,拍卖机制以及基于市场的更一般的方法。相关问题的综合审查可在[9]中获得。鉴于此背景,部分与我们相似的工作是[10],其中提出了一种近似随机博弈的方法。我们认为这项工作受到了另一篇论文中一系列贝叶斯博弈生成粗糙解决方案的方法的启发。通用游戏竞赛是一个相对较新的主题。尽管早期已经进行了一些工作,但自从引入GDL[12,13]并自2005年以来组织了年度AAAIGGP竞赛后,它才真正开始引起人工智能社区的广泛关注。张[6]提出使用GGP来模拟自动化谈判,这显示了为更好的任务分配设计协议无关代理的可能性。基于前人的工作,我们在接下来的章节中提出了我们的模型和方法。尽管GDL最初是为GGP而设计的,但它以类似的方式被应用于其他领域的知识表示,比如自动化谈判[6]。在本文中,我们展示了游戏描述语言在谈判和多智能体环境中作为一种声明性语言的理解。在我们的扩展中,我们考虑了时间因素,以便更好地探索游戏树。然而,这可能会导致一些有前途的路径由于游戏事件或其他玩家的随机行为而不再可用。这种情况需要开发新的通用解决方案[5]。我们提出了一种分散式调度的分散式博弈机制,以解决动态任务调度问题,其中代理需要相互协商,确定在下一个时间步骤执行哪些任务,使用GDL。具体来说,每个代理都必须处理一系列随时间变化的任务,通常任务可能需要在截止日期之前由一个以上的代理完成,而任务集是动态的,这意味着随时间出现新的任务[10]。在上述模型环境中,集中式最优算法可能无法满足领域的控制机制的额外要求,即解决方案的最优性和鲁棒性以及解决方案的及时性和计算处理的便利性,因为其通信使用受限。为了满足这些要求,我们提出了一种基于游戏描述语言(GDL)和博弈论的新方法,通过代理之间的谈判来实现计划。重要的是,我们将任务分配问题定义为一个随机博弈模型,其中代理的效用是以这样一种方法导出的,即全局最优解位于纳什均衡集合中。为了生成最优解,需要相互协商,确定在下一个时间步骤执行哪些任务[15],特别是我们建议使用GDL作为谈判方法[16],因为已经表明它实质上是描述一般谈判场景的一个很好的选择。本文的潜在扩展包括将我们的模型推广到处理复杂任务场景的其他要求,例如允许代理放弃任务,或考虑代理执行任务的偏好和能力,并为每个代理发送不同的截止日期,所有这些都必须在制定策略时考虑他们的决策。使用谈判方法进行通信的范围非常广泛。如何在有限的通信条件下实现有效的谈判方案也是未来需要研究的一个方面。此外,我们认为可以合并具有不同资源的异构任务和代理[17]。这样一个示例应用是在RoboCup Rescue Simulation联赛中整合所有三种代理类型的模拟控制机制,包括救护车、消防队和警察。0竞争利益声明0作者声明,他没有已知的竞争性财务利益或个人关系,可能会影响本文报告的工作。0参考文献0[1] A. Filippoupolitis , E. Gelenbe,建筑疏散的分布式决策支持系统,人类系统互动,2009. HSI’09. 第2届会议,Ieee,2009,页323–330 .0[2] H. Kitano , S. Tadokoro , I. Noda , H. Matsubara , T. Takahashi , A. Shinjou , S. Shimada , Robocup rescue: 大规模灾难中的搜救作为自主代理研究领域,系统、人、与控制论,1999. IEEESMC’99 会议论文集。1999 IEEE国际会议,6,IEEE,1999,页739–743 .0[3] R. Stranders , A. Farinelli , A. Rogers , N.R. Jennings,使用最大和算法进行移动传感器的分散协调,IJCAI,9,2009,页299–304 . [4] P. Chand , D.A.Carnegie,多机器人的减少人类用户输入任务分配方法的开发,机器人和自主系统60(10) (2012) 1231–1244 .0[5] M. Genesereth , M. Thielscher , 通用游戏玩法,人工智能和机器学习综合讲座8(2) (2014) 1–229 . [6] D. De Jonge , D.Zhang,使用gdl来代表自动化谈判的领域知识,国际自主体和多自主体系统会议,Springer,2016,页134–153 .0[7] M.L. Littman , 马尔可夫博弈作为多智能体强化学习框架,机器学习会议论文集1994,Elsevier,1994,页157–163 . [8] D. Monderer , L.S. Shapley , 潜在博弈,博弈与经济行为14(1)(1996) 124–143 . [9] A.C. Chapman , 使用纯策略纳什均衡的游戏控制大型分布式系统,南安普顿大学,2009 .0[10] A.C. Chapman , R.A. Micillo , R. Kota , N.R. Jennings,使用重叠潜在博弈的分散动态任务分配,计算机杂志53(9) (2010) 1462–1477 .0[11] G. Arslan , J.R. Marden , J.S. Shamma , 自主车辆-目标分配:博弈论建模,动态系统、测量和控制杂志129 (5) (2007) 584–596 .0[12] M. Genesereth , N. Love , B. Pell,通用游戏玩法:AAAI竞赛概述,人工智能杂志26(2) (2005) 62 . [13] D.E. Knuth , R.W.Moore,Alpha-beta剪枝分析,人工智能6(4) (1975) 293–326 .204 0H. Zou 和 Y. Xi 认知机器人学 1 (2021) 197–2040[14] S. Schi�el , M. Thielscher,游戏描述语言的多智能体语义,国际代理和人工智能会议,Springer,2009,页44–55 .0[15] D. De Jonge , C. Sierra , Gangster: 应用遗传算法的自动化谈判者,近期智能体复杂自动化谈判进展,Springer,2016,页225–234 .0[16] K.E. Booth , G. Nejat , J.C. Beck,退休院中多机器人任务分配和调度的约束编程方法,约束编程原理与实践国际会议,Springer,2016,页539–555 .0[17] 刘洋,杨健,郑勇,吴忠,姚敏,任务和通信约束下复杂环境中的多机器人协调,国际先进机器人系统杂志10(5) (2013) 229 .
下载后可阅读完整内容,剩余1页未读,立即下载
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)