Evolving controllers for autonomous robot search teams

Deploying autonomous robot teams instead of humans in hazardous search and rescue missions could provide immeasurable benefits. In such operations, rescue workers often face environments where information about the physical conditions is impossible to obtain, which not only hampers the efficiency and effectiveness of the effort, but also places the rescuers in life-threatening situations. These types of risk promote the potential for using robot search teams in place of humans. This article presents the design and implementation of controllers to provide robots with appropriate behavior. The effective utilization of genetic algorithms to evolve controllers for teams of homogeneous autonomous robots for area coverage in search and rescue missions is described, along with a presentation of a robotic simulation program which was designed and developed. The main objective of this study was to contribute to efforts which attempt to implement real-world robotic solutions for search and rescue missions.     

Using Virtual Pheromones and Cameras for Dispersing a Team of Multiple Miniature Robots

To safely and efficiently guide personnel of search and rescue operations in disaster areas, swift gathering of relevant information such as the locations of victims, must occur. Using the concept of ‘repellent virtual pheromones’ inspired by insect colony coordination behaviors, miniature robots can be quickly dispersed to survey a disaster site. Assisted by visual servoing, dispersion of the miniature robots can quickly cover an area. An external observer such as another robot or an overhead camera is brought into the control loop to provide each miniature robot estimations of the positions of all of the other near-by robots in the robotic team. These miniature robots can then move away from the other near-by robots on the team, resulting in the robot collective becoming swiftly distributed through the local area. The technique has been simulated with differing pheromone persistence levels and implemented using the miniature Scout robots, developed by the Center for Distributed Robotics at the University of Minnesota, which are well-suited to surveillance and reconnaissance missions.     

Lifelong Adaptation in Heterogeneous Multi-Robot Teams: Response to Continual Variation in Individual Robot Performance

Generating teams of robots that are able to perform their tasks over long periods of time requires the robots to be responsive to continual changes in robot team member capabilities and to changes in the state of the environment and mission. In this article, we describe the L-ALLIANCE architecture, which enables teams of heterogeneous robots to dynamically adapt their actions over time. This architecture, which is an extension of our earlier work on ALLIANCE, is a distributed, behavior-based architecture aimed for use in applications consisting of a collection of independent tasks. The key issue addressed in L-ALLIANCE is the determination of which tasks robots should select to perform during their mission, even when multiple robots with heterogeneous, continually changing capabilities are present on the team. In this approach, robots monitor the performance of their teammates performing common tasks, and evaluate their performance based upon the time of task completion. Robots then use this information throughout the lifetime of their mission to automatically update their control parameters. After describing the L-ALLIANCE architecture, we discuss the results of implementing this approach on a physical team of heterogeneous robots performing proof-of-concept box pushing experiments. The results illustrate the ability of L-ALLIANCE to enable lifelong adaptation of heterogeneous robot teams to continuing changes in the robot team member capabilities and in the environment.     

Control sharing in human-robot team interaction

The interaction between humans and robot teams is highly relevant in many application domains, for example in collaborative manufacturing, search and rescue, and logistics. It is well-known that humans and robots have complementary capabilities: Humans are excellent in reasoning and planning in unstructured environments, while robots are very good in performing tasks repetitively and precisely. In consequence, one of the key research questions is how to combine human and robot team decision making and task execution capabilities in order to exploit their complementary skills. From a controls perspective this question boils down to how control should be shared among them. This article surveys advances in human-robot team interaction with special attention devoted to control sharing methodologies. Additionally, aspects affecting the control sharing design, such as human behavior modeling, level of autonomy and human-machine interfaces are identified. Open problems and future research directions towards joint decision making and task execution in human-robot teams are discussed.     

Exploration strategies based on multi-criteria decision making for searching environments in rescue operations

Some applications require autonomous robots to search an initially unknown environment for static targets, without any a priori information about environment structure and target locations. Targets can be human victims in search and rescue or materials in foraging. In these scenarios, the environment is incrementally discovered by the robots exploiting exploration strategies to move around in an autonomous and effective way. Most of the strategies proposed in literature are based on the idea of evaluating a number of candidate locations on the frontier between the known and the unknown portions of the environment according to ad hoc utility functions that combine different criteria. In this paper, we show some of the advantages of using a more theoretically-grounded approach, based on Multi-Criteria Decision Making (MCDM), to define exploration strategies for robots employed in search and rescue applications. We implemented some MCDM-based exploration strategies within an existing robot controller and we evaluated their performance in a simulated environment.     

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.     

