Distributed Autonomous Robotic Systems

We consider the problem of patrolling an assigned area using a team of heterogeneous robots consisting of sentinels and searchers in the presence of stochastic arrivals of attacks. Sentinels and searchers operate using a different sensor model featuring a tradeoff between accuracy and the sensed area. Using an approach based on queuing theory, we derive an accurate analytic characterization of the patrolling performance that can be used to predict the behavior of a given configuration or inform the composition of a team in order to meet a desired target performance. Extensive simulation results corroborate our theoretical findings.

We address the coordination between humans and robots in tasks that involve exploration and reconnaissance with applications to search and rescue. Specifically, we consider the problem of humans and robots cooperatively searching an indoor environment in a distributed manner where we assume that each robot is equipped with sensors that are able to locate targets of interest. Rather than have humans issue explicit commands to and guide robots, we allow humans to make decisions on their own and let the robots adapt to decisions taken by the human. The main contribution of this paper is a framework in which the robots in the team respond and adapt to the behavior of the human agents in the task of exploring and clearing an indoor environment. The central idea is the assignment of robots to homotopy classes that are complementary to the classes being pursued by human agents. By the virtue of the sparse topological representation of the agent trajectories, our algorithm lends itself naturally to a distributed implementation. The framework has three advantages: it (a) ensures that robots and humans pursue different homotopy classes; (b) requires very little communication between the humans and the robots; and (c) allows robots to adapt to human movement without having to model complex human decision-making behaviors. We demonstrate the effectiveness of the proposed algorithm through a distributed implementation on a ROS (Robot Operating System) platform.

We consider the problem of coverage path planning in an initially unknown or partially known planar environment using multiple robots. Previously, Voronoi partitioning has been proposed as a suitable technique for coverage path planning where the free space in the environment is partitioned into non-overlapping regions called Voronoi cells based on the initial positions of the robots, and one robot is allocated to perform coverage in each region. However, a crucial problem arises if such a partitioning scheme is used in an environment where the location of obstacles is not known a priori—while performing coverage, a robot might perceive an obstacle that occludes its access to portions of its Voronoi cell and this obstacle might prevent the robot from completely covering its allocated region. This would either result in portions of the environment remaining uncovered or requires additional path planning by robots to cover the disconnected regions. To address this problem, we propose a novel algorithm that allows robots to coordinate the coverage of inaccessible portions of their Voronoi cell with robots in neighboring Voronoi cells so that they can repartition the initial Voronoi cells and cover a set of contiguous, connected regions. We have proved analytically that our proposed algorithm guarantees complete, non-overlapping coverage. We have also quantified the performance of our algorithm on e-puck robots within the Webots simulator in different environments with different obstacle geometries and shown that it successfully performs complete, non-overlapping coverage.

Although robotic coverage and collision avoidance are active areas of robotics research, the avoidance of collision situations between robots has often been neglected in the context of multi-robot coverage tasks. In fact, for robots of physical size, collisions are likely to happen during deployment and coverage in densely packed multi-robot configurations. For this reason, we aim to motivate by this paper the combined use of multi-robot coverage and reciprocal collision avoidance. We present a taxonomy of collision scenarios in multi-robot coverage problems. In particular, coverage tasks with built-in heterogeneity such as multiple antagonistic objectives or robot constraints are shown to benefit from the combination. Based on our taxonomy, we evaluate four representative robotic use cases in simulation by combining the specific methods of Voronoi coverage and reciprocal velocity obstacles.

In real applications, it is always important to consider the generation of safe paths for robots during deployment or in future excursions through the environment. In order to include safety in the problem of deploying mobile robotic networks, we propose a new strategy based on the locational optimization framework. Our approach models the optimal deployment problem as a constrained optimization problem with inequality and equality constraints. This optimization model is built by incorporating into the locational optimization framework new features such as the classical Generalized Voronoi Diagram (GVD) commonly used as a safe roadmap in the context of path planning and a new metric to compute distance between robots and points in the environment. This new metric induces a new Voronoi partition of the environment. Furthermore, inspired by the classical Dijkstra algorithm, we present a novel efficient distributed algorithm to compute solutions in complicated environments.

