We present an empirical study of the relationship between map connectivity and the empirical hardness of the multi-agent pathfinding (MAPF) problem. By analyzing the second smallest eigenvalue (commonly known as lambda2) of the normalized Laplacian matrix of different maps, our initial study indicates that maps with smaller lambda2 tend to create more challenging instances when agents are generated uniformly randomly. Additionally, we introduce a map generator based on Quality Diversity (QD) that is capable of producing maps with specified lambda2 ranges, offering a possible way for generating challenging MAPF instances. Despite the absence of a strict monotonic correlation with lambda2 and the empirical hardness of MAPF, this study serves as a valuable initial investigation for gaining a deeper understanding of what makes a MAPF instance hard to solve.

We consider a large-scale multi-robot path planning problem in a cluttered environment. Our approach achieves real-time replanning by dividing the workspace into cells and utilizing a hierarchical planner. Specifically, we propose novel multi-commodity flow-based high-level planners that route robots through cells with reduced congestion, along with an anytime low-level planner that computes collision-free paths for robots within each cell in parallel. A highlight of our method is a significant improvement in computation time. Specifically, we show empirical results of a 500-times speedup in computation time compared to the baseline multi-agent pathfinding approach on the environments we study. We account for the robot’s embodiment and support non-stop execution with continuous replanning. We demonstrate the real-time performance of our algorithm with up to 142 robots in simulation, and a representative 32 physical Crazyflie nanoquadrotor experiment.

Solving Multi-Agent Path Finding (MAPF) problems optimally is known to be NP-Hard for both make-span and total arrival time minimization. Many algorithms have been developed to solve MAPF problems optimally and they all have different strengths and weaknesses. There is no dominating MAPF algorithm that works well in all types of problems and no standard guidelines for when to use which algorithm. Therefore, there is a need for developing an automatic algorithm selector that suggests the best optimal algorithm to use given a MAPF problem instance. We propose a model based on convolutions and inception modules by treating the input MAPF instance as an image. We further show that techniques such as single-agent shortest path annotation and graph embedding are very effective for improving training quality. We evaluate our model and show that it outperforms all individual algorithms in its portfolio, as well as an existing state-of-the-art MAPF algorithm selector.

We are interested in learning models of non-stationary environments, which can be framed as a multitask learning problem. Model-free reinforcement learning algorithms can achieve good asymptotic performance in multitask learning at a cost of extensive sampling, due to their approach, which requires learning from scratch. While model-based approaches are among the most data efficient learning algorithms, they still struggle with complex tasks and model uncertainties. Meta-reinforcement learning addresses the efficiency and generalization challenges on multi task learning by quickly leveraging the meta-prior policy for a new task. In this paper, we propose a meta-reinforcement learning approach to learn the dynamic model of a non-stationary environment to be used for meta-policy optimization later. Due to the sample efficiency of model-based learning methods, we are able to simultaneously train both the meta-model of the non-stationary environment and the meta-policy until dynamic model convergence. Then, the meta-learned dynamic model of the environment will generate simulated data for meta-policy optimization. Our experiment demonstrates that our proposed method can meta-learn the policy in a non-stationary environment with the data efficiency of model-based learning approaches while achieving the high asymptotic performance of model-free meta-reinforcement learning.

For multiple robots performing exploration in a previously unmapped environment, such as planetary exploration, maintaining accurate localization and building a consistent map are vital. If the robots do not have a map to localize against and do not explore the same area, they may not be able to find visual loop closures to constrain their relative poses, making traditional SLAM impossible. This paper presents a method for using UWB ranging sensors in multi-robot SLAM, which allows the robots to localize and build a map together even without visual loop closures. The ranging measurements are added to the pose graph as edges and used in optimization to estimate the robots' relative poses. This method builds a map using all robots' observations that is consistent and usable. It performs similarly to visual loop closures when they are available, and provides a good map when they are not, which other methods cannot do. The method is demonstrated on PUFFER robots, developed for autonomous planetary exploration, in an unstructured environment.

