MARL-Ped+Hi map: Aumen ando la
p oduc i idad de simulaciones basadas en
agen es con una he amien a de a ays
dis ibuidos
Edua do Rod iguez-Gu iez 1, F ancisco Ma inez-Gil 2, Juan Manuel O du˜na-Hue as 3,
A u o Gonzalez-Esc ibano 4
Resumen— Los sis emas Mul i-agen e es ´an cons i-
uidos po piezas so wa e llamadas agen es que son
capaces de pe cibi el en o no y ac ua en ´el de man-
e a au ´onoma. MARL-Ped es un modelo Mul i-agen e
de pea ones donde cada agen e (pea ´on) ap ende
el compo amien o adecuado pa a la simulaci´on de
di e en es si uaciones (aglome aciones, c uces, e ac-
uaciones de ecin os ce ados,...). MARL-Ped u iliza
el es ´anda de paso de mensajes MPI pa a su ex-
plo aci´on en sis emas dis ibuidos de o ma po able.
P og ama u ilizando di ec amen e sis emas de paso
de mensajes equie e un g an es ue zo si se desean in-
oduci pol´ı icas de epa o de ca ga lexibles y que
se adap en a la pla a o ma de des ino. Hi map es
una biblio eca de unciones pa a acili a la p og a-
maci´on de aplicaciones pa alelas, basada en a ays dis-
ibuidos. In oduce abs acciones pa a la pa ici´on
y mapeo anspa en e de a ays, as´ı como pa a con-
s ui pa ones de comunicaci´on lexibles que se adap-
an a la pa ici´on de o ma au om´a ica.
En es e abajo p esen amos la me odolog´ıa y
´ecnicas de Hi map aplicadas a la simulaci´on de
agen es, u ilizando MARL-Ped como caso de es u-
dio. Mos amos concep ual y expe imen almen e las
en ajas de aplica Hi map pa a aumen a la p oduc-
i idad de es e ipo de aplicaciones, an o en adap -
abilidad como en endimien o, pe mi iendo ag upa
agen es en p ocesos y educiendo los cos es de comu-
nicaci´on y sob eca gas de o ma anspa en e.
Palab as cla e— Agen es, simulaci´on de mul i udes,
paso de mensajes, he amien as de p og amaci´on, a -
ays dis ibuidos
I. In oducci´
on
Los sis emas Mul i-agen e [1], [2] es ´an basados
en la cons ucci´on de p ocesos compu acionales in-
dependien es denominados agen es que ienen la
capacidad de pe cibi el en o no y, de mane a
au ´onoma, oma decisiones ace ca de las ac i idades
a lle a a cabo pa a consegui sus obje i os. Es e
ipo de so wa e es especialmen e in e esan e pa a
es udia sis emas complejos, como la din´amica de
los pea ones, donde la in e acci´on au ´onoma de los
indi iduos gene a compo amien os globales del sis-
ema. MARL-Ped [3] es un modelo de pea ones
Mul i-agen e dis ibuido donde cada agen e (pea ´on)
ap ende un compo amien o p opio, que pe mi e
1Dp o. de In o m´a ica, Uni . Valladolid, e-mail:
[email p o ec ed]
2Dp o. de In o m´a ica, Uni . Valencia, e-mail:
[email p o ec ed]
3Dp o. de In o m´a ica, Uni . Valencia, e-mail:
[email p o ec ed]
4Dp o. de In o m´a ica, Uni . Valladolid, e-mail:
[email p o ec ed]
simula a g upos de pea ones (desde unos pocos
has a mul i udes) en di e en es escena ios como con-
ges iones, c uces, a ance en colas e c. La can idad
de agen es necesa ia pa a simula muchedumb es, as´ı
como la g an ca ga compu acional que implica an o
el p oceso de ap endizaje de los agen es como la sim-
ulaci´on de su compo amien o y del en o no, hacen
de MARL-Ped un buen ejemplo de aplicaci´on pa -
alela ap opiada pa a en o nos de al o endimien o.
La e si´on ac ual de MARL-Ped u iliza el es ´anda
de paso de mensajes MPI pa a su explo aci´on en sis-
emas dis ibuidos de o ma po able. P og ama
u ilizando di ec amen e sis emas de paso de men-
sajes equie e un g an es ue zo si se desean in o-
duci pol´ı icas de epa o de ca ga lexibles y que se
adap en a la pla a o ma de des ino.
Po o a pa e, Hi map [4] es una biblio eca de
unciones dise˜nada pa a acili a la p og amaci´on de
aplicaciones pa alelas, basada en a ays dis ibuidos.
In oduce abs acciones pa a la pa ici´on y mapeo
au om´a ico de a ays, as´ı como pa a cons ui pa-
ones de comunicaci´on lexibles que se adap an a la
pa ici´on de o ma au om´a ica.
En es e abajo p esen amos la me odolog´ıa y
´ecnicas de Hi map aplicadas a la simulaci´on de
agen es, u ilizando MARL-Ped como caso de es udio.
Mos amos las en ajas de aplica Hi map pa a au-
men a la p oduc i idad de es e ipo de aplicaciones,
an o en es ue zo de desa ollo, como en adap abil-
idad y endimien o. Los esul ados mues an que
la e si´on de MARL-Ped u ilizando Hi map es m´as
simple en ´e minos de c´odigo, y a la ez m´as lex-
ible. Hi map pe mi e de o ma anspa en e ag u-
pa agen es en p ocesos pa a educi los cos es de
comunicaci´on y e i a sob eca gas, pe mi iendo una
mayo escalabilidad y una explo aci´on m´as e icien e
de los ecu sos de c´ompu o.
El es o del a ´ıculo se es uc u a de la siguien e
o ma. La secci´on II p esen a abajo elacionado.
La secci´on III desc ibe los undamen os de MARL-
Ped y Hi map. La secci´on IV desc ibe la aplicaci´on
de Hi map al p og ama o iginal. La secci´on V p e-
sen a un es udio expe imen al en ´e minos de es-
ue zo de desa ollo y escalabilidad de la soluci´on
conseguida. Finalmen e la secci´on VI p esen a las
conclusiones y abajo u u o.
II. T abajo elacionado
Los es udios de din´amicas de pea ones se han de-
sa ollado a lo la go de los ´ul imos 75 a˜nos. Aunque
la apa ici´on de los p ime os modelos de pea ones
basados en modelos ´ısicos de luidos y las ecuaciones
cin´e icas de gases son de los a˜nos 60 del siglo XX,
el e dade o desa ollo de modelos acon eci´o con el
auge del uso de compu ado es de bajo cos e a pa -
i de la d´ecada de los 80 del pasado siglo. En e
los modelos de pea ones que m´as ´exi o han enido
en e la comunidad cien ´ı ica debido a su e sa ili-
dad y simplicidad se encuen a el modelo de ue zas
sociales [5], los modelos basados en au ´oma as celu-
la es [6], los modelos con inuos basados en ecuaciones
de cin´e ica de gases [7] y los basados en agen es [8].
Den o de es e ´ul imo g upo, en los ´ul imos a˜nos
se han ealizado abajos pa a inco po a ´ecnicas
de ap endizaje m´aquina (machine lea ning) a es e
campo [9]. Los sis emas de ap endizaje aplicado al
modelado de pea ones iene ca ac e ´ıs icas muy in-
e esan es que los se˜nalan como una al e na i a a los
sis emas m´as cl´asicos indicados an e io men e. En-
e ellas la m´as des acada consis e en que es el p opio
agen e o pea ´on el que ap ende su compo amien o,
libe ando al p og amado de es a a ea. Siendo la
din´amica de g upos de pea ones un p oblema com-
plejo, es a a ea se ha con e ido en la di icul ad
p incipal de odo modelo de pea ones.
Po o a pa e, a ni el compu acional la simulaci´on
mic osc´opica de pea ones en escena ios de g andes
densidades (mul i udes) cons i uyen un desa ´ıo en
el que son necesa ias nue as es a egias de p oce-
samien o pa alelo y o ganizaci´on y paso de in o -
maci´on. En es e sen ido, en el abajo de Lozano e
al. [10] se p opone una a qui ec u a escalable basada
en un sis ema clien e-se ido je ´a quico que sopo a
del o den de miles de agen es. En los abajos pos-
e io es [11], [12], [13] se p opone una a qui ec u a
pa alela pa a simulaci´on de muchedumb es en la que
se ido es in e conec ados compa en la ca ga com-
pu acional p o enien e de dos cuellos de bo ella: el
se ido de acciones y la base de da os que ep esen a
el e eno. En el abajo de Yilmaz e al. [14] se p o-
pone una a qui ec u a basada en CUDA con l´ogica
di usa que se us´o pa a simula un ma a ´on con m´as
de un mill´on de co edo es.
Hi map o ece una capa de abs acci´on in e me-
dia en e el manejo manual en paso de mensajes de
es uc u as dis ibuidas y los lenguajes PGAS (Pa -
i ioned Global Ad ess Space), como Chapel [15], o
UPC [16]. Es os modelos no p opo cionan su icien es
he amien as pa a pe mi i el pa alelismo de p oce-
sos je ´a quicos en en o nos h´ıb idos como Hi map.
Hi map pe mi e adem´as cons ui pa ones de co-
municaci´on eu ilizables en iempo de ejecuci´on que
se adap an a la pa ici´on de da os, gene ando un
n´ume o m´ınimo de comunicaciones ag egadas. Es o
pe mi e consegui , po ejemplo, una e iciencia com-
pa able a UPC educiendo incluso la complejidad
de p og amaci´on [4]. Hi map se u iliza como capa
de ejecuci´on en el sis ema de p og amaci´on pa alela
ENVIRONMENT AGENT
LEARNING AGENT
M3 M4 M5
M0 M1 M2
Communica ion
Module
Si ua ion Awa eness
&
Rewa d Func ion
Ac ion
Rewa d &
Senso iz.
Communica ion
Module
Raw Senso iza ion
Ac ions
ODE
Physics Module Rewa ds
Ac ion
Fea u e Ex ac ion
Module
Gene . S a e + Rewa d
Lea ning
Algo i hm
Value Func ion
∑iɸiθi
Decision Module
Gene aliza ion Module
i
Fig. 1. Esquema de los ipos de agen es y su elaci´on en
MARL-Ped.
T asgo [17], que o ece una ap oximaci´on simila a
los lenguajes PGAS. Hi map ex iende las uncionali-
dades de c eaci´on de je a qu´ıas y de epa o de da os
de o as biblio ecas o modelos de a ays dis ibuidos,
po ejemplo HTAs [18] o Pa ay [19]. En e o as
cosas pe mi e la u ilizaci´on de pol´ı icas de pa ici´on
anspa en es e in e cambiables, egula es o i egu-
la es, de inidas como m´odulos con un in e az com´un.
Es o elimina la necesidad de oma decisiones sob e
la g anula idad y sinc onizaci´on en di e en es ni eles
je ´a quicos. Hi map ha sido ambi´en ex endido pa a
sopo a es uc u as de da os como ma ices dispe -
sas o g a os, usando la misma me odolog´ıa e in e -
az [20].
III. MARL-Ped y Hi map
A. MARL-Ped
MARL-Ped es un sis ema mul iagen e pa a mod-
elado y simulaci´on de pea ones que u iliza ap en-
dizaje po e ue zo ( ein o cemen lea ning, RL)
pa a ap ende el compo amien o indi idual de cada
pea ´on (agen e) en un de e minado escena io (con-
ges i´on, e acuaci´on de un ecin o ce ado, ci culaci´on
po un pasillo con lujos de mo imien o con a -
ios,...). El obje i o del algo i mo de ap endizaje
RL consis e en calcula una unci´on de con ol (lla-
mada unci´on de alo en el campo de RL) que in-
dica ´a al pea ´on qu´e acci´on oma en cada momen o
en unci´on del es ado local pe cibido. Exis en en
MARL-Ped dos clases de agen es: los agen es pea ´on,
que ejecu an los algo i mos de ap endizaje po e-
ue zo y almacenan la unci´on de con ol ap endida,
y el agen e en o no que ejecu a el sis ema ´ısico que
simula a los pea ones en el escena io y que senso iza
el es ado en el que se encuen a cada pea ´on den-
o de es e escena io. El escena io es un mundo i -
ual 3D en el que el mo o ´ısico Open Dynamic En-
gine (ODE) se enca ga de simula las colisiones y las
ue zas que mue en a los pea ones. En la Figu a 1
apa ece una desc ipci´on g ´a ica del sis ema.
Es posible obse a en la Figu a 1 que an o los
agen es pea ones (en la igu a “Lea ning Agen s”)
como el agen e en o no (en la igu a “En i onmen
agen ”) es ´an compues os de di e en es m´odulos un-
cionales. Exis en dos modos de uncionamien o en
MARL-Ped: modo de ap endizaje y modo de sim-
ulaci´on. Ambos modos es ablecen el mismo ipo de
comunicaci´on en e los agen es y el en o no. La ´unica
di e encia es que en el modo de ap endizaje los algo-
i mos de RL es ´an ac i os y la unci´on de con ol se
a calculando inc emen almen e.
El modo de uncionamien o es s´ınc ono y consis e
en un ciclo cl´asico compues o de obse aci´on-acci´on-
ecompensa. Conc e amen e el ciclo se compone de
los siguien es pasos:
1. El agen e en o no consul a a ODE la si uaci´on
din´amica de cada pea ´on que consis e en
posici´on, elocidad, dis ancia a los npea ones
m´as ce canos y dis ancia a los nobje os m´as
ce canos. Si es amos en el modo ap endizaje,
el agen e en o no p epa a una ecompensa pa a
cada uno de los agen es pea ones en unci´on de
a ios hechos:que el pea ´on haya llegado a su ob-
je i o, que se haya chocado con a o o pea ´on
u obje o, e c.
2. El agen e en o no ansmi e la in o maci´on del
es ado y la ecompensa de cada agen e al sis-
ema pa a que sea ecogida po los agen es.
3. Cada agen e ecibe la in o maci´on del en o no
y p epa a con ella las ca ac e ´ıs icas espec´ı icas
que de inen el es ado pa a el algo i mo de ap en-
dizaje y la se˜nal de ecompensa. Ambas in-
o maciones son usadas po el algo i mo de RL
pa a modi ica la unci´on de con ol que ambi´en
es ´a ges ionada po el agen e pea ´on (“Lea ning
agen ” en la Figu a 1). En el modo de simu-
laci´on, la in o maci´on del es ado si e pa a con-
sul a di ec amen e ala unci´on de con ol mien-
as que los algo i mos de RL es ´an desac i a-
dos.
4. El agen e consul a a la unci´on de con ol la
nue a acci´on que, en el es ado ac ual, se debe
de ejecu a . Las acciones consis en en una mod-
i icaci´on de la di ecci´on y apidez con la que se
mue e el pea ´on.
5. Los agen es ansmi en las acciones al agen e
en o no que es el enca gado de aduci las a ac-
ciones ´ısicas que son ejecu adas po ODE en el
en o no i ual.
La comunicaci´on de da os en MARL-Ped se
es ablece en e el agen e en o no y los agen es
pea ones, no habiendo comunicaci´on en e los
agen es pea ones. Exis e un doble lujo de da os,
que se puede obse a en la Figu a 1. Un lujo co-
munica los da os de senso izaci´on del es ado de cada
agen e y la co espondien e ecompensa desde el en-
o no has a cada uno de los agen es ( lechas de colo
e de). O o lujo comunica la siguien e acci´on a e-
aliza po cada uno de los agen es al en o no ( lechas
de colo ama illo). Es e ciclo desc i o se ejecu a un
n´ume o de eces que es a su ez un pa ´ame o de con-
igu aci´on del sis ema. En el modo ap endizaje con
decenas de agen es, es e ciclo puede epe i se desde
cien os de miles de eces has a millones de eces.
B. Hi map
Hi map [4] es una biblio eca de unciones pa a la
ges i´on y dis ibuci´on je ´a quica de es uc u as de
da os en iempo de ejecuci´on. T abaja sob e a ays
densos y ha sido ambi´en ex endida pa a sopo a es-
uc u as de da os como ma ices dispe sas o g a os,
usando la misma me odolog´ıa e in e az [20]. Se basa
en un modelo SPMD (Single P og am Mul iple Da a)
y en el pa adigma de paso de mensajes. Hi map de-
ine a ias abs acciones pa a esc ibi p og amas pa -
alelos que manejan es uc u as de da os dis ibuidas.
La biblio eca se puede di idi en es pa es:
B.1 M´e odos de iling
De inici´on y manipulaci´on de a ays y iles. Es-
os m´e odos se pueden usa de mane a independien e
al es o de uncionalidades de Hi map, pa a mejo a
la localidad en el c´odigo secuencial, as´ı como pa a
gene a dis ibuciones de da os manualmen e pa a la
ejecuci´on en pa alelo. Se de inen obje os pa a ep e-
sen a los dominios de ´ındices de las es uc u as de
da os de o ma compac a. Se de ine una clase de ob-
je os denominada Tile que ep esen a la asociaci´on
en e elemen os del espacio de ´ındices y los da os, y
pe mi en el acceso o modi icaci´on de los mismos. Los
iles pueden c ea se c ea se de o ma que en un p o-
ceso s´olo se dispone localmen e de una pa e del espa-
cio de ´ındices ob eni´endose la es uc u a dis ibuida.
B.2 M´e odos de mapping
Incluye m´odulos in e cambiables que imple-
men an pol´ı icas pa a pa iciona dominios au-
om´a icamen e, dependiendo de una opolog´ıa i -
ual seleccionada en iempo de ejecuci´on. Pe mi en
c ea obje os denominados Layou s que pueden se
consul ados espec o a la pa e de un dominio de
´ındices que es asignada an o localmen e, como o a
cualquie o o p oceso emo o. Adem´as, se es able-
cen elaciones de ecindad en ´e minos de las eglas
de la opolog´ıa i ual escogida.
B.3 M´e odos de comunicaciones
Es as unciones son una abs acci´on del modelo
de paso de mensajes pa a comunica iles o pa es de
iles en e p ocesado es i uales. Pe mi e c ea ob-
je os que almacenan la in o maci´on necesa ia pa a
empaque a e in e cambia los da os seleccionados
en e p ocesado es. Hi map p o ee de m´ul iples in-
e aces de c eaci´on que implemen an di e sos ipos
de comunicaciones pun o-a-pun o, colec i as, o pa-
ones m´as complejos compues os de m´ul iples co-
municaciones de di e sa na u aleza o sob e di e -
sos iles. Las in e aces de c eaci´on incluyen un ob-
je o de ipo Layou , que es consul ado in e namen e
pa a decidi qu´e iene que comunica se y a qui´en,
gene ´andose au om´a icamen e la in o maci´on in e na
necesa ia. Po an o, es os obje os se adap an ans-
pa en emen e en el momen o de su c eaci´on a la
pla a o ma de ejecuci´on y la dis ibuci´on de da os
A
P...
A
Pk-1
E
Pk
A
P0
A
P1
A A A A A A A A A A A A
P0
E
A A
A
P1
A A
A
P...
A A
A
Pk
A A
A
A A A A A A A A A
A A A
Fig. 2. Es uc u a gene al de la simulaci´on y el epa o de
a eas en e p ocesado es en MARL-Ped o iginal (a iba)
y as aplica Hi map (abajo).
u ilizada. Los obje os de comunicaci´on son eu iliz-
ables. El m´e odo que ealmen e ejecu a la comu-
nicaci´on se puede in oca en cualquie momen o de-
spu´es de su c eaci´on, an as eces como sea necesa io
a lo la go de la aplicaci´on. In e namen e se basan en
el es ´anda MPI, u ilizando ´ecnicas e icien es como
la c eaci´on de ipos de da os de i ados, comunica-
ciones as´ınc onas, e c.
IV. Aplicaci´
on de la me odolog
´
ıa y
´
ecnicas de Hi map
En es a secci´on se desc ibe c´omo aplica la
me odolog´ıa y ´ecnicas p opias de Hi map a aplica-
ciones de simulaci´on basadas en agen es, u ilizando
MARL-Ped como caso de es udio.
A. Cambios es uc u ales
La es uc u a de la aplicaci´on MARL-Ped ha sido
edise˜nada. La e si´on de Hi map aplica el concep o
de a ays dis ibuidos pa a ag upa agen es en p o-
cesos, en luga de u iliza un p oceso MPI pa a cada
agen e, m´as o o pa a la simulaci´on del en o no. En
la pa e supe io de la igu a 2 se ap ecia la dis-
ibuci´on concep ual de la compu aci´on en MARL-
Ped o iginal. Cada p oceso ejecu a el c´odigo de un
agen e. El ´ul imo p oceso ejecu a el c´ompu o de la
simulaci´on del en o no. Los obje os de clase RLA-
gen yRLEn i onmen ienen un m´e odo que in e -
namen e ejecu a epe i i amen e el bucle de simu-
laci´on.
Una p ime a decisi´on de dise˜no pa a la nue a
e si´on es epa i los agen es en e los p ocesos
disponibles sin ese a un p oceso pa a el en o no.
El c´odigo del en o no lo ejecu a ´a uno de los p oce-
sos que ambi´en iene agen es asignados ya que la
compu aci´on p incipal de los agen es y del en o no
se al e nan sin solapa se en el iempo.
Hi map p o ee de las he amien as necesa ias
pa a dis ibui equi a i amen e los agen es en e los
p ocesos disponibles ( e la pa e de abajo en la
igu a 2). Cada p oceso iene que pode ejecu a
en cada i e aci´on de simulaci´on el c´odigo de a ios
agen es, y en el caso del p oceso designado pa a ello,
adem´as ejecu a el c´odigo del en o no. Po an o, el
bucle de simulaci´on no puede es a den o de los ob-
je os de agen e o en o no. Es necesa io edise˜na la
aplicaci´on pa a que el bucle de simulaci´on lo ejecu e
el p og ama p incipal, que debe i e a a su ez depen-
diendo del n´ume o de agen es asignados al p oceso.
Pa a ello se elimina el bucle de simulaci´on den o
del co espondien e m´e odo de la clase de agen es y
en o no. Se ans o man los m´e odos a los que se in-
ocaba den o de ese bucle en m´e odos p´ublicos. Y
se aslada la l´ogica de con ol de dichas in ocaciones
al nue o bucle de i e aciones de simulaci´on en el p o-
g ama p incipal. Se ealiza lo mismo con el en o no,
odeando la l´ogica de con ol del mismo, aho a en
el p og ama p incipal, con un condicional pa a que
s´olo sea ejecu ado po un p oceso. Hi map dis ingue
pa a cada g upo de p ocesos a uno de ellos como el
l´ıde del g upo. Es e p oceso puede iden i ica se a
si mismo a a ´es de una llamada a una unci´on, y
po an o es el seleccionado pa a ejecu a la l´ogica
del en o no.
B. A ays dis ibuidos y pa ones de comunicaci´on
Las comunicaciones basadas en MPI de MARL-
Ped o iginal se han subs i uido po el manejo de a -
ays dis ibuidos con Hi map. Pa a ello, las es uc-
u as de da os implicadas en las comunicaciones se
subs i uyen po es uc u as de ipo Hi Tile. La es-
uc u a Hi Tile debe especializa se al comienzo del
p og ama seg´un los di e en es ipos de da os de cada
a ay que se aya a decla a y maneja con Hi map.
En ase de inicializaci´on del p og ama se c ean los
a ays dis ibuidos y obje os de ipo Hi Com con las
especi icaciones de las comunicaciones que se ´an in-
ocadas en las i e aciones del bucle de simulaci´on.
Pa a las se˜nales de con ol s´olo es necesa ia una a i-
able de ipo en e o en cada p oceso, independien e-
men e del n´ume o de agen es que se le asignen. Pa a
cada lujo de da os en e el agen e que ges iona el en-
o no y los agen es pea on, se decla an dos a ays dis-
ibuidos con un dominio de ´ındices igual al n´ume o
de agen es pea ´on. En uno se u iliza una pol´ı ica
de dis ibuci´on que epa e y asigna los elemen os de
o ma equi a i a en e los p ocesos. En el o o se u i-
liza una pol´ı ica que dis ibuye odos los elemen os
al p oceso que ejecu a el en o no. Hi map pe mi e
con una ´unica llamada a una unci´on cons ui un
obje o Hi Com que implemen a un pa ´on que e-
dis ibuye los da os desde un a ay dis ibuido con
una pol´ı ica cualquie a, a los co espondien es ele-
men os locales o emo os de o o a ay con el mismo
dominio, pe o dis ibuido con o a pol´ı ica di e en e.
Es a ´ecnica pe mi e cons ui obje os de comuni-
caci´on que mo e ´an de o ma anspa en e los da os
en e las dos copias de cada a ay, la ealmen e dis-
ibuida y la que iene odo el dominio en el p oceso
del en o no. El pa ´on de comunicaci´on se adap a
a los esul ados de las pol´ı icas de pa ici´on inde-
pendien emen e del n´ume o de agen es y p ocesos.
Es e mecanismo soluciona de una o ma ´unica la con-
s ucci´on de los lujos de comunicaci´on necesa ios.
V. Es udio expe imen al
Es a secci´on desc ibe el es udio expe imen al eal-
izado pa a comp oba las en ajas de aplica Hi map
en p og amas de simulaci´on basados en agen es como
MARL-Ped. El es udio se ocaliza en mos a la
mayo capacidad de escalado en cuan o a n´ume o
de agen es, y la p edic ibilidad de los pa ´ame os de
ejecuci´on pa a ob ene un mayo endimien o.
A. Me odolog´ıa de expe imen aci´on
En es e es udio expe imen al se ob ienen medi-
das de iempos de ejecuci´on de las dos e siones de
c´odigo; MARL-Ped o iginal y la e si´on u ilizando
Hi map. Se p esen an los mismos en ´e minos de
escalabilidad.
En es e a ´ıculo nos ocalizamos en la pa e
del p oceso de ap endizaje, que es compu acional-
men e la m´as cos osa, y que no implica ope a-
ciones de en ada/salida du an e la ase de com-
pu aci´on/comunicaci´on. Los c´odigos han sido in-
s umen ados pa a medi el iempo de ejecuci´on de
cada p oceso dis ibuido desde el momen o en que
comienza la inicializaci´on de es uc u as elacionadas
con el pa alelismo (MPI o Hi map), has a el mo-
men o en que e mina la ejecuci´on del ap endizaje,
jus o an es de comenza a esc ibi en iche os los e-
sul ados. De las mediciones ob enidas en cada p o-
ceso, se u iliza como esul ado de la medida el iempo
mayo , es deci , el del p oceso que ha a dado m´as
en e mina . Cada expe imen o se epi e a ias eces
pa a pode comp oba ambi´en la a iabilidad en los
esul ados.
Dado que los iempos de ejecuci´on de un en e-
namien o comple o son ex emadamen e la gos, pa a
pode explo a un espacio de b´usqueda amplio en
cuan o a pa ´ame os de ejecuci´on, se ha limi ado el
p og ama a la ejecuci´on de s´olo 100 i e aciones de
en enamien o en odos los casos. Como se e ´a en
los esul ados, es e n´ume o de i e aciones p oduce
una ca ga y un n´ume o de ases de comunicaci´on y
sinc onizaci´on su icien emen e ep esen a i os. En
odos los casos se ejecu a un escena io de ejemplo
u ilizado y alidado en abajos an e io es [3]. El
escena io ep oduce un dilema de na egaci´on cl´asico
en din´amica de pea ones denominado “sho es pa h
s quickes pa h”. En es e escena io un g upo de
pea ones debe pasa de una habi aci´on a un luga
obje i o si uado ue a de ´es a. Exis en dos salidas
y una es ´a mas ce ca del obje i o que la o a. Los
agen es deben ap ende que si odos in en an sali
po la pue a m´as ce cana, se o ma ´a una aglom-
e aci´on que alen iza ´a la e acuaci´on. Una soluci´on
´op ima es la di isi´on del g upo en pea ones que eli-
gen la salida con el camino m´as co o y agen es que
eligen la o a salida, lo que p opo ciona ´a una e ac-
uaci´on m´as ´apida.
En la con igu aci´on seleccionada se han si uado 28
agen es en una habi aci´on ec angula de longi ud de
18 m. con dos salidas posibles de 1 m.de anchu a que
di icul a el paso simul ´aneo de m´as de un pea ´on.
El obje i o de los agen es es alcanza un pun o de
encuen o al o o lado de las salidas.
Los c´odigos se han ejecu ado en di e en es
pla a o mas mul ico e donde las comunicaciones son
menos cos osas y des acan m´as los po enciales o e -
heads asociados, en e o as cosas, a los cambios en
la es uc u a de ejecuci´on, al manejo de las es uc-
u as p opias de Hi map, o a los c´alculos y decisiones
sob e las comunicaciones.
En es e abajo mos amos esul ados ob enidos
en una m´aquina denominada Chime a. Tiene dos
CPUs In el E5-2620 2, a 2˙
10 GHz, con un o al de
12 co es eales, con la opci´on de hype h eading ac-
i ada. Dispone de 8 Gb de memo ia DDR4. El
sis ema ope a i o es Cen OS 7.0 1406 x64. El com-
pilado u ilizado es GCC 4.8.2 con el lag de op i-
mizaci´on -O3. La implemen aci´on de MPI u ilizada
es Mpich 3.1.3.
B. Escalabilidad en n´ume o de agen es
Uno de los obje i os de es e abajo es consegui
una mayo escalabilidad en ´e minos de n´ume o de
agen es, g acias a la es a egia de asocia a ios
agen es a un mismo p oceso con Hi map. El p ime
es udio ealizado comp ueba expe imen almen e la
di e encia de escalabilidad en e la e si´on o iginal
de MARL-Ped y la e si´on que u iliza Hi map. Los
p og amas se han ejecu ado en ase de en enamien o
ijando el n´ume o de p ocesos MPI al n´ume o de
co es disponibles en la m´aquina, aumen ando p o-
g esi amen e el n´ume o de agen es po encima de
ese n´ume o.
Los esul ados se mues an en la igu a 3. En
el caso de MARL-Ped o iginal, el n´ume o de p o-
cesos MPI necesa ios c ece con el n´ume o de agen es
(siendo el n´ume o de agen es m´as uno). La es uc-
u a de es as aplicaciones de simulaci´on, que u ilizan
comunicaciones colec i as con pun os cla os de sin-
c onizaci´on global al ededo de la ejecuci´on del mo o
de simulaci´on, no p esen an la p opiedad de pa allel
slackness, que apa ece en cie as aplicaciones cuando
a ios p ocesos asignados al mismo elemen o de p o-
ceso solapan al e na i amen e ases de compu aci´on
y comunicaci´on. En los esul ados se obse a c´omo
el sob ecos e de ealiza o e subsc ibing (lanza m´as
p ocesos que elemen os de p oceso disponibles) iene
un impac o nega i o en el endimien o y la escala-
bilidad de la aplicaci´on. En la m´aquina Chime a,
con 12 co es y que iene ac i ado hype h eading, el
e ec o es mucho m´as no able a pa i de 24 agen es,
donde MARL-Ped ya u iliza 25 p ocesos MPI. La
o ma en los que los p ocesos se o an en los plan-
i icado es adquie e ele ancia. Po ello se obse an
mayo es di e encias en e los iempos de ejecuci´on
m´ınimos y m´aximos. La e si´on que u iliza Hi map,
man iene una buena escalabilidad, ya que limi a el
n´ume o de p ocesos y ejecu a secuencialmen e den-
o de cada uno el c´odigo de a ios agen es de una
o ma m´as e icien e.

