Problemas de Búsqueda y Planificación

Sin lugar a dudas, una de las principales características que reconocemos en la inteligencia es la capacidad para resolver problemas. Si consideramos una inteligencia como la humana, a la habilidad para analizar los elementos intrínsecos de cada problema, que está presente también en muchas otras especies animales, se añade la capacidad de abstraerlos e identificar las acciones que se pueden realizar sobre ellos para resolver el problema. En un nivel incluso superior de abstracción, reconocible solo en las llamadas especies superiores, podemos considerar también la capacidad de determinar cuál puede ser, de entre los posibles métodos que se idean, el más adecuado, ya sea en términos de tiempo, de recursos, de seguridad para el individuo, etc. De esta forma, aparece una triple capacidad de análisis, abstraccción y estrategia que sitúa el tema general de la resolución de problemas en el núcleo de la inteligencia artificial y, por ello, no resulta extraño que se consideren deseables para cualquier individuo, artificial o no, que queramos que se comporte inteligentemente.

Podemos pensar en una variedad de problemas que van desde cómo alcanzar una fuente de comida situada a cierta distancia y a la que no se puede ir directamente, hasta cómo resolver un pequeño juego como podría ser el famoso cubo de Rubik, o resolver el problema matemático de encontrar la solución a una ecuación numérica. En todos ellos encontramos elementos comunes tras un proceso de abstracción que nos permiten de forma general definir la resolución de problemas como: 

el proceso que, partiendo de una situación inicial y utilizando un conjunto de procedimientos/reglas/acciones seleccionados a priori, es capaz de explicitar el conjunto de pasos que nos llevan a una situación posterior que llamamos solución.

Lo que consideremos o no solución dependerá del contexto concreto del problema, y puede ser, por ejemplo, el conjunto de acciones que nos llevan a cumplir cierta propiedad, conseguir cierto objetivo, o verificar ciertas restricciones.

Como estamos interesados en la generación de mecanismos automáticos que se puedan llamar inteligentes, no nos contentamos con resolver problemas individuales y dar para cada problema una solución independiente, sino que intentaremos buscar elementos comunes a una gran bolsa de problemas que faciliten dar una clasificación de los mismos y reconocer métodos y estrategias que puedan ser válidos de la forma más general posible.

Para ello, y teniendo en cuenta lo la idea de modelar, es necesario que podamos expresar las características de los problemas usando un lenguaje formal común a todos ellos, para posteriormente proporcionar métodos y estrategias generales (en forma de algoritmos o de heurísticas, en nuestro caso) con los que poder obtener con ciertas garantías soluciones de esos problemas.

Una de las aproximaciones más generales y sencillas de formalizar un problema y sus posibles mecanismos de solución es por medio de lo que se denomina espacio de estados. Antes de definir formalmente en qué consiste este espacio, observemos que en todo momento estamos tratando con métodos en los que la resolución de los problemas se dan de forma dinámica, es decir, se supone que se produce una evolución temporal, que pasa por etapas, que nos permite llegar de la situación inicial en la que el problema se presenta hasta una situación final en la que se ha encontrado la solución del mismo. Es precisamente esta dinámica, en la que aplicamos las reglas u operaciones de las que disponemos, la que permite ir modificando cada situación posible para llevarnos desde el inicio a la solución. Simplemente, denominaremos estado a la representación de los elementos que describen el problema en un momento dado, es decir, a la situación en que se encuentra o se podría encontrar el problema en cada instante de tiempo.

Problema de búsqueda básico

Si nos imaginamos este espacio de estados como un terreno por el cual nos podemos mover, donde partimos de un punto concreto del terreno (estado inicial) y podemos aplicar las reglas válidas para ir saltando de un estado a otro, podemos identificar la resolución del problema (llegar hasta un estado final válido) con el problema de buscar un camino adecuado entre un estado inicial y un estado final. Es por ello que muy habitualmente se habla del Problema de Búsqueda en el Espacio de Estados. Pasemos pues a dar una definición formal de esta idea:

Un problema de búqueda básico es una 4-tupla \((X,S,G,d)\), donde 

