En este curso, analizaremos una elaborada pero muy significativa extensión del modelo clásico de planificación en IA, a saber, la planificación Totalmente Observable No Determinista (FOND, por sus siglas en inglés), y su relación con otros problemas importantes como la síntesis reactiva y las formas generalizadas de planificación.
La planificación en IA es un enfoque para el comportamiento autónomo, donde el comportamiento del agente se deriva automáticamente a partir de un modelo simbólico. En la planificación FOND, las acciones pueden ser no deterministas, es decir, pueden tener un conjunto finito de efectos posibles que son conocidos a priori, pero cuya realización real se observa después de su ejecución. Por ejemplo, un robot que agarra un vaso puede resultar en que el agarre sea exitoso o que el vaso permanezca en la mesa. Aunque es una simple extensión de la planificación clásica, el marco de trabajo FOND ha surgido como un paradigma computacional altamente versátil que puede usarse para resolver otros tipos de problemas desafiantes.
Es importante señalar que se ha demostrado una fuerte conexión entre la planificación FOND y la síntesis reactiva a partir de especificaciones lógicas, lo que vincula la IA con los métodos formales. El curso introducirá el problema de planificación FOND desde cero, así como las técnicas algorítmicas y los solvers de última generación desarrollados hasta ahora, antes de abordar su importancia en la planificación generalizada y la síntesis en Ciencias de la Computación.
Planificación clásica para la toma de decisiones secuenciales.
Acciones no deterministas en la planificación automatizada.
Conceptos de solución en la planificación FOND: soluciones débiles, fuertes, y fuertemente cíclicas.
Supuestos de equidad.
Solvers para la planificación FOND: búsqueda heurística, SAT, verificación de modelos.
Juegos de dos jugadores y síntesis de controladores - relación con la planificación FOND.
Planificación generalizada, planificación numérica cualitativa y programas de planificación de agentes.
Matematica discreta (conjuntos; grafos y árboles; lógica básica).
Algoritmos (e.g., recorrido de árboles; programación dinámica; notación O).
Mejor pero no obligatorio: conocimientos introductorios de IA, teoría de autómatas.
Geffner, H., & Bonet, B. (2013). A Concise Introduction to Models and Methods for Automated Planning. Morgan-Claypool.
Ghallab, M., Nau, D., Traverso P.: Automated planning - theory and practice. Elsevier 2004.
Daniele, M., Traverso, P., & Vardi, M. Y. (1999). Strong cyclic planning revisited. In Proceedings of the European Conference on Planning (ECP) , Vol. 1809 of LNCS, pp. 35–48. Springer.
Cimatti, A., Pistore, M., Roveri, M., & Traverso, P. (2003). Weak, strong, and strong cyclic planning via symbolic model checking. Artificial Intelligence, 147(1-2), 35–84.
Muise, C., McIlraith, S. A., & Beck, J. C. (2012). Improved non-deterministic planning by exploiting state relevance. In Proc. of the Int. Conf. on Automated Planning and Scheduling (ICAPS), 172–180
Sebastian Sardiña, Nicolás D'Ippolito: Towards Fully Observable Non-Deterministic Planning as Assumption-based Automatic Synthesis. IJCAI 2015: 3200-3206
Camacho, A., Bienvenu, M., & McIlraith, S. A. (2019). Towards a unified view of AI planning and reactive synthesis. In Proc. of the National Conference on Artificial Intelligence (AAAI), pp. 58–67.
Giuseppe De Giacomo, Alfonso Gerevini, Fabio Patrizi, Alessandro Saetti, and Sebastian Sardina (2016). Agent planning programs. Artificial Intelligence, 231:64--106.
Ivan D. Rodriguez, Blai Bonet, Sebastian Sardiña, Hector Geffner: Flexible FOND Planning with Explicit Fairness Assumptions. Journal of Artificial Intelligence Research 74 (2022)
Bonet, B., & Geffner, H. (2020). Qualitative Numeric Planning: Reductions and complexity. Journal of Artificial Intelligence Research (JAIR), 69, 923–961.
Srivastava, S., Immerman, N., & Zilberstein, S. (2011a). A new representation and associated algorithms for generalized planning. Artificial Intelligence, 175(2), 615–647.
Desarrollado por el Departamento de Computación, FCEyN, UBA