A semantically-informed multirobot system for exploration of relevant areas in search and rescue settings

Coordinated multirobot exploration involves autonomous discovering and mapping of the features of initially unknown environments by using multiple robots. Autonomously exploring mobile robots are usually driven, both in selecting locations to visit and in assigning them to robots, by knowledge of the already explored portions of the environment, often represented in a metric map. In the literature, some works addressed the use of semantic knowledge in exploration, which, embedded in a semantic map, associates spatial concepts (like ‘rooms’ and ‘corridors’) with metric entities, showing its effectiveness in improving the total area explored by robots. In this paper, we build on these results and propose a system that exploits semantic information to push robots to explore relevant areas of initially unknown environments, according to a priori information provided by human users. Discovery of relevant areas is significant in some search and rescue settings, in which human rescuers can instruct robots to search for victims in specific areas, for example in cubicles if a disaster happened in an office building during working hours. We propose to speed up the exploration of specific areas by using semantic information both to select locations to visit and to determine the number of robots to allocate to those locations. In this way, for example, more robots could be assigned to a candidate location in a corridor, so the attached rooms can be explored faster. We tested our semantic-based multirobot exploration system within a reliable robot simulator and we evaluated its performance in realistic search and rescue indoor settings with respect to state-of-the-art approaches.     

Robotic experience companionship in music listening and video watching

We propose the notion of robotic experience companionship (REC): a person’s sense of sharing an experience with a robot. Does a robot’s presence and response to a situation affect a human’s understanding of the situation and of the robot, even without direct human–robot interaction? We present the first experimental assessment of REC, studying people’s experience of entertainment media as they share it with a robot. Both studies use an autonomous custom-designed desktop robot capable of performing gestures synchronized to the media. Study I (\(n=67\)), examining music listening companionship, finds that the robot’s dance-like response to music causes participants to feel that the robot is co-listening with them, and increases their liking of songs. The robot’s response also increases its perceived human character traits. We find REC to be moderated by music listening habits, such that social listeners were more affected by the robot’s response. Study II (\(n=91\)), examining video watching companionship supports these findings, demonstrating that social video viewers enjoy the experience more with the robot present, while habitually solitary viewers do not. Also in line with Study I, the robot’s response to the video clip causes people to attribute more positive human character traits to the robot. This has implications for robots as companions for digital media consumption, but also suggests design implications based on REC for other shared experiences with personal robots.     

Motion in ambiguity: Coordinated active global localization for multiple robots

The task of the robot in localization is to find out where it is, through sensing and motion. In environments which possess relatively few features that enable a robot to unambiguously determine its location, global localization algorithms can result in ‘multiple hypotheses’ locations of a robot. This is inevitable with global localization algorithms, as the local environment seen by a robot repeats at other parts of the map. Thus, for effective localization, the robot has to be actively guided to those locations where there is a maximum chance of eliminating most of the ambiguous states — which is often referred to as ‘active localization’. When extended to multi-robotic scenarios where all robots possess more than one hypothesis of their position, there is an opportunity to do better by using robots, apart from obstacles, as ‘hypotheses resolving agents’. The paper presents a unified framework which accounts for the map structure as well as measurement amongst robots, while guiding a set of robots to locations where they can singularize to a unique state. The strategy shepherds the robots to places where the probability of obtaining a unique hypothesis for a set of multiple robots is a maximum. Another aspect of framework demonstrates the idea of dispatching localized robots to locations where they can assist a maximum of the remaining unlocalized robots to overcome their ambiguity, named as ‘coordinated localization’. The appropriateness of our approach is demonstrated empirically in both simulation & real-time (on Amigo-bots) and its efficacy verified. Extensive comparative analysis portrays the advantage of the current method over others that do not perform active localization in a multi-robotic sense. It also portrays the performance gain by considering map structure and robot placement to actively localize over methods that consider only one of them or neither. Theoretical backing stems from the proven completeness of the method for a large category of diverse environments.     

