Finding near-optimal solutions for dense multi-agent pathfinding (MAPF) problems in real-time remains challenging even for state-of-the-art planners. To this end, we develop a hybrid framework that integrates a learned heuristic derived from MAGAT, a neural MAPF policy with a graph attention scheme, into a leading search-based algorithm, LaCAM. While prior work has explored learning-guided search in MAPF, such methods have historically underperformed. In contrast, our approach, termed LaGAT, outperforms both purely search-based and purely learning-based methods in dense scenarios. This is achieved through an enhanced MAGAT architecture, a pre-train–then–fine-tune strategy on maps of interest, and a deadlock detection scheme to account for imperfect neural guidance. Our results demonstrate that, when carefully designed, hybrid search offers a powerful solution for tightly coupled, challenging multi-agent coordination problems.

Learning complex robot behavior through interactions with the environment necessitates principled exploration. Effective strategies should prioritize exploring regions of the state-action space that maximize rewards, with optimistic exploration emerging as a promising direction aligned with this idea and enabling sample-efficient reinforcement learning. However, existing methods overlook a crucial aspect: the need for optimism to be informed by a belief connecting the reward and state. To address this, we propose a practical, theoretically grounded approach to optimistic exploration based on Thompson sampling. Our approach is the first that allows for reasoning about _joint_ uncertainty over transitions and rewards for optimistic exploration. We apply our method on a set of MuJoCo and VMAS continuous control tasks. Our experiments demonstrate that optimistic exploration significantly accelerates learning in environments with sparse rewards, action penalties, and difficult-to-explore regions. Furthermore, we provide insights into when optimism is beneficial and emphasize the critical role of model uncertainty in guiding exploration.

Cooperative Simultaneous Localization and Mapping (C-SLAM) enables multiple agents to work together in mapping unknown environments while simultaneously estimating their own positions. This approach enhances robustness, scalability, and accuracy by sharing information between agents, reducing drift, and enabling collective exploration of larger areas. In this paper, we present Decentralized Visual Monocular SLAM (DVM-SLAM), the first open-source decentralized monocular C-SLAM system. By only utilizing low-cost and light-weight monocular vision sensors, our system is well suited for small robots and micro aerial vehicles (MAVs). DVMSLAM's real-world applicability is validated on physical robots with a custom collision avoidance framework, showcasing its potential in real-time multi-agent autonomous navigation scenarios. We also demonstrate comparable accuracy to state-of-the-art centralized monocular C-SLAM systems. We opensource our code and provide supplementary material online${ }^{1}$.

We present a method for synthesizing navigation policies for multi-robot teams that interpret and follow natural language instructions. We condition these policies on embeddings from pretrained Large Language Models (LLMs), and train them via offline reinforcement learning with as little as 20 minutes of randomly-collected real-world data. Experiments on a team of five real robots show that these policies generalize well to unseen commands, indicating an understanding of the LLM latent space. Our method requires no simulators or environment models, and produces low-latency control policies that can be deployed directly to real robots without finetuning. We provide videos of our experiments at https://sites.google.com/view/llm-marl.

This work presents an optimization method for generating kinodynamically feasible and collision-free multi-robot trajectories that exploits an incremental denoising scheme in diffusion models. Our key insight is that high-quality trajectories can be discovered merely by denoising noisy trajectories sampled from a distribution. This approach has no learning component, relying instead on only two ingredients: a dynamical model of the robots to obtain feasible trajectories via rollout, and a fitness function to guide denoising with Monte Carlo gradient approximation. The proposed framework iteratively optimizes a deformation for the previous trajectory with the current denoising process, allows anytime refinement as time permits, supports different dynamics, and benefits from GPU acceleration. Our evaluations for differential-drive and holonomic teams with up to 16 robots in 2D and 3D worlds show its ability to discover high-quality solutions faster than other black-box optimization methods such as MPPI. In a 2D holonomic case with 16 robots, it is almost twice as fast. As evidence for feasibility, we demonstrate zero-shot deployment of the planned trajectories on eight multirotors.