Adequate motion simulation and collision detection for soccer playing humanoid robots

In this paper a humanoid robot simulator based on the multi-robot simulation framework (MuRoSimF) is presented. Among the unique features of this simulator is the scalability in the level of physical detail in both the robot’s motion and sensing systems. It facilitates the development of control software for humanoid robots which is demonstrated for several scenarios from the RoboCup Humanoid Robot League.Different requirements exist for a humanoid robot simulator. E.g., testing of algorithms for motion control and postural stability require high fidelity of physical motion properties whereas testing of behavior control and role distribution for a robot team requires only a moderate level of detail for real-time simulation of multiple robots. To meet such very different requirements often different simulators are used which makes it necessary to model a robot multiple times and to integrate different simulations with high-level robot control software.MuRoSimF provides the capability of exchanging the simulation algorithms used for each robot transparently, thus allowing a trade-off between computational performance and fidelity of the simulation. It is therefore possible to choose different simulation algorithms which are adequate for the needs of a given simulation experiment, for example, motion simulation of humanoid robots based on kinematical, simplified dynamics or full multi-body system dynamics algorithms. In this paper also the sensor simulation capabilities of MuRoSimF are revised. The methods for motion simulation and collision detection and handling are presented in detail including an algorithm which allows the real-time simulation of the full dynamics of a 21 DOF humanoid robot. Merits and drawbacks of the different algorithms are discussed in the light of different simulation purposes. The simulator performance is measured and illustrated in various examples, including comparison with experiments of a physical humanoid robot.     

Team NimbRo at MBZIRC 2017: Fast landing on a moving target and treasure hunting with a team of micro aerial vehicles

The Mohamed Bin Zayed International Robotics Challenge (MBZIRC) 2017 has defined ambitious new benchmarks to advance the state‐of‐the‐art in autonomous operation of ground‐based and flying robots. This study covers our approaches to solve the two challenges that involved micro aerial vehicles (MAV). Challenge 1 required reliable target perception, fast trajectory planning, and stable control of an MAV to land on a moving vehicle. Challenge 3 demanded a team of MAVs to perform a search and transportation task, coined “Treasure Hunt,” which required mission planning and multirobot coordination as well as adaptive control to account for the additional object weight. We describe our base MAV setup and the challenge‐specific extensions, cover the camera‐based perception, explain control and trajectory‐planning in detail, and elaborate on mission planning and team coordination. We evaluated our systems in simulation as well as with real‐robot experiments during the competition in Abu Dhabi. With our system, we—as part of the larger team NimbRo—won the MBZIRC Grand Challenge and achieved a third place in both subchallenges involving flying robots.     

Trial by fire [rescue robots]

On September 11, 2001, the Center for Robot-Assisted Search and Rescue (CRASAR) responded within six hours to the World Trade Center (WTC) disaster; this is the first known use of robots for urban search and rescue (USAR). The University of South Florida (USF) was one of the four robot teams, and the only academic institution represented. The USF team participated onsite in the search efforts from 12-21 September 2001, collecting and archiving data on the use of all robots, in addition to actively fielding robots. This article provides an overview of the use of robots for USAR, concentrating on what robots were actually used and why. It describes the roles that the robots played in the response and the impact of the physical environment on the platforms. The quantitative and qualitative performance of the robots are summarized in terms of their components (mobility, sensors, control, communications, and power) and within the larger human-robot system. Lessons learned are offered and a synopsis of the current state of rescue robotics and activities at the CRASAR concludes the article.     

Swarm robotics search & rescue: A novel artificial intelligence-inspired optimization approach

