Market-based task assignment for multi-point dynamic aggregation tasks

Multi-agent task assignment problem exists in collaborative target tracking, collaborative rescue, regional search, etc. Most researchers regarding multi-agent task assignment only consider static tasks. However, in complex scenarios, the states of tasks (e.g., Monitoring of hazardous environments) are time-varying. This type of the task can be modeled as a multi-point dynamic aggregation (MPDA) process. This paper proposes a distributed task assignment method for the MPDA task. This method firstly adopts an auction algorithm to obtain a pre-allocation planning that can ensure every task can be completed. Then, the agents who complete the pre-allocation planning will evaluate the uncompleted tasks and assist other agents to complete these tasks, so that tasks can be completed as soon as possible. Compared with the optimal solution, simulations show that the task allocation method can obtain satisfied allocation solutions with a lower computational cost. The gap from the optimal solution is only 8% on average. Especially, for problems including more than 100 tasks, the proposed method can obtain planning solutions within one second, and the makespan of the MPDA task is more than 50% better than the best one of the 1000 random sample solutions.