A proposal toward a possibilistic multi-robot task allocation

One of the main problems to solve in multi-agent (or multi-robot) systems is to select the best robot or group of robots to carry out a specific task. This problem, referenced as Multi-Agent (robot) task allocation (MRTA), is still an open issue in real environments. Swarm intelligence methods provide very simple solutions for the MRTA problem. One of the most widely used swarm methods are the so-called Response Threshold algorithms, where the behavior of the systems is modeled as a Markov chain and the robots in each time step select the next task to execute according to a transition probability function. Among other factors, this probability depends on a stimulus (for example the distance between the robot and the task). This classical probabilistic approach presents a lot of disadvantages:the transition function must meet constraints of a probabilistic distribution, the system only convergences to a stationary asymptotically, and so on. In order to overcome these problems, a new theoretical framework based on fuzzy (possibilistic) Markov chains was proposed [2]. As was proved, the possibilistic Markov chains outperform the classical probabilistic when a Max-Min algebra is considered for matrix composition. For example, fuzzy Markov chains convergence to a stable state in a finite number of steps 10 times faster than its probability counter part. Moreover, they improve the predictions of the system under imprecise information. Firstly, this paper will review relevant work in MRTA, from theoretical and experimental point of view. Then it will be summarized the aforementioned recent advances given toward a new possibilistic swarm multi-robot task allocation framework. It will be seen how the possibilistic Markov chains behave when other algebras are considered for matrix composition [1] and how the possibility transition function impacts on the system's performance [3]. Finally, it will be proposed new future works in this field. (Author)