Translate

lunes, 12 de noviembre de 2018

Programacion Web con AllegroServe

Breve introducción

Típicamente las páginas web son creadas en hipertexto (HTML) que le dicen al navegador como mostrar la pagina, incluyendo donde insertar imágenes y links hacia otras paginas. Por ejemplo una pagina en HTML luce asi:

<html>
   <head>
       <title>Hola</title>
   </head>

   <body>
      <p>Hola mundo!</p>
      <p>Esta es una imagen: <img src="imagen.gif"></p>
      <p>Este es un <a href="another-page.html">link</a> a otra pagina.</p>
   </body>
</html>



El navegador y el server se comunican usando un protocolo llamado Protocolo de Transferencia de Hipertexto (HTTP). Aunque no necesitas saber los detalles del protocolo es necesario entender que consiste de una secuencia de solicitudes iniciadas por el navegador y respondidas por el servidor. Esto es así, el navegador se conecta al servidor web y envía una solicitud que incluye al menos la URL deseada y la versión del protocolo HTML que utiliza el navegador. El navegador puede usar también datos en esta solicitud que le indican al servidor como mostrar el form HTML.

Para contestar una solicitud el servidor envía una respuesta que consta de un conjunto de cabeceras y un cuerpo. Las cabeceras contienen información sobre el cuerpo, como de que tipo de dato se trata (por ejemplo HTML, texto plano o una imagen), y el cuerpo es el dato mismo, que es mostrado por el navegador. El servidor puede enviar también una respuesta de error diciendo al navegador que esta solicitud no puede ser respondida por alguna razón. Una vez que el navegador ha recibido la respuesta completa desde el servidor, no hay comunicación entre ambos hasta la próxima vez que el navegador decide solicitar una pagina al servidor. Esto es lo principal sobre programación web, no hay manera de que el código se ejecute sobre el servidor para afectar lo que el usuario ve en su navegador sin que el navegador envíe una nueva solicitud al servidor. Algunas paginas web, llamadas estáticas, son simples archivos .html almacenados en el servidor web y ejecutadas cuando el navegador las solicita. Por otro lado, las páginas dinámicas consisten en HTML generado cada vez que la pagina es solicitada por el navegador. Por ejemplo una página dinámica puede ser generada a través de una consulta a una base de datos y luego construyendo el HTML que representa el resultado de la consulta. Cuando es generada la respuesta a una consulta, el código del lado del servidor tiene cuatro piezas principales de información. La primera pieza de información es la URL solicitada. Sin embargo, a menudo la URL es usada por el servidor web para determinar que código es responsable de generar la respuesta. Luego, si la URL contiene un signo de pregunta, todo lo que sigue al signo
de pregunta se considera como un "string de consulta", que es ignorada normalmente por el servidor web, excepto que esta disponible para la generación de código de la respuesta. La mayoria de las veces, la cadena de consulta contiene un conjunto de pares clave/valor. Las solicitudes desde el navegador también pueden contener "datos post", que también consisten usualmente en pares clave/valor. Los datos post son comúnmente usados para enviar formularios HTML. Los pares clave/valor suministrados tanto en la cadena de consulta como en los datos post son los llamados: "parámetros de consulta". Luego de haber enviado los string como una secuencia de solicitudes desde el navegador, el código ejecutándose en el servidor puede "configurar una cookie", enviando una cabecera especial en su respuesta al navegador, que contienen datos opacos llamados como "cookie". Después de que una cookie es configurada desde un servidor particular, el navegador enviará la cookie con cada solicitud enviada hacia ese servidor. Al navegador no le interesa los datos de la cookie, este solo regresa de vuelta hacia el servidor ese código a ser interpretado.
Hay 99% de elementos primitivos desde el lado del servidor. El navegador envía una solicitud, el servidor busca algún código para manejar la solicitud y ejecutarla, y el código usa tanto parámetros de consulta como cookies para determinar que hacer.

AllegroServe


AllegroServe esta incluido en la version de Allegro disponible desde Franz. AllegroServe provee un modelo de programación similar en espíritu a los Servlets de Java, tanto sobre archivos individuales como contenidos de un directorio. Cada vez que un navegador solicita una página, AllegroServe analiza la solicitud y observa un objeto, llamado "entidad", que maneja la solicitud. Algunas clases de entidad proveen como parte de AllegroServe información sobre como servir contenido estático. En otros casos, se ejecutara código Lisp arbitrario para generar la respuesta. La función start del paquete net.aserve arranca al servidor. Esta toma un numero de parámetros, pero el único que necesitas pasarle es :port, que especifica el puerto a ser activado. Si utilizas un sistema operativo derivado del Unix, probablemente deberías usar un puerto alto como 2001 en lugar del puerto por defecto para servidores HTTP, 80, debido a que en estos sistemas operativos solo el usuario root puede activar puertos por debajo de 1024. Para ejecutar AllegroServe activando el puerto 80 en Unix, necesitarías iniciar Lisp como root y luego usar los parámetros :setuid y :setgid para cambiar la identidad al iniciar después de abrir el puerto. Puedes arrancar un servidor activando el puerto 2001 de la siguiente forma:

> (use-package :net.aserve)
> (start :port 2001)
#<WSERVER port 2001 @ #x72511c72>

El servidor esta ahora corriendo en tu Lisp. Es posible que obtengas un error que diga algo sobre "port already in use" ("el puerto ya esta siendo utilizado") cuando intentes arrancar el servidor. Esto ocurre cuando el puerto 2001 está siendo utilizado por algún otro servidor en tu máquina. En ese caso, la manera más fácil de resolverlo es usar un puerto distinto, cambiando por otro valor en lugar de 2001 en las URLs usadas en este texto. Puedes continuar interactuando con Lisp a través del terminal debido a que AllegroServe arranca su propio hilo para manejar solicitudes desde navegadores. Esto ocurre, entre otras cosas, para que puedas usar el terminal Lisp para obtener una vista dentro de las entrañas de tu servidor mientras se está ejecutando, lo que permite corregir y testear una parte de manera más fácil que si el servidor fuera una completa caja negra. Asumiendo que estas ejecutando Lisp en la misma máquina que tu navegador, puedes chequear que ese servidor está activo y ejecutándose accediendo a la dirección en tu navegador http://localhost:2001/. En este punto deberías obtener un mensaje de error de página no encontrada en el navegador pues no tienes nada publicado aun. Pero el mensaje de error será desde AllegroServe; este lo mostrará en la parte superior de la página. Por otro lado, si el navegador mostrara un dialogo de error que diga algo como "La conexión fue rechazada cuando intentaba conectarse a localhost:2001", eso ocurre tanto si el servidor no se está ejecutando como así también cuando has iniciado con un puerto diferente del 2001.
Ahora puedes publicar algunos archivos. Supongamos que tienes un archivo hola.html en el directorio c:/servidor/ con el siguiente contenido: (Nota: Si utilizas Windows, el archivo del directorio que es "C:\Servidor\hola.html" se escribe en Lisp como "c:/Servidor/hola.html". Si el contenido se encontrara en la carpeta "Documentos" de un usuario llamado "RenePC" por ejemplo se accedería en Lisp así: "c:/Users/RenePC/Documents/hola.html")

<html>
   <head>
      <title>Hola</title>
   </head>

   <body>
      <p>Hola mundo!</p>
   </body>
</html>

Puedes publicar esto individualmente con la función publish-file:

> (publish-file :path "/hola.html" :file "c:/servidor/hola.html")
#<NET.ASERVE::FILE-ENTITY @ #x725eddea>

