Development of a reduced human user input task allocation method for multiple robots

Task allocation mechanisms are employed by multi-robot systems to efficiently distribute tasks between different robots. Currently, many task allocation methods rely on detailed expert knowledge to coordinate robots. However, it may not be feasible to dedicate an expert human user to a multi-robot system. Hence, a non-expert user may have to specify tasks to a team of robots in some situations. This paper presents a novel reduced human user input multi-robot task allocation technique that utilises Fuzzy Inference Systems (FISs). A two-stage primary and secondary task allocation process is employed to select a team of robots comprising manager and worker robots. A multi-robot mapping and exploration task is utilised as a model task to evaluate the task allocation process. Experiments show that primary task allocation is able to successfully identify and select manager robots. Similarly, secondary task allocation successfully identifies and selects worker robots. Both task allocation processes are also robust to parameter variation permitting intuitive selection of parameter values.     

编队多机器人类人探测方法

针对多机器人探测和处理多目标的控制任务,模仿人类探索未知环境的过程,提出了多机器人探测的边界、编队、目标吸引、重复探测、路径状况和探测扩张等6个类人探测规则.根据多机器人相互协调和高效探测的需要,通过规则的对应适值控制机器人的运动,使各个机器人沿优化路径共同完成多目标探测任务,解决了在全局未知环境下的多机器人路径规划问题.仿真结果表明,所提出的类人探测各种规则能有效地控制多机器人实现未知环境探测,具有可行性.     

生物交哺行为启发的群体机器人搜集行为研究

为了提高群体机器人系统的整体性能,受生物系统中普遍存在的交哺现象的启发,在原来多机器人系统的基本行为的基础上,提出了一种引入交哺行为的多机器人协作机制。机器人依靠有限的感知能力和局部交互功能,以自组织方式执行目标搜集任务。机器人的内部状态变量反映其执行任务的情况以及对环境和其他机器人的评价。比较机器人的内部状态变量,可以判断是否需要交哺和交哺的方向性。主要目的是减少机器人之间的冲突,降低系统能量消耗的同时,提高机器人搜集目标的效率。最后通过计算机仿真实验以及与其他多机器人协作方法比较,分析该方法对提高系统性能的有效性。     

多机器人协同搜索目标源及几何图形部署

近60年来,机器人已经快速发展,然而就目前的机器人作为自主个体的应用来看,几乎所有的机器人在完成任务的过程中,都是不能缺少位置信息的。但是当今世界有越来越多艰难的任务需要多个智能机器人在不了解位置信息的情况下协同进行作业,例如水下打捞作业。针对这一情况,利用已有的单机器人的极值控制算法结合反应对流扩散方程以及多机器人的协同控制算法仿真实现多机器人协同搜索光源,并且使多机器人在点光源周围的部署成一定的几何图形,如圆、椭圆等以便完成相应的任务。为了验证算法的有效性和可操作性,采用7个机器人进行协作搜索光源过程仿真并给出仿真结果。     

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

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

Contribution to the path planning of a multi-robot system: centralized architecture

The current study is set to investigate the problem of planning trajectories for a multi-robot system in a dynamic environment. The planning study is conducted in a “barrier-free” and “with obstacle” environment, based on the artificial potential field (APF) technique. This study seeks to improve the APF method in order to have good trajectory planning of a multi-robot system. Also, for multi-robot mobile systems, one of the main technical considerations is the technique used to coordinate the movements of different robots. In this paper, we proposed a centralized architecture for the trajectory planning of a multi-robot system.

     

Collaboration of Multiple Autonomous Industrial Robots through Optimal Base Placements

Multiple autonomous industrial robots can be of great use in manufacturing applications, particularly if the environment is unstructured and custom manufacturing is required. Autonomous robots that are equipped with manipulators can collaborate to carry out manufacturing tasks such as surface preparation by means of grit-blasting, surface coating or spray painting, all of which require complete surface coverage. However, as part of the collaboration process, appropriate base placements relative to the environment and the target object need to be determined by the robots. The problem of finding appropriate base placements is further complicated when the object under consideration is large and has a complex geometric shape, and thus the robots need to operate from a number of base placements in order to obtain complete coverage of the entire object. To address this problem, an approach for Optimization of Multiple Base Placements (OMBP) for each robot is proposed in this paper. The approach aims to optimize base placements for multi-robot collaboration by taking into account task-specific objectives such as makespan, fair workload division amongst the robots, and coverage percentage; and manipulator-related objectives such as torque and manipulability measure. In addition, the constraint of robots maintaining an appropriate distance between each other and relative to the environment is taken into account. Simulated and real-world experiments are carried out to demonstrate the effectiveness of the approach and to verify that the simulated results are accurate and reliable.     

Distributed multirobot exploration, mapping, and task allocation

