Xudong Chen

Ce Zheng, Xudong Chen, Runxin Xu et al.

Frame semantic parsing is a fundamental NLP task, which consists of three subtasks: frame identification, argument identification and role classification. Most previous studies tend to neglect relations between different subtasks and arguments and pay little attention to ontological frame knowledge defined in FrameNet. In this paper, we propose a Knowledge-guided Incremental semantic parser with Double-graph (KID). We first introduce Frame Knowledge Graph (FKG), a heterogeneous graph containing both frames and FEs (Frame Elements) built on the frame knowledge so that we can derive knowledge-enhanced representations for frames and FEs. Besides, we propose Frame Semantic Graph (FSG) to represent frame semantic structures extracted from the text with graph structures. In this way, we can transform frame semantic parsing into an incremental graph construction problem to strengthen interactions between subtasks and relations between arguments. Our experiments show that KID outperforms the previous state-of-the-art method by up to 1.7 F1-score on two FrameNet datasets. Our code is availavle at https://github.com/PKUnlp-icler/KID.

Xudong Chen, M. -A. Belabbas, Tamer Basar

We consider the problem of estimating the states of weakly coupled linear systems from sampled measurements. We assume that the total capacity available to the sensors to transmit their samples to a network manager in charge of the estimation is bounded above, and that each sample requires the same amount of communication. Our goal is then to find an optimal allocation of the capacity to the sensors so that the average estimation error is minimized. We show that when the total available channel capacity is large, this resource allocation problem can be recast as a strictly convex optimization problem, and hence there exists a unique optimal allocation of the capacity. We further investigate how this optimal allocation varies as the available capacity increases. In particular, we show that if the coupling among the subsystems is weak, then the sampling rate allocated to each sensor is nondecreasing in the total sampling rate, and is strictly increasing if and only if the total sampling rate exceeds a certain threshold.

Jingyu Song, Xudong Chen, Liupei Lu et al.

High-definition (HD) maps provide environmental information for autonomous driving systems and are essential for safe planning. While existing methods with single-frame input achieve impressive performance for online vectorized HD map construction, they still struggle with complex scenarios and occlusions. We propose MemFusionMap, a novel temporal fusion model with enhanced temporal reasoning capabilities for online HD map construction. Specifically, we contribute a working memory fusion module that improves the model's memory capacity to reason across a history of frames. We also design a novel temporal overlap heatmap to explicitly inform the model about the temporal overlap information and vehicle trajectory in the Bird's Eye View space. By integrating these two designs, MemFusionMap significantly outperforms existing methods while also maintaining a versatile design for scalability. We conduct extensive evaluation on open-source benchmarks and demonstrate a maximum improvement of 5.4% in mAP over state-of-the-art methods. The project page for MemFusionMap is https://song-jingyu.github.io/MemFusionMap

Xudong Chen

Gradient descent methods have been widely used for organizing multi-agent systems, in which they can provide decentralized control laws with provable convergence. Often, the control laws are designed so that two neighboring agents repel/attract each other at a short/long distance of separation. When the interactions between neighboring agents are moreover nonfading, the potential function from which they are derived is radially unbounded. Hence, the LaSalle's principle is sufficient to establish the system convergence. This paper investigates, in contrast, a more realistic scenario where interactions between neighboring agents have fading attractions. In such setting, the LaSalle type arguments may not be sufficient. To tackle the problem, we introduce a class of partitions, termed dilute partitions, of formations which cluster agents according to the inter- and intra-cluster interaction strengths. We then apply dilute partitions to trajectories of formations generated by the multi-agent system, and show that each of the trajectories remains bounded along the evolution, and converges to the set of equilibria.

Stephen G. Dale, Nikita Kazeev, Alastair J. A. Price et al.