Thompson sampling (TS) is a powerful and widely used strategy for sequential decision-making, with applications ranging from Bayesian optimization to reinforcement learning (RL). Despite its success, the theoretical foundations of TS remain limited, particularly in settings with complex temporal structure such as RL. We address this gap by establishing no-regret guarantees for TS using models with Gaussian marginal distributions. Specifically, we consider TS in episodic RL with joint Gaussian process (GP) priors over rewards and transitions. We prove a regret bound of $\mathcal{\tilde{O}}(\sqrt{KH\Gamma(KH)})$ over $K$ episodes of horizon $H$, where $\Gamma(\cdot)$ captures the complexity of the GP model. Our analysis addresses several challenges, including the non-Gaussian nature of value functions and the recursive structure of Bellman updates, and extends classical tools such as the elliptical potential lemma to multi-output settings. This work advances the understanding of TS in RL and highlights how structural assumptions and model uncertainty shape its performance in finite-horizon Markov Decision Processes.

Evolutionary science provides evidence that diversity confers resilience in natural systems. Yet, traditional multi-agent reinforcement learning techniques commonly enforce homogeneity to increase training sample efficiency. When a system of learning agents is not constrained to homogeneous policies, individuals may develop diverse behaviors, resulting in emergent complementarity that benefits the system. Despite this, there is a surprising lack of tools that quantify behavioral diversity. Such techniques would pave the way towards understanding the impact of diversity in collective artificial intelligence and enabling its control. In this paper, we introduce System Neural Diversity (SND): a measure of behavioral heterogeneity in multi-agent systems. We discuss and prove its theoretical properties, and compare it with alternate, state-of-the-art behavioral diversity metrics used in the robotics domain. Through simulations of a variety of cooperative multi-robot tasks, we show how our metric constitutes an important tool that enables measurement and control of behavioral heterogeneity. In dynamic tasks, where the problem is affected by repeated disturbances during training, we show that SND allows us to measure latent resilience skills acquired by the agents, while other proxies, such as task performance (reward), fail to. Finally, we show how the metric can be employed to control diversity, allowing us to enforce a desired heterogeneity set-point or range. We demonstrate how this paradigm can be used to bootstrap the exploration phase, finding optimal policies faster, thus enabling novel and more efficient MARL paradigms.

Multirobot systems are essential for environmental monitoring, particularly for tracking spatial phenomena like pollution, soil minerals, and water salinity, and more. This study addresses the challenge of deploying a multirobot team for optimal coverage in environments where the density distribution, describing areas of interest, is unknown and changes over time. We propose a fully distributed control strategy that uses Gaussian processes (GPs) to model the spatial field and balance the tradeoff between learning the field and optimally covering it. Unlike existing approaches, we address a more realistic scenario by handling time-varying spatial fields, where theexploration-exploitationtradeoff is dynamically adjusted over time. Each robot operates locally, using only its own collected data and the information shared by the neighboring robots. To address the computational limits of GPs, the algorithm efficiently manages the volume of data by selecting only the most relevant samples for the process estimation. The performance of the proposed algorithm is evaluated through several simulations and experiments, incorporating real-world data phenomena to validate its effectiveness.

The study of behavioral diversity in Multi-Agent Reinforcement Learning (MARL) is a nascent yet promising field. In this context, the present work deals with the question of how to control the diversity of a multi-agent system. With no existing approaches to control diversity to a set value, current solutions focus on blindly promoting it via intrinsic rewards or additional loss functions, effectively changing the learning objective and lacking a principled measure for it. To address this, we introduce Diversity Control (DiCo), a method able to control diversity to an exact value of a given metric by representing policies as the sum of a parameter-shared component and dynamically scaled per-agent components. By applying constraints directly to the policy architecture, DiCo leaves the learning objective unchanged, enabling its applicability to any actor-critic MARL algorithm. We theoretically prove that DiCo achieves the desired diversity, and we provide several experiments, both in cooperative and competitive tasks, that show how DiCo can be employed as a novel paradigm to increase performance and sample efficiency in MARL. Multimedia results are available on the paper’s website: https://sites.google.com/view/dico-marl

Memory models such as Recurrent Neural Networks (RNNs) and Transformers address Partially Observable Markov Decision Processes (POMDPs) by mapping trajectories to latent Markov states. Neither model scales particularly well to long sequences, especially compared to an emerging class of memory models called Linear Recurrent Models. We discover that the recurrent update of these models resembles a monoid, leading us to reformulate existing models using a novel monoid-based framework that we call memoroids. We revisit the traditional approach to batching in recurrent reinforcement learning, highlighting theoretical and empirical deficiencies. We leverage memoroids to propose a batching method that improves sample efficiency, increases the return, and simplifies the implementation of recurrent loss functions in reinforcement learning.

