Learning to cooperate in distributed partially observable environments with no communication abilities poses significant challenges for multi-agent deep reinforcement learning (MARL). This paper addresses key concerns in this domain, focusing on inferring state representations from individual agent observations and leveraging these representations to enhance agents' exploration and collaborative task execution policies. To this end, we propose a novel state modelling framework for cooperative MARL, where agents infer meaningful belief representations of the non-observable state, with respect to optimizing their own policies, while filtering redundant and less informative joint state information. Building upon this framework, we propose the MARL SMPE$^2$ algorithm. In SMPE$^2$, agents enhance their own policy's discriminative abilities under partial observability, explicitly by incorporating their beliefs into the policy network, and implicitly by adopting an adversarial type of exploration policies which encourages agents to discover novel, high-value states while improving the discriminative abilities of others. Experimentally, we show that SMPE$^2$ outperforms a plethora of state-of-the-art MARL algorithms in complex fully cooperative tasks from the MPE, LBF, and RWARE benchmarks.

In Amazon robotic warehouses, the destination-to-chute mapping problem is crucial for efficient package sorting. Often, however, this problem is complicated by uncertain and dynamic package induction rates, which can lead to increased package recirculation. To tackle this challenge, we introduce a Distributionally Robust Multi-Agent Reinforcement Learning (DRMARL) framework that learns a destination-to-chute mapping policy that is resilient to adversarial variations in induction rates. Specifically, DRMARL relies on group distributionally robust optimization (DRO) to learn a policy that performs well not only on average but also on each individual subpopulation of induction rates within the group that capture, for example, different seasonality or operation modes of the system. This approach is then combined with a novel contextual bandit-based estimator of the worst-case induction distribution for each state-action pair, significantly reducing the cost of exploration and thereby increasing the learning efficiency and scalability of our framework. Extensive simulations demonstrate that DRMARL achieves robust chute mapping in the presence of varying induction distributions, reducing package recirculation by an average of 80% in the simulation scenario.

Distributionally Robust Optimization (DRO) accounts for uncertainty in data distributions by optimizing the model performance against the worst possible distribution within an ambiguity set. In this paper, we propose a DRO framework that relies on a new distance inspired by Unbalanced Optimal Transport (UOT). The proposed UOT distance employs a soft penalization term instead of hard constraints, enabling the construction of an ambiguity set that is more resilient to outliers. Under smoothness conditions, we establish strong duality of the proposed DRO problem. Moreover, we introduce a computationally efficient Lagrangian penalty formulation for which we show that strong duality also holds. Finally, we provide empirical results that demonstrate that our method offers improved robustness to outliers and is computationally less demanding for regression and classification tasks.

We consider an online stochastic game with risk-averse agents whose goal is to learn optimal decisions that minimize the risk of incurring significantly high costs. Specifically, we use the Conditional Value at Risk (CVaR) as a risk measure that the agents can estimate using bandit feedback in the form of the cost values of only their selected actions. Since the distributions of the cost functions depend on the actions of all agents that are generally unobservable, they are themselves unknown and, therefore, the CVaR values of the costs are difficult to compute. To address this challenge, we propose a new online risk-averse learning algorithm that relies on one-point zeroth-order estimation of the CVaR gradients computed using CVaR values that are estimated by appropriately sampling the cost functions. We show that this algorithm achieves sub-linear regret with high probability. We also propose two variants of this algorithm that improve performance. The first variant relies on a new sampling strategy that uses samples from the previous iteration to improve the estimation accuracy of the CVaR values. The second variant employs residual feedback that uses CVaR values from the previous iteration to reduce the variance of the CVaR gradient estimates. We theoretically analyze the convergence properties of these variants and illustrate their performance on an online market problem that we model as a Cournot game.

In this work, we address the problem of formal safety verification for stochastic cyber-physical systems (CPS) equipped with ReLU neural network (NN) controllers. Our goal is to find the set of initial states from where, with a predetermined confidence, the system will not reach an unsafe configuration within a specified time horizon. Specifically, we consider discrete-time LTI systems with Gaussian noise, which we abstract by a suitable graph. Then, we formulate a Satisfiability Modulo Convex (SMC) problem to estimate upper bounds on the transition probabilities between nodes in the graph. Using this abstraction, we propose a method to compute tight bounds on the safety probabilities of nodes in this graph, despite possible over-approximations of the transition probabilities between these nodes. Additionally, using the proposed SMC formula, we devise a heuristic method to refine the abstraction of the system in order to further improve the estimated safety bounds. Finally, we corroborate the efficacy of the proposed method with simulation results considering a robot navigation example and comparison against a state-of-the-art verification scheme.

