Task Allocation with Growing Costs

Abstract

We examine task allocation when the tasks grow over time and propose a model for the interaction between agents and changing tasks. Our model accounts for both the natural growth of tasks and the effort of the agents at containing such growth. We use the model to reason spatially and temporally to achieve the objective of efficiently coordinate agents, i.e., to produce solutions that minimize the growth of tasks. This problem has a strong temporal component, as both the agents require time to move between tasks and during this time the cost of completing the tasks grow. Three different cases are examined for the agent travel time: very prohibitive where agents can only be assigned once, agents have zero travel time between tasks, and agent reassignment is possible but takes time to travel to a different task. We provide an optimal solution for when agents can only be assigned once. With zero travel time between tasks, we identify optimal solutions for three families of growth functions. New algorithms are proposed for task allocation when the travel time is not zero, and are tested with the modeling of the task growth as inaccurate. A centralized approach is proposed that is the optimal solution in some cases and performs well even when imperfectly modeling the growth. We also propose a distributed coordination algorithm (based on max-sum) that works well even when there are errors in modeling the environment and is shown to outperform other methods in both a simple simulation and the RoboCup Rescue agent simulation.