Módulo 2 - Lectura 1 - Apuntes 1 PDF

Preview

Summary

Lectura 1 - Modulo 2 Canvas...

Description

Algoritmos de búsqueda: búsqueda no informada

Variantes en los agentes reactivos

Buscando la aptitud para resolver problemas

El concepto de problema

Búsqueda en el espacio de estados

Métodos de búsqueda exhaustiva en el espacio de estados

Referencias

Lección 1 de 6

Variantes en los agentes reactivos

Actividades

Resolver problemas de búsqueda en el espacio de estados a través de métodos exhaustivos y heurísticos. Reconocer las formas de representar el conocimiento y los métodos de razonamiento.

Como se recordará, para orientar el estudio de la inteligencia artificial (AI), se recurrió a la metáfora de agentes, a los que se interpreta como “entidades racionales que funcionan en forma continua y autónoma, en ambientes en que interactúan con otras entidades” (Russell y Norvig, 2004). Esta construcción abstracta facilita la asignación de cualidades, con la finalidad de cubrir un espectro de casos que representen entidades asociables a niveles, en una cierta escala de conductas inteligentes. Así es que Russell y Norvig (2004) propuso una escala de cinco niveles de agentes y Nilsson (2001) propuso otra, una de cuatro niveles (las dos escalas fueron descriptas en la lectura 4 de la unidad 1).

En ambas clasificaciones, hay coincidencia en el primer nivel, que corresponde a los llamados agentes reactivos, de estímulo-respuesta (ER) o de reflejo simple. Estos agentes no son capaces de ninguna acción espontánea y su conducta queda, exclusivamente, determinada por su entorno. Es decir, sus acciones son una consecuencia directa de los estímulos percibidos en el ambiente donde operan y, a pesar de su simplicidad, debe reconocerse que, a partir de este tipo de comportamiento, se puede concebir una gran variedad de dispositivos. Incluso, en muchas oportunidades, quizás más de las deseables, los seres humanos se comportan como agentes reactivos. Puede citarse como ejemplo el caso del conductor de automóvil que aplica rápidamente su pie sobre el pedal del freno cuando advierte, a cierta distancia, algún obstáculo.

Pero es necesario distinguir entre la acción refleja elemental, recién citada, y la acción decidida a partir de la evaluación de otros factores. Entre estos, pueden encontrarse registros históricos de la percepción del medio (mediante sensores) y de conductas anteriores del propio agente, lo que representa información sobre la actividad cumplida y disponible para ser consultada posteriormente. En ese caso, el agente definirá su respuesta a partir de la realidad de entonces y la de los registros anteriores de desempeños similares. Por ejemplo, puede citarse el caso de una unidad de control de temperatura, donde se regula la válvula de gas no solo a partir de la temperatura actual, sino, también, considerando registros históricos de regulaciones y resultados previos. Conociendo gradientes térmicos que resultan de la evolución de la señal de entrada, se pueden prever respuestas más complejas y obtener conductas más estables. Debe notarse que memorizar una conducta anterior implica adoptar la forma de una

máquina de estados, donde el agente responde según el estímulo exterior y el estado en que se encuentra como consecuencia de su historia.

Es interesante comprobar que, en este caso, en que, en su conducta, el Agente considera la percepción actual y sus antecedentes, ya no hay coincidencia entre las propuestas de Russell y Norvig (2004) y Nilsson (2001). Para el primero, se trata de un segundo nivel, denominado agentes reactivos basados en modelos y, para el segundo, sigue siendo un agente de estímulo respuesta, es decir, de nivel 1.

C O NT I N U A R

Lección 2 de 6

Buscando la aptitud para resolver problemas

Dando un paso más en esta metáfora, se van a considerar agentes capaces de buscar e identificar secuencias de acciones que los conduzcan a alcanzar las condiciones deseadas, denominadas metas u objetivos. Para Russell y Norvig (2004), se está ante agentes basados en objetivos (nivel 3) y, para Nilsson (2001), ante agentes planificadores (nivel 2). Cabe aclarar que, al confrontar ambas clasificaciones, se está buscando entender mejor las cualidades de los agentes y sus consecuencias, quedando, en un segundo plano, la posible ventaja que ofrezca alguna de ellas.