Decentralized Motion Planning for Multiple Mobile Robots: The Cocktail Party Model

This paper presents an approach for decentralized real-time motion planning for multiple mobile robots operating in a common 2-dimensional environment with unknown stationary obstacles. In our model, a robot can see (sense) the surrounding objects. It knows its current and its target's position, is able to distinguish a robot from an obstacle, and can assess the instantaneous motion of another robot. Other than this, a robot has no knowledge about the scene or of the paths and objectives of other robots. There is no mutual communication among the robots; no constraints are imposed on the paths or shapes of robots and obstacles. Each robot plans its path toward its target dynamically, based on its current position and the sensory feedback; only the translation component is considered for the planning purposes. With this model, it is clear that no provable motion planning strategy can be designed (a simple example with a dead-lock is discussed); this naturally points to heuristic algorithms. The suggested strategy is based on maze-searching techniques. Computer simulation results are provided that demonstrate good performance and a remarkable robustness of the algorithm (meaning by this a virtual impossibility to create a dead-lock in a random scene).     

Reducing the Range of Perception in Multi-agent Patrolling Strategies

Multi-Agent Patrolling Problems consist in moving agents throughout a graph in order to optimize a collective performance metric. Some strategies from the literature tackle this problem by dispatching decentralized autonomous agents that coordinate themselves merely by sensing and writing information in the nodes. In this work, they are called k-range local strategies, were k indicates the range, in number of edges, of the agents’ sensing capabilities. The 1-range strategies (where agents can sense up to its neighbor nodes) are certainly the most common case in the literature. And only few 0-range strategies (where agents can only sense its current node) were found, although this type of strategy has the advantage of requiring simpler hardware, when applied in the design of real robots. In this work, we propose two higher-level procedures to reduce the perception range of 1-range strategies to 0: the Zr Method and the EZr Method. Applying both methods in 1-range strategies found in the literature, we created twenty new 0-range strategies, which were evaluated in a simulation experiment described and analyzed here. We also developed a prototype of a low-cost patrolling robot that is able to run the 0-range strategies proposed in this work.     

The Freeze-Tag Problem: How to Wake Up a Swarm of Robots

An optimization problem that naturally arises in the study of swarm robotics is the Freeze-Tag Problem (FTP) of how to awaken a set of "asleep" robots, by having an awakened robot move to their locations. Once a robot is awake, it can assist in awakening other slumbering robots. The objective is to have all robots awake as early as possible. While the FTP bears some resemblance to problems from areas in combinatorial optimization such as routing, broadcasting, scheduling, and covering, its algorithmic characteristics are surprisingly different. We consider both scenarios on graphs and in geometric environments. In graphs, robots sleep at vertices and there is a length function on the edges. Awake robots travel along edges, with time depending on edge length. For most scenarios, we consider the offline version of the problem, in which each awake robot knows the position of all other robots. We prove that the problem is NP-hard, even for the special case of star graphs. We also establish hardness of approximation, showing that it is NP-hard to obtain an approximation factor better than 5/3, even for graphs of bounded degree. These lower bounds are complemented with several positive algorithmic results, including: · We show that the natural greedy strategy on star graphs has a tight worst-case performance of 7/3 and give a polynomial-time approximation scheme (PTAS) for star graphs. · We give a simple O(log δ)-competitive online algorithm for graphs with maximum degree δ and locally bounded edge weights. · We give a PTAS, running in nearly linear time, for geometrically embedded instances.     

Analyzing the Multiple-target-multiple-agent Scenario Using Optimal Assignment Algorithms

