Token-based Autonomous Task Allocation in Flocking Systems
András Kőkuti, Vilmos Simon, Bernát Wiandt
Citation: Proceedings of the 2016 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 8, pages 1461–1466 (2016)
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.
- 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
- 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
- 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
- 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
- S. K. Lee, “Distributed space coverage for exploration, localization, and navigation in unknown environments,” 2015.
- 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
- 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
- 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
- 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
- P. Cramton, Y. Shoham, and R. Steinberg, “Combinatorial auctions,” 2006.
- 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
- 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
- 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
- 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
- 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
- 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.
- 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
- R. M. Karp, Reducibility among combinatorial problems. Springer, 1972. http://dx.doi.org/10.1007/978-1-4684-2001-2_9
- 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
- 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
- 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
- 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.
- D. J. Watts and S. H. Strogatz, “Collective dynamics of small-world networks,” nature, vol. 393, no. 6684, pp. 440–442, 1998.