Bitacora 05: Logica B2011: Busqueda

Saludos,

Esta semana estamos combinando varios documentos. El capítulo 5 del texto guía está dedicado a "búsqueda", un tema en el que la Inteligencia Artificial tiene una larga y muy rica tradición. Trataré de resumir la idea con un ejemplo similar al del texto, pero que funciona en el computador:

http://webdelprofesor.ula.ve/ingenieria/jacinto/kowalski/capitulo05.html

Pero también comenzamos esta semana a revisar el capítulo A1 del texto guía, que explica la sintaxis de las formas lógicas que estudiamos en el curso. Un objetivo de revisar ese capítulo es conocer cómo se suele codificar el conocimiento en los diversos sabores de lógica, incluyendo la computacional. Avanzamos apenas hasta la página 9, por una razón que explico a continuación:

http://webdelprofesor.ula.ve/ingenieria/jacinto/kowalski/lcph-cap-a1.pdf

Pero para no perder de vista el objetivo superior de conocer la semántica asociada a esa sintaxis, comenzamos a revisar el capítulo 1 de mi libro: lógica práctica y aprendizaje computacional, hasta la sección sobre validez!.

http://webdelprofesor.ula.ve/ingenieria/jacinto/libros/logica-practica-aprendizaje-computacional.pdf

Les suplico que lean con cuidado esa primera parte de mi libro, hasta la página 20, sección 1.2.1, y nos preparemos para discutir el tema de validez en lógica. Suele ser una fuente de confusión por varias razones.

Es muy probable que NO tengamos clase presencial la próxima semana. Les confirmo tan pronto pueda. Nos invitaron a un evento académico en Caracas. Si así fuese, podríamos usar la semana para discutir los avisos de las colas y ese tema de validez, por vía de la lista. Voy a insistir que envíen sus contribuciones a todos en la lista. También sirve el blog. Pero no olviden que no es un asunto de todos contra uno. Es uno asunto de todos contra todos en el que no necesariamente domina la mayoría.

Permítanme volver con el problema de búsqueda. Como he dicho varias veces, es un tema tradicional en inteligencia artificial. Se construye una máquina, normalmente el software de la máquina, para que pueda buscar la solución de un problema recorriendo, en su "mente" un espacio de posibilidades que podría ser infinito. Hay muchas realizaciones de esas máquinas. Incluso existe una taxonomía de soluciones que comienza con las alternativas muy gruesas de 1) búsqueda por fuerza bruta y 2) búsqueda informada.

En este curso tenemos una gran ventaja inicial. Prolog es una máquina de búsqueda que utiliza una forma de razonamiento hacia atrás: la regla de resolución, para revisar un espacio que se construye a partir de una base de conocimiento, buscando cómo probar un teorema (y subteoremas, que son como metas y submetas).

Consideren el ejemplo que construimos en clase y que es muy cercano a la descripción del ejemplo de las vacacaciones del profesor Kowalski:

--
% busqueda.pl
%

ir(A,B) :- juntos(A,B).
ir(A,B) :- juntos(A,C), ir(A,C), ir(C,B).
--

A esta implementación de las reglas generales para ir de un punto a otro tenemos que agregarle la descripción particular de nuestra "geografía". Entre comillas porque, como verán, puede ser una "geografía ideal" (geografía de ideas!). Algo como esto:

--
juntos(pobre, estudiante).
juntos(pobre, ladron).
juntos(estudiante, profesional).
juntos(ladron, rico).
juntos(profesional, rico).
--

Ese programa puede decirnos si es posible ir de pobre a rico:

--
?- ir(pobre, rico).
true
--

aunque no nos dice cómo. Para hacer explícito el camino, consideren esta versión de las mismas reglas con un argumento auxiliar:

--
ir(A,B,[B]) :- juntos(A,B).
ir(A,B,[C|Camino]) :- ir(A,C,[C]), ir(C,B,Camino).
--

ahora si podemos saber el cómo:

--
?- ir(pobre, rico, Como).
Como = [estudiante, profesional, rico]
--

Este programa, como ven, sirve para encontrar una solución. Pero si le pido, como hice descuidadamente en clase, otra solución (con Prolog eso se hace escribiendo punto y coma ";" justo después del true) el programa cae en un ciclo infinito. Esto ocurre porque Prolog usa un algoritmo de fuerza bruta, primero en profundidad, para encontrar las soluciones. Sin ayuda adicional (sin más información), cae en un ciclo, después de la primera respuesta.

Noten, antes de que decidan olvidar ese código y a Prolog, que el programa puede ayudarnos a verificar si la otra solución que a alguien se le pudiera ocurrir también es un "Como":

--
?- ir(pobre, rico, [ladron, rico]).
true
--

Es decir, la lógica es infalible. Lo que falla acá es la estrategia de búsqueda sobre esas reglas lógicas.

Pero incluso esto se puede corregir en Prolog. Noten esta versión de uno de los códigos del Prof. Bratko en:

http://webdelprofesor.ula.ve/ingenieria/jacinto/logica/manual-prolog/grafos-prolog.html

--
% ir_sin_ciclos
ir_sin_ciclos(Start,Stop,Camino) :-
    ir(Start,Stop,[Start],Camino).

ir(Stop,Stop,Camino,Camino).
ir(Start,Stop,ActCamino,Camino) :-
       Start\=Stop,
       juntos(Start,Proximo),
       no_miembro(Proximo,ActCamino),
       ir(Proximo,Stop,[Proximo|ActCamino],Camino).

no_miembro(_,[]).
no_miembro(X,[Y|T]) :-
       X\=Y,
       no_miembro(X,T).
--

Este programa no es estructuralmente muy distinto a nuestro primer código. Sin embargo, no tiene problemas con los ciclos y calcula todas las respuestas que necesitamos (noten que el camino se muestra al revés):

--
?- ir_sin_ciclos(pobre, rico, Camino).
Camino = [rico, profesional, estudiante, pobre] ;
Camino = [rico, ladron, pobre] .
--

Confío que el ejemplo les dé una idea de qué es buscar en este contexto. Les sugiero que lo prueben Uds mismos en Prolog y reconstruyan el árbol de búsqueda que Prolog recorre al ejecutarlo. Así es como se genera un espacio de búsqueda infinito a partir de un código finito.

Muy pendiente a sus preguntas y comentarios,

Gracias,

Jacinto