BÚSQUEDA CON INFORMACIÓN PARCIAL

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.

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

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.

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