Espacios De Estados

Espacios de estados Muchos de los problemas que pueden ser resueltos aplicando técnicas de inteligencia artificial se modelan en forma simbólica y discreta definiendo las configuraciones posibles del universo estudiado. El problema se plantea entonces en términos de encontrar una configuración objetivo a partir de una configuración inicial dada, aplicando transformaciones válidas según el modelo del universo. La respuesta es la secuencia de transformaciones cuya aplicación sucesiva lleva a la configuración deseada. Los ejemplos más característicos de esta categoría de problemas son los juegos (son universos restringidos fáciles de modelar). En un juego, las configuraciones del universo corresponden directamente a las configuraciones del tablero. Cada configuración es un estado que puede ser esquematizado gráficamente y representado en forma simbólica. Las transformaciones permitidas corresponden a las reglas o movidas del juego, formalizadas como transiciones de estado. Entonces, para plantear formalmente un problema, se requiere precisar una representación simbólica de los estados y definir reglas del tipo condición acción para cada una de las transiciones válidas dentro del universo modelado. La acción de una regla indica como modificar el estado actual para generar un nuevo estado. La 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. El espacio de estados de un juego es un grafo cuyos nodos representan las configuraciones alcanzables (los estados válidos) y cuyos arcos explicitan las movidas posibles (las transiciones de estado). 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). 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. Búsqueda en espacio de estados Existen varios algoritmos para encontrar un camino solución en un espacio de estados. El esquema general de estos algoritmos es el siguiente: 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. Búsqueda en el espacio de estados Es un proceso usado en el campo de la Informática, incluyendo la Inteligencia Artificial (AI), en el cual se consideran sucesivos estados de una instancia, con la meta de encontrar un "estado final" con las características deseadas. Los problemas se modelan a menudo como un espacio de estados, un conjunto de estados que contiene el problema. El conjunto de estados forma un grafo donde dos estados están conectados si hay una operación que pueda se pueda llevar a cabo para transformar el primer estado en el segundo. La búsqueda en el espacio de estados difiere de los métodos de búsqueda tradicionales porque el espacio de estados está implícito: El grafo del espacio de estados típico es demasiado grande para generarlo y guardarlo en memoria. En su lugar, los nodos se generan en el momento en que se exploran y generalmente son descartados después. Una solución puede consistir solamente en un estado objetivo, o en un camino desde un estado inicial hasta el estado final.

Razonamiento con Incertidumbre

Ser capaz de razonar sin tener todo el conocimiento relevante en un campo determinado utilizando lo mejor posible el conocimiento que se tiene. Asociar a los elementos del formalismo de representación, información adicional (normalmente valores numéricos) que indique su grado de certeza y manejar esa información en las inferencias. Implementación: Es difícil cumplir estos requerimientos utilizando la lógica de primer orden Deben de introducirse modelos para manejar información vaga, incierta, incompleta y contradictoria. Crucial para que un sistema funcione en el “mundo real”. El propósito último de un sistema inteligente es actuar de forma óptima utilizando el conocimiento del sistema y un conjunto de percepciones. Para actuar se necesita decidir qué hacer. ¿Cuál es la forma correcta de decidir? La decisión racional: cuando se tienen distintas opciones un sistema debe decidirse por aquella acción que le proporcione el mejor resultado. Cuando hay incertidumbre para poder decidir racionalmente se requiere:  La importancia de los distintos resultados de una acción.  La certidumbre de alcanzar esos resultados cuando se realiza la acción. Cuestiones a resolver por las aproximaciones a la Incertidumbre:  ¿Cómo evaluar la aplicabilidad de las condiciones de las reglas? Si X es mayor necesita gafas. ¿Se puede aplicar la regla si X tiene 40 años?  ¿Cómo combinar hechos imprecisos? X es alto, X es rubio. ¿Con que certidumbre puedo afirmar que X es alto y rubio?  Dado un hecho impreciso y una regla imprecisa: ¿qué confianza se puede tener en las conclusiones? X estudia mucho. Si X estudia mucho aprobará ¿Con que certidumbre puedo afirmar que X aprobará?  Dada la misma conclusión incierta de varias reglas: ¿qué confianza se puede tener en la conclusión? Juan llega tarde, Luis llega tarde. Si Juan llega tarde la carretera está cortada. Si Luis llega tarde la carretera está cortada. ¿Cuál es la certidumbre de que la carretera esté cortada? Inicialmente la mayoría de los investigadores en IA enfatizaban la importancia del razonamiento simbólico y evitaban la utilización de números. Los sistemas expertos no deben usar números puesto que los expertos humanos no lo hacen. Los expertos no pueden suministrar los números requeridos. Sin embargo, los ingenieros que

