INTRODUCCIÓN
En este
capítulo hablaremos de los
agentes que están basados
en resolver problemas en
donde veremos que un agente
puede realizar búsqueda de secuencias de acciones donde alcanzara sus
objetivos, ya que
conoceremos de lo agentes basados
en objetivos, hay que saber que los
agentes resolvente de problemas ellos toman decisiones de que hacer para encontrar secuencias de acciones que los conlleve
a un estado deseables
Agentes resolventes-problemas
Se supone que los
agentes inteligentes deben maximizar su medida de rendimiento. Como mencionamos
en el Los agentes resolventes-problemas deciden que hacer para encontrar secuencias
de acciones que conduzcan a los estados deseables.
Los algoritmos son no
informados, en el sentido que no da información sobre el problema salvo su definición.
Los algoritmos de búsqueda informada, los que tengan cierta idea de dónde
buscar las soluciones.
El primer paso para
solucionar un problema es la formulación del objetivo basado en la situación
actual y la medida de rendimiento del agente.
Problemas y soluciones bien definidos
Puede definirse, formalmente, por cuatro componentes importantes:
Ø
El estado inicial en el que comienza el agente.
ü Acciones.- son disponibles por el agente
ü
Espacio de Estado.-
trata del conjunto de todos los estados alcanzables
desde el estado inicial.
ü
El test
objetivo, el
cual determina si un estado es un estado objetivo.
ü
Costo del Camino
que asigna un costo numérico
a cada camino.
ü
El costo
individual de
una acción a que va desde un estado xal estado y se denota por cix,a,y).Los
costos individuales para Rumania se muestran en la Figura 3.2 como las
distancias de las carreteras.
Una solución de un problema es un camino desde
el estado inicial a un estado objetivo. La calidad de la solución se mide por
la función costo del camino, y una solución óptima tiene el costo más pequeño
del camino entre todas las soluciones.
Formular los problemas
En la sección anterior propusimos
una formulación del problema de ir a Bucarest en términos de estado inicial, función
sucesor, test objetivo y costo del camino. Esta formulación parece razonable, a
pesar de omitir muchos aspectos del mundo real.
o
Estados: la descripción de un estado especifica la localización de cada una de
las ocho fichas y el blanco en cada uno de los nueve cuadrados.
o
Estado
inicial: cualquier estado
puede ser un estado inicial. Nótese que cualquier objetivo puede alcanzarse
desde exactamente la mitad de los estados iniciales posibles
•
Fundón
sucesor: esta genera los
estados legales que resultan de aplicar las cuatro acciones (mover el blanco a
la Izquierda, Derecha, Arriba y Abajo).
•
Test
objetivo: comprueba si el
estado coincide con la configuración objetivo que se muestra en la Figura 3.4.
(son posibles otras configuraciones objetivo).
•
Costo
del camino: el costo de cada
paso del camino tiene valor 1, así que el costo del camino es el número de
pasos.
Busqueda de soluciones
ARBOL DE BUSQUEDA explicito generado por el estado inicial y la función
sucesor, definiendo así el espacio de estados. La raíz del árbol de búsqueda es
el nodo de búsqueda que
corresponde al estado inicial, En{Arad).
Es importante distinguir entre el espacio de estados y
el arbol de busqueda.
Una estructura de datos con cinco componentes:
ü Estado: el estado del espacio de
estados que corresponden con el nodo
ü Nodo padre: el nodo en el árbol de búsqueda que ha generado este nodo
ü
Acción: la acción que realiza
al padre para generar el nodo
ü
Costo del camino: el costo tradicionalmente denotado
por g(n), de un camino desde el estado inicial al nodo, indicado por los
punteros a los padres;
ü
Profundidad: el número de paso
a lo largo del camino desde el estado inicial
Imagen
Medir el rendimiento de la resolución del
problema
ü Completitud: está garantizado
que el algoritmo encuentre una solución
cuando esta exista
ü Optimización: encuentra la
estrategia de solución óptima
ü
Complejidad
del tiempo: cuando tarda en encontrar una solución
ü
Complejidad
en espacio: cuando se necesita para funcionamiento de búsqueda
Estrategias de búsqueda no informada
Esta sección trata
cinco estrategias de búsqueda englobadas bajo el nombre de búsqueda no
informada El termino significa que ellas no tienen información
adicional acerca de los estados más allá de la que proporciona la definición
del problema.
Busqueda primero en anchura
Es una estrategia sencilla en la que se expande primero el nodo raíz, a continuación
se expanden todos los sucesores del nodo raíz, después sus sucesores, etc. En
general, se expanden todos los nodos a una profundidad en el árbol de búsqueda
antes de expandir cualquier nodo del próximo nivel.
Búsqueda de costo uniforme
La búsqueda primero en anchura es óptima cuando todos
los costos son iguales, porque siempre expande el nodo no expandido más
superficial. Con una extensión sencilla, podemos encontrar un algoritmo que es óptimo
con cualquier función costo. En vez de expandir el nodo más superficial, la búsqueda
de costo uniforme expande el nodo n con el camino de costo más pequeño.
Notemos que si todos los costos son iguales, es idéntico a la búsqueda primero
en anchura.
Busqueda primero en profundidad
Siempre expande el nodo más profundo en la frontera
actual del árbol de búsqueda. El progreso de la búsqueda se ilustra en la búsqueda
procede inmediatamente al nivel más profundo del árbol de búsqueda, donde los
nodos no tienen ningún sucesor. Cuando esos nodos se expanden, son quitados de
la frontera, así entonces la búsqueda ≪retrocede≫ al siguiente nodo más superficial que todavía tenga
sucesores inexplorados.
Búsqueda
de profundidad limitada
Se puede aliviar el problema de árboles ilimitados
aplicando la búsqueda primero en profundidad con un límite de profundidad t predeterminado.
Es decir, los nodos a profundidad i se tratan como si no tuvieran ningún
sucesor.
Búsqueda
primero en profundidad con profundidad iterativo
Es una estrategia general, usada a menudo en combinación
con la búsqueda primero en profundidad, la cual encuentra el mejor límite de
profundidad hasta que encontramos un objetivo.
Búsqueda
bidireccional
La idea de la búsqueda bidireccional es ejecutar dos búsquedas
simultáneas: una hacia delante desde el estado inicial y la otra hacia atrás
desde el objetivo, parando cuando las dos búsquedas se encuentren en el centro mucho
menor
Conclusión
En este capítulo
concluimos que los agentes resolventes-problemas son agentes basados en objetivo aprendienendo
a utilizar los métodos de busquedad para
cada problema, llegando a una buena solución bien definidos y llegando
al objetivo planteado del agente, utilizando
objetivos el cual se encarga de organizar los problemas.
BIBLIOGRAFÍA
Holger,
B. Rubén, O. 2012. Fundamentos de Inteligencia Artificial.Ing. Sup. en
Informática, 3º. (En línea). PE. Consultado, 15
de oct.2014. Disponible
en:http://www.ia.urjc.es/grupo/docencia/fia/material/temario_FIA_tema1.pdfRussell,
S., Norvig, P. 2008. Inteligencia Artificial Un Enfoque Moderno. Segunda Edición.
Pearson Education. España
