LeJOS en Mac OSX

Este viene a conformarse como un breve tutorial para hacer funcionar LeJOS en Mac OSX.

Los pasos a seguir son los siguientes:

1.- Bajar e instalar Java.

2.- Bajar e instalar el driver USB de LEGO para Mac OSX.

3.- Bajar, instalar, y configurar LeJOS.

4.- Conectar el brick NXT, y verificar si podemos conectarnos con éste.

1.- Bajar e instalar Java.

En Mac OSX, java viene instalado por default, así que lo único que tenemos que hacer es asegurarnos de que tenemos la última version instalada (para efectos de este tutorial, la versión corresponde a la 1.6 (Update 3)).

Para lo anterior, seleccionamos , y posteriormente la opción de “Software Update”.

2.- Bajar e instalar el driver USB de LEGO para Mac OSX.

El driver que necesitaremos bajar, es el conocido como “Fantom Driver”; este puede ser ubicado en la página de soporte de LEGO Mindstorms.

El driver, puede ser bajado de la siguiente dirección:

http://mindstorms.lego.com/en-us/support/files/Driver.aspx

3.- Bajar, instalar, y configurar LeJOS

Desde la página oficial de LeJOS, descargamos la versión para Linux / Mac OSX:

http://lejos.sourceforge.net/nxj-downloads.php

La carpeta puede ser extraída donde sea; en mi caso, lo he hecho en el directorio Home.

El siguiente paso consiste en configurar las variables de entorno, tanto para Java como para LeJOS; para esto, abrimos la Terminal, e introducimos el siguiente comando:

sudo pico .profile

La línea anterior, nos permitirá crear un archivo denominado .profile, o editarlo en caso de que ya exista. Introducimos nuestro password de administrador, y añadimos las siguientes líneas:

export JAVA_HOME=/System/Library/Frameworks/JavaVM.framework/Versions/1.6.0/Home

export NXJ_HOME=/Users/rafaelochoa/lejos_nxj

export DYLD_LIBRARY_PATH=$NXJ_HOME/bin

export PATH=$PATH:$JAVA_HOME/bin:$NXJ_HOME/bin

En mi caso, mi directorio Home, corresponde a “rafaelochoa”; habrá que modificarlo, según el nombre del directorio que el usuario haya asignado.

La primer línea corresponde a la ruta donde se encuentra instalado JAVA.

La segunda, corresponde a la ruta donde se encuentra localizada la carpeta lejos_nxj

La tercera sólo es necesaria, para hacer uso de una configuración de eclipse que nos hará más fácil tanto la compilación, como la subida de archivos al brick NXT.

La cuarta línea, añade las carpetas correspondientes a los binarios tanto de LeJOS como de Java.

Para salir, tecleamos CTRL + X , Y (Yes) para salvar los cambios,  y enter, confirmando antes, que el nombre del archivo es .profile.

Suponiendo que hemos extraído la carpeta “lejos_nxj” , en el directorio Home, accedemos al directorio “lejos_nxj/bin”:

cd lejos_nxj/bin

Una vez en el directorio, ejecutamos el siguiente comando:

chmod +x *

Para que los cambios que hemos realizado tengan efecto, debemos reiniciar nuestra computadora.

Nota:

Si se tiene instalado Snow Leopard, y LeJOS no funciona, luego de terminar la instalación/configuración, sustituye los archivos de la carpeta lejos_nxt/bin, por los siguientes:

http://www.multiupload.com/V4FOPIVG7Q

Luego de extraer la carpeta, basta con sustuir la carpeta bin original, por la contenida en el archivo .zip.

Si fue necesario hacer la sustición anteriormente mencionada, es necesario volver a cambiar los permisos de la carpeta por medio del comando:

chmod +x *

Los archivos contenidos en el .zip forzan a Java a ejecutarse en un modo de 32 bits, con el fin de ser completamente compatible con LeJOS.

Si se posee una versión anterior a Snow Leopard, este paso no es necesario.

4.- Conectar el brick NXT, y verificar si podemos conectarnos con éste.

Una vez instalado, y configurado el LeJOS, vamos a verificar si nos podemos conectar con éste. Para ello, conectamos el brick con el cable USB, prendemos el brick, y tecleamos el sigueinte comando:

nxjbrowse

Deberá aparecer una ventana como la siguiente:

Le damos click en connect, una vez establecida la conección, podemos decir que ha sido configurado todo lo necesario para poder comenzar a escribir programas, y hacerlos funcionar en nuestro brick NXT.


Finalmente, adjunto una liga para descargar esta misma guía en formato pdf:


http://www.multiupload.com/ESOJ2TYQV6

Mindstorms NXT - LeJOS (Salir de un laberinto)

El objetivo de este ejercicio consiste en programar al robot, para que utilizando el sensor ultrasónico, pueda localizar obstáculos y girar para evitarlos. El robot también se debe programar para que utilizando estas habilidades (localizar obstáculos y girar) pueda salir de un laberinto de ángulos rectos.

Se muestra a continuación un par de fotografías que ilustran el modelo de robot utilizado, para la resolución del problema:

Solución

Como se comentó hace tres entradas, se utilizó para programar al robot, una arquitectura conocida como “subsumption architecture”; para más información acerca de en qué consiste, consultar la entrada del blog mencionada.

En el caso preciso de este ejercicio, se cuenta con una única capa, que representa el “seguir el contorno de una pared/objeto”.

El código para lograr lo anterior, se encuentra divido en dos clases: WallFollower.java, y FollowWall.java,. La primera de ellas actúa básicamente como un activador del comportamiento descrito en el párrafo anterior.

Se muestra a continuación el código de cada una de las dos clases:

WallFollower.java

import lejos.nxt.*;
import lejos.robotics.navigation.*;
import lejos.robotics.subsumption.*;

public class WallFollower { 
 public static void main(String [] args){
  TachoPilot pilot = new TachoPilot(5.6f, 11.25f, Motor.A, Motor.C);
  UltrasonicSensor sonic = new UltrasonicSensor(SensorPort.S3);

  Behavior b1 = new FollowWall(pilot, sonic);
  
  Behavior [] behaviorArray = {b1};
  Arbitrator arbitrator = new Arbitrator(behaviorArray);
  
  LCD.drawString("WallFollower", 2, 2);
  Button.waitForPress();
  arbitrator.start();
 }

}

FollowWall.java

import lejos.nxt.*;
import lejos.robotics.subsumption.*;
import lejos.robotics.navigation.*;

public class FollowWall implements Behavior{
 private TachoPilot pilot;
 private UltrasonicSensor sonic;

 private int distance;
 private int lastDistance;
 private int distanceDifference;
 
 private int veryCloseLeft;
 private int slightlyCloseLeft;
 private int notCloseLeft;
 private int slightlyFarRight;
 private int veryFarRight;
 
 private int basePowerLeft;
 private int basePowerRight;
 
 private Motor rightMotor;
 private Motor leftMotor;

 public FollowWall(TachoPilot pilot, UltrasonicSensor sonic){
  this.pilot = pilot;
  this.sonic = sonic;

  distance = 0;
  lastDistance = 0;
  
  veryCloseLeft = 20;
  slightlyCloseLeft = 25;
  notCloseLeft = 30;
  
  slightlyFarRight = 35;
  veryFarRight = 40;
  
  basePowerLeft = 100;
  basePowerRight = 99;
  
  rightMotor = (Motor)pilot.getRight();
  leftMotor = (Motor)pilot.getLeft();
 }

 public boolean takeControl(){
   LCD.clear();
   LCD.drawString("WallFollow", 2, 2);
   return true;
 }

 public void suppress(){
  pilot.stop();
 }

 public void action(){
  pilot.forward();

  while(true){
   lastDistance = distance;
   distance = sonic.getDistance();
   distanceDifference = lastDistance - distance;
   
   if(distance <= notCloseLeft){
    if(distance <= veryCloseLeft){
     rightMotor.setPower(basePowerRight);
     rightMotor.backward();
     leftMotor.setPower(basePowerRight);
     leftMotor.forward();
    }
    else if(distance <= slightlyCloseLeft){
     rightMotor.setPower(0);
     rightMotor.stop();
     leftMotor.setPower(basePowerLeft);
     leftMotor.forward();
    }
    else if(distance <= notCloseLeft){
     leftMotor.setPower(basePowerLeft);
     leftMotor.forward();
     rightMotor.setPower(0);
     rightMotor.flt();
    }  
   }
   else{
    if(distance >= slightlyFarRight){
     if(distanceDifference < 2){
      leftMotor.setPower(0);
      leftMotor.stop();
      rightMotor.setPower(basePowerRight);
      rightMotor.forward();
     }
    }
    else if(distance >= veryFarRight){
     leftMotor.setPower(basePowerLeft/2);
     leftMotor.forward();
     rightMotor.setPower(basePowerLeft);
     rightMotor.forward();
    }
   }
   try {
    Thread.sleep(30);
   } catch (InterruptedException e) {}
  }
 }
}

