Article Preview
Top1. Introduction
The industry needs have pushed more and more the development of robotic systems with a very advanced technology. Therefore, the industry leaders have a tendency to use the multi-robot systems [MRS] for saving time and minimise the logistics cost in order to increase their earnings. However, the design of MRS requires a particular attention to the nature of tasks and the uncertainty in its execution by robots in a dynamic industrial environment (Kumar et al. 2016). In other word, such system required a mechanism of decomposition and assignment of sub-tasks between robots to meet certain criteria (Yan et al. 2012). The process of assigning individual robots to sub-tasks by centralised controller is called centralised task allocation. But when this process is repeated by several robots and at the same time, it is called parallel dynamic task allocation [PDTA](Lerman et al. 2006).
In PDTA there is an absence of the central control mechanism, in which task allocation decision-making is usually the result of the interaction “ robots-robots ” or as a result of the interactions “ robots-environment ”. Most “ robots-robots ” interaction approaches assume that a reliable communication between robots is necessary for the task allocation process. In “ robots-environment ” interaction approaches with which this paper is concerned, there is very little or no direct communication between robots. In this case, the task allocation decision-making will result from the implicit coordination that can emerge through indirect communication of the robot in its environment. (Gerkey and Matarić 2004; Zlot et al. 2002).
Several approaches have been proposed to adress PDTA problem. Gerkey (Gerkey and Matarić 2004; Lerman et al. 2006) proposed a mathematical model of a general dynamic task allocation mechanism to solve PDTA without communication. This model assumes that robot estimates the state of the environment and decides which task to choose based on its observations. The authors have also analysed the effect of observations and decisions of robots on the system performance. Korsah et al.(2013) have presented a taxonomy of task allocation in multi-robot systems called “iTex” that complete the taxonomy proposed in (Gerkey and Matarić 2004). iTex takes into consideration the 'utility of robots' in performing tasks and formulating them as a mathematical function. In the literature of task allocation, several methods have been proposed to define this utility function, where each method depends on the criteria that should be optimised by the task allocation process. For example, in (Dahl et al. 2009), the method requires a prior knowledge about the nature of the tasks, and the individual capabilities of each robot to calculate the value of the utility function. In (Gerkey and Matarić 2004), the utility function is defined as the difference between the cost and the quality of executing task and its value is used to estimate the robot's performances. In (Zlot et al. 2002), the value of the utility function is computed based on robot's observations. Dahl et al. (2009) have defined the utility function assuming that individual robots are prone to failures or malfunction and proposed a task allocation algorithm in a multi-robot system based on “vacancy chains”. The authors have compared a vacancy chains algorithm with random and static task allocation algorithms.
In (Wang and De Silva 2008), a “machine-learning” approach is proposed to resolve the robot task allocation problem in an unknown and dynamic environment. In (Dasgupta 2011; Wawerla and Vaughan 2010) authors have used heuristic algorithm for efficient foraging task allocation in robot teams. Tsalatsanis et al.(2009) have presented a dynamic task allocation using “fuzzy logic” in real-time to compute the value of utility functions that quantifying the ability of the robot to perform a task. The Fuzzy logic has also used in (Islam and Akhtar 2017) for allocating tasks in the multi-robot system based on a model of the ant colony.