Multi-Agent Constraint Systems with Preferences: Efficiency, Solution Quality, and Privacy Loss

In this paper, we consider multi-agent constraint systems with preferences, modeled as soft constraint systems in which variables and constraints are distributed among multiple autonomous agents. We assume that each agent can set some preferences over its local data, and we consider two different criteria for finding optimal global solutions: fuzzy and Pareto optimality. We propose a general graph-based framework to describe the problem to be solved in its generic form. As a case study, we consider a distributed meeting scheduling problem where each agent has a pre-existing schedule and the agents must decide on a common meeting that satisfies a given optimality condition. For this scenario we consider the topics of solution quality, search efficiency, and privacy loss, where the latter pertains to information about an agent's pre-existing meetings and available time-slots. We also develop and test strategies that trade efficiency for solution quality and strategies that minimize information exchange, including some that do not require inter-agent comparisons of utilities. Our experimental results demonstrate some of the relations among solution quality, efficiency, and privacy loss, and provide useful hints on how to reach a tradeoff among these three factors. In this work, we show how soft constraint formalisms can be used to incorporate preferences into multi-agent problem solving along with other facets of the problem, such as time and distance constraints. This work also shows that the notion of privacy loss can be made concrete so that it can be treated as a distinct, manipulable factor in the context of distributed decision making.     

基于多Agent协商的服务流程定制

针对复杂业务需求,提出了基于多Agent协商的服务流程定制模型、算法和系统．首先介绍了该模型及其支持系统的框架以及服务Agent的结构和工作原理;然后在将业务需求满足定义为分布式柔性约束满足问题的基础上,提出了基于多Agent协商的求解算法并介绍了一个应用案例;最后,给出了一个原型系统．该模型和系统能够对复杂的业务需求进行建模和求解,从而寻找到合适的服务,满足了服务流程定制的需要．     

Multi-objective robust optimization using a sensitivity region concept

In multi-objective design optimization, it is quite desirable to obtain solutions that are multi-objectively optimum and insensitive to uncontrollable (noisy) parameter variations. We call such solutions robust Pareto solutions. In this paper we present a method to measure the multi-objective sensitivity of a design alternative, and an approach to use such a measure to obtain multi-objectively robust Pareto optimum solutions. Our sensitivity measure does not require a presumed probability distribution of uncontrollable parameters and does not utilize gradient information; therefore, it is applicable to multi-objective optimization problems that have non-differentiable and/or discontinuous objective functions, and also to problems with large parameter variations. As a demonstration, we apply our robust optimization method to an engineering example, the design of a vibrating platform. We show that the solutions obtained for this example are indeed robust.     

分布式约束优化方法研究进展

多agent系统作为分布式人工智能研究领域的重要分支,已被广泛应用于多个领域中复杂系统的建模.而分布式约束优化作为一种多agent系统求解的关键技术,已成为约束推理研究的热点.首先对其适用性进行分析,并基于对已有算法的研究,总结出采用该方法解决问题的基本流程,在此基础上,从解的质量保证、求解策略等角度对算法进行了完整的分类;其次,根据算法分类结果以及执行机制,对大量经典以及近年来的分布式约束优化算法进行了深入分析,并从通信、求解质量、求解效率等方面对典型算法进行了实验对比;最后,结合分布式约束优化技术的求解优势给出了分布式约束优化问题的实际应用特征,总结了目前存在的一些问题,并对下一步工作进行了展望.     

一种基于分布式约束满足的资源优化模型*

分布式约束满足作为分布式人工智能领域的一个重要分支,在许多领域均得到了广泛应用。针对Web服务事务协调过程中的资源优化问题,在分布式逃逸算法的基础上提出了一种基于分布式约束满足的资源优化模型,并通过仿真实验证实了模型及其算法的收敛性和优化性。     

低约束密度分布式约束优化问题的求解算法

多Agent协作过程中的许多挑战都可以建模为分布式约束优化问题.针对低约束密度的分布式约束优化问题,提出了一种基于贪婪和回跳思想的求解算法.在该算法中,各Agent基于贪婪原则进行决策,能够利用低约束密度问题中大量赋值组合代价为0这一特点来加快求解速度.同时,Agent间的回跳机制可以在贪婪原则陷入局部最优时保证算法的完全性.相对于已有主流算法,该算法可以在保持多项式级别的消息长度/空间复杂度的前提下,以较少的消息数目求解低约束密度的分布式约束优化问题.给出了算法关键机制的正确性证明,并通过实验验证了算法的上述性能优势.     