Artificial intelligence and machine learning are reshaping how we approach scientific discovery, not by replacing established methods but by extending what researchers can probe, predict, and design. In this roadmap we provide a forward-looking view of AI-enabled science across biology, chemistry, climate science, mathematics, materials science, physics, self-driving laboratories and unconventional computing. Several shared themes emerge: the need for diverse and trustworthy data, transferable electronic-structure and interatomic models, AI systems integrated into end-to-end scientific workflows that connect simulations to experiments and generative systems grounded in synthesisability rather than purely idealised phases. Across domains, we highlight how large foundation models, active learning and self-driving laboratories can close loops between prediction and validation while maintaining reproducibility and physical interpretability. Taken together, these perspectives outline where AI-enabled science stands today, identify bottlenecks in data, methods and infrastructure, and chart concrete directions for building AI systems that are not only more powerful but also more transparent and capable of accelerating discovery in complex real-world environments.

Xudong Chen, Yixin Liu, Hua Wei et al.

Large language models (LLMs) have become a strong foundation for multi-agent systems, but their effectiveness depends heavily on orchestration design. Across different tasks, role design, capacity assignment, and dependency construction jointly affect both solution quality and execution efficiency. Existing approaches automate parts of this design process, yet they often optimize these decisions partially or sequentially, and rely on execution-level feedback that provides limited credit assignment for local orchestration decisions. We propose LEMON (\textbf{L}earning \textbf{E}xecutable \textbf{M}ulti-agent \textbf{O}rchestratio\textbf{N} via Counterfactual Reinforcement Learning), an LLM-based orchestrator that generates an executable orchestration specification. The specification integrates task-specific roles, customized duties, capacity levels, and dependency structure into a single deployable system. To train the orchestrator, we augment the orchestration-level GRPO objective with a localized counterfactual signal that edits role, capacity, or dependency fields and applies the resulting reward contrast only to the edited spans. Experiments on six reasoning and coding benchmarks, including MMLU, GSM8K, AQuA, MultiArith, SVAMP, and HumanEval, show that LEMON achieves state-of-the-art performance among the evaluated multi-agent orchestration methods. Our code is available at https://anonymous.4open.science/r/LEMON-B23C.

Xudong Chen

We introduce in the paper a novel observability problem for a continuum ensemble of nonholonomic control systems with unknown population density. We address the problem by focussing on a prototype of such ensemble system, namely, the ensemble of Bloch equations. The dynamics of the equations are structurally identical, but show variations in Larmor dispersion and radio frequency (rf) inhomogeneity. We assume that the initial state of every individual system is unknown and, moreover, the population density of these individual systems is also unknown. Furthermore, we assume that at any time, there is only one scalar measurement output at our disposal. The measurement output integrates a certain observation function, common to all individual systems, over the continuum ensemble. The observability problem we pose in the paper is thus the following: Whether one is able to use the common control input (i.e., the rf field) and the single measurement output to estimate the initial states of the individual systems and, moreover, to identify the population density? Amongst other things, we establish a sufficient condition for the ensemble system to be observable: We show that if the common observation function is any harmonic homogeneous polynomial of positive degree, then the ensemble system is observable. The main focus of the paper is to demonstrate how to leverage tools from representation theory of Lie algebras to address the observability problem. Although the results we establish in the paper are for the specific ensemble of Bloch equations, the approach we develop along the analysis can be generalized to investigate observability of other general ensembles of nonholonomic control systems with a single, integrated measurement output.

Muhammad U. Javed, Jorge I. Poveda, Xudong Chen

In this paper, we study the problem of robust global synchronization of resetting clocks in multi-agent networked systems, where by robust global synchronization we mean synchronization that is insensitive to arbitrarily small disturbances, and which is achieved from all initial conditions. In particular, we aim to address the following question: Given a set of homogeneous agents with periodic clocks sharing the same parameters, what kind of information flow topologies will guarantee that the resulting networked systems can achieve robust global synchronization? To address this question, we rely on the framework of robust hybrid dynamical systems and a class of distributed hybrid resetting algorithms. Using the hybrid-system approach, we provide a partial solution to the question: Specifically, we show that one can achieve robust global synchronization with no purely discrete-time solutions in any networked system whose underlying information flow topology is a rooted acyclic digraph. Such a result is complementary to the existing result [1] in which strongly connected digraphs are considered as the underlying information flow topologies of the networked systems. We have further computed in the paper the convergence time for a networked system to reach global synchronization. In particular, the computation reveals the relationship between convergence time and the structure of the underlying digraph. We illustrate our theoretical findings via numerical simulations towards the end of the paper.

