Incorporating Machine Learning in Search and Planning Problems

Abstract

Heuristic search is a universal problem-solving method and the core of automated planning, which offers key theoretical properties such as completeness and solution quality guarantees, including w-optimality.

Although machine learning (ML) has experienced significant success in areas like image classification and natural language processing, its application to search and automated planning presents considerable challenges. Current methods frequently sacrifice the theoretical benefits of traditional search algorithms, underscoring the need for approaches that merge the adaptability of ML with the dependability of search-based techniques.

This thesis explores how ML methods can be effectively integrated into heuristic search to enhance efficiency and scalability without sacrificing critical guarantees. It addresses three research questions: (1) How can learned heuristics and policies be incorporated into search algorithms while maintaining suboptimality guarantees? (2) How can GPU-based batch processing accelerate the computation of learned heuristics without compromising these guarantees? (3) How can partially specified symbolic models enhance the performance of black-box search algorithms using ML-based heuristics or policies?

Key contributions include the development of Focal Discrepancy Search (FDS), a bounded suboptimal search algorithm that integrates learned heuristics while preserving theoretical guarantees, and K-Focal Search, a GPU-accelerated method that improves search efficiency while providing w-optimal solutions. Furthermore, this work introduces a novel framework that combines partial symbolic models with ML-based approaches, enabling more scalable and efficient solutions for sequential decision-making tasks.

Alternate 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.