基于并行约束规划的最大团识别研究

为提高大数据平台下大规模图例的最大团问题求解效率,提出一种基于并行约束规划的最大团识别算法.通过BMT图划分策略将一个复杂图例分割为若干个可独立计算的子图,并将其分配给Spark集群中的计算节点,每个计算节点采用约束规划方法对分割产生的子问题分别进行建模和求解,实现最大团问题的并行化处理.引入时间预测模型,设计基于任务运行时间预测模型的并行图划分方法,从而有效解决计算节点的负载均衡问题.实验结果表明,与基于BMC图划分策略的最大团并行识别算法相比,该算法具有更高的求解效率,可取得近似线性的加速比.     

基于布谷鸟搜索的多处理器任务调度算法

多处理器系统在高性能计算中扮演着重要角色.为提高系统的并行性能,基于布谷鸟搜索算法,提出一种新的多处理器任务调度算法.该算法以全部任务的最晚完成时间最小为目标,利用基于任务优先权的编码方式使连续的布谷鸟搜索算法适用于离散的多处理器任务调度问题.实验结果表明,所提算法不仅求解质量高,而且求解速度最快,与目前广泛采用的遗传算法和粒子群算法相比其执行时间缩短超过60％.     

多核处理平台上任务图模型的并行调度策略研究

凭借着高性能,低功耗的特性,多核处理器已经占据了目前的主要市场.提出一种多核处理平台上基于任务图模型的调度策略.建立了多核平台上任务图的空间与时间并行调度模型;针对任务图的空间并行与时间并行调度模型提出了并行节点合并、分配的优化算法与流水线并行的优化算法.最后,提出将优化的空间与时间并行调度技术相结合的并行调度策略.通过实验验证,本文提出的算法比其他多核并行调度算法降低了处理器核心间的通信与同步开销,提高了系统的计算效率与吞吐量.     

串并行软件系统测试资源动态分配建模及求解

系统测试是软件开发各个阶段中最消耗时间和资源的阶段,对于串并行软件系统来说,系统可靠性随着测试时间的推进会发生变化,如果再按照最初的方案分配测试资源,可能会造成测试资源的浪费,这时需要分阶段对测试资源进行再分配.在基于搜索理论的软件工程领域展开研究,首先,在分析测试资源、测试代价和系统可靠性关系的基础上构建了以测试资源为约束,以最大化可靠性和最小化测试成本为目标的测试资源多目标动态分配模型,按照测试进程的推进,动态地分配测试资源;然后,基于具有改进种群初始化策略的“一维整数向量编码”差异演化算法,提出了一种针对串并行软件系统的测试资源动态分配算法.对比实验结果表明,测试资源动态分配模型在保证系统可靠性的前提下,有效地节省了系统测试的消耗,提高了串并行软件系统的开发效率.     

基于资源拍卖的农业多机器人任务分配

针对农田环境中多机器人协同作业的问题,提出一种基于资源的任务分配算法,用于在具有机器人资源的再填充站的长期任务中高效地执行多个任务.针对多机器人任务分配问题,对多机器人任务进行建模,并分析任务相关模型及任务能量指标.在进行拍卖算法任务分配时,在考虑机器人数目约束、工作时间约束、距离约束的基础上,加入任务执行能力的约束,考虑机器人在长期任务执行期间资源量消耗问题,使各个农机有序地为农田地块服务,降低整个系统的执行代价,提高任务完成量.利用MATLAB平台进行仿真实验,生成多机器人多任务点的分配优化结果,并设置多组不同数量的机器人,对比该算法同其他三种算法的效果.仿真结果表明,该算法可以有效地提高作业效率,在相同条件下使资源消耗量及任务完成量达到最优,证明了其优越性,同时计算结果与实际作业完成量更接近,提高了结果的精准性.     

工作流系统中一个基于双权角色的条件化RBAC访问控制模型

传统的RBAC访问控制模型已经不能表达复杂的工作流安全访问控制约束。基于传统的RBAC模型,提出了一个新的基于双权角色的条件化RBAC访问控制模型CRDWR(conditioned RBAC based on double—weighted roles)。阐述了基于动态角色分配的条件化RBAC策略,定义了基于双权角色的工作流系统访问授权新概念,并针对多个角色协同执行任务的序约束问题,给出了基于令牌的序约束算法。该模型能够表达复杂的工作流安全访问控制约束。     

