INTELIGENCIA ARTIFICIAL 2

jueves, 13 de noviembre de 2014

FUNCIONES HEURÍSTICAS

INTRODUCCIÓN

En computación, dos objetivos fundamentales son encontrar algoritmos con buenos tiempos de ejecución y buenas soluciones, usualmente las óptimas. Una heurística es un algoritmo que abandona uno o ambos objetivos; por ejemplo, normalmente encuentran buenas soluciones, aunque no hay pruebas de que la solución no pueda ser arbitrariamente errónea en algunos casos; o se ejecuta razonablemente rápido, aunque no existe tampoco prueba de que siempre será así. Las heurísticas generalmente son usadas cuando no existe una solución óptima bajo las restricciones dadas (tiempo, espacio, etc.), o cuando no existe del todo.

OBJETIVO

La siguiente clase tiene como objetivo entender que son las funciones heurísticas.

FUNCIONES HEURÍSTICAS

El coste medio de la solución para los casos generados al azar del 8-puzle son aproximadamente 22 pasos. El factor de ramificación es aproximadamente tres. (Cuando la ficha vacía está en el medio, hay cuatro movimientos posibles; cuando está en una es quina hay dos; y cuando está a lo largo de un borde hay tres.) Esto significa que una búsqueda exhaustiva a profundidad 22 miraría sobre 3^33 = 3,1 X 10^10 estados. Manteniendo la pista de los estados repetidos, podríamos reducirlo a un factor de aproximadamente 170.000, porque hay sólo 9 !/2 = 181.440 estados distintos que son alcanzables.

• h1 = número de piezas mal colocadas, las 8 piezas están fuera de su posición, así que el estado inicial tiene h1 = 8. h1 es una heurística admisible, porque está claro que cualquier pieza que está fuera de su lugar debe mover se por lo menos una vez.

• h2 = suma de las distancias de las piezas a sus posiciones en el objetivo. Como las piezas no pueden moverse en diagonal, la distancia que contaremos será la suma de las distancias horizontales y verticales. Esto se llama a veces la distancia en la ciudad o Distancia de Manhatta h2 es también admisible, porque cualquier movimiento que se puede hacer es mover una pieza un paso más cerca del objetivo. Las piezas 1 a 8 en el estado inicial nos dan una distancia de Manhattan de h2 = 3 + 1 + 2 + 2 + 2 + 3 + 3 + 2 = 18

Como era de esperar, ninguna sobrestima el coste solución verdadero, que es 26.

El efecto de la precisión heurística en el rendimiento

Inventar funciones heurísticas admisibles

A un problema con menos restricciones en las acciones se le llama problema relajado

Una ficha puede moverse del cuadrado A al cuadrado B si A es horizontalmente o verticalmente adyacente a B y B es la vacía.

Podemos generar tres problemas relajados quitando una o ambas condiciones:

(a) Una ficha puede moverse del cuadrado A al cuadrado B si A es adyacente a B.

(b) Una ficha puede moverse del cuadrado A al cuadrado B si B es el vacío.

CONCLUSIÓN

Las funciones heurísticas son funciones que busque el mejor camino para llegar a un resultado y podemos inventar a partir de las que tenemos definidas.

BIBLIOGRAFÍA

Zambrano, R. 2010. Funciones Heuristicas. (En línea). Disponible en: https://www.cs.us.es/cursos/ia1/temas/tema-04.pdf

Russell, s.2008.inteligencia artificial un enfoque moderno. Segunda edición. Pearson education. Madrid-España.

jueves, 6 de noviembre de 2014

ESTRATEGIAS DE BÚSQUEDA INFORMADA

INTRODUCCIÓN

Las estrategias de búsqueda no informada resuelven problemas mediante generación sistemática de estados, pero son muy ineficientes

Vamos a ver cómo las estrategias de búsqueda informada o heurística, usando conocimiento específico del problema, pueden resolver problemas más eficientemente

OBJETIVO

