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.     

A decentralized Artificial Immune System for solution selection in Cyber–Physical Systems

Centralization has become a de facto standard for implementing networked environments such as the Cyber–Physical Systems (CPS). Though easy to implement and control, centralized systems are difficult and expensive to scale in terms of the number of devices and the flow of information. This set of circumstances calls for a decentralized and distributed architecture for realizing such networked systems. However, due to the absence of global information in decentralized systems, one of the primary challenges is to find the best solution for problems distributed across the devices which are part of the CPS. Since the problems are distributed and no participating device has access to the full information, the devices may need to interact and share the information to select the best solution for a problem occurred. In this paper, we present a decentralized and distributed mechanism, which adapts to a stream of varying problems and continuously evolves and learns the best mappings between the problems and their associated solutions. The proposed approach integrates the concepts propounded in the three major Immune theories and can cater to real-world situations. The evolved mappings are shared across the physical network, thereby accelerating the search for the best set of solutions. In order to validate the performance of the proposed mechanism, we present the results obtained from solving a problem of sorting a stream of varying data in an emulated decentralized and distributed manner. To substantiate its working in real-world scenarios, we also describe the results obtained by embodying the system in real robots that discover the best path-following algorithms.     

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.     

Evolutionary optimization using epsilon method for resource-constrained multi-robotic disassembly line balancing

This paper concentrates on a resource-constrained multi-robotic disassembly line balancing (RC-MDLB) problem. In this RC-MDLB problem, different types of end-of-life products are disassembled simultaneously on the same line under the following conditions: allocating multiple robots to a workstation to simultaneously process the disassembly tasks that have no precedence relationship with each other, each robot needs a fixed number of limited resources to process tasks, and the total resources for each workstation is fixed. A mathematical model is presented for the RC-MDLB problem to minimize the cycle time and the number of robots being occupied simultaneously. A constrained multi-objective evolutionary algorithm framework and a constrained NSGA-II (E-NSGA-II) algorithm with epsilon method are proposed to handle the constraints of the RC-MDLB problem. The proposed E-NSGA-II is applied to a set of RC-MDLB problem instances introduced in this paper and compared with five representative multi-objective evolutionary algorithms. The experimental results reveal that the proposed E-NSGA-II presents outstanding performance on most of the cases analyzed.     

Coalition Formation for Multi-Robot Task Allocation via Correlation Clustering

Abstract

The complexity of a vast number of real world tasks provides a great challenge for the currently available robots due to their limited capabilities. Thus, multiple robots would need to form coalitions for the completion of such tasks. In this paper, we examine the multi-robot coalition formation problem for task allocation where a group of robots needs to be allocated to a set of tasks. Our approach for this problem is to use a correlation clustering technique enabling similar robots to form coalitions. The algorithm presented in this paper is fast and scales better in comparison to two existing algorithms.     

Problem decomposition in distributed problem-solving systems

Distributed Problem Solving (DPS) is defined as the cooperative solution of problems by a decentralized and loosely coupled collection of problem solvers (agents), each of them knowing how to execute only some of the necessary tasks. This approach considers the problem-solving process as occurring in three phases: problem decomposition, subproblem solution, and answer synthesis. In the problem decomposition phase, one has to determine which tasks will be executed by each agent and when. One of the key research questions in the problem decomposition process is how to decompose a problem in order to minimize the cost of resources needed for its solution. In this article, we construct mathematical programming models in order to describe the decomposition process under the above criterion, study its complexity, and present exact and heuristic algorithms for its solution. Our work was motivated by the operation of an actual system that can be considered as a distributed problem solver for the assessment of irrigation projects design.     

Assistance networks for dynamic multirobot tasks

In this paper, we consider dynamic multirobot tasks that can be done by any of the robots, but only with the assistance of any other robot. We propose a novel approach based on the concept of ‘assistance networks’ with two complementary aspects, namely assistant finding and network topology update. Each robot, encountering a new task, seeks an assisting robot among its immediate neighbors in the assistance network in a decentralized manner. The network topology is defined based on pairwise stability via payoff functions that consider general task-related guidelines. As such, the number of potential assisting robots can be ensured a priori depending on tasks’ requirements. As robots move around, the topology is updated via pairwise games. If the games are conducted by a network coordinator, each game is shown to result in a pairwise stable network. A series of simulation and experimental results in a variety of different scenarios demonstrate that the robots are able to get assistance or give assistance flexibly.     

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.     

Programming for modular reconfigurable robots

Composed of multiple modular robotic units, self-reconfigurable modular robots are metamorphic systems that can autonomously rearrange the modules and form different configurations depending on dynamic environments and tasks. The goal of self-reconfiguration is to determine how to change connectivity of modules to transform the robot from the current configuration to the goal configuration subject to restrictions of physical implementation. The existing reconfiguration algorithms use different methods, such as divide-and-conquer, graph matching, and the like, to reduce the reconfiguration cost. However, an optimal solution with a minimal number of reconfiguration steps has not been found yet. The optimal reconfiguration planning problem consists in finding the least number of reconfiguration steps transforming the robot from one configuration to another. This is an NP-complete problem. In this paper, we describe an approach to solve this problem. The approach is based on constructing logical models of the problem under study.     

Line and circle formation of distributed physical mobile robots

