MÉTODO DE COMPARACIÓN UTILIZANDO MÉTRICAS DE CALIDAD PARA PROTOCOLOS DE NEGOCIACIÓN ELECTRÓNICA EN SISTEMAS MULTI-AGENTE

COMPARISON METHOD FOR ELECTRONIC NEGOTIATION PROTOCOLS USING QUALITY METRICS IN MULTI-AGENT ENVIRONMENTS

MARCELA PASTRANA DAVID
Universidad Nacional de Colombia, Escuela de Sistemas, Facultad de Minas, mmpastra@unalmed.edu.co

DEMETRIO ARTURO OVALLE CARRANZA
Universidad Nacional de Colombia, Director Escuela de Sistemas, Facultad de Minas, dovalle@unalmed.edu.co

Recibido para revisar Marzo 31 de 2007, aceptado Julio 07 de 2007, versión final Noviembre 13 de 2007


RESUMEN: El objetivo del trabajo presentado en este artículo consiste en la definición de un método de comparación basado en la aplicación de métricas de calidad elaboradas con el fin de medir protocolos de negociación electrónica en entornos Multi-Agente. Para la comparación de los protocolos se escogen los siguientes criterios de calidad: Rapidez, Eficiencia, Escalabilidad y Completitud. Para la aplicación y validación del método de Comparación se implementan dos prototipos de negociación electrónica basados en las subastas inglesa y holandesa, utilizando la plataforma JADE (Java Agents DEvelopment Framework) y se obtuvieron resultados preliminares de su comportamiento los cuales fueron analizados y se sacaron las conclusiones respectivas.

PALABRAS CLAVE: Sistemas Inteligentes, Protocolos de Negociación Electrónica, Métricas de Calidad, Método de comparación de Protocolos Multi-Agente, Subasta Inglesa, Subasta Holandesa.

ABSTRACT: This paper aim at defining a comparison method based on the application of quality metrics which are proposed for measuring electronic negotiation protocols in Multi-Agent environments. In order to make a formal comparison several quality criteria were taken into account: Speediness, Efficiency, Scalability and Completeness. Then, to apply and validate the proposed method for comparing electronic protocols two prototypes based on English auction and Dutch auction were built. For doing so, JADE (Java Agents DEvelopment Framework) platform was used and preliminary results on their behavior were obtained. Those results were finally analyzed and corresponding conclusions were provided.

KEYWORDS: Intelligent Systems, Electronic Negotiation Protocols, Quality Metrics, Comparison Method for Multi-Agent Protocols, English Auction, Dutch Auction.


1. INTRODUCCIÓN

Cuando se habla de un Sistema Multi-Agente (SMA), una de las problemáticas más estudiadas, es la forma cómo los agentes interactúan unos con otros para alcanzar sus objetivos de la forma más rápida y eficiente, es por esto, que a la hora de implementar un SMA [1] donde se lleve a cabo comunicación y cooperación negociada, uno de los principales aspectos a tener en cuenta, es la escogencia de un buen mecanismo de negociación, de tal forma que resulte adecuado para llevar a cabo las interacciones entre los agentes y su cooperación para el logro de un objetivo común, es aquí donde se empiezan a mencionar los términos protocolo y estrategia de negociación Multi-Agente.

Los protocolos y las estrategias de negociación Multi-agente, generalmente se asemejan a la forma como los humanos negocian en un mercado competitivo, ésto posibilita que los Sistemas con la orientación de agentes sean muy utilizados en la representación e implementación de mercados de productos o servicios, tanto en ambientes simulados como en ambientes reales a través de Internet, también denominado Comercio Electrónico E-Bussines.

2. REVISIÓN DEL ESTADO DEL ARTE

En el área de los sistemas Multi-Agente, particularmente enfatizando en los protocolos de negociación, se encuentra un campo con muchos aspectos que deben ser estudiados. Existen muchos trabajos recientes que ahondan en la problemática relacionada a la definición y caracterización de los protocolos de negociación y a su aplicación a distintos problemas del mundo real.