Finalmente, se adjunta un par de videos, donde se puede apreciar al robot ejecutando la tarea encomendada:

Mindstorms NXT - LeJOS (Rodear un objeto)

El objetivo de este ejercicio consiste en programar al robot, para que utilizando el sensor de tacto, pueda encontrar, y rodear un objeto siguiendo su contorno. El objeto puede tener cualquier forma (rectangular, como una caja o cilíndrica como un bote), asimismo, el objeto será lo suficientemente pesado como para que el robot no lo mueva, dentro de límites razonables.

Se muestra a continuación un par de fotografías que ilustran el modelo de robot utilizado, para la resolución del problema:

Solución

Como se comentó hace dos entradas, se utilizó para programar al robot, una arquitectura conocida como “subsumption architecture”; para más información acerca de en qué consiste, consultar la entrada del blog mencionada.

En el caso preciso de este ejercicio la capa más baja representa el “moverse hacia delante”; por su parte, la capa más elevada representa el comportamiento de “reconocer que se ha chocado, retirarse del objeto que se tiene enfrente una distancia determinada, rotar de tal manera que el sensor ultrasónico quede mirando en dirección al objeto, y rodearlo”; ésta capa toma control cuando se ha detectado una colisión por medio del sensor de tacto.

El código para lograr lo anterior, se encuentra divido en tres clases: BWallFollower.java, DriveForward.java, y HitWall.java,. La primera de ellas actúa básicamente como un regulador, para decidir qué comportamientos deben ser activados, mientras que las otras dos, aluden a los comportamientos descritos en el párrafo anterior, de manera correspondiente.

Se muestra a continuación el código de cada una de las tres clases:

BWallFollower.java

import lejos.nxt.*;
import lejos.nxt.comm.RConsole;
import lejos.robotics.navigation.*;
import lejos.robotics.subsumption.*;

public class BWallFollower { 
 public static void main(String [] args){
  TachoPilot pilot = new TachoPilot(5.6f, 11.25f, Motor.A, Motor.C);
  TouchSensor touch = new TouchSensor(SensorPort.S1);
  UltrasonicSensor sonic = new UltrasonicSensor(SensorPort.S3);
  
  Behavior b1 = new DriveForward(pilot);
  Behavior b2 = new HitWall(pilot, touch, sonic);
  
  Behavior [] behaviorArray = {b1, b2};
  Arbitrator arbitrator = new Arbitrator(behaviorArray);
  
  LCD.drawString("BWallFollower", 2, 2);
  Button.waitForPress();
  arbitrator.start();
 }

}

DriveForward.java

import lejos.nxt.LCD;
import lejos.robotics.subsumption.*;
import lejos.robotics.navigation.*;

public class DriveForward implements Behavior{
 
 private Pilot pilot;
 
 public DriveForward(Pilot pilot){
  this.pilot = pilot;
 }
  
 public boolean takeControl(){
  LCD.clear();
  LCD.drawString("DriveForward", 2, 2);
  return true;
 }
 
 public void suppress(){
  pilot.stop();
 }
 
 public void action(){
  pilot.forward();
 }

}

HitWall.java

import lejos.nxt.*;
import lejos.robotics.subsumption.*;
import lejos.robotics.navigation.*;


public class HitWall implements Behavior, SensorPortListener{
 private TachoPilot pilot;
 private TouchSensor touch;
 private UltrasonicSensor sonic;
 private boolean hasCollided;

 private int backoff;
 private int rotationAngle;
 private int distance;
 private int lastDistance;
 private int distanceDifference;
 
