Practica 4 - Sistemas Multiagente

Introducción y Desarrollo

En la presente práctica de laboratorio se implementó un sistema multi-agente con el protocolo ContractNet. Se escoge al mejor, que tenga similitudes, y se envía un mensaje de aceptación.

En los juegos en linea se utiliza una herramienta para buscar otros jugadores que se encuentren jugando 'cierta partida' entonces similar al protocolo contract net donde el agente cierra un contrato al encontrar a otro agente similar(en este caso , su experiencia en nivel del juego).

A continuación se presenta un fragmento del código de la clase MatchMaking.java

public class MatchMaking extends Agent{

private boolean CrearPartida=false;
 
private AgentAddress encontrado=null;


public void activate(){
 println("Matchmaking");
 println("Buscando Jugadores...");
 
if(isGroup("Halo")){
 println ("Existe, me uno");
 CrearPartida=false;
 }
 else{
println ("No existe, voy a crearlo");
createGroup(true,"halo",null,null);
CrearPartida=true;
}
requestRole("halo","jugador",null);
}

public void live(){
 println("Buscando a otro jugador...");
do
{
 exitImmediatlyOnKill();
 pause(100);
 AgentAddress[] v = getAgentsWithRole("halo","jugador");
 
for (int i=0; i < v.length; i++){
 AgentAddress agent = v[i];
 if (! agent.equals(getAddress()))
 encontrado = agent;
 }
 }
 while (encontrado == null);
 
println("El Jugador se ha unido :"+encontrado);
// Si no soy el creador del grupo, envio la pelota primero.
 
if (! CrearPartida)
 
sendMessage(encontrado, new StringMessage("Se creo una partida.. "));
for (int i = 5; i > 0; i--){

Message m = waitNextMessage();
 
if(! m.getSender().equals(encontrado)){
while(true){

exitImmediatlyOnKill();
Message m2 = waitNextMessage(1000);
 
if(m2==null){
encontrado = m.getSender();
i=5;
println("El Creador del grupo se fue");
println("Encontre un nuevo jugador "+encontrado);
break;
}
else if(m2.getSender().equals(encontrado))
break;
}
}

Video

Referencias

• En la pagina Madkit.org se encontraron referencias de las clases y de cómo crear y enviar mensajes (comunicación) entre los agentes.

Practica 3 - Reconocimiento de Patrones

Introducción

El reconocimiento de voz es una herramienta esencial en cuanto a la accesibilidad de algunos usuarios, se pueden dar órdenes y el sistema interpretara los comandos, de ésta manera se facilita por ejemplo : a las personas que no pueden escribir u alguna discapacidad, tiene la opción de interactuar con la máquina mediante comandos de voz. También por comodidad se puede usar en otras áreas , cosas de la vida cotidiana como encender un foco , cerrar/abrir una llave, entre otras cosas.

El reconocimiento del Habla permite a un ser humano comunicarse con un ordenador. A grandes rasgos, consiste en que el ordenador captura la señal de voz que emite una persona a través de un micrófono, convirtiéndola en información digital. El motor de voz debe ser capaz de reconocer las silabas de entre un conjunto de fonemas que ha recibido, y combinarlas para formar las palabras que se habían dicho anteriormente por el usuario.

Durante las últimas décadas se ha estudiado la posibilidad de desarrollar interfaces hombre-computador controlados por voz para sustituir en ciertas aplicaciones a las interfaces tradicionales basadas en teclados o ratones. El Reconocimiento Automático de Voz es un campo de investigación de creciente relevancia que día a día gana mas partidarios.

El reconocimiento es basado en la comparación de patrones de referencia denominados modelos con los vectores de características generados para la palabra a reconocer.

Objetivo

Por medio de ésta práctica, el alumno implementará una de las técnicas vistas hasta el momento en clase, programando un sistema adaptativo relacionado con temas de sistemas inteligentes.

Desarrollo

Usando la librería de Cloud Garden TalkingJava SDK con la implementación de Java Speech API se ha conseguido realizar el reconocimiento de ciertas palabras mediante un diccionario que cumple con JSGF, el cual es un conjunto de convenciones para la gramática en el reconocimiento de Voz.

Elegimos Reconocimiento de Voz debido al interés por ir avanzando con nuestro proyecto de CLASE que va muy relacionado. Se desarrolló un Sistema Inteligente basado en JAVA donde el objetivo radica en ejecutar aplicaciones de Windows mediante la voz.

El inconveniente en ésta práctica es que sólo está soportada para el Sistema Operativo Windows. Entre los problemas que se presentaron está que al utilizar el micrófono integrado con la webcam de una laptop, con el ruido del entorno se tarda en reconocer y confunde ciertas palabras similares.Aún así haciendo pruebas con un micrófono externo se logran reconocer correctamente las palabras incluidas en el Archivo Programas.txt

A continuación se presenta un fragmento del código de la clase Reconocedor.java

public void iniciarRec() {
  
JOptionPane.showMessageDialog(null, "Pronuncie Aplicacion a Ejecutar");
  
 try{
  //Se configura al reconocedor para que entienda el idioma inglés
  oreja = Central.createRecognizer(new EngineModeDesc(Locale.ROOT));
  oreja.allocate();
  FileReader diccionario =new FileReader("Programas.txt"); //ruta donde esta el archivo con las Frases
  RuleGrammar gramatica = oreja.loadJSGF(diccionario);//Establece la forma en que debe de estar estructurado el archive gramatica
  gramatica.setEnabled(true); //accesa al archivo
  oreja.addResultListener(new Programas());  //Se hace referencia a la clase de escucha del reconocedor
 
  for(int i=0;i<=23;i++){
   System.out.println("");
  }
  System.out.println("Pronuncia un programa");
  oreja.commitChanges();
  oreja.requestFocus();
  oreja.resume();
 } catch (Exception e){
            e.printStackTrace();
     System.exit(0);
 } 
return;
}

A continuación se presenta un fragmento del código de la clase Programas.java

public void resultAccepted(ResultEvent e){
 try {
     Result res = (Result)(e.getSource());
     ResultToken tokens[] = res.getBestTokens();
     String Frase[]= new String[1];
     Frase[0]="";

     for (int i=0; i < tokens.length; i++){
  Programa = tokens[i].getSpokenText();
  Frase[0]+=Programa+" "; 
  System.out.print(Programa + " ");
     }
     System.out.println();
   
     if(Programa.equals("Fin")){
  oreja.deallocate();
  Frase[0]="Hasta la proxima!";
  System.out.println(Frase[0]);
  System.exit(0);
     }
     else if(Programa.equals("Facebook")) {
  try { 
      System.out.println("Abriendo Facebook...");
      // Se lanza el ejecutable. 
       Process p=Runtime.getRuntime().exec ("cmd.exe /c start Chrome www.facebook.com"); 
             
      InputStream is = p.getInputStream(); 
                    BufferedReader br = new BufferedReader (new InputStreamReader (is)); 
             
      String aux = br.readLine(); 
                    while (aux!=null) { 
   System.out.println (aux); 
   aux = br.readLine(); 
      } 
  } catch (Exception es) { 
      es.printStackTrace(); 
  } 
     }
            else {
  getPrograma();
  oreja.suspend();
  oreja.resume();
     }
 }catch(Exception ex) {
 }
}

Para ver el código completo:

http://gist.github.com/4002766

Video

Conclusiones

Una vez visto los resultados de la aplicación se observa que el reconocimiento de voz es un área de estudio muy grande, la cual está en desarrollo continuo.

Aún se piensa ir mejorando la aplicación sobretodo pensando en nuestro Proyecto Final de Clase.

Referencias

• TalkingJava SDK with Java Speech API implementation Current Version 1.7.0
• http://www.sicuma.uma.es/sicuma/independientes/argentina08/Liliana/JSAPI.htm
• http://www.w3.org/TR/jsgf

Practica 2 - Autómatas Celulares

ENTREGA FINAL

Objetivo.

Por medio de esta práctica el alumno implementará algunas de las técnicas vistas en el curso de la materia de Programación de Sistemas Adaptativos. Se programará un Sistema Adaptativo con cómputo evolutivo o sistemas complejos.

Diseño del Sistema.

Para la siguiente práctica se estudia el comportamiento de un Autómata Celular que con el paso del tiempo se ha ido estudiando marcando 3 etapas importantes con científicos que hicieron aportes importantes.

• La era de Von Neumann (Máquina de Turing).
• La era de John Horton COnway (Juego de la Vida).
• La era de Stephen Wolfram(Sistema caótico en la evolución al establecer condiciones alteatorias).

Diseño de la Solución.
Se considera un vector con valores binarios dependiendo de la regla escogida por el usuario para establecer la Regla a mostrar y poder entender el proceso de obtención de cada regla.

Se realiza la conversión de entero a binario en la clase MainCelular.java y se manda a la clase Regla.java el vector del número binario obtenido de la conversión del numero escogido por el usuario para establecer la regla a mostrar en el Frame.

  
do {
    do {
 numRegla = JOptionPane.showInputDialog("Inserta el numero de regla a mostrar:","90");
    }while(numRegla.equals(""));
 regla = Integer.parseInt(numRegla);
}while( regla < 0 || regla > 255);
 int pregunta = JOptionPane.showConfirmDialog(null, "¿Desea generar un vector inicial aleatorio?", "Inicializacion", JOptionPane.YES_NO_OPTION);
    if (pregunta == 0) {
 R.Random();
    } 

/* Se hace la conversion de Entero a Binario */
 
    for(int i=7;i>=0;i--) {
        NumBinario[i]=regla%2;
        System.out.println("El elemento ["+i+"] -> "+NumBinario[i]);
        regla/=2;
    }

    R.getRegla(NumBinario[0],NumBinario[1],NumBinario[2],NumBinario[3],NumBinario[4], NumBinario[5],NumBinario[6],NumBinario[7]);

Se establece como Valor inicial un pixel en el centro cuyo valor booleano es true para la visualización en el Panel donde se va a dibujar el fractal simple indicado por el usuario.

Ya dentro de la clase Regla.java se recibe el vector binario y se 'crea' la regla. Dentro del método getCasilla se va siguiendo la regla y regresa el nuevo valor que la célula tendrá en la siguiente etapa del tiempo (k+1).

  
public int getCasilla(int A,int B ,int C) {
    int r=0;
        if(A==0 && B==0 && C==0){r=a;
     }else if(A==0 && B==0 && C==1){r=b;
     }else if(A==0 && B==1 && C==0){r=c;
     }else if(A==0 && B==1 && C==1){r=d;
            }else if(A==1 && B==0 && C==0){r=e;
     }else if(A==1 && B==0 && C==1){r=f;
     }else if(A==1 && B==1 && C==0){r=g;
     }else if(A==1 && B==1 && C==1){r=h;
     }
    return r;
}

En el método Regla se expone que al cambiar el vector inicial, que mostraba solamente un pixel encendido (true), por uno aleatorio se genera un fractal mas complejo. ('Sistema Caotico')

  
public void Reglas(){

 for(int i=0;i<1000;i++){
    A[0][i]=0;
 }

 if (rand == true) {
     Random r = new Random();
     for(int j=0; j<=500; j++) {  
      boolean truefalse = r.nextBoolean();
      A[0][j] = (truefalse == true)?1:0; /*Se genera un vector inicial aleatorio*/
     }
 } else {
     A[0][100]=1;
 }
    }

Para ver el código completo del programa:

https://gist.github.com/3762974

Video.

Conclusiones.

Una vez visto los resultados de la aplicación se observa que el estudio de los autómatas celulares requiere mayor estudio debido a que si se selecciona una regla y una configuración inicial y se sigue la evolución temporal se observará un cambio considerable en el curso del tiempo.

Cabe mencionar que un autómata celular puede ser imprescindible con configuraciones iniciales aleatorias ya que es considerado un ejemplo común de un Sistema Caótico.

Referencias:

http://delta.cs.cinvestav.mx/~mcintosh/comun/tesismaestria/rene/tesisReneHtml/node14.html

http://www.ejournal.unam.mx/cns/no24/CNS02405.pdf

Practica # 1 - Control de Semáforos

ENTREGA FINAL

Objetivo.

Por medio de esta práctica el alumno desarrollará lo mas profundo posible las diferentes soluciones y posibles problemas que se puede encontrar para el problema propuesto. Implementará un sistema que simule un crucero congestionado y éste regule automáticamente la duración del verde de los semáforos de los cruces.

Diseño del Sistema.

Para la siguiente práctica se recomienda que el alumno considere de apoyo los siguientes Temas:

• Sistema de Colas
• Hilos de Ejecución (Threads)
• Programación Modular

En los siguientes diagramas se presenta el escenario con el que se va a trabajar a lo largo de esta práctica. A continuación el Diseño del cruce:

A continuación se presenta la Matriz y el Grafo de Conflictos:

Vector de Características

Diseño de la Solución.

Con lo anterior se puede deducir lo siguiente:

Si se imagina el cómo sería el comportamiento de los automóviles, dependiendo de las luces, es fácil ver que tanto los carros del carril A tanto del B nunca entraría en conflicto, y no harían colisión. Lo mismo ocurre con las filas C y D. Por tanto, no hay ningún problema si la luz está en verde tanto para el carril A como el carril B simultáneamente.

De esta manera, es como se da la sincronización de los semaforos, pues dos de ellos irán siempre encendidos u apagados al mismo tiempo, y los que cambiarán serán los otros dos, que a su vez, estarán sincronizados uno con el otro.

Para la determinación del tiempo de activación de la Luz verde para los cuatro carriles se consideran como carriles principales los carriles A y B; y como carriles secundarios a los carriles C y D. Para la solución de nuestro problema se asignaron valores de tiempo para la activación de la luz verde en los carriles, dependiendo del congestionamiento de autos que se presente.

* Los tiempos reales en la Simulación van a disminuir considerablemente.

Para determinar la solución del congestionamiento en los carriles, se consideró que si se encuentran 10 o mas carros en los carriles principales(A,B) se tomaría como Congestionados CongA = true y CongB = true y si se encontraban 5 automóviles o más en los carriles secundarios(C,D) se tomaría como Congestionados CongC = true y CongD = true.

Una vez teniendo como valores booleanos el Congestionamiento en los carriles se realizó la siguiente tabla de verdad:

Posteriormente se realizó un Mapa de Karnaught para encontrar la ecuación booleana que nos ayude a controlar los semáforos, es decir, que determine qué semáforo es el que tendrá el paso.

Se analizó el Mapa siguiendo la lógica del OR y se obtuvo la siguiente ecuación:

SemAB = (A + B + D')·(A + C' + D')·(A + B + C')·(B + C' + D');

El estado del SemCD se pasaría como el contrario de SemAB, es decir:

SemCD = !SemAB;

A continuación se presentan las partes interesantes del código para comprender mejor la solución del problema. Para ver los códigos completos:

https://gist.github.com/3662916

Código de la clase Sistema.java:

ListaCarros LisCarr = new ListaCarros();

    while(true) {
     if (CarrilA > 10) { CA = true; }
            if (CarrilB > 10) { CB = true; }
     if (CarrilC > 5 ) { CC = true; }
     if (CarrilD > 5 ) { CD = true; }

 SemAB = (CA | CB | !CD ) & (CA | !CC | !CD ) & (CA | CB | !CC) & (CB | !CC | !CD);
 SemCD = !SemAB;

 LisCarr.setEstado(SemAB,SemCD);

            if (SemAB == true) {
  EstadoAB = "Verde";
  EstadoCD = "Rojo";

            } else {
  EstadoAB = "Rojo";
  EstadoCD = "Verde"; 
     } 

 for(int r=0;r<20;r++){System.out.println("\n");}
  System.out.println("\t\t----------------------------------");
  System.out.println("\t\t~Sistema de Control de Semaforos~"); 
  System.out.println("\t\t----------------------------------");
  System.out.println("\n\n\t\t~Congestionamiento~");
  System.out.println("\n\tHay "+CarrilA+" carros en A");
  System.out.println("\n\tHay "+CarrilB+" carros en B");
  System.out.println("\n\tHay "+CarrilC+" carros en C");
  System.out.println("\n\tHay "+CarrilD+" carros en D");

  System.out.println("\n\n\t\t~Estado Semaforos~");
  System.out.println("\n\tA y B -> "+EstadoAB );
  System.out.println("\n\tC y D -> "+EstadoCD );

    Thread.sleep(5000);
    } //Fin del while

Código de la clase ListaCarros.java:

  a = ( ( Rand.nextInt(10000) % 16) + 1);
  CarrilA = CarrilA + a;
  if (CarrilA < 0) { CarrilA = 0; }
  b = ( ( Rand.nextInt(10000) % 16) + 1);
  CarrilB = CarrilB + b;
  if (CarrilB < 0) { CarrilB = 0; }
  c = ( ( Rand.nextInt(10000) % 8) + 1);
  CarrilC = CarrilC + c;
  if (CarrilC < 0) { CarrilC = 0; }
  d = ( ( Rand.nextInt(10000) % 8) + 1);
  CarrilD = CarrilD + d;
  if (CarrilD < 0) { CarrilD = 0; }

 if (aux = true) {

     if (SemAB = true) {

  CarrilA=CarrilA-3;
  CarrilB=CarrilB-2;

     if (CarrilA < 0) { CarrilA = 0; }
     if (CarrilB < 0) { CarrilB = 0; }

  CarrilC=CarrilC+5;
  CarrilD=CarrilD+5;

     } else {

  CarrilC=CarrilC-2;
  CarrilD=CarrilD-2;

     if (CarrilC < 0) { CarrilC = 0; }
     if (CarrilD < 0) { CarrilD = 0; }

  CarrilA=CarrilA+3;
  CarrilB=CarrilB+3; 
     }
 }

Sistema CtrlSem = new Sistema();
CtrlSem.start();
CtrlSem.setCarros(CarrilA,CarrilB,CarrilC,CarrilD);

Video de la Simulación:

Referencias:

http://epere4.blogspot.mx/2008/04/cmo-funciona-synchronized-en-java.html

http://es.wikibooks.org/wiki/Programaci%C3%B3n_en_Java/Operadores_booleanos 

Sistemas de Colas

Los sistemas de colas son modelos de sistemas que proporcionan servicio. Como modelo, pueden representar cualquier sistema en donde los trabajos o clientes llegan buscando un servicio de algún tipo y salen después de que dicho servicio haya sido atendido. Podemos modelar los sistemas de este tipo tanto como colas sencillas o como un sistema de colas interconectadas formando una red de colas. 

Los problemas de “colas” se presentan permanentemente en la vida diaria: un estudio en los Estados Unidos concluyó que, por término medio, un ciudadano medio pasa cinco años de su vida esperando en distintas colas, y de ellos casi seis meses parado en los semáforos. 

Introducción a la Teoría de Colas 

En muchas ocasiones en la vida real, un fenómeno muy común es la formación de colas o líneas de espera. 

Esto suele ocurrir cuando la demanda real de un servicio es superior a la capacidad que existe para dar dicho servicio.

El origen de la Teoría de Colas está en el esfuerzo de Agner Kraup Erlang en 1909 para analizar la congestión de tráfico telefónico con el objetivo de cumplir la demanda incierta de servicios en el sistema telefónico de Copenhague. Sus investigaciones acabaron en una nueva teoría denominada teoría de colas o de líneas de espera. Esta teoría es ahora una herramienta de valor en negocios debido a que un gran número de problemas pueden caracterizarse, como problemas de congestión llegada-salida. 

Modelo de formación de Colas. 

La teoría de la formación de colas busca una solución al problema de la espera prediciendo primero el comportamiento del sistema. Pero una solución al problema de la espera consiste en no solo en minimizar el tiempo que los clientes pasan en el sistema, sino también en minimizar los costos totales de aquellos que solicitan el servicio y de quienes lo prestan.

La teoría de colas en sí no resuelve este problema, sólo proporciona información para la toma de decisiones. 

Objetivos de la Teoría de Colas.

Los objetivos de la teoría de colas consisten en:

• Identificar el nivel óptimo de capacidad del sistema que minimiza el coste global del mismo. 
• Evaluar el impacto que las posibles alternativas de modificación de la capacidad del sistema tendrían en el coste total del mismo. 
• Establecer un balance equilibrado (“óptimo”) entre las consideraciones cuantitativas de costes y las cualitativas de servicio. 
• Hay que prestar atención al tiempo de permanencia en el sistema o en la cola: la “paciencia” de los clientes depende del tipo de servicio específico considerado y eso puede hacer que un cliente “abandone” el sistema. 

Modelo de Colas.

Un modelo de sistema de colas debe especificar la distribución de probabilidad de los tiempos de servicio para cada servidor. 

La distribución más usada para los tiempos de servicio es la exponencial, aunque es común encontrar la distribución degenerada o determinística (tiempos de servicio constantes) o la distribución Erlang (Gamma). 

Características claves. 

Existen dos clases básicas de tiempo entre llegadas:

• Determinístico, en el cual clientes sucesivos llegan en un mismo intervalo de tiempo, fijo y conocido(Ciclos de Tiempo).

• Probabilístico, en el cual el tiempo entre llegadas sucesivas es incierto y variable. Los tiempos entre llegadas probabilísticos se describen mediante una distribución de probabilidad. 

Por convención los modelos que se trabajan en teoría de colas se etiquetan:

Las distribuciones que se utilizan son: 

• M: Distribución exponencial (markoviana) 
• D: Distribución degenerada (tiempos constantes)
• E k : Distribución Erlang 
• G : Distribución general 

Ejemplos:

* M / M / s : Modelo donde tanto los tiempos entre llegada como los tiempo de servicio son exponenciales y se tienen s servidores. 

* M / G / 1: Tiempos entre llegada exponenciales, tiempos de servicio general y 1 sólo servidor.

El Proceso de Servicio.  

El proceso de servicio define cómo son atendidos los clientes. En algunos casos, puede existir más de una estación en el sistema en el cual se proporcione el servicio requerido.

En los sistemas de colas de canal múltiple los servidores pueden ser idénticos, en el sentido en que proporcionan la misma clase de servicio con igual rapidez, o pueden no ser idénticos. Es importante hacer notar que incluso en un sistema de canal sencillo pueden existir muchos servidores que, juntos, llevan a cabo la tarea necesaria.

Otra característica más de un proceso de servicio es si se permite o no la prioridad, esto es:

 ¿Puede un servidor detener el proceso con el cliente que está atendiendo para dar lugar a un cliente que acaba de llegar?.

Con un tiempo de servicio determinista, cada cliente requiere precisamente de la misma cantidad conocida de tiempo para ser atendido. Con un tiempo de servicio probabilístico, cada cliente requiere una cantidad distinta e incierta de tiempo de servicio. Los tiempos de servicio probabilísticos se describen matemáticamente mediante una distribución de probabilidad. 

En la práctica resulta difícil determinar cuál es la distribución real, sin embargo, una distribución que ha resultado confiable en muchas aplicaciones , es la distribución exponencial:

donde:
m = número promedio de clientes atendidos por unidad de tiempo.

de modo que:

1/ m = tiempo promedio invertido en atender a un cliente.

Referencias:

www.ingenieria.unam.mx/javica1/ingsistemas/Simulacion/COLAS.doc

http://www2.ing.puc.cl/~iic11021/materia/cap13.htm