Genetic Algorithm for Planning and Scheduling Problem -- StarCraft II Build Order case study

• Autorzy: Gmyrek Konrad , Antkiewicz Michał , Myszkowski Paweł

Identyfikatory

DOI

10.15439/2023F6015

• Języki publikacji: EN

Abstrakty

EN

The Planning and Scheduling (PS) problem plays a vital role in several domains, such as economics, military, management, finance, and games, where finding the optimal plan and schedule to achieve specific goals is essential. In this article, we present a Genetic Algorithm for the Planning and Scheduling (GAPS) problem in the StarCraft II Build Order Optimization problem (SC2 BO) context -- as it signifies that modern strategy games present a more challenging environment than classical planning problems. We evaluate the performance of GAPS and compare it with state-of-the-art methods. Experimental results provide valuable insight into the effectiveness of GA in the context of the PS Problem under various configurations, notably in the context of Lamarckianism and the Baldwin Effect. Ultimately, this research enhances the understanding of GA application for the PS problem, offering notable insights regarding GA performance and potential for future work.

Słowa kluczowe

EN

schedule; sociology; finance; game; planning

PL

harmonogram; socjologia; finanse; gra; planowanie

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2023
• Tom: Vol. 35
• Strony: 131--140
• Opis fizyczny: Bibliogr. 14 poz., wykt., tab., rys.

Twórcy

autor

Gmyrek Konrad

• Wrocław University of Science and Technology Faculty of Information and Communication Technology ul. I. Łukasiewicza 5, 50-371 Wrocław, Poland

autor

Antkiewicz Michał

• Wrocław University of Science and Technology Faculty of Information and Communication Technology ul. I. Łukasiewicza 5, 50-371 Wrocław, Poland

autor

Myszkowski Paweł

• Wrocław University of Science and Technology Faculty of Information and Communication Technology ul. I. Łukasiewicza 5, 50-371 Wrocław, Poland

Bibliografia

• 1. Kovarsky, A., and Buro, M. (2006) "A first look at build-order optimization in real-time strategy games." Proceedings of the GameOn Conference. 2006.
• 2. Justesen, Niels and Risi, Sebastian. (2017). Continual online evolutionary planning for in-game build order adaptation in StarCraft. 187-194. 10.1145/3071178.3071210.
• 3. Wei, LZ and LW Sun. (2009) “Build Order Optimisation For Realtime Strategy Game”, http://www.nus.edu.sg/nurop/2009/SoC/nuropLimZhanWei.pdf
• 4. Blackford, J., and Lamont, G. (2014) "The real-time strategy game multi-objective build order problem." Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment. Vol. 10. No. 1. 2014.
• 5. Churchill, D., and Buro M. (2011) "Build order optimization in starcraft." Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment. Vol. 7. No. 1.
• 6. Weber, Bryan S. (2018) "Standard economic models in nonstandard settings–starcraft: Brood war." 2018 IEEE Conference on Computational Intelligence and Games (CIG). IEEE,.
• 7. Buro, M., and Kovarsky, A. (2007) "Concurrent action execution with shared fluents.", AAAI Conf. 2007: 950-955.
• 8. Fox, M., and Derek Long. "PDDL2. 1: An extension to PDDL for expressing temporal planning domains." Journal of artificial intelligence research 20 (2003): 61-124.
• 9. Vinyals, O., Babuschkin, I., Czarnecki, W.M. et al. Grandmaster level in StarCraft II using multi-agent reinforcement learning. Nature 575, 350–354 (2019). https://doi.org/10.1038/s41586-019-1724-z
• 10. Liu, Ruo-Ze and Pang, Zhen-Jia and Meng, Zhou-Yu and Wang, Wenhai and Yu, Yang and Lu, Tong. (2022) "On Efficient Reinforcement Learning for Full-length Game of StarCraft II", Journal of Artificial Intelligence Research 75, 2022, pp.213-260.
• 11. El-Nabarawy, Islam and Arroyo, K. and Wunsch, D. (2020). "StarCraft II Build Order Optimization using Deep Reinforcement Learning and Monte-Carlo Tree Search", https://arxiv.org/pdf/2006.10525.pdf.
• 12. M. Kuchem, M. Preuss and G. R. (2013) "Multi-objective assessment of pre-optimized build orders exemplified for StarCraft 2" 2013 IEEE Conference on Computational Intelligence in Games (CIG), 2013, pp. 1-8, http://dx.doi.org/10.1109/CIG.2013.6633626.
• 13. C.W. Leung, T.N. Wong, K.L. Mak, R.Y.K. Fung, (2010) Integrated process planning and scheduling by an agent-based ant colony optimization, Computers and Industrial Engineering, Vol. 59 (1), pp.166-180.
• 14. Cobb, Charles W., and Paul H. Douglas. "A theory of production." (1928).

Uwagi

1. Main Track Regular Papers

2. Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2024).