Xudong Chen

We propose in the paper a novel framework for using a common control input to simultaneously steer an infinite ensemble of networked control systems. We address the problem of co-designing information flow topology and network dynamics of every individual networked system so that a continuum ensemble of such systems is controllable. To keep the analysis tractable, we focus in the paper on a special class of ensembles systems, namely ensembles of multi-agent formation systems. Specifically, we consider an ensemble of formation systems indexed by a parameter in a compact, real analytic manifold. Every individual formation system in the ensemble is composed of $N$ agents. These agents evolve in $\mathbb{R}^n$ and can access relative positions of their neighbors. The information flow topology within every individual formation system is, by convention, described by a directed graph where the vertices correspond to the $N$ agents and the directed edges indicate the information flow. For simplicity, we assume in the paper that all the individual formation systems share the same information flow topology described by a common digraph $G$. Amongst other things, we establish a sufficient condition for approximate path-controllability of the continuum ensemble of formation systems. We show that if the digraph $G$ is strongly connected and the number $N$ of agents in each individual system is great than $(n + 1)$, then every such system in the ensemble is simultaneously approximately path-controllable over a path-connected, open dense subset.

Xudong Chen

We investigate the joint actuator-sensor design problem for stochastic linear control systems. Specifically, we address the problem of identifying a pair of sensor and actuator which gives rise to the minimum expected value of a quadratic cost. It is well known that for the linear-quadratic-Gaussian (LQG) control problem, the optimal feedback control law can be obtained via the celebrated separation principle. Moreover, if the system is stabilizable and detectable, then the infinite-horizon time-averaged cost exists. But such a cost depends on the placements of the sensor and the actuator. We formulate in the paper the optimization problem about minimizing the time-averaged cost over admissible pairs of actuator and sensor under the constraint that their Euclidean norms are fixed. The problem is non-convex and is in general difficult to solve. We obtain in the paper a gradient descent algorithm (over the set of admissible pairs) which minimizes the time-averaged cost. Moreover, we show that the algorithm can lead to a unique local (and hence global) minimum point under certain special conditions.

Xin Zhao, Xiaojun Chen, Xudong Chen et al.

Diffusion Models (DMs) achieve state-of-the-art synthesis results in image generation and have been applied to various fields. However, DMs sometimes seriously violate user privacy during usage, making the protection of privacy an urgent issue. Using traditional privacy computing schemes like Secure Multi-Party Computation (MPC) directly in DMs faces significant computation and communication challenges. To address these issues, we propose CipherDM, the first novel, versatile and universal framework applying MPC technology to DMs for secure sampling, which can be widely implemented on multiple DM based tasks. We thoroughly analyze sampling latency breakdown, find time-consuming parts and design corresponding secure MPC protocols for computing nonlinear activations including SoftMax, SiLU and Mish. CipherDM is evaluated on popular architectures (DDPM, DDIM) using MNIST dataset and on SD deployed by diffusers. Compared to direct implementation on SPU, our approach improves running time by approximately 1.084\times \sim 2.328\times, and reduces communication costs by approximately 1.212\times \sim 1.791\times.

Qile Zhao, Xianhong Zhao, Xu Ma et al.

