Hybrid Control for Connectivity Preserving Flocking

In this technical note, we address the combined problem of motion and network topology control in a group of mobile agents with common objective the flocking behavior of the group. Instead of assuming network connectivity, we enforce it by means of distributed topology control that decides on both deletion and creation of communication links between agents, adapting the network to the group's spatial distribution. With this protocol ensuring network connectivity, a decentralized motion controller aligns agent velocity vectors and regulates inter-agent distances to maintain existing network links. The stability of the flocking controller is established in continuous time by means of an observability argument on a quadratic form of the graph Laplacian that exploits the time delay between link deletion and creation caused by the topology control protocol, which induces a dwell time between network switches.      

Algebraic Connectivity Estimation Based on Decentralized Inverse Power Iteration

In this work, we propose a new scheme to estimate the algebraic connectivity of the graph describing the network topology of a multi‐agent system. We consider network topologies modeled by undirected graphs. The main idea is to propose a new decentralized conjugate gradient algorithm and a decentralized compound inverse power iteration scheme. The matrix inversion computation in this scheme is replaced by solving the non‐homogeneous linear equations relying on the proposed decentralized conjugate gradient algorithm. With this scheme, we can achieve a fast convergence rate in estimating the algebraic connectivity by setting the parameter μ properly. Simulation results demonstrate the effectiveness of the proposed scheme.     

Randomized mechanism design for decentralized network scheduling

ABSTRACT

In the network scheduling, jobs (tasks) must be scheduled on uniform machines (processors) connected by a complete graph so as to minimize the total weighted completion time. This setting can be applied in distributed multi-processor computing environments and also in operations research. In this paper, we study the design of randomized decentralized mechanism in the setting where a set of non-preemptive jobs select randomly a machine from a set of uniform machines to be processed on, and each machine can process at most one job at a time. We introduce a new concept of myopic Bayes–Nash incentive compatibility which weakens the classical Bayes–Nash incentive compatibility and derive a randomized decentralized mechanism under the assumption that each job is a rational and selfish agent. We show that our mechanism can induce jobs to report truthfully their private information referred to myopic Bayes–Nash implementability by using a graph theoretic interpretation of the incentive compatibility constraints. Furthermore, we prove that the performance of this mechanism is asymptotically optimal.     

Tracking and formation control of multiple autonomous agents: A two-level consensus approach

Simultaneous tracking and formation control is addressed for a team of autonomous agents that evolve dynamically in a space containing a measurable vector field. Each agent measures the local value of the field along its trajectory and occasionally shares relevant information with other agents, in order to estimate the spatial average obtained from averaging measurements across all agents. Using shared information, agents control their trajectories in a cooperative manner, with the dual goals of driving the average field measurement to a specified value and maintaining a desired formation about the average. Two approaches to virtual leader estimation are considered. The first involves the synthesis of a common virtual leader state, whereas the second involves decentralized estimation of the virtual leader by individual agents. Under the second approach, control is posed as a two-level consensus problem, where agents reach agreement on the virtual leader state at one level and reach formation about the virtual leader at the other level. The decentralized approach is effective even when communication among agents is limited, in the sense that the associated network graph can be disconnected in frozen time.     

A Distributed Ant Algorithm for\protect Efficiently Patrolling a Network

We consider the problem of patrolling—i.e. ongoing exploration of a network by a decentralized group of simple memoryless robotic agents. The model for the network is an undirected graph, and our goal, beyond complete exploration, is to achieve close to uniform frequency of traversal of the graphs edges. A simple multi-agent exploration algorithm is presented and analyzed. It is shown that a single agent following this procedure enters, after a transient period, a periodic motion which is an extended Eulerian cycle, during which all edges are traversed an identical number of times. We further prove that if the network is Eulerian, a single agent goes into an Eulerian cycle within 2|E|D steps, |E| being the number of edges in the graph and D being its diameter. For a team of k agents, we show that after at most 2( 1 + 1/k) |E|D steps the numbers of edge visits in the network are balanced up to a factor of two. In addition, various aspects of the algorithm are demonstrated by simulations.     

Decentralized observers with consensus filters for distributed discrete-time linear systems