The formation problem of distributed mobile robots was studied in the literature for idealized robots. Idealized robots are able to instantaneously move in any directions, and are equipped with perfect range sensors. In this study, we address the formation problem of distributed mobile robots that are subject to physical constraints. Mobile robots considered in this study have physical dimensions and their motions are governed by physical laws. They are equipped with sonar and infrared range sensors. The formation of lines and circles is investigated in detail. It is demonstrated that line and circle algorithms developed for idealized robots do not work well for physical robots. New line and circle algorithms, with consideration of physical robots and sensors, are presented and validated through extensive simulations. © 1997 John Wiley & Sons, Inc.     

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.     

Experimental Testbed for Large Multirobot Teams

Experimental validation is particularly important in multi-robot systems research. The differences between models and real-world conditions that may not be apparent in single robot experiments are amplified because of the large number of robots, interactions between robots, and the effects of asynchronous and distributed control, sensing, and actuation. Over the last two years, we have developed an experimental testbed to support research in multirobot systems with the goal of making it easy for users to model, design, benchmark, and validate algorithms. In this article, we describe our approach to the design of a large-scale multirobot system for the experimental verification and validation of a variety of distributed robotic applications in an indoor environment.     

Performance of local search heuristics on scheduling a class of pipelined multiprocessor tasks

This paper presents the evaluation of the solution quality of heuristic algorithms developed for scheduling multiprocessor tasks for a class of multiprocessor architectures designed to exploit temporal and spatial parallelism simultaneously. More specifically, we deal with multi-level or partitionable architectures where MIMD parallelism and multiprogramming support are the two main characteristics of the system. We investigate scheduling a number of pipelined multiprocessor tasks with arbitrary processing times and arbitrary processor requirements in this system. The scheduling problem consists of two interrelated sub-problems, which are finding a sequence of pipelined multiprocessor tasks on a processor and finding a proper mapping of tasks to the processors that are already being sequenced. For the solution of the second problem, various techniques are available. However, the problem remains of generating a feasible sequence for the pipelined operations. We employed three well-known local search heuristic algorithms that are known to be robust methods applicable to various optimization problems. These are Simulated Annealing, Tabu Search, and Genetic Algorithms. We then conduct computational experiments and evaluate the reduction achieved in completion time by each heuristic. We have also compared the results with well-known simple list-based heuristics.     

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

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

Teamwork in Self-Organized Robot Colonies

Swarm robotics draws inspiration from decentralized self-organizing biological systems in general and from the collective behavior of social insects in particular. In social insect colonies, many tasks are performed by higher order group or team entities, whose task-solving capacities transcend those of the individual participants. In this paper, we investigate the emergence of such higher order entities. We report on an experimental study in which a team of physical robots performs a foraging task. The robots are “identical” in hardware and control. They make little use of memory and take actions purely on the basis of local information.      

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.     

A flooding algorithm for multirobot exploration

In this paper, we present a multirobot exploration algorithm that aims at reducing the exploration time and to minimize the overall traverse distance of the robots by coordinating the movement of the robots performing the exploration. Modeling the environment as a tree, we consider a coordination model that restricts the number of robots allowed to traverse an edge and to enter a vertex during each step. This coordination is achieved in a decentralized manner by the robots using a set of active landmarks that are dropped by them at explored vertices. We mathematically analyze the algorithm on trees, obtaining its main properties and specifying its bounds on the exploration time. We also define three metrics of performance for multirobot algorithms. We simulate and compare the performance of this new algorithm with those of our multirobot depth first search (MR-DFS) approach presented in our recent paper and classic single-robot DFS.     

Optimal self assembly of modular manipulators with active and passive modules

In this paper, we develop self-assembling robot systems composed of active modular robots and passive bars. The target structure is modeled as a dynamic graph. We present two provably correct algorithms for creating the structure. A decentralized optimal algorithm for the navigation of multiple modular robots on a partial truss structure is used to guide the robots to their location on the target structure. A decentralized algorithm for scheduling the transportation and placement of truss elements is used to coordinate the creation of the target structure. Both algorithms rely on locally optimal matching. The truss self-assembly algorithm has quadratic competitive ratio for static as well as dynamic graph representation. We show simulation results and results for experiments with two 3DOF robots and passive bars that can create and control a 6DOF manipulation.     

Adaptive Allocation of Independent Tasks to Maximize Throughput

In this paper, we consider the task allocation problem for computing a large set of equal-sized independent tasks on a heterogeneous computing system where the tasks initially reside on a single computer (the root) in the system. This problem represents the computation paradigm for a wide range of applications such as SETI@home and Monte Carlo simulations. We consider the scenario where the systems have a general graph-structured topology and the computers are capable of concurrent communications and overlapping communications with computation. We show that the maximization of system throughput reduces to a standard network flow problem. We then develop a decentralized adaptive algorithm that solves a relaxed form of the standard network flow problem and maximizes the system throughput. This algorithm is then approximated by a simple decentralized protocol to coordinate the resources adaptively. Simulations are conducted to verify the effectiveness of the proposed approach. For both uniformly distributed and power law distributed systems, a close-to-optimal throughput is achieved, and improved performance over a bandwidth-centric heuristic is observed. The adaptivity of the proposed approach is also verified through simulations.     

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.