Decentralized Game-Theoretic Control for Dynamic Task Allocation Problems for Multi-Agent Systems

We propose a decentralized game-theoretic framework for dynamic task allocation problems for multi-agent systems. In our problem formulation, the agents' utilities depend on both the rewards and the costs associated with the successful completion of the tasks assigned to them. The rewards reflect how likely is for the agents to accomplish their assigned tasks whereas the costs reflect the effort needed to complete these tasks (this effort is determined by the solution of corresponding optimal control problems). The task allocation problem considered herein corresponds to a dynamic game whose solution depends on the states of the agents in contrast with classic static (or single-act) game formulations. We propose a greedy solution approach in which the agents negotiate with each other to find a mutually agreeable (or individually rational) task assignment profile based on evaluations of the task utilities that reflect their current states. We illustrate the main ideas of this work by means of extensive numerical simulations.

I. Introduction

We consider a dynamic task allocation problem for a multi-agent system whose agents have continuous state and input spaces and have to complete a set of spatially distributed tasks (obtain in-situ measurements or pick up packages from different locations over a given spatial domain). We adopt a game-theoretic approach which seeks for task assignments that maximize the individual utility of each agent conditional on the assignments of their teammates (individual rationality principle) while also ensuring that the self-interests of the agents are aligned with those of the team. To this aim, we design the agents' utilities based on the concept of wonderful life utility [1] (WLU) which allows us to associate the dynamic task allocation problem with a sequence of potential games [2]. We propose a greedy decentralized algorithm that computes task assignment profiles which are mutually agreeable in the long run.