Story Transcript
´cnica Superior de Escuela Te ´ tica Ingenier´ıa Informa
´ gica, Computacio ´n Departamento de Lo e Inteligencia Artificial Proyecto fin de carrera
MercadosP2P con Sistemas Multiagente. Aplicaci´ on a la compra-venta de productos agr´ıcolas
Autor: David Sol´ıs Mart´ın
Tutores: D. Joaqu´ın Borrego D´ıaz D. Gonzalo A. Aranda Corral
Sevilla, Viernes 1 de Septiembre de 2014
´Indice general
Lista de figuras
IX
Lista de tablas
XIII
Introducci´ on
1
1.
Motivaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
2.
Descripci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
3.
Estado del arte . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
4.
Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
5.
Prueba de la aplicaci´on . . . . . . . . . . . . . . . . . . . . . . .
4
6.
Estructura de la Memoria . . . . . . . . . . . . . . . . . . . . .
5
1. Teor´ıa de subastas
9
1.
Evoluci´on de la subastas . . . . . . . . . . . . . . . . . . . . . .
9
2.
Tipos de subastas y sus caracter´ısticas . . . . . . . . . . . . . .
10
2. Sistemas multiagente 1.
13
Clasificaci´on de los agentes . . . . . . . . . . . . . . . . . . . . .
14
1.1.
Clasificaci´on seg´ un sus propiedades principales . . . . . .
14
1.2.
Clasificaci´on seg´ un sus caracter´ısticas individuales . . . .
15
V
1.3.
Clasificaci´on seg´ un el modo de relacionarse . . . . . . . .
15
2.
Ciclo de vida de un agente . . . . . . . . . . . . . . . . . . . . .
16
3.
Sistemas multi-agente (SMA) . . . . . . . . . . . . . . . . . . .
18
3.1.
Arquitecturas est´andares de SMA . . . . . . . . . . . . .
22
3.2.
Comunicaci´on entre agentes . . . . . . . . . . . . . . . .
25
3. Metodolog´ıas de desarrollo de SMA. Plataformas 1.
2.
Ingenier´ıa de Agentes . . . . . . . . . . . . . . . . . . . . . . . .
41
1.1.
INGENIAS . . . . . . . . . . . . . . . . . . . . . . . . .
42
1.2.
MaSE . . . . . . . . . . . . . . . . . . . . . . . . . . . .
43
1.3.
Prometheus . . . . . . . . . . . . . . . . . . . . . . . . .
45
1.4.
Tropos . . . . . . . . . . . . . . . . . . . . . . . . . . . .
46
1.5.
PASSI . . . . . . . . . . . . . . . . . . . . . . . . . . . .
48
Plataformas de Sistemas Multi-Agente . . . . . . . . . . . . . .
49
4. Desarrollo del sistema 1.
2.
3.
41
57
Descripci´on del sistema . . . . . . . . . . . . . . . . . . . . . . .
57
1.1.
El sistema de subastas . . . . . . . . . . . . . . . . . . .
60
Dise˜ no del sistema . . . . . . . . . . . . . . . . . . . . . . . . .
61
2.1.
Modelo de datos . . . . . . . . . . . . . . . . . . . . . .
62
2.2.
Aplicaci´on web: dise˜ no y manual de uso. . . . . . . . . .
63
2.3.
Aplicaci´on m´ovil . . . . . . . . . . . . . . . . . . . . . .
66
2.4.
Sistema multiagente . . . . . . . . . . . . . . . . . . . .
66
Despliegue del sistema . . . . . . . . . . . . . . . . . . . . . . .
76
5. Resultados y conclusiones
79 VI
1.
Generaci´on de datos de prueba
. . . . . . . . . . . . . . . . . .
79
2.
Todos los compradores con la misma estrategia . . . . . . . . . .
80
2.1.
Orden por menor precio de salida . . . . . . . . . . . . .
80
2.2.
Orden aleatorio . . . . . . . . . . . . . . . . . . . . . . .
82
2.3.
Orden de cercan´ıa al agricultor . . . . . . . . . . . . . .
82
2.4.
El generoso . . . . . . . . . . . . . . . . . . . . . . . . .
83
3.
Diferentes estrategias conjuntas . . . . . . . . . . . . . . . . . .
84
4.
Los transportistas . . . . . . . . . . . . . . . . . . . . . . . . . .
84
4.1.
85
Totales . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6. Trabajo futuro
91
1.
Servicio de notificaciones . . . . . . . . . . . . . . . . . . . . . .
91
2.
La interfaz web . . . . . . . . . . . . . . . . . . . . . . . . . . .
91
3.
Sistema multiagente . . . . . . . . . . . . . . . . . . . . . . . .
92
3.1.
C´alculo de rutas . . . . . . . . . . . . . . . . . . . . . . .
92
3.2.
VRP (Vehicule Routing Problem) . . . . . . . . . . . . .
92
3.3.
Subasta de m´ ultiples intereses . . . . . . . . . . . . . . .
93
3.4.
Problema del rechazo . . . . . . . . . . . . . . . . . . . .
93
Bibliograf´ıa
94
VII
´Indice de figuras 1.
Evoluci´on interanual del IPOD (Junio 2014) . . . . . . . . . . .
2
2.1. Ciclo de vida de un agente (FIPA . . . . . . . . . . . . . . . . .
16
2.2. Diagrama de una arquitectura gen´erica de un agente BDI . . . .
20
2.3. Arquitectura de subsunci´on . . . . . . . . . . . . . . . . . . . .
21
2.4. Arquitecturas por capas . . . . . . . . . . . . . . . . . . . . . .
22
2.5. Modelo de referencia del est´andar FIPA . . . . . . . . . . . . . .
25
2.6. Protocolo FIPA Request [6] . . . . . . . . . . . . . . . . . . . .
31
2.7. Protocolo FIPA-Cancel-Meta-Protocol [6] . . . . . . . . . . . . .
32
2.8. Protocolo FIPA Request-When [6] . . . . . . . . . . . . . . . . .
33
2.9. Protocolo FIPA Propose [6] . . . . . . . . . . . . . . . . . . . .
34
2.10. Protocolo FIPA Contract-Net [6] . . . . . . . . . . . . . . . . .
34
2.11. Protocolo FIPA Iterated Contract Net [6] . . . . . . . . . . . . .
35
2.12. Protocolo FIPA Subscribe [6] . . . . . . . . . . . . . . . . . . .
36
2.13. Protocolo FIPA English Auction [6] . . . . . . . . . . . . . . . .
37
2.14. Protocolo FIPA Dutch Auction [6] . . . . . . . . . . . . . . . . .
38
2.15. Protocolo FIPA Brokering [6] . . . . . . . . . . . . . . . . . . .
39
2.16. Protocolo FIPA Recruit [6] . . . . . . . . . . . . . . . . . . . . .
40
3.1. INGENIAS Development Kit (IDK) . . . . . . . . . . . . . . . .
43
IX
3.2. Herramienta agentTool . . . . . . . . . . . . . . . . . . . . . . .
44
3.3. Herramienta Prometheus Design Tool (PDT) . . . . . . . . . . .
45
3.4. Metodolog´ıa Prometheus . . . . . . . . . . . . . . . . . . . . . .
46
3.5. Fase de requisitos iniciales Tropos. [15] . . . . . . . . . . . . . .
47
3.6. Fase y etapas PASSI [16] . . . . . . . . . . . . . . . . . . . . . .
48
3.7. Modelo parcial de JADE . . . . . . . . . . . . . . . . . . . . . .
52
3.8. Metodolog´ıas de desarrollo de SMA [10] . . . . . . . . . . . . . .
53
4.1. Diagrama de sistema . . . . . . . . . . . . . . . . . . . . . . . .
58
4.2. Esquema del proceso de subastas llevado a cabo por el SMA . .
61
4.3. Modelo de datos . . . . . . . . . . . . . . . . . . . . . . . . . . .
62
4.4. Direcciones. A la izquierda la lista de direcciones, a la derecha la edici´on de una direcci´on. . . . . . . . . . . . . . . . . . . . . . .
64
4.5. Alertas y notificaciones. A la izquierda las notificaciones de un agricultor, en la parte central las notificaciones de un comprador, y la derecha las notificaciones de un transportista. . . . . . . . .
64
4.6. Cosechas. A la izquierda la pantalla de lista de cosechas, a la derecha la pantalla de edici´on de una nueva cosecha. . . . . . . .
65
4.7. Ventas del agricultor. A la izquierda las ventas programadas, en la parte centra la ventas realizadas y a la derecha la pantalla de edici´on de una venta programada. . . . . . . . . . . . . . . . . .
66
4.8. Transportes. A la izquierda los transportes programados (reglas), en la parte central los transportes pendientes de ser entregados y a la izquierda la edici´on de un nuevo transporte programado (regla). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
67
4.9. Compras. En la parte superior izquierda las reglas de compra activa y en la parte inferior las reglas de compra que han sido ya usadas por una oferta aceptada. A la izquierda la edici´on de una regla de compra. . . . . . . . . . . . . . . . . . . . . . . . . . .
68
4.10. Compras realizadas. . . . . . . . . . . . . . . . . . . . . . . . . .
69
X
4.11. Notificaciones al comprador. . . . . . . . . . . . . . . . . . . . .
70
4.12. Diagrama de secuencia b´asico del SMA . . . . . . . . . . . . . .
71
4.13. Diagrama de estados del sistema de turnos . . . . . . . . . . . .
72
4.14. Agentes y comportamientos del MSA . . . . . . . . . . . . . . .
73
4.15. Diagrama de estados del rol Iniciador en la subasta inglesa . . .
75
4.16. Diagrama de estados del rol Participante en la subasta inglesa .
76
5.1. Distribuci´on de los datos de prueba . . . . . . . . . . . . . . . .
80
5.2. Evoluci´on de la ventas con todos los agentes siguiendo la estrategia de participar primero en las subastas con menor precio de salida. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
83
5.3. Evoluci´on de la ventas con todos los agentes siguiendo la estrategia aleatoria de participaci´on en las subastas. . . . . . . . . .
84
5.4. Evoluci´on de la ventas con todos los agentes siguiendo la estrategia de participar primero en las subastas cuyos agricultores est´an m´as cerca. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
85
5.5. Media del coste de transporte por estrategia. . . . . . . . . . . .
85
5.6. Evoluci´on de ventas con los agentes siguiendo la estrategia generosa. 86 5.7. Evoluci´on de la ventas con distribuciones de las estrategias en las que predomina una de ellas. . . . . . . . . . . . . . . . . . . . .
87
5.8. Evoluci´on de la ventas frente al beneficio de los transportistas. .
88
5.9. Ventas medias de los agricultores por estrategia. . . . . . . . . .
89
5.10. Ganancias medias de los transportistas por estrategia. . . . . . .
89
XI
´Indice de cuadros ´Indice de precios en el origen y destino de los alimentos (Junio 2014) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
Par´ametros de las reglas de los agricultores generadas autom´aticamente por el sistema . . . . . . . . . . . . . . . . . . . . . . .
7
2.1. Categor´ıa de los actos comunicativos FIPA . . . . . . . . . . . .
27
2.2. Par´ametros de un mensaje ACL . . . . . . . . . . . . . . . . . .
29
2.3. Par´ametros de un mensaje KQML . . . . . . . . . . . . . . . . .
30
5.1. Reglas de venta de los agricultores . . . . . . . . . . . . . . . . .
81
5.2. Reglas de los transportistas . . . . . . . . . . . . . . . . . . . .
82
5.3. Ejemplo de 10 reglas de compra generadas aleatoriamente . . . .
82
1. 2.
XIII
Introducci´ on
1.
Motivaci´ on
Creo que es indudable que para cualquiera que tenga la posibilidad de crear algo, en base a los conocimientos adquiridos durante su formaci´on y/o durante el desarrollo de un proyecto concreto, que adem´as pueda contribuir a una mejora global supone una gran satisfacci´on. Aun m´as, si este trabajo puede derivar en un producto que sea el germen de una futura empresa. Es el caso de este proyecto, cuyo objetivo como veremos en m´as en detalle posteriormente, es el de posibilitar que elementos de primera necesidad como son los alimentos agr´ıcolas est´en al alcance de todos y que adem´as sea justo para todos: productores, consumidores y transportistas. La motivaci´on de plantear el presente proyecto se basa en estudiar si mediante la tecnolog´ıa multiagente es posible descentralizar mercados fuertemente centrados.
2.
Descripci´ on
Es bien conocida la problem´atica existente entre los productores agr´ıcolas y los intermediarios. Existen multitud de noticias, tanto en prensa escrita como en televisi´on, donde se pone de manifiesto el incremento del precio de los productos agr´ıcolas, desde que estos salen de su zona de producci´on hasta que llegan al consumidor final al pasar por uno o varios intermediarios. Y no es u ´nicamente el consumidor final el afectado por este incremento de precio, sino que los productores agr´ıcolas vienen avisando de los bajos precios a los que se les compra el producto, incluso no llegando a sufragar el gasto de producci´on, lo que evidentemente lleva a un abandono progresivo del campo por parte de 1
2
Figura 1: Evoluci´on interanual del IPOD (Junio 2014)
1
los agricultores. Como bien dice David Borda, responsable de fruta dulce de COAG: ”Los productores nos encontramos completamente expuestos al mercado, padeciendo las presiones de la gran distribuci´on y de las importaciones a bajo precio y debemos afrontar crisis de precios m´as frecuentes, menos predecibles y m´as virulentas” En la tabla 1 se puede apreciar el incremento del precio que se produce en los productos al llegar a su lugar de destino, en especial en ciertos productos como son el calabac´ın, la berenjena, la naranja, etc. En la figura 1 podemos ver la tendencia creciente que viene sufriendo este ´ındice en el a˜ no 2014. En este trabajo se pretende dar un soluci´on a esta situaci´on mediante un sistema que ayude a agricultores y consumidores a no depender de esos intermediarios que incrementan el precio de un producto de primera necesidad de
3. Estado del arte
3
manera tan abrumadora. La soluci´on que presentamos pasa por descentralizar el proceso, creando un mercado donde los distintos agentes pueden interaccionar sin intermediarios. Ese mercado est´a dise˜ nado sobre una plataforma multiagente.
3.
Estado del arte
La red ARCO (Agricultura de Responsabilidad Compartida), impulsada por la Coordinadora de Organizaciones de Agricultores y Ganaderos (COAG2 ) y financiada mediantes fondos FEADER (Fondo Europeo Agr´ıcola de Desarrollo Rural) y por el Ministerio de Agricultura, Alimentaci´on y Medio Ambiente en diversos puntos de la geograf´ıa espa˜ nola, apuesta por un pacto entre productores y consumidores para construir un modelo de explotaci´on sostenible. Sus principios son sencillos: buscar la formaci´on de grupos de consumidores (familias, vecinos o compa˜ neros de trabajo) que realizan pedidos fijos, ya sea semanal, quincenal o mensualmente, a grupos de agricultores o ganaderos. La idea es buena, pero desde esta plataforma3 u ´nicamente se aporta, desde el punto de vista tecnol´ogico, un directorio web para poder contactar con los agricultores telef´onicamente. Otro portal que va en esta misma l´ınea es naranjasyfrutas.com4 . Igualmente se trata de una base de datos que te permite buscar un producto concreto, seleccionando su variedad, a qu´e tratamientos a estado sometido, as´ı como el lugar de procedencia y el periodo de recolecci´on. B´asicamente es un localizador de cosechas. Como ejemplo del tama˜ no de la base de datos, si buscamos cosechas de naranjas, se encuentran 603 producciones. MASFIT es un sistema de subastas de pescado por internet, desarrollado por AUTEC mediante el convenio IIIA-CSIC (Instituto de Investigaci´on en IA del Consejo Superior de Investigaciones Cient´ıficas) y usado en Mercapesca5 . Este interconecta las subastas de pescado fresco y congelado que tienen lugar en las lonjas asociadas, permitiendo en tiempo real, acceder a las subastas de pescado en dichas lonjas sin necesidad de estar pendiente de la subasta (agentes de software realizar´an las acciones de puja previamente definidas) compitiendo con los compradores presentes. Esta u ´ltima plataforma adopta t´ecnicas y tecnolog´ıas multiagente, como en el presente trabajo. 2
http://www.coag.org http://www.arcocoag.org 4 http://www.naranjasyfrutas.com 5 http://www.mercapesca.net 3
4
4.
Objetivos
Se pretende dise˜ nar y desarrollar un sistema que permita de una forma sencilla la compra-venta de productos agr´ıcolas y su posterior transporte sin la necesidad de la intermediaci´on de terceros que incrementan el precio. Para ello, se ha optado por un modelo de subastas, similar al usado en las lonjas. Dicho sistema de subastas se modelar´a mediante un sistema multiagente (SMA en adelante). Los sistemas de cara al usuario final ser´an una aplicaci´on web, como soluci´on gen´erica para la interacci´on con el sistema de subastas, una aplicaci´on m´ovil desarrollada para el sistema operativo Android. Mediante el sistema de notificaciones se dar´a una mayor flexibilidad a los usuarios a la hora de participar en la subastas.
5.
Prueba de la aplicaci´ on
Si se quiere probar la aplicaci´on, se ha instalado todo el sistema en http: //mowento.cs.us.es/mercadosp2p. Al acceder con un dispositivo Android, se le dar´a la opci´on de descarga de la aplicaci´on. Una vez instalada solo es necesario indicar el rol (comprador, agricultor o transportista) y un nombre. En el cap´ıtulo 4, en la subsecci´on 2.2.2 de la secci´on dise˜ no del sistema, se puede encontrar una descripci´on de todas las partes de la aplicaci´on que puede ser usada como manual de uso. Dado que es necesario un n´ umero m´ınimo de agentes para poder hacer funcionar el sistema de subastas, este genera autom´aticamente un conjunto de reglas de todos los roles. En concreto todas la reglas de los agricultores y de los compradores son para naranjas barberinas. En la tabla 2 se muestra los par´ametros de la reglas de los agricultores que genera el sistema. En base a ´esta, si se crea una regla para un comprador y se quiere tener una alta probabilidad de conseguir un acuerdo, habr´ıa que configurarla por ejemplo con m´as de 100 kilogramos de naranjas barberinas, de calibre entre 1 y 5 y un precio m´aximo de 40 cents.
6. Estructura de la Memoria
6.
5
Estructura de la Memoria Esta memoria est´a dividida en los siguientes cap´ıtulos:
Introducci´ on. Se describe el trabajo a realizar y la motivaci´on que ha llevado a su desarrollo. Tambi´en se dan unos apuntes a tener en cuenta para probar el sistema. 1. Teor´ıa de subastas. Breve introducci´on a la teor´ıa de subastas. Se har´a un repaso hist´orico de las subastas y se expondr´an los principales tipos de subasta. 2. Sistemas multiagente. Los SMA son la base del sistemas de subastas desarrollado en este trabajo. Se dar´a una descripci´on de los agentes, su ciclo de vida y de las distintas arquitecturas y est´andares de SMA. Tambi´en se repasar´an algunas de las metodolog´ıas de desarrollo de SMA y las herramientas y APIs para la creaci´on de SMA m´as actuales. 3. Desarrollo de la aplicaci´ on. Se describen los sistemas desarrollados en este trabajo. 4. Resultados Experimentales. Se presentan los resultados de los experimentos realizados. Se plantean problemas que han surgido y se analizan las soluciones tomadas. 5. Trabajo Futuro. Se plantean futuras ampliaciones del sistema y l´ıneas de trabajo futuro en este campo.
6
PRODUCTO PATATA CEBOLLA AJO REPOLLO COLIFLOR CALABAC´ IN ˜ ON ´ CHAMPIN ´ BROCOLI ACELGA BERENJENA TOMATES DE ENS. ZANAHORIA PIMIENTO VERDE PIMIENTO ROJO PEPINO LECHUGA* ´ PLATANO AGUACATE ´ MELON SAND´IA ´ MELOCOTON NECTARINA CIRUELA ALBARICOQUE CEREZA NARANJA ´ LIMON
PRECIO ORIGEN (e/kg) 0.16 0.22 0.95 0.13 0.37 0.12 1.06 0.39 0.40 0.18 0.51 0.35 0.49 0.95 0.18 0.12 0.60 1.51 0.24 0.16 0.57 0.56 0.55 0.68 1.25 0.17 0.52
PRECIO DESTINO (e/kg) 0.70 1.00 5.28 1.18 1.41 1.26 3.60 2.01 1.85 1.47 1.81 0.99 1.85 1.99 1.27 0.86 1.82 3.77 1.38 0.95 2.31 2.24 2.70 2.67 3.78 1.31 1.72
No de veces inc.
% inc.
4.38 4.55 5.56 9.08 3.81 10.50 3.40 5.15 4.63 8.17 3.55 2.83 3.78 2.09 7.06 7.17 3.03 2.50 5.75 5.94 4.05 4.00 4.91 3.93 3.02 7.71 3.31
338 % 355 % 456 % 808 % 281 % 950 % 240 % 415 % 363 % 717 % 255 % 183 % 278 % 109 % 606 % 617 % 203 % 150 % 475 % 494 % 305 % 300 % 391 % 293 % 202 % 671 % 231 %
Cuadro 1: ´Indice de precios en el origen y destino de los alimentos (Junio 2014)
6. Estructura de la Memoria
Kg. Min 77 72 66 95 67 81 65 49 84 97 52 76 38 72 42 56 38 33 53 27
7
Precio min. (cents/kg) Calibre 9 3 15 3 13 4 8 1 13 3 9 5 12 4 9 5 14 4 12 4 15 2 15 1 9 5 8 2 12 5 10 2 11 4 9 4 11 5 15 2
Cuadro 2: Par´ametros de las reglas de los agricultores generadas autom´aticamente por el sistema
Cap´ıtulo 1 Teor´ıa de subastas
En esta secci´on se har´a un breve repaso a la evoluci´on hist´orica de las subastas y los tipos de subastas m´as conocidos y estudiados.
1.
Evoluci´ on de la subastas
El uso de la subasta se remonta a la ´epoca Babil´onica, donde no se permit´ıa a los padres dar sus hijas en matrimonio al hombre de su elecci´on, sino que estas eran subastadas en la plaza del pueblo. Se comenzaba por la mujer considerada ”m´as guapa”que era asignaba a quien realizaba la mayor oferta por ella. En la Grecia antigua se utilizaban las subastas para llevar a cabo las concesiones de minas, y en la ´epoca romana es cuando adquiere una mayor difusi´on y empieza a ser usada con cierta regularidad. Se usaba la subasta para vender bienes confiscados, los botines de guerras y los esclavos. La palabra ”subasta”(y tambi´en ”auction”) proceden del lat´ın. Cuando se iba a subastar un bot´ın, se clavaban lanzas (”hasta” en lat´ın) alrededor del lugar de celebraci´on, as´ı la subasta se llevaba a cabo bajo lanza (”sub hasta”). La palabra inglesa tiene su origen en los incrementos (”auctio”) de precios en la subasta inglesa. Pero no es hasta el siglo XVII cuando adquiere una mayor importancia y comienzan a aparecer nuevos m´etodos como la subasta holandesa, la subasta descendente y la limitaci´on de tiempo para la presentaci´on de ofertas. En el siglo XX el n´ umero de transacciones realizadas por medio de subastas ha sido de importancia capital y se ha venido aplicando a muy diversos vienes 9
10
Cap´ıtulo 1. Teor´ıa de subastas
y servicios. Por ejemplo, el estado ha adquirido gran importancia al realizar la contrataci´on de servicios y vendiendo bienes de diversos or´ıgenes mediante subasta. Igualmente a finales del siglo XX se comienza a usar internet como un soporte fundamental en las subastas. En 2001 eBay contaba con 42 millones de usuarios y subastaba 1 mill´on de art´ıculos por d´ıa. Internet ha puesto la subasta al alcance de cualquiera que tenga un ordenador o m´ovil con conexi´on a Internet Aunque la subasta se viene usando desde tiempos remotos, no es hasta mediados del siglo XX cuando se empiezan a publicar trabajos analizando y estudiando los mecanismos de la subasta. Vickey?? es el primero en usar el equilibrio de la Teor´ıa de juegos como an´alisis de la subasta, y es a mediados de los a˜ nos ochenta cuando se produce un auge en la investigaci´on de la subastas.
2.
Tipos de subastas y sus caracter´ısticas
Las subastas tienen sentido cuando el vendedor desconoce las cantidades que los compradores est´an dispuestos a pagar. Si las conociera u ´nicamente tendr´ıa que ofrecer el producto al comprador que estuviera dispuesto a pagar el mejor precio. Por tanto, la incertidumbre en el valor del producto por parte de los compradores y vendedores es una caracter´ıstica inherente de la subasta. En este sentido podemos establecer los siguientes caracter´ısticas de la subasta: Determinan el precio de mercado de productos que pueden fluctuar o que no se comercian con regularidad. Asignan un producto a quien m´as lo valora. Maximizan los ingresos del vendedor. Transparencia y objetividad. La literatura suele considerar 4 tipos de subastas b´asicos: Subasta ascendente o inglesa. Se trata de la subasta m´as usada. El precio se va incrementando sucesivamente hasta que u ´nicamente queda un comprador dispuesto a pagar el u ´ltimo precio aceptado por ´el mismo. El incremento del precio puede venir dado por los propios compradores que
2. Tipos de subastas y sus caracter´ısticas
11
indican el siguiente precio que est´an dispuesto a pagar, por el vendedor o por un sistema automatizado. En el segundo caso, los compradores u ´nicamente deben indicar si est´an dispuestos a continuar dentro de la subasta o no. Subasta holandesa o descendente. Toma su nombre por ser el mecanismo usado en la venta de flores en Holanda. El precio comienza siendo muy alto y se va decrementado hasta que alg´ un comprador lo acepta. Subasta con sobre cerrado al primer precio. La pujas son entregadas en un sobre cerrado y gana la mayor oferta presentada. Hay que destacar que en este sistema no existen rondas y que adem´as no se conoce la oferta presentada por los dem´as compradores. Subasta con sobre cerrado al segundo precio o de Vickrey. Es igual a la anterior pero el precio a pagar ser´ıa el segundo m´as alto presentado. Se busca con este m´etodo obligar a los compradores a presentar ofertas con un valor verdadero. eBay, Google y Yahoo!’s usan variantes de este m´etodo. Si los compradores desconocen la valoraci´on de los dem´as se denomina subasta de valor privado. En este tipo de subastas la valoraci´on de los dem´as compradores potenciales no influyen en tu puja ya que esa valoraci´on es desconocida. Por tanto este tipo de subasta tiene mayor sentido cuando el bien subastado es para el consumo o uso por parte del comprador. Si la valoraci´on es la misma para todos, pero no es conocida estamos ante una subasta de valor com´ un, como ser´ıa el caso de la venta de un pozo de petr´oleo. En este trabajo, la subasta utilizada es la subasta inglesa con valor privado. No se va a tratar la teor´ıa de juegos en este trabajo. Solo, a modo de referencia, indicamos que este tipo de subasta cumple con el modelo de referencia, lo que implica que nos encontramos ante un juego con informaci´on incompleta (tambi´en llamados juegos bayesianos). Adem´as la estrategia o´ptima es muy sencilla: cada jugador debe seguir pujando hasta que el precio supere su valoraci´on. Estrategia o ´ptima en subasta inglesa: Si mi valoraci´on es v y otro comprador puede ganar con una puja a < v, deber´ıa estar dispuesto a pagar b, con a < b < v.
Cap´ıtulo 2 Sistemas multiagente
En esta secci´on veremos que es un agente y sus caracter´ısticas, as´ı como su ciclo de vida. Respecto a las sociedades de agentes, se repasar´an los distintos tipos de sistemas donde los agentes pueden convivir e interactuar. Por u ´ltimo mencionaremos las metodolog´ıas de desarrollo de sistemas multi-agente m´as actuales y aquellos entornos orientados a su implementaci´on.
Introducci´ on Con el notable avance de internet en las u ´ltimas d´ecadas, actualmente la programaci´on distribuida est´a en auge. Uno de los u ´ltimos modelos distribuidos que ha tenido una notable menci´on es la programaci´on en la nube (cloud computing), un tipo concreto de grid computing en el cual se proporcionan los recursos para poder dar servicios bajo demanda a trav´es de internet con la seguridad de ser escalable y fiable. En este mismo sentido la Inteligencia Artificial Distribuida estudia los sistemas distribuidos en los que intervienen m´ ultiples entidades aut´onomas que se comunican, cooperan y compiten entre ellos, considerando que una inteligencia colectiva puede ser m´as eficiente que la inteligencia de una sola entidad individual. El verbo en lat´ın agere significa llevar, construir, hacer y de su participio agens se deriva el termino agente, y expresa la capacidad de acci´on o actuaci´on de una entidad. En los negocios, un agente es considerado el que por oficio tiene capacidad de gestionarlos. Un Agente Software es capaz de percibir el 13
14
Cap´ıtulo 2. Sistemas multiagente
entorno, procesar las se˜ nales obtenidas y tomar decisiones o llevar a cabo acciones en funci´on de ´estas con el objetivo de mejorar el resultado. Como se ha mencionado anteriormente, la autonom´ıa (capacidad de tomar decisiones sin la supervisi´on de un ser humano) de los agentes es una las principales y m´as atractivas caracter´ısticas de los agentes. En [4] se establecen las principales caracter´ısticas que definen el comportamiento de un agente: Funcionamiento continuo y aut´onomo. Comunicaci´on en su entorno y con otros agentes existentes en ´el, a trav´es de un lenguaje o formalismo de comunicaci´on. Robustez: capacidad de reaccionar de forma apropiada ante situaciones excepcionales o fallos. Adaptabilidad, entendida como la capacidad de cumplir objetivos y tareas en diferentes contextos de forma flexible.
1.
Clasificaci´ on de los agentes
Los agentes pueden ser clasificados seg´ un sus caracter´ısticas generales, seg´ un el entorno en que trabajan, seg´ un su comportamiento, seg´ un el modo de organizaci´on y seg´ un su utilidad. Veremos las clasificaciones m´as importantes:
1.1.
Clasificaci´ on seg´ un sus propiedades principales
Tenemos dos clases en agentes en este caso: Agentes reactivos Caracterizados por ser capaces de interactuar con su entorno de forma din´amica, y de responder ante eventos no esperados (comportamiento no determinista). Agentes pro-activos Son agentes que intentan anteponerse a ciertos sucesos de cara a alcanzar objetivos, aprovechando diferentes oportunidades o alternativas de actuaci´on. Agentes sociales Si a˜ nadimos a un agente la capacidad de comunicarse y colaborar con otros agentes tendremos un agente social. A estos agentes se les reconoce diferentes tipos de habilidades sociales:
1. Clasificaci´ on de los agentes
15
1. Comunicaci´on: Es la capacidad de enviar y recibir mensajes de cara a alcanzar sus objetivos. La calidad de la comunicaci´on depender´a del n´ umero de mensajes necesarios, de su tama˜ no y la complejidad de estos. 2. Cooperaci´on: Es la habilidad para ofrecer y hacer uso de servicios ofertados por otros agentes. 3. Negociaci´on: Se refiere a la habilidad de un agente para resolver conflictos y alcanzar acuerdos con otros agentes, de cara a cumplir sus objetivos.
1.2.
Clasificaci´ on seg´ un sus caracter´ısticas individuales
Agentes reactivos Llevan a cabo acciones simples que pueden alterar su estado interno y/o de su entorno en funci´on de acciones recibidas (percepci´on). Los agentes reactivos no realizan procesos de razonamiento, y carecen de mecanismos de representaci´on de conocimiento. Agentes cognitivos Se puede decir que un agente cognitivo es individualmente inteligente, se comunica con otros agentes y tiene capacidad de razonamiento bajo su base de conocimiento.
1.3.
Clasificaci´ on seg´ un el modo de relacionarse
Seg´ un si el agente se relaciona dentro de un SMA o no con otros agentes y de que tipo de relaci´on se trata en caso de existir, los agentes se pueden clasificar en:
Agentes individuales Son agentes que no necesitan de la colaboraci´on de otros agentes para llevar a cabo sus funciones. Agentes cooperativos Estos agentes pueden realizar tareas en solitario o con la colaboraci´on de otros agentes. Los agentes negociadores, que tratan de poner de acuerdo a otros agentes para que puedan obtener un recurso que necesitan son un tipo de agentes cooperativos. Agentes competitivos Son agentes que compiten con otros agentes para conseguir un recurso limitado com´ un. Los agentes que intervienen en una subasta son de este tipo.
16
Cap´ıtulo 2. Sistemas multiagente
Figura 2.1: Ciclo de vida de un agente (FIPA)
2.
1
Ciclo de vida de un agente
El ciclo de vida de un agente viene determinado por el conjunto de estados que pueden llegar a alcanzar y las transiciones para pasar de un estado a otro. En la figura 2.1 se muestra el ciclo de vida de un agente seg´ un el est´andar FIPA (Foundation for Intelligent Physical Agents). El est´andar FIPA, que se ver´a con m´as detalle con posterioridad, es la propuesta m´as extendida y aceptada y que implementa JADE, el entorno de desarrollo de agentes usado en este trabajo.
Estados de un agente Vamos a describir cada uno de los estados por los puede pasar un agente: Iniciado. El agente se ha creado, pero a´ un se le ha asignado nombre ni
2. Ciclo de vida de un agente
17
direcci´on, ni ha sido registrado en el AMS (p´aginas blancas) por lo que no puede comunicarse con otros agentes. Activo. El agente ya ha sido registrado en el AMS, con un nombre y una direcci´on. Ahora ya puede intervenir en el proceso de subasta. Suspendido. El hilo de ejecuci´on del agente est´a detenido y no ejecuta ning´ un comportamiento. En espera. El agente est´a esperando alg´ un evento para continuar, como por ejemplo recibir un mensaje. Desconocido. El Agente ha sido eliminado. El hilo de ejecuci´on ha terminado y se ha eliminado del registro del AMS. Tr´ansito. Un Agente m´ovil entra en este estado mientras est´a migrando a una nueva localizaci´on. El sistema sigue guardando los mensajes en el buffer hasta que el agente vuelve a estar activo.
Transiciones entre estados Un agente cambia de estado a trav´es de transiciones (figura 2.1). En JADE estas transiciones pueden ser invocadas mediante la ejecuci´on de m´etodo del agente o ser capturadas por m´etodo que pueden ser sobrescritos. Crear. Creaci´on de un nuevo agente. Esta acci´on es realizada por el constructor del agente y puede ser capturada por el m´etodo setup(). Invocar. El agente pasa desde iniciado a activo. Suspender. Pone a un agente en suspenso. Puede ser invocado por el AMS o por el propio agente. El m´etodo que realiza esta acci´on es doSuspend(). Reanudar. Continua la ejecuci´on de un agente que se encontraba suspendido. Solo puede ser invocado por el AMS. ´ Esperar. Pone al agente en estado de espera. Unicamente lo puede invocar el agente. El m´etodo usado es doWait(). Despertar. Continua con la ejecuci´on de un agente que estaba en espera. Solo puede ser invocado por el AMS. El m´etodo que lo lleva a cabo es doWake().
18
Cap´ıtulo 2. Sistemas multiagente
Mover. Cambia el contenedor del agente. Solo puede ser iniciado por el agente. El m´etodo que lo invoca es doMove() y puede ser capturado con mediante beforeMove() y afterMove(). Ejecutar. Continua la ejecuci´on de un agente que estaba en tr´ansito. Solo lo puede iniciar el AMS. Destruir. Es la terminaci´on normal o forzosa del agente. El AMS es el u ´nico que lo puede invocar y no puede ser ignorado por el agente.
3.
Sistemas multi-agente (SMA)
Cuando tratamos con tareas complejas compuestas por multitud de subsistemas que interact´ uan entre s´ı, se hace interesante la opci´on de distribuir la inteligencia entre varios agentes y construir sistemas multiagente. Si cada subsistema tiene capacidad de decisi´on local, el problema de gesti´on se puede abordar definiendo pol´ıticas de cooperaci´on, coordinaci´on y negociaci´on entre agentes [4]. En general, un SMA presentar´a las siguiente caracter´ısticas:
1. Estar´a formado por un conjunto de agentes aut´onomos y especializados con las habilidades necesarias para llevar a cabo su objetivo. 2. El SMA tiene una misi´on com´ un que puede ser descompuesta en tareas independientes. 3. Cada agente tiene un conocimiento limitado.
Adem´as, los SMA facilitan el uso de informaci´on distribuida e incrementan la flexibilidad, escalabilidad, reutilizaci´on y mantenimiento del sistema. Cada arquitectura establece c´omo los agentes pueden reaccionar ante est´ımulos, comunicarse y actuar. Para ello definen una serie de m´odulos que interact´ uan entre s´ı. En funci´on del tipo de arquitectura pueden aparecer diferentes tipos de m´odulos como son de interacci´on, bases de conocimiento, interpretaci´on de la informaci´on, planificaci´on, comunicaci´on, cooperaci´on, etc. Existen multitud de arquitecturas, por lo que se resumir´an en este trabajo los tipos m´as importantes. La clasificaci´on m´as importante diferencia entre arquitecturas deliberativas, reactivas e h´ıbridas atendiendo al comportamiento que presentan los agentes, es decir, dependiendo del tipo de procesamiento.
3. Sistemas multi-agente (SMA)
19
Arquitecturas deliberativas
Hacen uso de la tradicional visi´on de los sistemas de Inteligencia Artificial para definir el entorno, las decisiones son tomadas mediante razonamiento l´ogico, haciendo uso del conocimiento con el que cuentan y modificando su estado interno. Por ejemplo, el agente destinado a determinar si tiene que abrir o cerrar un toldo puede disponer de un conjunto de predicados (su creencia o estado interno) en l´ogica de primer orden que se representar´ıan como Luz(23), TemperaturaActual(30), Humedad(baja), Viento(10) y el proceso de decisi´on estar´a modelado mediante un conjunto de reglas de deducci´on. La siguiente acci´on a realizar ser´a tomada de alguna de la reglas que puedan ser probadas con el estado interno actual. Este modelo tiene la desventaja del coste computacional de la demostraci´on de teoremas. Por otro lado la asunci´on de que el mundo no cambia durante el proceso de decisi´on, puede llevar a tomar una acci´on que se considera racional en el momento de comenzar el proceso y que ya no lo es una vez a terminado. La arquitectura deliberativa m´as estudiada es la arquitectura BDI (Belief, Desire, Intention).
Arquitectura BDI La arquitectura BDI (Belief, Desire, Intention) est´a inspirada en el estudio filos´ofico del razonamiento pr´actico - el proceso de decisi´on, momento a momento, de que acci´on llevar a cabo para conseguir nuestras metas. El modelo BDI proporciona soluciones en entornos cambiantes o inciertos, en los que los agentes s´olo tienen una visi´on parcial del problema y, posiblemente, manejen un n´ umero limitado de recursos. Las creencias representan el conocimiento que tiene el agente del mundo que lo rodea. Esta representaci´on puede ser mediante expresiones l´ogicas, bases de datos relacionales o variables. Las creencias son esenciales en estos sistemas y su buena gesti´on es vital para construir buenos agentes. Los deseos son igualmente esenciales y representan el estado final deseado. Para alcanzar los objetivos, es necesario definir un mecanismo de planificaci´on que nos permita identificar las intenciones. Las intensiones son simplemente un conjunto de caminos de ejecuci´on (hilos) que pueden ser interrumpidos para recibir informaci´on acerca del entorno [4].
20
Cap´ıtulo 2. Sistemas multiagente
Figura 2.2: Diagrama de una arquitectura gen´erica de un agente BDI Arquitecturas reactivas Debido a la necesidad de sistemas que puedan operar r´apidamente y en entornos din´amicos surgen arquitecturas en las que no es necesario una representaci´on simb´olica del entorno. Un ejemplo muy conocido es la arquitectura de subsunci´on mostrada en la figura 2.3. En estas arquitecturas, el proceso de decisi´on se realiza a trav´es de un conjunto de tareas organizadas jer´arquicamente de menor a mayor nivel de abstracci´on, com´ unmente denominadas comportamientos. Cada comportamiento puede disponer de una funci´on de acci´on que recibe como entrada una percepci´on del entorno y que act´ ua en consecuencia. Es en definitiva un sistema que se basa en mecanismos de respuestas a est´ımulos. Otra caracter´ıstica es que varios comportamientos pueden ser lanzados simult´aneamente, siendo necesario decidir prioridades para cada uno de los comportamientos para determinar cual debe ser ejecutado. La principal aplicaci´on de las arquitecturas reactivas ha sido en rob´otica, ya
3. Sistemas multi-agente (SMA)
21
Figura 2.3: Arquitectura de subsunci´on que los robots, considerados agentes reales, deben operar en entornos cambiantes, lo que dificulta el uso de arquitecturas deliberativas.
Arquitecturas h´ıbridas Los sistemas h´ıbridos pretenden aprovechar las ventajas de las anteriores arquitecturas combin´andolas, como por ejemplo teniendo dos subsistemas, uno simb´olico orientado a la planificaci´on y otro reactivo para atender a eventos imprevistos. Esto conlleva a una estructuraci´on en capas que pueden ser horizontal (todas las capas acceden a los sensores y actuadores) o vertical (solo una capa accede a los sensores y actuadores). Se suelen definir tres niveles:
Reactivo Este nivel suele ser implementado mediante una arquitectura de subsunci´on y es la que reacciona a los cambios del entorno. Conocimiento Normalmente usa representaci´on simb´olica para representar el conocimiento que el agente tiene del entorno. Social Se manejan los aspectos sociales del entorno, informaci´on de otros agentes, deseos, intenciones, etc.
22
Cap´ıtulo 2. Sistemas multiagente
Figura 2.4: Arquitecturas por capas
3.1.
Arquitecturas est´ andares de SMA
Cuando cada sistema SMA implementa su propia arquitectura aparecen problemas de interoperabilidad (posibilidad de intercambiar informaci´on y usar esta informaci´on entre dos sistemas) y extensi´on (anexar m´odulos adicionales al sistema que a˜ naden funcionalidad).
Arquitectura FIPA La especificaci´on FIPA esta compuesta por una colecci´on de est´andares, cuyo objetivo es promover la interacci´on de agentes heterog´eneos (facilitando la interacci´on entre agentes y sistemas de agentes a trav´es de diferentes plataformas de agentes de diferentes fabricantes) y los servicios que ellos pueden representar [6].
3. Sistemas multi-agente (SMA)
23
La especificaci´on FIPA est´a dividida en 5 grandes grupos: Aplicaciones Son ejemplos de ´areas de aplicaci´on en los que FIPA puede ser desarrollado: FIPA Nomadic Application Support Specificacion FIPA Quality of Service Specificacion FIPA Personal Travel Assistance Specification FIPA Audio-Visual Entertainment and Broadcasting Specification FIPA Network Management and provisioning Specification FIPA Personal Assistant Specification FIPA Message Buffering Service Specification De las cuales u ´nicamente las dos primeras est´an estandarizadas, siendo el resto experimentales. Arquitectura abstracta Tiene estatus de est´andar y aborda las entidades abstractas que son necesarias para desarrollar servicios y entornos de agentes. Esta compuesta por las especificaciones: FIPA Abstract Architecture Specification FIPA Domains and Policies Specification De las cuales la primera tiene estatus de est´andar y la segunda a quedado en desuso aunque mantiene el estatus preliminar. Comunicaci´ on Aborda el formato de los mensajes del lenguaje de comunicaci´on de los agentes (ACL), los protocolos de interacci´on, los actos comunicativos y el lenguaje de contenido. Dentro de los protocolos de comunicaci´on se definen los siguientes est´andares: FIPA Request Interaction Protocol Specification FIPA Query Interaction Protocol Specification FIPA Request When Interaction Protocol Specification FIPA Contract Net Interaction Protocol Specification FIPA Iterated Contract Net Interaction Protocol Specification FIPA Brokering Interaction Protocol Specification
24
Cap´ıtulo 2. Sistemas multiagente
FIPA Recruiting Interaction Protocol Specification FIPA Subscribe Interaction Protocol Specification FIPA Propose Interaction Protocol Specification y las subastas holandesa e inglesa mantienen el estatus de experimentales: FIPA English Auction Interaction Protocol Specification FIPA Dutch Auction Interaction Protocol Specification de los cuales veremos m´as adelante el protocolo de subasta inglesa ya que es el usado en este trabajo. Con respecto a los actos comunicativos solo existe la recomendaci´on FIPA Communicative Act Library Specification y en relaci´on a los lenguajes de comunicaci´on u ´nicamente el lenguaje SL tiene consideraci´on de est´andar, el resto (CCL, KIF y RDF) est´an en estado experimental. Gesti´ on de agentes Aborda el control y manejo de agentes dentro y a trav´es de diferentes plataformas. Define las siguiente especificaciones: FIPA Agent Management Specification FIPA Agent Discovery Service Specification FIPA JXTA Discovery Middleware Specification Siendo est´andar u ´nicamente la primera y en la que especifican que componentes puede y/o debe poseer el sistema. Agentes. Define a los agentes como procesos computacionales aut´onomos, con capacidad de comunicaci´on haciendo uso de ACL (Agent Communication Language) y que debe disponer de un identificador u ´nico (AID) dentro del universo de los agentes. Facilitador de Directorio (DF). Es un elemento opcional que proporciona el servicio de p´aginas amarillas al resto de los agentes. Cada agente puede registrar sus servicios en el DF o buscar a otros agentes que ofrezcan un servicio determinado. Se trata de un servicio de p´aginas amarillas. Sistema de Gesti´ on de Agentes (AMS). Es el componente principal de la AP y ofrece el servicio de p´aginas blancas. Cada agente debe registrarse en un AMS para poder obtener un AID v´alido. Ofrece servicios como creaci´on y eliminaci´on de agentes, gesti´on de los recursos y canales de comunicaci´on.
3. Sistemas multi-agente (SMA)
25
Figura 2.5: Modelo de referencia del est´andar FIPA Sistema de Transporte de Mensajes (MTS). Servicio encargado de transportar los mensajes FIPA-ACL entre agentes, ya sea dentro de la misma plataforma o entre plataformas diferentes. Plataforma de Agentes (AP). Es la infraestructura en la que se establecen y utilizan los agentes. El dise˜ no interno de esta plataforma se deja en manos de los desarrolladores (no forma parte del est´andar FIPA).
3.2.
Comunicaci´ on entre agentes
Como ya se coment´o anteriormente, para poder resolver la comunicaci´on distribuida entre agentes y SMA’s se hizo necesario estandarizar la comu-
26
Cap´ıtulo 2. Sistemas multiagente
nicaci´on, evitando as´ı que cada plataforma implementara un sistema de comunicaciones que fuera incompatible con otros. Veremos en este apartado los actos comunicativos y protocolos definidos por FIPA y mencionados anterior m´as en detalle. Actos comunicativos Dentro del campo de la comunicaci´on la la teor´ıa del acto del habla tiene una especial importancia. El fil´osofo del lenguaje, John Austin, establece que la comunicaci´on puede ser visto como un acto en si mismo. Un ejemplo t´ıpico es el del a´rbitro de un partido de f´ utbol que expulsa a un jugador. Este acto de ense˜ nar una tarjeta roja a un jugador, conlleva adem´as que se le retire a un jugador el permiso para entrar en terreno de juego. John Austin argumenta que toda comunicaci´on puede ser enunciado de una forma declarativa haciendo uso de determinados verbos (performatives). Por ejemplo una sentencia informativa como ”el avi´on aterrizar´a con un retraso de 30 min.” puede ser transformada a ”Informo de que el avi´on aterrizar´a con un retraso de 30 min.”. Igualmente una petici´on tal como ”Env´ıame las peticiones pendientes” puede ser vista como ”Solicito que me env´ıes las peticiones pendientes”. Este tipo de construcciones son muy importantes dentro de un SMA, ya que en ellas queda patente si se e´sta informando o se est´a solicitando algo, por lo es posible identificar el prop´osito principal del acto comunicativo (el tipo de mensaje) y separarlo del contenido proposicional. La recomendaci´on FIPA Communicative Act Library Specification, CAL de aqu´ı en adelante, especifica cada uno de los actos comunicativos. Estos pueden ser categorizados tal y como se aprecia en la tabla 2.1. Paso de informaci´ on inform. Se informa al receptor de que cierta preposici´on es verdadera. inform-ref. Se pide al receptor que se le informe sobre un objeto o conjunto de objetos cuya descripci´on coincide con una expresi´on referencial especificada en el contenido del mensaje. disconfirm. Se informa al receptor de que una preposici´on es falsa, cuando se conoce que este puede pensar que es verdadera. Solicitud de informaci´ on query-if. El emisor solicita al receptor que le informe si una preposici´on dada es cierta.
27
3. Sistemas multi-agente (SMA) Acto Comunicativo accept-proposal agree cancel call for proposal failure inform inform-if inform-ref disconfirm not-understood propose query-if refuse reject-proposal request request-when request-whenever subscribe
Paso de Inform.
Solicitud de Informaci´ on
Negociaci´ on
Acciones
Errores
X X X X X X X X X X X X X X X X X X
Cuadro 2.1: Categor´ıa de los actos comunicativos FIPA query-ref. Se solicita que le informe sobre el conjunto de objetos que cumple la expresi´on referencial indicada en el contenido del mensaje. subscribe. Se solicita que se informe de manera persistente (cada vez que se produzca un cambio) de un valor indicado mediante una expresi´on referencial. Realizaci´ on de acciones agree. Acepta la petici´on de llevar a cabo una acci´on cuando se cumpla cierta condici´on establecida. cancel. Indica que se cancele o detenga una acci´on previamente requerida. refuse. Se comunica el receptor que la acci´on indicada no se va llevar a cabo por la una raz´on indicada. request. Se solicita al receptor que lleve a cabo una acci´on determinada. El contenido del mensaje describe la acci´on. request-when. Se solicita al receptor que lleve cabo una acci´on cuando este considera que una preposici´on dada es cierta.
28
Cap´ıtulo 2. Sistemas multiagente
request-whenever. Se solicita al receptor que lleve a cabo una acci´on siempre que una preposici´on llegue a ser verdadera. Implica que si la proposici´on pasa a ser falsa y esta vuelve a ser verdadera se volver´a a llevar a cabo la acci´on.
Control de errores failure. Se informa del fallo al intentar llevar a cabo una acci´on. not-understood. Se indica al receptor de que se ha recibido una acci´on pero no se ha comprendido.
Negociaci´ on propose. El emisor propone llevar a cabo cierta acci´on siempre y cuando se cumpla cierta preposici´on. call for proposal. Se solicita el inicio de un proceso de negociaci´on para llevar a cabo una acci´on. accept-proposal. Acepta una propuesta previamente recibida. reject-proposal. Se rechaza la realizaci´on de una acci´on determinada durante la negociaci´on.
Est´ andares de comunicaci´ on Para que cada agente pueda interpretar los mensajes enviados entre ellos, es necesario que existe un est´andar que defina la estructura y contenido de los mensajes. Vamos a ver dos de los lenguajes m´as conocidos: ACL y KQML.
ACL (Agent Communication Language) En FIPA [6] podemos encontrar la especificaci´on de ACL (Agent Communication Language). Un mensaje ACL puede estar compuesto por uno o m´as par´ametros en funci´on de tipo de mensaje. El u ´nico par´ametro que es obligatorio es performative, que identifica el tipo de acto comunicativo (descritos en el apartado anterior), aunque lo m´as com´ un es que los par´ametros sender, receiver y content tambi´en est´en presentes. En la tabla 2.2 podemos ver la lista de par´ametros disponibles. Si un agente no reconoce alguno de los par´ametros o sus valores, puede responder con not-understood. FIPA deja libertad para hacer uso de los par´ametros.
29
3. Sistemas multi-agente (SMA)
Par´ ametro performative sender receiver content language encoding ontology protocol conversation-id reply-with in-reply-to reply-by
Tipo de par´ ametro Tipo de acto comunicativo Emisor Receptor Contenido del mensaje Descripcion del contenido Descripci´on del contenido Descripci´on del contenido Control de la conversaci´on Control de la conversaci´on Control de la conversaci´on Control de la conversaci´on Control de la conversaci´on
Cuadro 2.2: Par´ametros de un mensaje ACL KQML (Knowledge Query and Manipulation Language) Fue desarrollado en los a˜ nos 80 por el Knowledge-Sharing Effort esponsorizado por DARPA y como complemento a otros trabajos de representaci´on del conocimiento como las ontolog´ıas [5]. En KQML se divide en tres capas: Capa de contenido. KQML u ´nicamente tiene inter´es en identificar el inicio y final del mensaje. El contenido de este puede ser expresado en cualquier lenguaje. Capa de mensaje. Es el n´ ucleo de KQML y determina los tipos de iteraci´on, protocolos, ontolog´ıas y el acto de habla (performative). Capa de comunicacion. Identifica los par´ametros de m´as bajo nivel de la comunicaci´on (emisor, receptor e identificador del mensaje). Un mensaje KQML expresa la intenci´on de llevar a cabo alguna acci´on (performative o acto de habla) que puede contener los par´ametros indicados en la tabla 2.3
Protocolos de comunicaci´ on FIPA Para que la comunicaci´on cumpla su objetivo es necesario establecer un serie de reglas que establecen la sintaxis, sem´antica y sincronizaci´on de la comunicaci´on. Estas reglas deben ser independientes de su implementaci´on.
30
Cap´ıtulo 2. Sistemas multiagente
Par´ ametro :content :sender :receiver :language :ontology :reply-with :in-reply-to
Significado La informaci´on Emisor del mensaje Receptor del mensaje El nombre del lenguaje de representaci´on empleado en el atributo :content El nombre de la ontolog´ıa utilizada en el atributo :content Etiqueta para la respuesta (si es que el emisor la espera) La etiqueta esperada en la respuesta Cuadro 2.3: Par´ametros de un mensaje KQML
Veremos en este apartados varios protocolos que permiten a los agentes comunicarse dentro de un SMA. Se repasar´an los protocolos estandarizados en FIPA y mencionados anteriormente: subscribe, request, request-when, contractnet, iterated contract-net, los protocolos de subasta inglesa y alemana, brokering y recruiting. 1. Request El protocolo FIPA Request, descrito en la figura 2.6, permite a un agente llevar a cabo la petici´on de realizar una acci´on (en el sentido indicado anteriormente como una acto de habla) a otro agente. El agente participante (receptor) puede aceptar o rechazar la petici´on. En caso de ser aceptada, posteriormente el participante debe informar del ´exito o fallo de la acci´on. En cualquier momento el receptor puede indicar que no comprende o que no puede procesar (not-understood ) la comunicaci´on. En tal caso, el protocolo deber´ıa terminar. Igualmente, el iniciador de la comunicaci´on podr´ıa cancelar la petici´on en cualquier momento haciendo uso del protocolo FIPA-Cancel-Meta-Protocol 2.7. Se puede entender en tal caso que el iniciador de la petici´on ya no est´a interesado en la petici´on anteriormente realizada. 2. Request-When El protocolo FIPA Request-When, descrito en la figura 2.8, permite a un agente solicitar al receptor que realice una acci´on cuando una precondici´on dada sea verdadera. Si el receptor acepta la petici´on, se supone que ´este se compromete a realizar la acci´on nada m´as se cumpla la precondici´on. 3. Propose En este protocolo 2.9, un agente iniciador plantea a los receptores que ´el realizar´a las acciones descritas en el acto comunicativo propose cuando
3. Sistemas multi-agente (SMA)
31
Figura 2.6: Protocolo FIPA Request [6] ellos acepten esta propuesta. En el caso de aceptaci´on de la propuesta, es com´ un el llevar a cabo la acci´on y su posterior informaci´on del resultado. 4. Contract Net En este protocolo, descrito en la figura 2.10, el iniciador del protocolo indica una serie de acciones que desea ver realizadas por uno o m´as participantes. El protocolo se inicia mediante el acto comunicativo call for propose (cfp). Los participantes deber´an notificar su intensi´on de participaci´on antes de un deadline. Posteriormente el agente iniciador delegar´a las tareas en los agentes que han aceptado. 5. Iterated Contract Net Descrito en la figura 2.11, se trata de una extensi´on del protocolo FIPA
32
Cap´ıtulo 2. Sistemas multiagente
Figura 2.7: Protocolo FIPA-Cancel-Meta-Protocol [6] Contract Net, en la que se puede volver a proponer la realizaci´on de acciones, probablemente con caracter´ısticas modificadas. Para ello, primero se rechaza la propuesta de los participantes y posteriormente se emite un nuevo cfp. 6. Subscribe Este protocolo que podemos ver en la figura 2.12, permite a un agente indicar a otro que desea recibir informaci´on cada vez que un objeto referenciado cambie. El agente participante podr´a aceptar o rechazar la petici´on. En caso de ser aceptada, este deber´a notificar al agente iniciador de cualquier cambio mediante mensajes de tipo inform. 7. Subasta inglesa En la subasta inglesa el subastador (iniciador) va incrementando progresivamente el precio del objeto a vender hasta que no hay compradores (participants) interesados en pagar tal cantidad. El objeto ser´a vendido siempre y cuando supere un precio m´ınimo establecido por el vendedor. El comienzo de la subasta se notifica mediante un mensaje call for propose. Los participantes deber´an responder con un mensaje propose indicando si est´an o no de acuerdo en el precio actual y posteriormente el iniciador ir´a informando de los nuevos precios. El final de la subasta est´a regulado por un tiempo m´aximo sin recibir respuesta 8. Subasta holandesa En el protocolo de subasta holandesa, se parte de un valor inicial que se va decrementando hasta que es aceptado por alg´ un comprador.
3. Sistemas multi-agente (SMA)
33
Figura 2.8: Protocolo FIPA Request-When [6] 9. Brokering Este protocolo, representado en la figura 2.15, posibilita a un agente el trasladar un acto comunicativo a un agente broker que se encargar´a de buscar a otros agentes que ciertas capacidad que permitan llevar a cabo dicho acto. Un ejemplo com´ un es aquel en el cual se le solicita a un agente broker que busque ciertos agentes capaces de dar respuesta a una query. 10. Recruit ´ Un agente recruit es un tipo de broker. Unicamente se diferencia del protocolo anterior en que el receptor de final de la interacci´on puede no ser el agente iniciador de ´esta.
34
Cap´ıtulo 2. Sistemas multiagente
Figura 2.9: Protocolo FIPA Propose [6]
Figura 2.10: Protocolo FIPA Contract-Net [6]
3. Sistemas multi-agente (SMA)
Figura 2.11: Protocolo FIPA Iterated Contract Net [6]
35
36
Cap´ıtulo 2. Sistemas multiagente
Figura 2.12: Protocolo FIPA Subscribe [6]
3. Sistemas multi-agente (SMA)
Figura 2.13: Protocolo FIPA English Auction [6]
37
38
Cap´ıtulo 2. Sistemas multiagente
Figura 2.14: Protocolo FIPA Dutch Auction [6]
3. Sistemas multi-agente (SMA)
Figura 2.15: Protocolo FIPA Brokering [6]
39
40
Cap´ıtulo 2. Sistemas multiagente
Figura 2.16: Protocolo FIPA Recruit [6]
Cap´ıtulo 3 Metodolog´ıas de desarrollo de SMA. Plataformas 1.
Ingenier´ıa de Agentes
Existen entornos de desarrollo que proporcionan una soluci´on parcial al modelado de comportamientos y a la coordinaci´on de agentes como son la gesti´on de agentes, librer´ıas de algoritmos, localizaci´on de agentes y movilidad. JADE, Grasshopper, ABLE, ZEUS y agentTool son algunas de estos entornos. Aunque estos entornos facilitan el trabajo, se hace necesario un proceso de desarrollo especializado para agentes, por lo que surge la Ingenier´ıa del Software Orientado a Agentes (AOSE). El Proceso Unificado de Jacobson para sistemas orientados a objetos y otras como CommonKADS orientados a sistemas de gesti´on del conocimiento no tienen en cuenta las necesidades espec´ıficas de un SMA como son su car´acter distribuido, la planificaci´on de tareas, el intercambio de mensajes mediante lenguajes orientados a agentes, etc. Por todo ello se han propuesto varias metodolog´ıas que describen m´etodos y gu´ıas para la construcci´on de los SMA. Casi todas las propuestas metodol´ogicas adaptan el Modelo Unificado de Jacobson definiendo algunas actividades espec´ıficas orientadas a las necesidades de los agentes. Tambi´en han aparecido recientemente metodolog´ıas y herramientas ´agiles como AGIL-Shell, Agile Passi, Agent-Factory, etc. Pero antes de comenzar el desarrollo de un SMA se debe determinar si realmente es necesario un sistemas de agentes o podr´ıa ser resulto el problema con una paradigma orientado a objetos, que es m´as sencillo. En [4] se especifican una serie de cuestiones a plantearse: 41
42
Cap´ıtulo 3. Metodolog´ıas de desarrollo de SMA. Plataformas
¿Se trata de un sistema distribuido abierto? ¿Pueden incorporarse din´amicamente nuevos tipos de entidades en el sistema? ¿Pueden cambiar las existentes? ¿Es necesario considerar una evoluci´on del comportamiento independiente para uno de los componentes del sistema o para una parte significativa? ¿Hay incertidumbre? ¿Es posible para una entidad del sistema conocer su contexto suficientemente para poder decidir con certeza el efecto de las acciones que puede realizar? ¿Hay personalizaci´on? ¿Un mismo servicio se puede ofrecer simult´aneamente de manera distinta seg´ un las caracter´ısticas de cada usuario? ¿Hace falta definir una organizaci´on de entidades que interact´ uan para resolver conjuntamente problemas globales? Se indica en [4] que si la respuesta a varias de estas preguntas es positiva, entonces ser´a conveniente concebir el sistema como una sociedad de agentes.
1.1.
INGENIAS
Esta metodolog´ıa es una evoluci´on de MESSAGE, en la que se integran varias metodolog´ıas y resultados de investigaci´on en el ´area de agentes y considera cinco puntos de vista. INGENIAS se basa en la generaci´on de meta-modelos que permite la posterior generaci´on de otros artefactos como son c´odigo, pruebas, documentaci´on, etc. INGENIAS adem´as se apoya en un conjunto de herramientas denominado INGENIAS Development Kit (IDK). Se puede ver una captura del IDK en la figura 3.1. Los cinco puntos de vista considerados por INGENIAS son: 1. Agente. Describe las responsabilidades con tareas y roles y considera el control del agente definiendo sus objetivos y estados mentales. 2. Organizaci´on. Describe el marco en el que existir´an los agentes, los recursos, las tareas y el prop´osito del sistema. La organizaci´on se define describiendo los grupos y flujos de trabajo, las relaciones sociales y la funcionalidad. 3. Entorno. Define los sensores y actuadores, as´ı como los recursos, otros agentes y aplicaciones como por ejemplo APIs, bases de datos o servicios webs.
1. Ingenier´ıa de Agentes
43
Figura 3.1: INGENIAS Development Kit (IDK) 4. Tareas y Objetivos. Tiene como prop´osito justificar la ejecuci´on de tareas en funci´on de los objetivos y proporciona la descomposici´on de tareas en funci´on de los objetivos. 5. Interacciones. Describen como se produce la coordinaci´on entre los agentes.
1.2.
MaSE
MaSE (Multi-agent Systems Software Engineering) usa un n´ umero de modelos gr´aficos derivados del est´andar UML para describir los tipos de agentes en el sistema y sus interfaces con otros agentes. La prioridad de MaSe es guiar el dise˜ no desde un conjunto de requisitos a trav´es del an´alisis, dise˜ no e implementaci´on de un SMA. MaSe ve a un SMA como una abstracci´on del paradigma de orientaci´on a objetos, donde los agentes son objetos especializados. En vez de simples objetos, con m´etodos que pueden ser invocados por otros objetos, los agentes se coordinan con otros mediante conversaciones y acciones para conseguir sus objetivos individuales y del sistema. El desarrollo con MaSe consta de varias etapas, las cuales en su mayor´ıa pueden ser realizadas con la herramienta agentTool :
44
Cap´ıtulo 3. Metodolog´ıas de desarrollo de SMA. Plataformas
Figura 3.2: Herramienta agentTool 1. Fase de an´alisis Captura de objetivos. A partir de los requisitos de los usuarios se generar´a una jerarqu´ıa de objetivos. Aplicar casos de uso. An´alisis de los casos de uso y generaci´on de los diagramas de secuencia correspondientes. Refinar roles. A partir de estos diagramas se podr´an determinar los roles y tareas del sistema. 2. Fase de dise˜ no Creaci´on de la clases de agentes. Se definir´an las clases a partir de los roles. Construcci´on de conversaciones. Las conversaciones en MaSe se definen como un protocolo de coordinaci´on entre dos agentes y se describen mediante dos aut´omatas, uno por cada parte. Ensamblar clases de agentes. Se definen los aspectos internos de las clases de agentes (atributos, m´etodos, etc.). Dise˜ no del sistema. Es la fase final y usa diagramas de despliegue para mostrar el n´ umero, tipo y localizaci´on de las instancias de agente en el sistema.
1. Ingenier´ıa de Agentes
45
Figura 3.3: Herramienta Prometheus Design Tool (PDT)
1.3.
Prometheus
En la metodolog´ıa Prometheus , creada por Lin Padgham y Michael Winikoff, en colaboraci´on con Agent Software a lo largo de 7-8 a˜ nos, se define un lenguaje de modelado relativamente sencillo, que forma parte de los fundamentos de AUML junto con otras metodolog´ıas. Su herramienta de desarrollo PDT (Prometheus Design Tool) public´o su u ´ltima release en 2001. Se puede apreciar una imagen de la herramienta en la figura 3.3. Prometheus fue pensado y ha sido usado tanto en el entorno acad´emico como en la industria. Esta metodolog´ıa cubre el proceso completo de desarrollo de software (an´alisis, dise˜ no e implementaci´on). Tiene como objetivo el desarrollo de agentes inteligentes, en particular agentes BDI que contengan creencias, objetivos, planes y eventos. La metodolog´ıa Prometheus, mostrada en la figura 3.4, se divide en tres fases: 1. Especificaci´on del sistema. Enfocada a identificar la funciones b´asicas del sistema, junto con las entradas (percepciones), salidas (acciones) y su procesamiento. 2. Dise˜ no de la arquitectura. Determina que agentes contendr´a el sistema y como interactuar´an.
46
Cap´ıtulo 3. Metodolog´ıas de desarrollo de SMA. Plataformas
Figura 3.4: Metodolog´ıa Prometheus 3. Dise˜ no detallado. Se describe el interior de cada agente y como llevar´a a cabo sus tareas. Enfocada a definir las capacidades, creencias, conocimientos, eventos internos, planes y estructuras de datos detalladas.
1.4.
Tropos
Tropos [13, 14] tiene como principal caracter´ıstica respecto a las otras alternativas, que ´esta hace un mayor ´enfasis en la identificaci´on y an´alisis de los requisitos. El desarrollo de tropos se compone de 5 fases:
1. Ingenier´ıa de Agentes
47
Figura 3.5: Fase de requisitos iniciales Tropos. [15] 1. An´alisis de requisitos iniciales. Esta fase se considera incremental y se busca determinar que actores relevantes se consideran dentro del dominio y que relaciones existen entre ellos. Para ello contempla dos diagramas: de actores y de justificaci´on (del ingl´es ”rationale”). El diagrama de actores es un grafo dirigido cuyos nodos ser´an agentes y las aristas representan relaciones entre ellos que seg´ un su tipo podr´a ser objetivos, tareas o recursos. Los diagramas de justificaci´on examinan los objetivos de un actor concreto (descomponi´endolos en subobjetivos) y sus dependencias con otros actores. Podemos ver un ejemplo de estos diagramas en la figura 3.5. 2. An´alisis de requisitos tard´ıos. Repite la fase anterior considerando el sistema que se pretende implementar como un nuevo actor y usando los mismos diagramas, para identificar requisitos funcionales y no funcionales. 3. Dise˜ no arquitect´onico. Configura la estructura de la organizaci´on del sistema a trav´es de su descomposici´on en subsistemas relacionados mediantes subsistemas. Esta fase se desarrolla en tres etapas: definici´on de la es-
48
Cap´ıtulo 3. Metodolog´ıas de desarrollo de SMA. Plataformas
Figura 3.6: Fase y etapas PASSI [16] tructura general del sistema, especificaci´on de las capacidades disponibles para cada actor y la definici´on de los tipos de agentes. 4. Dise˜ no detallado. Consistente en aumentar el nivel de destalle de los componentes identificados en la fase anterior, incluyendo los protocolos de comunicaci´on entre agentes.
1.5.
PASSI
PASSI (Process for Agent Societies Specification and Implementation) es una metodolog´ıa que pasa por todas las fases de desarrollo desde la toma de requisitos hasta la implementaci´on orientada al dise˜ no y desarrollo de sociedades de agentes haciendo uso de modelos y conceptos de la paradigma orientado a objetos y de los principios de la inteligencia artificial. En esta l´ınea, usa tecnolog´ıas bien conocidas como la notaci´on UML, XML para estructurar las comunicaciones y la plataforma FIPA como destino de la implementaci´on. PASSI considera cinco fases de desarrollo. El resultado de cada fase ser´a un modelo: System Requirements Model, Agente Society Model, Agent Implentatios Model, Code Model, y por u ´ltimo Deployment Model. Para la elaboraci´on de estos modelos se consideran diferentes etapas, por lo que en PASSI tenemos varias fases compuestas por diferentes etapas. Se trata de un proceso iterativo, con fases de prueba entre varias de sus etapas 3.6. Veremos ahora a grandes rasgos cada una de fases:
2. Plataformas de Sistemas Multi-Agente
49
1. System Requirements Model. A lo largo de las diferentes etapas de esta fase se identifican los agentes, y se determinan los casos de uso del sistema. Se platean los posibles roles de cada agente mediante diagramas de secuencia y se especifican las tareas asignadas a cada agente mediante diagramas de actividad. 2. Agente Society Model. Se describe el conocimiento y las comunicaciones entre los agentes siguiente los contenidos FIPA o definiendo nuevos protocolos mediante diagramas AUML. 3. Agent Implentatios Model. Se define la estructura general de sistema mediante un diagrama de clases que representa las interacciones significativas y por otro lado se define la estructura individual de cada agente con un diagrama de clase por cada agente. Tambi´en se define el comportamiento de los agentes mediante diagramas de actividad. La estructura del sistema y los agentes esta condicionada a el comportamiento y al contrario por lo que se hace necesario realizar interacciones entre estas dos etapas. 4. Code Model. Se lleva a cabo la implementaci´on haciendo uso de herramientas que ayuden a la generaci´on de c´odigo mediante plantillas y uso de patrones. 5. Deployment Model. Se describe el despliegue del sistema mediante diagramas de despliegue con una sintaxis extendida que permita la expresar la movilidad de los agentes. Como soporte a la metodolog´ıa, se dispone de la herramienta PTK (PASSI ToolKit) que incluye la generaci´on de c´odigo. Esta herramienta se compone de un plugin para Rational Rose y un herramienta para la reutilizaci´on de patrones de agentes.
2.
Plataformas de Sistemas Multi-Agente
Durante los primeros a˜ nos de investigaci´on en la materia hubo una proliferaci´on de herramientas y APIs, de las que hoy d´ıa u ´nicamente un n´ umero limitado de ellas se han mantenido. Por otra parte, parece que la mayor parte de este tipo de herramientas fueron desarrolladas en el mundo acad´emico y s´olo unas pocas se dise˜ naron y se est´an utilizando dentro de la industria. Podemos encontrar una lista de estos plataformas en la web AgentLink [17]: Grasshopper, ZEUS, JATLite, FIPA-OS, JAFMAS, OAA, Ara, AgentScape, y Bond. Nos centraremos en esta secci´on en algunos de los frameworks desarrollados en los u ´ltimos a˜ nos y aquellos que se han seguido manteniendo.
50
Cap´ıtulo 3. Metodolog´ıas de desarrollo de SMA. Plataformas
Cougaar Cougaar (Cognitive Agent Architecture) es una plataforma de software abierto basado en java desarrollado con la financiaci´on de DARPA. Este esta orientado a la descomposici´on jer´arquica de tareas complejas, integraci´on de aplicaciones y fuentes de datos distribuidas, y generaci´on din´amica de planes y aplicaciones altamente paralelas. La principal idea de Cougaar es la imitaci´on del proceso cognitivo de los seres humanos que incluye la descomposici´on, delegaci´on, consolidaci´on, monitorizaci´on, colecci´on y presentaci´on de informes. Cougaar adopta la noci´on de plugin por la se implementan comportamientos para lograr llevar a cabo tareas y planes. Cougaar soporta tanto planificaci´on est´atica como din´amica.
Cybele Cybele esta en continuo desarrollado por Intelligent Automation Inc. Es una plataforma para el desarrollo y despliegue de sistemas distribuidos a gran escala. En la plataforma de Cybele el kernel, los agentes, actividades y servicios est´an desarrollados en Java y para el desarrollo del SMA se usa AOPI (Agent Oriented Promming Interface). El desarrollo de un SMA en Cybele esta compuesto por contenedores que consisten en agentes, que a su vez se componen de actividades, que son esencialmente los comportamientos de los agentes. Cybele se utiliz´o en las a´reas de gesti´on del tr´afico a´ereo, la programaci´on y la planificaci´on, y la simulaci´on.
MadKit MadKit es una plataforma modular y escalable escrita en Java construida sobre el modelo organizacional AGR (Agente/Grupo/Role): los agentes son partes de grupos en los que juegan un rol. Aunque esta desarrollado en Java, los agentes pueden ser programados en Scheme, Jess, Java, Python, o BeanSHell. De hecho, con el fin de evitar la compilaci´on se recomienda usar alguno de los lenguajes de scripting soportados. Un agente en Madkit consiste en cuatro partes:
1. Activaci´on. Que es esencialmente una fase de configuraci´on 2. Live. Donde se incluyen los comportamientos.
2. Plataformas de Sistemas Multi-Agente
51
3. End. Que se el procedimiento de finalizaci´on. 4. initGUI. Que se ocupa de la interfaz gr´afica del agente.
Madkit esta equipado con su propio IDE y metodolog´ıa y proporciona la infraestructura para la ejecuci´on de SMA. Adem´as permite la monitorizaci´on de los agentes y sus interacciones.
JIAC JIAC (Java Intelligent Agent Compontentware) es un framework dirigido a facilitar el desarrollo de aplicaciones complejas y distribuidas, soportando el desarrollo en entorno heterog´eneos. JIAC ha sido desarrollado siguiendo el enfoque de desarrollo basado en componentes, la cual tambi´en ha sido usada para el desarrollo de los SMA. Una aplicaci´on JIAC consiste en AgentNodes los cuales pueden ser f´acilmente publicados y proporcionan servicios de p´aginas amarillas. Cada AgentNode puede ejecutar varios agentes que pueden contener m´ ultiples AgentBeans que representan los comportamientos. Un AgentBean tiene dos partes: memoria y ejecuci´on. JIAC ofrece un conjunto herramientas para facilitar el desarrollo de los SMA.
Agent Factory Agent Factory es una colecci´on de herramientas, plataformas y lenguajes orientados a la creaci´on de SMA. El framework cumple con los est´andares FIPA, as´ı el uso de un lenguaje com´ un posibilita el dise˜ no e implementaci´on de lenguajes de programaci´on de agentes (actualmente se incluye AgentSpeak y TeleoReactive).
JACK JACK provee un entorno de desarrollo de agentes totalmente construido en Java y basado en la arquitectura BDI. Es un entorno orientado a las aplicaciones industriales. La plataforma proporciona un lenguaje espec´ıfico llamado JAL (JACK Agent Language) para la definici´on los agentes y un entorno para su ejecuci´on.
52
Cap´ıtulo 3. Metodolog´ıas de desarrollo de SMA. Plataformas
Figura 3.7: Modelo parcial de JADE JADE JADE es framework m´as usado en la comunidad investigadora. Est´a basado en Java y totalmente orientado a la creaci´on de SMAs cumpliendo con los est´andares FIPA. Esta compuesto por una plataforma (o middleware) para la ejecuci´on de agentes, y un conjunto completo de librer´ıas que facilitan el desarrollo de los SMA. Adem´as, JADE proporciona a los desarrolladores facilidades de soporte que incluye: Consola de monitorizaci´on desde la que se pueden ejecutar, suspender, terminar, clonar y migrar agentes de una plataforma a otra. Sniffer con el que es posible monitorizar las comunicaciones de los agentes. Depurador para monitorizar los comportamientos de agentes, incluyendo los mensajes entrantes y salientes y los estados de los agentes. El depurador adem´as permite el control de los agentes mediante puntos de interrupci´on y control de los estados. El concepto usado en JADE es muy simple, lo cual ha contribuido al aumento de su popularidad. En la figura 3.7 se presenta una parte del modelo de clases de JADE. Como se puede observar el elemento principal de JADE es la clase Agent que puede estar asociado a una ontolog´ıa y puede ser usado para comunicarse con otros agentes mediante mensajes ACL. La funcionalidad de JADE est´a centrada en los comportamientos, que son considerados como hilos virtuales (no son hilos del sistema operativo, sino que son manejados por la plataforma de jade). Se proporcionan varios tipos de comportamientos que permiten la especificaci´on de protocolos. JADE est´a en continuo desarrollo (la u ´ltima versi´on se liber´o en marzo de 2014) y ha sido extendida para adaptarse a la administraci´on de procesos y flujos de trabajo surgiendo WADE (Workflows and Agents Development Environment). Otra extensi´on importante es JADEX, que adopta BDI para aportar a JADE los aspectos de esta arquitectura.
2. Plataformas de Sistemas Multi-Agente
Figura 3.8: Metodolog´ıas de desarrollo de SMA [10]
53
Cap´ıtulo 4 Desarrollo del sistema
Una vez se han repasado los tipos de subastas y de haberse revisado las teor´ıa de agentes, m´as concretamente los sistemas multiagentes vamos a pasar a describir el desarrollo de proyecto y las soluciones aportadas.
1.
Descripci´ on del sistema
A grandes rasgos el proyecto consiste en un SMA dedicado al sistema de subastas, una aplicaci´on web en la que se gestionan cada uno de los roles del sistema (consumidores, agricultores y transportistas), una aplicaci´on m´ovil para Android y las interfaces REST para la comunicaci´on del SMA. En el diagrama 4.1 podemos ver c´omo interact´ uan cada uno de los subsistemas. Vamos a ver una breve descripci´on de cada uno de ellos: Base de datos El almacenamiento de datos es un elemento esencial en cualquier sistema hoy en d´ıa. En este proyecto, no se especifica ning´ un sistema gestor de almacenamiento concreto. El sistema ORM de Django nos abstrae del gestor de base de datos final, por lo que el sistema podr´a trabajar con diversos sistemas gestores de bases de datos sin necesidad de hacer modificaciones en la aplicaci´on. Negocios Es la parte de la aplicaci´on que se encarga de implementar toda la l´ogica de negocios del sistema (gesti´on de usuario, autorizaciones y autenticaciones), y es la u ´nica que interact´ ua directamente con la base de datos. 55
56
Cap´ıtulo 4. Desarrollo del sistema
Figura 4.1: Diagrama de sistema Servicios REST Se exponen una serie de servicios REST para que el SMA (y algunas partes de la aplicaci´on web) pueda interactuar con el sistema. Aplicaci´ on web Desarrollada en Python + Django, es la interfaz de usuario desde la que puede gestionar las reglas de compra o ventas seg´ un su rol, as´ı como consultar las compras y ventas ya realizadas. Aplicaci´ on m´ ovil Proporciona la misma funcionalidad que la aplicaci´on web y adem´as podr´a recibir notificaciones directamente en el m´ovil sobre el desarrollo de la subasta. El sistema deber´a realizar las siguientes tareas: Mantenimiento y gesti´on de las reglas para el proceso de subasta. Gesti´on de las ventas y compras ya realizadas. Sistema aut´onomo de subastas. Sistema de notificaciones sobre acuerdos alcanzados. Antes de comenzar el desarrollo del sistema se ha entrevistado a varios agricultores y posibles compradores. En un principio, el sistema estaba orientado
1. Descripci´ on del sistema
57
a la venta de productos agr´ıcolas en general, pero tras estas entrevistas y un estudio realizado por Lorenzo L´opez Mu˜ noz y Paula Luna Huertas del departamento de Econom´ıa Financiera y Direcci´on de Operaciones de la Universidad de Sevilla, se recomienda redirigir el proyecto a productos ecol´ogicos. En definitiva, desde el punto de vista del sistema, es indiferente el limitarse a productos ecol´ogicos ya que cada subasta del SMA se restringe a un producto de una variedad y con un tratamiento concreto. De las entrevistas con los agricultores se obtuvieron las siguientes conclusiones: Los agricultores no suelen tener un lugar de almacenamiento del producto. La recogida del producto es un proceso del que se encarga el intermediario o la cooperativa. Igualmente del transporte tambi´en se encarga el intermediario o la cooperativa. Los productos de mayor calidad (seg´ un el calibre y color) son exportados al extranjero. Tanto la recogida como el transporte pueden tener un coste en torno a los 5 cents/kg. Por tanto, surge la necesidad de dar una soluci´on al problema del transporte y la recolecci´on. Como soluci´on se propone en este trabajo introducir, adem´as del rol del agricultor y comprador, el rol del transportista. As´ı, adem´as de dar una soluci´on a la problem´atica de los intermediarios, el sistema podr´ıa generar puestos de trabajo adicionales como transportistas aut´onomos. En esta situaci´on tenemos tres roles bien diferenciados para cada tipo de agente: Agricultor. Necesitar´a definir el producto o productos que cosecha, qu´e tratamientos aplica durante su producci´on as´ı como el periodo de ´esta. Esta informaci´on es necesaria y muy u ´til para los compradores. Tambi´en necesitar´a definir las reglas de venta para sus productos seg´ un la variedad y el calibre. Por u ´ltimo podr´a consultar el hist´orico de ventas realizadas. Comprador. Debe poder definir sus reglas de ventas seg´ un el producto, variedad y calibre. De cara a la subasta, ser´a necesario definir un precio de compra m´axima para dicho producto. Igualmente deber´a poder consultar
58
Cap´ıtulo 4. Desarrollo del sistema
el hist´orico de compras. Adem´as el comprador debe aceptar o rechazar de manera manual el acuerdo alzado. Transportista. El transportista deber´a definir cu´al es su carga de transporte m´axima. Ser´a el sistema el que se encargue de establecer en cada momento si le conviene o no realizar un transporte en funci´on del tiempo de recorrido, tiempo de carga, tiempo de descarga y gasto de combustible.
1.1.
El sistema de subastas
Para el desarrollo de este trabajo se ha optado por la subasta inglesa. Es un subasta bien conocida y que no presenta mayores problemas, aunque surgen ciertos problemas derivados de la complejidad del sistema completo. Uno de ellos es que tenemos m´ ultiples vendedores de un mismo producto. Todos ellos quieren vender lo m´aximo posible cubriendo gastos y obteniendo beneficios. Por otro lado tenemos m´ ultiples compradores que quieren comprar lo m´as barato posible, pero una vez que acepten un acuerdo ya no podr´an participar en el resto de subastas en las que podr´ıan obtener un precio menor. Si se pretende satisfacer a los compradores - y suponiendo que el agricultor tiene suficiente cantidad de producto - el sistema solo atender´a a aquellos agricultores que proporcionen el menor precio m´ınimo de venta, ya que son con ellos con los que hay mayor probabilidad de obtener un mejor precio de venta. Esto ir´ıa en contra de propio sistema, ya que si los agricultores no venden, al final no usar´ıan el sistema, por lo que hace necesario buscar un m´etodo en el que el mayor n´ umero de agricultores vendan y que adem´as sea los m´as equitativo posible. La soluci´on que se propone en este trabajo es la de imponer un turno rotatorio de subastas y estudiar varias estrategias a la hora de seleccionar el orden de las subastas en las que participan. S´olo hemos hablado hasta ahora del agricultor y el comprador, pero adem´as tenemos que buscar un transporte. Es aqu´ı donde surge el punto m´as interesante del sistema de subasta propuesto. Para buscar a un transportista, tambi´en se levantar´a una subasta entre todos los transportistas del sistema para encontrar aquel que nos oferte el transporte m´as econ´omico. Es posible que no se encuentre, por lo que la subasta anterior tampoco tendr´ıa validez sin transporte y quedar´ıa autom´aticamente anulada. Lo ideal ser´ıa que esta situaci´on no se produjese, es decir, que el sistema no tuviera que cancelar ninguna subasta. Para ello surge la idea de una subasta a tres bandas de la que no se ha encontrado literatura al respecto y que tampoco ha podido ser desarrollada en este trabajo.
2. Dise˜ no del sistema
59
Figura 4.2: Esquema del proceso de subastas llevado a cabo por el SMA El la figura 4.2 podemos ver un esquema orientativo del funcionamiento del sistema de subastas completo. Por otro lado, el transportista estar´a dispuesto a hacer un transporte, no solo en funci´on de la localizaci´on del agricultor y del punto de entrega, sino tambi´en de la ruta que ya tenga previamente definida. En definitiva, el encontrar el reparto m´as equitativo posible, que a todos deje contentos, ser´ıa el objetivo ideal a conseguir para este proyecto.
2.
Dise˜ no del sistema
Veremos en esa secci´on cada una de los subsistemas desarrollados, centr´andonos especialmente en el SMA. Aunque no se ha seguido una metodolog´ıa de desarrollo con rigurosidad en este trabajo, el desarrollo del SMA ha estado guiado por la filosof´ıa de la metodolog´ıa PASSI y sus fases de desarrollo.
60
Cap´ıtulo 4. Desarrollo del sistema
Figura 4.3: Modelo de datos
2.1.
Modelo de datos
El modelo de datos de la aplicaci´on que podemos ver en el diagrama 4.3 ha ido evolucionando a lo largo del desarrollo de este trabajo apareciendo y desapareciendo tablas y atributos. La informaci´on que se almacena en este es la siguiente:
Informaci´on de autenticaci´on de usuarios en la tabla userprofile. De esta tabla se derivan las tablas Farmer, Buyer y Shipper como una especializaci´on para cada rol del sistema.
2. Dise˜ no del sistema
61
Informaci´on sobre localizaci´on en la tablas Province, City y Localization. Informaci´on sobre los productos agr´ıcolas en las tablas FoodType, Variety y Treatment. Informaci´on de reglas para el sistema de subastas en las tablas BuyerRule, ShippingRule y SaleRule. Informaci´on sobre los acuerdos alcanzados por el sistema entre un agricultor, un comprador y un transportista en la tabla FullDeal. Informaci´on sobre el dispositivo Android del usuario para realizar las notificaciones en la tabla UserDevice.
2.2.
Aplicaci´ on web: dise˜ no y manual de uso.
La aplicaci´on web se ha desarrollo con un estilo que se adapte lo mejor posible a los dispositivos m´oviles. En la parte inferior se presenta un men´ u con las secciones principales de la aplicaci´on seg´ un el rol del usuario. De entre ellas, la secci´on Direcciones es com´ un a todos los roles. Todos ellos necesitan especificar una o varias direcciones para la recogida y entrega del producto. En el caso del transportista adem´as se usa para calcular el tiempo de transporte desde su direcci´on hasta el productor y posteriormente hasta el punto de entrega. Podemos ver las pantallas en la imagen 4.4. Las alertas o notificaciones, aunque tambi´en es una secci´on que est´e presente en todos los roles, difieren un poco en la informaci´on que se muestra a cada uno de ellos. Para el agricultor y el transportista, ´estas son u ´nicamente un elemento informativo de aquellos acuerdos que se han realizado con ´exito. En el caso del comprador, adem´as en cada notificaci´on de acuerdo realizado tiene la posibilidad de aceptar o rechazar ese acuerdo y continuar participando en la subasta, por lo que su secci´on de notificaciones est´a divido en notificaciones pendientes, aceptadas y rechazadas como se puede apreciar en la imagen 4.5 El resto de secciones son particulares de cada rol. En agricultor, deber´a crear una o varias cosechas para especificar el producto y variedad cosechada, as´ı como los tratamientos aplicados, la producci´on total estimada y las fechas de recolecci´on. Esta informaci´on no se usa para el proceso de subasta (a excepci´on del producto, variedad y tratamientos), pero puede ser de inter´es de los compradores para determinar si aceptan o no la oferta alcanzada. En la imagen 4.6 podemos ver la pantalla de lista de cosechas por un lado y la pantalla de edici´on de una de estas.
62
Cap´ıtulo 4. Desarrollo del sistema
Figura 4.4: Direcciones. A la izquierda la lista de direcciones, a la derecha la edici´on de una direcci´on.
Figura 4.5: Alertas y notificaciones. A la izquierda las notificaciones de un agricultor, en la parte central las notificaciones de un comprador, y la derecha las notificaciones de un transportista.
2. Dise˜ no del sistema
63
Figura 4.6: Cosechas. A la izquierda la pantalla de lista de cosechas, a la derecha la pantalla de edici´on de una nueva cosecha.
Adem´as, el agricultor deber´a crear las reglas de venta, donde se especificar´a la cosecha, kilogramos m´ınimos de venta, precio m´ınimo por kilogramo en c´entimos, el calibre del producto y la fecha de caducidad de la regla. Se podr´a agregar una imagen del producto a vender para el que el comprador tenga una mejor idea de lo que est´a comprando exactamente. Podemos verlo en la imagen 4.7. El transportista u ´nicamente tiene que crear, adem´as de la direcci´on, sus reglas de transporte, en la que especifican los kilogramos m´aximos que puede transportar. Como podemos ver en la imagen 4.8, aunque se piden el precio m´ınimo por kg y los kil´ometros a recorrer como m´aximo, estos par´ametros no son tenidos en cuenta por el SMA. Se ha mantenido el primer dise˜ no del modelo de datos. Desde la secci´on ventas, tambi´en se dispone del listado de transportes acordados pero a´ un pendientes de entregar y los ya entregados. Por u ´ltimo, el comprador debe crear sus reglas de compra, desde la secci´on REGLAS (se puede ver en la imagen 4.9). Adem´as se pueden consultar las reglas de compra anteriormente usadas en las subastas y de las que se acept´o una oferta. Por u ´ltimo, en la secci´on COMPRAS se dispone de un listado de las compras realizadas (Figura 4.10).
64
Cap´ıtulo 4. Desarrollo del sistema
Figura 4.7: Ventas del agricultor. A la izquierda las ventas programadas, en la parte centra la ventas realizadas y a la derecha la pantalla de edici´on de una venta programada.
2.3.
Aplicaci´ on m´ ovil
La aplicaci´on m´ovil desarrollada para Android es una aplicaci´on con un navegador incrustado que hace uso de la aplicaci´on web anterior y que se encarga de la gesti´on de las notificaciones recibidas a trav´es del sistema GCM (Google Cloud Messaging). No es la mejor soluci´on, ya que presenta problemas dif´ıciles de solventar, ya que el navegador incrustado en ocasiones no gestiona bien los eventos recibidos por el sistema operativo, derivando en comportamientos poco deseables. Cuando se alcanza un acuerdo con un comprador, el sistema le enviar´a un notificaci´on. Si el usuario dispone de la aplicaci´on Android instalada, le enviar´a un notificaci´on al dispositivo como se puede ver en la captura 4.11. Si el usuario no dispone de aplicaci´on m´ovil, se le enviar´a la notificaci´on al correo.
2.4.
Sistema multiagente
El sistema multiagente es la parte m´as compleja de todo el sistema y el objetivo central de este proyecto. Vamos a ver cada una de las partes de este:
2. Dise˜ no del sistema
65
Figura 4.8: Transportes. A la izquierda los transportes programados (reglas), en la parte central los transportes pendientes de ser entregados y a la izquierda la edici´on de un nuevo transporte programado (regla). Los agentes El SMA mantiene varios tipos de agentes. En concreto, cada regla definida para la subasta ser´a un agente por lo que tendremos un agente por cada regla de venta de los agricultores, uno por cada regla de compra y uno por cada regla de transporte. Estos agentes funcionar´an como iniciadores o participantes de la subasta. Adem´as se crear´a un agente inicial, denominado SynAgent, que es el encargado de iniciar todo el sistema, obteniendo todas las reglas mediante la interfaz REST y creando el comportamiento del sistema de turnos que veremos m´as adelante. Adem´as de los agentes anteriores, cuando se gana una subasta entre un comprador y un agricultor se crear´a un agente, llamado BAF (Buyer And Farmer) para identificar ese acuerdo alcanzado y que funcionar´a como iniciador de la subasta dedicada a la b´ usqueda de un transporte. En la figura 4.12 podemos ver un diagrama de secuencias del funcionamiento b´asico del SMA.
El sistema de turnos Como se ha mencionado anteriormente, el agente SynAgent crea un comportamiento para gestionar el sistema de turnos de las subastas. La implementaci´on
66
Cap´ıtulo 4. Desarrollo del sistema
Figura 4.9: Compras. En la parte superior izquierda las reglas de compra activa y en la parte inferior las reglas de compra que han sido ya usadas por una oferta aceptada. A la izquierda la edici´on de una regla de compra.
se hace mediante una m´aquina finita de estados que podemos ver en la imagen 4.13. Este agente mantiene un lista de los agentes que representan cada regla de venta. Dado que el orden en que se obtiene estas reglas de venta de la base de datos siempre es el mismo, lo primero que debe hacer es realizar una (des)ordenaci´on aleatoria, para evitar favorecer a ning´ un agricultor. Esta (des)ordenaci´on se realiza cada vez que ha pasado por todas las reglas de venta. Se estar´a intentado levantando subasta constantemente hasta que hayan pasado un cierto n´ umero de minutos definidos sin llegar a conseguir ning´ un acuerdo completo entre agricultor, comprador y transportista.
67
2. Dise˜ no del sistema
Figura 4.10: Compras realizadas. Los comportamientos Se ha implementado m´ ultiples comportamientos que podemos clasificar en tres grupos: comportamientos de mensajer´ıa, comportamientos del sistema de turnos y comportamientos del sistema de subasta 4.14. En el punto anterior ya se han visto los comportamientos de turnos. Vamos a ver los otros dos grupos: Comportamientos de mensajer´ıa La implementaci´on de la mensajer´ıa ha sido lo m´as delicado de implementar. Para facilitar su desarrollo se ha creado varios comportamientos gen´ericos que, implementan el env´ıo y recepci´on de los mensajes y agregan el protocolo adecuado en funci´on de lo que se quiere informar o solicitar. Al crear el comportamiento se debe indicar el tipo de conversaci´on. Los tipos disponibles son: • LOCATION REQUEST: Se solicita la localizaci´on. • MAX PRICE TRANSPORT REQUEST: Se solicita el precio m´aximo para la subasta de transporte. • PRICE PAID: Se solicita el precio pagado. • KILOGRAMS BUY: Se solicita el n´ umero kilogramos a transportar. • NO TRANSPORT FOUND INFORM: Se informa de que no se ha encontrado transporte. • REGISTER: Se solicita a un agente su registro en las p´aginas amarillas.
68
Cap´ıtulo 4. Desarrollo del sistema
Figura 4.11: Notificaciones al comprador. • START AUCTION PRICE: Se solicita el precio de inicio de la subasta. • START AUCTION: Se informa del comienzo de la subasta. De esta forma si el agente comprador est´a dispuesto a informar de su localizaci´on en caso de que se le solicite, u ´nicamente tiene que agregar a sus comportamientos un comportamiento DataRequestReceiver de tipo LOCATION REQUEST. Igualmente, cuando se quiere solicitar la localizaci´on a otro agente, solo es necesario agregar un comportamiento DataRequest del mismo tipo. DataRequest ya se encarga de esperar la respuesta (mediante un comportamiento DataReceiver ) y procesarla adecuadamente. Si s´olo se quiere enviar una informaci´on a otro agente, sin esperar ning´ un tipo de respuesta asociada, solo es necesario usar un comportamiento DataInform. Comportamientos del protocolo de subasta Como vemos en el diagrama de clases 4.14, a excepci´on del agente BuyerConsumer, el resto de agentes solo implementan un comportamiento relacionado con la subasta inglesa. En el caso de Buyer consumer se han implementado varias ”estrategias” de participaci´on en las subastas para investigar de qu´e forma puede evolucionar el sistema en funci´on de distintos comportamientos y c´omo adaptar el sistema para que sea lo m´as efectivo y u ´til posible. Vamos a ver una breve descripci´on de los comportamientos m´as importantes:
2. Dise˜ no del sistema
69
Figura 4.12: Diagrama de secuencia b´asico del SMA SaleRuleInitiator: Implementa el comportamiento iniciador de la subasta inglesa entre una regla de venta definida por el agricultor y las reglas de compra de los compradores. Esta implementaci´on u ´nicamente devuelve el siguiente precio en la subasta actual y el identificador del agricultor. BuyerAndFarmerDealInitiator: Implementa el comportamiento iniciador de la subasta inglesa para encontrar un transportista para un acuerdo ya alcanzado entre un agricultor y un comprador. Este comportamiento s´olo tiene la particularidad de que toma un precio inicial (el restante entre el m´aximo establecido en la regla de compra y el pagado al agricultor) y va decreciendo en cada iteraci´on, ya que se busca aquel transportista m´as barato. Adem´as del siguiente precio en la subasta en cada iteraci´on se devuelven los kilogramos de producto a transportar, ya que esta informaci´on la necesitan los transportistas para calcular sus beneficios y por tanto el
70
Cap´ıtulo 4. Desarrollo del sistema
Figura 4.13: Diagrama de estados del sistema de turnos precio m´ınimo al que pueden hacer dicho transporte. ShippingRuleParticipant: Implementa el rol participante de la subasta inglesa entre un BAF y una regla de transporte. Para determinar si puede o no aceptar un precio, este comportamiento tiene en cuenta los anteriores transportes ya acordados y calcula una ruta obteniendo el coste total de todos los transportes. La aceptaci´on o no de la oferta actual de la subasta depender´a de: • La distancia total a recorrer. Se hace un calculo del coste aproximado en combustible que ser´a restado a los beneficios. • El tiempo de transporte. En funci´on de la distancia se calcula el tiempo de transporte, al que se le a˜ nade un tiempo de carga y descarga en funci´on de los kilos a transportar. Si este tiempo supera un limite establecido, se rechazar´a la oferta. Adem´as este tiempo es usado para calcular las ganancias por hora. • Los kilogramos a transportar. Cuantos m´as kilos incluya la oferta, menor ser´a el precio al que el transportista puede hacer dicho transporte ya que disminuye el n´ umero de paradas y por tanto el tiempo de carga y descarga. Por otro lado, cada transportista define un n´ umero de kilogramos m´aximos que puede transportar. • El beneficio por hora. Una vez calculado todos los par´ametros anteriores, se calcular´a el beneficio por hora y solo se aceptar´a el transporte si supera un beneficio m´ınimo. BuyerRuleParticipant Es una clase abstracta que expone varios m´etodos a ser implementados por las clases hijas para especificar la estrategia a seguir. La estrategias implementadas en el sistema se basan en la elecci´on del orden a participar en la subastas. Las estrategias implementadas son: • Orden por menor precio de salida. Este comportamiento lo primero que hace es pedir a todos los agentes de venta que les informe de su
2. Dise˜ no del sistema
71
Figura 4.14: Agentes y comportamientos del MSA precio de salida. El comportamiento mantendr´a una lista ordenada de los precios, e ir´a participando en las subastas seg´ un este orden. • Orden aleatorio. En este caso, una vez obtenidos todos los precios de salida, los ordena aleatoriamente, e ir´a participando en las subastas seg´ un ese orden. • Orden por cercan´ıa al agricultor. Obtiene la localizaci´on de cada agricultor, e ira participando en cada subastas seg´ un lo cerca que se encuentre de este. • Generoso. Este comportamiento, independiente de los precios participar´a primero en las subastas de aquellos agricultores a los que no haya comprado recientemente.
72
Cap´ıtulo 4. Desarrollo del sistema
La subasta
Para la subasta inglesa se ha usado la implementaci´on del protocolo especificado por FIPA encontrada en Google code1 , la cual ten´ıa alg´ un error que fue solventado. En los gr´aficos 4.15 4.16 podemos ver los diagramas de estados del iniciador (el vendedor en nuestro caso) y el participante (los compradores).
1
http://code.google.com/p/fipa-english-auction-interaction-protocol/wiki/ EnglishDescriptionDraft
2. Dise˜ no del sistema
Figura 4.15: Diagrama de estados del rol Iniciador en la subasta inglesa
73
74
Cap´ıtulo 4. Desarrollo del sistema
Figura 4.16: Diagrama de estados del rol Participante en la subasta inglesa Adem´as de la resoluci´on de los errores encontrados en la implementaci´on, ´esta ha sido adaptada a nuestro caso. La implementaci´on u ´nicamente enviaba el precio de la siguiente iteraci´on a los participantes, pero en nuestro caso los participantes en la subasta necesitan m´as informaci´on, como por ejemplo el identificador del vendedor y la localizaci´on para calcular las rutas y el coste de los transportes.
3.
Despliegue del sistema
El sistema completo ha sido desplegado en el servidor Mowento. La direcci´on del portal es http://mowento.cs.us.es/mercadosp2p.
3. Despliegue del sistema
75
Para instalar la aplicaci´on m´ovil solo es necesario acceder a la web mediante el navegador del m´ovil. Esta detectar´a que se trata de un dispositivo Android y le redirigir´a a la p´agina de descarga. Tras la instalaci´on, la aplicaci´on le pedir´a el rol y el nombre para crear su usuario. Las autenticaciones posteriores las realizar´a la aplicaci´on autom´aticamente. El sistema est´a funcionando lanzando las subastas cada 30 minutos, con reglas generadas autom´aticamente, por lo que puede ser probado en cualquier momento. Todas la reglas reglas generadas de agricultores y compradores son sobre el producto naranjas barberinas con tratamiento ecol´ogico, por lo que si se quiere probar un agricultor nuevo o comprador nuevo es aconsejable usar este producto y tratamiento para entrar en dichas subastas.
Cap´ıtulo 5 Resultados y conclusiones
Una vez que se ha implementado el sistema es el momento de analizar su funcionamiento. En esta secci´on se expondr´an los experimentos realizados y se intentar´an extraer conclusiones que puedan ayudar a mejorar los resultados.
1.
Generaci´ on de datos de prueba
Para realizar las pruebas con el sistema se han generado autom´aticamente varios agentes (agricultores, compradores y transportistas). Se ha limitado la localizaci´on de todos a la provincia de Sevilla y sus alrededores, como se puede apreciar en la imagen 5.1. En concreto, las cosechas de los agricultores se han distribuido aleatoriamente alrededor del n´ ucleo urbano de la ciudad de Sevilla como si ´estos estuvieran en zonas agr´ıcolas de la provincia a una distancia m´axima de aproximadamente de 20 kil´ometros. En total se ha generado 20 cosechas. Se han generado las reglas de estos agricultores (se pueden consultar en la tabla 5.1), las cuales permanecen inalterables durante todas la pruebas. Los transportistas se han repartido dentro del n´ ucleo urbano de Sevilla y se ´ han generado sus reglas. Se muestran en la tabla 5.2. Unicamente incluimos los kilogramos m´aximos que pueden transportar, ya que este par´ametro junto con su ubicaci´on son lo usados por los SMA. Para el caso de los compradores, en el sistema hay generados alrededor de 100, distribuidos por el n´ ucleo urbano de Sevilla. El sistema genera alrededor de 70 reglas entre ´estos cada vez que se va a comenzar un ronda de subastas. Todas estas reglas se generan con el producto naranjas de variedad barberina y 77
78
Cap´ıtulo 5. Resultados y conclusiones
Figura 5.1: Distribuci´on de los datos de prueba con el tratamiento ecol´ogico.
2.
Todos los compradores con la misma estrategia
Vamos a ver en esta secci´on c´omo se comporta el sistema cuando todos los compradores siguen la misma estrategia, y qu´e diferencias pueden existir entre unas y otras.
2.1.
Orden por menor precio de salida
Este tipo de agente participar´a en la subastas en orden de su precio de salida. La l´ogica nos dir´ıa que el objetivo del agente en buscar los mejores acuerdos
79
2. Todos los compradores con la misma estrategia Regla 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Kg m´ınimos 77 72 66 95 67 81 65 49 84 97 52 76 38 72 42 56 38 33 53 27
Precio m´ın por Kg (cents) 9 15 13 8 13 9 12 9 14 12 15 15 9 8 12 10 11 9 11 15
Calibre 3 3 4 1 3 5 4 5 4 4 2 1 5 2 5 2 4 4 5 2
Cuadro 5.1: Reglas de venta de los agricultores
en aquellas subastas donde el precio de salida es menor y por tanto con mayor posibilidad de recibir un menor precio. Pero si todos los agentes siguen la misma l´ogica, la situaci´on es totalmente adversa como se pueden apreciar en la gr´afica 5.2. Los mayores precios se obtiene en los primeros acuerdos, donde evidentemente hay una mayor participaci´on de agentes compradores y m´as importante, los agentes que est´an dispuestos a pagar m´as est´an presentes y son los que ganar´an la subasta. En la gr´afica de color verde, se aprecia c´omo los agentes van participando en orden de precio y como una vez se han pasado por las 20 reglas de venta configuradas en el sistema, se vuelve otra vez a la primera de menor precio. Como era de prever, el precio de venta va disminuyen seg´ un avanza la sesi´on debido a que cada vez hay menos compradores, y que adem´as los que quedan son los que est´an dispuestos a pagar menos.
80
Cap´ıtulo 5. Resultados y conclusiones Regla 1 2 3 4 5 6 7 8 9
Kg. max. 2130 2320 1990 850 1940 1540 710 810 530
Cuadro 5.2: Reglas de los transportistas Kg 159 157 162 82 182 79 81 181 199 113
Calibre min. 2 1 3 3 3 2 2 3 2 1
Calibre max. 5 4 5 5 4 5 4 5 4 5
Estrategia Cercan´ıa al agricultor Generoso Cercan´ıa al agricultor Menor precio de salida Aleatorio Cercan´ıa al agricultor Aleatorio Menor precio de salida Cercan´ıa al agricultor Menor precio de salida
Cuadro 5.3: Ejemplo de 10 reglas de compra generadas aleatoriamente
2.2.
Orden aleatorio
Este tipo de agente no tiene preferencias por ning´ un agricultor, as´ı que participar´a en las subastas en un orden aleatorio. Se busca con esta estrategia hacer que los agentes se distribuyan entre los agricultores evitando que todos participen en la misma subasta y conseguir as´ı que los compradores que est´en dispuestos a pagar m´as se distribuyan independiente del precio de salida. Podemos ver en la gr´afica 5.3 que los u ´ltimos acuerdos tienen un precio de compra bastante alto, del orden de los conseguidos a mitad de la sesi´on.
2.3.
Orden de cercan´ıa al agricultor
En este caso, los compradores participar´an primero en las subastas de aquellos agricultores que est´an m´as cerca y posteriormente en aquellas cuyos agricultores se encuentran m´as alejados. De esta forma, el agente pretende reducir
2. Todos los compradores con la misma estrategia
81
Figura 5.2: Evoluci´on de la ventas con todos los agentes siguiendo la estrategia de participar primero en las subastas con menor precio de salida. el coste del transporte. Si analizamos la gr´afica 5.4 sin la informaci´on del transporte, vemos que presenta un comportamiento tambi´en aleatorio respecto al precio de salida e incluso en la diferencia entre el precio de salida y el precio de compra, llegando en ocasiones a solo estar interesado un comprador y en otras ocasiones increment´andose considerablemente. En la gr´afica 5.5 podemos ver el coste medio del transporte por estrategia. Como se puede observar, precisamente el orden por cercan´ıa es la que mayor coste en media tiene. Esto puede ser debido a que el coste debido a la distancia influye muy poco en el coste total del transporte y que adem´as la estrategia hace que se acumulen los compradores en las subastas de unos agricultores y participen poco en las de otros. Seg´ un nuestro modelo y en el entorno geogr´afico en el que nos movemos, el tiempo de carga y descarga se lleva la parte del coste.
2.4.
El generoso
Este agente no participar´a en aquellas subastas de los agricultores en la que hubiese participado y ganado en sus 10 u ´ltimas compras. Se pretende distribuir la compras independientemente del coste que le suponga, por eso el nombre de el generoso. A pesar de la generosidad, en la primeras subastas sigue habiendo muchos compradores, lo que incrementa el precio, que van desapareciendo a lo largo del tiempo disminuyendo este, como pasaba en la estrategia por orden por precio de precio. Sin embargo si que se consigue algo interesante. Si observamos la linea que representa la diferencia entre el precio de salida y el precio pagado,
82
Cap´ıtulo 5. Resultados y conclusiones
Figura 5.3: Evoluci´on de la ventas con todos los agentes siguiendo la estrategia aleatoria de participaci´on en las subastas. podemos ver que no llega al m´ınimo como pasaba con las otras estrategias.
3.
Diferentes estrategias conjuntas
En la imagen 5.7 presentamos cuatro gr´aficas. En todas ellas est´an presentes las cuatro estrategias, pero hay una mayor proporci´on de una de ellas. De nuevo, se puede ver como la estrategia del generoso hace que la tendencia de ca´ıda entre el precio de venta y el precio de salida sea menor.
4.
Los transportistas
Veremos ahora c´omo se comporta el sistema respecto a los transportistas, es decir, si existe alguna relaci´on entre los repartos de cada uno y la estrategias seguidas. En la figura 5.8 se muestra cinco gr´aficas. Cuatro de ellas en la que solo interviene una estrategia en todas las subastas y la u ´ltima en la que existe una distribuci´on de estrategias mas o menos repartida. Si nos centramos en los beneficios totales de los repartidores, vemos que puede existir bastante diferencia entre unos y otros. Ser´ıa interesante que el sistema fuera capaz de buscar una reparto m´as equitativo entre todos los transportistas. Por otro lado, como se puede ver, pr´acticamente nunca el comprador llega a gastar el total del presupuesto. Esto es beneficioso en dos sentidos. El comprador
4. Los transportistas
83
Figura 5.4: Evoluci´on de la ventas con todos los agentes siguiendo la estrategia de participar primero en las subastas cuyos agricultores est´an m´as cerca.
Figura 5.5: Media del coste de transporte por estrategia. se encontrar´a especialmente satisfecho si adem´as de recibir el producto esperado, le ha costado menos de lo que ten´ıa previsto. Por otro lado, este margen puede ser usado para facturar al comprador los servicios del sistema, por ejemplo cobrando a ´este un tanto por ciento de dicho margen. Creemos que el comprador estar´ıa dispuesto a asumir dicho cobro, si globalmente el producto le ha costado menos de lo esperado.
4.1.
Totales
Por u ´ltimo veremos las ganancias medias de cada agricultor y cada transportista para ver que estrategia hace un reparto m´as equitativo entre cada uno de estos. Atendiendo a la gr´aficas 5.9 y 5.10 se puede ver que tanto las estrate-
84
Cap´ıtulo 5. Resultados y conclusiones
Figura 5.6: Evoluci´on de ventas con los agentes siguiendo la estrategia generosa. gias de orden aleatorio como la del generoso son las que hacen un reparto m´as equitativo entre los distintos agricultores.
4. Los transportistas
85
Figura 5.7: Evoluci´on de la ventas con distribuciones de las estrategias en las que predomina una de ellas.
86
Cap´ıtulo 5. Resultados y conclusiones
Figura 5.8: Evoluci´on de la ventas frente al beneficio de los transportistas.
4. Los transportistas
Figura 5.9: Ventas medias de los agricultores por estrategia.
Figura 5.10: Ganancias medias de los transportistas por estrategia.
87
Cap´ıtulo 6 Trabajo futuro
Aunque el prototipo funciona alcanzando los objetivos inicialmente planteados, hay muchas l´ıneas de mejora y depuraci´on. Vamos a ver cada uno de los puntos, separando la interfaz web y el SMA.
1.
Servicio de notificaciones
Actualmente el servicio de notificaciones es parte de la l´ogica de portal web. Por otro lado los servidores web tienen establecido un tiempo espera m´aximo por petici´on para evitar determinados tipos de ataques. En estas circunstancias, cuando el env´ıo de las notificaciones tarda m´as de este tiempo m´aximo se produce un timeout por parte del servidor que corta el proceso env´ıo de las notificaciones. Para solucionar el problema, lo ideal es crear un servicio independiente que se encargue de consultar peri´odicamente si existen notificaciones que enviar y gestione dichos env´ıos.
2.
La interfaz web
Se ha implementado la parte m´as esencial de la interfaz web y se pueden hacer muchas mejoras en ella, proporcion´andole m´as funcionalidad. Vamos a ver algunas de estas: 89
90
Cap´ıtulo 6. Trabajo futuro
Sistema de puntuaci´ on. Un sistema de puntuaci´on al estilo de eBay ser´ıa interesante. De esta forma los agentes podr´ıan tenerlo en cuenta para implementar preferencias por unos u otros agricultores y transportistas. Selecci´ on de agricultores. Siendo realistas es muy posible que los compradores finales quieran realizar alguna selecci´on de aquellos agricultores a los que comprar, por lo que ser´ıa necesario agregar dicha funcionalidad al sistema. Gesti´ on de la rutas. Un elemento muy atractivo para los transportistas ser´ıa el proporcionales herramientas para poder gestionar las rutas y de repartos. El haber contrato un transporte no implica que se entregue de inmediato, sino que este puede esperar varios d´ıas para ser recogido y entregado, seg´ un la necesidades del comprador. Calculo de gastos del transportista. Los par´ametros de c´alculo del gasto de transporte (gasto de combustible, tiempo de carga y descarga, ...) actualmente es com´ un para todos los transportistas, pero este puede variar de uno a otro, por lo que ser´ıa necesario hacerlo configurable para cada uno.
3.
Sistema multiagente
Se pueden estudiar varios aspectos interesantes que podr´ıan ser integrados dentro del SMA y que podr´ıan mejorar los resultados.
3.1.
C´ alculo de rutas
El SMA actualmente hace una estimaci´on no o´ptima del tiempo de transporte para ir desde un punto a otro. Agregar un agente destinado a calcular y proporcionar los resultados a los otros agentes ser´ıa muy interesante para obtener resultados m´as reales.
3.2.
VRP (Vehicule Routing Problem)
La resoluci´on del problema VRP (Vehicule Routing Problem) mediante algoritmos gen´eticos y de enfriamiento simulado fue el tema de mi trabajo de fin de carrera de la Ingenier´ıa T´ecnica de Inform´atica. El realizar este c´alculo antes
3. Sistema multiagente
91
de la subastas y asignar cada ruta a cada transportista puede ser un elemento de optimizaci´on importante.
3.3.
Subasta de m´ ultiples intereses
Como ya se mencion´o a lo largo del trabajo, cuando un agente comprador entra en una subasta de un agricultor, este debe dejar reservado parte de su dinero para contratar el transporte. Normalmente este dinero reservado es excesivo y podr´ıa ser optimizado con un sistema en el que las subasta estuviera compuesta por el agricultor, los compradores y los transportistas al un´ısono en busca del mejor acuerdo conjunto.
3.4.
Problema del rechazo
El sistema permite a un comprador rechazar un acuerdo. En tal caso, la regla del comprador vuelve a entrar en el proceso de subastas en curso. Puesto que conforme avanza el tiempo el n´ umero de participantes es menor, existe una gran probabilidad de que el siguiente acuerdo consiga un acuerdo de menor precio. Esta es una situaci´on que puede ser usada por lo usuarios y que convendr´ıa ser controlada de alguna forma por el sistema, como por ejemplo obligando a pagar el coste anterior anteriormente acordado o no permitiendo que vuelva a entrar el proceso de subastas.
Bibliograf´ıa [1] P. Dur´an Juez, Teor´ıa de subastas y reputaci´on del vendedor, Comisi´on Nacional del Mercado de Valores, 2003 [2] V. Krishna, Auction Theory, Academic Press, 2009 [3] J. Momparler, M. Hidalg, Modelo de subastas y su aplicaci´on a los concursos, XIII Jornadas de ASEPUMA, 2005 [4] A. Mas. Agentes Software y sistemas multi-agente: Conceptos, arquitecturas y aplicaciones. Pearson Education, 2004. [5] G. Weiss, Multiagent systems, MIT Press,2013 [6] Foundation for Intelligent Physical Agents page, http://www.fipa.org. [7] S. Poslad, Specifying Protocols for Multi-Agent Systems Interaction, 2007 [8] K. Sycara, A. Pannu, M. Williamson and D. Zeng. Distributed Intelligent Agents. IEEE Expert, 11(6):36-46. 1996 [9] H. Knublauch. Extrem Programming of Multi-Agent Systems, 2002 [10] P. Geovanny, O. Kirby. Metodolog´ıas de desarrollo de SMA, 2013 [11] S.A. DeLoach, The MaSE Methodology, 2004. [12] L. Padgham, M. Winikoff. Developing intelligent agent systems : a practical guide, 2004 [13] P. Besciani, A. Perini, F. Giunchiglia, J. Mylopoulos. Tropos: An agentoriented software devolopment methodology. Autonomous Agents and Multi-Agent Systems, 2004 [14] P. Guiorgini, M. Kolp, J. Mylopoulos, J. Castro. Tropos: A requirementsdriven methodology for agent-oriented software. Agent-Oriented Methodologies, pagina 20. 2005 93
94
Bibliograf´ıa
[15] Tropos Project page, http://www.troposproject.org/ [16] M. Conssentino. From requirements to code with the passi methodology. 2005 [17] AgentLink page, http://www.agentlink.org [18] A. Sturm, O. Shehory, The Evolution of MAS Tools, 2014 [19] Vickrey, W. Counterspeculation, auctions and competitive sealed tenders. Journal of Finance 16 (1961), 8-37 [20] T.J. Marchetti, A.J. Garc´ıa. Evaluaci´on de Plataformas para el Desarrollo de Sistemas Multiagente, 2003