El argumento :path es el path que aparecerá en la URL solicitada por el navegador, mientras el argumento :file es el nombre del archivo en el sistema de archivos. Después de evaluar la expresión publish-file, puedes acceder a la dirección http://localhost:2001/hola.html, y debería mostrar una página como esta:



También puedes publicar el directorio entero c:/servidor/ (y todos sus subdirectorios) con la función publish-directory.

> (publish-directory :prefix "/" :destination "c:/Servidor/")
#<NET.ASERVE::DIRECTORY-ENTITY @ #x72625aa2>

En este caso, el argumento :prefix especifica el inicio del path de las URLs que deberían ser manejadas por esta entidad. De esta manera, si el servidor recibe una solicitud para http://localhost:2001/foo/bar.html, el path es c:/foo/bar.html. Este path es luego traducido al nombre reemplazando el prefijo "/" con el lugar de destino (destination) c:/tmp/html/. Así, la URL http://localhost:2001/hola.html será traducido en la solicitud por el archivo c:/servidor/hola.html.

Generando Contenido Dinámico con AllegroServe


Publicar entidades que generen contenido dinámico es casi tan simple como publicar contenido estático. Las funciones publish y publish-prefix son los análogos dinámicos de publish-file y publish-directory. La idea básica de estas dos funciones es que tu publicas una función que sera llamada para generar la respuesta a una solicitud tanto para una URL especifica como para cualquier URL con un prefijo dado. La función sera llamada con dos argumentos: un objeto representando la solicitud y la entidad publicada. La mayoría de las veces no necesitas hacer nada con el objeto entidad excepto para pasarle un par de macros de la que hablaremos en un momento. Por otro lado, usaras el objeto solicitud para obtener información enviada por los parámetros de consulta del navegador incluida en la URL o los datos post usando un formulario HTML.

Para un ejemplo trivial del uso de una función que genera contenido dinámico, se muestra una función que genera una pagina con un numero aleatorio distinto cada vez que es solicitada.

(defun numero-aleatorio (solicitud entidad)
   (with-http-response (solicitud entidad :content-type "text/html")
      (with-http-body (solicitud entidad)
         (format
            (request-reply-stream solicitud)
               "<html>~@
                  <head><title>Numero al azar</title></head>~@
                  <body>~@
                     <p>Numero Aleatorio: ~d</p>~@
                  </body>~@
                </html>~@
               "
               (random 1000)))))

Las macros with-http-response y with-http-body son parte de AllegroServe. El primero inicia el proceso para generar una respuesta HTTP y puede ser usado, como en este caso, para especificar cosas como el tipo de contenido que será devuelto. El with-http-body actualmente envía la cabeceras HTTP y luego ejecuta su cuerpo, que debería contener el código que genera el contenido de la respuesta. Dentro de with-http-response pero antes de whit-http-body, puedes agregar o cambiar las cabeceras HTTP para enviarlas en la respuesta. La función request-reply-stream es también parte de AllegoServe y devuelve el stream que se escribirá como salida para ser enviada al navegador. Como lo muestra esta función, puedes usar solo FORMAT para imprimir el HTML al stream devuelto por request-reply-stream.
En la próxima sección, se mostrara la manera mas conveniente para generarla por programa.
NOTA: El ~@ seguido por una nueva linea le dice a FORMAT que ignore los espacios en blanco después de la nueva linea, lo que te permite indentar tu código en forma amigable sin necesidad de agregar un grupo de espacios al HTML. Los espacios en blanco no significan nada en HTML, y no les interesan al navegador, pero esto hace que el código HTML generado luzca un poco mas amigable a las personas. Ahora estas listo para publicar esta función:

(publish :path "/numero-aleatorio.html" :function 'numero-aleatorio)
#<COMPUTED-ENTITY @ #x7262bab2>

Así como lo hace la función publish-file, el argumento :path especifica el path de la URL de esta función al ser invocada. El argumento :function especifica tanto el nombre como el objeto de la función actual. Usando el nombre de una función, como se muestra aquí, te permite redefinir la función sin tener que volver a publicarla y AllegroServe usará la nueva definición de la función. Después de evaluar la llamada a publish, puedes escribir la dirección en tu navegador http://localhost:2001/numero-aleatorio.html para obtener una página con un numero aleatorio en ella, como muestra la figura.



Allegro Common Lisp

Quería mostrar esta herramienta para el desarrollo de programas en Common Lisp. Me parece muy interesante. Viene disponible para varios sistemas operativos, windows y para varias distribuciones linux.


La ventana de la izquierda de la pantalla es el terminal (la consola lisp), y la ventana de la derecha es un editor para crear el programa.
La verdad me parece genial. 
Puedes descargar el programa desde: https://franz.com/downloads/clp/validate_survey
En esa página, tienes que colocar tu dirección de correo, activar la casilla que dice "I agree ..."  y presionar el botón "submit"

domingo, 4 de noviembre de 2018

Tic-tac-toe 5




El programa era mas fácil de lo que lo había hecho antes. Me complique demasiado, en realidad había que dividir el tablero en lineas, y el ordenador debería buscar las lineas que van cumpliendo con el objetivo, e ir completándolas. Hay ocho lineas posibles, 3 verticales, 3 horizontales y las dos diagonales. El orden de la búsqueda de la posición en blanco para cada linea puede ser al azar. También debe impedir que el humano complete sus lineas. Las versiones anteriores consultaban todas las posibilidades con el tablero completo de nueve entradas. La versión 4 era mas de lo mismo, por eso ni me moleste en publicarla. El problema con las versiones anteriores era que consumían demasiados recursos, para 3 entradas, por ejemplo, un barrido costaría solo unos pocos segundos, pero con nueve el tiempo de computo aumenta exponencialmente. La solución para un problema complejo es dividirlo en pequeñas partes e ir resolviéndolo, es decir generalizar. Aquí tendré en cuenta solo lineas de tres entradas, para ir luego tomándolas del tablero de nueve y seleccionar que linea conviene modificar. Una vez modificada una línea, se averigua su posición en el tablero. Para eso se usan listas con claves, que son las lineas-n. Cada linea-n de esta lista tiene dos claves :lin y :pos. :lin me da la linea del tablero, por ejemplo (N X O) y pos me dice cual linea es dentro del *tablero*.
Las posiciones del *tablero* son:
0   1   2  ---->  :pos 0
3   4   5  ---->  :pos 1
6   7   8  ---->  :pos 2

Las primeras tres horizontales desde arriba hacia abajo son las lineas-n con :pos 0,1 y 2; las que siguen son las verticales desde izquierda a derecha, que son las lineas cuya :pos son 3,4 y 5. Restan las diagonales. Entonces la primera diagonal formada por las posiciones 0,4,8 es la linea-n con :pos 6. Por último nos queda, la diagonal formada por las posiciones 2,4,6 es la linea-n con :pos 7.
Con la linea modificada y la posición, basta copiar este valor en las posiciones del tablero.
Visto de esta manera, el tiempo de computo tiende a cero :-D
Todavía hay que probar que no pierda el juego, y ver si se puede arreglar eso, es decir, probar el modo de jugar del programa.
Bueno aquí dejo el programa tal como quedó actualmente:

(setf *tablero* '(n n n n n n n n n))


;--------------------------------------------------------------------------------
;Para una linea

(defun agrega-x (linea pos)
;Devuelve una linea con la 'x colocada
  (setf (nth pos linea) 'x)
  linea)
  


(defun busca-n (linea)
;Devuelve la posicion de un espacio en blanco para una linea
  (setf pos nil)
  (setf ordenamientos '((0 1 2) (0 2 1)
(1 0 2) (1 2 0)
(2 0 1) (2 1 0)))

  (setf orden (nth (random 6) ordenamientos))
  
  (if (equal (nth (first orden) linea) 'n)
      (setf pos (first orden))
    (if (equal (nth (second orden) linea) 'n)
(setf pos (second orden))
      (if (equal (nth (third orden) linea) 'n)
  (setf pos (third orden)))))

  pos)

;---------------------------------------------------------------------------
; Obtener las lineas del tablero

(defun obtener(tablero)
;Obtiene las ocho lineas posibles            0   1   2
;linea 0 1 2 son horizontales                    3   4   5
;lineas 3 4 5 verticales                             6   7   8
;linea 6 diagonal \
;linea 7 diagonal /
  (setf linea-0 (list :lin (list (nth 0 tablero) (nth 1 tablero) (nth 2 tablero)) :pos 0))
  (setf linea-1 (list :lin (list (nth 3 tablero) (nth 4 tablero) (nth 5 tablero)) :pos 1))
  (setf linea-2 (list :lin (list (nth 6 tablero) (nth 7 tablero) (nth 8 tablero)) :pos 2))
  (setf linea-3 (list :lin (list (nth 0 tablero) (nth 3 tablero) (nth 6 tablero)) :pos 3))
  (setf linea-4 (list :lin (list (nth 1 tablero) (nth 4 tablero) (nth 7 tablero)) :pos 4))
  (setf linea-5 (list :lin (list (nth 2 tablero) (nth 5 tablero) (nth 8 tablero)) :pos 5))
  (setf linea-6 (list :lin (list (nth 0 tablero) (nth 4 tablero) (nth 8 tablero)) :pos 6))
  (setf linea-7 (list :lin (list (nth 2 tablero) (nth 4 tablero) (nth 6 tablero)) :pos 7))
  (setf lineas-n (list linea-0 linea-1 linea-2 linea-3 linea-4 linea-5 linea-6 linea-7))
  lineas-n)
  
;----------------------------------------------------------------------------------
;Seleccionar las lineas mas importantes 

(defun seleccionar(lineas-n)
  (setf seleccion nil)
  (setf seleccion (remove-if #'(lambda (linea-n) (< (cuenta (getf linea-n :lin) 'x) 2)) lineas-n));obtiene las lineas-n con dos 'x
  (if (equal seleccion nil)
      (setf seleccion (remove-if #'(lambda (linea-n) (< (cuenta (getf linea-n :lin) 'o) 2)) lineas-n));obtiene las lineas-n con dos 'o
    (if (equal seleccion nil)
(setf seleccion (remove-if #'(lambda (linea-n) (< (cuenta (getf linea-n :lin) 'x) 1)) lineas-n));obtiene las lineas-n con una 'x
      (if (equal seleccion nil)
  (setf seleccion (remove-if #'(lambda (linea-n) (< (cuenta (getf linea-n :lin) 'o) 1)) lineas-n)))));obtiene las lineas-n con una 'o

  (if (equal seleccion nil)
      (setf seleccion lineas-n)) ;si no encontro nada < 1 no hay jugadas aun, el tablero es todo 'n
  seleccion)


(defun cuenta (linea var)
  ;Cuenta la cantidad de veces que esta una variable ('x o 'o) en la linea
  (setf cuenta 0)
  (when (equal (nth 0 linea) var) (incf cuenta))
  (when (equal (nth 1 linea) var) (incf cuenta))
  (when (equal (nth 2 linea) var) (incf cuenta))
  cuenta)

(defun quita-completos (lineas-n)
  (setf lineas-n (remove-if #'(lambda (linea-n) (= (cuenta (getf linea-n :lin) 'n) 0)) lineas-n));quita las lineas-n si no tienen espacios en blanco
  lineas-n)
;---------------------------------------------------------------------------------------------

(defun gana (jugador);jugador es 'x y 'o. Verifica si un jugador gana
  (setf lineas-n (obtener *tablero*));las lineas-n tienen claves
  (setf respuesta nil)
  (when (some #'(lambda (linea-n) (= (cuenta (getf linea-n :lin) jugador) 3)) lineas-n)
    (setf respuesta T))
  respuesta)

;;;;--------------------------------------------------------------------------------------------------------------
;;;; Una jugada del ordenador -----------------------------------------------------------------------------------
;;;;--------------------------------------------------------------------------------------------------------------


(defun una-jugada-ordenador ()
  (setf pos-tablero nil) ;posicion absoluta de *tablero*
  (setf lineas-n (obtener *tablero*));las lineas-n tienen claves
  (setf lineas-n (quita-completos lineas-n)); quita las lineas que ya estan completas.
  (when (not (equal lineas-n nil))
    (progn
      (setf seleccion (seleccionar lineas-n))
      (setf linea-n (nth (random (length seleccion)) seleccion)) ;toma una linea-n al azar de seleccion
      (setf linea (getf linea-n :lin));linea seleccionada
      (setf posicion (getf linea-n :pos));tipo de linea seleccionada - | / \
      (setf pos-x (busca-n linea));busca una posicion en blanco
      (agrega-x linea pos-x) ;coloca la 'x

;Coloca la linea correspondiente en el tablero    0   1   2
;linea 0 1 2 son horizontales                                3   4   5
;lineas 3 4 5 verticales                                         6   7   8
;linea 6 diagonal \
;linea 7 diagonal /
;pos-x es la posicion dentro de una linea y pos-tablero es la posicion absoluta dentro de *tablero*
      (cond
       ((= posicion 0) 
(cond
((= pos-x 0) (setf pos-tablero 0))
((= pos-x 1) (setf pos-tablero 1))
((= pos-x 2) (setf pos-tablero 2))))

       ((= posicion 1)
(cond
((= pos-x 0) (setf pos-tablero 3))
((= pos-x 1) (setf pos-tablero 4))
((= pos-x 2) (setf pos-tablero 5))))
       
       ((= posicion 2) 
(cond
((= pos-x 0) (setf pos-tablero 6))
((= pos-x 1) (setf pos-tablero 7))
((= pos-x 2) (setf pos-tablero 8))))

       ((= posicion 3) 
(cond
((= pos-x 0) (setf pos-tablero 0))
((= pos-x 1) (setf pos-tablero 3))
((= pos-x 2) (setf pos-tablero 6))))

       ((= posicion 4) 
(cond
((= pos-x 0) (setf pos-tablero 1))
((= pos-x 1) (setf pos-tablero 4))
((= pos-x 2) (setf pos-tablero 7))))

       ((= posicion 5) 
(cond
((= pos-x 0) (setf pos-tablero 2))
((= pos-x 1) (setf pos-tablero 5))
((= pos-x 2) (setf pos-tablero 8))))

       ((= posicion 6) 
(cond
((= pos-x 0) (setf pos-tablero 0))
((= pos-x 1) (setf pos-tablero 4))
((= pos-x 2) (setf pos-tablero 8))))

       ((= posicion 7) 
(cond
((= pos-x 0) (setf pos-tablero 2))
((= pos-x 1) (setf pos-tablero 4))
((= pos-x 2) (setf pos-tablero 6)))))

      (setf (nth pos-tablero *tablero*) (nth pos-x linea)))) ;Coloca la ficha en *tablero*
  
  pos-tablero) ;Devuelve la posicion absoluta de tablero, donde se coloco la ficha


Ok. :-) y dejo el link del programa completo con interfaz gráfica: tic-tac-toe-5.lisp


Para recordar como se ejecutan estos programas con ltk:
1    1) Tener tcl/tk instalado en tu sistema operativo.
      
       Si tenes alguna distribución linux, hay que instalar primero los paquetes tcl8.5 y tk8.5, podes hacerlo desde el gestor de paquetes. Voy a mostrar la instalación en ubuntu:

Abre una terminal y logueate como administrador:

> sudo su

Instala los paquetes con apt-get, o con algun gestor de paquetes.

> apt-get install tcl8.5

> apt-get install tk8.5

Si tu sistema operativo es Windows puedes descargar e instalar la última versión de ActiveTcl desde: https://www.activestate.com/activetcl/downloads
Asegurate de tener el sistema operativo actualizado, prueba ejecutar c:\ActiveTcl\bin\wish.exe y te aparecerá una ventana vacía. Si da error debes actualizar Universal C Runtime: https://support.microsoft.com/es-ar/help/2999226/update-for-universal-c-runtime-in-windows 

2) Tener el archivo ltk.lisp.


3    
      3) Cargar el programa ltk.lisp y tic-tac-toe-5.lisp en la consola de lisp.

      (load "/ruta/ltk.lisp") ;en mi caso hago: (load "c:/users/renepc/documents/mis-programas-lisp/ltk.lisp")
      (load "/ruta/tic-tac-toe.lisp") ;en mi caso hago: (load "c:/users/renepc/documents/mis-programas-lisp/tic-tac-toe-5.lisp")

      4) Ejecutar el main dentro del paquete:    
           
          (tic-tac-toe:main)

      También se puede crear un archivo arranca-ttt5.lisp por ejemplo, que carge el ltk.lisp, el programa tic-tac-toe-5.lisp y ejecute (tic-tac-toe:main), para no tener que hacer tantos pasos.



jueves, 1 de noviembre de 2018

Inteligencia Artificial 1: Los primeros programas con ia. (D: SGP versión 2. Análisis)



Hemos mostrado que el SGP es extensible a múltiples dominios. El punto principal es que no necesitamos cambiar el programa mismo para obtener los nuevos dominios de trabajo; solo cambiamos la lista de operadores que se pasan al SGP. La experiencia en distintos dominios sugirió cambios que podrían hacerse, y mostramos como incorporar algunos cambios. Aunque la versión 2 es una gran mejora de la versión 1, esta deja mucho que desear. Ahora descubriremos algo sobre la mayoría de los problemas.

El problema de no ver después de no saltar

Resolvimos el problema de “saltar antes de ver” introduciendo variables para mantener una representación de posibles estados futuros, que es mejor que solo una variable representando el estado actual. Esto previene al SGP de tomar una acción inapropiada, pero deberíamos ver que con todas las estrategias de reparación introducidas en la última sección, esto no garantiza que una solución sea encontrada cuando es posible.
Para ver el problema, se agrega otro operador al frente de la lista *ops-escuela* y se cambia la salida del de-bug así:
(use (push (op 'hijo-a-escuela-en-taxi
                           :precondiciones ' (hijo-en-casa tener-dinero)
                           :agregar-lista ' (hijo-en-escuela)
                           :borrar-lista ' (hijo-en-casa tener-dinero))
                      *ops-escuela*))
(de-bug :sgp)

Ahora, considere el problema de llevar el hijo a la escuela sin tener nada de dinero:

> (sgp '(hijo-en-casa tener-dinero automovil-funciona)
            '(hijo-en-escuela tener-dinero))
Objetivo: HIJO-EN-ESCUELA
Considera: HIJO-A-ESCUELA-EN-TAXI
 Objetivo: HIJO-EN-CASA
 Objetivo: TENER-DINERO
Accion: HIJO-A-ESCUELA-EN-TAXI
Objetivo: TENER-DINERO
Objetivo: TENER-DINERO
Objetivo: HIJO-EN-ESCUELA
Considera: HIJO-A-ESCUELA-EN-TAXI
 Objetivo: HIJO-EN-CASA
 Objetivo: TENER-DINERO
Accion: HIJO-A-ESCUELA-EN-TAXI
NIL

Las primeras cinco líneas de salida exitosamente resuelven el objetivo hijo-en-escuela con la acción HIJO-A-ESCUELA-EN-TAXI. La siguiente línea muestra un intento fallido para resolver el objetivo tener-dinero. El siguiente paso es intentar el otro ordenamiento. Esta vez, el objetivo tener-dinero se intenta primero, y es exitoso. Luego, el objetivo hijo-en-escuela es alcanzado nuevamente por la acción HIJO-A-ESCUELA-EN-TAXI.  Pero la verificación para consistencia en alcanza-cada-uno falla, y no hay reparaciones disponibles. El objetivo falla, cuando hay una solución válida: conducir hacia la escuela.
El problema es que alcanzar-objetivo usa algo para ver en los apropiado-ops. De esta manera, si hay algún operador apropiado, alcanzar-objetivo es exitoso. Si hay un único objetivo, este llevara a una solución correcta. Sin embargo, si hay múltiples objetivos, como en este caso, alcanzar-objetivo logrará solo encontrar una manera de cumplir el primer objetivo. Si la primera solución es mala, el único recurso es intentar repararlo. En dominios tales como el mundo de bloques y los laberintos, la reparación trabaja bien, debido a que todos los pasos son reversibles. Pero en el ejemplo del taxi, ningún tipo de plan de reparación puede obtener el dinero una vez que se ha gastado, así el plan entero falla. Hay dos maneras de encarar este problema. El primer enfoque es examinar todas las posibles soluciones, no solo la primera solución que alcanza cada subobjetivo. El lenguaje Prolog, que será discutido en el capítulo 11, hace exactamente eso. El segundo enfoque es tener alcanzar-objetivo y alcanzar-todos-los-objetivos alimentados con una lista de objetivos que deben estar protegidos. En el ejemplo del taxi, podríamos trivialmente alcanzar el objetivo de tener-dinero y luego intentar alcanzar hijo-en-escuela, mientras está protegido el objetivo tener-dinero. Un operador podría solamente ser apropiado si no puede borrar ningún objetivo que esté protegido. Este enfoque requiere algún tipo de reparación a través de recorridos de múltiples soluciones. Si intentáramos solo un único ordenamiento - alcanzando el objetivo hijo-en-escuela y luego intentar protegerlo mientras alcanza tener-dinero- luego no buscaríamos la solución. El planeador WARPLAN de David Warren hace un buen uso de la idea de objetivos protegidos.

El problema de la ausencia de descripción del poder


Esto sería algo referente a la economía, en el dominio de laberintos, para tener un operador que diga nosotros podemos mover desde aquí hacia allá si estamos en “aquí”, y si aquí es una conexión desde “aquí” hacia “allá”. Luego la entrada a un problema particular listaría las conexiones válidas, y resolveríamos cualquier laberinto solo con este operador. Similarmente, hemos definido un operador donde el mono empuja la silla desde la puerta hacia el medio de la habitación, pero sería mejor tener un operador donde el mono pueda empujar la silla desde donde sea hacia cualquier otra ubicación cerca, o mejor aún, un operador para empujar cualquier objeto “móvil” desde una ubicación hacia otra, sin intervención de obstáculos. La conclusión es que nos gustaría tener variables en los operadores, así podríamos decir algo como esto:

(op '(empujar X desde A hacia B)
        :precondiciones '((mono en A) (X en A) (movil X) (camino A B))
        :agregar-lista '((mono en B) (X en B))
        :borrar-lista '((mono en A) (X en A)))

Desde luego deseamos caracterizar un estado en términos de algo más abstracto que una lista de condiciones. Por ejemplo, al resolver un problema de ajedrez, el objetivo es tener al oponente en jaque mate, una situación que no puede ser descrita económicamente en términos primitivos como (rey negro sobre A 4), así que necesitamos ser capaces de tener un estado de algún tipo de restricción sobre el estado de objetivos, mejor que solo listar sus componentes. Podemos buscar ser capaces de alcanzar una disyunción o una negación de condiciones, donde el formalismo actual permita solo una conjunción.
Esto también es importante, en muchos dominios, ser capaces de tener estados de problemas tratados con tiempo: buscamos alcanzar X antes del tiempo T0, y luego alcanzar Y antes que T2 pero no antes que T1. El trabajo programado en el piso de una fábrica o construcción de una casa son ejemplos de planeamiento donde el tiempo juega un papel importante.
Desde luego que hay costos asociados con acciones, y buscamos encontrar una solución con mínimos costos, o con lo más cercano al mínimo. El costo puede ser simple como el número de operadores requeridos para una solución –nuestro juego en el dominio del mundo de bloques en que algunas veces un operador que podría ser aplicado inmediatamente fue ignorado, y un operador que ha necesitado varias precondiciones satisfechas fue cambiado en lugar de él.  O podemos satisfacerlo con una solución parcial, si una solución completa es imposible o demasiado expansiva. Podemos también buscar tener en cuenta el costo (y el tiempo) de computación.

El problema de la información perfecta


Todos los operadores que hemos visto tienen resultados ambiguos, ellos agregan o borran ciertas cosas del estado actual, y el SGP siempre sabe exactamente lo que ellos van a hacer. En el mundo real, las cosas son raramente muy cortas y secas. Yendo hacia atrás al problema de ser rico, un operador relevante podría ser jugar la lotería. Este operador tiene el efecto de consumir algo de dólares, y por una vez, mientras juega, el pago de una gran suma. Pero no tenemos ninguna manera de representar un pago “por una vez, mientras juega”. En forma similar, no tenemos manera de representar dificultades inesperadas de cualquier tipo, en el problema de la escuela; podríamos representar el problema con la batería del automóvil teniendo al SGP explícitamente testeando para ver si el automóvil estuvo funcionando, o si este necesitó una batería, cada vez el programa considera el operador de conducir. En el mundo real, debemos ser cuidadosos; tomamos el automóvil, y solo cuando este no arranca consideramos la posibilidad de una batería muerta.

El problema de objetivos que interactúan


La gente tiende a tener múltiples objetivos, en vez de trabajar con uno solo a la vez. No solamente se busca llevar al niño a la escuela, sino que se busca tener otro automóvil, hacer mi trabajo, trabajar bien, conocer amigos, divertirse, continuar respirando, y así sucesivamente. Yo también tengo que descubrir objetivos propios, antes de trabajar sobre un conjunto de objetivos predefinidos pasados a mí a través de alguien más. A algunos objetivos los puedo mantener en segundo plano por años, y luego trabajar sobre ellos cuando la oportunidad se presenta. Nunca hay una noción de satisfacer todos los posibles objetivos. En vez de, haber un proceso continuo de alcanzar objetivos, parcialmente alcanzamos otros, y luchamos o abandonamos otros logros.
Para tener objetivos activos, la gente también pasa por situaciones indeseables que se intentan en vano. Por ejemplo, suponga que tengo como objetivo visitar a un amigo al hospital. Esto requiere ir al hospital. Un operador aplicable puede ser caminar al hospital, mientras que otro podría ser dañarme a mí mismo severamente y esperar a que la ambulancia me lleve hacia allá. El segundo operador solo alcanza el objetivo (tal vez ir más rápido), pero esto tiene un efecto indeseable. Este podría ser entendido tanto como una noción del costo de la solución, tal como se habló en el parágrafo anterior; como una lista de objetivos en segundo plano donde cada solución se intenta proteger.
Herb Simon acuño el término “satisfacer” para describir la estrategia de satisfacer un numero razonable de objetivos para grados razonables, mientras abandona o pospone otros objetivos. El SGP solo sabe de éxitos y fallas, y de este modo no hay manera de maximizar los sucesos parciales.

El objetivo del SGP


Estas últimas cuatro secciones nos dan una pista sobre las limitaciones del SGP. En efecto, este no es un solucionador general de problemas en todo. Esto es general en el sentido que los algoritmos no están unidos a un dominio particular; nosotros podemos cambiar el dominio cambiando los operadores. Pero el SGP falla en ser general en que no puede resolver muchos problemas importantes. Este queda confinado a pequeños trucos y juegos.
Hay una importante razón aún de por qué el SGP estuvo destinado a fallar, una razón que no fue apreciada en el año 1957 pero que ahora es el núcleo de la ciencia de ordenadores. Es ahora reconocido que hay problemas que los ordenadores no pueden resolver – no debido a que teóricamente el programa correcto no pueda ser escrito, sino porque la ejecución del programa llevaría demasiado tiempo. Un gran número de problemas pueden caer dentro de la clase de problemas “NP-hard”. El cómputo de una solución a estos problemas toma un tiempo que aumenta exponencialmente según aumenta el tamaño del problema. Esta es una propiedad de los problemas mismos, y se mantiene sin importar cuan hábil sea el programador.
El aumento exponencial hace que problemas que puedan ser resueltos en segundos en cinco casos de entrada pueden tomar trillones de años cuando hay 100 entradas. Comprar un ordenador rápido no ayuda mucho. Después de todo, si un problema podría tomar un trillón de años para ser resuelto por tu ordenador, no ayudaría mucho comprar 1000 ordenadores que sean 1000 veces más rápidos que el que tú tienes: estas logrando reducirlo a un millón de años de espera. Para un científico teórico, descubrir que un problema es NP-hard es un fin en sí mismo. Pero para un trabajador en inteligencia artificial, está siendo respondida la pregunta incorrecta. Muchos problemas son NP-hard cuando insistimos en una solución óptima pero son mucho más fáciles de resolver cuando aceptamos una solución que puede no ser la mejor.
La entrada para el SGP es esencialmente un programa, y la ejecución del SGP es la ejecución de ese programa. Si el lenguaje de entrada del SGP es lo suficientemente general para expresar cualquier programa, entonces habrá problemas que no pueden ser resueltos, tanto porque toman demasiado tiempo para ejecutarse, como así también por el hecho de que no tienen solución. Los programas modernos de solución de problemas reconocen esta limitación fundamental, y pueden limitar la clase de problemas que intentan resolver o consideran maneras de encontrar soluciones parciales o bien aproximadas. Algunos solucionadores de problemas también monitorean su propio tiempo de ejecución y saben lo suficiente para tomar un problema como demasiado difícil.
El siguiente comentario del artículo de Drew Mc Dermott “La inteligencia artificial encuentra la estupidez natural” contribuye a la actual sensación sobre el SGP. Téngalo en cuenta la próxima vez que nombre un programa.
¿Recuerda al SGP? Por ahora, “SGP” es un término sin color denotando un programa particularmente estúpido que resuelve rompecabezas.  El originalmente llamado “Solución General de Problemas” causó a todos una innecesaria excitación y distracción. Debería haber sido llamado BRGCL “Buscador en Redes Guiado por Características Locales”.
Nada de eso, el SGP ha sido un vehículo útil para la programación exploratoria en general, y para la programación en inteligencia artificial en particular. Más importante que eso, éste ha sido un vehículo útil para explorar “la naturaleza de la deliberación”. Seguramente admitiremos que Aristóteles fue una persona más inteligente que tú o yo, aun con el agregado de un modelo computacional de la mente como una metáfora, y el agregado de un programa de ordenador trabajando para ayudar a explorar la metáfora, hemos visto una apreciación más cercana al análisis de medios-fines – al menos  con el modelo computacional. Debemos resistir la tentación de creer que todo pensamiento sigue este modelo.
El concepto de inteligencia artificial puede ser visto como una división entre medios y fines. El objetivo de un proyecto exitoso de IA puede ser un programa que acompaña algunas tareas útiles de un mejor modo, más rápido, o más barato que lo que podría hacerse antes. A través de esa mirada, el SGP es en su mayoría una falla, porque no puede resolver muchos problemas de buena manera. Pero los medios llevan a esos fines encerrados en investigación y formalización de los procesos de resolución de problemas. Teniendo en cuenta esto, nuestra reconstrucción del SGP es un éxito al grado en que lleva al lector a un mejor entendimiento de estas cuestiones.

Historia y Referencias


El SGP original está documentado en textos de Newell y Simon 1963 y su libro Resolver Problema Humano 1972, como así también en Ernst y Newell 1969. La implementación en este capítulo está basada en el programa STRIPS (Fikes y Nilsson 1971).
Hay otros programas importantes de planeamiento. El programa de Earl Sacerdoti ABSTRIPS fue una modificación del STRIPS que sirvió para el planeamiento jerárquico. La idea fue el esbozo de un plan esqueleto que resolvía el programa entero a un nivel abstracto, y luego completa los detalles. El planificador WARPLAN de David Warren está cubierto en Warren 1974a,b y en una sección de Coelho y Cotta 1988. El sistema NONLIN de Austin Tate (Tate 1977) alcanzó mucha más eficiencia considerando un plan como una secuencia parcialmente ordenada de operaciones antes que una secuencia estrictamente ordenada de situaciones. El TWEAK de David Chapman sintetiza y formaliza el estado del arte en planeamiento de 1987.
Todos estos textos –y otros pocos textos importantes de planeamiento- están impresos de nuevo en Allen, Hendler y Tate 1990.


jueves, 25 de octubre de 2018

Inteligencia Artificial 1: Los primeros programas con ia. (C: SGP versión 2. Otros dominios de problemas)



Nota del T: Antes de comenzar debemos crear una función: mappend. mappend es una función de orden superior construida en el desarrollo de este libro, y que se usará regularmente, tal como encontrar-todos-if. Toma dos argumentos, una función y una lista. Mappend aplica la función sobre cada elemento de la lista y une juntos todos los resultados. La primera definición sigue inmediatamente de la descripción y el hecho de que la función apply puede ser usada para aplicar una función a una lista de argumentos.

(defun mappend (funcion lista)
  "Aplica funcion a cada elemento de la lista y une los resultados."
  (apply #'append (mapcar funcion lista)))

Ahora experimentamos un poco para ver cómo trabaja mappend. El primer ejemplo aplica la funcion + a una lista de números:

> (apply #'+ '(1 2 3 4)) => 10

El próximo ejemplo aplica append a una lista de dos argumentos, donde cada argumento es una lista. Si los argumentos no son listas, daría error.

> (apply #'append '((1 2 3) (a b c))) => (1 2 3 A B C)

Ahora definimos una nueva funcion, mismo-y-doble, y aplicamos una variedad de argumentos.

> (defun mismo-y-doble (x) (list x (+ x x)))
> (mismo-y-doble 3) => (3 6)
> (apply #'mismo-y-doble '(3)) => (3 6)

Si hemos intentado aplicar mismo-y-doble a una lista de más que un argumento, o a una lista que no contiene un número, daría un error al evaluar (mismo-y-doble 3 4) o (mismo-y-doble 'Pedro). Ahora debemos regresar a las funciones de mapeo:

> (mapcar #'mismo-y-doble '(1 10 300)) => ((1 2) (10 20) (300 600))
> (mappend #'mismo-y-doble '(1 10 300)) => (1 2 10 20 300 600)

Cuando se pasa a mapcar una función y una lista de tres argumentos, ésta siempre devuelve una lista de tres valores. Cada valor es el resultado de llamar la función sobre el argumento respectivo. En contraste, cuando mappend es llamado, devuelve una lista grande, que es igual a todos los valores que mapcar podría generar uniendo todo. Daría un error la llamada a mappend sin una función que no devuelva listas, debido a que append espera listas como sus argumentos.

Nota del T: deberás cargar gps1.lisp y gps2.lisp para ejecutar los ejemplos, o ir construyéndolos a medida que avanza. Estos ejemplos los podes bajar de dominios.lisp.

El dominio de Búsqueda del Laberinto
Ahora consideraremos otro problema "clásico", búsqueda del laberinto. Asumiremos un laberinto particular, diagramado aquí:
 

Es mucho más fácil definir algunas funciones para ayudar a construir los operadores para este dominio que podrían escribir en todos los operadores directamente. El siguiente código define un conjunto de operadores para laberintos en general, y para este laberinto en particular:

(defun construir-laberinto-ops (par)
  "Construye ops laberinto en ambas direcciones"
  (list (construir-laberinto-op (first par) (second par))
                (construir-laberinto-op (second par) (first par))))

(defun construir-laberinto-op (aqui alla)
  "Construye un operador para mover entre dos lugares"
  (op `(mover desde ,aqui hacia ,alla)
      :precondiciones `((en ,aqui))
      :agregar-lista `((en ,alla))
      :borrar-lista `((en ,aqui))))

Nota del T: Observe la comilla (`) es casi lo mismo que la comilla ('), solo que después de cada coma (,) dentro del paréntesis, se activa la evaluación. En este caso se devuelve el valor que tiene "aqui" o "alla".

(defun mappend (funcion lista)
  "Aplica funcion a cada elemento de la lista y une los resultados."
  (apply #'append (mapcar funcion lista)))

(defparameter *ops-laberinto*
  (mappend #'construir-laberinto-ops
                   '((1 2) (2 3) (3 4) (4 9) (9 14) (9 8) (8 7) (7 12) (12 13)
                     (12 11) (11 6) (11 16) (16 17) (17 22) (21 22) (22 23)
                     (23 18) (23 24) (24 19) (19 20) (20 15) (15 10) (10 5) (20 25))))

Podemos ahora usar esta lista de operadores para resolver varios problemas con este laberinto. Y fácilmente podríamos crear otros laberintos dando otra lista de conexiones. Observe que no hay nada que diga que los lugares en el laberinto están dispuestos en un tablero de 5x5, esto es solo una manera de visualizar la conectividad.

> (use *ops-laberinto*) => 48

>  (sgp '((en 1)) '((en 25)))
((INICIO) (EJECUTANDO (MOVER DESDE 1 HACIA 2))
 (EJECUTANDO (MOVER DESDE 2 HACIA 3)) (EJECUTANDO (MOVER DESDE 3 HACIA 4))
 (EJECUTANDO (MOVER DESDE 4 HACIA 9)) (EJECUTANDO (MOVER DESDE 9 HACIA 8))
 (EJECUTANDO (MOVER DESDE 8 HACIA 7)) (EJECUTANDO (MOVER DESDE 7 HACIA 12))
 (EJECUTANDO (MOVER DESDE 12 HACIA 11)) (EJECUTANDO (MOVER DESDE 11 HACIA 16))
 (EJECUTANDO (MOVER DESDE 16 HACIA 17)) (EJECUTANDO (MOVER DESDE 17 HACIA 22))
 (EJECUTANDO (MOVER DESDE 22 HACIA 23)) (EJECUTANDO (MOVER DESDE 23 HACIA 24))
 (EJECUTANDO (MOVER DESDE 24 HACIA 19)) (EJECUTANDO (MOVER DESDE 19 HACIA 20))
 (EJECUTANDO (MOVER DESDE 20 HACIA 25)) (EN 25))

Hay un bug sutil que el dominio de laberintos deja afuera. Buscamos que el SGP devuelva una lista de las acciones ejecutadas. Sin embargo, para el caso donde los objetivos pueden ser alcanzados sin ninguna acción, yo incluí (INICIO) en el valor devuelto por SGP. Estos ejemplos incluyen las formas INICIO y EJECUTANDO pero también una lista de formas (EN n), para algunos n. Este es el bug. Si volvemos para atrás y miramos en la funcion SGP, encontramos que este reporta el resultado de remover todos los átomos desde el estado devuelto por alcanzar-todos-los-objetivos. Este es un "juego de palabras" -decimos remueve átomos, cuando lo que realmente queremos es remover todas las condiciones excepto las formas (INICIO) y (EJECUTANDO accion). Bien por ahora, todas estas condiciones eran átomos, esto es un acercamiento. El dominio de laberintos introduce condiciones de la forma (EN n), así que para la primera vez hubo un problema. La moraleja es que cuando un programador usa juegos de palabras convenientes en lugar de lo que realmente pasa hay un problema. Lo que realmente buscamos no es remover átomos sino encontrar todos los elementos que denotan acciones. El código abajo dice lo que queremos:

(defun SGP (estado objetivos &optional (*ops* *ops*))
  "Solución General de Problemas: desde estado, alcanza objetivos usando *ops*."
  (encontrar-todos-if #'accion-p
                       (alcanzar-todos-los-objetivos (cons '(inicio) estado) objetivos nil)))

(defun accion-p (x)
  "Es x algo que sea (inicio) o (ejecutando ...)?"
  (or (equal x '(inicio)) (ejecutando-p x)))

El dominio de laberintos resuelve también puntos afuera una ventaja de la versión 2: que devuelve una representación de las acciones tomadas mejor que solo imprimirlas en pantalla. La razón de esto es un ventaja es que podemos buscar usar los resultados para algo, es mejor que solo mirarlos. Suponga que buscamos una funcion que nos dé un camino a través de un laberinto como una lista de ubicaciones para visitar en turnos. Podríamos hacer esto llamando a SGP como una subfuncion y luego manipular los resultados:

(defun encontrar-camino (inicio fin)
  "Busca un laberinto por un camino desde inicio hasta fin."
  (let ((resultados (SGP `((en ,inicio)) `((en ,fin)))))
    (unless (null resultados)
      (cons inicio (mapcar #'destino
                                                  (remove '(inicio) resultados
                                                                  :test #'equal))))))


(defun destino (accion)
  "Encuentra el Y en (ejecutando (mover desde X hacia Y))"
  (fifth (second accion))) (fifth lista) ;fifth devuelve el quinto elemento de lista

La función encontrar-camino llama a SGP para obtener los resultados. Si este el nil, no hay respuesta, luego toma el resto de los resultados (en otras palabras, ignora la parte (inicio)). Escoge el destino, y, de cada forma (EJECUTANDO (MOVER DESDE x HACIA y)), y recuerda incluir el punto de inicio.

> (use *ops-laberinto*) => 48
> (encontrar-camino 1 25) =>
(1 2 3 4 9 8 7 12 11 16 17 22 23 24 19 20 25)
> (encontrar-camino 1 1) => (1)
> (equal (encontrar-camino 1 25) (reverse (encontrar-camino 25 1))) => T

El dominio del Mundo de Bloques

Otro dominio que ha llamado la atención en círculos de inteligencia artificial es el dominio del mundo de bloques. Imagine un conjunto de bloques de construcción para niños sobre una mesa. El problema es mover los bloques desde su configuración inicial en algunas configuraciones objetivo. Asumiremos que cada bloque puede tener solamente otro bloque directamente sobre el, aunque ellos pueden ser apilados en alturas arbitrarias. La única acción que puede tomar en este mundo es mover un solo bloque que no tenga nada encima de él, tanto por encima de otro bloque como sobre la mesa que representa el mundo de bloques. Crearemos un operador para cada posible movimiento de bloques.

(defun construir-bloques-ops (bloques)
  (let ((ops nil))
    (dolist (a bloques)
      (dolist (b bloques)
                (unless (equal a b)
                  (dolist (c bloques)
                    (unless (or (equal c a) (equal c b))
                      (push (mover-op a b c) ops)))
                  (push (mover-op a 'mesa b) ops)
                  (push (mover-op a b 'mesa) ops))))
    ops))

(defun mover-op (a b c)
  "Construir un operador para mover A desde B hacia C"
  (op `(mover ,a desde ,b hacia ,c)
      :precondiciones `((espacio sobre ,a) (espacio sobre ,c) (,a sobre ,b))
      :agregar-lista (mover-sobre a b c)
      :borrar-lista (mover-sobre a c b)))

(defun mover-sobre (a b c)
(if (eq b 'mesa)
    `((,a sobre ,c))
  `((,a sobre ,c) (espacio sobre ,b))))

Ahora intentaremos estos operadores sobre algunos problemas. El problema más simple posible es apilar un bloque sobre otro:



> (use (construir-bloques-ops '(a b))) => 4
> (sgp '((a sobre mesa) (b sobre mesa) (espacio sobre a) (espacio sobre b)
                 (espacio sobre mesa))
       '((a sobre b) (b sobre mesa)))
((INICIO) (EJECUTANDO (MOVER A DESDE MESA HACIA B)))

Hay un problema ligeramente más complejo: invertir una pila de dos bloques. Esta vez mostraremos la salida de-bug.


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

> (sgp '((a sobre b) (b sobre mesa) (espacio sobre a) (espacio sobre mesa))
       '((b sobre a)))
Objetivo: (B SOBRE A)
Considera: (MOVER B DESDE MESA HACIA A)
 Objetivo: (ESPACIO SOBRE B)
 Considera: (MOVER A DESDE B HACIA MESA)
  Objetivo: (ESPACIO SOBRE A)
  Objetivo: (ESPACIO SOBRE MESA)
  Objetivo: (A SOBRE B)
 Accion: (MOVER A DESDE B HACIA MESA)
 Objetivo: (ESPACIO SOBRE A)
 Objetivo: (B SOBRE MESA)
Accion: (MOVER B DESDE MESA HACIA A)
((INICIO) (EJECUTANDO (MOVER A DESDE B HACIA MESA))
 (EJECUTANDO (MOVER B DESDE MESA HACIA A)))

> (undebug) => NIL

Nota del T: deberás cargar gps1.lisp, gps2.lisp y dominios.lisp para ejecutar los siguientes ejemplos, o ir construyéndolos a medida que avanzas. Los siguientes ejemplos están en dominios2.lisp. Hago así porque van cambiando algunas funciones en los ejemplos que siguen.
Algunas veces es importante que intentes resolver los conjuntos adentro. Por ejemplo, no puedes tener tu pastel y haberlo comido al mismo tiempo, pero puedes tener una fotografía de tu pastel y haberlo comido al mismo tiempo, como veras tomas la fotografía antes de comértelo. En el mundo de bloques, tenemos:
                                                                  
(use (construir-bloques-ops '(a b c))) => 18

> (sgp '((a sobre b) (b sobre c) (c sobre mesa) (espacio sobre a) (espacio sobre mesa))
       '((b sobre a) (c sobre b)))
((INICIO) (EJECUTANDO (MOVER A DESDE B HACIA MESA))
 (EJECUTANDO (MOVER B DESDE C HACIA A))
 (EJECUTANDO (MOVER C DESDE MESA HACIA B)))

> (sgp '((a sobre b) (b sobre c) (c sobre mesa) (espacio sobre a) (espacio sobre mesa))
       '((c sobre b) (b sobre a)))
NIL

En el primer caso, la torre fue construida poniendo B sobre A primero, y luego C sobre B. En el segundo caso, el programa primero toma C sobre B, pero incluía ese objetivo mientras tomaba B sobre A. La situación de "objetivo hermano incluido" es reconocida, pero el programa no hace nada con eso. Una cosa que podría hacer es intentar variar el orden del conjunto de objetivos. Esto es, podríamos cambiar alcanzar-todos-los-objetivos como sigue:

(defun alcanzar-todos-los-objetivos (estado objetivos pila-objetivo)
  "Alcanza cada objetivo, intentando algunos ordenamientos."
  (some #'(lambda (objetivos) (alcanza-cada-uno estado objetivos pila-objetivo))
                             (ordenamientos objetivos)))

(defun alcanza-cada-uno (estado objetivos pila-objetivo)
  "Alcanza cada objetivo, y se asegura que ellos 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 ordenamientos (l)
  (if (> (length l) 1)
      (list l (reverse l))
    (list l)))

Ahora podemos representar el objetivo de cada manera, y se cumplirán tomando una respuesta. Observe que únicamente consideramos dos ordenamientos. El orden dado y el orden al revés. Obviamente, para conjuntos de objetivos de uno dos conjuntos se usan todas las posibilidades de ordenamiento. En general, si hay solo una interacción por conjunto de objetivos, luego uno de estos dos ordenamientos funcionará. De esta manera, asumimos que las interacciones del tipo "objetivo hermano incluido" son raras, y que raramente ocurrirá más de una interacción por conjunto de objetivos. Otra posibilidad seria considerar todas las posibles permutaciones de los objetivos, pero eso podría tomar un largo tiempo con conjuntos de objetivos extensos. Otra consideración es la eficiencia de soluciones. Considera la simple tarea de tomar el bloque C sobre la mesa en el siguiente diagrama:

> (sgp '((c sobre a) (a sobre mesa) (b sobre mesa)
                              (espacio sobre c) (espacio sobre b) (espacio sobre mesa))
       '((c sobre mesa)))
((INICIO) (EJECUTANDO (MOVER C DESDE A HACIA B))
 (EJECUTANDO (MOVER C DESDE B HACIA MESA)))

La solución es correcta, pero hay una solución más fácil que mueve C directamente a la mesa. La solución más simple no fue encontrada debido a un accidente: sucedió que construir-bloques-ops define los operadores de manera tal que  mover C desde B hacia la mesa ocurre antes de mover C desde A a la mesa. De esta manera el primer operador es intentado, y eso es exitoso estableciendo que C esta sobre B. De este modo, la solución de dos pasos es encontrada antes siquiera que la solución de un solo paso sea considerada. El siguiente ejemplo toma cuatro pasos cuando podría hacerse en dos:
                                                               
> (sgp '((c sobre a) (a sobre mesa) (b sobre mesa)
                              (espacio sobre c) (espacio sobre b) (espacio sobre mesa))
       '((c sobre mesa) (a sobre b)))
((INICIO) (EJECUTANDO (MOVER C DESDE A HACIA B))
 (EJECUTANDO (MOVER C DESDE B HACIA MESA))
 (EJECUTANDO (MOVER A DESDE MESA HACIA C))
 (EJECUTANDO (MOVER A DESDE C HACIA B)))

¿Cómo podríamos encontrar soluciones más cortas? Una manera podría ser hacer una búsqueda completa: las soluciones cortas se intentan primero, temporalmente abandonadas cuando algo sea más prometedor, y luego reconsideradas más tarde. Este enfoque es tomado en el capítulo 6, usando una función de búsqueda general. Una solución menos drástica es hacer un reordenamiento del orden en que los operadores son buscados: lo que tienen menos precondiciones se intentan primero. En particular, esto significa que los operadores con todas las precondiciones previas cumplidas siempre se intentan antes que los otros operadores. Para implementar este enfoque, cambiamos alcanzar-objetivo:

(defun alcanzar-objetivo (estado objetivo pila-objetivo)
  "Un objetivo se logra si ya se cumple, o si hay una opción apropiada 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))
                                (apropiado-ops objetivo estado))))) ))))

(defun apropiado-ops (objetivo estado)
  "Devuelve una lista de operadores apropiados, ordenados segun el numero de precondiciones insatisfechas."
  (sort (copy-list (encontrar-todos objetivo *ops* :test #'apropiado-p)) #'<
                             :key #'(lambda (op)
                                (count-if #'(lambda (precondiciones)
                                                      (not (member-equal precondiciones estado)))
                                                  (op-precondiciones op)))))

Ahora obtenemos las soluciones que buscamos:

> (sgp '((c sobre a) (a sobre mesa) (b sobre mesa)
                              (espacio sobre c) (espacio sobre b) (espacio sobre mesa))
                                                                                     '((c sobre mesa) (a sobre b)))
((INICIO) (EJECUTANDO (MOVER C DESDE A HACIA MESA))
 (EJECUTANDO (MOVER A DESDE MESA HACIA B)))


> (sgp '((a sobre b) (b sobre c) (c sobre mesa) (espacio sobre a) (espacio sobre mesa))
       '((b sobre a) (c sobre b)))
((INICIO) (EJECUTANDO (MOVER A DESDE B HACIA MESA))
 (EJECUTANDO (MOVER B DESDE C HACIA A))
 (EJECUTANDO (MOVER C DESDE MESA HACIA B)))

>(sgp '((a sobre b) (b sobre c) (c sobre mesa) (espacio sobre a) (espacio sobre mesa))
      '((c sobre b) (b sobre a)))
((INICIO) (EJECUTANDO (MOVER A DESDE B HACIA MESA))
 (EJECUTANDO (MOVER B DESDE C HACIA A))
 (EJECUTANDO (MOVER C DESDE MESA HACIA B)))      

La anomalía Sussman
Sorprendentemente, hay problemas que no pueden ser resueltos por ningún reordenamiento de objetivos. Considere:

Esto no luce muy difícil, así que veamos cómo lo maneja nuestro SGP:

> (setf comienza '((c sobre a) (a sobre mesa) (b sobre mesa) (espacio sobre c)
                                  (espacio sobre b) (espacio sobre mesa)))
((C SOBRE A) (A SOBRE MESA) (B SOBRE MESA) (ESPACIO SOBRE C) (ESPACIO SOBRE B)
 (ESPACIO SOBRE MESA))

> (sgp comienza '((a sobre b) (b sobre c)))
NIL

> (sgp comienza '((b sobre c) (a sobre b)))
NIL

Hay un problema de "objetivo hermano incluido" ¡sin importar cuál sea el orden de los conjuntos! En otras palabras, ninguna combinación de planes para los dos objetivos individuales puede resolver la conjunción de los dos objetivos. Esto es sorprendentemente cierto, y el ejemplo ha sido conocido como "la anomalía Sussman". Volveremos a este problema en el capítulo 6.

Dejo los enlaces del sgp y los ejemplos mostrados aquí: gps1.lispgps2.lispdominios.lisp y dominios2.lisp.