Parte V

Tiempo en el razonamiento probabilista

Tiempo e incertidumbre 

• En esta actividad combinaremos tiempo, incertidumbre, decisiones y acciones secuenciales, proyecciones de esas acciones, utilidades y multiagentes cooperando o no y con ello generando “emociones” que afectan al modo de tomar decisiones y así, a las utilidades.
• Tiempo: el mundo y el estado emocional cambian, hay que rastrear los cambios en intervalos discretos de tiempo.
• Incertidumbre: el panorama decisional no es claro.
• Acciones secuenciales: la tarea en el tiempo se desglosa en varias acciones encadenadas. Idea básica: copiar variables de estado y de evidencia para cada paso temporal.
• Proyecciones: cada acción tiene consecuencias temporales deseadas y no deseadas, denominadas “proyecciones de una acción”.
• Utilidades: la ristra de acciones nos hará más o menos felices.
• Comunicación de multiagentes: facilitando a las “emociones” habrá agentes cuyas señales las provoquen en otros agentes sensibles.
• “Emociones”: según cuáles sean, restringirán el subconjunto de acciones de un dado agente sensible a “emociones”.

Variables aleatorias

Una variable aleatoria booleana tendrá un dominio que sea verdad o falso. Para ser realmente un sistema probabilista, se debe reconocer en primer lugar la presencia de no menos de una variable aleatoria.

Para el mundo de la “mochila 1-0”, una variable aleatoria sería la capacidad C de la serie de mochilas disponibles. Cada uno de los 10 candidatos a meter dentro de la mochila elegida (de dudosa capacidad C) podrá estar (1) o no estar (0) en una dada selección. Aparecerá entonces un número “aleatorio” de 10 cifras binarias representando el contenido temporal de la mochila elegida.

Iconos de la red decisional

Nodos aleatorios: contienen variables probabilistas representando el estado del ambiente. 

Nodos decisionales: contienen posibles elecciones para una dada acción. 

Nodo de utilidad: contiene una función para calcular la utilidad basada en las variables probabilistas y en las decisiones.

El problema de la mochila

¿En que consiste?

• Tenemos n objetos y una mochila.
• Cada objeto tiene un peso wi y valor vi .
• La mochila tiene una capacidad de peso W.
• Elegir objetos de tal forma que no se sobrepase la capacidad de la mochila pero se maximize el valor total de los objetos.

¿Cuales pueden ser los enfoques de solución?

Hay tres variantes:

• Fuerza bruta.
• Greedy.
• Programación Dinámica.

Fuerza bruta: Probar todas las posibilidades. Un objeto puede ser añadido o restado a la mochila y sumar los pesos correspondientes para estar seguro de no sobrepasar la capacidad de carga W. Es un aproximación bastante mala 

Greedy: En cada iteración agregar el objeto con la relación Bi / Wi más alta. Ejemplo con W = 500 (Carga máxima).

La solución con el método greedy sería seleccionar traje de baño y los lentes para el sol con un beneficio total: 500.

Obviamente esta solución no es la óptima; pero también podríamos tomar la toalla y los lentes para el sol y obtener un beneficio total de 570. 

Programación dinámica:

Sea :

• W: capacidad máxima de la mochila
• G(W): beneficio máximo que se obtiene de una mochila de capacidad W
• Bj: beneficio obtenido por un artículo único de tipo j
• Wj: el peso de un solo artículo del tipo j.

Donde:

• Resulta obvio que G(0) = 0 para W > 0
• G(W) = MAX j{ Bj + G(W - Wj) } (1)
• Donde j es un tipo de artículo, se debe cumplir además que Wj = W
• X(W) es cualquier tipo de artículo que alcanza el máximo en la ecuación (1)

Obtener todas las posibles G(Wj); donde Wj es un entero tal que Wj = W; y j es un tipo de artículo

G(W) = MAX j{ Bj + G(W - Wj) }

Una vez que se obtienen las soluciones anteriores, se obtiene G(W – Wj ) sucesivamente hasta que W-Wj = 0 o
W –Wj es menor que el peso de cualquier artículo.

