Defina con sus palabras lo que entiende por inteligencia artificial e indique con cuál de los enfoques históricos estaría más relacionada su definición.

«Inteligencia Artificial» es la disciplina de la computación que construye y busca entender software inteligente, el cual debe seguir un modelo PEAS: agente -racional-, medidas de rendimiento, ambiente, actuador, sensor. No nos interesa los estados internos de estos agentes para compararlo con otros agentes naturales como los seres humanos u otros animales, nos interesa en cambio sus resultados.

Con estados internos nos referimos a los algoritmos -máquinas de Turing que dadas entradas válidas eventualmente termina-, procedimientos -máquinas de Turing que dadas entradas válidas no sabemos si termina- o datos del software.

El agente racionales es un agente que actúa autónomamente con la consigna de lograr la mejor decisión posible según sus circustancias: medida de rendimiento, ambiente, actuador, sensor.

Este enfoque históricamente es conocido como «actuando racionalmente».

Seleccione una de las objeciones que menciona Turing en su artículo de 1950, “Computing Machinery and Intelligence”, y argumente si se mantiene o no en la actualidad la respuesta que da Turing en el artículo.

«El argumento desde la percepción extra sensorial» no está vigente porque la premisa «la percepción extra sensorial tiene evidencia estadística significativa» es falsa. Después de la muerte de Turing, la investigación en distintas partes del mundo llegó a está conclusión.

El resto del argumento e ideas para evitar que los humanos modifiquen las condiciones de la prueba son completamente olvidables.

Describa con sus propias palabras cada uno de los elementos que conforman la descripción PEAS/REAS de un agente inteligente. (10 puntos)

PEAS es la descripción de las tareas y recursos para ejecutarla sobre el ambiente.

Medida de rendimiento. Conjunto de cualidades, resultados o objetivos a lograr, maximizar o minimizar.

Ambiente. Conjunto de lugares o situaciones donde el agente se ejecuta.

Las situaciones son clasificadas por la observabilidad, interación con otros agentes, determinismo, secuencialidad, dinamicidad, continuidad, conocido.

Actuadores. Conjunto de componentes del agente responsables de mover y controlar el ambiente.

Sensores. Conjunto de componentes del agente responsables de observar el ambiente.

Tipo de agente. Si bien no está incluido en el acrónimo, los agentes suelen ser clasificados según el tipo de actividades que realiza.

Descartando los ejemplos contenidos en las diapositivas del curso, proporcione un ejemplo para cada uno de los siguientes tipos de agentes inteligentes incluyendo su descripción PEAS/REAS

Juego de las torres de Hanoi

Considere el juego de las torres de Hanoi con tres discos en la torre de la izquierda y ninguno en las torres del centro y derecha. Suponga que el objetivo es mover los discos a la torre de la derecha y desea formular esto como un problema de búsqueda.

Proponga una representación de estados para el problema.

Cada estado específica una configuración válida de las torres de Hanoi: cada uno de los discos apilados en orden creciente en alguna de las 3 torres.

Indique cuál sería el estado inicial.

El estado inicial es la primera configuración válida que es 3 discos en la torre de la izquierda y ninguno en las torres del centro y derecha.

Dado un estado cualquiera, indique las acciones que serían legales.

Las acciones legales son mover un disco en la primera posición a la vez a cualquiera de las otras torres tal que sea de radio menor que del disco siguiente apilado.

Indique el tamaño del espacio de búsqueda.

Es bien conocido que $2^n-1$ -una demostración puede encontrarse en Concrete Mathematics, Knuth- es la cantidad de movimientos mínimo para $n$ discos. Para nuestro caso, $2^3-1=7$.

Pero el tamaño de espacio de búsqueda es equivalente a preguntarse ¿cuántas configuraciones válidas no repetidas existen?

Sea [1,2,3] una secuencia representativa de los tres discos cuya tiene como propiedad siempre estar en orden ascedente, ¿cuántas configuraciones son válidas para [1,2,3]? $\sum_{i=1}^{n=3} {3 \choose i}=7$ Las cuales son: [1], [2,3], [1,2], [3], [1,3], [2], [1,2,3]. Estás debemos a su vez agruparlas para que siempre sean igual a 3 discos válidos en juego: [[1], [2,3]], [[1,2], [3]], [[1,3], [2]], [[1,2,3]].

Ahora sí podemos contestar a la pregunta original.

