MARL-Ped+Hi map: Towa ds Imp o ing
Agen -based Simula ions wi h Dis ibu ed
A ays
Edua do Rod iguez-Gu iez1, F ancisco Ma inez-Gil2, Juan Manuel O du˜na2,
and A u o Gonzalez-Esc ibano1?
1Dp o. de In o m´a ica, Uni e sidad de Valladolid,
Campus Miguel Delibes s/n, 47011 Valladolid (Spain),
{edua do,a u o}@in o .u a.es
2Dp o. de In o m´a ica, Uni e sidad de Valencia,
A da. Uni e sidad s/n, 46100 Bu jasso (Valencia, Spain)
{ ancisco.ma inez-gil,juan.o duna}@u .es
Abs ac . Mul i-agen sys ems allow he modelling o complex, he -
e ogeneous, and dis ibu ed sys ems in a ealis ic way. MARL-Ped is a
mul i-agen sys em ool, based on he MPI s anda d, o he simula ion
o di e en scena ios o pedes ians who au onomously lea n he bes
beha io by Rein o cemen Lea ning. MARL-Ped uses one MPI p ocess
o each agen by design, wi h a ixed ine-g ain g anula i y. This equi e-
men limi s he pe o mance o he simula ions o a es ic ed numbe o
p ocesso s ha is lesse han he numbe o agen s. On he o he hand,
Hi map is a lib a y o ease he p og amming o pa allel applica ions
based on dis ibu ed a ays. I includes abs ac ions o he au oma ic
pa i ion and mapping o a ays a un ime wi h a bi a y g anula i y,
as well as unc ionali ies o build lexible communica ion pa e ns ha
anspa en ly adap o he da a pa i ions.
In his wo k, we p esen he me hodology and echniques o g anula -
i y selec ion in Hi map, applied o he simula ions o agen sys ems.
As a i s app oxima ion, we use he MARL-Ped mul i-agen pedes ian
simula ion so wa e as a case o s udy o in a-node cases. Hi map al-
lows o anspa en ly map agen s o p ocesses, educing o e subsc ip ion
and in a-node communica ion o e heads. The e alua ion esul s show
signi ican ad an ages when using Hi map, inc easing he lexibili y, pe -
o mance, and agen -numbe scalabili y o a ixed numbe o p ocessing
elemen s, allowing a be e exploi a ion o isola ed nodes.
Keywo ds: Agen s, c owd simula ion, message-passing, p og amming
ools, dis ibu ed a ays
?This wo k has been unded by Spanish MINECO and he EU ERDF p og am un-
de g an s HomP og-He Sys TIN2014-58876-P, TIN2015-66972-C5-5-R, CAPAP-H5
ne wo k TIN2014-53522-REDT, and COST P og am Ac ion IC1305: Ne wo k o
Sus ainable Ul ascale Compu ing (NESUS).
2
1 In oduc ion
Mul i-agen sys ems allow he modelling o complex, he e ogeneous, and dis-
ibu ed sys ems, in a ealis ic way. They assign an agen o each en i y in ol ed
in he eal-wo ld en i onmen [18, 17]. This so wa e pa adigm is pa icula ly ap-
p op ia ed o he s udy o pedes ian dynamics, whe e au onomous in e ac ions
among indi iduals gene a e global sys em beha io s. MARL-Ped [13] is a mul i-
agen dis ibu ed ool whe e each agen (pedes ian) lea ns i s own beha io by
Rein o cemen Lea ning (RL) [15], allowing he simula ion o pedes ian g oups
( anging om a ew ones o c owds) in di e en scena ios (queue o wa ding,
conges ion scena ios, e acua ion o enclosed a es, e c.). The g ea compu a ional
wo kload added by he lea ning p ocess o each agen , oge he wi h he equi ed
numbe o agen s in medium and la ge scale scena ios equi e he use o High Pe -
o mance Compu ing pla o ms. Indeed, he numbe o agen s es ed in lea ning
en i onmen s is usually limi ed by he a ailable compu ing esou ces. MARL-
Ped is based on he MPI message-passing s anda d which p o ides po abili y
ac oss dis ibu ed- and sha ed-memo y en i onmen s. I uses one MPI p ocess
o each agen by design, wi h a ixed ine-g ain g anula i y. This equi emen
limi s he pe o mance o he simula ions o a es ic ed numbe o p ocesso s
ha is lesse han he numbe o agen s. On he o he hand, Hi map [7] is a
lib a y designed o ease he ask o p og amming pa allel applica ions by using
dis ibu ed a ays. I includes abs ac ions o he au oma ic pa i ioning and
mapping o a ays wi h a bi a y g anula i y, as well as he au oma ic cons uc-
ion o lexible communica ion pa e ns adap ed o he pa i ion.
In his wo k, we p esen he me hodology and echniques o g anula i y se-
lec ion in Hi map applied o he simula ions o agen sys ems, using MARL-Ped
as a case o s udy. Hi map allows o anspa en ly map agen s o p ocesses. We
show he bene i s o using his mechanism o imp o ing he pe o mance o
agen -based applica ions execu ed in a es ic ed numbe o p ocessing elemen s
ha is lesse han he numbe o agen s. I elimina es o e subsc ip ion e ec s,
and educes in a-node communica ion o e heads by g ouping communica ions.
The applica ion o he Hi map me hodology does no inc ease he de elopmen
e o . The compa a i e pe o mance e alua ion shows ha he e sion using
Hi map uses mo e e icien ly he compu ing esou ces, becoming mo e scalable
in e ms o he numbe o simula ed agen s.
The es o he pape is o ganized as ollows: Sec ion 2 shows some ela ed
wo k. Sec ion 3 in oduces MARL-Ped and Hi map ools. Nex , Sec ion 4 de-
sc ibes how Hi map has been included in he MARL-Ped o iginal applica ion.
Then, Sec ion 5 p esen s an expe imen al e alua ion o he modi ied applica ion.
Finally, Sec ion 6 discusses some conclusion ema ks and u u e wo k o be done.
2 Rela ed Wo k
Pedes ian-dynamics models we e imp o ed and ex ended in he 80s wi h he
ad en o low cos compu e s. Many di e en models ha e been used: he social
3
o ces model [9], models based on cellula au oma a [2], o con inuum models
based on gas kine ics equa ions [10]. Howe e , he mos ex ended ones a e agen -
based models [14], due o he ease o ex ac ing global beha io as he sum o
indi idual beha io s. In he las yea s, some e o s ha e been made o add
machine lea ning echnique o agen -based pedes ian models [12], in such a
way ha he agen s lea n hei indi idual beha io by hemsel es, eleasing
he p og amme o his ask. Since he beha io lea ning is a complex ask, i
has become he main challenge o he pedes ian models. On he o he hand,
he mic oscopic simula ion o pedes ian in c owded scena ios equi es pa allel
p ocessing. In his sense, speci ic a chi ec u es ha e been p oposed o hese
simula ions [1], and pa allel a chi ec u es, whe e in e connec ed se e s sha e he
compu a ional wo kload, ha e been de eloped [16]. E en a chi ec u es based on
many-co e p ocesso s ha e been used o simula ing a ma a hon o one million
unne s [19].
Hi map o e s an in e media e abs ac ion laye , hal way be ween he man-
ual p og amming o dis ibu ed da a s uc u es on message-passing models,
and PGAS languages (Pa i ioned Global Add ess Space), like Chapel [3] o
UPC [11]. Hi map also p o ides mechanisms o he cons uc ion o eusable
communica ion pa e ns a un ime ha adap o he da a pa i ion, c ea -
ing a low numbe o agg ega ed communica ions. This leads, o example, o a
pe o mance e iciency compa able o UPC, wi h a educed p og amming com-
plexi y and de elopmen e o [7]. Hi map is used as a un ime sys em o he
T asgo pa allel p og amming amewo k [8], ha o e s an app oach simila o
PGAS languages. Hi map ex ends and gene alizes he hie a chy c ea ion and
da a pa i ion unc ionali ies o o he lib a ies o dis ibu ed a ays models,
such as HTAs [5] o Pa ay [4]. I allows o use anspa en pa i ion policies,
ei he egula o i egula , de ined as in e changeable modules wi h a common
in e ace. This hides o he p og amme he decisions abou g anula i y and syn-
ch oniza ion ac oss hie a chical le els. Hi map has also been ex ended o suppo
da a s uc u es such as spa se ma ices, o g aphs, using he same me hodology
and in e ace [6].
3 MARL-Ped & Hi map
3.1 MARL-Ped
MARL-Ped is a mul i-agen sys em ool o pedes ian simula ion which uses
ein o cemen lea ning (RL) [15] in each agen o lea n he indi idual beha io
o a single pedes ian. The pu pose o he RL algo i hm is o compu e a con ol
unc ion which will be used by he agen o selec a a gi en momen he ac ion
o do, based on he senso ized local s a e. MARL-Ped includes wo ypes o
agen s: (a) Pedes ian (Lea ning) agen s, which execu e he RL algo i hms and
s o e he con ol unc ion lea ned; and (b) an En i onmen agen , which execu e
he physical sys em simula ion o he scena io, and senso izes he s a e o each
agen . The scena io is a 3D i ual wo ld whe e he physical model engine named
Open Dynamic Engine (ODE) simula es he collisions and o ces mo ing he
4
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. MARL-Ped scheme showing he ypes o agen s and hei ela ionships.
pedes ians. Fig. 1 shows a g aphic scheme o he sys em, including bo h ypes
o agen s, and he communica ions exchange. These communica ions ake place
exclusi ely be ween he En i onmen agen and he es o agen s.
MARL-Ped has wo wo king modes: lea ning mode and simula ion mode.
Bo h modes include he same communica ions be ween lea ning agen s and he
en i onmen . The only di e ence is ha RL algo i hms a e ac i e in he lea ning
mode o inc emen ally compu e he con ol unc ion, ha will be used in he
simula ion mode. Bo h modes a e synch onous, and composed o he classical
cycle o obse a ion-ac ion- ewa d:
1. The En i onmen agen que ies he ODE abou he dynamic si ua ion o each
agen , consis ing o posi ion, speed, dis ance o he closes npedes ians, and
he dis ance o he closes nobjec s. In lea ning mode, he En i onmen
agen also assigns a ewa d o each pedes ian agen depending on di e en
ac s: i i has eached he a ge , i i has collisioned wi h o he agen s o
objec s, e c.
2. The En i onmen agen sends he s a e and ewa d in o ma ion o he Lea n-
ing agen s.
3. Each Lea ning agen uses he ecei ed in o ma ion o build he local s a e
and he immedia e ewa d alue. In he lea ning mode, he da a buil will be
used by he RL algo i hm o upda e he con ol unc ion. In he simula ion
mode, he con ol unc ion is no upda ed.
4. The agen que ies he cu en con ol unc ion o ob ain he new ac ion o
be execu ed. The ac ion indica es a change in di ec ion and/o speed o he
pedes ian.
5
5. The agen s send hei ac ions o he En i onmen agen , which in u n ans-
la e hem in o physical ac ions execu ed by he ODE in he i ual en i on-
men .
This cycle is epea ed a gi en numbe o imes which is a con igu a ion pa-
ame e o he sys em. In he lea ning mode wi h some ens o agen s, his
pa ame e can ange om hund eds o housands o se e al million imes.
3.2 Hi map
Hi map [7] is a lib a y o he pa i ion, mapping, and managemen o hie -
a chically dis ibu ed da a s uc u es a un ime. I was o iginally designed o
dense a ays, and has been also ex ended o suppo spa se da a s uc u es, such
as spa se ma ices o g aphs, using he same me hodology and in e ace [6]. I
is based on an SPMD (Single P og am Mul iple Da a) model and he message-
passing pa adigm. Hi map de ines se e al abs ac ions o w i e pa allel p og ams
using dis ibu ed da a s uc u es. The unc ions in he lib a y a e g ouped in
h ee main modules.
Tiling unc ions. They allow he de ini ion and managemen o hie a chically
iled da a s uc u es. These unc ionali ies can be used independen ly o he es
o he lib a y o imp o e locali y on sequen ial code. They de ine classes o ep-
esen domains o indexes in a compac o m. A class named Hi Tile ep esen s
he associa ion be ween he elemen s o he indexes-domain space and he ac ual
da a, allowing he accesses o da a wi h he same e iciency as manually de el-
oped codes wi hou he ile abs ac ion. A p ocess can decla e and alloca e a
subspace o he o iginal domain, in o de o c ea e a dis ibu ed da a s uc u e.
Mapping unc ions. They include in e changeable modules ha implemen
policies o au oma ically pa and map domains in e ms o he p ocesses o a
i ual opology. The i ual opologies a e also gene a ed by ano he class o
policy modules a un ime. Neighbo ela ions ac oss p ocesses a e es ablished
by hese policies. The pa i ions a e ep esen ed by objec s named Hi Layou s
ha can be que ied o ob ain he indexes subdomain mapped o he local, a
neighbo , o any o he emo e i ual p ocess.
Communica ion unc ions. They a e an abs ac ion o he message-passing
model o iles o iles pa s ac oss i ual p ocesses. They allow he c ea ion
o Hi Com objec s ha s o e he in o ma ion needed o ma shall/unma shall
and exchange selec ed ile da a ac oss p ocesses. Se e al in e aces o di e -
en ypes o poin - o-poin and collec i e communica ions a e a ailable. Mo e
complex pa e ns composed o mul iple communica ion ope a ions in ol ing one
o mo e iles (se e al Hi Com objec s), a e implemen ed as Hi Pa e n objec s.
The cons uc o unc ions ha e always Hi Layou pa ame e s ha a e que ied
in e nally o au oma ically de e mine who communica es and wha . Thus, hese
objec s a e anspa en ly adap ed on cons uc ion o he a ge pla o m de ails
and he ac ual da a dis ibu ion selec ed. The communica ion objec s ha e a
me hod ha can be called a any ime, and as many imes as needed, o execu e
he communica ions. In e nally, hese objec s exploi e icien MPI echniques
such as de i ed da a ypes, asynch onous communica ions, e c.

