Repeated auctions for robust task execution by a robot team

We present empirical results of an auction-based algorithm for dynamic allocation of tasks to robots. The results have been obtained both in simulation and using real robots. A distinctive feature of our algorithm is its robustness to uncertainties and to robot malfunctions that happen during task execution, when unexpected obstacles, loss of communication, and other delays may prevent a robot from completing its allocated tasks. Therefore tasks not yet achieved are resubmitted for bids every time a task has been completed. This provides an opportunity to improve the allocation of the remaining tasks, enabling the robots to recover from failures and reducing the overall time for task completion.     

Distributed Service-Based Cooperation in Aerial/Ground Robot Teams Applied to Fire Detection and Extinguishing Missions

This paper presents a system for the coordination of aerial and ground robots for applications such as surveillance and intervention in emergency management. The overall system architecture is described. An important part for the coordination between robots is the task allocation strategy. A distributed market-based algorithm, called S + T, has been developed to solve the multi-robot task allocation problem in applications that require cooperation among the robots to accomplish all the tasks. Using this algorithm, robots can provide transport and communication relay services dynamically to other robots during the missions. Moreover, the paper presents a demonstration with a team of heterogeneous robots (aerial and ground) cooperating in a mission of fire detection and extinguishing.     

COBOS: Cooperative backoff adaptive scheme for multirobot task allocation

In this paper, the cooperative backoff adaptive scheme (COBOS) is proposed for task allocation amongst a team of heterogeneous robots. The COBOS operates in regions with limited communication ranges, and is robust against robot malfunctions and uncertain task specifications, with each task potentially requiring multiple robots. The portability of tasks across teams (or when team demography changes) is improved by specifying tasks using basis tasks in a matrix framework. The adaptive feature of COBOS further increases the flexibility of robot teams, allowing robots to adjust their actions based on past experience. In addition, we study the properties of COBOS: operation domain; communication requirements; computational complexity; and solution quality; and compare the scheme with other task-allocation mechanisms. Realistic simulations are carried out to verify the effectiveness of the proposed scheme.     

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.     

基于市场法及能力分类的多机器人任务分配方法

针对多机器人系统研究中如何有效地实现复杂任务的分布式动态分配这个基础性问题，提出了一种对这类问题进行形式化描述的一般方法．该方法从能力分类的角度出发，提出了机器人及任务能力向量的概念，并对多机器人任务分配问题进行了形式化描述，讨论了单个及多个机器人合作完成任务的能力条件．基于这种形式化描述方法，提出了一种采用市场机制的完全分布式的多机器人任务分配方法．仿真实验结果表明该方法能够有效地实现多机器人复杂任务的动态分布式分配．     

Balancing task allocation in multi-robot systems using K-means clustering and auction based mechanisms

This paper aims to solve the balanced multi-robot task allocation problem. Multi-robot systems are becoming more and more significant in industrial, commercial and scientific applications. Effectively allocating tasks to multi-robots i.e. utilizing all robots in a cost effective manner becomes a tedious process. The current attempts made by the researchers concentrate only on minimizing the distance between the robots and the tasks, and not much importance is given to the balancing of work loads among robots. It is also found from the literature that the multi-robot system is analogous to Multiple Travelling Salesman Problem (MTSP). This paper attempts to develop mechanism to address the above two issues with objective of minimizing the distance travelled by ‘m’ robots and balancing the work load between ‘m’ robots equally. The proposed approach has two fold, first develops a mathematical model for balanced multi-robot task allocation problem, and secondly proposes a methodology to solve the model in three stages. Stage I groups the ‘N’ tasks into ‘n’ clusters of tasks using K-means clustering technique with the objective of minimizing the distance between the tasks, stage II calculates the travel cost of robot and clusters combination, stage III allocates the robot to the clusters in order to utilise all robot in a cost effective manner.     

Analysis of processor allocation in multiprogrammed,distributed-memory parallel processing systems

A main objective of scheduling independent jobs composed of multiple sequential tasks in shared-memory and distributed-memory multiprocessor computer systems is the assignment of these tasks to processors in a manner that ensures efficient operation of the system. Achieving this objective requires the analysis of a fundamental tradeoff between maximizing parallel execution, suggesting that the tasks of a job be spread across all system processors, and minimizing synchronization and communication overheads, suggesting that the job's tasks be executed on a single processor. The authors consider a class of scheduling policies that represent the essential aspects of this processor allocation tradeoff, and model the system as a distributed fork-join queueing system. They derive an approximation for the expected job response time, which includes the important effects of various parallel processing overheads (such as task synchronization and communication) induced by the processor allocation policy     

智能仓储中的多机器人调度方法

近年来,传统仓储系统已满足不了日益增长的订单需求并已渐渐向智能仓储转变。针对智能仓储中移动机器人的调度问题,以移动机器人执行任务时的转向次数、路程代价、最大任务等待时间为优化目标,提出一种兼顾任务分配和路径规划的调度算法。算法采用遗传算法进行任务分配,同时以多个移动机器人为目标进行任务分配,保证每个机器人分配到的任务没有重复。然后采用Q-learning算法对机器人分配到的任务进行路径规划,根据转向次数和路程代价约束路径,对于路径转向和每一步可行的动作均设有惩罚值,最终形成一条转向次数少、行程较短的路径。通过将该算法与其他算法进行对比,证实了该算法的有效性。     