The field of Multi-Agent Reinforcement Learning (MARL) is currently facing a reproducibility crisis. While solutions for standardized reporting have been proposed to address the issue, we still lack a benchmarking tool that enables standardization and reproducibility, while leveraging cutting-edge Reinforcement Learning (RL) implementations. In this paper, we introduce BenchMARL, the first MARL training library created to enable standardized benchmarking across different algorithms, models, and environments. BenchMARL uses TorchRL as its backend, granting it high-performance and maintained state-of-the-art implementations while addressing the broad community of MARL PyTorch users. Its design enables systematic configuration and reporting, thus allowing users to create and run complex benchmarks from simple one-line inputs. BenchMARL is open-sourced on GitHub at https://github.com/facebookresearch/BenchMARL

Wireless local area networks (WLANs) manage multiple access points (APs) and assign scarce radio frequency resources to APs for satisfying traffic demands of associated user devices. This paper considers the channel allocation problem in WLANs that minimizes the mutual interference among APs, and puts forth a learning-based solution that can be implemented in a decentralized manner. We formulate the channel allocation problem as an unsupervised learning problem, parameterize the control policy of radio channels with graph neural networks (GNNs), and train GNNs with the policy gradient method in a model-free manner. The proposed approach allows for a decentralized implementation due to the distributed nature of GNNs and is equivariant to network permutations. The former provides an efficient and scalable solution for large network scenarios, and the latter renders our algorithm independent of the AP reordering. Empirical results are presented to evaluate the proposed approach and corroborate theoretical findings.

Traditional approaches to the design of multiagent navigation algorithms consider the environment as a fixed constraint, despite the obvious influence of spatial constraints on agents' performance. Yet hand-designing improved environment layouts and structures is inefficient and potentially expensive. The goal of this paper is to consider the environment as a decision variable in a system-level optimization problem, where both agent performance and environment cost can be accounted for. We begin by proposing a novel environment optimization problem. We show, through formal proofs, under which conditions the environment can change while guaranteeing completeness (i.e., all agents reach their navigation goals). Our solution leverages a model-free reinforcement learning approach. In order to accommodate a broad range of implementation scenarios, we include both online and offline optimization, and both discrete and continuous environment representations. Numerical results corroborate our theoretical findings and validate our approach.

Conflict-Based Search is one of the most popular methods for multi-agent path finding. Though it is complete and optimal, it does not scale well. Recent works have been proposed to accelerate it by introducing various heuristics. However, whether these heuristics can apply to non-grid-based problem settings while maintaining their effectiveness remains an open question. In this work, we find that the answer is prone to be no. To this end, we propose a learning-based component, i.e., the Graph Transformer, as a heuristic function to accelerate the planning. The proposed method is provably complete and bounded-suboptimal with any desired factor. We conduct extensive experiments on two environments with dense graphs. Results show that the proposed Graph Transformer can be trained in problem instances with relatively few agents and generalizes well to a larger number of agents, while achieving better performance than state-of-the-art methods.

We consider the problem of navigating a mobile robot towards a target in an unknown environment that is endowed with visual sensors, where neither the robot nor the sensors have access to global positioning information and only use first-person- view images. In order to overcome the need for positioning, we train the sensors to encode and communicate relevant viewpoint information to the mobile robot, whose objective it is to use this information to navigate to the target along the shortest path. We overcome the challenge of enabling all the sensors (even those that cannot directly see the target) to predict the direction along the shortest path to the target by implementing a neighborhood-based feature aggregation module using a Graph Neural Network (GNN) architecture. In our experiments, we first demonstrate generalizability to previously unseen environments with various sensor layouts. Our results show that by using communication between the sensors and the robot, we achieve up to 2.0 × improvement in SPL (Success weighted by Path Length) when compared to a communication-free baseline. This is done without requiring a global map, positioning data, nor pre-calibration of the sensor network. Second, we perform a zero-shot transfer of our model from simulation to the real world. Laboratory experiments demonstrate the feasibility of our approach in various cluttered environments. Finally, we showcase examples of successful navigation to the target while both the sensor network layout as well as obstacles are dynamically reconfigured as the robot navigates. We provide a video demo11https://www.youtube.com/watch?v=kcrnr6RUgucw, the dataset, trained models, and source code22https://github.com/proroklab/sensor-guided-visual-nav.