Sabemos que hay $3!$ maneras de acomodar una configuración de tamaño 2 (las cuales son 3) y 3 maneras de acomodar una configuración de tamaño 1. Obteneniendo el tamaño del espacio de búsqueda: $3!3+3=21$.

Proporcione el “goal test” para este problema.

Este es encontrado cuando el estado legal coincida con las tres discos en la tercera torre.

Un bot en el supermercado

Suponga que le proporcionan un conjunto de N artículos que debe comprar G={g1, g2,..., gN}, una lista de m tiendas S={s1, s2,..., sM} y los inventarios de las tiendas, si una tienda si tiene en inventario el artículo gk lo indicamos gk ∊ si.

Suponga que desea programar un robot para que lo surta de todos los artículos deseados y los lleve a su casa, adoptando la tienda s1 como su casa y punto de partida, la cual no tiene actualmente inventario de ninguno de los artículos.

Las acciones a considerar son viajar-y-comprar, tal que el robot viaja de la tienda actual si a una nueva tienda sj de la forma más rápida posible y compra todos los artículos que se encuentren en la tienda sj y que aún no hayan sido comprados.

El tiempo de viaje de si a sj lo de denotamos t(si, sj) y puede suponer que siempre se toman las rutas más cortas. El robot inicia en su casa sin artículos y usted desea que compre todos los artículos y regrese a casa en el menor tiempo posible.

Para este problema, utilice un espacio de estados en el cual cada estado es un par (s, u) donde s es la tienda actual y u es el conjunto de artículos que faltan por comprar.

Para cada una de las siguientes heurísticas, aplicadas a los estados (s, u), establezca la fórmula para calcularla a partir de los tiempos de viaje e indique si es admisible, consistente, ambas o ninguna de las dos.

Condiciones para optimalidad

Sea $g(n)$ el costo del camino desde el node inicial al nodo $n$ y el $h(n)$ el costo estimado del más económico camino desde $n$ al objetivo, $f(n)=g(n)+h(n)$ es el costo estimado de la solución más económica desde el nodo inicial al objetivo.

Las dos condiciones de optimalidad son admisibilidad y consistencia.

La primera es que $h(n)$ nunca sobreestime el costo para alcanzar el objetivo. Formalmente, $h(n)$ es admisible cuando para toda $n$, $h(n)\le h^*(n)$, donde $h^*(n)$ es el costo óptimo desde $n$ al objetivo.

La seguna es que $h(n)$ si su estimación es siempre menor o igual al estimado desde el nodo vecino al objetivo más el costo de alcanzar ese vecino. Formalmente, $h(n)\le c(n, P)+h(P),h(G)=0$, $P$ es cualquier vecino desde $n$, $G$ es cualquier nodo objetivo, $c(n,P)$ es el costo de ir del nodo desde $n$ a $P$.

Si es $h$ es consistente, entonces $h$ es admisible. Si es admisible, no necesariamente es consistente.

Formulación

En vez de usar $n$ usaremos $s_i,s_j$ para hablar el mismo lenguaje que el problema.

El estado inicial es $(s_1,G)$. El estado objetivo es $(s_1,\emptyset)$. El costo está dado por el tiempo y la cantidad de artículos faltantes de ir desde el nodo $s$ al $s_j$ $c((t(s,s_j), u),P)$. De la misma manera $h(t(s,s_j),u)$. $t(s_i,s_j)$ es la secuencia de tiempos para ir desde un nodo $s_i$ a todos los nodos $s_j$.

El tiempo más corto de la ubicación actual a cualquier otra tienda diferente.

La heurística $h(t(s,s_j),u)=min_{s\neq s_j}(t(s,s_j))$ no es admisible, por lo cual tampoco es consistente.

La heurística no es admisible porque $min_{s\neq s_j}(t(s,s_j))> h^*(t(s,s_j),u)$. A continuación mostramos un ejemplo:

graph TD
  s -->|t=1,u=A,B,C| sj
  sj -->|t=5,u=A,B| s1
  s -->|t=2,u=A,B,C| si
  si -->|t=2,u=| s1

El tiempo de llegar a casa a partir de la ubicación actual.

La heurísitica $h(t(s,s_1),u)=t(s,s_1)$ es consistente y por lo tanto admisible.

