This is a eposi o y copy o “P edic i e Receding-Ho izon Mul i-Robo Task
Alloca ion wi h Mo ing Tasks” in he Depósi o de In es igación de la Uni e sidad
de Se illa.
Ve sion: Au ho Accep ed Ve sion
Ci a ion: Ja ie G. Ma in, Muhammad Hani , Takeshi Ha anaka, José M. Maes e &
Edua do F. Camacho. “P edic i e Receding-Ho izon Mul i-Robo Task Alloca ion
wi h Mo ing Tasks”. 2022 Eu opean Con ol Con e ence (ECC), 12-15 Julio 2022 –
London (UK). IEEE. ISBN 978-3-9071-4407-7.
h p://doi.o g/10.23919/ECC55457.2022.9838127
To ci e his publica ion, please use he inal published e sion (i applicable).
Please check he documen e sion abo e.
Copy igh : O he han o s ic ly pe sonal use, i is no pe mi ed o download,
o wa d o dis ibu e he ex o pa o i , wi hou he consen o he au ho (s)
and/o copy igh holde (s), unless he wo k is unde an open con en license such
as C ea i e Commons.
Takedown policy: Please con ac us ([email p o ec ed]) and p o ide de ails i you belie e
his documen b eaches copy igh s. We will emo e access o he wo k immedia ely
and in es iga e you claim.
P edic i e Receding-Ho izon Mul i-Robo Task Alloca ion wi h Mo ing
Tasks*
Ja ie G. Ma in , Muhammad Hani , Takeshi Ha anaka , Senio Membe , IEEE, Jose M. Maes e ,
Senio Membe , IEEE, and Edua do F. Camacho , Fellow, IEEE
Abs ac — This pape add esses a mul i- obo ask allo-
ca ion (MRTA) owa ds mo ing asks and p esen s a no el
compu a ionally e icien p edic i e alloca ion algo i hm ha
equi es sol ing a linea p og am (LP) p oblem. Following he
eceding ho izon con ol policy, he p esen algo i hm epea s
he op imiza ion o u u e ask assignmen s wi hin an alloca ion
ho izon while p edic ing he e olu ion o he sys em. The online
op imiza ion is o mula ed so ha he assignmen p oblem is
educed exac ly o an LP. The algo i hm is also compa ed wi h
o he adi ional me hods, namely, he g eedy app oach and a
gene ic algo i hm (GA). Ou esul s show ha he algo i hm
he ein p oposed ou pe o ms he g eedy app oach o small
p edic ion ho izons and has signi ican ly lowe compu a ional
load han GA.
I. INTRODUCTION
Mul i- obo sys ems (MRS) comp ise a se o obo s
ha wo k collabo a i ely o pe o m asks. Among hei
applica ions, MRS can be used o mapping [1], [2], su eil-
lance [3]–[5], main enance [6], and also as obo ic senso ne -
wo ks (RSN), a pa icula case o wi eless senso ne wo ks
(WSN) whe e senso s a e moun ed on mobile obo s [7], [8].
A common challenge in MRS managemen is he so-
called mul i- obo ask alloca ion (MRTA) p oblem [9], [10],
whe e a se o asks a e assigned o he obo s in he
mos e icien way. This p oblem can be add essed bo h
wi h decen alized and cen alized app oaches. While he
decen alized app oach ends o be mo e scalable and obus
o communica ion ailu es, he cen alized one bene i s om
i s access o b oade in o ma ion o gene a e alloca ions
close o he op imal one.
Acco ding o he axonomy p oposed in [11], MRTA
p oblems can be classi ied o he numbe o simul aneous
asks pe obo (single- ask obo (ST) s. mul i- ask obo
(MT)), he numbe o obo s pe ask (single- obo ask (SR)
s. mul i- obo ask (MR)), and he a ailabili y o in o -
ma ion o plan u u e alloca ions (ins an aneous assignmen
(IA) s. ime-ex ended assignmen (TA)). This axonomy
*This wo k has been unded by he Eu opean Resea ch Council
(ERC) unde he Ad anced G an OCONTSOLAR (g an ag eemen
numbe 789051), G an PID2020-119476RB-I00 unded by MCIN/AEI/
10.13039/501100011033, and Jun a de Andaluc´
ıa (g an P18-HO-4713).
Finally, unding om VI PPIT-US is also g a e ully acknowledged.
J. G. Ma in, J. M. Maes e and E. F. Camacho a e wi h he De-
pa men o Sys ems and Au oma ion Enginee ing, Uni e si y o Se ille,
Spain {jga ma , e camacho,pepemaes e}@us.es and
M. Hani and T. Ha anaka a e wi h he Dep . o Sys ems and
Con ol Enginee ing, Majo in Sys ems and Con ol Enginee ing,
Tokyo Ins i u e o Technology [email p o ec ed],
[email p o ec ed]
has been u he de eloped in [12] by conside ing he in e -
dependencies be ween asks, e.g., o he cases o in-schedule
(ID) and c oss-schedule (XD) dependencies.
TA MRTA p oblems become mo e challenging when asks
mo e as in [13], whe e an algo i hm based on p eda o
dynamics is p oposed o deal wi h his issue, and [14], whe e
manipula o s wi h limi ed communica ions mus ope a e o e
dynamic asks. In his wo k, a no el linea app oach is
p esen ed o add ess he XD[ST-SR-TA] MRTA p oblem
wi h mo ing asks aking in o conside a ion he o de in
which obo s pe o m he asks. To his end, an algo i hm
ha p edic s he e olu ion o he asks and obo s as i is
done in he model p edic i e con ol (MPC) amewo k is
p oposed [15], [16]. MPC is a con ol echnique ha uses a
model o p edic he esponse o a sys em and o compu e
op imal con ol signals du ing a ce ain ime ho izon. A each
ime s ep, he i s con ol ac ion o he sequence o inpu s is
applied a e i s co esponding upda e using he mos ecen
in o ma ion a ailable. P edic i e con ol me hods in he MRS
ield ha e been p oposed in o he wo ks, e.g., [17], whe e
a decen alized model-p edic i e con ol s a egy is used o
add ess he obse a ion o mul iple mo ing a ge s; [18],
whe e a non-linea model p edic i e con ol s a egy is used
o dynamically se he o ma ion leade , and [19], whe e i is
used o compu e he ime o change he assignmen o asks o
obo s in XD[ST-SR-TA] MRTA p oblems wi h s a ic asks.
The es o his pape is o ganized as ollows. In Sec ion II,
he p oblem o mula ion is ma hema ically exp essed. In
Sec ion III, he p oposed algo i hm is in oduced. Sec ion IV
p esen s he case s udy whe e he algo i hm is es ed and he
co esponding esul s a e discussed. Finally, in Sec ion V,
he conclusions o his wo k a e de ailed and some u u e
esea ch lines a e gi en.
No a ion: 1a×bdeno es a ma ix o ones wi h a ows and
bcolumns; 0a×b ep esen s a ma ix o ze os wi h a ows
and bcolumns; Ias ands o he iden i y ma ix wi h a ows
and columns; and diag(x)is employed o deno e a diagonal
ma ix con aining ec o x as i s main diagonal.
II. PROBLEM STATEMENT
Le us conside a se o Nhe e ogeneous mobile obo s,
R={ 1, 2, ..., N}, which mus comple e a se o M
mo ing asks, S={s1, s2, ..., sM}, ollowing a gi en
sequence speci ied by o dinal indixes con ained in se K=
{1,2, ..., K}. The speed and he posi ion o obo i∈ R
a e deno ed as i∈Rand pi∈R2, espec i ely. On he
o he hand, he changing loca ion and eloci y o each ask
sj∈ S can be p edic ed and a e deno ed by qj∈R2and
uj∈R2, espec i ely. Likewise, ask sj∈ S has a ele ance
quan i ied by a posi i e scala φjand equi es an ope a ion
ime τj o be pe o med (besides he ime employed o
each he ask posi ion). Fo simplici y, τjis conside ed
independen o he obo ha pe o ms he ask. Likewise,
any ime spen pe o ming ask sjwill be sub ac ed om
τjin u he alloca ions. Finally, we de ine bi∈[0,100]
as he S a e o Cha ge (SOC) o obo i, and wias i s
discha ge a e, which will be used o a oid he assignmen
o un easible asks om an ene ge ic iewpoin . Mo eo e ,
we may wan o p io i ize some obo s o e o he s, e.g.,
unmanned g ound ehicles (UGVs) o e unmanned ae ial
ehicles (UAVs) because UAVs ha e less au onomy. To his
end, we de ine he penal y λi o he use o obo i.
A. Alloca ion Va iables
The alloca ion, i.e., he assignmen o obo s o asks, is
desc ibed by a se o Boolean a iables δijk ha a e se o 1
when he k− h mission o obo iis o pe o m ask sj(0
o he wise). Fo con enience, xis de ined as he agg ega ed
ec o x= [δijk]i∈R,j∈S,k∈K. The ollowing cons ain s
need o be imposed in he op imiza ion
N
X
i=1
K
X
k=1
δijk = 1 j∈ S,(1)
M
X
j=1
δijk ≤1i∈ R. k ∈ K,(2)
o ensu e ha all asks a e pe o med (1), and o a oid ha
obo s a e simul aneously assigned mo e han one ask pe
mission slo (2).
An example o he desc ibed a iables can be seen in
Fig. 1, whe e asks ha e been conside ed s a ic.
B. Dis ance and Time Compu a ions
The dis ance be ween obo iand ask sjis de ined as
dij =||qj−pi||2, and he ime o obo i o each ask sj
becomes ij =dij
i, as shown in Fig. 2.
Fig. 1: 1pe o ms i s s1and hen s2; 2pe o ms ask s3.
Le 1, 2and 3be he comple ion ime o s1,s2, and s3
espec i ely. Then, 1is he ime i akes o 1 o each s1
plus τ1; 2is 1plus he ime i akes 1 o go om s1 o
s2plus τ2; and 3is he ime i akes o 2 o each ask s3
plus τ3. Likewise, he dis ance a eled by 1is he dis ance
om i s ini ial posi ion o s1plus he dis ance om s1 o
s2; and he dis ance a eled by 2is ha om i s ini ial
posi ion o s3.
Le us in oduce now he mean ime o pe o m he k− h
ask as
k=1
M·N·
N
X
i=1
M
X
j=1
( ijk +τj)k∈ K,(3)
whe e ijk is he ime i akes o obo i o pe o m ask
sjas i s k− h mission.
The compu a ion o he ime o comple e a ask sj, say
j, equi es o know all he p e ious asks ca ied ou by
he obo ha pe o ms sj. To o e come his issue, we
app oxima e he accumula ed ime be o e he beginning o
he k− h mission as
k
a=
k−1
X
µ=1
µk∈ K.(4)
Thus, an es ima ion o jcan be calcula ed as
j=
N
X
i=1
K
X
k=1
δijk · E
ijk j∈ S,
E
ijk = k
a+ ijk +τji∈ R, j ∈ S, k ∈ K,
(5)
wi h E
ijk as he es ima ed ime i ask sjis alloca ed o obo
ias i s k− h mission.
Finally, we can es ima e he dis ance a eled by he obo
ias
di=
N
X
i=1
M
X
j=1
K
X
k=1
dijk ·δijk i∈ R.(6)
whe e dijk is he es ima ed dis ance a eled o obo ii
alloca ed wi h ask sjas i s k− h mission.
C. Ene ge ic Feasibili y
Using (5), i is possible o de ine a amily o unc ions
βijk =1i bi−wi· E
ijk ≥0
−1i bi−wi· E
ijk <0(7)
Fig. 2: Example wi h 2 obo s and 2 asks. Dis ances om
obo s o ask s1a e in ed, and o ask s2in blue. Task
ajec o ies can be seen in g een.
o assess whe he i will be easible om an ene ge ic
iewpoin o obo i o pe o m ask sjas i s k− h mission.
This allows us o o mula e a new cons ain o ensu e ha
asks will only be assigned o obo s wi h enough SOC:
βijk ·δijk ≥0i∈ R j∈ S, k ∈ K,(8)
D. Op imiza ion Goals
The co e o he mul i-c i e ia objec i e unc ion employed
by ou algo i hm akes in o accoun bo h he ime in which
asks a e pe o med and he dis ance a eled by he obo s
and i is de ined as
Jc=
M
X
j=1
φj· j(x) +
N
X
i=1
λi·di(x),(9)
whe e λi∈Ris he penal y o he use o obo i;diis he
dis ance a eled by he obo i, which can be es ima ed by
means o (6); φj∈Ris he penal y o he ime employed
o comple e ask sj; and jis he comple ion ime in which
ask sjis inished, which can be es ima ed by means o (5).
Then, he cos unc ion (9) can be ans o med in o
Js=
N
X
i=1
M
X
j=1
K
X
k=1
k·δijk ·(λi·dijk +φj· E
ijk),(10)
whe e he mul iplica ion by ken o ces ha a obo can only
be assigned a ask as i s k− h mission i i al eady has
ano he ask alloca ed in i s (k−1)− h mission slo .
Conside ing he easibili y o he ul illmen o all asks,
we can ind wo possible cases:
1) All he asks can be pe o med. When N·K≥M, he e
a e enough obo s o comple e he asks in he alloca ion
ho izon and he MRTA p oblem can be o mula ed as:
min
δijk ∈{0,1}Js
s. . (1), (2), (8).
(11)
No e ha i K = M all alloca ions can be explo ed
(including hose using he same obo o pe o m all he
asks). Thus, i K<Mop imali y can be los , al hough
he compu a ional cos o he p oblem dec eases ( he
numbe o decision a iables in he p oblem is N·M·K).
2) Some asks canno be comple ed when N·K<M,
he p oblem mus be changed conside ing he ollowing
cons ain s
N
X
i=1
K
X
k=1
δijk ≤1j∈ S,(12)