多核平台下XEN虚拟机动态调度算法研究

虚拟机调度算法对并行任务的执行效率考虑不够充分。现代处理器平台具备了多个可用的计算核心,使多个虚拟机并发执行成为了现实。针对多核平台下的并行虚拟机调度优化问题,提出一种基于任务特征虚拟机CON-Credit调度算法。该算法在调度并行任务时,使用动态方式对计算机核心进行分配,采用传统的虚拟机调度算法为执行普通任务的虚拟机进行分配;采用定制的同步算法给执行并行任务的虚拟机分进分配。相关实验显示,CON-Credit调度算法能显著提高并行任务的执行效率。     

基于反馈机制的动态负载平衡算法研究*

动态负载平衡是提高多处理器系统资源利用率和并行计算性能的重要途径。为了解决变化负载系统中子任务可并行计算的双重循环(PTM-NL)问题,提出一种基于反馈机制的动态负载平衡算法。该算法以处理器作业速度为负载指标,在循环计算中根据反馈的负载指标分配计算任务,动态适应负载变化。实验结果表明,该算法在变化负载的系统中能有效提高PTM-NL问题并行效率。     

云环境下基于强化学习的多目标任务调度算法

针对云计算环境下的多目标任务调度问题,提出一种新的基于Q学习的多目标优化任务调度算法(Multi-objective Task Scheduling Algorithm based on Q-learning,QM TS).该算法的主要思想是:首先,在任务排序阶段利用Q-learning算法中的自学习过程得到更加合理的任务序列;然后,在虚拟机分配阶段使用线性加权法综合考虑任务最早完成时间和计算节点的计算成本,达到同时优化多目标问题的目的;最后,以产生更小的makespan和总成本为目标函数对任务进行调度,得到任务完成后的实验结果.实验结果表明,QMTS算法在使用Q-learning对任务进行排序后可以得到比HEFT算法更小的makespan;并且根据优化多目标调度策略在任务执行过程中减少了makespan和总成本,是一种有效的多目标优化任务调度算法.     

考虑时序约束的多智能体协同任务分配

研究多智能体系统的多目标多任务分配问题, 考虑任务之间的时序关系, 建立分布式任务分配模型. 扩展了一致性包算法(CBBA), 按优先级将目标任务归入不同层级, 各智能体在构建任务包和任务路径时, 只将分配过高阶段任务的目标添加至相应的任务包和任务路径中, 从而保证目标任务时序约束的同时, 保持了CBBA算法的特性. 与多任务分配问题经典算法的比对实验表明, 所提出的改进算法求解结果稳定可靠, 运行时间优于经典算法.

     

邻域交互结构优化的多智能体快速蜂拥控制算法

针对多智能体系统在动态演化过程中容易出现的"局部聚集"现象,融 合复杂网络中的拓扑结构优化理论与多智能体系统协调蜂拥控制研究,提出了一种基 于邻域交互结构优化的多智能体快速蜂拥控制算法.该算法首先从宏观上分析多智 能体的局部聚集现象,利用社团划分算法将局部相对密集的多个智能体聚类成一个 社团,整个多智能体系统可以划分成多个相对稀疏的社团,并为每个社团选择度 最大的个体作为信息智能体,该个体可以获知虚拟领导者信息;随后从多智能体 系统中不同社团相邻个体间的局部交互结构入手,取消社团间相邻个体的交 互作用,设计仅依赖于社团内部邻居个体交互作用的蜂拥控制律;理论分 析表明,只要每个社团存在一个信息智能体,在虚拟领导者的引导作用下,整个多 智能体系统就可以实现收敛的蜂拥控制行为;仿真实验也证实了对多智 能体系统进行邻域交互结构优化可以有效提高整个系统的收敛速度.     

Bipartite Byzantine-resilient event-triggered consensus control of heterogeneous multi-agent systems

