多agent规划综述*

多Agent规划是智能规划和多Agent系统的交叉领域,随着智能规划领域研究范围的不断扩展和多Agent系统领域研究内容的不断深入,多Agent规划受到了越来越多的关注。有鉴于此,本文对多Agent规划的概念和主要方法进行全面综述。具体内容包括智能规划和多Agent系统的背景介绍、多Agent规划的各种形式化描述方式以及基于规划修复、合并或者马尔可夫决策过程的的分布式规划方法。最后,还给出了多Agent规划的发展趋势。     

Multi-Dimensional,MultiStep Negotiation

We present a multi-dimensional, multi-step negotiation mechanism for task allocation among cooperative agents based on distributed search. This mechanism uses marginal utility gain and marginal utility cost to structure this search process, so as to find a solution that maximizes the agents’ combined utility. These two utility values together with temporal constraints summarize the agents’ local information and reduce the communication load. This mechanism is anytime in character: by investing more time, the agents increase the likelihood of getting a better solution. We also introduce a multiple attribute utility function into negotiations. This allows agents to negotiate over the multiple attributes of the commitment, which produces more options, making it more likely for agents to find a solution that increases the global utility. A set of protocols are constructed and the experimental result shows a phase transition phenomenon as the complexity of negotiation situation changes. A measure of negotiation complexity is developed that can be used by an agent to choose an appropriate protocol, allowing the agents to explicitly balance the gain from the negotiation and the resource usage of the negotiation.This revised version was published online in August 2005 with a corrected cover date.     

IMPACTing SHOP: Putting an AI Planner Into a Multi-Agent Environment

In this paper we describe a formalism for integrating the SHOP HTN planning system with the IMPACT multi-agent environment. We define the A-SHOP algorithm, an agentized adaptation of the SHOP planning algorithm that takes advantage of IMPACT's capabilities for interacting with external agents, performing mixed symbolic/numeric computations, and making queries to distributed, heterogeneous information sources (such as arbitrary legacy and/or specialized data structures or external databases). We show that A-SHOP is both sound and complete if certain conditions are met.     

The analysis and performance evaluation of the pheromone-Q-learning algorithm

Abstract: The paper presents the pheromone‐Q‐learning (Phe‐Q) algorithm, a variation of Q‐learning. The technique was developed to allow agents to communicate and jointly learn to solve a problem. Phe‐Q learning combines the standard Q‐learning technique with a synthetic pheromone that acts as a communication medium speeding up the learning process of cooperating agents. The Phe‐Q update equation includes a belief factor that reflects the confidence an agent has in the pheromone (the communication medium) deposited in the environment by other agents. With the Phe‐Q update equation, the speed of convergence towards an optimal solution depends on a number of parameters including the number of agents solving a problem, the amount of pheromone deposit, the diffusion into neighbouring cells and the evaporation rate. The main objective of this paper is to describe and evaluate the performance of the Phe‐Q algorithm. The paper demonstrates the improved performance of cooperating Phe‐Q agents over non‐cooperating agents. The paper also shows how Phe‐Q learning can be improved by optimizing all the parameters that control the use of the synthetic pheromone.     

Dynamic Motion Planning using a distributed representation

Methods for dynamic motion planning are presented which take into account not only geometric environmental constraints but also physical constraints on motion. The approach uses a distributed representation which allows parallel implementation of the using a cellular strength-diffusion method in the search for the motion in space-time. We consider three cases: (1) no knowledge of the motion of the obstacles is assumed so that the planning is purely reactive; (2) full knowledge of the moving obstacles is available so that the planner can deliver an optimal motion; and (3) an interleaved algorithm in which the ability to predict a short time ahead (based on an assumption of simple linear motion of the obstacles) is exploited. This last algorithm emphasizes the importance of the interaction between the planner and the environment via sensors. We conclude that to plan motion in a dynamic environment in which uncertainties abound, the only sensible strategy is to constantly sense the world and plan the motion accordingly.The experimental work reported here was carried out while the authors were at Department of Computer Science, Queen Mary and Westfield College, University of London.     

基于隐私保持的分布式数据挖掘技术研究

分析了基于隐私保持的分布式数据挖掘的特点,对现有的保持隐私的分布式数据挖掘技术进行了分类和总结,最后详细讨论了评价指标。     

一个基于Agent的隐私保护信息过滤系统的结构

把隐私保护问题引入信息过滤系统中，提出一个改进的、基于代理的信息过滤系统的总体结构。     

改进的分布式关联规则安全挖掘算法

以往各种分布式数据挖掘隐私保护算法无法有效解决串通问题,从而限制了其大规模应用,针对上述问题,在Clifton分布式关联规则安全挖掘算法的基础上,提出AKCA算法。采用各站点联合建立并求解方程组的安全多方求和方法。结果证明经过改进的算法能够抵御串通攻击,不借助签名验证也能发现恶意篡改。     

多智能体路径规划综述

多智能体路径规划（multi-agent path finding;MAPF）是为多个智能体规划路径的问题;关键约束是多个智能体同时沿着规划路径行进而不会发生冲突。MAPF在物流、军事、安防等领域有着大量应用。对国内外关于MAPF的主要研究成果进行系统整理和分类;按照规划方式不同;MAPF算法分为集中式规划算法和分布式执行算法。集中式规划算法是最经典和最常用的MAPF算法;主要分为基于[A*]搜索、基于冲突搜索、基于代价增长树和基于规约四种算法。分布式执行算法是人工智能领域兴起的基于强化学习的MAPF算法;按照改进技术不同;分布式执行算法分为专家演示型、改进通信型和任务分解型三种算法。基于上述分类;比较MAPF各种算法的特点和适用性;分析现有算法的优点和不足;指出现有算法面临的挑战并对未来工作进行了展望。     