The Multi-Agent Pickup and Delivery (MAPD) problem models applications where a large number of agents attend to a stream of incoming pickup-and-delivery tasks. Token Passing (TP) is a recent MAPD algorithm that is efficient and effective. We make TP even more efficient and effective by using a novel combinatorial search algorithm, called Safe Interval Path Planning with Reservation Table (SIPPwRT), for single-agent path planning. SIPPwRT uses an advanced data structure that allows for fast updates and lookups of the current paths of all agents in an online setting. The resulting MAPD algorithm TP-SIPPwRT takes kinematic constraints of real robots into account directly during planning, computes continuous agent movements with given velocities that work on non-holonomic robots rather than discrete agent movements with uniform velocity, and is complete for wellformed MAPD instances. We demonstrate its benefits for automated warehouses using both an agent simulator and a standard robot simulator. For example, we demonstrate that it can compute paths for hundreds of agents and thousands of tasks in seconds and is more efficient and effective than existing MAPD algorithms that use a post-processing step to adapt their paths to continuous agent movements with given velocities.

For robots with different types of sensors, loop closure in a multi-robot SLAM scenario requires keypoints that can be matched between sensor measurement point clouds with different properties such as point density and noise. In this paper, we evaluate the performance of several 3D keypoint detectors (Harris3D, ISS, KPQ, KPQ-SI, and NARF) for repeatability between scans from different sensors towards building a heterogeneous multi-robot SLAM system. We find that KPQ-SI and NARF have the best relative repeatability, with KPQ-SI finding more keypoints overall and a higher number of repeatable keypoints, at the cost of significantly worse computational performance. In scans of the same area from different poses, both detectors find enough keypoints for point cloud registration and loop closure. For heterogenous multirobot SLAM applications with computational or bandwidth restrictions, the NARF detector consistently finds repeatable keypoints while also allowing for real-time performance.

Quadrotor stabilizing controllers often require careful, model-specific tuning for safe operation. We use reinforcement learning to train policies in simulation that transfer remarkably well to multiple different physical quadrotors. Our policies are low-level, i.e., we map the rotorcrafts' state directly to the motor outputs. The trained control policies are very robust to external disturbances and can withstand harsh initial conditions such as throws. We show how different training methodologies (change of the cost function, modeling of noise, use of domain randomization) might affect flight performance. To the best of our knowledge, this is the first work that demonstrates that a simple neural network can learn a robust stabilizing low-level quadrotor controller (without the use of a stabilizing PD controller) that is shown to generalize to multiple quadrotors. The video of our experiments can be found at https://sites.google.com/view/sim-to-multi-quad.

The Multi-Agent Pickup and Delivery (MAPD) problem models applications where a large number of agents attend to a stream of incoming pickup-and-delivery tasks. Token Passing (TP) is a recent MAPD algorithm that is efficient and effective. We make TP even more efficient and effective by using a novel combinatorial search algorithm, called Safe Interval Path Planning with Reservation Table (SIPPwRT), for single-agent path planning. SIPPwRT uses an advanced data structure that allows for fast updates and lookups of the current paths of all agents in an online setting. The resulting MAPD algorithm TP-SIPPwRT takes kinematic constraints of real robots into account directly during planning, computes continuous agent movements with given velocities that work on non-holonomic robots rather than discrete agent movements with uniform velocity, and is complete for well-formed MAPD instances. We demonstrate its benefits for automated warehouses using both an agent simulator and a standard robot simulator. For example, we demonstrate that it can compute paths for hundreds of agents and thousands of tasks in seconds and is more efficient and effective than existing MAPD algorithms that use a post-processing step to adapt their paths to continuous agent movements with given velocities. This paper was published at AAAI 2019.

An upcoming frontier for distributed computing might literally save lives in future military operations. In civilian scenarios, significant efficiencies were gained from interconnecting devices into networked services and applications that automate much of everyday life from smart homes to intelligent transportation. The ecosystem of such applications and services is collectively called the Internet of Things (IoT). Can similar benefits be gained in a military context by developing an IoT for the battlefield? This paper describes unique challenges in such a context as well as potential risks, mitigation strategies, and benefits.

We describe a trajectory planning method for heterogeneous mobile robot teams in known environments. We consider two core problems that arise with heterogeneous robot teams: asymmetric inter-robot collision constraints and varying dynamic limits. Asymmetric collision constraints are important for close-proximity flight of rotorcraft due to the downwash effect, which complicates spatial coordination. Varying dynamic limits complicate temporal coordination between robots and must be taken into account during planning. Our method builds upon a hybrid planner that combines graph-planning techniques with trajectory optimization and scales well to large homogeneous robot teams. We extend the hybrid planning approach to include the additional spatial and temporal coordination to support heterogeneous teams. Our method scales well with the number of robots and robot types and we demonstrate our approach on a team of 15 physical robots of 4 different types, including quadrotors and differential drive robots.