This work considers the problem of maximum utilization of a set of mobile robots with limited sensor-range capabilities and limited travel distances. The robots are initially in random positions. A set of robots properly guards or covers a region if every point within the region is within the effective sensor range of at least one vehicle. We wish to move the vehicles into surveillance positions so as to guard or cover a region, while minimizing the maximum distance traveled by any vehicle. This problem can be formulated as an assignment problem, in which we must optimally decide which robot to assign to which slot of a desired matrix of grid points. The cost function is the maximum distance traveled by any robot. Assignment problems can be solved very efficiently. Solution times for one hundred robots took only seconds on a Silicon Graphics Crimson workstation. The initial positions of all the robots can be sampled by a central base station and their newly assigned positions communicated back to the robots. Alternatively, the robots can establish their own coordinate system with the origin fixed at one of the robots and orientation determined by the compass bearing of another robot relative to this robot. This paper presents example solutions to the multiple-target-multiple-agent scenario using a matching algorithm. Two separate cases with one hundred agents in each were analyzed using this method. We have found these mobile robot problems to be a very interesting application of optimal assignment algorithms, and we expect this to be a fruitful area for future research.     

Pheromone Robotics

We describe techniques for coordinating the actions of large numbers of small-scale robots to achieve useful large-scale results in surveillance, reconnaissance, hazard detection, and path finding. We exploit the biologically inspired notion of a virtual pheromone, implemented using simple transceivers mounted atop each robot. Unlike the chemical markers used by insect colonies for communication and coordination, our virtual pheromones are symbolic messages tied to the robots themselves rather than to fixed locations in the environment. This enables our robot collective to become a distributed computing mesh embedded within the environment, while simultaneously acting as a physical embodiment of the user interface. This leads to notions of world-embedded computation and world-embedded displays that provide different ways to think about robot colonies and the types of distributed computations that such colonies might perform.     

Optimal Deterministic Protocols for Mobile Robots on a Grid

This paper studies a system of m robots operating in a set of n work locations connected by aisles in a × grid, where m≤n. From time to time the robots need to move along the aisles, in order to visit disjoint sets of locations. The movement of the robots must comply with the following constraints: (1) no two robots can collide at a grid node or traverse a grid edge at the same time; (2) a robot's sensory capability is limited to detecting the presence of another robot at a neighboring node. We present a deterministic protocol that, for any small constant ε>0, allows m≤(1-ε)n robots to visit their target locations in O( ) time, where each robot visits no more than d≤n targets and no target is visited by more than one robot. We also prove a lower bound showing that our protocol is optimal. Prior to this paper, no optimal protocols were known for d>1. For d=1, optimal protocols were known only for m≤ , while for general m≤n only a suboptimal randomized protocol was known.     

Mechanism and Convergence Analysis of a Multi-Robot Swarm Approach Based on Natural Selection

The Darwinian Particle Swarm Optimization (DPSO) is an evolutionary algorithm that extends the Particle Swarm Optimization (PSO) using natural selection, or survival-of-the-fittest, to enhance the ability to escape from local optima. An extension of the DPSO to multi-robot applications has been recently proposed and denoted as Robotic Darwinian PSO (RDPSO), benefiting from the dynamical partitioning of the whole population of robots. Therefore, the RDPSO decreases the amount of required information exchange among robots, and is scalable to large populations of robots. This paper presents a stability analysis of the RDPSO to better understand the relationship between the algorithm parameters and the robot’s convergence. Moreover, the analysis of the RDPSO is further extended for real robot constraints (e.g., robot dynamics, obstacles and communication constraints) and experimental assessment with physical robots. The optimal parameters are evaluated in groups of physical robots and a larger population of simulated mobile robots for different target distributions within larger scenarios. Experimental results show that robots are able to converge regardless of the RDPSO parameters within the defined attraction domain. However, a more conservative parametrization presents a significant influence on the convergence time. To further evaluate the herein proposed approach, the RDPSO is further compared with four state-of-the-art swarm robotic alternatives under simulation. It is observed that the RDPSO algorithm provably converges to the optimal solution faster and more accurately than the other approaches.     

Coordination of multiple mobile robots with limited communication range in pursuit of single mobile target in cluttered environment