Coded aperture snapshot spectral imaging (CASSI) is a technique used to reconstruct three-dimensional hyperspectral images (HSIs) from one or several two-dimensional projection measurements. However, fewer projection measurements or more spectral channels leads to a severly ill-posed problem, in which case regularization methods have to be applied. In order to significantly improve the accuracy of reconstruction, this paper proposes a fast alternating minimization algorithm based on the sparsity and deep image priors (Fama-SDIP) of natural images. By integrating deep image prior (DIP) into the principle of compressive sensing (CS) reconstruction, the proposed algorithm can achieve state-of-the-art results without any training dataset. Extensive experiments show that Fama-SDIP method significantly outperforms prevailing leading methods on simulation and real HSI datasets.

Qinghui Zhang, Xiaojun Chen, Yansong Zhang et al.

Most existing secure neural network inference protocols based on secure multi-party computation (MPC) typically support at most four participants, demonstrating severely limited scalability. Liu et al. (USENIX Security'24) presented the first relatively practical approach by utilizing Shamir secret sharing with Mersenne prime fields. However, when processing deeper neural networks such as VGG16, their protocols incur substantial communication overhead, resulting in particularly significant latency in wide-area network (WAN) environments. In this paper, we propose a high-throughput and scalable MPC protocol for neural network inference against semi-honest adversaries in the honest-majority setting. The core of our approach lies in leveraging packed Shamir secret sharing (PSS) to enable parallel computation and reduce communication complexity. The main contributions are three-fold: i) We present a communication-efficient protocol for vector-matrix multiplication, based on our newly defined notion of vector-matrix multiplication-friendly random share tuples. ii) We design the filter packing approach that enables parallel convolution. iii) We further extend all non-linear protocols based on Shamir secret sharing to the PSS-based protocols for achieving parallel non-linear operations. Extensive experiments across various datasets and neural networks demonstrate the superiority of our approach in WAN. Compared to Liu et al. (USENIX Security'24), our scheme reduces the communication upto 5.85x, 11.17x, and 6.83x in offline, online and total communication overhead, respectively. In addition, our scheme is upto 1.59x, 2.61x, and 1.75x faster in offline, online and total running time, respectively.

Haoyu Yin, Yi Li, Ouyang Du et al.

This paper introduces and solves a structural controllability problem for ensembles of switched linear systems. All individual systems in the ensemble are sparse and governed by the same sparsity pattern, and undergo switching among subsystems by following the same switching sequence. The controllability of an ensemble system describes the ability to use a common control input to simultaneously steer every individual system. A sparsity pattern is called structurally controllable for pair \((k,q)\) if it admits a controllable ensemble of \(q\) individual systems with at most \(k\) subsystems. We derive a necessary and sufficient condition for a sparsity pattern to be structurally controllable for a given \((k,q)\), and characterize when a sparsity pattern admits a finite \(k\) that guarantees structural controllability for \((k,q)\) for arbitrary $q$. Compared with the linear time-invariant ensemble case, this second condition is strictly weaker. We further show that these conditions have natural connections with maximum flow, and hence can be checked by polynomial algorithms. Specifically, the time complexity of deciding structural controllability is \(O(n^3)\) and the complexity of computing the smallest number of subsystems needed is \(O(n^3 \log n)\), with \(n\) the dimension of each individual system.

Haoyu Yin, Xudong Chen, Bruno Sinopoli

In this paper, we study four-strategy conservative replicator dynamics induced by constant payoff matrices. We establish necessary and sufficient conditions for permanence to occur by associating the payoff matrix with its digraph, revealing exactly five distinct digraph classes governing the global behavior. We further show that, whenever the dynamics is permanent, every non-equilibrium trajectory in the relative interior of the simplex is a Lyapunov-stable periodic orbit. Together with the classification of the boundary phase portraits, these results provide a complete characterization of the global dynamics in the four-strategy case with permanence.

Deyi Ji, Yuekui Yang, Liqun Liu et al.

