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.     

Solving a modified consensus problem of linear multi-agent systems

A distributed protocol is proposed for a modified consensus problem of a network of agents that have the same continuous-time linear dynamics. Each agent estimates its own state using its output information and then sends the estimated state to its neighbor agents for the purpose of reaching a consensus. The modified consensus problem requires the group decision value to be a linear function of initial states and initial estimated states of all agents in the network, and the transformation matrix associated with this linear function not to be a zero matrix. It is proved that under the proposed control protocol, the modified consensus problem can be solved if and only if the system matrices of the agent’s dynamics are stabilizable and detectable, the input matrix is not a zero matrix, and the communication topology graph has a spanning tree. The proposed protocol can also be extended to multi-agent systems where agents are described by discrete-time linear dynamics. The corresponding necessary and sufficient conditions are provided as well.     

Finite-time consensus protocols for networks of dynamic agents by terminal iterative learning

This paper aims to address finite-time consensus problems for multi-agent systems under the iterative learning control framework. Distributed iterative learning protocols are presented, which adopt the terminal laws to update the control input and are offline feedforward design approaches. It is shown that iterative learning protocols can guarantee all agents in a directed graph to reach the finite-time consensus. Furthermore, the multi-agent systems can be enabled to achieve a finite-time consensus at any desired terminal state/output if iterative learning protocols can be improved by introducing the desired terminal state/output to a portion of agents. Simulation results show that iterative learning protocols can effectively accomplish finite-time consensus objectives for both first-order and higher order multi-agent systems.     

A simple population protocol for fast robust approximate majority

We describe and analyze a 3-state one-way population protocol to compute approximate majority in the model in which pairs of agents are drawn uniformly at random to interact. Given an initial configuration of x’s, y’s and blanks that contains at least one non-blank, the goal is for the agents to reach consensus on one of the values x or y. Additionally, the value chosen should be the majority non-blank initial value, provided it exceeds the minority by a sufficient margin. We prove that with high probability n agents reach consensus in O(n log n) interactions and the value chosen is the majority provided that its initial margin is at least . This protocol has the additional property of tolerating Byzantine behavior in of the agents, making it the first known population protocol that tolerates Byzantine agents.     

非平衡拓扑结构的多智能体网络系统一致性协议

针对多智能体网络系统,本文分别研究了非平衡拓扑结构的多智能体连续状态和离散状态下的一致性协议.首先提出了能使用有向图表示的多智能体网络系统的拓扑结构,并根据该拓扑结构建立了网络系统的1阶数学模型和提出了多智能体网络系统一致收敛准则.对于多智能体网络连续系统,该系统的一致平衡点最终收敛于初始状态的凸组合,本文最终确定了非平衡拓扑结构的一致平衡点.如果多智能体网络系统的拓扑结构没有改变,在离散状态下系统的一致平衡点仍收敛于初始状态的凸组合,并且离散状态下系统的一致平衡点与连续状态下系统的一致平衡点相等.最后采用8个智能体组成的网络拓扑进行计算机仿真,验证理论的正确性.     

Mean square average-consensus under measurement noises and fixed topologies: Necessary and sufficient conditions

In this paper, average-consensus control is considered for networks of continuous-time integrator agents under fixed and directed topologies. The control input of each agent can only use its local state and the states of its neighbors corrupted by white noises. To attenuate the measurement noises, time-varying consensus gains are introduced in the consensus protocol. By combining the tools of algebraic graph theory and stochastic analysis, the convergence of these kinds of protocols is analyzed. Firstly, for noise-free cases, necessary and sufficient conditions are given on the network topology and consensus gains to achieve average-consensus. Secondly, for the cases with measurement noises, necessary and sufficient conditions are given on the consensus gains to achieve asymptotic unbiased mean square average-consensus. It is shown that under the protocol designed, all agents’ states converge to a common Gaussian random variable, whose mathematical expectation is just the average of the initial states.     

Finite-time weighted average consensus with respect to a monotonic function and its application

The consensus state is an important and fundamental quantity for consensus problems of multi-agent systems, which indicates where all the dynamical agents reach. In this paper, weighted average consensus with respect to a monotonic function, which means that the trajectories of the monotonic function along the state of each agent reach the weighted average of their initial values, is studied for a group of kinematic agents with time-varying topology. By constructing a continuous nonlinear distributed protocol, such a consensus problem can be solved in finite time even though the time-varying topology involves unconnected graphs. Then the distributed protocol is employed to compute the maximum-likelihood estimation of unknown parameters over sensor networks. Compared with the existing results, the estimate scheme proposed here may reduce the costs of data communication, storage memory, book-keeping and computational overheads.     

Reach a nonlinear consensus for MAS via doubly stochastic quadratic operators