Planning the motion of bearings-only sensors is critical for enabling accurate tracking of the positions of moving targets. In this paper, we demonstrate planning the observer's motion over horizons greater than one step for estimating an unknown and varying number of indistinguishable, maneuvering targets of interest using a probability hypothesis density (PHD) filter, with a Rériyi divergence reward for selecting actions. We describe approximations to make this approach computationally feasible, and we propose using Monte Carlo tree search (MCTS) to further reduce the cost. Finally, we present simulation results showing that longer planning horizons reduce the error in the estimates and that MCTS can reduce the cost of planning without sacrificing the quality of the estimates.

We consider the problem of optimally allocating tasks, expressed as global linear temporal logic (LTL) specifications, to teams of heterogeneous mobile robots of different types. Each task may require robots of multiple types. To obtain a scalable solution, we propose a hierarchical approach that first allocates specific robots to tasks using the information about the tasks contained in the nondeterministic B$\ddot{\text{u}}$chi automaton (NBA) that captures the LTL specification and then designs low-level paths for robots that respect the high-level assignment. Specifically, motivated by “lazy collision checking” methods in robotics, we first prune and relax the NBA by removing all negative atomic propositions, which simplifies the planning problem by checking constraint satisfaction only when needed. Then, we extract sequences of subtasks from the relaxed NBA along with their temporal orders and formulate a mixed integer linear program to allocate these subtasks to robots. Finally, we define generalized multirobot path planning problems to obtain low-level paths that satisfy both the high-level task allocation and the constraints captured by the negative atomic propositions in the original NBA. We show that our method is complete for a subclass of LTL that covers a broad range of tasks and present numerical simulations demonstrating that it can generate paths with lower cost, considerably faster than existing methods.

We study the problem of synthesizing control strategies for Linear Temporal Logic (LTL) objectives in unknown environments. We model this problem as a turn-based zero-sum stochastic game between the controller and the environment, where the transition probabilities and the model topology are fully unknown. The winning condition for the controller in this game is the satisfaction of the given LTL specification, which can be captured by the acceptance condition of a deterministic Rabin automaton (DRA) directly derived from the LTL specification. We introduce a model-free reinforcement learning (RL) methodology to find a strategy that maximizes the probability of satisfying a given LTL specification when the Rabin condition of the derived DRA has a single accepting pair. We then generalize this approach to LTL formulas for which the Rabin condition has a larger number of accepting pairs, providing a lower bound on the satisfaction probability. Finally, we illustrate applicability of our RL method on two motion planning case studies.

The majority of existing linear temporal logic (LTL) planning methods rely on the construction of a discrete product automaton, which combines a discrete abstraction of robot mobility and a Büchi automaton that captures the LTL specification. Representing this product automaton as a graph and using graph search techniques, optimal plans that satisfy the LTL task can be synthesized. However, constructing expressive discrete abstractions makes the synthesis problem computationally intractable. In this article, we propose a new sampling-based LTL planning algorithm that does not require any discrete abstraction of robot mobility. Instead, it incrementally builds trees that explore the product state-space, until a maximum number of iterations is reached or a feasible plan is found. The use of trees makes data storage and graph search tractable, which significantly increases the scalability of our algorithm. To accelerate the construction of feasible plans, we introduce bias in the sampling process, which is guided by transitions in the Büchi automaton that belong to the shortest path to the accepting states. We show that our planning algorithm, with and without bias, is probabilistically complete and asymptotically optimal. Finally, we present numerical experiments showing that our method outperforms relevant temporal logic planning methods.

We present a reinforcement learning (RL) framework to synthesize a control policy from a given linear temporal logic (LTL) specification in an unknown stochastic environment that can be modeled as a Markov Decision Process (MDP). Specifically, we learn a policy that maximizes the probability of satisfying the LTL formula without learning the transition probabilities. We introduce a novel rewarding and path-dependent discounting mechanism based on the LTL formula such that (i) an optimal policy maximizing the total discounted reward effectively maximizes the probabilities of satisfying LTL objectives, and (ii) a model-free RL algorithm using these rewards and discount factors is guaranteed to converge to such policy. Finally, we illustrate the applicability of our RL-based synthesis approach on two motion planning case studies.