This paper presents a decentralized observer with a consensus filter for the state observation of discrete-time linear distributed systems. Each agent in the distributed system has an observer with a model of the plant that utilizes the set of locally available measurements, which may not make the full plant state detectable. This lack of detectability is overcome by utilizing a consensus filter that blends the state estimate of each agent with its neighbors’ estimates. It is proven that the state estimates of the proposed observer exponentially converge to the actual plant states under arbitrarily changing, but connected, communication and pseudo-connected sensing graph topologies. Except these connectivity properties, full knowledge of the sensing and communication graphs is not needed at the design time. As a byproduct, we obtained a result on the location of eigenvalues, i.e., the spectrum, of the Laplacian for a family of graphs with self-loops.     

Optimal Signaling Policies for Decentralized Multicontroller Stabilizability Over Communication Channels

In this note, we study the problem of distributed control over communication channels, where a number of distributed stations collaborate to stabilize a linear system. We quantify the rate requirements and obtain optimal signaling, coding and control schemes for decentralized stabilizability in such multicontroller systems. We show that in the absence of a centralized decoder at the plant, there is in general a rate loss in decentralized systems as compared to a centralized system. This result is in contrast with the absence of rate loss in the stabilization of multisensor systems. Furthermore, there is rate loss even if explicit channels are available between the stations. We obtain the minimum data rates needed in terms of the open-loop system matrix and the connectivity graph of the decentralized system, and obtain the optimal signaling policies. We also present constructions leading to stability. In addition, we show that if there are dedicated channels connecting the controllers, rate requirements become more lenient, and as a result strong connectivity is not required for decentralized stabilizability. We determine the minimum number of such external channels leading to a stable system, in case strong connectivity is absent.     

Decentralized Bayesian Search Using Approximate Dynamic Programming Methods

We consider decentralized Bayesian search problems that involve a team of multiple autonomous agents searching for targets on a network of search points operating under the following constraints: 1) interagent communication is limited; 2) the agents do not have the opportunity to agree in advance on how to resolve equivalent but incompatible strategies; and 3) each agent lacks the ability to control or predict with certainty the actions of the other agents. We formulate the multiagent search-path-planning problem as a decentralized optimal control problem and introduce approximate dynamic heuristics that can be implemented in a decentralized fashion. After establishing some analytical properties of the heuristics, we present computational results for a search problem involving two agents on a 5 times 5 grid.     

Multi-Agent Dynamic Area Coverage Based on Reinforcement Learning with Connected Agents

Dynamic area coverage with small unmanned aerial vehicle (UAV) systems is one of the major research topics due to limited payloads and the difficulty of decentralized decision-making process. Collaborative behavior of a group of UAVs in an unknown environment is another hard problem to be solved. In this paper, we propose a method for decentralized execution of multi-UAVs for dynamic area coverage problems. The proposed decentralized decision-making dynamic area coverage (DDMDAC) method utilizes reinforcement learning (RL) where each UAV is represented by an intelligent agent that learns policies to create collaborative behaviors in partially observable environment. Intelligent agents increase their global observations by gathering information about the environment by connecting with other agents. The connectivity provides a consensus for the decision-making process, while each agent takes decisions. At each step, agents acquire all reachable agents’ states, determine the optimum location for maximal area coverage and receive reward using the covered rate on the target area, respectively. The method was tested in a multi-agent actor-critic simulation platform. In the study, it has been considered that each UAV has a certain communication distance as in real applications. The results show that UAVs with limited communication distance can act jointly in the target area and can successfully cover the area without guidance from the central command unit.     

Motion planning for cooperative unicycle-type mobile robots with limited sensing ranges: A distributed receding horizon approach

This paper presents a decentralized motion planner for a team of nonholonomic mobile robots subject to constraints imposed by sensors and the communication network. The motion planning scheme consists of decentralized receding horizon planners that reside on each vehicle to achieve coordination among flocking agents. The advantage of the proposed algorithm is that each vehicle only requires local knowledge of its neighboring vehicles. The main requirement for designing an optimal conflict-free trajectory in a decentralized way is that each robot does not deviate too far from its presumed trajectory designed without taking the coupling constraints into account. A comparative study between the proposed algorithm and other existing algorithms is provided in order to show the advantages, especially in terms of computing time. Finally, experiments are performed on a team of three mobile robots to demonstrate the validity of the proposed approach.     

