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 T₀, y luego alcanzar Y antes que T₂ pero no antes que T₁. 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.