An algorithm for cooperative task allocation in scalable,constrained multiple robot systems

The current trends in the robotics field have led to the development of large-scale multiple robot systems, and they are deployed for complex missions. The robots in the system can communicate and interact with each other for resource sharing and task processing. Many of such systems fail despite the availability of necessary resources. The major reason for this is their poor coordination mechanism. Task planning, which involves task decomposition and task allocation, is paramount in the design of coordination and cooperation strategies of multiple robot systems. Task allocation mechanism allocates the task in a mission to the robots by maximizing the overall expected performance, and thereby reducing the total allocation cost for the team. In this paper, we formulate a heuristic search-based task allocation algorithm for the task processing in heterogeneous multiple robot system, by maximizing the efficiency in terms of both communication and processing cost. We assume a set of decomposed tasks of a mission, which needs to be allocated to the robots. The near-optimal allocation schemes are found using the proposed peer structure algorithm for the given problem, where the number of the tasks is more than the robots present in the system. The cost function is the summation of static overhead cost of robots, assignment cost, and the communication cost between the dependent tasks, if they are assigned to different robots. Experiments are performed to verify the effectiveness of the algorithm by comparing it with the existing methods in terms of computational time and quality of solution. The experimental results show that the proposed algorithm performs the best under different problem scales. This proves that the algorithm can be scaled for larger system and it can work for dynamic multiple robot system.     

Design of a modular assembly of four-footed robots with multiple functions

Modern industries use many types of robots. In addition to general robotic arms, bipedal, tripedal, and quadrupedal robots, which were originally developed as toys, are gradually being used for multiple applications in manufacturing processes. This research begins with establishing the platform for four-footed robots with multiple functions, high sensitivity, and modular assembly and this is how a fundamental model of the industrial robots is constructed. Under additional loads, the four feet of the quadrupedal robot reinforce its carrying ability and reliability compared to bipedal or tripedal robots, which helps it to carry more objects and enhances functionality. Based on different requirements and demands from the manufacturing processes, the highly sensitive four-footed robot provides an expandable interface to add different sensing components. In addition, when combined with a wireless communication module or independent 1.2 GHz radio frequency CCD wireless image transmission system, the user can control the robot remotely and instantly. The design helps the four-footed robot to expand its applications. By assembling and disassembling modules and changing the sensing components, the highly sensitive four-footed robot can be used for different tasks. Moreover, the remote control function of the robot will increase interaction with human beings, so it can become highly become involved in people's lives. The platform of the four-footed robot will become a design reference for the commercialization of different industrial robots, and it will provide the design of industrial robots with more options and useful applications.     

一个面向复杂任务的多机器人分布式协调系统

基于多智能体系统理论, 研究在非结构、不确定环境下面向复杂任务的多机器人分布式协调系统的实现原理、方法和技术. 提出的递阶混合式协调结构、基于网络的通讯模式和基于有限状态机的规划与控制集成方法, 充分考虑了复杂任务和真实自然环境的特点. 通过构建一个全实物的多移动机器人实验平台, 对规划、控制、传感、通讯、协调与合作的各关键技术进行了开发和集成, 使多机器人分布式协调技术的研究直接面向实际应用, 编队和物料搬运的演示实验结果展示了多机器人协调技术的广阔应用前景.     

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.     

Complex Task Allocation in Mobile Surveillance Systems

In mobile surveillance systems, complex task allocation addresses how to optimally assign a set of surveillance tasks to a set of mobile sensing agents to maximize overall expected performance, taking into account the priorities of the tasks and the skill ratings of the mobile sensors. This paper presents a market-based approach to complex task allocation. Complex tasks are the tasks that can be decomposed into subtasks. Both centralized and hierarchical allocations are investigated as winner determination strategies for different levels of allocation and for static and dynamic search tree structures. The objective comparison results show that hierarchical dynamic tree task allocation outperforms all the other techniques especially in complex surveillance operations where large number of robots is used to scan large number of areas.     

