In real-time systems optimization, designers often face a challenging problem posed by the non-convex and non-continuous schedulability conditions, which may even lack an analytical form to understand their properties. To tackle this challenging problem, we treat the schedulability analysis as a black box that only returns true/false results. We propose a general and scalable framework to optimize real-time systems with continuous variables, named Numerical Optimizer with Real-Time Highlight (NORTH). NORTH is built upon the gradient-based active-set methods from the numerical optimization literature but with new methods to manage active constraints for the non-differentiable schedulability constraints. In addition, we also generalize NORTH to NORTH+ to collaboratively optimize priority assignments, a common type of discrete variables, with continuous variables based on numerical optimization algorithms. We demonstrate the algorithm performance with two example applications: energy minimization based on dynamic voltage and frequency scaling (DVFS), and optimization of control system performance. In these experiments, NORTH are 10 2 to 10 5 times faster than state-of-the-art methods while maintaining similar or better solution quality. NORTH+ outperforms NORTH by 30% with similar algorithm scalability. Both NORTH and NORTH+ support black-box schedulability analysis, ensuring broad applicability.

The Logical Execution Time (LET) programming model has recently received considerable attention, particularly because of its timing and dataflow determinism. In LET, task computation appears always to take the same amount of time (called the task's LET interval), and the task reads (resp. writes) at the beginning (resp. end) of the interval. Compared to other communication mechanisms, such as implicit communication and Dynamic Buffer Protocol (DBP), LET performs worse on many metrics, such as end-to-end latency (including reaction time and data age) and time disparity jitter. Compared with the default LET setting, the flexible LET (fLET) model shrinks the LET interval while still guaranteeing schedulability by introducing the virtual offset to defer the read operation and using the virtual deadline to move up the write operation. Therefore, fLET has the potential to significantly improve the end-to-end timing performance while keeping the benefits of deterministic behavior on timing and dataflow. To fully realize the potential of fLET, we consider the problem of optimizing the assignments of its virtual offsets and deadlines. We propose new abstractions to describe the task communication pattern and new optimization algorithms to explore the solution space efficiently. The algorithms leverage the linearizability of communication patterns and utilize symbolic operations to achieve efficient optimization while providing a theoretical guarantee. The framework supports optimizing multiple performance metrics, and guarantees bounded suboptimality when optimizing end-to-end latency. Experimental results show that our optimization algorithms improve upon the default LET and its existing extensions and significantly outperform implicit communication and DBP in terms of various metrics, such as end-to-end latency, time disparity, and its jitter.

Monitoring the health and vigor of grasslands is vital for informing management decisions to optimize rotational grazing in agriculture applications. To take advantage of forage resources and improve land productivity, we require knowledge of pastureland growth patterns that is simply unavailable at the state of the art. In this paper, we propose to deploy a team of robots to monitor the evolution of an unknown pastureland environment to fulfill the above goal. To monitor such an environment, which usually evolves slowly, we need to design a strategy for rapid assessment of the environment over large areas at a low cost. Thus, we propose an integrated pipeline comprising data synthesis, deep neural network training, and prediction along with a multi-robot deployment algorithm that monitors pasturelands intermittently. Specifically, using expert-informed agricultural data coupled with novel data synthesis in ROS Gazebo, we first propose a new neural network architecture to learn the spatiotemporal dynamics of the environment. Such predictions help us to understand pastureland growth patterns on large scales and make appropriate monitoring decisions for the future. Based on our predictions, we then design an intermittent multi-robot deployment policy for low-cost monitoring. Finally, we compare the proposed pipeline with other methods, from data synthesis to prediction and planning, to corroborate our pipeline’s performance. Note to Practitioners—Pasturelands are an integral part of agricultural production in the United States. To take full advantage of the forage resource and avoid environmental degradation, pastureland must be managed optimally. This paper focuses on the question of how to deploy robot teams to sense and model physical processes over varying timescales. The goal of this work is to develop a new integrated pipeline for the long-term deployment of heterogeneous robot teams grounded in the problem of autonomous monitoring in precision grazing to improve land productivity. By using the proposed pipeline in grassland ecosystem management, we will have a better understanding of the physical environment while respecting energy budgets.

Modern real-time systems often involve numerous computational tasks characterized by intricate dependency relationships. Within these systems, data propagate through cause–effect chains from one task to another, making it imperative to minimize end-to-end latency to ensure system safety and reliability. In this article, we introduce innovative nonpreemptive scheduling techniques designed to reduce the worst-case end-to-end latency and/or time disparity for task sets modeled with directed acyclic graphs (DAGs). This is challenging because of the noncontinuous and nonconvex characteristics of the objective functions, hindering the direct application of standard optimization frameworks. Customized optimization frameworks aiming at achieving optimal solutions may suffer from scalability issues, while general heuristic algorithms often lack theoretical performance guarantees. To address this challenge, we incorporate the “1-opt” concept from the optimization literature (Essentially, 1-opt means that the quality of a solution cannot be improved if only one single variable can be changed) into the design of our algorithm. We propose a novel optimization algorithm that effectively balances the tradeoff between theoretical guarantees and algorithm scalability. By demonstrating its theoretical performance guarantees, we establish that the algorithm produces 1-opt solutions while maintaining polynomial run-time complexity. Through extensive large-scale experiments, we demonstrate that our algorithm can effectively reduce the latency metrics by 20% to 40%, compared to state-of-the-art methods.

In the optimization of real-time systems, designers often face a challenging problem where the schedulability conditions are non-convex, non-continuous, or lack an analytical form to understand their properties. In this paper, we propose a general and scalable framework for optimizing real-time systems, named Numerical optimizer with Real-Time Highlight (NORTH). NORTH treats schedulability analysis as a blackbox which may only return true/false results on system schedulability. Built upon the active-set methods from the gradient-based numerical optimization literature, NORTH proposes new methods to manage active constraints to further improve the gradient-based optimizers. We apply the proposed approach to two example problems, one on energy optimization for systems with dynamic voltage and frequency scaling, and the other on the optimization of control performance. Experimental results demonstrate that the proposed framework runs 102to 105times faster than state-of-the-art methods while maintaining similar solution quality.

Equipping real-time systems with soft error resilience can be challenging due to the tradeoff of the timing and failure requirements for mixed-criticality tasks. Violation of these requirements yields failed task scheduling in one way or another. However, not every task requires the same degree of soft error resilience. For example, low-criticality tasks can run with low or even no soft error resilience, whereas mid- or highcriticality tasks may require relatively high resilience depending on their inherent failure requirement. Unfortunately, existing soft error resilience schemes do not have the ability to control the degree of their resilience in a fine-grained way, i.e., they can only be turned on or off as a whole during task execution. To this end, this paper presents RTailor (Resilience Tailor), a compiler-directed parameterized soft error resilience scheme that achieves the desired level of soft error protection according to the demand of each task. The key idea is that for a given protection ratio, compilers can transform a hot loop such that the number of its iterations protected over the total iterations matches the ratio. Compared to full resilience protecting every iteration, RTailor's parameterized soft error resilience significantly reduces the performance overhead of tasks, thereby improving their real-time schedulability. The experimental results highlight that for four representative fault rates, RTailor achieves 15%~average schedulability improvements over the state-of-the-art work that lacks parameterized soft error resilience.

This article addresses a fundamental question of multiagent knowledge distribution: what information should be sent to whom and when with the limited resources available to each agent? Communication requirements for multiagent systems can be rather high when an accurate picture of the environment and the state of other agents must be maintained. To reduce the impact of multiagent coordination on networked systems, for example, power and bandwidth, this article introduces two concepts for the partially observable Markov decision processes (POMDPs): 1) action-based constraints that yield constrained-action POMDPs (CA-POMDPs) and 2) soft probabilistic constraint satisfaction for the resulting infinite-horizon controllers. To enable constraint analysis over an infinite horizon, an unconstrained policy is first represented as a finite-state controller (FSC) and optimized with policy iteration. The FSC representation then allows for a combination of the Markov chain Monte Carlo and discrete optimization to improve the probabilistic constraint satisfaction of the controller while minimizing the impact on the value function. Within the CA-POMDP framework, we then propose intelligent knowledge distribution (IKD) which yields per-agent policies for distributing knowledge between agents subject to interaction constraints. Finally, the CA-POMDP and IKD concepts are validated using an asset tracking problem where multiple unmanned aerial vehicles (UAVs) with heterogeneous sensors collaborate to localize a ground asset to assist in avoiding unseen obstacles in a disaster area. The IKD model was able to maintain asset tracking through multiagent communications while only violating soft power and bandwidth constraints 3% of the time, while greedy and naive approaches violated constraints more than 60% of the time.