In this paper, a novel heuristic algorithm is proposed to solve continuous non-linear optimization problems. The presented algorithm is a collective global search inspired by the swarm artificial intelligent of coordinated robots. Cooperative recognition and sensing by a swarm of mobile robots have been fundamental inspirations for development of Swarm Robotics Search & Rescue (SRSR). Swarm robotics is an approach with the aim of coordinating multi-robot systems which consist of numbers of mostly uniform simple physical robots. The ultimate aim is to emerge an eligible cooperative behavior either from interactions of autonomous robots with the environment or their mutual interactions between each other. In this algorithm, robots which represent initial solutions in SRSR terminology have a sense of environment to detect victim in a search & rescue mission at a disaster site. In fact, victim’s location refers to global best solution in SRSR algorithm. The individual with the highest rank in the swarm is called master and remaining robots will play role of slaves. However, this leadership and master position can be transitioned from one robot to another one during mission. Having the supervision of master robot accompanied with abilities of slave robots for sensing the environment, this collaborative search assists the swarm to rapidly find the location of victim and subsequently a successful mission. In order to validate effectiveness and optimality of proposed algorithm, it has been applied on several standard benchmark functions and a practical electric power system problem in several real size cases. Finally, simulation results have been compared with those of some well-known algorithms. Comparison of results demonstrates superiority of presented algorithm in terms of quality solutions and convergence speed.     

The World robot summit disaster robotics category – achievements of the 2018 preliminary competition

The World Robot Summit is a robot Olympics and aims to be held in a different country every four years from 2020. The concept of the Plant Disaster Prevention challenge is daily inspections, checks, and emergency response in industrial plants, and in this competition, robots must carry out these types of missions in a mock-up plant. The concept of the Tunnel Disaster Response and Recovery challenge is emergency response to tunnel disasters, and is a simulation competition whereby teams compete to show their ability to deal with disasters, by collecting information and removing debris. The Standard Disaster Robotics challenge assesses, in the form of a contest, the standard performance levels of a robot that are necessary for disaster prevention and emergency response. The World Robot Summit Preliminary Competition was held at Tokyo Big Sight in October 2018, and 36 teams participated in the Disaster Robotics Category. UGVs and UAVs contended the merits of new technology for solving complex problems, using core technologies such as mobility, sensing, recognition, performing operations, human interface, autonomous intelligence etc., as well as system integration and implementation of strategies for completing missions, gaining high-level results.     

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.     

Combining Simulation and Reality in Evolutionary Robotics

Evolutionary Robotics (ER) is a promising methodology, intended for the autonomous development of robots, in which their behaviors are obtained as a consequence of the structural coupling between robot and environment. It is essential that there be a great amount of interaction to generate complex behaviors. Thus, nowadays, it is common to use simulation to speed up the learning process; however simulations are achieved from arbitrary off-line designs, rather than from the result of embodied cognitive processes. According to the reality gap problem, controllers evolved in simulation usually do not allow the same behavior to arise once transferred to the real robot. Some preliminary approaches for combining simulation and reality exist in the ER literature; nonetheless, there is no satisfactory solution available. In this work we discuss recent advances in neuroscience as a motivation for the use of environmentally adapted simulations, which can be achieved through the co-evolution of robot behavior and simulator. We present an algorithm in which only the differences between the behavior fitness obtained in reality versus that obtained in simulations are used as feedback for adapting a simulation. The proposed algorithm is experimentally validated by showing the successful development and continuous transference to reality of two complex low-level behaviors with Sony AIBO¹ robots: gait optimization and ball-kicking behavior. ¹AIBO is a trademark of Sony Corporation     

Real-time exploration of a multi-robot rescue system in disaster areas

A system procedure is proposed for a multi-robot rescue system that performs real-time exploration over disaster areas. Real-time exploration means that every robot exploring the area always has a communication path to human operators standing by at a base station and that the communication path is configured by ad hoc wireless networking. Real-time exploration is essential in multi-robot systems for USAR (urban search and rescue) because operators must communicate with every robot to support the victim detection process and ad hoc networking is suitable to configure a communication path among obstacles. The proposed system procedure consists of the autonomous classification of robots into search and relay types and behavior algorithms for each class of robot. Search robots explore the areas and relay robots act as relay terminals between search robots and the base station. The rule of the classification and the behavior algorithm refer to the forwarding table of each robot constructed for ad hoc networking. The table construction is based on DSDV (destination-sequenced distance vector) routing that informs each robot of its topological position in the network and other essentials. Computer simulations are executed with a specific exploration strategy of search robots. The results show that a multi-robot rescue system can perform real-time exploration with the proposed system procedure and reduce exploration time in comparison with the case where the proposed scheme is not adopted.     