• \(X\) es un conjunto de estados (el que hemos estado llamando Espacio de Estados).
• \(S \subseteq X\), es un conjunto no vacío de estados iniciales (no tiene porqué existir un solo estado de partida).
• \(G \subseteq X\), es un conjunto no vacío de estados finales (\(G\) se usa como inicial de Goals, objetivos en inglés, y al igual que no existe un único estado de partida, puede ocurrir que haya muchos estados finales válidos para el mismo problema).
• \(d: X \rightarrow \cal{P}(X)\) es una función de transición. Para cada \(x\in X\), \(d(x)\) determina el conjunto de estados sucesores de \(x\) (\(\cal{P}(X)\) representa las partes de \(X\), es decir, el conjunto de los posibles subconjuntos de \(X\), ya que desde un estado concreto podemos llegar a varios posibles estados aplicando distintas operaciones o reglas permitidas).

Observa que esta definición formal no explicita ni la forma en que hay que almacenar la información en los estados ni cuáles son las reglas válidas que permiten pasar de un estado a otro durante la resolución, ya que todo ello depende del problema concreto que se esté resolviendo y nosotros estamos interesados en dar un marco general que permita aplicar los métodos que desarrollemos al mayor conjunto posible de problemas. 

Una vez fijado este primer marco de representación, podemos dar los pasos generales necesarios para "buscar" el camino que lleve desde el planteamiento inicial del problema hasta una solución:

1. Dar una representación del problema, es decir, definir un espacio de estados que refleje las características del mundo real que sean necesarias para la resolución del problema. Como ya se ha indicado, ha de tenerse en cuenta que esta elección no es única, y que determinará en gran medida la facilidad o dificultad de resolver el problema que tenemos entre manos. Asimismo, este paso determina también las acciones disponibles para moverse por este espacio. La capacidad para cambiar de representación para obtener una más adecuada a la solución del problema es lo que se denomina perspicacia.
2. Especificar uno, o más, estados iniciales.
3. Especificar uno, o más estados finales (objetivos o metas). A veces no se especifican propiamente los estados finales, sino alguna propiedad que han de cumplir para que se consideren válidos.
4. Definir reglas a partir de las acciones disponibles. El conjunto de reglas definirá la función de transición del sistema formal. Estas reglas determinan la estructura del espacio de estados, y esta estructura es responsable, en gran medida de la dificultad que nos encontremos posteriormente para realizar búsquedas en el espacio.
5. El problema se resuelve usando las reglas en combinación con una estrategia de control. De nuevo, obsérvese que aquí no prefijamos ninguna estrategia de control específica. Más adelante veremos algunas de las más habituales y estudiaremos sus bondades e inconvenientes para resolver problemas de forma general. Una buena estrategia de control debe establecer el orden de aplicación de las reglas y resuelve los posibles conflictos que puedan aparecer.
6. Dependiendo de la estrategia de control utilizada, o de las necesidades de la búsqueda, puede ser necesaria una función de coste que indique cuánto cuesta aplicar una regla determinada a un estado determinado, de esa forma podemos calcular cuánto cuesta el proceso total de ir desde un estado inicial hasta un estado final aplicando dicha estrategia, y de esta forma comparar entre sí los distintos caminos que existen para resolver el problema.

Planificación

En muchos casos no estamos interesados "simplemente" en encontrar un estado final que verifique ciertas propiedades, sino en encontrar la sucesión de acciones-movimientos que nos llevan desde un estado inicial particular hasta un estado final deseado. En este caso estamos ante lo que se conoce como un Problema de Planificación, y a la sucesión concreta de acciones que resuelve el problema se le denomia plan.

Este tipo de problemas tiene muchas aplicaciones en el mundo real, que van desde la robótica hasta la generación de planes para la automatización de cadenas de montaje pasando, por supuesto, en la resolución de juegos. 

Aunque se suele relacionar con los Problemas de Scheduling, donde también se busca una sucesión de acciones ordenadas temporalmente, hay una diferencia principal, y es que en este caso el énfasis se pone en la optimización de recursos que usan las acciones que intervienen.

Tal y como sucedía con los problemas de búsqueda, aquí es importante dar una representación formal del mundo y de las acciones que podemos aplicar sobre él, y si usamos la representación del mundo como espacio de estados, entonces podemos usar los algoritmos que desarrollemos para búsquedas, pero teniendo la precaución de almacenar la sucesión de acciones ejecutadas y medir las características de los caminos construidos para decidir el proceso de búsqueda en marcha.