6
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. Global s uc u e o he simula ion and ask dis ibu ion ac oss p ocesso s in
he o iginal MARL-Ped design ( op) and a e applying Hi map (bo om).
4 Applying Hi map Techniques & Me hodology
In his sec ion we desc ibe how he Hi map me hodology and echniques can be
applied o agen -based simula ion applica ions o adap he g anula i y o asks
o he a ailable p ocessing esou ces. We show his p ocess using MARL-Ped as
a case o s udy.
4.1 S uc u al Changes
The s uc u e o he MARL-Ped applica ion has been edesigned. The Hi map
e sion applies he concep o dis ibu ed a ays o g oup lea ning agen s in p o-
cesses, ins ead o using a single MPI p ocess o each one, and a di e en p ocess
o he en i onmen agen . Fig. 2 ( op) shows he concep ual dis ibu ion o he
compu a ion in he o iginal MARL-Ped e sion. Each p ocess execu es he code
o a single agen (RLAgen class). The las p ocess pe o ms he en i onmen
simula ion (RLEn i onmen class). The objec s o hese classes ha e se e al
me hods ha implemen he co esponding ope a ions o he simula ion loop
ha is epea edly execu ed.
One o he i s design decisions o he Hi map e sion is o dis ibu e agen s
ac oss he a ailable p ocesses wi hou ese ing a special p ocess o he en i-
onmen . The en i onmen code will be execu ed by one o he p ocesses ha
will also ha e lea ning agen s assigned, as he main compu a ion o he lea n-
ing agen s and en i onmen ne e o e lap in ime. Hi map p o ides he ools
needed o he balanced dis ibu ion o agen s be ween he a ailable p ocesses
as depic ed in Fig. 2 (bo om). Each p ocess should be able o execu e, o each
i e a ion o he simula ion loop, he code o se e al lea ning agen s.
In addi ion, he p ocess in which he en i onmen agen is mapped should
execu e i s code. Thus, he simula ion loop code canno be placed inside he
en i onmen o lea ning agen classes. The applica ion mus be edesigned o
execu e he simula ion loop in he main unc ion. The simula ion loop mus
i e a e ac oss he numbe o agen s mapped o he p ocess. To achie e his, he
7
codes o he simula ion loop a e emo ed om he me hods o he lea ning and
en i onmen classes. The p i a e and p o ec ed me hods called inside he loops
a e edecla ed as public. The con ol logic ha do he calls is eloca ed inside
he new simula ion loop a he main unc ion. The en i onmen con ol logic is
w apped wi h condi ionals o ensu e ha only one p ocess execu es i . Hi map
au oma ically labels one p ocess as he g oup leade . This p ocess can iden i y
i sel by using a unc ion call, and is he e o e he one selec ed o execu e he
en i onmen logic.
4.2 Dis ibu ed A ays and Communica ion Pa e ns
The MPI-based communica ions in o iginal MARL-Ped code ha e been eplaced
by dis ibu ed-a ay managemen unc ions p o ided by Hi map. All da a s uc-
u es in ol ed in communica ions a e subs i u ed by Hi Tile s uc u es.
Du ing he ini ializa ion s age o he p og am, he dis ibu ed a ays and
objec s o ype Hi Com and Hi Pa e n a e c ea ed o con ain he speci ica ions
o he communica ions ha will be in oked om he new simula ion loop. Con-
ol signals a e ep esen ed by a single in ege - ype a iable a each p ocess,
independen ly o he numbe o assigned agen s. On he o he hand, wo dis-
ibu ed a ays a e decla ed o each da a low be ween he en i onmen and
he lea ning agen s. These a ays ha e a global index domain equal o he num-
be o lea ning agen s. Fo one o he a ays, we use a dis ibu ion policy ha
maps i s elemen s e enly ac oss he p ocesses. Fo he o he one, we use a policy
ha maps all o he domain elemen s o he p ocess unning he en i onmen .
Gi en hese wo a ays wi h he same domain bu di e en dis ibu ion poli-
cies, Hi map allows he c ea ion o a Hi Pa e n objec wi h a single unc ion
call. This objec implemen s a communica ion pa e n capable o edis ibu ing
he da a om one a ay o he co esponden local o emo e elemen s o he
o he a ay. This echnique allows he cons uc ion o communica ion objec s
ha will anspa en ly mo e he da a be ween he wo copies o each a ay; he
one ac ually dis ibu ed and he o he one ha ing he en i e index domain a
he en i onmen p ocess. The communica ion pa e n adap s (a cons uc ion
ime) o he esul s o he pa i ion policies, ega dless o he numbe o agen s
and p ocesses. This mechanism sol es, in a unique way, he cons uc ion o he
communica ion lows.
5 Expe imen al S udy
This sec ion desc ibes an expe imen al s udy o show he ad an ages o using
Hi map on agen -based simula ion p og ams. The s udy is ocused on wo a eas.
The i s one is he code complexi y and de elopmen e o . The second one is
he pe o mance when he numbe o agen s g ows abo e he numbe o a ailable
p ocessing elemen s.
8
MARL-Ped MARL-Ped+Hi map
KDSI (code lines) 1970 1888
McCabe’s C.C. 209 171
Hals ead 19.38 ×10618.26 ×106
Table 1. Measu emen s o complexi y and de elopmen e o .
5.1 De elopmen E o
The i s pa o his expe imen al s udy shows ha p og amming wi h Hi map
in oduces g anula i y lexibili y, e en wi h a sligh ly lowe de elopmen e o
and code complexi y han he o iginal agen -pe -p ocess app oach. We ha e
measu ed se e al me ics bo h in he o iginal MARL-Ped sou ce code and in
he modi ied Hi map e sion: (a) The KDSI me ic o he COCOMO me hod-
ology, based in he o al numbe o sou ce code lines; (b) McCabe’s cycloma ic
complexi y; and (c) Hals ead de elopmen e o me ic. We ha e applied hese
me ics on he main unc ion o he p og ams and he h ee classes modi ied
when edesigning he o iginal applica ion. We ha e conside ed bo h he code o
he modi ied unc ions and he heade iles, excluding commen s and emo ing
condi ional compila ion pa s ela ed o e sions, al e na i es o de ails o he
MPI lib a ies used, e c. The modi ied code ep esen s 16% o he o al applica-
ion code, ha has app oxima ely 12 200 lines o code.
The esul s in Table 1 show ha he e sion di ec ly designed and p o-
g ammed using Hi map p esen s sligh ly lowe complexi y and e o han he
o iginal MPI e sion. P og amming a di ec MPI e sion wi h he agen dis i-
bu ion and load balancing capaci y o he Hi map e sion would clea ly inc ease
he p og amming e o , since he p og amme would ha e o include code deal-
ing wi h decisions abou dis ibu ed a ay pa i ion and managemen , ha a e
anspa en ly implemen ed in Hi map.
5.2 Expe imen al Me hodology o Pe o mance S udies
The second pa o he expe imen al s udy includes pe o mance measu emen s
o bo h he o iginal MARL-Ped p og am and he Hi map-based e sion. This
wo k is ocused on he MARL-Ped lea ning p ocess, which is he mos compu a-
ionally demanding mode, and does no imply inpu /ou pu ope a ions du ing
he main compu a ion and communica ion loop. The code has been ins umen ed
in o de o measu e he execu ion ime o each dis ibu ed p ocess. We ha e
measu ed he ime elapsed om he s a o he ini ializa ion o pa allelism-
ela ed s uc u es (MPI o Hi map) o he end o he execu ion o he lea ning
p ocess, be o e w i ing he esul s in iles. Since each execu ion o he whole
p og am gi es one ime measu emen o each p ocess, we conside as he global
esul he ime o he slowes p ocess, he one ha has equi ed he longe ime
o be comple ed. In addi ion, each expe imen has been epea ed se e al imes in
9
Fig. 3. Snapsho o he simula ed scena io.
o de o es he a iabili y o he esul s. Bo h codes ha e been execu ed in mul-
ico e pla o ms, whe e communica ion cos s a e lowe and po en ial o e heads
ha e a highe impac on he o e all pe o mance. These po en ial o e heads can
be associa ed o changes in execu ion s uc u e, handling o in e nal Hi map
da a s uc u es, o compu a ions and choices abou he pa icula communica-
ions, among o he s. We ha e selec ed wo machines, one wi h 8 co es (named
Miami), and he o he wi h 12 co es (named Chime a). Bo h machines had he
hype h eading op ion enabled. Table 2 summa izes he cha ac e is ics o hese
pla o ms as well as he de elopmen ools used in he s udy.
Since he execu ion ime equi ed o a ull lea ning p ocess execu ion is ex-
emely long (RL is based on a long i e a i e p ocess), he p og am has been
limi ed o only 100 aining i e a ions in all cases, in o de o analyze a sea ch
space ha is b oad enough in e ms o execu ion pa ame e s. This h eshold
has been expe imen ally se o p oduce bo h a la ge compu a ional load, and a
signi ican numbe o communica ion and synch oniza ion s eps. The es sce-
na io selec ed o he expe imen s has been alida ed in p e ious wo ks [13].
This scena io ep oduces a classic na iga ion p oblem in pedes ian dynamics
called “sho es pa h s. quickes pa h”. In his scena io, a g oup o pedes i-
ans mus mo e om he oom whe e hey a e ini ially loca ed o a a ge place
loca ed ou side o he oom. This oom has wo exi s, one o hem being close
o he a ge han he o he one. Agen s mus lea n ha i all o hem head
o he nea es exi , hen a bo leneck is o med, making he o e all e acua ion
ime longe . A be e solu ion implies ha app oxima ely hal o he agen s use
he nea es exi , while he o he hal lea es he oom h ough he mos dis an
one, leading o a quicke e acua ion. The con igu a ion chosen places 28 agen s
in a 30-me e by 30-me e squa e oom wi h wo possible exi s. Each exi has
a wid h o one me e in o de o p e en passage o mo e han one pedes ian