Robotic swarms are decentralized multi-robot systems whose members use local information from proximal neighbors to execute simple reactive control laws that result in emergent collective behaviors. In contrast, members of a general multi-robot system may have access to global information, all-to-all communication or sophisticated deliberative collaboration. Some algorithms in the literature are applicable to robotic swarms. Others require the extra complexity of general multi-robot systems. Given an application domain, a system designer or supervisory operator must choose an appropriate system or algorithm respectively that will enable them to achieve their goals while satisfying mission constraints (e.g, bandwidth, energy, time limits). In this paper, we compare representative swarm and general multi-robot algorithms in two application domains - navigation and dynamic area coverage - with respect to several metrics (e.g, completion time, distance travelled). Our objective is to characterize each class of algorithms to inform offline system design decisions by engineers or online algorithm selection decisions by supervisory operators. Our contributions are (a) an empirical performance comparison of representative swarm and general multi-robot algorithms in two application domains, (b) a comparative analysis of the algorithms based on the theory of information invariants, which provides a theoretical characterization supported by our emnirical results.

The interaction between swarm robots and human operators is significantly different from the traditional humanrobot interaction due to unique characteristics of the system, such as high cognitive complexity and difficulties in state estimation. In this paper, we concentrated on the method of conveying input from the operator to the swarm. Previous research has shown that control through switching between behaviors offers the greatest flexibility but is particularly difficult for human operators. A recently developed method for finding optimal sequences for composing behaviors offered a potential tool for aiding human operators controlling swarms through behavior switching. This paper compared participants performing a navigation task with and without the availability of the optimal sequencing aid. Results showed that the task of preplanning a sequence of behaviors and durations appeared more difficult for participants than switching between executing behaviors to navigate. Users who used the aid frequently was found to create shorter paths than infrequent users and the control group. In the trails that the aid was used, participants tended to generate more complicated sequences and achieve the first attempt more rapidly, compared to the trails that the aid was not used.

We consider the general problem of moving a large number of networked robots toward a goal position through a cluttered environment while preserving network communication connectivity and avoiding both inter-robot collisions and collision with obstacles. In contrast to previous approaches that either plan complete paths for each individual robot in the high-dimensional joint configuration space or control the robot group as a whole with explicit constraints on the group's boundary and inter-robot pairwise distance, we propose a novel decentralized online behavior-based algorithm that relies on the topological structure of the multi-robot communication and sensing graphs to solve this problem. We formally describe the communication graph as a simplicial complex that enables robots to iteratively identify the frontier nodes and coordinate forward motion through the sensing graph. This approach is proved to automatically deform robot teams for collision avoidance and always preserve connectivity. The effectiveness of our approach is demonstrated using numerical simulations. The algorithm is shown to scale linearly in the number of robots.

Robotic swarms are distributed systems that exhibit global behaviors arising from local interactions between individual robots. Each robot can be programmed with several local control laws that can be activated depending on an operator's choice of global swarm behavior. While some simple behaviors (e.g. rendezvous) with guaranteed performance on known objectives under strict assumptions have been studied in the literature, real missions occur in uncontrolled environments with dynamically arising objectives and require combinations of behaviors. Given a library of swarm behaviors, a supervisory operator commanding the swarm must choose a sequence of behaviors to execute in order to accomplish a particular task during a mission composed of many dynamically arising tasks. In this paper, we formalize the problem of finding an optimal behavior sequence to maximize swarm performance on a complex task. Given the swarm behavior library, a set of decision time points and a performance criterion, we present an informed search algorithm that computes the maximum performance behavior sequence. The algorithm is proven to be optimal and complete. A relevant modification is presented that generates bounded suboptimal solutions more quickly. We apply the algorithm to a swarm navigation application and a dynamic area coverage application, demonstrating the utility of our algorithm even in situations where the behaviors in the library have not been designed for the task at hand.

In many multi-robot applications such as target search, environmental monitoring and reconnaissance, the multi-robot system operates semi-autonomously, but under the supervision of a remote human who monitors task progress. In these applications, each robot collects a large amount of task-specific data that must be sent to the human periodically to keep the human aware of task progress. It is often the case that the human-robot communication links are extremely bandwidth constrained and/or have significantly higher latency than inter-robot communication links, so it is impossible for all robots to send their task-specific data together. Thus, only a subset of robots, which we call the knowledge leaders, can send their data at a time. In this paper, we study the knowledge leader selection problem, where the goal is to select a subset of robots with a given cardinality that transmits the most informative task-specific data for the human. We prove that the knowledge leader selection is a submodular function maximization problem under explicit conditions and present a novel distributed submodular optimization algorithm that has the same approximation guarantees as the centralized greedy algorithm. The effectiveness of our approach is demonstrated using numerical simulations.