Analysis of autonomous cooperative assembly using coordination schemes by heterogeneous robots using a control basis approach

Robotic technology is quickly evolving allowing robots to perform more complex tasks in less structured environments with more flexibility and autonomy. Heterogeneous multi-robot teams are more common as the specialized abilities of individual robots are used in concert to achieve tasks more effectively and efficiently. An important area of research is the use of robot teams to perform modular assemblies. To this end, this paper analyzed the relative performance of two robots with different morphologies and attributes in performing an assembly task autonomously under different coordination schemes using force sensing through a control basis approach. A rigid, point-to-point manipulator and a dual-armed pneumatically actuated humanoid robot performed the assembly of parts under a traditional “push-hold” coordination scheme and a human-mimicked “push-push” scheme. The study revealed that the scheme with higher level of cooperation—the “push-push” scheme—performed assemblies faster and more reliably, lowering the likelihood of stiction phenomena, jamming, and wedging. The study also revealed that in “push-hold” schemes industrial robots are better pushers and compliant robots are better holders. The results of our study affirm the use of heterogeneous robots to perform hard-to-do assemblies and also encourage humans to function as holder’s when working in concert with a robot assistant for insertion tasks.     

CONRO: Towards Deployable Robots with Inter-Robots Metamorphic Capabilities

Metamorphic robots are modular robots that can reconfigure their shape. Such capability is desirable in tasks such as earthquake search and rescue and battlefield surveillance and scouting, where robots must go through unexpected situations and obstacles and perform tasks that are difficult for fixed-shape robots. The capabilities of the robots are determined by the design specification of their modules. In this paper, we present the design specification of a CONRO module, a small, self-sufficient and relatively homogeneous module that can be connected to other modules to form complex robots. These robots have not only the capability of changing their shape (intra-robot metamorphing) but also can split into smaller robots or merge with other robots to create a single larger robot (inter-robot metamorphing), i.e., CONRO robots can alter their shape and their size. Thus, heterogeneous robot teams can be built with homogeneous components. Furthermore, the CONRO robots can separate the reconfiguration stage from the locomotion stage, allowing the selection of configuration-dependent gaits. The locomotion and automatic inter-module docking capabilities of such robots were tested using tethered prototypes that can be reconfigured manually. We conclude the paper discussing the future work needed to fully realize the construction of these robots.     

Development of multiple robotic fish cooperation platform

This article presents the development of a multiple robotic fish cooperation platform, which is established by employing a group of radio-controlled, multi-link fish-like robots. This work is inspired by the observation from nature that the capability of one single fish is limited, as in order to survive the atrocious circumstances in the sea, fish often swim in schools. The analogical situations occur in the robotic fish case. In engineering applications, most missions are so complex that they must be accomplished by effective cooperation of multiple fish robots. The platform presented in this article, as a novel test bed for multiple robotic fish cooperation, can be applied to different types of complex tasks. More importantly, it provides a good platform to test and verify all kinds of algorithms and strategies for cooperation of multiple underwater mobile robots. We use two cooperative tasks as examples to heuristically demonstrate the performance of this platform.     

群机器人通信研究综述

为了完成规定任务,群机器人中的个体机器人之间须进行协调合作,这有赖于机器人在有限感知和局部交互基础上的群体智能行为涌现,故对群机器人系统中的通信研究现状进行述评。首先对通信机制进行了划分,指出隐式通信的效率较显式通信为低,且作为人工系统的群机器人中更多采用显式通信机制。针对显式通信,通过对通信方式、网络拓扑结构、通信协议及通信语言等主要内容进行阐述,明确群机器人中通信研究的现状,并对该领域的研究方向进行了展望。     

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.     

Automatic cooperative disassembly robotic system: Task planner to distribute tasks among robots

