Unidad 2. Técnicas de Búsqueda

2.1. Solución de problemas con búsqueda.

La solución de problemas es fundamental para la mayoría de las aplicaciones de IA; existen principalmente dos clases de problemas que se pueden resolver mediante procesos computables: aquéllos en los que se utiliza un algoritmo determinista que garantiza la solución al problema y las tareas complejas que se resuelven con la búsqueda de una solución; de ésta última clase de problemas se ocupa la IA.

La solución de problemas requiere dos consideraciones:

• Representación del problema en un espacio organizado.
• La capacidad de probar la existencia del estado objetivo en dicho espacio.

Las anteriores premisas se traducen en: la determinación del estado objetivo y la determinación del camino óptimo guiado por este objetivo a través de una o más transiciones dado un estado inicial

El espacio de búsqueda, se le conoce como una colección de estados.
En general los espacios de búsqueda en los problemas de IA no son completamente conocidos de forma a priori. De lo anterior ‘resolver un problema de IA’ cuenta con dos fases:

• La generación del espacio de estados
• La búsqueda del estado deseado en ese espacio.

Debido a que ‘todo el espacio de búsqueda’ de un problema es muy grande, puede causar un bloqueo de memoria, dejando muy poco espacio para el proceso de búsqueda. Para solucionar esto, se expande el espacio paso a paso, hasta encontrar el estado objetivo.

2.2. Espacios de estados.

Muchos de los problemas que pueden ser resueltos aplicando técnicas de inteligencia artificial se modelan en forma simbólica y discreta definiendo las configuraciones posibles del universo estudiado. El problema se plantea entonces en términos de encontrar una configuración objetivo a partir de una configuración inicial dada, aplicando transformaciones válidas según el modelo del universo. La respuesta es la secuencia de transformaciones cuya aplicación succesiva lleva a la configuración deseada.

Los ejemplos más carácteristicos de esta categoría de problemas son los juegos (son universos restringidos fáciles de modelar). En un juego, las configuraciones del universo corresponden directamente a las configuraciones del tablero. Cada configuración es un estado que puede ser esquematizado gráficamente y representado en forma simbólica. Las transformaciones permitidas corresponden a las reglas o movidas del juego, formalizadas como transiciones de estado.

Entonces, para plantear formalmente un problema, se requiere precisar una representación simbólica de los estados y definir reglas del tipo condición   acción para cada una de las transiciones válidas dentro del universo modelado. La acción de una regla indica como modificar el estado actual para generar un nuevo estado. La condición impone restricciones sobre la aplicabilidad de la regla según el estado actual, el estado generado o la historia completa del proceso de solución.

El espacio de estados de un juego es un grafo cuyos nodos representan las configuraciones alcanzables (los estados válidos) y cuyos arcos explicitan las movidas posibles (las transiciones de estado). En principio, se puede construir cualquier espacio de estados partiendo del estado inicial, aplicando cada una de las reglas para generar los sucesores immediatos, y así succesivamente con cada uno de los nuevos estados generados (en la práctica, los espacios de estados suelen ser demasiado grandes para explicitarlos por completo).

Cuando un problema se puede representar mediante un espacio de estados, la solución computacional correspende a encontrar un camino desde el estado inicial a un estado objetivo.

2.2.1. Determinísticos.

El espacio de estados determinísticos contienen un único estado inicial y seguir la secuencia de estados para la solución. Los espacios de estados determinísticos son usados por los sistemas expertos.

Se puede describir asu vez, que un sistema es determinístico si, para un estado dado, al menos aplica una regla a él y de solo una manera.


2.2.2. No determinísticos.

El no determinístico contiene un amplio número de estados iniciales y sigue la secuencia de estados perteneciente al estado inicial del espacio. Son usados por sistemas de lógica difusa.
En otras palabras,  si más de una regla aplica a cualquier estado particular del sistema, o si una regla aplica a un estado particular del sistema en más de una manera, entonces el sistema es no determinístico.

2.3. Métodos de búsqueda.

2.3.1. Primero en anchura (breadthfirst).

En inglés, breadth-first search.

Si el conjunto open se maneja como una lista FIFO, es decir, como una cola, siempre se estará visitando primero los primeros estados en ser generados. El recorrido del espacio de estados se hace por niveles de profundidad.