Según lo expuesto, es fácil advertir que, al diseñarse una máquina reactiva, se deben anticipar las reacciones apropiadas para todas las posibles situaciones que enfrentará el agente, lo que es, en muchos casos, impracticable. O visto desde otro ángulo, el desempeño del agente queda muy acotado y condicionado a ciertos escenarios prestablecidos. Y aun, en el caso de que tal diseño fuese posible, el almacenamiento de la información necesaria para posibilitar el desarrollo de tareas relativamente complejas demandaría grandes espacios de memoria y elevados tiempos de consulta. 

La opción para superar estas limitaciones es procurar un agente que incorpore conductas adaptables al medio, que no requieran un diseño explícito anticipado. También, esto implica reducir el volumen de tablas y reglas que deben ser predefinidas y almacenadas, a cambio de incorporar la capacidad de realizar procesos, los que tendrán la finalidad de seleccionar y respaldar las acciones que, en cada caso, tome el agente. Y estas expectativas son las que conducen a los ya citados niveles 3 de Russell y Norvig (2004) y 2 de Nilsson (2001). El primero identifica, en este nivel, un agente específico para resolver problemas, que denomina agentes resuelve problemas (problema solver), mientras que el segundo los denomina genéricamente agentes planificadores. Ambos agentes disponen de la capacidad analítica necesaria para anticipar los efectos de sus acciones, lo que les permite seleccionar sus conductas entre aquellas que son, aparentemente, más apropiadas para alcanzar sus objetivos.

En resumen, no existe, ahora, una relación directa entre entrada y salida, entre estímulo y respuesta. Por el contrario, hay una respuesta que es elaborada a partir de un proceso exploratorio, de búsqueda, cuya determinación constituye la solución de un problema. Por este motivo, queda encuadrado en un marco de actividad planificada. En la implementación de estos agentes, deben considerarse las variantes que puede presentar el comportamiento del dominio que constituye su medio ambiente. Estas son:

1

dominio estático: sólo afectado por las acciones del propio agente;

2

dominio dinámico: se presentan condiciones externas que muestran una variación en el tiempo y son ajenas al agente;

3

dominio interactivo: hay presencia de otros agentes que comparten el mismo medio y tienen sus propios objetivos; y

4

dominio competitivo: la actividad habitual enfrenta uno o más agentes que se constituyen en rivales en pugna por los mismos objetivos.

El tiempo disponible para definir la respuesta del agente está limitado en los dominios que no son estáticos. Esto es debido a que, mientras se evalúan las alternativas, transcurre el tiempo y cambian las condiciones. Por otra parte, en los dominios interactivos, deben contemplarse las acciones de otros agentes, ya que se constituyen eventuales aliados o rivales que persiguen un objetivo común. Este último caso corresponde a dominios competitivos que requieren la exploración de situaciones idealizadas, en las que alternativamente deben considerarse todas las posibles acciones de los agentes contrincantes.

La figura 1 muestra un esquema que presenta la arquitectura de un agente planificador.

Figura 1: Esquema de un agente planificador

Fuente: elaboración propia.

C O NT I N U A R

Lección 3 de 6

El concepto de problema

Enfrentar un problema significa que se desea alcanzar cierto objetivo, se conocen las acciones disponibles, pero no se sabe cuáles son las apropiadas para conseguirlo. Normalmente el problema se manifiesta ante la existencia de alternativas para alcanzar el objetivo y el desconocimiento de cuáles y en qué orden deben ser invocadas. La decisión que se tome, seguramente, influirá en la efectividad y en la eficiencia de la solución elegida. En resumen, la existencia de un problema queda determinada por los siguientes tres componentes:

1

una situación o dificultad inicial;

2

un objetivo o meta a alcanzar; y

3

un conjunto de acciones posibles, capaces de conducir a soluciones alternativas.

El objetivo puede estar representado por algo tangible, como un objetivo físico, o algo eminentemente abstracto, como la demostración de un teorema. Por lo tanto, las acciones conducentes al objetivo serán, en algunos casos, actividades físicas y, en otros, razonamientos o actividades puramente mentales.

En la inteligencia artificial, a los problemas, se los representa como un espacio de estados, que constituyen la base de la mayoría de los métodos de resolución. Tales métodos se distinguen por las siguientes dos características:

1

permiten expresar formalmente un problema y

2

posibilitan la definición del proceso de resolución de manera sistemática.

En esta interpretación, un problema es reconocido como la necesidad de convertir alguna situación inicial dada en otra situación deseada, usando, para ello, un conjunto de operaciones permitidas. Se define, entonces, formalmente, un problema como una terna:

P =( I,O,M )

Donde:

