Registro:
| Documento: | Tesis de Grado |
| Título: | Aprendiendo políticas de exploración generales para escalar la síntesis de controladores discretos |
| Título alternativo: | Learning general exploration policies for scaling discrete controller synthesis |
| Autor: | Delgado, Tomás |
| Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
| Publicación en la web: | 2023-09-12 |
| Fecha de defensa: | 2023-05-02 |
| Fecha en portada: | 2023 |
| Grado Obtenido: | Grado |
| Título Obtenido: | Licenciado en Ciencias de la Computación |
| Departamento Docente: | Departamento de Computación |
| Director: | Uchitel, Sebastián |
| Director Asistente: | Braberman, Víctor Adrián |
| Jurado: | Gravano, Agustín; Riera, Pablo |
| Idioma: | Español |
| Palabras clave: | SINTESIS DE CONTROLADORES; APRENDIZAJE POR REFUERZO; REDES NEURONALES; GENERALIZACION; HEURISTICAS DE BUSQUEDACONTROLLER SYNTHESIS; REINFORCEMENT LERANING; NEURAL NETWORKS; GENERALIZATION; HEURISTIC SEARCH |
| Formato: | PDF |
| Handle: |
http://hdl.handle.net/20.500.12110/seminario_nCOM000491_Delgado |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000491_Delgado.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/seminario/document/seminario_nCOM000491_Delgado |
| Ubicación: | Dep.COM 000491 |
| Derechos de Acceso: | Esta obra puede ser leída, grabada y utilizada con fines de estudio, investigación y docencia. Es necesario el reconocimiento de autoría mediante la cita correspondiente. Delgado, Tomás. (2023). Aprendiendo políticas de exploración generales para escalar la síntesis de controladores discretos. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de http://hdl.handle.net/20.500.12110/seminario_nCOM000491_Delgado |
Resumen:
El área de síntesis de controladores discretos estudia la construcción automática de estrategias de comportamiento con garantías de correctitud, para sistemas descriptos formalmente por autómatas. La limitación de estas técnicas viene dada por la maldición de la dimensionalidad, que hace que el tamaño de los autómatas crezca muy velozmente y restringe la aplicabilidad. La síntesis on-the-fly busca eludir esta problemática construyendo el espacio de estados parcialmente, agregando una transición a la vez desde el estado inicial e intentando explorar solo lo necesario para la estrategia ganadora, o para mostrar que tal estrategia no existe. En esta tesis desarrollamos un primer método para aprender una heurística que guíe la exploración a partir de la experiencia. En primer lugar, definimos una tarea de aprendizaje por refuerzo para la cual el agente representa una política de exploración. Luego, mostramos una forma de usar Q-Learning abstrayendo tanto estados como acciones en un conjunto de features. Esta abstracción hace posible el aprendizaje y la generalización, pero genera un alto grado de observabilidad parcial. La evaluación empírica muestra que, a pesar de la falta de garantías teóricas, es posible aprender consistentemente políticas competitivas en las instancias de entrenamiento. Más aún, las políticas inducidas en instancias grandes superan en promedio a la mejor heurística desarrollada por humanos, empujando la frontera de problemas resueltos en algunos de los dominios del benchmark.
Abstract:
Controller Synthesis studies the automated construction of behavior strategies with guaranteed correctness for systems that can be formally described as automatons. The applicability of these techniques is usually limited by the curse of dimensionality, which makes automatons rapidly become intractably large as problems become more interesting. An on-the-fly synthesis algorithm can avoid the state explosion by building the automaton partially, starting from the initial state and adding one transition at a time, attempting to only explore the subgraph needed for the winning strategy or to show that such strategy does not exist. In this thesis, we develop a first method for learning a heuristic that guides the exploration from experience. First, we define a Reinforcement Learning task where the agent represents an exploration policy. Then, Q-Learning is used while abstracting both states and actions with a set of features. This abstraction makes learning and generalization possible, but causes a form of partial observability that we call Very Partially Observable MDP. Empirical evaluation shows that, despite the lack of theoretical guarantees, it is possible to learn competitive policies consistently in the training instances. Furthermore, the policies induced in the larger versions of the problems outperform the best human- designed heuristic overall, pushing the frontier of solvable problems for a subset of the benchmark problems.
Citación:
---------- APA ----------
Delgado, Tomás. (2023). Aprendiendo políticas de exploración generales para escalar la síntesis de controladores discretos. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nCOM000491_Delgado
---------- CHICAGO ----------
Delgado, Tomás. "Aprendiendo políticas de exploración generales para escalar la síntesis de controladores discretos". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2023.https://hdl.handle.net/20.500.12110/seminario_nCOM000491_Delgado
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000491_Delgado.pdf
Distrubución geográfica
