Logo PTI
Polish Information Processing Society
Logo FedCSIS

Annals of Computer Science and Information Systems, Volume 8

Proceedings of the 2016 Federated Conference on Computer Science and Information Systems

Token-based Autonomous Task Allocation in Flocking Systems

, ,

DOI: http://dx.doi.org/10.15439/2016F424

Citation: Proceedings of the 2016 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 8, pages 14611466 ()

Full text

Abstract. There are serious contributions to the theoretical foundations of flocking systems, but there are only few systems which have the capability of autonomous task allocation, however, many use cases demand this functionality. The implementation of a task allocation algorithm could be a serious challenge even in a simulated environment due to the numerous problems arising from the nature of these systems.


  1. H. M. La, W. Sheng, and J. Chen, “Cooperative and active sensing in mobile sensor networks for scalar field mapping,” Systems, Man, and Cybernetics: Systems, IEEE Transactions on, vol. 45, no. 1, pp. 1–12, 2015. http://dx.doi.org/10.1109/tsmc.2014.2318282
  2. X. Wang, J. Qin, and C. Yu, “Iss method for coordination control of nonlinear dynamical agents under directed topology,” Cybernetics, IEEE Transactions on, vol. 44, no. 10, pp. 1832–1845, 2014. http://dx.doi.org/10.1109/tcyb.2013.2296311
  3. X. Zhu, C. Wei, H. Duan, and Q. Li, “Some new results on bees-mechanism-based flock control with neighbors chosen by topological distance,” in Guidance, Navigation and Control Conference (CGNCC), 2014 IEEE Chinese, pp. 2681–2686, IEEE, 2014. http://dx.doi.org/10.1109/cgncc.2014.7007591
  4. S. H. Semnani and O. A. Basir, “Semi-flocking algorithm for motion control of mobile sensors in large-scale surveillance systems,” Cybernetics, IEEE Transactions on, vol. 45, no. 1, pp. 129–137, 2015. http://dx.doi.org/10.1109/tcyb.2014.2328659
  5. S. K. Lee, “Distributed space coverage for exploration, localization, and navigation in unknown environments,” 2015.
  6. B. Wiandt, A. Kokuti, and V. Simon, “Application of collective movement in real life scenarios: Overview of current flocking solutions,” Scalable Computing: Practice and Experience, vol. 16, no. 3, pp. 233–248, 2015. http://dx.doi.org/10.12694/scpe.v16i3.1099
  7. B. P. Gerkey and M. J. Matari, “Sold!: Auction methods for multirobot coordination,” Robotics and Automation, IEEE Transactions on, vol. 18, no. 5, pp. 758–768, 2002. http://dx.doi.org/10.1109/tra.2002.803462
  8. M. Badreldin, A. Hussein, and A. Khamis, “A comparative study between optimization and market-based approaches to multi-robot task allocation,” Advances in Artificial Intelligence, vol. 2013, p. 12, 2013. http://dx.doi.org/10.1155/2013/256524
  9. M. Koes, K. Sycara, and I. Nourbakhsh, “A constraint optimization framework for fractured robot teams,” in Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, pp. 491–493, ACM, 2006. http://dx.doi.org/10.1145/1160633.1160724
  10. P. Cramton, Y. Shoham, and R. Steinberg, “Combinatorial auctions,” 2006.
  11. M. Mito and S. Fujita, “On heuristics for solving winner determination problem in combinatorial auctions,” Journal of Heuristics, vol. 10, no. 5, pp. 507–523, 2004. http://dx.doi.org/10.1023/b:heur.0000045322.51784. 2a
  12. K. Zhang, E. G. Collins Jr, and D. Shi, “Centralized and distributed task allocation in multi-robot teams via a stochastic clustering auction,” ACM Transactions on Autonomous and Adaptive Systems (TAAS), vol. 7, no. 2, p. 21, 2012. http://dx.doi.org/10.1145/2240166.2240171
  13. T. Sandholm, “Algorithm for optimal winner determination in combinatorial auctions,” Artificial intelligence, vol. 135, no. 1, pp. 1–54, 2002. http://dx.doi.org/10.1016/s0004-3702(01)00159-x
  14. C. M. Clark, R. Morton, and G. A. Bekey, “Altruistic relationships for optimizing task fulfillment in robot communities,” in Distributed Autonomous Robotic Systems 8, pp. 261–270, Springer, 2009. http://dx.doi.org/10.1007/978-3-642-00644-9_23
  15. A. Wagner and R. Arkin, “Multi-robot communication-sensitive reconnaissance,” in Robotics and Automation, 2004. Proceedings. ICRA’04. 2004 IEEE International Conference on, vol. 5, pp. 4674–4681, IEEE, 2004. http://dx.doi.org/10.1109/robot.2004.1302455
  16. R. Powers and Y. Shoham, “New criteria and a new algorithm for learning in multi-agent systems,” in Advances in neural information processing systems, pp. 1089–1096, 2004.
  17. C. Perkins, E. Belding-Royer, and S. Das, “Ad hoc on-demand distance vector (aodv) routing,” tech. rep., 2003. http://dx.doi.org/10.17487/rfc3561
  18. R. M. Karp, Reducibility among combinatorial problems. Springer, 1972. http://dx.doi.org/10.1007/978-1-4684-2001-2_9
  19. P. M. Ruiz and A. F. Gomez-Skarmeta, “Approximating optimal multicast trees in wireless multihop networks,” in Computers and Communications, 2005. ISCC 2005. Proceedings. 10th IEEE Symposium on, pp. 686–691, IEEE, 2005. http://dx.doi.org/10.1109/iscc.2005.34
  20. L. Kou, G. Markowsky, and L. Berman, “A fast algorithm for steiner trees,” Acta informatica, vol. 15, no. 2, pp. 141–145, 1981. http://dx.doi.org/10.1007/bf00288961
  21. A. Z. Zelikovsky, “An 11/6-approximation algorithm for the network steiner problem,” Algorithmica, vol. 9, no. 5, pp. 463–470, 1993. http://dx.doi.org/10.1007/bf01187035
  22. N. Matloff, “Introduction to discrete-event simulation and the simpy language,” Davis, CA. Dept of Computer Science. University of California at Davis. Retrieved on August, vol. 2, p. 2009, 2008.
  23. D. J. Watts and S. H. Strogatz, “Collective dynamics of small-world networks,” nature, vol. 393, no. 6684, pp. 440–442, 1998.