In this paper we propose an algorithm to actively control the distance of a motor-propeller system (MPS) to a large obstacle using data from a single microphone. The method is based upon a broadband constructive/destructive interference pattern across the audible frequency band that is present when the MPS is near an obstacle. By taking the difference between the power spectrum in the obstacle-free case and the spectrum when recording near an obstacle, a broadband oscillation with respect to frequency is revealed. The frequency of this oscillation is linearly-related to the distance from the microphone to the wall. We present both static and dynamic experiments showcasing the ability of the proposed method to estimate the distance to a wall as well as actively control it.

In this paper, we propose a Deep Imitative Q-learning (DIQL) method to synthesize control policies for mobile robots that need to satisfy Linear Temporal Logic (LTL) specifications using noisy semantic observations of their surroundings. The robot sensing error is modeled using probabilistic labels defined over the states of a Labeled Transition System (LTS) and the robot mobility is modeled using a Labeled Markov Decision Process (LMDP) with unknown transition probabilities. We use existing product-based model checkers (PMCs) as experts to guide the Q-learning algorithm to convergence. To the best of our knowledge, this is the first approach that models noise in semantic observations using probabilistic labeling functions and employs existing model checkers to provide suboptimal instructions to the Q-learning agent.

In this article, we consider the problem of mass transport cloaking using mobile robots. The robots move along a predefined curve that encloses a safe zone and carry sources that collectively counteract a chemical agent released in the environment. The goal is to steer the mass flux around a desired region so that it remains unaffected by the external concentration. We formulate the problem of controlling the robot positions and release rates as a partial differential equation (PDE)-constrained optimization, where the propagation of the chemical is modeled by the advection-diffusion (AD) PDE. We use a neural network (NN) to approximate the solution of the PDE. Particularly, we propose a novel loss function for the NN that utilizes the variational form of the AD-PDE and allows us to reformulate the planning problem as an unsupervised model-based learning problem. Our loss function is discretization-free and highly parallelizable. Unlike passive cloaking methods that use metamaterials to steer the mass flux, our method is the first to use mobile robots to actively control the concentration levels and create safe zones independent of environmental conditions. We demonstrate the performance of our method in simulations.

In this paper, we consider the problem of Active Source Identification in steady-state advection-diffusion (AD) transport systems. Unlike existing bioinspired heuristic methods, we propose a model-based approach that employs the AD-partial differential equation (PDE) to capture the transport phenomenon. Specifically, we formulate the source identification (SI) problem as a PDE-constrained optimization problem in function spaces. To obtain a tractable solution, we reduce the dimension of the concentration field using Proper Orthogonal Decomposition and approximate the unknown source field using nonlinear basis functions, drastically decreasing the number of unknowns. Moreover, to collect the concentration measurements, we control a robot sensor through a sequence of waypoints that maximize the smallest eigenvalue of the Fisher Information matrix of the unknown source parameters. Specifically, after every new measurement, an SI problem is solved to obtain a source estimate that is used to determine the next waypoint. We show that our algorithm can efficiently identify sources in complex AD systems and nonconvex domains, in simulation and experimentally. This is the first time that PDEs are used for robotic SI in practice.

This paper considers the problem of distributed state estimation (DSE) using multirobot systems. The robots have limited communication capabilities and, therefore, communicate their measurements intermittently only when they are physically close to each other. To decrease the distance that the robots need to travel only to communicate, we divide them into small teams that can communicate at different locations to share information and update their beliefs. Then, we propose a new distributed scheme that combines: first, communication schedules that ensure that the network is intermittently connected, and second, sampling-based motion planning for the robots in every team with the objective to collect optimal measurements and decide a location for those robots to communicate. To the best of our knowledge, this is the first DSE framework that relaxes all network connectivity assumptions, and controls intermittent communication events so that the estimation uncertainty is minimized. We present simulation results that demonstrate significant improvement in estimation accuracy compared to methods that maintain an end-to-end connected network for all time.

