Abstract
Robot soccer is one of the major domains for studying the coordination of multi-robot teams. Decentralized Partially Observable Markov Decision Process (Dec-POMDP) is a recent mathematical framework which has been used to model multi-agent coordination. In this work, we model simple robot soccer as Dec-POMDP and solve it using an algorithm which is based on the approach detailed in [1]. This algorithm uses finite state controllers to represent policies and searches the policy space with genetic algorithms. We use the TeamBots simulation environment. We use score difference of a game as a fitness and try to estimate it by running many simulations. We show that it is possible to model a robot soccer game as a Dec-POMDP and achieve satisfactory results. The trained policy wins almost all of the games against the standard TeamBots teams, and a reinforcement learning based team developed elsewhere.
Chapter PDF
Similar content being viewed by others
References
Eker, B.: Evolutionary Algorithms for Solving DEC-POMDP Problems. PhD thesis, Boğaziçi University (2012)
Bernstein, D.S., Hansen, E.A., Zilberstein, S.: Bounded Policy Iteration for Decentralized POMDPs. In: Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, Edinburgh, Scotland, pp. 1287–1292 (2005)
Balch, T.: Teambots mobile robot simulator (2000)
Meriçli, Ç., Meriçli, T., Levent Akın, H.: A Reward Function Generation Method Using Genetic Algorithms: A Robot Soccer Case Study. In: Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2010, Richland, SC, vol. 1, pp. 1513–1514 (2010); International Foundation for Autonomous Agents and Multiagent Systems
Bernstein, D.S., Givan, R., Immerman, N., Zilberstein, S.: The Complexity of Decentralized Control of Markov Decision Processes. Math. Oper. Res. 27, 819–840 (2002)
Wu, F., Chen, X.: Solving Large-Scale and Sparse-Reward DEC-POMDPs with Correlation-MDPs. In: Visser, U., Ribeiro, F., Ohashi, T., Dellaert, F. (eds.) RoboCup 2007. LNCS (LNAI), vol. 5001, pp. 208–219. Springer, Heidelberg (2008)
Stone, P., Sutton, R.S.: Scaling Reinforcement Learning toward RoboCup Soccer. In: Proc. 18th International Conf. on Machine Learning, pp. 537–544. Morgan Kaufmann, San Francisco (2001)
Stone, P., Sutton, R.S., Singh, S.: Reinforcement Learning for 3 vs. 2 Keepaway. In: Stone, P., Balch, T., Kraetzschmar, G.K. (eds.) RoboCup 2000. LNCS (LNAI), vol. 2019, pp. 249–258. Springer, Heidelberg (2001)
Stone, P., Sutton, R.S., Singh, S.: Reinforcement Learning for 3 vs. 2 Keepaway. In: Stone, P., Balch, T., Kraetzschmar, G.K. (eds.) RoboCup 2000. LNCS (LNAI), vol. 2019, pp. 249–258. Springer, Heidelberg (2001)
Whiteson, S., Kohl, N., Miikkulainen, R., Stone, P.: Evolving Soccer Keepaway Players Through Task Decomposition. Machine Learning 59, 5–30 (2005), 10.1007/s10994-005-0460-9
Stone, P., Kuhlmann, G., Taylor, M.E., Liu, Y.: Keepaway Soccer: From Machine Learning Testbed to Benchmark. In: Bredenfeld, A., Jacoff, A., Noda, I., Takahashi, Y. (eds.) RoboCup 2005. LNCS (LNAI), vol. 4020, pp. 93–105. Springer, Heidelberg (2006)
Pietro, A.D., While, L., Barone, L.: Learning In RoboCup Keepaway Using Evolutionary Algorithms. In: GECCO 2002, pp. 1065–1072 (2002)
Amato, C., Bernstein, D.S., Zilberstein, S.: Optimal Fixed-Size Controllers for Decentralized POMDPs. In: Proceedings of the AAMAS Workshop on Multi-Agent Sequential Decision Making in Uncertain Domains, Hakodate, Japan, pp. 61–71 (2006)
Levent Akın, H.: Evolutionary Computation: A Natural Answer to Artificial Questions. In: Proceedings of ANNAL: Hints from Life to Artificial Intelligence, pp. 41–52. METU, Ankara (1994)
Eker, B., Levent Akın, H.: Using evolution strategies to solve DEC-POMDP problems. Soft Computing-A Fusion of Foundations, Methodologies and Applications 14(1), 35–47 (2010)
Meffert, K., Meseguer, J., Marti, E.D., Meskauskas, A., Vos, J., Rotstan, N.: Jgap: Java genetic algorithms package (2011)
Meriçli, Ç., Levent Akın, H.: A Layered Metric Definition and Evaluation Framework for Multirobot Systems. In: Iocchi, L., Matsubara, H., Weitzenfeld, A., Zhou, C. (eds.) RoboCup 2008. LNCS, vol. 5399, pp. 568–579. Springer, Heidelberg (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Aşık, O., Akın, H.L. (2013). Solving Multi-agent Decision Problems Modeled as Dec-POMDP: A Robot Soccer Case Study. In: Chen, X., Stone, P., Sucar, L.E., van der Zant, T. (eds) RoboCup 2012: Robot Soccer World Cup XVI. RoboCup 2012. Lecture Notes in Computer Science(), vol 7500. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-39250-4_13
Download citation
DOI: https://doi.org/10.1007/978-3-642-39250-4_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-39249-8
Online ISBN: 978-3-642-39250-4
eBook Packages: Computer ScienceComputer Science (R0)