The Marsubots fleet is an heterogeneous robot fleet consisting of Marsus and Motherbots, the purpose of this fleet is to explore previously unexplored areas as well as partially explored areas or areas that have suffered alterations. In order to be able to explore large areas such as large buildings and open spaces, the robots need to recharge their batteries from the Motherbot’s recharging bay. This paper focuses on describing the simulation environment MarSim that has been created using NetLogo to model the fleet in order to be able to use tools like Genetic Algorithms to refine the parameters that have been identified as key parameters for the robots to complete the task at hand successfully, specially after a large amount of recharge cycles.

Localization of distributed robots can be improved by fusing the sensor data from each robot collectively in the network. This may allow for each individual robot’s sensor configuration to be reduced while maintaining an acceptable level of uncertainty. However, the scalability of a reduced sensor configuration should be carefully considered lest the propagated error become unbounded in large networks of robots. In this paper, we propose a minimal but scalable sensor configuration for a fleet of vehicles localizing on the urban road. The cooperative localization is proven to be scalable if the sensors’ data are informative enough. The experimental results justify that pose uncertainty will remain at an acceptable level when the number of robots increases.

Cooperative localization allows groups of robots to improve their overall localization by sharing position estimates within the team. In spite of being a well studied problem, very few works deal with the increased complexity when a large number of robots is used, as is the case in robotic swarms. In this paper, we present a characterization and analysis of the cooperative localization problem for robotic swarms. We use a decentralized cooperative mechanism in which robots take turns as dynamic landmarks providing information to their teammates. We perform several simulations and analyze the influence of these dynamic landmarks in the localization. More specifically, we study the impact of the number of robots in the localization and how the choice of landmarks affects the results.

To effectively act on the same physical space, robots must first communicate to share and fuse the map of the area in which they operate. For long-term online operation, the merging of maps from heterogeneous devices must be fast and allow for scalable growth in both the number of clients and the size of the map. This paper presents a system which allows multiple clients to share and merge maps built from a state-of-the-art relative SLAM system. Maps can also be augmented with virtual elements that are consistently shared by all the clients. The visual-inertial mapping framework which underlies this system is discussed, along with the server architecture and novel integrated multi-session loop closure system. We show quantitative results of the system. The map fusion benefits are demonstrated with an example augmented reality application.

This paper presents a novel multi-robot manipulation algorithm which allows a large number of small robots to move a comparatively large object along a desired trajectory to a goal location. The algorithm does not require an explicit communication network among the robots. Instead, the robots coordinate their actions through sensing the motion of the object itself. It is proven that this implicit information is sufficient to synchronize the forces applied by the robots. A leader robot then steers the forces of the synchronized group to manipulate the object through the desired trajectory to the goal. The paper presents algorithms that are proven to control both translational and rotational motion of the object. Simulations demonstrate the approach for two scenarios with 20 robots transporting a rectangular plank and 1000 robots transporting a piano.

We present a scalable distributed path planning algorithm for transporting a large object through an unknown environment using a group of homogeneous robots. The robots are randomly scattered across the terrain and collectively sample the obstacles in the environment in a distributed fashion. Given this sampling and the dimensions of the bounding box of the object, the robots construct a distributed configuration space. We then use a variant of the distributed Bellman-Ford algorithm to construct a shortest-path tree using a custom cost function from the goal location to all other connected robots. The cost function encompasses the work required to rotate and translate the object in addition to an extra control penalty to navigate close to obstacles. Our approach sets up a framework that allows the user to balance the trade-off between the safety of the path and the mechanical work required to move the object. The path is optimal given the sampling of the robots and user input parameters. We implemented our algorithm in both simulated and real-world environments. Our approach is robust to the size and shape of the object and adapts to dynamic environments.