La siguiente clase tiene como objetivo comprender las estrategias de Búsqueda informada.

Búsqueda voraz primero el mejor

La búsqueda voraz priman el mejor trata de expandir el nodo más cercano al objetivo, alegando que probablemente conduzca rápidamente a una solución. Así, evalúa los nodos utilizando solamente la función heurística: ñn) = h(n). Veamos cómo trabaja para los problemas de encontrar una ruta en Rumania utilizando la heurística «Bstanriaoi linea recta que llamaremos hDUt Si el objetivo es Bucarest, tendremos que conocer las distancias en línea recta a Bucarest, que se muestran en la. Por ejemplo, h[xJyEn(Arad)) = 366. Notemos que los valores de hDLRno pueden calcularse de la descripción de problema en sí mismo. Además, debemos tener una cierta cantidad de experiencia para saber que hnK está correlacionada con las distancias reales del camino y es, por lo tanto, una heurística útil.

BÚSQUEDA A*

Características Principales

Como todo algoritmo de búsqueda en anchura, A* es un algoritmo completo: en caso de existir una solución, siempre dará con ella. Si para todo nodo n del grafo se cumple g(n) = 0, nos encontramos ante una búsqueda voraz. Si para todo nodo n del grafo se cumple h(n) = 0, A* pasa a ser una búsqueda de coste uniforme no informada.

Para garantizar la optimalidad del algoritmo, la función h(n) debe ser admisible, o sea que no sobrestime el coste real de alcanzar el nodo objetivo.

De no cumplirse dicha condición, el algoritmo pasa a denominarse simplemente A, y a pesar de seguir siendo completo, no se asegura que el resultado obtenido sea el camino de coste mínimo. Asimismo, si garantizamos que h(n) es consistente (o monótona), es decir, que para cualquier nodo n y cualquiera de sus sucesores, el coste estimado de alcanzar el objetivo desde n no es mayor que el de alcanzar el sucesor más el coste de alcanzar el objetivo desde el sucesor. La complejidad computacional está relacionada con la calidad de laheurística que se utilice en el problema. En el caso peor, con una heurística de pésima calidad, la complejidad será exponencial, mientras que en el caso mejor, con una buena h'(n), el algoritmo se ejecutará en tiempo lineal.

El espacio requerido por A* para ser ejecutado es su mayor problema. Dado que tiene que almacenar todos los posibles siguientes nodos de cada estado, la cantidad de memoria que requerirá será exponencial con respecto al tamaño del problema. Para solucionar este problema, se han propuesto diversas variaciones de este algoritmo, como pueden ser RTA*, IDA* o SMA*.

El rendimiento de los algoritmos de búsqueda heurística depende de la calidad de la función heurística.

BÚSQUEDA CON MEMORIA ACOTADA

Problema del algoritmo A* => Altos requerimientos de memoria.
Algoritmo A*PI: Los requerimientos de memoria se pueden solucionar aplicando el algoritmo de PI
(Profundidad Iterativa) al A*:
– Función de corte: f-coste (g+h)
– En cada iteración el valor del corte es f-coste más pequeño de cualquier nodo que excedió el coste de la iteración anterior.
Algoritmos con memoria acotada:
– BRPM: Búsqueda recursiva primero el mejor.
– A*M: Algoritmo A* con memoria acotada.
– A*MS: Algoritmo A* con memoria simplificada.

CONCLUSIÓN

Búsqueda voraz primero el mejor.- Expande el nodo más cercano al objetivo, asumiendo que probablemente conduzca más rápidamente a la solución. La función de evaluación f(n) es la función heurística h(n)=f(n) = h(n) donde h(n) = costo estimado del camino más barato desde el nodo n hasta el objetivo

Búsqueda A*.- Minimizar el costo estimado total de la solución
Evalúa los nodos combinando g(n) y h(n)
g(n): costo de haber alcanzado n
h(n): costo para llegar desde n hasta el objetivo
f(n) = g(n) + h(n) -> costo más barato estimado de la f(n) = g(n) + h(n) -> costo más barato estimado de la solución a través de n En cada paso se expande el nodo con el valor más bajo de f(n), ó sea, de g(n)+h(n)