In this paper, we develop a distributed intermittent communication framework for teams of mobile robots that are responsible for accomplishing time-critical dynamic tasks and sharing the collected information with all other robots and possibly also with a user. Specifically, we consider situations where the robot communication capabilities are not sufficient to maintain reliable and connected networks while the robots move to accomplish their tasks. In this case, intermittent communication protocols are necessary that allow the robots to temporarily disconnect from the network in order to accomplish their tasks free of communication constraints. We assume that the robots can only communicate with each other when they meet at common locations in space. Our proposed distributed control framework determines offline schedules of communication events and integrates them online with task planning. The resulting paths ensure task accomplishment and exchange of information among robots infinitely often at locations that minimize a user-specified metric. Simulation results corroborate the proposed distributed control framework.

We consider a team of heterogeneous robots, which are deployed within a common workspace to gather different types of data. The robots have different roles due to different capabilities: some gather data from the workspace (source robots) and others receive data from source robots and upload them to a data center (relay robots). The data-gathering tasks are specified locally to each source robot as high-level linear temporal logic formulas, which capture the different types of data that need to be gathered at different regions of interest. All robots have a limited buffer to store the data. Thus, the data gathered by source robots should be transferred to relay robots before their buffers overflow, respecting at the same time a limited communication range for all robots. The main contribution of this work is a distributed motion coordination and intermittent communication scheme that guarantees the satisfaction of all local tasks, while obeying the above constraints. The robot motion and interrobot communication are closely coupled and coordinated during runtime by scheduling intermittent meeting events to facilitate the local plan execution. We present both numerical simulations and experimental studies to demonstrate the advantages of the proposed method over existing approaches that predominantly require all-time network connectivity.

In this paper, we present a control framework that allows magnetic microrobot teams to accomplish complex micromanipulation tasks captured by global linear temporal logic (LTL) formulas. To address this problem, we propose an optimal control synthesis method that constructs discrete plans for the robots that satisfy both the assigned tasks as well as proximity constraints between the robots due to the physics of the problem. The proposed algorithm relies on an existing optimal control synthesis approach combined with a novel sampling-based technique to reduce the state-space of the product automaton that is associated with the LTL specifications. The synthesized discrete plans are executed by the microrobots independently using local magnetic fields. Simulation studies show that the proposed algorithm can address large-scale planning problems that cannot be solved using existing optimal control synthesis approaches. Moreover, we present experimental results that also illustrate the potential of the method in practice. To the best of our knowledge, this is the first control framework that allows independent control of teams of magnetic microrobots for temporal micromanipulation tasks.

We consider a team of multiple dynamical and heterogeneous robots which are deployed for gathering different types of data within a common workspace. The robots have different roles due to different capabilities: some gather data from the workspace (Type-A robots) and others receive data from Type-A robots and upload them to a data center (Type-B robots). The data-gathering tasks are specified locally to each Type-A robot as high-level Linear Temporal Logic (LTL) formulas. All robots have a limited buffer to store the data. Thus the data gathered by Type-A robots should be transferred to Type-B robots before the buffers overflow, respecting at the same time limited communication range for all robots. The main contribution of this work is a distributed task coordination and intermittent meeting scheme that guarantees the satisfaction of all local tasks while obeying the above constraints. We present numerical simulations to demonstrate the advantages of the proposed method over most existing approaches that require all-time network connectivity.

In this paper, we consider scenarios where mobility can be exploited to enable reliable communications in wireless networks with scarce resources that are unable to concurrently service their nodes. Specifically, we consider cases where a team of robots operate as mobile access points (APs) that provide service, namely sufficient end-to-end communication routes, to a multihop network of static source nodes which generate data. We introduce the connectivity scheduling problem, a novel framework that combines motion planning of the APs with service scheduling of the source nodes and network routing control so that integrity of communications is guaranteed over time. We formulate the connectivity scheduling problem as a multistage mixed integer programming (MIP) problem, where path planning, service scheduling, and routing decisions are all jointly optimized over a discrete-time horizon. Since MIP problems can grow intractable quickly, we further consider a continuous convex reformulation of the problem and employ sparse optimization techniques, specifically the reweighted ℓ1regularization scheme, to recover the desired integrality structure of the solution. We propose a decentralized method to solve the above relaxation that is based on the recently developed accelerated distributed augmented Lagrangians (ADAL) algorithm. Specifically, we modify ADAL by incorporating in the algorithm the reweighted ℓ1scheme, which enables us to recover the desired sparsity structure of the original MIP at the final solution. Numerical results are presented that validate the effectiveness of the proposed framework.