I: el estado o situación inicial en el dominio del problema; O: conjunto de todos los operadores o acciones disponibles, que puedan ser aplicadas a las instancias del espacio de estados; y M: la meta, el estado, cuya condición caracteriza la situación final o estado objetivo.

La presentación formal del problema lleva a la definición de numerosos conceptos, que son enunciados a continuación.

Acción: se denomina así al resultado de aplicar cierto operador Ok a una expresión. En caso de poder aplicarse un operador a más de una expresión, queda definida una clase de acciones. Requisitos y consecuencias: toda acción disponible tiene definidas las condiciones que deben cumplir los operadores para poder ser aplicados en el estado actual y sus consecuencias, las que darán lugar a un nuevo estado. Sucesor: se dice que el estado K es sucesor del estado J, si es alcanzable a partir de J, mediante la aplicación de alguna secuencia de acciones. En caso de que K pueda ser alcanzado con una única acción, se dice que es sucesor inmediato de J o, también, que J genera a K.

Figura 2: Sucesor

Fuente: elaboración propia.

Espacio de búsqueda o espacio de estados: es el conjunto de todos los estados que pueden ser alcanzados desde el estado, inicial aplicando los operadores disponibles. Solución de un problema: es la secuencia ordenada de operadores que, como resultado de su aplicación al estado inicial I, satisface la condición M. La inexistencia de tal secuencia de operadores prueba que un problema no tiene solución. Por el contrario, si la secuencia de operadores es un conjunto vacío, significa que el problema ya está resuelto. Objetivo: ante un problema, es factible que se requiera alguna de estas tres opciones: 

1. una solución, 2. todas las posibles soluciones, o 3. la solución óptima.

Estado final: es obtenido a partir de una solución que, como ya se dijo, estará formada por la secuencia ordenada de operadores intervinientes. Estado inicial: debe disponer de la información apropiada que define el problema. Algunos de sus elementos permanecerán invariantes durante la solución y son reconocidos como hechos. Otros cambiarán conforme progrese la aplicación de los operadores y son reconocidos como condiciones iniciales. Dependiendo de cada caso, la representación de los estados podrá tomar desde formas muy simples (vectores de estados) hasta otras muy complejas. Condición de la solución: el grado de especificación con que se define el objetivo de un problema puede ser variable, lo que permite distinguir entre dos tipos de casos:

1. completamente especificados: por lo general se trata de demostraciones; Y 2. incompletamente especificados: normalmente se trata de búsquedas.

La condición que debe cumplirse en la solución es formulada como una propiedad que debe ser satisfecha en cierto estado y es independiente de la distinción anterior. Tipos de objetivos: es necesario reconocer que, en la solución de un problema, puede presentarse alguno de los tres objetivos diferentes que siguen:

1. hallar la solución del problema, lo que significa identificar un estado final; 2. hallar la forma de resolver el problema cuyo estado final es conocido, es decir, encontrar la

secuencia de operadores apropiada; o 3. alguna combinación de los anteriores.

C O NT I N U A R

Lección 4 de 6

Búsqueda en el espacio de estados

Debe tenerse en cuenta que el esfuerzo requerido para resolver un problema es definitivamente dependiente de la forma en que este es representado. Los espacios de estados pueden ser substancialmente reducidos, empleando representaciones que restrinjan la información representada. Esto a través de la combinación de ciertos operadores, para dar lugar a otros más poderosos o, en ciertos casos, optando por descartarlos. También, un cierto problema puede ser llevado a la forma de otro equivalente para aprovechar una representación más apropiada.

Esto significa que pueden admitirse múltiples representaciones de un mismo problema, todas ellas equivalentes entre sí. Las representaciones equivalentes de un problema original podrían ser reconocidas como modelos, cuya condición es rescatar sus características esenciales. Al trabajarse en la búsqueda de un modelo o representación equivalente de un problema, deben ser tenidas en cuenta las siguientes cinco condiciones:

1

claridad: relación inmediata entre el modelo y el problema real;

2

completitud: preservación de todos los aspectos esenciales del problema real;

3

concisión: omisión de características irrelevantes, redundantes e implícitas;

4

exactitud: formulación precisa y fiel representación de la realidad. Clara definición de sus límites de aplicación; y

5

utilidad:representación conveniente que facilite la resolución del problema.

Algunos autores resumen las condiciones de completitud y concisión en estrictez: que implica que todo buen modelo debe ser tan completo como sea necesario y tan simple como sea posible.