 private int veryCloseLeft;
 private int slightlyCloseLeft;
 private int notCloseLeft;
 private int slightlyFarRight;
 private int veryFarRight;
 
 private int basePowerLeft;
 private int basePowerRight;
 
 private Motor rightMotor;
 private Motor leftMotor;

 public HitWall(TachoPilot pilot, TouchSensor touch, UltrasonicSensor sonic){
  this.pilot = pilot;
  this.touch = touch;
  this.sonic = sonic;

  hasCollided = false;
  SensorPort.S1.addSensorPortListener(this);

  backoff = 5;
  rotationAngle = -90;
  distance = 0;
  lastDistance = 0;
  
  veryCloseLeft = 20;
  slightlyCloseLeft = 25;
  notCloseLeft = 30;
  
  slightlyFarRight = 35;
  veryFarRight = 40;
  
  basePowerLeft = 100;
  basePowerRight = 99;
  
  rightMotor = (Motor)pilot.getRight();
  leftMotor = (Motor)pilot.getLeft();
 }

 public void stateChanged(SensorPort port, int oldValue, int newValue){
  if(touch.isPressed())
   hasCollided = true;
 }

 public boolean takeControl(){
  if(hasCollided){
   LCD.clear();
   LCD.drawString("HitObject", 2, 2);
   hasCollided = false;
   return true;
  } else
   return false;
 }

 public void suppress(){
  pilot.stop();
 }

 public void action(){
  pilot.stop();
  pilot.travel(-backoff);
  pilot.rotate(rotationAngle);
  
  while(true){
   lastDistance = distance;
   distance = sonic.getDistance();
   distanceDifference = lastDistance - distance;
   
   if(distance <= notCloseLeft){
    if(distance <= veryCloseLeft){
     rightMotor.setPower(basePowerRight);
     rightMotor.backward();
     leftMotor.setPower(basePowerRight);
     leftMotor.forward();
    }
    else if(distance <= slightlyCloseLeft){
     rightMotor.setPower(0);
     rightMotor.stop();
     leftMotor.setPower(basePowerLeft);
     leftMotor.forward();
    }
    else if(distance <= notCloseLeft){
     leftMotor.setPower(basePowerLeft);
     leftMotor.forward();
     rightMotor.setPower(0);
     rightMotor.flt();
    }  
   }
   else{
    if(distance >= slightlyFarRight){
     if(distanceDifference < 2){
      leftMotor.setPower(0);
      leftMotor.stop();
      rightMotor.setPower(basePowerRight);
      rightMotor.forward();
     }
    }
    else if(distance >= veryFarRight){
     leftMotor.setPower(basePowerLeft/2);
     leftMotor.forward();
     rightMotor.setPower(basePowerLeft);
     rightMotor.forward();
    }
   }
   try {
    Thread.sleep(30);
   } catch (InterruptedException e) {}
  }
 }
}

Finalmente, se adjunta un par de videos, donde se puede apreciar al robot ejecutando la tarea encomendada:

Mindstorms NXT - LeJOS (Ubicar y encontrar una fuente de sonido)

El objetivo de este ejercicio consiste en programar el robot, para que utilizando el sensor de sonido (micrófono), pueda ubicar e ir en dirección de una fuente de sonido.

Se muestra a continuación un par de fotografías que ilustran el modelo de robot utilizado, para la resolución del problema:

Solución

Como se comentó en la entrada anterior, se utilizó para programar al robot, una arquitectura conocida como “subsumption architecture”; para más información acerca de en qué consiste, consultar la entrada anterior.

En el caso preciso de este ejercicio la capa más baja representa el “no escuchar a la fuente de sonido”; el robot al encontrarse en esta situación, comienza a hacer giros incrementales, de izquierda a derecha, hasta que vuelve a encontrar la fuente; es en este momento, que toma control la capa más elevada, y que básicamente se encarga de mover al robot hacia delante, mientras lo que el sensor de sonido “escuche”, sea un determinado nivel de decibeles.

El código para lograr lo anterior, se encuentra divido en tres clases: SoundFollower.java, OutOfSound.java, y DriveForward.java. La primera de ellas actúa básicamente como un regulador, para decidir qué comportamientos deben ser activados, mientras que las otras dos, aluden a los comportamientos descritos en el párrafo anterior, de manera correspondiente.

