s.e.p. centro nacional y desarrollo tecnolÓgico · s.e.p. s.e.i.t. d.g.i.t. centro nacional de...
TRANSCRIPT
S.E.P. S.E.I.T. D.G.I.T.
CENTRO NACIONAL DE INVESTIGACI~N Y DESARROLLO TECNOLÓGICO
cenidef
“UN MODELO DE COiWJNICACIÓN ENTRE MÚLTIPLES AGENTES INTENCIONALES BASADOS EN LA ARQUITECTURA B I G
T E S I S QUE PARA OBTENER EL GRADO DE:
M A E S T R O E N C I E N C I A S EN CIENCIAS COMPUTACIONALES
P R E S E N T A :
NADIRARODRÍGUEZ DAM&
DIRECTOR DE TESIS
DR. JOSÉ LUIS LIÑAN GAR&
1
CUERNAVACA, MORELOC \ \ \ ‘i.
’ /
SEP CENIBET DGlT CION CENTRO DE INFORMA
ENERO 2000
Centro Nacional de Investigación y Desarrollo Tecnológico FORMA C3
REVISION DE TESIS
M.C. Máximo López Sánchez Presidente de la Academia de Ciencias Computacionales Presente
Nos es grato comunicarle, que conforme a los iineamientos para la obtención del grado de Maestro en Ciencias de este Centro, y después de haber sometido a revisión académica la tesis denominada: UN MODELO DE COMUNICACIÓN ENTRE MÚLTIPLES AGENTES INTENCIONALES BASADOS EN LA ARQUITECTURA BIG, realizada por la C. Nadira Rodríguez Damíán, y habiendo cumplido con todas las correcciones que le fueron indicadas, acordamos no tener objeción para que se le conceda la autorización de impresión de la tesis.
Sin otro particular, quedamos de usted.
Atentamente
La comisión de revisión de tesis
a 0 Z
'$
\ A D S : L i s L ; x
M.C Moisés González GarcíaJ::z;.,-. . . . , . i Dr. José Luis Liñan García Director de tesis
. . . . .... ,.~ ,;. :! :; I . . .
1 '. C.C.P. Dr. Javier Ortiz Hernández/Jefe del Departamento de Ciencias Computacionales
INTERIOR INTERNADO PALMIRA S N . CUERNAVACA. MOR. MgXICO APARTADO POSTAL 5-164 CP 62050. CUERNAVACA. TELS. (73)12 2314.12 7613 , l a 7741. FAX(73) 12 2434 EMAIL [email protected]> cenidef
Centro Nacional de Investigación y Desarrollo Tecnológico FORMA C 4
AUTORIZACION DE IMPRESIÓN DE TESIS
C. Nadira Rodiíguez Darnián Candidato al grado de Maestro en Ciencias en Ciencias Computacionales Presente
Después de haber atendido las indicaciones sugeridas por la misión Revisora de la Academia de Ciencias Computacionales en relación a su trabajo de tesis: UN MODELO DE COMUNICACIÓN ENTRE MÚLTIPLES AGENTES INTENCIONALES BASADOS EN LA ARQUITECTURA BIG, me es grato comunicarle, que conforme a los lineamientos establecidos para la obtención del grado de Maestro en Ciencias en este Centro, se le concede la autorización para que proceda con la impresión de su tesis.
,,.,".,. <,, . .. ~,~ . . .i ' ' . ~
<,, ,::. ;: ... ., 7 .. . .
Atentamede .. . .
Jefe del Depto./ Ciencias Computacionales /
,/ i
INTERIOR IhTERNADO PALMIRA SIN CUERhAVACA MOR MEXICO APARTADO POSTAL 5-1M CP 62050 CLERhAVACA TELS (73112 2314 12 7613 18 7741 FAX 173, 12 24.M EMAIL [email protected]
~
cenídef
D E D I C A TORI A
A Dios por haberme darme la fortaleza necesaria para cumplir esta meta en mi camino
A los pilares de mi vida me dieron la vida, me educaron con amor, dedicación y disciplina. Por todo los valores que me inculcaron y por su continua preocupación por mi bienestar, gracias por todo los quiero:
Moisés Rodriguez Berna1
Ma. Concepción Damián Robles Y
A mis hermanas por Sus continuas muestras de cariño, SU
apoyo, sus consejos, SU
comprensión y confianza mil gracias, no se olviden que siempre están en mi pensamiento las quiero:
Noemí Ga by Si boney
A una nueva personita en mi familia mi sobrino Guillermo (mueganito)
Por t u apoyo incondicional, cariño, confianza y compañía gracias, Juan Carlos t e quiero.
AGRADECIMIENTOS
A mi familia por SU apoyo incondicional, amor y compañía en los momentos difíciles de mi estancia en Cuernavaca.
A mi asesor Dr. José Luis Liñan García por compartir conmigo sus conocimientos y la confianza que me tuvo en el desarrollo de este trabajo.
AI comité de revisión por sus comentarios y sugerencias, para mejorar y enriquecer este tema de investigación: M.C Moisés González García, M.C Manuel Mejía Lavalle, M.C Matilde Velazco Soní.
A mis profesores por su amistad y apoyo durante mi formación académica.
A las personas que me brindan su amistad sinceramente: Sony González, Ver0 Campos, Lucero María Ayala Lugo, Alejandra Kauffman Mireles, Esmeralda Barba, Gaby Calderon, Juanita Canul, Elias Rodríguez, Jorge Ibarra, Alberto Alvarado.
A mis compañeros de generación, a mis compañeros y amigos de electrónica de está institución me faltaría lugar para nombrarlos, pero ustedes saben que siempre cuentan conmigo y gracias por los momentos que compartimos.
A mis compañeros del Tecnológico de Celaya generación 1997 y 1998.
A todo el personal de está institucibn, y al apoyo económico de SEP.
CONTENIDO ............................ LISTA DE FIGURAS .......................................................................................... iv
LISTA DE TABLAS ........................................................................... .......................................... v
CAPITULO 1
I NTRODUCCI~N 1.1 INTRODUCCIÓN ................. ................................. 1 1.2 RESUMEN DE LA TESIS ..................................................................................................... 2 1.3 ANTECEDENTES .............................................................................. 1.4 DEFINICION DEL PROBLEMA ................................. 1.5 OBJETIVO .............. 1.6 BENEFICIOS Y ALC 1.7 FUNDAMENTO FILOSOFICO 1.8 ORGANIZACIÓN DE LA TESl ...................
CAPITULO 2
MARCO TEÓRICO
2.1 INTRODUCCI~N .................................................................................................................. 8 2.2 INTELIGENCIA ARTIFICIAL ........................... 9
2.2.1 Inteligencia artificial 9
artificial distribuida ......................................... 9 2.2.2 Divisiones de la inteligencia
2.3 PARADIGMA DE PROGRAMACION ................. 10
........................................................................................... I1 2.3.4 Sistema multi ........................... 12 2.3.5 Problemas re
2.4 PROBLEMAS DE COMUNICACIÓN
2.4.3 Actos del habla ....................................... 16 2.5 ARQUITECTURA BDI (Creencias, Deseos e Intenciones)
2.5.1 Introducción a arquitecturas ......................................................................................... 18
2.5.3 Modelos de comunicación basados enla arquitectura BDI ..................................... : ..... 20 ................. 20
21 IRMA PRS ................ COSY .............................................................. 23 GRATE'. ..................................................................................................................... .26
2.5.4 Tabla de comparación entre los modelos bajo la arquitectura BDI ............................... 28
2.5.2 Arquitectura BDI (creencias, deseos, intenciones) ....................................................... 18
CAPITULO 3
MODELACIÓN DE AGENTES CON LÓGICAS MODALES
3.1 INTRODUCCI~N ................................. 3.2 PROTOCOLO DE COMUNICACI~N ................................. ................
3.2.1 Definición de protocolo de comunicación 3.2.2 Componentes de un protocolo de comun 3.2.3 protocolo de comunicación y los actos
3.3 CLASIFICACIÓN DE LOS ACTOS DEL HABLA .............. 3.4 INTENCIONES EN COMUNICACI~N ................................................... 3.5 LÓGICA MODAL ........................................................................ 36
3.5.1 Lógica Tempora ...................................................... 37
3.7.2 Sintaxis ...
con la arquitectura BGI ....... .......................... .............................. 53
CAPITULO 4
SIMULACIÓN CON AGENTES INTENCIONALES PARA EQUILIBRAR EL TRÁFICO EN UNA RED DE ÁREA LOCAL
4.1 INTRODUCCI~N ................................................................. 56 4.2 PROBLEMA DE TRÁFICO EN REDES DE ARE LOCAL .............................................. 4.3 ELECCIÓN DEL ALGORITMO PARA EQUILIBRAR EL TRAFICO
EN UNA RED DE AREA LOCAL ................................ JUSTIFICACIÓN DEL USO DE AGENTES ................ 4.4
4.5 ESTAPAS DE SOLUCIÓN ............ 4.5.1 Algoritmo de enrulamiento p 4.5.2 Diseño del algoritmo con agentes intencionales 4.5.3 Implantación del algoritmo con agentes intencionales
ii
4.5.4 Descubrir a sus nodos vecinos .................. ; ................................................................ 64 4.5.5 Medir el retarda para cada uno de los nodos .............................................. 67 4.5.6 Construir un paquete de estado .................... ........................................ 4.5.7 Enviar el paquete de estado ....................................................................... 4.5.8 Calcular la trayedona más coria ............... ............................................. 4.5.9 Descripción de la interfaz gráfica del simulador .......................................................... 72 4.5.10 Resultados obienidos en las corridas de prueba ....................................................... 75
CAPITULO 5
CONCLUSIONES Y TRABAJOS FUTUROS
5.1 CONCLUSIONES .................................................... 5.2 TRAEAJOSF ........................................................................ 5.3 PUBLICACIONES ........ .................................................... 5.4 LECCIONES ............................................................. a3 5.5 APORTACIONES .............................................................. .............................. a4 5.6 BENEFICIOS OBTENIDOS ............................... a4
APÉNDICE A .......................................................... ..............................................................
................................................. ..............................................................
... 111
LISTA DE FIGURAS
Figura 2.1 Caracteristicas de un agente y su entorno ..................................... 11
Figura 2.2 Un sistema multiagente .................................................................. 12
Figura 2.3 Cuadro de análisis y clasificación de investigaciones de agentes ........... 14
Figura 2.4 Arquitectura IRMA ...... ........................................ 21
Figura 2.5 Arquitectura PRS ..... ............................. 23
........................................ 24
........................... 25
Figura 2.6 Arquitectura del agente COSY ......
Figura 2.7 Estructura de un compon
Figura 2.8 Arquitectura funcional G
Figura 3.1 Arboi lógico de creencias
...................................... ~. 26
........................... 44
Figura 3.2 Modelo básico de comunicación .................................................... 46
Figura 3.3 Representación del funcionamiento de un protocolo ..................... 47
Figura 3.4 Un árbol de aplicación para las posibles opciones de un agente ... . 52
Figura 3.5 Representación del funcionamiento interno del protocolo de comunicación propuesto ........................................................ 54
Figura 4.1 Modelo del agente para el algoritmo de enrutamiento
Figura 4.2 Modelo de intercambio de información entre dos
por estado de enlace ............................................................. 60
agentes para el balanceo de tráfico ............................................ 61
.. 62 Figura 4.3 Un ejemplo de una red de área local .................................
Figura 4.4 Representación del funcionamiento del protocolo de comunicación con la preformativa NA-HELLO ...................... 64
Figura 4.5 Interpretación matemática de NA - HELLO y NA-REHELLO .... . . . . . . . 65
Figura 4.6 Ponderación de pesos dentro de una red . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
i V
iv
LISTA DE TABLAS
Tabla 1.1 Características de los diferentes modelos bajo la arquitectura BGI ................................................... 29
Tabla 4.1 Estructura de los vecinos para el nodo local ..................................... 66
Tabla 4.2 Estructura para información de todos los nodos de la red ................ 68
Tabla 4.3 Estructura para vecinos de cada nodo de la red ............................... 68
'Y
Introducción.
CAPITULO 1
INTRODUCCION
INTRODUCCION
1.2 Resumen de trabajo realizado en la tesis.
1.4 Definición del problema.
1.6 Organización de la tesis
1.3 Antecedentes del problema
1.5 Objetivo especifico.
1.6 Beneficios y alcances.
1.7 Fundamento filosófico.
Capitulo 2. Marco teórico.
Capitulo 3. Modelación de agentes con lógicas modales.
Capitulo 4. Simulación con agentes intencionales para equilibrar'el tráfico en una red de área local.
Capitulo 5. Conclusiones y trabajos
I
,
futuos.
I .I INTRODUCCI~N
En el presente capítulo se presenta un panorama general sobre el contexto en que se realizó este trabajo de tesis, presentándose un resumen del tema investigado.
Especificando el problema y sus antecedentes, así como los alcances y limitaciones del mismo. Se explica de forma breve los beneficios que' se obtienen al resolver este problema.
Por lo anterior es que este capítulo de introducción se contesta a las preguntas 'Qué es el problema? ,¿De dónde surge el mismo?, ¿En qué área se ubica y bajo que contexto?. También se presenta explica brevemente la forma en que se desarrollo la solución, presentándose una introducción a cada uno de los capítulos que conforman el presente trabajo y su organización.
/I
1
Introducción.
1.2 RESUMEN DE LA TESIS
El paradigma orientado a agentes surge cuando un grupo de investigadores comienza a estudiar el funcionamiento de sociedades compuestas por seres humanos, con respecto a la forma en que un grupo de personas coopera para trabajar y resolver problemas en forma conjunta. Lo anterior con el fin de implementar este comportamiento en equipos compuestos por computadoras [O’Hare 19961.
Este enfoque de sistemas multiagentes [Nwana 19961 se utiliza actualmente para la solución de problemas de carácter distribuido, los cuales son difíciles de resolver mediante un enfoque centralizado.
Dicha solución consiste en crear un grupo de agentes’, donde cada agente resuelve parte de un problema dado e intercambia resultados parciales para la solución global de un problema dado.
Una característica principal dentro de los sistemas multiagentes es la comunicación. El intercambio de información acerca de resultados parciales sobre un problema, y la forma en que dicha información afecta el desempeño de un agente se llama comunicación de alto nivel.
La comunicación de alto nivel es una técnica de comunicación para sistemas de computadoras, que va más allá del simple paso de mensajes, ya que trata de crear una abstracción sobre la forma en que se presenta la comunicación en sociedades. Involucra la teoria de intenciones en la comunicación, para crear sistemas lo más dinámicos posibles, considerando que la información que se intercambia también es muy variable dentro de estos sistemas.
En el presente trabajo se propone una solución al problema de comunicación en un sistema mulfiagenfe. Por madi0 de un modelo de comunicación entre agentes de tipo intencional, con el uso de la técnica de comunicación de alto nivel. lnvolucrando intenciones y creencias en el proceso de comunicación, desarrollando una arquitectura para el agente bajo la arquitectura BIG Belief, .Intention, Goals (Creencias, Intenciones y Metas).
Lo anterior es sólo un modelo teórico, por lo que es necesario una prueba práctica del mismo. Planteándose una solución al problema de balanceo de tráfico de redes de área local, usando el algoritmo de enrutamiento por estado de enlace programado bajo el modelo de comunicación propuesto con agentes intencionales.
’ Para este trabajo se entiende por agente un módulo de software y/o hardware con características de autonomía, capaz de activar metas específicas y comunicarse con otros agentes. Cada agente es experto como un sistema experto en un área dada.
2
Introducción.
El sistema consta de un agente que reside en cada enrutador dentro de la red, este agente se encarga de crear rutas Óptimas para el envío de información dentro de la red.
El envio de información es aleatorio, es decir, en cuanto el nodo requiera enviar información se crea una ruta. La ruta indicará el camino a seguir para que la información llegue a su destino de acuerdo al estado de tráfico en la red, así como estar observando el estado general de la red, para tomar decisiones adecuadas sobre la ruta más rápida para transportar información.
1.3 ANTECEDENTES
Un enfoque a la solución de problemas distribuidos dentro de la inteligencia artificial distribuida está constituido por los sistemas multiagentes. Los cuales estudian cómo un conjunto de agentes autónomos convive en un medio ambiente, es decir, se comunican e interaccionan entre sí para alcanzar una meta común, creando así una sociedad compuesta por agentes.
Para realizar lo anterior Shoham [Shoham 19931 propone un acercamiento para la , especificación de agentes, que llama programación oíientada a agentes, por hacer una analogía con la programación orientada a objetos. Esto se explica más a fondo en la sección 2.2.
Un sistema multiagente está constituido por un grupo de agentes, donde cada.agente se constituye de componentes esenciales tales como: creencias sobre su medio ambiente, capacidades de realizar acciones, y capacidad para generar varios planes de solución a un problema dado, así como seleccionar la mejor opción.
La estructura en que se acomodan los componentes de un agente y la forma en 1
trabajan internamente estos componentes, para funcionar como sistema establece la arquitectura para el sistema multiagente, la cual se explica en la sección 2.3
Dentro de un grupo de agentes la comunicación se vuelve esencial cuando se tiene ,, un objetivo común (compartido o adoptado), que desean alcanzar cooperativamente. ''
.Por lo que necesitan comunicar el momento en que las acciones empiezan, qué o cuáles agentes las están ejecutando y cuándo termina una acción determinada.
Tomando en cuenta que dentro de un sistema mulfiagente un agente solamente tiene un punto de vista parcial,de la situación del problema a resolver, surge la necesidad , de crear mecanismos de comunicación. Sección 3.2.
Los mecanismos mencionados deben mantener actual y consistente la base de conocimiento (creencias) del agente, realizando revisiones constantes de la información que llegue como nueva con la existente para evitar crear contradicciones en la base de conocimiento [O'Hare 19961.
:'
Introducción.
Por lo anterior los investigadores de sistemas multiagentes han realizado estudios sobre intenciones en comunicación colectivas. Donde consideran la manera en que los miembros de un grupo se comunican para lograr el éxito de sus acciones.
Doyle y De Kleer en O'Hare [O'Hare 19961 proponen un mecanismo, llamado belief (creencia) el cual consiste en una revisión exhaustiva de las bases de conocimientos, y una actualización continua de esta información. Esté es uno de los mecanismos que utilizamos para crear el modelo de comunicación. Se explica en la sección 2.2.5.
1.4 DEFINICIÓN DEL PROBLEMA
Entre los aspectos más relevantes de la problemática asociada con la construcción de sistemas basados en multiagentes, resalta la siguiente:
a) Los agentes de un sistema multiagente requieren poseer capacidad de comunicación que permita a los diversos agentes tener conocimiento del estado global del sistema para la toma de decisiones adecuada
b) Los procesos que trabajan juntos requieren coordinarse para la obtención
Por estos puntos específicamente se delimita el problema creando los siguientes objetivos, que se solucionaran con este trabajo de investigación.
de resultados globales coherentes.
1.5 OBJETIVO
Proponer un modelo de comunicación que permita a los agentes dentro de un sistema multiagente poder compartir información de alto nivel, es decir, compartir sólo la información necesaria para el funcionamiento del agente.
Con este modelo de comunicación se propone una herramienta de diseño para sistemas multiagentes, que ayude en la generación de sistemas con agentes, y en la selección de la información que les proporcione para el funcionamiento interno de cada agente.
Desarrollar un prototipo que demuestre que el uso del modelo de comunicación entre agentes es una alternativa factible, para la solución de problemas en sistemas multiagentes.
'I
4
Introducción.
1.6 BENEFICIOS Y ALCANCES
En este trabajo se considera esencial el diseño de mecanismos para comunicación: ~
basados en los actos esenciales de comunicación y la teoría de intenciones conjuntas para facilitar la comunicacion de alto nivel entre los agentes.
Con el presente trabajo se pretende alcanzar los siguientes beneficios, al diseñar un sistema multiagente:
A) Crear soluciones actuales con respecto al medio ambiente, manteniendo una comunicación eficaz se asegura que la información utilizada en la toma de decisiones es actual, por lo que las bases de datos se consideran consistentes con respecto al medio ambiente en que están trabajando creando así sistemas dinámicos como su medio ambiente lo requiera.
B) Una ventaja es el cambio de acciones de acuerdo como el medio ambiente lo requiera, haciendo una herramienta de diseño versátil en el contexto en que se aplique. Por esto se considera al tipo de agentes intencionales. La investigación se enfoca a obtener las intenciones de los agentes como una medida de compromiso [O'Hare 19961.
C) Aplicaciones diversas del modelo, dada la importancia de la comunicación entre entidades que cooperan, para poder basarse en el concepto integral de comunicación (intencionalidad, cambios de estados en los agentes y un marco común) [Scott 19951 permitirá que el modelo de comunicación .sea más robusto y funcional en una gran diversidad de contextos distribuidos, como redes, sistemas ¡ operativos, etc.
D) Definición de dominios en donde se aplique el modelo, con el modelo de .:
comunicación que se propone también se debe delimitar el contexto del problema en i i
que se desee aplicar el modelo. Desarrollando un medio ambiente con un dominio bien definido de acuerdo al problema que se desea resolver. Esto es importante dentro de un ambiente colaborativo, donde los mecanismos de comunicación juegan un papel importante.
Dentro de los beneficios y alcances que se pretenden con la aplicación del modelo son los siguientes:
E) Reducción de tiempos en envíos de mensajes, al tener agentes que actualicen el estado de la red, se cuenta con datos necesarios para crear una rutas rápidas.
F) Reducción de análisis para cambios de estado en la red, este otro beneficio es por lo mismo al observar constantemente el estado de la red, se puede sab'kr en cualquier momento si un nodo deja de funcionar o si un nodo se agrega a la red,
I.
I
'!
5
Introducción.
1.7 FUNDAMENTO FlLOSOFlCO
Basándose en las ideas filosóficas de Bratman, en este trabajo se considera un modelo diferente a los apoyados en la arquitectura BDI (Belief, Desire, Intentions) tal como lo propone [Rao, 19911 [Cohen 19951. El modelo de agentes que se adoptará se llama arquitectura BIG (Belief, Intentions, Goals), donde los estados mentales de los deseos los hemos eliminado por las siguientes razones:
1. Contradicciones : mientras que las intenciones regulan la conducta de un agente, los deseos pueden provocar estados conflictivos en el mismo. Ejemplo : yo puedo desear ir a Canadá en invierno y deseo ahorrar para un nuevo automóvil.
2. Razonamiento : una intención fuerza al agente a realizar razonamientos para lograr un estado futuro, un deseo no necesariamente lo hace.
Así que en este modelo se parte de un conocimiento del agente (creencias) y codificando las acciones que un agente puede adoptar (intenciones), éste alcanzará sus metas u objetivos (metas). Se explica en la sección 3.3.
I .8 ORGANIZACIÓN DE LA TESIS
El presente trabajo está constituido por los siguientes capítulos:
Capitulo 2. Se proporciona una introducción general a ¡a inteligencia artificial distribuida y sus vertientes de estudio; un panorama general sobre la programación orientada a agentes; los tipos de agentes existentes, haciendo énfasis en los problemas de comunicación y la forma en que se interpreta la comunicación para nuestro estudio y el estado del arte de este problema.
Capitulo 3. Se muestra una introducción a la lógica modal y lógica temporal como los formalismos en que se basa el modelo a desarrollar, y el desarrollo del modelo de comunicación propuesto.
Capitulo 4. Se explica el prototipo en que se prueba el modelo de comunicación, el cual 'fue una simulación de balanceo de tráfico en una red de área local, por medio de un algoritmo de enrutamiento por estado de enlace.
Capitulo 5. Se explican las conclusiones a las que s e , llegó con el presente trabajo y los posibles trabajos futuros.
6
Marco Teórico
CAPITULO 2
MARCO TEÓRICO
2.2.1 Inteligencia artificial distribuida.
2.2.2 Divisiones de la inteligencia artificial distribuida -f’ agentes. !I
2.3.1 Definición de agente.
2.3.2 Características de los agentes.
2.2 Inteligencia Artificial
2.3.3 Tipos de agentes. I,
2.3.4 Problemas relacionados con los agentes -f comunicación bajo una arquitectura establecida para disefiar agentes.
I 2.3 Sistema multiagente
2.4 Problema de Comunicación
2.5 Arquitectura BDI
2.4.1 Esquemas de comunicación
2.4.2 Comunicación de alto nivel. Relacionada con las intenciones de comunicar información -f
Arquitectura BDI
2.4.3 Actos del habla, explicando la filosofía diversos estados mentales dentro del proceso de comunicación.
!/I
componentes. I 2.5.1 Introducción a arquitecturas, definición,y
2.5.2 Introducción a la filosofia de intenciones dentro de la comunicación, definiendo la arquitectura BDI.
2.5.3 Modelos de comunicación basados en la arquitectura BDI.
If
La flecha significa que el tema antes de ella -f deriva el siguiente lema después de la flecha.
,7
Marco Teórico
2.1 INTRODUCCI~N
Este capítulo se divide en cuatro puntos principales, 10s cuales nos sitúan en el contexto en que se abordo este problema. Durante el desarrollo de estos cuatro Puntos nos daremos cuenta de qué herramientas necesitamos para resolver nuestro problema, así como las soluciones propuestas a la fecha.
El primer punto a tratar es la inteligencia artificial distribuida, presentándose una definición del tipo de investigación que tiene a cargo esta área y las aplicaciones asociadas a ella. Se definen las divisiones de esta área de investigación, enfocando nuestro interés a los sistemas multiagentes.
Ubicados en el tipo de investigación de los sistemas multiagentes, continuamos presentando cómo se construye, y las características que debe tener. Los métodos de diseño e implantación establecidos a la fecha, así como los trabajos realizados con relación a estos sistemas.
De esto surge la problemática que se tiene al definir un sistema multiagenfe, la falta métodos válidos para implantarlos. Uno de los problemas que destaca es la comunicación. Por esto se han desarrollado varios trabajos llamados técnicas o esquemas de comunicación.
Dentro de estás técnicas encontramos una de interés para este trabajo, que es la comunicación de alto nivel, Presentamos la composición de esta corriente filosófica basada en la teoría de intenciones en comunicación, así como sus fundamentos y los trabajos realizados en esta corriente.
AI investigar los trabajos^ realizados dentro de la 'teoría de intenciones en comunicación, observamos que se necesita establecer una arquitectura para diseñar a los agentes, donde la arquitectura debe tener una técnica de comunicación, que para nuestro trabajo será la comunicación de alto nivel.
Por lo que continuamos con saber qué es una arquitectura y de que se compone, presentándose un estado de'arte de la arquitectura que se ha aplicado hasta el momento sobre esta este tema, siendo la arquitectura BDI (Creencias, Deseos e Intenciones).
Incluimos una introducción a la filosofía en se basa la arquitectura BDI, mostrando los trabajos realizados sobre esta arquitectura, sus aplicaciones y una breve descripción de ellos.
8
Marco Teórico
2.2 INTELIGENCIA ARTIFICIAL
El tipo de investigación que hace la inteligencia artificial es lograr la construcción de' entidades inteligentes, mediante el estudio y comprensión del comportamiento ~
humano.
Una definición de inteligencia artificial como lo expresa Rich y Knight es: "El1estudio' de cómo lograr que las computadoras realicen tareas que, por el momento, los humanos hacen mejor". [Rich 19911 Está definición abarca una enorme cantidad de subcampos, ya que tiene que ver con todo aquello en donde se aplique el intelecto humano. Uno de estos subcampos es la inteligencia artificial distribuida, que se describe a continuación.
2.2.1 INTELIGENCIA ARTIFICIAL DISTRIBUIDA
Actualmente los sistemas de computación requieren que la solución de un problema sea proporcionada por una colección de procesos independientes, frecuentemente distribuidos en múltiples computadoras autónomas, conectadas a través de redes de comunicación, así como la colaboración de personas.
Esto ha impulsado el desarrollo de la inteligencia artificial distribuida como un área; que desde hace poco más de una década, se ha dedicado a estudiar modelos de comportamiento en sociedades humanas. Así como técnicas de comunicación y razonamiento, utilizando diseiios basados en conocimiento. Integrando una amplia gama de especializaciones necesarias para participar en sociedades compuestas por computadoras y personas [Lander 19971 [Scott 19951.
2.2.2 DIVISIONES DE LA INTELIGENCIA ARTIFICIAL DISTRIBUIDA
Generalmente la comunidad de investigación en inteligencia artificial distribuida distingue dos áreas principales dentro de ella [Nwana 19961, las cuales son:
Solución de problemas distribuidos (SPD). Que estudia cómo un problema particular puede ser dividido en diversos módulos que cooperan compartiendo conocimiento para resolver problemas En un sistema de solución de problemas distribuidos puro, todas las estrategias de interacción se incorporan como una parte integral del sistema [O'Hare 19961.
I
Sistemas multiaqentes (SMA). Estos se ocupan de la conducta de una colección de agentes que resuelven un problema dado [Gamble 19981.
Marco Teórico
Un sistema muifiagenfe puede definirse como "una red de resolvedores de problemas débilmente acoplados', que van más allá de sus capacidades individuales" [Durfee 19891.
2.3 PARADIGMA DE PROGRAMACIÓN PARA SISTEMAS MULTIAGENTES
2.3.1 DEFINICI~N DE AGENTE
En la actualidad existen varias definiciones de agente, sin tener una definición establecida. Por eso para el contexto de este trabajo un agente es "un sistema capaz de percibir y actuar en su medio ambiente" [Guerra 19971. En términos computacionales un agente es considerado como una unidad de software con características especiales para participar en sociedades compuestas por computadoras y gente.
2.3.2 CARACTERkTlCAS DE UN AGENTE
Por la definición anterior el comportamiento general de un agente no es necesariamente una composición lineal de los módulos que lo componen, puede emerger de las interacciones del comportamiento generado por los módulos individuales que lo forman. De acuerdo a Shoham se ha desarrollado una nueva forma de programar, a la que le llama programación orientada a agentes [Shoham 19901, donde cada agente cuenta con las siguientes características:
Conocimiento de su mundo por medio de una entidad, cuyo estado consiste de componentes mentales tales como creencias o base de datos.
Obligaciones o función principal del agente.
Capacidades de razonamiento, es decir, generación de alternativas para posibles soluciones a un problema dado. Y decisión al elegir la alternativa para la solución del problema.
Enlazando las características de un agente inteligente y su definición, deducimos que un agente para alcanzar una meta a futuro, considera el conocimiento que posee y la información proporcionada por los otros agentes (creencias).
Además utiliza sus capacidades de razonamiento. y decisión, para evaluar un conjunto de alternativas y seleccionar la mejor solución, (decisión) de esta manera alcanza la meta previamente establecida [Scott 19951.
I
* Con débilmente acoplados se interpreta que los procesos son independientes, y que no necesitan esperar algún tipo de activación para ejecutar alguna acción.
. .
10
Marco Teórico
CAPACIDADES restringen Métodos de solución de problemas
Cuando un agente toma una decisión, determina un conjunto de acciones que debe llevar a cabo. En la figura 2.1 se muestra la forma gráfica de representar las características internas que constituyen a un agente.
I
Figura 2.1 Características de un agente inteligente y su entorno.
2.3.3 TIPOS DE AGENTES
Existen diferentes tipos de agentes, agrupados en categorías de acuerdo a sus capacidades de solución de problemas [O'Hare 19961. A continuación se muestra una clasificación de acuerdo a las capacidades específicas de cada agente:
¡I
Aaente reactivo: este tipo de agente reacciona a cambios en su ambiente, l. ~
es decir, a mensajes de otros agentes. Este tipo de agentes no es capaz de razonar sobre sus intenciones. Sus acciones son realizadas como /I resultado de la ejecución de reglas previamente establecidas. Un claro ;i ejemplo de este tipo de agentes son los sistemas expertos de primera generación. li
Aaente intencional: tiene la habilidad de razonar sobre sus intenciones y creencias, creación de planes para ejecutar acciones, así como ejecutar ii estos planes, estos tipos de agentes pueden ser considerados como sistemas planificadores, que pueden seleccionar sus metas y razonar sobre ellas. En un sistema mulfiagenfe, con agentes intencionales se coordinan y cambian información acerca de sus creencias, metas o acciones.
Aaente social: posee modelos explícitos de comportamiento acerca de ;,
otros agentes, también debe tener la habilidad de actualizar estos modelos. ,, Razonar sobre el conocimiento incorporado a estos modelos, así como tomar decisiones y crear planes con respecto a otros modelos de agentespcott 19951.
0 0 - 0 0 0 2 1'1
Marco Teórico
En este trabajo el problema que se desea resolver es de comunicación y no de coordinación explícitamente. Por esto se eligió trabajar con agentes intencionales, ya que cumplen con la definición en general de agentes, sin ser ,tan complicados como los sociales, en el aspecto de actualizar modelos de otros agentes.
t
2.3.4 SISTEMA MULTIAGENTE
Lo anterior nos expone las características generales de cualquier agente, lo independiente que deben ser, además de autónomos, esto es un concepto fundamental para nuestro estudio.
Ahora definimos que es un sistema multiagente, el cual está formado por más de un agente cooperando en forma conjunta para la solución de un problema dado.
Un sistema multiagente lo podemos representar como en la figura 2.2, se muestran dos agentes convivie,ndo en un ambiente común, donde cada agente tiene sus características individuales e independientes del otro agente. La Única forma para intercambio de información es por medio de un modelo de comunicación.
1 Ambiente 1
Bases de creencias, deseos, intenciones
COMUNICACI~N
Bases de creencias, deseos, intenciones
1 I
+ + + Módulos de Procesamiento
Canal de Canal de h m Figura 2 2 Un sistema multiagente
12
Marco Teórico
2.3.5 PROBLEMAS RELACIONADOS CON SISTEMAS MULTIAGENTES
Esta forma de solucionar los problemas no es muy reciente data de finales de los 1970 cuando Carl Hewtti's de acuerdo a un' artículo den Nwana [Nwana 19961' propone el concepto auto-contenido en programas llamándolos actores, que con el! transcurso del tiempo fue evolucionando para convertirse en un nuevo paradigma de programación e investigación orientado a agentes.
Las investigaciones realizadas para el establecimiento de alguna metodología en la construcción de sistemas multiagentes continúan abiertas.
Cuando se crea un sistema mulfiagenfe, se debe hacer una abstracción de las situaciones del mundo real en que se aplicaría el sistema, Primero se estudia el comportamiento de los expertos que conforman el sistema, para simularlos con agentes y poder crear una sociedad compuesta por agentes. AI hacer esto nos enfrentamos con una serie de conflictos al establecer los conceptos que se aplicarían al sistema mulfiagenfe.
Dichos conceptos causan cierta polémica en términos computacionales, el escuchar palabras como autonomía, actos del habla, estados mentales del sistema, toma de decisiones, y algunos otros conceptos que se manejan en esta área de sistemas mulfiagenfes.
Además de los problemas que se presentan en la definición de conceptos en está área, se tienen otros problemas al disenar la estructura interna que tenüra cada agente propiamente.
O'Hare [O'Hare 19961 clasifica los problemas relacionados con la estructura intern'C, de un agente y los problemas al crear un sistema mulfiagenfe como se muestra en el cuadro figura 2.3, donde hace una abstracción del análisis relacionado con la's investigaciones realizadas en este campo de sistemas mulfiagenfes.
Primero se presenta la perspectiva del agente, es decir, los puntos importantes qub se contemplan al construir un agente internamente, tomándolo como un programa independiente y autónomo.
Después en la perspectiva de grupo, destacan los puntos a considerar al tener un grupo de agentes para construir un sistema multiagente. El agente debe saber como esta ubicado en el sistema, con quienes puede intercambiar información y de que tipo. i
Se observa también con letras negritas el problema específico en que se enfoca esta tesis, situada en el contexto de sistema mulfiagenfe.
143
Marco Teórico
Comunicación +
Categoría del agente (que tipo de agente). Estructuras para mantenimiento de conocimiento.
Habilidades de adaptación y aprendizaje. Arquitectura del agente (diseño interno de los módulos).
Habilidades de razonamiento (funciones).
Primitivas de comunicación. Planes ó Pase de mensajes. Intercambio de información usando pizarrones. Comunicación de alto nivel. Interacción máquina-persona.
Figura 2.3 Cuadro de aná1isis.y clasificación de investigaciones en agentes (O’Hare G.M.P. and N.R. Jennings Foundations of Distributed Artificial Intelligence Wiley;
1996, p. 7, traducción de la tesista )
AI construirse por más de un agente un sistema multiagente debe tener la habilidad de compartir datos e intercambiar información entre las unidades de software que lo componen, requiriendo un soporte de interoperabilidad en varios niveles de abstracción como los observados en la figura 2.3.
También se debe considerar que un sistema constituido por agentes es demasiado cambiante, por esto la solución al problema de comunicación debe utilizar un modelo de comunicación que no sea tan dependiente de un lenguaje de programación.
El modelo de comunicación debe estar en un nivel de abstracción que indique cómo se está llevando a cabo la comunicación, y cómo se interpretan las características que conforman a un agente [Lander 19971. Esta inquietud se une a la expresada por ofros investigadores del área de sistemas multiagentes como lo expresa Bond y Gasser que habla sobre un enfoque de compartir información [Bond 19921.
14
Marco Teórico ::
2.4 PROBLEMA DE COMUNICACI~N
2.4.1 ESQUEMAS DE COMUNICACI~N
Entre las soluciones propuestas para el problema de comunicación e intwcambio de.' mensajes se presentan las técnicas generales de comunicación, en que se basan losl modelos de comunicación para el diseno de agentes [O'Hare 19961:
1. Sin comunicación. Se usa la teoría de juegos, utilizando matrices que almacenan los posibles resultados de agentes para cada iteración, de esta forma un agente solo infiere los planes de otros agentes sin necesidad de pasarle información, exigiendo un conocimiento común de reglas en información para realizar acciones.
2. Pasando planes y pase de mensajes. Este pase de mensajes es total o 11
parcial de la información entre los agentes involucrados, siendo costoso de hacer en computación y difícil de realizar.
3. Intercambio de información a través de pizarrón. Es un modelo donde se comparte memoria denominado repositorio, sobre el cual los agentes escriben mensajes, colocan resultados parciales y obtienen información de otros agentes. Los repositorios están divididos en niveles de abstracción para un problema dado. Los agentes tienen diferentes tipos de acceso , dentro del pizarrón, cuya información puede ser actualizada o sólo consultada. 1:
4. Comunicación de alto nivel. Este tipo de técnica se basa en las ' investigaciones hechas sobre la comunicación en el lenguaje natural. 1; Acerca de cómo es posible hacer intercambio de mensajes entre múltiples 11; agentes con distintas intenciones y posiblemente contradictorias, tomando los estados como creencias, hechos e intenciones. Esta técnica examina la 4 transformación de los diálogos a creencias e intenciones en la 11 comunicación.
5. Interacción máquina persona. Esta técnica define que todos los integrantes ;:
de un sistema, soportan tareas intelectuales cooperativas. Aquí los agentes , computacionales, sólo asisten a las personas en diferentes caminos, para coordinar las acciones que solucionen el problema dado.
~
'
Las anteriores son técnicas generales para llevar a cabo una comunicación entre agentes, las cuales se deben complementar con un modelo o metodología de programación, que proporcione el comportamiento y estructura general de un agente, la perspectiva del agente, así como una base formal que respalde el modelo [Scott 19951.
Marco Teórico
2.4.2 COMUNICACI~N DE ALTO NIVEL
Como se mostró en el punto anterior, existen varias técnicas de intercambio de información, dichas técnicas van desde las que no involucran comunicación, hasta los que involucran una sofisticada comunicación, como la comunicación de alto nivel que es el punto central de este trabajo.
Dicha técnica de comunicación se basa en la teoría de comunicación propuesta por Cohen y Levesque [Cohen, 19881 [Cohen 1990bl [Keith 19981 [Munindar 19911. Ellos proponen tomar en cuenta estados mentales durante el proceso de comunicación, derivados de una teoría formal de interacciones basada en compromisos e intenciones que abarca la comunicación.
Varios autores entre ellos El-Fallah, [El-Fallah 19991, Nwana [Nwana 19961, Rao [Rao 19911, y Scott [Scott 19951, se han unido a esta teoría definiendo el intercambio de mensajes para los agentes, como los actos del habla que se presentan en la comunicación entre humanos. Los cuales se interpretan como solicitudes, Órdenes o promesas, manteniendo las capacidades de razonamiento por medio de estados mentales. Las conversaciones pueden ser vistas como interacciones coordinadas cooperativamente. Para comprender como es que se conforma este tipo comunicación, definimos primero los actos del habla.
2.4.3 ACTOS DEL HABLA
En la teoría de los actos de/ habla las expresiones humanas son vistas como acciones, en el mismo sentido que las acciones son ejecutadas en el mundo real. El estudio de estás expresiones nos ayuda a encontrar la forma en que se'conformara el modelo de comunicación basado en la comunicación entre humanos. Un ejemplo de comprensión de actos del habla es el siguiente:
La expresión "favor de cerrar la puerta" dicha en forma general en una sala con un grupo de personas, genera un proceso en el cual todas las personas presentes atienden dicha expresión, pero solamente la persona que esté cerca de la puerta es la que al escuchar la frase la toma como petición generando una acción, las otras personas escuchan.la expresión la procesan y desechan al darse cuenta que no es una acción que puedan ejecutar.
Esta teoría de los actos del habla considera tres efectos, en el .proceso para atender una expresión que son los siguientes:
Locucionario, se refieren a la interpretación de las expresiones, por el agente en un acto del habla. En otras palabras las expresiones que acepta un agente, con respecto a su estructura, en algún lenguaje propuesto.
16
Marco Teórico
En el ejemplo de "favor de cerrar la puerta", se estableció previamente un alfabeto de símbolos a ... z, con respecto a este conjunto de símbolos, las reglas para formar palabras válidas dentro de este lenguaje la, de, .cerrar...., y la forma en que dichas palabras se colocan para formar una oración como sujeto verbo predicado.
favor de cerrar la puerta
sujeto verbo predicado QQQ J oración válida
Ilocucionario, se refiere al tipo de acción a ejecutar, que indica explícitamente la expresión. La parte importante en las expresiones es la acción a ejecutar, que nos indica el verbo denominado performativo (performatives) algunos ejemplos de estos verbos son: "requerir", "advertir", "informar", etc.
En el ejemplo de "favor de cerrar la puerta", se toma directamente el significado de las partes que componen la expresión emitida, como no se encuentra el sujeto explícitamente, se debe asignar un nombre por lo ,/
que favor de se interpreta cómo, quien sea.
La base del aspecto ilocucionario es la acción que nos indica el verbo. :
Dicha acción será realizada por el sujeto, complementándose por el predicado que es el contexto sobre quien se realizará la acción indicada, en este caso cerrar que es el verbo y de acuerdo al predicado la puerta, que es sobre quien se tiene que realizar la acción de cerrar.
'
.O Perlocucionario, se refiere al efecto implícito que causa el escuchar una expresión, cómo influenciará esta al receptor en el contexto de aplicaciones basadas en agentes.
En el ejemplo el efecto que causará, es sobre el agente que esté cerca , de la puerta, porque al escuchar la expresión el sujeto cercano a la ,
puerta recibe el mensaje y asume ser el sujeto quien sea (como se interpretó en el aspecto ilocucionario).
El efecto que causa sobre el agente cercano a la puerta es un cambio r de acciones inmediatas sobre la que este ejecutando, para tomar la expresión como orden y ejecutar la acción que se pidió de "cerrar la puerta". Este es el efecto perlocucionario, en este ejemplo.
Los verbos performativos corresponden a la fuerza de las expresiones para algún lenguaje de comunicación, en el que existen suposiciones implícitas acerca de acciones a realizar dentro de expresiones ilocucionarias, ya que al enviar un mensaje (efecto iocucionario) los agentes comunican la necesidad de que se realice una acción (efecto ilocucionario).
17
Marco Teóflco
Una acción se interpreta como intención inicialmente, para posteriormente ser transforma a meta, pasando primero por las creencias y verificar su congruencia con el medio ambiente actual (estado actual del sistema), para finalmente llegar a ser meta (efecto per1ocucionario)que es la acción a ejecutar de algún hecho real.
En el proceso ilocucionario el agente espera que las expresiones sean entendidas como intenciones, para la realización de alguna acción en el agente receptor. Cuando el agente emisor no tiene control sobre la influencia que causen las expresiones enviadas, la expresión no se considera perlocucionaria [Nwana 19991.
2.5 ARQUITECTURA BDI (Creencias, Deseos e Intenciones)
2.5.1 INTRODUCCION A ARQUITECTURAS
En los puntos anteriores de este capítulo se abordaron las características que debe tener una unidad de software para considerarse agente, también se presentaron las diferentes clases de agentes, y los problemas que se tienen cuando se desea crear un sisfema multiagentes. En esta problemática resalta la comunicación, se mostró el enfoque de este trabajo para solución de la comunicación. Por medio de actos del habla, estados mentales, así como las creencias que tiene cada agente, falta presentar la forma en se unen dichas características para comenzar a diseñar sistemas multiagentes, con las técnicas de programación ya explicadas. '
La metodología a seguir para programar sistemas multiagentes, es por medio de arquitecturas, que indican cómo se están interpretando cada una de las partes que forman un sistema de este tipo, además de cómo diseñarlo una arquitectura deacuerdo a su definición, "La arquitectura debe administrar una infraestructura de comunicación para facilitar el intercambio de datos, en un lenguaje compartido y un protocolo de comunicación, que asegure la ejecución de los agentes en tiempos adecuados" [Lander 19971.
2.5.2 ARQUITECTURA BDI (Belief, Desire, Intention)
Una arquitectura muy utilizada es la BDI (Belief, Desire, Intention) que corresponde a creencias, deseos e intenciones. Cuyo autor principal es Bratman [Bratman 19871, dicha arquitectura se basa en la definición general de un agente, por lo que les atribuye actitudes mentales para cumplir con la autonomía que todo agente debe tener, las actitudes mentales son: creencias, deseos e intenciones.
Kiss agrupa la estructura con actitudes mentales en las siguientes tres categorías [Kiss 19921:
o Congnoscitivo, como creencias y conocimiento mejor conocidos como entradas de un sistema.
Marco Teórico 1
Connotativo, 'como intenciones, planes y compromisos, que están relacionados con las acciones a realizar así como el control que se debe aplicar sobre ellas. Esto es el proceso interno para crear una solución. ::
Afectivo, aquí interfieren deseos, metas y preferencias, ya en lenguaje computacionai los llamamos salidas.
Las creencias que tiene un agente se toman del medio ambiente que lo rodea, es decir la base de datos con la que van a contar y los método's para su constante actualización. Los deseos e intenciones se refieren a las diversas soluciones que, genera el agente con los métodos que tiene programados, antes de tomar una acción a ejecutar, los deseos junto con las intenciones tienen el control sobre las diversas
I
propuestas de solución así como la elección de una de ellas. !!
La .diferencia entre deseos e intenciones es que las intenciones son una medida de obligación, asociadas con guías y controles que aseguran un comportamiento consistente, para actividades futuras del agente. Mientras que un deseo, salirse de¡ límite de las capacidades del agente o crear inconsistencias [Cohen 19951.
AI requerir una acción que no tiene un grado de compromiso, no necesariamente se fuerza a ser validada una acción, por la base de conocimientos que se tiene y de las capacidades para que fue hecho el agente. Más adelante trataremos este tema a detalle. /I
Con respecto a las intenciones, que son tomadas como guías para determinar la conducta de un agente, algunos autores como Cohen y Levesque [Cohen 19901 basaron sus desarrollos en esta arquitectura de Bratman [Bratman 19881, dicho trabajo fue tomado como base para otros avances, los cuales procuran describir, analizar y especificar el comportamiento de los agentes, por medio de relaciones existentes entre creencias, deseos e intenciones.
Dentro de la arquitectura BDI se han desarrollado modelos de comunicación, para programar orientado a agentes. Los modelos con la arquitectura BDI de agentes, existen para una amplia variedad de aplicaciones, en particular para aplicaciones de ambientes dinámicos y con acciones racionales para responder a cambios en tiempo real, dado que el comportamiento general de un agente no es necesariamente un Comportamiento lineal de los módulos que lo conforman.
Para establecer una idea más clara de lo que se pretende desarrollar con el'presente trabajo, a continuación presentamos los modelos realizados a la fecha bajo la arquitectura BDI. La estructura que fue definida para cada modelo, y la forma en que se interpretaron los componentes que conforman cada modelo o protocolo db comunicación. Así como el funcionamiento interno de los módulos que forman los esquemas.
19
Marco Teórico
2.5.3 MODELOS DE COMUNICACI~N BASADOS EN LA ARQUITECTURA BDI
IRMA
IRMA (intelligent resource-bounded machine architecture) por sus siglas en inglés, es una arquitectura para una máquina inteligente con límite de recursos, donde los recursos son referencias primarias de limitaciones con respecto al poder computacional [Bratman 19881. Este diseño Utiliza una especie de razonador sobre medios y fines para un problema planteado, al seleccionar la mejor alternativa tomando en cuenta los límites que tienen sobre sus recursos. Este modelo hace una representación indirecta de creencias, deseos e intenciones.
La figura 2.4 muestra que la estructura de IRMA almacena diferente información (indicados con Óvalos) y procesos (indicados con rectángulos). Está información es almacenada como creencias, deseos, librería de planes, intenciones estructuradas en planes. Existe una diferencia entre planes los que son recibidos y los que son adoptados para ejecutar [O'Hare 19961.
La librería de planes, contiene los planes que son vistos como un subconjunto de creencias en los agentes, revisan cuales planes son aplicables para realizar ciertas tareas y las circunstancias para su realización. Los planes posteriores son los que están ejecutando actualmente, correspondiendo a intenciones que son almacenadas en Estructuras de lntenciones dentro de Planes.
Los procesos razonamiento de medios y fines, e l analizador de oportunidad, los mecanismos de filtros y la deliberación, son los que tienen acceso a deseos, intenciones y planes en la información almacenada.
*:* El razonador de medios y fines es invocado por cada plan parcial existente, para hacer el subplan que lo complete. Puede proponer un número de opciones para satisfacer el mismo significado.
*3 El analizador de. oportunidad es el componente que propone opciones
e:* El fWro de compafibilidad verifica si una opción es compatible con las intenciones de agentes existentes, de ser así pasa a deliberación de procesos. Una opción que se estima incompatible puede pasar a traves del mecanismo de filtros de rechazo los cuales corren en paralelo.
Q Mecanismo de filtros de rechazo,,el principal propósito es limitar' la cantidad de requerimientos computacionales por la deliberación en razonamientos prácticos.
03 La deliberación de procesos, procesa amplias opciones de competencia contra otras y actualiza las estructuras de intenciones dentro de planes.
como resultado de cambios en el ambiente.
,. . . 20
. . .
Marco Teórico
Filtros de Compatibilidad
I
intenciones
Oportunidad de medios y
fines
Mecanismos de Filtros de rechazo
I , \opciones .. 1 Opciones r I a I I , . I I
I I , I I ' ' I I I I opciones de supervivencia
I I
Intenciones /¡
'I:
Figura 2.4. Arquitectura IRMA (Bratman 1988) (O'Hare G.M.P. and N.R. Jennings Foundations of Distributed Artificial Intelligence, Wiley?
Interscience, 1996, p, 172, traducción de la tesista )
PRS i
PRS (procedural reasoning system) por sus siglas en ingles sistema de razonamiento procedural, cuyos autores son Goergeff y Lansky 1987, George e lngrand.1989 en O'Hare [O-Hare 19961. Este sistema razona sobre las tareas ejecutadas en ambientes dinámicos. En PRS las actitudes acerca de creencias, deseos e intenciones están representadas explicitamente, y juntas determinan acciones para el sistema en cualquier instante dado [Rao 19911 [O'Hare 19961. :,
Marco Teórico
Los componentes que constituyen esta arquitectura son: bases de datos, metas, librerías de áreas de conocimiento, estructura de intenciones e intérpretes.
Las bases de datos contienen hechos o creencias actuales acerca del mundo, El conocimiento que contiene la base de datos es necesario para completar tareas, y poder reaccionar bajo ciertas circunstancias encapsuladas en especificaciones de procedimientos declarativos, llamados áreas de conocimiento (AC).
Cada área de conocimiento (AC) tiene un cuerpo, consistente de procedimientos por pasos e invocación a condiciones que se describen dentro de las condiciones aplicables a cada AC. La librería de /as areas de conocimiento hace una aplicación de dominios por medio de meta-niveles, y de un conjunto de sistemas dependientes por omisión. Un meta-nivel incluye el tipo de conocimiento que requiere para la acción a ejecutar, además hace un razonamiento sobre la manipulación de creencias, deseos e intenciones por el PRS mismo. La selección del meta-nivel puede ser a través de otros meta-niveles dentro de las areas de conocimiento.
Las metas representan el comportamiento deseado del sistema, es decir el estado estático del mundo a ser activado. Los autores distinguen dos tipos de metas: intrínsecas-y operacionales.
*:e Las metas intrínsecas no están relacionadas con alguna meta existente y son consideradas como un resultado de la obtención de nuevas creencias acerca del mundo.
0:. Las metas operacionales tienen relación con alguna acción presente.
Las intenciones en PRS son tareas que el sistema ha elegido para ejecutar de inmediato o en un tiempo cercano. Una simple intención consta de algunas áreas de conocimiento iniciales para cumplir una tarea, junto con otras sub-áreas de conocimiento involucrados para realizar dicha tarea. Las intenciones del sistema son insertadas dentro de una estructura de intención, de acuerdo a su precedencia. Su orden puede cambiar como resultado de la ejecución de algunos meta-niveles de las áreas de conocimiento.
Una intención puede estar en uno de los tres estados posibles: activo (ejecutándose actualmente), suspendido (no ha hecho una decisión para su ejecución) o condicional suspendido (esta en espera hasta que se cumpla alguna condición de activación).
La operación del intérprete PRS corre en el sistema por completo y puede ser conceptualmente descrita como sigue: cuando el sistema tiene alguna meta, mantiene algunos conocimientos en su base de datos. Estas metas y creencias comienzan a ser aplicables para un subgrupo en áreas de conocimiento, donde si una de estas áreas de conocimiento es elegida para ejecutarse, es situada dentro de una estructura de intención. Durante la ejecución de una intención nuevas submetas son producidas e introducidas en la pila de metas del sistema, para las cuales otros ciclos de razonamientos finales tomarán su lugar.
1
22
Marco Teórico '
.Aunque algunas creencias o metas activas son nuevas en las áreas de conocimiento, el sistema trata primero las intenciones que ya fueron decididas previamente. LO anterior se hace para centrarse en la forma en que las metas directas serán introducidas, por medio de un razonamiento análogo sobre las áreas de; conocimiento, expandiendo la ejecución de subrutinas en el sistema de programación procedural. PRS razonará sobre sus creencias e intenciones actuales y tal vez elija trabajar con algunas otras metas.
Las áreas de conocimiento involucradas no son sólo resultado de metas propuestas, son como una reacción a ciertas condiciones en el ambiente. En estas entradas el agente no excede las intenciones y toma los cambios en el ambiente a considerar. La figura 2.5 muestra gráficamente la arquitectura antes descrita.
(Razonador)
Figura 2.5. Arquitectura PRS (Goergeff e lngrand 1989 ) (O'Hare G.M.P. and N.R. Jennings Foundations of Distributed Artificial Intelligence, Wiley
Interscience, 1996, p. 174, traducción de la tesista )
COSY
La puesta en marcha de COSY (cooperating knowledge-based systems) fue L proyecto de investigación para aplicarlo a sistemas de cooperación basados en conocimiento. Este modelo describe a un agente por sus intenciones, comportamientos, acciones, percepciones, los recursos requeridos por intenciones completadas'y ejecución de comportamientos. Distinguimos dos tipos de intenciones llamadas:
intenciones estratégicas, se utilizan en términos de grandes metas, actitudes, papeles, responsabilidades. Menciones tácticas, las cuales son límites directos de las acciones de un agente.
23
Marco Teórico
Utiliza protocolos de cooperación representados con estereotipos de diálogo, dentro de un patrón específico de operación como contratación. Correspondiente al componente del protocolo de ejecución (CPE), verifica y administra la ejecución de protocolos de cooperación, preparando mensajes que van a ser enviados y procesando mensajes recibidos con un protocolo en particular. En la figura 2.6 se presenta la arquitectura COSY.
INTENCIONES
CRDR ............ ............. + ....,
SENSORES
I COGNOSCITIVO
Figura 2.6 Arquitectura del agente COSY (O'Hare G.M.P. and N.R. Jennings Foundations of Distributed Artificial Intelligence, Wiley
Interscience, 1996, p. 176, traducción de la tesista )
La arquitectura COSY es modular, compuesta por los siguientes módulos: ejecutores, sensores, comunicación, intenciones y cognoscitivo.
El módulo cognoscitivo consiste de una base de conocimientos (BC), componente de ejecución como guión (CEG), componente del protocolo de ejecución (CPE), y componentes "razonando, decidiendo y reaccionando" (CRDR) figura 2.6.
El cognoscitivo trata el compromiso que tienen las intenciones tácticas para su formación, revisión o abandono. Este módulo implementado como un sistema basado en conocimiento, evalúa el conocimiento percibido y prepara la acción apropiada para una situación dada por las consultas del módulo de intenciones.
La tripleta "creencias, deseos e intenciones" es directamente representada y aprovechada en COSY como: su base de conocimientos que contiene las creencias, los deseos están representados en el módulo de intenciones, los guiones elegidos, y las intenciones codificadas en protocolos.
La solución de un problema es independiente del dominio, ya que se basa en guiones y protocolos de cooperación. Un guión es un estereotipo de receta o plan de activación en tareas especificas, este guión contiene llamadas a otros guiones, protocolos, y comportamiento primitivo.
24
Marco Teórico :
+i Componentes j
Los comportamientos primitivos, son "planificadores" realizados por el proceso de: ejecutores. El componente cognoscitivo de ejecución como guión (CEG), administra la ejecución de los guiones, delegando la ejecución de comportamientos primitivos al los ejecutores y la ejecución de protocolos de cooperación al componente del protocolo de ejecución (CPE).
Los componentes "razonando, decidiendo y reaccionando" son responsables de la interpretación del medio ambiente, y reaccionan si la situación lo demanda, deliberando cual es la mejor intención que pueda ser convertida en meta.
Los componentes "razonando, decidiendo y reaccionando" se componen de una agenda, una estructura de intención y procedimientos para operación de esa estructura de datos, que esta constituida por guiones, requeridos como entradas a procedimientos.
Los guiones son puestos en las agendas como resultado de la percepción de otros agentes en situaciones actuales por sensores y comunicación. En la figura 2.7 se muestra un esquema de esta estructura
7 !I
li
!!
,I
1 ComponenteE
Guioi;ies aplicables
,... ........................... .~:: ..................................... ....................................................................
Filtros ! I
~ ...................................................................... + !
I I Guiones uara I Ejecución 2, ,
Guiones de Suspención
-1
Intra - protocolos de Decisión
j/ Figura 2.7 Estructura de un componente RDRC
(O'Hare G.M.P. and N.R. Jennings Foundations of Distributed Artificial Intelligence, Wiley I
Interscience, 1996, p 174, traducción de la tesista )
El módulo RDRC (razonando, decidiendo, y reaccionando) junto con sus componentes se ejecuta en forma lineal, con procedimientos especiales llamado's
reaccionando", utilizan primero al procedimiento filtro después el control es dividido en dos direcciones, una para el procedimiento de deliberación y otra por el procedimiento de reacción.
filtros, reacción y deliberación. Los componentes "razonando, decidiendo y I
25
Marco Teórico
El filtro proporciona la prioridad a la segunda clase de guiones antes considerados, éstos se refieren a los planes de agentes existentes en las. metas actuales. Los guiones de la última categoría requieren deliberación, la cual es ejecutada por dicho procedimiento refiriendo a intenciones estratégicamente dentro del módulo de intenciones.
GRATE’
El agente de arquitectura funcional [Jennings 19931 reensambla IRMA adicionando componentes que incorporan soluciones a problemas cooperativos. Utilizando el concepto de unir intenciones con un grado de responsabilidad para establecer una actividad de colaboración en grupo, y observar la ejecución de actividades unidas. GRATE* ha sido implantado y probado en aplicaciones reales en administración del suministro de electricidad. La figura 2.8 muestra un esquema de esta arquitectura.
Comunidad de Eventos Eventos Locales Actos Relacionados
b Control de Ejecución b Fallas de Compromisc
Nuevos Objetivos
Objetivos Locales Nuevos Análisis de Actos Sociales Nuevos
1 Significados Finales
Verificador d Habilidades v
Participantes Potenciales intenciones
Inconsistentes 4 A
intencioneS , Modificadas
Verificador d
Definidos
Figura 2.8 Arquitectura funcional GRATE* (O‘Hare G.M.P. and N.R. Jennings Foundations of Distributed Artificial Intelligence, Whey . Interscience, 1996, p. 179, traducción de la tesista) !
26
Marco Teórico
L~~ eventos ocurren como resultado de problemas locales O cambios en e\ ambiente,: manifestando una necesidad potencial para la realización de nUeVOS objetivos. Estos! nuevos objetivos sirven WmO entradas al proceso de análisis para resultados finales, tomando en .cuenta la existencia de un nuevo objetivo.
El analizador de resultados finales hace una consulta en las librerías existentes para crear un -plan apropiado al nuevo objetivo, de esta forma el analizador de resultados finales considera como afectan las intenciones actuales a los nuevos objetivos y: verificar que las actividades actuales sean consistentes con la actividad futura.
Si el analizador de resultados finales resuelve que el agente tome la intención loca) como nuevo objetivo, debe asegurarse de que este satisfaga al objetivo que existía antes además de ser compatible con las intenciones existentes. Si los result.ados de compatibilidad localizan una inconsistencia, entonces el proceso de solución de inconsistencias intenta modificar los compromisos existentes o cambiar los objetivos para remover el conflicto existente.
Los elementos de control en este proceso de solución para inconsistencias son sobre las preferencias o deseos del agente. Comúnmente las tareas menos importantes son expuestas a modificaciones, en la mayoría de los casos el resultado sobre el proceso en conflicto requerirá de un análisis completo de resultados finales. 'I
Cualquier solución hecha por el mecanismo de soluciones se refleja en la representación de intenciones. Si el resultado del analizador de significados finales toma la.decisiÓn de realizar objetivos colaborativos, entonces se debe establecer una acción social. I
El primer paso es identificar los agentes de la comunidad que están interesados en formas parte de esta solución (miembros potenciales), una vez identificados los miembros potenciales existen un esqueleto de intenciones unidas donde sus participantes registran sus intenciones, pero no han hecho selección de grupo para una solución en común, sólo se hace la formación del grupo de trabajo.
La segunda fase es la finalización fuera de línea de un objetivo y orientación de acciones individuales a ejecutar para alcanzar el objetivo planteado.
Como resultado de la generación y selección del plan las funciones de asignación son transferidas a otros miembros del grupo para ejecuciones locales, las cuales son incluidas dentro del analizador de resultados finales donde las acciones principales se adaptan a las obligaciones existentes, mientras se satisfacen las relaciones asociadas a sus acciones.
Cada vez que una nueva acción individual o en conjunto es propuesta el verificador de inconsistencias verifica la coherencia entre intenciones unidas e individuales.
.I
27
Marco Teórico
En GRATE* las intenciones no sólo proveen significados de concordancia para acciones,, también actúan como guía para tareas de ejecución y verificación. Los problemas del nivel de dominio son presentados como tareas atómicas de procesamiento cuando son vistas por las leyes de control y cooperación.
Los monitores de eventos, analizador de resultados finales, verificador de compatibilidad, el proceso para solución de inconsistencias y verificador de consistencia son orientados dentro del módulo contribución de situación.
El módulo de cooperación es responsable de identificar el potencial de los participantes. La librería de recibidores, intenciones, unión de intenciones y deseos se almacena en el mismo modelo, y las capacidades de otros son almacenadas en el modelo.
2.5.4TABLA DE COMPARACIÓN ENTRE LOS MODELOS BAJO LA ARQUITECTURA BDI (Creencias, Deseos, Intenciones) !
Se presenta una tabla con un resumen de las características de cada modelo presentado bajo la arquitectura .BDI, se establece cómo interpretan las nociones básicas referentes a creencias, deseos e intenciones.
En la tabla 2.1 podemos observar que un deseo hace un proceso antes de ser considerado como meta, este proceso pasa por una fase donde el deseo es convertido en intención dentro de una estructura definida, ya que las intenciones se consideran como metas futuras, porque pasan por un filtro de que verifica su congruencia y realización.
Los deseos no tienen un grado de compromiso ni cuentan con una estructura para un plan de ejecución. bien definido, Por lo que sería recomendable tener sólo intenciones, es decir, planes que se consideren realizabÍes respecto a las limitaciones del sistema, y con respecto al estado actual del sistema (creencias, base de conocimiento).
Marco Teórico '
Inicialmente los toma como planes a corto o largo plazo.
Las representa como metas, determinadas por el funcionamiento del sistema.
Se representan por el módulo de intenciones.
Los definen el resolvedor de inconsistencias
ARQUITECTURP IRMA
P RS
Dejan de ser Pasan por planes, filtros de convirtiéndose compatibilidad en estructuras para ejecutar para planes alguna acción, bien definidos. solicitada. Maneja las Son intenciones representadas para ejecutar por los los planes de diferentes la librería estados de las donde se intenciones: tienen áreas de Activo conocimiento. Suspendido
Suspendido condicional.
Se representan Son los con una guiones para agenda de ejecución. estructura de intenciones. Establecidos Los contiene el por el checador monitor de de significados eventos. finales.
COSY
GRATE*
CREENCIAS DES Son tomadas por la percepción de su medio ambiente.
Son su base de datos.
Representado como sistema de conocimiento.
Los representa por medio de un monitor de eventos.
DESEOS I INTENCIONES METAS
Tabla 2.1 Características de los diferentes modelos bajo la arquitectura BGI
29
Marco Teórico
30
Modelación de agentes con lógicas modales
CAPíTULO 3
MODELACION DE AGENTES CON LÓGICAS MODALES
3.2.1 Definición. 3.2 PROTOCOLO DE COMUNICACIÓN 3.2.2 Componentes
3.2.3 Base filosófica+ 3.3 Actos del habla
3.1 INTRODUCCI~N
Definición de está teoría.
Forma de representación+ 3.4 Intenciones en ' comunicación.
3.3 ACTOS DEL HABLA
3.4 INTENCIONES EN COMUNICACI~N + 3.5 LÓGICAL MODAL
3.5.1 Lógica Temporal 3.5.2 Bases axiomáticas de lógica temporal I/ 3.5.3 Semántica de mundos posibles 3.5.4 Tiempos ramificados en lógicas temporales
$1 3.6.1 Protocolo abierto en un sistema multiagente
, .li
',
li
'I
3.5 LÓGICA MODAL
3.6.2 Problemas relacionados con los modelos de comunicación
3.7.1 De estados mentales a los actos de comunicación
3.6 FORMALIZACIONES
DE COMUNICACIÓN BÁSICAS PARA MODELOS
1 3.7.2 Sintaxis i
3.7 MODELO DE COMUNICACION 3.7.3 Sistema axiomático 3.7.4 Semántica 3.7.5 Arquitectura para un agente bajo el modelo de comiinicación con la arquitectura BGI !
31
Modelación de agentes con lógicas modales
3.1 INTRODUCCI~N
Uno de los objetivos de este trabajo de tesis es proponer un modelo de comunicación, que permita a los agentes dentro de un sistema multiagente poder COmpaf?ir información de' alto .nivel. Asegurando que las aplicaciones que se resuelvan bajo este enfoque, garanticen a los diseñadores crear agentes que alcancen en un máximo posible las funciones para las que fueron creados bajo este modelo.
Como se observó en el capítulo anterior para crear un sistema multiagenfe es necesario tener una arquitectura que indique las funciones del sistema, así como el modelo con un protocolo de comunicación bajo el cual se va a diseñar el sistema.
Para crear un modelo de comunicación que sea válido, es necesario tener sistemas formales que permitan describir y razonar con elementos de diseño dentro de un marco bien definido, que elimine ambigüedades en la interpretación de información y conducta de los agentes ante un cambio en su medio ambiente.
Para establecer lo anterior se recurrió a investigar la lógica modal y lógica femporal [Rao 19951, como herramientas que proveen elementos para representar conceptos como las intenciones en los agentes, y las características temporales de los programas que ejecutan funciones de comunicación en programas concurrentes, estas son necesarias para crear el modelo de comunicación que necesitamos para este trabajo de tesis.
En este capítulo se presenta una breve introducción a la sintaxis y, la semántica de los operadores que utiliza la Lógica Modal.
Se comienza con una breve descripcibn de lo que es un protocolo de comunicación, llamado así dentro del paradigma orientado a agentes para representar el modelo de comunicación, después ., se presentarán las características que debe tener, finalizando con los formalismos que sustentan este trabajo así como una introducción a la lógica modal y lógica temporal.
3.2 PROTOCOLO DE COMUNICACIÓN
Existen reglas generales que determinan el comportamiento de un agente ante varias situaciones. 'Abordando el tema de comunicación es necesario contar con un lenguaje de inferacción, que debe responder a las siguientes preguntas:
¿ Qué lenguaje se debe utilizar para el intercambio de información? ¿ Cuáles son los términos adecuados que al unirse con el lenguaje,
garanticen una buena interpretación del agente receptor del mensaje recibido?
32
Modelacfón de agentes con Iógicas modales
¿ Qué tan robusta debe ser la estructura y la sintaxis de los mensajes para que ayuden a una rápida interpretación de los mismos?
¿ Cómo tratar las inconsistencias de información y los errores eventuales de tipos que difieren sobre diferentes puntos de vista acerca del mundo?
¿ Qué protocolo debemos utilizar en el intercambio de diálogos?
Un protocolo forma parte de lenguaje de interacción, y un lenguaje de interacción forma parte de un modelo de comunicación. Por lo que comenzaremos estableciendo primero el protocolo, después ' el lenguaje y más adelante el modelo de comunicación.
3.2.1 DEFINICIÓN DE PROTOCOLO DE COMUNICACIÓN
Un protocolo de comunicación establece un marco común de referencias en donde los agentes intercambian información sin problemas, por medio de reglas que deben seguir para hacer una buena interacción.
El protocolo no se preocupa por detalles de implantación como lo hace el lenguaje de interacción, finalmente un protocolo es sólo una herramienta de diseño de comunicación
3.2.2 COMPONENTES DE UN PROTOCOLO DE COMUNICACI~N
Dentro de un protocolo de comunicación se debe considerar la definición y estructura de los aspectos que contestan a las preguntas: ¿Con que comunicar?, ¿Por que comunicar?, ¿Cómo comunicar?, ¿Cuándo comunicar?, ¿Qué comunicar?, 'Qué
Aparte dé esas preguntas también se debe establecer, la reacción que debe adoptar el que envía un mensaje después de enviarlo [El-Fallah 19991.
debe esperar el.que envía un mensaje después'del envio?. I
Un protocolo se puede representar de la siguiente forma [El-Fallah 19991: $
Una red de transiciones, que define un conjunto de posibles
estados en que los agentes pueden acoplarse alternativamente para el intercambio de actos interactivos.
Una transición puede restringir algunos campos en los acLos de interacción.
Las condiciones que un agente debe satisfacer para cambiar de estado pueden ser etiquetadas antes de ser usadas.
transiciones las cuales deben ser relacionadas con un conjunto de /I
j:
33
Mqdelación de agentes con lógicas modales
3.2.3 EL PROTOCOLO DE COMUNICACIÓN Y LA TEORIA DE LOS ACTOS DEL HABLA
Para establecer formalismos sobre el protocolo de comunicación abordaremos nuevamente los actos del habla, como se describió en el punto 2.2.7, cuando un agente genera una expresión se dice que produce una acción, la cual está constituida por tres aspectos siendo el más representativo el efecto ilocucionario, donde se interpreta el significado implícito que lleva una expresión sobre alguna acción [O’Hare 19961.
La fuerza de un acto del habla se produce cuando el locutor aplica una fuerza ilocucionaria al contenido de una proposición, especificando la acción que se intenta activar y a quién afecta dicha acción directamente, se puede representar gráficamente como sigue:
Fuerza de un acto del habla
3.3 CLASIFICACIÓN DE LOS ACTOS DEL HABLA
En sistemas multiagentes se aplican los actos del habla en una teoría acerca de performativas [DARPA 19931, la cual esta compuesta por acciones, conformadas de sucesos con valores’verdaderos o falsos, y la ejecución de los denominados actos del habla, de la misma forma que una lectura indirecta de un acto del habla se obtiene de un acto ilocucionario directamente.
Las performativas se explican como verbos, basados en la fuerza de un acto ilocucionario [Cohen 19951, las performativas indican acciones a ejecutar por un agente y de acuerdo a Searle y Vanderveken [Keith 19981 se clasifican en 5 categorías como se muestra a continuación:
Representativos: aseguran un hecho acerca del mundo, algo que existe en su base de datos como cierto por un largo tiempo. Directos: mandan directivas al interlocutor, es decir, establece comunicación con un grado de compromiso de obtener respuesta a sus peticiones. De compromiso: crean un compromiso en el locutor sobre algunos actos para un futuro cercano. Declarativos: comprometen un acto en el presente con un fuerte esquema a diferencia del anterior que es para el futuro.
O
34
, . . ..
Modelación de agentes con lógicas modales I
;Expresivos: proporcionan indicaciones al interlocutor acerca del estado I
mental del locutor.
Los actos del habla son también vistos como acciones a ejecutar, pero de acuerdo al tipo de expresión que los preceda es el tipo de compromiso que existe para realizar alguna acción en específico.
Existen otras clasificaciones sobre estás acciones representadas como actos del habla, una de ellas es la de Campbell [El-Fallah 19991 pero es demasiado general ya que toma en cuenta actos aislados en condiciones de aplicación y efectos locales los cuales pueden recaer en el interlocutor.
Otros tratan secuencias de interacciones las cuales pueden establecer por ellos mismos entre el interlocutor durante una de sus comunicaciones. Moescherl, utiliza una extensión sobre el trabajo de Searle [Keith 19981 acerca de los actos del habla. Trognon y Brassac [El-Fallah 19991 intentan suplir los actos del habla con una teoría de cadenas hacia estructuras de conversación entre múltiples agentes.
. I
/I
3.4 INTENCIONES EN COMUNICACI~N Ji
En el punto anterior se explicaron los actos del habla y su función al emitir una expresión por un agente, donde las expresiones se crean con diferentes. tipos de intenciones, retornando el ejemplo del punto 2.2.7, donde se emite la expresión "cerrar la puerta" lleva cierta intención implícita, la cual genera una acción de petición o solicitud para algún agente que realice la acción que se está solicitando.
Otro ejemplo es la expresión "está lloviendo", la cual se puede contemplar como una acción tie aviso'a otros agentes, que no necesariamente están esperando que se ejecute alguna acción. Por lo que las intenciones que se manejan en la comunicación también interfieren de forma importante en el desarrollo de un modelo de comunicación.
Para el contexto en este trabajo las intenciones son vistas como comportamientos de acuerdo a planes que permiten a los agentes expresar sus intenciones al c:omunicar!
Las intenciones son acciones que toma un agente al recibir una expresióri, junto con el proceso que genera el recibir una expresión para crear algún cambio en el agente
con su conocimiento previo, de acuerdo a lo anterior es como se activa alguna acción en el receptor con base al significado contextual que infiere éste acerca del enunciado recibido.
Como un ejemplo práctico de lo anterior existe un modelo de cornunicacióq, propuesto por Cohen y Levesque [Cohen 19951, el cual está basado en una teoría racional de interacciones entre agentes.
receptor. Es decir, la interpretación que atribuye quien atiende la peticióri (receptor) c
.i
35
Modelación de agentes con lógicas modales
Presentando una semántica basada en la lógica de primer orden y la utilización de mundos posibles, que son descripciones simultáneas y de razonamiento acerca de estados mentales de los agentes, se representan con 4 operadores modales divididos en:
*3 Dos operadores de actitudes como proposiciones, be/ (proviene de su palabra en ingles belief) para representar las creencias y goal (de SU palabra en ingles goal) para representar las metas.
*:* Dos operadores temporales, done (de su palabra en ingles done) y happens (de su palabra en ingles happens) que significan respectivamente su significado de hecho, y qué es lo que está ocurriendo.
En este modelo no se tiene un operador directo para representar los deseos, éstos son creados por medio de los operadores de act.itudes, al igual que en el punto 2.3.2 los modelos implementados bajo la arquitectura BDI no muestran claramente una representación de los deseos, algunos los toman como una meta débil la cual debe ser coherente y consistente para poder tomarse como meta.
En este trabajo se decide eliminar los deseos y solamente trabajar con creencias, intenciones y metas bien definidas, que se puedan representar formalmente.
Los deseos son eliminados por que no generar un razonamiento acerca de los planes para ejecutar acciones. Mientras que una intención se considera como una meta persistente y consistente, en la que un agente se compromete a hacer un acción en un estado mental en particular [Cohen 19951.
A continuación se presentan las bases lógicas que sustentan el enfoque que se toma para crear el modelo de comunicación que se presenta al final del capítulo.
3.5 LÓGICA MODAL
Cuando se pretende desarrollar una arquitectura para un sistema de agentes, surge el problema de cómo formular un modelo que incluya las actitudes mentales descritas en párrafos anteriores.
Trabajos [Cohen 1990al [Munindar 19911 [Nwana 19961 previos han establecido que las nociones intencionales son hechas usando una lógica modal o alguna variación de está.
Tradicionalmente las lógicas han sido clasificadas como inductivas y deductivas. Las inductivas utilizan métodos de inferencia que pueden quedarse cortos en cuanto al mantenimiento de la verdad.
e
,!.
36
Modelación de agentes con lógicas modales
Normalmente se emplean para razonamiento en situaciones en donde existe información incompleta. Por su parte las lógicas deductivas no necesariamente están limitadas a los dos valores de verdad clásicos, ejemplos de estás lógicas ,son las' siguientes: lógicas modal,es (de necesidad y posibilidad), lógicas epistémicas (de conocimiento y creencia) y las lógicas deónticas (de obligación y compromiso), entre otras.
Como se describió en párrafos anteriores los sistemas multiagentes presentan una naturaleza cambiante, estos cambios se ven reflejados en sus propiedades conforme transcurre el tiempo o suceden eventos que impulsan algún cambio. De lo anterior surge el interés por encontrar modelos formales que permitan representar cambios usando un enfoque simbólico.
4)
En demanda de una propuesta formal para representar ese tipo de comportamientos en los sistemas, surge la lógica modal tradicional originalmente desarrollada por filósofos que estudian diferentes modos de verdad. Tales modos incluyen además de necesidad y posibilidad, obligación, conocimiento, creencia y percepción.
Un ejemplo representativo de esta herramienta de formalización es el siguiente, la aserción P puede ser falsa en el mundo presente, pero existe la posibilidad de que la aserción P pueda ser verdadera en un mundo alterno, llamado mundo posible.
.Este tipo de herramienta de formalización es Útil para representar creencias, metas, e intenciones dentro de un sistema computacional, además del manejo de situaciones diversas las cuales cambian constantemente sin un tiempo definido.
En un artículo clásico de Amir Pnuelli al cual hace referencia Gotzhein [Gotzhein 19921, argumenta que la lógica temporal como una división de la lógica modal, y puede ser un formalismo útil para especificar y verificar programas computacionales. Esto es apropiado especialmente en programas concurrentes que utilizan operaciones continuas en el tiempo, ejemplos de éstos programas concurrentes son los sistemas operativos y los PrOtOCOlOs de comunicación en redes, que responden a una petición solicitada dependiendo del estado actual del sistema,
3.5.1 L6GICA TEMPORAL
Como se mencionó en el párrafo anterior la lógica temporal es un tipo especial de lógica modal, que provee un sistema formal para descripciones cualitativas y razonaniientos acerca de la variación de los valores de verdad en los mundos posibles, con una relación de accesibilidad correspondiente a la evolusión de un sistema concurrente en el tiempo.
La lógica temporal es de vital importancia en programas concurrentes cornputmionales que se' utilizan actualmente, donde los sistemas deberi ser aptos para percibir cambios del medio ambiente en el que se ejecuten [Emerson 19901.
I:
I!
37
Modelación de agentes con lógicas modales
En un programa secuencia1 ordinario, creamos precondiciones y postcondiciones cuya la semántica fundamental puede ser vista como una transformación de un estado inicial a un estado final. Sin embargo, esto no es funcional para operaciones continuas dentro de un programa que no es terminal, por lo que será necesario hacer uso otros de formalismos [Werner 19901.
Los formalismos mencionados en párrafo anterior los proporciona la lógica temporal además de la lógica de primer orden para representar operaciones continuas en el tiempo, o que cambian de acuerdo a diversas situaciones que se presentan en el medio ambiente, tomando en cuenta el estado actual del sistema y las condiciones en que se presenta algún suceso que active determinada acción.
La lógica temporal utiliza dos operadores de la lógica modal para describir y razonar acerca de valores de verdad en aserciones variantes con respecto al tiempo. Estos operadores de necesidad y posibilidad son los siguientes:
,.
O que representa algunas veces y se le llama "operador existencia1 modal", O que representa siempre y se le llama "operador universal modal".
A continuación se presenta un ejemplo de la forma de aplicación e interpretación de los operadores modales.
AI representar la siguiente proposición: La Luna está dentro de la órbita de la Tierra, con Iógica formal solamente se puede representar en el tiempo presente, sin dar opción a situaciones constantes en el tiempo como se observa gráficamente a continuación:
La Luna está dentro de la órbita de la Tierra. La fecha representa el tiempo, y la línea que la cruza representa un acontecimiento dado, que para este ejemplo quiere decir que la proposición solo se ocurre una vez en el tiempo. , .
-t
Como se observa la lógica tradicional no toma en cuenta hechos permanentes en el tiempo, por lo que hay que considerar que en ciertos programas los procesos no están definidos en el tiempo, es decir, que algunos hechos o creencias son verdad por siempre o al menos así parece.
Es aquí donde se hace uso de los operadores modales como sigue:
O(La Luna está dentro de la órbita de la Tierra). AI anteponer el operador modal en la proposición indicamos que la proposición se mantiene constante en el tiempo subrayando el tiempo como se ve en el dibujo.
-t
36
A
Modelación de agentes con lógicas modales
Estos operadores también ayudan a representar acciones futuras, como la siguiente proposición: El cometa Halley está en un punto cercano al Sol, lo anterior tal vez en este momento no sea válido pero tal vez en.un futuro lo será o tal vez alguna vez 10'1 fue:
O(€/ cometa Halley está en un punto cercano al Sol) la modificación que representa anteponer el operador a la oración, es que en algún punto en el tiempo va ocurrir que el cometa este en un punto cercano ai sol, sin especificar un tiempo, solo el hecho de que este evento va ocurrir.
ii I .t
Usando los dos operadores también podemos hacer combinaciones, teniendo cuidado en el orden que aparecen, ya que dependiendo de su orden es su significado.
AI poner 00 se lee siempre eventualmente o muchas veces infinitamente, ya que e'l tiempo es infinito, que significa que la proposición siempre eventualmente sera válida y variante en el tiempo. Por ejemplo:
OO(Es luna llena) no siempre ocurre que la luna este llena, pero se sabe que ocasionalmente sucede este hecho en forma constante en el tiempo y que no va a cambiar.
1 1 1 1 1 .+t .I!
AI invertir los operadores"O0 se lee casi siempre o casi en todas partes, significa que en a partir de algún punto en el tiempo, la proposición sucederá y permanecerá invariable en el tiempo. Por ejemplo:
03(El Sol no emitirá luz) es posible que el Sol deje de emitir luz y cua,ndo esto suceda se mantendrá de esta forma por un lapso grande en el tiempo o por siempre, con los operadores modales se puede observar gráficamente de la siguiente forma:
\ II '11
9
' !
.t .. -.
n
3.5.2 EASES AXIOMATICAS DE L ~ G I C A TEMPORAL !i
El método de diagramas semánticos es un procedimiento de decisiones por procediinientos para lógica temporal tradicional, que puede ser implantada en computadoras con operaciones continuas utilizando las definiciones de Gotzhein [Gotzhein 19921, donde la lógica temporal tradicional se basa en la lógica propositional. A continuación se presentan los principios en que se bass el modelo de comiinicación que se propone.
39
Modelación de agentes con lógicas modales
AI utilizar los operadores de la lógica proposicional como son: bicondicionai ++, implicación +, conjunción A, disyunción v, y negación 7 , se puede obtener una lógica temporal proposicional.
Con un conjunto de reglas de formación que definen la construcción de fórmulas sintácticamente correctas que pueden definirse de la siguiente manera:
Se comienza estableciendo que todas las reglas para las fórmulas bien formadas (fbf) de la lógica proposicional clásica, son reglas de formación en la lógica proposicional modal. Sí A es una fórmula bien'formada, entonces O A y O A son fórmulas bien formadas.
DEFINICI~N I
Sea 4 un conjunto de proposiciones atómicas. Entonces las siguientes sentencias son fórmulas de lógica temporal tradicional [Gotzhein 19921:
(1) Para todo p E 4 : p es una fórmula atómica. (2) Sea I$ una fórmula, entonces +I es una fórmula. (3) Sea 41,4z fórmulas entonces (41 A 44, (41 v 421, (41 3 4zh (41 = $2)
también son fórmulas. (4) Sea 4 una fórmula, entonces U+, 04 son fórmulas.
, .
Mediante la aplicación repetitiva de estas reglas se pueden obtener fórmulas correctas sintácticamente. La aplicación de estas fórmulas no nos dice lo que estás fórmulas significan.
El significado dedichas fórmulas puede ser llevado a cabo mediante un modelo, es decir, se debe proveer una interpretación no' solamente para las letras proposicionales, sino también para la representación fundamental del tiempo.
DEFINICI~N 2
Un modelo es una secuencia de estados o = <So,&, ..., S,, ... > (posiblemente infinito), donde cada estado está definido por un conjunto de proposiciones atómicas y que contienen una interpretación completa de las letras proposicionales que aparecen en la fórmula [Werner 19901.
Ejemplo. Sea 4 = x>O, x=l , x=2 y o = (x>O, x=1, x>O, x>O, x=2, , . . . )
En este modelo O, las proposiciones atómicas "x>O y "x=l" están completas en el estado So, "x>O es verdad en SI, en SJ ninguna de las proposiciones atómicas es verdadera. Cada elemento de una proposición atómica puede ser verdadero o falso en cada estado del modelo.
40
Modelación de agentes con lógicas modales "
II Con esto se puede dar un significado a las fórmulas de la lógica temporal mediante un termino con relación al modelo, uno de sus estados y una fórmula que se mantendrá si y sólo si la fórmula es verdad esta situación.
DEFINICI~N 3
Sea o = <SO. Si ,..., S, ,... > un modelo, y +o,$i,$2 fórmulas arbitrarias p E 4. La relación de satisfacción está definida por el ii-ésimo estado de o como sigue:
o , n \ p 1 0 1 . . S i p E S n o, n k14 o,n ~ I $ I A ~ z Sio,n. \ I$ iyo,n 1 6 2 o, n 1 4 s*
o , n \O$
Si no o.n 1 I$
Si o,m \ 4 para toda m 2 n Si o,m \ $ para algún m 2 n
Basados en la verdad de! las fórmulas podemos determinar definiciones previas, ~
obteniendo varias nociones interesantes [Gotzhein 19921. Tales como: II
Se dice que una fórmula 4 es satisfecha en un modelo o escrito o 1 4, si y sólo si $ es verdad para algún estado de o.
Se dice que $ es válida (1 4) si y sólo si 6 es verdad para todos los estados del modelo o.
DEFINICI~N 4 . . '1
El problema de encontrar un método efectivo para decidir sobre algún objeto arbitrario pertenece o no,,a los miembros de cierta clase de objetos, es llamado problema de decisión basado en el Teorema de Godel. Si este método existe entonces el problema es llamado decidible. de otra forma es llamado indecidible 1
I! c [Gotzhein 19921.
Con está definición se puede enumerar todos los estados del modelo, y computar el !
valor de verdad de 4 en cada estado. A primera vista se puede ver que no efectivo porque un modelo puede"ser infinito. Pero existen métodos lógicos para probar lo anterior con una serie de pasos establecidos.
Otra ventaja de esté método de diagramas semántico, es que una formula 4 es válida, si y solo si es verdad para todos los estados S,, en CT. Para mostrar que 4 no es válida, es suficiente encontrar un estado Sn en el niodelo o en el que 4 no sea .
,l. 1
!,
válida. Si esto es imposible entonces I$ debe ser válida para el modelo.
DEFINICI~N 5
II
,/I li
Una fórmula 4 temporal puede ser derivada por aplicación de axiomas y reglas de transformación llamadas teoremas, se escribe como t 4.
41
Modelación de agentes con Iógicas modales
DEFINICIÓN 6 I
Las bases axiomáticas para los sistemas de lógica consisten de un conjunto de axiomas y un conjunto de reglas de transformación [Gotzhein 19921.
reflexiva reflexiva consecuente cerrado transitividad linearidad discretes regla de modus ponens
regla de generalización
DEFINICI~N 7
Una fórmula temporal 4 es válida para el modelo O, si 6 es verdad en todos los estados O E S,; 4 es inicialmente válida (representado en la fórmula con un subíndice i en el símbolo de satisfacción 1, como h ) para el modelo O si cada estado IJ E S, satisface inicialmente a 4.
S" b 6
S, h I$
Si cr.n 16 para todo Q E S,, y toda n 2 O
Si O h 41 para todo O E S, Si 4 es válida para el modelo O entonces el programa se dice un programa P creado bajo esté modelo O tiene la propiedad 4 .
Un teorema importante dentro de la lógica temporal. se demuestra haciendo uso de las teorias vistas antes, mostramos la siguiente comprobación [Emerson 19901.
Es válida de acuerdo con las siguientes bases asumiendo que s E S, es un estado de un modelo O,
P
y suponiendo que sb o-P
entonces debe existir un estado s' E S, en el que
42
.
Modelación de agentes con lógicas modales
Desde que SI p, para todos los estados accesibles desde s por p, en particular para s'.
SI 1 P
De lo anterior suponemos que la siguiente proposición debe ser falsa: I
Esto es decir:
S I 1 0 1 p
Puesto que O y s son arbitrarias se prueba que: !/I
p a 7 0 , p
Es una fórmula válida en Iógica femporal proposicional.
3.5.3 SEMANTICA DE MUNDOS POSIBLES
Para aplicar las reglas axiomáticas de los puntos anteriores es necesario tener una estructura básica de representación. Una de ellas es la semántica de mundos ,
posibles introducida por Kripke, este concepto tiene la idea básica de evaluar una "
fórmula modal dentro de un'conjunto de mundos posibles, el cual es provisto con una cierta relación de accesibilidad.
Para construir el modelo semántico de las nociones intencionales es necesario conocer la semántica de los mundos posibles utilizando una estructura de Kripke [Hintikka 19721, que consiste de una tripleta cW, R. V> donde W es un conjunto de ',
mundos posibles o estados del sistema, como se usó en las definiciones anteriores en este trabajo.
Donde R c W x W es una relación vista en este conjunto de mundos posibles, y V: 4 x W + O,l) es un valor de asignación el cual determina el valor de verdad de cada J
formula dentro del conjunto de mundos posibles.
Las estructuras Kripke se utilizan para representar propiedades satisfechas en algún ,, mundo en particular, las h a l e s no logran mantenerse en el desempeiio de un ',
sistema, se introduce la notación estado inicial representado por o 4 , la cual ' significa que la fórmula 4, es inicialmente satisfecha en el modelo o.
El valor de verdad de una fórmula modal dependerá del mundo posible bajo consideración. En otros términos, p es verdad en un mundo dado si y sólo si p es verdad en al menos un muhdo posible accesible desde ese mundo.
I1
,I
43 "
Modelación de agentes con iógicas modales
Un mundo posible es una asignación de verdad o falsedad a cada fórmula bien formada, como una interpretación en el mundo clásico. Un mundo posible (estado),w es accesible desde otro mundo w’si todo lo que conoce en w es conocido en w’. Una relación de accesibilidad determina si un mundo w;es accesible desde cualquier otro w,, en el universo del discurso.
La relación de accesibilidad es la que permite conectar dos mundos posibles. Y dependiendo del tipo de relación accesibilidad (transitiva. simétrica o reflexiva), se obtienen diferentes teorías dando origen al sistema axiomático visto anteriormente.
3.5.4 TIEMPOS RAMIFICADOS EN LOGICAS TEMPORALES
La lógica teniporalse refiere a una colección de tiempos lineales, por otro lado existe un enfoque diferente dentro de la iógica temporal con respecto al tiempo. En este enfoque se reemplaza la secuencia lineal de estados por un árbol de estados [Emerson 19901.
Originando la lógica tenipora/ de tiempos 1-arnificados, con este enfoque se puede crear una serie de caminos alternos para la solución de un problema dado. La principal ventaja es que el árbol mantiene información de los estados, que llevaron a cabo decisiones no deterministas y divididas.
Suponiendo que un agente se encuentra en un estado SO en un tiempo to en el cual se satisface p, tiene dos mundos posibles b l y b2. Su representación es por medio de árboles lógicos CTL (Computational Tree Logic) [.Emerson 19901 se muestran en la figura 3.1.
(bi, t i , p?) (bzi 12. P)
Figura 3.1 Árbol Iogico de creencias
Las ramas representan opciones disponibles para el agente al momento de seleccionar las acciones a realizar, en la figura 3.1 las ramas b, y b2 son dependientes del tiempo reportado.
La ventaja de tener múltiples mundos accesibles (creencias), es permitir que diferentes posibilidades sean modeladas, incluyendo varios casos en donde falte
’información o se tenga incertidumbre acerca de algún estado posible, como en la figura 3.1 la rama b2 solamente sucederá si se mantiene la formula p.
44
Modelación de agentes con lógicas modales ' . Cada una de las ramas mostradas en la figura 3.1, a SU Vez es también un árbol CTL de tiempo, de esta forma el agente en Cualquier mOment0 puede cambiar sus creencias acerca de las opciones disponibles dependiendo de las condiciones que S e
le presenten.
Otra de las aplicacione6 de la lógica temporal es en la especificación de requerimientos propiamente. Esto significa que los requerimientos comienzan como, un conjunto de propiedades que caracterizan el entorno problema. Las propiedades pueden ser consideradas y especificadas una para cada tiempo, tomándolas de la especificación completa.
Cuando se modela el comportamiento de un agente con lógica temporal se puede hacer distinción inusual, clasificando las propiedades temporales dentro dos que Son; seguras y vivas (entiéndase por propiedades vivas acciones que se están ejecutando actualmente, y acciones'lkeguras que se presentarán en un tiempo cercano), en donde aplicamos los operadores modales ya vistos más sentencias propias para cada problema. Ambas propiedades seguras y vivas pueden ser invariables en el
Antes de concluir con este punto se muestra un ejemplo sobre las propiedades de las lógicas mencionadas, y el uso de los operadores modales.
Primero se introduce un operador modal del pasado (+) el cual se aplica al ejemplo, el significado del operador se describe a continuación [Gotzhein 19921.
+ p significa que p'es verdad ahora o fue verdad alguna vez en el pasado ' Con el ejemplo se presenta una visión de la forma de aplicación de algcinos de los conceptos vistos, por medio instrucciones que son entendidas como expresiones generauas por un sistema, que para este caso sería un sistema de comunicación entre computadoras:
I , I/
tiempo. .I
o, n = + p: Si o,m O p para todo Os m 5 n
'I
(, lil . o ( send ( m ) 3 state = connected ) Expresa que un mensaje puede enviarse sólo si existe conexión.
Para llegar al estado de acuse de recibido de un mensaje, este',mensaje debió de ser recibido previamente.
Exige que si B recibió un mc?nsaje éste debió de ser enviado por A.
o ( send-ack ( m )3+ receibe ( m ))
o ( B 'receive ( m ) a+ A send ( m ) ) !I I,'
Modelación de agentes con lógicas modales s
3.6 FORMALIZACIONES BÁSICAS PARA MODELOS DE COMUNICACI~N
El formalismo de lógica temporal puede ser aplicado para crear modelos principalmente de comunicación, ayudando a establecer formalismos dentro de un marco común en comunicación Como ejemplo se muestran dos entidades que interactuán en la figura 3 2
I entidad A entidad 6
I I
Figura 3.2 Modelo básico de comunicación
Obteniendo las siguientes propiedades utilizando formalizaciones de la lógica temporal con operadores de la lógica de primer orden (Y universal, 3 existencial), creando la lógica temporal de primer orden con operadores de eventos de ocurrencia [Gotzhein 19921:
OVx ( # [ ofrece ( x ) ] > # [ acepta ( x ) ] ) ( # [ ofrece ] = # [ acepta ] ) O( [ ofrece ] - [ acepta ] )
Una propiedad es llamada consfructiva si la descripción para ese formalismo puede ser ejecutable (como los formalismos de la lógica temporal), una ventaja es que las especificaciones se pueden utilizar en prototipos rápidos o para la derivación de implantaciones de referencias las cuales pueden ser usadas para propósitos de prueba.
La desventaja es que las propiedades del sistema generalmente no son expresadas con técnicas constructivas, por consecuencia éstas deben ser verificadas como propiedades mediante descripciones implícitas. Sin embargo, pueden ser dificiles de incorporar y solamente las propiedades esenciales, las cuales resultan de especificaciones menos abstractas reducen las múltiples soluciones correctas, y descubren propiedades esenciales cuando se leen como especificaciones.
Dentro de la lógica temporal las propiedades del sistema se expresan directamente. Esto tiene la ventaja de que cada propiedad se considere por separado haciendo fácil decidir si es esencial o no.
AI establecer los formalismos que tendrá algún sistema, se comienza a crear establecer un modelo de comunicación, el cual necesitará de un protocolo que delimite el marco de referencia para el intercambio de información del sistema, que se muestra a continuación.
46
Modelación de agentes con lógicas modales
3.6.1 PROTOCOLO ABIERTO EN UN SISTEMA MULTIAGENTE
En un entorno de agentes que se comunican es importante definir las actividadesl
conforme a los estados mentales en que se encuentre el agente, por 10 "que Un protocolo óptimo depende de las situaciones actuales de los agentes y puede ser determinado solamente durante la ejecución [Werner 19901.
Algunas otras definiciones establecen a un protocolo como una colección de reglas para intercambio de resultados, las cuales inicialmente no intercambian su información abiertamente.ipero más adelante se ajustan alternativamente, Vreeswijk de acuerdo con Ama1 [El-Fallah 19991.
Cuando se presenta una alteración de acciones por conflicto dentro del sistema, significa cambios en las creencias de un agente, cuando esto sucede el protocolo es quien confronta las nuevas creencias, para .aceptarlas o rechazarlas. Cada de tipo de sistema multiagente tiene una actividad regulada por sus creencias, un protocolo abierto cambiante de acuerdo a las actividades que demande el sistema. Es el protocolo quién gobierna la disputa entre una cantidad de agentes, por lo que regula también.la producción de nuevas creencias como se observa en la siguiente figura 3.3:
4
I I
14 1
I n I
I .I' I Figura 3.3 Representación del funcionamiento de un protocolo.
Y¡. i.
3.6.2 FROBLEMAS RELACIONADOS CON LOS MODELOS DE COMUNICACI6N
It II Existen varios problemas relacionados con el establecimiento de un modelo de comunicación, uno de ellos es que debe tomar en cuenta las bases filosóficas que sigue el paradigma orientado a agentes, como son las intenciones al emitir un mensaje, los cambios de estado que debe generar en el agente al que se envía el mensajf! así como del que envió dicho mensaje, y la forma en que se manejará el paso de mensajes[Nwana 19991 [Keith 19981.
Otro problema importante que se debe tener en cuenta es que no existen estándares para los modelos de com:unicaciÓn [Lander 19971, a los cuales se debe seguir para el establecimiento de un modelo, lo único que se debe tener en cuenta es contar con una forrnalización matemática que justifique el modelo a proponer como se mostró antes, en este trabajo de tesis fueron las lógicas temporales, modales Jf de primer orden.
'! 47
Modelación de agentes con Iógicas modales
Para los sistemas que utilizan intercambio de información con la técnica de alto nivel, los agentes deben proveer simultáneamente la planeación y ejecución de reacciones ante fallas de planes o acciones, además de un soporte dinámico con respecto a los cambios del mundo. Y un protocolo de comunicación adecuado que delimite el marco en que se presentará el problema a resolver.
3.7 MODELO DE COMUNICACIÓN PROPUESTO
Los agentes necesitan coordinarse y cooperar para la solución de un problema, para llevar esto a cabo es necesaria una comunicación efectiva, que garantice la ejecución de acciones de otros agentes en busca de la solución al problema [Werner 19901, por medio de un conjunto estándar de actos del habla el cual define las acciones comunicativas para el universo del agente.
Por lo que surge una idea principal de crear un modelo de comunicación que contengan las ideas filosóficas de la comunicación propuestas por Bratman [Bratman 19871 acerca de los estados mentales e intenciones de comunicación, los cuales surgen durante el proceso de razonamiento que realiza un agente para alcanzar ciertos objetivos y resolver los problemas que se le plantean.
'I
3.7.1 DE ESTADOS MENTALES A LOS ACTOS DE COMUNICACION
En está sección se expone el proceso de razonamiento que realiza un agente en un sistema mulfiagenfe, dicho proceso se concentra en el razonamiento que realiza un agente al elegir el método que utilizará para alcanzar cierto estado, o para lograr alcanzar subobjetivos que le permitirán alcanzar el objetivo general [Werner 19901.
Ejemplos de tales subobjetivos son los actos de comunicación donde un agente decide las acciones parciales a realizar para lograr objetivos de más alto nivel.
Recordando que un agente va formando una intención de actuar, sobre sus objetivos propios o sobre un objetivo compartido, Por lo que se requiere especificar en que condiciones aparece la necesidad de cooperar, es decir, en que momento del proceso de razonamiento aparece la comunicación. Alguna de está condiciones se exponen a continuación:
1. Cuando un agente detecta que no posee suficiente información y requiere actualizarse con las creencias de otro agente (Preguntar).
2. AI solicitar la cooperación de un agente para alcanzar un objetivo (Solicitar) este debe informar a otro agente de su estado, entonces él decide ejecutar un subobjetivo de comunicar sus actitudes mentales (Informar).
46
Modelación de agentes con lógicas modales '
3, Otra situación aparece cuando un agente tiene Una intención de actuar sobre un objetivo adoptado y cree que e\ otro agente no está enterado de su compromiso, así ei agente se formará el subobjetivo de informar su intención (Informar).
4. También se presenta la necesidad de comunicar cuando a un agente Se le solicita cooperar con respecto a un objetivo, y desea informar al otro agente la acción o acciones que ejecutó para el logro de SU objetivo (Ofrecer, Proponer).
'
I
Para llevar a cabo las diferentes acciones de comunicación, el'modelo debe contemplar un conjunto mínimo de acciones que permitan al agente realizar los subobjetivos de comunicación. Así surge la necesidad de definir primitivas de comunicación (formando un protocolo de comunicación) que forman parte de las interacciones más complejas entre agentes es decir, los modelos de comunicación.
Como fue presentado en secciones anteriores, para crear un modelo de comunicación es necesario,conocer la filosofía bajo la que se rige y los formalismos que lo sustentan en este trabajo la filosofía son las características que poseen los agentes vistas como creencias, intenciones y metas. Y los formalismos como las lógicas modales y temporales, continuamos estableciendo los componentes que requiere un sistema formal [O'Hare 19961:
J Una sintaxis, que indique la forma correcta de escribir las sentencias en un sistema dado.
J Un sistema axiomático que incluye un conjunto de fórmuias bien formadas, ',
con base en las definiciones vistas antes dentro de este capítulo, dichas formulas deben respetar el conocimiento del universo del problema.
J Una semántica ad,ecuada que se encarga de especificar lo que significan iíis sentencias en un sistema dado.
.
'/I
3.7.2 SINTAXIS
Para el modelo se utilizan los formalismos de la lógica modal, para representar nociones 'intencionales. 'La sintaxis del modelo se obtiene con operadores de la lógica modal más operadores de la lógica clásica, como se muestra a continuación:
Los operadores de la lógica de primer orden: 3 implicación, A conjunción, I v exclusión,
3 cuantificador existencial.
Los operadores modalesm(sección 3.5):
.I !
negación, = igual, V cuantificador univer,sal,
!I
O de necesidad, O satisfacción, O de posibilidad
49
Modelación de agentes con lógicas modales
Los operadores temporales, representan el estado del sistema
BEL Creeencias INT Intenciones GOAL Metas
Variables:
Predicados:
Para representar agentes: Para representar acción:
x, Y> 2. P, 4, a, P.
Para representar proposición: p, 4, a, p.
3.7.3 SISTEMA AXIOMÁTICO
La semántica de las fórmulas estará definida en términos de la estructura de Kripke del modelo definido en la sección 3.5.3:
M = ( W, R, V )
Se agregan algunos operadores para representar los mundos posibles del sistema como: el operador BEL para representar el conocimiento, así como el operador GOAL para representar las metas de un agente, y el operador INT que representa las intenciones de un agente. Los operadores anteriores conforman la arquitectura en que se basa el modelo BIG (Belief, Intention, Goal), que significa creencias, intenciones y metas.
Los operadores anteriores tienden a ser más expresivos que de acuerdo con las teorías de Bratman [Bratman 19871. se puede modelar intenciones.Gon una medida de compromiso que regulará la conducta del agente y forzará su coordinación interna para el logro de sus objetivos en una sociedad de agentes.
La semántica de las creencias, intenciones y metas de un agente en término de los posibles mundos se representa uniendo las estructuras de Kripke, y los operadores de la sintaxis establecida como:
M = ( W , R , V ) donde: W =BEL,INTE,GOAL R=Ix, Y, z) V=b, h a> Dl
Las propiedades que se aplican a las fórmulas que se obtengan de la estructura presentada, son las vistas en la sección 3.5.2. Tomando como fórmulas de las proposiciones del conjunto V, que son vistas como acciones a efectuar en un futuro para un agente determinado por R, en un mundo W.
50
Modelaciofi de agefifes con Iógicas modales -
En la seccione 3.5 se mostró el sistema axiomático para, escribir correctamente las fórmulas con lógicas modales y teiiipoi-ales. Alioia iiiodelaiiios las creencias [Cohen 19901 asociadas a un conjunto de estados accesibles de creencias para cada situación. De manera similar las intenciones y los objetivos, se modelan utilizando una relación de accesibilidad adecuada a cada estado mental.
Sea B un conjunto de posibles creencias accesibles de un agente x, desde un estado sen el tiempo t se denota por:
I1
B S , I ( 4 donde Bs.1 (x) = IS' I B(x, S , t, S ' )
Similarmente se usa Is,, (xj y G,,, (x), para denotar el conjunto de los mundos accesibles de intenciones y metas del agente x en el estado s en un tiempo f respectivamente.
3.7.4 SEMÁNTICA
De acuerdo a los estados me,ntales de un agente, la semántica asociada a un modelo M con respecto a una variable de asignación V y un mundo S en el tiempo f. está dada como:
'
i
(M, V, St) b (BEL x P) Si VS'E Bs, I (Xj, (M, V, SI) 1 p ( 1 )
(M, V. SI) ( INT x p) si VS'E &,I (x), (M, V, SI) 1 p (2)
(M, V, SI) 1 (GOAL x pj.si b's'c Gs,t (x), (M, V, SI) 1 p ( 3 )
La interpretación de la expresión 1 es comprobar la creencia que representa la formula p para el agente x, es válida si para todo estado s que pertenezca a la base de datos se satisface p, dentlo del conjunto B definido.
La expresión 2 indica que la intención (1 en el agente x se satisface si para todo estado s dentro del conjunto de intenciones que tiene un conjunto I definido se satisface. De igual forma la fórmula 3 representa una meta 13 para el agente x, y se considera si es válida para todos los estados dentro del conjunto G definido.
Ahora se examinará el significado de los posibles mundos mediante un ejemplo gráfico del uso de lógicas temporales ratnificadas, donde se crea un árbol con el conjunto de creencias que el agente cree que son posibles.
Suponiendo que un agente estando en un estado SO en el tiempo to, en el cual se satisface p, tiene dos posibles opciones b l y b2. Figura 3.4.
t
Modelación de agenfes con lógicas modales
Figura 3.4 Un árbol de aplicación para las posibles opciones de un agente.
Como la relación de creencias es independiente del tiempo, el mapeo de B,,,(x) en algún tiempo t l es diferente en t2. De esta forma el agente puede cambiar sus creencias (p?) acerca de las opciones disponibles como se ve en la figura 3.4.
Donde se observa que BEL x p ) se cumple en b, y ( BEL x p )se cumple en b2, de manera similar se representaron las posibles opciones para las intenciones y metas de un agente.
Ahora definimos una intención a de un agente x como: (INT x, a) , un objetivo a de un agente x como (GOAL x. a) y finalmente una creencia a de un agente x como (BEL x, a).
Y establecemos una relación de consistencia entre las intenciones y las metas con su significado, es decir, un agente debe creer que sus intenciones planeadas sean posibles o alcanzables en un futuro lo cual es representado por
(INT x, a ) 3 (GOAL x, u) ( 4 )
La condición de consistencia entre las creencias y objetivos establece que si un agente adopta un objetivo, entonces debe creer que es posible dicho objetivo y se presenta como:
(GOAL x, u) 3 (BEL x, u) ( 5 ) ##.
Las creencias acerca de los objetivos, que se interpretan como si un agente tiene un objetivo a alcanzar, éste debe creer en dicho objetivo:
(GOAL x. a ) = (BEL x. (GOAL x, a ) ) ( 6 )
De creencias acerca de intenciones:
(INT x, u.) (BEL x (INT x. v.)) ( 7 )
Y así sucesivamente, cuidando que las intenciones no persistan por siempre. A continuación se muestra el sistema axiomático que toma el modelo de comunicación que se propone en este trabajo.
52
Modelación de agentes con lógicas modales
3.7.5 ARQUITECTURA PARA UN AGENTE BAJO EL MODELO DE COMUNICACIÓN CON LA ARQUITECTURA BGI I:
I I/(. .I! Presentado el modelo de comunicación con su forrnalización matemática, pasamos a presentar la estructura gráfica en que se vería. un agente modelado bajo está arquitectura BGI (creencias, intenciones, metas). Está estructura nos ~
muestra la forma en se debe modelar un agente para el sistema multiagente que '
se desea diseñar, con una serie de módulos que representan las características de los agentes y la filosotía con la que se trabajo a lo largo del presente trabajo de .! tesis, que es tratar a los $gentes como sistemas intencionales, y como entidades autónomas. La arquitectura adoptada ya con el modelo de comunicación se muestra en la figura 3.5.
Para esta arquitectura se conformara de por un monitor, que es un módulo que está pendiente de los cambios que ocurren en el medio ambiente, es el proceso de recepción de informahión inicialmente. Este pasa la información pertinente al agente .hacia el filtro de información.
El filtro de información como su nombre lo indica hace una selección de la información recolectada por el monitor, y sólo pasa la que este dentro del ~
protocolo valido para el sistema multiagente, y que el agente tiene activado.
El filtro de información a" su vez. reparte la información pertinente a la base de I datos o a la generación d e planes propiamente, de acuerdo a como corresponda.
La base de datos (creencias), es un proceso que se puede ver como una base de datos, contendrá funciones internas para verificar la consistencia de la ' información nueva con la existente, y funciones de búsqueda de información conforme lo requiera el sistema a modelar. Es una parte fundamental en el sistema ya que de acuerdo a la información que aquí se tenga, serán las decisiories que tome el sistema ante una situación que se le presente.
Por otro lado esta la generación de planes, representa los procesos que tsndká un agente para crear proyectos sobre la ejecución de una acción a ejecutar, es decir, este proceso se encarga de verificar que una acción solicitada al agente sea congrumte con las creencias, y basándose en ello poder crear un camino para llegar a ejecutar dicha acción, con una estructura previamente establecida al momenio de diseñar el programa, y un poco dinámica ya que depende de los datos actuales el rumbo que tomará alguna acción solicitada.
El generador de planes, esta en constante intercambio con el verificador de consistencias, encargado,, de verificar que los planes que se propongan estén actuales con la información que se tiene propiamente, y también se encarga de verificar cuales planes sd ejecutan en un momento dado, y cuales esperan un poco ardes de ser ejecutados de acuerdo al estado del sistema en general.
~
'
53
Modelación de agentes con lógicas modales
Para que un plan se convierta en meta o acción a realizar debe pasar por el generador de planes, después por el verificador de consistencias, y finalmente pasar el módulo de nombrado, acciones a realizar. En este módulo se trata la estructura de plan como acción, y comienzan a funcionar los procesos correspondientes para realizar la acción establecida, y los resultados son pasados al actuador.
El actuador, es el proceso del agente que deja los resultados de una acción solicitada al sistema multiagente.
I
A Monitor I I U
I, Actuador
Base de datos (Creencias) Filtro de
t
Generación de planes o acciones (Intenciones)
IAccionesa I t realizar
(Metas)
Figura 3.5 Representación del funcionamiento interno del protocolo de comunicación propuesto.
En la figura 3.5 se muestran las características que debe tener cada agente del sistema que se desee crear, se debe establecer un protocolo de comunicación que está más ligado con el contexto del problema que se desea resolver, y de acuerdo al problema se establecen una serie de reglas para su creación y manejo.
En el siguiente capítulo se muestra una aplicación del modelo a un problema de redes de computadoras, donde se delimita el contexto en que se aplicaran los agentes, mostrando de está manera un protocolo de comunicación y el modelo presentado.
.
54
Simulación con agentes mfencionales pata equilibmr el tráfico en una red de área local
CAPITULO 4
SIMULACIÓN CON AGENTES Y'
LOCAL II
INTENCIONALES PARA EQQILIBRAR EL TRÁFICO EN UNA RED DE ÁREA
SIMULACI~N
4.1 INTRODUCCION @
4 2 PROBLEMA DE TRÁFICO EN REDES DE ÁREA LOCAL
4 3 ELECCIÓN DEL ALGORITMO PARA EQUILIBRAR EL TRÁFICO EN UNA RED DE ÁREA LOCAL
4 4 JUSTIFICACION DEL USO DE AGENTES INTENCIONALES I
YI /.
4.5 ETAP DE LA SOLU ÓN
4.5.1 Algoritmo de enrutamiento por estado de enlace.
~
4.5.2 Diseño del algoritmo con agentes intencionales.
4.5.3 Implantación del algoritmo con agentes intencionales.
4.5.4 Descubrir a sus nodos vecinos.
4.5.5 .Medir el retardo para cada uno de sus nodos vecinos.
4.5.6 Construir un paquete de estado.
4.5.7 Enviar este paquete por la red.
4.5.8 Calcular la trayectoria mús corta
4.5.9 Descripción de la interfaz gráfica del simulador.
4.5.10 Resultados obtenidos eri las corridas de prueba.
II
55;
Simulación con agentes intencionales para equilibrar el fráfico en una red de área local
4.1 INTRODUCCI~N
Tomando en cuenta que el uso de las redes se ha incrementado por los beneficios que ofrecen de compartir información y recursos en sistemas computacionales.
Resulta esencial un buen desempeño de las redes, buena parte de dicho desempeño recae en los algoritmos que utilicen para su funcionamiento, por esto resulta interesante aportar nuevos métodos para un mayor aprovechamiento de los algoritmos y mejoren el desempeño de las redes.
Un problema que se ha detectado en estudios sobre el desempeño de las redes, se encuentra en el paso de información entre las computadoras que forman la red, llamado tráfico en redes [Tanenbaum 19971.
Existe un modelo de referencia para construir arquitecturas de redes (contienen los algoritmos para mejorar el desempeño de las redes), una arquitectura común es presentada por OS1 (Open System Interconnection, interconexión de sistemas abiertos), esta arquitectura esta divida en varias en capas encargadas de problemas específicos en el funcionamiento de las redes.
Dentro la arquitectura OS1 existe la capa ,de red, encargada de asegurarse que se lleve a cabo el intercambio de información de una máquina origen a la máquina destino, por medio de la creación de rutas por donde circulara la información para llegar a su destino, evitando la saturación de un canal en especifico en la red. Este tema es de interés para resolver el problema de tráfico en redes.
La capa de red cuenta con diversos algoritmos encargados de establecer el envío de mensajes, seleccionar rutas de envío y las estructuras de datos que contendrán los mensajes que posteriormente usarán los nodos para el intercambio de información, es esta parte la que debemos diseñar para balancear el intercambio de mensajes entre computadoras y evitar largos tiempos de atrasos en la información o saturación de un canal en especifico.
En la aplicación que se describe a lo largo de este capítulo, se hace énfasis sobre la forma en que se diseñó el algoritmo bajo el paradigma orientado a agentes, y lo importante sobre la aplicación de agentes en este problema.
4.2 PROBLEMA DE TRÁFICO EN REDES DE ÁREA LOCAL
Como se mencionó antes el problema con el que se prueba el modelo de comunicación presentado en la sección 3.7, será el balancear el tráfico en una red de área local.
El problema es que teniendo una serie de computadoras conectadas simulando una red de área local, se comiencen a intercambiar información por una misma ruta hasta saturar ciertos nodos que forman la red.
56
Simulación con aaenfes infencionales oara eauilibrar el frifico en una red de área local
Aminorando el desempeño de la red por aumento de tiempo en la recepción' de información, por lo que es bueno tomar caminos alternos para evitar retrasos en el envío de información. !;
Para la creación de estos caminos alternos se debe tomar en consideración el estado actual de la red, considetando los nodos.que se encuentran activos y hacer cálculos sobre los tiempos actuales en el intercambio de información entre los nodos de la red. Esto requiere de un programa con un algoritmo adecuado que de forma automática tome decisiones para crear las rutas, y genere acciones a tomar de acuerdo al estado de la red, para el envio de información.
4.3 ELECCIÓN DE ALGORITMO PARA EQUILIBRAR EL TRÁFICO EN UNA RED DE ÁR'EA LOCAL
Para dar una solución a este problema se eligió un algoritmo adecuado, y 'después se justifica la aplicación dB un sistema multiagente.
La estabilidad del tráfico 'tlentro de una red es una meta importante para la capa de red, por lo que cuenta c08 algoritmos de enrutamiento encargados de elegir las .rutas que recorrerá un mensaje para llegar a su destino por la ruta más corta y segura.
También se debe considerar la rápida adaptación a los diferentes cambios de topología en la red, un buen algoritmo de enrutamiento debe seguir funcionando aún cuando exista la caída de!talguno de los nodos de la red.
Analizando los diferentes algoritmos de enrutamiento se encontró que uno de los algoritmos que contempla la mayoría de los problemas existentes en las redes, es el algoritmo de enrutamiento por estado de enlace, y. se eligió por las siguientes características [Tanenbau'm 19971:
I¡
A.naliza el estado de la red en forma constante, por medio de unas tablas de estado con infoTmación de los nodos de la red, formando una base de datos con informac"ión del estado actual de la red.
+ Calcula las rutas para los paquetes en forma dinámica, esto lo hace con base en las tablas' de estado las cuales contienen información sobre' los nodos existentes eh la red así como un costo asociado a cada camino.
+Mide el tiempo de1,retraso entre nodos, por medio de un mensaje de prueba que envía a sus vecinos cada determinado tiempo. Este mensaje tiene dos objetivos"uno es asegurar 'que todos los nodos estén activos y otro es medir el tiempo de retraso, dicha información forma parte de la base de datos.
I1
57
Simulación con agentes intencionales para equilibrar el ftáfico en una red de área local
Una ventaja que presenta este algoritmo, es que asegura el paso de información entre los diferentes nodos por el camino más seguro y rápido, en caso de que el nodo destino este fuera de servicio se informa rápidamente a todos los nodos que conforman la red, para que lo eliminen dentro de sus caminos alternos para el envío de información, así como una rápida notificación a los nodos origen de mensajes que estaban dirigidos hacia el nodo que ya no está en servicio dentro de la red.
El enfoque que se propone para modelar el algoritmo de enrutamiento por estado de enlace, es con el uso de sistema mulfiagenfe.
4.4 JUSTIFICACIÓN DEL USO DE AGENTES INTENCIONALES
Una característica importante de este problema es la .interacciÓn constante con el medio ambiente (el estado de la red), y que requieren una solución con un programa autónomo.
Se requiere un programa que de forma automática actualice la información acerca de los nodos activos en la red, y su tiempo en el envío de información. Lo anterior sirve para establecer las rutas de los mensajes entre los nodos de la red.
Dicho programa simulara parte del trabajo de un administrador de la red, al examinar el estado de la red y tomar decisiones sobre rutas de envío de mensajes. Convirtiendo este problema en una aplicación ideal para agentes por sus características de autonomía y generación de diversas soluciones de manera dinámica al problema de tráfico en una red.
Se construirá un sistema multiagente teniendo un agente por cada nodo que participe en la red, para aseguramos que el funcionamiento de red no recae en un solo nodo, sino que cada nodo de forma independiente estará encargado de actualizar el estado de la red como describe en la siguiente sección.
AI estar actualizando elestado de la red el agente genera su propio conocimiento sobre su medio ambiente, y con está información creará las rutas para enviar mensajes, evitando saturar nodoc en la red.
Se decidió trabajar con agentes de tipo intencional, porque un agente de tipo intencional cumple con las características de un agente, de actualizar su información y con base en esa información tomar sus decisiones que rigen su comportamiento.
El agenfe no tiene como principal objetivo conocer la estructura de otros agentes, por lo que no seria conveniente un agente de tipo social u otro más complejo.
58
Simulación con agenfes infencionales para equilibrar el tráfico en una red de área local
En el sistema multiagente que se va a crear (un agente en cada nodo de la red), cada agente va a tener(diversas intenciones, las cuales son: cuando actualice el estado de la red, al enviar un mensaje por una ruta establecida, al medir un tiempo de retraso en el paso de información entre los nodos de la red.
Por esto se trabajo con un modelo que tome en cuenta las intenciones y que facilite la comunicación en un sistema multiagente, como lo es la arquitectura de intenciones BIG (creencias, intenciones y metas), y el modelo de comunicación entre agentes propuesto bajo las mismas consideraciones de intenciones y agentes del mismo tipo.
i
I1
4.5 ETAPAS DE LA SOLUCIÓN ,fi
Primero se describe ed'forma general los cinco pasos básicos de los que se compone el algoritmo por estado de enlace y posteriormente se explica como fue la implantación con el modelo de comunicación entre múltiples agentes intencionales basados en la arquitectura BIG (creencias, deseos, intenciones).
4.5.1 ALGORITMO DE ENRUTAMIENTO POR ESTADO DE ENLACE
I El algoritmo por estado de enlace consta de cinco pasos básicos que se presentan a' continuación: I/
I!
1
1. Descubrir a sus nodos vecinos y conocer sus direcciones de red.
2. Medir el retardo o costo para cada uno de sus nodos vecinos.
3. Construir un paquete de estado que indique todo lo que acaba de aprender. I1
4. Enviar este paquete a todos los demás nodos. I ,I
5. Calcular la trayectoha más corta a los nodos que se necesite enviar ir8formación.
4.5.2 DISENO DEL ALGORITMO CON AGENTES INTENCIONALES
Para hacer la simulación se creará un agente el cual debe residir en cada nodo de la ,; red. El agente cubre con las características descritas en la sección 2.3.2. Un panorama general sobre el algoritmo de enrutamiento por estado de enlace y su 1
representación con agentes de tipo intencional se explica en la figura 4.1.
Las creencias se representan con la información acerca del estado de la red, ~
clasificando la información ;recolectada en dos tipos: las tablas de estado (contiene los nodos activos en toda 1.a red y los tiempos de retraso, asociados en el envío de información), y el conocimiento descriptivo acerca de sus nodos vecinos que están activos.
I/
59
Simulación con agentes intencionales para equilibrar el tráfico en una red de área local
Las intenciones surgen cuando un agente tiene un mensaje a enviar, que puede ser de prueba (para medir el tiempo de retraso) o con información que requiera ser enviada por la red. Cuando se requiera enviar información se comienzan a generar una serie de posibles soluciones (rutas para el mensaje), generadas a partir de la información que tienen las tablas de estado (creencias). Después se comparan las rutas generadas y una intención es convertida a meta que debe ser la ruta Óptima (tiempo mínimo de envío), para un nodo destino el cual debe ser factible dentro de la red.
La meta de enviar información se considera externa ya que la acción de crear una ruta para un mensaje, fue solicitada y no generada por el agente mismo. Las metas internas del agente son: crear reportes (las tablas de estado) con fespecto al tiempo de retraso entre ese nodo agente y su vecino, la otra meta es enviar mensajes de prueba para calcular el tiempo asociado de un nodo agente a sus nodos vecinos.
Tablas de estado Conocimiento sobre sus vecinos restricciones
Decisiones o Metas: Elección de la ruta Óptima Reporte de tabla de estados
I / ' I /
Capacidades o Intenciones: Generación de rutas I/ restricciones
I Generación de tiempos'de retraso acciones
Acciones : Envío del mensaje Envío de tabla de estados
Figura 4.1 Modelo del agente para el algoritmo de enrutamiento por estado de enlace
Como podemos observar, cada agente tiene metas particulares como son generar la ruta de un mensaje que requiera ser enviado por la red, así como estar actualizando su tabla de conocimiento de sus vecinos para saber las rutas actuales por donde puede enviar la información.
Se justifica el llamarse agente porque tiene conocimiento propio que genera y comparte con otros, dicho conocimiento es dinámico cambia de acuerdo como lo requiera el medio. Tiene metas externas e internas 'que van combinando para determinar que función sera ejecutada de acuerdo a como lo requiera en entorno de red, las metas son resueltas por cada agente de forma independiente al estado de otros agentes dentro de la red lo que hace autónomo.
60
Simulación con agentes intencionales para equilibrar el tráfico en una red de área local
Haciendo un análisis se observa que un agente solo tiene información de una parte de la red, y que para cubrir su meta general o global dentro del balanceo de tráfico en una red, debe comunicarse con otros agentes que le proporcionen información sobre. otra parte de la red'que no es factible directamente por el.
AI componerse el sistema por varios agentes, se crea información diversa que debe compartirse en el sistema como se observa en la figura 4.2 y son:
I! +:* Las tablas de estado contienen información sobre partes parciales del
estado de la red. Estas son las que se comunican. 0:. Envío de mensajes (información) por un canal adecuado. 0:. Mensajes prueba para actualizar el estado (activo o inactivo) de un nodo
agente en la red, y ;medir su tiempo de retraso en el envío de información.
Capacidades .Tranimision de tabla de
eriador modificada
a SUS Y E E i " 0 X i
.Tiempos dc re t ra~o .
lor d e m i s enrutadorer.
envio de mcnsajc
Agente B
CXC"CiaS
.Transmisión d e tabla d e IU Capacidades estados modificada
respecto
.Envio del mcnsajc por el a SUI "SC i"0S .
canal adecuado.
.Calcular l a trayectoria más coria con respacto a Io$ d c m á s enrutadarsi .
Solicitud de envio
Figura 4.2 Modelo de intercambio de información entre dos agentes para el balanceo de tráfico.
Un ejemplo de lo anterior, es cuando una red como la mostrada en la figura 4.3, tiene un nodo agente A al cual se le solicita enviar un mensaje a un nodo agente J (meta I
externaj, pero no existe un camino directo de A hacia J.
61
Simulación con agentes intencionales para equilibrar el tráfico en una red de área local
La siguiente acción del nodo agente A es buscar en su base de datos (creencias) si el nodo J es factible, y generar los caminos posibles (intenciones) por los que puede alcanzar este nodo, para después elegir la ruta que contenga un menor tiempo, y tomar ese camino estableciéndolo como ruta Óptima para el mensaje solicitado.
Cumpliendo la meta propuesta inicialmente, de enviar el mensaje de un origen a un destino (meta particular), y equilibrar el tráfico en la red (meta global).
Figura 4.3 Un ejemplo de una red de área local
4.5.3 IMPLANTACIÓN DEL ALGORITMO CON AGENTES INTENCIONALES
La idea principal del modelo de comunicación surge de la necesidad de intercambio de información que presentan los agentes dentro de cada nodo de la red para balancear su tráfico. Dicha comunicación se presenta en el proceso de alcanzar las metas globales y particulares explicadas.
Para el modelo propuesto los actos de comunicación son definidos en función de estados o mundos posibles (sección 4.6.2 ) y un protocolo de comunicación que se describen a continuación. Los mundos posibles pueden ser subobjetivos de otros objetivos más complejos en los que un agente tiene una intención de actuar.
El sistema multiagente debe contar con un protocolo de comunicación, que indique. las performativas válidas y el significado de ellas, para este algoritmo se detectaron 6 performativas que indican diferentes cosas y dependiendo del contexto en que se manejen las interpretará el agente.
+ NA-HELLO, sirve para anunciar que un nodo se encuentra activo. *:e NA-REHELLO, sirve para responder a un nodo que anuncio que está
activo. o:* NA-ECHO, sirve para verificar que un nodo sigue activo, y medir el tiempo
de retraso para un mensaje. $3 NA-REECHO, sirve para responder que sigue activo un nodo y reportar el
tiempo de retraso. *:* MandaFile, sirve para enviar un mensaje con información. *3 MandaFile, sirve para enviar paquetes que indiquen el estado-de la red.
62
B ~ ~ ~ u l a c i ó ~ ~ COIJ ageiiles infeiJcio/iales para equilibrar el tráfico eii uiia red de área local 11
I1 Se interpretan como se describe en los siguientes párrafos dentro del sistema:
G NA-HELLO Se presenta al inicio del algoritnio, cuando un agente no posee suficiente información aGerca de sus nodos vecinos o del estado en general,
conocer a cada uno de, sus nodos vecinos, quienes le contestarán con NA-REHELLO, como se observa en 1a.figura 4.4.
de la red. El agente debe enviar iriensajec de prueba por priniera vez, para ':I
, G NA-REHELLO es una ,respuesta de confirniación que regresa un nodo,
habiendo recibido previamente un NA HELLO, contiene la dirección del nodo que envia y del que recibe ia i ka r ido los datos de conexión. Y finalmente cuando se rgcibe el NA-REHELLO se establece la conexión, figura 4.4.
Establecida previanierite la coiiiuiiicacioii. el age'iite ' debe observar constanterriente el estado de la red. Entonces eiivia iiietisajes de prueba NA-ECHO con el objeto d,e niedir el tieiiipo de respuesta de un nodo vecino que le respondera con uh NA-REECHO, y as¡ crear las tablas de estado para comunicarlas a otros agentes. Se puede ver igual que NA-HELLO Y NA-REHELLO en la figura 4.4.
t7 La instrucción riiaiidaFile se usa para eiiviar las tablas de estado con información correspondierite a una paitr r l , , J nstado actual de la red. Sólo es para informar a sus vecinos sobre su estado. y con quien tiene conexión asi como los tiempos asociados.
'
G La instrucción iiiaiidaFile taiiibieii se utiliza para envios de mensajes de un nodo agente fuente a Iin nodo agente destino.
La sintaxis interna de los mensajes que circulati por la red es.la siguiente: , . ,(i . '
2 : ,.
. . Origen!Destino!Trayecto&k,!Meiisaje "j'. ,, :,;;
, , ? . . , ' . .. . Donde: . .
Origen = Destino: son los iioiiibres de los nodos ruteadores involucrados.
Trayectoria: es la serie de iioriibies de los nodos ruteadores por los que el paquete pasará, cada nombre seguido de una coma (J.
1(
,/
Mensaje. consiste de peifoiiiiativa (14 protocolo de comunicación y la información que se iiecesite, o la iiiforiiiacioti que el usuario desea mandar por ejemplo un íragiiienio del arcliivo de prueba. etc
I
El signo de admiración ( ! ): es un deliiiiitador en el mensaje que circula por la red. ,:
1 63
Simulación con agerifes iriiericionales para equilibrar el tráfico eri una red de área /oca/
Creencias
Meta (NA-REHELLO) Enlace de comunicación
Met a (IJA-RE HELLO) Enlace de comunicación.
8
Figura 4.4 Representación del funcioiiaiiiieiito del protocolo de comunicación con la perforrnativa NA-HELLO Y NA-REHELLO
En esta sección se explicó la forma en que se interpretan, los componentes del modelo de comunicación su significado para este sislema
También se mostró la estructuia qiie leiidrari los iiierisajes, lo cual es muy importante en el funcionamiento de la siiiiulacioii eii que se prueba el modelo, a continuación se explica como rueroii iiilerpieláiidoce cada uno de los pasos del algoritmo de enrutaiiiierito por estado de eiilace. coil el protocolo y adaptandolo al paradigma orientado a agentes
4 5 4 DESCUBRIR A SUS NODOS VECINOS Y CONOCER SUS DIRECCIONES DE RED
Para hacer esto se diseño el agetile nodo coil tiiia estitictiira ei i doiide inicialmente se dan de alta los nodos (direccioiies) coil quienes podia establecer conexion.
AI iniciar sus actividades uti agente nodo. debeiá ioriiar las diieccioiies que tenga registradas como riodos vecinos. y eiiviailes la iiisti iiccioii NA-- t iELLO. Esperar un tiempo de 1 minuto como niaxiiiio para recibir la resptiesta NA-REHELLO; y etiquetar a ese nodo como activo o de lo contrario etiquetarlo como inactivo.
64
Simulación con agentes Mencionales para equilibrar el trrifico en una red de área local
.......................... !DNA-HELLO I ..........................
I
,I/ ( INT x, a ) (GOAL X, a ) .......................... i DNA-HELLO i
Selección de una ruta adecuada. Meta
..........................
T I
información
NA HELLO
NA-ECHO
MandaFile
I. -
II
Tablas de Estado Válidas (Creencias)
r
rutas ( Intenciones)
t I .
Verificador de I- ( INT x, a )=(BEL x : a )
&alización de tablas de estado. 1
( GOAL x, a ) s ( BEL x, ( GOAL x, a ) )
Figura 4.5 Interpretación matemática de NA-HELLO y NA-REHELLO
La figura 4.5 es una interpretación gráfica del funcionamiento interno del agente y de '
la forma en que se aplica el modelo propuesto basado en creencias, intenciones y metas BIG.
El módulo monitor debe tener un procesó para detectar que el nodo agente a ha iniciado su funcionamiento !en la red, comienza revisando que nodos son vecinos, para triitar de establecer I. comunicación con esos nodos vecinos formando la intención x para agente a.
Primero debe pasar por la verificación de creencias del agente, marcando que una intención deber ser congruente con su base de conocimiento para poder ilegar a ser meta. Por lo que el agente a debe creer que la dirección x está dada de alta como un nodo vecino. )!I
i!,
La intención x se transforma en meta al crear la estructura del mensaje, con la dirección de un nodo vecino tomada de las creencias del agente y la performativa NA-HELLO, para ser enviada y establecer comunicación con el nodo vecino.
65
Simulación con agentes intencionales para equilibrar el tráfico en una red de area local
NeighborName NeighborAddr NeighborActivo (Nombre del nodo (Dirección del (Indica que un
vecino) nodo vecino) nodo está activo)
Carácter Numérico Booleano
statTime (Tiempo de retraso
asociado a este nodo,
milisegundos) Time
La clase NetworkAgentGUl es el archivo ejecutable principal, es el agente propiamente, quien hace las llamadas a clases y métodos para funcionar apropiadamente. - Está clase cuenta con el método HELLO que se encarga de 1lamar.a otra clase
La clase LocallnfoPanel es la inicial da de alta al nodo local donde se está corriendo la simulación, introduciendo el nombre del nodo y su dirección. La clase NeightborlnfoPanel genera las tablas de información sobre.los nodos I
vecinos. La clase AgentOutPort maneja el cliente que funciona como salida del agente, corriendo en hilos para poder tener una conexión con cada servidor. Esta clase es la encargada de hacer la función HELLO por medio de sockets con el método connect. La clase AgentlnPort maneja el servidor de sockets, para tener varios vecinos tiene varias conexiones una por cada vecino, el nodo local tiene una parte de servidor, que es el trabajo de la clase AgentlnPort. Encargada de manejar el nodo local como servidor, corriendo un hilo para cada conexión, al tener conexión con un nodo vecino se cumple la intención de establecer conexión. Esta clase tiene los métodos saber que tipo de, mensaje se recibe y.tomar una acción adecuada, ver apéndice A.
para conocer a sus nodos vecinos.
66
Simulación con agentes intencionales para equilibrar el tráfico en una red de área local,
C m 0 se Puede observar Un nodo agente local hace funciones de servidor Y cliente de acuerdo a COmO Sea solicitado, también debe tener métodos de actualización parai 10s datos que les envíen, dichos métodos deben verificar la información externa con ia interna y mantenerla congruente, ver apéndice A.
4.5.5 MEDIR EL RETARDO O COSTO PARA CADA UNO DE LOS NODOS
Después de haber actualizado las creencias de un nodo agente acerca de sus vecinos, es decir, al tener la base de datos los nodos vecinos activos, se tiene una conexión hacia ellos (por medio de hilos) y la certeza sobre sus direcciones.
Para este momento ya se puede comenzar a enviar mensajes de prueba para comenzar a crear el estado de la red. Por medio de la performativa NA-ECHO, que crea un mensaje de prueba.
El mensaje de prueba funciona grabando el tiempo del sistema en milisegundos, antes de enviarlo a al vecino correspondiente, el vecino al recibir en un mensaje la performativa NA-ECHO deberá reenviar el mensaje pero con NA-REECHO.
Cuando se recibe NA-REdHO se vuelve a tomar el tiempo del sistema y se hace '' una diferencia de tiempos, para establecer un peso asociado a al nodo vecino. Y con , esto crear un registro para formar una tabla de estado con información del nodo actual, sus nodos vecinos yjel tiempo de retraso asociado a cada uno de ellos.
Se tiene la clase ECHO que mide el costo asociado a cada nodo vecino con quien se ~
tiene conexión, como en eli,proceso descrito anteriormente, se maneja una variable startTime que sirve de conthdor de tiempo en milisegundos, que se inicia al enviar el mensaje y se detiene al momento en que regresa el mensaje, ver apéndice A,' El paquete se forma como sigue:
Msg= IocalName ! NeighborName ! IocalName , NeighborName ! NA-ECHO
AI manciar el mensaje se tiene la intención de medir el tiempo de retraso asociado a un nodc vecino, cuando ilesa el mensaje la intención se convierte en meta al tener el valor de la variable startTime.
Esto se hace por cada nodo vecino y se maneja por medio de hilos, la clase Echo Timer es quien se encarga de generar estos tiempos haciendo uso de la clase Echo para cada nodo vecino, ver apéndice A.
Estás son clases que contiene el nodo agente local como intenciones para posteriormente generar tablas de estados y poder calcular rutas míriimas, que ayudarán a cumplir con su meta general de balancear el tráfico en la red.
'
ij
67
Simulación con agentes intencionales para equilibrar el tráfico en una red de area local
allName (Nombre del nodo)
4.5.6 CONSTRUIR UN PAQUETE DE ESTADO QUE INDIQUE TODOS LO QUE
Una vez que el agente ha terminado de establecer los tiempos de retraso asociados a sus nodos vecinos activos, se continua con el algoritmo de enrutamiento por estado de enlace.
El siguiente paso que es construir una tabla de estado (mensaje), se forma poniendo como encabezado el nombre y dirección del nodo actual, después las direcciones de los nodos vecinos seguidos del tiempo de retraso. La estructura se puede ver como sigue:
' . ACABA.DE APRENDER'. ,
Nombre, Dirección, Número de envío
Dirección de vecino, tiempo de retraso Mensaje
El tiempo de retraso es muy importante porque de acuerdo a este, más adelante se pueden construir las rutas óptimas para enviar información.
La estructura que se utiliza para estos tipos de datos se declara en ¡a clase NetState como una lista con cabecera, como la tabla 4.2, ver apéndice A.
AllAddr sec Tabla de (Dirección del nodo) (Número de envio, Vecinos
milisegundos)
Neighbord (Dirección del nodo
vecino) Numérico
Delay (Tiempo de retraso,
milisegundos) Entero
4 5.7 ENVIAR ESTE PAQUETE A TODOS LOS NODOS
Creados los paquetes son enviados a los nodos vecinos de un nodo.agente a, y ellos a su vez lo enviaran a sus nodos vecinos, este algoritmo se le llama inundación
68
Simulación con agentes infencionales pata equilibrar el tdfico en una red de área local
Una problema de este algbritmo es que cuando se tengan dos paquetes del mismo" nodo.agente a, con nuevaiinformación a cerca de la red como sabrá el nodotagente ~
vecino a que información desechar y cual tomar.
Por lo que se decidió ponerle un número que indique que paquete es, es decir el , primer paquete comienza en 1 y el segundo que se cree en 2, así si en un momento dado le llegan dos paquetes de un nodo agente a, a un nodo agente p tomará el de número mayor, ya que es el actual. Esto se hace con el objetivo de tener informados a todos los nodos de la red,el estado actual de esta.
La clase LinkState es la <ue genera y manda la tabla de estado, con la información acerca del nodo local y sus nodos vecinos reportando también el tiempo de tetraso ' asociado a cada nodo. La'j'estructura que se usa es como la que se mostró en la sección 4.5.6, ver apéndice A.
Como se mencionó cada agente envía y recibe las tablas de estado de sus nodos vecinos, por lo que el nodo!!agente local también cuenta con métodos encargados de recibir las tablas de estado de sus nodos agentes vecinos.
La clase AgentlntPort esta encargada de actualizar estos datos en la base de conocimientos (creencias);"por medio del método table que actualiza los datos de NetState de la estructura cbrrespondiente a allName y alllndex, que del mismo tipo de estructura mostrada en la sección 4.5.6, ver apéndice A
11
4.5.8 CALCULAR LA TRA~ECTORIA !I. MÁS CORTA
El agente a para este momento ya cuenta con información acerca de sus 'nodos vecinos, además de la información acerca de otros nodos manteniendo el estado general de la red.
Por lo que será capaz de crear rutas Óptimas para la información que requiera llegar aun destino cualquiera factible dentro de la red. Para crear la ruta óptima se utiliza el "
algoritmo de Dijkstra [Tanenbaum 19971, se explica a continuación:
Cuando se le solicita al agente enviar información, primero se verifica que el destino sea factible desde este oiigen. Después si es factible se pasa como intención externa, es decir, se va a tener la intención de crear una ruta Óptima para la infor,mación. Primero se crean todos los caminos posibles y después SI? elige con ,
.respecto ai menor tiempo cdai será la ruta óptima.
Inicialmente no se conocen las trayectorias, por lo que todos los nc,dos tienen ,, etiqueta infinito. A medida!/ que avanza el algoritmo, se encuentran trayectorias diferentes entonces pueden ser cambiada.s las etiquetas reflejando mejores trayectorias.
/ I
ti
69
Simulación con agentes infencionales para equilibmr el tráfico en una red de área local
Una etiqueta puede ser tentativa o permanente; inicialmente todas las etiquetas son tentativas; al descubrirse que una etiqueta representa la trayectoria mas corta posible del origen a ese nodo, y se vuelve permanente para no cambiar mas (para la ruta que se está calculando en ese momento).
Para ilustrar el funcionamiento de este algoritmo se realiza la siguiente figura 4.6 inciso a, donde las ponderaciones representan distancias. Se quiere encontrar la trayectoria más corta posible de A a D.
Se comienza marcando como permanente el nodo A, indicando por un círculo relleno. Se examina por turno entonces cada uno de los nodos .vecinos hacia A reetiquetando a cada uno de los nodos con los tiempos encontrados desde A. Cada vez que es reetiqueta un nodo también se reetiqueta el nodo desde el que se hizo la prueba, para poder reconstruir la trayectoria final.
Examinados cada uno de los nodos vecinos hacia A, se examinan todos los nodos etiquetados tentativamente en el grafo completo (B y G) y se hace permanente el nodo de la etiqueta mas pequeña B, como se muestra en la figura 4.4 inciso b, donde B se convierte en el nodo de trabajo.
Ahora se continúa examinándose todos los nodos vecinos al nodo B. Si la suma de la etiqueta B y la distancia desde B al nodo vecino E es menor, que hacia cualquier otro nodo vecino que B pudiera tener, tiene la trayectoria más?. corta por lo que reetiquetamos ese nodo, para este caso fue E.
En este proceso de elección para un nodo de trabajo también entra el nodo G en la selección porque sigue siendo una ruta posible (recordando que el' nodo G había quedado eliminado al seleccionar B).
Este proceso se observa como un árbol de múltiples opciones, donde todas las ramas siguen compitiendo durante todo el proceso de generación de la ruta, con esto se asegura que se contemplaron todas las rutas .posibles de un nodo origen a un nodo destino.
Tras inspeccionar todos los nodos adyacentes al nodo de trabajo y cambiar las etiquetas tentativas se busca el nodo etiquetado con el menor valor tentativamente. Este nodo se hace permanente y se convierte en el nodo de trabajo para la siguiente ronda.
Para comprobar el funcionamiento del algoritmo se muestra el resultado en la figura 4.4 inciso c donde E se hace permanente. Suponiendo que hubiera una trayectoria mas corta que ABE, por ejemplo AGE, entonces existen dos posibilidades:
*:* El nodo G ya se hizo permanente, entonces E ya se probó por lo que la trayectoria AGE no ha escapado a nuestra atención.
*:* El nodo G no se ha hecho permanente.
70
Simulación con agentes infencionales para equilibrar el tráfico en una red de área local
Ahora se considera el caso en el que G aún está etiquetada tentativamente, existiendo dos posibilidades:
*:* Que la etiqueta de G es mayor o igual que la de E, en cuyo caso AGE no
-3 Que es .menor que la de E en cuyo caso G y no E se volverá permanente
Como se observa en el desarrollo de este algoritmo para encontrar la ruta Óptima, siempre se toman en cuenta las otras posibilidades, asegurando que la ruta que resulte será la óptima.
Se utilizan los tiempos asociados a los nodos vecinos, por lo que se incrementa el valor de tener información actualizada acerca del estado general de la red. Y observamos que en todo momento se involucran, las creencias o base de datos, las intenciones o rutas generadas, y se elige una de ellas.
puede ser una trayectoria más corta que ABE
primero, permitiendo probar E desde G. i
Figura 4.6 Ponderación de pesos dentro de una red
La clase Shortpath se encarga de encontrar la ruta más corta entre dos nodos dentro de la red, utiliza el algoritmo de Dijastra implementado dentro del método findpath, ver apéndice A. !I
71
Simulación con agentes intencionales para equilibrar el tráfico en una red de área local
Para la simulación que se realizó no había un mensaje de un nodo hacia otro que fuera solicitado, por eso se decidió calcular ,las rutas hacia todos los nodos alcanzables desde el nodo local.
Por medio del método update de la clase Shortpath, se van analizando uno a uno los nodos registrados en.la tabla de estado de la red, para calcular un tiempo mínimo y reportarlo. Se reportará un tiempo de infinito para indicar que un nodo no se alcanzó, ver apéndice A.
Para simular el funcionamiento de la red se crearon archivos, los cuales son enviados aleatoriamente por la red, dichos archivos se crean en la clase Networmgent con el método writeFile se crea el archivo test.txt y se envía a los nodos vecinos.
Teniendo diseñado e indicado el funcionamiento, se hizo una simulación de este programa, haciendo un agente para cada nodo en la red, que se muestra en la siguiente sección.
4.5.9 DESCRIPCIÓN DE LA INTERFAZ GRÁFICA DEL SIMULADOR
Explicado el diseño del modelo y la forma de implantarlo se presenta la simulación que se efectuó. El simulador presenta inicialmente una ventana con diferentes pestañas que son el menú al que podemos entrar y observar todas las pantallas de entrada y salida de los datos.
AI arrancar el simulador se presenta la pantalla para introducir los datos sobre el nodo local.
72
Simulación con agentes infencionales pam equilibrar el tráfico en una red de área local,
Para el caso de la pantalla, se solicita el nombre del nodo local para este caso es el nodo "A" y su dirección e~'~132.254.41.74. Los datos de las variables del nodo local.., serían: 1
LocalName = A .LocalAddr=l32.254.41.73
El siguiente panel que debe ser llenado con las direcciones IP de sus nodos vecinos /I
A continuación se debe llenar el panel red, en el cual se pondrá el nombre de todos los nodos de la red.
Y
Simulación con agenfes intencionales pam equilibrar el tráfico en una red de área local
NeighborName NeighborAddr (Nombre del (Dirección del nodo vecino) nodo vecino)
Para finalizar se va al panel simulación donde se puede dibujar la topología de la red. Esto no es necesario, dado que es sólo para presentar una imagen gráfica de la red a los observadores.
NeighborActivo statTime (Indica que un nodo (Tiempo de retraso
nodo. está activo) asociado a este
En este paso se van llenando los datos de la estructura de los vecinos mostrada en la sección 4.5.4 y sería:
B D
132.25~. . . . . . . -- .- 132.254.41.77 IT I3396
I '
milisegundos) 141 74 IT I7r115
En este Panel también se encuentra el botón de Inicio, el cual debe ser apretado sólo cuando se ha introducido toda la información de la red y sólo si fue introducida correctamente, para que mmiencen a trabajar los agentes.
Si se crearon errores al introducir los datos, esto repercutirá fuertemente en la corrida del programa, como dejar nodos desconectados o bloquear uno de los nodos agentes por completo.
En esta versión no se incluyen herramientas gráficas para corregir errores, aunque si hay algunas herramientas en el código, pero no son accesibles desde las interfaces creadas.
74
Simulación con agentes intencionales para equilibrar el tráfico en una red de área local,
allName (Nombre del nodo)
B D C E A
Si se cometen errores, se debe reiniciar al agente en la máquina en la que se" cometió el error. El botón de unir dibuja una unión entre dos nodos ya dibujados.
Una vez que se inició la simulación el botón es reemplazado por el botón de mandar, el cual sirve para mandar archivos a otros nodos.
' AllAddr sec (Dirección del nodo) (Tiempo de retraso,
milisegundos) 132.254.41.74 O 132.254.41.77 O 132.254.41.80 1 132.254.41.85 1 137 754 41 90 1
En este momento se van illenando las estructuras faltantes al recibir las tablas de estado de los nodos vecinos que van quedando de la siguiente forma:
allName Neighbord (Nombre del nodo) j (Dirección del nodo
:l. vecino) A 132.254.41.74 (B) A il32.254.41.77 (D) B i132.254.41.80 (C) B 132.254.41.85 (E) D (132.254.41.85 (E)
C '1 32.254.41.85 (E) E '432.254.41.74 (B) E \132.254.41.77 (D) E 132.254.41.80 (C)
C ,il32.254.41.74 (8)
Delay (Tiempo de retraso,
milisegundos 1336 2476 1632 2032 2533 1022 1172 1923 1232 1863
'!I
4 5.10 F.ESULTADOS OBTENIDOS EN LAS CORRIDAS DE PRUEBA
El simulador fue corrido con varias topologías y diferentes números de nodos. Para todos Icis resultados obtenidos fueron similares. Un ejemplo de los resultados se presenta a continuación. 11
75
Simulación con agentes intencionales para equilibrar el tráfico en una red d e area local
Para esta prueba se utilizaron 5 nodos, conectados en la manera en que se muestra en la pantalla anterior.
Se mandaron archivos del nodo C al nodo D para hacer las pruebas, con lo que se tienen tres rutas para los paquetes, C-E-D, C-B-A-D y C-E-B-A-D.
Cuando iniciamos la prueba, el simulador encontró los siguientes pesos de las líneas:
76
Simulación con agentes intencionales para equilibrar el tráfico en una red de área local
Esta pantalla es una foto inicial sobre los tiempos asociados a los nodos en la red, antes de que comiencen a trabajar los. agentes, dichos tiempos se explicaron en la sección 4.3.5.
AI mandar los paquetes la. primera vez, la trayectoria seguida es C-E-D, dado que' mide 2404. Los costos de i'as líneas están expresados con el origen en el eje vertical , y el destino en el horizontal.
Un peso de O indica que no hay conexión y para conexiones muertas, esto es, que existe línea pero el costo no se pudo medir, se le da un valor de 1000000.
La trayectoria C-B-A-D mide 5081 y la trayectoria C-E-B-A-D mide 7154. En e'l panel de trayectorias de puede ver la trayectoria que cada paquete de un archivo de , prueba mandado desde el nodo local tomó.
Para la simulación se enviaron archivos de prueba para saturar la red donde, cada archivo de prueba tiene 100 paquetes.
11
Mandando a D via: C E D Mandando 3 D via: C E D Mandando a D via: C E D Mandando a D via: C E r Mandando a D via : C E D
En la siguiente medición de las líneas, se encontró que el tráfico en algunas de ellas subió ccinsiderablemente. I/
I,,
77
Simulación con agentes intencionales para equilibrar el tráfico en una red de área local
Nuevamente mandamos el archivo de pruebas desde C a D, pero esta vez tomó otra ruta, C-B-A-D, la cual medía 6740.
La ruta C-E-D medía 31525 y la ruta C-E-B-A-D medía 32127.
Mandando a D via: C B A D Mandando e D via: C B A D Mandando a D via: C B A D
Mandando a D via: C B A D Mandando a D via: C B A D
Después de la siguiente actualización encontramos que las líneas que habían subido de costo antes bajaron de costo y ahora otras subieron de costo.
78
Simulación con agentes intencionales para equilibrar el frrjfico en una red de área local
Con esto podemos ver que los agentes están, cambiando las .trayectorias de los 11
paquetes para que una línea no suba mucho de costo.
Con los resultados de la simulación observamos que si se van equilibrando los ,!
pesos, existen varios comentarios en este sentido.
Se decidió terminar hasta aquí el presente trabajo por las siguientes razones:
1. El objetivo de la simulación era probar el modelo de comunicación presentado en el capítulo 3, teniendo bueno resultados en el sentido de que se acoto el problema, al crear un agente por nodo se presenta una solución dis.tribuida.
Dicha solución no depende de los otros nodos que intervienen en la red, es decir, cada nodo es independiente y unidos forman un sistema mulliagente, que resuelve el problema de trafico en una red, sin importar que el estado de la red cambie en forma constante.
Se aprecia también que se baja la complejidad de al diseñar un sistema de esie tipo, porque solo nos preocupamos por tener un agente, con diversos procesos, que se comporten en diversas situaciones.
!.
~
2. No s.e reportaron tiempos porque es una simulación, que depende del equipo en que sea probado, por lo que resulta muy variante.
Los resultados que podemos observar, serían que cuando un tiempo en un nodo agente a no baja para ningún nodo vecino, es porque su velocidad es baja y no tanto porque la red esté saturada.
79 .,
Simulación COR agentes intencionales para equilibrar el tráfico en una red de área local
ubrir los puntos propuestos al inicio del trabajo, donde se hace un compromiso de crear un modelo y llevarlo a la práctica, mostrando que simplifica los problemas de comunicación que presentan los agentes.
Se hizo la prueba en un sistema de redes donde la comunicación es vital para el funcionamiento. del sistema, por lo cambiante que suelen ser y .se observó que efectivamente el sistema cambia respecto a como lo hace su medio ambiente, y cambia de actitudes para adaptarse.
De este modo damos por terminado la prueba del modelo, y presentamos las conclusiones generadas del presente trabajo.
80
Conclusiones y Trabajos Futuros '
CAPITULO 5 .!/
CONCLUSIONES Y TRABAJOS FUTUROS
5.1 CONCLUSIONES
Durante el desarrollo del presente trabajo se realizó una investigación sobre la programación orientada a agentes como un nuevo enfoque para resolver problemas.
AI investigar este nuevo enfoque se observa que todavía no se tiene un estándar establecido como metodobgía de programación, como podríamos observar en la ~
programación orientada a objetos, siendo un área importante para investigar y aportar nuevas ideas.
En el presente trabajo se desarrolló un modelo de comunicación con ,bases matemáticas que justifican !:su comportamiento en diversas situaciones además de tomarse como fundamento en aplicaciones posteriores para sistemas bajo este enfoque, evitando incongruencias en la ejecución de acciones utilizando la arquitectura que también se'propone en este trabajo para un sistema mulfiagente.
~
./I
Como conclusiones de este trabajo se tienen las siguientes:
1, Podemos afirmar que la naturaleza distribuida de algunos problemas se debe resolver con enfoques de características similares, por lo que la programación orientada a agentes es un enfoque recomendable.
2. Como resultado del desarrollo de. la' simulación se pudo comprobar que la comunicación entre agentes es un soporte para resolver el problema de balanceo de tráfico en una red de área local, sin importar la topología que tenga la red o lo cambiante que está pueda comportarse al tiempo de ejecución.
3. Se presentó la aplicación de una arquitectura para la construcción de agentes, la cual ektá soportada en un modelo matemático. formal que es la lógica modal,,, y una aplicación real del modelo matemático desarrollado, por lo que podemos observar que las teorías mostradas a lo largo de este trabajo son totalmente aplicables a la solución de problemas distribuidos reales.
li
5,'
,;
!.
I! 81
Conclusiones y Trabajos Futuros
4. El uso de agentes para formar un sistema mulfiagenfe con un protocoio de comunicación adecuado es una buena solución al problema de tráfico en redes, ya que para el balanceo total de la red se requiere un sistema distribuido en el que todos los elementos que lo constituyan aporten información necesaria para la solución al problema del tráfico.
5. Una aportación importante del modelo de comunicación, es observar como se hace una abstracción real del comportamiento de personas para resolver problemas en sociedades, lo anterior es con respecto en la evolución de una intención desde que se toma como tal se hace su verificación de congruencias hasta que finalmente se convierte en meta generando una acción a ejecutar, lo que hace más sólido a un sistema a tiempo de ejecución.
6. La simulación donde se aplicó el sistema mulfiagenfe nos demostró que el grupo de agentes colaborando (comunicando información, para este .caso el estado actual de la red) en un problema global (el tráfico de la red) logran resolverlo, es decir en nuestro problema'se alcanzó un balance equilibrado del tráfico de red.
7. Falta hacer pruebas más específicas de la simulación, en equipos con diferentes características y en diversas condiciones, con el fin de establecer en forma definitiva que la aplicación de agentes a sistemas de redes es una solución óptima y eficaz. e
5.2 TRABAJOS FUTUROS
Como trabajos futuros se propone:
* Que el problema de balanceo dentro del tráfico en una red de área local sea llevado a una aplicación real, no solo en simulación sino como una implantación con uso de ruteadores reales como los que,,se modelan con inteligencia para tomar decisiones.
* Crear una propuesta para agilizar le elección de rutas Óptimas para el problema de'balanceo de tráfico en una red, es decir proponer un método que no se tenga tablas de estados y sea más ágil, ya que cuando estas crecen demasiado búsqueda de una ruta Óptima se retrasa.
* También se podrían crear aplicaciones reales para la mejora de seguridad en redes por medio del modelo de comunicación entre agentes intencionales.
82
Conclusiones y Trabajos Futuros ,
* Otro trabajo es crear un procedimiento de búsqueda inteligente el cual podría ser implementado al presente algoritmo para enfrentar el problema de redes demasiado grandes.
* Algunos casos de experimentación podrían ser en equipos que cuenten con estacion'es de trabajo, o diversos equipos con PC, estaciones de trabajo, y ambientes)de trabajo diversos como son los sistemas operativos.
11
5.3 PU BLlCAClO N ES
Se obtuvieron logros con el desarrollo del presente trabajo de tesis como fue una publicación en el 6to. Congreso Internacional de Investigación en Ciencias Computacionales (CiiCC'99).
Se obtuvieron logros con el desarrollo del presente trabajo de tesis como fue una publicación en Congreso Internacional de Computación (ClC'99).
,I 5.4 LECCIONES APRENDIDAS
Durante el desarrollo del presente trabajo de tesis, realice diversas actividades que me han formado profesionalmente, entre las más importantes son las siguientes:
o:* Desarrolle habilidad para recopilar información sobre un tema nuevo, ya que el tema elegido ,en esta tesis, carecía de información sobre sus métodos, usos, implahtaciones y manejo.
*:* Los agentes se deben estudiar tomando en cuenta al especialista que se 'intenta simular, esthdiar detenidamente cuales son los factores que iritervienen en su toma de decisiones y que información es fundamental en su desempeíio.
I
e:* Los agentes son una buena herramienta para sistemas cambiantes en el tiempo, al generar cdnstantes soluciones a sus problemas, los hacer 'ser
03 Se aporto material nuevo en la incursión de un área, como son los sistemas multiagentes, que comienzan a tomar fuerza en aplicaciones, y que no se había trabajado en este tema, aportando un estado del arte en
40 Un tema muy valioso y que en lo personal muy complicado, es el hacer un modelo matemático,, porque se tienen que estudiar formalismos matemáticos, entenderlos y después poder aplicarlos correctamente.
dinámicos. 'I(.
esta área de investigación. 'I
I1
83
Conclusiones y Trabajos Futuros
Además de entender la relación con sistemas compuestos por computadoras y como afectarán su comportamiento.
03 Por último fue muy interesante estudiar la comunicación con un punto de vista filosófico, y entender todos los factores que intervienen en ella, por eso es que es una herramienta importante en toda sociedad.
5.5 A P O RTAC I O N ES
AI desarrollar el presente trabajo se aportaron varios aspectos importantes para el área de sistemas multiagentes como: .i ,
03 Se presenta una introducción al paradigma orientado a agentes, un estado del arte sobre el tema de comunicación presentado en el capítulo 2, donde se establece de manera especifica que él lo que se obtendrá con este trabajo.
0:. También se aporta una investigación hacia el estudio de lógicas para la representación de sistemas continuos en el tiempo capítulo’3.
*:e Una de las aportaciones más importantes es el desarrollo de un modelo matemático que se presenta en el capítulo 3, presentando los formalismos que avalan el presente modelo.
03 Con el presente trabajo no se buscaba presentar una teoría mas para programar agentes, sino que se pretende comprobar que este nuevo paradigma de programación funciona por lo que se hizo una simulación donde se ve cómo pueden ser representados en términos computacionales las características de los agentes. Se presenta la forma de abordar un problema, diseñarlo e implantarlo de tal forma que cumpla con el concepto de agente (autonomía).
e:* AI crear la simulación se hicieron aportaciones también .presentado una 1 nueva alternativa para balancear el tráfico de redes, utilizando agentes. En
este trabajo sólo se presenta la simulación y por medio de los resultados se observó que efectivamente, el programa trata de equilibrar los envíos de información entre todos los nodos que conformen la red.
5.6 BENEFICIOS OBTENIDOS
AI inicio de este trabajo en la sección 1.6 se plantearon algunos beneficios y alcances, que se pretendería alcanzar con el presente trabajo, por lo que en está sección los retomamos para comentar como se lograron cada uno de ellos, y se presentan a continuación:
84
Conclusiones y Trabajos Futuros
A) Crear soluciones actuales con respecto ai medio ambiente, dentro de la sección 4.4, presentambs una aplicación del modelo propuesto y describimos en que moment0 un sistema pasa de ser un simple algoritmo, a un algoritmo se comporta de acuerdo a como su medio lo solicita.
AI agregar características de autonomía en un sistema multiagente, obliga a programar al agente a tener control sobre sus acciones, y conocimiento acerca de lo que están desarrollando, hace que los sistemas de este tipo estén cambiando continuamente de acuerdo a como lo requiera el medio, y eso es lo que se explica en este tema de tesis.
B) Otro beneficio es los cambios de acciones de acuerdo al medio en que trabajen, esta tesis muestra cómo son tomados los datos y cómo va cambiando para que el programa, llamado agentes, evolucione con el medio. Es decir no va a cambiar su estructura de funcionamiento tal vez dependiendo de los requerimientos cada agente tiene programas para responder adecuadamente, y es algo nuevo en este tipo de trabajos. Sección 4.5
C) Aplicaciones diversas 'bel modelo, para este trabajo solamente se presenta una aplicación, ya que el tiempo para desarrollar un fundamento matemático es extenso, pero al explicar el modelo y entender su funcionamiento, se puede crear distintas aplicac/ones distribuidas en problemas semejantes de '' comunicación que cambia continuamente.
D) Definición de dominios donde se aplique el modelo, con este punto se pretende que el lector a l aplicar el modelo, comprenda cuáles son. los puntos criticos de su aplicación, para de esta forma poder crear una semántica adecuada a cada problema, y simplificar el trabajo descubriendo las funciones que manipularán está información. Sección 3.7
E) Rediicción de análisis para cambios de estado en la red, en la sección 4.10 se muestran las pantallas de resultados y observamos que la primera pantalla es como una foto del sistema un momento antes de que comiencen a trabajar los agentes, en las pantallas posteriores se observa como los. tiempos tienc;en a ser más uniformes, por lo que este se cubre con está prueba. Pero faltan algunas pruebas más del sistema en diversas situaciones, para afirmar que !os tiempos fueron reducidos.
~
':
I1
!
~
F) Redwxión de tiempo en envíos de mensajes, este punto abarca algo muy impcrtante y que a todos los desarrollares de software nos interesa, el ahorrar tiempo tanto el desarrollo como para el mantenimiento. AI crear sistemas con el paradigma orientado a agentes delimitamos el problema, de tal forma que se debe desarrollar un 'I sólo programa que conviva con otros programas iguales pero no necesite de ellos para trabajar, tal esto suene iun poco complicado pero no lo es tanto cuando uno se apega a una metodología, como la presentada en este trabajo. Sección 4.5.10
a5
Conclusiones y Trabajos Futuros
. 1, . . . . .i . .
86
Apéndice A
APENDICE A
COüiGO FUENTE FUNCIÓN ALLINFOPANEL.JAVA
import javax.swing.'; o
O llimport com.sun.java.swing.'; 0 import javax.swing.JPane1; o import java.awt:; o import java.awi.event.'; o
o I1 Esta clase genera el panel para agregar los nodos de la red
.ALL ="enter$ ALL = "clear al?;
static JButton accept-ail; static JButton clear-all; static JTexiField allNameField; static JTexiArea allArea; static JScrollPane allScrollPane; public AiiinfoPanei() (
II
add(allNameLabel); I(
setLayout(nul1); allNameLabel = new JLabel("N0mbre"t
allNameField = new JTexiField(l5); add(allNameField); accept-ail = new JButton("Aceptai"); ' accept-all.setActionCommand(ENTER~ALL);
add(accept-all ); clear-all = new JButton("Limpia?); clear-all.setActionCommand(CLEAR-ALL);
add(clear-all); allArea = new JTexIAreaO: aliArea.setEditable(false); allScrollPane = new JScrollPane(allAre~);
accept-all.addActionListener(this);
clear-all.addActionListener(this);
1:
allScrollPane.setVerticalScrollBarPol~cvfJScrollPane.VERT CA._SCRO.LBAR-ALWAVS) " I
a lscrol Pane setPrefeneoS ze(ner D.mension(100. 80));
add(allScroliPane); allArea.setTexi(""):
allNameLabel.setBounds(l0 + insets.leR, 10 +
aliNameFieId..set8ounds(l50 + insets.left. 10 +
Insets insets = getlnsets(); ./I
insets.top.100. 20);
insets.top.200, 20);
accept-all.setEounds(25 + insets.leR, 50 + clear-ali.setBounds(265+ insets.leR, 50 +
allScrollPane.setBounds(95 + insets.left. 130 +
insets.top.1 OO. 20);
insets.top.1 OO. 20);
insets.top,lOO, 80);
public void actionPerformed(ActionEvent e) ( NetState netstate = new Netstate(); String command = e.getActionCommand0: String name = new String(); String addr = new String(); String newline =
System.getProperiy("line.separator); if (command == CLEAR-ALL) (
allNameField.setText(""): 1 if (command == ENTER-ALL) (
try (
allNameField.getText();
name.compareTo("OK) = = O 1 1 name.compareTorERR0R) == O)
name =
if(name.length(i 1 1 1
(
allNameField.setTexi("ERROR);
else (
if(netState.getAlllndex(name) == -1) (
allNameField.setText("OIC');
newline); allArea.append(name +
netState.addAll(name);
SelectionPanel.nodeList.addElement(name); SelectionPanel.linkOneList.addElement(name); SelectionPanel.linkTwoList.addElement(name);
I else (
allNameField.setText~REPETlü0); ) )
catch (NullPointerException npe) ( allNameField.setText("ERR0R NPE);
)
llimport javax.swing.'; O import javax.swing.JPane1; o import com.sun.java.swing.'; o import java.awt.'; o import java.awt.event.*; o ii Esta clase genera el panel para presentar los datos no o ii graficamente. dado que no se logro imprimir los //costos de cada linea en el dibujo
public class PathPanel extends JPanel ( static JLabel titulo; static JTextArea pathArea;
87
Apéndice A
static JScrollPane pathScrollPane; public Pathpanelo (
setLayout(nu1i); " titulo = new JLabel("Trayect0rias"); add(titul0); ' , '
pathArea =new JTextAreaO; pathArea.setEditable(false); pathScroilPane = new JScroiiPane(pathArea);
patnScroliPane setVerticalScro IBarPo icyi.Scroi Pane VE RT CA-_SCRO--BAR-A.iNAYS).
painScro Pane setpreferreas ze(nen Dimens on(400 200)).
add(pathScrollPane), DathArea setTextYi. insets insets = g i t i ke tso ; titulo.setBounds(250 + insets.lefl. 1 O + insets.top,l O0
pathScroliPane.setBounds(l00 + insets.ieft, 40 + 20);
insets.top.400, 200); 1
1 import javax.swing.JPane1; o import java.awi:: O import java.awt.event.'; O iiimport javaxswing:;
import com.sun.java.swing.';
il Esta clase genera el dibujo grafico de la red class Shapepanel extends JPanel(
Font.PLAIN, 20);
~.
final static Font font = new Font("Monospaced,
final static String NAME ="name"; final static String OVAL = "ovalll; final static String LINE ="line"; static String[] shapes = new String[lOO]; static String1 names = new String[iOO]; static int[] parl = new int[100]; static int[] par2 = new int[lOO]; static int[] par3 = new int[lOO]; static int[] par4 = new int[100]; static int index = O; . . . public ShapePanei()(
1
setBackground(Color.white); setForeground(Color.black);
repainto; public void rendershape() (
1 pJb..c void aodhoae(int p l , in1 p2 mt p3) (
snapes[inaex] = OVAL parl [index] = p l ; parí>[index] = p2; par3[indexl = p3; index++;
I pub c .o d add- ne, ni p l nt p2 in1 p3 n i p4, (
snapes[index] = .NE parl[index] = p l ; pari[index] = p2; par3IindexI = p3; par4[index] = p4; index++;
1 public void addName(String name, int Y, int y) (
shapes[index] = NAME: parl[index] = x: paR[index] = y ; names[index] =name; index++;
1 public void paintcomponent (Graphics g) (
super.paintComponent(g); inti; g.setFont(font); g.setColor(Coior.biack); for(¡ = O ; icindex; i++) (
if(shapes[i] == OVAL)
if(shapes[i] == LINE)
if(shapes[i] == NAME)
g.drawOvai(par1 [I], par2[i], par3[i], pargi]);
g.drawLine(parl[i], paR[i], par3[i], par4[i]);
g.drawString(names[i], parl [i], par2[i]); . . I
1 I
iiimport javax.swing.';
import javax.swing.JPanel; O import com.sun.java.swing.'; 0 . import java.awi.'; import java.awt.event.'; //Esta clase genera el panel para dar la entrada de datos I/ del dibujo de la red, y para mandar paquetes public das5 SelectionPanel extends JPanel implements ActionListener (
static final String DRAW = "draw; static final String LINK = "IinK; static final String START = "staf; static final String SEND = "send"; Static JList node; static DefaultListModel nodeList = new
DefaultListModel(); - static JList linkone: static DefaultListModel IinkOneList = new
DefauitListModel(), static JList IinkTwo; Static DefaultListModel iinkTwoList = new
static JList xPosition; static DefaultListModel xPositionList = new
static JList yPosition; static DefaultListModei yPositionList = new
static JLabel nodelabel: Static JLabel xLabel; static JLabel yLabel; static JLabel one; static JLabel two; static JButton draw; static JButton link: static JButton start; static String[][] position = new String[4][4]; Static JScroliPane twoScrollPane; public SelectionPanelO (
DefaultListModel();
DefaultListModel();
DefaultListModel();
setLayout(nui1); nodeLabel = new JLabelcNodo"); add(n0deLabei); xLabel = new JLabel("Coiumna"); add(xLabei);
aa
Apéndice A'
yLabel = new JLabel("Reng1on"); add(yLabe1); node = new JList(n0deList); I¡:
node.setSelectionMode(ListSelectionModel.SlNGLE-sELE CTION);
node.setSelectedlndex(0); JScrollPane nodeScrollPane = new
add(nodeScrollPane1: JScrollPane(node): I/.
xPosition = new JLisiixPositionList); xPosition.setSelectionMode(LlstSelectionModel.
xPosition.setSelectedlndex(0l: SINGLE-SELECTION):
JScrollPane xScrollPane = &J
add(xScrol1Pane); yPosition = new JList(yPos1tionList); yPosition.setSelectionMode(ListSelectionM0del.
yPosition.setSelectedIndex(0); JScrollPane yScrollPane =new
JScrollPane(xPosition):
SINGLE-SELECTION);
JScrollPane(yP0sition); add(yScr0llPane): 1)
draw = new Jüutton("Dibuja"); draw.setActionCommand(DRAW);
draw.addActionListener(this); addidraw):
one = new JLabelrNodo 1"); add(one); linkone = new JList(link0neList);
linkOne.setSelectionMode(ListSelectionModel.Sl NGLE SELECTION): -
linkOne.setSelectedlndex(0); fl JScrollPane oneScrollPane = new
add(oneScr0llPane); JScrollPane(link0ne);
two = new JLabelrNodo 2"); add(two); II
IinkTwo = new JList(linkTw0Listj; linkTwo.setSelectionMode(ListSelectionModel.Sl
linkTwo.setSelectedlndex(0); ¡ iwoScrollPane = new JScrollPane(linkTw0);
NGLE-SELECTION);
add(twoScr0llPane); iu
link = new JBuiton("Unii"); iink.setActionCommand(LlNK)
link.addActionListener(this); add(link); I,
stati = new Jüutton("lniciai"); start.setActionCommand(START):
start.addActionListener(this); : add(start); Insets insets = getlnsetso; nodeLabei.setüounds(l0 + insets.left, 10 +
xLabel.setüounds(70 + insets.lefl, 10 +
yLabel.selüounds(l30 + insels.left, 1 O +
insets.top.60, 20);
insets.top,60. 20);
insets.top.60, 20); !I nodeScrollPane.setüounds(l0 + insets.lefi, 40 +
xScrollPane.setüounds(70 + insetdeft, 40 +
yScrollPane.setüounds(130 + insets.len, 40 +
draw.setfiounds(l90 + insets.lefl, 50 + insets.top.75,
one.setüounds(l0 + insets.left, 130 + insets.top,'lO,
insets.top.50, 80);
insets.top.50. 80): #t.
insets.top.50, 80); 1,
30);
20); /I
two.setBounds(90 + insets.left 130 + insets.top.70,
oneScrollPane.setüounds(l0 + insets.left, 160 +
twoScrollPane.setüounds(90 + insets.left. 160 +
link.setüounds(170 + insets.left. 160 + insets.top.85,
start.setüounds(l70 + insets.len, 200 + insets,top,85,
~
20);
insets.top,50. 80);
insets.top.50, 80):
30);
30); inti, j; for(i.0; ic4; lb+) (
for(j.0; j<4; j++) ( positionh][i] = null;
) I
xPositionList.addElementr1"); xPosnionList.addElemenl("2"); xPositionList.addElement("3"); xPositionList.addElementr4); yPositionList.addElementr1"): yPositionList.addElement("2); yPositionList.addElement("3"); yPositionList.addElementr4);
public void actionPerformed(ActionEvent e ) ( NetState netstate = new Netstate();
String command = e.getActionCommand(); String name = new String(); String addr = new String(); String first = new String(); String second = new String(); int x, y, x2. y2, a=O, b=O; int size = 25; inti, j; Shape shape; String newline = System.getPropettypw.separator"); if (command == DRAW) (
I
try ( i = node.getSelectedlndex(); name .= node.getSeiectedVaiue().toString(): x = xPosition.getSelectedIndex(); y = yPosition.getSelectedlndex(); if(position[y][x]==null) (
position[y][x]=name; x=lO+(x'70); y=10+(yf70) ; NetworkAgentGUI.drawing.addNode(x, y, size); x = x + 7 : y = y + 20; NetworkAgentGUI.drawing.addName(name, Y, y); NetworkAgentGUI.drawing.renderShape(); I nodeList.removeElemeniAt(i);
)catch (NullPointerException npe) () 1
if (command == LINK) (
first = linkOne.getSelectedValue().toString(); second = linkTwo.getSelectedValue().toString(); if(first.compareTo(second) != O)
1
try (
for(i.0; ic4; i++) ( for(i=ü; jc4; I++) (
if(position~](i] != null) ( if(first.~ompareTo(position0l[il) == O) (
1
a=¡: b=j'
1 1
89
Apéndice A
1 x = 1 O + (a'70); y = 10 + (b'70); for(¡-0; ic4;'i++) (
for(i=o; jc4; j++) ( if(position0][i] I= null)
if(second.compareTo(position~][i]) == a=¡; b=j;
) 1
x2 = 10 + (a'70); y2 = 10 + (b.70); iflX > X2)
x2 = x2 + 25;
x = x + 25; if(X c X2)
if(X == X2) ( x = x + 1 3 ; x 2 = x 2 + t 3 :
1 if& ' Y2)
y2 = y2 i 25; if(V c Y21
y = y + 25; if(Y == y2) (
y = y + 13; y 2 = y2 i 13;
I
Networl<AgentGUi.drawing.addLine(x, y, x2. y2); Networl<AgentGUI.drawing.renderShape();
1 )catch (NullPointerException npe) ()
1 if (command == START) (
Networl<AgentGUl.selectionPanei.one.setTexi("Origen");
Networl<AgentGUl.selectionPanel.two.setText("Destino"); . , .
int fin = linkOneList.getSize(); for(i.0; icfin; i++)
if(netState.getLocalNameO.compareTo(link0neList.elemen tAt(i).toString()) ! = O ) ( , ,
linkOneList.removeElementAt(i);
fin-; .
)
fin = linkTwoList.getSize(); for(i.0; iciin: I++) ( .
if(netState.getLocaIName().compareTo(linkTwoList.eleBen tAt(i).toString()) ==O) (
linkTwoList.removeElementAt(i); I-; fin--;
1 link.setText("Mandaf'); link.setActionCommand(SEND); new Thread(new Networl<Agentlnput()).start();
Networl<AgentGUl.hello(); whiie(!netState.heiioDone()) () new Thread(new NetworkAgentOutput()).start();
//El hello representa una de las intenciones del Agente
11 Las siguientes dos llamadas tambien son intenciones, una para medir
I1 el costo de la linea, el otro para mandar los paquetes de estado
new Thread(new EchoTimer()).start(); new Thread(new LinkState()).start(); while(!netState.firstUpdate()) ()
) if(command == SEND) (
try ( second = llnkTwo.getSelectedValue().toString(); NetworkAgentGUI.mandaFile(second);
)catch (NullPointerException npe) () 1
) 1 //import javax.swing:;
import javax.swing.JPanel; O import com.sun.java.swing.'; o ,. import java.awt.'; o import java.awt.event.'; O /I Esta clase genera el panel para presentar los datos no o I/ graficamente, dado que no se logro imprimir los o il costos de cada linea en el dibujo public class NoGraphPanel extends JPanel (
static JLabel titulo; static JTextArea resultArea; static JScroliPane resuiiScrollPane; public NoGraphPanelO (
set Layout(nul1); titulo =new JLabei("Resu1tados"); add(titul0); resuRArea = new JTexiAreaO; resultArea.setEditable(false); resultScrollPane = new JScrollPane(resu1tArea);
resultScrollPane.setVerticalScrollBarPoiicy(JScrollPane.VE RTICAL-SCROLLBAR-ALWAYS);
resultScrollPane.setPreferredSize(new Dimension(400,
add(resultScro1lPane); resultArea .setTexi(); Insets insets = getlnsets(); titulo.setBounds(250 + insets.lefl, 10 + insets.top,lOO,
200));
201' -~ , , resultScrollPane.setBounds(lO0 + insets.iefl. 40 +
insets.top,400. 200);
public void updateResult() (, NetState netstate = new Netstate(); inti, j ; String Salida = new String(); String source = new String(); String target = new String(); String newline =new
String tab = new String("\t"); if(netState.getAIiMax() > O) (
String(System.getProperly("line,sFparator));
salida =salida +tab; fOr(i=O; icnetState.getAIIMax(); i++)
salida =salida + netState.getAIIName(i) +tab; salida = salida + newline; for(i=O; icnetState.getAIIMax(); i++) (
source = netState.getAIIName(i):
90
Apéndice A
Salida = salida +source + tab; fOr(jZ0; jcnetState.getAiIMax(); j++) (
target = netState.getAIName(i):
public void windowCiosing(WindowEvent e) ( System.exit(0); I I\. I I , , salida = salida + ietState.get%e(source, target) frame.getContentPane()add(new
+tab; NetworkAgentGUI(),BorderLayout.CENTER); ) frame.setSize(600, 320); salida =salida + newiine; frame.setVisible(true);
1 resultArea.setText(salida); new Thread(new ResultUpdate()).start();
/I I/ Se inicia el hilo que presenta los resultados no graficos "
1
import javax.swing.JPane1; o //import javax.swing.'; o import com.sun.java.swing.': o I1
import java.awt.': o import java.awt.event.'; o l 11 Esta clase es el archivo ejecutable, el cual crea la
I1 interfaz grafica e inicializa al agente
public class NetworkAgentGUI extends JPanel (
I/ static LocallnfoPanel locallnfo; static NeighborlnfoPanel neighborlnfo; static AlllnfoPanel alllnfo; static SelectionPanel selectionPanel; ' ,
static Shapepanel drawing; static NoGraphPanel noGraph;
public NetworkAgentGUIO ( 11 Se genera un panel con pestañas
JTabbedPaneO;
static Pathpanel pathpanel; il
JTabbedPane tabbedpane = new
locallnfo = new LocalinfoPanel(): tabbedPane.addTab("Local", locallnfá); tabbedPane.setSelectedlndex(0); neighborlnfo = new NeighborlnfoPanel(); tabbedPane.addTab("Vecinos", neighborlnfo); alllnfo = new AllinfoPanel(); tabbedPane.addTab("Red, aillnfo); '1 Component netinfo = netinfopanel(); l. tabbedPane.addTab("Simulacion", netlnfo); noGraph = new NoGraphPanel(); tabbedPane.addTab("Resultados". noGraph): pathpanel = new Pathpanel(); tabbedPane.addTab("Trayectorias", pathpanel); setLayout(new GridLayout(1,I)); add(tabbedPane):
protected Component netlnfoPanel() ( JPanel panel = new JPanelO; panel.setLayout(new GridLayout(l,Z))f Comoonent selection: seleCt on = new select onpanelo pane a00,s.e ecr on). drarving = new ShapePanelg
,I/ panel.add(drawing); return panel;
) public static void main(String[] args) (
writefile(); JFrame frame = new JFrame("NetworkAgenY'); frame.addWindowListener(new WindowAdapter() (
it Esta fUnCiOn genera el archivo de pruebas a mandar public Static void wiReFile() (
inti, j ; try (
File outputFile = new File('Yest.txt"); Filewriter out = new FiieWriter(outputFi1e); String testString =new String(); int c; for(j=O; j400; j++) (
teststring = "Archivo de pruebas " + j + "\n" for(i=O; ictestString.length(); i++) (
c = (int)testString.charAt(i); out.write(c);
) out.close();
I ! catch (IOException ioe) (
System.err.println("Enor en la creacion del archivo
System.exit(9); de prueba");
I I1 Este metodo manda los paquetes HELLO a cada vecino
public static void hello0 ( NetState netstate = new Netstate(); int a; String msg =new String(); String target = new String(); netState.freeAll(); for(a.0; acnetState.getNeighborMax(); a++)(
msg ='"A-HELLO; target=netState.getNeighborAddr(a); new Thread(new AgentOutPort(target, msg)).start(); ,
1 I
11 Este metodo manda el archivo de pruebas il public Static void mandaFile(String target) (
NetState netstate = new Netstate(); Shortpath shortpath = new Shortpatho; String msg = new String(); String mensaje = new String(); String tmp = new String(); I1
String[] path = new stringpa]; String local = new String(); String printout = new String(); intj; local = netState.getLocalName(); try (
FileReader input = new FileReader('Yest.txt"); BufferedReader in = new BufferedReader(input); msg = in.readLine();
while(msg !=null) (
11 Se genera el paquete, con el formato /I localldestinolpath(separado por comas),!datos
mensaje = new String(); path = shortPath.getPath(loca1, target);
printout = "Mandando a " + target + " via: "; j = o '
do (
91
Apéndice A
printout = printout + pathD] + " "; mensaje = mensaje + pathu] + ","; j++;
)while (pathu] I= null); printout = printout + "W; PathPanel.pathArea.append(printout); msg = mensaje +"I" + msg; msg = local + "I" +target + "I" + msg;
netState.queue[netState.getNeighborlndex(path[l ])].addEl ement(msg);
) input.close();
msg = in.readLine():
)
System.err.println("l0Exception error\n"); 1
catch (IOException ioe) (
1 1 //import javax.swing.'; U import com.sun.java.swing.*; G import javax.swing.JPane1; U import java.awt:; o import java.awt.event:; U /I Esta clase genera el panel donde se agrega la informacion O //sobre el nodo local G public class LocalinfoPanel extends JPanel implements ActionListener (
static Rnal String ENTER-LOCAL = "enter-local":
static final String VIEW-LOCAL = "view-local"; static final String CLEAR-LOCAL = "clear-local"; static JLabel IocalNameLabel; static JLabel IocalAddrLabel; Static JEuiton accept-local; static JEutton view-local; static JEuiion clear-local; static JTextField IocalNameFieid; static JTextField IocalAddrField; public LocalinfoPanel() (
setLayout(null); IocalNameLabel = new
addilocalNameLabeli: JLabelrNombre");
IocalNameField = new JTextField(l5), add(localNameField), IocalAddrLabel = new
add(localAddrL%bel); IocalAddrField = new JTextField(l5); add(l0calAddrField); accept-local = new JüuttonrAceptar);
accept-locai.setActionCommand(ENTER-LOCA
JLabeir Direccion");
LJ; accept~iocai.addActionListener(this); add(accept-local ): view-local = new
Jüunon("Despiegar);
view-iocai.setActionCommand(ViEW-LOCAL); view iocal.addActionListeneríthisi: add(view-local ), clear-local = new Jñuiton("Limpiar),
clear-locai.setActionCommand(CLEAR_ LOCAL) clear-local.addActionListener(this):
add(clear-local); Insets insets = getlnsets(); IocalNameLabel.SetEounds(l0 + insets.left 10 + insets.top, 100, 20); localNameField.setEoundsil50 + 'insets.leñ. 10 4 insets.top, 200, 20); localAddrLabel.setüounds(l0 + insets.lefl. 50 + insets.top, 100, 20); localAddrField.setüounds(l50 + insets.left. 50 + insets.top, 200, 20); accept-local.setñounds(25 + insets.left 90 + insets.top. 100, 20); view-local.setEounds(145 + insets.lefi, 90 + insets.top, 100, 20); clear-local.setEounds(265 + insets.leñ, 90 + insets.top, 100, 20); public void actionPerformed(Acti0nEvent e) NeiState netstate = new Netstate(): e.getActionCommand(); String,name = new String(); String addr = new String(); System.getProperty("line.separator); if (command == CLEAR-LOCAL) ( localNameField.setText(); localAddrField.setTextYi: i if [command == VIEW-LOCAL) ( localNameField.setTexi(netState.getLocalName()): localAddrField.setText(netState.getLocalAddr()); if (command == ENTER-LOCAL) try ( name = iocalNameField.getTexi(): addr = localAddrFieid.getText(); if(name.length() c 1 1 1 name.compareTo("0K) = = O II name.compareTo("ERR0R) = = O 1 1 addr.lengih() 1 1 1 addr.compareTo('OK) ==O 1 1 addr.compareTorERROR) ==O) ( localNameField.setText~ERROR); localAddrField.setText('ERROR); ) else ( iocalNameField.setTextt("OK"); localAddrField.setText("OK); netState.local(name. addr); AlllnfoPanel.allArea.append(name + newline); SelectionPanei.nodeList.addEiement(name); SelectionPanel.linkOneList.addElement(name);
catch (NullPointerException npe) ( iocalNameField.setTextrERROR NPE); localAddrField.setTextrERROR NPE); ] ) ))
//import javax.swing:; o import javax.swing.JPane1; a import com.sun.java.swing.'; o import java.awt.'; o import java.awt.event.'; o I/ Esta clase genera el panel de informacion sobre los vecinos public class NeighborlnfoPanel extends JPanel implements ActionListener i
String command =
String newline =
SelectionPanel.linkTwoList.addElement(name); )
static'finai string ENTER-NEIGHBOR = "enter-neighbor;
Static m a l String CCEAR NEIGHBOR = - "clear-neighbor;
Static JLabel neighborAddrLabel; static JEunon accept-neighbor;
92
Apéndice A
static JButton clear-neighbor;) Static JTextField neighborAddrField; Static JTexiArea neighborArea; static JScrollPane neighborScrollPane; public NeighborlnfoPanel() [ I(!
~etLavoutlnulli: I I ,,
neighborAddrLabei = new JLabel("Direccion"),
add(neighborAddrLabe1) neighborAddrField ='new
add(neighb0rAddrField). accept-neighbor = new
JTextFieid(15).
JButton("Aceptar),
accept-neighbor.setActionCommand(ENTER-N EIGHBOR):
accept-neighbor.addActionListener(this): add(accept-neighbor ); clear-neighbor = new
il JButton("Limpiar");
clear-neighbor.setActionCommand(CLEAR_"l
clear-neighbor.addActionListener(this); add(ciear-neighbor); neighborArea = new JTextAreaO; neighborArea.setEddable(false); neighborScrollPane = new,
neighborScrollPane.setVerticalScrollBarPolicy(
GHBOR);
JScrollPane(neighb0rArea);
JScrollPane.VERTICAL-SCROLLBAR-ALWAY SI;
neighborScrollPane.setPreferredSize(new Dimension(200, 60));
add(neighborScr0iiPane); neighborArea.setText(""); Insets insets = getlnsetso; neiahborAddrLabel.setBoundsll0 +
~~~~ ~~ ~~
insets.left 10 + insets.tOp, 100,20);
insets.ieli, 10 + insets.top, 200, 20); neighborAddrField.setBounds(150 +
acceDt neiqhbor.setBounds(25 + . - - insets.leii, 50 + insets.top, 100, 20);
insets.leii. 50 + insets.top, 100,20);
insets.left 130 + insets.top, 200,ao);
clear-neighbor.setBounds(265+
neighborScroliPane.setBounds(95 +
1 public void actionPerformed(ActionEvent e) (
NetState netstate = new NetStateO: String command =
String name = new String(); String addr = new String(); String newline =
if (command == CLEAR-NEIGHBOR) (
,I e.getActionCommand();
System.getProperty("line.separator");
neighborAddrField.setText(); 1 11
if (command == ENTER-NEIGHBOR)
try ( addr = neighborAddrField.getText();
if(addr.length() < 1 11 addr.compareTo("OlC') == O11 addr.compareTo("ERR0R)
neighborAddrField.setTextcERR0R); ) else ( if(netState.getNeighborindexByAddr(addr) ''
== -1) [ neighborAddrField.setTexicOK'); neighborArea.append(addr + newline); netState.addNeighbor(addr); ) else (
) )catch (NuliPointerException npe) ( neighborAddrFieid.setText("ERROR NPE);
==o) (
neighborAddrField.setText("REPETlD0); )
) 1
)
import java.net.';
o import java.io.';
O
O I / Esta clase abre el lector y el escritor para los sockets
o
o public class SocketUtil(
o
O public static BufferedReader getBufferedReader
u (Sockets) throws IOException
return(new BufferedReadN
new InputStreamReader(
s.getlnputStream()))),
)
public static Printwider getPrintWriter(S0cket 5 )
throws IOException (
return(new PrintWriter(s.getOutputStream(). true));
)
import java.lang.';
O import java.io::
o
93
Apéndice A
import java uti1 *,
U
o 11 Esta clase encuentra la ruta mas corta entre dos servidores
O 11 utilizando el algoritmo Dqkstra
O
O public class ShortPath (
protected int[] hosts = new int[30];
protected String[] names =new String[30];
protected int[]U delays = new int[30][30];
il Este metodo es el que funciona como interfaz de la clase
I1 para ser accezado por otros objetos
public String[] getPath(String src. String tgt)
NetState netstate = new Netstate();
int s, t;
this.update();
for@ = O; sc30; si+)
names[s] = null;
s = netState.getAlllndex(src);
t = netState.geiAlllndex(tgt);
this.findPath(s, 1);
this.convert();
return names;
1
11 Este metodo obtiene la tabla de estado mas reciente
protected void update() (
NetState netstate = new Netstate();
int max. i, j;
Strings = new String();
String t = new String();
max = netState.getAIIMax0;
for(¡=(]; iemax; I++) (
s = netState.getAIIName(i);
for(j=O; jcmax; j++) (
t = netState.getniiName(j);
delays[i][i] = netState.getTime(s, 1);
1
1
I1 Este metodo encuentra la ruta, utilizando el algoritmo
11 del libro de Tannenbaum. pero escrito en java
protected void findPath(int s, int t)
NetState netstate = new Netstate();
int[] predecessor = new int[8];
int[] length = new int[8]:
boolean[] label = new boolean[ü];
final int INF = 100000000;
inti, k. min;
int n=netState.getAIIMax()+1 ;
for (¡=O; i<n; i++)(
predecessor[i]=-I ; I
length[i]=INF;
label[i]=false;
1 iength[t]=o;
label[t]=true;
k=t;
do (
for (¡=O; icn; ¡++)
if (delays[kl[i]!=O 88 iabel[i]==faise)(
i f (length[k] + delays[k][i]clength[i])(
94
Apéndice A
predecessor(i]=k;
length[i]=length[k] + delays[k](i];
)
1 k=O;
min= INF;
for(i=O; i<n; i++) li
if (label[¡] == false 88 length[¡] < min)
min=lenglh[i];
k=p
I
label[k]=true;
)while (k!=s);
k=s;
for(¡-0; ¡<IO; I++)
hosts[¡] = -1 ;
i=0;
,
II do I
hosts[i++]=k;
k=predecessor[k];
)while (kr=O);
protected void convert0 (
NetState netstale = new NetStateO;
inti;
¡=O;
do (
names[i] = netState.getAIIName(hosts[i++]);
)while (hosts[i]>=O);
1
import java.lang::
o
o / I Esta clase actualiza los resultados no graficos
o
o public class ResuitUpdate implements Runnable (
private final long PERIODO = 100001;
private static long IastTime;
public void run() (
IastTime = Syjtem.currentTimeMiilis();
whiie(true) (
if(lastTime+PERIODO < System.currentTimeMillis())
NetworkAgentGUl.noGraph.updateResult();
IastTime = System.currentTimeMiIlis();
import java.net.';
o import java.io:;
o import java.util:;
o
O I / Esta clase maneja 10s hilos de los clientes, que funcionan
11 como salidas de io5 agentes
public class NetworkAgentOutput implements Runnable(
boolean endFlag =false;
public void forward() (
NetState netstate = new Netstate();
int i = O;
95
Apéndice A
String tgt = new String().
String msg = new string(),
for(i=O icnetstate getNeighborMax(). I++) (
if(netState.queue[i].isEmpty() == false) (
tgt = netState.getNeighborName(i);
msg = netState.queue[i].firstEiement().toString();
netState.queue[i].removeElementAt(O);
if(msg.compareTorNA-HELLO) != O)
, , .
. . while (netState.getLine(tgt) ==false) ()
new Thread(new AgentOutPort(tgt. msg)).start(); . . . .
if(endFiag)
break;
) while(true);
public void run() (
this.fonvard():
1 )
import java.net.*:
import java.io:;
import java.util:;
I/ Esta clase maneja los hilos de los servidores que funcionan
11 como entradas del Agente
public class NetworkAgentlnput implements Runnabie(
boolean endFlag =false,
public void listen() (
Serversocket listener = null:
NetState netstate = new NetStateO;
try (
listener = new ServerSocket(5555);
whiie(irue) (
11 Por cada vecino se abre un servidor
if(netState.getCon() c netState.getNeighborMax()) (
netState.incCon();
new Thread(new AgentlnPort(listener.accept())).start();
I
if(endFlag)
break;
iistener.close();
)catch (IOException ioe) (
System.out.printin~lOException: 'I + ioe);
ioe.printStackTrace();
)
)
public void run() (
this.listen();
)
import java.iang:;
o import java.net.';
import java.io.';
import java.util::
public class NetworkAgent (
public static void main(String[] args) (
96
.
writeFile();
localState();
pantallaMenu0;
public static void witeFile() (
inti, j:
try (
File outputFile = new File('test.txt");
Filewriter out = new FileWriter(0utputFiie);
String teststring = new String();
int c; II
for(j=O; jci00; j++) (
teststring = '"Archivo de pruebas '' + j + "\n";
for(i=O; i<testString.length(); i++) (
c = (int)testString.charAt(i);
out.wriie(c);
I
1
out.close();
)catch (IOException ioe) (
System.err.println("Error en la creacion del archivo de prueba");
System.exit(9);
I
public static void localState()
NetState netstate = new NetStateO;
Slring name = new String();
String addr = new String();
BufferedReader stdl? =
new BufferedReader(new InputStreamReader(System.in));
I/
I1
Apéndice A,
try (
System.out.println("\nConfiguracion del nodo locar);
System.out.printin("Nombre");
name = stdln.readLine();
System.out.println("Direccion");
addr = stdln.readLine();
netState.local(name, addr):
)catch (IOException ioe) (
System,err.printin("Error en la entrada de datos");
System.exit(1):
I 1
public static void pantallaMenu0 (
String select = new string();
BufferedReader stdln =
new BufferedReader(new InputStreamReader(System.in));
try (
System.out.println("\n[N]odos");
System.out.println("[Tjopologia"):
System.out.println("[S]ali~);
select = stdhreadLine0;
)catch (IOException ioe) (
System.err.println("Error de entrada de datos\n"):
System.exit(1):
1 if(select.compareTo("N") == O)
pantallaVecinos0;
else if(select.compareTo("T") == O)
pantallaTopologia();
else if(select.compareTo("S) == O)
System.exit(0);
else
97
Apéndice A
System.err.printlnrOpcion no valida");
pantallaMenu0:
public static void pantallaVecinos() (
NetState netstate = new Netstate();
String name = new String();
String addr = new String();
String select = new String();
BufferedReader stdln =
new BufferedReader(new InputStreamReader(System.in));
try (
System.out.println("Vecinos");
System.out.printlnr[C]reaf);
System.out.println("[E]Iiminaf);
System.out.println("[M]odificar);
System.out.println~[S]alif);
select = stdln.readLine();
if(seiect.compareTorC) == O) (
Cystem.out. println("Direccion");
addr = stdln.readLine();
netState.addNeighbor(addr);
) else if(select.compareTorE) = = O ) (
System.out.pnntln("Nombre");
name = stdln.readLine(); . ., . .
netState.delNeighbor(name);
) else if(select.compareTo("M") ==O) (
String newName = new String();
String newAddr = new String();
System.out.pnntln~Nombre"):
name = stdln.readLine(); .
System.out.println("Nombre nuevo");
newName = stdln.readtine():
System.out.println("Direccion nueva");
newAddr = stdln.readLine();
netState.modNeighbor(name. newName, newAddr);
)else if(select.compareTo("S) ==O) (
) else (
System.err.println("0pcion no validaw);
pantallaVecinos0;
1
pantallaMenu0;
)catch (IOException ioe) (
System.err.printlnrError de entrada de datos\n");
System.exit(1);
1
public static void pantailaTopologia() (
String select = new String(),
BufferedReader stdln =
new BufferedReader(new InputStreamReader(System in)),
try (
System.out.println("Topoiogia");
System.out.printlnr[M]odificar");
System.out.println("[l]niciaf);
System.out.println("[S]alif);
select = stdin.readLine(); . if (selecl.compareTorM) == o) (
pantallaNodos();
98
Apéndice A
)else if (select.compareTo("") == O) (
inicio();
) else if (select.cornpareTorS) =:,O)
pantallaMenu();
) else (
Systern.err.println("0pcion no validah");
pantallaTopologia0;
I!
)catch (IOException ioe) (
System.err.printlnrError de entraüa de datosb");
system.exit(1);
1 ) II
public static void pantallaNodos() ( I1
NetState netstate = new Netstate():
String name = new String();
String addr = new String();
String select = new String();
BufferedReader stdln =
new BufferedReader(new . InpuiStreamReader(System.in));
I1
try ( II
Systeni.oui.printin("Nodos");
Systero.out.printlnr[C]reaf);
System.out.println~[E]liminar); il
Syster~l.out.println~[M]odificaf);
Systern.out.printlnr[S]alif);
select = stdln.readLine(); :¡I
¡I if(select.compareTorC) == O)
Syst~?m.out.println~Nombre");
name = stdln.readLine();
netState.addAll(narne); 1)
I!
)else if(select.cornpareTorE) ==O) (
System.out.println("Nombre");
name = stdln.readLine0;
netState.delAll(narne); ,I
)else if(select.compareTorM) ==O) (
String newName = new String():
String newAddr = new String();
System.out.printin("Nombre");
name = stdln.readLine();
System.out.printlnC"ambre nuevo");
newNarne = stdln.readLine();
netState.modAll(name, newName):
)else if(select.compareTorS) ==O) (
) else (
System.en.printlnrOpcion no validah");
pantaliaNodos();
)
pantallaTopologia();
)catch (IOException ioe) (
System.err.printlnrError de entrada de datos\n");
System.exit(1);
)
public static void inicio() (
NetState netstate = new Netstate();
int a;
boolean flag = false;
String select = new String();
BufferedReader stdln =
99
Apéndice A
I
new BufferedReader(new lnputStreamReader(System.in));
new Thread(new NetworkAgentlnput()).start():
11 El hello representa una, de las intenciones del Agente
hello();
while(!netState.helloDone()) )
new Thread(new NeiworhAgentOutput()).start();
//Las siguientes dos llamadas tambien son intenciones, una para medir
11 el costo de la linea, el otro para mandar los paquetes de estado
new Thread(new EchoTimerO) start(),
new Thread(new Linkstate()) start().
whi!e(!netState.firstüpdate()) O
do (
try (
System.out. println("Simulacion");
system.out.printin('[M]anda~);
System.out.println("[S]ali~);
select = stdln.readLine0;
if (select,compareTorM) ==O) (
String name = new String();
System.out.printin("Destin0");
name = stdln.readLine0:
mandaFile(name):
)else if(select.compareTo('S) == O)
flag =true;
else
System err println("0pcion no valida\n"),
)catch (IOException ioe)
System err println('Error de entrada de datosin"),
System.exit(1);
1 while (iflag);
System.exit(0);
1
protected static void hello() (
NetState netstate = new Netstate();
int a; 'I
String msg = new String();
String target = new String();
netState.freeAllO:
for(a=O: a<netState.getNeighborMax(); a++)(
msg ='"A-HELLO;
target=netState.getNeighborAddr(a);
new Thread(new AgentOutPort(target, msg)).start();
1
1
public static void mandaFile(String target)
NetState netstate = new NetStateO; ,
Shortpath shortpath = new Shortpatho;
String msg = new String();
String mensaje = new StringO;
String tmp = new String();
String[] path = new String[30];
String local = new StringO;
int j ;
local = netstate getLocalName0,
try i FileReader input = new FileReaderrtest t c ) ,
BufferedReader in
= new BufferedReader(1nput).
msg = in readline().
1 O0
. Apéndice A
while(msg != null) (
mensaje = new String();
path = shortPath.getPath(locai, target);
j = O; ii.
do (
mensaje = mensaje + path11 + ",";
j t t ;
)while (path11 != null);
msg = mensaje + "!" + msg;
msg = local + "!" +target + ' 'Y + ,msg;
netState.queue[netState.getNeighborlndex(path[i])l.addEl ement(msg);
msg = in.readLine();
1 input.close();
)catch (IOException ioe)
System.en.println("l0Exception error\n");
1
import java.iang.';
o import java.io:;
o import java.iitil:;
O
0 it Esta clase tiene los conocimientos del Agente
0
O public class NetState
o . I
o / I Conocimientos
G protected static String IocalName =new String();
protected static String IocaiAddr = new String();
protected static int iocalsec = O;
protected static String[] neighborName = new String[30]:
protected static String[] neighborAddr = new String[301;
public static Vector[] queue = new Vector[30];
protected static booleanu IineFree = new boolean[30];
protected static long[] startTime = new iong[30];
protected static long[] endTime = new iong[30];
protected Static int neighborlndex = O;
protected static int updated = 0 ;
protected static boolean first = false;
protected static int ackHello = O;
I
protected static String[] allName = new String[30];
protected static int[] secuencia = new int[30];
protected Static int allindex = O;
protected static int[][l costs = new int[30][30];
protected static int c o n k e d = o;
ii Interfaces para accesar y modificar los conocimientos
public int getLocalSec()(
iocalSec = IocalSec + 1:
return IocalSec;
)
Public Void setSec(int sec, String name) (
int index;
index = findNode(name. allName, alllndeu);
if(index != -1)
secuencia[index] = sect
return;
101
Apéndice A
public int getCec(String name)
int index:
index = findNode(name. allName, alllndex),
if(index I= -i)
return secuenc~a[index].
return O;
1
public void updatedOnce0 (
first = true;
1
public boolean firstupdate0 (
return first;
1
public void incHello0 (
ackHello = ackHello +'I;
1
public boolean hellODone0 (
if(ackHell0 >= getNeighborMax0)
return true,
return false;
1
public void resetupdated0 (
updated = O ;
1
public void incUpdated0 (
updated++;
public int getupdatedo (
return updated;
I
public boolean getLine(Ctring name) (
int index;
index = findNode(name, neighborName. neighborlndex),
if(lineFree(index] ==true) (
IineFree[index] =false,
return true,
) else (
return false,
1
I
public void freeLine(String name) (
int index;
index = findNode(name, neighborName. neighborlndex);
if(index != -1)
lineFree[index] =true:
1
public void freenil() (
int i;
for(i=O; ic30; I++)
lineFree[i] = true;
1
public void setCon(int c) (
conUsed = c;
1 o2
Apéndice A
public int getcon() (
return conused;
1
public void incCon() (
conusedi+;
I
4
!¡ public void decCon() (
conllsed-;
I
public void local(String name, String áddr) (
IocalName = name;
IocalAddr = addr; I1
addAll(name);
1
public String getLocalName() (
return IocalName;
1
11
public String getLocalAddr() ., return IocalAddr;
)
public void resetEnd(int index) (
endTimf[index] = 01,
) 11
public void startTimer(int index) (
startTime[index] = System.currentTimeMiilis();
1
public boolean end(int index) (
if(endTime[index] != 01)
return true;
return false;
)
public int getDelay(int index) (
long result;
result = endTime(index1 - startTirne[index];
return (intpesult;
1
public void stopTimer(int index) (
endTime[index] = System.currentTimeMillis();
1
public void addNeighbor(String addr) (
if(findNode(addr. neighborAddr, neighborlndex) == -1) (
neighborAddr[neighborlndex] = addr;
queue[neighborlndex] = new Vector();
neighborlndex++; 11
)
public void addNeighborName(String name, String addr) (
int index = O:
index = findNode(addr, neighborAddr, neighborlndex);
if(index != -1)
neighborName[index] = name;
'I 1
public void de¡Neighbor(String name)
f 03
Aoéndice A
int index = O;
index = findNode(name, neighborName,
if(index != -1) (
neighborindex);
if(index != neighborlndex - 1) (
neighborName[index] = neighborNarne[neighborlndex - 11;
neighborAddr[index] = neighborAddr[neighborlndex - 11;
I
neighborName[neighborlndex - I ] =null,
neighborAddr[neighborindex - I ] = null,
neighborlndex--;
1
public void modNeighbor(String oldName.
String name, String addr) (
int index = O.
index = findNode(oldName, neighborName,
if(index I= -i) (
neighborlndex).
neighborName[index] = name,
neighborAddr[index] = addr.
)
public in1 getNeighborMax0 (
return neighborlndex,
public int getNeighborlndex(String n) (
int index = -1,
index = findNode(n, neighborName, neighborlndex),
return index;
1
public int getNeighborlndexByAddr(String a) (
int index = -1;
index = findNode(a, neighborAddr. neighborlndex);
return index;
)
public String getNeighborName(int index) (
if(index c neighborindex && index >= O )
return neighborName[index]:
else
return null;
)
public String getNeighborAddr(int index) (
if(index c neighborlndex &8 index >=O)
return neighborAddr[index];
else
return null;
1
public void addAIi(String name)
if(findNode(name, allName, alllndex) == -1) (
ailName[alllndex] =name;
ail lndexii;
public void delAII(String name) (
int index = O;
index = findNode(name, allName. alllndex);
if(index i= -1) (
104
Apéndice A
¡((index != neighborlndex - 1)
allName[index] = allName[alllndqx - I]; )
allName[alllndex - I] = null;
alllndex--;
I1
., 1 ) I!
¡I public void modAll(String oldName,
String name)
int index = O:
index = findNode(oldName, allName, alllndex);
if(index I= -1)
allName[index] =name;
1 i k
1
public int getAIIMax()
return alllndex;
)
public int getAiiindex(String n) ( II
int index = -1;
index = lindNode(n, allName. alllndex);
return index;
public String getAIIName(int index) ( 11
alllndex && index >= O) if(index
return allName[index];
else .I
return null;
public void updateTime(String srcName, String tgtName, int delay)
int src = O;
int tgt = O;
src = findNode(srcName, allName, alllndex);
tgt = findNode(tgtName, allName, alllndex);
costs[src][tgt] =delay;
1
public int getTime(String srcName, String tgtName)
int src = O;
int tgt = O;
src = findNode(srcNarne. allName, alilndex);
tgt = findNode(tgtName, aliName, alllndex);
return costs[src][tgt];
public void print() (
int I, j;
for(i=O; icalllndex: I++)
for(j=O; jcalilndex; j++) (
System.out.print(costs[i]tj] + " ");
System.out.pnnt("\n");
System.out.print("W);
protected int findNode(Str1ng name, String lista[]. int last) (
int ¡=o;
Apéndice A
boolean flag =false;
while (¡clast && !flag) (
if(lista[i].compareTo(name) == O)
flag =true;
else
i++;
I if (Iflag)
[=.l.
return i;
I 1 import java.lang.';
o
o I1 Esta clase manda la tabla de estado de las lineas a todos
O I/ los nodos a traves de inundacion
0 public class LinkState implements Runnable (
o
O private void checkUpdatedO (
NetState netstate = new Netstate();
while(true) (
if(netState.getUpdated() >= netState.getNeighborMax0)
sendstate();
netState.resetUpdated();
netState.updatedOnce();
> 1
I
private void sendstate() (
NetState netstate = new Netstate();
ShoriPath shortpath = new Shortpath():
int iJ;
String msg =new String();
String mensaje =new String();
String host = new String();
String loca! = new String();
String[] path = new String[30];
int delay.= O;
local = netState.getLocalName();
11 Se genera el paquete de estado
for(i=O; icnetState.getNeighborMax(); i++) (
host = netState.getNeighborName(1);
delay = netState.getTime(loca1, host);
msg = host + "," + delay + '";' + msg;
)
msg; msg = '"!NA-TABLE!" + netState.getLocalSec() + "!" +
for(i=O; icnetState.getNeighborMax(); i++) (
mensaje = new string();
host = netState.getNeighborName(i);
path = shortPath.getPath(locai, host);
j = o;
do (
mensaje = mensaje + patho] + ",";
j++;
while (pathlj] !=null);
mensaje = local + "!" + host + "I" + mensaje + msg;
I1 Se encola el paquete
netState.queue[netState.getNeighborlndex(path[l])].addEl
106
ApéndiceA ~
ement(mensa1e).
)
netstate resetupdatedo,
netstate print(),
I
public void run() (
thischeckUpdated0;
1
I import lava iang I ,
o
U /I Esta clase cuenta cada cuanto tiempo se debe medir el costo de
o /I las hneas
o
o I
public class EchoTimer implements Runnabie ( II
private final long PERIODO = 1200001;
private static long IastTime;
public void run() (
NetState netstate = new Netstate();
int a;
!I 11 Se mide el costo ai iniciar el agente
IastTime = System.currentTimeMillis() - PERIODO;
while(tNe) (
I1 Si ya pasc el periodo marcado de tiempo
if(iast1 imeiPERlOD0 c Syslem.currentTimeMiilis()) (
netState.resetUpdated();
11 Se inicia un hilo para cada linea ,,
for(a.0; a<netState.getNeighborMaxO; a++)
new Thread(new Echo(aj).stait();
IastTime = System.currentTimeMiilis();
netState.print();
1
I
)
>
I import java.lang.';
o
o I I1 Esta clase manda un ECHO para medir el costo de la linea,
11 en milisegundos
public class Echo implements Runnable (
int index:
public Echo(int a) (
this.index = a :
1
public static void echo(int index) (
NetState netstate = new Netstate();
String msg =new String();
String target = new String();
String IocalName = new String():
int delay;
boolean flag =false;
long startTime = 01;
final long PERiODO = 11 00001;
11 Se forma el paquete
IocalName = netState.getLocalName();
1'07
Aoéndice A
target = netstate getNeighborName(index),
msg = "NA-ECHO.
msg = IocaiName + '"I" +target + "I" + iocalName + ";' +
target + "," + "I.. + msg,
netstate resetEnd(index).
I/ Se inicia el contador
netState.startTimer(index);
11 Se encola el paquete
netState.queue[index].addElement(msg);
startTime = System.currentTimeMillis();
whiie(netState.end(index) == false) (
if(startTimeiPERIOD0 <= System.cunentTimeMillis()) (
flag =true;
break;
, , 1
1
I1 Si el paquete regreso, se pone el resultado obtenido
if(fiag == false)
delay=netState.getDelay(index);
11 Si el paquete no regreso en 110000 millisegundo, se le
/I Done un costo a la linea de 1000000 miiiisegundos
1
import java.io.';
O import java.util.';
o
O //Esta clase maneja el servidor que funciona como entrada del agente
o /I Corre en un hilos para que se pueda aceptar mas de una
/I conexion a la vez
public class AgentlnPort implements Runnable (
private Socket server = null;
public AgentlnPort(S0cket server) (
this.seNer = SeNer;
1
protected void handieConnectionServer() (
NetState netstate =new Netstate();
int nag = O, i, j;
String msg =new String();
String input = new String();
String nextHost = new String();
else int index = O,
delay=lOOOOOO,
netstate updateTime(l0calName. target, delay),
netstate incUpdated0,
I/ Se genera un lector y un escritor para mandar paquetes por el
11 socket
try (
BufferedReader in = public void run() (
this.echo(index);
1
1 import lava net *.
o
socketUtii.getüufferedReader(seNer);
PrintWriter out =
SocketUtil.getPrintWriter(server):
11 Se lee el paquete que se mando
108
Apéndice A
input = in.readLine0:
I1 Se interpreta el paquete para tomar la acclon apropiada
flag = interpret(input).
11 Es un paquete de datos dirigido a este servido1
if(flag == O) (
out.println("Acknowledge"); I1
I1 Es un paquete de datos dirigido a otro servido
else if(flag == 1) (
nextHost = getNext(input);
index = netState.getNeighborlndex(nextHost);
netState.queue[index].addElement(input);
out.println('Acknowledge");
i
I¡
'? .il
I/ Es un paquete de control HELLO
1 else if(flag == 2) ( ii
out.println("NA-REHELLO!" + netState.getLocalName());
/I ES un paqdete de control ECHO
else ififlag == 3) Ih
out.~!rintln("NA-REECHo);
)
/I Es un paquete de control TABLE nuevo
else ifíflag == 4) (
out.println("NA-RETABLE);
tablr(input);
I
11 Es un paquete de control TABLE reclbido con anterioridad
else if(flag == 40) (
out.println("NA-RETABLEAGAIN); ,,
)
/I No se pudo identificar el paquete, existio un error
else (
out.println("Erro?);
I1 Se sierra la conexion
server.ciose();
I/ Se decrementa el contador de conexiones usadas
netState.decCon(),
1 catch (IOException ioe) (
) ' 1
I1 Este metodo descompone el paquete e identifica que tipo de
I1 paquete es
protected int interpret(String mensaje) (
NetState netstate = new Netstate();
inti;
String temp=mensaje;
String rest = new String();
int sec = O ;
if(mensaje.compareTo("NA-HELLO) == o) return 2;
i = temp.indexOf("I");
if(¡ != -1) (
String source = temp.substring(0, i);
temp = temp.substring(i+l);
Apéndice A -7 i = temp.indexOf("!");
if(¡ != -1) (
String target = temp.substring(0, i);
temp = temp.substring(i+l);
i = temp.indexOf("!");
if(¡ I= -1) (
temp = temp.substring(i+l); *
I = temp.indexOf("!");
if(¡ I= -1) (
rest = temp.substring(i+l);
temp = temp.substring(0, i);
if(target.compareTo(netState.getLocalName()) != 0) (
return 1 ;
J else if (temp,compareTo("NA-ECHO) == O) (
return 3;
)else if (temp.compareTo("NA-TABLE) ==O) (
i = rest.indexOf("!");
if(¡ != -1) (
sec = new Integer(rest.substring(0, i)).intValueO;
if(secmetState.getSec(source))
return 4;
1 return 40;
) else if (target.compareTo(netState.getLocaiName()) == O ) (
System.out.println("Mensaje recibido de " +
source + ": "
+temp);
return O:
J else (
return 5;
)
1 return 5:
/ I Este metodo identifica el siguiente receptor en un paquete
I/ de datos
protected String getNext(String msg)
NetState netstate = new Netstate();
inti;
String temp=msg;
String host = new String();
i = temp.indexOf("!");
temp = temp.substring(ii1);
i = temp.indexOf("!");
temp = temp.substring(i+l);
do (
I = temp.indexOf(".");
host = temp.substring(0, i);
temp = temp.substring(i+l):
) while(host.compareTo(netState.getLocalName()) != 0);
i = temp.indexOfr.");
host = temp.substring(0, i);
return host;
J
// Este metodo actualiza los valores de la tabla de estado
// utilizando los valores de ECHO recolectados por otro servidor
protected void tabie(String input) (
NetState netstate = new Netstate();
Shortpath shortpath = new ShortPathO;
110
Apéndice A ,
inti. delay, j, sec;
String temp=input;
String src, tgt;
String target = new string();
String msg =new String();
ll
i = temp.indexOf("!");
5rc = temp.substring(0, i);
i = temp.lastlndexOf("!");
rnsg = temp.substring(0, i);
temp = temp.substring(i+l);
i = msg.lastlndexOi("!");
sec = new Integer(msg.substring(i+l)).intValue();
netState.setSec(sec, src);
for(j=O; j<netState.getNeighborMax(); I++) (
target = netState.getNeighborNameij);
ii(target !=nul!) (
rnsg =temp;
msg = src + "!" + target + ''1'' + src + "," +
target + "," + "!" + "NA-TABLE!"
+ sec + "l" + msg;
netState.queue~].addElement(msg);
)
11 1 do I
i = ten:p.indexOf(",");
tgt = tempsubstring(0, i);
temp = temp.substring(i+l);
i = tenip.indexOf(".");
delay :: new Integer(temp.substring(0, i)).intVaiue():
netStaie.updateTime(src, tgt, delay);
temp i: temp.substring(i+l);
'I
\
while (temp.length() > 2);
public void run() (
this.handleConnectionServer();
return;
1
! 1 import java.net.*;
o import java.io.*;
G import java.uti!:;
I
//Esta clase maneja e! cliente que funciona como salida del agente
li Corre en hilos para poder tener una conexion con cada SeNidor
I/ vecino
public class AgentOutPort implements Runnabie (
protected String target:
protected String mensaje;
protected String name;
protected int error = o;
public AgentOutPort (String name, String mensaje) (
this.name =name;
thismensaje = mensaje;
1
public void connect() (
NetState netstate = new Netstate();
target = thismame;
ii(mensaje compareTo("NA-HELLO) I= O)
target = netstate getNeighborAddr(netState getNeighborlndex(nam e)) .
try (
11 1
ApéndiG A
ii Se pide la conexion con el servidor del otro agente
Socket client = new Socket(target, 5555);
handleConnectionClient(c1ient);
I/ Si se mando un HELLO, no se necesita liberar la linea
if(mensaje.compareTorNA-HELLO) != O)
netState.freeLine(name);
else
I/ Se actualiza elcontador de HELLO, para saber cuando se logro un
// HELLO con cada vecino
netState.incHello0;
) catch(UnknownHostExcepti0n uhe) (
System.out.println("Unknown host: " + target):
uhe.printStackTrace();
) catch(ConnectExcepti0n ce)
this.connect();
) catch(l0Exception ioe) (
System.out.println('lOException: " + ioe);
ioe.printStackTrace0;
return;
// Este metodo maneja la conexion
protected void handleConnectionClient(S0cket client)
throws IOException (
Netstate netstate = new Netstate();
Printwriter out =
SocketUtil.getPrintWrRer(ciient);
BufferedReader in =
SocketUtil.getBufferedReader(client);
String input = new String();
inti, a;
String temp;
String com =new String();
/ I AI establecer la conexion, se manda el paquete
out.println(mensaje);
input = in.readLine();
ciient.close();
U Si hubo un error, se intenta 5 veces mas
if(input.compareTo("Errof) ==O) (
error++;
if(error > 5)
return;
connect();
if(input == null 11 input.compareTorAcknowiedge") == O
11 input.compareTo("NA-RETABLE) = = O )
return:
I/ Si fue un ECHO, se para el contador que mide el costo de la linea
if(input.compareTo("NA-REECHO)==O) (
temp = mensaje;
i = temp.indexOl('!");
temp = temp.substring(i+l);
i = temp.indexOf("!");
temp = temp.substring(0.i);
i = netState.getNeighborlndex(temp);
netState.stopTimer(i); /
return;
i/ Si fue un HELLO, se actualiza el nombre del vecino
temp = input;
112
Apéndice A
i = temp.indexOf("!");
if(¡ != -1)
corn = temp.substring(0, i);
temp = temp.substring(i+l);
i i . 1 '
if(com.compareTo(."A-REHELLO) == O) (
for(a=O; a<netState.getNeighborMax(); a++) (
com = netCtate.getNeighborAddr(a);
if(com.cornpareTo(name) == O)
I = a;
)
i f ( i k l ) (
netState.addNeighborName(temp, netCtate.getNeighborAddr(i));
)
)
)
return;
1
public void run() (
this.conriect();
return;
)
1
.Aoéndice A
114
REFERENCIAS
[Bratman 1987) “Intentions, Plans, and Practical Reasoning” Bratman, M E Harvard University Press, 1987
A subject-indexed bibliogrphy of distributed artificial intilligence. Bond A H , and Gasser, L IEEE Trans Syst Man Cybernet SMC-22(6) 1260-1 281, 1992
[Bond 19921
[Cohen, 19881
[Cohen 1990al
[Cohen 1990bl
[Cohen 19941
[Cohen 19951
[DARPA 19931
“Rational Interaction as Basis for Communication” Cohen P. R. and Levesque H. J. Tehnical Report, SRI International 1988.
“Performative in Rational Bases Speech Act Theory” Cohen R. Philip and Levesque J. Hector Proceedings of the 28‘h Annual Meeting of the Association for Computational Linguistic, Pittsburgh, Pennsylvania. Junio 1990.
“Intention is Choice with Commitment” Cohen R. Philip and Levesque J. Hector Technical Report SRI International 1990.
.:‘An Open Agent Arquitecture*” Cohen Philip R., Adam Cheyer, Michelle Wang and S. C Baeg in AAAl Spring Symposium pp. 1-8, Marchl994.
,“Communicative Actions for Artificial Agents” Cohen R. Philip and Levesque J. Hector First International Conference on Multi-Agent Systems pp, 65. Junio 12-1 14, 1995
DRAFT. Specification of the KQML Agent- Communication Language plus example agente ’ policies and architectures The DARPA Knowledge Sharing Initiative External Interfaces Working Group.
115
[Duerfee 19891
[El-Fallah 19991
[Emerson 19901
[Gamble 19991
[Gotzhein 19921
[Guerra 19971
[Hintikka 19721
Junio 15, 1993. http://www.darpa.mil/
[email protected] [email protected]
Duerfee, E.H .; Lesser, VR and Corkill Cooperative Distributed problem solving. Handbook of Artificial Intelligence., Vol 4. Addisson Wesley 1989.
Tutorial Multiagentes. El-Fallah Amal, Demazeu Yves y Lemaitre. Primeras Jornadas Franco-Mexicanas de Informática y Atumática. Marzo 15/18 1999
Temporal and modal logic. Handbook of Theorical Computer Science Ed. J. Van Leeuwen.
Elsevier, Amsterdan 1990.
KQML-USER(íuISI.EDU
pp 996-1 072.
Gamble Rose; and Sen Sandip Using Formal Specification to resolve Conflicts between Contracting Agents Department of Mathematical & Computer Scinces University of Tulsa, 600 South Collage Avenue Tulsa, OK 74104-3189, e-mail:[email protected], [email protected]
Temporal logic applications-a tutorial Gotzhein Reinhard pp. 203-21 8. Elselvier Science Publishers B.V All rights revserved., 1992
'"Selección de Acción en Agentes Autónomos, una aproximación basados en el comportamiento" Guerra Hernandez Alejandro; García Vega Angelica pp. 75-85.
Junio 1 1-1 3. . Primer Simposio Internacional en Tecnologiac Inteligentes,
Apizaco, Tlaxcala, México., 1997. Knowledge and Belief Hintikka, J. Cornell University Press, 1972
116
_c---
[Keith 19981
[KISS 19921
[Lander 19971
[O’Hare 19961
[Munindar 19911
[Nwana 19961
[Nwana 19991
[Rao 19911
.“Meaning and speech acts” Keith Allan, Linguitistics Department, Monash
March 1, 1998.
‘,‘Variable coupling of agents to their environment: Combining situated and symbolic automata” Kiss, G. Descentralized Artificial lnteliqence 3 Ed. Werner and Demazeau
Elsevier/North-Holland, Amsterdan.
“lssies in Multiagent Desing Systems” Lander Susan E. Blackboard Technology
March-April 1997.
Foundations of Distributed Artificial Intelligence O’lhare G.M.P. and N.R. Jennings Wiley, 1996
“A semantics for Speech Acts” Munindar P Singh and Austin TX 78754 Annals of Mathematics and Artificial lntelligencial Volumen 8, pp 47-71. Mayo 1991
“Software Agent: An Overview” Nwana S. Hyacinth Cambridge University Press, Knowledge Engineering Review, Vol 11 No. 3 pp. 205-244 OctubrelNoviembrel996.
“Software Agent Technologies” Intelligent Systems Research Nwana hyacinth (BT) and (QMW) Michael Wooldridge Applied Research and Technology, BT Labs Enero 1999.
‘University. I
http://www.arts.monash.edu.auílinaíspeech acts allan.shtml
Pp. 231-248
IEEE EXPERT, pp 18-26
h t tp i l lw . labs. bt.com/proiectslaaents/publ¡sh/papers/sat report.htm
“Modeling Rational Agents within a BDI Architecture” O ~ - O O U ~
117 I SEP CENBDET DGlT
CENTRO DE INFORMACION