Minimising Task Tardiness for Multi-Agent Pickup and Delivery

Multi-agent pickup and delivery, a variant of the multi-agent path finding problem, aims to find collision-free paths for a set of agents performing a continuous stream of pickup and delivery tasks. Owing to the service guarantee nature of applications, these agents often need to execute the tasks within their stipulated deadlines. When failure to meet task deadlines is unavoidable, there is a need to minimise the tardiness experienced by the tasks. To address this problem, we propose a cost-based integrated task assignment and path planning algorithm to assign tasks to the agents.