In this paper, we consider networks of mobile robots responsible for servicing a collection of tasks in complex environments, while ensuring end-to-end connectivity with a fixed infrastructure of access points. Tasks are associated with specific locations in the environment, are announced sequentially, and are not assigned a priori to any robots. Information generated at the tasks is propagated to the access points via a multihop communication network. We propose a distributed, hybrid control scheme that dynamically grows tree networks, rooted at the access points, with branches that connect robots that service individual tasks to the main network structure. To achieve this goal, the robots switch between different roles related to their functionality in the network. The switching process is tightly integrated with distributed optimization of the communication variables and motion planning in complex environments, giving rise to the proposed distributed hybrid system. Our proposed scheme results in an efficient use of the available robots and also allows for global planning by construction, a task that is particularly challenging in complex environments.

We present an approach for correcting the bias in 3D reconstruction of points imaged by a calibrated stereo rig. Our analysis is based on the observation that, due to quantization error, a 3D point reconstructed by triangulation essentially represents an entire region in space. The true location of the world point that generated the triangulated point could be anywhere in this region. We argue that the reconstructed point, if it is to represent this region in space without bias, should be located at the centroid of this region, which is not what has been done in the literature. We derive the exact geometry of these regions in space, which we call 3D cells, and we show how they can be viewed as uniform distributions of possible pre-images of the pair of corresponding pixels. By assuming a uniform distribution of points in 3D, as opposed to a uniform distribution of the projections of these 3D points on the images, we arrive at a fast and exact computation of the triangulation bias in each cell. In addition, we derive the exact covariance matrices of the 3D cells. We validate our approach in a variety of simulations ranging from 3D reconstruction to camera localization and relative motion estimation. In all cases, we are able to demonstrate a marked improvement compared to conventional techniques for small disparity values, for which bias is significant and the required corrections are large.

This paper presents a novel method that enables a team of aerial robots to enclose a target in 3D space by attaining a desired geometric formation around it. We propose an approach in which each robot obtains its motion commands using measurements of the relative position of the other agents and of the target, without the need for a central coordinator. As contribution, our method permits any desired 3D target enclosing configuration to be defined, in contrast with the planar circular patterns commonly encountered in the literature. The proposed control strategy relies on the minimization of a cost function that captures the collective motion objective. In our method, the robots do not need to use a common reference frame. This coordinate independence is achieved through the introduction in the cost function of a rotation matrix computed locally by each robot. We prove that our motion controller is exponentially stable, and illustrate its performance through simulations.

We consider a source (Alice) trying to communicate with a destination (Bob), in a way that an unauthorized node (Eve) cannot infer, based on her observations, the information that is being transmitted. The communication is assisted by multiple multi-antenna cooperating nodes (helpers) who have the ability to move. While Alice transmits, the helpers transmit noise that is designed to affect the entire space except Bob. We consider the problem of selecting the helper weights and positions that maximize the system secrecy rate. It turns out that this optimization problem can be efficiently solved, leading to a novel decentralized helper motion control scheme. Simulations indicate that introducing helper mobility leads to considerable savings in terms of helper transmit power, as well as total number of helpers required for secrecy communications.

In this paper, we consider the problem of precisely localizing a group of stationary targets using a single stereo camera mounted on a mobile robot. In particular, assuming that at least one pair of stereo images of the targets is available, we seek to determine where to move the stereo camera so that the localization uncertainty of the targets is minimized. We call this problem the Next-Best-View problem. The advantage of using a stereo camera is that, using triangulation, the two simultaneous images can yield range and bearing measurements of the targets, as well as their uncertainty. We use a Kalman filter to fuse location and uncertainty estimates as more measurements are acquired. Our solution to the Next-Best-View problem is to iteratively minimize the fused uncertainty of the targets' locations subject to field-of-view constraints. We capture these objectives by appropriate artificial potentials on the camera's relative frame and the global frame, respectively. In particular, with every new observation, the mobile stereo camera computes the new next best view on the relative frame and subsequently realizes this view in the global frame via gradient descent on the space of robot positions and orientations, until a new observation is made. Integration of next best view with motion planning results in a hybrid system, which we illustrate in computer simulations.