Dynamic task allocation for multi-robot search and retrieval tasks

Many application domains require search and retrieval, which is also known in the robotic domain as foraging. For example, in a search and rescue domain, a disaster area needs to be explored and transportation of survivors to a safe area needs to be arranged. Performing such a search and retrieval task by more than one robot increases performance if they are able to distribute their workload efficiently and evenly. In this work, we study the Multi-Robot Task Allocation (MRTA) problem in the search and retrieval domain, where a team of robots is required to cooperatively search for targets of interest in an environment and also retrieve them back to a home base. In comparison with typical foraging tasks, we look at a more general search and retrieval task in which the targets are distinguished with various types, and task allocation also requires taking into account temporal constraints on the team goal. As usual, robots have no prior knowledge about the location of targets in the environment but in addition they need to deliver targets to the home base in a specific order according to their types, which significantly increases the complexity of a foraging problem. We first use a graph-based model to analyse the search and retrieval problem and the dynamics of exploration and retrieval within a cooperative team. We then proceed to present an extended auction-based approach, as well as a prediction approach. The essential difference between these two approaches is that the task allocation and execution procedures in the auction approach are running in parallel, whereas a robot in the prediction approach only needs to choose a task to perform when it has no thing to do. The auction approach uses a winner determination mechanism to allocate tasks to each robot, whereas the robots in the prediction approach implicitly coordinate their activities by team reasoning that leads to consensuses about task allocation. We use the Blocks World for Teams (BW4T) simulator to evaluate the two approaches in our experimental study.     

Performance of a class of multi-robot deploy and search strategies based on centroidal voronoi configurations

This article considers a class of deploy and search strategies for multi-robot systems and evaluates their performance. The application framework used is deployment of a system of autonomous mobile robots equipped with required sensors in a search space to gather information. The lack of information about the search space is modelled as an uncertainty density distribution. The agents are deployed to maximise single-step search effectiveness. The centroidal Voronoi configuration, which achieves a locally optimal deployment, forms the basis for sequential deploy and search (SDS) and combined deploy and search (CDS) strategies. Completeness results are provided for both search strategies. The deployment strategy is analysed in the presence of constraints on robot speed and limit on sensor range for the convergence of trajectories with corresponding control laws responsible for the motion of robots. SDS and CDS strategies are compared with standard greedy and random search strategies on the basis of time taken to achieve reduction in the uncertainty density below a desired level. The simulation experiments reveal several important issues related to the dependence of the relative performances of the search strategies on parameters such as the number of robots, speed of robots and their sensor range limits.     

An improved model for swarm robotics in surveillance based on cellular automata and repulsive pheromone with discrete diffusion

ABSTRACT

An inverted ant cellular automata model called IACA-DI is proposed for the coordination of a swarm of robots performing the surveillance task. The swarm communicate indirectly through the repulsive pheromone, which is available as neighborhood information. The pheromone is deposited at each time step by each robot over its neighborhood. The new model started from a previous one named IACA. However, a discrete modeling of the pheromone diffusion is used in IACA-DI returning a sparser distribution of the robots over the environment. Next movement decisions are based on stochastic cellular automata rules that use the pheromone levels in the neighborhood to perform a probabilistic draw. While in IACA all the neighborhood cells participate in this draw, just a subgroup of them participate in the IACA-DI. It is formed by elite cells ? those with the lowest pheromone levels - and some random selected ones. Besides, the cell that keeps the current robot’s direction receives an increment in its probability to be chosen, giving an inertial tendency to the robot motion. Simple simulations were performed enabling to refine parameters and to choose the better strategies. After this refinement, the resultant model was implemented in the simulation platform Webots? aiming to evaluate IACA-DI with real-world robotic architecture in more realistic scenarios.