This paper proposes a collective construction method through interaction between simple robots and intelligent blocks that has a rule set and functions to communicate with neighboring blocks. In our proposed method, the structure is formed by growing chain of blocks. The growth direction is determined by the rule set and a counter value passed between the blocks. The robots load or unload the block based on a simple algorithm and a local signal from the blocks. Because of the simplicity of each robot’s behavior, the structure is locally unstable: the blocks can be attached or detached randomly from the structure even if they have already formed a part of the structure. The structure is considered a dynamic equilibrium structure that is locally unstable but globally stable. In this paper, we first explain the mechanism of our proposal and show some fundamental characteristics obtained by computer simulation. Then, we show the adaptability of the system by introducing simple sensing dynamics for an external stimulus.

This paper addresses cooperative manipulation and transportation of any payload shape, by assembling a group of simple mobile robots (denoted m-bots) into a modular poly-robot (p-bot). The focus is made in this paper on the chosen methodology to obtain sub-optimal positioning of the robots around the payload to lift it and to transport it while maintaining a geometric multi-robot formation. This appropriate positioning is obtained by combining the constraint to ensure Force Closure Grasping (FCG) for stable and safe lifting of the payload and the maximization of the Static Stability Margin (SSM) during the transport. A predefined control law is then used to track a virtual structure in which each elementary robot has to keep the desired position relative to the payload. Simulation results for an object of any shape, described by a parametric curve, are presented. Additional 3D simulation results with a multi-body dynamic software validate our proposal.

We present a multi agent collaboration algorithm to recruit an approximate number of individually simple robots with controllable variance. We propose a sigmoid response threshold function motivated by task allocation in social insects, and describe macro-level models backed by micro-level simulations to predict the resulting team sizes and their variance. These results are further validated through physical experiments using the “Droplet” swarm robotics platform. We show that the slope of the response threshold function can be used to control the variance of group size, allowing agents to trade off deterministic team size with coordination speed, and making the proposed mechanism applicable to a variety of applications.

This paper presents a potential game-theoretic interpretation and analysis of a decentralized task allocation algorithm, consensus-based bundled algorithm, which was developed by the authors’ prior work. It is, in particular, proved that the consensus-based bundle algorithm converges to a pure strategy Nash equilibrium of some distributed welfare game, and the price of anarchy and the price of stability of this equilibrium are 1/2 and 1, respectively.

This paper presents an extension to the Hybrid Information and Plan Consensus Algorithm (HIPC) that accounts for imperfect situational awareness (SA). This algorithm uses implicit coordination to plan for a subset of the team on-board each agent, then uses plan consensus to satisfy assignment constraints. By combining the ideas of implicit coordination and local plan consensus, the algorithm empirically reduces the convergence time for distributed task allocation problems. The contribution of this work is that it extends previous results to account for the likely possibility of imperfect situational awareness across the team. This is accomplished by tracking when predictions are incorrect and removing offending predictions if they are hindering algorithmic convergence. Empirical results are provided to demonstrate that this new approach allows the use of inconsistent situational awareness to improve convergence speed.

This paper presents a control architecture for safe and smooth navigation of a group of Unmanned Ground Vehicles (UGV) while keeping a specific formation. The formation control is based on Leader-follower and Behavioral approaches. The proposed control architecture is designed to allow the use of a single control law for different multi-vehicle contexts (navigation in formation, transition between different formation shapes, obstacle avoidance, etc.). The obstacle avoidance strategy is based on the limit-cycle approach while taking into account the dimension of the formation. A new Strategy for Formation Reconfiguration (SFR) of the group of UGVs based on suitable smooth switching of the set-points (according, for instance, to the encountered obstacles or the new task to achieve) is proposed. The inter-vehicles collisions are avoided during the SFR using a penalty function acting on the vehicle velocities. Different simulations on cluttered environments show the performance and the efficiency of the proposal, to obtain fully reactive and distributed control strategy for the navigation in formation of a group of UGVs.

