Angel "Java" Lopez : Inteligencia Artificial, C Sharp

Inteligencia Artifical en C# (1) Primeros Agentes

lopez — Sun, 21 Apr 2013 09:04:59 GMT

Ayer comencé a implementar ejemplos del libro Artificial Intelligence: A Modern Approach, de Stuart Russell y Peter Norvig. Ver el sitio del libro

http://aima.cs.berkeley.edu/

Hay implementaciones en distintos lenguajes:

http://aima.cs.berkeley.edu/code.html (hay en Python, Java, C#, Prolog, Lisp, … )

Mi implementación en

https://github.com/ajlopez/SharpAima

Quiero ir armándola con TDD. Por ahora me baso en la versión en Python, pero puede que también vea la versión en Java, debido a las diferencias de los lenguajes: C# y Java son lenguajes tipados.

La versión que presento hoy es la 0.0.1

https://github.com/ajlopez/SharpAima/tree/0.0.1

Por cada post iré “taggeando” una nueva versión. Mi primer código trata de implementar los primeros agentes descriptos en el capítulo 2. Me basé en el código de:

http://aima-python.googlecode.com/svn/trunk/agents.py

Tengo una solución con dos proyectos: uno de clases y otro de tests:

La idea es tener agentes en un ambiente:

(Adaptado de la figura 2.1 del libro)

El agente recibe percepciones y genera acciones. La primera implementación es:

public abstract class Agent<TLocation, TPerception, TAction>
{
	public TLocation Location { get; set; }

	public int Performance { get; set; }

	public abstract TAction GetAction(TPerception perception);
}

Y las implementaciones en concreto son de un agente robot máquina aspiradora (VacuumAgent y variantes).

Vean la historia del proyecto, cómo fue evolucionando desde TDD. Primero implementé un agente concreto, y luego fue surgiendo la abstracción de arriba. Noten que en C# tenemos que apelar a algo tipado, y de ahí el uso de tipos genéricos: un tipo de agente concreto se define dando el tipo de lugares (location) que maneja (por ejemplo, una posición X, Y, a implementar en la próxima versión), el tipo de percepciones que recibe (ej: “estoy en lugar A y el lugar está limpio”), y el tipo de acciones (“Limpiar”, “Ir a la Derecha”, … ). En Python es más simple, por no tener tipos.

Nos leemos!

Angel “Java” Lopez
http://www.ajlopez.com
http://twitter.com/ajlopez

AjGa: una librería de algoritmos genéticos

lopez — Wed, 28 Jan 2009 07:33:03 GMT

Estuve codificando una librería de algoritmos genéticos, usando C#. El código está en mi proyecto AjCodeKatas en Google Code dentro de:

http://code.google.com/p/ajcodekatas/source/browse/#svn/trunk/AjGa

El proyecto principal es AjGa (con AjGa.Tests para testing):

Las principales interfaces son:

Uso generics, con dos tipos genéricos: G, que es el tipo de implementación de un gen, y V como el tipo al que se evalúa un genoma (por ejemplo, int, double). Con ese valor se catalogan los genomas.

IPopulation es una colección de genomas.

IGenome es una colección de genes, que es evaluado a un valor de tipo V.

IEvaluator está a cargo de evaluar un genoma.

La implementación de IEvolution ejecuta generaciones sobre una población, que va cambiando, usando mutadores, operadores de cruzamiento, para irla modificando después de cada ejecución.

Hay interfaces para generar un genoma, mutar uno existente o hacer cruzamiento de dos genomas.

Para probar estas ideas, implementé un proyecto con gen, genoma, y operadores, que ataca el clásico problema del Travelling Salesman Problem, el vendedor que tiene que visitar una serie de ciudades, minimazando la distancia a recorrrer:

En este ejemplo, el evaluador tiene una lista de posiciones de ciudades a visitar:


    public class Evaluator : IEvaluator<int, int>
    {
        private List<Position> positions;

        public Evaluator(List<Position> positions)
        {
            this.positions = positions;
        }

El tipo de gen acá es int, y cada valor de genoma se expresa como un int. El genoma mantiene una lista de enteros, que representan el número ordinal de las ciudades a visitar:

    using AjGa;

    public class Genome : BaseGenome<int, int>
    {        
        public Genome(int size)
        {
            for (int k = 0; k < size; k++)
            {
                AddGene(k);
            }
        }

Esto es, cada gen es un int, y un genoma con genes 2, 0, 1, representa un viaje que visita la tercera ciudad, pasa por la primera, y termina en la segunda.

Podemos ejecutar el proyecto WinForm, para probar esta implementación:

En la ejecución de arriba, la distribución de ciudades es al azar. Las ciudades pueden ser distribuidas en una grilla:

De esta forma, podemos probar la eficiencia del algoritmo para encontrar un solución óptima, que en el caso de disponer las ciudades en grilla, se conoce de antemano.

Si queremos implementar un nuevo proyecto GA, tenemos que:

- Definir el tipo que tendrán los genes

- Definir el tipo valor a usar

- Escribir operadores (creadores, mutadores, cruzadores) de genomas

Los tests que tengo están en verde:

Buen Code coverage:

En 4 horas tuve la primera versión, gasté 3 horas explorando TSP, y cerca de 8 horas preparando y "tuneando" la aplicación WinForm.

Como de costumbre, ¡me divertí escribiendo este ejemplo!

Nos leemos!

Angel "Java" Lopez
http://www.ajlopez.com
http://twitter.com/ajlopez

Jugando con programas evolutivos

lopez — Tue, 16 Dec 2008 08:59:47 GMT

El fin de semanas, estuve escribiendo un ejercicio casi tipo codekata. Me gusta explorar la idea de programas evolutivos (como agentes con programas incorporados que van evolucionando en ambientes simulados), así que puse manos a la obra, y creé una solución dedicada a experimentar con una ejemplo de prueba de concepto. Está escrito en C#, usando VS 2008, usando el soporte de test de la herramienta. He publicado el código dentro de mi Google code project ajcodekatas en:

http://code.google.com/p/ajcodekatas/source/browse/#svn/trunk/EvolveExample

La solución es EvolveExample:

(Si no tienen el soporte de test de VS, pueden remover el proyecto Evolve.Test).

Las clases principales residen en el proyecto de librería de clases Evolve :

Animal representa un agente. Tiene una lista de Instructions, que son generadas al azar. El animal habita un campo con comida. Su programa tiene instrucciones como Eat, Move East, North, West, South, o Predate (tomar energía/comida de otro animal que esté en la misma celda de la grilla). Cada instrucción tiene un costo: un punto de energía. Eat es una instrucción que toma 10 puntos de energía o menos, tomando comida de la celda actual. Predate toma 100 puntos de energía o menos, restándoselo a otro animal que esté en la misma celda.

Para ver el programa en acción, lanzar el proyecto winform Evolve.GUI, seleccionar la opción Evolve -> Run. Veremos:

El campo es una grilla (en este ejemplo, de 20x20). Cada celda tiene un nivel de comida (verde está llena, negro es vacía). A la derecha, una lista muestra los mejores animales y sus programas. Los animales son rankeados de acuerdo a su nivel de energía al final de cada ronda de simulación. El programa continúa con más simulaciones, usando nuevos campos. En cada nueva simulación, la población es ordenada por energía descendente, y los mejores son incluidos en la nueva simulación, los lugares vacantes son ocupados por mutaciones de esos mejores, y algunos animales son inyectados con programas aleatorios.

Durante una simulación, aparece información sobre el nivel de comida y el animal que mejor se desempaña, al pie de la ventana.

Con las opciones de menú Food y Population podemos establecer el nivel de comida y el número de animales, a usar al comienzo de cada simulación. Estos valores se usan recién la próxima vez que elijamos Evolve -> Run. La opción Evolve -> Stop puede ser usado para terminar una serie de simulaciones.

Próximos pasos

Este es un primer ejemplo, una prueba de concepto que sirva de base. Tengo algunas ideas, para explorar en futuras versiones:

- Tener un conjunto de instrucciones más interesantes, con condicionales, y que sea sensible al ambiente. Me gustaría añadir instrucciones como "Si hay comida en tal dirección, ir hacia allí". En vez de un programa lineal, podría armar un árbol de instrucciones, algo como un programa Lisp.

- Los valores de ejecución (tamaño del campo, nivel de comida, energía inicial para cada animal), deberían poder establecerse por un formulario, y leer y grabarse de archivos XML.

- Serializar los resultados y poblaciones en archivos XML

- Evolución en un cluster. Podría usar AjMessages, AjAgents, o MPI sobre unc luster HPC, para simular evolución en una grilla o cluster de máquinas.

Como es habitual, ¡me divertí escribiendo este código!

Angel "Java" Lopez
http://www.ajlopez.com
http://twitter.com/ajlopez
http://delicious.com/ajlopez

AjLisp: un intérprete Lisp en .NET

lopez — Thu, 31 Jul 2008 13:30:41 GMT

Soy un entusiasta de escribir intérpretes, especialmente del tipo Lisp. Mi primer intérprete Lisp fue escrito al principio de los 80, usando el lenguaje assembler de un Intel 808x. Era un trabajo muy "geek". Una de las características más "tricky" de implementar es un recolector de basura (garbage collector). Por suerte, desde mediados de los 90 tenemos Java y su librería de clases como una tecnología ampliamente disponible con un garbage collector decente. En este siglo, .NET es la nueva plataforma de lenguajes con GC..

En el 2005, Martin Salias y yo dimos un TechNight, aquí en Buenos Aires, Argentina, para la oficina local de Microsoft. Trató sobre lenguajes implementados en .NET. Fue la primera vez que presenté F#, así como P# y otros. Despues de esa charla, la misma noche viajé a Mar del Plata, para dar otra charla sobre ASP.NET. Mar del Plata es una bella ciudad, en frente del océano Atlántico, a la que trato de volver cada año. Entonces, era mi primer visita luego de treinta años. En el viaje, "nació" AjLisp.

Esa versión era un intérprete Lisp escrito en Visual Basic .NET. El pasado domingo, lo porté a C# (usando alguna opción de menú de SharpDevelop, ¿alguna otra herramienta que conozcan?). El código original fue usado hace unas semanas en mi post sobre VPL:

Lisp-like interpreter using DSS and VPL
Intérprete tipo Lisp usando DSS y VPL

La nueva versión C# version está publicada en Google Code en:

http://code.google.com/p/ajlisp/

Me gusta Google Code: tiene soporte de SVN, asi que uso mi cliente local TortoiseSVN para enviar los cambios en el proyecto.

La solución

Tiene tres proyectos:

AjLisp: el proyecto núcleo, una librería, que puede ser invocada desde otra aplicación.

AjLisp.Tests: Todos los tests, usando NUnit 2.2.8. Si no tienen NUnit, pueden remover el proyecto de la solución.

AjLisp.Console: un simple programa de consola.

Los tipos

Una interfaz base es IAtom:

    public interface IAtom
    {
        bool IsAtom();
    }

Otra es IList:

    public interface IList
    {
        SymbolicExpression First
        {
            get;
            set;
        }

        SymbolicExpression Rest
        {
            get;
            set;
        }

        bool IsList();
    }

Todos los tipos derivan de una SymbolicExpression:

namespace AjLisp.Types
{
    public abstract class SymbolicExpression : IList, IAtom
    {
 ....

Implementé los tipos comunes a usar en un Lisp, como List, Atom, Identifier, Function (para invocar a primitivas y funciones generadas por lambdas), True, Nil...:

Existe una clase Environment para mantener valores asociados a nombres. Cada Environment tiene un Environment padre, para mantener una lista de ambientes con valores.

La clase Interpreter es la principal a manejar: tiene un Environment y define algunos nombres para las primitivas iniciales:

    public class Interpreter
    {
        private Environment environment = new Environment();

        public Interpreter()
        {
            Define("nil", Nil.Value);
            Define("t", True.Value);
            Define("cons", new SubrCons());
            Define("first", new SubrFirst());
            Define("car", new SubrFirst());
            Define("rest", new SubrRest());
            Define("cdr", new SubrRest());
            Define("list", new SubrList());
            Define("quote", new FSubrQuote());
            Define("append", new SubrAppend());
            Define("cond", new FSubrCond());
            Define("atom", new SubrAtom());
            Define("eval", new SubrEval());
            Define("null", new SubrNull());
            Define("lambda", new FSubrLambda());
            Define("progn", new FSubrProgN());
            Define("flambda", new FSubrFLambda());
            Define("nlambda", new FSubrNLambda());
            Define("mlambda", new FSubrMLambda());
            Define("numberp", new SubrNumberP());
            Define("functionp", new SubrFunctionP());
            Define("idp", new SubrIdP());
            Define("define", new FSubrDefine());
            Define("definef", new FSubrDefineF());
            Define("definen", new FSubrDefineN());
            Define("definem", new FSubrDefineM());
            Define("eq", new SubrEq());
            Define("if", new FSubrIf());
            Define("let", new FSubrLet());
            Define("lets", new FSubrLetS());
            Define("set", new SubrSet());
            Define("consp", new SubrConsP());
            Define("less", new SubrLess());
            Define("greater", new SubrGreater());
            Define("plus", new SubrPlus());
            Define("difference", new SubrDifference());
            Define("times", new SubrTimes());
            Define("quotient", new SubrQuotient());
            Define("remainder", new SubrRemainder());
        }

....

Uds. pueden escribir sus propias primitivas y agregarlas a este constructor.

Las primitivas

El intérprete tiene las primitivas usuales:

Hay primitivas, que antes de su invocación, evalúan los argumentos recibidos. Son las que derivan de Subr:

    public abstract class Subr : Function
    {
        public abstract SymbolicExpression Execute(SymbolicExpression args, Environment env);

        public override SymbolicExpression Apply(SymbolicExpression form, Environment env)
        {
            return Execute(form.Rest.Evaluate(env), env);
        }
    }

form.First es la función, y form.Rest es la lista de argumentos. Para evaluar el form, Function usa un objeto Environment.

Otras primitivas no evalúan sus argumentos, derivan de FSubr:

    public abstract class FSubr : Function
    {
        public abstract SymbolicExpression Execute(SymbolicExpression args, Environment env);

        public override SymbolicExpression Apply(SymbolicExpression form, Environment env)
        {
            return Execute(form.Rest, env);
        }
    }

Una de las primitivas más interesantes, es la implementación de lambda, llamada FSubrLambda:

    public class FSubrLambda : FSubr
    {
        public override SymbolicExpression Execute(SymbolicExpression args, Environment env)
        {
            return new SubrClosure(args.First, env, args.Rest);
        }
    }

Crea un Closure, una manera de recordar el Environment actual para usarlo en una futura invocación de la expresión lambda. Implementé también NLambda, FLambda, MLambda: N es por NonSpread (maneja su lista de argumentos como si fuera un solo argumento), F es cuando no son evaluados los argumentos antes de la invocación, y M es por Macro (tengo que revisar hasta donde implementé esta "feature").

Los tests

Toda la funcionaliad está cubierta por tests. Configuré el proyecto AjLisp.Test para ejecuter NUnit GUI:

La consola

AjLisp.Console es un simple programa de consola. Pueden ingresar una expresión y la evalúa:

Es tan simple, que hay que usar Control-C para salir... ;-).

Próximos pasos

Hay tanto para hacer. Quiero mejorar algunos puntos:

Reescribir interfaces y clases de base
Manejar e invocar objetos .NET nativos
Tratar a Reales y Enteros por separado (hoy a ambos, al operar, los trata como valores double)
Revisar Macro expansion
Mejor consola
Librería de ejemplos
Un manual mínimo

La idea es llegar a extender este mini lenguaje para ser usado como la base programación de agentes distribuidos. Sería bueno portarlo a Java. Entonces, la conducta de los agentes y su estado puede ser escrito en este lenguaje, y viajar a distintos nodos de la grilla, de forma independiente a la plataforma.

Bueno, son sueños. Ahora, el estado actual: está funcionando, y me divertí escribiéndolo. Disfruten!

(Este artículo es una traducción a Spanish, desde el Anglish (Angel's English) original:
AjLisp- a Lisp interpreter in .NET

)

Angel "Java" Lopez
http://www.ajlopez.com/en