IACA-DI is a new model for the coordination of robot swarms performing the surveillance task. It is based on cellular automata modeling and the swarm communicate indirectly through the repulsive pheromone deposited by the robots in the environment cells. Letters (a) and (b) show two snapshots from a simulation of a 3-robots swarm performing the surveillance task. The robots start at random positions in an environment composed by 7 rooms in (a). Thus, based on the IACA-DI decisions, they start to make steps to explore the environment aiming to cover all the rooms in a short interval of time. The trace of each robot after 100 time steps is shown in (b) by representing each individual trajectory with a different color. The behavior of each robot is managed by the IACA-DI model, which can be represented by the FSM with 4 states in (c). Different strategies and formulations were investigated for the two major states ‘next position decision’ and ‘pheromone deposition’. The resultant IACA-DI model is analyzed here using simulations performed in Webots? platform -as the snapshots shown in (a) and (b) -with real-world robotic architectures.     

Distributed Algorithms for Multi-Robot Observation of Multiple Moving Targets

An important issue that arises in the automation of many security, surveillance, and reconnaissance tasks is that of observing the movements of targets navigating in a bounded area of interest. A key research issue in these problems is that of sensor placement—determining where sensors should be located to maintain the targets in view. In complex applications involving limited-range sensors, the use of multiple sensors dynamically moving over time is required. In this paper, we investigate the use of a cooperative team of autonomous sensor-based robots for the observation of multiple moving targets. In other research, analytical techniques have been developed for solving this problem in complex geometrical environments. However, these previous approaches are very computationally expensive—at least exponential in the number of robots—and cannot be implemented on robots operating in real-time. Thus, this paper reports on our studies of a simpler problem involving uncluttered environments—those with either no obstacles or with randomly distributed simple convex obstacles. We focus primarily on developing the on-line distributed control strategies that allow the robot team to attempt to minimize the total time in which targets escape observation by some robot team member in the area of interest. This paper first formalizes the problem (which we term CMOMMT for Cooperative Multi-Robot Observation of Multiple Moving Targets) and discusses related work. We then present a distributed heuristic approach (which we call A-CMOMMT) for solving the CMOMMT problem that uses weighted local force vector control. We analyze the effectiveness of the resulting weighted force vector approach by comparing it to three other approaches. We present the results of our experiments in both simulation and on physical robots that demonstrate the superiority of the A-CMOMMT approach for situations in which the ratio of targets to robots is greater than 1/2. Finally, we conclude by proposing that the CMOMMT problem makes an excellent domain for studying multi-robot learning in inherently cooperative tasks. This approach is the first of its kind for solving the on-line cooperative observation problem and implementing it on a physical robot team.     

Performance Evaluation of a Multi-Robot Search & Retrieval System: Experiences with MinDART

Swarm techniques, where many simple robots are used instead of complex ones for performing a task, promise to reduce the cost of developing robot teams for many application domains. The challenge lies in selecting an appropriate control strategy for the individual units. This work explores the effect of control strategies of varying complexity and environmental factors on the performance of a team of robots at a foraging task when using physical robots (the Minnesota Distributed Autonomous Robotic Team). Specifically we study the effect of localization and of simple indirect communication techniques on task completion time using two sets of foraging experiments. We also present results for task performance with varying team sizes and target distributions. As indicated by the results, control strategies with increasing complexity reduce the variance in the performance, but do not always reduce the time to complete the task.     

Towards cooperation of heterogeneous,autonomous robots: A case study of humanoid and wheeled robots

In this paper a case study of the cooperation of a strongly heterogeneous autonomous robot team, composed of a highly articulated humanoid robot and a wheeled robot with largely complementing and some redundant abilities is presented. By combining strongly heterogeneous robots the diversity of achievable tasks increases as the variety of sensing and motion abilities of the robot system is extended, compared to a usually considered team of homogeneous robots. A number of methodologies and technologies required in order to achieve the long-term goal of cooperation of heterogeneous autonomous robots are discussed, including modeling tasks and robot abilities, task assignment and redistribution, robot behavior modeling and programming, robot middleware and robot simulation. Example solutions and their application to the cooperation of autonomous wheeled and humanoid robots are presented in this case study. The scenario describes a tightly coupled cooperative task, where the humanoid robot and the wheeled robot track a moving ball, which is to be approached and kicked by the humanoid robot into a goal. The task can be fulfilled successfully by combining the abilities of both robots.