David González Asenjo¹, Luis R. Izquierdo² and Javier Sedano¹

¹ Instituto Tecnológico de Castilla y León, Burgos, Spain.

² Escuela Politécnica Superior, Universidad de Burgos, Burgos, Spain.

davidgonzalezsg3@gmail.com

Keywords: Teoría de juegos evolutiva; Simulación basada en agentes; Control distribuido; Dinámicas evolutivas.

En este trabajo describimos una propuesta de investigación para desarrollar un doctorado sobre la aplicación de teoría de juegos evolutiva a problemas de control distribuido.

Hoy en día existen muchos sistemas ingenieriles que son difíciles de controlar debido al gran número de componentes que los constituyen, las interdependencias no lineales que existen entre ellos, y su autonomía distribuida [1]. El control de estos sistemas distribuidos a gran escala requiere del diseño de reglas de decisión individuales que garanticen la consecución de un objetivo común en un entorno dinámico y de gran incertidumbre. En este contexto, la teoría de control tradicional no suele ser especialmente útil [2].

Recientemente se ha demostrado la utilidad de la teoría de juegos evolutiva para la resolución de problemas de control distribuido en contextos ingenieriles, sobre todo en aquellos donde debido a dicha descentralización se dan restricciones de acceso a la información y donde los controles centralizados son menos eficientes o imposibles de acometer. La analogía entre sistemas distribuidos en el contexto de ingeniería y las interacciones sociales analizadas en teoría de juegos evolutiva es clara y ha sido establecida formalmente en numerosos contextos ingenieriles [1-3].

La aplicación de teoría de juegos a problemas de control distribuido consiste básicamente en encontrar un juego y un protocolo de revisión tales que la dinámica inducida conduzca a la consecución del objetivo global perseguido a nivel de sistema. No obstante, la aplicación no es inmediata: el enfoque seguido en teoría de juegos para estudiar sistemas sociales requiere de algunas modificaciones fundamentales para poder ser aplicado de forma ventajosa en contextos ingenieriles.

Este enfoque ha dado lugar a resultados prometedores en los últimos años, siendo uno de los éxitos más notables el desarrollo de algoritmos que permiten formalizar numerosos problemas que aparecen con frecuencia en ingeniería como juegos de tipo potencial [4-6]. En esta línea de investigación se han conseguido varios resultados prometedores, pero también se han identificado ciertas limitaciones.

En nuestra propuesta de investigación proponemos abordar esas limitaciones desde una doble propuesta, combinando el análisis teórico matemático y la simulación basada en agentes, aprovechando las fortalezas de cada técnica y las sinergias que surgen entre ambas.

Este punto de vista resulta especialmente de utilidad en aquellos sistemas que manejan un alto grado de incertidumbre en cuanto a las interacciones entre sus componentes y donde el enfoque teórico no siempre es aconsejable debido al elevado número de suposiciones a realizar y a la complejidad de cálculo que ello conlleva. En estas situaciones la simulación basada en agentes muestra sus bondades, ya que permite establecer relaciones directas entre los agentes en nuestro modelo y las entidades del sistema que pretendemos modelar.

Bajo esta perspectiva, el objetivo general que se persigue con esta propuesta es diseñar un conjunto de algoritmos simples, completamente descentralizados, y con requisitos mínimos de información, que puedan conducir en tiempos razonables a resultados eficientes en problemas de control distribuido en los que no se conoce con precisión la relación entre las acciones de sus componentes y la función objetivo a optimizar.

Asimismo, el diseño de dichos algoritmos se plantea desde criterios de sencillez, descentralización, manejo de información limitada y eficiencia.

Como hemos mencionado, para conseguir los objetivos de esta propuesta resulta imprescindible hacer un uso complementario y sinérgico de: a) análisis teórico-matemático y b) simulación basada en agentes. A continuación se explican las razones de esta necesidad.

Tradicionalmente, el método más habitual seguido por la comunidad científica en teoría de juegos es el enfoque teórico-matemático, el cual ha proporcionado grandes avances en nuestro conocimiento del funcionamiento de sistemas socio-económicos evolutivos, pero normalmente se apoya en una serie de hipótesis simplificadoras que a menudo no son plenamente satisfactorias para modelar sistemas reales concretos. Este problema es especialmente relevante en el contexto de problemas de control distribuido en entornos dinámicos e inciertos.

Afortunadamente, actualmente es posible complementar el análisis teórico tradicional con otros enfoques de carácter más computacional, sin pérdida de rigor científico. Una de las técnicas de mayor utilidad es la simulación basada en agentes, que consiste en la programación y análisis de modelos que implementan de forma explícita los comportamientos de los individuos y sus reglas de interacción. Esta técnica permite explorar la relación existente entre los comportamientos individuales de los agentes (y sus interacciones) y los resultados obtenidos a nivel agregado. Las características del modelado basado en agentes permiten construir modelos que tienen el potencial de ser más descriptivos y con menos hipótesis simplificadoras que los modelos teóricos tradicionales, pero esta misma característica implica que un análisis riguroso de su comportamiento es normalmente mucho más complejo y a veces incluso inviable [7].

Por ello, y basándonos en nuestra experiencia en el análisis de estos sistemas, consideramos imprescindible hacer uso de los dos enfoques (teórico-matemático y simulación computacional), ya que existen multitud de sinergias y complementariedades entre los dos [8].