Feasible Formation of Coalitions Among Autonomous Agents in Nonsuperadditive Environments

Cooperating and sharing resources by creating coalitions of agents are important ways for autonomous agents to execute tasks and to maximize payoff. Such coalitions will form only if each member of a coalition gains more by joining the coalition than it could gain otherwise. There are several ways of creating such coalitions and dividing the joint payoff among the members. In this paper we present algorithms for coalition formation and payoff distribution in nonsuperadditive environments. We focus on a low-complexity kernel-oriented coalition formation algorithm. The properties of this algorithm were examined via simulations. These have shown that the model increases the benefits of the agents within a reasonable time period, and more coalition formations provide more benefits to the agents.
     

多目标优化设计在杀螺剂配方研究中的应用

针对某生物杀螺剂制作中多目标约束问题,提出了一种应用Pareto遗传算法来解决问题的优化方法。建立了用于多目标优化的适应度函数,使用排列选择方法将带约束的多目标问题转换为无约束优化问题;并根据计算中的收敛情况引入了适当的移民算子,改善了遗传算法的进化性能,得到了Pareto最优解集,成功地解决了该生物杀螺剂的最优配方问题。     

一种基于正关系的多Agent协调算法

多Agent之间的协调(coordination)与协作(cooperation)已经成为多Agent系统(multiagent system,MAS)中的一个关键问题。这是因为MAS的主要研究目标之一就是使得多Agent的信念、意图、期望、行为达到协调甚至协作。在开放、动态的MAS环境下,具有不同目标的多个Agent必须对其资源的使用以及目标的实现进行协调[1,4]。例如,在出现资源冲突时,若没有很好的协调机制,就有可能出现死锁。而在另一种情况下,当单个Agent无法独立完成目标,需要其它Agent帮助时,则需要协作。本文提出了一种基于正关系的多Agent协调机制和协调算法。在该算法中,通过使用这种协调机制,Agent能委托或接受交互中的子计划,从而形成系统负载均衡和有效降低系统运行开销。     

具有复杂动力学的多智能体系统分布式优化综述

多智能体系统分布式优化由于其高效性、灵活性和可靠性等特点吸引了大量学者的关注,在多机器人协同控制、无线传感器网络、能源系统等领域具有广泛的应用前景.分布式优化的基本目标是利用智能体的个体目标函数梯度、自身及其邻居状态信息设计分布式控制协议,驱动所有智能体的状态或输出到全局目标函数的最优解,系统动力学是影响智能体状态演化的重要因素.鉴于此,在回顾现有连续时间分布式优化算法的基础上,根据系统动力学分类,尽可能全面地评述具有复杂动力学的多智能体系统分布式优化问题的最新研究进展,并对未来发展方向进行展望.     

Coordinated circumnavigation by multiple agents under directed topology

ABSTRACT

This paper focuses on the coordinated circumnavigation problem for multiple agents with directed communication topology. All agents are required to be evenly spaced around a moving target, and orbit around it with prescribed radii and circular velocity. We divide the coordinated circumnavigation system into a cascaded system consisting of a standoff tracking subsystem and a spacing distribution subsystem. A tracking controller and an additional controller for the two subsystems are developed, respectively. The global uniform stability of the coordinated circumnavigation system is analysed using the cascaded control theory. The presented controllers render each individual agent circumnavigating the target with the desired requirements. More importantly, we show that the derived tracking controller is a general extension of existing controllers for single agent circumnavigation problem. Another feature of the proposed controllers is that the directed topology considered only needs to have a directed spanning tree. Furthermore, the proposed controllers take the velocity constraints into consideration, that is more rational for practical applications. Numerical simulations are provided to verify the effectiveness of the proposed methods.     

足球机器人决策子系统设计与分析

足球机器人系统目前已成为人工智能应用技术研究的重要实验平台,系统的核心部分就是决策子系统。本文介绍了一种决策子系统的分层控制结构设计,它由协调层,运动规划层和基本动作层组成,这三层在逻辑上紧密联系又相对独立,使该决策子系统具有适应性强,扩展性好等特点。