In this article, we address the problem of coordinating the motion of a team of robots with limited field of view (FOV), which inducesasymmetryin their interactions. In this context, we first propose a general coordinated motion framework for multirobot systems with triangular FOV capable of guaranteeing stability under asymmetric (directed) interactions. In deriving this framework, we illustrate that asymmetry in multirobot interactions can lead to degenerate configurations for which a fully decentralized controller may be insufficient to achieve coordination. Thus, we introduce a switching control mechanism that achievesadaptive decentralization, enabling collaborative behaviors that seek support of a centralized planner for situations that are inherently unstable (degenerate). To demonstrate the generality of our framework we provide a case study involving varying team objectives, such as topology control, that the robots can achieve with limited FOV, while remaining stable. Experimental and numerical validations based on the previously discussed case study are provided to corroborate the theoretical findings

In this work, we consider the problem of planning paths for a team of autonomous unmanned aerial vehicles (UAVs) to assist search and rescue practitioners. To address the problem, we develop a fully integrated framework that includes information from all aspects of the search environment. We take into consideration lost person motion via a behavior-based predictive model, anticipated human searcher trajectories, as well as measurements from fixed field of view sensors on board UAVs. We use a metric of posterior risk as the optimization target as it is an indicator of improved situational awareness and the effectiveness of continuing search efforts. Monte Carlo simulations are presented to demonstrate the effectiveness of the proposed framework.