Advertising (Ad) is a cornerstone of the digital economy, yet the moderation of video advertisements remains a significant challenge due to their complexity and the need for precise violation localization. While recent advancements, such as the RAVEN model, have improved coarse-grained violation detection, critical gaps persist in fine-grained understanding, explainability, and generalization. To address these limitations, we propose RAVEN++, a novel framework that introduces three key innovations: 1) Active Reinforcement Learning (RL), which dynamically adapts training to samples of varying difficulty; 2) Fine-Grained Violation Understanding, achieved through hierarchical reward functions and reasoning distillation; and 3) Progressive Multi-Stage Training, which systematically combines knowledge injection, curriculum-based passive RL, and active RL. Extensive experiments on both public and proprietary datasets, on both offline scenarios and online deployed A/B Testing, demonstrate that RAVEN++ outperforms general-purpose LLMs and specialized models like RAVEN in terms of fine-grained violation understanding, reasoning capabilities, and generalization ability.

Haitao Liu, Changjun Liu, Xiaomo Jiang et al.

The demand of probabilistic time series forecasting has been recently raised in various dynamic system scenarios, for example, system identification and prognostic and health management of machines. To this end, we combine the advances in both deep generative models and state space model (SSM) to come up with a novel, data-driven deep probabilistic sequence model. Specifically, we follow the popular encoder-decoder generative structure to build the recurrent neural networks (RNN) assisted variational sequence model on an augmented recurrent input space, which could induce rich stochastic sequence dependency. Besides, in order to alleviate the inconsistency issue of the posterior between training and predicting as well as improving the mining of dynamic patterns, we (i) propose using a lagged hybrid output as input for the posterior at next time step, which brings training and predicting into alignment; and (ii) further devise a generalized auto-regressive strategy that encodes all the historical dependencies for the posterior. Thereafter, we first investigate the methodological characteristics of the proposed deep probabilistic sequence model on toy cases, and then comprehensively demonstrate the superiority of our model against existing deep probabilistic SSM models through extensive numerical experiments on eight system identification benchmarks from various dynamic systems. Finally, we apply our sequence model to a real-world centrifugal compressor forecasting problem, and again verify its outstanding performance by quantifying the time series predictive distribution.

Xudong Chen, Shugong Xu, Qiaobin Ji et al.

Face Anti-spoofing (FAS) is a challenging problem due to complex serving scenarios and diverse face presentation attack patterns. Especially when captured images are low-resolution, blurry, and coming from different domains, the performance of FAS will degrade significantly. The existing multi-modal FAS datasets rarely pay attention to the cross-domain problems under deployment scenarios, which is not conducive to the study of model performance. To solve these problems, we explore the fine-grained differences between multi-modal cameras and construct a cross-domain multi-modal FAS dataset under surveillance scenarios called GREAT-FASD-S. Besides, we propose an Attention based Face Anti-spoofing network with Feature Augment (AFA) to solve the FAS towards low-quality face images. It consists of the depthwise separable attention module (DAM) and the multi-modal based feature augment module (MFAM). Our model can achieve state-of-the-art performance on the CASIA-SURF dataset and our proposed GREAT-FASD-S dataset.

Xiaoyu Chen, Shugong Xu, Xudong Chen et al.

Transmission control protocol (TCP) congestion control is one of the key techniques to improve network performance. TCP congestion control algorithm identification (TCP identification) can be used to significantly improve network efficiency. Existing TCP identification methods can only be applied to limited number of TCP congestion control algorithms and focus on wired networks. In this paper, we proposed a machine learning based passive TCP identification method for wired and wireless networks. After comparing among three typical machine learning models, we concluded that the 4-layers Long Short Term Memory (LSTM) model achieves the best identification accuracy. Our approach achieves better than 98% accuracy in wired and wireless networks and works for newly proposed TCP congestion control algorithms.

Zhixin Zhang, Xudong Chen, Jie Liu et al.

