Multi-robot exploration under the constraints of wireless networking

A multi-robot system can be highly beneficial for exploration, which is a core robotics task. Application domains include, for example, surveillance, reconnaissance, planetary exploration or rescue missions. When using a team of robots, the overall performance can be much faster and more robust. In this article, an approach to multi-robot exploration is presented that takes the constraints of wireless networking into account. An algorithm is introduced based on a population that samples the possible moves of all robots and a utility to select the best one in each time step. Results from two scenarios are presented. In the first one, a team of robots explores its environment while permanently maintaining an ad hoc network structure with each other as well as a base station at a fixed location. In the second one, the robots move freely as a pack while maintaining communication with each other.     

A multi-robot exploration algorithm based on a static Bluetooth communication chain

In the first part of the present paper, a novel communication scheme of an autonomous robot team via Bluetooth radio is investigated. In the presented solution, an autonomous unit is equipped with two independent Bluetooth radios and so a relatively fast communication is possible in the team in a static (i.e. no ad hoc) networking topology. The performance of such a network was tested by implementing a linear graph topology by NXT robots. It was found that the reliability and the speed of such a communication scheme are satisfactory and give rise to applications in a robot team control task. In the second part of the paper, an area exploration method is presented based on the static linear communication network above. The method was tested by computer simulations for various obstacle configurations and densities. It was found that the proposed method performs better than the chosen reference methods in the case of zero or low obstacle density and when high (75% or 100%) exploration ratio is required. With a simple proof, we have shown that the proposed (fixed chain-like team) exploration method is optimal in the obstacle-free case under the constraint of the connectivity with the base station.     

可变形灾难救援机器人控制站系统的设计与实现

针对灾难救援应用领域具体需求,提出了控制站系统的设计原则.基于人机交互技术,设计了可变形灾难救援机器人控制站系统,该系统具有感知信息完整、操控灵活、界面友好、交互性强等特点.通过灾难救援模拟环境进行实验,验证丁该控制站系统可以实现机器人在复杂环境中的运动控制、多通道信息交互等功能,在灾难救援等领域具有可行性及有效性.     

Collaboration in Multi-Robot Exploration: To Meet or not to Meet?

Work on coordinated multi-robot exploration often assumes that all areas to be explored are freely accessible. This common assumption does not always hold, especially not in search and rescue missions after a disaster. Doors may be closed or paths blocked detaining robots from continuing their exploration beyond these points and possibly requiring multiple robots to clear them. This paper addresses the issue how to coordinate a multi-robot system to clear blocked paths. We define local collaborations that require robots to collaboratively perform a physical action at a common position. A collaborating robot needs to interrupt its current exploration and move to a different location to collaboratively clear a blocked path. We raise the question when to collaborate and whom to collaborate with. We propose four strategies as to when to collaborate. Two obvious strategies are to collaborate immediately or to postpone any collaborations until only blocked paths are left. The other two strategies make use of heuristics based on building patterns. While no single strategy behaves optimal in all scenarios, we show that the heuristics decrease the time required to explore unknown environments considering blocked paths.     

Efficient terrain coverage for deploying wireless sensor nodes on multi-robot system

Coverage and connectivity are the two main functionalities of wireless sensor network. Stochastic node deployment or random deployment almost always cause hole in sensing coverage and cause redundant nodes in area. In the other hand precise deployment of nodes in large area is very time consuming and even impossible in hazardous environment. One of solution for this problem is using mobile robots with concern on exploration algorithm for mobile robot. In this work an autonomous deployment method for wireless sensor nodes is proposed via multi-robot system which robots are considered as node carrier. Developing an exploration algorithm based on spanning tree is the main contribution and this exploration algorithm is performing fast localization of sensor nodes in energy efficient manner. Employing multi-robot system and path planning with spanning tree algorithm is a strategy for speeding up sensor nodes deployment. A novel improvement of this technique in deployment of nodes is having obstacle avoidance mechanism without concern on shape and size of obstacle. The results show using spanning tree exploration along with multi-robot system helps to have fast deployment behind efficiency in energy.     

Distributed multi-robot coordination in area exploration

This paper proposes a reliable and efficient multi-robot coordination algorithm to accomplish an area exploration task given that the communication range of each robot is limited. This algorithm is based on a distributed bidding model to coordinate the movement of multiple robots. Two measures are developed to accommodate the limited-range communications. First, the distances between robots are considered in the bidding algorithm so that the robots tend to stay close to each other. Second, a map synchronization mechanism, based on a novel sequence number-based map representation and an effective robot map update tracking, is proposed to reduce the exchanged data volume when robot subnetworks merge. Simulation results show the effectiveness of the use of nearness measure, as well as the map synchronization mechanism. By handling the limited communication range we can make the coordination algorithms more realistic in multi-robot applications.     