Ejemplo: Suponga que se ha de llenar una mochila de 10 kilos con los artículos que aparecen en la tabla que se muestra abajo. Para maximizar el beneficio total ¿Cómo se debe llenar la mochila? 

• G(0) = G(1) = G(2) = 0 Ningún artículo cabe en una mochila de 0, 1 o 2 Kg
• X(0) = X(1) = X(2) = 0
• G(3) = 7 y X(3) = 2 Solo cabe un artículo 2 en una mochila de 3 Kg
• G(4) = MAX 11 + G(0) = 11 Artículo tipo 1 (4 Kg)
  • 7 + G(1) = 7 Artículo tipo 2 (3 Kg)
  • Por tanto G(4) = 11 y X(4) = 1
• G(5) = MAX 11 + G(1) = 11 Artículo tipo 1 (4 kg) 
  • 7 + G(2) = 7 Artículo tipo 2 (3 kg)
  • 12 + G(0) = 12 Artículo tipo 3 (5 kg) 
  • Por tanto G(5) = 12 y X(5) = 3
• G(6) = MAX 11 + G(2) = 11 Artículo tipo 1 (4 Kg)
  • 7 + G(3) = 14 Artículo tipo 2 (3 Kg)
  • 12 + G(1) = 12 Artículo tipo 3 (5 Kg)
  • Por tanto G(6) = 14 y X(6) = 2
• G(7) = MAX 11 + G(3) = 18 Artículo tipo 1 (4 Kg) 
  • 7 + G(4) = 18 Artículo tipo 2 (3 Kg)
  • 12 + G(2) = 12 Artículo tipo 3 (5 Kg)
  • Por tanto G(7) = 18 y X(7) = 1 o X(7) = 2
• G(8) = MAX 11 + G(4) = 22 Artículo tipo 1 (4 kg) 
  • 7 + G(5) = 19 Artículo tipo 2 (3 kg)
  • 12 + G(3) = 19 Artículo tipo 3 (5 kg)
  • Por tanto G(8) = 22 y X(8) = 1
• G(9) = MAX 11 + G(5) = 23 Artículo tipo 1 (4 kg) 
  • 7 + G(6) = 21 Artículo tipo 2 (3 kg)
  • 12 + G(4) = 23 Artículo tipo 3 (5 kg)
  • Por tanto G(9) = 23 y X(9) = 1 o X(9) = 3 
• G(10) = MAX 11 + G(6) = 25 Artículo tipo 1 (4 kg)
  • 7 + G(7) = 25 Artículo tipo 2 (3 kg)
  • 12 + G(5) = 24 Artículo tipo 3 (5 kg)
  • Por tanto G(10) = 25 y X(10) = 1 o X(10) = 2 

Existen 2 soluciones de X(10):

• Colocando inicialmente un artículo del tipo 1 tenemos una ganancia de 11 Pesos con 4 Kg mochila. Quedan por llenar (10-4) = 6 Kg de la mochila.
• Colocando a continuación un artículo tipo 2 tenemos una ganancia de 11 + 7 = 18 Pesos con 7 Kg en la mochila. Quedan por llenar (6-3)=3 Kg de la mochila.
• Colocando a continuación un artículo tipo 2 tenemos una ganancia de 18 + 7 = 25 Pesos con 10 Kg en la mochila.
  Quedan por llenar (3 - 3)=0 Kg de la mochila. Está llena.

En resumen: Se alcanza el beneficio máximo G(10) = 25 llenando la mochila con 2 artículos tipo 2 y uno tipo1.

Importancia del problema:

• Permite representar una gran cantidad de problemas reales.
• Es un buen ejemplo para tomarlo como material didáctico para adentrarse a la complejidad de problemas entre NP y P.
• Es muy usado en la programación de enteros (Programación entera).

Papel de las emociones

Las nociones de emociones y de sensaciones pueden ser formalizadas y hechas útiles en diseño de agentes inteligentes artificiales que deben obrar en ambientes inciertos, complejos, a veces poblados por agentes y humanos.