Una vez representado el problema, las operaciones constituyen transformaciones que son sucesivamente aplicadas y van alterando el estado del modelo, hasta alcanzar el estado final, el que debe satisfacer las condiciones establecidas para la solución.

La solución fue definida como una secuencia ordenada de operaciones. Debido a que las acciones no pueden ser aplicadas en cualquier momento, cada acción debe respetar ciertos prerrequisitos establecidos como precondiciones. Esto conduce a la necesidad de definir reglas que establecen las condiciones que deben ser

satisfechas, para que cada una de las acciones sean aplicables. Luego, las transformaciones que provocan la aplicación de estas reglas impactan en el vector del estado y deben ser vistas como sus consecuencias.

Para que el proceso de resolución de un problema sea correcto, la formulación del conjunto de reglas que representan todas las acciones disponibles debe reunir, también, ciertas características esenciales:

1

precisión: toda propuesta de acción debe estar especificada sin ambigüedad y su validez claramente delimitada;

2

consistencia: ningún subconjunto de reglas determinará que una acción es aplicable mientras que, simultáneamente, otro subconjunto determina lo contrario para esa misma acción;

3

completitud: todas las acciones permitidas en el dominio del problema deben estar especificadas; e

4

independencia: una regla no debe referenciar otras reglas, ya que solo se aplican a la estructura de representación usada.

Resumiendo, la descripción formal de un problema implica:

representar apropiadamente al problema y definir su espacio de estados; identificar un estado que describa la situación inicial; especificar uno o más estados como objetivos, los que representan soluciones aceptables; y especificar un conjunto de reglas que describan las acciones disponibles.

Tal como la búsqueda de la solución de un problema ha sido planteada, está lo que se denomina un sistema de producción, cuyos componentes son:

un conjunto finito, no vacío, de reglas; el conocimiento sobre el entorno: su espacio de estados; a estrategia de control o criterios de selección de las reglas; y el aplicador de las reglas.

La estrategia de control es el elemento determinante para que un agente alcance sus objetivos. Y, en el caso de los agentes planificadores, a la posibilidad de resolver un problema, debe sumarse la rapidez con que se hace. Esto último es determinante, debido a que la estrategia de selección de las reglas incluye un proceso de exploración o búsqueda del camino apropiado, que demanda tiempo.

Ahora una necesaria aclaración: es habitual, en inteligencia artificial, remitirse a juegos, para demostrar la conveniencia de una técnica, comprobar su eficacia e identificar sus limitaciones. Los juegos representan escenarios apropiados para confirmar aptitudes y evaluar desempeños, este último es representado por el tiempo y espacio demandado.

Ejemplo Se tienen dos jarras, una de ellas de cuatro litros de capacidad y la otra de tres. Ninguna de ellas tiene una marcación que permita reconocer el volumen del contenido y se dispone de un dispositivo que permite llenar las jarras, vaciarlas o trasvasar líquido de una a la otra. Se desea definir un procedimiento que asegure un volumen de dos litros en la jarra de cuatro litros de capacidad.

Representación del problema El problema es representado por un par ordenado (x, y) que considera el contenido de la jarra grande (x) y de la chica chica (y), respectivamente. El espacio de estados queda, entonces, definido por todos los diferentes vectores (x, y), donde se adoptan variables reales para representar apropiadamente los llenados x e y.

Espacio de estados La representación de este espacio de estados es una superficie continua, ya que está constituido por infinitos vectores que corresponden a todas las posibles combinaciones, donde 0 ≤ x ≤ 4 y 0 ≤ y ≤ 3. Entre estas, se encuentran los estados inicial y final, como se observa en la figura 3.

Figura 3: Estado de espacios

Fuente: elaboración propia.

Si por simplicidad se asume que x e y solo toman valores enteros, el espacio de estados se convierte en discreto. En este caso, se distinguen veinte condiciones diferentes, que son representadas en la figura correspondiente. Para facilitar la interpretación de esta forma de representar un problema, se representa, en ambos modelos, el estado inicial (I) y la meta (M). Se sugiere al lector comprender la posición asignada a ambos estados extremos en el modelo discreto y los casos en que las metas fueran el estado N (2,3) y Q (4,1).

Conjunto de reglas disponibles El conjunto de acciones posibles, para operar con las jarras, es especificado en forma de reglas y representadas en una tabla que detalla el significado de cada regla, la condición a cumplir por el vector de estado para poder aplicarse y la consecuencia de cada acción o regla en el vector de estado. Al estar claramente definidas las condiciones y las consecuencias, la posibilidad de resolver el probl...