cienciasdelacomputacion.com

Goal-Driven y Busqueda a lo ancho

Conducida por el objetivo (goal driven – backward chaining)

• Tomar el objetivo que queremos resolver, establecer que reglas o movimientos legales podrían usarse para generar este objetivo y determinar que condiciones deben ser verdaderas para ser usadas.
• Estas condiciones constituyen los nuevos objetivos de la búsqueda y la búsqueda continua hacia atrás hasta encontrar los hechos del problema

BREATH FIRST.- Busqueda a lo ancho. La busqueda se realiza a lo largo del arbol o grafo, recorriendo todos los nodos de una correspondiente fila antes de pasar a la siguiente:

Este es una implementacion en pseudocodigo el cual representa el comportamiento de esta estrategia de busqueda:

Begin
open := [Start];
closed := [ ];
while open ? [ ] do
begin
remove leftmost state from open, call it X;
if X is a goal then returns SUCCESS
else begin
generate children of X;
put X on closed;
discard children of X if already on open or closed;
put remaining children on right end of open
end
end
return FAIL
end

Aplicacion en un arbol, donde el objetivo a encontrar es U
1.    open = [A]; closed = [ ]
2.    open = [B,C,D]; closed = [A]
3.    open = [C,D,E,F]; closed = [B,A]
4.    open = [D,E,F,G,H]; closed = [C,B,A]
5.    open = [E,F,G,H,I,J]; closed = [D,C,B,A]
6.    open = [F,G,H,I,J,K,L]; closed = [E,D,C,B,A]
7.    open = [G,H,I,J,K,L,M] L ya esta en open; closed =[F,E,D,C,B,A]
8.    open = [H,I,J,K,L,M,N]; closed = [G,F,E,D,C,B,A]
9.    Continua hasta encontrar U, o open = [ ].

Estrategias y Algoritmos de Busqueda de Informacion

Existen diferencia de estrategias de búsqueda de información:

• Algoritmo Primero a lo Ancho (BREATH-FIRST)
• Algoritmo Primero en Profundidad (DEPTH-FIRST)
• Búsqueda Heurística:
• Ascenso a Colina
• Recocido Simulado
  • Búsqueda Primero el Mejor (BEST-FIRST)
  • Teorema de Admisibilidad
  • Algoritmo Guiado por Agenda

Las técnicas de solución de problemas en IA, en general, incorporan un proceso de búsqueda.
Todo proceso de búsqueda puede ser visualizado como el recorrido por un árbol en el que cada nodo representa un estado y cada rama representa las relaciones entre los estados cuyos nodos conecta.
En general, las reglas contienen en forma implícita el árbol, y se genera en forma explícita sólo aquellas partes que se decide explorar.
La dirección en la cual se conduce la búsqueda (hacia adelante o hacia atrás).
La estrategia de control, o forma de seleccionar las reglas que pueden ser aplicables. Los principales requerimientos de una buena estrategia de control son: que cause desplazamiento en el espacio de estado; y, que sea sistemático.

La forma de representar cada nodo del proceso de búsqueda (representación del conocimiento).

Muchas veces, tratar el proceso como búsqueda en un grafo en lugar de una búsqueda en un árbol, puede reducir el esfuerzo que se gasta en explorar senderos, esencialmente iguales, varias veces. Sin embargo, los requisitos asociados, son:
Cada vez que se genere un nodo se debe chequear para ver si ha sido generado antes.

Se deben introducir procedimientos especiales para que la búsqueda no quede atrapada en algún lazo.

Existen dos formas de conducer las busquedas:

Conducida por el objetivo (goal driven – backward chaining)

Tomar el objetivo que queremos resolver, establecer que reglas o movimientos legales podrían usarse para generar este objetivo y determinar que condiciones deben ser verdaderas para ser usadas.Estas condiciones constituyen los nuevos objetivos de la búsqueda y la búsqueda continua hacia atrás hasta encontrar los hechos del problema.
Conducida por los datos (data driven – forward chaining)

Búsqueda empieza con los hechos o datos conocidos y un conjunto de movimientos legales o reglas para cambiar de estado.La búsqueda se realiza aplicando las reglas a los datos o hechos, produciendo nuevos datos o hechos. Este proceso continua hasta generar una ruta que satisfaga la condición del objetivo.

Plateamiento de problemas en IA

A continuación se plantean tres soluciones diferentes del problema de tres en raya analizando la conveniencia de cada una. Cada una de las soluciones plantea un enfoque diferente, pero solo la última simula la forma en que una computadora lo resolveria de forma inteligente:

Solución 1:

