Segunda parte Búsqueda heurística

En palabras de Fuentetaja, en la tesis doctoral escrita el año 2010 titulada “Búsqueda heurística en planificación basada en costes”, en planificación mediante búsqueda heurística se han aplicado heurísticas de muy diversos tipos y naturaleza. A grandes rasgos las heurísticas se pueden dividir en dos categorías: Heurísticas dependientes del dominio y heurísticas independientes del dominio. Con heurísticas independientes del dominio se hace referencia a aquellas cuyo proceso de cálculo es el mismo para todos los dominios. Las heurísticas dependientes del dominio, pueden ser muy útiles para guiar la búsqueda, sin embargo, no se pueden aplicar a problemas con estructura distinta a aquellos para los que se generaron. Estas heurísticas requieren de un trabajo adicional en cada dominio para generar la información, o la función, que permite calcular la heurística. Cuando este trabajo se puede realizar de forma automática, se acercan más a las heurísticas independientes del dominio, que son aquellas que no requieren de ninguna información adicional al propio dominio o problema. Estas últimas están acordes con la idea de la planificación como un proceso general de resolución de problemas y han tenido un gran auge en los últimos años. Las heurísticas independientes del dominio más comunes en planificación mediante búsqueda heurística se pueden clasificar en función de su objetivo como: (1) Heurísticas numéricas. Aquellas que estiman numéricamente la distancia entre dos estados, un estado fuente y un estado destino. (2) Heurísticas de poda u ordenación. Aquellas que sirven para podar el espacio de estados, o para ordenar ciertos nodos. (3) Heurísticas con vistas futuras. Aquellas que permiten generar rápidamente estados profundos mediante la aplicación, total o parcial, de una política.

Fuentetaja, en la tesis doctoral citada anteriormente, continúa mencionando que los algoritmos de búsqueda progresiva que se han venido utilizando en planificación clásica se pueden dividir en dos grupos: (1) Aquellos que aplican algoritmos de búsqueda local, y (2) Aquellos que aplican algoritmos de tipo mejor primero. La búsqueda local funciona de la siguiente forma: de entre la vecindad de un único nodo actual, elige un nodo que pasa a ser el nuevo nodo actual y el proceso se repite de forma iterativa hasta que se cumpla un criterio de terminación. La búsqueda local se caracteriza porque no tiene memoria y no revisa las decisiones una vez que estas se han tomado, es decir, es un procedimiento irrevocable. El criterio de terminación normalmente se cumple cuando se ha encontrado una solución, cuando se ha realizado un determinado número de iteraciones y aparentemente el proceso de búsqueda está estancado o cuando no se puede continuar a partir el nodo actual. A continuación se mencionan algunos tipos de búsqueda local que se han aplicado en planificación, como la búsqueda de ascenso de colinas y la búsqueda forzada de ascenso de colinas, complementándose esta descripción con el algoritmo de búsqueda mejor primero.

La búsqueda de ascenso de colinas o búsqueda en escalada, es uno de los procedimientos más conocidos de búsqueda local. En este caso, el siguiente nodo de cada iteración se elige de entre los que tienen una mejor evaluación heurística de entre todos los sucesores. En caso de que el nodo elegido tenga una evaluación heurística peor que el padre, la búsqueda termina. El funcionamiento de la búsqueda en escalada depende de la topología del espacio de búsqueda. Cuando se encuentra un óptimo local, es decir, un estado para el que todos los sucesores tienen peor evaluación, la búsqueda termina sin encontrar solución alguna. La búsqueda de ascenso de colinas forzada es una variante del ascenso de colinas en la que se generan sucesores utilizando búsqueda en amplitud, hasta encontrar un sucesor, que puede ser indirecto, con una evaluación heurística mejor que el nodo actual. En este caso el nuevo nodo actual es este sucesor. La búsqueda mejor primero constituye un esquema de búsqueda global, que se caracteriza por elegir el siguiente nodo a expandir basándose en una función de evaluación. Normalmente se consideran mejores los nodos con un menor valor para la función de evaluación. La búsqueda mejor primero se suele implementar utilizando una lista ordenada en orden creciente respecto a la función de evaluación, la lista abierta, de manera que el siguiente nodo a expandir es siempre el primer elemento de la lista. Cuando un nodo se expande, se generan todos sus sucesores, y éstos se introducen en la lista abierta. El nodo expandido se introduce en una lista cerrada. El algoritmo analiza cuando el nodo que se extrae de la lista abierta es un nodo solución.