Se muestra a continuación el código de cada una de las tres clases:


SoundFollower.java

import lejos.nxt.*;
import lejos.robotics.navigation.*;
import lejos.robotics.subsumption.*;

public class SoundFollower {
 
 public static void main(String[] args){
  Pilot pilot = new TachoPilot(5.6f, 11.5f, Motor.A, Motor.C);
  SoundSensor sound = new SoundSensor(SensorPort.S3);
  pilot.setTurnSpeed(180);
  
  Behavior b1 = new OutOfSound(pilot, sound);
  Behavior b2 = new DriveForward(pilot, sound);
  Behavior [] behaviorArray = {b1, b2};
  Arbitrator arbitrator = new Arbitrator(behaviorArray);
  
  LCD.drawString("SoundFollower", 2, 2);
  Button.waitForPress();
  arbitrator.start();
 }

}

OutOfSound.java

import lejos.nxt.*;
import lejos.robotics.subsumption.*;
import lejos.robotics.navigation.*;

public class OutOfSound implements Behavior, SensorPortListener{

 private Pilot pilot;
 private SoundSensor sound;
 private int sweep;
 private boolean suppress;
 private boolean outOfSound;

 public OutOfSound(Pilot pilot, SoundSensor sound){
  this.pilot = pilot;
  this.sound = sound;
  suppress = false;
  outOfSound = false;
  SensorPort.S3.addSensorPortListener(this);
 }

 public void stateChanged(SensorPort port, int oldValue, int newValue){
  if(sound.readValue() < 40)
   outOfSound = true;
 }

 public boolean takeControl(){
  if(outOfSound){
   LCD.clear();
   LCD.drawString("OutOfSound", 2, 2);
   outOfSound = false;
   return true;
  } else
   return false;
 }

 public void suppress(){
  suppress = true;
 }

 public void action(){
  sweep = 10;
  while(!suppress){
   pilot.rotate(sweep, true);
   while(!suppress && pilot.isMoving())
    Thread.yield();
   sweep*=-2;
  }
  pilot.stop();
  suppress = false;
 }
}

DriveForward.java

import lejos.nxt.*;
import lejos.robotics.subsumption.*;
import lejos.robotics.navigation.*;

public class DriveForward implements Behavior, SensorPortListener{
 
 private Pilot pilot;
 private SoundSensor sound;
 private boolean heardSound;
 
 public DriveForward(Pilot pilot, SoundSensor sound){
  this.pilot = pilot;
  this.sound = sound;
  heardSound = false;
  SensorPort.S3.addSensorPortListener(this);
 }
 
 public void stateChanged(SensorPort port, int oldValue, int newValue){
  if(sound.readValue() >= 40)
   heardSound = true;  
 }
 
 public boolean takeControl(){
  if(heardSound){
   LCD.clear();
   LCD.drawString("DriveForward", 2, 2);
   heardSound = false;
   return true;
  } else
   return false;
 }
 
 public void suppress(){
  pilot.stop();
 }
 
 public void action(){
  pilot.forward();
  while(sound.readValue() >= 40)
   Thread.yield();
 }

}

Finalmente, se adjunta un video, donde se puede apreciar al robot ejecutando la tarea encomendada:

Mindstorms NXT - LeJOS (Seguir una línea negra)

El objetivo de este ejercicio consiste en programar al robot, para que utilizando el sensor de luz, pueda encontrar, y seguir una trayectoria marcada con una línea negra, pintada sobre una superficie plana.

Se muestra a continuación un par de fotografías que ilustran el modelo de robot utilizado, para la resolución del problema:

La siguiente fotografía corresponde a la trayectoria (marcada por una línea negra) a seguir por el robot:

Solución

En general, para los cuatro ejercicios presentados, como parte de la práctica, se utilizó para programar al robot, una arquitectura conocida como: “subsumption architecture”, la cual consiste básicamente en una arquitectura para robots reactivos, altamente asociada con robótica basada en comportamientos.