This paper addresses the problem of coordinating multiple mobile robots in searching for and capturing a mobile target, with the aim of reducing the capture time. Compared with the previous algorithms, we assume that the target can be detected by any robot and captured successfully by two or more robots. In this paper, we assume that each robot has a limited communication range. We maintain the robots within a mobile network to guarantee the successful capture. In addition, the motion of the target is modeled and incorporated into directing the motion of the robots to reduce the capture time. A coordination algorithm considering both aspects is proposed. This algorithm can greatly reduce the expected time of capturing the mobile target. Finally, we validate the algorithm by the simulations and experiments.     

A Framework for Augmented Reality using Non-Central Catadioptric Cameras

This paper proposes a strategy for a group of swarm robots to self-assemble into a single articulated(legged) structure in response to terrain difficulties during autonomous exploration. These articulated structures will have several articulated legs or backbones, so they are well suited to walk on difficult terrains like animals. There are three tasks in this strategy: exploration, self-assembly and locomotion. We propose a formation self-assembly method to improve self-assembly efficiency. At the beginning, a swarm of robots explore the environment using their sensors and decide whether to self-assemble and select a target configuration from a library to form some robotic structures to finish a task. Then, the swarm of robots will execute a self-assembling task to construct the corresponding configuration of an articulated robot. For the locomotion, with joint actuation from the connected robots, the articulated robot generates locomotive motions. Based on Sambot that are designed to unite swarm mobile and self-reconfigurable robots, we demonstrate the feasibility for a varying number of swarm robots to self-assemble into snake-like and multi-legged robotic structures. Then, the effectiveness and scalability of the strategy are discussed with two groups of experiments and it proves the formation self-assembly is more efficient in the end.     

Perpetual Robot Swarm: Long-Term Autonomy of Mobile Robots Using On-the-fly Inductive Charging

Swarm robotics studies the intelligent collective behaviour emerging from long-term interactions of large number of simple robots. However, maintaining a large number of robots operational for long time periods requires significant battery capacity, which is an issue for small robots. Therefore, re-charging systems such as automated battery-swapping stations have been implemented. These systems require that the robots interrupt, albeit shortly, their activity, which influences the swarm behaviour. In this paper, a low-cost on-the-fly wireless charging system, composed of several charging cells, is proposed for use in swarm robotic research studies. To determine the system’s ability to support perpetual swarm operation, a probabilistic model that takes into account the swarm size, robot behaviour and charging area configuration, is outlined. Based on the model, a prototype system with 12 charging cells and a small mobile robot, Mona, was developed. A series of long-term experiments with different arenas and behavioural configurations indicated the model’s accuracy and demonstrated the system’s ability to support perpetual operation of multi-robotic system.     

Value-based action selection for observation with robot teams using probabilistic techniques

We present an approach for directing next-step movements of robot teams engaged in mapping objects in their environment: Move Value Estimation for Robot Teams (MVERT). Resulting robot paths tend to optimize vantage points for all robots on the team by maximizing information gain. At each step, each robot selects a movement to maximize the utility (in this case, reduction in uncertainty) of its next observation. Trajectories are not guaranteed to be optimal, but team behavior serves to maximize the team's knowledge since each robot considers the observational contributions of team mates. MVERT is evaluated in simulation by measuring the resulting uncertainty about target locations compared to that obtained by robots acting without regard to team mate locations and to that of global optimization over all robots for each single step. Additionally, MVERT is demonstrated on physical teams of robots. The qualitative behavior of the team is appropriate and close to the single-step optimal set of trajectories.     

Vision-based remote control of cellular robots

This paper describes the development and design of a vision-based remote controlled cellular robot. Cellular robots have numerous applications in industrial problems where simple inexpensive robots can be used to perform different tasks that involve covering a large working space. As a methodology, the robots are controlled based on the visual input from one or more cameras that monitor the working area. As a result, a robust control of the robot trajectory is achieved without depending on the camera calibration. The remote user simply specifies a target point in the image to indicate the robot final position.