La búsqueda A* es óptima siempre y cuando la función heurística h(n) sea una heurística admisible,
nunca sobreestime el costo de alcanzar el objetivo, son funciones optimistas.

BIBLIOGRAFÍA

Cesar S 2008. Búsqueda Informada. (En línea). EC. Consultado, 13 de Noviembre. 2014. Formato HTML. Disponible en: http://www.ecured.cu/index.php/Algoritmo_de_B%C3%BAsqueda_Heur%C3%ADstica_A*
Ruiz, j. 2012. Búsqueda Informada. (En línea). Disponible en: http://www.cs.us.es/cursos/ia1/temas/tema-06.pdf

Russell, s.2008.inteligencia artificial un enfoque moderno. Segunda edición. Pearson education. Madrid-España.

jueves, 30 de octubre de 2014

ESTRATEGIAS DE BÚSQUEDA NO INFORMADA

INTRODUCCIÓN

Un problema típico de la Inteligencia Artificial consiste en buscar un estado concreto entre un conjunto determinado, al que se le llama espacio de estados. Imaginemos, por ejemplo, una habitación con baldosines en la que hay un libro. Un robot se desea desplazar por la habitación con el fin de llegar a dicho libro. ¿De qué manera lo hará? En este punto es donde entran en juego las estrategias y los algoritmos de búsqueda.

Cuando el sistema agente (en este caso, el robot) posee algún tipo de información del medio, se utilizan técnicas de búsquedas informadas; sin embargo, si carece de conocimiento alguno, se deberán emplear algoritmos de búsqueda no informadas.

OBJETIVO

La siguiente clase tiene como objetivo comprender las estrategias de Búsqueda no informada.

ESTRATEGIAS DE BÚSQUEDA NO INFORMADA

Esta sección trata cinco estrategias de búsqueda englobadas bajo el nombre de búsqueda no informada (llamada también búsqueda a ciegas). El término significa que ellas no tienen información adicional acerca de los estados más allá de la que proporciona la definición del problema. Todo lo que ellas pueden hacer es generar los sucesores y distinguir entre un estado objetivo de uno que no lo es.

Búsqueda en amplitud

La técnica de búsqueda primero en amplitud

La búsqueda primero en amplitud o 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.

La búsqueda primero en anchura se puede implementar utilizando una estructura de tipo cola primero en entrar primero en salir, asegurándose que los nodos primeros visitados serán los primeros expandidos.

La principal desventaja de la búsqueda en anchura es los requisitos de memoria para almacenar todos los nodos que no han sido expandidos durante la búsqueda.

Continuaremos con el ejemplo del problema del agente de viajes con la misma formulación vista en la búsqueda en profundidad.

Si tenemos una estructura de datos de tipo cola para implementar esta estrategia de búsqueda:

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.

La principal desventaja de la búsqueda en anchura es los requisitos de memoria para almacenar todos los nodos que no han sido expandidos durante la búsqueda.

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.

La búsqueda de costo uniforme no se preocupa por el número de pasos que tiene un camino, pero sí sobre su coste total. Por lo tanto, éste se meterá en un bucle infinito si expande un nodo que tiene una acción de coste cero que conduzca de nuevo al mismo estado. Podemos garantizar completitud si el costo de cada paso es mayor o igual a alguna constante positiva pequeña e. Esta condición es también suficiente para asegurar optimización. Significa que el costo de un camino siempre aumenta cuando vamos por él. De esta propiedad, es fácil ver que el algoritmo expande nodos que incrementan el coste del camino. Por lo tanto, el primer nodo objetivo seleccionado para la expansión es la solución óptima. (Recuerde que la búsqueda en árboles aplica el test objetivo sólo a los nodos que son seleccionados para la expansión.)

Búsqueda en profundidad

