Task Allocation with Growing Costs

Thumbnail Image

Persistent link to this item

View Statistics

Journal Title

Journal ISSN

Volume Title


Task Allocation with Growing Costs

Published Date




Thesis or Dissertation


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.



University of Minnesota Ph.D. dissertation. January 2017. Major: Computer Science. Advisor: Maria Gini. 1 computer file (PDF); vii, 91 pages.

Related to




Series/Report Number

Funding information

Isbn identifier

Doi identifier

Previously Published Citation

Suggested citation

Parker, James. (2017). Task Allocation with Growing Costs. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/185583.

Content distributed via the University Digital Conservancy may be subject to additional license and use restrictions applied by the depositor. By using these files, users agree to the Terms of Use. Materials in the UDC may contain content that is disturbing and/or harmful. For more information, please see our statement on harmful content in digital repositories.