Inteligencia Artificial 1: Los primeros programas con ia. (B: SGP versión 2)

Un solucionador de problemas más general

Ya estamos listos para ver una nueva versión del SGP con soluciones para los problemas de "correr una vuelta de cuadra", "objetivo hermano incluido", "saltar antes de ver" y el "subobjetivo recursivo".

Pero antes, como en el caso anterior, hay una función definida antes en el libro que utiliza este programa, que es encontrar-todos-if. Hay que verla como una variación de remove, en lugar de remover los ítems que coinciden, esta mantiene los que sí coinciden y remueve los que no.

Visto de esta manera la función encontrar-todos-if es la misma que remove-if-not. Por lo tanto mejor que definirla con un defun, es más fácil copiarla desde remove-if-not:

(setf (symbol-function 'encontrar-todos-if) #'remove-if-not)

Ok, y antes de avanzar con el programa muestro un ejemplo de su ejecución:

> (encontrar-todos-if #'(lambda(x) (< x 5)) '(1 2 3 4 5 6 7 8 9 0))

(1 2 3 4 0)

Nota del T: Aclaro antes de seguir, que deben cargarse en el intérprete Lisp (tu implementación de Lisp) la primera versión del SGP completa, o ir construyéndola a medida que avanza.

El glosario para la nueva versión del SGP es:

Funciones de alto nivel
SGP	Resuelve un objetivo usando una lista de operadores
Variables Globales
*ops*	Una lista de operadores disponibles
Tipos de dato
op	Un operador con accion, precondiciones, agregar-lista y borrar-lista
Funciones principales
alcanzar-todos-los-objetivos	alcanza una lista de objetivos.
alcanzar-objetivo	alcanza un objetivo individual
apropiado-p	decide si un operador es apropiado para un objetivo
aplicar-op	aplica un operador al estado actual
Funciones Auxiliares
ejecutando-p	¿Esta una condición ejecutándose?
comienza-con	¿Es el argumento una lista que comienza con un átomo dado?
convertir-op	Convierte un operador para usar la convención de ejecución
op	Crea un operador.
use	Usa una lista de operadores
member-equal	Testea si un elemento es igual a un miembro de una lista.
Funciones de Common-Lisp
member	verifica si un elemento es miembro de una lista
set-difference	Todos los elementos en un conjunto y no los del otro
subsetp	¿Un conjunto está totalmente contenido en otro?
union	Todos los elementos de ambos conjuntos
every	verifica si todos los elementos de una lista pasan un test
some	verifica si algún elemento de una lista pasa un test
remove-if	Elimina todos los ítems que satisfacen un test.
Funciones definidas previamente
encontrar-todos	una lista de todos los elementos que coinciden con un patrón de búsqueda
encontrar-todos-if	una lista de todos los elementos que satisfacen un predicado.
mappend	Aplica una función a cada elemento de una lista y une los resultados.

El cambio más importante es que, en lugar de mostrar un mensaje cuando cada operador es aplicado, se mostrará que el SGP devuelve el estado resultante. Una lista de "mensajes" en cada estado indica que acciones han sido tomadas. Cada mensaje es actualmente una condición, una lista de la forma (operador ejecutándose). Esto resuelve el problema de "correr la vuelta a la cuadra": podríamos llamar a SGP con un objetivo inicial de ((ejecutar-correr-vuelta-cuadra)), y podría ejecutar el operador correr-vuelta-cuadra, para satisfacer el objetivo.

El siguiente código define una nueva funcion, op, que construye operadores que incluyen el mensaje en su agregar-lista.

(defun ejecutando-p (x)

  "¿Esta x en la forma: (ejecutando ...) ?"

  (comienza-con x 'ejecutando))

(defun comienza-con (list x)

  "Es esta una lista cuyo primer elemento es x?"

  (and (consp list) (eql (first list) x)))

(defun convertir-op (op)

  "Construye un op (operador) conforme a la convención (EJECUTANDO op)."

  (unless (some #'ejecutando-p (op-agregar-lista op))

    (push (list 'ejecutando (op-accion op)) (op-agregar-lista op)))

  op)

(defun op (accion &key precondiciones agregar-lista borrar-lista)

  "Crea un nuevo operador que obedece la convención (EJECUTANDO op)."

  (convertir-op

   (make-op :accion accion :precondiciones precondiciones

                    :agregar-lista agregar-lista :borrar-lista borrar-lista)))

Los operadores construidos por op serán correctos, pero pueden ser convertidos desde operadores existentes usando convertir-op directamente:

(mapc #'convertir-op *ops-escuela*)

Este es un ejemplo de programación exploratoria: en lugar de comenzar a resolver todo cuando descubrimos una limitación en la primera versión, podemos usar Lisp para alterar las estructuras de datos existentes para la nueva versión del programa.

La definición de la variable *ops* y de la estructura op son exactamente las mismas que antes, y el resto del programa consiste de cinco funciones que ya hemos visto: SGP, alcanzar-todos-los-objetivos, alcanzar-objetivo, apropiado-p, y aplicar-op. La funcion SGP llama a alcanzar-todos-los-objetivos que devuelve tanto nil como un estado valido. A partir de esto eliminamos todos los átomos, que viven solo los elementos del estado final que son en otras palabras listas, las acciones de la forma (ejecutando operador). De esta manera, el valor de SGP en sí mismo es la lista de acciones tomadas para arribar al estado final. El SGP no devuelve RESUELTO cuando busca una solución, pero obedece la convención de devolver nil para una falla, y no-nil para el trabajo bien hecho. En general, es una buena idea tener un programa que devuelva un valor antes que mostrar ese valor, si hay la posibilidad que algunos otros programas puedan usar ese valor.

(defvar *ops* nil "Una lista de operadores disponibles.")

(defstruct op "Una operación"

  (accion nil) (precondiciones nil) (agregar-lista nil) (borrar-lista nil))

(defun SGP (estado objetivos &optional (*ops* *ops*))

  "Solución General de Problemas: desde estado, alcanza los objetivos usando *ops*."

  (remove-if #'atom(alcanzar-todos-los-objetivos (cons '(inicio) estado) objetivos nil)))

El mayor cambio en la versión 2 es evidente desde la primera línea de programa: no existe la variable *estado*. En lugar de esto, el programa contiene variables de estado locales. Esto es para resolver el problema de "saltar antes de ver", como se mencionó anteriormente.

Todas las funciones alcanzar-objetivo, alcanzar-todos-los-objetivos y aplicar-op toman un argumento extra que es el estado actual, y todas devuelven un nuevo estado como su valor. Ellas también deben obedecer la convención de devolver nil cuando fallan.

Así tendremos una ambigüedad potencial: ¿nil representa una falla, o representa un estado valido que no tiene condiciones? Resolvemos la ambigüedad adoptando la convención de que todos los estados deben tener al menos una condición. Esta convención es impuesta por la funcion SGP. En lugar de llamar (alcanzar-todos-los-objetivos estado objetivos nil), el SGP llama a (alcanzar-todos-los-objetivos (cons '(inicio) estado) objetivos nil)). De esta manera siempre que el usuario pasa al SGP un estado inicial nulo, pasara sobre un estado conteniendo (inicio) para alcanzar-todos-los-objetivos. Desde luego, estamos garantizando que ningún estado será nil, porque la única función que construye un nuevo esta es aplicar-op, y podemos ver observando en la última línea de aplicar-op que este siempre agrega algo dentro del estado que está devolviendo. (Una agregar-lista nunca puede ser nil, porque si fuera así, el operador no sería apropiado. Además, cada operador incluye la condición (ejecutando...).)

Observe que el valor final que devolvemos desde el SGP tiene todos los átomos removidos, así terminamos reportando solamente las acciones realizadas, ya que ellas son representadas por las condiciones de la forma (ejecutando accion). Agregar la condición (inicio) al comienzo también sirve para diferenciar entre un problema que no puede ser resuelto y uno que es resuelto sin ejecutar ninguna accion. La falla devuelve nil, mientras una solución sin pasos al menos incluirá la condición (inicio), y nada más.

Las funciones que devuelven nil como una indicación de falla y devuelven algún valor útil en otro caso son conocidas como semipredicados. Estos son errores que ocurren solamente en los casos donde el nil puede ser construido como un valor útil. Se cuidadoso cuando defines y usas semipredicados: (1) Decide si nil podría ser siempre un valor significativo. (2) Asegúrese que el usuario no puede corromper el programa suministrando nil como valor. En este programa, SGP es la única función donde el usuario podría llamar, así que una vez que tenemos respuesta para eso, estamos cubiertos. (3) Asegúrese que el programa no puede suministrar nil como valor. Hacemos esto viendo que hubo solo un lugar en el programa donde los nuevos estado fueros construidos, y que estos nuevos estados fueron formados agregando un elemento de lista dentro de otro estado.

Siguiendo estos tres procedimientos, tenemos una prueba informal de que los semipredicados encierran estados que funcionaran apropiadamente. Este tipo de prueba informal es un elemento común de diseño de un buen programa.

El otro gran cambio en la versión 2 es la introducción de una pila de objetivo para resolver el problema del subobjetivo recursivo. El programa se asegura que los objetivos están trabajando e inmediatamente falla si un objetivo aparece como un subobjetivo de sí mismo. Este test está hecho en la segunda cláusula de alcanzar-objetivo.

La funcion alcanzar-todos-los-objetivos intenta alcanzar cada uno de los objetivos en turnos, colocando la variable estado2 como el valor devuelto desde cada llamada sucesiva a alcanzar-objetivo. Si todos los objetivos son alcanzados en turnos, y si todos los objetivos ya se cumplen al fin (como subsetp chequea), luego el estado final es devuelto en otro caso la función falla, devolviendo nil.

La mayoría del trabajo es hecho por alcanzar-objetivo, que toma un estado, un solo objetivo como condición, y la pila de objetivos trabajados anteriormente. Si la condición ya está lista en el estado, entonces alcanzar-objetivo tiene éxito y devuelve el estado. Por otro lado, si el objetivo como condición ya está listo en la pila de objetivos, entonces no tiene sentido continuar -estaremos atrapados en un bucle sin fin- así alcanzar-objetivo devuelve nil. En otro caso, alcanzar-objetivo mira a través de la lista de operadores, intentando buscar uno apropiado para aplicar.

(defun alcanzar-todos-los-objetivos (estado objetivos pila-objetivo)

  "Alcanza cada objetivo, y se asegura que se cumplan al final."

  (let ((estado-actual estado))

    (if (and (every #'(lambda (g)

                                               (setf estado-actual

                                                     (alcanzar-objetivo estado-actual g pila-objetivo)))

                                   objetivos)

                     (subsetp objetivos estado-actual :test #'equal))

                estado-actual)))

(defun alcanzar-objetivo (estado objetivo pila-objetivo)

  "Un objetivo es alcanzado si ya está resuelto, o si hay un op apropiado para el que sea aplicable."

  (dbg-indent :sgp (length pila-objetivo) "Objetivo: ~a" objetivo)

  (cond ((member-equal objetivo estado) estado)

                ((member-equal objetivo pila-objetivo) nil)

                (t (some #'(lambda (op) (aplicar-op estado objetivo op pila-objetivo))

                                (encontrar-todos objetivo *ops* :test #'apropiado-p)))))

El objetivo ((ejecutando correr-una-vuelta-de-cuadra)) es una lista de una condición, donde la condición se pasa como una lista de dos elementos. Permitir listas como condiciones nos da más flexibilidad, pero también tenemos que ser más cuidadosos. El problema es que no todas las listas que lucen de la misma forma son las mismas. El predicado equal testea si dos argumentos lucen igual, mientras que el predicado eql testea si dos argumentos son idénticos. Funciones tales como member usan eql por defecto, tenemos que especificar con una clave :test que buscamos a equal en lugar de eso. Cuando esto esta se ha hecho varias veces, introducimos la función member-equal. En efecto, tendríamos que llevar la abstracción un paso más adelante y definir member-situacion, una función para testear si una condición es verdadera en una situación.

Esto podría permitir al usuario cambiar la funcion de coincidencia desde eql a equal, y para cualquier cosa más que pueda ser usado.

(defun member-equal (item lista)

  (member item lista :test #'equal))

La función aplicar-op, que es usada para cambiar el estado e imprimir en pantalla un mensaje reflejando esto, ahora devuelve el nuevo estado en lugar de mostrar cualquier cosa. Primero computa el estado que debería resultar de alcanzar todas las precondiciones del operador. Si es posible arribar a tal estado, entonces aplicar-op devuelve un nuevo estado derivado de este estado agregando lo que está en agregar-lista y eliminando todo lo que está en borrar-lista.

(defun aplicar-op (estado objetivo op pila-objetivo)

  "Devuelve un estado nuevo, transformado si op es aplicable."

  (dbg-indent :sgp (length pila-objetivo) "Considera: ~a" (op-accion op))

  (let ((estado2 (alcanzar-todos-los-objetivos estado (op-precondiciones op)

                                                                                     (cons objetivo pila-objetivo))))

    (unless (null estado2)

       Devuelve un estado actualizado

      (dbg-indent :sgp (length pila-objetivo) "Accion: ~a" (op-accion op))

      (append (remove-if #'(lambda (x)

                                                    (member-equal x (op-borrar-lista op)))

                                                estado2)

                      (op-agregar-lista op)))))

 

(defun apropiado-p (objetivo op)

  "Un op es apropiado para un objetivo si está en su agregar-lista."

  (member-equal objetivo (op-agregar-lista op)))

Hay una última complicación en la manera que computamos los nuevos estados. En la versión 1 del SGP, los estados eran (conceptualmente) conjuntos desordenados de condiciones, así nosotros podríamos usar union y set-difference para operar sobre ellos. En la versión 2, los estados son listas ordenadas, debido a que necesitamos preservar el orden de las acciones. De esta manera, tenemos que usar las funciones append y remove-if, ya que estas son definidas para preservar el orden, mientras que union y set-difference no lo hacen.

Finalmente, la última diferencia en la versión 2 es que esta introduce una nueva funcion: use. Ella está definida para ser usada como una función que ordena las declaraciones que son listas de operadores para ser usadas por series de problemas.

(defun use (listaop)

  "Usa listaop como la lista de operadores por defecto. Devuelve algo útil, pero no muy prolijo:

 el numero de operadores.”

  (length (setf *ops* listaop)))

La llamada a use establece el parámetro *ops*, así que no es necesario especificarlo en cada llamada al SGP. En consecuencia, en la definición del SGP misma el tercer argumento, *ops*, es ahora opcional si no es administrado, un valor por defecto será usado. El valor por defecto para *ops* es tomado como *ops*. Esto puede verse redundante o superfluo, ¿cómo podría una variable ser ella misma por defecto?

La respuesta es que las dos ocurrencias de *ops* lucen iguales, pero ellas actualmente se refieren a dos uniones completamente separadas de la variable global *ops*. La mayoría de las veces, las variables en listas de parámetros son variables locales, pero no hay una regla sobre uniones en variables globales como parámetro. Recuerde que el efecto de unir una variable global es que todas las referencias a la variable global que ocurra en cualquier lugar del programa -por fuera del alcance léxico de la función- se refiere a la nueva union de la variable global.

De esta manera luego de una secuencia de llamadas eventualmente llegamos a alcanzar-objetivo, con referencias a *ops*, y veremos las nuevas valores de las uniones de *ops*. La definición del SGP es repetida aquí, con una versión alternativa que une una variable local y explícitamente establece y reinicia la variable global *ops*. Claramente, el idioma de uniones de una variable global es más conciso, y  puede ser inicialmente confuso, esto es útil una vez que se entiende.

(defun SGP (estado objetivos &optional (*ops* *ops*))

  "Solución general de problemas: desde estado, alcanza objetivos usando *ops*."

  (remove-if #'atom (alcanzar-todos-los-objetivos (cons '(inicio) estado) objetivos nil)))

(defun SGP (estado objetivos &optional (ops *ops*))

  "Solución general de problemas: desde estado, alcanza objetivos usando *ops*."

  (let ((anteriores-ops *ops*))

    (setf *ops* ops)

    (let ((result (remove-if #'atom (alcanzar-todos-los-objetivos

                                                                    (cons '(inicio) estado)

                                                                    objetivos nil))))

      (setf *ops* anteriores-ops)

      result)))

Ahora veremos el funcionamiento de la versión 2. Usamos la lista de operadores que incluye el operador "preguntar a la tienda su número telefónico".

Primero nos aseguramos que se cumplan los ejemplos de la versión 1 haciendo:

> (use *ops-escuela*) => 7

Nota del T: No olvidarse de usar (use *ops-escuela*) que activa los operadores *ops-escuela*

> (sgp '(hijo-en-casa automovil-necesita-bateria tener-dinero tener-guia-telefonica)

       '(hijo-en-escuela))

((INICIO) (EJECUTANDO CONSULTAR-NUMERO) (EJECUTANDO MARCAR-TELEFONO-MERCADO)

 (EJECUTANDO LLAMAR-AL-MERCADO) (EJECUTANDO DAR-DINERO-MERCADO)

 (EJECUTANDO MERCADO-COLOCA-BATERIA) (EJECUTANDO LLEVAR-HIJO-A-ESCUELA))

> (de-bug :sgp) => (:SGP)

> (sgp '(hijo-en-casa automovil-necesita-bateria tener-dinero tener-guia-telefonica)

       '(hijo-en-escuela))

Objetivo: HIJO-EN-ESCUELA

Considera: LLEVAR-HIJO-A-ESCUELA

 Objetivo: HIJO-EN-CASA

 Objetivo: AUTOMOVIL-FUNCIONA

 Considera: MERCADO-COLOCA-BATERIA

  Objetivo: AUTOMOVIL-NECESITA-BATERIA

  Objetivo: MERCADO-CONOCE-PROBLEMA

  Considera: LLAMAR-AL-MERCADO

   Objetivo: EN-COMUNICACION-CON-MERCADO

   Considera: MARCAR-TELEFONO-MERCADO

    Objetivo: CONOCER-NUMERO-TELEFONICO

    Considera: PREGUNTAR-NUMERO-TELEFONICO

     Objetivo: EN-COMUNICACION-CON-MERCADO

    Considera: CONSULTAR-NUMERO

     Objetivo: TENER-GUIA-TELEFONICA

    Accion: CONSULTAR-NUMERO

   Accion: MARCAR-TELEFONO-MERCADO

  Accion: LLAMAR-AL-MERCADO

  Objetivo: MERCADO-QUIERE-DINERO

  Considera: DAR-DINERO-MERCADO

   Objetivo: TENER-DINERO

  Accion: DAR-DINERO-MERCADO

 Accion: MERCADO-COLOCA-BATERIA

Accion: LLEVAR-HIJO-A-ESCUELA

((INICIO) (EJECUTANDO CONSULTAR-NUMERO) (EJECUTANDO MARCAR-TELEFONO-MERCADO)

 (EJECUTANDO LLAMAR-AL-MERCADO) (EJECUTANDO DAR-DINERO-MERCADO)

 (EJECUTANDO MERCADO-COLOCA-BATERIA) (EJECUTANDO LLEVAR-HIJO-A-ESCUELA))

> (undebug) => NIL

> (sgp '(hijo-en-casa automovil-funciona)

       '(hijo-en-escuela))

((INICIO) (EJECUTANDO LLEVAR-HIJO-A-ESCUELA))

Ahora podemos ver que la versión 2 puede manejar los tres casos en que la versión 1 falló. En cada caso, el programa evita un bucle infinito, y también evita saltar antes de ver.

> (sgp '(hijo-en-casa automovil-necesita-bateria tener-dinero tener-guia-telefonica)

       '(tener-dinero hijo-en-escuela))

NIL

> (sgp '(hijo-en-casa automovil-necesita-bateria tener-dinero tener-guia-telefonica)

       '(hijo-en-escuela tener-dinero))

NIL

> (sgp '(hijo-en-casa automovil-necesita-bateria tener-dinero)

       '(hijo-en-escuela))

NIL

Finalmente, vemos que esta versión del SGP también trabaja sobre problemas triviales que no requieren acciones:

> (sgp '(hijo-en-casa) '(hijo-en-casa)) => ((INICIO))

El nuevo dominio de problemas: monos y bananas

Para mostrar que el SGP es general, tenemos que hacerle trabajar en distintos dominios. Comenzaremos con un "clásico" problema de inteligencia artificial. Imagine el siguiente escenario: un mono hambriento está parado en la puerta de una habitación. En el medio de la habitación está un ramo de bananas suspendido del techo por una soga, fuera del alcance del mono. Hay una silla cerca de la puerta, que es lo suficientemente liviana para el mono para empujar y lo suficientemente alta para alcanzar la mayoría de las bananas. Solo para hacer las cosas más complicadas, suponga que el mono tiene una pelota y puede tener solo una cosa a la vez. Para intentar representar este escenario, tenemos algo de flexibilidad para elegir que ponemos en el estado actual y que ponemos en los operadores. Por ahora, definimos los operadores como sigue:

(defparameter *ops-banana*

  (list

   (op 'trepar-la-soga

       :precondiciones '(soga-en-medio-de-habitacion en-medio-de-habitacion sobre-el-piso)

       :agregar-lista '(en-bananas sobre-la-soga)

       :borrar-lista '(en-medio-de-habitacion sobre-el-piso))

   (op 'empujar-silla-desde-puerta-hacia-el-medio-de-habitacion

       :precondiciones '(silla-en-puerta en-puerta)

       :agregar-lista '(soga-en-medio-de-habitacion en-medio-de-habitacion)

       :borrar-lista '(silla-en-puerta en-puerta))

   (op 'caminar-desde-puerta-hacia-el-medio-de-habitacion

       :precondiciones '(en-puerta sobre-el-piso)

       :agregar-lista '(en-medio-de-habitacion)

       :borrar-lista '(en-puerta))

   (op 'sujetar-bananas

       :precondiciones '(en-bananas manos-vacias)

       :agregar-lista '(tener-bananas)

       :borrar-lista '(manos-vacias))

   (op 'arrojar-pelota

       :precondiciones '(tener-pelota)

       :agregar-lista '(manos-vacias)

       :borrar-lista '(tener-pelota))

   (op 'comer-bananas

       :precondiciones '(tener-bananas)

       :agregar-lista '(manos-vacias sin-hambre)

       :borrar-lista '(tener-bananas con-hambre))))

Nota del T: Ok, a esta altura ya se habrán dado cuenta que en operadores no pongo ningún acento, y que siempre uso los verbos en infinitivo (en vez de tengo-bananas coloco tener-bananas, por ejemplo).

Usando estos operadores, podríamos plantear el problema de estar sin-hambre, dado el estado inicial de estar en la puerta, parado sobre el piso, tener la pelota, con hambre, y con la silla en la puerta. El SGP puede buscar una solución a este problema:

> (use *ops-banana*) => 6

> (sgp '(en-puerta sobre-el-piso tener-pelota con-hambre silla-en-puerta)

       '(sin-hambre))

((INICIO) (EJECUTANDO EMPUJAR-SILLA-DESDE-PUERTA-HACIA-EL-MEDIO-DE-HABITACION)

 (EJECUTANDO TREPAR-LA-SOGA) (EJECUTANDO ARROJAR-PELOTA)

 (EJECUTANDO SUJETAR-BANANAS) (EJECUTANDO COMER-BANANAS))

Observe que no necesitamos hacer ningún cambio en el programa SGP. Solo hemos usado un conjunto de operadores distinto.

Dejo aca el link de la segunda version del sgp: SGP version 2