1 Aplicaciones actuales del Lenguaje PROLOG

2 Líneas Futuras

3 Bibliografía

Como hemos visto, programar en Prolog abre nuestras mentes a un nuevo modo de ver la computación. Puede que nos resulte difícil comprender esta técnica, pero nos preocupa, finalmente, más que su dificultad, su utilidad, ya que muchas veces nos preguntamos para qué aprender conceptos que puede que en el futuro no sirvan.

Este capítulo trata de mostrar de forma general la importancia actual que este tipo de paradigmas tiene. En concreto, el paradigma declarativo lógico y, por supuesto, el lenguaje Prolog.

Prolog se puede utilizar para resolver, básicamente, cualquier tipo de problema. Principalmente es útil en la gestión de Juegos, en Inteligencia Artificial y Sistemas Expertos, como lenguaje especialmente pensado para construir bases de conocimientos basados en la lógica que forman parte importante de cualquier agente inteligente, en la construcción de Compiladores e Intérpretes, en el Reconocimiento del Lenguaje Natural, etc.

[ÍNDICE]

La resolución de juegos y la planificación así como la construcción de agentes inteligentes constituyen amplios campos que abarca la rama de la Inteligencia Artificial. A continuación, veremos algunos ejemplos de resolución de juegos y problemas típicos de planificación implementados en Prolog. Podremos observar la facilidad con la que podemos plasmar las especificaciones de los problemas directamente, utilizando una sintaxis que nos proporciona un alto grado de abstracción. Esto nos aporta una gran ventaja a la hora de realizar el desarrollo de la aplicación una vez analizado el problema y diseñada su solución.

[ÍNDICE]

El problema de las ocho reinas y en general de las N reinas, se basa en colocar 8 reinas en un tablero de 8´ 8 (o N en un tablero de N´ N, si el problema se generaliza), de forma que en no puede haber dos piezas en la misma línea horizontal, vertical o diagonal, ver Figura 1.

Este programa has sido muy estudiado por los matemáticos. Se trata de un problema NP-Completo que no tiene solución para N=2 y N=3. Para N=4 tiene una única solución. Para N=8 hay más de 80 soluciones dependiendo de las restricciones que se impongan.

Una forma de abordar el problema se lleva a cabo mediante la construcción de un predicado en Prolog del tipo siguiente: reinas(N, Solucion), donde N representa las dimensiones del tablero y el número de reinas y Solucion es una lista que contiene la permutación de la lista de números que resuelven el problema. Los índices de dicha lista representan la columna en la que se encuentra una reina y el número que almacena la posición o índice representa la fila donde la reina está colocada. Así, para el ejemplo mostrado en la Figura 1, tenemos que R=[2,4,1,3].

Este problema es resuelto, de modo clásico, por el método de prueba y error, luego se adapta perfectamente a un algoritmo de backtracking. Básicamente, el problema se reduce a colocar una reina, e intentar repetir el proceso teniendo en cuenta la reina colocada. Si logramos poner todas las reinas el problema se ha resuelto, en caso contrario, deshacemos lo que llevamos hasta ahora y probamos con otra combinación. Por tanto, hemos de generar un conjunto de permutaciones y seleccionar aquella que cumpla los requisitos impuestos por el juego.

Veamos el código que resuelve el problema:

[FUENTES EN FORMATO ZIP] [EJECUTABLE EXE]

Es muy importante comprender como funciona cada uno de los predicados para entender el funcionamiento del algoritmo general.

Prolog permite implementar los programas casi directamente a partir de las especificaciones realizadas a partir de un análisis y diseño de la solución desde un alto nivel de abstracción. Además el procedimiento de backtracking está implícito en el propio motor de inferencia, luego este paradigma se adapta perfectamente a nuestro problema.

Si analizamos y diseñamos nuestro problema tenemos que la forma de resolverlo se resume en los pasos siguientes:

1. Para N, obtenemos una lista de números comprendidos entre 1 y N: [1,2,3,4,...,N].
2. Obtenemos una permutación del conjunto de números de la lista.
3. Comprobamos que la permutación es correcta.
4. Si la permutación no es correcta, lo que debemos hacer es volver al paso 2 para generar una permutación nueva.