Using task migration to improve non-contiguous processor allocation in NoC-based CMPs

In this paper, a processor allocation mechanism for NoC-based chip multiprocessors is presented. Processor allocation is a well-known problem in parallel computer systems and aims to allocate the processing nodes of a multiprocessor to different tasks of an input application at run time. The proposed mechanism targets optimizing the on-chip communication power/latency and relies on two procedures: processor allocation and task migration. Allocation is done by a fast heuristic algorithm to allocate the free processors to the tasks of an incoming application when a new application begins execution. The task-migration algorithm is activated when some application completes execution and frees up the allocated resources. Task migration uses the recently deallocated processors and tries to rearrange the current tasks in order to find a better mapping for them. The proposed method can also capture the dynamic traffic pattern of the network and perform task migration based on the current communication demands of the tasks. Consequently, task migration adapts the task mapping to the current network status. We adopt a non-contiguous processor allocation strategy in which the tasks of the input application are allowed to be mapped onto disjoint regions (groups of processors) of the network. We then use virtual point-to-point circuits, a state-of-the-art fast on-chip connection designed for network-on-chips, to virtually connect the disjoint regions and make the communication latency/power closer to the values offered by contiguous allocation schemes. The experimental results show considerable improvement over existing allocation mechanisms.     

Punctual versus continuous auction coordination for multi-robot and multi-task topological navigation

This paper addresses the interest of using punctual versus continuous coordination for mobile multi-robot systems where robots use auction sales to allocate tasks between them and to compute their policies in a distributed way. In continuous coordination, one task at a time is assigned and performed per robot. In punctual coordination, all the tasks are distributed in Rendezvous phases during the mission execution. However, tasks allocation problem grows exponentially with the number of tasks. The proposed approach consists in two aspects: (1) a control architecture based on topological representation of the environment which reduces the planning complexity and (2) a protocol based on sequential simultaneous auctions (SSA) to coordinate Robots’ policies. The policies are individually computed using Markov Decision Processes oriented by several goal-task positions to reach. Experimental results on both real robots and simulation describe an evaluation of the proposed robot architecture coupled wih the SSA protocol. The efficiency of missions’ execution is empirically evaluated regarding continuous planning.     

Task allocation for maximizing reliability of distributed systems: A simulated annealing approach

This paper addresses the problem of task allocation in heterogeneous distributed systems with the goal of maximizing the system reliability. It first develops an allocation model for reliability based on a cost function representing the unreliability caused by the execution of tasks on the system processors and the unreliability caused by the interprocessor communication time subject to constraints imposed by both the application and the system resources. It then presents a heuristic algorithm derived from the well-known simulated annealing (SA) technique to quickly solve the mentioned problem. The performance of the proposed algorithm is evaluated through experimental studies on a large number of randomly generated instances. Indeed, the quality of solutions are compared with those derived by using the branch-and-bound (BB) technique.     

Gradual spatial pattern formation of homogeneous robot group

This paper proposes a gradual formation of a spatial pattern for a homogeneous robot group. The autonomous formation of spatial pattern is one of key technologies for the advancement of cooperative robotic systems because a pattern formation can be regarded as function differentiation of a multi-agent system. When multiple autonomous robots without a given local task cooperatively work for a global objective, the function differentiation is the first and indispensable step. For example, each member of cooperative insects or animals can autonomously recognize own local tasks through mutual communication with local members. There were a lot of papers that reported a spatial pattern formation of multiple robots, but the global information was supposed to be available in their approaches. It is however almost impractical assumption for a small robot to be equipped with an advanced sensing system for global localization due to robot’s scale and sensor size. The local information-based algorithm for the pattern formation is desired even if each robot is not equipped with a global localization sensor.We therefore propose a gradual pattern formation algorithm, i.e., a group of robots improves complexity of their pattern from to a simple pattern to a goal pattern like a polygon. In the algorithm, the Turing diffusion-driven instability theory is used so that it could differentiate roles of each robot in a group based only on local information. In experiment, we demonstrate that robots can make a few polygon patterns from a circle pattern by periodically differentiating robot’s roles into a vertex or a side. We show utilities of the proposed gradual pattern formation algorithm for multiple autonomous robots based on local information through some experiments.     

Optimized Stochastic Policies for Task Allocation in Swarms of Robots

We present a scalable approach to dynamically allocating a swarm of homogeneous robots to multiple tasks, which are to be performed in parallel, following a desired distribution. We employ a decentralized strategy that requires no communication among robots. It is based on the development of a continuous abstraction of the swarm obtained by modeling population fractions and defining the task allocation problem as the selection of rates of robot ingress and egress to and from each task. These rates are used to determine probabilities that define stochastic control policies for individual robots, which, in turn, produce the desired collective behavior. We address the problem of computing rates to achieve fast redistribution of the swarm subject to constraint(s) on switching between tasks at equilibrium. We present several formulations of this optimization problem that vary in the precedence constraints between tasks and in their dependence on the initial robot distribution. We use each formulation to optimize the rates for a scenario with four tasks and compare the resulting control policies using a simulation in which 250 robots redistribute themselves among four buildings to survey the perimeters.      

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.     