This article studies the bipartite resilient event-triggered consensus control for a class of the heterogeneous multi-agent systems. Due to the external cyberattacks, some agents may become the Byzantine agents and will affect the behavior of the other agents. To improve the security of the multi-agent systems against the Byzantine agents, a novel bipartite event-triggered heterogeneous mean-subsequence-reduced algorithm is designed. First, to handle the heterogeneous multi-agent systems, a state transformation is carefully designed, to facilitate the design and analysis of the bipartite resilient consensus algorithm. Based upon the designed state transformation, the bipartite resilient control inputs are constructed, where the structural balance analysis shows that the resulting effective signed graph and the equivalent signed graph are both structurally balanced, if the signed graph of the multi-agent systems is structurally balanced. In addition, a dynamic event-triggered mechanism is proposed, where a set of dynamic factors are introduced into the event-triggered functions to prevent the usage of the global topology information. By virtue of the designed algorithm, it is guaranteed that the heterogeneous multi-agent systems can achieve the bipartite consensus in the presence of the Byzantine agents, and the communication burden among the agents can be reduced. The numerical simulations are conducted to verify the effectiveness of the proposed algorithm.     

Participant Selection for Short-term Collaboration in Open Multi-agent systems

In multi-agent systems, agents coordinate their behaviour and work together to achieve a shared goal through collaboration. However, in open multi-agent systems, selecting qualified participants to form effective collaboration communities is challenging. In such systems, agents do not have access to complete domain knowledge, they leave and join the systems unpredictably. More importantly, agents are mostly self-interested and have multiple goals and policies that may be even conflicting with others, which makes the participant selection even more challenging.Many of the current approaches are not applicable in constantly evolving open systems, where their performance will be affected by any unpredictable behaviour, agents’ lack of complete domain knowledge and the impossibility of having a central coordinator agent. In open systems, agents require a mechanism that enables them to dynamically change their perception of the environment and observe their neighbouring agents, so that they can identify qualified collaboration participants that have no conflicting goals and to balance their level of cooperation and self-interest.In this paper, we propose OPSCO, as a solution for On-demand Participant Selection for Short-term Collaboration in Open multi-agent systems. Unlike the existing research, we do not assume any predefined setting for agents’ structure in the system and do not have access to complete domain knowledge and allow each agent to build a dynamic dependency model and maintain when there is a change in the system. The model captures the agent’s most recent dependency structure of goals and policies with its neighbouring agents. It enables them to identify and select a qualified non-conflicting set of participants.OPSCO is evaluated in a real world open system smart grid and constrained resource sharing case studies. OPSCO outperforms other methods by selecting a qualified non-conflicting set of agents to collaborate. OPSCO balances the self-interest and level of cooperation and decreases failure in the overall agents’ goals (individual/shared).     

复杂约束条件下异构多智能体联盟任务分配

分布式任务决策是提高多智能体系统自主性的关键. 以异构多智能体协同执行复杂任务为背景, 首先建立 了一种考虑任务载荷资源约束、任务耦合关系约束及执行窗口约束等条件的异构多智能体分布式联盟任务分配模 型; 其次, 对一致性包算法(CBBA)进行了扩展, 提出了基于改进冲突消解原则的一致性联盟算法(CBCA), 以实现异 构多智能体协同无冲突任务分配, 并进一步证明了在一定条件下CBCA算法收敛于改进顺序贪婪算法(ISGA). 最后 通过数值仿真, 验证了CBCA算法求解复杂约束条件下异构多智能体联盟任务分配问题的可行性和快速性.     

A Resource Logic for Multi-Agent Plan Merging

In a multi-agent system, agents are carrying out certain tasks by executing plans. Consequently, the problem of finding a plan, given a certain goal, has been given a lot of attention in the literature. Instead of concentrating on this problem, the focus of this paper is on cooperation between agents which already have constructed plans for their goals. By cooperating, agents might reduce the number of actions they have to perform in order to fulfill their goals. The key idea is that in carrying out a plan an agent possibly produces side products that can be used as resources by other agents. As a result, an other agent can discard some of its planned actions. This process of exchanging products, called plan merging, results in distributed plans in which agents become dependent on each other, but are able to attain their goals more efficiently. In order to model this kind of cooperation, a new formalism is developed in which side products are modeled explicitly. The formalism is a resource logic based on the notions of resource, skill, goal, and service. Starting with some resources, an agent can perform a number of skills in order to produce other resources which suffice to achieve some given goals. Here, a skill is an elementary production process taking as inputs resources satisfying certain constraints. A service is a serial or parallel composition of skills acting as a program. An operational semantics is developed for these services as programs. Using this formalism, an algorithm for plan merging is developed, which is anytime and runs in polynomial time. Furthermore, a variant of this algorithm is proposed that handles the exchange of resources in a more flexible way. The ideas in the paper will be illustrated by an example from public transportation.     