Comencemos a analizar la solución implementada. El problema se resuelve con el predicado reina(N, Solucion):-rango(1,N,L1), permuta(L1,Solucion), correcta(Solucion). Como vemos es, sencillamente, una copia de las especificaciones realizadas más arriba. Se genera el rango entre 1 y N, se obtiene una permutación y se comprueba si la permutación es, o no, correcta. En el caso de que cualquier predicado del consecuente falle, la propia máquina Prolog se encarga de realizar el proceso de backtracking. Con lo cual ya tenemos cubiertos los cuatro pasos fundamentales del algoritmo.

Para tener más claras las ideas, observemos el árbol de ejecución general del objetivo reina(4,Solucion) en la Figura 2.

Para N=4, existe una única solución, aunque si ejecutamos el programa, veremos que se obtienen dos soluciones. La segunda solución es la primera girada, ver Figura 3.

[ÍNDICE]

Analogía es un problema clásico de Inteligencia Artificial diseñado por Evans para resolver cuestiones de analogía geométrica en tests de Inteligencia.

En este tipo de tests de Inteligencia se presentan varias figuras geométricas complejas. Cada figura compleja está formada por figuras más pequeñas unas dentro de otras, a este conjunto lo denominamos Origen. Por otro lado, tenemos otro conjunto de figuras complejas que forman parte del conjunto Respuesta. Se trata, pues, de encontrar una similitud entre las figuras de Origen y las figuras del conjunto Respuesta. La relación entre las figuras de Origen es del tipo A es a B como C es a X, siendo X la solución que puede encontrarse, o no, en el conjunto Respuesta. Si existe en dicho conjunto una figura que satisfaga la anterior afirmación, X se empareja con dicha figura, en caso contrario, hemos de responder que no existe analogía entre el conjunto Origen y el conjunto Respuesta.

Veamos un ejemplo que ilustre todos estos conceptos. Dada la situación de la Figura 4, la respuesta correcta sería 2.

La solución como vemos consiste en aplicar la operación invertir a la figura C. Teniendo en cuenta esto, podemos escribir un programa que resuelva, de forma general, este tipo de analogías. Los pasos fundamentales se exponen a continuación.

1. A debe ser el inverso de B.
2. Eso implica que debemos calcular el inverso de C.
3. Si el inverso de C está en la lista de respuestas, hemos encontrado la respuesta.
4. En caso contrario, volvemos al paso 2 para encontrar otra solución.

La implementación de las figuras complejas es sumamente importante. Por tanto, vamos a definirlas. Las figuras complejas están formadas por dos figuras más simples una dentro de otra. Así la figura A se puede representar mediante el predicado: dentro(cuadro,triangulo).

Una vez que sabemos plasmar dichas figuras, veamos el código fuente del programa Prolog que resuelve este tipo de analogías.

[FUENTES EN FORMATO ZIP] [EJECUTABLE EXE]

Si nos centramos en el predicado analogia vemos que se ajusta, perfectamente, a los pasos generales de resolución del problema expuestos en la fase de análisis-diseño:

Por un lado intentamos casar A y B, esto implica que A debe ser el inverso de B. Si este predicado se cumple, continuamos con la siguiente cláusula del consecuente. Como X no está aún instanciada, X se instancia al valor inverso de C. A continuación, se comprueba si X está en la lista de respuestas. En caso de que esté, analogia termina, si no, analogia mediante backtracking busca una nueva solución, hasta que la encuentre o demuestre que no existe.

test_analogia(Numero, X) es un predicado que permite probar el funcionamiento de analogia para un conjunto de figuras dado. Para testear el predicado diseñado se han seleccionado los tests de la Figura 5.

[ÍNDICE]

Los agentes y sistemas expertos se pueden considerar entes capaces de actuar como lo haría un experto humano en la resolución de un determinado problema. Pueden percibir el ambiente mediante sensores y actúan sobre ese ambiente por medio de efectores. En los agentes hardware, los sensores son sustituidos por cámaras y telémetros y los efectores son reemplazados mediante motores. En los agentes software, las percepciones y acciones vienen a ser las cadenas de bits codificados. La Figura 6 muestra un agente genérico.

Pero, tanto si un agente es hardware o software, necesita un programa que permita transformar los datos provenientes del entorno de usuario en acciones adecuadas para la resolución del problema para el que han sido diseñados.

Estos programas se pueden construir siguiendo multitud de paradigmas, y uno de ellos es la programación lógica, que, como hemos visto, se adapta perfectamente a la representación del conocimiento.

Existen muchos tipos de sistemas expertos: de diagnóstico médico, para el análisis de imágenes de satélite, clasificadores, controladores, asesores, agentes económicos, etc.

