Abstract
This paper presents an approach to solve the variant of the well-known Travelling Salesman Problem (TSP) by using a gamesourcing approach. In contemporary literature is TSP solved by wide spectra of modern as well as classical computational methods. We would like to point out the possibility to solve such problems by computer game plying that is called a gamesourcing. Gamesourcing can be understood as a version of game-driven crowdsourcing. The main part and contribution of this paper is a demonstration of gamesourcing use in the game called Labyrinth that reflects TSP structure. The game has a form of a maze-labyrinth that enables players to move through it like the Ant Colony Optimization. The playing of the Labyrinth, thus, by playing, solves the problem. The performance of the “human ant-like system” is then evaluated and compared against some well-known versions of ACO. As we believe, our experiments suggest that this approach can serve as an alternative way that employs gamesourcing to assist a combinatorial optimizer in achieving better results on a well-known NP-hard optimization problem.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Notes
References
Arleth J (2017) Computer Games, Gamesourcing and Swarm Intelligence in Problem Solution, FEI, VSB - Technical university of Ostrava, Thesis
Ashby WR (1968) Some consequences of bremermann’s limit for information-processing systems. In: Cybernetic problems in bionics, vol 76
Aškić L, Mimica N, Šimić G, Mimica N, Huić T, Dajčić T (2016) Sea hero quest-with videogame to scientific advancement in the understanding of dementia. Neurol Croatica Suppl 65(Suppl. 2):93–93
Baniasadi P, Foumani M, Smith-Miles K, Ejov V (2020) A transformation technique for the clustered generalized traveling salesman problem with applications to logistics. Eur J Oper Res
Bernstein E, Shore J, Lazer D (2018) How intermittent breaks in interaction improve collective intelligence. Proc Natl Acad Sci 115(35):8734–8739
Bloom V, Argyriou V, Makris D (2014) G3di: a gaming interaction dataset with a real time detection and evaluation framework. In: Workshop at the European conference on computer vision. Springer, pp 698–712
Brabham DC (2008) Crowdsourcing as a model for problem solving: an introduction and cases. Convergence 14(1):75–90
Brabham DC (2013) Crowdsourcing. Wiley Online Library, New York
Bremermann HJ (1962) Optimization through evolution and recombination. Self-organizing Syst 93:106
Bullnheimer B, Hartl RF, Strauss C (1999) An improved ant system algorithm for thevehicle routing problem. Ann Oper Res 89:319–328
Bullnheimer B, Hartl RF, Strauss C (1997) A new rank based version of the ant system: a computational study
Cárdenas-Montes M (2018) Creating hard-to-solve instances of travelling salesman problem. Appl Soft Comput 71:268–276
Chen J, Fornés A, Mas J, Lladós J, Pujadas JM (2012) Word-hunter: speeding up the transcription of manuscripts via gamesourcing. VIENNA, p 23
Coburn C (2014) Play to cure: genes in space. Lancet Oncol 15(7):688
Cooper S (2011) The science behind foldit. UW Baker Lab, Seattle
Cordon O, de Viana IF, Herrera F, Moreno L (2000) A new aco model integrating evolutionary computation concepts: the best-worst ant system
Davendra D, Zelinka I (2016) Self-organizing migrating algorithm methodology and implementation. Springer, New York
Dorigo M, Gambardella LM (1997) Ant colonies for the travelling salesman problem. Biosystems 43(2):73–81
Dorigo M, Gambardella LM (1997) Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Trans Evol Comput 1(1):53–66
Dorigo M, Stützle T (2004) Ant colony optimization. Bradford Company, Scituate
Eagle N (2009) txteagle: mobile crowdsourcing. In: Internationalization, design and global development, pp 447–456
Elloumi W, El Abed H, Abraham A, Alimi AM (2014) A comparative study of the improvement of performance using a pso modified by aco applied to tsp. Appl Soft Comput 25:234–241
Foumani M, Moeini A, Haythorpe M, Smith-Miles K (2018) A cross-entropy method for optimising robotic automated storage and retrieval systems. Int J Prod Res 56(19):6450–6472
Games S (2013) State of online gaming report. Spil Games
Garey MR, Johnson DS (2002) Computers and intractability, vol 29. W.H. Freeman, New York
Graham T (2014) Players of crowdsourcing game beat supercomputers at designing rna molecules, geek.com. https://www.geek.com/news/players-of-crowdsourcing-game-beat-supercomputers-at-designing-rna-molecules-1583401/
Halim AH, Ismail I (2019) Combinatorial optimization: comparison of heuristic algorithms in travelling salesman problem. Arch Comput Methods Eng 26(2):367–380
He Q, Wang L (2007) An effective co-evolutionary particle swarm optimization for constrained engineering design problems. Eng Appl Artif Intell 20(1):89–99
Hoffman KL, Padberg M, Rinaldi G (2013) Traveling salesman problem. In: Encyclopedia of operations research and management science. Springer, pp 1573–1578
Howe J (2006) The rise of crowdsourcing. Wired Mag 14(6):1–4
Joshi CK, Laurent T, Bresson X (2019) An efficient graph convolutional network technique for the travelling salesman problem, arXiv preprint arXiv:1906.01227
Kawrykow A, Roumanis G, Kam A, Kwak D, Leung C, Wu C, Zarour E, Sarmenta L, Blanchette M, Waldispühl J et al (2012) Phylo: a citizen science approach for improving multiple sequence alignment. PLoS ONE 7(3):e31362
Lloyd S (1999) Ultimate physical limits to computation, arXiv:quant-ph/9908043 preprint
MacGregor JN, Ormerod T (1996) Human performance on the traveling salesman problem. Percept Psychophys 58(4):527–539
Mazzeo S, Loiseau I (2004) An ant colony algorithm for the capacitated vehicle routing. Electron Notes Discrete Math 18:181–186
Owens J (2013) Can the power of the public help personalise cancer treatment? Cancer research UK. Technical report. http://scienceblog.cancerresearchuk.org/2013/03/01/can-the-power-of-the-public-help-personalise-cancer-treatment/
Souvenir R, Hajja A, Spurlock S (2012) “Gamesourcing to acquire labeled human pose estimation data. In: CVPR workshops. IEEE, 2012, pp 1–6. http://dblp.uni-trier.de/db/conf/cvpr/cvprw2012.html#SouvenirHS12
Souvenir R, Hajja A, Spurlock S (2012) Gamesourcing to acquire labeled human pose estimation data. In: 2012 IEEE computer society conference on computer vision and pattern recognition workshops (CVPRW). IEEE, 2012, pp 1–6
Spurlock S, Souvenir R (2015) An evaluation of gamesourced data for human pose estimation. ACM Trans Intell Syst Technol 6(2):19
Stützle T, Hoos HH (2000) Max-min ant system. Future Gener Comput Syst 16(8):889–914
Traub MC, van Ossenbruggen J, He J, Hardman L (2014) Measuring the effectiveness of gamesourcing expert oil painting annotations. In: ECIR, ser. Lecture Notes in Computer Science, vol 8416. Springer, pp 112–123
Von Ahn L (2006) Games with a purpose. Computer 39(6):92–94
Von Ahn L, Dabbish L (2008) Designing games with a purpose. Commun ACM 51(8):58–67
Whitla P (2009) Crowdsourcing and its application in marketing activities. Contemp Manag Res 5(1):15–28
Xing L-N, Chen Y-W, Yang K-W, Hou F, Shen X-S, Cai H-P (2008) A hybrid approach combining an improved genetic algorithm and optimization strategies for the asymmetric traveling salesman problem. Eng Appl Artif Intell 21(8):1370–1380
Yan Y, suk Sohn H, Reyes G (2017) A modified ant system to achieve better balance between intensification and diversification for the traveling salesman problem. Appl Soft Comput 60:256–267
Yang X-S (2005) Engineering optimizations via nature-inspired virtual bee algorithms. In: Artificial intelligence and knowledge engineering applications: a bioinspired approach, pp 317–323
Zelinka IBM (2016) Soma swarm algorithm in computer games. In: International conference on artificial intelligence and soft computing, ser. Lecture Notes in Computer Science. Springer, pp 395–406, in print
Zelinka I (2004) Soma–self organizing migrating algorithm. In: Onwubolu G, Babu B (eds) New optimization techniques in engineering. Springer, New York, pp 167–218 ISBN 3-540-20167X
Zelinka I, Bukacek M (2016) Soma swarm algorithm in computer games. In: International conference on artificial intelligence and soft computing. Springer, pp 395–406
Zelinka I, Celikovský S, Richter H, Chen G (eds) In: Evolutionary algorithms and chaotic systems, ser. Studies in Computational Intelligence. Springer, 2010, vol 267. http://dblp.uni-trier.de/db/series/sci/sci267.html
Zelinka I, Sikora L (2015) Starcraft: Brood war strategy powered by the soma swarm algorithm. In: 2015 IEEE conference on computational intelligence and games (CIG), pp 511–516
Acknowledgements
This work was supported by the internal Grant SGS SP2020/78 of VSB-TU Ostrava.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Zelinka, I., Das, S. Gamesourcing: an unconventional tool to assist the solution of the traveling salesman problem. Nat Comput 21, 347–357 (2022). https://doi.org/10.1007/s11047-020-09817-z
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11047-020-09817-z