基于多节点社团意识系统的属性图聚类算法

属性图用属性向量描述节点,用边描述节点间的关系。为了把节点划分为具有紧密联系的社团,一种有效的方法是对属性图进行聚类。聚类方法有不同的标准,如节点连接度和属性相似度。虽然社团一般是围绕紧密的连边和相似的属性值的节点形成,但是目前的方法都只关注了这两种数据形式中的一种。通过给每个节点赋予一个自治域,提出一个准确且可延展的多节点系统用于提取属性图中的重叠社团。首先,引入带有可调带宽因子的核函数用于测度每个节点的影响力,具有最高局部影响力的节点可以被看作领导节点。其次,提出一种新颖的局部扩展策略,使每一个领导节点能够吸收属性图中相关性最强的跟随者。接着,设计了多节点社团意识系统,该系统为节点之间的充分沟通提供了必要的条件,从而能够得出最优的重叠社团结构。社团中的节点不仅互相联系紧密,而且也有相似的属性。该算法的计算复杂度在特定带宽条件下近似于连边数目的线性函数。最后,基于标准属性图和真实属性图的实验验证了该系统的有效性和高效性。     

Formation Reorganization by Primitive Operations on Directed Graphs

In this paper, we study the construction and transformation of 2-D persistent graphs. Persistence is a generalization to directed graphs of the undirected notion of rigidity. Both notions are currently being used in various studies on coordination and control of autonomous multiagent formations. In the context of mobile autonomous agent formations, persistence characterizes the efficacy of a directed formation structure with unilateral distance constraints seeking to preserve the shape of the formation. Analogously to the powerful results about Henneberg sequences in minimal rigidity theory, we propose different types of directed graph operations allowing one to sequentially build any minimally persistent graph (i.e., persistent graph with a minimal number of edges for a given number of vertices), each intermediate graph being also minimally persistent. We also consider the more generic problem of obtaining one minimally persistent graph from another, which corresponds to the online reorganization of the sensing and control architecture of an autonomous agent formation. We prove that we can obtain any minimally persistent formation from any other one by a sequence of elementary local operations such that minimal persistence is preserved throughout the reorganization process. Finally, we briefly explore how such transformations can be performed in a decentralized way.     

Potential Fields for Maintaining Connectivity of Mobile Networks

The control of mobile networks of multiple agents raises fundamental and novel problems in controlling the structure of the resulting dynamic graphs. In this paper, we consider the problem of controlling a network of agents so that the resulting motion always preserves the connectivity property of the network. In particular, the connectivity condition is translated to differentiable constraints on individual agent motion by considering the dynamics of the Laplacian matrix and its spectral properties. Artificial potential fields are then used to drive the agents to configurations away from the undesired space of disconnected networks while avoiding collisions with each other. We conclude by illustrating a class of interesting problems that can be achieved while preserving connectivity constraints.     

A New Consensus Algorithm for Multi-Agent Systems via Decentralized Dynamic Output Feedback

In this paper, we study a consensus problem for multi-agent systems via dynamic output feedback control. The entire system is decentralized in the sense that each agent can only obtain output information from its neighbor agents. For practical purpose, we assume that actuator limitation exists, and require that the consensus be achieved among the agents at a specified convergence rate. By using an appropriate coordinate transformation, we reduce the consensus problem on hand to solving a strict matrix inequality, and then propose to use the homotopy based method for solving the matrix inequality. It turns out that our algorithm includes the existing graph Laplacian based algorithm as a special case.     

An Optimal Approach to Collaborative Target Tracking with Performance Guarantees

In this paper, we present a discrete-time optimization framework for target tracking with multi-agent systems. The “target tracking” problem is formulated as a generic semidefinite program (SDP) that when paired with an appropriate objective yields an optimal robot configuration over a given time step. The framework affords impressive performance guarantees to include full target coverage (i.e. each target is tracked by at least a single team member) as well as maintenance of network connectivity across the formation. Key to this work is the result from spectral graph theory that states the second-smallest eigenvalue—λ ₂—of a weighted graph’s Laplacian (i.e. its inter-connectivity matrix) is a measure of connectivity for the associated graph. Our approach allows us to articulate agent-target coverage and inter-agent communication constraints as linear-matrix inequalities (LMIs). Additionally, we present two key extensions to the framework by considering alternate tracking problem formulations. The first allows us to guarantee k-coverage of targets, where each target is tracked by k or more agents. In the second, we consider a relaxed formulation for the case when network connectivity constraints are superfluous. The problem is modeled as a second-order cone program (SOCP) that can be solved significantly more efficiently than its SDP counterpart—making it suitable for large-scale teams (e.g. 100’s of nodes in real-time). Methods for enforcing inter-agent proximity constraints for collision avoidance are also presented as well as simulation results for multi-agent systems tracking mobile targets in both ?² and ?³.     