Es común encontrar, en los SMA en general, que involucran procesos cooperativos y que implican mecanismos de negociación entre agentes, que se definan nuevos protocolos particulares, aplicados a un problema específico, como es el caso de los trabajos de Zhang [2], Bartolini [3] y Jaiswal [4]. Ésto en ciertos casos no tiene mucha razón de ser, pues lo ideal sería poder tener caracterizados los protocolos existentes, de forma que se pueda identificar cuáles son los más adecuados a ciertos tipos de problemas, con el fin de no tener que reinventar un protocolo de negociación cada vez que se haga un SMA, sino hacer pequeñas adaptaciones en detalles muy específicos del problema o dominio particular a implementar.

En el trabajo de Reaidya [5] se trabajan SMA orientados a la manufactura, para ello se realiza un estudio de los mecanismos de negociación que pueden ser asociados a problemas en este dominio de conocimiento. Con base en ello, se desarrollan 5 protocolos basados en FIPA Contract Net (toma de decisiones consensual, teoría de juegos, centralizado, de menor tiempo de completación esperada y el último, basado en una métrica de dinero). Estos protocolos son comparados a través de simulaciones en entornos Multi-Agente.

Los protocolos de negociación utilizados en el trabajo de Jaiswal [4] se relacionan con los mercados electrónicos B2B (Business to Business). Se implementa un marketplace multi-agente seguro denominado MAGNET. Así, en este trabajo se considera que para un protocolo Multi-Agente, que opere en el contexto de los mercados electrónicos, una de las características fundamentales debe ser la seguridad, ya que sin ésto no es posible ganar la confianza de los clientes e incentivarlos a realizar sus negocios a través de este tipo de sistemas.

Anumba [6], por su parte, propone en su trabajo una negociación multi-agente colaborativa para la construcción de edificios industriales. Se examinan algunas de las principales teorías de negociación y sus posibles aplicaciones en mecanismos de negociación multi-agente. Con base en ello se desarrolla un protocolo de negociación llamado ADLIB y con él se desarrolla un prototipo de SMA.

Teniendo en cuenta los trabajos analizados se identificaron una serie de limitaciones con relación a la definición y caracterización de protocolos de negociación en sistemas Multi-Agente.

Las principales limitaciones que se tuvieron en cuenta para el desarrollo del trabajo de investigación que se presenta en este artículo son:

3. PROTOCOLOS DE NEGOCIACIÓN ELECTRÓNICA

Los protocolos de negociación electrónica son mecanismos manejados en la teoría de los SMA. Éstos representan los patrones o conjunto de reglas que modelan las posibles interacciones presentes en el sistema. Lo anterior incluye: Tipos de participantes permitidos, estados de la negociación, eventos que ocasionan la transición de los estados y las acciones válidas de los participantes en los estados particulares [7].

Dos de los protocolos de negociación más conocidos y que han sido definidos por la FIPA (Foundation for Intelligent Physical Agents) son [8]:

4. MÉTRICAS DE CALIDAD EN PROTOCOLOS DE NEGOCIACIÓN ELECTRÓNICA

Para definir las métricas, se analizaron distintos criterios de calidad que pudieran permitir la comparación de los dos protocolos de negociación mencionados en la sección anterior. De ellos se lograron destacar cuatro criterios para la definición de las métricas de calidad, objeto de este trabajo, los criterios escogidos fueron los siguientes: Rapidez [5], Completitud [2], Escalabilidad [11] y Eficiencia [12].

4.1 Rapidez
Se define la rapidez (Ra), como el tiempo que tarda un protocolo en alcanzar el fin de la negociación. Para llegar a plantear una formula de la rapidez de un protocolo se deben tener ciertas condiciones constantes, en el caso particular de este trabajo se tomaran como constantes todo lo relativo a la plataforma y el número de agentes.