En la arquitectura mencionada, se descompone comportamiento inteligente en varios módulos “simples” de comportamiento, los cuales son organizados en capas. Cada capa implementa una meta en particular del agente, y capas más altas, son incrementalmente abstractas. La meta de cada capa subsume la de capas que se encuentran por debajo de ésta. En el caso preciso de este ejercicio la capa más baja representa el estar “fuera de la línea”, donde el robot al encontrarse en esta situación, comienza a hacer giros incrementales, de izquierda a derecha, hasta que se encuentra con una línea negra; es en este momento, que toma control la capa más elevada, y que básicamente se encarga de mover al robot hacia delante, mientras lo que el sensor de luz “vea”, sea una línea negra.

El código para lograr lo anterior, se encuentra divido en tres clases: LineFollower.java, OutOfLine.java, y DriveForward.java. La primera de ellas actúa básicamente como un regulador, para decidir qué comportamientos deben ser activados, mientras que las otras dos, aluden a los comportamientos descritos en el párrafo anterior, de manera correspondiente.

Se muestra a continuación el código de cada una de las tres clases:

LineFollower.java

import lejos.nxt.*;
import lejos.robotics.navigation.*;
import lejos.robotics.subsumption.*;

public class LineFollower {
 
 public static void main(String[] args){
  Pilot pilot = new TachoPilot(5.6f, 11.25f, Motor.A, Motor.C);
  LightSensor light = new LightSensor(SensorPort.S3);
  pilot.setTurnSpeed(180);
  
  Behavior b1 = new OutOfLine(pilot, light);
  Behavior b2 = new DriveForward(pilot, light);
  Behavior [] behaviorArray = {b1, b2};
  Arbitrator arbitrator = new Arbitrator(behaviorArray);
  
  LCD.drawString("Line Follower", 2, 2);
  Button.waitForPress();
  arbitrator.start();
 }

}

OutOfLine.java

import lejos.nxt.*;
import lejos.robotics.subsumption.*;
import lejos.robotics.navigation.*;

public class OutOfLine implements Behavior, SensorPortListener{

 private Pilot pilot;
 private LightSensor light;
 private int sweep;
 private boolean suppress;
 private boolean outOfBlackLine;

 public OutOfLine(Pilot pilot, LightSensor light){
  this.pilot = pilot;
  this.light = light;
  suppress = false;
  outOfBlackLine = false;
  SensorPort.S3.addSensorPortListener(this);
 }

 public void stateChanged(SensorPort port, int oldValue, int newValue){
  if(light.readValue() > 35)
   outOfBlackLine = true;
 }

 public boolean takeControl(){
  if(outOfBlackLine){
   LCD.clear();
   LCD.drawString("OutOfLine", 2, 2);
   outOfBlackLine = false;
   return true;
  } else
   return false;
 }

 public void suppress(){
  suppress = true;
 }

 public void action(){
  sweep = 10;
  while(!suppress){
   pilot.rotate(sweep, true);
   while(!suppress && pilot.isMoving())
    Thread.yield();
   sweep*=-2;
  }
  pilot.stop();
  suppress = false;
 }
}

DriveForward.java

import lejos.nxt.*;
import lejos.robotics.subsumption.*;
import lejos.robotics.navigation.*;

public class DriveForward implements Behavior, SensorPortListener{
 
 private Pilot pilot;
 private LightSensor light;
 private boolean seenBlackLine;
 
 public DriveForward(Pilot pilot, LightSensor light){
  this.pilot = pilot;
  this.light = light;
  seenBlackLine = false;
  SensorPort.S3.addSensorPortListener(this);
 }
 
 public void stateChanged(SensorPort port, int oldValue, int newValue){
  if(light.readValue() <= 35)
   seenBlackLine = true;  
 }
 
 public boolean takeControl(){
  if(seenBlackLine){
   LCD.clear();
   LCD.drawString("DriveForward", 2, 2);
   seenBlackLine = false;
   return true;
  } else
   return false;
 }
 
 public void suppress(){
  pilot.stop();
 }
 
 public void action(){
  pilot.forward();
  while(light.readValue() <= 35)
   Thread.yield();
 }

}

Finalmente, se adjunta un video, donde se puede apreciar al robot ejecutando la tarea encomendada, en la pista anteriormente mostrada:

Lógica de primer orden - Base de conocimientos de relaciones familiares