We present an integrated approach to multirobot exploration, mapping and searching suitable for large teams of robots operating in unknown areas lacking an existing supporting communications infrastructure. We present a set of algorithms that have been both implemented and experimentally verified on teams—of what we refer to as Centibots—consisting of as many as 100 robots. The results that we present involve search tasks that can be divided into a mapping stage in which robots must jointly explore a large unknown area with the goal of generating a consistent map from the fragment, a search stage in which robots are deployed within the environment in order to systematically search for an object of interest, and a protection phase in which robots are distributed to track any intruders in the search area. During the first stage, the robots actively seek to verify their relative locations in order to ensure consistency when combining data into shared maps; they must also coordinate their exploration strategies so as to maximize the efficiency of exploration. In the second and third stages, robots allocate search tasks among themselves; since tasks are not defined a priori, the robots first produce a topological graph of the area of interest and then generate a set of tasks that reflect spatial and communication constraints. Our system was evaluated under extremely realistic real-world conditions. An outside evaluation team found the system to be highly efficient and robust.     

一种基于双令牌的多机器人协作策略研究

规划协作和自组织协作是两种比较常见的多机器人协作方式，前者规划精度高，但设计复杂，且系统鲁棒性不强，后者灵活性很强，但由于单个机器人自主性很强，因此，协作存在一定盲目性。该文为此提出了一个基于双令牌的多机器人自组织协作模型。模型中采用了具有两级策略评价标准的多机器人策略调整机制，通过双令牌来协调机器人之间的策略调整行为。设计了一个基于本文自组织模型的多机器人控制系统，进行了仿真实验验证。     

Hybrid ensemble selection algorithm incorporating GRASP with path relinking

The greedy randomized adaptive search procedure (GRASP) is an iterative two-phase multi-start metaheuristic procedure for a combination optimization problem, while path relinking is an intensification procedure applied to the solutions generated by GRASP. In this paper, a hybrid ensemble selection algorithm incorporating GRASP with path relinking (PRelinkGraspEnS) is proposed for credit scoring. The base learner of the proposed method is an extreme learning machine (ELM). Bootstrap aggregation (bagging) is used to produce multiple diversified ELMs, while GRASP with path relinking is the approach for ensemble selection. The advantages of the ELM are inherited by the new algorithm, including fast learning speed, good generalization performance, and easy implementation. The PRelinkGraspEnS algorithm is able to escape from local optima and realizes a multi-start search. By incorporating path relinking into GRASP and using it as the ensemble selection method for the PRelinkGraspEnS the proposed algorithm becomes a procedure with a memory and high convergence speed. Three credit datasets are used to verify the efficiency of our proposed PRelinkGraspEnS algorithm. Experimental results demonstrate that PRelinkGraspEnS achieves significantly better generalization performance than the classical directed hill climbing ensemble pruning algorithm, support vector machines, multi-layer perceptrons, and a baseline method, the best single model. The experimental results further illustrate that by decreasing the average time needed to find a good-quality subensemble for the credit scoring problem, GRASP with path relinking outperforms pure GRASP (i.e., without path relinking).     

Probabilistic stopping rules for GRASP heuristics and extensions

The main drawback of most metaheuristics is the absence of effective stopping criteria. Most implementations of such algorithms stop after performing a given maximum number of iterations or a given maximum number of consecutive iterations without improvement in the best‐known solution value, or after the stabilization of the set of elite solutions found along the search. We propose effective probabilistic stopping rules for randomized metaheuristics such as GRASP (Greedy Randomized Adaptive Search Procedures). We show how the probability density function of the solution values obtained along the iterations of such algorithms can be used to implement stopping rules based on the tradeoff between solution quality and the time needed to find a solution that might improve the best solution found. We show experimentally that, in the particular case of GRASP heuristics, the solution values obtained along its iterations fit a normal distribution that may be used to give an online estimation of the number of solutions obtained in forthcoming iterations that might be at least as good as the incumbent. This estimation is used to validate the stopping rule based on the tradeoff between solution quality and the time needed to find a solution that might improve the incumbent. The robustness of this strategy is illustrated and validated by a thorough computational study reporting results obtained with GRASP implementations to four different combinatorial optimization problems.     

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

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

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.     

A hybrid data mining GRASP with path-relinking

The exploration of hybrid metaheuristics—combination of metaheuristics with concepts and processes from other research areas—has been an important trend in combinatorial optimization research. An instance of this study is the hybrid version of the GRASP metaheuristic that incorporates a data mining process. Traditional GRASP is an iterative metaheuristic which returns the best solution reached over all iterations. In the hybrid GRASP proposal, after executing a significant number of iterations, the data mining process extracts patterns from an elite set of sub-optimal solutions for the optimization problem. These patterns present characteristics of near optimal solutions and can be used to guide the following GRASP iterations in the search through the combinatorial solution space. The hybrid data mining GRASP has been successfully applied for different combinatorial problems: the set packing problem, the maximum diversity problem, the server replication for reliable multicast problem and the p-median problem. In this work, we show that, not only the traditional GRASP, but also GRASP improved with the path-relinking heuristic—a memory-based intensification strategy—could benefit from exploring a data mining procedure. Computational experiments, comparing traditional GRASP with path-relinking and different path-relinking hybrid proposals, showed that employing the combination of path-relinking and data mining made the GRASP find better results in less computational time. Another contribution of this work is the application of the path-relinking hybrid proposal for the 2-path network design problem, which improved the state-of-the-art solutions for this problem.     

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 robust extended H∞ filtering approach to multi-robot cooperative localization in dynamic indoor environments