Bajo estas condiciones se define la Rapidez, denotada por la sigla Ra, de un protocolo como:

Ra=#c

Donde: #c: Es el número de conversaciones realizadas durante el proceso de negociación llevado a cabo por los agentes del SMA.

Estos valores arrojados deben ser normalizados para obtener resultados comprensibles y claros sobre la rapidez del protocolo, para este proceso de normalización se toman en cuenta 2 factores:

De la cual se llega a la ecuación final para denotar la rapidez normalizada, que equivale a lo siguiente:

Rango: Según la ecuación anterior podemos garantizar que la rapidez está definida en el rango [0,1].

4.2 Eficiencia
Se define la métrica de eficiencia (Ef) de un protocolo de negociación Multi-Agente, como el número comprendido entre [0,1], el cual valora la eficiencia de las utilidades obtenidas por los agentes, tanto compradores como vendedores, durante el proceso de negociación.

Las formulas para representar la Ef son:

Donde:

Rango: Según la ecuación anterior podemos garantizar que el valor para la métrica de eficiencia está comprendido en el rango [0, 1].

4.3 Escalabilidad
La métrica de Escalabilidad determina cómo cambia el desempeño del SMA cuando su tamaño, dado por el número de agentes, incrementa o disminuye. La medición de este criterio se hace aumentando el número de agentes dentro del SMA, y tomando en cuenta en cada caso, la completitud, la rapidez y la eficiencia. Si estos valores se degradan desproporcionadamente a medida que el tamaño del sistema aumenta, entonces, se puede decir que el protocolo tiene una escalabilidad deficiente.

Rango: El rango para la métrica de escalabilidad está comprendido en el intervalo [0, 1]. Se manejaron 4 valores lingŁísticos para identificar el valor de desempeño del SMA con respecto a la métrica de escalabilidad de un protocolo específico que se describen en la tabla 1.

Tabla 1. Intervalos para la interpretación de la Eficiencia
Table 1. Intervals for efficiency interpretation

4.4 Completitud
La completitud (Co) de un protocolo, es la capacidad de encontrar una solución al proceso de la negociación electrónica. Para la medida de este factor se debe fijar un tiempo máximo de la subasta y se debe verificar si la negociación se completó o no.

Rango: Toma sólo 2 valores dentro del rango [0, 1].

1 => Si se realizó el proceso de negociación completo dentro del tiempo de la subasta.
0 => No se realizó el proceso de negociación en el tiempo fijado.

5. MÉTODO DE COMPARACIÓN DE PROTOCOLOS Y APLICACIÓN A UN CASO DE ESTUDIO

A partir de las métricas de calidad definidas en la sección anterior se propone la definición de un método de comparación de protocolos de negociación electrónica Multi-Agente. Este método se compone de las siguientes tres fases:

Las diferentes fases contienen: documentos y artefactos de entrada, una descripción de las actividades que se realizan y unas salidas del proceso realizado.

5.1 Fase de Definición del caso de estudio
El caso de estudio que se escogió en este trabajo consiste en un sistema de negociación para la compra y venta de libros, en donde se realizarán procesos de subasta de los diferentes tipos de libros a los precios establecidos para ello (ver figura 1).


Figura 1.
Diagrama de procesos de la negociación de libros
Figure 1. Process chart for book negociation

Para especificar y analizar el SMA, se desarrollan los diferentes modelos de la metodología de análisis y diseño de Sistemas Multi-Agente MAS Common-KADS [13], en la cual se proponen siete modelos para el desarrollo de un SMA, a saber:

Dentro de los distintos Modelos propuestos por esta metodología se elaboran plantillas donde se registra la información de los distintos elementos que componen el SMA.

En la tabla 2 se puede observar una de las plantillas elaboradas durante la construcción del Modelo de Agentes, en ésta se detalla el agente Vendedor del Caso de Estudio Mercado de Libros.

