Incorporating machine learning in search and planning problems
Loading...
Date
2025
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
La busqueda heurística es un método universal de resolución de problemas y es el núcleo de la planificación automática. La búsqueda ofrece propiedades teóricas como la completitud y las garantías sobre la calidad de la solución, como la w-optimalidad. Si bien el aprendizaje automático (ML) ha logrado un éxito notable en dominios como la clasificación de imágenes y el procesamiento del lenguaje natural, su aplicación a la búsqueda y la planificación automática presenta desafíos significativos. Los enfoques existentes comúnmente comprometen las propiedades teóricas de los algoritmos de búsqueda tradicionales, lo que destaca la necesidad de nuevos métodos que combinen la adaptabilidad del ML con la confiabilidad de las técnicas basadas en búsqueda. Esta tesis explora cómo los modelos y métodos de ML se pueden integrar de manera efectiva en los problemas de búsqueda para mejorar la eficiencia y la escalabilidad sin sacrificar sus propiedades teóricas. Esta tesis aborda tres preguntas de investigación: (1) ¿Cómo se pueden incorporar las heurísticas y políticas aprendidas en los algoritmos de búsqueda manteniendo las garantías de suboptimalidad? (2) ¿Cómo puede el procesamiento por lotes basado en GPU acelerar el cálculo de las heurísticas aprendidas sin comprometer estas garantías? (3) ¿Cómo pueden los modelos simbólicos parcialmente especificados mejorar el rendimiento de los algoritmos de búsqueda utilizando heurísticas o políıticas basadas en ML? Entre las contribuciones se incluyen el desarrollo de Focal Discrepancy Search (FDS), un algoritmo de búsqueda acotado por suboptimalidad que integra heurísticas aprendidas al tiempo que conserva las garantías teóricas y K-Focal Search, un método acelerado por GPU que mejora la eficiencia de la búsqueda y proporciona soluciones w-optimas. Además, este trabajo presenta un nuevo marco que combina modelos simbólicos parciales con enfoques basados en ML, lo que permite soluciones más escalables y eficientes para tareas de toma de decisiones secuenciales.
Description
Tesis (Doctor in Engineering Sciences)--Pontificia Universidad Católica de Chile, 2025
Keywords
Búsqueda heurística, Planificación automática, Aprendizaje automático