Inteligencia artificial
Solución de problemas y búsqueda
Inteligencia artificial
Solución de problemas y búsqueda
Pierre Sergei Zuppa Azúa
www.utel.edu.mx
Inteligencia artificial
Solución de problemas y búsqueda
Keyword
www.utel.edu.mx
Inteligencia artificial
Solución de problemas y búsqueda
Solución de problemas
Tipos de problemas:
IA
Específica
• Buscar una solución.
• Determinar si existe solución
y encontrar un estado final.
• Buscar cualquier solución lo
más rápidamente posible.
• Buscar todas las soluciones.
• Buscar la solución más
corta.
• Buscar la solución menos
costosa.
www.utel.edu.mx
Inteligencia del
conocimiento
Inteligencia artificial
Solución de problemas y búsqueda
Búsqueda
Son una serie de esquemas
de representación del
conocimiento, que mediante
diversos algoritmos nos
permite resolver ciertos
problemas desde el punto de
vista de la IA.
www.utel.edu.mx
Inteligencia artificial
Solución de problemas y búsqueda
Elementos de búsqueda
• Conjunto de estados: todas
las configuraciones posibles
en el dominio.
• Estados iniciales: estados
desde los que partimos.
• Estados
finales:
soluciones del problema.
Categorías
las de búsqueda
• Operadores: se aplican para
pasar de un estado a otro.
www.utel.edu.mx
Con
información
Sin
información
Inteligencia artificial
Solución de problemas y búsqueda
Tipo de búsqueda
Tipos de búsqueda
Descripción
Exhaustiva (a ciegas)
No existe información específica sobre el problema que nos ayude a determinar cuál es el
mejor operador que se debería aplicar en cada momento o el mejor nodo por el cual
continuar la búsqueda.
Heurística
Usan el conocimiento del dominio para adaptar el solucionador y, de esta manera, éste
sea más potente y consiga llegar a la solución con mayor rapidez. Por tanto, estas técnicas
utilizan el conocimiento para avanzar buscando la solución al problema.
Estrategia
El primer requisito que debe cumplir una buena estrategia de control es que cause algún
cambio, las estrategias de control que no causen cambio de estado nunca alcanzan la
solución. El segundo requisito que debe cumplir una buena estrategia de control es que
sea sistemática.
Profundidad
Se genera solo un sucesor del nodo en cada paso, es decir, cada vez que se obtiene un
nuevo sucesor, se le aplica a éste un nuevo operador, se obtiene un nuevo sucesor, y así
sucesivamente.
www.utel.edu.mx
Inteligencia artificial
Solución de problemas y búsqueda
Búsqueda exhaustiva
Tipos de búsqueda
exhaustiva
Descripción
Amplitud
Va construyendo un grafo de estados explícito mediante la aplicación de
los operadores disponibles al nodo inicial, después aplica los operadores
disponibles a los nodos sucesores directos del nodo inicial, y así
sucesivamente.
Coste uniforme
Variación a lo ancho del camino para encontrar el más barato, cada cambio
de estado tiene asociado un costo.
Profundidad limitada
Es óptima y garantiza el encontrar la solución al igual que la búsqueda a lo
ancho, pero con requerimientos menores de memoria.
Iterativa
Combina aspectos de la búsqueda a lo ancho y en profundidad.
Bidireccional
Consiste en buscar simultáneamente desde estado inicial y el final.
www.utel.edu.mx
Inteligencia artificial
Solución de problemas y búsqueda
Consideraciones para implementar una estrategia de
búsqueda
• Abarcamiento: ¿La estrategia garantiza encontrar una
solución, si es que la hay?
• Complejidad temporal: ¿Cuánto tiempo es necesario
para encontrar la solución?
• Complejidad espacial: ¿Cuánta memoria se necesita
para efectuar la búsqueda?
• Calidad: ¿La estrategia dará como resultado un resultado
óptimo, en caso de que existan varias soluciones?
www.utel.edu.mx
Inteligencia artificial
Solución de problemas y búsqueda
Espacios de estados
El espacio de búsqueda será un
grafo dirigido en el que cada nodo
representa un posible estado del
sistema.
Búsqueda
estados
en
un
espacio
de
– Espacio de estados
Representación del problema a través
de las (posibles) acciones del agente.
– Búsqueda en el espacio de
estados:
Resolución del problema mediante la
proyección de las distintas acciones del
agente.
www.utel.edu.mx
Inteligencia artificial
Solución de problemas y búsqueda
Espacio-estado
Es un grafo cuyos nodos representan
las configuraciones alcanzables (los
estados válidos) y cuyos arcos
explicitan las movidas posibles (las
transiciones de estado).
Cuando un problema se puede
representar mediante un espacio de
estados, la solución computacional
corresponde a encontrar un camino
desde el estado inicial a un estado
objetivo.
En principio, se puede construir
cualquier
espacio
de
estados
partiendo del estado inicial, aplicando
cada una de las reglas para generar
los sucesores inmediatos, y así
sucesivamente con cada uno de los
nuevos estados generados (en la
práctica, los espacios de estados
suelen ser demasiado grandes para
explicitarlos por completo).
www.utel.edu.mx
Inteligencia artificial
Solución de problemas y búsqueda
Representación espacio-estado
Elementos
Acción: indica cómo modificar el
estado actual para generar un
nuevo estado.
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.
Operadores
Operadores:
Representan un conjunto finito de acciones
básicas que transforman unos estados en otros.
Elementos que describen un operador
Aplicabilidad: precondición y postcondición.
Estado resultante de la aplicación de un operador
(aplicable) a un estado.
Criterio para elegir operadores
Depende de la representación de los estados.
Preferencia por representaciones con menor
número de operadores.
www.utel.edu.mx
Inteligencia artificial
Solución de problemas y búsqueda
Elementos para la implementación de espacio-estado
Elección de una representación (estructura de datos):
• Para los estados.
• Para los operadores.
La implementación de un problema como espacio de estados consta de:
• Una variable *ESTADO-INICIAL*.
• Una función ES-ESTADO-FINAL (ESTADO).
• Una lista de operadores: *OPERADORES*.
• Una función APLICA (OPERADOR, ESTADO).
La función APLICA (OPERADOR, ESTADO):
• Devuelve NO-APLICABLE si OPERADOR no es aplicable a estado.
• En caso contrario, devuelve el estado resultante de aplicar OPERADOR a
ESTADO.
www.utel.edu.mx
Inteligencia artificial
Solución de problemas y búsqueda
Representación por reducción del problema
Para la descripción del algoritmo de
búsqueda en un grafo Y-O, se
definirá
un
valor
llamado INUTILIDAD. Si el valor
estimado para una solución se hace
mayor
que
el
valor
de
INUTILIDAD, se abandona la
búsqueda.
El valor de INUTILIDAD debe
elegirse para que cualquier solución
con un costo superior resulte
demasiado costosa como para ser
de utilidad práctica, aún en el caso
de que sea posible encontrarla.
www.utel.edu.mx
Inteligencia artificial
Solución de problemas y búsqueda
Ejemplo de espacio de estados
Descripción del problema:
Un arriero se encuentra en el
borde de un río llevando un
puma, una cabra y una lechuga.
Debe cruzar a la otra orilla por
medio de un bote con capacidad
para dos (el arriero y alguna de
sus pertenecías). La dificultad es
que si el puma se queda solo con
la cabra la devorará, y lo mismo
sucederá si la cabra se queda
sola con la lechuga. ¿Cómo
cruzar
sin
perder
ninguna
pertenencia?
www.utel.edu.mx
Inteligencia artificial
Solución de problemas y búsqueda
Representación del universo del problema
(ejemplo)
Basta precisar la situación antes o después
de cruzar.
El arriero y cada una de sus pertenencias
tienen que estar en alguna de las dos orillas.
La representación del estado debe entonces
indicar en qué lado se encuentra cada uno
de ellos. Para esto se puede utilizar un
término
simbólico
con
la
siguiente
sintaxis:
estado
(A,P,C,L),
en
que A, P, C y L son variables que
representan, respectivamente, la posición
del arriero, el puma, la cabra y la lechuga.
Las
variables
pueden
tomar
dos
valores:
i
y
d,
que
simbolizan
respectivamente el borde izquierdo y el
borde derecho del río. Por convención se
elige partir en el borde izquierdo.
El estado inicial es entonces estado (i,i,i,i).
El estado objetivo es estado (d,d,d,d).
Definición de las reglas de transición:
El arriero tiene cuatro acciones posibles:
cruzar solo, cruzar con el puma, cruzar con
la cabra y cruzar con la lechuga. Estas
acciones están condicionadas a que ambos
pasajeros del bote estén en la misma orilla y
a que no queden solos el puma con la cabra
o la cabra con la lechuga. El estado
resultante de una acción se determina
intercambiando los valores i y d para los
pasajeros del bote.
www.utel.edu.mx
Inteligencia artificial
Solución de problemas y búsqueda
Generación del espacio de estados
(ejemplo)
En este ejemplo se puede explicitar todo el
espacio
de
estados
(el
número
de
configuraciones está acotado por 24).
El camino que pasa por la siguiente
secuencia de estados es una solución del
problema:
estado(i,i,i,i)
cruza
con
cabra
estado(d,i,d,i)
cruza
solo
estado(i,i,d,i)
cruza
con
puma
estado(d,d,d,i)
cruza
con
cabra
estado(i,d,i,i)
cruza
con
lechuga
estado(d,d,i,d)
cruza
solo
estado(i,d,i,d)
cruza
con
cabra
estado(d,d,d,d)
www.utel.edu.mx
Inteligencia artificial
Solución de problemas y búsqueda
Algoritmo búsqueda en espacio de estados
(ejemplo)
procedure Búsqueda {
open {estado_inicial}
closed {}
while (open no está vacío) {
remover un estado X del conjunto 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
conjunto open
}
}
return fracaso
}
El conjunto open contiene a los estados
generados que todavía no han sido
visitados (no se ha verificado si son
estados objetivo y no se han generado sus
sucesores). El conjunto closed contiene a
los estados visitados. Al considerar sólo a
los
sucesores
que
no
han
sido
previamente generados se evita entrar en
ciclos.
Dependiendo del orden en que se visiten
los estados del conjunto open se obtienen
distintos tipos de recorrido.
www.utel.edu.mx
Inteligencia artificial
Solución de problemas y búsqueda
Algoritmo búsqueda en profundidad
(ejemplo)
procedure Búsqueda_en_profundidad {
El mayor problema de este algoritmo es
open [estado_inicial]
que puede "perderse" en una rama sin
closed {}
encontrar la solución. Además, si se
while (open no está vacía) {
encuentra una solución no se puede
remover el primer estado X de la lista
garantizar que sea el camino más corto.
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
}
www.utel.edu.mx
Inteligencia artificial
Solución de problemas y búsqueda
Algoritmo búsqueda en amplitud
(ejemplo)
procedure Búsqueda_en_amplitud {
Contrariamente a la búsqueda
open [estado_inicial]
profundidad, la búsqueda
closed {}
amplitud garantiza encontrar
while (open no está vacía) {
remover el primer estado X de la lista
camino más corto.
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
}
www.utel.edu.mx
en
en
el
Inteligencia artificial
Solución de problemas y búsqueda
Algoritmo búsqueda heurística
(ejemplo)
procedure Búsqueda_heurística {
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 camino hasta X
else {
generar el conjunto de sucesores del estado X
foreach (Y en sucesores) {
if (Y no está en open ni en closed) {
asignar a Y un valor heurístico
agregar Y en la lista open
}
elsif (Y está en open) {
if (el nuevo camino a Y es más corto)
actualizar el camino almacenado en open
}
elsif (Y está en closed) {
if (el nuevo camino a Y es más corto) {
remover el estado Y del conjunto closed
agregar el estado Y en la lista open
}
}
}
agregar el estado X al conjunto closed
reordenar la lista open según valores heurísticos
}
}
return fracaso
}
Además de utilizar una cola de prioridad, este algoritmo se
diferencia por actualizar los caminos almacenados en la
lista open cada vez que se encuentra un camino más corto,
lo que mejora la probabilidad de encontrar el camino óptimo.
El camino se almacena en cada estado como un puntero al
padre.
Cuando se llega a un estado en closed por un camino más
corto, habría que transmitir esta información a todos sus
sucesores. Sin embargo, algunos de estos sucesores pueden
haber sido generados o posteriormente actualizados por otro
camino que hasta el momento parecía más corto, por lo cual
estarían
desvinculados
del
ancestro
que
se
está
considerando. Administrar este problema sería muy
engorroso, entonces se opta por repetir la búsqueda.
Se puede obtener una versión simplificada de esta búsqueda
heurística eliminando toda la información histórica contenida
en open y closed. En cada paso se generan los sucesores del
estado actual y sólo se conserva al mejor de ellos para el
paso siguiente. El algoritmo se detiene cuando ninguno de
los sucesores tiene una mejor evaluación que el estado
actual (sino entraría en un ciclo infinito). Esta estrategia se
llama algoritmo del gradiente (hill climbing, en inglés).
Funciona adecuadamente cuando no hay óptimos locales.
www.utel.edu.mx
Inteligencia artificial
Solución de problemas y búsqueda
Frase
“Es ridículo vivir 100 años y
solo ser capaces de recordar
30 millones de bytes. O sea,
menos que un compact disc.
La condición humana se hace
más obsoleta cada minuto”
Marvin Minsky
www.utel.edu.mx
Descargar

estado