Odor plume tracing is a challenging robotics application, made difficult by the combination of the patchy characteristics of odor distribution and the slow response of the available sensors. This work proposes a graph-based formation control algorithm to coordinate a group of small robots equipped with odor sensors, with the goal of tracing an odor plume to its source. This approach makes it possible to organize the robots in arbitrary and evolving formation shapes with the aim of improving tracing performance. The algorithm was evaluated in a high-fidelity submicroscopic simulator, using different formations and achieving quick convergence and negligible distance overhead in laminar wind flows.

In this paper, we address the problem of visibility-based target tracking for a team of mobile observers trying to track a team of mobile targets. Based on the results of previous work, the notion of pursuit fields around a single corner is introduced. We use the pursuit fields to generate navigation strategies for a single observer to track a single target in general environments. In order to tackle the case when more than one observer or target is present in the environment, we propose a two level hierarchical approach. At the upper level, the team of observers use a ranking and aggregation technique for allocating each target to an observer. At the lower level, each observer computes its navigation strategy based on the results of the single observer-single target problem, thereby, decomposing a large multi-agent problem into several 2-agent problems. Finally, we present a scalable algorithm that can accommodate an arbitrary number of observers and targets. The performance of this algorithm is evaluated based on simulation and implementation.

Underwater gliders are robust ocean sensor platforms characterized by high reliability and endurance. Because of their relatively low speed, the motion of underwater gliders is strongly affected by the ocean current, providing data to estimate the depth averaged flow velocity. The glider computerized tomography (Glider CT) algorithm reconstructs a depth-averaged flow field from the navigation errors accumulated along the glider trajectories. This paper justifies the convergence of the Glider CT algorithm as a row action method solving nonlinear equations previously used for bent-ray ultrasonic CT. The paper also validates the algorithm through experiments where the horizontal motion of underwater gliders under flow is imitated by mobile robots in an indoor lab setting. Both theoretical analysis and experimental results suggest Glider CT as a promising method for marine operations.

Over the recent years, the increasing influence of climate change has given rise to an uncontrolled proliferation of jellyfish in marine habitats, which has visibly damaged many ecosystems, industries, and human health. To resolve this issue, our team developed a robotic system to successfully and efficiently remove jellyfishes, named JEROS (Jellyfish Elimination RObotic Swarm). The JEROS consists of multiple USVs (Unmanned Surface Vehicles) that freely move in a marine environment to scavenge for and eliminate jellyfishes. In this paper, we propose a constrained formation control algorithm that enhances the efficiency of jellyfish removal. Our formation control algorithm is designed in consideration of the characteristic features of JEROS. It is designed to effectively work with the simple leader-follower algorithm. The leader-follower formation control does not work well if a reference path of the leader is generated without considering a minimum turning radius. In order to overcome such a limitation, a new path planning method—angular rate-constrained path planning—is proposed in this paper. The performance of the jellyfish removal function was tested at Masan Bay in the Southern coast of South Korea and formation control tests were conducted at Bang-dong Reservoir in Daejeon, South Korea.

In order for robots to exist together with humans, safety for humans has to be ensured. On the other hand, safety might decrease working efficiency of robots. Namely, this is a trade-off problem between the human safety and robot efficiency in a field of human-robot interaction. For this problem, we propose a novel motion planning technique of multiple mobile robots. Two artificial potentials are presented for generating repulsive force. A behavior potential is provided for humans. A congestion potential is provided for robots. Through simulation experiments, the effectiveness of the behavior and congestion potentials used in the motion planning technique for the human safety and robot efficiency is discussed. Moreover, a sensing system for humans in a real environment is developed. Finally, the significance of the potential generated from the actual human behavior is discussed.