无人驾驶坦克自主作战决策系统框架

提出了一个分布式解决无人驾驶坦克自主作战决策的框架，将自主作战、动态任务规划和任务策略的智能评估等思想引入无人驾驶坦克自主作战决策系统。包括以下两个重要内容：主体个体的能力和职责；信息和知识如何在主体之间传播使得他们能准确地完成作战任务。文中重点是无人驾驶坦克自主作战决策系统中主体之间动态知识的交换。主体确保自己的行为是一种动态的经验操作和直接与其他主体交流事实、需求和规则的结合。在各个主体中，知识可以作为事实、规则、需求的结合体来传播交换。     

Adaptive decision-making frameworks for dynamic multi-agent organizational change

This article presents a capability called Adaptive Decision-Making Frameworks (ADMF) and shows that it can result in significantly improved system performance across run-time situation changes in a multi-agent system. Specifically, ADMF can result in improved and more robust performance compared to the use of a single static decision-making framework (DMF). The ADMF capability allows agents to dynamically adapt the DMF in which they participate to fit their run-time situation as it changes. A DMF identifies a set of agents and specifies the distribution of decision-making control and the authority to assign subtasks among these agents as they determine how a goal or set of goals should be achieved. The ADMF capability is a form of organizational adaptation and differs from previous approaches to organizational adaptation and dynamic coordination in that it is the first to allow dynamic and explicit manipulation of these DMF characteristics at run-time as variables controlling agent behavior. The approach proposed for selecting DMFs at run-time parameterizes all domain-specific knowledge as characteristics of the agents’ situation, so the approach is application-independent. The presented evaluation empirically shows that, for at least one multi-agent system, there is no one best DMF for multiple agents across run-time situational changes. Next, it motivates the further exploration of ADMF by showing that adapting DMFs to run-time variations in situation can result in improved overall system performance compared to static or random DMFs.     

Multi-agent exploration of spatial dynamical processes under sparsity constraints

This paper addresses the development of an efficient information gathering and exploration strategy for robotic missions when a high level of autonomy is expected. A multi-agent system is considered, which consists of several mobile sensing platforms with the goal to identify the parameters of a spatio-temporal process modeled by a partial differential equation. Specifically, an exploration of a diffusion process driven by an unknown number of sparsely located sources is considered. A probabilistic approach toward partial differential equations and sparsity constraints modeling with factor graphs is developed and realized by a customized message passing algorithm. The algorithm permits efficient identification of source parameters: the number of sources, their locations and amplitudes. In addition, an exploration strategy to guide the agents to more informative sampling locations is proposed; this accelerates identification of the source parameters. The message passing implementation facilitates efficient distributed implementation, which is of significant advantage with respect to scalability, computational complexity and an implementation in a multi-agent system. The effectiveness of the algorithm is demonstrated using synthetic data in simulations.     

面向全球数值天气预报模式的加权等积并行数据划分算法

极区计算对全球数值预报模式设计的重要性主要体现在2个方面:模式动力框架中的极区处理和极区并行数据划分带来的并行负载不平衡问题.其中后者是全球数值预报模式大规模并行计算的性能瓶颈,对此提出一种新的基于加权等积的球面数据划分算法.该算法以球带数目和权函数为参数,将南北两极分别划分到单独的子区域,形成极点通区,使从极点到赤道方向每个纬度对应的子区域数目逐渐增多,灵活地实现球面网格的高质量划分.从理论上分析该算法的划分质量后,以基于球谐谱的浅水波模式PSTSWM为实验平台,验证了提出的划分算法具有很好的并行划分性能以及可扩展性.结合我国自主设计的GRAPES全球模式,展望了该算法的应用前景.     

基于动态描述逻辑的多主体协作模型

基于动态描述逻辑的主体模型和协作过程就是既考虑了智能主体的知识表示与推理问题,又紧密地结合主体的设计与编程问题,把表示与推理应用到主体的具体设计中．它充分利用了动态描述逻辑的统一的形式化框架,同时从静态的知识表示与推理和动态的运行与变化两个方面来刻画主体的心智状态和协作过程,探讨了主体信念、行为能力、目标和规划等心智要素的表示、推理与修改以及联合目标的形成、多目标的规划问题．多主体协作模型将理论和实践有机地结合起来,能够充分体现智能主体的本质特征与运行机制,为多主体系统的设计与编程奠定了很好的基础．