Evaluación de una búsqueda

La evaluación de la eficiencia de una técnica de búsqueda esta fuera del alcance de este curso ya que puede ser muy complicada. De hecho, esta evaluación se lleva gran parte de la investigación en IA. Sin embargo, veremos dos medidas elementales que son importantes para obtener una idea de las ventajas y desventajas de utilizar una u otra técnica:

1. La rápidez con que se encuentra la solución.

2. La calidad de la solución.

Hay varios tipos de problemas para los cuales lo principal es encontrar una solución con el mínimo esfuerzo.

Para ese tipo de problemas, la primera medida es importante. Sin embargo, en otras situaciones, lo más importante es que la solución sea lo más aproximado a una solución óptima.

Tanto la longitud del camino para la solución como el número real de nodos que atraviesa, determina

la velocidad de búsqueda.

Es importante entender la diferencia entre encontrar una solución óptima y una solución buena. La diferencia radica en el hecho de que encontrar una solución óptima a menudo nos exige una búsqueda exhaustiva porque puede que sea este el único camino para determinar si hemos encontrado o no la mejor solución. No obstante, encontrar una buena solución significa encontrar una que esté inmersa en un conjunto de restricciones(sin importar si hay o no una mejor solución)

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. A esta aproximación se le llama búsqueda de profundidad limitada. El límite de profundidad resuelve el problema del camino infinito. Lamentablemente, también introduce una fuente adicional de incompletitud si escogemos € < d, es decir, el objetivo está fuera del límite de profundidad. (Esto no es improbable cuando es desconocido.) La búsqueda de profundidad limitada también será no óptima si escogemos i > d. Su complejidad en tiempo es 0(kf) y su complejidad en espacio es 0(bí). La búsqueda primero en profundidad puede verse como un caso especial de búsqueda de profundidad limitada.

Aveces, los límites de profundidad pueden estar basados en el conocimiento del problema.

Búsqueda primero en profundidad con profundidad

iterativa

La búsqueda con profundidad iterativa (o búsqueda primero en profundidad con profundidad iterativa) 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. Esto se hace aumentando gradualmente el límite (primero 0, después 1, después 2, etcétera) hasta que encontramos un objetivo. Esto ocurrirá cuando el límite de profundidad alcanza d, profundidad del nodo objetivo. La profundidad iterativa combina las ventajas de la búsqueda primero en profundidad y primero en anchura. En la búsqueda primero en profundidad, sus exigencias de memoria son muy modestas: La búsqueda primero en anchura, es completa cuando el factor de ramificación es finito y óptima cuando el coste del camino es una función que no disminuye con la profundidad del nodo.

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. La motivación es que bd/2 + tí112 es mucho menor que tí1, o en la figura, el área de los dos círculos pequeños es menor que el área de un círculo grande centrado en el inicio y que alcance al objetivo.

La búsqueda bidireccional se implementa teniendo una o dos búsquedas que comprueban antes de ser expandido si cada nodo está en la frontera del otro árbol de búsqueda; si esto ocurre, se ha encontrado una solución. Por ejemplo, si un problema tiene una solución a profundidad d = 6, y en cada dirección se ejecuta la búsqueda primero en anchura, entonces, en el caso peor, las dos búsquedas se encuentran cuando se han expandido todos los nodos excepto uno a profundidad 3. Para b = 10, esto significa un total de 22.200 nodos generados, comparado con 11.111.100 para una búsqueda primero en anchura estándar. Verificar que un nodo pertenece al otro árbol de búsqueda se puede hacer en un tiempo constante con una tabla h a sh, así que la complejidad en tiempo de la búsqueda bidirecdonal es 0 ( tfi/2). Por lo menos uno de los árboles de búsqueda se debe mantener en memoria para que se pueda hacer la comprobación de pertenencia, de ahí que la complejidad en espacio es también OÍZ^2). Este requerimiento de espacio es la debilidad más significativa de la búsqueda bidirecdonal. El algoritmo es completo y óptimo (para costos uniformes) si las búsquedas son primero en anchura; otras combinaciones pueden sacrificar la completitud, optimización, o ambas. La reducción de complejidad en tiempo hace a la búsqueda bidireccional atractiva, pero ¿cómo busca hacia atrás? Esto no es tan fácil como suena. Sean los predecesores de un nodo n, Pred(n), todos los nodos que tienen como un sucesor a n. La búsqueda bidireccional requiere que Pred{rí) se calcule eficientemente. El caso más fácil es cuando todas las acciones en el espacio de estados son reversibles, así que Pred[rí) = Succ{rí). Otro caso puede requerir ser ingenioso.