We provide a theoretical framework for controlling graph connectivity in mobile robot networks. We discuss proximity-based communication models composed of disk-based or uniformly-fading-signal-strength communication links. A graph-theoretic definition of connectivity is provided, as well as an equivalent definition based on algebraic graph theory, which employs the adjacency and Laplacian matrices of the graph and their spectral properties. Based on these results, we discuss centralized and distributed algorithms to maintain, increase, and control connectivity in mobile robot networks. The various approaches discussed in this paper range from convex optimization and subgradient-descent algorithms, for the maximization of the algebraic connectivity of the network, to potential fields and hybrid systems that maintain communication links or control the network topology in a least restrictive manner. Common to these approaches is the use of mobility to control the topology of the underlying communication network. We discuss applications of connectivity control to multirobot rendezvous, flocking and formation control, where so far, network connectivity has been considered an assumption.

Distributed task assignment for multiple agents raises fundamental and novel problems in control theory and robotics. A new challenge is the development of distributed algorithms that dynamically assign tasks to multiple agents, not relying on a priori assignment information. We address this challenge using market-based coordination protocols where the agents are able to bid for task assignment with the assumption that every agent has knowledge of the maximum number of agents that any given task can accommodate. We show that our approach always achieves the desired assignment of agents to tasks after exploring at most a polynomial number of assignments, dramatically reducing the combinatorial nature of discrete assignment problems. We verify our algorithm through both simulation and experimentation on a team of non-holonomic robots performing distributed formation stabilization and group splitting and merging.

Distributed motion planning of multiple agents raises fundamental and novel problems in control theory and robotics. In particular, in applications such as coverage by mobile sensor networks or multiple target tracking, a great new challenge is the development of motion planning algorithms that dynamically assign targets or destinations to multiple homogeneous agents, not relying on any a priori assignment of agents to destinations. In this paper, we address this challenge using two novel ideas. First, distributed multidestination potential fields are developed that are able to drive every agent to any available destination. Second, nearest neighbor coordination protocols are developed ensuring that distinct agents are assigned to distinct destinations. Integration of the overall system results in a distributed, multiagent, hybrid system for which we show that the mutual exclusion property of the final assignment is guaranteed for almost all initial conditions. Furthermore, we show that our dynamic assignment algorithm will converge after exploring at most a polynomial number of assignments, dramatically reducing the combinatorial nature of purely discrete assignment problems. Our scalable approach is illustrated with nontrivial computer simulations.

Control of mobile networks raises fundamental and novel problems in controlling the structure of the resulting dynamic graphs. In particular, in applications involving mobile sensor networks and multiagent systems, a great new challenge is the development of distributed motion algorithms that guarantee connectivity of the overall network. Motivated by the inherently discrete nature of graphs as combinatorial objects, we address this challenge using a key control decomposition. First, connectivity control of the network structure is performed in thediscretespace of graphs and relies on local estimates of the network topology used, along with algebraic graph theory, to verify link deletions with respect to connectivity. Tie breaking, when multiple such link deletions can violate connectivity, is achieved by means of gossip algorithms and distributed market-based control. Second, motion control is performed in thecontinuousconfiguration space, where nearest-neighbor potential fields are used to maintain existing links in the network. Integration of the earlier controllers results in a distributed, multiagent, hybrid system, for which we show that the resulting motion always ensures connectivity of the network, while it reconfigures toward certain secondary objectives. Our approach can also account for communication time delays as well as collision avoidance and is illustrated in nontrivial computer simulations.

Distributed motion planning of multiple agents raises fundamental and novel problems in control theory and robotics. Recently, one such great challenge has been the development of motion planning algorithms that dynamically assign targets or destinations to multiple homogeneous agents, not relying on any a priori assignment of agents to destinations. In this paper, we address this challenge using two novel ideas. First, we develop distributed multi-destination potential fields able to drive every agent to any available destination for almost all initial conditions. Second, we propose sensor-based coordination protocols that ensure that distinct agents are assigned to distinct destinations. Integration of the overall system results in a distributed, multi-agent, hybrid system for which we show that the mutual exclusion property of the final assignment is guaranteed for almost all initial conditions. Moreover, we show that our dynamic assignment algorithm converges after exploring at most a polynomial number of assignments, dramatically reducing the combinatorial nature of purely discrete assignment problems. Our scalable approach is illustrated with nontrivial computer simulations.

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.