Probabilistic Road Map sampling strategies for multi-robot motion planning

This paper presents a Probabilistic Road Map (PRM) motion planning algorithm to be queried within Dynamic Robot Networks—a multi-robot coordination platform for robots operating with limited sensing and inter-robot communication.

First, the Dynamic Robot Networks (DRN) coordination platform is introduced that facilitates centralized robot coordination across ad hoc networks, allowing safe navigation in dynamic, unknown environments. As robots move about their environment, they dynamically form communication networks. Within these networks, robots can share local sensing information and coordinate the actions of all robots in the network.

Second, a fast single-query Probabilistic Road Map (PRM) to be called within the DRN platform is presented that has been augmented with new sampling strategies. Traditional PRM strategies have shown success in searching large configuration spaces. Considered here is their application to on-line, centralized, multiple mobile robot planning problems. New sampling strategies that exploit the kinematics of non-holonomic mobile robots have been developed and implemented. First, an appropriate method of selecting milestones in a PRM is identified to enable fast coverage of the configuration space. Second, a new method of generating PRM milestones is described that decreases the planning time over traditional methods. Finally, a new endgame region for multi-robot PRMs is presented that increases the likelihood of finding solutions given difficult goal configurations.

Combining the DRN platform with these new sampling strategies, on-line centralized multi-robot planning is enabled. This allows robots to navigate safely in environments that are both dynamic and unknown. Simulations and real robot experiments are presented that demonstrate: (1) speed improvements accomplished by the sampling strategies, (2) centralized robot coordination across Dynamic Robot Networks, (3) on-the-fly motion planning to avoid moving and previously unknown obstacles and (4) autonomous robot navigation towards individual goal locations.     

Semi-autonomous serially connected multi-crawler robot for search and rescue

In this paper, we develop a semi-autonomous serially connected multi-crawler robot for search and rescue. In large-scale disasters, such as earthquakes and tornadoes, the application of rescue robots to search for survivors under rubble would be beneficial. Snake-like robots (robots composed of serially connected units) are an effective candidate for such robots. Their long body enables them to overcome obstacles, and they can move into narrow spaces because of their thin shape. However, conventional snake-like robots have significant problems with operability. The numerous degrees of freedom of their bodies require complex operation to overcome obstacles, and training is required for the operators. Thus, survivors or community members cannot operate conventional robots to search for victims, despite the availability of such rescue robots. Here, we address this problem and develop a semi-autonomous serially connected multi-crawler robot designed for non-trained operators, such as community members or rescued survivors. It can be controlled easily by a conventional two-channel user interface with levers for turning and straight line motion. To demonstrate the effectiveness of our proposed mechanism, a prototype robot was developed and experiments were conducted. The results confirm that the proposed robot had both higher operability and higher mobility than conventional robots.     

Cooperative task excecution of a search and rescue mission by a multi-robot team

Rescue robots have proved to be an extremely useful work partner for urban search and rescue (USAR) missions. Human rescuers who carry out these missions frequently enter dangerous zones to search for survivors; however, due to the unstable nature of collapsed buildings or objects, their lives may also be threatened. For this reason, in order to reduce life-threatening risks, rescue robots are deployed to carry out the job instead. Rescuers can now operate the robots at a safe place while the missions are carried out. When the robots have gathered enough information about the location of the victims and data about their physical conditions, rescuers can then enter the disaster site with enough knowledge to avoid harm and rescue the victims in the shortest time possible. In this paper, we introduce examples of 'effective multiple robot cooperative activities' and 'a study of the number of robots and operators in a multi-robot team' from our experiences gained from participating in RoboCup Rescue competitions.     

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.     

Multi-Robot Graph Exploration and Map Building with Collision Avoidance: A Decentralized Approach

This paper proposes a decentralized multi-robot graph exploration approach in which each robot takes independent decision for efficient exploration avoiding inter-robot collision without direct communication between them. The information exchange between the robots is possible through the beacons available at visited vertices of the graph. The proposed decentralized technique guarantees completion of exploration of an unknown environment in finite number of edge traversals where graph structure of the environment is incrementally constructed. New condition for declaring completion of exploration is obtained. The paper also proposes a modification in incidence matrix so that it can be used as a data structure for information exchange. The modified incidence matrix after completion represents map of the environment. The proposed technique requires either lesser or equal number of edge traversals compared to the existing strategy for a tree exploration. A predefined constant speed change approach is proposed to address the inter-robot collision avoidance using local sensor on a robot. Simulation results verify the performance of the algorithm on various trees and graphs. Experiments with multiple robots show multi-robot exploration avoiding inter-robot collision.     