Evitar estados repetidos

Hasta este punto, casi hemos ignorado una de las complicaciones más importantes al proceso de búsqueda: la posibilidad de perder tiempo expandiendo estados que ya han sido visitados y expandidos. Para algunos problemas, esta posibilidad nunca aparece; el espacio de estados es un árbol y hay sólo un camino a cada estado. La formulación eficiente del problema de las ocho reinas (donde cada nueva reina se coloca en la columna vacía de más a la izquierda) es eficiente en gran parte a causa de esto (cada estado se puede alcanzar sólo por un camino). Si formulamos el problema de las ocho reinas para poder colocar una reina en cualquier columna, entonces cada estado con n reinas se puede alcanzar por n\ caminos diferentes.

Para algunos problemas, la repetición de estados es inevitable. Esto incluye todos los problemas donde las acciones son reversibles, como son los problemas de búsqueda de rutas y los puzles que deslizan sus piezas. Los árboles de la búsqueda para estos problemas son infinitos, pero si podamos parte de los estados repetidos, podemos cortar el árbol de búsqueda en un tamaño finito, generando sólo la parte del árbol que atraviesa el grafo del espacio de estados. Considerando solamente el árbol de búsqueda hasta una profundidad fija, es fácil encontrar casos donde la eliminación de estados repetidos produce una reducción exponencial del coste de la búsqueda. En el caso extremo, un espacio de estados de tamaño d + 1 se convierte en un árbol con 2rf hojas Un ejemplo más realista es la rejilla rectangular como se ilustra en la Figura. Sobre una rejilla, cada estado tiene cuatro sucesores, entonces el árbol de búsqueda, incluyendo estados repetidos, tiene 4 hojas; pero hay sólo 2a* estados distintos en cada pasos desde cualquier estado. Para d = 20, significa aproximadamente un billón de nodos, pero aproximadamente 800 estados distintos. Entonces, si el algoritmo no detecta los estados repetidos, éstos pueden provocar que un problema resoluble llegue a ser irresoluble. La detección por lo general significa la comparación del nodo a expandir con aquellos que han sido ya expandidos; si se encuentra un emparejamiento, entonces el algoritmo ha descubierto dos caminos al mismo estado y puede desechar uno de ellos.

Para la búsqueda primero en profundidad, los únicos nodos en memoria son aquellos del camino desde la raíz hasta el nodo actual. La comparación de estos nodos permite al algoritmo descubrir los caminos que forman ciclos y que pueden eliminarse inmediatamente. Esto está bien para asegurar que espacios de estados finitos no hagan árboles de búsqueda infinitos debido a los ciclos; lamentablemente, esto no evita la proliferación exponencial de caminos que no forman ciclos, en problemas como los de la Figura. El único modo de evitar éstos es guardar más nodos en la memoria. Hay una compensación fundamental entre el espacio y el tiempo. Los algoritmos que olvidan su historia están condenados a repetirla.

Problema:

El mismo estado puede repetirse varias veces en el árbol de búsqueda

Puede generarse el mismo subárbol varias veces

Soluciones:

Ignorarlo

Evitar ciclos simples:

No añadir el padre de un nodo al conjunto de sucesores

Evitar ciclos generales:

Np añadir un antecesor de un nodo al conjunto de sucesores

