Task Allocation with Growing Costs
2017-01
Loading...
View/Download File
Persistent link to this item
Statistics
View StatisticsJournal Title
Journal ISSN
Volume Title
Title
Task Allocation with Growing Costs
Authors
Published Date
2017-01
Publisher
Type
Thesis or Dissertation
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.
Keywords
Description
University of Minnesota Ph.D. dissertation. January 2017. Major: Computer Science. Advisor: Maria Gini. 1 computer file (PDF); vii, 91 pages.
Related to
Replaces
License
Collections
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.