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

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

一个基于模拟退火的多主体模型及其应用

近些年,多主体系统的理论及应用得到了人们的广泛关注,并得以迅速发展.研究者提出了很多基于多主体系统理论的模型,用于求解各种问题.AER(Agent-environment-rules)模型正是一个用于求解约束满足问题较为成功的例子.但是,主体的静态策略选择在一定程度上限制了模型的求解性能.将模拟退火算法与多主体系统思想相结合,并赋予主体更为高效的动态策略选择的能力,提出了SAAER模型(simulated annealing based AER model).基于约束满足问题经典实例--N-Queen问题和染色问题的实验表明,改进后的模型较之原模型获得了更高的效率和稳定性.对于N=10000的大规模N-Queen问题,能在200s左右的时间求得精确解.     

一个基于动态代理次序的分布式约束求解算法

最近分布式约束满足问题逐渐成为人工智能领域一个新的研究热点,它的提出将约束满足问题的应用范围扩展到复杂的分布式环境.并发搜索是求解分布式约束满足问题的一个高效算法.文中改进了并发搜索中的变量选择策略,将动态代理次序应用到其中,同时提出了一个适合于分布式条件下的基于动态代理次序的并发搜索算法.多组随机生成问题实验结果显示加入动态代理次序的并发回溯搜索在求解效率和通信量方面都表现出优异的性能.     

面向多目标追踪的无线传感器网络协同任务分配研究

在基于动态联盟机制的无线传感器网络协同任务分配研究中,为了解决多目标追踪带来的联盟间的资 源竞争问题,本文采用分布式约束满足算法解决多动态联盟间的协同问题．根据无线传感器网络多目标追踪的应用 需求,建立了基于动态联盟机制的协同任务分配的分布式约束满足模型,并采用分布式随机算法求解满足约束条件 的动态联盟集合,实现多动态联盟间的协同．仿真结果表明,分布式约束满足算法有效地解决了多目标追踪中多个 动态联盟间的资源竞争问题,能够有效降低系统的能量消耗．     

基于MAS的分布式约束满足求解在供应链研究中的应用

简要介绍了多智能体系统(MAS)在供应链研究中的应用，给出了约束满足问题(Constraint Satisfaction Problem,CSP)和分布式约束满足问题(Distributed CSP)的定义以及其应用现状，提出了一个利用基于MAS的分布式约束满足求解来研究供应链问题的基本框架，并给出了其求解过程。     

基于分布式约束满足的多约束单路径路由问题求解

约束路由问题是IP网络的一个核心功能,由于求解多约束路由问题属于NP完全问题,所以大量的研究工作围绕此展开.基于分布式约束满足的思想,设计多约束单路径路由问题求解算法,分析表明该求解算法降低计算复杂度,提高算法的性能.在分布式条件下完成算法的实现,经实验表明,算法近似程度较好,求解速度快.     

以多人博弈效用函数为演化指导函数的演化算法

研究一种基于多人纯策略非合作博弈的演化优化算法,可用于一类组合优化问题的求解.该算法的演化过程可建模为一个马尔科夫链模型.它将组合优化问题映射为多人非合作博弈,通过博弈主体的理性行为对问题的解进行优化.给出定义良好并可供扩展的算法框架,明确算法的要素所必须满足的3个约束:有限性约束、弱一致性约束和收敛性约束,并应用于若干典型NP-Hard的组合优化问题的求解.理论和实验结果表明,与一些传统优化算法相比,本算法在实际应用中具有良好的问题求解能力.     

矩阵方程的分布式求解算法研究概述

近年来,随着大规模网络的兴起和分布式优化理论的广泛应用,矩阵方程的分布式求解算法研究也受到了越来越多的重视.矩阵方程的计算求解在理论和工程领域都有着重要的意义.在多智能体网络下的分布式计算问题中,矩阵方程中的数据信息按照各种方式进行划分,单个智能体只能够获取其中的一份数据,然后通过与其邻居智能体进行信息交互,最终合作求解出不同类型的符合方程要求的解.本文集中讨论了近几年来针对线性代数方程、几类不带约束和带约束线性矩阵方程、以及其他矩阵相关的分布式计算和求解问题,介绍了投影一致方法、转化成分布式优化问题再求解的方法、以及针对特殊矩阵如稀疏矩阵的信息传递方法等分布式算法设计方法.最后,简要总结全文以及对分布式矩阵计算方向的研究进行了展望.     