Evitar todos los estados repetidos:

No añadir ningún nodo existente en el árbol al conjunto de sucesores

CONCLUSIÓN

Las estrategias de búsquedas vistas en esta unidad nos dan una idea de cómo los investigadores en IA proponen diferentes formas de solución para los problemas. Estas técnicas son clásicas de la IA y es por ello que deben ser conocidas por todos aquellos que están relacionados con programación de soluciones por computadora. Estas técnicas son clásicas de la IA y es por ello que deben ser conocidas por todos aquellos que están relacionados con programación de soluciones por computadora. Todos ellos requieren de una mayor complejidad de computación y mayor conocimiento e información del problema. En la mayoría de las estrategias contempladas en el cápitulo, debe utilizarse médios para evitar estados repetidos, de esta forma se ahorrara espacio de almacenamiento y tiempo de recorrido. Los algoritmos que olvidan su historia están condenados a repetirla.

El mundo real es más complejo de lo que se formula en los problemas para solucionar por computadora, sin embargo asumimos que los seres humanos para encontrar soluciones tampoco requieren de mucha información, o al menos no requiere conocer todo el universo para encontrar soluciones buenas. Por ejemplo, no requerimos de mucha información, ni de mucho tiempo para seleccionar una botella de refresco que compramos en el supermercado. Esto justifica en parte lo que hacemos cuando reducimos nuestro problema. Aún cuando por su simplicidad sean problemas de juguete.

BIBLIOGRAFÍA

Russell, s.2008.inteligencia artificial un enfoque moderno. Segunda edición. Pearson education. Madrid-España.

Universidad de Castilla - La Mancha 2010, Búsqueda no informada. (En línea). EC. Consultado, 15 de Octubre. 2014. Formato PDF. Disponible en: http://www.sanchezcrespo.org/Docencia/IA/IA%20-%20Tema%203B%20-%20Busquedas%20v1.3.pdf

García D 2009. Búsqueda no informada. (En línea). EC. Consultado, 15 de Octubre. 2014. Formato PDF. Disponible en: http://www.unistmo.edu.mx/~daniel.garcia/unidadiii_ia.pdf

Hermoso, R y Vasirani, M. 2012. Búsqueda no informada. (En línea). EC. Consultado, 15 de Octubre. 2014. Formato PDF. Disponible en: http://www.ia.urjc.es/cms/sites/default/files/userfiles/file/ia4/2011/IA4_%5BBusq_No_Inf%5D.pdf

jueves, 23 de octubre de 2014

BÚSQUEDA CON INFORMACIÓN PARCIAL

INTRODUCCIÓN

OBJETIVO

La siguiente clase tiene como objetivo comprender las estrategias de Búsqueda no informada.

Búsqueda con información parcial

El entorno es totalmente observable y determinista y que el agente conoce cuáles son los efectos de cada acción. Por lo tanto, el agente puede calcular exactamente cuál es el estado resultado de cualquier secuencia de acciones y siempre sabe en qué estado está. Su percepción no proporciona ninguna nueva información después de cada acción. ¿Qué pasa cuando el conocimiento de los estados o acciones es incompleto? Encontramos que diversos tipos de incompletitud conducen a tres tipos de problemas distintos:

Problemas sin sensores (también llamados problemas conformados): si el agente no tiene ningún sensor, entonces (por lo que sabe) podría estar en uno de los posibles estados iniciales, y cada acción por lo tanto podría conducir a uno de los posibles estados sucesores.

Problemas de antingencia: si el entorno es parcialmente observable o si las acciones son inciertas, entonces las percepciones del agente proporcionan nueva información después de cada acción. Cada percepción posible define una contingencia que debe de planearse. A un problema se le llama entre advosarios si la incertidumbre está causada por las acciones de otro agente.

Problemas de exploración: cuando se desconocen los estados y las acciones del entorno, el agente debe actuar para descubrirlos. Los problemas de exploración pueden verse como un caso extremo de problemas de contingencia.