Graph Neural Network (GNN) architectures are defined by their implementations of update and aggregation modules. While many works focus on new ways to parametrise the update modules, the aggregation modules receive comparatively little attention. Because it is difficult to parametrise aggregation functions, currently most methods select a ``standard aggregator'' such as mean, sum, or max. While this selection is often made without any reasoning, it has been shown that the choice in aggregator has a significant impact on performance, and the best choice in aggregator is problem-dependent. Since aggregation is a lossy operation, it is crucial to select the most appropriate aggregator in order to minimise information loss. In this paper, we present GenAgg, a generalised aggregation operator, which parametrises a function space that includes all standard aggregators. In our experiments, we show that GenAgg is able to represent the standard aggregators with much higher accuracy than baseline methods. We also show that using GenAgg as a drop-in replacement for an existing aggregator in a GNN often leads to a significant boost in performance across various tasks.

Nearly all real world tasks are inherently partially observable, necessitating the use of memory in Reinforcement Learning (RL). Most model-free approaches summarize the trajectory into a latent Markov state using memory models borrowed from Supervised Learning (SL), even though RL tends to exhibit different training and efficiency characteristics. Addressing this discrepancy, we introduce Fast and Forgetful Memory, an algorithm-agnostic memory model designed specifically for RL. Our approach constrains the model search space via strong structural priors inspired by computational psychology. It is a drop-in replacement for recurrent neural networks (RNNs) in recurrent RL algorithms, achieving greater reward than RNNs across various recurrent benchmarks and algorithms _without changing any hyperparameters_. Moreover, Fast and Forgetful Memory exhibits training speeds two orders of magnitude faster than RNNs, attributed to its logarithmic time and linear space complexity. Our implementation is available at https://github.com/proroklab/ffm.

Graph Neural Networks (GNNs) are a paradigm-shifting neural architecture to facilitate the learning of complex multi-agent behaviors. Recent work has demonstrated remarkable performance in tasks such as flocking, multi-agent path planning and cooperative coverage. However, the policies derived through GNN-based learning schemes have not yet been deployed to the real-world on physical multi-robot systems. In this work, we present the design of a system that allows for fully decentralized execution of GNN-based policies. We create a framework based on ROS2 and elaborate its details in this paper. We demonstrate our framework on a case-study that requires tight coordination between robots, and present first-of-a-kind results that show successful real-world deployment of GNN-based policies on a decentralized multi-robot system relying on Adhoc communication. A video demonstration of this case-study can be found online11youtube.com/watch?v=COh-WLn4i04.

The 17 papers in this special section focus on resilience in networked robotic systems. This collection of articles aims to provide a deeper understanding of resilience as it pertains to multirobot systems, and to disseminate the current advances in designing and operating networked robotic systems. We understand resilience to be a characteristic that enables amultirobot system to withstand or overcome unexpected adverse conditions or shocks, and unknown, unmodeled disturbances. It refers to the contingent nature of the robots’ behaviors that is aimed at preserving their functionality or minimizing the time periods during which their functionality is compromised. The papers explore new algorithmic and mathematical foundations toward resilience.

Recent work in the multi-agent domain has shown the promise of Graph Neural Networks (GNNs) to learn complex coordination strategies. However, most current approaches use minor variants of a Graph Convolutional Network (GCN), which applies a convolution to the communication graph formed by the multi-agent system. In this paper, we investigate whether the performance and generalization of GCNs can be improved upon. We introduce ModGNN, a decentralized framework which serves as a generalization of GCNs, providing more flexibility. To test our hypothesis, we evaluate an implementation of ModGNN against several baselines in the multi-agent flocking problem. We perform an ablation analysis to show that the most important component of our framework is one that does not exist in a GCN. By varying the number of agents, we also demonstrate that an application-agnostic implementation of ModGNN possesses an improved ability to generalize to new environments.