We present the Intelligent Robotic IoT System (IRIS), a modular, portable, scalable, and open-source testbed for robotic wireless network research. There are two key features that separate IRIS from most of the state-of-the-art multi-robot testbeds. (1)Portability: IRIS does not require a costly static global positioning system such as a VICON system nor time-intensive vision-based SLAM for its operation. Designed with an inexpensive Time Difference of Arrival (TDoA)localization system with centimeter level accuracy, the IRIS testbed can be deployed in an arbitrary uncontrolled environment in a matter of minutes. (2)Programmable Wireless Communication Stack: IRIS comes with a modular programmable low-power IEEE 802.15.4 radio and IPv6 network stack on each node. For the ease of administrative control and communication, we also developed a lightweight publish-subscribe overlay protocol called ROMANO that is used for bootstrapping the robots (also referred to as the IRISbots), collecting statistics, and direct control of individual robots, if needed. We detail the modular architecture of the IRIS testbed design along with the system implementation details and localization performance statistics.

Collaboration between two or more geographically dispersed teams has applications in research and training. In many cases specialized devices, such as robots, may need to be combined between the collaborating groups. However, it would be expensive or even impossible to collocate them at a single physical location. We describe the design of a mixed reality test bed which allows dispersed humans and physically embodied agents to collaborate within a single virtual environment. We demonstrate our approach using Unity's networking architecture as well as open source robot software and hardware. In our scenario, a total of 3 humans and 6 drones must move through a narrow doorway while avoiding collisions in the physical spaces as well as virtual space.

This paper addresses combinatorial problems that arise in multirobot battery exchange systems. The multirobot battery exchange system addressed herein is characterized by two types of robots: task robots that provide services at requested locations and delivery robots that deliver charged batteries to task robots when required. Combinatorial problems arising in these systems involve multiple aspects of resource scheduling and path planning that make them more complex than wellknown combinatorial problems studied in operations research. We present several heuristic algorithms for solving these combinatorial problems. Our algorithms are inspired by techniques used in artificial intelligence and the design of approximation algorithms. We demonstrate the performance of our algorithms in simulation and analyze how they scale with increasing size of the multirobot system.

We describe a method for multirobot trajectory planning in known, obstacle-rich environments. We demonstrate our approach on a quadrotor swarm navigating in a warehouse setting. Our method consists of following three stages: 1) roadmap generation that generates sparse roadmaps annotated with possible interrobot collisions; 2) discrete planning that finds valid execution schedules in discrete time and space; 3) continuous refinement that creates smooth trajectories. We account for the downwash effect of quadrotors, allowing safe flight in dense formations. We demonstrate computational efficiency in simulation with up to 200 robots and physical plausibility with an experiment on 32 nano-quadrotors. Our approach can compute safe and smooth trajectories for hundreds of quadrotors in dense environments with obstacles in a few minutes.

We define a system architecture for a large swarm of miniature quadcopters flying in dense formation indoors. The large number of small vehicles motivates novel design choices for state estimation and communication. For state estimation, we develop a method to reliably track many small rigid bodies with identical motion-capture marker arrangements. Our communication infrastructure uses compressed one-way data flow and supports a large number of vehicles per radio. We achieve reliable flight with accurate tracking (<; 2 cm mean position error) by implementing the majority of computation onboard, including sensor fusion, control, and some trajectory planning. We provide various examples and empirically determine latency and tracking performance for swarms with up to 49 vehicles.

Multi-Agent Path Finding (MAPF) is well studied in both AI and robotics. Given a discretized environment and agents with assigned start and goal locations, MAPF solvers from AI find collision-free paths for hundreds of agents with user-provided sub-optimality guarantees. However, they ignore that actual robots are subject to kinematic constraints (such as velocity limits) and suffer from imperfect plan-execution capabilities. We therefore introduce MAPF-POST to postprocess the output of a MAPF solver in polynomial time to create a plan-execution schedule that can be executed on robots. This schedule works on non-holonomic robots, considers kinematic constraints, provides a guaranteed safety distance between robots, and exploits slack to avoid time-intensive replanning in many cases. We evaluate MAPF-POST in simulation and on differential-drive robots, showcasing the practicality of our approach.

