Inteligencia Artificial 1: Los primeros programas con ia. (A: el SGP)

Hola amigos, estaré traduciendo y publicando regularmente, si Dios quiere, el libro "Paradigmas de Programación en Inteligencia Artificial" de Peter Norvig. Abajo dejo el link del libro en inglés, ¡me costó conseguirlo! Este libro comienza con los primeros programas con ia, en base a eso va introduciendo algunos conceptos importantes en ia. Luego ira profundizando en los contenidos. A los programas en Lisp escritos en el libro también los traduzco. Los voy probando en mi compilador a medida que traduzco, así que funcionan.

Antes que nada necesitamos escribir una función que se llame encontrar-todos. (Nota del T: Esta función había sido definida previamente en el libro en los capítulos de introducción al Common Lisp, y el programa SGP la utiliza, por eso la pongo aquí.)

Suponga que queremos escribir una función de secuencia que sea similar a find y find-if, excepto que ella devuelve una lista de todos los elementos que coinciden con un ítem. Llamaremos a la función encontrar-todos. Otra forma de verlo es como una variación de remove. En lugar de remover ítems que coinciden, esta mantiene todos los ítems que coinciden, y remueve los que no coinciden. Afortunadamente remove puede ayudar a construirla. Todo lo que tenemos que hacer es usar remove con el complemento del argumento :test. Por ejemplo, si queremos buscar todos los elementos que son iguales a 1 en una lista, sería equivalente a remover elementos que no son iguales a 1:

> (setf nums '(1 2 3 4 2 1)) ===> (1 2 3 4 2 1)

> (remove 1 nums :test #'/=) ===> (1 1)

Ahora lo que necesitamos es una función que devuelva el complemento de otra función. En otras palabras, tomar =, debe devolver /=. Esta función es llamada complement en ANSI Common Lisp. Cuando encontrar-todos es llamada con un argumento :test, todo lo que tenemos que hacer es llamar a remove con el complemento del argumento :test. Cuando el argumento :test no esta especificado, el valor por defecto es eql. Deberíamos también verificar cuando el usuario especifica el argumento test-not, que es usado para especificar que la coincidencia ocurre cuando el predicado es falso. Es un error especificar ambos argumentos :test y :test-not en la misma llamada, así que necesitamos no verificar en tal caso. La definición es:

(defun encontrar-todos (ítem secuencia &rest argumentos

                                                    &key (test #'eql) test-not &allow-other-keys)

  "Busca todos los elementos de la secuencia que coinciden con ítem"

  (if test-not

      (apply #'remove ítem secuencia

                     :test-not (complement test-not) argumentos)

    (apply #'remove ítem secuencia

                   :test (complement test) argumentos)))

La única parte difícil de esta definición es entender la lista de parámetros. El &rest acumula todos los pares clave/valor en la variable "argumentos". Además del parámetro &rest, hay dos parámetros especificados :test y :test-not. Todas las veces que pones &key en una lista de parámetros, necesitas un &allow-other-keys si, en efecto, otras palabras clave son permitidas. En este caso, deseamos aceptar palabras clave como :start y :key y pasárselas a remove. Todos los pares clave/valor serán acumulados en la lista "argumentos", incluyendo los valores :test o :test-not. De esta manera, probamos:

> (encontrar-todos 1 nums :test #'= :key #'abs) ====> (1 1)

SGP: Solución general de problemas

La solución general de problemas SGP fue desarrollada en 1957 por Allan Newell y Herbert Simon. El algoritmo original había sido escrito en un lenguaje arcaico de bajo nivel llamado IPL.

Por un lado hablamos aquí sobre el programa SGP, por el otro esto se trata sobre el proceso de desarrollo de un programa de inteligencia artificial. El estudio del algoritmo SGP ilustra algunos aspectos importantes sobre en el desarrollo de ia.

Seguimos cinco etapas en el desarrollo de nuestra versión del SGP, con la esperanza de que el lector escriba su propio programa.

Las cinco etapas para la programación en IA son:

1. Describa el problema en vagas ideas.

2. Especifica el problema en términos algorítmicos.

3. Implemente el problema en un lenguaje de programación.

4. Testea el programa con ejemplos representativos.

5. Hacer el debug y analizar el programa, y repetir nuevamente desde el principio.

1. Descripción

Como nuestra descripción de problema, comenzaremos con un comentario del libro de Newell y Simon en 1972, sobre resolver un problema humano:

"El método principal del SGP está unido a la heurística de los análisis de medios-fines. El análisis de los medios-fines está tipificado por el siguiente tipo de argumentos de sentido común:

Yo deseo llevar a mi hijo a la escuela. ¿Cuál es la diferencia entre lo que tengo y lo que busco? Una de distancia.   ¿Que cambia la distancia? Mi automovil (Nota del T: carro en algunos países, auto en otros). Mi automovil no funciona ¿Que es necesario para que el automovil funcione? Una batería nueva. ¿Quién tiene baterías nuevas? El mercado de autopartes. Yo deseo que el mercado de autopartes coloque la batería nueva, pero el mercado no sabe que yo necesito una. ¿Cuál es la dificultad? Una de comunicación ¿Que permite la comunicación? Un teléfono... y así sucesivamente.

El tipo de análisis -clasificando cosas en términos de las funciones que sirven y oscilan entre fines, funciones requeridas y los medios que las ejecutan- forman el sistema básico de la heurística del SGP."

Por supuesto que, este tipo de análisis no es exactamente nuevo. La teoría del análisis de medios-fines fue expuesta elegantemente por Aristóteles hace 2300 años en el capítulo titulado como "La naturaleza de la deliberación y sus objetos" del Nicomadeon Eticas (Libro III. 3,1112b):

"Deliberamos no sobre fines, sino sobre los medios. Un doctor no delibera sobre la salud, ni un orador delibera sobre persuasión, ni un hombre de estado sobre producir leyes, ni nadie delibera sobre sus fines. Ellos asumen el fin y consideran como y a través de que medios tratarlo y si eso parece producido por algunos medios ellos consideran cual es el más fácil y mejor producido, mientras que si es resuelto por uno solamente ellos consideran como será resuelto por este y a través de qué medios ese mismo medio será resuelto, hasta que encuentren la primera causa, que es la última en descubrirse... y lo que es último en el análisis parece ser lo primero en importancia. Y eso nos lleva a una imposibilidad, tomamos la búsqueda, por ejemplo, de que si necesitamos dinero y este no puede ser obtenido pero si una cosa es posible intentamos hacerla."

Tomando esta descripción de una teoría de solución de problemas, ¿cómo deberíamos avanzar en un programa?

Primero, intentamos entender más profundamente el procedimiento del comentario antes citado. La idea principal es resolver un problema usando un proceso llamado análisis de medios-fines, donde el problema está situado en términos de que buscamos que ocurra. En el ejemplo de Newell y Simon, el problema es llevar al niño a la escuela, pero en general nos gustaría un programa que sea capaz de resolver toda clase de problemas. Podemos resolver un problema si podemos buscar alguna manera de eliminar "la diferencia entre que es lo que tengo y que es lo que busco" Por ejemplo, si lo que tengo es un hijo en casa, y lo que busco es un hijo en la escuela, entonces conducir puede ser una solución, debido a que sabemos que conducir produce un cambio en la ubicación. Nos daríamos cuenta que usar el análisis de medios-fines es una opción: es posible iniciar desde la situación actual y buscar hacia adelante los objetivos, o emplear una variación de diferentes estrategias de búsqueda. Algunas acciones requieren la resolución de precondiciones como subproblemas. Antes de que podamos conducir el automovil, necesitamos resolver el subproblema de tener el automovil en condiciones de funcionamiento. Puede ser que el automovil ya esté funcionando, en cuyo caso no tenemos que hacer nada para resolver el subproblema. De esta manera un problema es resuelto tanto por tomar acciones apropiadas directamente, como por la resolución de las precondiciones de una accion apropiada y luego tomando dicha accion. Es claro que necesitaremos alguna descripción de las acciones permitidas, con sus precondiciones y efectos. Necesitaremos también desarrollar una definición de lo que es apropiado. Sin embargo, si podemos definir estas nociones mejor, parece que no necesitaremos nuevas nociones. Así, decidiremos arbitrariamente que la descripción del problema está completa, y nos moveremos hacia la especificación del problema.

2. Especificación

En este punto tenemos una vaga idea de los medios para resolver un problema en el SGP. Podemos refinar estas nociones en representaciones específicas para Lisp tales como:

- Podemos representar el estado actual del universo -"que tengo"- o el estado de los objetivos -"que busco"- como conjuntos de condiciones. En Common Lisp no hay tipo de datos para conjuntos, pero este tiene listas, las que pueden ser usadas para implementar conjuntos. Cada condición puede ser representada por un símbolo. Así, un objetivo típico puede ser una lista de dos condiciones (rico famoso), y un estado actual típico puede ser (desconocido pobre).

- Necesitamos una lista de operadores permitidos. Esta lista será constante sobre el curso de un problema, o sobre una serie de problemas, pero buscamos que estén disponibles a ser cambiados y poder abordar un nuevo dominio de problemas.

- Un operador puede ser representado como una estructura compuesta de una accion, una lista de precondiciones, y una lista de efectos. Podemos colocar limites sobre los tipos de posibles efectos diciendo que un efecto puede tanto agregar como borrar una condición del estado actual. De esta manera, la lista de efectos puede ser partida en dos, una agregar-lista y una borrar-lista. Este fue el acercamiento tomado por la implementación del STRIPS (Stanford Research Institute Problem Solver, diseñado por Richard Fikes y Nils Nilsson en 1971), que será en efecto reconstruido en este capítulo. El SGP original permitía más flexibilidad en la especificación de efectos, pero la flexibilidad conduce a la ineficiencia.

- Un problema completo es descrito para el SGP en términos de un estado inicial, un estado de objetivos, y un conjunto de operadores conocidos. De esta manera, el SGP será una función con tres argumentos. Por ejemplo, un ejemplo de llamada puede ser:

(sgp '(desconocido pobre) '(rico famoso) lista-de-operadores)

En otras palabras, iniciando desde el estado de ser pobre y desconocido, alcanzar el estado de ser rico y famoso, usando cualquier combinación de operadores conocidos. El SGP debería devolver un valor verdadero solo si resuelve el problema, y debería imprimir en pantalla un archivo de las acciones tomadas. El acercamiento más simple es ir a través de las condiciones en el estado de objetivos en un instante e intentar alcanzar a cada uno. Si todos ellos pueden ser alcanzados, entonces el problema ha sido resuelto.

- Una condición de objetivo puede ser alcanzada de dos maneras. Si ya está en el estado actual, el objetivo es trivialmente alcanzado sin esfuerzo. En otro caso, tenemos que buscar algún operador apropiado e intentar aplicarlo.

- Un operador es apropiado si uno de los efectos del operador es para agregar el objetivo en cuestión al estado actual en otras palabras, si el objetivo está en la agregar-lista del operador.

- Podemos aplicar un operador si podemos alcanzar todas las precondiciones. Pero esto es fácil, debido a que solo hemos definido la noción de alcanzar un objetivo en el punto anterior. Una vez que las precondiciones han sido alcanzadas, aplicar un operador provoca la ejecución de la accion y actualiza el estado actual en términos del agregar-lista y borrar-lista del operador. Desde que nuestro programa es solo una simulación -esta no será realmente conducir un automovil o marcar un numero de telefono- debemos contentarnos simplemente con imprimir en pantalla la accion, que es mejor que tener cualquier accion real.

3. Implementación del algoritmo desarrollado en Common Lisp.

Las variables, tipos de datos y funciones necesarias para desarrollar el programa SGP son:

Funciones de alto nivel
SGP	Resuelve un objetivo usando una lista de operadores
Variables Globales
*estado*	El estado actual: una lista de condiciones
*ops*	Una lista de operadores disponibles
Tipos de dato
op	Un operador con accion, precondiciones, agregar-lista y borrar-lista
Funciones
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 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
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
Funciones definidas previamente
encontrar-todos	una lista de todos los elementos que coinciden con un patrón de búsqueda

                                                                             

Bueno, acá va el programa SGP completo en Common-Lisp:

(defvar *estado* nil "El estado actual: una lista de condiciones.")

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

(defstruct op "Un operador"

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

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

  "Solución General de Problemas: alcanza todos los objetivos usando *ops*."

  (if (every #'alcanzar-objetivo objetivos) 'resuelto))

(defun alcanzar-objetivo (objetivo)

  "Un objetivo es resuelto si ya está controlado (en *estado*), o si hay un operador apropiado para el

que sea aplicable."

  (or (member objetivo *estado*)

      (some #'aplicar-op

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

(defun apropiado-p (objetivo op)

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

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

(defun aplicar-op (op)

  "Escribe un mensaje y actualiza *estado* si el op(operador) es aplicable."

  (when (every #'alcanzar-objetivo (op-precondiciones op))

    (print (list 'ejecutando (op-accion op)))

    (setf *estado* (set-difference *estado* (op-borrar-lista op)))

    (setf *estado* (union *estado* (op-agregar-lista op)))

    t))

Hay dos defvar que declaran variables globales *estado* y *ops*, que pueden ser accedidas desde cualquier lugar del programa.

El defstruct genera una estructura llamada op, que tiene campos llamados accion, precondiciones, agregar-lista y borrar-lista. Las estructuras en Common-Lisp son similares a estructuras (struct) en C o registros (record) en Pascal. El defstruct automáticamente define una función para construir que se llama make-op, y una función de acceso para cada campo de la estructura. Las funciones de acceso son llamadas op-accion, op-precondiciones, op-agregar-lista, y op-borrar-lista. El defstruct también define una función para copiar, copy-op, un predicado op-p y definiciones setf para cambiar cada campo. Ninguno de estos fue usado en el programa SGP.

Luego en el programa SGP hay cuatro funciones. La función principal SGP, recibe tres argumentos. El primero es el estado actual, el segundo el estado de los objetivos, y el tercero es una lista de operadores permitidos. El cuerpo de la función dice simplemente que si podemos resolver cada uno de los objetivos, entonces el problema ha sido resuelto.

La función alcanzar-objetivo toma como argumento un solo objetivo. La función tiene éxito si ese objetivo ya está en el estado actual (en cuyo caso no tenemos que hacer nada) o si podemos aplicar un operador apropiado. Es recomendable construir primero la lista de operadores apropiados y luego verificar si cada uno puede ser aplicado. alcanzar-objetivo llama a encontrar-todos que fue definida previamente. encontrar-todos devuelve una lista de operadores que coinciden con el objetivo actual, testeando los operadores disponibles *ops* con apropiado-p.

La función apropiado-p verifica si un operador es apropiado para resolver un objetivo. (Se sigue la convención de Lisp de que los predicados terminan en -p).

Finalmente, la función aplicar-op dice que si puede resolver todas las precondiciones para un operador, puede aplicar el operador. La función consiste en mostrar un mensaje de que está cambiando el estado global, borrando lo que estuvo en borrar-lista y agregando lo que estuvo en agregar-lista. aplicar-op es también un predicado, devuelve t solamente cuando el operador fue aplicado.

4. Testear el programa:

En esta sección se definirá una lista de operadores aplicables al dominio "conducir a la escuela", que implica un problema relacionado con llevar al hijo hacia la escuela. Se mostrara como plantear y resolver algunos problemas en ese dominio. Primero, necesitamos construir la lista de operadores para el dominio. La forma defstruct para el tipo op automáticamente define la función make-op, que puede ser usada de la siguiente manera:

(make-op :accion 'llevar-hijo-a-escuela

                 :precondiciones '(hijo-en-casa automovil-funciona)

                 :agregar-lista '(hijo-en-escuela)

                 :borrar-lista '(hijo-en-casa))

Esta expresión devuelve un operador cuya accion es el símbolo llevar-hijo-a-escuela y cuyas precondiciones, agregar-lista y borrar-lista son las listas especificadas. La intención de este operador es que cada vez que el hijo este en casa y el automovil funcione, llevar-hijo-a-escuela pueda ser aplicado, y cambia el estado borrando el hecho de que el hijo está en casa, y agregando el hecho de que el hijo está en la escuela.

Deberíamos indicar que usar un átomo compuesto como hijo-en-casa es práctico solo para ejemplos simples como este. Una mejor representación podría romper el átomo en sus componentes: tal vez (hijo en casa). El problema con átomos compuestos es de combinatoria. Si hay 10 predicados (tales como este) y 10 personas u objetos, luego habrá 10 * 10 * 10 = 1000 posibles átomos compuestos, pero solo 20 componentes. Claramente podría ser más fácil describir los componentes. En este capítulo usamos átomos compuestos debido a que es más simple, y no necesitamos describir el mundo entero. Más adelante tomaremos la representación del conocimiento más seriamente.

Con este operador como modelo, podemos definir otros operadores. Habrá un operador para colocar una bateria, decirle al mercado sobre el problema, y llamar por telefono al mercado. Podemos completar agregando operadores para mirar el número de telefono del mercado, para pagarle el dinero, y así sucesivamente.

Nota del T: Aclaro antes de escribir los operadores que el libro se escribió antes de que existan los celulares, y por eso había que consultar en una guia telefonica antes de llamar a alguien. Para algunos milenials: en la guia telefonica estaban todos los telefonos fijos de la gente, para una ciudad determinada.

(defparameter *ops-escuela*

  (list

   (make-op :accion 'llevar-hijo-a-escuela

                    :precondiciones '(hijo-en-casa automovil-funciona)

                    :agregar-lista '(hijo-en-escuela)

                    :borrar-lista '(hijo-en-casa))

   (make-op :accion 'mercado-coloca-bateria

                    :precondiciones '(automovil-necesita-bateria mercado-conoce-problema mercado-quiere-dinero)

                    :agregar-lista '(automovil-funciona))

   (make-op :accion 'llamar-al-mercado

                    :precondiciones '(en-comunicación-con-mercado)

                    :agregar-lista '(mercado-conoce-problema))

   (make-op :accion 'marcar-telefono-mercado

                    :precondiciones '(conocer-numero-telefonico)

                    :agregar-lista '(en-comunicación-con-mercado))

   (make-op :accion 'consultar-numero

                    :precondiciones '(tener-guia-telefonica)

                    :agregar-lista '(conocer-numero-telefonico))

   (make-op :accion 'dar-dinero-mercado

                    :precondiciones '(tener-dinero)

                    :agregar-lista '(mercado-quiere-dinero)

                    :borrar-lista '(tener-dinero))))

El paso siguiente es plantear algunos problemas al SGP y examinar las soluciones. Mostrando tres problemas de ejemplo. En cada caso, el objetivo es el mismo: resolver la condición hijo-en-escuela. La lista de operadores disponibles es también la misma en cada problema la diferencia está en el estado inicial. Cada uno de los tres ejemplos consiste del prompt, ">", el cual es mostrado por el sistema Lisp, seguido por una llamada a SGP, " (sgp . . .)", que es tipeado por el usuario, luego la salida del programa, "EJECUTANDO . . . )", y finalmente el resultado de la llamada a la función, que puede ser RESUELTO o NIL.

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

       '(hijo-en-escuela)

       *ops-escuela*)

(EJECUTANDO CONSULTAR-NUMERO)

(EJECUTANDO MARCAR-TELEFONO-MERCADO)

(EJECUTANDO LLAMAR-AL-MERCADO)

(EJECUTANDO DAR-DINERO-MERCADO)

(EJECUTANDO MERCADO-COLOCA-BATERIA)

(EJECUTANDO LLEVAR-HIJO-A-ESCUELA)

RESUELTO

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

       '(hijo-en-escuela)

       *ops-escuela)

NIL

> (sgp '(hijo-en-casa automovil-funciona) '(hijo-en-escuela) *ops-escuela*)

(EJECUTANDO LLEVAR-HIJO-A-ESCUELA)

RESUELTO

En estos tres ejemplos el objetivo es llevar el hijo a la escuela. El único operador que tiene hijo-en-escuela en su agregar-lista es llevar-hijo-a-escuela. Así el sgp selecciona ese operador inicialmente. Antes que pueda ejecutar el operador, el sgp tiene que resolver las precondiciones. En el primer ejemplo, el programa trabaja, yendo para atrás, sobre los operadores mercado-coloca-bateria, dar-dinero-mercado, llamar-al-mercado, marcar-telefono-mercado y consultar-numero, que no tienen precondiciones destacadas. De esta manera, la accion consultar-numero puede ser ejecutada, y el programa se mueve sobre la otra accion. Como Aristóteles dice, "El último en el orden de análisis parece ser el primero en el orden de importancia"

El segundo ejemplo inicia exactamente del mismo modo, pero el operador consultar-numero falla debido a que su precondicion, tener-guia-telefonica no puede ser resuelta. El número de telefono es una precondicion, directa o indirectamente, de todos los operadores, así ninguna accion es tomada y el SGP devuelve NIL.

Finalmente, el tercer ejemplo es mucho más directo el estado inicial especifica que el automovil funciona, así el operador de conducir puede ser aplicado inmediatamente.

5. Análisis

En esta sección mostraremos como corregir las limitaciones del SGP en una segunda versión del programa. Limitaciones es solo un eufemismo para "bugs". ¿Estamos incrementado el programa, o lo estamos corrigiendo? No hay cuestiones claras en este punto, porque nunca insistiremos sobre una descripción o especificación de un problema específico. La programación de IA es explorativa esto consiste frecuentemente en descubrir más acerca del área del problema, en mayor medida de lo que fue definida en la especificación. Esto va en contraste con una noción de programación tradicional, donde el problema es completamente especificado antes de que la primer línea de código sea escrita.

El problema de correr una vuelta a la cuadra

Representar el operador "conducir desde casa hacia la escuela" es fácil: la precondicion y borrar-lista incluye estar en casa, y el agregar-lista incluye estar en escuela. Pero suponga que deseamos representar "corriendo una vuelta a la cuadra". No habría manera de cambiar de lugar, así esto que ocurre aquí no tendría agregar- o borrar- lista? Si esto pasa, no habría razón para aplicar el operador. Quizás el agregar-lista debería contener algo como "tengo algún ejercicio" o "sentirse cansado" o algo más general como "experiencia corriendo una vuelta a la cuadra" Volveremos a ver esta cuestión más adelante.

El problema del objetivo hermano incluido

Considere el problema de que no solamente tenemos que llevar al chico a la escuela sino que también queremos algo de dinero para usar el resto del día. SGP puede fácilmente resolver este problema con la siguiente condición inicial.

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

       '(tener-dinero hijo-en-escuela)

       *ops-escuela*)

(EJECUTANDO LLEVAR-HIJO-A-ESCUELA)

RESUELTO

Sin embargo, en el siguiente ejemplo el SGP reporta el suceso de manera incorrecta, cuando en efecto se ha gastado el dinero en la bateria.

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

       '(tener-dinero hijo-en-escuela)

       *ops-escuela*)

(EJECUTANDO CONSULTAR-NUMERO)

(EJECUTANDO MARCAR-TELEFONO-MERCADO)

(EJECUTANDO LLAMAR-AL-MERCADO)

(EJECUTANDO DAR-DINERO-MERCADO)

(EJECUTANDO MERCADO-COLOCA-BATERIA)

(EJECUTANDO LLEVAR-HIJO-A-ESCUELA)

RESUELTO

El "bug" es que el SGP usa la expresión (every #' alcanzar-objetivo objetivos) para resolver un conjunto de objetivos. Si esta expresión devuelve verdadero, ocurre que todos los objetivos han sido resueltos en secuencia, pero eso no ocurre cuando todos ellos permanecen verdaderos al final. En otras palabras, el objetivo (tener-dinero hijo-en-escuela), que tenía la intención de decir "al final en estado donde tanto tener-dinero como hijo-en-escuela son verdaderos" fue interpretado por el SGP como "primero alcanzar el objetivo de tener-dinero, y luego alcanza el objetivo hijo-en-escuela." Algunas veces resolver un objetivo puede incluir otro, previamente resuelto. Llamaremos a esto el problema del "objetivo hermano incluido". Esto es que, uno de los prerrequisitos para el plan para hijo-en-escuela es automovil-funciona, y resolver ese objetivo implica el objetivo tener-dinero.

Modificar el programa para reconocer el problema del "objetivo hermano incluido" es sencillo. Primero observe que llamamos a (every #' alcanzar-objetivo algo) dos veces en el programa, de esta manera reemplazamos estas dos formas con (alcanzar-todos-los-objetivos algo). Podemos definir alcanzar-todos-los-objetivos como sigue:

(defun alcanzar-todos-los-objetivos (objetivos)

  "Intenta resolver cada objetivo, luego se asegura que este se cumpla"

  (and (every #'alcanzar-objetivo objetivos) (subsetp objetivos *estado*)))

La función Common Lisp subsetp devuelve verdadero si su primer argumento es un subconjunto el segundo. En resolver-todo, se devuelve verdadero si todos los objetivos quedan en el estado actual después de haber resuelto todos los objetivos. Esto es lo único que deseamos verificar. alcanzar-todos-los-objetivos previene al SGP de devolver verdadero cuando uno de los objetivos envuelve a otro, pero no fuerza al SGP a volver a tratar un objetivo incluido. No consideramos esa posibilidad ahora, pero lo retomaremos nuevamente en la sección sobre los dominios de bloques, que fue el ejemplo primario de Sussman.

El problema de saltar antes de ver

Otra forma de tratar el problema de los "objetivos hermanos incluidos" es simplemente ser más cuidadoso en el orden de los objetivos en una lista de objetivos. Si deseamos llevar al niño a la escuela, ¿porque no solo especificamos el objetivo como (tener-dinero hijo-en-escuela) en lugar de (hijo-en-escuela tener-dinero)? Podemos ver lo que pasa cuando intentamos eso:

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

       '(hijo-en-escuela tener-dinero)

       *ops-escuela*)

(EJECUTANDO CONSULTAR-NUMERO)

(EJECUTANDO MARCAR-TELEFONO-MERCADO)

(EJECUTANDO LLAMAR-AL-MERCADO)

(EJECUTANDO DAR-DINERO-MERCADO)

(EJECUTANDO MERCADO-COLOCA-BATERIA)

(EJECUTANDO LLEVAR-HIJO-A-ESCUELA)

NIL

SGP devuelve nil, reflejando el hecho de que el objetivo no puede ser resuelto, pero solo después de ejecutar todas las acciones incluyendo conducir hacia la escuela. Yo llamo a esto el problema de "saltar antes de ver", debido a que si tu preguntas al programa para resolver por los dos objetivos (saltar-sobre-acantilado aterrizar-seguro) debería felizmente saltar primero, solo para descubrir que no tiene operador para aterrizar en forma segura. Este es un comportamiento poco prudente. El problema se origina debido a que el planteo y la ejecución están intercalados. Una vez que las precondiciones para un operador son resueltas, la accion es tomada -y *estado* es irrevocablemente cambiado- y esta accion puede eventualmente llevar a terminar muerto. Una alternativa podría ser reemplazar la variable global *estado* con distintas variables de estado locales, de tal modo que una nueva variable es creada para cada nuevo estado. Esta alternativa es buena por otras razones como veremos más adelante.

El problema del sub-objetivo recursivo

En nuestro mundo simulado aquí, hay una sola manera de encontrar un número telefonico: mirarlo en la guia telefonica. Suponga que deseamos agregar un operador para buscar si una guia telefonica y preguntarle a alguien. Por supuesto, para preguntarle a alguien algo, necesitas entrar en comunicación con algo o alguien. El operador preguntar-numero-telefonico podría ser implementado como sigue:

(push (make-op :accion 'preguntar-numero-telefonico

                       :precondiciones '(en-comunicación-con-mercado)

                       :agregar-lista '(conocer-numero-telefonico))

      *ops-escuela*)

La forma especial (push ítem lista) introduce el ítem al frente de la lista eso es equivalente a (setf lista (cons ítem lista)) en un caso simple.

Desafortunadamente, algo inesperado pasa cuando intentamos resolver un problema simple con este nuevo operador. Considere lo siguiente:

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

      '(hijo-en-escuela)

      *ops-escuela*)

*** - Program stack overflow. RESET

El mensaje de error (que variará de acuerdo a la implementación de un Common Lisp a otro) dice que fueron hechas demasiadas llamadas a funciones recursivas anidadas. Esto indica tanto un problema complejo como, más comúnmente, un bug en el programa provocado por recursividad infinita. Una manera de intentar ver la causa del bug es trazar una función relevante, tal como alcanzar-objetivo:

> (trace alcanzar-objetivo)

 Rastreando la función ALCANZAR-OBJETIVO.

(ALCANZAR-OBJETIVO)

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

      '(hijo-en-escuela)

      *ops-escuela*)

...

970. Trace: (ALCANZAR-OBJETIVO 'EN-COMUNICACION-CON-MERCADO)

971. Trace: (ALCANZAR-OBJETIVO 'CONOCER-NUMERO-TELEFONICO)

972. Trace: (ALCANZAR-OBJETIVO 'EN-COMUNICACION-CON-MERCADO)

973. Trace: (ALCANZAR-OBJETIVO 'CONOCER-NUMERO-TELEFONICO)

974. Trace: (ALCANZAR-OBJETIVO 'EN-COMUNICACION-CON-MERCADO)

975. Trace: (ALCANZAR-OBJETIVO 'CONOCER-NUMERO-TELEFONICO)

976. Trace: (ALCANZAR-OBJETIVO 'EN-COMUNICACION-CON-MERCADO)

977. Trace: (ALCANZAR-OBJETIVO 'CONOCER-NUMERO-TELEFONICO)

La salida de trace nos da las pistas necesarias. Newell y Simon hablan sobre "oscilar entre fines, funciones requeridas, y los medios que las ejecutan". Aquí tenemos infinitas oscilaciones entre estar en comunicación con el mercado y conocer el numero telefonico. La razón es la siguiente: queremos al mercado para saber acerca del problema con la bateria, y esto requiere estar en comunicación con algo o alguien. Una manera de obtener una comunicación es el telefono, pero no tenemos una guia telefonica para mirar el número. Deberíamos preguntar su número de telefono, pero esto requiere estar en comunicación con alguien. Como Aristóteles dice, "Si no estamos deliberando siempre, tendremos que avanzar sobre el infinito" Llamaremos a esto el problema del "sub-objetivo recursivo": intentar resolver un problema en términos de sí mismo. Una manera de encarar el problema es tener resueltos todos los objetivos que están siendo trabajados cuando aparece un bucle en la pila de objetivos.

El problema de la falta de información intermedia

Cuando el SGP falla al buscar una solución, solo devuelve nil. Esto es molesto en casos donde el usuario espera una solución a ser encontrada, debido a que eso no da información sobre la causa de la falla. El usuario podría siempre trazar alguna función, así como como trazamos alcanzar-objetivo antes, pero la salida de trace raramente muestra la información deseada. Esto debería ser más amigable, como tener una herramienta de salida donde el programador inserte los estados de impresión dentro de su código, según la información deseada.

La función dbg provee esta capacidad. dbg muestra la salida de la misma manera que format, pero esta solo imprimirá cuando se desee la salida. Cada llamada a dbg es acompañada de un identificador que es usado para especificar una clase de mensaje de salida. Las funciones debug y undebug son usadas para agregar o remover clases de mensaje a la lista de clases que deberían ser impresas. Aquí, todas las salidas usaran el identificador :sgp. Otros programas usaran otros identificadores, y un programa complejo usara muchos identificadores. Una llamada a dbg resultara en salida si el primer argumento para dbg, el identificador, es uno que fue especificado en una llamada a debug. Los otros argumentos para dbg son una cadena format seguida por una lista de argumentos a ser impresos de acuerdo a la cadena format. En otras palabras, escribiremos funciones que incluyen llamadas a dbg tales como:

(dbg :sgp "El objetivo actual es: ~a" objetivo)

Si cambiamos la función de debugging con (debug :sgp), entonces llamara a dbg con el identificador :sgp e imprimirá la salida. La salida es cambiada con (undebug :sgp). debug y undebug están diseñados en forma similar a trace y untrace respectivamente, en que hacen un diagnóstico de la salida. Ellos también siguen la convención que debug sin argumentos, devuelve la lista actual de identificadores, y que undebug sin argumentos, apaga todos los debugging. Sin embargo, ellos difieren de trace y untrace en que son funciones, no macros. Si usas solo claves y enteros para identificadores, entonces no notaras la diferencia.

Dos nuevas características internas son introducidas aquí. La primera, *debug-io* es el stream normalmente usado para hacer debugging de entradas/salidas. En todas las llamadas previas a format hemos usado t como el argumento de stream, que provoca la salida para ir al stream de salida estándar *standard-output*. Enviando diferentes tipos de salida a diferentes stream permite al usuario algo de flexibilidad. Por ejemplo, la salida del debugging podría esta direccionada a una ventana separada, o esta podría ser copiada a un archivo. La segunda es la función fresh-line que avanza a la próxima línea de salida, sin el stream de salida estará listo en el comienzo de la línea.

(defvar *dbg-ids* nil "Identificadores usados por dbg")

(defun dbg (id format-string &rest args)

  "Imprime información de debugging si (DEBUG ID) ha sido especificado."

  (when (member id *dbg-ids*)

    (fresh-line *debug-io*)

    (apply #'format *debug-io* format-string args)))

(defun de-bug (&rest ids)
  "Inicia la salida dbg sobre los ids dados"
  (setf *dbg-ids* (union ids *dbg-ids*)))

(defun undebug (&rest ids)
  "Detiene dbg sobre los ids. Sin ids, detiene dbg para todos"
  (setf *dbg-ids* (if (null ids) nil
    (set-difference *dbg-ids* ids))))

Algunas veces es más fácil ver la salida del debugging si esta indentada de acuerdo a algún patrón, tal como la profundidad de llamadas anidadas para una función. Para generar salidas indentadas, la función dbg-indent es definida:

(defun dbg-indent (id indent format-string &rest args)

  "Imprime información de debugging indentada si (DEBUG ID) ha sido especificado."

  (when (member id *dbg-ids*)

    (fresh-line *debug-io*)

    (dotimes (i indent) (princ " " *debug-io*))

    (apply #'format *debug-io* format-string args)))

Ok! Aca dejo el link del libro de Peter: Inteligencia Artificial. Paradigmas
Para leerlo necesitas el DejaVu: DejaVu
Para el que lo quiera descargar el SGP version 1: GPS1.lisp