In this article, we formulate and solve the probabilistic security problem, defined as the probability that a multirobot system (MRS) with probabilistic interaction graphs has realizations that are secure from adversarial attacks. The concept of security is based on the control-theoretic notion of left invertibility, which depends on the existence of disjoint paths and subcuts in the topology describing robot interactions. To model uncertainties in interactions, we associate the existence of edges with a probability distribution. We, then, derive a probability expression based on disjoint paths and subcuts that defines the probability of security of the MRS. The exact probability is computed using the concept of binary decision diagrams (BDDs), a graphical method used to represent Boolean functions. To improve computational complexity, we formulate a combinatorial optimization problem that aims to bound the probability of security. Since MRSs are inherently dynamic, we leverage the graphical properties of BDDs to adapt to any topological changes. To demonstrate the validity of our results, we first track the probability of security of an MRS performing an environmental monitoring task, with Monte Carlo simulations as a baseline for comparison. Finally, we study the behavior of a probabilistic MRS when under attack in three different scenarios.

In this paper, we formulate and solve the intermittent deployment problem, which yields strategies that couple when heterogeneous robots should sense an environmental process, with where a deployed team should sense in the environment. As a motivation, suppose that a spatiotemporal process is slowly evolving and must be monitored by a multi-robot team, e.g., unmanned aerial vehicles monitoring pasturelands in a precision agriculture context. In such a case, an intermittent deployment strategy is necessary as persistent deployment or monitoring is not cost-efficient for a slowly evolving process. At the same time, the problem of where to sense once deployed must be solved as process observations yield useful feedback for determining effective future deployment and monitoring decisions. In this context, we model the environmental process to be monitored as a spatiotemporal Gaussian process with mutual information as a criterion to measure our understanding of the environment. To make the sensing resource-efficient, we demonstrate how to use matroid constraints to impose a diverse set of homogeneous and heterogeneous constraints. In addition, to reflect the cost-sensitive nature of real-world applications, we apply budgets on the cost of deployed heterogeneous robot teams. To solve the resulting problem, we exploit the theories of submodular optimization and matroids and present a greedy algorithm with bounds on sub-optimality. Finally, Monte Carlo simulations demonstrate the correctness of the proposed method.

In this paper, we address the problem of optimal topology selection for stable coordination of multi-robot systems with asymmetric interactions. This problem arises naturally for multi-robot systems that interact based on sensing, e.g., with limited field of view (FOV) cameras. From our previous efforts on motion control in such settings, we have shown that not all interaction topologies yield stable coordinated motion when asymmetry exists. At the same time, not all robot-to-robot interactions are of equal quality, and thus we seek to optimize asymmetric interaction topologies subject to the constraint that the topology yields stable multi-robot motion. In this context, we formulate an optimal topology selection problem (OTSP) as a mixed integer semidefinite programming (MISDP) problem to compute optimal topologies that yield stable coordinated motion. Simulation results are provided to corroborate the effectiveness of the proposed OTSP formulation.