0
50
100
150
200
250
300
350
400
450
500
12 14 16 18 20 22 24 26 28 30
Time (seconds)
Numbe o agen s
Execu ion ime s numbe o agen s (Chime a)
MARL-Ped min
MARL-Ped a g
MARL-Ped max
Hi map 12 p oc min
Hi map 12 p oc a g
Hi map 12 p oc max
Fig. 3. Tiempos de ejecuci´on en elaci´on al n´ume o de agen es. La g ´a ica mues a el iempo de ejecuci´on de 100 i e aciones
de en enamien o pa a un n´ume o c ecien e de agen es. En el caso MARL-Ped o iginal el n´ume o de p ocesos c ece con el
n´ume o de agen es. En el caso de MARL-Ped+Hi map el n´ume o de p ocesos MPI es ijo, e igual al n´ume o de elemen os
de p oceso (co es) eales disponibles.
50
100
150
200
250
300
350
0 5 10 15 20 25
Time (seconds)
Numbe o p ocesses execu ing agen s
Execu ion ime s p ocesses (Chime a)
28 Agen s Hi map
28 Agen s Hi map
28 Agen s Hi map
28 Agen s Hi map
28 Agen s Hi map
28 Agen s Hi map
MARL-Ped a g
Fig. 4. Tiempos de ejecuci´on en elaci´on al n´ume o de p ocesos pa a un n´ume o de agen es ijo. La g ´a ica mues a el iempo
de ejecuci´on de 100 i e aciones de en enamien o. En el caso de MARL-Ped o iginal el n´ume o de p ocesos MPI depende
po dise˜no del n´ume o de agen es y es igual a 29. Pa a MARL-Ped+Hi map se mues an a ias l´ıneas co espondien es a
a ios expe imen os consecu i os, pa a mos a la a iabilidad de los esul ados.
C. Impac o del n´ume o de p ocesos
En es a secci´on se es udia el impac o de modi ica
el n´ume o de p ocesos, y po an o la dis ibuci´on de
agen es po p oceso, en MARL-Ped+Hi map. En la
igu a 4 se obse an los esul ados ob enidos pa a 28
agen es. En odos los casos los esul ados en iem-
pos de ejecuci´on de MARL-Ped+Hi map son mejo es
que en MARL-Ped o iginal debido al e ec o de o e -
subsc ip ion comen ado en la secci´on an e io .
Se obse a que los esul ados u ilizando Hi map
mejo an lige amen e al i epa iendo los agen es en-
e un n´ume o peque˜no pe o c ecien e de p ocesos,
ya que aumen a el pa alelismo. Al supe a el n´ume o
de p ocesos al n´ume o de co es eales (sin con a con
hype h eading), los esul ados empeo an y se uel-
en m´as ines ables, ya que apa ecen e ec os nega-
i os de i ados del o e subsc ip ing. Las pol´ı icas
de plani icaci´on comienzan ambi´en a hace los e-
sul ados m´as imp edecibles. En algunos casos se ob-
iene iempos an buenos como an es de comenza
el o e subsc ip ing, pe o en muchos o os casos em-
peo an. Al supe a el l´ımi e del n´ume o de h eads
disponibles con ando con hype h eading los esul a-
dos, como e a de espe a empeo an no ablemen e.
Es os esul ados indican que en MARL-
Ped+Hi map el n´ume o de p ocesos a escoge
pa a el en enamien o es p edecible. Los iempos
de ejecuci´on son meno es y m´as es ables cuando se
u iliza un n´ume o de p ocesos igual al n´ume o de
elemen os de p oceso eales, sin ene en cuen a la
opci´on de hype h eading.
VI. Conclusiones
En es e a ´ıculo se p esen a la aplicaci´on de las
´ecnicas y he amien as de la biblio eca de manejo
de a ay dis ibuidos Hi map a la simulaci´on basada
en agen es. Se u iliza la aplicaci´on mul i-agen e pa a
simulaci´on de pea ones MARL-Ped como caso de es-
udio. Se mues a c´omo la u ilizaci´on de a ays dis-
ibuidos y pol´ı icas de pa ici´on au om´a icas pe -
mi e ob ene una mayo p oduc i idad y escalabili-
dad, g acias a la capacidad de Hi map de dis ibui
la ca ga en e p ocesos de o ma anspa en e al p o-
g amado . MARL-Ped+Hi map pe mi e hace sim-
ulaciones con un n´ume o mucho mayo de agen es
man eniendo iempos de ejecuci´on es ables y p edeci-
bles.
El abajo u u o incluye ex ende la aplicaci´on de
Hi map a o os ipos de aplicaciones de simulaci´on
elacionadas; in es iga la po encial eliminaci´on de
cuellos de bo ella en las ases de simulaci´on; y u i-
liza la nue a e si´on de MARL-Ped+Hi map pa a
p o undiza en el es udio de la calidad y esul ados
de las simulaciones de muchedumb es con un n´ume o
mucho mayo de agen es.
Ag adecimien os
Es a in es igaci´on ha sido pa cialmen e inanciada
po el Minis e io de Econom´ıa y Compe i i idad
(Spain) y el p og ama ERDF de la Uni´on Eu o-
pea: P oyec o HomP og-He Sys TIN2014-58876-P,
P oyec o TIN2015-66972-C5-5-R y COST P og am
Ac ion IC1305: Ne wo k o Sus ainable Ul ascale
Compu ing (NESUS).
Re e encias
[1] M.J. Woold idge and N.R. Jennings, “In elligen agen s:
heo y and p ac ice,” The Knowledge Enginee ing Re-
iew, ol. 10, pp. 115–152, 1995.
[2] M. Woold idge, Mul i-Agen Sys ems 2nd Edi ion, chap-
e In elligen Agen s, pp. 3–50, MIT P ess, 2013.
[3] F ancisco Ma inez-Gil, Miguel Lozano, and Fe nando
Fe n´andez, “MARL-ped: A mul i-agen ein o cemen
lea ning based amewo k o simula e pedes ian g oups,”
Simula ion Modelling P ac ice and Theo y, ol. 47, pp.
259–275, 2014.
[4] A. Gonzalez-Esc ibano, Y. To es, J. F esno, and D.R.
Llanos, “An ex ensible sys em o mul ile el au oma ic
da a pa i ion and mapping,” IEEE T ansac ions on
Pa allel and Dis ibu ed Sys ems, ol. 25, no. 5, pp. 1145–
1154, 2014.
[5] D. Helbing and P. Moln´a , “Social o ce model o pedes-
ian dynamics,” Phys. Re . E, ol. 51, pp. 4282–4286,
1995.
[6] V. J. Blue and J. L. Adle , “Cellula au oma a mic osim-
ula ion o modeling bi-di ec ional pedes ian walkways,”
T anspo a ion Resea ch Pa B: Me hodological, ol. 35,
no. 3, pp. 293–312, 2001.
[7] R. L. Hughes, “The low o human c owds,” Annu. Re .
Fluid Mech., ol. 35, pp. 169–182, 2003.
[8] C. Reynolds, “S ee ing beha io s o au onomous cha -
ac e s,” in Game De elope s Con e ence, San F ancisco,
Cali o nia., 1999, pp. 763–782, Mille F eeman Game
G oup.
[9] F ancisco Ma inez-Gil, Miguel Lozano, and Fe nando
Fe n´andez, “Mul i-agen ein o cemen lea ning o sim-
ula ing pedes ian na iga ion,” in Adap i e and Lea n-
ing Agen s: In e na ional Wo kshop, ALA 2011, Held a
AAMAS 2011, Taipei, Taiwan. 2012, pp. 54–69, Sp inge
Be lin Heidelbe g.
[10] M. Lozano, P. Mo illo, J. M. O du˜na, V. Ca e o, and
G. Vigue as, “A new sys em a chi ec u e o c owd sim-
ula ion,” J. Ne wo k and Compu e Applica ions, ol.
32, no. 2, pp. 474–482, 2009.
[11] G. Vigue as, M. Lozano, J. M. O du˜na, and F. G imaldo,
“A compa a i e s udy o pa i ioning me hods o c owd
simula ions,” Appl. So Compu ., ol. 10, no. 1, pp.
225–235, Jan. 2010.
[12] Guille mo Vigue as, Juan M. O du˜na, and Miguel
Lozano, “A ead-copy upda e based pa allel se e o
dis ibu ed c owd simula ions,” The Jou nal o Supe -
compu ing, ol. 64, no. 1, pp. 156–166, 2013.
[13] Guille mo Vigue as, Juan M. O du˜na, Miguel Lozano,
and Y on J´egou, “A scalable mul iagen sys em a chi ec-
u e o in e ac i e applica ions,” Science o Compu e
P og amming, ol. 78, no. 6, pp. 715 – 724, 2013, Special
sec ion: The P og amming Languages ack a he 26 h
{ACM}Symposium on Applied Compu ing (SAC 2011);
Special sec ion on Agen -o ien ed Design Me hods and
P og amming Techniques o Dis ibu ed Compu ing in
Dynamic and Complex En i onmen s.
[14] E. Yilmaz, V. Isle , and Y. Y. Ce in, “The i ual
ma a hon: Pa allel compu ing suppo s c owd simula-
ions,” IEEE Compu e G aphics and Applica ions, ol.
29, no. 4, pp. 26–33, 2009.
[15] B.L. Chambe lain, D. Callahan, and H.P. Zima, “Pa allel
p og ammabili y and he chapel language,” In . J. High
Pe o m. Compu . Appl., ol. 21, no. 3, pp. 291–312, aug
2007.
[16] D. A. Mall´on, A. G´omez, J. C. Mou i˜no, G. L. Taboada,
C. Teijei o, J. Tou i˜no, B. B. F aguela, R. Doallo, and
B. Wibecan, “Upc pe o mance e alua ion on a mul i-
co e sys em,” in P oceedings o he Thi d Con e ence
on Pa i ioned Global Add ess Space P og aming Mod-
els, New Yo k, NY, USA, 2009, PGAS ’09, pp. 9:1–9:7,
ACM.
[17] A u o Gonzalez-Esc ibano and Diego R. Llanos,
“T asgo: a nes ed-pa allel p og amming sys em,” The
Jou nal o Supe compu ing, ol. 58, no. 2, pp. 226–234,
2011.
[18] Basilio B. F aguela, Ganesh Bikshandi, Jia Guo,
Ma ´ıA J. Ga za ´aN, Da id Padua, and Ch is oph Von
P aun, “Op imiza ion echniques o e icien h a p o-
g ams,” Pa allel Compu ., ol. 38, no. 9, pp. 465–484,
sep 2012.
[19] Yi eng Chen, Xiang Cui, and Hong Mei, “Pa ay: A uni-
ying a ay ep esen a ion o he e ogeneous pa allelism,”
SIGPLAN No ., ol. 47, no. 8, pp. 171–180, eb 2012.
[20] J. F esno, A. Gonzalez-Esc ibano, and D.R. Llanos,
“Blending ex ensibili y and pe o mance in dense and
spa se pa allel da a managemen ,” IEEE T ansac ions
on Pa allel and Dis ibu ed Sys ems, ol. 25, no. 10, pp.
2509–2519, 2014.