Tasks with Cost Growing Over Time and Agent Reallocation Delays

To efficiently complete tasks whose completion costs change predictably over time requires agents that can take into account these changes. When there are more agents than tasks the problem is how to coordinate the allocation of agents to prevent tasks from growing so much that they become unsolvable. This work focuses on a subset of cost functions for modeling tasks whose cost grows over time and provides an optimal solution when agents can be allocated to tasks instantly. We present both the Latest Finishing First (LFF) algorithm, which is suitable when the cost of reallocating agents is high, and the Real-Time Latest Finishing First (RT-LFF) algorithm, which adapts to agent reallocation delays and new tasks appearing. These algorithms are compared against the optimal zero travel time solution with varying delays in reallocation in a simple environment. We then show how to apply this model to the complex problem of allocating agents to extinguish fires in the RoboCup Rescue simulator and show how RT-LFF solves the problem efficiently.