In this paper, we optimize the interaction graph of a multi-robot system (MRS) by maximizing its probability of security while requiring the MRS to have the fewest edges possible. Edges that represent robot interactions exist according to a probability distribution and security is defined using the control theoretic notion of left invertibility. To compute an optimal solution to our problem, we first start by reducing our problem to a variation of the rooted k-connections problem using three graph transformations. Then, we apply a weighted matroid intersection algorithm (WMIA) on matroids defined on the edge set of the interaction graph. Although the optimal solution can be found in polynomial time, MRSs are dynamic and their topologies may change faster than the rate at which the optimal security solution can be found. To cope with dynamic behavior, we present two heuristics that relax optimality but execute with much lower time complexity. Finally, we validate our results through Monte Carlo simulations.

In this paper, our motivating application lies in precision agriculture where accurate modeling of forage is essential for informing rotational grazing strategies. Unfortunately, a major difficulty arises in modeling forage processes as they evolve on large scales according to complex ecological influences. As robots can collect data over large scales in a forage environment, they act as a promising resource for the forage modeling problem when combined with a data-driven Gaussian processes (GPs) technique. However, GPs are nonparametric in nature and may be blind to certain nuances of a process that a parameterized expert model may predict well. Indeed, for the forage modeling problem specifically, there exist several highly parameterized models from agricultural experts that exhibit powerful predictive capabilities. Expert models, however, often come with two shortcomings: (1) parameters may be difficult to determine in general; and (2) the model may not make complete spatiotemporal predictions. For example, a stochastic differential equation (SDE) that models the dynamics of the average output of an environment may be available from experts (a typical case). In such cases, we propose to take advantage of both data-driven (GPs) and expert (SDE) models, by fusing data collected by robots, which often yields spatial insight, with models from experienced professionals that often yield temporal insights. Specifically, we propose to leverage Bayesian estimation to combine these two methods, resulting in a posterior prediction that is a hybrid of data-driven and expert models. Finally, we provide simulations to demonstrate the effectiveness of the proposed method.

In this paper, we formulate a combinatorial optimization problem that aims to maximize the accuracy of a lower bound estimate of the probability of security of a multi-robot system (MRS), while minimizing the computational complexity involved in its calculation. Security of an MRS is defined using the well-known control theoretic notion of left invertiblility, and the probability of security of an MRS can be calculated using binary decision diagrams (BDDs). The complexity of a BDD depends on the number of disjoint path sets considered during its construction. Taking into account all possible disjoint paths results in an exact probability of security, however, selecting an optimal subset of disjoint paths leads to a good estimate of the probability while significantly reducing computation. To deal with the dynamic nature of MRSs, we introduce two methods: (1) multi-point optimization, a technique that requires some a priori knowledge of the topology of the MRS over time, and (2) online optimization, a technique that does not require a priori knowledge, but must construct BDDs while the MRS is operating. Finally, our approach is validated on an MRS performing a rendezvous objective while exchanging information according to a noisy state agreement process.

This paper addresses a fundamental question of multi-agent knowledge distribution: what information should be sent to whom and when, with the limited resources available to each agent? Intelligent Knowledge Distribution is a framework that answers these questions. Communication requirements for multi-agent systems can be rather high when an accurate picture of the environment and the state of other agents must be maintained. To reduce the impact of multi-agent coordination on systems, including communications, this paper introduces the concept of action-based constraints on partially observable Markov decision processes, rewards based upon the value of information driven by Kullback-Leibler Divergence, and probabilistic constraint satisfaction through discrete optimization and Markov chain Monte Carlo analysis. Intelligent Knowledge Distribution is driven by determining the information content an agent believes another agent will obtain by receiving certain information, along with the importance or relevance of that information to the system objective. To perform constraint analysis on an infinite-horizon policy, policies are represented as a Finite State Controller allowing Markov chain Monte Carlo analysis to determine a probabilistic level of guarantee that the constraints will be satisfied. The analysis of performance for an example mission presented in this paper shows the constrained controllers, during the highest constraint seen in simulations, can be constructed to meet minimal constraint guarantees (80%) while impacting the optimal value less than 50%, where the unconstrained optimal controller only satisfied the constraint 10% of the time.