General detectors follow the pipeline that feature maps extracted from ConvNets are shared between classification and regression tasks. However, there exists obvious conflicting requirements in multi-orientation object detection that classification is insensitive to orientations, while regression is quite sensitive. To address this issue, we provide an Encoder-Decoder architecture, called Rotated Feature Network (RFN), which produces rotation-sensitive feature maps (RS) for regression and rotation-invariant feature maps (RI) for classification. Specifically, the Encoder unit assigns weights for rotated feature maps. The Decoder unit extracts RS and RI by performing resuming operator on rotated and reweighed feature maps, respectively. To make the rotation-invariant characteristics more reliable, we adopt a metric to quantitatively evaluate the rotation-invariance by adding a constrain item in the loss, yielding a promising detection performance. Compared with the state-of-the-art methods, our method can achieve significant improvement on NWPU VHR-10 and RSOD datasets. We further evaluate the RFN on the scene classification in remote sensing images and object detection in natural images, demonstrating its good generalization ability. The proposed RFN can be integrated into an existing framework, leading to great performance with only a slight increase in model complexity.

Xudong Chen

Ensemble control deals with the problem of using a finite number of control inputs to simultaneously steer a large population (in the limit, a continuum) of control systems. Dual to the ensemble control problem, ensemble estimation deals with the problem of using a finite number of measurement outputs to estimate the initial condition of every individual system in the ensemble. We introduce in the paper an innovative class of ensemble systems, termed distinguished ensemble systems, and establish sufficient conditions for controllability and observability of such systems. Every distinguished ensemble system has two key components, namely distinguished control vector fields and codistinguished observation functions. Roughly speaking, a set of vector fields is distinguished if it is closed (up to scaling) under Lie bracket, and moreover, every vector field in the set can be obtained by a Lie bracket of two vector fields in the same set. Similarly, a set of functions is codistinguished to a set of vector fields if the Lie derivatives of the functions along the given vector fields yield (up to scaling) the same set of functions. We demonstrate in the paper that the structure of a distinguished ensemble system can significantly simplify the analysis of ensemble controllability and observability, and can be used as a principle for ensemble system design. We further address in the paper the existence of a distinguished ensemble system for a given manifold. Specifically, we show that every connected, semi-simple Lie group admits a set of distinguished vector fields, together with a set of codistinguished functions. The proof is constructive, leveraging structure theory of semi-simple real Lie algebras and representation theory. Examples will be provided along the presentation illustrating key definitions and main results.

Xudong Chen

In this paper, we investigate the geometry of a general class of gradient flows with multiple local maxima. we decompose the underlying space into disjoint regions of attraction and establish the adjacency criterion. The criterion states a necessary and sufficient condition for two regions of attraction of stable equilibria to be adjacent. We then apply this criterion on a specific type of gradient flow which has as many as n! local maxima. In particular, we characterize the set of equilibria, compute the index of each critical manifold and moreover, find all pairs of adjacent neighbors. As an application of the adjacency criterion, we introduce a stochastic version of the double bracket flow and set up a Markov model to approximate the sample path behavior. The study of this specific prototype with its special structure provides insight into many other difficult problems involving simulated annealing.

Xudong Chen, M. -A. Belabbas

We consider the actuator placement problem for linear systems. Specifically, we aim to identify an actuator which requires the least amount of control energy to drive the system from an arbitrary initial condition to the origin in the worst case. Said otherwise, we investigate the minimax problem of minimizing the control energy over the worst possible initial conditions. Recall that the least amount of control energy needed to drive a linear controllable system from any initial condition on the unit sphere to the origin is upper-bounded by the inverse of the smallest eigenvalue of the associated controllability Gramian, and moreover, the upper-bound is sharp. The minimax problem can be thus viewed as the optimization problem of minimizing the upper-bound via the placement of an actuator. In spite of its simple and natural formulation, this problem is difficult to solve. In fact, properties such as the stability of the system matrix, which are not related to controllability, now play important roles. We focus in this paper on the special case where the system matrix is positive definite. Under this assumption, we are able to provide a complete solution to the optimal actuator placement problem and highlight the difficulty in solving the general problem.

Xudong Chen, Ji Liu, M. -A. Belabbas et al.