• Una primera solución directa a este juego podría ser la de almacenar en un vector las 19.693 posibilidades de un tablero de 3 x 3 con tres valores posibles en cada casilla (vacío-X-O), así como las correspondientes jugadas sucesoras.
• Para realizar una jugada, bastaría con acceder a la posición del tablero actual y la jugada sucesora correspondiente.
• Las desventajas de este eficiente programa son bastante obvias:
• Necesita gran cantidad de memoria; alguien debe realizar el pesado trabajo de introducir todas las jugadas y sus sucesoras; y el juego no se puede ampliar, por ejemplo a tres dimensiones.

Solución 2:

• El programa posee una estrategia para cada turno de jugador.
• Analiza el posible triunfo a partir de un estado del tablero dado.
• Aunque es menos eficiente que la solución anterior en términos de tiempo, tiene la ventaja que es más eficiente en términos de espacio.
• Su estrategia es más fácil de comprender y realizar cambios, aunque el programador debe comprender la totalidad de la estrategia de antemano.
• Además, no es posible generalizar parte del conocimiento del programa hacia un dominio distinto, como tres en raya 3D.

Solución 3:

• Una estructura contiene el tablero actual, así como una lista de posiciones del tablero que podrían ser el próximo movimiento, y una estimación de la probabilidad de que esa jugada lleve a la victoria.
• Para decidir la siguiente jugada se tienen en cuenta las posiciones de tablero que resultan de cada movimiento posible.
• Se decide la posición que corresponde a la mejor jugada, considerando si la jugada produce la victoria, y en caso contrario considerando todos los movimientos que el oponente puede realizar asumiendo que éste elegirá el peor para nosotros.
• El algoritmo inspecciona varias secuencias de movimientos intentando maximizar la probabilidad de victoria.
• Necesita mucho más tiempo que los demás, ya que debe realizar una búsqueda en un árbol de posibilidades antes de realizar cada movimiento. Sin embargo, es superior a las demás soluciones pues podría ser ampliado para manipular juegos más complicados.
• Además, puede aumentar su potencia usando conocimiento sobre el juego, por ejemplo, en lugar de considerar todos los posibles movimientos considerar solo un subconjunto siguiendo algún criterio razonable.

Este último es un ejemplo del uso de una técnica de IA.

Dado este ejemplo, podemos definir tres parámetros importantes para poder resolver un problema usando IA:

• Búsqueda: proporciona una forma de resolver problemas en los que no se dispone de un método directo
• Uso del conocimiento: proporciona una forma de resolver problemas complejos explotando las estructuras existentes entre los objetos involucrados

• Abstracción: proporciona una forma de separar aspectos y variaciones importantes de aquellos otros sin importancia, y que en caso contrario podrían colapsar el proceso.

Más adelante describiremos en detalle cada uno de estos elementos.

Breve reseña historica de la IA

El desarrollo de la IA ha sido bien documentada a travez del tiempo. Con una excelente herramienta como es el Internet, resulta muy sencillo entender el desarrollo de la misma, gracias personajes muy como Turing.

Empero existen otros personajes importantes en el desarrollo de esta rama de la ciencia de la computación, que no son muy conocidos, más no por ello menos importantes de resaltar. Hea qui en breve resumen por períodos del desarrollo de la IA:

• 1950-1965. Periodo “clásico…”

Resolvedor general de problemas (GPS) [Newell, Simon]. Resolución de problemas de sentido común, los cuales incluyen razonamiento de objetos físicos y sus relaciones, como también razonamiento de acciones y sus consecuencias. Solo se resolvieron tareas simples, pues no se pudo crear un programa con la cantidad suficiente de conocimiento de un dominio específico.

Principal énfasis en la implementación de juegos (ajedrez, damas, etc.) así como en la demostración de teoremas matemáticos.

• 1965-1975. Periodo “romántico”

Representación “general” del conocimiento.

Redes semánticas [Quillian]

Prototipos (frames) [Minsky]

Perceptrón [Minsky y Papert]

Lógica [Kowalski]

Mundo de bloques [Winograd]

Percepción (visión y habla), compresión de lenguaje natural, robótica.

Dificultades de representación “general”, problemas de “juguete”.

• 1975-actualidad. Periodo “moderno”, inteligencia “especifica” vs. “general”.

Se identifica la necesidad de trabajar en sociedad con profesionales de otras áreas de conocimiento

Representación explícita del conocimiento específico del dominio.

Sistema experto médico MYCIN (experto en enfermedades infecciosas de la sangre) iniciado en la Universidad de Stanford

Sistemas expertos o basados en conocimiento.

Regreso de redes neuronales [Hopfield, Rumelhart, Hinton], algoritmos genéticos [Holland, Goldberg]

Reconocimiento de voz , incertidumbre (Lógica difusa), planeación, aprendizaje

Aplicaciones “reales” (medicina, finanzas, ingeniería, exploración, etc.).

Comercialización de la IA, etapa de conocimiento general de la misma

Estos son breves rasgos de la historia actual de la IA. Para mayor informacion , aqui.