An anatomy of industrial robots and their controls

In the United States, commercially available industrial robots perform very well in limited areas of industrial tasks such as arc welding, paint spraying, etc. These tasks mainly involve synchronization but no task interaction. A close examination of the basic structure and controls of the robots reveals their resulting limitations which lead to unnatural specifications and inefficient performance of task interactions. It is our opinion that, to expand the range of robot tasks to include labor intensive jobs such as product assembly, sensors of multiple purposes must be added onto the robots and integrated into their control systems. Computer command language must be developed to enable nonexpert users to operate the robots, and a work-method must be available for analyzing robot time-motion so that the robots can be programmed to achieve best efficiency with least production cost.     

A heterogeneous modular robotic design for fast response to a diversity of tasks

This paper describes a heterogeneous modular robot system design which attempts to give a quick solution to a diversity of tasks. The approach is based on the use of an inventory of three types of modules i.e., power and control module, joint module and specialized module. Each module type aims to balance versatility and functionality. Their design permits rapid and cost effective design and fabrication. They are interchangeable in different ways to form different robot or system configurations. Depending on the task, the operator decides what type of robot can provide the best performance within the mission. A spherical joint module is described and used to build different robots, hence, forward and inverse kinematics models are obtained. Finally, from the modules described in this work, several robot configurations such as robotic arms, leg-based robots and wheel-based robots are assembled to demonstrate the execution of manipulation and locomotion tasks.     

A PATH PLANNING METHOD BASED ON CELLULAR AUTOMATA FOR COOPERATIVE ROBOTS

A Cellular Automaton-based technique suitable for solving the path planning problem in a distributed robot team is outlined. Real-time path planning is a challenging task that has many applications in the fields of artificial intelligence, moving robots, virtual reality, and agent behavior simulation. The problem refers to finding a collision-free path for autonomous robots between two specified positions in a configuration area. The complexity of the problem increases in systems of multiple robots. More specifically, some distance should be covered by each robot in an unknown environment, avoiding obstacles found on its route to the destination. On the other hand, all robots must adjust their actions in order to keep their initial team formation immutable. Two different formations were tested in order to study the efficiency and the flexibility of the proposed method. Using different formations, the proposed technique could find applications to image processing tasks, swarm intelligence, etc. Furthermore, the presented Cellular Automaton (CA) method was implemented and tested in a real system using three autonomous mobile minirobots called E-pucks. Experimental results indicate that accurate collision-free paths could be created with low computational cost. Additionally, cooperation tasks could be achieved using minimal hardware resources, even in systems with low-cost robots.     

An effective iterated greedy algorithm for reliability-oriented task allocation in distributed computing systems

This paper investigates the problem of allocating parallel application tasks to processors in heterogeneous distributed computing systems with the goal of maximizing the system reliability. The problem of finding an optimal task allocation for more than three processors is known to be NP-hard in the strong sense. To deal with this challenging problem, we propose a simple and effective iterative greedy algorithm to find the best possible solution within a reasonable amount of computation time. The algorithm first uses a constructive heuristic to obtain an initial assignment and iteratively improves it in a greedy way. We study the performance of the proposed algorithm over a wide range of parameters including problem size, the ratio of average communication time to average computation time, and task interaction density. The viability and effectiveness of our algorithm is demonstrated by comparing it with recently proposed task allocation algorithms for maximizing system reliability available in the literature.     

Task allocation for maximizing reliability of distributed computing systems using honeybee mating optimization

This paper deals with the problem of task allocation (i.e., to which processor should each task of an application be assigned) in heterogeneous distributed computing systems with the goal of maximizing the system reliability. The problem of finding an optimal task allocation is known to be NP-hard in the strong sense. We propose a new swarm intelligence technique based on the honeybee mating optimization (HBMO) algorithm for this problem. The HBMO based approach combines the power of simulated annealing, genetic algorithms with a fast problem specific local search heuristic to find the best possible solution within a reasonable computation time. We study the performance of the algorithm over a wide range of parameters such as the number of tasks, the number of processors, the ratio of average communication time to average computation time, and task interaction density of applications. The effectiveness and efficiency of our algorithm are demonstrated by comparing it with recently proposed task allocation algorithms for maximizing system reliability available in the literature.     

LOGUE: an architecture for task and behavior object transmission among multiple autonomous robots

This paper proposes a new communication and control architecture which improves the capability and the flexibility of multiple autonomous robot systems in performing a complicated task and coping with unpredictable situations. This system treats robot’s information as a Behavior Element Object (BEO) and a Task Object (TO) in terms of Object Oriented paradigm. Both BEO and TO can be serialized, so they can be communicated among the robots and behavior server system in the network. The action manager module, device module, and some checking mechanisms are also designed for executing new TO or BEO sent from other robots or a server system. A simulation and basic experiments are presented for a situation of robots’ relief for an emergency purpose.