Se muestra a continuación, una representación sistemática, del dominio del parentesco, a través del uso de la lógica de primer orden. La base de conocimientos, de esta manera, viene a conformarse por los siguientes predicados y funciones:

Búsquedas - Mapa de Rumania y Eight Puzzle

Se adjunta a continuación un link con el código fuente relativo a las búsquedas (heurísticas y no heurísticas), implementado tanto para resolver el mapa de Rumania, así como el Eight Puzzle.

http://www.multiupload.com/FWPVLZI4KX

Heurística, y búsquedas heurísticas

Heurística

Heurística, es un término para técnicas basadas en la experiencia, que ayudan en la resolución de un problema, aprendizaje, y descubrimiento. Un método heurístico es usado para llegar a una solución rápidamente que se espera sea cercana a la mejor respuesta posible, o “solución óptima”. Una heurística es una conjetura, un juicio intuitivo, o simplemente sentido común.

En ciencias computacionales, una heurística es una técnica diseñada para resolver un problema que ignora si la solución puede ser probada correcta, pero que usualmente produce una buena solución o resuelve un problema más simple que contiene o intersecta con la solución de un problema más complejo.

La intención de las heurísticas, es ganar desempeño computacional, o simplicidad conceptual, potencialmente al costo de precisión.

Búsqueda heurística

Una búsqueda heurística, es aquella que emplea  una “heurística”, tal como fue definida en la sección anterior. En una búsqueda de este tipo, cada sucesión iterativa, depende del paso anterior, por lo tanto, la búsqueda heurística aprende qué caminos perseguir, y qué caminos ignorar midiendo qué tan cerca la iteración actual, se encuentra a la solución. Por lo tanto, algunas posibilidades nunca serán generadas pues son consideradas de menor probabilidad para llegar a la solución.

Un método heurístico puede lograr su tarea, usando árboles de búsqueda. Sin embargo, en lugar de generar todas las ramas de posibles soluciones, una búsqueda heurística selecciona las ramas con mayor probabilidad de producir resultados, que otras ramas. Es selectiva en cada punto de decisión, escogiendo las ramas, que tienen mayor probabilidad de generar soluciones.

Búsqueda primero el mejor (Best first search)

La aproximación general para estrategias de búsqueda informada, es conocida como búsqueda primero el mejor (best first search), donde un nodo es seleccionado para expansión, basados en una función de evaluación f(n).

La función de evaluación se interpreta como un estimado del costo, de tal manera que el nodo con la menor evaluación, se expande primero.

Lo anterior, implica para la implementación del algoritmo, la necesidad de ordenar los nodos en la frontera de acuerdo a un orden incremental de los costos.

La mayoría de los algoritmos primero el mejor, incluyen a una función heurística como componente de f, denominado h(n):

h(n) = costo estimado de la ruta de menor costo desde el estado en el nodo n, al estado final.

Existen dos casos especiales de búsqueda primero el mejor:

• Búsqueda voraz primero el mejor (Greedy best first search).
• Búsqueda A*.

Estos algoritmos se analizan con mayor detenimiento a continuación.

Búsqueda voraz primero el mejor (Greedy best first search)

La búsqueda voraz primero el mejor, intenta expandir el nodo que se encuentra más cerca de la meta, bajo la suposición de que esto es probable que lleve a una solución rápidamente. De esta manera, evalúa nodos usando sólo la función heurística; esto es, f(n) = h(n).

Propiedades

• Este algoritmo no es completo, puede quedarse atascado en ciclos.
• Tiempo: O(b^m), pero una buena heurística puede proporcionar una mejora dramática.
• Espacio: O(b^m), mantiene todos los nodos en memoria.
• Óptimo: No.

Búsqueda A*

Es un algoritmo  que se utiliza ampliamente en la búsqueda de rutas, y el recorrido de grafos, el proceso de trazar un camino eficientemente transitable entre puntos, denominados nodos. Conocido, por su desempeño, y precisión, goza de un amplio uso. Se le considera una extensión del algoritmo de Dijkstra. A* logra un mejor desempeño (con respecto al tiempo), haciendo uso de heurísticas.

Descripción

El algoritmo A* utiliza una búsqueda primero el mejor, y encuentra la ruta de menor costo dado un nodo inicial, hacia un nodo objetivo.