Cooperative pathfinding is often addressed in one of two ways in the literature. In fully coupled approaches, robots are considered together and the plans for all robots are constructed simultaneously. In decoupled approaches, the plans are constructed only for a subset of robots at a time. While decoupled approaches can be much faster than fully coupled approaches, they are often suboptimal and incomplete. Although there exist a few decoupled approaches that achieve completeness, global information (which makes global coordination possible) is assumed. Global information may not be accessible in distributed robotic systems. In this paper, we provide a window-based approach to cooperative pathfinding with limited sensing and communication range in distributed systems (called DisCoF). In DisCoF, robots are assumed to be fully decoupled initially, and may gradually increase the level of coupling in an online and distributed fashion. In some cases, e.g., when global information is needed to solve the problem instance, DisCoF would eventually couple all robots together. DisCoF represents an inherently online approach since robots may only be aware of a subset of robots in the environment at any given point of time. Hence, they do not have enough information to determine non-conflicting plans with all the other robots. Completeness analysis of DisCoF is provided.

This work studies conflict avoidance between moving, non-communicating agents with minimum sensing information. While safety can be provided by reactive obstacle avoidance methods for holonomic systems, deadlock avoidance requires reasoning over different homotopic paths in cluttered scenes. A method to compute the “interaction cost” of a path is proposed, which considers only the neighboring agents’ observed positions. Minimizing the interaction cost in a prototypical challenge with two agents moving through two corridors from opposing sides guarantees the selection of non-conflicting paths. More complex scenes, however, are more challenging. This leads to a study of alternatives for decentralized path selection. Simulations indicate that following a “minimum-conflict” path given the other agents’ observed positions provides deadlock avoidance. A scheme that selects between the minimum-conflict path and a set of shortest paths given their interaction cost improves path quality while still achieving deadlock avoidance. Finally, learning to select between the minimum-conflict and one of the shortest paths allows agents to be adaptive to the behavior of their neighbors and can be achieved using regret minimization.

This work investigates the application of boundary control of the wave equation to achieve leader-induced formation control of a multi-robot network with a chain topology. In contrast to previous related work on controlling formations of single integrator agents, we consider a model for double integrator agents. For trajectory planning, we use the flatness based method for assigning trajectories to leader agents so that the agents’ trajectories and control inputs are computed in a decentralized way. We show how the approximation greatly simplifies the planning problem and the resulting synthesized controls are bounded and independent of the number of agents in the network. We validate our formation control approach with simulations of 100 and 1000 agents that converge to configurations on three different type of target curves.

We consider the problem of synthesizing controllers automatically for distributed robots that are loosely coupled using a formal synthesis approach. Formal synthesis entails construction of game strategies for a discrete transition system such that the system under the strategy satisfies a specification, given for instance in linear temporal logic (LTL). The general problem of automated synthesis for distributed discrete transition systems suffers from state-space explosion because the combined state-space has size exponential in the number of subsystems. Motivated by multi-robot motion planning problems, we focus on distributed systems whose interaction is nearly decoupled, allowing the overall specification to be decomposed into specifications for individual subsystems and a specification about the joint system. We treat specifically reactive synthesis for the GR(1) fragment of LTL. Each robot is subject to a GR(1) formula, and a safety formula describes constraints on their interaction. We propose an approach wherein we synthesize strategies independently for each subsystem; then we patch the separate controllers around interaction regions such that the specification about the joint system is satisfied.

This paper presents a framework, called the knowledge co-creation framework (KCF), for the heterogeneous multi-robot transfer learning method with utilization of cloud-computing resources. A multi-agent robot system (MARS) that utilizes reinforcement learning and transfer learning methods has recently been deployed in real-world situations. In MARS, autonomous agents obtain behavior autonomously through multi-agent reinforcement learning and the transfer learning method enables the reuse of the knowledge of other robots’ behavior, such as for cooperative behavior. These methods, however, have not been fully and systematically discussed. To address this, KCF leverages the transfer learning method and cloud-computing resources. In prior research, we developed a hierarchical transfer learning (HTL) method as the core technology of knowledge co-creation and investigated its effectiveness in a dynamic multi-agent environment. The HTL method hierarchically abstracts obtained knowledge by ontological methods. Here, we evaluate the effectiveness of HTL with two types of ontology: action and state.