This paper presents a task planner based on decision trees. Two different types of cooperative tasks are described: common task and parallel task. In the first type of task two or more robots are required to accomplish the task. In the second type, several tasks can be performed in parallel by different robots to reduce the total disassembly time. The planner presented is based on a hierarchical representation of the product and performs the distribution of the tasks among robots using decision trees. The system takes into consideration the work area of each robot and its own characteristics. The work cell can be composed of j robotic manipulators. Finally, a practical application of a PC disassembly system is shown.     

Local communication of multiple mobile robots: Design of optimal communication area for cooperative tasks

This paper presents an optimal design for local communication between multiple mobile robots. In previous studies of local communication in multirobot systems, the area of communication was not designed using mathematical analysis, but only time-consuming simulations of multirobot communications. We analyzed the information transmission efficiency and created an optimal communication area that minimizes the information transmission time to multiple robots. This optimization comprises two steps. First, we derive the “information transmission probability” for various task models. Next, the derived information transmission probability is used to minimize the information transmission time. The optimal communication design is tested for various tasks, using system parameters. The analytical results are further verified by using computer simulations of multirobot communications and experiments with local communication. © 1998 John Wiley & Sons, Inc.     

服务机器人技术研究现状与发展趋势

服务机器人技术经过近30年的发展,在机械、信息、材料、控制、医学等多学科交叉方面取得了重要的成果,本文结合作者在机器人领域的相关工作,在分析国内外关于服务机器人发展研究现状的基础上,就服务机器人目前涉及的仿生材料与结构、自重构机器人、复杂环境下机器人动力学问题、智能认知与感知、网络化交互及微纳系统等关键技术的研究进展做简要的综述,并概要展望了其发展趋势.希望能够在把握国际服务机器人前沿技术发展动态的同时,为培育我国服务机器人产业提供相关理论、方法及技术.     

A distributed multi-agent production planning and scheduling framework for mobile robots

Inspired by the new achievements in mobile robotics having as a result mobile robots able to execute different production tasks, we consider a factory producing a set of distinct products via or with the additional help of mobile robots. This particularly flexible layout requires the definition and the solution of a complex planning and scheduling problem. In order to minimize production costs, dynamic determination of the number of robots for each production task and the individual robot allocation are needed. We propose a solution in terms of a two-level decentralized Multi-Agent System (MAS) framework: at the first, production planning level, agents are tasks which compete for robots (resources at this level); at the second, scheduling level, agents are robots which reallocate themselves among different tasks to satisfy the requests coming from the first level. An iterative auction based negotiation protocol is used at the first level while the second level solves a Multi-Robot Task Allocation (MRTA) problem through a distributed version of the Hungarian Method. A comparison of the results with a centralized approach is presented.     

Efficient Boustrophedon Multi-Robot Coverage: an algorithmic approach

This paper presents algorithmic solutions for the complete coverage path planning problem using a team of mobile robots. Multiple robots decrease the time to complete the coverage, but maximal efficiency is only achieved if the number of regions covered multiple times is minimized. A set of multi-robot coverage algorithms is presented that minimize repeat coverage. The algorithms use the same planar cell-based decomposition as the Boustrophedon single robot coverage algorithm, but provide extensions to handle how robots cover a single cell, and how robots are allocated among cells. Specifically, for the coverage task our choice of multi-robot policy strongly depends on the type of communication that exists between the robots. When the robots operate under the line-of-sight communication restriction, keeping them as a team helps to minimize repeat coverage. When communication between the robots is available without any restrictions, the robots are initially distributed through space, and each one is allocated a virtually-bounded area to cover. A greedy auction mechanism is used for task/cell allocation among the robots. Experimental results from different simulated and real environments that illustrate our approach for different communication conditions are presented.     

Deployment of mobile robots with energy and timing constraints