Tabla 2. Plantilla para especificar el agente Vendedor
Table 2. Template for seller software agent specification

5.2 Fase de diseño, implementación y medición del desempeño de los protocolos Multi-Agente
En esta fase de diseño e implementación se utiliza la especificación del sistema realizada anteriormente (ver sección anterior), con el fin de realizar un Prototipo de SMA por cada uno de los protocolos de Negociación Multi-Agente estudiados para el caso de estudio, los cuales son:

Los prototipos implementados en este proyecto fueron desarrollados con la plataforma JADE (Java Agent DEvelopment Framework) [7], la cual es un middleware que proporciona tanto un entorno de desarrollo como un entorno de ejecución para la realización y mantenimiento de SMA. Está realizado enteramente en JAVA y proporciona una serie de herramientas que permiten al desarrollador controlar y depurar a los agentes en tiempo real. Además, JADE cumple con las especificaciones de FIPA para la interoperabilidad de plataformas de SMA, y lo cumple a dos niveles: a nivel de arquitectura y a nivel de Mensajes (FIPA ACL).

Con los prototipos implementados a través de la plataforma JADE, se realizó la toma de los resultados. En este artículo se presentan algunos de los resultados más significativos, los cuales fueron tomados utilizando las plantillas definidas en el método de comparación propuesto.

5.3 Fase de evaluación de resultados
Luego de tener todos los datos de las diferentes métricas se procede a la elaboración de las tablas resumidas, con las cuales se toman las conclusiones con respecto a la Eficiencia, Rapidez, Escalabilidad y Completitud de los protocolos Multi-Agente estudiados.

Los resultados de la Eficiencia se evalúan a la luz del dominio del problema en el cual han sido implementados y se hace una tabla resumen que tenga los protocolos implementados y el valor numérico con la correspondiente interpretación, en la tabla 2 se muestra la plantilla propuesta para ello.

Los resultados de la Rapidez se evalúan de acuerdo a los datos del problema y a los arrojados por la experimentación, los resultados registrados según la plantilla establecida por el método se pueden observar en la tabla 3.

Tabla 3. Plantilla para llenar los resultados de la evaluación de la Eficiencia en la Subasta Inglesa
Tabla 3. Template provided to fulfill the results obtained from the efficiency criterion evaluation

Tabla 4. Resultados de la evaluación de la Eficiencia
Tabla 4. Results obtained from the efficiency criterion evaluation

Tabla 5. Resultados de la evaluación de la Rapidez
Table 5.
Results obtained from the Speedness evaluation

Para la evaluación de la escalabilidad de unprotocolo, con relación a los resultados arrojados y a su concordancia con las otras métricas se debe, antes que nada, elaborar una tabla resumen que contenga todos los casos evaluados y sintetizados, tomando en cuenta el tipo de protocolo y el número de agentes, se propone para esto la plantilla que se muestra en la tabla 6. La rapidez en los datos mostrados fue normalizada tomando como Rapidez más alta 75 y Rapidez más baja 953 conversaciones.

Tabla 6. Plantilla para resumir los resultados de la Escalabilidad
Tabla 6.
Template to collect results from Scalability criterion calculation

Luego de tener la tabla resumida que refleja como van cambiando las condiciones del SMA a medida que se varia el número de agentes, se procede a llenar la plantilla que se muestra en la tabla 7, la cual va a contener el resultado tanto numérico como lingŁístico de la escalabilidad de los distintos protocolos implementados. Estos resultados son tomados subjetivamente, ya que involucran el análisis de la tabla 6, dado que los distintos parámetros de eficiencia del comprador, del vendedor, rapidez y completitud están dados en términos que no se pueden unificar.

Tabla 7. Plantilla para la evaluación de la Escalabilidad
Table 7.
Template for Scalability criterion evaluation

6. CONCLUSIONES Y TRABAJO FUTURO