We describe the complete system at various levels: the visual information processing, the robot characteristics and the closed loop control system design, including the stability analysis when the camera location is unknown. Results are presented and discussed.

In our opinion, such a system may have a wide spectrum of applications in industrial robotics and may also serve as an educational testbed for advanced students in the fields of vision, robotics and control.     

Probabilistic network formation through coverage and freeze-tag

We address the problem of propagating a piece of information among robots scattered in an environment. Initially, a single robot has the information. This robot searches for other robots to pass it along. When a robot is discovered, it can participate in the process by searching for other robots. Since our motivation for studying this problem is to form an ad hoc network, we call it the Network Formation Problem. In this paper, we study the case where the environment is a rectangle and the robots’ locations are unknown but chosen uniformly at random. We present an efficient network formation algorithm, Stripes, and show that its expected performance is within a logarithmic factor of the optimal performance. We also compare Stripes with an intuitive network formation algorithm in simulations. The feasibility of Stripes is demonstrated with a proof-of-concept implementation.     

Coordinated multi-robot exploration

In this paper, we consider the problem of exploring an unknown environment with a team of robots. As in single-robot exploration the goal is to minimize the overall exploration time. The key problem to be solved in the context of multiple robots is to choose appropriate target points for the individual robots so that they simultaneously explore different regions of the environment. We present an approach for the coordination of multiple robots, which simultaneously takes into account the cost of reaching a target point and its utility. Whenever a target point is assigned to a specific robot, the utility of the unexplored area visible from this target position is reduced. In this way, different target locations are assigned to the individual robots. We furthermore describe how our algorithm can be extended to situations in which the communication range of the robots is limited. Our technique has been implemented and tested extensively in real-world experiments and simulation runs. The results demonstrate that our technique effectively distributes the robots over the environment and allows them to quickly accomplish their mission.     

Cooperative exploration based on supervisory control of multi-robot systems

When multiple mobile robots cooperatively explore an unknown environment, the advantages of robustness and redundancy are guaranteed. However, available traditional economy approaches for coordination of multi-robot systems (MRS) exploration lack efficient target selection strategy under a few of situations and rely on a perfect communication. In order to overcome the shortages and endow each robot autonomy, a novel coordinated algorithm based on supervisory control of discrete event systems and a variation of the market approach is proposed in this paper. Two kinds of utility and the corresponding calculation schemes which take into account of cooperation between robots and covering the environment in a minimal time, are defined. Different moving target of each robot is determined by maximizing the corresponding utility at the lower level of the proposed hierarchical coordinated architecture. Selection of a moving target assignment strategy, dealing with communication failure, and collision avoidance are modeled as behaviors of each robot at the upper level. The proposed approach distinctly speeds up exploration process and reduces the communication requirement. The validity of our algorithm is verified by computer simulations.     

Decentralized Coordinated Tracking with Mixed Discrete–Continuous Decisions

In this paper, we study the problem of dynamically positioning a team of mobile robots for target tracking. We treat the coordination of mobile robots for target tracking as a joint team optimization to minimize uncertainty in target state estimates over a fixed horizon. The optimization is inherently a function of both the positioning of robots in continuous space and the assignment of robots to targets in discrete space. Thus, the robot team must make decisions over discrete and continuous variables. In contrast to methods that decouple target assignments and robot positioning, our approach avoids the strong assumption that a robot's utility for observing a target is independent of other robots’ observations. We formulate the optimization as a mixed integer nonlinear program and apply integer relaxation to develop an approximate solution in decentralized form. We demonstrate our coordinated multirobot tracking algorithm both in simulation and using a pair of mobile robotic sensor platforms to track moving pedestrians. Our results show that coupling target assignment and robot positioning realizes coordinated behaviors that are not possible with decoupled methods.