Multi robot task allocation

With reference to the taxonomy of Gerkey and Mataric [6], multi-robot task allocation problems can be classified along three dimensions. In the dimension of robot, it can be a single-task robot or a multi-task one. A single-task robot is capable... 

Multi-robot task allocation is a typically NP-hard problem. Its challenges become even more complicated when operations in uncertain environments, such as unexpected interference between robots, stochastic task requests, inconsistent information, and various component failures, are considered [4]. In such cases, it is not worth spending time and resources to secure an optimal solution, if the solutimi keeps changing as operations go on. Moreover, if time-window constraints are imposed, there may not be enough time to compute an exact and global solution. 

The basic objective of a multi-robot task allocation problem is to have tractable planning that produces efficient and practicable solutions. Auction-based, or market-based, approaches manage this by assembling team information at a single location to make decisions about assigning tasks over the team to produce practicable solutions quickly and concisely [8]. 

Mosteo AR, Montano L (2007) Comparative experiments on optimization criteria and algorithms for auction based multi-robot task allocation. In Proceedings of IEEE international conference on robotics and automation, Roma, Italy, pp 3345-3350... 

In this chapter, we first propose a model for the multi-robot indoor surveillance application supported by a wireless sensor network. Then, we tackle two different underlying issues in the SURV-TRACK application and propose solutions with respect to the following features (1) multi robot task allocation for target capturing and (2) path planning. 

Effective Collaboration between Robots and Sensor Nodes Presents a key challenge in our work since most robotic applications rely on autonomous robots. The incorporation of a WSN as an actor in the surveillance application will make the collaboration task more challenging indeed, three types of collaboration take place robot-to-robot, robot-to-sensor, and sensor-to-sensor collaboration models. We address the collaboration issue in Section 4 and we instantiate it as a multi-robot task allocation problem. 

MULTI-ROBOT TASK ALLOCATION FOR TARGET CAPTURING... 

Several researchers (Pizzocaro Preece, 2009 Geikey Mataric, 2004) have conducted studies to answer the following question Which robot should execute which task Dias et al. (2006) provide a good survey on multi-robot coordination (based on market-based approach) in which they propose the following formal definition of the Multi-Robot Task Allocation Problem ... 

It just happens that many multi-robot task allocation problems are NP-Hard problems these problems have no exact solutions in a polynomial time, therefore heuristics and approximate algo-rilhms are typically used to estimate solutions. The purpose of tiiis chapter is to propose solutions to this problem and apply them to the SURV-TRACK application. 

In the literature, several research works propose different solutions to the MRTA problem applied to different areas. Elmogy et al. (2009) propose a solution for the Multi Robot Task Allocation... 

Second, we tackled the problem of multi-robot task allocation for target capturing and we proposed three coordination strategies centralized, distributed and market-based. Centralized and market-based approaches were shown to provide better solution qualities in terms of traveled distance per robot and mission time as compared to the distributed strategy. This comes atthe expense of the need for global knowledge of the system status either periodically in case of centralized approach, or on demand in case of market-based approach. These results did not consider communication delay and overhead, which should impact the performance ofthese three strategies. We plan to study this issue in future work, as it is important... 

Multi Robot Task Allocation It consists in finding the efficient allocationmechanism in order to assign different tasks to the set of available robots. It aims at ensuring an efficient execution of tasks under consideration and thus minimizing the overall system cost. 

Task allocation for multiple robots addresses the problem of assigning a set of tasks to the corresponding robots while achieving some specific objectives of team performance. Research in this field dates back to the late 1980s. Task allocation of multiple robots in dynamic environments is core to multi-robot control for a number of real-world applications, such as military [1], transport services [2], search and rescue [3], etc. 

The working environments of task allocation can be static or dynamic [4]. Static task allocation assumes completely known information about the environment, such as the number of tasks and robots, the arrival time of tasks, and the process of task execution. Traditionally, applications in multi-robot domains have largely remained in static scenarios, with an aim to minimise a cost function, such as total path length, or execution time of the team. Obviously, static approaches cannot adapt to changes in a dynamic environment. 

The closed-loop bid adjustment mechanism is incorporated with a multi-robot dynamic task allocation module in a simulator, which also includes a module for motion planning of a fleet of robots. The details of this motion planning approach can be found in [21]. 

Lerman K, Jones C, Galstyan A, Mataric MJ (2006) Analysis of dynamic task allocation in multi-robot systems. Int J Robot Res 25(3) 225-241... 

Gerkey, B., Mataric, M. (2004). A formal analysis and taxonomy of task allocation in multi-robot systems. The International Journal of Robotics Research, 23(9), 939-954. doi 10.1177/0278364904045564... 

---