Robotic simulators are crucial for academic research and education as well as the development of safety-critical applications. Reinforcement learning environments— simple simulations coupled with a problem specification in the form of a reward function—are also important to standardize the development (and benchmarking) of learning algorithms. Yet, full-scale simulators typically lack portability and paral-lelizability. Vice versa, many reinforcement learning environments trade-off realism for high sample throughputs in toy-like problems. While public data sets have greatly benefited deep learning and computer vision, we still lack the software tools to simultaneously develop—and fairly compare—control theory and reinforcement learning approaches. In this paper, we propose an open-source OpenAI Gym-like environment for multiple quadcopters based on the Bullet physics engine. Its multi-agent and vision-based reinforcement learning interfaces, as well as the support of realistic collisions and aerodynamic effects, make it, to the best of our knowledge, a first of its kind. We demonstrate its use through several examples, either for control (trajectory tracking with PID control, multi-robot flight with downwash, etc.) or reinforcement learning (single and multi-agent stabilization tasks), hoping to inspire future research that combines control theory and machine learning.

We present an algorithm for the concurrent assignment and planning of collision-free trajectories (DC-CAPT) for robots whose kinematics can be modeled as Dubins cars, i.e., robots constrained in terms of their initial orientation and their minimum turning radius. Coupling the assignment and trajectory planning subproblems allows for a computationally tractable solution. This solution is guaranteed to be collision- free through the use of a single constraint: the start and goal locations have separation distance greater than some threshold. We derive this separation distance by extending a prior work that assumed holonomic robots. We demonstrate the validity of our approach, and show its efficacy through simulations and experiments where groups of robots executing Dubins curves travel to their assigned goal locations without collisions.

This work deals with the problem of planning conflict-free paths for mobile robots in cluttered environments. Since centralized, coupled planning algorithms are computationally intractable for large numbers of robots, we consider decoupled planning, in which robots plan their paths sequentially in order of priority. Choosing how to prioritize the robots is a key consideration. State-of-the-art prioritization heuristics, however, do not model the coupling between a robot's mobility and its environment. This is particularly relevant when prioritizing between robots with different degrees of mobility. In this paper, we propose a prioritization rule that can be computed online by each robot independently, and that provides consistent, conflict-free path plans. Our innovation is to formalize a robot's path prospects to reach its goal from its current location. To this end, we consider the number of homology classes of trajectories, which capture distinct prospects of paths for each robot. This measure is used as a prioritization rule, whenever any robots enter negotiation to deconflict path plans. We perform simulations with heterogeneous robot teams and compare our method to five benchmarks. Our method achieves the highest success rate, and strikes a good balance between makespan and flowtime objectives.

Effective communication is key to successful, decentralized, multi-robot path planning. Yet, it is far from obvious what information is crucial to the task at hand, and how and when it must be shared among robots. To side-step these issues and move beyond hand-crafted heuristics, we propose a combined model that automatically synthesizes local communication and decision-making policies for robots navigating in constrained workspaces. Our architecture is composed of a convolutional neural network (CNN) that extracts adequate features from local observations, and a graph neural network (GNN) that communicates these features among robots. We train the model to imitate an expert algorithm, and use the resulting model online in decentralized planning involving only local communication and local observations. We evaluate our method in simulations by navigating teams of robots to their destinations in 2D cluttered workspaces. We measure the success rates and sum of costs over the planned paths. The results show a performance close to that of our expert algorithm, demonstrating the validity of our approach. In particular, we show our model's capability to generalize to previously unseen cases (involving larger environments and larger robot teams).

This article considers the problem of assigning mobile robots to goals on transport networks with uncertain and potentially correlated information about travel times. Our aim is to produce optimal assignments such that the average waiting time at destinations is minimized. Since noisy travel time estimates result in suboptimal assignments, we propose a method that offers robustness to uncertainty by making use of redundant robot assignments. However, solving the redundant assignment problem optimally is strongly NP-hard. Hence, we exploit the structural properties of our mathematical problem formulation to propose a polynomial-time, near-optimal solution. We demonstrate that our problem can be reduced to minimizing a supermodular cost function subject to a matroid constraint. This allows us to develop a greedy assignment algorithm, for which we derive suboptimality bounds. We demonstrate the effectiveness of our approach with simulations on transport networks with correlated uncertain edge costs and uncertain node positions that lead to noisy travel time estimates. Comparisons to benchmark algorithms show that our method performs near-optimally and significantly better than the nonredundant assignment. Finally, our findings include results on the benefit of diversity and complementarity in redundant robot coalitions; these insights contribute toward providing resilience to uncertainty through the targeted composition of robot coalitions. Note to Practitioners-This article is motivated by the problem of assigning mobile robots (e.g., vehicles and drones) to goals when travel times from robot origins to goal locations are uncertain. Existing robust assignment methods deal with uncertainty by minimizing risk or by predefining acceptable risk thresholds. In this article, we propose a complementary method that offers robustness to uncertainty by making use of robot redundancy. In other words, we assign more robots than necessary to a given goal, in the expectation that one of the redundant robots will reach the goal faster (than the originally assigned robot). However, solving this redundant assignment problem is computationally intractable for large systems. By characterizing the mathematical problem, we show how the redundant assignment problem can be solved efficiently. We apply our assignment algorithm to transport network problems to reduce the average waiting times at goal locations when travel times from vehicle origins to destinations are uncertain and potentially also correlated. Our results show that exploiting robot redundancy is an effective approach to reducing waiting times. In this work, we build on the premise that time is the primary commodity, and we do not explicitly model the additional cost of utilizing redundant robots. Future work should more explicitly address the tradeoff between the cost of providing redundancy (e.g., travel costs and robot costs) and performance gains.