Mobile robots can be used in many applications, such as carpet cleaning, search and rescue, and exploration. Many studies have been devoted to the control, sensing, and communication of robots. However, the deployment of robots has not been fully addressed. The deployment problem is to determine the number of groups unloaded by a carrier, the number of robots in each group, and the initial locations of those robots. This paper investigates robot deployment for coverage tasks. Both timing and energy constraints are considered; the robots carry limited energy and need to finish the tasks before deadlines. We build power models for mobile robots and calculate the robots' power consumption at different speeds. A speed-management method is proposed to decide the traveling speeds to maximize the traveling distance under both energy and timing constraints. Our method uses rectangle scanlines as the coverage routes, and solves the deployment problem using fewer robots. Finally, we provide an approach to consider areas with random obstacles. Compared with two simple heuristics, our solution uses 36% fewer robots for open areas and 32% fewer robots for areas with obstacles.     

Darwinian swarm exploration under communication constraints: Initial deployment and fault-tolerance assessment

In most real multi-robot applications, such as search-and-rescue, cooperative robots have to move to complete their tasks while maintaining communication among themselves without the aid of a communication infrastructure. However, initially deploying and ensuring a mobile ad-hoc network in real and complex environments is an arduous task since the strength of the connection between two nodes (i.e., robots) can change rapidly in time or even disappear. An extension of the Particle Swarm Optimization to multi-robot applications has been previously proposed and denoted as Robotic Darwinian PSO (RDPSO). This paper contributes with a further extension of the RDPSO, thus integrating two research aspects: (i) an autonomous, realistic and fault-tolerant initial deployment strategy denoted as Extended Spiral of Theodorus (EST); and (ii) a fault-tolerant distributed search to prevent communication network splits. The exploring agents, denoted as scouts, are autonomously deployed using supporting agents, denoted as rangers. Experimental results with 15 physical scouts and 3 physical rangers show that the algorithm converges to the optimal solution faster and more accurately using the EST approach over the random deployment strategy. Also, a more fault-tolerant strategy clearly influences the time needed to converge to the final solution, but is less susceptible to robot failures.     

A reactive coordination scheme for a many-robot system

This paper presents a novel approach for coordinating a homogeneous system of mobile robots using implicit communication in the form of broadcasts. The broadcast-based coordination scheme was developed for the Army Ant swarm-a system of small, relatively inexpensive mobile robots that can accomplish complex tasks by cooperating as a team. The primary drawback, however, of the Army Ant system is that the absence of a central supervisor poses difficulty in the coordination and control of the agents. Our coordination scheme provides a global "group dynamic" that controls the actions of each robot using only local interactions. Coordination of the swarm is achieved with signals we call "heartbeats". Each agent broadcasts a unique heartbeat and responds to the collective behavior of all other heartbeats. We generate heartbeats with van der Pol oscillators. In this application, we use the known properties of coupled van der Pol oscillators to create predictable group behavior. Some of the properties and behaviors of coupled van der Pol oscillators are discussed in detail. We emphasize the use of this scheme to allow agents to simultaneously perform an action such as lifting, steering, or changing speed. The results of experiments performed on three actual heartbeat circuits are presented and the behavior of the realized system is compared to simulated results. We also demonstrate the application of the coordination scheme to global speed control.     

无人仓多搬运机器人协同作业轨迹自动控制研究

由于无人仓多搬运机器人协同作业线路较为复杂,导致协同作业轨迹控制难度增加,为了保证多搬运机器人能够按照规划路线执行搬运作业,提出了无人仓多搬运机器人协同作业轨迹自动控制方法;采用栅格图建模法,结合无人仓内货架的实际分布情况,建立无人仓环境场景;从组成结构、运动学以及动力学3个方面,构建搬运机器人的数学模型;遵循就近原则分配多机器人搬运任务,规划多搬运机器人的协同作业轨迹,根据多搬运机器人实时位姿的自动检测结果计算控制量,利用作业轨迹自动控制器的安装与运行,完成无人仓多搬运机器人协同作业轨迹的自动控制任务;实验结果表明,在该方法应用后,多搬运机器人在无人仓中的作业轨迹与规划轨迹基本相同,计算得出的平均位置控制误差和姿态角控制误差分别为2.27 cm和0.05°,搬运机器人的碰撞次数能被控制在规定范围内,实际应用效果好。