基于声音的分布式多机器人相对定位

提出了一种基于声音的分布式多机器人相对定位方法.首先,每个机器人通过声源定位算法估计发声机器人在其局部坐标系下的坐标;然后,每个机器人（不含发声机器人）通过无线通信方式将发声机器人在其坐标系下的坐标广播给所有其他机器人,通过坐标变换每个机器人可计算出所有其他机器人在其坐标系下的坐标,从而实现分布式相对定位.理论推导及实验证明只要两个机器人先后发声,通过本文所提方法即可实现多机器人相对定位.室内外环境中采用6个自制小型移动机器人实验表明,所提方法在3米的范围内可实现16厘米的相对定位精度.     

Wireless video sensor networks for sparse, resource-constrained, multi-robot teams

Small-size robots provide access and maneuverability in the tight confines of highly rubbled and uncertain environments such as those encountered in Urban Search and Rescue (USAR). Small size also provides easy portability and deployability and the potential for redundancy through multi-robot teaming. Unfortunately, small size does not diminish the data demands of these applications, such as high-resolution imagery and other forms of high bandwidth data. Furthermore, achieving redundancy in tight environments requires wireless operation to avoid the entanglement of tethers, but wireless communication links have proven unreliable in such environments. The net effect of this is a set of robust networking requirements that include high bandwidth, low latency, and low power with multi-hop routing in a sparse and highly volatile network configuration, which has been collectively difficult to achieve. Our metric for benchmarking these requirements is a stream of uncompressed 320 ×  240, 24-bit color images updated at 1 frame per second (roughly 1.8 Mbps - image compression is not the focus of this research as it only serves to increase the possible resolution or frame rate). No existing ad hoc wireless sensor network approaches have been able to achieve these requirements. Wi-Fi requires high power and size and does not have the latency, while Zig-bee does not have the bandwidth. Instead, this work focuses on augmenting the Bluetooth protocol, which is master/slave based, with a hybrid, multi-hop routing protocol. Bluetooth has the desired low power and high bandwidth characteristics, but lacks multi-hop routing and rapid recovery. In this paper, a hybrid routing protocol for ad hoc multi-robot networking is described that features: (1) high-bandwidth, (2) low power, and (3) low latency of data traffic for sparse, highly volatile networks—exactly what is required for large teams of highly distributed, small-scale robots. Furthermore, this paper compares simulations and robot implementations of different routing protocols over Bluetooth sensor networks and demonstrates the viability of our protocol as a wireless network solution for multi-robot teams characterized by high mobility in difficult RF environments. To the best of our knowledge, the work presented in this paper is the first attempt at comparison of different routing protocols for real robots with physical experiments over Bluetooth sensor networks.     

栅格地图中多机器人协作搜索目标

目标搜索是多机器人领域的一个挑战.本文针对栅格地图中多机器人目标搜索算法进行研究.首先,利用Dempster-Shafer证据理论将声纳传感器获取的环境信息进行融合,构建搜索环境的栅格地图.然后,基于栅格地图建立生物启发神经网络用于表示动态的环境.在生物启发神经网络中,目标通过神经元的活性值全局的吸引机器人.同时,障碍物通过神经元活性值局部的排斥机器人,避免与其相撞.最后,机器人根据梯度递减原则自动的规划出搜索路径.仿真和实验结果显示本文提及的算法能够实现栅格地图中静态目标和动态目标的搜索.与其他搜索算法比较,本文所提及的目标搜索算法有更高的效率和适用性.     

基于多智能体深度强化学习的协作导航应用

多机器人协作导航目前广泛应用于搜索救援、物流等领域, 协作策略与目标导航是多机器人协作导航面临的主要挑战. 为提高多个移动机器人在未知环境下的协作导航能力, 本文提出了一种新的分层控制协作导航(hierarchical control cooperative navigation, HCCN) 策略, 利用高层目标决策层和低层目标导航层, 为每个机器人分配一个目标点, 并通过全局路径规划和局部路径规划算法, 引导智能体无碰撞地到达分配的目标点. 通过Gazebo平台进行实验验证, 结果表明, 文中所提方法能够有效解决协作导航过程中的稀疏奖励问题, 训练速度至少可提高16.6%, 在不同环境场景下具有更好的鲁棒性, 以期为进一步研究多机器人协作导航提供理论指导, 应用至更多的真实场景中.     

