Ontología para planificación lineal

Abstract

Como consecuencia de la ineficiencia potencial de la planificación lineal manifestada en el excesivo retroceso durante la búsqueda en algunos de los primeros sistemas planificadores lineales, este tipo de planificación había quedado relegado a un segundo plano como herramienta de propósito general. Recientemente, sin embargo, se ha reabierto el debate al incluirse un nuevo elemento de juicio: la mayor capacidad de expresión en la codificación de los dominios, lo que facilita la implementación de conocimiento específico para guiar la búsqueda, al desarrollarse ésta en un espacio de estados. En esta tesis se ha continuado esta línea de investigación, aportando un marco formalizador para la representación de conocimiento específico en dominios de planificación clásica. Se propone una metodología innovadora de propósito general que se ha denominado ESPLAN (EStrategias para PLANificación), para capturar el conocimiento específico en los términos del experto en el dominio. A tal fin, el planificador ESPLAN debe poder representar intuiciones, posiblemente incompletas, aprovechar nuevas oportunidades que se presenten y recuperarse de errores en su propia base de conocimiento, durante la planificación. Esta metodología aportada ESPLAN se fundamenta en una nueva ontología que utiliza la noción estrategia para construir jerarquías, de forma similar a lo que ocurre en la planificación HTN. A diferencia de las tareas HTN, se ha previsto para las estrategias que puedan ser incompletas y que puedan transmitir información durante los retrocesos. Las estrategias conforman la base de conocimiento del planificador ESPLAN que se encuentra en un plano superior a las acciones concretas, lo que permite diseñar la Teoría de Estrategias para el dominio, de forma totalmente independiente de la posterior representación de las acciones. La ontología se complementa con un nuevo algoritmo de planificación que introduce una búsqueda de oportunidades y de contingencia innovadora, que se solapa con la búsqueda convencional. Se definen además los elementos necesarios para controlar la complejidad añadida, así como condiciones operativas para su uso. En esta tesis el modelado ESPLAN se ha aplicado al ajedrez, dominio éste en el que normalmente no se ha utilizado la perspectiva de la planificación. En este dominio complejo se ha definido aquí una Teoría de Estrategias lo suficientemente representativa para realizar búsquedas totalmente guiadas por estrategias en algunas posiciones prototipo, en el que el conocimiento existente permite dirigir la búsqueda completamente. Se han construido varios demostradores. Uno de ellos, además de validar la metodología propuesta en el dominio del ajedrez, tiene la suficiente entidad como para ser un verdadero banco de pruebas que permita, en un futuro próximo, incorporar cada vez más conocimiento heurístico a este dominio, en términos similares a los que emplean los Grandes Maestros.