We describe a method for formation-change trajectory planning for large quadrotor teams in obstacle-rich environments. Our method decomposes the planning problem into two stages: a discrete planner operating on a graph representation of the workspace, and a continuous refinement that converts the non-smooth graph plan into a set of Ck-continuous trajectories, locally optimizing an integral-squared-derivative cost. We account for the downwash effect, allowing safe flight in dense formations. We demonstrate the computational efficiency in simulation with up to 200 robots and the physical plausibility with an experiment with 32 nano-quadrotors. Our approach can compute safe and smooth trajectories for hundreds of quadrotors in dense environments with obstacles in a few minutes.

We have conducted two investigations on the ability of human participants to solve challenging collective coordination tasks in a distributed fashion with limited perception and communication capabilities similar to those of a simple ground robot. In these investigations, participants were gathered in a laboratory of networked workstations and were given a series of different collective tasks with varying communication and perception capabilities. Here, we focus on our latest investigation and describe our methodology, platform design considerations, and highlight some interesting observed behaviors. These investigations are the preliminary phase in designing a formal strategy for learning human-inspired behaviors for solving complex distributed multirobot problems, such as pattern formation.

In this paper, we study the Complex Routing Problem (CRP), where several homogeneous robots need to visit given task locations to accomplish complex tasks in a cooperative setting. Each task location hosts a task. The complexity level of a task is defined as the number of robots that need to be simultaneously present at its location to accomplish it. The robots need to be routed so that all tasks get accomplished with minimal makespan. We present a new centralized algorithm, called SAGL, for solving the CRP heuristically. SAGL is inspired by the application of linear programming duality to the Steiner Forest Problem. It makes less restrictive assumptions than the state-of-the-art distributed Approach with Reaction Functions and scales better in both the complexity levels of tasks and the number of complex tasks (whose complexity levels are greater than one), although it results in somewhat larger makespans.

When tracking multiple targets with autonomous cameras for 3D scene reconstruction, e.g., in sports, a significant challenge is handling the unpredictable nature of the targets' motion. Such a monitoring system must reposition according to the targets' movements and maintain satisfactory coverage of the targets. We propose an approximate, centralized approach for maximizing the visible boundary of dynamic targets using mobile cameras in a bounded 2D environment. Targets and obstacles translate, rotate, and deform independently, and cameras are only aware of the current position and shape of the targets and obstacles. Using current information, the environment is searched for better viewing positions, then cameras navigate to those positions while avoiding collisions with targets and obstacles. We present a benchmark and metrics to evaluate the performance of our method, and compare our approach to a simple gradient-based local method in several real-time simulations.

We study formation change for robot groups in known environments. We are given a team of robots partitioned into groups, where robots in the same group are interchangeable with each other. A formation specifies the locations occupied by each group. The objective is to find collision-free paths that move all robots from a given start formation to a given goal formation. Our algorithm TAPF* has the following features: (a) it incorporates kinematic constraints of robots in form of velocity limits; (b) it maintains a user-specified safety distance between robots; (c) it attempts to minimize the makespan; and (d) it runs efficiently for hundreds of robots and dozens of groups even in dense 3D environments with narrow corridors and other occlusions. We demonstrate the efficiency and effectiveness of TAPF* in simulation and on robots.

Mixed Reality can be a valuable tool for research and development in robotics. In this work, we refine the definition of Mixed Reality to accommodate seamless interaction between physical and virtual objects in any number of physical or virtual environments. In particular, we show that Mixed Reality can reduce the gap between simulation and implementation by enabling the prototyping of algorithms on a combination of physical and virtual objects, including robots, sensors, and humans. Robots can be enhanced with additional virtual capabilities, or can interact with humans without sharing physical space. We demonstrate Mixed Reality with three representative experiments, each of which highlights the advantages of our approach. We also provide a testbed for Mixed Reality with three different virtual robotics environments in combination with the Crazyflie 2.0 quadcopter.

We consider the problem of deploying a team of robots in an unknown, obstructed environment to form a multi-hop communication network. As a solution, we present a unified framework, onLinE rObotic Network formAtion (LEONA), that is general enough to permit optimizing the communication network for different utility functions in non-convex environments. LEONA adopts the principle of “optimism in the face of uncertainty” to allow the team of robots to form optimal network configurations efficiently and rapidly without having to map link qualities in the entire area. We demonstrate and evaluate this framework on two specific scenarios concerning the formation of a multi-hop communication path between fixed end-points: one minimizing the total path cost, and another maximizing the bottleneck communication rate. Our simulation-based evaluation shows that the use of the optimism principle can significantly reduce resources spent in exploring and mapping the entire region prior to network optimization. We also present a mathematical modeling of how the searched area scales with various relevant parameters in each case.