Con este método de comparación propuesto se logra realizar de una forma clara y ordenada la identificación, caracterización y

evaluación del desempeño de distintos protocolos Multi-Agente de Negociación Electrónica. A través de la aplicación del método propuesto se obtuvieron resultados satisfactorios sobre el desempeño de los diferentes protocolos de negociación electrónica Multi-Agentes. Este conocimiento es muy útil al momento de escoger alguno de ellos para realizar la subasta electrónica de productos tangibles.

Tomando en cuenta los resultados obtenidos en la ejecución y comparación de los protocolos de negociación electrónica se puede concluir lo siguiente en términos de la Eficiencia y Rapidez de los protocolos implementados:

En términos de la Escalabilidad podemos concluir lo siguiente:

En términos de La Completitud, los protocolos Subasta Inglesa y holandesa, bajo las condiciones adecuadas, implementadas en este trabajo, resultaron completos.

El método propuesto en este trabajo, resultó exitoso, pues permite determinar bajo ciertas métricas cuál protocolo es más beneficioso entre varios propuestos al momento de subastar electrónicamente productos tangibles.

Como trabajo futuro y como mejoras que se plantean a este trabajo, se proponen los siguientes puntos:

REFERENCIAS

[1] OVALLE D. & MORENO J. “Computational Hybrid System based on Neural-Fuzzy Techniques & Intelligent Software Agents to Assist Colombian Electricity Free Market”. IJCIR International Journal of Computational Intelligence Research, ISSN 0973-1873, v.3, n.2, 2007.
[2] ZHANG W., WANG, G., MAILLER R., LESSER V. “Analysis of negotiation protocols by distributed search”. Distributed Sensor Networks: A multiagent perspective. 2003.
[3] BARTOLINI C., PREIST C., KUNO H. Requirements for automated negotiation. Hewlett-Packard Labs, 2004.
[4] JAISWAL A., YONGDAE K., GINI M. Design and implementation of a secure multi-agent marketplace. En: Electronic Commerce Research and Applications 3 355–368, 2004.
[5] REAIDYA J., MASSOTTEA P., DIEP D., “Comparison of negotiation protocols in dynamic agent-based manufacturing systems”. International journal of production economics. 2003
[6] ANUMBA C.J., REN Z., THORPE A., UGWU O., NEWNHAM L. Negotiation within a multi-agent system for the collaborative design of light industrial buildings. En: Advances in Engineering Software 34 389–401, 2003.
[7] BEER M., D’INVERNO M., LUCK M., JENNINGS N., PREIST C., AND SCHROEDER M.. “Negotiation In Multi-Agents Systems”. 1999.
[8] FIPA (Foundation Intelligent Physical Agents) www.fipa.org. 2005.
[9] REAIDYA J., MASSOTTEA P., DIEP D., “Comparison of negotiation protocols in dynamic agent-based manufacturing systems”. International journal of production economics. 2003.
[10] ZHANG W., WANG, G., MAILLER R., LESSER V. “Analysis of negotiation protocols by distributed search”. Distributed Sensor Networks: A multiagent perspective. 2003.
[11] BEN-AMEUR H., CHAIB-DRAA B. AND KROPF P., “Multi-Item Auctions for Automatic Negotiation”. Cirano. Scientific Series s-68 ISSN 1198-8177. 2002.
[12] BELLIFEMINE F., POGGI A. AND RIMASSA G. “JADE–A FIPA-compliant agent framework”, Italy.
[13] IGLESIAS C. “Definición de una metodología para el desarrollo de sistemas multiagentes”. Tesis doctoral. Departamento de ingeniería de sistemas Telemáticos, Universidad politécnica de Madrid, pp. 322, 1998.
[14] WURMAN PETER R., WALSH WILLIAM E., WELLMAN MICHAEL P. “Flexible Double Auctions For Electronic Commerce: Theory And Implementation.” University of Michigan. 1998.