In this paper, we formulate an environmental sensing problem for multi-robot teams that couples intermittent deployments with the selection of team composition and sensor type over time. We suppose that a multi-robot team needs to autonomously sense an environmental process and find the optimal policy for deploying heterogeneous robots. In addition, heterogeneous robot teams can be composed in various ways by selecting different mobility and sensor types which have varying accuracies and costs, resulting in a more complex problem. The question is then how to find an optimal intermittent deployment and sensor selection policy that captures both cost and estimation accuracy based on partial environmental information. By utilizing structural results from partially observable Markov decision processes (POMDP) and exploiting submodularity, an optimal policy, which minimizes cost while maintaining a high accuracy, can be achieved in this paper. The effectiveness of this method is demonstrated by simulation results and comparisons with naive policies.

We study two multi-robot assignment problems for multi-target tracking. We consider distributed approaches in order to deal with limited sensing and communication ranges. We seek to simultaneously assign trajectories and targets to the robots. Our focus is on local algorithms that achieve performance close to the optimal algorithms with limited communication. We show how to use a local algorithm that guarantees a bounded approximate solution within O(hlog1/ε) communication rounds. We compare with a greedy approach that achieves a 2-approximation in as many rounds as the number of robots. Simulation results show that the local algorithm is an effective solution to the assignment problem.

In this paper, we develop a method for determining the probability of a multi-robot system (MRS) being secure when robot interactions are modeled as a probabilistic graph. To define the security of an MRS, we apply an existing control-theoretic notion of network attacks based on the left invertibility of a dynamical system. We then extend previous work by assuming probabilistic robot communication and sensing, modeling the effects of noise, failure, or adversarial influence on interactions in the network. The probabilistic graph security problem can then be seen as a variant of problems solved in the field of system reliability. This interpretation motivates the application of an efficient graphical representation of boolean functions known as binary decision diagrams (BDDs). Specifically, we use the canonical properties of a special type of BDD, the Reduced Order BDD, to generate a tree that can be efficiently traversed to compute the probability that a networked MRS is left invertible, and thus, secure. We then show how our adopted approach can be applied to systems that have interactions that change over time, e.g., for mobile multi-robot teams. Finally, we demonstrate the validity of our method by simulating a mobile MRS performing a rendezvous objective, while tracking its probability of security over time.

In this paper, we demonstrate how topological constraints, as well as other abstract constraints, can be integrated into task allocation by applying the combinatorial theory of matroids. By modeling problems as an intersection of matroid constraints, arbitrary combinatorial relationships can be achieved in the task allocation space. To illustrate the expressiveness of the framework, we model a novel task allocation problem that couples abstract per-robot constraints with a communication spanning tree constraint. As our problem is cast as a matroid intersection, provable optimality bounds with simple greedy algorithms follows immediately from theory. Next, we present a decentralized algorithm that applies auction methods to task allocation with matroid intersections. Simulations of task allocation for surveillance in urban environments demonstrate our results. Finally, Monte Carlo results are provided that indicate greedy task allocations can be highly competitive even with near-optimal solutions in practice.

In this paper, we consider the problem of general topology control in multirobot systems with nonholonomic kinematics. Our contribution is twofold: We first demonstrate the correctness of topology control under the assumption that the network topology can switch arbitrarily and that potential-based mobility is discontinuous with respect to topology changes; we then demonstrate that a multirobot team under the above listed conditions continues to achieve topology control when actuator saturation is applied and in the presence of arbitrary discontinuous (and possibly nonpairwise) exogenous objectives. Simulation results are given to corroborate our theoretical findings.

In this paper, we consider the problem of connectivity maintenance in multi-robot systems with unicycle kinematics. While previous work has approached this problem through local control techniques, we propose a solution which achieves global connectivity maintenance under nonholonomic constraints. In addition, our formulation only requires intermittent estimation of algebraic connectivity, and accommodates discontinuous spatial interactions among robots. Specifically, we extend a decision-based link maintenance framework to unicycle kinematics and discontinuous potential-based interaction, by exploiting techniques from nonsmooth analysis. Then, we couple this extension with an existing connectivity estimation technique which yields an estimate with tunable precision in finite time, achieving our result. To illustrate the correctness of our methods, we provide a brief simulation result that closes the paper.

In this paper, we consider the problem of controlling a multi-robot team in order to track a mobile target with unknown dynamics. Our contribution in this context is a non-linear observability analysis of the target tracking network, which yields insights into the topological and actuation conditions necessary for the underlying state estimation problem. We demonstrate a metric of observability which allows us to determine robot inputs that maximize observability to improve team localization. Combining the observability metric with topological control then yields a robust target tracking solution. We close the paper with a simulation example which demonstrates the ability of our solution to cope with scenarios in which relative measurements poorly distinguish the target.