分布式约束满足问题及其在MAS任务分配中的应用*

针对多智能体系统(MAS)任务分配问题中多个任务与MAS两者的分布式特征,将任务分配问题形式化为分布式约束满足问题(DCSP)进行求解,分别建立了以任务为中心和以agent为中心两种MAS任务分配模型,基于改进的DCSP分布式并行求解算法,提出了基于DCSP的MAS任务分配问题求解框架。该方法适合求解agent间通信有随机延迟以及agent间存在多约束的问题,应用实例的求解表明了其实用性与有效性。     

基于自适应精确罚函数的分布式资源分配算法

在多智能体系统中, 分布式资源分配问题是近年来研究热点之一. 分布式资源分配问题旨在通过智能体间信息交互实现资源最优配置. 其中智能体局部约束给算法设计带来巨大挑战. 首先, 针对一阶多智能体系统, 提出基于自适应精确罚函数的分布式资源分配算法, 其中各智能体利用距离函数实现局部约束求解. 此外, 自适应设计思想旨在避免算法对全局先验知识获取. 其次, 利用跟踪技术实现二阶多智能体系统算法设计. 并利用凸函数和非光滑分析法给出严谨的收敛性分析. 最后, 仿真结果验证了本文所设计优化算法对强凸分布式资源分配问题的有效性.     

Algorithms for Distributed Constraint Satisfaction: A Review

When multiple agents are in a shared environment, there usually exist constraints among the possible actions of these agents. A distributed constraint satisfaction problem (distributed CSP) is a problem to find a consistent combination of actions that satisfies these inter-agent constraints. Various application problems in multi-agent systems can be formalized as distributed CSPs. This paper gives an overview of the existing research on distributed CSPs. First, we briefly describe the problem formalization and algorithms of normal, centralized CSPs. Then, we show the problem formalization and several MAS application problems of distributed CSPs. Furthermore, we describe a series of algorithms for solving distributed CSPs, i.e., the asynchronous backtracking, the asynchronous weak-commitment search, the distributed breakout, and distributed consistency algorithms. Finally, we show two extensions of the basic problem formalization of distributed CSPs, i.e., handling multiple local variables, and dealing with over-constrained problems.     

Nogood-FC for solving partitionable constraint satisfaction problems

Many real problems can be naturally modelled as constraint satisfaction problems (CSPs). However, some of these problems are of a distributed nature, which requires problems of this kind to be modelled as distributed constraint satisfaction problems (DCSPs). In this work, we present a distributed model for solving CSPs. Our technique carries out a partition over the constraint network using a graph partitioning software; after partitioning, each sub-CSP is arranged into a DFS-tree CSP structure that is used as a hierarchy of communication by our distributed algorithm. We show that our distributed algorithm outperforms well-known centralized algorithms solving partitionable CSPs.     

The distributed constraint satisfaction problem: formalization andalgorithms

We develop a formalism called a distributed constraint satisfaction problem (distributed CSP) and algorithms for solving distributed CSPs. A distributed CSP is a constraint satisfaction problem in which variables and constraints are distributed among multiple agents. Various application problems in distributed artificial intelligence can be formalized as distributed CSPs. We present our newly developed technique called asynchronous backtracking that allows agents to act asynchronously and concurrently without any global control, while guaranteeing the completeness of the algorithm. Furthermore, we describe how the asynchronous backtracking algorithm can be modified into a more efficient algorithm called an asynchronous weak-commitment search, which can revise a bad decision without exhaustive search by changing the priority order of agents dynamically. The experimental results on various example problems show that the asynchronous weak-commitment search algorithm is, by far more, efficient than the asynchronous backtracking algorithm and can solve fairly large-scale problems     

多智能体系统动态协调与分布式控制设计