Como ejemplo, utilizaremos el entorno del mundo de la aspiradora. Recuerde que el espacio de estados tiene ocho estados, como se muestra en la Figura. Hay tres acciones {Izquierda, Derecha y Aspirar) y el objetivo es limpiar toda la suciedad (estados 7 y 8). Si el entorno es observable, determinista, y completamente conocido, entonces el problema es trivialmente resoluble por cualquiera de los algoritmos que hemos descrito. Por ejemplo, si el estado inicial es 5, entonces la secuencia de acciones [Derecha, Aspirar] alcanzará un estado objetivo, 8. El resto de esta sección trata con las versiones sin sensores y de contingencia del problema.

Problemas sin sensores

Supongamos que el agente de la aspiradora conoce todos los efectos de sus acciones, pero no tiene ningún sensor. Entonces sólo sabe que su estado inicial es uno del conjunto {1, 2, 3, 4, 5, 6, 7, 8}. Quizá supongamos que el agente está desesperado, pero de hecho puede hacerlo bastante bien. Como conoce lo que hacen sus acciones, puede, por ejemplo, calcular que la acción Derecha produce uno de los estados {2, 4, 6, 8}, y la secuencia de acción [Derecha, Aspirar] siempre terminará en uno de los estados {4, 8}. Finalmente, la secuencia (Derecha, Aspirar, Izquierda, Aspirar] garantiza alcanzar el estado objetivo 7 sea cual sea el estado inicio. Decimos que el agente puede coaccionar con la acción al mundo en el estado 7, incluso cuando no sepa dónde comenzó. Resumiendo: cuando el mundo no es completamente observable, el agente debe decidir sobre los conjuntos de estados que podría poner, más que por estados simples. Llamamos a cada conjunto de estados un estado de creencia, representando la creencia actual del agente con los estado de CREENCIA estados posibles físicos en los que podría estar. (En un ambiente totalmente observable, cada estado de creencia contiene un estado físico.) Para resolver problemas sin sensores, buscamos en el espacio de estados de creencia más que en los estados físicos. El estado inicial es un estado de creencia, y cada acción aplica un estado de creencia en otro estado de creencia. Una acción se aplica a un estado de creencia uniendo los resultados de aplicar la acción a cada estado físico del estado de creencia. Un camino une varios estados de creencia, y una solución es ahora un camino que conduce a un estado de creencia, todos de cuyos miembros son estados objetivo. La Figura muestra el espacio de estados de creencia accesible para el mundo determinista de la aspiradora sin sensores. Hay sólo 12 estados de creencia accesibles, pero el espacio de estados de creencia entero contiene todo conjunto posible de estados físicos, por ejemplo, 2^8 = 256 estados de creencia. En general, si el espacio de estados físico tiene S estados, el espacio de estados de creencia tiene 12 estados de creencia. Nuestra discusión hasta ahora de problemas sin sensores ha supuesto acciones de terministas, pero el análisis es esencialmente el mismo si el entorno es no determinista, es decir, si las acciones pueden tener varios resultados posibles. La razón es que, en ausencia de sensores, el agente no tiene ningún modo de decir qué resultado ocurrió en realidad, así que varios resultados posibles son estados físicos adicionales en el estado de creencia sucesor.

CONCLUSIÓN

BIBLIOGRAFÍA

Russell, s.2008.inteligencia artificial un enfoque moderno. Segunda edición. Pearson education. Madrid-España.

Roberto J 2010, Búsqueda con Información Parcial. (En línea). EC. Consultado, 22 de Octubre. 2014. Formato PDF. Disponible http://www.aconute.es/iartificial/documentos/ia_intro_busqueda.pdf

Cesar S 2008. Búsqueda con Información Parcial. (En línea). EC. Consultado, 22 de Octubre. 2014. Formato PDF. Disponible en: http://www.sanchezcrespo.org/Docencia/IA/IA%20-%20Tema%203A%20-%20Busquedas%20v1.2.pdf