We consider in this paper a networked system of opinion dynamics in continuous time, where the agents are able to evaluate their self-appraisals in a distributed way. In the model we formulate, the underlying network topology is described by a rooted digraph. For each ordered pair of agents $(i,j)$, we assign a function of self-appraisal to agent $i$, which measures the level of importance of agent $i$ to agent $j$. Thus, by communicating only with her neighbors, each agent is able to calculate the difference between her level of importance to others and others' level of importance to her. The dynamical system of self-appraisals is then designed to drive these differences to zero. We show that for almost all initial conditions, the trajectory generated by this dynamical system asymptotically converges to an equilibrium point which is exponentially stable.

Xudong Chen

This paper, as a continuing work of [1], focus on establishing the fact that if we equip a reciprocal multi-agent (RMA) system with a triangulated Laman graph (TLG), then the associated potential function is generically an equivariant Morse function, i.e, there are only finitely many critical orbits each of which is nondegenerate. Though this assumption on the potential function of being an equivariant Morse function has been used, and in fact indispensable, in several occasions. But it is actually still an open question whether it is true for a given RMA system. Thus, in this paper we will provide a confirmative answer to the question for the class of RMA systems with TLGs. The main result, as well as the analysis of this paper, has many implications for other difficult problems.

Xudong Chen, M. -A. Belabbas, Tamer Basar

In this paper, we investigate the controllability of a class of formation control systems. Given a directed graph, we assign an agent to each of its vertices and let the edges of the graph describe the information flow in the system. We relate the strongly connected components of this graph to the reachable set of the formation control system. Moreover, we show that the formation control model is approximately path-controllable over a path-connected, open dense subset as long as the graph is weakly connected and satisfies some mild assumption on the numbers of vertices of the strongly connected components.

Xudong Chen

In this paper, we investigate a decentralized formation control algorithm for an undirected formation control model. Unlike other formation control problems where only the shape of a configuration counts, we emphasize here also its Euclidean embedding. By following this decentralized formation control law, the agents will converge to certain equilibrium of the control system. In particular, we show that there is a quadratic Lyapunov function associated with the formation control system whose unique local (global) minimum point is the target configuration. In view of the fact that there exist multiple equilibria (in fact, a continuum of equilibria) of the formation control system, and hence there are solutions of the system which converge to some equilibria other than the target configuration, we apply simulated annealing, as a heuristic method, to the formation control law to fix this problem. Simulation results show that sample paths of the modified stochastic system approach the target configuration.

Xudong Chen, M. -A. Belabbas, Tamer Basar

A consensus system is a linear multi-agent system in which agents communicate to reach a so-called consensus state, defined as the average of the initial states of the agents. Consider a more generalized situation in which each agent is given a positive weight and the consensus state is defined as the weighted average of the initial conditions. We characterize in this paper the weighted averages that can be evaluated in a decentralized way by agents communicating over a directed graph. Specifically, we introduce a linear function, called the objective map, that defines the desired final state as a function of the initial states of the agents. We then provide a complete answer to the question of whether there is a decentralized consensus dynamics over a given digraph which converges to the final state specified by an objective map. In particular, we characterize not only the set of objective maps that are feasible for a given digraph, but also the consensus dynamics that implements the objective map. In addition, we present a decentralized algorithm to design the consensus dynamics.

Xudong Chen, M. -A. Belabbas, Tamer Basar

Formation control deals with the design of decentralized control laws that stabilize agents at prescribed distances from each other. We call any configuration that satisfies the inter-agent distance conditions a target configuration. It is well known that when the distance conditions are defined via a rigid graph, there is a finite number of target configurations modulo rotations and translations. We can thus recast the objective of formation control as stabilizing one or many of the target configurations. A major issue is that such control laws will also have equilibria corresponding to configurations which do not meet the desired inter-agent distance conditions; we refer to these as undesired equilibria. The undesired equilibria become problematic if they are also stable. Designing decentralized control laws whose stable equilibria are all target configurations in the case of a general rigid graph is still an open problem. We propose here a partial solution to this problem by exhibiting a class of rigid graphs and control laws for which all stable equilibria are target configurations.