We introduce a unique experimental testbed that consists of a fleet of 16 miniature Ackermann-steering vehicles. We are motivated by a lack of available low-cost platforms to support research and education in multi-car navigation and trajectory planning. This article elaborates the design of our miniature robotic car, the Cambridge Minicar, as well as the fleet's control architecture. Our experimental testbed allows us to implement state-of-the-art driver models as well as autonomous control strategies, and test their validity in a real, physical multi-lane setup. Through experiments on our miniature highway, we are able to tangibly demonstrate the benefits of cooperative driving on multi-lane road topographies. Our setup paves the way for indoor large-fleet experimental research.

We present a method for calibration-free, infrastructure-free localization in sensor networks. Our strategy is to estimate node positions and noise distributions of all links in the network simultaneously - a strategy that has not been attempted thus far. In particular, we account for biased, non-line-of-sight (NLOS) range measurements from ultra-wideband (UWB) devices that lead to multi-modal noise distributions, for which few solutions exist to date. Our approach circumvents cumbersome a-priori calibration, allows for rapid deployment in unknown environments, and facilitates adaptation to changing conditions. Our first contribution is a generalization of the classical multidimensional scaling algorithm to account for measurements that have multi-modal error distributions. Our second contribution is an online approach that iterates between node localization and noise parameter estimation. We validate our method in 3-dimensional networks, (i) through simulation to test the sensitivity of the algorithm on its design parameters, and (ii) through physical experimentation in a NLOS environment. Our setup uses UWB devices that provide time-of-flight measurements, which can lead to positively biased distance measurements in NLOS conditions. We show that our algorithm converges to accurate position estimates, even when initial position estimates are very uncertain, initial error models are unknown, and a significant proportion of the network links are in NLOS.

We present a novel framework for integrity analysis of swarm robotic systems using the symmetric Kullback-Leibler Divergence. The objective is to understand a robot swarm's vulnerability to malicious intrusion and to develop the necessary computational tools that would detect the presence of malicious agents within the swarm. Using ensemble approaches for modeling and analyzing stochastic task allocation, we analyze the performance of the proposed strategy subject to different system parameters, and show how different design choices can facilitate early intrusion detection. We further evaluate the performance of our method in realistic scenarios through stochastic simulations for different team sizes. The main contribution is an analysis framework whose output can be used to avoid system-inherent design flaws and to decrease the damage that can be inflicted by an undetected attacker.

Urban transportation is being transformed by mobility-on-demand (MoD) systems. One of the goals of MoD systems is to provide personalized transportation services to passengers. This process is facilitated by a centralized operator that coordinates the assignment of vehicles to individual passengers, based on location data. However, current approaches assume that accurate positioning information for passengers and vehicles is readily available. This assumption raises privacy concerns. In this work, we address this issue by proposing a method that protects passengers' drop-off locations (i.e., their travel destinations). Formally, we solve a batch assignment problem that routes vehicles at obfuscated origin locations to passenger locations (since origin locations correspond to previous drop-off locations), such that the mean waiting time is minimized. Our main contributions are two-fold. First, we formalize the notion of privacy for continuous vehicle-to-passenger assignment in MoD systems, and integrate a privacy mechanism that provides formal guarantees. Second, we present a polynomial-time iterative version of the Hungarian algorithm to allocate a redundant number of vehicles to a single passenger. This algorithm builds on the insight that even during peak rush hour there are unoccupied (redundant) traveling vehicles. This strategy allows us to reduce the performance deterioration induced by the privacy mechanism. In particular, it enables the exploration of the trade-off between privacy levels, waiting time, and deployed fleet size. We evaluate our methods on a real, large-scale data set consisting of over 11 million taxi rides (specifying vehicle availability and passenger requests), recorded over a month's duration, in the area of Manhattan, New York. Based on current traffic statistics, our evaluations indicate that privacy can be achieved without incurring a significant loss of performance, and that this loss can be further controlled by varying operator or user preferences.