We present a novel end-to-end solution for distributed multirobot coordination that translates multitouch gestures into low-level control inputs for teams of robots. Highlighting the need for a holistic solution to the problem of scalable human control of multirobot teams, we present a novel control algorithm with provable guarantees on the robots' motion that lends itself well to input from modern tablet and smartphone interfaces. Concretely, we develop an iOS application in which the user is presented with a team of robots and a bounding box (prism). The user carefully translates and scales the prism in a virtual environment; these prism coordinates are wirelessly transferred to our server and then received as input to distributed onboard robot controllers. We develop a novel distributed multirobot control policy which provides guarantees on convergence to a goal with distance bounded linearly in the number of robots, and avoids interrobot collisions. This approach allows the human user to solve the cognitive tasks such as path planning, while leaving precise motion to the robots. Our system was tested in simulation and experiments, demonstrating its utility and effectiveness.

We consider the problem of task assignment for a multi-robot system where each robot must attend to one or more queues of tasks. We assume that individual robots have no knowledge of tasks in the environment that are not in their queue. Robots in communication with each other may share information about active tasks and exchange queues to achieve lower cost for the system. We show that allowing this kind of task switching causes tasks to be completed more efficiently. In addition, we present conditions under which queues can be guaranteed to make progress, and we support these claims with simulation and experimental results. This work has potential applications in manufacturing, environmental exploration, and pickup-delivery tasks.

Multirobot path planning and task assignment are traditionally treated separately, however task assignment can greatly impact the difficulty of the path planning problem, and the ultimate quality of solution is dependent upon both. We introduce task reassignment, an approach to optimally solving the coupled task assignment and path planning problems. We show that task reassignment improves solution quality, and reduces planning time in some situations.

We address the problem of developing feedback controllers for a group of robots with second-order dynamics in an obstacle-filled, D-dimensional environment. Our control algorithm takes into account communication constraints, obstacle avoidance, and inter-robot collision avoidance, by synthesizing a piecewise smooth vector field for safe navigation. First, the feasible free joint configuration space is tessellated into polytopes that account for the desired constraints. We search the graph of these polytopes to find a discrete path to the goal polytope. We then use a novel navigation function-based feedback controller that drives the system from one polytope to the next and eventually to the goal. The controller exploits the fact that two adjoining polytopes in the planned discrete path together form a star-shaped object that is obstacle free; this enables the design of navigation function-based controller for kinematic and dynamic fully actuated robots without spurious minima. We sequentially compose these controllers to drive the state to the goal. For a polygonal space, the algorithm we propose is complete. We present successful simulation results of the algorithm on a group of ground vehicles and quadrotors performing a cooperative navigation task in constrained environments.

We address the problem of controlling a formation of robots in a cluttered environment. Instead of explicitly controlling the relative positions between the robots and the environment, we construct a lower-dimensional abstraction of the group that establishes a boundary for the group. We then synthesize feedback controllers that allow the abstracted group to navigate a two-dimensional environment to a desired goal position, while automatically adapting the shape of the boundary as well as the position and orientation of the group to avoid collisions between the virtual boundary and the environment. In contrast to previous approaches, we address the planning and control problems concurrently and are naturally able to establish bounds on the positions of the robots through the abstraction. The complexity of the method is independent of the number of robots which promises scalability to large teams.

We propose a method for synthesizing decentralized feedback controllers for a team of multiple heterogeneous agents navigating a known environment with obstacles. The controllers are designed to drive agents with limited team state information to goal sets while avoiding collisions and maintaining specified proximity constraints. The method, its successful application to nonholonomic agents in dynamic simulation and experimentation, and its limitations are presented in this paper.

We propose a method for synthesizing decentralized feedback controllers for a team of multiple heterogeneous agents navigating a known environment with obstacles. The controllers are designed to drive agents with limited team state information to goal sets while avoiding collisions and maintaining specified proximity constraints. The method, its successful application to nonholonomic agents in dynamic simulation, and its limitations are presented in this paper.