M
X
j=1
δijk = 1 i maxi,k(βijk)=1
M
X
j=1
δijk = 0 i maxi,k(βijk) = −1
i∈ R
k∈ K ,(13)
o ensu e ha no all asks need o be ul illed in
he alloca ion ho izon (main aining ha hey can be
pe o med only once) and ha obo s a e no idle (unless
hey do no ha e enough ba e y o pe o m any o
he emaining missions). The p oblem can be hen
o mula ed as
min
δijk ∈{0,1}Js
s. . (12), (13), (8),
(14)
III. RECEDING HORIZON TASK ALLOCATION
ALGORITHM
In his sec ion, he LP elaxa ion o he p oblem p esen ed
in Sec ion II is de ailed and he p oposed p edic i e mul i-
obo ask alloca ion algo i hm is p esen ed.
A. LP elaxa ion
Bo h (11) and (14) can be ans o med in o an equi alen
LP p oblem o educe he compu a ional cos . The equi alen
LP p oblem is as ollows:
min
x≥0c·x
s. . A·x=b(15)
whe e c= [ci]i∈R and xT= [xT
i]i∈R, wi h
cT
i=


























1·(λi·di11 +φ1· E
i11)
2·(λi·di12 +φ1· E
i12)
.
.
.
K·(λi·di1K +φ1· E
i1K)
1·(λi·di21 +φ2· E
i21)
2·(λi·di22 +φ2· E
i22)
.
.
.
K·(λi·di2K +φ2· E
i2K)
.
.
.
1·(λi·diM1 +φM· E
iM1)
2·(λi·diM2 +φM· E
iM2)
.
.
.
K·(λi·diMK +φM· E
iMK)


