Aunque el problema de planificación general es completamente abierto y no añade restricciones al mundo y acciones, es habitual considerar algunas simplificaciones para poder abordarlo con ciertas garantías:

• Un espacio de estado finito.
• Estados completamente observables (es decir, no hay incertidumbre respecto a la situación del mundo).
• Acciones deterministas (en un estado concreto, la aplicación de la acción devuelve un único estado posible... no hay incertidumbre respecto al efecto de la acción).
• Tiempo implícito (las acciones tardan el mismo tiempo en ejecutarse, y no afecta a la ejecución del plan).

Esta es una posible aproximación a resolver problemas de planificación, pero en otra entrada veremos una aproximación completamente distinta, haciendo uso de Lógicas (proposicionales y de primer orden).

Ejemplos

Como primer ejemplo, consideremos el puzle de piezas deslizantes, donde el objetivo es deslizar las piezas usando el hueco hasta conseguir el orden deseado. El caso general consiste en un puzzle de \(n\times m\) cuadrículas, con \(n\times m-1\) piezas numeradas consecutivamente y 1 hueco. A veces podemos encontrar este puzle en una variante equivalente haciendo uso de imágenes que han de reconstruirse situando el orden adecuado en sus piezas.

El espacio de estados, \(X\), describe todas las posibles combinaciones de las piezas y el hueco. Como queremos dar un método general de resolución, el conjunto de los estados iniciales es, en este caso, todo el espacio \(S=X\), y el conjunto de estados finales es únicamente uno, el estado en el que todos están en orden y el hueco se sitúa al final, tal y como muestra la figura anterior. La función de transición describe el cambio que resulta de mover, en un estado concreto, el hueco en cualquiera de las 4 direcciones (en los bordes y esquinas sólo podrá moverse en 3 o 2 direcciones posibles, respectivamente).

Obsérvese que, en este caso, la solución al puzzle no es el estado final, que sabemos exáctamente cuál es, sino el camino que lleva desde un estado inicial (prefijado, o aleatorio) hasta ese estado final. Es decir, deseamos conocer la sucesión de movimientos que nos permiten resolver el puzle.

En el caso de un puzle de tamaño \(3\times 3\) (en este caso el puzle se conoce como 8-puzle, que es el número de piezas móviles) el número de posibles estados es de \(9!= 362880\), un tamaño que permite, con la capacidad de los ordenadores actuales, hacer una búsqueda exahustiva para encontrar el camino desde cualquier estado al estado final ordenado. Esta búsqueda exahustiva se consigue comenzando por el estado inicial e ir visitando a partir de él todos los demás estados por la aplicación sucesiva de las reglas de transición, de esta forma, si existe una solución (un camino que conecta el estado inicial y el final) este método la encontrará, aunque, posiblemente, de una forma completamente ineficiente.

Si jugamos con el puzle de tamaño \(4\times 4\) (que se conoce como 15-puzle) el número de posibles estados es de \(16! \approx 2x10^{13}\), demasiado grande para una búsqueda exahustiva. En casos como éste, donde el espacio de estados es excesivamente grande para hacer un recorrido exahustivo de sus elementos, hemos de encontrar estrategias de búsqueda más depuradas que nos permitan alcanzar las soluciones de forma más eficiente y usando menos recursos (en tiempo y en espacio almacenado).

Consideremos otro puzle habitual, el puzle de los misioneros y caníbales: Tres misioneros se perdieron explorando una jungla. Separados de sus compañeros, sin alimento y sin radio, sólo sabían que para llegar a su destino debían ir siempre hacia adelante. Los tres misioneros se detuvieron frente a un río que les bloqueaba el paso, preguntándose que podían hacer. De repente, aparecieron tres caníbales llevando un bote, pues también ellos querían cruzar el río. Ya anteriormente se habían encontrado grupos de misioneros y caníbales, y cada uno respetaba a los otros, pero sin confiar entre ellos. Los caníbales se comían a los misioneros cuando les superaban en número, y los misioneros bautizaban a los caníbales en situaciones similares. Todos querían cruzar el río, pero el bote no podía llevar más de dos personas a la vez y los misioneros no querían que los caníbales les aventajaran en número. ¿Cómo puede resolverse el problema, sin que en ningún momento hayan más caníbales que misioneros en cualquier orilla del río?