Swarm robotics aims to achieve physical flexibility, overall system robustness, and enhanced reliability and efficiency by employing a group of autonomous robots for collective task performance. Achieving collective performance by individual robots with limited sensing, processing, and communication capabilities, however, faces several technical challenges, such as difficulties in establishing reliable communication and decentralized control among the robots. This paper presents the following wireless communication algorithms that can be applied to homogeneous swarm robots: (1) infrared-based short-distance communication between the adjacent robots using a self-synchronization technique; and (2) long-distance communication and localization based on distance measurement using radio signals. In addition, two decentralized global shape formation algorithms for homogeneous swarm robots are presented for simulating dispersion and line formation collectively achieved by homogeneous swarm robots.

We study the problems of throughput optimisation of mobile sensor networks. A network of mobile sensor nodes equipped with limited sensing and communication capabilities for connectivity maintenance and measurement of quality of communication links with the nearest neighbours is deployed to exploit and collect environmental data. Communication throughput of the multi-hop ad-hoc network of mobile sensor nodes is maximised for fast and reliable data transmission from sources to destinations. We propose a method of designing the distributed control for mobile sensor nodes for throughput optimisation in two stages: (1) position-aware optimisation and (2) communication-aware optimisation. We demonstrate effectiveness of the method through Monte-Carlo simulation based statistical results.

This paper describes detection and notification of component failures in distributed component-based robot applications using the blackboard architecture. The blackboard architecture monitors each component of robot applications in order to detect component failures at runtime and it identifies the causes of failures. Using the dependency relationships between components, the blackboard architecture performs impact analysis between components so that it determines the scope of failure notification in the components of a distributed robot application. The notification messages delivered to components can trigger actions against the failures if robot application developers have implemented the actions along with application functions. The prototype of blackboard architecture has been implemented for the Microsoft Robotics Developer Studio (MSRDS) environment, and it has been applied to the Unmanned Ground Vehicle (UGV) application implemented on the simulator as a case study.

An important aspect of successful locomotion in Modular Self-reconfigurable Robots (MSRs) is to be able to autonomously coordinate the movement of the modules so that the robot can move towards the goal. We consider the locomotion problem in a partially distributed setting where multiple MSRs (disconnected groups of connected modules) are within the communication range of each other and modules do not have a priori information about other modules that belong to the same configuration. Coordinating the movement of modules in such a setting becomes a challenging problem because of the limited perception and computation resources available on each module. To address these problems, we propose a strategy that first combines neighbor-to-neighbor message passing techniques via infrared and wireless communication to enable each module to autonomously determine the set of modules that belong to the same MSR. The strategy then uses a distributed leader election algorithm to identify the leader, which thereafter coordinates the actions of the modules in its configuration. We have verified the performance of our approach using an accurately simulated model of the ModRED MSR within the Webots simulator and in the embedded system of ModRED (This work was done as part of the ModRED project which is supported by NASA EPSCoR grant no. NNH11ZHA003C.). It is shown that our strategy can successfully determine the set of connected modules, elect a leader for each configuration and coordinate the locomotion of MSRs for different numbers of modules.

Human motor behavior can be generated by distributed system. In this study, human standing-up motion is focused as an important daily activity. Especially, 13 muscle activation of lower body and trunk measured during human standing-up motion is decomposed into small numbers of modules of synchronized muscle activation called muscle synergy. Moreover human musculoskeletal model is developed with four rigid body segments based on dynamics and anatomical characteristics of human body. Forward dynamic simulation with the developed model showed that four muscle synergies had their own contribution toward body function: bending forward, moving the center of mass forward, extending whole body, and decelerating the center of mass. Results also indicated that combinations of four modules of synchronized muscle activation could generate human standing-up motion rather than controlling individual muscles.