  We propose a decentralized auction-based algorithm for the solution of
dynamic task allocation problems for spatially distributed multi-agent systems.
In our approach, each member of the multi-agent team is assigned to at most one
task from a set of spatially distributed tasks, while several agents can be
allocated to the same task. The task assignment is dynamic since it is updated
at discrete time stages (iterations) to account for the current states of the
agents as the latter move towards the tasks assigned to them at the previous
stage. Our proposed methods can find applications in problems of resource
allocation by intelligent machines such as the delivery of packages by a fleet
of unmanned or semi-autonomous aerial vehicles. In our approach, the task
allocation accounts for both the cost incurred by the agents for the completion
of their assigned tasks (e.g., energy or fuel consumption) and the rewards
earned for their completion (which may reflect, for instance, the agents'
satisfaction). We propose a Greedy Coalition Auction Algorithm (GCAA) in which
the agents possess bid vectors representing their best evaluations of the task
utilities. The agents propose bids, deduce an allocation based on their bid
vectors and update them after each iteration. The solution estimate of the
proposed task allocation algorithm converges after a finite number of
iterations which cannot exceed the number of agents. Finally, we use numerical
simulations to illustrate the effectiveness of the proposed task allocation
algorithm (in terms of performance and computation time) in several scenarios
involving multiple agents and tasks distributed over a spatial 2D domain.