Formalización, diseño racional del agente decisión – teórico, esto es, dicho agente actúa para maximizar la expectativa de su medida de desempeño. Este modelo de decisión-teórico de la toma de decisión se puede adaptar para definir formalmente los estados emocionales y las sensaciones de un agente racional.

Definiciones demuestran cómo los estados emocionales transforman la situación de la toma de decisión del agente, p. ej.: haciéndolo más miope, alterando la medida de desempeño subjetiva del agente, o modificando las probabilidades asignadas por el agente a los estados del mundo.

Así, las emociones pueden ser útiles para un agente racional:

1. Modificando el modelo decisión-teórico usado para la racionalidad deliberativa, las emociones permiten que el agente controle la asignación “anytime” de sus recursos cognoscitivos y la complejidad de sus deliberaciones, bajo presión del tiempo y en un ambiente incierto. P. ej.: limitando el número de los comportamientos alternativos considerados, o acortando el lapso de tiempo para una toma de decisión más rápida.

2. Las emociones y las sensaciones resultan tener para informar al otro agente sobre su propio estado interno. En vez de tener que describir los detalles de su estado interno, el agente puede utilizar términos más abstractos y más universales. Por ejemplo, las nociones de tensión o de pánico pueden ser convenientes para urgir a que el otro agente considere solamente efectos a corto plazo de sus acciones. Así, en el contexto de la comunicación con otros agentes, las definiciones formales de emociones sirven como semántica de términos emocionales, con los cuales los agentes pueden expresar sus propios estados internos y entender los estados en que están otros agentes.

3. Los estados emocionales bien definidos de uno mismo y de otros son cruciales en la interacción del agente con seres humanos. Con frecuencia, la interacción humano - agente resulta muy afectada porque la máquina no aprecia el estado emocional del humano. Pero el estado emocional de los usuarios se puede determinar usando factores mensurables. Es importante que la máquina modele y prediga el efecto que el estado emocional del humano tiene sobre la toma de decisión y la actuación de éste.

Cadenas de Markov

Un agente debe tomar con frecuencia una decisión bajo incertidumbre sobre muchos acontecimientos futuros. Los procesos estocásticos se adecuan a un modelo probabilista para los acontecimientos que se desarrollan en un cierto plazo. Un proceso estocástico suele estar determinado como cadena de Markov. En este modelo la incertidumbre futura depende solamente del estado actual y no de la historia del proceso hasta el presente. Se utiliza los Procesos de Decisión Markovianos (MDP) para modelizar las búsquedas en dominios estocásticos.

El "problema de la mochila" es un ejemplo de un problema de toma de decisión que se puede modelar por una cadena de Markov.

Una cadena de Markov es una serie de eventos, en la cual la probabilidad de que ocurra un evento depende del evento inmediato anterior. En efecto, las cadenas de este tipo tienen memoria. " Recuerdan" el último evento y esto condiciona las posibilidades de los eventos futuros. Esta suposición de Markov afirma la dependencia de un evento y distingue a las cadenas de Markov de las series de eventos como la de revolear monedas – series independientes.

En la figura se muestra el proceso para formular una cadena de Markov. El generador de Markov produce uno de n eventos posibles, Ej , donde j = 1, 2, . . . , n, a intervalos discretos de tiempo (que no siempre son iguales ). Las probabilidades de ocurrencia para cada uno de estos eventos depende del estado del generador. Este estado se describe por el último evento generado. Si el último evento generado fue Ej , entonces el generador se encuentra en el estado Mj.

La probabilidad de que Ek sea el siguiente evento generado es una probabilidad condicional : P ( Ek| Mj ). Esto se llama probabilidad de transición del estado Mj al estado Ek. Para describir completamente una cadena de Markov es necesario saber el estado actual y todas las probabilidades de transición.

Probabilidades de transición

Una forma de describir una cadena de Markov es con un diagrama que se muestra - Diagrama de Estados - donde se ve un sistema de Markov con cuatro estados posibles : M1, M2 , M3 y M4 . La probabilidad condicional o de transición de moverse de un estado a otro se indica en el diagrama.