This technical note addresses the new nonlinear protocol class of doubly stochastic quadratic operators (DSQOs) for coordination of consensus problem in multi-agent systems (MAS). We derive the conditions for ensuring that every agent reaches consensus on a desired rate of the group's decision where the group decision value in its agent's initial statuses varies. Besides that, we investigate a nonlinear protocol sub-class of extreme DSQO (EDSQO) to reach a consensus for MAS to a common value with nonlinear low-complexity rules and fast time convergence if the interactions for each agent are not selfish. In addition, to extend the results to reach a consensus and to avoid the selfish case we specify a general class of DSQO for reaching a consensus under any given case of initial states. The case that MAS reach a consensus by DSQO is if each member of the agent group has positive interactions of DSQO (PDSQO) with the others. The convergence of both EDSQO and PDSQO classes is found to be directed towards the centre point. Finally, experimental simulations are given to support the analysis from theoretical aspect.     

A connection between formation infeasibility and velocity alignment in kinematic multi-agent systems

In this paper, a feedback control strategy that achieves convergence of a multi-agent system to a desired formation configuration is proposed for both the cases of agents with single integrator and nonholonomic unicycle-type kinematics. When inter-agent objectives that specify the desired formation cannot occur simultaneously in the state space the desired formation is infeasible. It is shown that under certain assumptions, formation infeasibility forces the agents’ velocity vectors to a common value at steady state. This provides a connection between formation infeasibility and flocking behavior for the multi-agent system. We finally also obtain an analytic expression of the common velocity vector in the case of formation infeasibility.     

Interval consensus problem of multi-agent systems in accordance with switching protocol

In this paper, we discuss the interval consensus problem of multi-agent systems by providing a special Laplacian of directed graphs. As one of the most important issues in the coordination control of multi-agent systems, the consensus problem requires that the output of several spatially distributed agents reach a common value that depends on the states of all agents. For the given consensus protocol and initial states, a fixed consensus value is obtained. The resulting consensus value, however, may not be ideal or meet the quality that we require from the multi-agent system. In this paper, by introducing two state-dependent switching parameters into the consensus protocol, the system given by the proposed protocol can globally asymptotically converge to a designated point on a special closed and bounded interval. In other words, the system given by the proposed protocol can globally asymptotically reach interval consensus and then the system can also achieve a generalised interval average consensus if the directed graph is balanced. Simulations are presented to demonstrate the effectiveness of our theoretical results.     

Multi-agent team cooperation: A game theory approach

The main goal of this work is to design a team of agents that can accomplish consensus over a common value for the agents’ output using cooperative game theory approach. A semi-decentralized optimal control strategy that was recently introduced by the authors is utilized that is based on minimization of individual cost using local information. Cooperative game theory is then used to ensure team cooperation by considering a combination of individual cost as a team cost function. Minimization of this cost function results in a set of Pareto-efficient solutions. Among the Pareto-efficient solutions the Nash-bargaining solution is chosen. The Nash-bargaining solution is obtained by maximizing the product of the difference between the costs achieved through the optimal control strategy and the one obtained through the Pareto-efficient solution. The latter solution results in a lower cost for each agent at the expense of requiring full information set. To avoid this drawback some constraints are added to the structure of the controller that is suggested for the entire team using the linear matrix inequality (LMI) formulation of the minimization problem. Consequently, although the controller is designed to minimize a unique team cost function, it only uses the available information set for each agent. A comparison between the average cost that is obtained by using the above two methods is conducted to illustrate the performance capabilities of our proposed solutions.     

Optimal consensus algorithms for cooperative team of agents subject to partial information

The objectives of this work are the development and design of controllers for a team of agents that accomplish consensus for agents’ output in both leaderless (LL) and modified leader-follower (MLF) architectures. Towards this end, a semi-decentralized optimal control strategy is designed based on minimization of individual cost functions over a finite horizon using local information. Interactions among agents due to information flows are represented through the control channels in characterization of the dynamical model of each agent. It is shown that minimization of the proposed cost functions results in a modified consensus algorithm for LL and MLF architectures. In the latter case, the desired output is assumed to be available for only the leader while the followers should follow the leader using information exchanges existing among themselves and the leader through a predefined topology. Furthermore, the performance of the cooperative team under a member’s fault is formally analyzed and investigated. The robustness of the team to uncertainties and faults in the leader or followers and adaptability of the team members to these unanticipated situations are also shown rigorously. Finally, simulation results are presented to demonstrate the effectiveness of our proposed methodologies in achieving prespecified requirements.     

Consensus of networked multi-agent systems with communication delays based on the networked predictive control scheme

The consensus problem of discrete-time networked multi-agent systems (NMASs) with a communication delay is investigated in this article, where the dynamics of agents described by discrete-time linear time-invariant systems can be either uniform or non-uniform. For the NMASs with a directed topology and constant delay, a novel protocol based on the networked predictive control scheme is proposed to compensate for communication delay actively. Using algebraic graph theories and matrix theories, necessary and/or sufficient conditions of achieving consensus are obtained, which indicates that, under the proposed protocol, the consensus is independent of the network delay and only dominated by agents' dynamics and communication topology. Meanwhile, the protocol design and consensus analysis are also presented in the case of no network delay. Simulation results are further presented to demonstrate the effectiveness of theoretical results.     

Intermittent observer-based consensus control for multi-agent systems with switching topologies