分布式装配置换流水车间调度问题研究综述

近几十年来;现代制造业发展迅速;一种趋势是在分布式生产工厂进行工件的加工;待完成后到装配工厂集中装配成最终产品。该模式在带来诸多好处的同时;对资源调度提出了新的挑战。针对分布式装配置换流水车间调度问题（distributed assembly permutation flowshop scheduling problem; DAPFSP）;介绍了DAPFSP的背景和存在的主要困难;进而对以最小化最大完工时间为优化目标的DAPFSP;从数学模型、编解码策略、全局和局部搜索算法角度进行探讨;分别综述了以最小化总流程时间等为优化目标;具有零等待等约束;以及考虑准备时间等因素的DAPFSP研究成果。最后;对有待进一步开展的研究工作进行展望。     

基于局部并行搜索的分布式约束优化算法框架

针对当前局部搜索算法在求解大规模、高密度的分布式约束优化问题（DCOP）时,求解困难且难以跳出局部最优取得进一步优化等问题,提出一种基于局部并行搜索的分布式约束优化算法框架（LPOS）,算法中agent通过自身的取值并行地搜索局部所有邻居取值来进一步扩大对解空间的搜索,从而避免算法过早陷入局部最优。为了保证算法的收敛性与稳定性,设计了一种自适应平衡因子K来平衡算法对解的开发和继承能力,并在理论层面证明了并行搜索优化算法可以扩大对解空间的搜索,自适应平衡因子K可以实现平衡目的。综合实验结果表明,基于该算法框架的算法在求解低密度和高密度DCOP时性能都优于目前最新的算法。特别是在求解高密度DCOP中有显著的提升。     

2-local 5/4-competitive algorithm for multicoloring triangle-free hexagonal graphs

An important optimization problem in the design of cellular networks is to assign sets of frequencies to transmitters to avoid unacceptable interference. A cellular network is generally modeled as a subgraph of the infinite triangular lattice. The distributed frequency assignment problem can be abstracted as a multicoloring problem on a weighted hexagonal graph, where the weight vector represents the number of calls to be assigned at vertices. In this paper we present a 2-local distributed algorithm for multicoloring triangle-free hexagonal graphs using only the local clique numbers ω₁(v) and ω₂(v) at each vertex v of the given hexagonal graph, which can be computed from local information available at the vertex. We prove that the algorithm uses no more than colors for any triangle-free hexagonal graph G, without explicitly computing the global clique number ω(G). Hence the competitive ratio of the algorithm is 5/4.     

非平衡有向网络下带约束的连续时间分布式优化算法设计

本文基于权重不平衡有向网络,对一类分布式约束优化问题进行研究,其中全局目标函数等于具有李普希兹梯度的强凸目标函数之和,并且每个智能体的状态都有一个局部约束集.每个智能体仅知道自身的局部目标函数和非空约束集.本文的目标是用分布式方法求解该问题的最优解.针对优化问题,提出了一种新的分布式投影梯度连续时间协调算法,利用拉普拉斯矩阵的零特征值对应的左特征向量消除了图的不平衡性.在某些假设下,结合凸分析理论和李雅普诺夫稳定性理论,证明了算法能够获得问题的最优解.最后,通过仿真验证了算法的有效性.     

面向企业信用评估的分布式隐私保护数据挖掘

介绍企业信用评估和当前隐私保护数据挖掘技术的最新进展,利用适用于企业信用评估的大规模分布式隐私保护数据挖掘架构,讨论了基于该架构的面向企业信用评估的分布式隐私保护数据挖掘。该研究不仅将有助于大规模分布式环境下的隐私保护数据挖掘系统的研发,而且能够有力推动“信用中国”的建设步伐,以达到更好地服务经济的目的。     

真实语料下基于多Agent的分布式英语语块识别

为了能比较不同方法的性能,常常希望在公共的训练集和测试集上进行语块识别。但是,用于实验的公共训练集和测试集往往规模较小而且具有领域的局限性。因而,在跨领域的真实语料情况下,语块识别的精确率有很大的下降。采用真实开放语料,设计多组实验研究不同的词性标注结果、不同领域的语料和不同的知识库对语块识别的影响,考察基于多Agent结构的分布式英语语块识别策略在实际系统中应用的可能性。实验表明,基于多Agent结构的分布式英语语块识别策略在真实开放语料下F测度达到了92%,基本能够满足实际应用的需要。     

Finding a Feasible Solution for a Class of Distributed Problems with a Single Sum Constraint Using Agents

In this paper, we describe a Multi-Agent System which is capable of finding a feasible solution of a class of distributed problems, in which the subproblems share a single a sum constraint. Emphasis is given to correctness issues and termination detection.     

Nagging: A scalable fault-tolerant paradigm for distributed search

This paper describes nagging, a technique for parallelizing search in a heterogeneous distributed computing environment. Nagging exploits the speedup anomaly often observed when parallelizing problems by playing multiple reformulations of the problem or portions of the problem against each other. Nagging is both fault tolerant and robust to long message latencies. In this paper, we show how nagging can be used to parallelize several different algorithms drawn from the artificial intelligence literature, and describe how nagging can be combined with partitioning, the more traditional search parallelization strategy. We present a theoretical analysis of the advantage of nagging with respect to partitioning, and give empirical results obtained on a cluster of 64 processors that demonstrate nagging's effectiveness and scalability as applied to A^* search, β minimax game tree search, and the Davis–Putnam algorithm.