Recent work in the field of bio-inspired robotic systems has introduced designs for modular robots that are able to assemble into structures (e.g., bridges, landing platforms, fences) using their bodies as the building components. Yet, it remains an open question as to how to program large swarms of robotic modules so that the assembly task is performed as efficiently as possible. Moreover, the problem of designing assembly algorithms is compounded by the scale of these systems, and by the lack of centralized guidance in unstructured environments. The main contribution of this work is a decentralized algorithm to assemble structures with modular robots. Importantly, we coordinate the robots so that docking actions can be parallelized. We show the correctness of our algorithm, and we demonstrate its scalability and generality through multiple scenarios in simulation. Experiments on physical robots demonstrate the validity of our approach in real-world settings.

We consider the problem of distributing a large group of heterogeneous robots among a set of tasks that require specialized capabilities in order to be completed. We model the system of heterogeneous robots as a community of species, in which each species (robot type) is defined by the traits (capabilities) that it owns. In order to solve the distribution problem, we develop centralized as well as decentralized methods to efficiently control the heterogeneous swarm of robots. Our methods assume knowledge of the underlying task topology and are based on a continuous model of the system that defines transition rates to and from tasks, for each robot species. Our optimization of the transition rates is fully scalable with respect to the number of robots, number of species, and number of traits. Building on this result, we propose a real-time optimization method that enables an online adaptation of transition rates as a function of the state of the current robot distribution. We also show how the robot distribution can be approximated based on local information only, consequently enabling the development of a decentralized controller. We evaluate our methods by means of microscopic simulations and show how the performance of the latter is well predicted by the macroscopic equations. Importantly, our framework also includes a diversity metric that enables an evaluation of the impact of swarm heterogeneity on performance. The metric defines the notion of minspecies, i.e., the minimum set of species that are required to achieve a given goal. We show that two distinct goal functions lead to two specializations of minspecies, which we term as eigenspecies and coverspecies. Quantitative results show the relation between diversity and performance.

We are interested in a principled study of the impact of diversity in heterogeneous large-scale distributed robotic systems. In order to evaluate the implications of heterogeneity on performance, we consider the concrete problem of distributing a large group of robots among a set of tasks that require specialized capabilities in order to be completed. We model the system of heterogeneous robots as a community of species, where each species (robot type) is defined by the traits (capabilities) that it owns. We develop a continuous model of the system at a macroscopic level, and formulate an optimization problem that produces an optimal set of transition rates for each species, so that the desired trait distribution is reached as quickly as possible. In order to evaluate the effects of heterogeneity, we propose a diversity metric that defines the notion of eigenspecies. We show that our metric correlates with performance: the higher the cardinality of the eigenspecies, the harder it becomes to optimize the system. Our approach is validated over multiple levels of abstraction, and real robot results confirm its validity on physical platforms.

Large numbers of collaborating robots are advantageous for solving distributed problems. In order to efficiently solve the task at hand, the robots often need accurate localization. In this work, we address the localization problem by developing a solution that has low computational and sensing requirements, and that is easily deployed on large robot teams composed of cheap robots. We build upon a real-time, particle-filter based localization algorithm that is completely decentralized and scalable, and accommodates realistic robot assumptions including noisy sensors, and asynchronous and lossy communication. In order to further reduce this algorithm's overall complexity, we propose a low-cost particle clustering method, which is particularly well suited to the collaborative localization problem. Our approach is experimentally validated on a team of ten real robots.

