Adaptive Multi-agent System for Situated Task Allocation
Quentin Baert, Anne-Cécile Caron, Maxime Morge, Jean-Christophe Routier, Kostas Stathis · 2019
Multi-agent scheduling has received significant attention in tackling the problem of load balancing and task allocation in distributed systems. Apart from dividing the work through decentralization, we consider dynamicity because allocation of tasks must be concurrent with their execution, and adaptation because tasks must be reallocated when a disruptive event is performed. We will assume that agents are fully distributed and cooperative in order to optimize the global runtime, i.e a system-centric metric rather than user-centric metrics. We will also assume that a task can be performed by any single agent without preemption and precedence order. Moreover, tasks have no deadlines, are indivisible and not shareable. We follow a market-based approach to tackle the multi-agent situated task allocation problem. In order to improve load balancing, agents adopt a locality-based strategy in concurrent one-to-many negotiations for task delegations. The task reallocation is dynamic since the negotiation process is iterated and concurrent with the tasks processing. Moreover, the system is adaptive to disruptive events, e.g. task consumptions. As a practical application, we consider the distributed deployment of the MapReduce design pattern for processing large datasets. Our preliminary empirical results show that, for such an application, the locality-based strategy improves the runtime.