Utiliza una función heurística de “distancia más costo” (generalmente denominada f(x)) para determinar el orden en que la búsqueda visitará los nodos en el árbol. La heurística de “distancia más costo” es una suma de dos funciones:

• La función del costo de la ruta, la cual consiste en el costo desde el nodo inicial, al nodo actual (usualmente denominada g(x)).
• Y un “estimado de heurística” admisible de la distancia a la meta (usualmente denominado h(x)).

La parte h(x), de la función f(x), debe ser una heurística admisible, lo que significa, que no debe sobrestimar la distancia a la meta. De esta manera, para una aplicación como el ruteo, h(x) puede representar la distancia en línea recta a la meta, dado que físicamente, es la distancia más pequeña posible entre dos puntos, o nodos cualquiera.

Si la heurística satisface además la condición h(x) ≤ d(x, y) + h(y) para toda arista x, y del grafo (donde d denota la longitud de esa arista), entonces h es llamada monótona, o consistente. En tal caso, A* puede ser implementado más eficientemente.

Propiedades

De la misma manera que la búsqueda primero en anchura, A* es completa, y siempre encontrará una solución, si es que existe.

Si la función heurística h es admisible, entonces A* es admisible (óptimo) si no usamos una lista de nodos ya visitados (conjunto cerrado).

Si se utiliza un conjunto cerrado, entonces h debe ser monótona (o consistente) para que A* sea óptimo.

Asimismo, A* es óptimamente eficiente, para cualquier heurística h, lo cual significa, que ningún algoritmo que emplee la misma heurística, expandirá menos nodos que A*, excepto cuando existan múltiples soluciones parciales, donde h predice exactamente el costo del camino óptimo.

La complejidad en tiempo de A* depende se la heurística. En el peor caso, el número de nodos expandidos es exponencial en la longitud de la solución (el camino más corto), pero es polinomial cuando el espacio de búsqueda es un árbol, hay un sólo estado objetivo, y la función heurística cumple la condición de que su error no crecerá más rápidamente que el logaritmo de la “heurística perfecta” (aquella que regresa la verdadera distancia a la meta).

Formalización de problemas

Criptoaritmética

Estados: Un estado es una asignación (parcial) de dígitos a letras.

Operadores: La asignación de un dígito a una letra. (Puede incluir restricciones como que el dígito no haya sido ya usado, y que las reglas aritméticas no sean violadas).

Prueba de si se ha llegado al estado objetivo: Determinar si a todas las letras, le han sido asignadas dígitos, y que la suma sea correcta.

Estado inicial: Una asignación parcial de dígitos a letras.

Estado final: Un estado en el que a todas las letras le han sido asignadas dígitos, y la suma es correcta.

Misioneros, y caníbales

Operadores: Son cinco los operadores, los cuales se listan a continuación:

1. Llevar a un misionero al otro lado.
2. LLevar a un caníbal.
3. Llevar a dos misioneros.
4. Llevar a dos caníbales.
5. Llevar a un misionero, y a un caníbal.

Estados: Un estado se conforma de tres variables:

1. Número de lanchas en un lado.
2. Número de caníbales.
3. Número de misioneros.

Prueba de si se ha legado al estado objetivo: Determinar si el estado actual corresponde a (0, 0, 0)

Estado inicial: (3, 3, 1)

Estado final: (0, 0, 0)

Conclusiones Know & Want

Want.

• Qué tipos de Agentes.
• Saber Construirlos.
• Hacer algoritmos que aprendan solos.
• Robot´s Lego´s que salgan de laberintos.
• Explotar el Robot Lego.
• Cómo Funcionan y cómo hacerlos.

Know

• Toma de decisiones.
• Aprendizaje.
• Algoritmos Autónomos.
• Propósito específico.
• Relacion con su entorno.
• Automatización.
• Crear Inteligencia.

Conclusiones:
Despues del análisis de lo anterior, concluimos que el término "Agentes Inteligentes" es el concepto que más se ha estado utilizando en el tópico de Inteligencia Artificial en los últimos días. Creemos que los agentes inteligentes son entidades de software con cierto grado de autonomía para la toma de decisiones.

De esta manera queremos conocer qué tipos de "Agentes" existen y cómo implementarlos.