Document Open Access Logo

Lower Bounds for Dynamic Distributed Task Allocation

Authors Hsin-Hao Su, Nicole Wein

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.99.pdf
  • Filesize: 429 kB
  • 14 pages

Document Identifiers

Author Details

Hsin-Hao Su
  • Boston College, MA, USA
Nicole Wein
  • Massachusetts Institute of Technology, Cambridge, MA, USA

Funding

  • Wein, Nicole: supported by an NSF Graduate Fellowship and NSF Grant CCF-1514339.

Acknowledgements

We would like to thank Yufei Zhao for a discussion.

Cite As Get BibTex

Hsin-Hao Su and Nicole Wein. Lower Bounds for Dynamic Distributed Task Allocation. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 99:1-99:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ICALP.2020.99

Abstract

We study the problem of distributed task allocation in multi-agent systems. Suppose there is a collection of agents, a collection of tasks, and a demand vector, which specifies the number of agents required to perform each task. The goal of the agents is to cooperatively allocate themselves to the tasks to satisfy the demand vector. We study the dynamic version of the problem where the demand vector changes over time. Here, the goal is to minimize the switching cost, which is the number of agents that change tasks in response to a change in the demand vector. The switching cost is an important metric since changing tasks may incur significant overhead.
We study a mathematical formalization of the above problem introduced by Su, Su, Dornhaus, and Lynch [Su et al., 2017], which can be reformulated as a question of finding a low distortion embedding from symmetric difference to Hamming distance. In this model it is trivial to prove that the switching cost is at least 2. We present the first non-trivial lower bounds for the switching cost, by giving lower bounds of 3 and 4 for different ranges of the parameters.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • distributed task allocation
  • combinatorics
  • lower bounds
  • multi-agent systems
  • low-distortion embedding
  • dynamic algorithms
  • biological distributed algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Samuel N Beshers and Jennifer H Fewell. Models of division of labor in social insects. Annual review of entomology, 46(1):413-440, 2001. Google Scholar
  2. Eduardo Castello, Tomoyuki Yamamoto, Yutaka Nakamura, and Hiroshi Ishiguro. Task allocation for a robotic swarm based on an adaptive response threshold model. In 2013 13th International Conference on Control, Automation and Systems (ICCAS 2013), pages 259-266. IEEE, 2013. Google Scholar
  3. Jianing Chen. Cooperation in Swarms of Robots without Communication. PhD thesis, University of Sheffield, 2015. Google Scholar
  4. Alejandro Cornejo, Anna Dornhaus, Nancy Lynch, and Radhika Nagpal. Task allocation in ant colonies. In International Symposium on Distributed Computing, pages 46-60. Springer, 2014. Google Scholar
  5. Anna Dornhaus, Nancy Lynch, Frederik Mallmann-Trenn, Dominik Pajak, and Tsvetomira Radeva. Self-stabilizing task allocation in spite of noise. arXiv preprint, 2018. URL: http://arxiv.org/abs/1805.03691.
  6. Ana Duarte, Ido Pen, Laurent Keller, and Franz J Weissing. Evolution of self-organized division of labor in a response threshold model. Behavioral ecology and sociobiology, 66(6):947-957, 2012. Google Scholar
  7. Chryssis Georgiou and Alexander A Shvartsman. Cooperative task-oriented computing: Algorithms and complexity. Synthesis Lectures on Distributed Computing Theory, 2(2):1-167, 2011. Google Scholar
  8. Serge Kernbach, Dagmar Häbe, Olga Kernbach, Ronald Thenius, Gerald Radspieler, Toshifumi Kimura, and Thomas Schmickl. Adaptive collective decision-making in limited robot swarms without communication. The International Journal of Robotics Research, 32(1):35-55, 2013. Google Scholar
  9. Min-Hyuk Kim, Hyeoncheol Baik, and Seokcheon Lee. Response threshold model based uav search planning and task allocation. Journal of Intelligent & Robotic Systems, 75(3-4):625-640, 2014. Google Scholar
  10. Michael JB Krieger, Jean-Bernard Billeter, and Laurent Keller. Ant-like task allocation and recruitment in cooperative robots. Nature, 406(6799):992, 2000. Google Scholar
  11. Kristina Lerman, Chris Jones, Aram Galstyan, and Maja J Matarić. Analysis of dynamic task allocation in multi-robot systems. The International Journal of Robotics Research, 25(3):225-241, 2006. Google Scholar
  12. Kathryn Sarah Macarthur, Ruben Stranders, Sarvapali D Ramchurn, and Nicholas R Jennings. A distributed anytime algorithm for dynamic task allocation in multi-agent systems. In AAAI, pages 701-706, 2011. Google Scholar
  13. James McLurkin and Daniel Yamins. Dynamic task assignment in robot swarms. In Robotics: Science and Systems, volume 8. Citeseer, 2005. Google Scholar
  14. James Dwight McLurkin. Stupid robot tricks: A behavior-based distributed algorithm library for programming swarms of robots. PhD thesis, Massachusetts Institute of Technology, 2004. Google Scholar
  15. George F Oster and Edward O Wilson. Caste and ecology in the social insects. Princeton University Press, 1979. Google Scholar
  16. Jacques Penders, Lyuba Alboul, Ulf Witkowski, Amir Naghsh, Joan Saez-Pons, Stefan Herbrechtsmeier, and Mohamed El-Habbal. A robot swarm assisting a human fire-fighter. Advanced Robotics, 25(1-2):93-117, 2011. Google Scholar
  17. Tsvetomira Radeva, Anna Dornhaus, Nancy Lynch, Radhika Nagpal, and Hsin-Hao Su. Costs of task allocation with local feedback: Effects of colony size and extra workers in social insects and other multi-agent systems. PLoS computational biology, 13(12):e1005904, 2017. Google Scholar
  18. Gene E Robinson. Regulation of division of labor in insect societies. Annual review of entomology, 37(1):637-665, 1992. Google Scholar
  19. Erol Şahin. Swarm robotics: From sources of inspiration to domains of application. In International workshop on swarm robotics, pages 10-20. Springer, 2004. Google Scholar
  20. Hsin-Hao Su, Lili Su, Anna Dornhaus, and Nancy Lynch. Ant-inspired dynamic task allocation via gossiping. In International Symposium on Stabilization, Safety, and Security of Distributed Systems, pages 157-171. Springer, 2017. Google Scholar
  21. Zijian Wang and Mac Schwager. Multi-robot manipulation with no communication using only local measurements. In CDC, pages 380-385, 2015. Google Scholar
  22. Yongming Yang, Changjiu Zhou, and Yantao Tian. Swarm robots task allocation based on response threshold model. In 2009 4th International Conference on Autonomous Robots and Agents, pages 171-176. IEEE, 2009. Google Scholar
  23. Emaad Mohamed H Zahugi, Mohamed M Shanta, and TV Prasad. Oil spill cleaning up using swarm of robots. In Advances in Computing and Information Technology, pages 215-224. Springer, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact