论文部分内容阅读
复杂任务往往需要异构多智能体合作才能完成,而联盟是实现合作的重要方法之一。同时,在分布式系统中,通信是多智能体合作执行任务的前提。因此,在同时承担通信和任务执行的条件下,智能体如何合理有效地组建联盟是提高多智能体系统应对复杂任务的关键之一。然而,适合于通信的联盟结构(Coalition Structure,CS)不一定适合于合作完成任务,适合于合作完成任务的联盟结构也不一定能满足通信的要求;因此,需要基于这两者进行权衡协调,设计能同时满足二者的联盟优化组建框架。考虑到任务的动态性、多智能体的异构性以及智能体对彼此决策的不确定性,多智能体合作问题的解决面临巨大挑战。本文以合作博弈理论、贝叶斯理论和复杂网络理论为基础,通过分析通信和执行任务之间的约束关系,将复杂任务分配问题形式化为分布式异构多智能体系统动态联盟问题,研究了多智能体系统动态联盟优化方法,为该问题解决提供技术支撑。论文的主要研究成果如下:
1、考虑智能体同时承担任务执行和通信的系统特点,基于合作博弈理论,提出面向多重职责的分布式多智能体系统动态联盟组建框架(Multi-responsibility Oriented Coalition Formation Framework,MOCFF),支持智能体完成各职责相关的联盟优化组建。首先,分析通信和任务执行这两种职责的关系,将该问题分解成动态任务联盟组建和通信联盟重构;其次,通过定义基于动态任务联盟的通信联盟效能函数,有机整合了动态任务联盟组建和通信联盟重构,并提出面向多重职责的分布式多智能体系统动态联盟组建框架。
2、针对动态任务联盟组建问题,考虑智能体系统的异构性和任务的动态性,提出了基于双向选择市场机制的动态任务联盟组建方法(A Mutual-Selecting Market-based Algorithm,MSMA)。首先,考虑系统分布式的特点,采用社交网络(Social Networks)支持系统通信,并设计智能体之间的协商规则;其次,考虑任务的动态性和智能体的异构性,设计了联盟特征函数,并用智能体单体效能之和对系统全局效能进行逼近以适应分布式计算;再者,基于上述协商规则和联盟特征函数,提出基于双向选择市场机制的动态任务联盟组建方法。经过仿真实验对比,该算法的任务响应率较其它分布式动态联盟组建算法高30%。
3、针对通信联盟重构问题,考虑智能体通信的局部性,提出受限贝叶斯重叠联盟博弈模型(Constrained Bayesian Overlapping Coalition Game,CBOCG),对分布式多智能体系统中通信联盟自适应重构问题进行建模,并在此基础上提出分布式通信联盟自适应重构方法。首先,考虑智能体获取信息的局部性及各智能体对于彼此通信联盟决策的不确定性,提出受限贝叶斯重叠联盟博弈,对该通信联盟重构问题进行建模;其次,考虑地理位置对智能体各职责的约束,设计了一组自适应重构规则,将重构策略映射成地理位置选择;第三,基于上述模型和设计,提出了位置剪枝自适应算法(Location Pruning Self-Adaptive Algorithm,LPSA),以对通信联盟重构问题进行求解。经过仿真实验对比,该算法有效提高了系统通讯效率也进而提高了任务响应率。
4、针对通信联盟重构问题中节点状态判断和重构策略生成等问题,提出基于任务执行能力和通信能力的复杂网络节点关键性判断参数,即本地中心性(Local Centrality,LC),为系统通信联盟自适应重构提供可靠的节点评估,并优化自适应重构策略。基于复杂网络理论,分析系统复杂网络的特点,提出基于局部信息的网络节点关键性评估参数——本地中心性,以支持智能体对自己所处网络的各节点进行关键性判断,并生成合理优化的通信联盟重构策略。其次,基于本地中心性,提出分布式动态社交网络重构算法(Distributed Re-constructed Algorithm,DRA)。经仿真实验对比验证,该中心性参数能有效帮助提升系统任务响应率。
1、考虑智能体同时承担任务执行和通信的系统特点,基于合作博弈理论,提出面向多重职责的分布式多智能体系统动态联盟组建框架(Multi-responsibility Oriented Coalition Formation Framework,MOCFF),支持智能体完成各职责相关的联盟优化组建。首先,分析通信和任务执行这两种职责的关系,将该问题分解成动态任务联盟组建和通信联盟重构;其次,通过定义基于动态任务联盟的通信联盟效能函数,有机整合了动态任务联盟组建和通信联盟重构,并提出面向多重职责的分布式多智能体系统动态联盟组建框架。
2、针对动态任务联盟组建问题,考虑智能体系统的异构性和任务的动态性,提出了基于双向选择市场机制的动态任务联盟组建方法(A Mutual-Selecting Market-based Algorithm,MSMA)。首先,考虑系统分布式的特点,采用社交网络(Social Networks)支持系统通信,并设计智能体之间的协商规则;其次,考虑任务的动态性和智能体的异构性,设计了联盟特征函数,并用智能体单体效能之和对系统全局效能进行逼近以适应分布式计算;再者,基于上述协商规则和联盟特征函数,提出基于双向选择市场机制的动态任务联盟组建方法。经过仿真实验对比,该算法的任务响应率较其它分布式动态联盟组建算法高30%。
3、针对通信联盟重构问题,考虑智能体通信的局部性,提出受限贝叶斯重叠联盟博弈模型(Constrained Bayesian Overlapping Coalition Game,CBOCG),对分布式多智能体系统中通信联盟自适应重构问题进行建模,并在此基础上提出分布式通信联盟自适应重构方法。首先,考虑智能体获取信息的局部性及各智能体对于彼此通信联盟决策的不确定性,提出受限贝叶斯重叠联盟博弈,对该通信联盟重构问题进行建模;其次,考虑地理位置对智能体各职责的约束,设计了一组自适应重构规则,将重构策略映射成地理位置选择;第三,基于上述模型和设计,提出了位置剪枝自适应算法(Location Pruning Self-Adaptive Algorithm,LPSA),以对通信联盟重构问题进行求解。经过仿真实验对比,该算法有效提高了系统通讯效率也进而提高了任务响应率。
4、针对通信联盟重构问题中节点状态判断和重构策略生成等问题,提出基于任务执行能力和通信能力的复杂网络节点关键性判断参数,即本地中心性(Local Centrality,LC),为系统通信联盟自适应重构提供可靠的节点评估,并优化自适应重构策略。基于复杂网络理论,分析系统复杂网络的特点,提出基于局部信息的网络节点关键性评估参数——本地中心性,以支持智能体对自己所处网络的各节点进行关键性判断,并生成合理优化的通信联盟重构策略。其次,基于本地中心性,提出分布式动态社交网络重构算法(Distributed Re-constructed Algorithm,DRA)。经仿真实验对比验证,该中心性参数能有效帮助提升系统任务响应率。