Download - Clase 2
Resolver problemas medianteInteligencia Artificial
Universidad de Boyacá
Resolución de problemas Se quiere:
Resolver automáticamente un problema
Se necesita: Una representación del problema Algoritmos que usen alguna estrategia para
resolver el problema definido en esa representación
Definición de un problema Si se abstraen los elementos de un problema
se pueden identificar: Un punto de partida Un objetivo a alcanzar Acciones a disposición para resolver el
problema Restricciones sobre el objetivo (p.e., que se
quire) Elementos del dominio que son relevantes en
el problema (p.e., conocimiento incompleto del punto de partida)
Representación de problemas Existen diferentes formas de representar
problemas para resolverlos de manera automática
Representaciones generales: Espacio de estados. Un problema se divide en
un conjunto de pasos de resolución desde el inicio hasta el objetivo.
Reducción a sub-problemas. Un problema se descompone en una jerarquía de sub-problemas.
Representaciones para problemas específicos:
Resolución de juegos Satisfacción de restricciones
Representación de problemas: estados Se puede definir un problema por los elementos
que intervienen y sus relaciones. En cada instante de la resolución de un
problema esos elementos tendrán unas características y relaciones específicas.
Se denomina estado a la representación de los elementos que describen el problema en un momento dado.
Se distinguen dos estados especiales: el estado inicial (punto de partida) y el estado final (en general, el objetivo del problema).
¿Qué descriptores incluir en el estado? (Ej.: la localización)
Modificación del estado: función sucesor Para poder moverse entre los diferentes
estados se necesita una función sucesor (descripción de las posibles acciones).
� Función sucesor (o conjunto de operadores): función de transformación sobre la representación de un estado que lo convierte en otro estado
La función sucesor define una relación de accesibilidad entre estados.
Representación de la función sucesor: Condiciones de aplicabilidad Función de transformación
Espacio de estados El conjunto de todos los estados
alcanzables desde el estado inicial conforma lo que se denomina espacio de estados.
Representa todos los caminos que hay entre todos los estados posibles de un problema.
El espacio de estados forma un grafo (o mapa) en el cual los nodos son estados y los arcos son acciones.
La solución del problema está dentro de ese mapa.
Solución de un problema en el espacio de estados� Solución: Secuencia de pasos que llevan del estado inicial al final (secuencia de operadores) o también el estado final� Tipos de solución: una cualquiera, la mejor, todas� Costo de una solución: gasto en recursos de la aplicación de los operadores a los estados; puede ser importante o no según el problema y qué tipo de solución busquemos
Descripción de un problema en el espacio de estados Definir el espacio de estados (explícita o
implícitamente) Especificar el estado inicial Especificar el estado final o las condiciones
que cumple Especificar los operadores de cambio de
estado (condiciones de aplicabilidad y función de transformación)
Especificar el tipo de solución: La secuencia de operadores o el estado final Una solución cualquiera, la mejor (definición
de costo), todas �
Ejemplos: puzzle Espacio de estados:
configuraciones de 8 fichas en el tablero Estado inicial:
cualquier configuración Estado final:
fichas en orden específico Acción:
�mover hueco� Condiciones:
el movimiento está dentro del tablero Transformación:
�mover el hueco� a la Izquierda, Derecha, Arriba y Abajo
Solución: Qué pasos + El menor número
8
2 3
4
1
6
7
5
Ejemplo: n reinasn = 4 n = 8
Ejemplo: n reinas Estado inicial:
configuración sin reinas en el tablero Espacio de estados:
configuraciones de 0 a n reinas en el tablero con sólo una por fila y columna
Estado final: configuración en la que ninguna reina se mata entre sí
Operadores: colocar una reina en una fila y columna
Condiciones: la reina no es matada por ninguna ya colocada
Transformación: colocar una reina más en el tablero en una fila y columna
determinada
Solución: Las reinas ubicadas, pero no importan los pasos
Problema de las jarras de agua
Se tienen dos jarras de agua, una de 4litros y otra de 3litros sin escala de medición. Se desea tener 2 litros de agua en la jarra de 4 litros. Las siguientes operaciones son válidas: llenar las jarras, tirar agua de las jarras, pasar agua de una jarra a otra.
13
El espacio de estados se define como: { (X,Y)/ X son los litros en la jarra de 4l con 0<=X<=4 AND
Y son los litros de la jarra de 3l con 0<=Y<=3 }
14
Conclusión del ejemplo de las tres jarras:
15
Problema de los Caníbales y Monjes Se tienen 3 monjes y 3 caníbales en el margen
Oeste de un río. Existe una canoa con capacidad para dos personas como máximo. Se desea que los seis pasen al margen Este del río, pero hay que considerar que no debe haber más caníbales que monjes en ningún sitio porque entonces los caníbales se comen a los monjes. Además, la canoa siempre debe ser conducida por alguien.
Realice la misma construcción de acuerdo a la solución de las tres jarras.
16
Búsqueda en el espacio de estados Se define una representación del espacio
de estados para poder implementar algoritmos que busquen soluciones.
La resolución de un problema con esta representación pasa por explorar el espacio de estados.
Se empieza del estado inicial y se evalúa cada paso hasta encontrar un estado final.
En el caso peor se exploran todos los posibles caminos entre el estado inicial del problema y el estado final.
Estructura del espacio de estados Estructuras de datos: árboles y grafos Estados = nodos Operadores = arcos entre nodos (dirigidos) Árboles: sólo un camino lleva a un nodo Grafos: varios caminos pueden llevar a un
nodo
Resolución de problemas de IA Para construir un sistema que resuelva un sistema específico, es necesario:
1- Definir el problema formalmente con precisión.
2- Analizar el problema. 3- Representar el conocimiento necesario para resolver el problema.
4- Elegir la mejor técnica que resuelva el problema y aplicarla.
19
1. Definición formal del problema.
20
El primer paso para diseñar un programa que resuelva un problema es crear una descripción formal y manejable del propio problema. Sería adecuado contar con programas que produzcan descripciones formales a partir de descripciones informales, proceso denominado operacionalización. Dado que por ahora no se conoce la forma de construir estos programas este proceso debe hacerse manualmente.
Hay problemas que por ser artificiales y estructurados son fáciles de especificar (por ej. el ajedrez, el problema de las jarras de agua, etc. ). Otros problemas naturales, como por ej. la comprensión del lenguaje, no son tan sencillos de especificar.
Para producir una especificación formal de un problema se deben definir: �espacio de estados válidos; �estado inicial del problema; �estado objetivo o final; �reglas que se pueden aplicar para pasar de un estado a otro.
21
Un estado es la representación de un problema en un instante dado.Para definir el espacio de estados no es necesario hacer unaenumeración exhaustiva de todos los estado válidos, sino que esposible definirlo de manera más general.
El estado inicial consiste en uno o varios estados en los que puedecomenzar el problema.
El estado objetivo consiste en uno o varios estados finales que seconsideran solución aceptable.
Las reglas describen las acciones u operadores que posibilitan unpasaje de estados. Una regla tiene una parte izquierda y una partederecha. La parte izquierda determina la aplicabilidad de la regla, esdecir, describe los estados a los que puede aplicarse la regla. La partederecha describe la operación que se lleva a cabo si se aplica la regla,es decir, como obtener el estado sucesor.
La representación como espacio de estados formaparte de la mayoría de los métodos de IA. Suestructura se corresponde con la resolución deproblemas porque: Permite definir formalmente el problema, mediante
la necesidad de convertir una situación dada en unasituación deseada mediante un conjunto deoperaciones permitidas.
Permite definir el proceso de resolución de unproblema como una combinación de técnicasconocidas y búsqueda (la técnica general deexploración del espacio intenta encontrar algunaruta desde el estado actual hasta un estadoobjetivo).
22
2. Estrategia de control: Métodos de búsqueda El problema puede resolverse con el uso de reglas
en combinación con una estrategia de controlpara trasladarse a través del espacio de estadoshasta encontrar un camino desde el estado inicialhasta el estado final. Se elige una regla entreaquellas cuya parte izquierda concuerda con elestado actual. Se aplica la regla elegidarealizando el cambio de estado tal como sedescribe en la parte derecha de la regla. Si elnuevo estado es estado objetivo o final se haencontrado la solución. En caso contrario secontinúa con la aplicación de reglas al nuevoestado.
23
24
Una estrategia de control especifica el orden en el que se deben aplicar lasreglas, así como también la forma de resolver conflictos cuando es posibleaplicar más de una regla. Para que una estrategia de control sea válida debecumplir con dos requisitos:
� Causar cambios:las estrategias de control que no causan cambios de estado nunca alcanzan lasolución. Un ejemplo de estrategia de control que no causa cambios esseleccionar siempre la primera regla aplicable de la lista de reglas definidas. Enel ejemplo de las jarras de agua, se continuaría indefinidamente aplicando lasreglas 1 y 3 sin posibilidad de arribar a la solución.
� Ser sistemática:las estrategias de control que no son sistemáticas pueden utilizar secuencias deoperaciones no apropiadas varias veces hasta alcanzar la solución. Un ejemplode estrategia de control no sistemática es seleccionar la regla a aplicar al azar.Esta estrategia puede encontrar la solución eventualmente, pero luego de haberrealizado varios pasos innecesarios e incluso haber vuelto varias veces al mismoestado.
Algunos ejemplos de estrategias de control sistemáticas Los siguientes algoritmos de búsqueda
detallados a continuación son ejemplos deestrategias de control sistemáticas.
Todos se basan en considerar un árbol deestados cuya raíz es el estado inicial, y encada nivel se hallan los estados sucesorescorrespondientes. Búsqueda Breadth-First Search (primeroen ancho)
Búsqueda Depth-First Search (primero enprofundidad)
25
3. Análisis del problema
26
Luego de definir el problema formalmente, el segundo paso en laresolución del problema es el análisis del mismo. A fin de poder elegir elmétodo más apropiado para resolver un problema particular, es necesarioanalizar distintas cuestiones que afectan a al definición del mismo y a lascaracterísticas de la solución deseada. Existen varias preguntas aresponder acerca del problema:
1. ¿Puede descomponerse el problema en subproblemas máspequeños?
2. ¿Pueden deshacerse pasos inadecuados hacia la solución?3. ¿Es predecible el universo del problema?4. ¿Una solución es buena de manera absoluta o relativa?5. ¿La solución deseada es un estado o la ruta hacia un estado?6. ¿El conocimiento se necesita para resolver el problema o para
restringir la búsqueda de la solución?7. El programa que soluciona el problema ¿busca la solución solo o
necesita interactuar con una persona?
Webgrafia
www.lsi.upc.es/~luigi/II/IA-2008-spring/3c-representacion-del-conocimiento-(es).ppt
www.lsi.upc.es/~luigi/II/IA-2008-spring/4a-introduccion-a-los-sistemas-basados-en-el-conocimiento-(es).ppt
27