|
Task allocation is a problem that must be addressed by any multi-robot system. Over the past decade, numerous solutions to the Multi-Robot Task Allocation (MRTA) problem have been proposed in the literature. However, most of the proposed solutions assign individual robots to individual tasks. In other words, the existing solutions operate under the assumption that each task may be performed by a single robot, also called the single-task single-robot (ST-SR) assignment problem.
As multi-robot systems evolve, multi-robot tasks are becoming more complex. The increase in task complexity results in situations where a task cannot be completed by a single Robot and it becomes necessary to assign a team of robots to an individual task. This problem is called the single-task multiple-robot (STMR) allocation problem and is the central theme of this work. Each such team is referred to as a coalition. The set of all disjoint coalitions is called the Coalition structure. Finding the optimal coalition structure is called the coalition formation problem and has been proven to be NP-complete. Solutions to the coalition formation problem have many potential applications, especially in situations where tasks are located at considerable distances from one another and teams of robots need to be dispatched to different locations to autonomously complete their designated tasks.
Despite the existence of various multi- agent coalition formation algorithms, none of these algorithms had been demonstrated in the multi-robot domain. Although not heavily pursued in Multi-Robot Systems (MRS), coalition formation is an established area of Distributed Artificial Intelligence (DAI) research, and various heuristics have been proposed that yield good, tractable, sub-optimal solutions. However, these solutions make underlying assumptions that are not applicable to the multiple-robot domain, hence the existence of a discrepancy between the multi-agent and multi-robot coalition formation literature. Our prior work identifies these assumptions and provides modifications to multi-agent coalition formation algorithms to enable their use in the multi-robot domain. In this paper we outline extensions of this work so as to provide a framework for allocation of multi-robot (MR) tasks. In particular, we present RACHNA1, a novel dynamic, market-based architecture for allocating multi-robot tasks based on Individual robot capabilities.
|