多智能体系统的主要研究目的在于探索由个体之间的相互作用所产生的群体协调现象的内在机制和原理,而控制或反馈在多智能体协调运动中起着至关重要的作用．本文集中讨论了多智能体协调研究中的几个新兴的基本问题,包括输出调节、集合协调和覆盖．文中着重介绍了分布式估计和内模原理两种多智能体系统分布式输出调节方法及相关的研究进展：关于多智能体系统的目标集合协调,本文从集合聚集和集合优化两方面做了详尽论述：多智能体覆盖有多种分类方式,从覆盖对象的特征出发可将其划分为区域覆盖、边界覆盖和动态目标覆盖3种类型,并对它们的研究背景和最新成果予以介绍．另外文章还对多智能体系统协调控制的理论和应用研究进行了展望．     

Tractable classes for CSPs of arbitrary arity: from theory to practice

The research of this thesis focuses on the analysis of polynomial classes and their practical exploitation for solving constraint satisfaction problems (CSPs) with finite domains. In particular, I worked on bridging the gap between theoretical works and practical results in constraint solvers. Specifically, the goal of this thesis is to find explanation for the effectiveness of solvers, and also to show that studied tractable classes are not artificial since several real-problems among the ones used in the CSP 2008 Competition belong to them.Our work is organized into three main parts. In the first part, we proposed several types of microstructures for CSPs of arbitrary arity which are based on some knwon binary encoding of non-binary CSPs like, dual encoding, hidden-variable transformation and mixed (or double) encoding. These theoretical tools are designed to facilitate the study of tractable classes, sets of CSP instances which can be solved in polytime, when the constraints are non-binary. After that, we propose a new tractable classes of CSPs whose the highlighting should allow on the one hand to explain the effectiveness of solvers of the state of the art namely FC, MAC, RFL and on the second hand to provide the opportunities for easy integration in these solvers. These would include the definition of new tractable classes without using of an ad hoc algorithms as in the traditional case. These new tractable classes are related to the number of maximal cliques in the microstructure of binary or non-binary CSP. In the last part, we focus on the presence of instances belonging to polynomial classes in classical benchmarks used by the CP community. We study in particular the Broken-Triangle Property (BTP) and its extension DBTP to CSP of arbitrary arity. Next, we prove that BTP can also be used to reduce the size of the search space by merging pairs of values on which no broken triangle exists. Finally, we introduce a formal framework, called transformation, and we develop the concept of hidden tractable class that we exploit from an experimental point of view.     

A graph-based immune-inspired constraint satisfaction search

We propose an artificial immune algorithm to solve constraint satisfaction problems (CSPs). Recently, bio-inspired algorithms have been proposed to solve CSPs. They have shown to be efficient in solving hard problem instances. Given that recent publications indicate that immune-inspired algorithms offer advantages to solve complex problems, our main goal is to propose an efficient immune algorithm which can solve CSPs. We have calibrated our algorithm using relevance estimation and value calibration (REVAC), which is a new technique recently introduced to find the parameter values for evolutionary algorithms. The tests were carried out using randomly generated binary constraint satisfaction problems and instances of the three-colouring problem with different constraint networks. The results suggest that the technique may be successfully applied to solve CSPs.     

Time-varying formation control for double-integrator multi-agent systems with jointly connected topologies

Time-varying formation analysis and design problems for double-integrator multi-agent systems with jointly connected topologies are investigated. Different from the previous work on formation control, in this paper, the formation is specified by time-varying piecewise continuously differentiable vectors and the topology can be disconnected at any time instant. First, a distributed formation control protocol is constructed using local neighbour-to-neighbour information. In the case where the switching topology is jointly connected, necessary and sufficient conditions for double-integrator multi-agent systems to achieve time-varying formations are proposed, where the formation feasibility constraint is also derived. To describe the macroscopic movement of the whole formation, explicit expressions of the formation reference are presented, the motion modes of which can be partially assigned. Moreover, an approach to design the formation control protocol is given, which is fully distributed and requires no global information about the topology. Finally, the obtained theoretical results are applied to deal with the time-varying formation control problems of multi-vehicle systems.     

分布式优化的多智能体方法

分布式优化作为分布式协调控制领域中的一个基本而重要的研究课题,近年来,不同领域的众多学者对其产生了广泛的研究兴趣.本文总结归纳了分布式优化的研究现状和近期的研究成果,重点对离线分布式优化和在线分布式优化进行了阐述,并从算法设计和收敛性分析这两个角度进行了剖析.特别地,针对一类混合均衡问题,本文介绍了一类分布式求解算法.最后,阐述了当前尚未解决的问题和未来的研究方向.