,xi=


























δi11
δi12
.
.
.
δi1K
δi21
δi22
.
.
.
δi2K
.
.
.
δiM1
δiM2
.
.
.
δiMK


























.
and he ma ixes Aand bcon ain he co esponding con-
s ain s. Fo simplici y, we conside only he p oblem ex-
p essed in (11) because p oblem (14) can be elaxed in he
same manne . Then, hese ma ixes Aand bcan be w i en
as
A=R0
V I , b =1M+N·K×1
0N·M·K×1,(16)
wi h
R=R1R2· · · RN,
Ri=




11×K01×K· · · 01×K
01×K11×K· · · 01×K
.
.
..
.
.....
.
.
01×K01×K· · · 11×K





,
V=V1V2· · · VN
diag([β111 · · · βNMK]) ,
Vi=








0K×K0K×K· · · 0K×K
.
.
..
.
..
.
.
IKIK· · · IK
.
.
..
.
..
.
.
0K×K0K×K· · · 0K×K








.
1
.
.
.
i
.
.
.
N
No e ha he i− h block ow in Viis he one con aining he
IKma ices.
P oblem (15) is known o be equi alen o (11) in he
sense o ha ing he same op imize i he ma ix Ais o ally
unimodula and e e y elemen o bis an in ege [20]. The
la e condi ion is ob iously sa is ied in he p esen case.
Rega ding he o me , he ollowing lemma is shown o
be ue, which is equi alen o o al unimodula i y o A
(Theo em 19.3[20]).
Lemma 1 Ma ix Asa is ies ha ∃ξ∈ {0,±1}s. . A·ξ∈
{0,±1}.
P oo : Le us de ine
ξ=ξ1−ξ2ξ3· · · ±ξN−11×(M+1)·N·K,
ξi=11×K−11×K11×K· · · ±11×K,(17)
whe e ξNis posi i e i Nis odd and nega i e o he wise.
Tha is, he i s Kelemen s o ξa e equal o 1, he
ollowing Kones a e equal o −1, and his pa e n is epea ed
un il he K·M− h elemen . No e ha he las e m will be
posi i e i Kis odd and nega i e o he wise.
Then, i is easy o see ha R0·ξ∈ {0,1}, and
ha V I ·ξ∈ {0,±1}. Thus, A·ξ∈ {0,±1}, which
comple es he p oo .
The e o e, we can sol e he LP (15) a he han he in ege
p og am (11).
B. P edic i e Receding-Ho izon Mul i-Robo Task Alloca ion
(PMRTA) Algo i hm
To sol e he p oblem, we need dijk, ijk, k
a, and E
ijk
which can be ob ained ollowing Algo i hm 1.
A e compu ing dijk and ijk ∀k, he LP p oblem ex-
p essed in (15) is sol ed and he assignmen co esponding
o k= 1 is applied. Once a ask is comple ed, he algo i hm
is es a ed in an e en -d i en ashion a e upda ing he
posi ions o obo s and asks, and he ba e y s a us. In
his way, p edic ions and alloca ions a e cons an ly upda ed
based on he cu en in o ma ion. See Algo i hm 2, whe e
he p oposed p edic i e eceding-ho izon mul i- obo ask
alloca ion (PMRTA) algo i hm is desc ibed.
IV. RESULTS
A case s udy wi h 4 obo s and 16 asks mo ing no heas
a di e en speeds is employed using a sample ime o 0.1
seconds. The pa ame e s o he obo s and he asks ha e
been gene a ed andomly and can be seen in Table I.
An assessmen o he e ec s o he alloca ion ho izon Kin
he esul s and he inc ease o he compu a ional load wi h K
can be seen in Table II. Fo compa ison pu poses, Jhas been
compu ed ollowing (9) o each simula ion using he eal
dis ance a eled by each obo and he eal ime in which
he asks we e inished. No e ha he wo s alue is ob ained
wi h K = 1, which is equi alen o he g eedy app oach.
The bes alloca ion occu s when K=3and s abilizes
a e K = 4, ob aining he same alloca ion dis ega ding
he alue o Kand he compu a ional bu den inc eases
linea ly up o 2.02 seconds. We ha e compa ed i also wi h
Algo i hm 1: dijk, ijk, k
aand E
ijk es ima ion.
Le k= 1;
Ini ialize he es ima ed posi ion o obo s using hei
cu en posi ion, p0
ik =pi;
Ini ialize he es ima ed posi ion o asks using hei
cu en posi ion, q0
jk =qj;
while k≤Kdo
Compu e `ijk using p0
ik,q0
jk, i, and uj;
Compu e dijk =||`ijk −p0
ik||2∀i∈ R, j ∈ S;
Compu e ijk as ijk =dijk
ii∈ R, j ∈ R;
Use ijk and τj o compu e kusing (3);
Compu e kby means o (3);
Compu e k+1
aby means o (4);
Es ima e he posi ion o asks in k+ 1,q0
jk+1,
using q0
jk,ujand he ime ob ained in k
a;
Compu e E
ijk ∀i∈ R, j ∈ S by means o (5);
Remo e om S he ask wi h he lowes
es ima ed mean ime in k, since we will
conside his is he ask ha has been comple ed;
Compu e he posi ion o he obo s in k+ 1,
p0
ik+1, by means o
p0
ik+1 =p0
ik +
|S|+1
X
j=1
k
a· i·q0
j−pi
||q0
j−pi||2
·1
|S| + 1;
end
Algo i hm 2: P edic i e Receding-Ho izon Mul i-
Robo Task Alloca ion (PMRTA)
while |S| >0do
Upda e he eal posi ion o he obo s;
Upda e he eal posi ion o he asks;
Upda e he eal s a e o he ba e ies;
Upda e he p edic ed posi ion o he asks and he
obo s, dijk, ijk, k, k
aand E
ijk using
Algo i hm 1;
Sol e he alloca ion using (15);
Apply he pa o he alloca ion co esponding o
k= 1;
Comple e he co esponding ask and upda e he
numbe o emaining asks, |S| =|S| − 1;
end
he alloca ion ob ained by sol ing (15) once ob aining ha
he compu a ional bu den is simila o ha o K = 1 bu
he pe o mance dec eases signi ican ly, i.e., he pe iodic
ecompu ing o he alloca ion is necessa y. This phenomenon
is o be expec ed since he p edic ions employed by he LP
a e based on se e al simpli ying assump ions. Finally, he
alloca ions ob ained using K=3a e shown in Fig. 3. The e
a e 16 alloca ions because he e a e 16 asks and a new
alloca ion is compu ed e e y ime a ask is comple ed.
The esul s a e also compa ed wi h hose achie ed by he
Gene ic Algo i hm (GA) me hod p esen ed in [21], which