Motivated by the strong influence network rigidity has on collaborative systems, in this paper, we consider the problem of partitioning a multiagent network into two sub-teams, a bipartition, such that the resulting sub-teams are topologically rigid. In this direction, we determine the existence conditions for rigidity-preserving bipartitions, and provide an iterative algorithm that identifies such partitions in polynomial time. In particular, the relationship between rigid graph partitions and the previously identified Z-link edge structure is given, yielding a feasible direction for graph search. Adapting a supergraph search mechanism, we then detail a methodology for discerning graphs cuts that represent valid rigid bipartitions. Next, we extend our methods to a decentralized context by exploiting leader election and an improved graph search to evaluate feasible cuts using only local agent-to-agent communication. Finally, full algorithm details and pseudocode are provided, together with simulation results that verify correctness and demonstrate complexity.

In this paper, we address the decentralized and parallel construction of rigid graphs in the plane that optimize an edge-weighted objective function under cardinality constraints. Two auction-based algorithms to solve this problem in a decentralized fashion are first proposed. Centered around the notion of leader election, the first approach finds an optimal solution through a greedy bidding, while the second approach provides a sub-optimal solution which reduces complexity according to a sliding mode parameter. Then, by exploiting certain local structural properties of graph rigidity, a parallelization to build a portion of the optimal solution in constant time is derived. A theoretical characterization of algorithm performance is provided together with complexity analysis. Finally, simulation results are presented to corroborate the theoretical findings.

In this paper, we address the construction of optimally rigid networks that minimize an edge-weighted objective function over a planar graph. We propose two auction-based algorithms to solve this problem in a fully decentralized way. The first approach finds an optimal solution at the cost of high communication complexity; the second approach provides a sub-optimal solution while reducing the computational burden according to a sliding mode parameter ζ, yielding a tradeoff between complexity and optimality. A theoretical characterization of the optimality of the first algorithm is provided, and a closed form for the maximum gap between the optimal solution and the sub-optimal solution is also given. Simulation results are presented to corroborate the theoretical findings.

In this paper, we demonstrate a novel hybrid architecture for coordinating networked robots in sensing and information routing applications. The proposed INformation and Sensing driven PhysIcally REconfigurable robotic network (INSPIRE), consists of a Physical Control Plane (PCP) which commands agent position, and an Information Control Plane (ICP) which regulates information flow towards communication/sensing objectives. We describe an instantiation where a mobile robotic network is dynamically reconfigured to ensure high quality routes between static wireless nodes, which act as source/destination pairs for information flow. We demonstrate our propositions through simulation under a realistic wireless network regime.

In this paper, we consider the problem of evaluating the rigidity of a planar network, while satisfying common objectives of real-world systems: decentralization, asynchronicity, and parallelization. The implications that rigidity has in fundamental multirobot problems, e.g., guaranteed formation stability and relative localizability, motivates this study. We propose the decentralization of the pebble game algorithm of Jacobs et al. , which is an O(n2) method that determines the generic rigidity of a planar network. Our decentralization is based on asynchronous messaging and distributed memory, coupled with auctions for electing leaders to arbitrate rigidity evaluation. Further, we provide a parallelization that takes inspiration from gossip algorithms to yield significantly reduced execution time and messaging. An analysis of the correctness, finite termination, and complexity is given, along with a simulated application in decentralized rigidity control. Finally, we provide Monte Carlo analysis in a Contiki networking environment, illustrating the real-world applicability of our methods, and yielding a bridge between rigidity theory and realistic interacting systems.

In this paper, we consider the problem of controlling the connectivity of a network of mobile agents under local topology constraints and proximity-limited communication. The inverse iteration algorithm for spectral analysis is formulated in a distributed manner to allow each agent to estimate a component of global network connectivity, improving on the convergence rate issues of previous approaches. Potential-based controls drive the agents to maximize connectivity under local degree constraints, maintain established links to guarantee connectivity, and avoid collisions. To achieve constraint satisfaction we exploit a switched model of interaction that regulates link addition through symmetric, repulsive potentials between constraint violators, enforcing discernment in communication through spatial organization. Simulations of connectivity estimation as well as agent aggregation and leader-following applications demonstrate the ability of our proposed methods to generate connectivity maximizing, constraint-aware self organization.