Ultra-wideband (UWB) localization is a recent technology that promises to outperform many indoor localization methods currently available. Yet, non-line-of-sight (NLOS) positioning scenarios can create large biases in the time-difference-of-arrival (TDOA) measurements, and must be addressed with accurate measurement models in order to avoid significant localization errors. In this work, we first develop an efficient, closed-form TDOA error model and analyze its estimation characteristics by calculating the Cramér-Rao lower bound (CRLB). We subsequently detail how an online Expectation Maximization (EM) algorithm is adopted to find an elegant formalism for the maximum likelihood estimate of the model parameters. We perform real experiments on a mobile robot equipped with an UWB emitter, and show that the online estimation algorithm leads to excellent localization performance due to its ability to adapt to the varying NLOS path conditions over time.

Ultra-wideband (UWB) localization is one of the most promising indoor localization methods. Yet, non-line-of-sight (NLOS) positioning scenarios can potentially cause significant localization errors and remain a challenge. In this work, we propose a novel, probabilistic UWB TDOA error model which explicitly takes into account NLOS. In order to validate our approach systematically in a real world setup, we leverage the utility of a group of mobile robots, and introduce our error model into a real-time localization framework run onboard the robots. We subsequently extend our framework by employing a collaborative localization strategy which enables the sharing of inter-robot, relative position observations. Our experimental results show how the novel TDOA error model is able to improve localization performance when information on the LOS/NLOS path condition is available. These results are complemented by additional experiments which show how a collaborative team of robots is able to significantly improve localization performance when no information on the LOS/NLOS path condition is available.

Multi-robot systems can solve complex tasks that require the coordination of the team-member positions with respect to each other. While the development of ad-hoc relative positioning platforms embedding cheap off-the-shelf components is a practical choice, it leads not only to differences between the platforms themselves, but also to a high sensitivity to external factors. In this paper, we present a novel lightweight online calibration method composed of two phases, capable of running on miniature robots with limited computational capabilities. Furthermore, by exploiting a Gaussian process regression in its second phase, the proposed calibration approach is able to capture deviations from an assumed underlying physical model. We compare the performance of our approach with the theoretical Cramér-Rao lower bound and test its efficiency on real robots equipped with range and bearing modules.

This work is situated in the context of collaboratively solving the localization problem for unknown initial conditions. We address this problem with a novel, fully decentralized, real-time particle filter algorithm, designed to accommodate realistic robotic assumptions including noisy sensors, and asynchronous and lossy communication. In particular, we introduce a collaborative reciprocal sampling algorithm which allows a drastic reduction in the number of particles needed to achieve localization. We elaborate an analysis of our reciprocal sampling method and support our conclusions with simulation results. Finally, we validate our approach on a team of four real robots within a controlled experimental setup.

The efficiency of distributed sensor networks depends on an optimal trade-off between the usage of resources and data quality. The work in this paper addresses the problem of optimizing this trade-off in a self-configured distributed robotic sensor network, with respect to a user-defined objective function. We investigate a quadtree network topology and implement a fully distributed threshold-based field estimation algorithm. Simulations with field data as well as real robot experiments are performed, validating our distributed control strategy and evaluating the threshold-based formula for real world scenarios. We propose a theoretical analysis that predicts the system's behavior in real world case studies. The experiments and this prediction show very good correspondence, enabling the accurate employment of the objective function, optimizing the trade-off based on user needs.

Recent substantial progress in the domain of indoor positioning systems and a growing number of indoor location-based applications are creating the need for systematic, efficient, and precise experimental methods able to assess the localization and perhaps also navigation performance of a given device. With hundreds of Khepera III robots in academic use today, this platform has an important potential for single- and multi-robot localization and navigation research. In this work, we develop a necessary set of models for mobile robot navigation with the Khepera III platform, and quantify the robot's localization performance based on extensive experimental studies. Finally, we validate our experimental approach to localization research by considering the evaluation of an ultra-wideband (UWB) positioning system. We successfully show how the robotic platform can provide precise performance analyses, ultimately proposing a powerful approach towards advancements in indoor positioning technology.

In the present study, we are interested in verifying how the progressive addition of constraints on communication and localization impact the performance of a swarm of small robots in shape formation tasks. Identified to be of importance in a swarm-user interaction context, the time required to construct a given spatial configuration is considered as a performance metric. The experimental work reported in this paper starts from global and synchronized localization information, shown to be successful both on a real hardware system and in simulation. In a second step, communication is constrained to a local scale, thus obliging a single designated robot to disseminate the global localization information to the other agents. The reliability of the radio communication channel and its impact upon the performance of the system are considered.