El espacio de estados asociado al problema podría representarse de la siguiente forma (muy descriptiva, pero poco práctica desde el punto de vista computacional):

Ejercicio: Formaliza la siguiente versión del puzle "Todos los dígitos del Rey" explicitando una representación de sus estados y la función de transición entre ellos: Dado el conjunto de dígitos \(0123456789\), inserta los símbolos de los operadores aritméticos (\(\times + - /,\)) entre ellos para que la expresión resultante se evalúe como 100. Por ejemplo:

\[0+1+2+3+4+5+6+7+(8\times 9) =100\]

¿Puedes encontrar otros?

Criterios de evaluación

Antes de que pasemos a ver la variedad de algoritmos (estrategias) que han sido diseñados para resolver problemas de búsqueda en espacios de estados, puede merecer la pena mencionar, aunque sea de forma breve, cómo podemos evaluar la eficiencia de estos algoritmos. Habitualmente, se suelen usar los siguientes criterios de evaluación: 

• Complejidad en tiempo: Se puede medir como el número de veces que se aplica la función de transición que necesita el algoritmo para encontrar la solución. En un contexto más amplio suele medirse por medio del número de pasos que da un algoritmo en su ejecución.
• Complejidad en espacio: Se mide por la cantidad de espacio de almacenamiento necesario para encontrar la solución. En el caso que estamos viendo lo podemos medir como el número de estados que el algoritmo debe mantener en memoria para encontrar la solución. Algunos algoritmos podrán "olvidar" los estados por los que van pasando, mientras que otros necesitan mantener una memoria con esos estados para poder volver atrás en la búsqueda o saber por cuáles ha pasado.
• Completitud: Si existe una solución, ¿está garantizado por el algoritmo que la encontraremos?
• Optimalidad: Si existen varias soluciones, ¿encuentra el algoritmo la óptima? Esta optimalidad se mide respecto de alguna medida, por ejemplo, la que está más cerca en número de transformaciones para llegar desde el estado inicial, o la que ha usado menos memoria.

Una representación (casi) universal

Normalmente, los algoritmos que vamos a ver se basan en la suposición de que el espacio de búsqueda tiene la estructura de un grafo dirigido: cada nodo del grafo representa uno de los estados del espacio, y dos nodos están conectados si existe una forma de ir de uno al otro por medio de la función de transición.

Normalmente, cuando resolvemos el problema a partir de un estado particular, podemos construir un árbol que se construye partiendo del estado inicial y donde en cada nivel se añaden los estados que se pueden alcanzar desde los estados del nivel anterior (y que, en consecuencia, puede contener estados repetidos). En este caso, la profundidad (\(d\), de depth) del árbol es la longitud máxima de los caminos que se pueden construir desde cualquier nodo a la raíz; y el factor de ramificación (\(b\), de branch) del árbol es el máximo número de sucesores que puede tener un nodo del árbol.

En un árbol, los sucesores inmediatos de un nodo (salvo las hojas, claro, que son los nodos terminales) se llaman hijos, el predecesor de un nodo (salvo la raíz, que no tiene predecesor), que es único, se llama padre, y los nodos que tienen el padre común se llaman hermanos.

Es importante destacar que nuestro espacio de estados NO es un árbol, sino que el árbol se consigue al considerar la estructura ordenada que surge entre los diversos estados de nuestro problema al aplicar las reglas que permiten pasar de unos estados a otros. Si cambiamos la representación de los estados (y en consecuencia las reglas que se pueden aplicar) cambiará el árbol asociado, pero nuestro problema sigue siendo el mismo. Es por ello que la representación es fundamental para obtener soluciones más o menos eficientes, ya que los posibles caminos entre los nodos que representan estados iniciales y los nodos que representan estados finales pueden cambiar completamente dependiendo del árbol que obtengamos.

Para saber más...

Tema 3 de la asignatura de IA del Grado en Ingeniería en Informática - Tecnologías Informáticas

Tema 3 Artificial Intellicenge and its teaching

Tema 3 Artificial Intellicenge. Foundations of Computational Agents