procedure Búsqueda_en_amplitud {
   open ()[estado_inicial]
   closed () {}
   while (open no está vacía) {
     remover el primer estado X de la lista open
     if (X es un estado objetivo) return éxito
     else {
       generar el conjunto de sucesores del estado X
       agregar el estado X al conjunto closed
       eliminar sucesores que ya están en open o en closed
       agregar el resto de los sucesores al final de open
     }
   }
   return fracaso
 }

Si el factor de ramificación es B y la profundidad a la cual se encuentra el estado objetivo más cercano es n, este algoritmo tiene una complejidad en tiempo y espacio de O(Bⁿ). Contrariamente a la búsqueda en profundidad, la búsqueda en amplitud garantiza encontrar el camino más corto.

2.3.2. Primero en profundidad (depthfirst).

En inglés, depth-first search.

Si el conjunto open se maneja como una lista LIFO, es decir, como un stack, siempre se estará visitando primero los últimos estados en ser generados. Esto significa que si A genera B y C, y B genera D, antes de visitar C se visita D, que está más alejado de la raiz A, o sea más profundo en el árbol de búsqueda. El algoritmo tiene en este caso la tendencia de profundizar la búsqueda en una rama antes de explorar ramas alternativas.

procedure Búsqueda_en_profundidad {
   open () [estado_inicial]
   closed () {}
   while (open no está vacía) {
     remover el primer estado X de la lista open
     if (X es un estado objetivo) return éxito
     else {
       generar el conjunto de sucesores del estado X
       agregar el estado X al conjunto closed
       eliminar sucesores que ya están en open o en closed
       agregar el resto de los sucesores al principio de open
     }
   }
   return fracaso
 }

Considerando que la cantidad promedio de sucesores de los nodos visitados es B (llamado en inglés el branching factor y en castellano el factor de ramificación), y suponiendo que la profundidad máxima alcanzada es n, este algoritmo tiene una complejidad en tiempo de O(Bⁿ) y, si no se considera el conjunto closed, una complejidad en espacio de O(B × n). En vez de usar el conjunto closed, el control de ciclos se puede hacer descartando aquellos estados que aparecen en el camino generado hasta el momento (basta que cada estado generado tenga un puntero a su padre).

El mayor problema de este algoritmo es que puede "perderse" en una rama sin encontrar la solución. Además, si se encuentra una solución no se puede garantizar que sea el camino más corto.

2.3.3. Grafos O.

2.3.4. Grafos A.

2.4. Satisfacción de restricciones.
Los problemas pueden resolverse buscando en un espacio de estados, estos estados pueden evaluarse por heurísticas específicas para el dominio y probados para verificar si son estados meta.

Los componentes del estado, son equivalentes a un grafo de restricciones, los cuales están compuestos de:

• Variables. Dominios (valores posibles para las variables).
• Restricciones (binarias) entre las variables.

Objetivo: encontrar un estado (una asignación completa de valores a las variables) Que satisface las restricciones.

En los Problemas de Satisfacción de Restricciones (PSR), los estados y la prueba de meta siguen a una representación estándar, estructurada y muy simple.

Ejemplos:

• Crucigramas
• Colorear mapas  

2.5. Teoría de juegos.

Siendo una de las principales capacidades de la inteligencia humana su capacidad para resolver problemas, así como la habilidad para analizar los elementos esenciales de cada problema, abstrayéndolos, el identificar las acciones que son necesarias para resolverlos y el determinar cuál es la estrategia más acertada para atacarlos, son rasgos fundamentales.

Podemos definir la resolución de problemas como el proceso que partiendo de unos datos iníciales y utilizando un conjunto de procedimientos escogidos, es capaz de determinar el conjunto de pasos o elementos que nos llevan a lo que denominaremos una solución óptima o semi-óptima de un problema de planificación, descubrir una estrategia ganadora de un juego, demostrar un teorema, reconocer

Una imagen, comprender una oración o un texto son algunas de las tareas que pueden concebirse como de resolución.

Una gran ventaja que nos proporciona la utilización de los juegos es que a través de ellos es muy fácil medir el éxito o el fracaso, por lo que podemos comprobar si las técnicas y algoritmos empleados son los óptimos. En comparación con otras aplicaciones de inteligencia artificial, por ejemplo comprensión del lenguaje, los juegos no necesitan grandes cantidades de algoritmos. Los juegos más utilizados son las damas y el ajedrez.