In this paper, we consider the problem of controlling a network of locally interacting mobile agents, subject to a set of non-local topology constraints, towards a group flocking objective. As opposed to switching network links directly in the space of discrete graphs, yielding a divide in spatial configuration and communication topology, we regulate topology through mobility, enabling adjacent agents to retain or deny links spatially on the basis of constraint satisfaction. Specifically, we propose a distributed formulation consisting of a switching control and smooth potential fields for local link discrimination and flocking, coupled with consensus-based coordination over proposed topology changes, yielding transitions in communication that respect non-local constraints and correspond to agent configuration. An analysis of the interplay between the topology consensus and constraint composition, together with a Lyapunov-like convergence argument guarantees the flocking, collision avoidance, and constraint satisfaction properties of the system. Finally, simulations of a novel constrained coordination scenario highlight the correctness and applicability of our proposed methods.

In this paper, we consider the problem of evaluating the generic rigidity of an interconnected system in the plane, without a priori knowledge of the network's topological properties. We propose the decentralization of the pebble game algorithm of Jacobs et. al., an O(n2) method that determines the generic rigidity of a planar network. Our decentralization is based on asynchronous inter-agent message-passing and a distributed memory architecture, coupled with consensus-based auctions for electing leaders in the system. We provide analysis of the asynchronous messaging structure and its interaction with leader election, and Monte Carlo simulations demonstrating complexity and correctness. Finally, a novel rigidity evaluation and control scenario in the accompanying media illustrates the applicability of our proposed algorithm.

In this paper, we consider the problem of controlling the interactions of a group of mobile agents, subject to a set of topological constraints. Assuming proximity-limited interagent communication, we leverage mobility, unlike prior work, to enable adjacent agents to interact discriminatively, i.e., to actively retain or reject communication links on the basis of constraint satisfaction. Specifically, we propose a distributed scheme that consists of hybrid controllers with discrete switching for link discrimination, coupled with attractive and repulsive potentials fields for mobility control, where constraint violation predicates form the basis for discernment. We analyze the application of constrained interaction to two canonical coordination objectives, i.e., aggregation and dispersion, with maximum and minimum node degree constraints, respectively. For each task, we propose predicates and control potentials, and examine the dynamical properties of the resulting hybrid systems. Simulation results demonstrate the correctness of our proposed methods and the ability of our framework to generate topology-aware coordinated behavior.

In this paper we consider a probabilistic method for mapping a spatial process over a distributed multi-agent system and a coordinated level curve tracking algorithm for adaptive sampling. As opposed to assuming the independence of spatial features (e.g. an occupancy grid model), we adopt a novel model of spatial dependence based on the grid-structured Markov random field that exploits spatial structure to enhance mapping. The multi-agent Markov random field framework is utilized to distribute the model over the system and to decompose the problem of global inference into local belief propagation problems coupled with neighbor-wise inter-agent message passing. A Lyapunov stable control law for tracking level curves in the plane is derived and a method of gradient and Hessian estimation is presented for applying the control in a probabilistic map of the process. Simulation results over a real-world dataset with the goal of mapping a plume-like oceanographic process demonstrate the efficacy of the proposed algorithms. Scalability and complexity results suggest the feasibility of the approach in realistic multi-agent deployments.

In this work we investigate cooperative inference in multi-agent systems where uncertainty is modeled by the grid structured pairwise Markov random field. A framework is proposed, which we term the multi-agent Markov random field, that decomposes the global inference problem into inter-agent belief exchanges over a hypertree topology and local intra-agent inference problems. Due to the exponential complexity of exact inference, we propose a loopy belief propagation algorithm for approximate inference over appropriately formed local generalized cluster graphs. Both synchronous and intelligent message passing are considered and a grid scale-invariant scheme based on the notion of regions of influence in a cluster graph is presented. The algorithms are simulated over a grid workspace with a team of virtual Autonomous Surface Vehicles (ASVs), with the goal of spatial plume detection in oceanographic data captured from the Moderate Resolution Imaging Spectroradiometer (MODIS) instrument. We show that while the exact method produces predictably accurate and smooth grid maps, the approximate method competes well in terms of plume detection rate with the region of influence message passing scheme excelling over large tasks due to a lack of dependence on grid size.