0 10 20
0
5
10
15
y coo dina e(m)
Alloca ion1
1
2
3
4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
0 10 20
0
5
10
15 Alloca ion2
1
23
4
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
0 10 20
0
5
10
15 Alloca ion3
1
23
4
2
3
5
6
7
8
9
10
11
12
13
14
15
16
0 10 20
0
5
10
15 Alloca ion4
1
23
4
2
3
6
7
8
9
10
11
12
13
14
15
16
0 10 20
0
5
10
15 Alloca ion5
1
23
4
2
3
6
7
8
9
10
12
13
14
15
16
0 10 20
0
5
10
15 Alloca ion6
1
2
3
4
2
6
7
8
9
10
12
13
14
15
16
0 10 20
0
5
10
15 Alloca ion7
1
2
3
4
2
67
8
9
10
12
14
15
16
0 10 20
0
5
10
15 Alloca ion8
12
3
4
2
7
8
9
10
12
14
15
16
0 10 20
x coo dina e(m)
0
5
10
15
y coo dina e(m)
Alloca ion9
1
2
3
4
27
8
910
12
14
16
0 10 20
x coo dina e(m)
0
5
10
15 Alloca ion10
1
2
3
4
27
8
9
12
14
16
0 10 20
x coo dina e(m)
0
5
10
15 Alloca ion11
12
3
4
27
8
91416
0 10 20
x coo dina e(m)
0
5
10
15 Alloca ion12
1 2
3
4
27
8
14 16
0 10 20
x coo dina e(m)
0
5
10
15 Alloca ion13
1
2
3
4
27
816
0 10 20
x coo dina e(m)
0
5
10
15 Alloca ion14
1
2
3
4
7
8 16
0 10 20
x coo dina e(m)
0
5
10
15 Alloca ion15
12
3
48
16
0 10 20
x coo dina e(m)
0
5
10
15 Alloca ion16
12
3
48
Fig. 3: The lines ep esen he alloca ion ob ained in each i e a ion. The g een line ep esen s he pa o he alloca ion
co esponding o k= 1, i.e., he pa o he alloca ion which is applied, while he blue lines ep esen he pa o he
alloca ion o k > 1. In he i s alloca ion, obo 2is sen o ask 1, obo 4is sen o ask 4, obo 3is sen o ask 11,
and obo 1is sen o ask 5. The second alloca ion occu s when obo 2comple es ask 1. In his alloca ion, obo s 1,3,
and 4keep on comple ing he cu en asks while obo 2is sen o ask 3. No e ha in he p e ious alloca ion, he second
assignmen o obo 2was no ask 3bu ask 15. The hi d alloca ion is simila o he second one, bu obo 4 inishes and
is sen o a new ask ( ask 13). In he ou h alloca ion, we can see how ask 13 is ealloca ed o obo 4(since i has no
eached he ask ye ), and, in he i h alloca ion, we can see ha he p oposed algo i hm edi ec s obo 4 o ask 10 and
ask 13 is eassigned o obo 3. The e a e 16 alloca ions since each ime a ask is comple ed a new one is compu ed.
TABLE I: Pa ame e s o he obo s in he case s udy
Robo s pi(0) || i|| λibi(0) wi
1(2,5) 4 1 100 0.2
2(1,3) 8 2 80 0.5
3(4,2) 8 1 40 0.4
4(3,3) 16 2 30 0.1
Tasks qj(0) ˙qjτjφj
s1(1,1) (1,1) 1 3
s2(1,6) (3,2) 2 1
s3(2,1) (2,1) 3 5
4(2,3) (2,2) 2 4
5(3,5) (2,1) 2 2
6(3,9) (3,1) 1 3
7(7,7) (4,2) 4 1
8(4,5) (2,2) 5 1
9(5,8) (1,1) 7 6
10 (6,3) (3,3) 1 1
11 (7,1) (2,1) 2 4
12 (7,4) (2,4) 1 3
13 (8,2) (1,2) 4 5
14 (8,3) (2,3) 9 6
15 (9,3) (2,3) 3 2
16 (9,8) (3,1) 5 1
sol es
min
UJGA =
M
P
j=1
φj· j(U) +
N
P
i=1
λi·di(U) + γ(U)
s. . ui(n)∈ S ∪ {0} ∀ i, n, (18)
whe e U= [u1(1), u1(2), .., u1(M), u2(1), ..., uN(M)] ep-
esen s he comple e alloca ion and ui(n)∈ S ∪ {0},
s ands o he n− h alloca ed ask o obo i. No e ha
ui(n)=0when obo iis idle. He e, φjand λi espec i ely
co espond o he p io i y gi en o a ce ain ask sjand he
penal y o using obo i; j(U)and di(U)co espond o
nonlinea unc ions ega ding he ime ha i akes o com-
ple e ask sjand he dis ance a eled by obo iin a gi en
alloca ion U. Func ion γ(U)is a so es ic ion ensu ing he
ene ge ic easibili y (no obo has a nega i e ba e y le el
TABLE II: Resul s o he case-s udy o di e en K
K 1 2 3 4 ··· 16 16 (no ecom.)
J609.14 519.38 484.02 504.35 ··· 504.35 945.79
idi(m)
112.95 26.40 11.20 14.97 ··· 14.97 17.49
231.27 28.24 26.08 32.72 ··· 32.72 25.32
322.12 12.65 28.48 22.54 ··· 22.54 24.60
432.01 28.52 24.74 23.55 ··· 23.55 30.23
sj j(s)
s11.2 1.2 1.2 4.4··· 4.4 15.5
s22.2 2.2 12 13.3··· 13.3 31.5
s312.4 4.3 4.3 3.2··· 3.2 3.6
s44 2 2 2.3··· 2.3 4.3
s52 2.3 2.1 6.4··· 6.4 26.3
s65.4 3.8 8.1 8 ··· 8 33.4
s76.7 16.3 14.1 12.3··· 12.3 38.9
s87.4 7.7 16.7 16.7··· 16.7 45.5
s914.7 10.9 9.9 11 ··· 11 20.4
s10 1.3 10.2 9.4 10.7··· 10.7 39.8
s11 9.1 6.9 2.3 2.4··· 2.4 4.1
s12 2.5 3.4 9.5 9.3··· 9.3 21.2
s13 12.3 8.7 6.4 4.5··· 4.5 5.1
s14 18.1 16.1 11.4 11.4··· 11.4 21.4
s15 9 11.2 8.3 7.8··· 7.8 9.1
s16 7.9 15.6 14.8 16.1··· 16.1 27.9
Compu a ional ime (s)
0.74 0.79 0.86 0.93 ··· 2.02 0.76
a e he alloca ion) and ha e e y ask is pe o med once.
Finally, GA pa ame e s, which ha e been uned by ial and
e o o achie e a good balance be ween pe o mance and
compu a ional load, can be seen in Table III. No e ha gi en
he heu is ic na u e o GA, he p oblem has been sol ed 10
imes o a e age he esul s.
TABLE III: GA uning pa ame e s
Pop. size Max Gen. Max S all Gen. GCGEGM1 GM2
400 50 10 0.7 0.3 0.5 0.5
The compu a ional load o GA is a ound 60 seconds and
JGA is in he ange [600,650], i.e., GA ba ely eaches he
pe o mance achie ed by he g eedy app oach despi e i s
signi ican ly highe compu a ional load. Howe e , i mus be
aken in o accoun ha , unlike he g eedy app oach and he
p edic i e app oach, he implemen a ion o GA he e lacks
he capabili y o lea ing asks incomple e.
To alida e he p oposed me hod, we ha e gene a ed 1000
andom scena ios wi h N∈[1,10], and M∈[1,20], loca ed
in andom spo s o a 15×15 m squa e a ea. These scena ios
ha e been sol ed using GA and PMRTA ∀K∈[1,M]. The
es o he pa ame e s a e con ained in he ollowing anges:
i∈[4,20] m/s; λ∈(0,5);bi∈[0,100];wi∈(0,1);
ujcons an wi h ||uj|| ∈ (0,4] m/s and andom di ec ion;
τj∈(0,10); and φj∈(0,10) m/s.
Ou esul s show ha when GA is cons ained o achie e
an alloca ion in he same ime as he p oposed algo i hm i
achie es a wo se alloca ion in mos cases (90.15%). In Fig. 4,
i can be seen ha PMRTA is supe io in almos all cases wi h
small K(K>1), al hough i s pe o mance dec eases o
la ge p edic ion ho izons un il i inally becomes wo se han
he g eedy algo i hm (K=1). On he o he hand, when GA
has unlimi ed ime o con e ge ( he s opping c i e ion was
se o 30 gene a ions wi h no imp o emen ), i ou pe o ms
he p oposed algo i hm in mos cases, as expec ed. Howe e ,
e en in hese un ai condi ions, he p oposed algo i hm
occasionally bea s GA. Also, no e ha o K = 2 PMRTA
ou pe o ms he g eedy algo i hm and is able o ge be e
esul s han GA in 18.9% o he cases ( he g eedy algo i hm
ou pe o ms he unlimi ed GA only 7% o he simula ions).
1 2 3 4 5 6 7 8 9 1011121314151617181920
K
0
20
40
60
80
100
% o cases won
( o he same compu a ion ime)
PMRTA
Time limi ed GA
Fig. 4: Pe o mance compa ison be ween PMRTA and ime
limi ed GA.
V. CONCLUSIONS
A p edic i e MRTA algo i hm ha akes ad an age o
he a ailable in o ma ion ega ding he sys em e olu ion
has been p esen ed. In pa icula , he p oposed algo i hm
compu es he bes alloca ion based on he p edic ed sys em
e olu ion o a gi en ho izon and applies he i s elemen o
he calcula ed sequence in a eceding ho izon manne .
Ou esul s show ha he p oposed algo i hm ou pe o ms
well-es ablished heu is ical me hods such as he g eedy al-
go i hm and GA in ime-limi ed op imiza ions. Also, he
p oposed algo i hm pe o ms ema kably be e wi h small
ho izons han wi h la ge ones due o he use o a simple
in e nal model o he p edic ions. To o e come his issue,
we plan o i e a e he alloca ion un il con e gence is ob ained
and o employ myopic cos unc ions in u u e wo ks. Also,
in u u e wo ks, expe imen s wi h eal obo s in mo e chal-
lenging en i onmen s will be ca ied ou .
REFERENCES
[1] F. Nex and F. Remondino, “UAV o 3D Mapping Applica ions: A
Re iew,” Applied geoma ics, ol. 6, no. 1, pp. 1–15, 2014.
[2] P. Maini and P. Suji , “on Coope a ion Be ween a Fuel Cons ained
UAV and a Re ueling UGV o La ge Scale Mapping Applica ions,”
in 2015 In e na ional Con e ence on Unmanned Ai c a Sys ems
(ICUAS). IEEE, 2015, pp. 1370–1377.
[3] E. Semsch, M. Jakob, D. Pa licek, and M. Pechoucek, “Au-
onomous UAV Su eillance in Complex U ban En i onmen s,” in
2009 IEEE/WIC/ACM In e na ional Join Con e ence on Web In el-
ligence and In elligen Agen Technology, ol. 2. IEEE, 2009, pp.
82–85.
[4] A. Pu i, “A Su ey o Unmanned Ae ial Vehicles (UAV) o T a -
ic Su eillance,” Depa men o compu e science and enginee ing,
Uni e si y o Sou h Flo ida, pp. 1–29, 2005.
[5] H. Dan, J. Yamauchi, T. Ha anaka, and M. Fuji a, “Con ol ba ie
unc ion-based pe sis en co e age wi h pe o mance gua an ee and
applica ion o objec sea ch scena io,” in 2020 IEEE Con e ence on
Con ol Technology and Applica ions (CCTA). IEEE, 2020, pp. 640–
647.
[6] J. F anko, S. Du, S. Kallwei , E. Duelbe g, and H. Engemann, “Design
o a mul i- obo sys em o wind u bine main enance,” Ene gies,
ol. 13, no. 10, p. 2552, 2020.
[7] I. F. Akyildiz, W. Su, Y. Sanka asub amaniam, and E. Cayi ci, “Wi e-
less Senso Ne wo ks: A Su ey,” Compu e ne wo ks, ol. 38, no. 4,
pp. 393–422, 2002.
[8] A. Koubˆ
aa and A. Khelil, Coope a i e Robo s and Senso Ne wo ks.
Sp inge , 2014.
[9] A. Khamis, A. Hussein, and A. Elmogy, “Mul i- obo Task Alloca ion:
A Re iew o he S a e-o - he-a ,” in Coope a i e Robo s and Senso
Ne wo ks. Sp inge , 2015, pp. 31–51.
[10] W. Dai, H. Lu, J. Xiao, Z. Zeng, and Z. Zheng, “Mul i- obo dynamic
ask alloca ion o explo a ion and des uc ion,” Jou nal o In elligen
& Robo ic Sys ems, ol. 98, no. 2, pp. 455–479, 2020.
[11] B. P. Ge key and M. J. Ma a i´
c, “A Fo mal Analysis and Taxonomy o
Task Alloca ion in Mul i-Robo Sys ems,” The In e na ional jou nal
o obo ics esea ch, ol. 23, no. 9, pp. 939–954, 2004.
[12] G. A. Ko sah, A. S en z, and M. B. Dias, “A Comp ehensi e Taxon-
omy o Mul i-Robo Task Alloca ion,” The In e na ional Jou nal o
Robo ics Resea ch, ol. 32, no. 12, pp. 1495–1512, 2013.
[13] L. Jin, S. Li, H. M. La, X. Zhang, and B. Hu, “Dynamic ask alloca ion
in mul i- obo coo dina ion o mo ing a ge acking: A dis ibu ed
app oach,” Au oma ica, ol. 100, pp. 75–81, 2019.
[14] L. Jin and S. Li, “Dis ibu ed ask alloca ion o mul iple obo s:
A con ol pe spec i e,” IEEE T ansac ions on Sys ems, Man, and
Cybe ne ics: Sys ems, ol. 48, no. 5, pp. 693–701, 2016.
[15] C. E. Ga cia, D. M. P e , and M. Mo a i, “Model p edic i e con ol:
Theo y and p ac ice—a su ey,” Au oma ica, ol. 25, no. 3, pp. 335–
348, 1989.
[16] E. F. Camacho and C. B. Alba, Model P edic i e Con ol. Sp inge
science & business media, 2013.
[17] J. Kuhn, C. Reinl, and O. Von S yk, “P edic i e con ol o mul i- obo
obse a ion o mul iple mo ing a ge s based on disc e e-con inuous
linea models,” IFAC P oceedings Volumes, ol. 44, no. 1, pp. 257–
262, 2011.
[18] B. Augus o de Holanda, S. P. Mad uga, A. V. B i o, and T. P. Nasci-
men o, “Dynamic leade alloca ion in mul i- obo sys ems based on
nonlinea model p edic i e con ol,” Jou nal o In elligen & Robo ic
Sys ems, ol. 98, no. 2, pp. 359–376, 2020.
[19] M. Gagge o, D. Di Paola, A. Pe i i, and L. Ca iglione, “When
ime ma e s: P edic i e mission planning in cybe -physical scena ios,”
IEEE Access, ol. 7, pp. 11 246–11 257, 2019.
[20] A. Sch ij e , Theo y o linea and in ege p og amming. John Wiley
& Sons, 1998.
[21] J. G. Ma in, J. R. D. F ejo, R. Ga c´
ıa, and E. F. Camacho, “Mul i-
Robo Task Alloca ion P oblem wi h Mul iple Non-Linea C i e ia
Using B anch and Bound and Gene ic Algo i hms,” In elligen Se ice
Robo ics, 2021.