Como ejemplo de sistema experto tenemos el programa Prolog que permite conocer la velocidad de un vehículo dadas sus características y las de la vía por la que circula.

Dado que hemos hablado repetidas veces de estos sistemas a lo largo del curso, no vamos a profundizar más en esta cuestión.

[ÍNDICE]

La comprensión del lenguaje natural y la construcción de compiladores e intérpretes son campos de desarrollo muy adecuados para Prolog.

En esta sección vamos a ver una aplicación de la programación lógica a la teoría de autómatas y lenguajes formales.

En Prolog se puede especificar un autómata finito mediante tres hechos, simplemente. El predicado inicial, inicial(Q), es true si Q es el estado inicial. El predicado final(Q) es true si Q es el estado final. Y el predicado delta(Q, X, Q1) que funciona del siguiente modo: es true si el autómata cambia del estado Q al estado Q1 al recibir el símbolo X. El autómata recibe una cadena de símbolos del alfabeto S *. El autómata reconoce el lenguaje si comenzó en el estado inicial y acabó en el estado final tras seguir las transiciones especificadas por d .

Veamos un ejemplo concreto utilizando el lenguaje (ab)*. La Figura 7 representa el autómata que reconoce el lenguaje.

El código del programa Prolog para implementar el reconocedor se expone a continuación.

lista=char*

[FUENTES EN FORMATO ZIP] [EJECUTABLE EXE]

Las trazas de los programas para los casos ab y aa se muestran en la Figura 8.

(a)

(b)

[ÍNDICE]

Como ya hemos comentado, Prolog se puede adaptar a la resolución de casi cualquier tipo de problema con gran facilidad. Aunque, en mi opinión, es ideal como lenguaje de implementación de aplicaciones provenientes del campo de la Inteligencia Artificial.

En este punto, vamos a proponer y resolver algunos problemas típicos que se pueden resolver en Prolog de un modo sumamente sencillo.

[ÍNDICE]

El problema de las torres de Hanoi consiste en mover un conjunto de discos de un palo a otro palo utilizando un palo auxiliar situado en medio. Las reglas para mover los discos son las siguientes:

• No se puede mover más de un disco en cada ocasión.
• No puede quedar un disco de menor radio debajo de un disco de mayor radio.
• Mover el conjunto de discos se puede ver como: mover N-1 discos del palo izquierdo al palo del medio, mover el disco sobrante del palo izquierdo al palo derecho y mover N-1 discos del palo del medio al palo derecho.

El pseudocódigo del algoritmo queda como sigue:

hanoi(N)Þ mover(N,izquierda,medio,derecha).

mover(1,A,_,C)Þ Pasar disco de A a C.

mover(N,A,B,C)Þ mover(N-1,A,C,B), mover(1,A,C), mover(N-1,B,A,C).

La solución del problema de las torres de Hanoi para tres discos y tres palos se muestra en la Figura 9.

[ÍNDICE]

Durante el curso hemos hablado varias veces de agentes inteligentes. Los agentes que funcionan como sistemas de razonamiento son necesarios para obtener resultados eficaces. La principal ventaja que ofrecen es su alto grado de modularidad. Además, es posible independizar la estructura de control del conocimiento, con lo que cada porción del mismo mantiene total independencia entre sí. Actualmente se trabaja en la construcción de agentes inteligentes verdaderamente eficientes tanto hardware como software. Para comprender cuales son las líneas futuras que se pretenden trazar, conviene saber qué se está haciendo en la actualidad, por tanto, vamos a describir brevemente los cuatro grupos principales que componen la clasificicación de los sistemas de razonamiento automático, cada uno diseñado específicamente para resolver distintos tipos de problemas:

• Demostradores de teoremas y lenguajes de programación lógicos. En los demostradoress de teoremas se utiliza la resolución o algún otro procedimiento de inferencia completa para demostrar oraciones expresadas en lógica de primer orden total, frecuentemente en trabajos de razonamiento matemático y de tipo científico. También son empleados para responder preguntas: la demostración de una oración que contiene variables sirve como respuesta a una pregunta debido a que concretiza las variables. Los lenguajes de programación lógicos se caracterizan por restringir la lógica, lo que impide el manejo completo de la negación, la disyunción y/o la igualdad. Por lo general utilizan el encadenamiento hacia atrás, y a veces pueden incluir características no lógicas de los lenguajes de programación (por ejemplo, entrada y salida). Tenemos como ejemplos de demostradores de teoremas a SAM, AURA, OTTER, y como ejemplo de lenguajes lógicos, tenemos PROLOG, MRS, LIFE.
• Sistemas de producción. Estos sistemas, al igual que los lenguajes de programación, utilizan la implicación como elemento primario de representación. El consecuente de cada implicación se interpreta como recomendación de la acción, y no como mera conclusión lógica. Funcionan con una estructura de control de encadenamiento hacia delante. Algunos de ellos cuentan con un mecanismo de resolución de conflictos para decidir qué acción emprender cuando son varias las que se recomienda realizar. Citemos algunos ejemplos: OPS-5, CLIPS, SOAR.
• Sistemas de cuadro y redes semánticas. En estos sistemas se aplica la metáfora de que los objetos son nodos de una gráfica, de que estos nodos se organizan de acuerdo a una estructura taxonómica y de que los vínculos que existen entre los nodos representan relaciones binarias. En los sistemas de cuadro estas relaciones se consideran como ranuras de un cuadro que se llenan mediante otra. En las redes semánticas, en cambio, se consideran como flechas entre un nodo y otro. Tenemos ejemplos de sistemas de cuadro como OWL, FRAIL, KODIAK, y ejemplos de redes semánticas: SNEPS, NETL, Gráficas Conceptuales.
• Sistemas lógicos por descripción: Son la consecuencia de la evolución de las redes semánticas, al ser presionadas para formalizar el significado de las redes, sin dejar de poner énfasis en la estructura taxonómica como principio rector. La idea consiste en emplear como medio de expresión y de razonamiento las definiciones complejas de objetos y clases, así como sus relaciones entre ellos. Los trabajos más recientes se han enfocado al compromiso entra expresividad del lenguaje y complejidad para el cómputo de ciertas operaciones. Tenemos como ejemplos KL-ONE, CLASSIC, LOOM.

Durante el curso, nos hemos centrado en el estudio del primer grupo de la clasificación citada. Los lenguajes lógicos, como ya se ha comentado, ofrecen muchas ventajas y, evidentemente, plantean inconvenientes que deben ser subsanados.

En concreto, si utilizamos un entorno de programación interpretado de Prolog notaremos que la eficiencia, en cuanto a velocidad de ejecución se refiere, disminuye, al igual que en cualquier lenguaje interpretado, frente a un lenguaje compilado.

El conjunto de instrucciones de las computadoras actuales resulta muy pobre en relación con la semántica de Prolog, por lo que la mayoría de los compiladores de Prolog, que también existen, realizan una compilación a un lenguaje intermedio en vez de hacerlo directamente a lenguaje máquina. El lenguaje más popular es el Warren Abstract Machine (WAM), que es un conjunto de instrucciones abstractas utilizable en Prolog y que se puede interpretar o traducir a lenguaje máquina. Existen otros compiladores que traducen Prolog a un lenguaje de alto nivel como Lisp o C, y utilizan dicho compilador para traducir a lenguaje máquina.

Antes del trabajo de Warren sobre la compilación de la inferencia en Prolog, la programación lógica resultaba excesivamente lenta para su uso generalizado. Los compiladores diseñados por Warren y otros permitieron a Prolog alcanzar velocidades adecuadas en estaciones de trabajo promedio modelo 1990. En fechas más recientes, la aplicación de la moderna tecnología de compilación, incluidos inferencia de tipo, codificación abierta y análisis de flujo de datos entre procedimientos ha permitido a Prolog alcanzar velocidades tan óptimas que lo hace competir con C en cuanto a diversos aspectos estándar (Van Roy, 1990). Por supuesto, el hecho de poder escribir un planificador o un analizador de lenguaje natural en unas cuantas decenas de líneas de Prolog, hacen que éste sea más preferible que C en la realización de los prototipos de gran parte de los proyectos de investigación de Inteligencia Artificial a escala reducida.

Aparte de las mejoras que se están realizando en cuanto a velocidad de ejecución también se han desarrollado y se están desarrollando ampliaciones de Prolog que permiten su adaptación a muchos problemas que han surgido recientemente: programación lógica y orientación a objetos, programación concurrente, programación visual y construcción de razonadores completos de lógica de primer orden.

[ÍNDICE]

[Russell, 1996] Russell, Stuart. Norvig, Peter. "Inteligencia Artificial. Un enfoque moderno". Editorial Prentice Hall. 1996.

[Shapiro, 1986] E. Shapiro y L. Sterling. "The art of Prolog". The MIT Press, 1986.

[ÍNDICE]