Asi que quede claro: yo no he escrito el articulo original, no he probado nada de lo que se dice en el y lo hago con fines puramente academicos
Si alguien tiene algo que comentar, correcciones, notas adicionales y demas, los comentarios estan abiertos, aunque a partir de hoy estare unos 15 dias sin internet asi que no podre leerlos ni contestar.
y, sin mas preambulos, que lo disfruteis.
</Disclaimer>
Robots y Laberintos en Java
Los simuladores de robots pueden ser importantes herramientas de investigacicon y, como muestra el desarrollador de IBM Paul Reiners en este articulo, un camino hacia la diversion con el lenguaje de programacion Java. Descubre como crear robots virtuales que buscan fuentes de luz y resuelven laberintos usando Simbad, un simulador de robots open source basado en la tecnologia Java 3D, para realizar disenios de robots basados en el concepto de arquitectura de subsuncion[1]
Introduccion
La robotica es un campo que dejo de pertenecer a la ciencia-ficcion hace tiempo para pasar a formar parte de los avances de la automatizacion industrial, cuidados medicos, exploracion espacial y otras aplicaciones. Los simuladores de robots por software no solo simplifican el trabajo de desarrollo para los ingenieros en robotica, tambien proveen a los investigadores de una herramienta para estudiar algoritmos de inteligencia artificial y aprendizaje mecanizado. Uno de esos simuladores centrados en la investigacion es el proyecto de codigo abierto Simbad, basado en la tecnologia Java3D. Este articulo muestra como programar robots virtuales usando las herramientas de Simbad para crear disenios roboticos basados en la arquitectura de subsuncion.
Este articulo comienza con una breve descripcion de la robotica y explica el concepto de arquitectura de subsuncion. Despues presenta el entorno Simbad y muestra como implementar con el una arquitectura de subsuncion. Despues, programaras un robot simple usando esta arquitectura. Para terminar, echaremos un vistazo al fascinante mundo de los laberintos y programaras un segundo robot que, a diferencia de Homer Simpson, puede encontrar la salida de un laberinto. Tus robots no seran reales, existiran dentro del mundo virtual de Simbad.
Programacion robotica
La palabra Robot no tiene una definicion universal aceptada. Para el proposito de este articulo, consideraremos que un robot tiene tres partes:
* Una serie de sensores
* Un programa que define el comportamiento del robot
* Una serie de actuadores
Robotica tradicional
En la robotica tradicional (esto es, en la robotica antes de 1986), un robot tendria un “cerebro” central que construye y mantiene un “mapa” del mundo y hace planes basados en dicho mapa. Primero, los sensores del robot, por ejemplo sensores de tacto, de luz o infrarojos, toman informacion de su entorno. El cerebro del robot fusiona toda esa informacion recogida por sus sensores y actualiza el mapa de su mundo. El robot, entonces, decide que accion tomar y la ejecuta a traves de sus actuadores. Los actuadores son, basicamente, motores y estan montados junto a los efectores[2], que interactuan con el entorno del robot. Ejemplos de efectores son ruedas y brazos. (El termino actuador se usa comunmente para indicar tanto actuadores como efectores)
Resumiendo, un robot tradicional toma las entradas de, posiblemente, multitud de sensores, fusiona esa informacion, actualiza su mapa del mundo, traza un plan de acuerdo al punto de vista actual del mundo y despues actua. Aun asi, este metodo es problematico, para empezar porque es computacionalmente intensivo, pero tambien porque mantener un mapa del mundo es dificil porque el mundo esta continuamente cambiando. Ademas, muchos organismos, como los insectos, viven sin un mapa de su mundo externo y hasta sin memoria. Es quizas mejor intentar emularlos? Estos problemas dieron lugar a un nuevo estilo de robotica, llamada robotica basada en el comportamiento (BBR), BBR es, quizas, la filosofia dominante en los laboratorios de robotica actuales.
Arquitectura de Subsuncion
La BBR puede ser implementada usando una arquitectura de subsuncion. Su inventor, Rodney A. Brooks, ahora jefe del laboratorio de IA del MIT, la introdujo en su articulo de 1986, “Los elefantes no juegan al ajedrez”. Los robots basados en el comportamiento se construyen basados en un grupo de comportamientos simples e independientes. Dichos comportamientos estan definidos por los estimulos que los activan (generalmente una lectura de los sensores) y las acciones que toman (que generalmente tienen que ver con efectores). Los comportamientos se definen en capas, unos encima de otros. Cuando dos comportamientos coinciden, un arbitro central decide cual deberia realizarse primero. El comportamiento final del robot es emergente y, de acuerdo a los defensores de la BBR, puede ser mayor que la suma de sus partes. Los comportamientos emergentes de alto nivel asumen a los de bajo nivel. Mas que intentar diseniar un robot, simplemente se definen sus comportamientos y se mira a ver que sale.
Simbad: Un entorno de simulacion de robots
Simbad permite simular robots a base de software. De acuerdo a la pagina web del proyecto, “permite a los programadores escribir sus propios controladores de robots, modificar el entorno y usar los sensores disponibles. Esta dedicado principalmente a investigadores/programadores que quieren una base simple para estudiar Inteligencia Artificial Situada, Aprendizaje Mecanizado y mas algoritmos generales de IA en el contexto de la robotica y los agentes autonomos”.
Simbad esta escrito en el lenguaje Java por Louis Hugues y Nicolas Bredeche. El proyecto, disponible en SourceForge.net, es libre para usar y distribuir de acuerdo a las condiciones de la licencia GNU GPL.
Detalles Tecnicos
Un mundo de Simbad puede contener Agentes (robots) y objetos inanimados (cajas, paredes, luces y demas). El tiempo en el mundo de Simbad esta marcado por untervalos discretos. Simbad planifica y maneja el tiempo compartido entre Agentes. Como los robots fisicos, los Agentes de Simbad tienen sensores (de distancia, tacto, luz y demas) y actuadores (normalmente ruedas). El robot puede actuar en cada intervalo de tiempo.
Los Agentes sobreescriben el metodo performBehaviour() para determinar su comportamiento. En performBehaviour() un robot puede tomar nota de las lecturas de los sensores y cambiar su velocidad de rotacion y translacion. performBehaniour() ocurre en un momento, asi que no puede ejecutar acciones como “recorre un metro hacia delante”. Para resolver esta limitacion, generalmente tendras que tomar nota del estado de tu robot. Tambien puedes usar una variable que mida el numero de intervalos que tu robot ha estado en el actual estado.
La API de Simbad
Para los ejercicios de este articulo solo tendras que conocer dos paquetes de la API de Simbad
* simbad.sim : Las clases de este paquete representan tanto a tu robot como al mundo en el que vive. Incluye (entre otras):
o Agent: Los Agentes son robots.
o Arch: Un arco que tu robot puede rodear o pasar por debajo
o Box: Pueden ser usados como obstaculos en el mundo de tu robot
o CameraSensor: Permite ver el mundo del robot desde su punto de vista.
o EnvironmentDescription: Representa el “mundo” al cual aniades Agentes y objetos como paredes y cajas.
o LampActuator: Una lampara que puedes aniadir a tu robot
o LightSensor: Miden la intesidad de la luz
o RangeSensorBelt: Contiene una serie de sensores de distancia.
o RobotFactory: Se usa para aniadir sensores al robot
o Wall: Otro tipo de obstaculo para el robot.
* simbad.gui : Las clases de este paquete muestran el mundo de tu robot y te permiten controlarlo. Incluye (entre otras):
o Simbad: El marco que muestra el mundo del robot, la entrada de los sensores y sus controles.
Implementar una arquitectura de subsuncion en Simbad
Para empezar a implementar una arquitectura de subsuncion en Simbad tienes que definir una subclase de Agent, llamada BehaviorBasedAgent. BehaviorBasedAgent contiene un array de comportamientos y una matriz booleana que indica que comportamientos suprimen a que otros comportamientos:
private Behavior[] behaviors;
private boolean suppresses[][];
BehaviorBasedAgent actua como un planificador de Behaviours. El siguiente codigo recorre los comportamientos (usando la variable de clase currentBehaviorIndex para tomar nota de que comportamiento deberia ir despues) y arbitra entre ellos:
protected void performBehavior() {
boolean isActive[] = new boolean[behaviors.length];
for (int i = 0; i < isActive.length; i++) {
isActive[i] = behaviors[i].isActive();
}
boolean ranABehavior = false;
while (!ranABehavior) {
boolean runCurrentBehavior = isActive[currentBehaviorIndex];
if (runCurrentBehavior) {
for (int i = 0; i < suppresses.length; i++) {
if (isActive[i] && suppresses[i][currentBehaviorIndex]) {
runCurrentBehavior = false;
break;
}
}
}
if (runCurrentBehavior) {
if (currentBehaviorIndex < behaviors.length) {
Velocities newVelocities = behaviors[currentBehaviorIndex].act();
this.setTranslationalVelocity(newVelocities .getTranslationalVelocity());
this .setRotationalVelocity(newVelocities .getRotationalVelocity());
}
ranABehavior = true;
}
if (behaviors.length > 0) {
currentBehaviorIndex = (currentBehaviorIndex + 1)
% behaviors.length;
}
}
}
Fijate en que performBehavior() sobreescribe simbad.sim.Agent.performBehavior().
Behav ior tiene dos metodos abstractos:
Behavior has two abstract methods:.
* isActive() devuelve un valor booleano dependiendo de si deberia estar activo, teniendo en cuenta el estado actual de los sensores (todos los comportamientos comparten un grupo de sensores)
* act() devuelve un par de velocidades, de translacion y de rotacion (en este orden) que indica la accion que el motor debe tomar.
Ejemplo: Un robot vagabundo en busca de luz
Ahora crearas un robo de ejemplo que tiene cuatro comportamientos (en orden de precedencia descendente), mostrado en los trozos de codigo a continuacion.
* Avoidance: Cambia la direccion despues de chocar o para evitar la colision.
* LightSeeking: Se mueve hacia la luz.
* Wandering: Cambia de direccion al azar de vez en cuando.
* StraightLine: Se mueve en una linea recta.
public boolean isActive() {
return getSensors().getBumpers().oneHasHit()
|| getSensors().getSonars().oneHasHit();
}
public Velocities act() {
double translationalVelocity = 0.8;
double rotationalVelocity = 0;
RangeSensorBelt sonars = getSensors().getSonars();
double rotationalVelocityFactor = Math.PI / 32;
if (getSensors().getBumpers().oneHasHit()) { // if ran into something
translationalVelocity = -0.1;
rotationalVelocity = Math.PI / 8
- (rotationalVelocityFactor * Math.random());
} else if (sonars.oneHasHit()) { // reads the three front quadrants
double left = sonars.getFrontLeftQuadrantMeasurement();
double right = sonars.getFrontRightQuadrantMeasurement();
double front = sonars.getFrontQuadrantMeasurement(); // if obstacle near
if ((front < 0.7) || (left < 0.7) || (right < 0.7)) {
double maxRotationalVelocity = Math.PI / 4;
if (left < right)
rotationalVelocity = -maxRotationalVelocity
- (rotationalVelocityFactor * Math.random());
else
rotationalVelocity = maxRotationalVelocity
- (rotationalVelocityFactor * Math.random());
translationalVelocity = 0;
} else {
rotationalVelocity = 0;
translationalVelocity = 0.6;
}
}
return new Velocities(translationalVelocity, rotationalVelocity);
}
public boolean isActive() {
float llum = getSensors().getLightSensorLeft().getAverageLumina nce();
float rlum = getSensors().getLightSensorRight().getAverageLumin ance();
double luminance = (llum + rlum) / 2.0; // Seek light if it’s near.
return luminance > LUMINANCE_SEEKING_MIN;
}
public Velocities act() { // turn towards light
float llum = getSensors().getLightSensorLeft().getAverageLumina nce();
float rlum = getSensors().getLightSensorRight().getAverageLumin ance();
double translationalVelocity = 0.5 / (llum + rlum);
double rotationalVelocity = (llum – rlum) * Math.PI / 4;
return new Velocities(translationalVelocity, rotationalVelocity);
}
public boolean isActive() {
return random.nextDouble() < WANDERING_PROBABILITY;
}
public Velocities act() {
return new Velocities(0.8, random.nextDouble() * 2 * Math.PI);
}
public boolean isActive() {
return true;
}
public Velocities act() {
return new Velocities(0.8, 0.0);
}
private void initBehaviorBasedAgent(BehaviorBasedAgent behaviorBasedAgent) {
Sensors sensors = behaviorBasedAgent.getSensors();
Behavior[] behaviors = { new Avoidance(sensors),
new LightSeeking(sensors), new Wandering(sensors),
new StraightLine(sensors), };
boolean subsumes[][] = { { false, true, true, true },
{ false, false, true, true }, { false, false, false, true },
{ false, false, false, false } };
behaviorBasedAgent.initBehaviors(behaviors, subsumes);
}
El metodo initBehaviorBasedAgent() especifica que comportamientos suprimen a cuales.
Fijate que aunque los comportamientos en este ejemplo tienen un orden total de precedencia (o supresion), no es necesario que sea asi.
Como ejercicio, quizas podrias probar lo siguiente:
* Aniade un comportamiento social: moverse hacia amigos y huir de enemigos.
* Aniade un comportamiento para evitar la luz.
* Aniade luces a algunos robots, para que se atraigan unos a otros.
Laberintos
“Finalmente! Sabia que podriamos solucionar este laberinto usando el algoritmo de Tremaux!” Lisa Simpson
De todos los algoritmos que solucionan laberintos, los dos mas usados consumen un espacio de memoria constante independientemente del tamanio del laberinto. Estos son “seguir paredes” y el algoritmo de Pledge (inventado por Jon Pledge en Inglaterra a los 12 anios). El algoritmo de Tremaux (el elegido por Lisa Simpson) es un algoritmo excelente pero, para simplificar, este articulo se centra en los dos anteriormente mencionados.
Siguiendo paredes
Seguir paredes es un algortimo de laberitnos simple que puede que hayas aprendido de ninio. todo lo que tienes que hacer para solucionar un laberinto usando este algortimo es mantener tu mano izquierda en la pared izquierda (o la mano derecha en la pared derecha) y simplemente seguir hasta que salgas del laberinto. Es facil ver que este algoritmo siempre funciona si el laberinto tiene una entrada y una salida en el borde. Sin embargo, si el final esta en una isla, una parte del laberinto que esta desconectada del resto este algoritmo no puede encontrar una solucion porque no puede “saltar” a la isla.
El algortimo de Pledge
El algortimo de Pledge es mas sofisticado que el de seguir paredes y resuelve un grupo mayor de laberintos porque permite saltar entre islas. La idea basica del algoritmo de Pledge es que tienes que tomar una direccion absoluta (como norte, sur, este u oeste) y tratar de ir siempre en dicha direccion. Llamaremos a esta direccion la direccion favorita. Cuando te encuentres con un muro, giras a la derecha y sigues las paredes con la mano derecha hasta que vuelvas a estar en la direccion favorita y la suma total de giros sea cero (giros en el sentido de las agujas del reloj son considerados negativos y los contrarios a las agujas del reloj, positivos). En ese punto, continuas recto en la direccion favorita y vuelta a empezar. El requisito de que los giros sumen cero son necesarios para que no te quedes atrapado en ciertos bucles, como por ejemplo uno con forma parecida a la letra G (intentalo sobre el papel para ver de que hablo)
Algernon: Un robot solucionador de laberintos
Es hora de asombrar a tus amigos y construir un robot solucionador de laberintos llamado Algernon
Diseniando el robot
Para implementar tanto a un seguidor de paredes como el algoritmo de Pledge, necesitas saber cuando se llega a una interseccion y las direcciones de los pasillos que salen de ella.
Hay mas de una manera de conseguir esto, pero en este caso lo haras montando un sonar en el lado derecho del robot. Este sensor te avisara cuando el laberinto tenga pasillos que salen de la derecha. Para saber cuando se llega a un callejon sin salida (esto es, cuando el robot choca con una pared), necesitaras aniadir sensores de tacto en la parte delantera del robot.
Programando “Seguir Paredes”
Algernon se programa usando el paquete algernon.subsumption, Algernon es bastante simple, comparado con otros robots y podrias programarle directamente de una manera procedural. Sin embargo, usando programacion subsumida hace que el codigo sea mucho mas claro, mas modular y mas facil de entender hasta en un robot tan simple como este.
Para simplificar la implementacion de algoritmo, asumire que las paredes estan puestas en angulos rectos. Asi todos los giros del robot seran de 90 grados hacia la derecha o de 90 grados a la izquierda.
Si te basas en el algoritmo de seguir paredes (usando la mano derecha), veras que se puede descomponer en cuatro comportamientos
* Ir recto
* Cuando chocas con una pared, girar a la izquierda
* Si ves un pasillo a la derecha, girar a la derecha.
* Parar cuando llegues al final.
Necesitaras decidir la prioridad de los cuatro comportamientos. La anterior lista es correcta en orden de prioridad decreciente. Al final tendras cuatro clases, cada una de ellas extendera Behavior.
* GoStraight
* TurnRight
* TurnLeft
* ReachGoal
GoStraight. TRANSLATIONAL_VELOCITY es una constante inicializada a 0.4):
public boolean isActive() {
return true;
}
public Velocities act() {
double rotationalVelocity = 0.0;
return new Velocities(TRANSLATIONAL_VELOCITY, rotationalVelocity);
}
TurnRight. getRotationCount() devuelve el numero de intervalos (ticks) del reloj que haran falta para girar 90 grados usando la velocidad rotacional que estes usando:
public boolean isActive() {
if (turningRightCount > 0) {
return true;
}
RangeSensorBelt bumpers = getSensors().getBumpers(); // Check the front bumper.
if (bumpers.hasHit(0)) {
backingUpCount = 10;
turningRightCount = getRotationCount();
return true;
} else {
return false;
}
}
public Velocities act() {
if (backingUpCount > 0) { // We back up a bit (we just ran into a wall) before turning right.
backingUpCount–;
return new Velocities(-TRANSLATIONAL_VELOCITY, 0.0);
} else {
turningRightCount–;
return new Velocities(0.0, -Math.PI / 2);
}
}
Cuando Algernon gira a la derecha, primero avanza un poco para que su parte trasera no choque con la pared a su derecha. Despues gira a la derecha y, finalmente, necesita avanzar un poco para que la pared este a su derecha.
public boolean isActive() {
if (postGoingForwardCount > 0) {
return true;
}
RangeSensorBelt sonars = getSensors().getSonars(); // Check the sonar on the left.
if (sonars.getMeasurement(1) > 1.0) { // There is a passageway to the left.
preGoingForwardCount = 20;
postGoingForwardCount = 40;
turnLeftCount = getRotationCount();
return true;
} else {
return false;
}
}
public Velocities act() {
if (preGoingForwardCount > 0) {
preGoingForwardCount–;
return new Velocities(TRANSLATIONAL_VELOCITY, 0.0);
} else if (turnLeftCount > 0) {
turnLeftCount–;
return new Velocities(0.0, Math.PI / 2);
} else {
postGoingForwardCount–;
return new Velocities(TRANSLATIONAL_VELOCITY, 0.0);
}
}
ReachGoal:
public boolean isActive() {
RangeSensorBelt sonars = getSensors().getSonars(); // Is there open space all around us? That is, are we out of the maze?
double clearDistance = 1.2;
return sonars.getMeasurement(0) > clearDistance
&& sonars.getMeasurement(1) > clearDistance
&& sonars.getMeasurement(3) > clearDistance
&& sonars.getMeasurement(2) > clearDistance;
}
public Velocities act() { // Stop
return new Velocities(0.0, 0.0);
}
El codigo principal de los comportamientos de Algernon:
private void initBehaviorBasedAgent(
algernon.subsumption.BehaviorBasedAgent behaviorBasedAgent) {
algernon.subsumption.Sensors sensors = behaviorBasedAgent.getSensors();
algernon.subsumption.Behavior[] behaviors = { new ReachGoal(sensors),
new TurnLeft(sensors), new TurnRight(sensors),
new GoStraightAlways(sensors) };
boolean subsumes[][] = { { false, true, true, true },
{ false, false, true, true }, { false, false, false, true },
{ false, false, false, false } };
behaviorBasedAgent.initBehaviors(behaviors, subsumes);
}
Comments (0) 
Themocracy