On the Rendezvous Problem for Multiple Nonholonomic Agents

In this note, a decentralized feedback control strategy that drives a system of multiple nonholonomic unicycles to a rendezvous point in terms of both position and orientation is introduced. The proposed nonholonomic control law is discontinuous and time-invariant and using tools from nonsmooth Lyapunov theory and graph theory the stability of the overall system is examined. Similarly to the linear case, the convergence of the multi-agent system relies on the connectivity of the communication graph that represents the inter-agent communication topology. The control law is first defined in order to guarantee connectivity maintenance for an initially connected communication graph. Moreover, the cases of static and dynamic communication topologies are treated as corollaries of the proposed framework     

Formation stabilization and resizing based on the control of inter‐agent distances

We propose a control strategy that could steer the group of mobile agents in the plane to achieve a specified formation. The control law could be implemented in a fully decentralized manner so that each agent moves on their own local reference frame. Under the acyclic minimally persistent graph topology, each agent measures the relative displacements of neighboring agents and then adjusts the distances between them to achieve the desired formation. As well as achieving a fixed formation, we could resize the formation only by changing the leader edge, which connects the leader with the first‐follower in acyclic minimally persistent graph, without changing the structures of the control law. Copyright © 2014 John Wiley & Sons, Ltd.     

Multi-agent system motion planning under temporal logic specifications and control barrier function

In this paper, we provide a novel scheme to solve the motion planning problem of multi-agent systems under high-level task specifications. First, linear temporal logic is applied to express the global task specification. Then an efficient and decentralized algorithm is proposed to decompose it into local tasks. Moreover, we use control barrier function to synthesize the local controller for each agent under the linear temporal logic motion plan with safety constraint. Finally, simulation results show the effectiveness and efficiency of our proposed scheme.     

A connectivity-preserving flocking algorithm for multi-agent systems based only on position measurements

Most existing flocking algorithms rely on information about both relative position and relative velocity among neighbouring agents. In this article, we investigate the flocking problem with only position measurements. We propose a provably-stable flocking algorithm, in which an output vector is produced by distributed filters based on position information alone but not velocity information. Under the assumption that the initial interactive network is connected, the flocking algorithm not only can steer a group of agents to a stable flocking motion, but also can preserve the connectivity of the interactive network during the dynamical evolution. Moreover, we investigate the flocking algorithm with a virtual leader and show that all agents can asymptotically attain a desired velocity even if only one agent in the team has access to the information of the virtual leader. We finally show some numerical simulations to illustrate the theoretical results.     

An internal model approach to autonomous leader/follower trailing for non‐holonomic vehicles

The focus of this paper is on the design of a control architecture of decentralized type for controlling a leader/follower pair of autonomous non‐holonomic vehicles. A fundamental constraint in this trailing control requires that each agent employs local sensor information to process data on the relative position and velocity between its neighbouring vehicles, without relying on global communication with mission control. This constraint poses a challenge in the design of the control system because the reference trajectory to be tracked, which in the case considered in this paper is related to the motion of the leader, is not known a priori. It is shown in the paper that this specific control problem can be approached from the point of view of the internal model paradigm. In particular, once models of the autonomous dynamics of the leader are embedded in a decentralized dynamic controller, the design of the controller can be completed with a robust stabilizer, obtained by using ISS‐gain‐assignment techniques. It is shown that asymptotic convergence of the follower to an arbitrarily small neighbourhood of the desired steady‐state configuration is achieved, despite the presence of possibly large parameter uncertainties, while the motion of each agent remains confined into specified ‘sectors’ to avoid possible collision between neighbouring vehicles during transients. Simulation results are presented to illustrate the design methodology. Copyright © 2006 John Wiley & Sons, Ltd.