In many scenarios involving human interaction with a remote swarm, the human operator needs to be periodically updated with state information from the robotic swarm. A complete representation of swarm state is high dimensional and perceptually inaccessible to the human. Thus, a summary representation is often required. In addition, it is often the case that the human-swarm communication channel is extremely bandwidth constrained and may have high latency. This motivates the need for the swarm itself to compute a summary representation of its own state for transmission to the human operator. The summary representation may be generated by selecting a subset of robots, known as the information leaders, whose own states suffice to give a bounded approximation of the entire swarm, even in the presence of uncertainty. In this paper, we propose two fully distributed asynchronous algorithms for information leader selection that only rely on inter-robot local communication. In particular, by representing noisy robot states as error ellipsoids with tunable confidence level, the information leaders are selected such that the Minimum-Volume Covering Ellipsoid (MVCE) summarizes the noisy swarm state boundary. We provide bounded optimality analysis and proof of convergence for the algorithms. We present simulation results demonstrating the performance and effectiveness of the proposed algorithms.

Robotic swarms are distributed systems whose members interact via local control laws to achieve a variety of behaviors, such as flocking. In many practical applications, human operators may need to change the current behavior of a swarm from the goal that the swarm was going towards into a new goal due to dynamic changes in mission objectives. There are two related but distinct capabilities needed to supervise a robotic swarm. The first is comprehension of the swarm's state and the second is prediction of the effects of human inputs on the swarm's behavior. Both of them are very challenging. Prior work in the literature has shown that inserting the human input as soon as possible to divert the swarm from its original goal towards the new goal does not always result in optimal performance (measured by some criterion such as the total time required by the swarm to reach the second goal). This phenomenon has been called Neglect Benevolence, conveying the idea that in many cases it is preferable to neglect the swarm for some time before inserting human input. In this paper, we study how humans can develop an understanding of swarm dynamics so they can predict the effects of the timing of their input on the state and performance of the swarm. We developed the swarm configuration shape-changing Neglect Benevolence Task as a Human Swarm Interaction (HSI) reference task allowing comparison between human and optimal input timing performance in control of swarms. Our results show that humans can learn to approximate optimal timing and that displays which make consensus variables perceptually accessible can enhance performance.

Robotic swarms are distributed systems whose members interact via local control laws to achieve different behaviors. Practical missions may require a combination of different swarm behaviors, where these behavioral combinations are not known a priori but could arise dynamically due to changes in mission goals. Therefore, human interaction with the swarm (HIS) is needed. In this paper, we introduce, formally define and characterize a novel concept, Neglect Benevolence, that captures the idea that it may be beneficial for system performance if the human operator, after giving a command, waits for some time before giving a subsequent command to the swarm. This raises the important question of the existence and means of calculation of the optimal time for the operator to give input to the swarm in order to optimize swarm behavior. Human operators are limited in their ability to estimate the best time to give input to the swarm. Therefore, automated aids that calculate the optimal input time could help the human operator achieve the best system performance. Our contributions are as follows. First, we formally define the new notion of Neglect Benevolence. Second, we prove the existence of Neglect Benevolence for a class of linear dynamical systems. Third, we provide an analytic characterization and an algorithm for calculating the optimal input time. Fourth, we apply the analysis to the human control of swarm configuration.

In this paper, we present both centralized and distributed algorithms for aligning coordinate frames in multi-robot systems based on inter-robot relative position measurements. Robot orientations are not measured, but are computed by our algorithms. Our algorithms are robust to measurement error and are useful in applications where a group of robots need to establish a common coordinate frame based on relative sensing information. The problem of establishing a common coordinate frame is formulated in a least squares error framework minimizing the total inconsistency of the measurements. We assume that robots that can sense each other can also communicate with each other. In this paper, our key contribution is a novel asynchronous distributed algorithm for multi-robot coordinate frame alignment that does not make any assumptions about the sensor noise model. After minimizing the least squares error (LSE) objective for coordinate frame alignment of two robots, we develop a novel algorithm that out-performs state-of-the-art centralized optimization algorithms for minimizing the LSE objective. Furthermore, we prove that for multi-robot systems (a) with redundant noiseless relative sensing information, we will achieve the globally optimal solution (this is non-trivial because the LSE objective is non-convex for our problem), (b) with noisy information but no redundant sensing (e.g. sensing graph has a tree topology), our algorithm will optimally minimize the LSE objective. We also present preliminary results of the real-world performance of our algorithm on TurtleBots equipped with Kinect sensors.