En el trabajo práctico número 1 de Inteligencia Artificial, tuvimos que programar un pacman para que actuara en un ambiente donde había enemigos y alimento. Debíamos utilizar alguna estrategia de búsqueda.
En este tipo de estrategias, para encontrar una buena acción a llevar a cabo, el agente genera un árbol. El nodo principal representa el estado inicial del mismo. Por ejemplo, dicho estado indica que está en la posición (X,Y), con una cantidad determinada de energía y el conocimiento de N celdas. El agente aplica las acciones que son posibles en este nodo (estado), y así genera más nodos, que serán los hijos del primero, por cada una de las acciones aplicadas. Esto representa la expansión del nodo principal.
Así el agente va expandiendo nodos. Una vez que lo hace con el nodo principal, tiene que elegir otro. Y aquí es justamente donde difiere cada estrategia. Por lo demás, son idénticas. Algunas de las formas de ir eligiendo los nodos podría ser por profundidad, amplitud, o costo uniforme. En esta última existe un costo por cada acción, y la estrategia elije el siguiente nodo a expandir según cuál tenga el menor costo. Otra estrategia es la avara, la cual en lugar de utilizar un costo para los nodos, usa una heurística, que indica qué tan lejos del objetivo está, entonces toma una decisión según la acción que más lo acerque al mismo.
Volviendo al tema del post, en el trabajo práctico teníamos que mostrarle a los profesores que nuestro código funcionaba correctamente, es decir, si habíamos elegido la estrategia de amplitud, entonces la lista de nodos expandidos tenía que tener un orden de acuerdo a la misma. Una forma de hacerlo era escribir un archivo XML que vaya indicando cómo se forma el árbol y qué nodos se eligen. Pero es un poco tedioso leer un archivo así.
Estaría muy bueno que al correr el simulador se dibuje un árbol, por ejemplo en PDF, con los nodos que han sido elegidos por el algoritmo implementado, mostrando información de los mismos y qué acciones fueron tomadas para llegar a ellos. Esto parece complicado, pero no lo es si utilizamos LaTeX y el paquete qtree.
Lo que debemos hacer es guardar en una cola los nodos que el algoritmo fue expandiendo, es decir, eligiendo. También hay que pensar en un número de niveles a dibujar, que coincide por supuesto con los nodos elegidos para expandir. El código siguiente, en Java, escribe el documento LaTeX completo, listo para compilar:
private void toLatex(LinkedList nodosSeleccionados, int niveles) {
/* Salida para latex (genera un arbol usando el paquete qtree). El
* siguiente código genera el documento completo para compilar. Sólo
* hay que disponer de los paquetes necesarios. */
// Clase del documento y opciones generales
Busqueda.logLatex.debug("\\documentclass[a0,landscale]{a0poster}");
// Paquetes utilizados
Busqueda.logLatex.debug("\\usepackage{mathptmx}");
Busqueda.logLatex.debug("\\usepackage[scaled=.90]{helvet}");
Busqueda.logLatex.debug("\\usepackage{courier}");
Busqueda.logLatex.debug("\\usepackage{qtree}");
Busqueda.logLatex.debug("\\usepackage{nodo}");
Busqueda.logLatex.debug("\\usepackage[spanish]{babel}");
Busqueda.logLatex.debug("\\usepackage[utf8]{inputenc}");
Busqueda.logLatex.debug("\\title{Árbol de ejecución - Estrategia: " +
this.nombreEstrategia() + "}");
Busqueda.logLatex.debug("\\author{}");
Busqueda.logLatex.debug("\\begin{document}");
Busqueda.logLatex.debug("\\maketitle");
StringBuffer sf = new StringBuffer();
int cuentaArboles = 0;
int nivelesProcesados = 0;
for (Nodo unNodo : nodosSeleccionados) {
if (cuentaArboles == 0)
sf.append("\\begin{figure}[!h]\n");
sf.append("\\Tree " + unNodo.toQtree() + "\n");
cuentaArboles++;
if (cuentaArboles == 4) {
cuentaArboles = 0;
sf.append("\\end{figure}\n");
}
nivelesProcesados++;
if (nivelesProcesados >= niveles)
break;
}
if (cuentaArboles > 0)
sf.append("\\end{figure}");
sf.append("\n");
Busqueda.logLatex.debug(sf.toString());
Busqueda.logLatex.debug("\\end{document}");
}
Sólo hay que colocar el documento generado (nosotros utilizamos log4j para las salidas) junto a los archivos de qtree. Claro que no genera el árbol en la forma estándar (debido a cómo el paquete dibuja los árboles), sino que toma un nodo (por ejemplo el primero elegido, que vendría a ser la raíz), lo dibuja junto a sus hijos, luego pasa al siguiente nodo expandido y lo dibuja en un subárbol aparte con sus hijos, y así sucesivamente.
De esta forma, es mucho más cómodo visualizar el funcionamiento de nuestro algoritmo, que implementa alguna estrategia de búsqueda, que seguir con la vista un críptico archivo de texto. Los árboles generados se leen de izquierda a derecha, de arriba a abajo. Este orden de lectura, como mencioné antes, representa la secuencia de nodos que el algoritmo fue eligiendo para expandir.
Algunos ejemplos de archivos PDF generados…