Esto es así porque $h(G)=h(t(s_1,s_1),u)=t(s_1,s_1)=0$ y $t(s,s_1)\le t(s,P)+t(P,s_1)$, esto es así porque el camino entre dos nodos es la ruta más corta.

El tiempo más corto para llegar a cualquier tienda que tenga en inventario alguno de los artículos faltantes.

La heurísitica $h(t(s,s_j),u)=min(t(s,s_j))$ tal que un artículo $g\in u$ este en cualquier tienda $g \in s_j$ es consistente y por lo tanto admisible.

Esto es así porque $h(G)=h(t(s_1,s_1),u)=min(t(s_1,s_1))=0$ y $min(t(s,s_j))\le t(s,P)+min(t(P,s_1))$.

graph TD
  s -->|t=1,u=A,B,C| sj
  sj -->|t=5,u=A,B| s1
  s -->|t=2,u=A,B,C| si
  si -->|t=2,u=| s1

El tiempo más corto para llegar a casa desde cualquiera de las tiendas que tienen en inventario alguno de los artículos faltantes.

La heurísitica $h(t(s,s_j),u)=min(t(s_j,s_1))$ tal que al menos un artículo $g\in u$ este en cualquier tienda $g \in s_j$ es admisible, pero no consistente.

Esto así es porque siempre elige el costo menor para llegar a casa desde todas las tiendas. Pero no cumple la desigualidad del triángulo, dado que no utiliza la información del estado actual.

El tiempo total para obtener cada uno de los artículos faltantes de forma individual.

La heurísitica $h(t(s,s_j),u)=\sum_{g\in u} min(t(s_,s_j))$ donde $g \in s_j$ no es admisible, por lo cual tampoco es consistente.

No es admisible debido a $\sum_{g\in u} min(t(s_,s_j))> h^*(t(s,s_j),u)$ esto es porque la suma es sobre artículos individuales y no sobre el conjunto.

El número de artículos faltantes multiplicado por los tiempos más cortos entre tienda y tienda.

La heurísitica $h(t(s,s_j),u)=|u|min(t(s_i,s_j))$ no es admisible, por lo cual tampoco es consistente.

No es admisible debido a $|u|min(t(s_i,s_j))> h^*(t(s,s_j),u)$ esto es porque no está considerando el estado actual.

TSP (Traveling Salesman Problem)

Considere el problema TSP (Traveling Salesman Problem): dado una lista de ciudades y las distancias entre cada par, determinar la ruta más corta que visite cada una de las ciudades una vez y regrese a la ciudad de partida. Es decir, debe encontrar la ruta más corta que inicie y termine en la misma ciudad tal que pase por todas las demás sin repetir.

Indique una razón que nos llevaría a elegir una búsqueda local como “Hill-climbing” sobre un algoritmo como A* para resolver este problema.

Hill-climbing es un algoritmo greedy, esto implica que no necesita un heurística externa. A* en cambio si necesita una. Seleccionar una buena heurística (o siquiera pensar una) suele ser factor decisivo entre elegir A* y “Hill-climbing”.

En general, indique cuáles son las condiciones que se deben cumplir para que una búsqueda local sea mejor que la búsqueda A*.

La heuríristica externa no cumple los criterios de optimalidad puede llevar a resultados completamente malos, en cambio una búsqueda local da resultados buenos. La búsqueda local suele significar menor uso de memoria.

Suponga que conecta todas las ciudades en una ruta simple (no llega a ser un ciclo ya que no tiene la conexión de la última ciudad a la de origen). Proporcione un algoritmo que siga la lógica de “Hill-climbing” para el TSP partiendo de esa ruta.

hill_climbing(grafo)
   while T > 0
         elige_un_nodo_aleatorio_valido_que_no_este_en_la_ruta()
         if la nueva ruta es superior
             remplaza la ruta
          else
             remplaza el nodo anterior con una probabilidad p(T)
         T=T-diffT
   

Especifique si el algoritmo propuesto en el inciso previo podría quedar atrapado en un óptimo local.

Sí. El algoritmo queda atrapado en un óptimo local cuando elige nodos aleatorios cercanos al TSP pero la probabilidad provoca que quede atrapado.

Estrategia de podado Alpha-Beta

Aplique la estrategia de podado Alpha-Beta al siguiente árbol, indicando en el resultado las secciones del árbol que son podadas por la estrategia, así como los valores de Alpha y Beta para cada nodo interno que no termina siendo podado. (10 puntos)