desarrollaban las aplicaciones se dieron cuenta pronto de la necesidad de representar la incertidumbre. El sistema experto MYCIN (años 70) para el tratamiento de infecciones bacterianas fue el primer éxito en este campo. Los métodos numéricos (especialmente los basados en probabilidad) son actualmente una herramienta aceptada en IA debido a los éxitos prácticos y a la complejidad de las teorías alternativas.

Manejo de la Incertidumbre. Se han desarrollado diversas técnicas para manejo de incertidumbre en sistemas inteligentes, que podemos dividir en dos grandes grupos:  Técnicas simbólicas (no numéricas).  Técnicas numéricas. Entre las técnicas simbólicas tenemos:  Lógicas no monotónicas. Como la LPO (Lógica de Primer Orden) asume que el conocimiento es completo y consistente, una vez que un hecho se asume/es cierto permanece así (Monotonía). Por ejemplo: si de una Base de Conocimiento (BC) se deduce una expresión “s”, y se tiene otra Base de conocimiento BC’ de forma que BC  BC’, entonces de BC’ también se deduce s. Por tanto el añadir nuevo conocimiento siempre incrementa el tamaño de la Base de Conocimiento. La presencia de conocimiento incompleto nos lleva a modelos no monótonos: El conocimiento de nuevos hechos puede hacer que nos retractemos de algunas de nuestras creencias. Ejemplo: Generalmente voy a la Universidad en bus. Veo en el periódico que hay huelga. Tengo que retractar que voy a la Universidad en bus.  Lógicas por defecto. Propuesta por Reiter para solucionar el problema del conocimiento incompleto (1980). Para ello se introducen una serie de reglas por defecto. Intuitivamente: “Las reglas por defecto expresan características comunes a un conjunto de elementos que se asumen ciertas salvo que se indique lo contrario”.  Lógicas basadas en modelos mínimos. Asunción del mundo cerrado: Sirve para manejar conocimiento incompleto. Intuitivamente: “Lo que no se puede probar a partir de mi Base de Conocimiento es falso”. Es utilizado en las bases de datos y Prolog. Inconvenientes: Teorías complejas y a veces inconsistentes. Entre las técnicas numéricas tenemos:  Modelos estadísticos-probabilísticos.  Modelo aproximado.  Modelo de lógica difusa

Algoritmo de Busqueda Tipos de algoritmos de búsqueda

Las técnicas de búsqueda son una serie de esquemas de representación del conocimiento, que mediante d de vista de la I.A. Elementos de la busqueda. • • • •

Conjunto de estados: todas las configuraciones posibles en el dominio. Estados iniciales: estados desde los que partimos. Estados finales: las soluciones del problema. Operadores: se aplican para pasar de un estado a otro.

BUSQUEDA CIEGA Sólo utiliza información acerca de si un estado es o no objetivo para guiar su proceso de búsqueda.

Expandir un nodo: obtener los posibles hijos de un nodo a partir de la aplicación de los distintos opera

Nodo cerrado: Se han aplicado todos los posibles operadores sobre él, obteniéndose todos sus posibles TIPOS DE BÚSQUEDA CIEGA    

Búsqueda en amplitud. Búsqueda en profundidad. Búsqueda en profundidad progresiva. Búsqueda bidireccional.

Búsqueda en amplitud Procedimientos de búsqueda nivel a nivel Para cada uno de los nodos de un nivel se aplican todos los posibles operadores No se expande ningún nodo de un nivel antes de haber expandido todos los del nivel anterior Se implementa con una estructura FIFO. Búsqueda en profundidad: La búsqueda se realiza por una sola rama del árbol hasta encontrar una solución o hasta que se tome la decisión de terminar la búsqueda por esa dirección. Terminar la búsqueda por una dirección se debe a no haber posibles operadores que aplicar sobre el nodo hoja o por haber alcanzado un nivel de profundidad muy grande. Si esto ocurre se produce una vuelta atrás (backtracking) y se sigue por otra rama hasta visitar todas las ramas del árbol si es necesario. Búsqueda bidireccional Se llevan a la vez dos búsquedas: una descendente desde el nodo inicial y otra ascendente desde el nodo meta.

Al menos una de estas dos búsquedas debe ser en anchura para que el recorrido ascendente y descendente pueda encontrarse en algún momento

http://www.udb.edu.sv/udb/archivo/guia/informatica-ingenieria/sistemas-expertos-einteligencia-artificial/2016/i/guia-7.pdf

http://www.cs.us.es/~fsancho/?e=33 https://sites.google.com/site/inteligenciascarol/algoritmo-de-busqueda