En esta propuesta, dentro del enfoque teórico matemático, esperamos hacer uso de diversas disciplinas entre las que cabe destacar la Teoría de Juegos Evolutiva [9,10], la Teoría de Cadenas de Markov [11] y la Teoría de Aproximación Estocástica [12-14].

Para el enfoque de simulación computacional, utilizaremos Netlogo [15], aprovechando su sencillez, potencia, documentación, filosofía de código abierto y su activa comunidad de usuarios [16]. Nuestros desarrollos de programación seguirán la filosofía SCRUM, una metodología ágil de ingeniería de programación que facilita la creación iterativa e incremental de proyectos de software. Además, se llevará un estricto control de versiones para el software producido usando GitHub y todo el software desarrollado en esta propuesta se pondrá a disposición del público bajo la licencia de código libre GNU General Public Licence (GPL) para la difusión de software científico, comentando y documentando el código cuidadosamente, incluyendo guías de usuario. Estas actividades presentan una doble ventaja: por un lado, facilitan y fomentan que otras personas utilicen nuestro código; por otro lado, aseguran que los resultados del proyecto pueden ser inspeccionados y reproducidos, y los modelos pueden ser reimplementados por otros investigadores si así lo desean [17].

Agradecimientos Los autores agradecen la financiación de la Agencia Española de Investigación (PID2020-118906GB-I00/AEI/10.13039/501100011033) y de la Junta de Castilla y León – Consejería de Educación (BDNS 425389).

Referencias

1. Quijano, N., Ocampo-Martinez, C., Barreiro-Gomez, J., Obando, G., Pantoja, A., Mojica-Nava, E.: The Role of Population Games and Evolutionary Dynamics in Distributed Control Systems: The Advantages of Evolutionary Game Theory. IEEE Control Syst. 37, 70–97 (2017). https://doi.org/10.1109/MCS.2016.2621479.
2. Marden, J.R., Shamma, J.S.: Game Theory and Distributed Control. In: Young, H.P. and Zamir, S. (eds.) Handbook of Game Theory with Economic Applications. pp. 861–899. Elsevier, Amsterdam (2015). https://doi.org/10.1016/B978-0-444-53766-9.00016-1.
3. Marden, J.R., Shamma, J.S.: Game-Theoretic Learning in Distributed Control. In: Handbook of Dynamic Game Theory. pp. 1–36. Springer International Publishing, Cham (2017). https://doi.org/10.1007/978-3-319-27335-8_9-1.
4. Marden, J.R., Wierman, A.: Distributed Welfare Games. Oper. Res. 61, 155–168 (2013). https://doi.org/10.1287/opre.1120.1137.
5. Wang, Y., Cheng, D., Liu, X.: Matrix expression of Shapley values and its application to distributed resource allocation. Sci. China Inf. Sci. 62, 22201 (2019). https://doi.org/10.1007/s11432-018-9414-5.
6. Li, N., Marden, J.R.: Designing Games for Distributed Optimization. IEEE J. Sel. Top. Signal Process. 7, 230–242 (2013). https://doi.org/10.1109/JSTSP.2013.2246511.
7. Izquierdo, L.R., Galán, J.M., Santos, J.I., Del Olmo, R.: Modelado de sistemas complejos mediante simulación basada en agentes y mediante dinámica de sistemas. Empiria. Revista de metodología de ciencias sociales. 16,  85-112 (2008). https://doi.org/10.5944/empiria.16.2008.1391.
8. Izquierdo, L.R., Izquierdo, S.S., Galán, J.M., Santos, J.I.: Combining Mathematical and Simulation Approaches to Understand the Dynamics of Computer Models. In: Edmonds B., Meyer R. (eds) Simulating Social Complexity. Understanding Complex Systems. Springer, Cham. 293-330 (2017). https://doi.org/10.1007/978-3-319-66948-9_13.
9. Weibull, J.W.: Evolutionary Game Theory. The MIT Press (1995).
10. Sandholm, W.H.: Population Games and Evolutionary Dynamics. MIT Press, Cambridge. (2010).
11. Kulkarni, V.G.: Modeling and Analysis of Stochastic Systems. Chapman & Hall, Ltd., London, UK, UK (1995).
12. Benaim, M., Weibull, J.W.: Deterministic Approximation of Stochastic Evolution in Games. Econometrica. 71, 873–903 (2003). https://doi.org/10.1111/1468-0262.00429.
13. Borkar, V.S.: Stochastic Approximation. Hindustan Book Agency, Gurgaon (2008). https://doi.org/10.1007/978-93-86279-38-5.
14. Roth, G., Sandholm, W.H.: Stochastic Approximations with Constant Step Size and Differential Inclusions. SIAM J. Control Optim. 51, 525–555 (2013). https://doi.org/10.1137/110844192.
15. Wilensky, U..: Netlogo. Software. Center for Connected Learning and Computer-Based Modeling, Northwestern University, Evanston, IL, (1999). http://ccl.northwestern.edu/netlogo/.
16. Izquierdo, L.R., Izquierdo, S.S., Sandholm, W.H.: Agent-Based Evolutionary Game Dynamics. Chapter 0.3: “Introduction to NetLogo”.  https://wisc.pb.unizin.org/agent-based-evolutionary-game-dynamics/.
17. Polhill, J.G., Edmonds, B.: Open Access for Social Simulation. Journal of Artificial Societies and Social Simulation. Volume 10. Issue 3, (2007). http://jasss.soc.surrey.ac.uk/10/3/10.html.