Browsing by Author "Greco Chandía, Matías José Andrés"

Now showing 1 - 2 of 2
  • Thumbnail Image
    Item
    Heuristic Function to Solve The Generalized Covering TSP with Artificial Intelligence Search
    (IEEE, 2020) Greco Chandía, Matías José Andrés; Hernández, Carlos
    Search is a universal problem-solving method in Artificial Intelligence. Specifically, Heuristic Search algorithms, such as A*, use a heuristic function to guide the search process. The heuristic function allows algorithms to explore only a part of the search space, resulting in an efficient search process. This paper presents a new heuristic function to solve the Generalized Covering Traveling Salesman Problem (GCTSP). The heuristic function is precalculated. The method to obtain the function is pre-calculating optimal solutions consecutively to small sub-problems of the GCTSP of increasing difficulty, using an incremental Best First Search algorithm, which reuses heuristics values previously precalculated. The resultating heuristic function can be used with different heuristic search algorithms. To the best of our knowledge, this problem has not been solved with Heuristic Search. This paper is the first to present a solution to the GCTSP using Heuristic Search algorithms, such as A* and Anytime search algorithms. We evaluated different Heuristic Search algorithms. The experimental evaluation shows results of the same quality, obtained orders-of-magnitude faster than the exact methods traditionally used in Operations Research.
  • Thumbnail Image
    Item
    Incorporating machine learning in search and planning problems
    (2025) Greco Chandía, Matías José Andrés; Baier Aranda, Jorge Andrés; Pontificia Universidad Católica de Chile. Escuela de Ingeniería
    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.