Conflict free coordinated path planning for multiple robots using a dynamic path modification sequence

In this paper, a practically viable approach for conflict free, coordinated motion planning of multiple robots is proposed. The presented approach is a two phase decoupled method that can provide the desired coordination among the participating robots in offline mode. In the first phase, the collision free path with respect to stationary obstacles for each robot is obtained by employing an A* algorithm. In the second phase, the coordination among multiple robots is achieved by resolving conflicts based on a path modification approach. The paths of conflicting robots are modified based on their position in a dynamically computed path modification sequence (PMS). To assess the effectiveness of the developed methodology, the coordination among robots is also achieved by different strategies such as fixed priority sequence allotment for motion of each robot, reduction in the velocities of joints of the robot, and introduction of delay in starting of each robot. The performance is assessed in terms of the length of path traversed by each robot, time taken by the robot to realize the task and computational time. The effectiveness of the proposed approach for multi-robot motion planning is demonstrated with two case studies that considered the tasks with three and four robots. The results obtained from realistic simulation of multi-robot environment demonstrate that the proposed approach assures rapid, concurrent and conflict free coordinated path planning for multiple robots.     

A rescue robot system for collecting information designed for ease of use — a proposal of a rescue systems concept

A remote controlled robot for collecting information in disasters, e.g. earthquakes, is one of most effective applications of robots, because it is very dangerous for human beings to locate survivors in collapsed buildings and, in addition, small robots can move into narrow spaces to find survivors. However, previous rescue systems that use robots have a significant problem — a shortage of operators. In catastrophic disasters, in order to save victims, we must explore wide areas within a limited time. Thus, many rescue robots should be employed simultaneously. However, human interfaces of previous rescue robots were complicated, so that well-trained professional operators were needed to operate the robots and, thus, to use many rescue robots, many professional operators were required. However, in such catastrophic disasters it is difficult to get many professional operators together within a short time. In this paper we address the problem and propose a concept of rescue team organization in which professional rescue staff and volunteer staff work together for handling a catastrophic disaster. We point out the necessity for rescue robots which can be operated easily by non-professional volunteer staff. To realize a rescue robot which can be operated easily, we propose a rescue robot system which has a human interface seen in typical, everyday vehicles and a snake-like robot which has mechanical intelligence. We have demonstrated the validity and the effectiveness of the proposed concept by developing a prototype system.     

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.     

Robust multi-robot coordination in pick-and-place tasks based on part-dispatching rules

This paper addresses the problem of realizing multi-robot coordination that is robust against pattern variation in a pick-and-place task. To improve productivity and reduce the number of parts remaining on the conveyor, a robust and appropriate part flow and multi-robot coordinate strategy are needed. We therefore propose combining part-dispatching rules to coordinate robots, by integrating a greedy randomized adaptive search procedure (GRASP) and a Monte Carlo strategy (MCS). GRASP is used to search for the appropriate combination of part-dispatching rules, and MCS is used to estimate the minimum-maximal part flow for one combination of part-dispatching rules. The part-dispatching rule of first-in–first-out is used to control the final robot in the multi-robot system to pick up parts left by other robots, and the part-dispatching rule of shortest processing time is used to make the other robots pick up as many parts as possible. By comparing it with non-cooperative game theory, we verify that the appropriate combination of part-dispatching rules is effective in improving the productivity of a multi-robot system. By comparing it with a genetic algorithm, we also verify that MCS is effective in estimating minimum-maximal part flow. The task-completion success rate derived via the proposed method reached 99.4% for 10,000 patterns.     

VARIABLE PATROL PLANNING OF MULTI-ROBOT SYSTEMS BY A COOPERATIVE AUCTION SYSTEM

A cooperative auction system (CAS) is proposed to solve the large-scale multi-robot patrol planning problem. Each robot picks its own patrol points via the cooperative auction system and the system continuously re-auctions, based on the team work performance. The proposed method not only works in static environments but also considers variable path planning when the number of mobile robots increases or decreases during patrol. From the results of the simulation, the proposed approach demonstrates decreased time complexity, a lower routing path cost, improved balance of workload among robots, and the potential to scale to a large number of robots and is adaptive to environmental perturbations when the number of robots changes during patrol.