In this paper, we focus on the consensus problem for leaderless and leader–followers multi-agent systems with periodically intermittent control. The dynamics of each agent in the system is a linear system, and the interconnection topology among the agents is assumed to be switching. We assume that each agent can only share the outputs with its neighbours. Therefore, a class of distributed intermittent observer-based consensus protocols are proposed for each agent. First, in order to solve this problem, a parameter-dependent common Lyapunov function is constructed. Using this function, we prove that all agents can access a prescribed value, under the designed intermittent controller and observer, if there are suitable conditions on communication. Second, based on the investigation of the leader-following consensus problem, we design a new distributed intermittent observer-based protocol for each following agent. Finally, we provide an illustrative example to verify the effectiveness of the proposed approach.     

切换拓扑一阶积分器网络量化趋同控制

针对数字信道中传输的是经过量化和编码后的数据,研究了切换拓扑情况下连续时间一阶积分器网络中的量化趋同问题.通过均匀量化器,每个智能体将量化后的状态传输给邻居,并利用所得信息设计协议,实现量化趋同.在所提出的量化趋同协议下,所有状态将在有限时间内进入包含状态均值的量化层中.特别地,对于通信拓扑是时不变的情况,给出了实现量化趋同所需时间的上界.仿真结果验证了所提出算法的有效性.     

Finite-time median-related group consensus over directed networks

ABSTRACT

In this paper, we investigate a novel finite-time median-related group consensus problem, where the finial consensus value can be identified as a desired function of the median of initial states instead of the much studied average value. The underlying communication topology is modelled by a weighted dynamical directed network. A distributed control protocol is firstly introduced to ensure that the agents can reach a median-related consensus in finite time in a collaboration network, meaning that all edge-weights of the communication network are non-negative. We then generalise the results to cooperation–competition networks, where the communication network is divided into predetermined collaboration subnetworks allowing possibly negative weights. Effective group control protocols are designed to guarantee the median-related group consensus in finite time. Finally, numerical simulations are presented to illustrate the availability of our theoretical results.     

一种基于切换拓扑和事件触发机制的一致性协议

研究了一种新的基于切换拓扑的事件触发一致性协议,该协议设计了两个事件触发器,包括智能体状态演化引发的收敛事件触发器和拓扑变化引发的拓扑事件触发器,并给出了与事件触发器有关的公共Lyapunov函数的稳定性分析和理论证明,还设计了一种基于约束集的网络连通算法,用于提高网络的连通性。仿真实验结果表明,新的协议能够使得系统收敛一致,有效降低智能体控制器的更新频率,减少系统能耗,提升网络的连通效果,能为事件触发控制的后续研究提供理论支撑。     

Quantised consensus of multi-agent systems with nonlinear dynamics

This paper studies the consensus problem of first-order and second-order multi-agent systems with nonlinear dynamics and quantised interactions. Continuous-time and impulsive control inputs are designed for the multi-agent systems on the logarithmic quantised relative state measurements of agents, respectively. By using nonsmooth analysis tools, we get some sufficient conditions for the consensus of multi-agent systems under the continuous-time inputs. Compared with continuous-time control inputs, impulsive distributed control inputs just use the state variables of the systems at discrete-time instances. Based on impulsive control theory, we prove that the multi-agent systems can reach consensus by choosing proper control gains and impulsive intervals. The simulation results are given to verify the effectiveness of the theoretical results.     

To reach consensus using uninorm aggregation operator: A gossip‐based protocol

Gossip‐based protocols for group communication have attractive scalability and reliability properties. This paper presents a gossip‐based protocol that enables agents to reach a consensus based on a specific uninorm aggregation operator. We theoretically analyze the convergence, the speed and the randomness features of this protocol as well as its extensions. This model can be used to handle the uncertainty and the fast convergence characteristic of collective decision dynamics. The experimental results show that this protocol is efficient, scalable, and resilient against the failures under various network sizes, and topologies. © 2012 Wiley Periodicals, Inc.     

Distributed consensus of multi‐agent systems with general linear node dynamics and intermittent communications

Without assuming that the mobile agents can communicate with their neighbors all the time, the consensus problem of multi‐agent systems with general linear node dynamics and a fixed directed topology is investigated. To achieve consensus, a new class of distributed protocols designed based only on the intermittent relative information are presented. By using tools from matrix analysis and switching systems theory, it is theoretically shown that the consensus in multi‐agent systems with a periodic intermittent communication and directed topology containing a spanning tree can be cast into the stability of a set of low‐dimensional switching systems. It is proved that there exists a protocol guaranteeing consensus if each agent is stabilizable and the communication rate is larger than a threshold value. Furthermore, a multi‐step intermittent consensus protocol design procedure is provided. The consensus algorithm is then extended to solve the formation control problem of linear multi‐agent systems with intermittent communication constraints as well as the consensus tracking problem with switching directed topologies. Finally, some numerical simulations are provided to verify the effectiveness of the theoretical results. Copyright © 2013 John Wiley & Sons, Ltd.