Multi-robot cooperative localization serves as an essential task for a team of mobile robots to work within an unknown environment. Based on the real-time laser scanning data interaction, a robust approach is proposed to obtain optimal multi-robot relative observations using the Metric-based Iterative Closest Point (MbICP) algorithm, which makes it possible to utilize the surrounding environment information directly instead of placing a localization-mark on the robots. To meet the demand of dealing with the inherent non-linearities existing in the multi-robot kinematic models and the relative observations, a robust extended $H_{\infty }$ filtering (REHF) approach is developed for the multi-robot cooperative localization system, which could handle non-Gaussian process and measurement noises with respect to robot navigation in unknown dynamic scenes. Compared with the conventional multi-robot localization system using extended Kalman filtering (EKF) approach, the proposed filtering algorithm is capable of providing superior performance in a dynamic indoor environment with outlier disturbances. Both numerical experiments and experiments conducted for the Pioneer3-DX robots show that the proposed localization scheme is effective in improving both the accuracy and reliability of the performance within a complex environment.     

面向观测融合和吸引因子的多机器人主动SLAM

针对未知环境下多机器人主动SLAM(simultaneous localization and mapping)存在不能完全遍历环境、定位精度不理想等问题,本文基于EKF-SLAM(extended Kalman filter-simultaneous localization and mapping)算法提出一种多机器人主动SLAM算法。通过引入吸引因子,增强多机器人系统之间的交流,提升机器人自身定位精度与环境建图精度,同时又引导多机器人团队进行探索环境。当同一地标被多个机器人观测到,采用凸组合融合方法融合各个机器人对地标的估计,从而降低被估计地标的不确定度。仿真结果表明,所提算法能够对环境进行覆盖遍历,提升对地标估计的定位精度。     

Model construction, rule reduction, and robust compensation forgeneralized form of Takagi-Sugeno fuzzy systems

This paper presents a systematic procedure of fuzzy control system design that consists of fuzzy model construction, rule reduction, and robust compensation for nonlinear systems. The model construction part replaces the nonlinear dynamics of a system with a generalized form of Takagi-Sugeno fuzzy systems, which is newly developed by us. The generalized form has a decomposed structure for each element of A_i and B_i matrices in consequent parts. The key feature of this structure is that it is suitable for constructing IF-THEN rules and reducing the number of IF-THEN rules. The rule reduction part provides a successive procedure to reduce the number of IF-THEN rules. Furthermore, we convert the reduction error between reduced fuzzy models and a system to model uncertainties of reduced fuzzy models. The robust compensation part achieves the decay rate controller design guaranteeing robust stability for the model uncertainties. Finally, two examples demonstrate the utility of the systematic procedure developed     

霍夫空间中多足球机器人协作目标定位算法

针对嵌入式仿人足球机器人提出一种霍夫空间中的多机器人协作目标定位算法。机器人利用实验场地中的标志物采用基于三角几何定位方法进行自定位,把机器人多连杆模型进行简化,通过坐标系位姿变换把图像坐标系转换到世界坐标系中,实现机器人目标定位;在多机器人之间建立ZigBee无线传感器网络进行通信,把多个机器人定位的坐标点进行霍夫变换,在霍夫空间中进行最小二乘法线性拟合,获取最优参数,然后融合改进后的粒子滤波实现对目标小球的跟踪;最后在21自由度的仿人足球机器人上进行仿真和实验。数据结果表明,这种多机器人协作的定位算法的精度提高了约48%,在满足实时性的前提下,对目标的跟踪效果也得到了改善。     

Altruistic coordination for multi-robot cooperative pathfinding

When multiple robots perform tasks in a shared workspace, they might be confronted with the risk of blocking each other’s ways, which will lead to conflicts or interference among them. Planning collision-free paths for all the robots is a challenge for a multi-robot system, which is also known as the multi-robot cooperative pathfinding problem in which each robot has to navigate from its starting location to the destination while keeping avoiding stationary obstacles as well as the other robots. In this paper, we present a novel fully decentralized approach to this problem. Our approach allows robots to make real-time responses to dynamic environments and can resolve a set of benchmark deadlock situations subject to complex spatial constraints in a shared workspace by means of altruistic coordination. Specifically, when confronted with congested situations, each robot can employ waiting, moving-forwards, dodging, retreating and turning-head strategies to make local adjustments. Most importantly, each robot only needs to coordinate and communicate with the others that are located within its coordinated network in our approach, which can reduce communication overhead in fully decentralized multi-robot systems. In addition, experimental results also show that our proposed approach provides an efficient and competitive solution to this problem.