I
AE
S In
t
er
na
t
io
na
l J
o
urna
l o
f
Art
if
icia
l In
t
ellig
ence
(
I
J
-
AI
)
Vo
l.
14
,
No
.
1
,
Feb
r
u
ar
y
2
0
2
5
,
p
p
.
712
~
723
I
SS
N:
2
2
5
2
-
8
9
3
8
,
DOI
: 1
0
.
1
1
5
9
1
/ijai.v
14
.i
1
.
p
p
7
1
2
-
7
2
3
712
J
o
ur
na
l ho
m
ep
a
g
e
:
h
ttp
:
//ij
a
i
.
ia
esco
r
e.
co
m
Para
llel rapidly
e
x
plo
ring
rando
m
tree
m
ethod
for u
nma
nned
a
eria
l vehicles
aut
o
pilo
t
dev
elo
pme
nt
using
gra
phics
pro
cess
ing
unit
p
ro
cess
ing
L
esia
Mo
c
h
ura
d
1
,
M
o
nik
a
Da
v
idek
o
v
a
2
,
Ste
rg
io
s
-
Aristo
t
eles
M
it
o
uli
s
3
1
D
e
p
a
r
t
me
n
t
of
A
r
t
i
f
i
c
i
a
l
I
n
t
e
l
l
i
g
e
n
c
e
,
Lv
i
v
P
o
l
y
t
e
c
h
n
i
c
N
a
t
i
o
n
a
l
U
n
i
v
e
r
si
t
y
,
L
v
i
v
,
U
k
r
a
i
n
e
2
F
a
c
u
l
t
y
of
M
a
n
a
g
e
me
n
t
,
C
o
m
e
n
i
u
s
U
n
i
v
e
r
si
t
y
B
r
a
t
i
sl
a
v
a
,
B
r
a
t
i
sl
a
v
a
,
S
l
o
v
a
k
R
e
p
u
b
l
i
c
3
D
e
p
a
r
t
me
n
t
of
C
i
v
i
l
En
g
i
n
e
e
r
i
n
g
,
S
c
h
o
o
l
of
E
n
g
i
n
e
e
r
i
n
g
,
U
n
i
v
e
r
s
i
t
y
of
B
i
r
mi
n
g
h
a
m,
B
i
r
mi
n
g
h
a
m,
U
n
i
t
e
d
K
i
n
g
d
o
m
Art
icle
I
nfo
AB
S
T
RAC
T
A
r
ticle
his
to
r
y:
R
ec
eiv
ed
Mar
20
,
2
0
2
4
R
ev
is
ed
Au
g
1
,
2
0
2
4
Acc
ep
ted
Au
g
30
,
2
0
2
4
Au
to
n
o
m
o
u
s
a
ir
m
o
v
e
m
e
n
t
sy
st
e
m
s
h
o
ld
g
re
a
t
p
o
ten
ti
a
l
fo
r
tra
n
sfo
rm
in
g
v
a
rio
u
s
i
n
d
u
stries
,
m
a
k
i
n
g
t
h
e
ir
d
e
v
e
l
o
p
m
e
n
t
e
ss
e
n
ti
a
l.
Au
t
o
p
i
l
o
t
d
e
sig
n
in
v
o
lv
e
s
a
d
v
a
n
c
e
d
tec
h
n
o
l
o
g
ies
li
k
e
a
rti
ficia
l
in
telli
g
e
n
c
e
,
m
a
c
h
in
e
lea
rn
in
g
,
a
n
d
b
i
g
d
a
ta.
Th
is
p
a
p
e
r
fo
c
u
se
s
o
n
d
e
v
e
l
o
p
i
n
g
a
p
a
ra
ll
e
l
ra
p
id
l
y
-
e
x
p
lo
r
in
g
ra
n
d
o
m
tree
(RRT)
a
lg
o
r
it
h
m
u
sin
g
c
o
m
p
u
te
u
n
ifi
e
d
d
e
v
ice
a
rc
h
it
e
c
tu
re
(
CUD
A
)
tec
h
n
o
l
o
g
y
fo
r
e
fficie
n
t
p
r
o
c
e
ss
in
g
o
n
g
ra
p
h
ics
p
r
o
c
e
ss
in
g
u
n
it
s
(G
P
Us
).
Th
e
stu
d
y
e
v
a
lu
a
tes
t
h
e
a
lg
o
ri
th
m
'
s
p
e
rfo
rm
a
n
c
e
in
a
u
to
m
a
ted
tra
jec
to
ry
p
la
n
n
i
n
g
f
o
r
u
n
m
a
n
n
e
d
a
e
rial
v
e
h
icle
s
(UA
Vs
).
Nu
m
e
rica
l
e
x
p
e
rime
n
ts
sh
o
w
t
h
a
t
t
h
e
p
a
ra
ll
e
l
a
lg
o
rit
h
m
o
u
tp
e
rfo
rm
s
t
h
e
se
q
u
e
n
ti
a
l
c
e
n
tral
p
ro
c
e
ss
in
g
u
n
it
(
CP
U
)
-
b
a
se
d
v
e
rsio
n
,
e
sp
e
c
ially
a
s
tas
k
c
o
m
p
lex
it
y
a
n
d
sta
te
sp
a
c
e
d
ime
n
sio
n
s
i
n
c
re
a
se
.
In
sc
e
n
a
rio
s
with
n
u
m
e
ro
u
s
o
b
sta
c
les
,
th
e
p
a
ra
ll
e
l
a
lg
o
rit
h
m
m
a
in
tain
s
st
a
b
le
p
e
rfo
rm
a
n
c
e
,
m
a
k
in
g
i
t
we
ll
-
su
it
e
d
f
o
r
v
a
rio
u
s
a
p
p
li
c
a
ti
o
n
s.
C
o
m
p
a
riso
n
s
wit
h
CP
U
-
b
a
se
d
m
e
th
o
d
s
h
i
g
h
li
g
h
t
th
e
a
d
v
a
n
tag
e
s
o
f
G
P
U
u
se
,
p
a
rti
c
u
larly
i
n
term
s
o
f
sp
e
e
d
a
n
d
e
fficie
n
c
y
.
Ad
d
it
i
o
n
a
ll
y
,
th
e
p
e
rf
o
rm
a
n
c
e
o
f
two
G
P
U
m
o
d
e
ls,
NV
IDIA
R
TX
2
0
7
0
a
n
d
T4
is
c
o
m
p
a
re
d
,
wit
h
th
e
T
4
d
e
m
o
n
stra
ti
n
g
su
p
e
rio
r
p
e
rfo
rm
a
n
c
e
fo
r
sim
il
a
r
tas
k
s.
F
u
t
u
re
re
se
a
rc
h
sh
o
u
l
d
e
x
p
lo
re
i
n
teg
ra
ti
n
g
m
u
l
ti
p
le
a
lg
o
rit
h
m
s
fo
r
a
m
o
re
c
o
m
p
re
h
e
n
siv
e
UA
V
a
u
t
o
p
il
o
t
s
y
s
tem
.
Th
e
p
ro
p
o
se
d
a
p
p
ro
a
c
h
sta
n
d
s
o
u
t
f
o
r
it
s
sta
b
il
it
y
a
n
d
p
ra
c
ti
c
a
l
a
p
p
li
c
a
b
il
it
y
in
re
a
l
-
wo
rl
d
a
u
to
p
i
lo
t
imp
lem
e
n
tatio
n
s.
K
ey
w
o
r
d
s
:
Acc
eler
atio
n
C
o
m
p
u
te
u
n
if
ie
d
d
ev
ice
ar
ch
itectu
r
e
t
ec
h
n
o
lo
g
y
Sin
g
le
in
s
tr
u
ctio
n
m
u
ltip
le
d
ata
S
y
s
tem
of
a
u
to
p
ilo
t
U
n
m
an
n
ed
a
er
ial
v
eh
icle
T
h
is
is
an
o
p
e
n
a
c
c
e
ss
a
rticle
u
n
d
e
r
th
e
CC
BY
-
SA
li
c
e
n
se
.
C
o
r
r
e
s
p
o
nd
ing
A
uth
o
r
:
L
esia
Mo
ch
u
r
ad
Dep
ar
tm
en
t
of
Ar
tific
ial
I
n
tellig
en
ce
,
L
v
iv
Po
ly
tech
n
ic
Nati
o
n
al
Un
iv
er
s
ity
Kn
iazia
R
o
m
an
a
s
tr
.
,
5,
L
v
iv
7
9
9
0
5
,
Uk
r
ai
n
e
E
m
ail:
lesi
a.
i.
m
o
ch
u
r
ad
@
lp
n
u
.
u
a
1.
I
NT
RO
D
UCT
I
O
N
In
th
e
2
1
s
t
ce
n
tu
r
y
,
all
p
o
s
s
ib
le
tech
n
o
lo
g
ies
ar
e
d
ev
elo
p
in
g
to
war
d
s
au
to
n
o
m
y
an
d
au
to
m
atio
n
,
as
n
o
ted
in
[
1
]
,
[
2
]
.
Af
ter
th
e
s
u
cc
ess
of
d
ev
elo
p
in
g
a
co
m
p
lete
au
to
p
ilo
tin
g
s
y
s
tem
f
o
r
g
r
o
u
n
d
v
eh
icles
(
f
o
r
ex
am
p
le,
T
esla'
s
au
to
p
ilo
t:
s
ee
[
3
]
),
th
e
d
em
a
n
d
f
o
r
tech
n
o
lo
g
ies
f
o
r
au
to
m
atic
r
o
u
te
p
lan
n
in
g
f
o
r
all
ty
p
es
of
v
eh
icles
m
o
v
i
n
g
in
s
p
ac
e
h
as
r
ap
id
ly
in
cr
ea
s
ed
.
Veh
icles
th
at
can
move
in
d
ep
en
d
en
tly
,
f
u
lf
illi
n
g
th
eir
task
s
,
h
av
e
b
ec
o
m
e
one
of
th
e
m
ain
d
ir
ec
tio
n
s
of
d
ev
el
o
p
m
e
n
t
of
m
o
d
er
n
s
cien
ce
an
d
tech
n
o
lo
g
y
[
4
]
–
[
6
]
.
In
r
ec
en
t
y
ea
r
s
,
u
n
m
an
n
ed
ae
r
ial
v
eh
icl
es
(
UAVs)
h
av
e
r
ec
eiv
ed
s
p
ec
ial
atten
tio
n
,
as
th
e
air
s
p
ac
e
d
o
es
not
s
u
f
f
er
f
r
o
m
tr
af
f
ic
p
r
o
b
lem
s
an
d
co
n
tain
s
m
u
ch
f
ewe
r
o
b
s
tacle
s
to
m
o
v
e
m
en
t,
wh
ich
allo
ws
th
em
to
m
o
v
e
m
u
c
h
f
aster
an
d
s
af
er
,
p
er
f
o
r
m
in
g
a
wid
e
r
a
n
g
e
of
task
s
.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
n
t J Ar
tif
I
n
tell
I
SS
N:
2252
-
8
9
3
8
P
a
r
a
llel ra
p
id
ly
ex
p
lo
r
in
g
r
a
n
d
o
m
tr
ee
meth
o
d
fo
r
u
n
ma
n
n
e
d
a
eria
l v
eh
icles
…
(
Les
ia
Mo
ch
u
r
a
d
)
713
In
our
wo
r
k
,
t
h
e
m
ai
n
f
o
cu
s
is
on
t
h
e
d
ev
elo
p
m
en
t
of
a
s
y
s
tem
th
at
will
e
n
s
u
r
e
t
h
e
a
u
to
n
o
m
o
u
s
m
o
v
em
en
t
of
v
e
h
icles
in
air
s
p
ac
e
(
au
to
p
ilo
tin
g
)
,
s
in
ce
ev
e
n
now
UAVs
ar
e
u
s
ed
or
in
te
g
r
a
ted
in
to
all
ar
ea
s
of
h
u
m
an
ac
tiv
ity
,
f
o
r
ex
am
p
le
:
−
Ag
r
icu
ltu
r
al
an
d
ag
r
ar
ian
ac
ti
v
ities
–
d
r
o
n
es
ar
e
u
s
ed
f
o
r
w
ater
in
g
or
s
o
win
g
a
f
ield
a
n
d
d
etec
tin
g
p
ests
,
an
d
d
is
ea
s
es
am
o
n
g
c
u
ltiv
ated
p
lan
ts
[
7
]
.
−
Ma
p
p
in
g
an
d
ca
r
to
g
r
ap
h
y
–
cr
ea
tin
g
,
u
p
d
atin
g
,
an
d
d
etailin
g
cu
r
r
en
t
m
a
p
s
by
co
llectin
g
in
f
o
r
m
atio
n
ab
o
u
t
th
e
en
v
ir
o
n
m
en
t
u
n
d
e
r
s
tu
d
y
t
h
r
o
u
g
h
ae
r
ial
im
a
g
es
[
8
]
.
−
C
iv
ilian
an
d
r
esear
ch
ae
r
ial
p
h
o
to
g
r
ap
h
y
–
o
b
tain
in
g
u
n
i
q
u
e
f
o
o
ta
g
e
wh
ile
av
o
id
in
g
en
v
ir
o
n
m
en
tal
p
o
llu
tio
n
a
n
d
an
y
in
ter
f
e
r
en
ce
with
th
e
ec
o
s
y
s
tem
u
n
d
e
r
s
tu
d
y
[
9
]
,
[
1
0
]
.
−
T
r
a
n
s
p
o
r
t
a
t
i
o
n
–
U
A
V
s
a
r
e
u
s
e
d
to
t
r
a
n
s
p
o
r
t
m
a
t
e
r
i
a
l
s
a
n
d
m
e
d
i
c
i
n
e
s
in
p
l
a
c
e
s
w
h
e
r
e
t
h
e
a
v
a
i
l
a
b
i
l
i
t
y
of
r
o
a
d
s
a
n
d
t
r
a
n
s
p
o
r
t
a
t
i
o
n
is
l
i
m
i
t
e
d
or
in
c
a
s
e
s
w
h
e
r
e
t
h
e
r
e
is
a
n
e
e
d
to
a
c
h
i
e
v
e
h
i
g
h
s
p
e
e
d
of
t
r
a
n
s
p
o
r
t
a
t
i
o
n
[
1
1
]
,
[
1
2
]
.
T
o
d
ay
,
t
h
e
m
ar
k
et
v
alu
e
of
au
t
o
p
ilo
t
tech
n
o
lo
g
y
f
o
r
UAVs
is
g
r
o
win
g
r
ap
id
ly
an
d
h
as
p
o
s
itiv
e
g
r
o
wth
f
o
r
ec
asts
f
o
r
th
e
n
ex
t
15
y
ea
r
s
[
1
3
]
,
[
1
4
]
,
wh
ic
h
d
em
o
n
s
tr
ates
th
e
d
ev
elo
p
er
s
'
ef
f
o
r
ts
to
cr
ea
te
a
b
etter
o
f
f
er
,
as
well
as
th
e
co
r
r
esp
o
n
d
in
g
n
ee
d
f
o
r
in
v
esto
r
s
to
h
av
e
s
u
ch
te
ch
n
o
lo
g
y
.
Deliv
er
y
s
er
v
ices
an
d
th
e
tr
an
s
p
o
r
tatio
n
s
ec
to
r
as
a
wh
o
le,
d
esp
ite
th
eir
co
n
s
tan
t
d
ev
elo
p
m
en
t,
ar
e
lim
ited
by
two
s
ig
n
if
ican
t
d
r
awb
ac
k
s
:
th
e
s
p
ee
d
an
d
th
e
n
ee
d
f
o
r
h
u
m
a
n
p
r
esen
ce
to
p
er
f
o
r
m
tr
an
s
p
o
r
tatio
n
task
s
,
wh
ich
ca
u
s
es
a
lar
g
e
n
u
m
b
e
r
of
co
m
p
licatio
n
s
,
n
am
ely
:
waitin
g
tim
e
f
o
r
o
r
d
er
d
eliv
er
y
,
lo
s
s
of
p
r
o
f
it
due
to
th
e
n
ee
d
to
k
ee
p
p
eo
p
le
f
o
r
tr
an
s
p
o
r
tatio
n
(
in
clu
d
in
g
th
e
n
ee
d
to
p
a
y
f
o
r
th
eir
la
b
o
r
)
,
d
eter
io
r
atio
n
of
t
r
af
f
ic
on
t
h
e
r
o
ad
s
(
tr
u
ck
s
tak
e
up
a
l
o
t
of
s
p
ac
e
an
d
m
o
v
e
s
lo
wly
co
m
p
ar
ed
to
ca
r
s
)
,
cr
ea
tin
g
Mo
d
er
n
air
cr
a
f
t
ar
e
ca
p
ab
le
of
c
o
v
er
in
g
h
u
n
d
r
ed
s
of
k
ilo
m
eter
s
in
a
s
h
o
r
t
p
er
i
o
d
of
tim
e
,
wh
ic
h
is
m
u
c
h
b
etter
th
an
g
r
o
u
n
d
tr
an
s
p
o
r
tatio
n
.
T
h
e
av
ailab
ilit
y
of
UAVs
with
h
ig
h
-
q
u
ality
s
o
f
twar
e
as
a
v
eh
icle
f
o
r
t
h
e
tr
a
n
s
p
o
r
tatio
n
of
s
m
al
l
an
d
m
ed
iu
m
-
s
ized
ca
r
g
o
ca
n
s
o
lv
e
m
o
s
t
of
t
h
e
ab
o
v
e
p
r
o
b
lem
s
.
Desp
ite
all
t
h
e
attem
p
ts
an
d
r
esear
ch
co
n
d
u
cted
to
s
o
lv
e
th
e
p
r
o
b
lem
of
tr
an
s
p
o
r
tatio
n
u
s
in
g
UAVs,
th
is
s
y
s
tem
h
as
not
b
e
en
g
lo
b
ally
estab
lis
h
ed
(
ex
ce
p
t
f
o
r
a
f
ew
p
r
iv
ate
co
m
p
an
ie
s
th
at
ar
e
cu
r
r
en
tly
test
in
g
th
eir
s
y
s
tem
s
,
s
u
ch
as
Am
az
o
n
)
due
to
t
h
e
lack
of
p
u
b
lic
im
p
lem
en
tatio
n
s
of
p
ath
an
d
f
lig
h
t
p
ath
alg
o
r
ith
m
s
.
Similar
p
r
o
b
lem
s
ex
is
t
in
o
th
er
ar
ea
s
,
an
d
th
e
ir
s
o
lu
tio
n
d
e
p
en
d
s
on
th
e
av
ailab
ilit
y
of
p
u
b
lic
r
esear
ch
on
th
e
p
r
o
b
lem
of
au
t
o
p
ilo
tin
g
air
cr
a
f
t
by
b
u
ild
in
g
t
h
eir
f
lig
h
t
p
ath
,
w
h
ich
is
wh
at
we
ar
e
co
n
s
id
er
in
g
in
th
is
p
ap
er
.
T
h
u
s
,
a
lar
g
e
n
u
m
b
er
of
p
r
o
b
lem
s
in
v
ar
io
u
s
a
r
ea
s
of
h
u
m
an
ac
tiv
ity
a
r
e
s
o
l
v
ed
with
th
e
h
elp
of
UAVs,
th
e
cr
ea
tio
n
of
wh
ich
r
eq
u
ir
es
p
u
b
lic
r
esear
ch
on
th
e
p
r
o
b
lem
of
au
t
o
p
ilo
tin
g
,
wh
ic
h
is
th
e
to
p
ic
of
o
u
r
wo
r
k
.
Deliv
er
y
s
er
v
ices
an
d
tr
a
n
s
p
o
r
tatio
n
,
d
esp
ite
th
eir
co
n
tin
u
o
u
s
d
e
v
elo
p
m
e
n
t,
ar
e
lim
ited
by
tw
o
s
ig
n
if
ican
t
d
r
aw
b
ac
k
s
:
s
p
ee
d
a
n
d
th
e
n
ee
d
f
o
r
h
u
m
an
p
r
esen
c
e
to
p
er
f
o
r
m
tr
an
s
p
o
r
t
task
s
,
le
ad
in
g
to
n
u
m
er
o
u
s
co
m
p
licatio
n
s
.
T
h
ese
i
n
clu
d
e
d
eliv
er
y
waitin
g
tim
es,
lo
s
s
of
r
ev
en
u
e
d
u
e
to
th
e
n
ee
d
f
o
r
p
er
s
o
n
n
el
f
o
r
tr
an
s
p
o
r
tatio
n
(
in
cl
u
d
in
g
th
ei
r
p
ay
m
en
t)
,
wo
r
s
en
ed
tr
af
f
ic
c
o
n
g
esti
o
n
(
f
r
eig
h
t
v
eh
icles
tak
e
up
s
p
ac
e
an
d
m
o
v
e
s
lo
wly
co
m
p
ar
ed
to
p
ass
en
g
er
v
eh
icles),
r
o
ad
ac
cid
e
n
ts
,
an
d
m
an
y
o
th
er
s
[
1
5
]
–
[
1
7
]
.
Mo
d
er
n
d
r
o
n
es
ar
e
ca
p
a
b
le
of
co
v
er
in
g
h
u
n
d
r
e
d
s
of
k
ilo
m
eter
s
in
s
h
o
r
t
p
e
r
io
d
s
,
wh
ic
h
is
a
m
u
ch
b
etter
in
d
icato
r
th
a
n
g
r
o
u
n
d
tr
an
s
p
o
r
tatio
n
m
o
d
es.
T
h
e
p
r
esen
ce
of
d
r
o
n
es
with
q
u
ality
s
o
f
twar
e
as
a
tr
an
s
p
o
r
tatio
n
m
ea
n
s
f
o
r
s
m
all
to
m
ed
iu
m
-
s
ized
c
ar
g
o
can
s
o
lv
e
m
o
s
t
of
th
e
af
o
r
e
m
en
tio
n
ed
p
r
o
b
lem
s
.
Desp
ite
all
attem
p
ts
an
d
r
esear
ch
c
o
n
d
u
cte
d
to
ad
d
r
ess
tr
an
s
p
o
r
tatio
n
is
s
u
es
u
s
in
g
d
r
o
n
es,
th
is
s
y
s
tem
h
as
not
b
e
en
g
lo
b
ally
o
p
tim
ized
(
ex
ce
p
t
f
o
r
a
f
ew
p
r
iv
ate
co
m
p
an
ies
cu
r
r
e
n
tly
in
th
e
test
in
g
s
tag
e
of
th
eir
s
y
s
te
m
s
,
s
u
ch
as
Am
az
o
n
)
due
to
a
lack
of
p
u
b
lic
im
p
lem
en
tatio
n
s
of
p
at
h
p
la
n
n
in
g
an
d
f
lig
h
t
tr
ajec
to
r
y
alg
o
r
i
th
m
s
.
Simi
2
lar
p
r
o
b
lem
s
e
x
is
t
in
o
t
h
er
a
r
ea
s
,
an
d
th
eir
r
eso
lu
tio
n
d
e
p
en
d
s
on
th
e
av
ailab
ilit
y
of
p
u
b
lic
r
esear
c
h
on
th
e
is
s
u
es
of
d
r
o
n
e
a
u
to
p
ilo
tin
g
,
s
p
ec
if
ically
in
co
n
s
tr
u
ctin
g
f
lig
h
t
tr
ajec
to
r
ies,
wh
ich
is
th
e
s
u
b
ject
of
our
wo
r
k
.
T
h
e
r
ef
o
r
e,
a
lar
g
e
n
u
m
b
er
of
p
r
o
b
lem
s
in
v
ar
io
u
s
h
u
m
an
ac
tiv
ities
ar
e
s
o
lv
ed
u
s
in
g
d
r
o
n
es,
t
h
e
cr
ea
tio
n
of
wh
ich
r
eq
u
ir
es
p
u
b
lic
r
esea
r
ch
on
a
u
to
p
ilo
tin
g
is
s
u
es,
wh
ich
is
th
e
to
p
ic
of
o
u
r
wo
r
k
.
T
h
e
m
ajo
r
ity
of
th
e
a
n
aly
ze
d
liter
atu
r
e
s
o
u
r
ce
s
s
h
ar
e
a
co
m
m
o
n
id
eo
lo
g
y
.
T
he
im
p
o
r
tan
ce
of
r
esear
ch
in
g
m
ea
n
s
an
d
alg
o
r
it
h
m
s
f
o
r
en
s
u
r
in
g
th
e
au
to
n
o
m
o
u
s
o
p
e
r
atio
n
of
ai
r
cr
af
t
to
p
e
r
f
o
r
m
v
ar
io
u
s
ty
p
es
of
task
s
in
v
ar
io
u
s
ar
ea
s
of
h
u
m
an
ac
tiv
ity
.
It
s
h
o
u
ld
be
n
o
te
d
th
at
n
o
n
e
of
th
e
r
ev
iewe
d
s
t
u
d
ies
claim
ed
to
be
th
e
o
n
ly
"so
lu
tio
n
"
to
all
th
e
p
r
o
b
lem
s
of
th
is
p
r
o
b
lem
.
I
n
s
te
ad
,
th
e
au
th
o
r
s
wr
o
te
th
at
cu
r
r
en
tly
(
as
of
th
e
tim
e
of
wr
itin
g
)
th
e
r
e
is
no
alg
o
r
ith
m
or
m
eth
o
d
t
h
at
wo
u
l
d
id
ea
ll
y
s
o
lv
e
t
h
e
p
r
o
b
lem
of
tr
ajec
to
r
ies
an
d
a
u
to
p
ilo
tin
g
in
g
en
er
al
f
o
r
all
task
s
(
in
o
th
er
wo
r
d
s
,
s
o
l
u
tio
n
s
ar
e
s
elec
ted
f
o
r
s
p
ec
if
ic,
l
o
ca
lized
p
r
o
b
l
em
s
)
,
but
t
h
er
e
is
a
g
r
ea
t
d
e
m
an
d
f
o
r
wo
r
k
in
g
p
r
o
t
o
ty
p
es
an
d
al
g
o
r
ith
m
s
,
wh
ich
cr
ea
tes
a
ce
r
tain
"a
r
m
s
r
ac
e"
t
h
at
co
n
tin
u
es
to
th
is
d
ay
.
Fen
g
[
1
8
]
c
o
n
s
id
er
s
a
p
ath
p
lan
n
in
g
m
eth
o
d
f
o
r
a
m
o
b
i
le
r
o
b
o
t
u
s
in
g
a
co
m
b
in
atio
n
of
a
f
ast
ex
p
lo
r
ato
r
y
r
an
d
o
m
tr
ee
(
R
R
T
)
an
d
a
p
ar
ticle
s
war
m
o
p
tim
izer
(
PS
O)
[
1
9
]
.
T
h
e
m
ain
em
p
h
asis
is
on
th
e
s
p
ee
d
an
d
ef
f
icien
cy
of
th
e
n
ew
al
g
o
r
ith
m
in
a
cl
u
tter
ed
e
n
v
ir
o
n
m
en
t,
wh
e
r
e
s
u
cc
ess
f
u
l
o
b
s
tacle
av
o
id
an
ce
is
co
n
f
ir
m
e
d
by
th
e
r
esu
lts
of
a
co
m
p
u
ter
ex
p
e
r
im
en
t.
O
u
r
w
o
r
k
p
r
o
p
o
s
es
a
p
a
r
allel
RRT
alg
o
r
ith
m
b
ased
on
co
m
p
u
te
u
n
if
ied
d
e
v
ice
ar
ch
it
ec
tu
r
e
(
C
UDA
)
tech
n
o
lo
g
y
f
o
r
o
p
tim
al
p
r
o
ce
s
s
in
g
on
a
g
ra
p
h
ics
p
ro
c
e
ss
in
g
u
n
i
t
(
GPU
)
.
Usi
n
g
an
im
p
r
o
v
e
d
PS
O
alg
o
r
ith
m
,
Yan
g
et
a
l.
[
2
0
]
also
co
n
s
id
er
a
way
to
s
o
lv
e
th
e
p
r
o
b
lem
of
d
r
o
n
e
au
to
p
ilo
tin
g
by
s
ea
r
ch
i
n
g
f
o
r
a
f
lig
h
t
p
ath
.
T
h
ey
d
r
ew
atten
t
io
n
to
th
e
n
ee
d
f
o
r
UAVs
to
be
ab
le
to
o
p
er
ate
in
Evaluation Warning : The document was created with Spire.PDF for Python.
I
SS
N
:
2
2
5
2
-
8
9
3
8
I
n
t J Ar
tif
I
n
tell
,
Vo
l.
14
,
No
.
1
,
Feb
r
u
ar
y
2
0
2
5
:
712
-
7
2
3
714
an
u
n
k
n
o
wn
en
v
ir
o
n
m
e
n
t
(
n
o
t
alwa
y
s
th
e
en
tire
s
tr
u
ctu
r
e,
o
b
s
tacle
s
,
an
d
o
th
er
en
v
ir
o
n
m
e
n
tal
p
ar
am
eter
s
will
be
k
n
o
wn
in
ad
v
a
n
ce
,
wh
ich
can
lead
to
u
n
f
o
r
eseen
co
n
s
eq
u
en
ce
s
,
lo
s
s
of
th
e
UAV
its
elf
,
an
d
in
th
e
ca
s
e
of
attac
k
UAVs,
d
es
tr
u
ctio
n
of
allied
eq
u
ip
m
en
t
an
d
s
o
ld
ier
s
)
,
an
d
u
s
ed
th
e
PSO
alg
o
r
ith
m
cr
ea
ted
f
o
r
th
is
p
u
r
p
o
s
e,
im
p
r
o
v
i
n
g
it
with
o
p
ti
m
izer
s
.
Desp
ite
all
th
eir
ef
f
o
r
ts
,
th
e
au
th
o
r
s
f
ailed
to
f
u
lly
o
p
ti
m
ize
th
e
alg
o
r
ith
m
an
d
its
s
h
o
r
tco
m
in
g
s
,
s
u
ch
as
not
g
u
ar
a
n
teed
co
n
v
er
g
e
n
ce
an
d
th
e
p
o
s
s
ib
ilit
y
of
f
ix
atio
n
in
a
lo
ca
l
m
in
im
u
m
.
T
h
e
p
o
ten
tial
co
n
v
er
g
e
n
ce
of
th
e
alg
o
r
ith
m
is
th
e
m
ain
d
r
a
wb
ac
k
th
at
will
be
a
d
d
r
ess
ed
an
d
c
o
r
r
ec
ted
in
t
h
is
p
ap
er
.
Vo
elk
er
et
a
l.
[
2
1
]
d
ev
el
o
p
e
d
a
"lig
h
tweig
h
t"
au
to
p
ilo
t
f
o
r
s
m
all
UAV
s
u
s
in
g
th
e
D
u
b
in
'
s
Path
alg
o
r
ith
m
,
em
p
h
asizin
g
th
at
d
if
f
er
en
t
task
s
an
d
ty
p
es
of
d
r
o
n
es
r
eq
u
ir
e
d
is
tin
ct
alg
o
r
ith
m
s
an
d
ap
p
r
o
ac
h
es.
T
h
ey
h
ig
h
lig
h
ted
th
at
attac
k
d
r
o
n
es
n
ee
d
co
m
p
lex
,
p
r
ec
is
e
p
ath
s
at
h
ig
h
s
p
ee
d
s
,
wh
er
ea
s
r
eg
u
lar
d
r
o
n
es
b
en
e
f
it
f
r
o
m
n
av
ig
atio
n
alg
o
r
ith
m
s
f
o
r
u
n
k
n
o
wn
s
p
ac
es
wh
e
r
e
s
p
ee
d
is
less
cr
itical.
T
h
e
au
th
o
r
s
ch
o
s
e
Du
b
in
'
s
Path
f
o
r
its
s
im
p
licity
an
d
ex
ten
s
iv
e
d
o
cu
m
en
tatio
n
but
ac
k
n
o
wled
g
ed
s
ig
n
if
ican
t
lim
itatio
n
s
:
th
e
s
y
s
tem
is
o
n
ly
f
o
r
s
m
all
UAVs,
wo
r
k
s
in
two
-
d
im
en
s
io
n
al
s
p
ac
e,
ig
n
o
r
es
o
b
s
tacle
s
,
r
eq
u
ir
es
p
r
ec
is
e
c
o
n
tr
o
l,
lac
k
s
s
elf
-
im
p
r
o
v
em
e
n
t
ca
p
a
b
ilit
ies,
an
d
s
u
p
p
o
r
ts
o
n
ly
o
n
e
UAV
at
a
ti
m
e.
In
o
u
r
s
tu
d
y
,
all
th
ese
s
h
o
r
tco
m
in
g
s
ar
e
tak
en
in
to
ac
co
u
n
t
a
n
d
co
r
r
ec
ted
or
i
m
p
r
o
v
e
d
in
o
n
e
way
or
an
o
t
h
e
r
,
s
in
ce
our
p
r
o
p
o
s
ed
s
y
s
tem
can
wo
r
k
with
UAVs
of
d
if
f
er
e
n
t
s
izes,
an
d
is
not
li
m
ited
in
th
e
n
u
m
b
e
r
of
d
im
e
n
s
io
n
s
(
R
R
T
[
2
2
]
is
one
of
th
e
b
est
alg
o
r
ith
m
s
th
at
wo
r
k
in
th
r
ee
-
d
im
en
s
io
n
al
s
p
a
ce
,
an
d
its
ef
f
icien
cy
i
n
cr
ea
s
es
with
th
e
n
u
m
b
er
of
d
im
en
s
io
n
s
u
s
ed
)
.
Ou
r
s
y
s
tem
can
be
u
s
ed
f
o
r
a
wid
e
r
a
n
g
e
of
UAV
task
s
[
2
3
]
,
it
is
also
h
ig
h
ly
f
le
x
ib
le
a
n
d
s
ca
lab
le
(
it
can
be
im
p
r
o
v
ed
by
in
s
tallin
g
ad
d
itio
n
al
m
o
d
u
les
an
d
alg
o
r
ith
m
s
)
,
a
b
le
to
tak
e
in
to
ac
co
u
n
t
o
b
s
tacle
s
an
d
en
s
u
r
e
th
eir
av
o
id
a
n
ce
,
d
o
es
n
o
t
r
e
q
u
ir
e
p
r
ec
is
e
c
o
n
tr
o
l
of
th
e
co
u
r
s
e,
s
p
ee
d
,
an
d
o
t
h
er
UAV
p
ar
am
eter
s
,
a
n
d
can
wo
r
k
with
a
lar
g
e
n
u
m
b
er
of
v
eh
icles
s
im
u
ltan
eo
u
s
ly
,
wh
ich
m
a
k
es
it
b
etter
th
an
th
e
o
n
e
d
is
cu
s
s
ed
ab
o
v
e
.
L
i
an
d
Han
s
en
[
2
4
]
d
escr
ib
es
th
e
im
p
o
r
ta
n
ce
o
f
r
esear
ch
i
n
th
e
f
ield
o
f
UAV
s
o
f
twar
e,
s
i
n
ce
ev
er
y
y
ea
r
th
e
n
u
m
b
er
o
f
task
s
th
at
co
u
ld
b
e
s
im
p
lifie
d
with
t
h
e
h
elp
o
f
,
f
o
r
e
x
am
p
le,
d
r
o
n
es
o
r
ev
en
p
o
s
s
ib
le
o
n
ly
with
th
eir
h
elp
is
g
r
o
win
g
r
ap
id
ly
,
an
d
with
it
th
e
n
ee
d
f
o
r
au
to
n
o
m
o
u
s
,
b
u
t
s
till
co
n
tr
o
ll
ed
,
UAV
o
p
er
atio
n
.
T
h
e
au
th
o
r
s
s
tu
d
ied
th
e
ef
f
ec
t
iv
en
ess
o
f
s
ev
er
al
p
ath
f
in
d
in
g
alg
o
r
ith
m
s
(
Dijk
s
tr
a'
s
[
2
5
]
,
B
ellm
an
Fo
r
d
'
s
[
2
6
]
,
Flo
y
d
-
W
ar
s
h
all's
[
2
7
]
,
A*
[
2
8
]
,
D*
[
2
9
]
)
an
d
c
o
m
p
a
r
ed
th
e
m
,
p
ay
in
g
s
p
ec
ial
atten
tio
n
t
o
th
e
A*
alg
o
r
ith
m
,
as
its
r
esu
lts
wer
e
th
e
b
est
o
f
all.
Desp
ite
th
e
g
o
o
d
r
esu
lts
o
b
tai
n
ed
an
d
th
e
g
o
al
ac
h
iev
ed
(
d
r
o
n
e
f
lig
h
t
tr
ajec
to
r
ies
b
u
ilt),
th
e
s
tu
d
y
h
as a
d
r
awb
ac
k
-
th
e
en
v
ir
o
n
m
en
t in
wh
ich
t
h
e
p
ath
s
ea
r
ch
was p
er
f
o
r
m
ed
is
well
k
n
o
wn
: th
e
au
th
o
r
s
co
n
d
u
cte
d
a
p
r
elim
in
a
r
y
an
aly
s
is
o
f
th
e
e
n
v
ir
o
n
m
en
t
an
d
p
r
ep
a
r
ed
it t
o
en
s
u
r
e
th
e
co
r
r
ec
t o
p
er
atio
n
o
f
th
e
alg
o
r
ith
m
s
(
A*
am
o
n
g
th
em
)
.
I
n
o
u
r
s
tu
d
y
,
th
is
d
r
awb
ac
k
is
co
r
r
ec
ted
b
y
u
s
in
g
an
o
th
e
r
alg
o
r
ith
m
th
at
ca
n
wo
r
k
in
a
c
o
m
p
letely
u
n
k
n
o
w
n
,
n
ew
en
v
ir
o
n
m
en
t,
wh
ich
was o
n
e
o
f
th
e
m
ain
r
ea
s
o
n
s
f
o
r
its
ch
o
ice.
J
in
et
a
l.
[
3
0
]
in
v
esti
g
ate
th
e
p
r
o
b
lem
of
s
af
e
in
d
o
o
r
UAV
n
a
v
ig
atio
n
u
s
in
g
a
s
er
ies
of
al
g
o
r
ith
m
s
an
d
m
eth
o
d
s
to
ac
h
iev
e
ac
cu
r
ate
r
esu
lts
.
T
h
e
ar
ticle
was
wr
itten
r
ec
en
tly
(
at
th
e
tim
e
of
wr
itin
g
)
an
d
o
n
ce
ag
ain
em
p
h
asizes
th
e
im
p
o
r
tan
ce
of
s
tu
d
y
in
g
th
e
au
to
n
o
m
o
u
s
o
p
er
atio
n
of
UAVs
to
p
er
f
o
r
m
v
ar
io
u
s
task
s
,
t
h
e
n
u
m
b
er
of
wh
ich
is
g
r
o
win
g
ev
er
y
y
ea
r
,
an
d
t
h
e
n
ee
d
f
o
r
ef
f
ec
tiv
e
alg
o
r
ith
m
s
(
esp
ec
ially
p
u
b
lic
o
n
es)
f
o
r
b
u
ild
in
g
a
p
ath
a
n
d
f
lig
h
t
tr
a
jecto
r
y
is
g
r
o
win
g
ex
p
o
n
e
n
tially
.
T
h
e
au
t
h
o
r
s
to
o
k
in
t
o
a
cc
o
u
n
t
th
e
n
ee
d
to
n
av
ig
ate
in
u
n
f
am
iliar
en
v
i
r
o
n
m
en
ts
an
d
d
ec
id
ed
to
im
p
lem
e
n
t
th
eir
au
t
o
-
lear
n
i
n
g
:
a
s
ep
a
r
a
te
alg
o
r
ith
m
b
u
ild
s
a
p
s
eu
d
o
-
m
ap
of
th
e
en
v
ir
o
n
m
en
t
u
s
in
g
d
ata
f
r
o
m
th
e
UA
V's
ca
m
er
as
an
d
s
en
s
o
r
s
,
an
d
o
n
ly
af
ter
th
e
f
ir
s
t
alg
o
r
ith
m
is
co
m
p
lete
d
o
es
th
e
d
r
o
n
e
s
tar
t
b
u
ild
in
g
a
r
o
u
te.
Alth
o
u
g
h
th
is
ap
p
r
o
ac
h
p
r
o
v
e
d
to
be
ef
f
ec
tiv
e,
its
im
p
lem
en
tatio
n
is
v
er
y
cu
m
b
er
s
o
m
e,
m
u
lti
-
lay
er
ed
,
an
d
r
e
q
u
ir
es
s
o
m
e
s
p
ec
ial
eq
u
ip
m
en
t
to
wo
r
k
c
o
r
r
ec
tly
,
an
d
th
e
r
o
u
te
is
b
u
ilt
o
n
ly
af
te
r
a
co
m
p
lete
s
tu
d
y
of
th
e
en
v
i
r
o
n
m
en
t,
wh
ich
u
n
d
o
u
b
te
d
ly
t
ak
es
a
lo
t
of
tim
e.
Ou
r
ap
p
r
o
ac
h
to
s
o
lv
in
g
th
e
t
an
g
en
tial
p
r
o
b
lem
also
s
tu
d
ie
s
th
e
en
v
ir
o
n
m
en
t,
but
it
d
o
es
so
s
im
u
ltan
eo
u
s
ly
with
th
e
co
n
s
tr
u
ctio
n
of
th
e
f
lig
h
t
p
ath
(
R
R
T
alg
o
r
ith
m
)
,
wh
ich
,
f
ir
s
tly
,
s
im
p
lifie
s
i
m
p
lem
en
tatio
n
,
a
n
d
s
ec
o
n
d
ly
,
r
ed
u
ce
s
th
e
o
v
er
all
tim
e
r
eq
u
ir
ed
to
lau
n
ch
th
e
UA
V
alo
n
g
th
e
b
u
ilt
r
o
u
te.
In
ad
d
itio
n
,
as
m
en
tio
n
ed
ab
o
v
e,
o
u
r
im
p
lem
en
tatio
n
allo
ws
f
o
r
f
u
tu
r
e
im
p
r
o
v
em
e
n
ts
th
at
will
p
r
o
v
id
e
g
o
o
d
r
esu
lts
f
o
r
d
if
f
e
r
en
t
task
s
,
u
n
lik
e
th
e
a
p
p
r
o
ac
h
u
s
ed
in
t
h
is
p
ap
er
:
a
lar
g
e
n
u
m
b
er
of
in
ter
co
n
n
ec
te
d
alg
o
r
ith
m
s
will
be
m
u
c
h
h
a
r
d
er
to
im
p
r
o
v
e,
as
it
will
g
u
ar
an
tee
ch
an
g
es
in
th
e
im
p
lem
en
tatio
n
.
It
s
h
o
u
ld
also
be
n
o
ted
t
h
at
th
e
p
r
o
b
ab
ilis
tic
r
o
ad
m
ap
s
(
PR
M
)
alg
o
r
ith
m
u
s
ed
by
th
e
r
esear
ch
er
s
,
as
well
as
its
r
esu
lts
,
s
tr
o
n
g
ly
d
ep
en
d
on
t
h
e
c
h
o
s
e
n
p
r
im
ar
y
s
tr
ateg
y
,
wh
ich
,
as
Alar
ab
i
et
a
l.
[
3
1
]
n
o
tes,
is
d
if
f
ic
u
lt
to
ch
o
o
s
e
co
r
r
ec
tly
.
Xu
et
a
l.
[
3
2
]
p
r
o
p
o
s
ed
a
m
et
h
o
d
f
o
r
p
lan
n
in
g
th
e
tr
ajec
t
o
r
y
o
f
m
o
b
ile
ca
b
le
-
d
r
iv
en
p
a
r
a
llel
r
o
b
o
ts
b
ased
o
n
th
e
d
ev
elo
p
ed
m
u
lti
-
ag
en
t
r
an
d
o
m
tr
ee
,
wh
ich
allo
ws
f
o
r
ad
ap
tatio
n
o
f
th
e
s
am
p
l
in
g
in
th
e
s
u
b
s
p
ac
e
an
d
ef
f
icie
n
tly
g
e
n
er
ates
p
o
s
s
ib
le
p
ath
s
.
I
t
also
p
r
esen
ts
d
y
n
a
m
ic
co
n
tr
o
l
v
alid
atio
n
,
h
eu
r
is
tic
o
p
tim
izatio
n
,
an
d
p
er
f
o
r
m
an
ce
m
etr
ics
to
en
s
u
r
e
s
m
o
o
th
an
d
o
p
tim
al
p
ath
g
e
n
er
atio
n
,
v
er
if
ied
th
r
o
u
g
h
s
im
u
lat
io
n
s
an
d
p
r
o
to
ty
p
e
ex
p
er
im
en
ts
i
n
co
m
p
lex
s
ce
n
a
r
io
s
u
s
in
g
C
o
p
p
eliaSim
s
o
f
tw
ar
e.
Kar
v
e
an
d
Ka
p
ad
ia
[
3
3
]
i
n
v
esti
g
ate
a
wa
y
to
s
o
lv
e
th
e
p
r
o
b
lem
o
f
b
u
ild
in
g
a
f
lig
h
t
p
ath
f
o
r
UAVs
u
s
in
g
th
e
Dijk
s
tr
a
alg
o
r
ith
m
,
f
o
c
u
s
in
g
o
n
ac
h
iev
in
g
ce
r
tain
co
n
s
tr
ain
ts
,
s
u
ch
as c
o
v
e
r
in
g
t
h
e
lar
g
est p
o
s
s
ib
le
ar
ea
f
o
r
v
id
eo
r
ec
o
r
d
in
g
,
th
u
s
cr
ea
tin
g
a
c
er
tain
m
o
d
if
icatio
n
o
f
th
is
al
g
o
r
ith
m
.
T
h
e
a
u
th
o
r
s
m
an
ag
ed
to
ac
h
iev
e
g
u
ar
an
tee
d
g
e
n
er
atio
n
o
f
th
e
o
p
tim
al
f
li
g
h
t p
ath
(
o
n
e
o
f
th
e
m
ain
p
r
o
p
er
ties
o
f
th
e
Dijk
s
tr
a
alg
o
r
ith
m
)
,
b
u
t
t
h
er
e
ar
e
t
wo
co
m
m
o
n
p
r
o
b
lem
s
in
th
e
ir
im
p
lem
en
tatio
n
:
I
n
ab
ilit
y
to
tak
e
in
t
o
ac
co
u
n
t
an
d
av
o
i
d
o
b
s
tacle
s
in
its
p
ath
;
I
n
ab
ilit
y
to
wo
r
k
in
u
n
k
n
o
w
n
en
v
ir
o
n
m
en
ts
(
th
e
Evaluation Warning : The document was created with Spire.PDF for Python.
I
n
t J Ar
tif
I
n
tell
I
SS
N:
2252
-
8
9
3
8
P
a
r
a
llel ra
p
id
ly
ex
p
lo
r
in
g
r
a
n
d
o
m
tr
ee
meth
o
d
fo
r
u
n
ma
n
n
e
d
a
eria
l v
eh
icles
…
(
Les
ia
Mo
ch
u
r
a
d
)
715
alg
o
r
ith
m
r
eq
u
i
r
es
a
g
r
ap
h
o
f
th
e
en
v
ir
o
n
m
e
n
t
with
weig
h
ts
th
at
co
r
r
esp
o
n
d
t
o
ce
r
tai
n
f
ea
tu
r
es
as
in
p
u
t.
B
u
ild
in
g
an
d
p
r
e
p
ar
in
g
s
u
ch
a
g
r
ap
h
tak
es
a
lo
t
o
f
tim
e)
.
T
h
e
R
R
T
alg
o
r
ith
m
,
wh
ich
w
e
u
s
e
in
o
u
r
s
tu
d
y
,
p
r
o
v
id
es
a
s
o
lu
tio
n
to
th
e
a
b
o
v
e
p
r
o
b
lem
s
.
T
h
e
r
esear
ch
in
[
3
4
]
,
[
3
5
]
,
t
h
e
au
t
h
o
r
s
also
co
n
s
id
er
th
e
p
r
o
b
lem
o
f
in
cr
ea
s
in
g
th
e
ef
f
icien
cy
o
f
p
a
th
co
n
s
tr
u
ctio
n
in
t
h
e
s
tate
s
p
ac
e
u
s
in
g
th
e
R
R
T
alg
o
r
ith
m
.
T
h
e
au
t
h
o
r
s
s
o
lv
ed
th
is
p
r
o
b
lem
b
y
p
a
r
allelizin
g
th
e
R
R
T
alg
o
r
ith
m
o
n
ce
n
tr
al
p
r
o
ce
s
s
in
g
u
n
it
(
C
PU
)
,
wh
ich
r
esu
lted
in
a
p
er
f
o
r
m
an
ce
ac
ce
ler
atio
n
o
f
3
[
3
4
]
,
a
n
d
4
[
3
5
]
tim
es.
I
n
o
u
r
s
tu
d
y
,
we
im
p
lem
en
t
th
e
p
ar
a
llel
R
R
T
alg
o
r
ith
m
o
n
a
GPU
u
s
in
g
C
UDA
tech
n
o
lo
g
y
[
3
6
]
,
[
3
7
]
.
Sin
ce
th
e
GPU
is
m
u
ch
b
etter
at
h
a
n
d
li
n
g
lar
g
e
am
o
u
n
ts
o
f
co
m
p
u
tatio
n
th
an
th
e
C
PU,
we
ex
p
ec
t
to
ac
h
iev
e
b
etter
r
esu
lts
th
an
th
o
s
e
o
b
tain
e
d
b
y
th
e
a
u
th
o
r
s
o
f
th
e
p
ap
e
r
s
m
en
tio
n
ed
ab
o
v
e,
an
d
th
u
s
ex
p
ec
t
to
ac
h
iev
e
a
b
etter
s
o
lu
tio
n
to
th
e
p
ath
f
in
d
in
g
p
r
o
b
le
m
.
W
e
h
av
e
p
r
ev
io
u
s
ly
an
aly
ze
d
v
ar
i
o
u
s
m
o
d
e
r
n
tech
n
o
lo
g
ies
o
f
d
is
tr
ib
u
ted
an
d
p
r
elim
in
ar
y
co
m
p
u
tin
g
,
i
n
p
ar
tic
u
lar
,
th
o
s
e
co
v
e
r
ed
in
[
3
8
]
,
[
3
9
]
.
Ou
r
wo
r
k
f
o
c
u
s
es
on
t
h
e
d
e
v
elo
p
m
en
t
of
a
s
y
s
tem
th
at
en
s
u
r
e
s
th
e
au
to
n
o
m
o
u
s
m
o
v
e
m
en
t
of
v
eh
icles
in
air
s
p
ac
e
(
a
u
to
p
ilo
tin
g
)
,
a
d
d
r
ess
in
g
th
e
s
ig
n
if
ica
n
t
g
ap
in
p
u
b
lic
im
p
lem
en
tatio
n
s
of
p
ath
an
d
f
lig
h
t
p
ath
alg
o
r
ith
m
s
.
Ou
r
ap
p
r
o
ac
h
p
r
o
p
o
s
es
a
p
ar
allel
R
R
T
alg
o
r
ith
m
b
ased
on
C
UDA
tech
n
o
lo
g
y
f
o
r
o
p
tim
al
p
r
o
ce
s
s
in
g
on
a
GPU,
im
p
r
o
v
in
g
th
e
e
f
f
icien
cy
an
d
ca
p
ab
ilit
y
of
UAV
au
to
p
ilo
t
s
y
s
tem
s
in
u
n
k
n
o
wn
en
v
ir
o
n
m
en
ts
.
Desp
ite
all
atte
m
p
ts
an
d
r
esear
ch
c
o
n
d
u
cted
to
ad
d
r
ess
tr
an
s
p
o
r
tatio
n
is
s
u
es
u
s
in
g
d
r
o
n
es,
th
is
s
y
s
tem
h
as
not
b
ee
n
g
lo
b
ally
o
p
tim
ized
(
ex
ce
p
t
f
o
r
a
f
ew
p
r
iv
ate
co
m
p
an
ies
cu
r
r
en
tly
in
th
e
test
in
g
s
tag
e
of
th
eir
s
y
s
tem
s
,
s
u
ch
as
Am
az
o
n
)
due
to
a
lack
of
p
u
b
lic
im
p
lem
en
tatio
n
s
of
p
ath
p
lan
n
i
n
g
an
d
f
lig
h
t
tr
ajec
to
r
y
alg
o
r
ith
m
s
.
Similar
p
r
o
b
lem
s
ex
is
t
in
o
th
e
r
a
r
ea
s
,
an
d
th
eir
r
eso
lu
tio
n
d
ep
en
d
s
on
th
e
a
v
ailab
ilit
y
of
p
u
b
lic
r
esear
ch
on
th
e
is
s
u
es
of
d
r
o
n
e
au
to
p
ilo
tin
g
,
s
p
ec
if
ically
in
c
o
n
s
tr
u
ctin
g
f
lig
h
t
tr
ajec
to
r
ies,
wh
ich
is
th
e
s
u
b
ject
of
o
u
r
wo
r
k
.
We
aim
to
d
ev
elo
p
an
ef
f
ic
ien
t
p
ar
allel
RRT
alg
o
r
ith
m
f
o
r
ex
ec
u
tio
n
on
GPUs
,
s
ig
n
if
ican
tly
en
h
an
cin
g
au
to
m
ated
tr
ajec
to
r
y
p
lan
n
i
n
g
f
o
r
UAVs.
T
h
e
m
ajo
r
ity
of
th
e
an
aly
ze
d
liter
at
u
r
e
s
o
u
r
ce
s
s
h
ar
e
a
co
m
m
o
n
id
eo
l
o
g
y
:
th
e
im
p
o
r
ta
n
ce
of
r
esear
ch
i
n
g
m
ea
n
s
an
d
alg
o
r
ith
m
s
f
o
r
e
n
s
u
r
in
g
th
e
au
t
o
n
o
m
o
u
s
o
p
er
atio
n
of
air
cr
af
t
to
p
er
f
o
r
m
v
ar
io
u
s
ty
p
es
of
task
s
in
v
ar
i
o
u
s
ar
ea
s
of
h
u
m
a
n
ac
tiv
ity
.
T
h
is
h
ig
h
lig
h
ts
th
e
o
n
g
o
in
g
d
em
an
d
f
o
r
ef
f
ec
tiv
e
an
d
p
u
b
licly
av
ailab
le
s
o
lu
tio
n
s
to
im
p
r
o
v
e
UAV
au
to
p
ilo
tin
g
ca
p
a
b
ilit
ies.
T
h
e
m
ain
co
n
tr
ib
u
tio
n
of
th
is
p
ap
er
is
as
f
o
llo
ws
:
‒
A
n
ew
p
ar
allel
RRT
m
eth
o
d
is
p
r
o
p
o
s
ed
an
d
im
p
lem
e
n
ted
u
s
in
g
C
UDA
tech
n
o
lo
g
y
f
o
r
o
p
tim
a
l
p
r
o
ce
s
s
in
g
on
th
e
GPU.
‒
A
co
m
p
r
e
h
en
s
iv
e
s
tu
d
y
an
d
c
o
m
p
ar
is
o
n
of
th
e
ef
f
ec
tiv
e
n
ess
of
p
ar
allel
alg
o
r
ith
m
s
u
s
in
g
GPU
an
d
C
PU
f
o
r
a
u
to
m
ated
tr
ajec
to
r
y
p
lan
n
in
g
of
UAV
s
was
co
n
d
u
cte
d
.
It
was
f
o
u
n
d
th
at
th
e
p
r
o
p
o
s
ed
p
a
r
allel
alg
o
r
ith
m
is
h
ig
h
ly
ef
f
icien
t,
in
p
ar
ticu
lar
in
co
n
d
itio
n
s
of
in
cr
ea
s
ed
task
co
m
p
le
x
ity
a
n
d
s
tate
s
p
ac
e
d
im
en
s
io
n
ality
.
‒
Ad
d
itio
n
ally
,
we
co
m
p
ar
ed
th
e
NVI
DI
A
R
T
X
2070
an
d
T4
GPUs
,
r
ev
ea
lin
g
th
e
ad
v
an
ta
g
e
of
th
e
latte
r
in
p
er
f
o
r
m
in
g
s
im
ilar
task
s
.
T
h
is
em
p
h
asizes
th
e
im
p
o
r
tan
ce
of
ch
o
o
s
in
g
th
e
o
p
tim
al
h
ar
d
w
ar
e
to
im
p
r
o
v
e
th
e
p
er
f
o
r
m
an
ce
of
p
ar
allel
co
m
p
u
tin
g
.
Ov
er
all
,
th
e
wo
r
k
m
a
k
es
a
s
ig
n
if
ican
t
co
n
tr
ib
u
tio
n
to
th
e
f
ield
of
au
to
m
ate
d
tr
ajec
to
r
y
p
lan
n
in
g
f
o
r
UAV
s
by
in
tr
o
d
u
cin
g
a
n
ew
p
ar
allel
alg
o
r
ith
m
an
d
p
r
o
v
id
in
g
im
p
o
r
ta
n
t
co
m
p
ar
ativ
e
p
er
f
o
r
m
a
n
ce
a
n
aly
s
es.
2.
P
RO
B
L
E
M
ST
A
T
E
M
E
NT
L
et
∈
ℝ
d
e
n
o
te
th
e
s
tate
s
p
ac
e
of
th
e
u
n
k
n
o
wn
en
v
ir
o
n
m
en
t,
a
n
d
⊆
d
en
o
te
th
e
s
u
b
s
p
ac
e
of
th
e
s
tate
s
p
ac
e
in
wh
ich
th
e
m
o
v
in
g
o
b
ject
(
UAV)
is
not
in
a
s
tate
of
co
lli
s
io
n
with
an
o
b
s
t
ac
le
(
d
o
es
not
cr
o
s
s
,
in
ter
s
ec
t,
or
p
ass
th
r
o
u
g
h
)
.
L
et
∈
d
en
o
te
th
e
co
n
f
i
g
u
r
atio
n
of
th
e
f
ly
in
g
v
eh
icle
(a
s
e
t
of
p
r
im
itiv
e
d
ir
ec
tiv
es,
an
d
s
tates).
T
h
e
al
g
o
r
ith
m
tak
es
as
in
p
u
t
th
e
i
n
itial
s
tate
an
d
th
e
tar
g
et
s
tate
,
s
u
ch
t
h
at
∈
an
d
∈
.
It
is
n
ec
ess
ar
y
to
f
in
d
a
p
ath
∶
(
0
,
1
,
2
…
,
)
,
wh
er
e
0
=
,
=
,
an
d
lies
in
th
e
s
p
ac
e
,
av
o
id
in
g
all
o
b
s
tacle
s
an
d
g
u
ar
an
teei
n
g
s
af
e
ar
r
iv
al
at
th
e
s
tate
,
if
s
u
ch
a
p
ath
is
p
o
s
s
ib
le.
3.
M
E
T
H
O
D
3
.
1
.
O
v
er
v
iew
of
t
he
s
equen
t
ia
l
ra
pid
ly
-
ex
plo
ring
ra
nd
o
m
t
re
e
a
lg
o
rit
hm
T
h
e
RRT
alg
o
r
ith
m
,
o
r
ig
i
n
ally
d
ev
is
ed
f
o
r
p
ath
f
in
d
in
g
,
is
a
wid
ely
u
tili
ze
d
m
eth
o
d
ac
r
o
s
s
v
ar
io
u
s
d
o
m
ain
s
.
T
h
e
alg
o
r
ith
m
o
p
er
a
tes
by
co
n
s
tr
u
ctin
g
a
s
to
ch
asti
c
tr
ee
to
ef
f
icien
tly
ex
p
lo
r
e
th
e
s
tate
s
p
ac
e.
T
h
e
s
tar
tin
g
p
o
s
itio
n
,
s
er
v
in
g
as
t
h
e
o
r
ig
in
of
th
e
s
ea
r
ch
,
ac
ts
as
th
e
r
o
o
t
node
of
th
e
tr
ee
.
It
f
o
llo
ws
an
iter
ativ
e
ap
p
r
o
ac
h
wh
er
ein
,
d
u
r
in
g
ea
c
h
iter
atio
n
,
a
n
ew
p
o
in
t
is
r
a
n
d
o
m
ly
ch
o
s
en
f
r
o
m
th
e
s
tate
s
p
ac
e.
Su
b
s
eq
u
en
tly
,
th
e
n
ea
r
est
node
with
in
th
e
tr
e
e,
co
n
s
id
er
in
g
o
b
s
tacle
s
,
is
lo
c
ated
r
elativ
e
to
th
e
g
en
er
ate
d
p
o
in
t.
T
h
is
n
o
d
e
is
th
en
co
n
n
ec
te
d
to
th
e
g
e
n
er
a
ted
p
o
in
t
at
a
p
r
ed
e
f
in
ed
d
is
t
an
ce
,
a
h
y
p
e
r
p
ar
am
ete
r
of
th
e
alg
o
r
ith
m
,
in
th
e
d
ir
ec
tio
n
of
th
e
g
e
n
er
ated
p
o
i
n
t.
T
h
is
p
r
o
ce
s
s
iter
ates
u
n
til
eith
er
th
e
p
ath
to
th
e
d
esire
d
s
tate
is
d
is
co
v
er
ed
or
th
e
m
ax
im
u
m
allo
wed
n
u
m
b
er
of
iter
atio
n
s
,
d
ete
r
m
in
ed
by
a
n
o
th
er
alg
o
r
ith
m
p
ar
am
eter
,
is
r
ea
ch
ed
.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
SS
N
:
2
2
5
2
-
8
9
3
8
I
n
t J Ar
tif
I
n
tell
,
Vo
l.
14
,
No
.
1
,
Feb
r
u
ar
y
2
0
2
5
:
712
-
7
2
3
716
Her
e'
s
th
e
p
s
eu
d
o
co
d
e
r
ep
r
esen
tin
g
th
e
f
o
r
m
al
d
ef
in
itio
n
of
t
h
e
RRT
alg
o
r
ith
m
:
Function
RRT(x_init,
x_goal,
X,
O):
Initialize
tree
T(x_init,)
done
⟵
false
While
not
done:
x_rand
⟵
RandState(X,
O)
x_near
⟵
Nearest(x_rand,
T)
x_new
⟵
Steer(x_near,
x_rand)
e_new
⟵
{x_near,
x_new}
If
not
CheckCollision(e_new,
O):
Add
vertex
x_new
to
V:
V
=
V
∪
{x_new}
Add
edge
e_new
to
E:
E
=
E
∪
{e_new}
If
x_new
=
x_goal:
Path(x_new)
done
⟵
true
Return
T
T
h
is
p
s
eu
d
o
c
o
d
e
r
ep
r
esen
ts
th
e
RRT
alg
o
r
ith
m
u
s
in
g
f
u
n
ctio
n
s
:
(
,
)
–
f
u
n
ctio
n
f
o
r
g
en
er
atin
g
;
(
,
,
)
–
f
u
n
ctio
n
to
f
i
n
d
th
e
n
ea
r
est
n
o
d
e
;
(
,
)
–
a
f
u
n
ctio
n
f
o
r
b
u
ild
i
n
g
a
s
tate
f
r
o
m
th
e
n
e
ar
est
node
in
th
e
d
ir
ec
tio
n
;
ℎ
(
,
)
–
f
u
n
ctio
n
to
ch
ec
k
if
th
er
e
is
an
o
b
s
tacle
b
etwe
en
a
n
d
.
ℎ
(
)
–
a
f
u
n
ctio
n
f
o
r
tr
av
er
s
in
g
th
e
tr
e
e
in
th
e
r
ev
er
s
e
o
r
d
er
f
r
o
m
to
th
e
r
o
o
t
to
g
et
th
e
p
ath
.
T
h
e
RRT
f
u
n
ctio
n
tak
es
in
p
u
t
,
,
,
an
d
,
an
d
r
etu
r
n
s
th
e
tr
ee
r
ep
r
esen
tin
g
t
h
e
p
ath
f
o
u
n
d
by
th
e
RRT
alg
o
r
ith
m
.
W
h
er
e
∈
ℝ
−
s
ta
te
s
pa
c
e
;
⊆
−
is
th
e
s
et
o
f
o
b
s
tacle
s
,
wh
ich
is
o
b
v
io
u
s
ly
a
s
u
b
s
et
o
f
th
e
s
tat
e
s
p
ac
e;
=
(
,
)
–
tr
ee
b
u
ilt
as
a
r
esu
lt
of
th
e
RRT
alg
o
r
ith
m
;
−
s
et
o
f
tr
ee
n
o
d
es
⊆
b
ut
∩
=
;
−
s
e
t
of
tr
e
e
e
dge
s
;
−
in
itial
s
tate
;
−
tar
g
et
s
tate;
,
∈
;
−
r
an
d
o
m
ly
s
elec
ted
s
tate,
∈
;
−
is
th
e
n
ea
r
est
n
o
d
e
o
f
th
e
tr
ee
to
,
∈
;
−
s
elec
ted
p
o
in
t
b
ased
o
n
a
n
d
,
∈
;
–
ed
g
e
co
n
n
ec
tin
g
th
e
v
er
tices
an
d
.
3
.
2
.
P
a
ra
llel
ra
pid
ly
-
ex
plo
ri
ng
ra
nd
o
m
t
re
e
a
lg
o
rit
hm
B
ef
o
r
e
d
escr
ib
in
g
th
e
p
ar
allel
ized
v
er
s
io
n
of
R
R
T
,
we
b
elie
v
e
it
is
n
ec
ess
ar
y
to
g
iv
e
an
a
s
y
m
p
to
tic
esti
m
ate
of
th
e
co
m
p
le
x
ity
of
co
m
p
u
tin
g
s
eq
u
en
tial
RRT
:
(
,
)
=
(
)
+
(
)
+
(
∗
∗
l
og
(
)
)
=
∗
N
∗
l
og
(
N
)
wh
er
e
is
th
e
n
u
m
b
er
of
s
tates,
is
th
e
n
u
m
b
er
of
o
b
s
tacle
s
,
(
)
−
asy
m
p
to
tic
f
u
n
ctio
n
ev
alu
ati
o
n
;
(
)
−
asy
m
p
to
tic
f
u
n
ctio
n
e
v
a
lu
atio
n
,
(
∗
∗
l
og
(
)
)
−
asy
m
p
to
tic
ev
alu
atio
n
of
f
u
n
ctio
n
s
a
n
d
ℎ
.
Acc
o
r
d
in
g
ly
,
to
d
ev
elo
p
a
p
ar
allel
RRT
th
at
will
r
u
n
on
th
e
GPU,
we
h
av
e
b
ee
n
th
in
k
in
g
with
in
th
e
f
r
am
ewo
r
k
of
th
e
SIM
D
(
Sin
g
le
I
n
s
tr
u
ctio
n
Mu
ltip
le
Data
)
a
r
ch
itectu
r
e,
w
h
ich
will
allo
w
us
to
b
est
u
tili
ze
th
e
h
ar
d
war
e
ca
p
ab
ilit
ies
p
r
o
v
id
e
d
by
GPUs
.
Acc
o
r
d
in
g
ly
,
we
p
r
o
p
o
s
e
to
p
a
r
allelize
th
e
f
o
llo
win
g
alg
o
r
ith
m
f
u
n
ctio
n
s
:
,
,
ℎ
–
th
ey
ar
e
id
ea
l
f
o
r
ex
ec
u
tio
n
on
a
lar
g
e
n
u
m
b
e
r
of
GPU
p
r
o
ce
s
s
o
r
s
,
ar
e
au
to
n
o
m
o
u
s
,
i.
e.
,
do
n
o
t
r
eq
u
ir
e
s
y
n
c
h
r
o
n
izatio
n
,
an
d
will
n
o
t
ex
ce
e
d
th
e
e
x
ec
u
tio
n
tim
e
lim
it
(
f
o
r
ex
am
p
le,
f
o
r
C
UDA
tec
h
n
o
lo
g
y
,
it
is
one
s
ec
o
n
d
)
.
W
ith
s
u
ch
p
ar
alleliza
tio
n
,
we
s
h
o
u
ld
ac
h
iev
e
th
e
f
o
llo
win
g
asy
m
p
t
o
tic
co
m
p
u
ta
tio
n
al
co
m
p
lex
ity
:
(
,
)
=
(
)
+
(
)
+
(
∗
∗
l
og
(
)
/
)
=
∗
∗
l
o
g
(
N
)
wh
er
e
is
th
e
n
u
m
b
er
of
s
tates,
is
th
e
n
u
m
b
e
r
of
o
b
s
tacle
s
,
an
d
is
th
e
n
u
m
b
er
of
GPU
co
r
e
s
.
In
o
u
r
wo
r
k
,
we
u
s
ed
th
e
f
o
llo
win
g
tech
n
o
l
o
g
ies
to
d
ev
el
o
p
an
d
o
p
tim
ize
c
o
m
p
u
tin
g
p
r
o
ce
s
s
es:
−
C
UDA
:
S
o
f
twar
e
d
ev
elo
p
m
e
n
t
th
at
u
s
es
GPUs
to
p
er
f
o
r
m
g
en
er
al
-
p
u
r
p
o
s
e
co
m
p
u
tin
g
.
W
ith
th
e
h
elp
of
C
UDA,
co
m
p
u
tatio
n
al
ac
ce
ler
atio
n
was
ac
h
iev
ed
d
u
e
to
p
ar
allel
p
r
o
ce
s
s
in
g
of
d
ata
by
t
h
e
GPU.
−
Py
th
o
n
:
Usi
n
g
Py
th
o
n
as
an
in
ter
p
r
eted
p
r
o
g
r
a
m
m
in
g
lan
g
u
a
g
e
f
o
r
r
a
p
id
p
r
o
to
ty
p
i
n
g
,
d
e
v
e
lo
p
m
en
t,
an
d
s
o
lv
in
g
co
m
p
u
tatio
n
al
p
r
o
b
le
m
s
.
Py
th
o
n
was
ch
o
s
en
b
ec
au
s
e
of
its
wid
e
r
an
g
e
of
to
o
ls
an
d
ea
s
e
of
u
s
e.
−
Nu
m
b
a:
Usi
n
g
Nu
m
b
a
as
a
h
ig
h
er
-
lev
el
ab
s
tr
ac
tio
n
f
o
r
C
UDA
tech
n
o
lo
g
y
to
s
im
p
lify
d
ev
el
o
p
m
en
t,
m
ak
e
co
d
e
m
o
r
e
s
ec
u
r
e,
an
d
r
ed
u
ce
p
o
ten
tial
er
r
o
r
s
.
Nu
m
b
a
p
r
o
v
id
es
J
I
T
co
m
p
ilatio
n
f
o
r
ef
f
ici
en
t
GPU
an
d
C
PU
co
m
p
u
tin
g
.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
n
t J Ar
tif
I
n
tell
I
SS
N:
2252
-
8
9
3
8
P
a
r
a
llel ra
p
id
ly
ex
p
lo
r
in
g
r
a
n
d
o
m
tr
ee
meth
o
d
fo
r
u
n
ma
n
n
e
d
a
eria
l v
eh
icles
…
(
Les
ia
Mo
ch
u
r
a
d
)
717
−
Nu
m
Py
:
Usi
n
g
Nu
m
Py
to
p
r
o
ce
s
s
an
d
an
aly
ze
d
ata,
as
well
as
to
ef
f
icien
tly
im
p
lem
en
t
c
o
m
p
u
tatio
n
s
on
ar
r
ay
s
an
d
m
atr
ices
of
lar
g
e
s
izes.
Nu
m
Py
h
as
b
ee
n
u
s
ed
to
s
o
lv
e
s
cien
tific
co
m
p
u
tin
g
an
d
d
ata
p
r
o
ce
s
s
in
g
p
r
o
b
lem
s
.
−
Ma
tp
lo
tlib
:
Usi
n
g
Ma
tp
lo
tlib
to
v
is
u
alize
d
ata
an
d
ca
lc
u
latio
n
r
esu
lts
.
T
h
e
lib
r
a
r
y
allo
ws
you
to
cr
ea
t
e
v
ar
io
u
s
ty
p
es
of
g
r
a
p
h
s
f
o
r
ea
s
y
an
aly
s
is
an
d
p
r
esen
tatio
n
of
wo
r
k
r
esu
lts
.
T
h
u
s
,
th
e
co
m
b
i
n
atio
n
of
th
e
s
e
tech
n
o
lo
g
ies
allo
wed
us
to
d
ev
elo
p
ef
f
icien
t
s
o
f
twar
e
to
s
o
lv
e
th
e
co
m
p
u
tatio
n
al
p
r
o
b
lem
,
tak
in
g
ad
v
an
tag
e
of
GPUs
an
d
p
r
o
v
id
in
g
a
u
s
er
-
f
r
ien
d
ly
i
n
ter
f
ac
e
f
o
r
d
e
v
elo
p
m
e
n
t
an
d
v
is
u
aliza
tio
n
.
W
h
en
im
p
lem
en
tin
g
th
e
alg
o
r
ith
m
,
we
u
s
e
th
e
"Nu
m
b
a"
lib
r
ar
y
d
ec
o
r
ato
r
"c
u
d
a.
jit",
with
th
e
h
elp
of
w
h
ich
we
d
ef
i
n
e
f
u
n
ctio
n
s
th
at
will
be
ex
ec
u
ted
on
a
GPU
th
at
s
u
p
p
o
r
ts
C
UDA
tech
n
o
lo
g
y
.
Acc
o
r
d
in
g
ly
,
th
e
f
o
llo
win
g
f
u
n
ctio
n
s
wer
e
im
p
lem
en
te
d
,
−
eu
c_
d
is
ta
n
ce
_
2
d
_
d
ev
ice(
x1
,
y
1
,
x2
,
y2
)
–
f
u
n
ctio
n
f
o
r
ca
lcu
lati
n
g
th
e
E
u
clid
ea
n
d
is
tan
ce
b
et
wee
n
p
o
in
ts
on
th
e
GPU
,
@
cu
d
a
.
jit(d
ev
ice=Tru
e)
d
ef
eu
c_
d
is
ta
n
ce
_
2
d
_
d
ev
ice(
x
1
,
y1
,
x2
,
y2
)
:
d
=
ma
th
.
s
q
r
t(
(
x2
-
x
1
)
*
*
2
+(
y2
-
y1
)
*
*
2
)
r
etu
r
n
d
−
d
ef
d
is
ta
n
ce
K
ern
el(
d
_
o
u
t,x
,
y,
d
_
V
,
n
o
v)
:
–
k
e
r
n
el
f
u
n
ctio
n
r
esp
o
n
s
ib
le
f
o
r
p
ar
allel
ca
lcu
latio
n
of
th
e
d
is
tan
ce
s
b
etwe
en
th
e
g
en
er
at
ed
p
o
in
t
a
n
d
th
e
tr
ee
n
o
d
es
,
@
cu
d
a
.
jit()
d
ef
d
is
ta
n
ce
K
ern
el(
d
_
o
u
t,x
,
y,
d
_
V
,
n
o
v
)
:
i
=
cu
d
a
.
b
l
o
ck
I
d
x.
x
*
cu
d
a
.
b
lo
c
kDim.
x
+
cu
d
a
.
th
r
ea
d
I
d
x.
x
if
i
<
n
o
v:
d
_
o
u
t[
i]
=
eu
c_
d
is
ta
n
ce
_
2
d
_
d
ev
ice(
x,
y,
d
_
V
[
0
,
i]
,
d
_
V
[
1
,
i]
)
−
d
A
r
r
a
y(
x,
y,
V
,
n
o
v
)
–
f
u
n
ctio
n
to
en
ca
p
s
u
late
t
h
e
ex
c
h
an
g
e
of
in
f
o
r
m
atio
n
b
etwe
en
th
e
h
o
s
t
an
d
th
e
d
ev
ice
wh
en
ca
lcu
latin
g
d
is
tan
ce
s
,
d
ef
d
A
r
r
a
y(
x,
y,
V
,
n
o
v)
:
d_V
=
cu
d
a
.
to
_
d
ev
ice(
V
)
#
co
p
ies
th
e
in
p
u
t
d
a
ta
to
a
d
ev
ice
a
r
r
a
y
on
th
e
GP
U
d
_
d
is
ta
n
ce
=
cu
d
a
.
d
ev
ice_
a
r
r
a
y(
n
o
v
)
#
crea
tes
an
emp
ty
a
r
r
a
y
to
h
o
ld
t
h
e
o
u
t
p
u
t
BPG
=
(
n
o
v
+
TPB
-
1
)
//T
P
B
#
co
mp
u
tes
n
u
mb
er
of
b
lo
ck
s
d
is
ta
n
ce
K
ern
el[BP
G,
TPB
]
(
d
_
d
is
ta
n
ce
,
x,
y,
d
_
V
,
n
o
v
)
r
etu
r
n
d
_
d
is
ta
n
ce
.
co
p
y_
to
_
h
o
s
t(
)
−
d
ef
cc
K
ern
el(
d
_
o
u
t,x
,
y,
d
_
O,
a
ll_
r
a
d
ii):
–
k
er
n
el
f
u
n
ctio
n
r
esp
o
n
s
ib
le
f
o
r
th
e
p
ar
allel
ca
lcu
latio
n
of
co
llis
io
n
s
,
@
cu
d
a
.
jit()
d
ef
cc
K
ern
el(
d
_
o
u
t,x
,
y,
d
_
O,
a
l
l_
r
a
d
ii):
i
=
cu
d
a
.
b
l
o
ck
I
d
x.
x
*
cu
d
a
.
b
lo
c
kDim.
x
+
cu
d
a
.
th
r
ea
d
I
d
x.
x
#
fla
g
=
1
if
i
<
a
ll_
r
a
d
ii.si
z
e:
#
and
fla
g
==1
:
d
_
o
u
t[
i]
=
eu
c_
d
is
ta
n
ce
_
2
d
_
d
ev
ice(
x,
y,
d
_
O[0
,
i]
,
d
_
O[1
,
i]
)
>
a
ll_
r
a
d
ii[
i]
#
s
h
o
u
ld
be
1
fo
r
no
co
llis
io
n
#
fla
g
=
d
_
o
u
t[
i]
−
d
ef
d
A
r
r
a
y_
C
C
(
x,
y,
o
b
s
_
co
o
r
s
,
a
llo
w
a
b
le_
r
a
d
ii):
–
a
f
u
n
ctio
n
f
o
r
en
ca
p
s
u
latin
g
th
e
ex
ch
an
g
e
of
in
f
o
r
m
atio
n
b
etwe
en
th
e
h
o
s
t
an
d
th
e
d
ev
ice
wh
en
ca
lcu
latin
g
co
llis
io
n
s
with
o
b
s
tacle
s
,
d
ef
d
A
r
r
a
y_
C
C
(
x,
y,
o
b
s
_
co
o
r
s
,
a
llo
w
a
b
le_
r
a
d
ii):
noo
=
a
llo
w
a
b
le_
r
a
d
ii.si
z
e
d
_
a
ll_
r
a
d
ii
=
cu
d
a
.
to
_
d
ev
ice(
a
llo
w
a
b
le_
r
a
d
ii)
#
c
o
p
ies
th
e
i
n
p
u
t
d
a
ta
to
a
d
ev
ice
a
r
r
a
y
on
th
e
GP
U
d_O
=
cu
d
a
.
to
_
d
ev
ice(
o
b
s
_
c
o
o
r
s
)
#
co
p
ies
th
e
in
p
u
t
d
a
t
a
to
a
d
ev
ice
a
r
r
a
y
on
th
e
GP
U
d
_
co
llis
io
n
=
cu
d
a
.
d
ev
ice_
a
r
r
a
y(
n
o
o
)
#
crea
tes
an
emp
ty
a
r
r
a
y
to
h
o
ld
t
h
e
o
u
t
p
u
t
BPG
=
(
n
o
o
+
TPB
-
1
)
//T
P
B
#
co
mp
u
tes
n
u
mb
er
of
b
lo
ck
s
cc
K
ern
el[BP
G,
TPB
]
(
d
_
co
llis
io
n
,
x,
y,
d
_
O,
d
_
a
ll_
r
a
d
ii)
r
etu
r
n
d
_
co
llis
io
n
.
co
p
y
_
to
_
h
o
s
t(
)
4.
RE
SU
L
T
S
AND
D
I
SCU
SS
I
O
N
Nu
m
er
ical
ex
p
er
im
e
n
ts
f
o
r
th
i
s
wo
r
k
wer
e
co
n
d
u
cted
on
t
h
e
f
o
llo
win
g
h
a
r
d
war
e
s
y
s
tem
s
:
−
NVI
DI
A
GeFo
r
ce
R
T
X
2070
−
NVI
DI
A
T4
GPU
−
C
PU
I
n
tel(
R
)
C
o
r
e(
T
M)
i7
-
1
0
7
5
0
H
C
PU
@
2
.
6
0
GHz
2
.
5
9
GHz.
Evaluation Warning : The document was created with Spire.PDF for Python.
I
SS
N
:
2
2
5
2
-
8
9
3
8
I
n
t J Ar
tif
I
n
tell
,
Vo
l.
14
,
No
.
1
,
Feb
r
u
ar
y
2
0
2
5
:
712
-
7
2
3
718
In
th
is
s
tu
d
y
,
we
do
not
u
s
e
d
atasets
,
b
ec
au
s
e
th
e
RRT
alg
o
r
ith
m
s
o
lv
es
th
e
p
r
o
b
lem
of
f
i
n
d
in
g
a
p
ath
in
an
ar
b
itra
r
y
s
tate
s
p
ac
e,
so
we
d
ev
elo
p
ed
a
p
r
o
ce
d
u
r
e
to
g
e
n
er
ate
s
tate
s
p
ac
es
w
ith
an
ar
b
itra
r
y
n
u
m
b
er
of
o
b
s
tacle
s
u
s
in
g
th
e
Nu
m
Py
lib
r
ar
y
.
def
generate_obstacles(obstacles_count:
int,
radius:
float,
state_dimension:
int)
-
>
[np.ndarray,
np.ndarray]:
"""
:param
obstacles_count:
the
number
of
obstacles
to
generate
:param
radius:
the
radius
of
each
obstacle
:param
state_dimension:
the
dimensionality
of
the
state
space
:return:
two
NumPy
arrays
containing
the
radii
and
coordinates
of
the
generated
obstacles
"""
obstacles_radii
=
radius
*
np.ones(obstacles_count)
obstacles_coordinates
=
state_dimension
*
np.random.rand(2,
obstacles_count)
return
obstacles_radii,
obstacles_coordinates
generate_obstacles(512,
np.sqrt(3)
/
2,
100)
In
th
is
p
s
eu
d
o
-
co
d
e
,
th
e
g
en
er
ate_
o
b
s
tacle
s
f
u
n
ctio
n
g
en
er
at
es
a
s
p
ec
if
ied
n
u
m
b
er
of
o
b
s
t
ac
les
with
th
e
s
p
ec
if
ied
r
ad
iu
s
an
d
d
im
e
n
s
io
n
s
of
th
e
s
tate
s
p
ac
e.
T
h
e
r
esu
lt
is
two
Nu
m
Py
ar
r
ay
s
:
one
with
th
e
r
ad
ii
of
th
e
o
b
s
tacle
s
an
d
th
e
o
th
er
with
th
eir
co
o
r
d
i
n
ates
in
th
e
s
tate
s
p
ac
e.
An
ex
am
p
le
of
th
e
f
u
n
ct
io
n
ca
ll
s
h
o
ws
how
512
o
b
s
tacle
s
with
a
r
ad
iu
s
e
q
u
al
to
s
q
r
t(
3
)
/2
ca
n
be
g
en
e
r
at
ed
in
a
s
tate
s
p
ac
e
of
s
ize
1
0
0
.
We
g
r
o
u
p
ed
all
th
e
en
v
ir
o
n
m
en
ts
on
wh
ic
h
we
co
n
d
u
cted
t
h
e
ex
p
e
r
im
en
ts
an
d
s
av
ed
th
em
in
a
p
u
b
licly
av
aila
b
le
d
ataset
[
4
0
]
.
T
h
e
f
o
llo
win
g
ar
e
ex
am
p
les
of
b
u
ild
in
g
a
p
ath
s
ea
r
ch
tr
ee
in
th
e
g
en
er
ated
s
tate
s
p
ac
es.
F
ig
u
r
e
1
s
h
o
ws
th
e
s
ea
r
ch
tr
ee
b
u
ilt
u
s
in
g
th
e
RRT
alg
o
r
ith
m
(
g
r
ee
n
c
o
lo
r
i
n
d
icate
s
th
e
n
o
d
es
of
th
e
tr
ee
,
th
ey
a
r
e
co
n
n
ec
ted
by
b
lac
k
lin
es)
a
n
d
th
e
p
ath
f
o
u
n
d
(
y
ello
w
lin
e
)
b
etwe
en
th
e
p
o
in
ts
(
5
;5
)
a
n
d
(
9
0
;9
0
)
in
th
e
s
tate
s
p
ac
e
100
×
1
0
0
an
d
th
e
n
u
m
b
er
of
o
b
s
tacle
s
(
b
lu
e
co
l
o
r
)
5
1
2
;
NVI
DI
A
Ge
Fo
r
ce
R
T
X
2
0
7
0
.
In
Fig
u
r
e
1
(
a)
,
we
s
ee
th
e
r
esu
l
t
of
our
p
a
r
allel
RRT
alg
o
r
ith
m
,
wh
ich
s
u
cc
ess
f
u
lly
f
in
d
s
a
p
ath
b
etwe
en
th
e
s
tates
w
ith
co
o
r
d
in
ates
(
5
;5
)
an
d
(
9
0
;9
0
)
in
5
.
4
4
3
8
s
ec
o
n
d
s
,
t
h
e
f
o
u
n
d
p
ath
is
v
is
u
alize
d
by
a
y
ello
w
lin
e
.
T
h
e
g
r
ee
n
d
o
ts
co
n
n
ec
ted
by
b
lac
k
lin
es
p
r
o
v
i
d
e
a
g
r
ap
h
ical
r
ep
r
esen
tatio
n
of
th
e
s
ea
r
ch
p
r
o
ce
s
s
in
th
e
100
×
100
s
tate
s
p
ac
e.
In
Fig
u
r
e
1
(
b
)
,
we
can
o
b
s
er
v
e
th
e
wo
r
k
of
th
e
s
eq
u
en
tial
RRT
ex
ec
u
ted
on
th
e
C
PU,
th
e
ex
ec
u
tio
n
tim
e
is
5
.
1
8
1
s
ec
o
n
d
s
.
Alth
o
u
g
h
th
e
en
v
ir
o
n
m
e
n
ts
in
Fig
u
r
es
1(
a
)
an
d
1
(
b
)
ar
e
th
e
s
am
e
s
ize
(
1
0
0
×
1
0
0
)
,
it
is
e
asy
to
s
ee
th
at
th
e
en
v
ir
o
n
m
en
t
in
th
is
f
ig
u
r
e
is
m
u
ch
s
im
p
ler
(
1
2
8
o
b
s
tacle
s
in
Fig
u
r
e
1
(
a)
v
s
.
512
in
Fig
u
r
e
1
(
b
)
).
C
o
m
p
ar
in
g
th
ese
two
ca
s
es,
we
can
s
ee
th
a
t
wh
en
r
u
n
n
in
g
p
ar
allel
RRT
on
a
v
id
e
o
ca
r
d
,
with
a
more
c
o
m
p
lex
en
v
ir
o
n
m
en
t,
th
e
alg
o
r
ith
m
ex
p
l
o
r
ed
m
o
s
t
of
th
e
s
tate
s
p
ac
e
at
alm
o
s
t
th
e
s
am
e
tim
e
as
th
e
s
eq
u
en
tial
al
g
o
r
ith
m
in
a
m
u
ch
s
im
p
ler
s
p
ac
e,
wh
ich
s
ig
n
if
ic
an
tly
in
cr
ea
s
es
th
e
p
r
o
b
ab
ilit
y
of
f
in
d
in
g
a
p
ath
in
a
co
n
s
ta
n
t
tim
e.
T
h
is
is
th
e
m
ain
id
ea
b
eh
in
d
th
e
ap
p
licati
o
n
of
th
e
alg
o
r
ith
m
we
h
av
e
d
ev
elo
p
ed
:
by
p
ar
allelizin
g
a
n
d
u
s
in
g
th
e
h
ar
d
war
e
ca
p
ab
ilit
ies
of
GPU
s
,
we
not
o
n
ly
s
p
ee
d
up
th
e
s
o
lu
tio
n
of
th
e
p
r
o
b
lem
of
f
in
d
in
g
a
p
ath
in
th
e
s
tate
s
p
ac
e
but
also
in
cr
ea
s
e
th
e
p
r
o
b
ab
ilit
y
of
f
in
d
in
g
th
is
p
ath
in
s
o
m
e
tim
e.
T
h
e
f
o
l
lo
wi
n
g
f
o
r
m
u
l
a
was
u
s
ed
to
ca
l
c
u
la
te
t
h
e
s
p
ee
d
u
p
b
as
ed
on
t
h
e
m
e
asu
r
em
en
ts
of
t
h
e
e
x
ec
u
ti
o
n
tim
e
of
t
h
e
R
R
T
al
g
o
r
it
h
m
an
d
t
h
e
p
a
r
a
lle
l
v
er
s
io
n
we
d
e
v
e
lo
p
e
d
:
=
,
w
h
e
r
e
is
t
h
e
r
at
io
of
th
e
ti
m
e
r
e
q
u
i
r
e
d
to
p
e
r
f
o
r
m
ca
lc
u
la
ti
o
n
s
on
a
s
i
n
g
l
e
-
p
r
o
ce
s
s
o
r
c
o
m
p
u
t
er
s
y
s
te
m
to
th
e
ti
m
e
to
s
o
l
v
e
t
h
e
s
a
m
e
p
r
o
b
l
em
on
a
p
ar
all
el
s
y
s
te
m
(
i
n
our
ca
s
e
,
a
GPU
)
u
s
in
g
a
p
a
r
a
llel
al
g
o
r
it
h
m
.
T
h
u
s
,
t
h
e
t
im
e
m
ea
s
u
r
em
en
ts
of
t
h
e
s
eq
u
e
n
t
ial
a
n
d
p
a
r
a
lle
l
al
g
o
r
i
th
m
s
f
o
r
s
ta
te
s
p
ac
es
of
1
0
0
×
100
a
n
d
2
0
0
×
200
ar
e
p
r
es
en
te
d
in
T
a
b
le
s
1
an
d
2
a
n
d
v
is
u
alize
d
in
Fig
u
r
e
s
2
an
d
3
,
r
esp
ec
tiv
ely
.
T
h
e
p
a
r
allel
s
p
ee
d
u
p
r
ates
f
o
r
d
if
f
er
en
t
s
tate
s
p
ac
es
ar
e
p
r
esen
te
d
in
T
ab
le
s
3
an
d
4
.
L
et's
s
tar
t
an
aly
zin
g
th
e
r
esu
lts
of
th
e
n
u
m
er
ical
e
x
p
er
im
e
n
ts
by
ev
alu
atin
g
th
e
s
p
ee
d
of
th
e
two
alg
o
r
ith
m
s
u
n
d
er
s
tu
d
y
.
We
can
s
ee
th
at
th
e
GPU
-
p
ar
alle
lized
alg
o
r
ith
m
is
f
aster
th
a
n
th
e
co
n
v
en
tio
n
al
s
eq
u
en
tial
alg
o
r
ith
m
.
In
p
ar
tic
u
lar
,
as
th
e
p
ar
am
etr
ic
co
m
p
l
ex
ity
of
th
e
p
r
o
b
lem
in
c
r
ea
s
ed
,
th
e
d
if
f
e
r
en
ce
in
ex
ec
u
tio
n
tim
e
in
cr
ea
s
ed
s
ig
n
i
f
ican
tly
,
wh
ic
h
,
as
e
x
p
ec
ted
,
is
due
to
th
e
r
ed
u
ctio
n
in
t
h
e
o
v
er
all
co
m
p
lex
ity
of
th
e
alg
o
r
ith
m
(
in
cl
u
d
in
g
s
y
n
ch
r
o
n
izatio
n
tim
e
)
an
d
th
e
p
ar
allel
u
s
e
of
C
UDA
co
r
es
f
o
r
co
m
p
u
tatio
n
al
o
p
er
atio
n
s
.
We
can
s
ee
th
at
af
t
er
ap
p
ly
in
g
2
0
4
8
or
m
o
r
e
o
b
s
t
ac
les
in
th
e
g
en
e
r
ated
en
v
ir
o
n
m
en
t
d
e
f
in
ed
in
th
e
s
tate
s
p
ac
e
of
d
im
en
s
io
n
100
×
100,
th
e
co
m
p
u
tatio
n
tim
e
of
th
e
s
eq
u
en
tial
alg
o
r
ith
m
on
th
e
C
PU
in
cr
ea
s
e
s
ap
p
r
o
x
im
ately
twice
with
ea
c
h
s
tep
,
wh
ile
th
e
G
PU
-
p
ar
allelize
d
alg
o
r
ith
m
r
em
ain
s
in
p
lace
(
as
can
be
s
ee
n
in
T
ab
le
1
),
ag
ain
s
t
th
e
g
eo
m
etr
i
c
g
r
o
wth
of
th
e
n
u
m
b
er
of
o
b
s
tacle
s
(
an
d
,
as
a
r
esu
lt,
co
m
p
u
tatio
n
s
)
.
W
h
en
th
e
n
u
m
b
er
of
o
b
s
tacle
s
was
le
s
s
t
h
an
1
0
2
4
,
we
o
b
s
er
v
ed
an
ad
v
an
tag
e
in
th
e
s
p
ee
d
of
th
e
s
eq
u
en
tial
alg
o
r
ith
m
on
th
e
C
PU,
h
o
wev
er
,
t
h
e
p
er
f
o
r
m
an
ce
of
p
ar
allel
co
m
p
u
tatio
n
s
ev
en
with
5
1
2
o
b
s
tacle
s
d
if
f
e
r
ed
in
t
h
e
wo
r
s
t
ca
s
e
by
o
n
ly
0
.
3
.
In
o
th
er
wo
r
d
s
,
e
v
en
with
th
e
s
y
n
ch
r
o
n
izatio
n
tim
e,
th
e
p
ar
allelize
d
alg
o
r
ith
m
g
av
e
g
o
o
d
s
p
ee
d
r
esu
lts
,
wh
ich
m
ak
es
it
s
u
itab
l
e
f
o
r
r
elativ
ely
lig
h
tweig
h
t
p
r
o
b
lem
s
(
with
a
s
m
all
n
u
m
b
er
of
o
b
s
tacle
s
in
s
m
all
s
tate
s
p
ac
es).
Evaluation Warning : The document was created with Spire.PDF for Python.
I
n
t J Ar
tif
I
n
tell
I
SS
N:
2252
-
8
9
3
8
P
a
r
a
llel ra
p
id
ly
ex
p
lo
r
in
g
r
a
n
d
o
m
tr
ee
meth
o
d
fo
r
u
n
ma
n
n
e
d
a
eria
l v
eh
icles
…
(
Les
ia
Mo
ch
u
r
a
d
)
719
(
a)
(
b
)
Fig
u
r
e
1.
A
s
ea
r
ch
tr
ee
is
co
n
s
tr
u
cted
an
d
a
p
ath
is
f
o
u
n
d
b
et
wee
n
th
e
p
o
i
n
ts
(
5
;5
)
a
n
d
(
9
0
;
9
0
)
in
t
h
e
1
0
0
×
1
0
0
s
tate
s
p
ac
e:
(
a)
th
e
n
u
m
b
er
of
o
b
s
tacle
s
is
512
u
s
in
g
th
e
p
ar
a
llel
RRT
alg
o
r
ith
m
,
(
b
)
th
e
n
u
m
b
er
of
o
b
s
tacle
s
is
128
u
s
in
g
th
e
s
eq
u
en
tial
RRT
alg
o
r
ith
m
on
th
e
C
PU
Evaluation Warning : The document was created with Spire.PDF for Python.
I
SS
N
:
2
2
5
2
-
8
9
3
8
I
n
t J Ar
tif
I
n
tell
,
Vo
l.
14
,
No
.
1
,
Feb
r
u
ar
y
2
0
2
5
:
712
-
7
2
3
720
T
ab
le
1.
T
im
e
of
ex
e
cu
tio
n
of
s
eq
u
en
tial
an
d
p
a
r
allel
RRT
al
g
o
r
ith
m
s
in
a
s
tate
s
p
ac
e
of
s
ize
100
×
1
0
0
in
s
ec
o
n
d
s
f
o
r
p
o
in
ts
(
5
;5
)
an
d
(
9
0
;9
0
)
N
u
mb
e
r
of
o
b
s
t
a
c
l
e
s
S
e
q
u
e
n
t
i
a
l
(
C
P
U
)
P
a
r
a
l
l
e
l
N
V
I
D
I
A
G
e
F
o
r
c
e
R
TX
2
0
7
0
N
V
I
D
I
A
T4
G
P
U
2
5
6
4
.
4
4
8
9
8
4
1
4
6
1
1
8
7
.
9
8
6
0
4
9
4
1
3
6
5
.
2
9
8
4
1
7
8
0
6
6
5
1
2
8
.
5
1
6
0
9
6
1
1
5
1
1
2
1
2
.
8
6
0
9
8
2
4
1
8
0
8
.
9
1
5
8
0
2
2
4
0
3
1
,
0
2
4
1
2
8
.
2
2
8
5
5
5
9
1
7
7
8
5
.
5
7
4
7
6
2
8
2
1
1
7
6
.
2
8
0
8
2
3
7
0
7
6
2
,
0
4
8
1
2
2
.
1
1
1
3
4
8
1
5
2
1
7
4
.
0
7
2
2
5
0
1
2
7
7
6
6
.
9
1
7
2
1
4
8
7
0
5
4
,
0
9
6
2
4
1
.
3
4
1
8
3
0
0
1
5
1
7
4
.
8
0
2
2
3
2
9
8
0
7
6
8
.
6
1
1
8
6
3
6
1
3
1
8
,
1
9
2
4
6
8
.
4
6
6
1
8
6
0
4
6
6
7
6
.
2
2
3
2
4
6
5
7
4
4
7
7
.
3
1
6
7
1
0
4
7
2
1
T
ab
le
2
.
T
h
e
ex
ec
u
tio
n
tim
e
o
f
th
e
s
eq
u
en
tial a
n
d
p
ar
allel
R
R
T
alg
o
r
ith
m
s
in
a
2
0
0
×
2
0
0
s
tate
s
p
ac
e
in
s
ec
o
n
d
s
f
o
r
p
o
in
ts
(
1
5
;2
0
)
an
d
(
1
8
5
;
1
9
0
)
N
u
mb
e
r
o
f
o
b
s
t
a
c
l
e
s
S
e
q
u
e
n
t
i
a
l
(
C
P
U
)
P
a
r
a
l
l
e
l
N
V
I
D
I
A
G
e
F
o
r
c
e
R
TX
2
0
7
0
N
V
I
D
I
A
T4
G
P
U
2
5
6
4
3
.
2
4
9
9
8
7
8
4
0
6
3
4
.
6
4
2
3
0
9
1
8
8
8
1
5
.
5
7
8
4
7
5
2
3
6
8
5
1
2
4
2
.
1
3
3
6
4
2
9
1
1
9
3
1
.
8
5
2
3
6
0
7
2
5
4
3
0
.
4
3
0
5
6
7
2
6
4
6
1
,
0
2
4
1
7
6
.
3
1
2
6
4
8
2
9
6
3
7
4
.
0
9
9
0
2
4
0
5
7
3
7
4
.
7
4
9
5
6
7
0
3
1
9
2
,
0
4
8
2
9
9
.
9
1
2
0
7
7
9
0
3
7
7
6
.
4
6
6
8
0
6
9
8
3
9
7
5
.
3
7
7
1
8
5
9
1
6
9
4
,
0
9
6
5
5
5
.
5
0
3
5
3
7
6
5
4
8
7
6
.
6
1
2
1
4
9
9
5
3
8
7
5
.
6
1
2
1
4
9
9
5
3
8
8
,
1
9
2
9
8
4
.
0
2
3
2
7
2
0
3
7
5
7
6
.
8
0
1
2
4
9
2
6
5
6
7
5
.
8
8
0
6
9
8
3
9
4
7
Fig
u
r
e
2.
R
u
n
n
in
g
tim
e
of
s
eq
u
en
tial
an
d
p
ar
allel
RRT
alg
o
r
ith
m
s
in
a
s
tate
s
p
ac
e
of
s
ize
1
0
0
×
1
0
0
f
o
r
p
o
i
n
ts
(
5
;5
)
a
n
d
(
9
0
;9
0
)
Fig
u
r
e
3.
T
im
e
of
e
x
ec
u
tio
n
of
s
eq
u
en
tial
an
d
p
ar
allel
RRT
alg
o
r
ith
m
s
in
a
s
tate
s
p
ac
e
of
s
i
ze
200
×
200
in
s
ec
o
n
d
s
f
o
r
p
o
in
ts
(
1
5
;
2
0
)
an
d
(
1
8
5
;
1
9
0
)
0
100
200
300
400
500
256
512
102
4
204
8
409
6
819
2
E
xe
c
ut
i
o
n
t
i
m
e
,
se
c
o
nd
s
N
um
be
r
o
f
o
bs
t
ac
l
e
s
C
P
U
N
VIDI
A
G
e
F
o
r
c
e
R
T
X
2070
N
VIDI
A
T
4
G
P
U
0
200
400
600
800
100
0
120
0
256
512
102
4
204
8
409
6
819
2
E
xe
c
ut
i
o
n
t
i
m
e
,
se
c
o
nd
s
N
u
m
b
e
r
o
f
o
b
s
t
ac
l
e
s
C
P
U
NVI
DI
A
G
eFor
c
e
RT
X
20
7
0
N
VIDI
A
T
4
G
P
U
Evaluation Warning : The document was created with Spire.PDF for Python.
I
n
t J Ar
tif
I
n
tell
I
SS
N:
2252
-
8
9
3
8
P
a
r
a
llel ra
p
id
ly
ex
p
lo
r
in
g
r
a
n
d
o
m
tr
ee
meth
o
d
fo
r
u
n
ma
n
n
e
d
a
eria
l v
eh
icles
…
(
Les
ia
Mo
ch
u
r
a
d
)
721
T
ab
le
3
.
Par
allel
ac
ce
ler
atio
n
o
f
th
e
R
R
T
alg
o
r
ith
m
b
ased
o
n
m
ea
s
u
r
ed
d
ata
in
a
1
0
0
×
1
0
0
s
tate
s
p
ac
e
in
s
ec
o
n
d
s
f
o
r
p
o
in
ts
(
5
;5
)
an
d
(
9
0
;9
0
)
N
u
mb
e
r
o
f
o
b
s
t
a
c
l
e
s
N
V
I
D
I
A
G
e
F
o
r
c
e
R
TX
2
0
7
0
N
V
I
D
I
A
T4
G
P
U
2
5
6
0
.
5
5
7
0
9
4
0
.
8
3
9
6
8
2
5
1
2
0
.
6
6
2
1
6
5
0
.
9
5
5
1
6
9
1
,
0
2
4
1
.
4
9
8
4
3
8
1
.
6
8
1
0
0
6
2
,
0
4
8
1
.
6
4
8
5
4
3
1
.
8
2
4
8
1
2
4
,
0
9
6
3
.
2
2
6
3
9
8
3
.
5
1
7
4
9
4
8
,
1
9
2
6
.
1
4
5
9
7
5
6
.
0
5
9
0
5
5
T
ab
le
4.
Par
allel
ac
ce
ler
atio
n
of
th
e
RRT
alg
o
r
ith
m
b
ased
on
m
ea
s
u
r
ed
d
ata
in
a
200
×
200
s
tate
s
p
ac
e
in
s
ec
o
n
d
s
f
o
r
p
o
in
ts
(
1
5
;2
0
)
an
d
(
1
8
5
;
1
9
0
)
N
u
mb
e
r
of
o
b
s
t
a
c
l
e
s
N
V
I
D
I
A
G
e
F
o
r
c
e
R
TX
2
0
7
0
N
V
I
D
I
A
T4
G
P
U
2
5
6
1
.
2
4
8
4
7
3
2
.
7
7
6
2
6
6
5
1
2
1
.
3
2
2
7
7
9
1
.
3
8
4
5
8
3
1
,
0
2
4
2
.
3
7
9
4
1
9
2
.
3
5
8
7
1
1
2
,
0
4
8
3
.
9
2
2
1
2
1
3
.
9
7
8
8
1
8
4
,
0
9
6
7
.
2
5
0
8
5
4
7
.
3
4
6
7
5
2
C
o
m
p
ar
in
g
o
u
r
r
esu
lts
with
t
h
o
s
e
o
f
o
t
h
er
r
esear
ch
er
s
,
th
e
au
th
o
r
s
o
f
ar
ticles
[
3
4
]
,
[
3
5
]
,
wh
o
u
s
ed
C
PU
s
f
o
r
p
ar
alleliza
tio
n
,
we
ca
n
s
ay
th
at
we
h
av
e
ac
h
iev
ed
a
b
etter
r
esu
lt
th
an
th
ey
d
id
an
d
,
with
a
lar
g
e
n
u
m
b
er
o
f
o
b
s
tacle
s
,
o
u
r
s
p
ee
d
u
p
r
ates
ar
e
m
u
ch
h
ig
h
er
th
a
n
th
o
s
e
o
f
th
e
au
th
o
r
s
(
6
.
1
4
5
9
7
5
2
3
9
(
T
ab
le
2
)
o
f
p
ea
k
s
p
ee
d
u
p
v
e
r
s
u
s
3
.
5
1
2
[
3
4
]
an
d
4
.
1
2
3
[
3
5
]
f
o
r
a
1
0
0
×1
0
0
s
p
ac
e,
th
e
au
th
o
r
s
o
f
th
e
ar
t
icles d
o
n
o
t p
r
o
v
id
e
r
esu
lts
f
o
r
lar
g
er
s
p
ac
es).
W
e
also
co
n
d
u
cted
a
n
ex
p
er
im
e
n
t
al
co
m
p
ar
is
o
n
o
f
two
NVI
DI
A
G
PUs
:
R
T
X
2
0
7
0
an
d
T
4
.
B
o
th
g
r
ap
h
ics
ca
r
d
s
wer
e
in
tr
o
d
u
ce
d
in
2
0
1
8
,
s
o
we
co
n
s
id
er
th
eir
c
o
m
p
ar
is
o
n
to
b
e
ap
p
r
o
p
r
iate.
As
y
o
u
ca
n
s
ee
f
r
o
m
Fig
u
r
es
2
an
d
3
an
d
T
a
b
les 2
an
d
4
,
th
e
ac
ce
ler
atio
n
r
ates o
f
th
e
T
4
ar
e
s
lig
h
tly
h
ig
h
er
,
ev
en
th
o
u
g
h
th
e
p
o
wer
o
f
th
e
R
T
X
2
0
7
0
is
h
ig
h
er
.
T
h
is
is
b
ec
au
s
e
th
e
T
4
v
id
e
o
ca
r
d
was
cr
ea
ted
s
p
ec
if
ically
f
o
r
p
er
f
o
r
m
in
g
s
u
ch
task
s
,
f
o
r
wh
i
ch
it r
ec
eiv
ed
a
la
r
g
e
am
o
u
n
t
o
f
v
id
e
o
m
em
o
r
y
(
1
6
GB
)
.
5.
CO
NCLU
SI
O
N
I
n
co
n
clu
s
io
n
,
th
is
p
ap
er
ad
d
r
e
s
s
ed
th
e
p
r
o
b
lem
o
f
UAV
p
ath
f
in
d
in
g
,
f
o
cu
s
in
g
o
n
o
b
s
tacle
av
o
id
an
ce
an
d
tr
ajec
to
r
y
p
la
n
n
in
g
in
u
n
k
n
o
wn
en
v
ir
o
n
m
en
ts
.
W
e
im
p
lem
en
ted
th
e
R
R
T
alg
o
r
ith
m
an
d
im
p
r
o
v
ed
its
p
er
f
o
r
m
an
ce
t
h
r
o
u
g
h
p
ar
allel
izatio
n
u
s
in
g
C
UDA
o
n
GP
Us,
r
esu
ltin
g
in
s
ig
n
if
ican
tly
b
etter
e
f
f
icien
cy
co
m
p
ar
ed
to
a
C
PU
-
b
ased
ap
p
r
o
ac
h
.
T
h
e
p
a
r
allel
alg
o
r
ith
m
s
u
cc
ess
f
u
lly
av
o
id
ed
all
o
b
s
tacle
s
,
co
n
f
ir
m
in
g
th
e
ef
f
ec
tiv
en
ess
o
f
th
e
m
eth
o
d
.
T
h
is
ap
p
r
o
ac
h
en
ab
les
UAVs
to
n
av
ig
ate
co
m
p
lex
s
p
ac
es
with
o
u
t
r
eq
u
ir
in
g
p
r
ec
is
e
en
v
ir
o
n
m
en
tal
d
ata,
m
ak
in
g
i
t
s
u
itab
le
f
o
r
ch
allen
g
in
g
co
n
d
itio
n
s
s
u
ch
as
f
o
r
ests
o
r
i
n
d
o
o
r
s
p
ac
es.
Fu
tu
r
e
r
esear
ch
s
h
o
u
ld
f
o
cu
s
o
n
in
t
eg
r
atin
g
ad
d
itio
n
al
alg
o
r
ith
m
s
to
en
h
an
ce
th
e
o
v
er
all
p
er
f
o
r
m
an
ce
o
f
UAV
au
to
p
ilo
t sy
s
tem
s
an
d
f
u
r
th
er
ex
p
an
d
th
eir
ap
p
licatio
n
p
o
ten
tial.
ACK
NO
WL
E
DG
E
M
E
NT
S
T
h
is
wo
r
k
is
f
u
n
d
ed
by
th
e
E
u
r
o
p
ea
n
Un
io
n
’
s
Ho
r
iz
o
n
E
u
r
o
p
e
r
esear
ch
an
d
in
n
o
v
atio
n
p
r
o
g
r
a
m
u
n
d
er
g
r
a
n
t
a
g
r
ee
m
en
t
No
1
0
1
1
3
8
6
7
8
,
p
r
o
ject
Z
E
B
AI
(
I
n
n
o
v
ativ
e
m
eth
o
d
o
l
o
g
ies
f
o
r
th
e
d
esig
n
of
Z
er
o
-
E
m
is
s
io
n
an
d
c
o
s
t
-
ef
f
ec
tiv
e
B
u
ild
in
g
s
en
h
an
ce
d
by
Ar
tific
ial
I
n
tellig
en
ce
)
.
T
h
is
wo
r
k
w
as
s
u
p
p
o
r
ted
by
th
e
Slo
v
ak
R
esear
ch
an
d
Dev
el
o
p
m
en
t
Ag
en
cy
u
n
d
er
th
e
c
o
n
tr
a
ct
No
.
APVV
19
-
0
5
8
1
.
RE
F
E
R
E
NC
E
S
[
1
]
S
.
C
h
i
o
d
o
,
“
H
u
m
a
n
a
u
t
o
n
o
my
,
t
e
c
h
n
o
l
o
g
i
c
a
l
a
u
t
o
m
a
t
i
o
n
(
a
n
d
r
e
v
e
r
se),”
AI
a
n
d
S
o
c
i
e
t
y
,
v
o
l
.
3
7
,
n
o
.
1
,
p
p
.
3
9
–
4
8
,
2
0
2
2
,
d
o
i
:
1
0
.
1
0
0
7
/
s
0
0
1
4
6
-
0
2
1
-
0
1
1
4
9
-
5.
[
2
]
J.
A
.
J.
A
l
sa
y
a
y
d
e
h
e
t
a
l
.
,
“
D
e
v
e
l
o
p
m
e
n
t
o
f
p
r
o
g
r
a
m
ma
b
l
e
h
o
m
e
se
c
u
r
i
t
y
u
si
n
g
G
S
M
sy
s
t
e
m
f
o
r
e
a
r
l
y
p
r
e
v
e
n
t
i
o
n
,
”
AR
PN
J
o
u
r
n
a
l
o
f
En
g
i
n
e
e
r
i
n
g
a
n
d
Ap
p
l
i
e
d
S
c
i
e
n
c
e
s
,
v
o
l
.
1
6
,
n
o
.
1
,
p
p
.
8
8
–
9
7
,
2
0
2
1
.
[
3
]
K
.
N
.
M
a
a
n
y
u
,
D
.
G
.
R
a
j
,
R
.
V
.
K
r
i
s
h
n
a
,
a
n
d
S
.
B
.
C
h
o
u
b
e
y
,
“
A
s
t
u
d
y
o
n
T
e
sl
a
a
u
t
o
p
i
l
o
t
,
”
I
ssu
e
,
v
o
l
.
1
7
1
,
n
o
.
1
7
1
,
2
0
2
0
.
[
4
]
M
.
A
.
A
l
N
o
ma
n
e
t
a
l
.
,
“
A
c
o
m
p
u
t
e
r
v
i
s
i
o
n
-
b
a
se
d
l
a
n
e
d
e
t
e
c
t
i
o
n
t
e
c
h
n
i
q
u
e
u
s
i
n
g
g
r
a
d
i
e
n
t
t
h
r
e
s
h
o
l
d
a
n
d
h
u
e
-
l
i
g
h
t
n
e
ss
-
sa
t
u
r
a
t
i
o
n
v
a
l
u
e
f
o
r
a
n
a
u
t
o
n
o
mo
u
s
v
e
h
i
c
l
e
,
”
I
n
t
e
rn
a
t
i
o
n
a
l
J
o
u
r
n
a
l
o
f
El
e
c
t
ri
c
a
l
a
n
d
C
o
m
p
u
t
e
r
En
g
i
n
e
e
r
i
n
g
,
v
o
l
.
1
3
,
n
o
.
1
,
p
p
.
3
4
7
–
3
5
7
,
2
0
2
3
,
d
o
i
:
1
0
.
1
1
5
9
1
/
i
j
e
c
e
.
v
1
3
i
1
.
p
p
3
4
7
-
3
5
7
.
[
5
]
S
.
A
b
d
u
l
-
K
h
a
l
i
l
,
S
.
A
b
d
u
l
-
R
a
h
m
a
n
,
S
.
M
u
t
a
l
i
b
,
S
.
I
.
K
a
m
a
r
u
d
i
n
,
a
n
d
S
.
S
.
K
a
mar
u
d
d
i
n
,
“
A
r
e
v
i
e
w
o
n
o
b
j
e
c
t
d
e
t
e
c
t
i
o
n
f
o
r
a
u
t
o
n
o
mo
u
s
m
o
b
i
l
e
r
o
b
o
t
,
”
I
A
ES
I
n
t
e
r
n
a
t
i
o
n
a
l
J
o
u
rn
a
l
o
f
Ar
t
i
f
i
c
i
a
l
I
n
t
e
l
l
i
g
e
n
c
e
,
v
o
l
.
1
2
,
n
o
.
3
,
p
p
.
1
0
3
3
–
1
0
4
3
,
2
0
2
3
,
d
o
i
:
1
0
.
1
1
5
9
1
/
i
j
a
i
.
v
1
2
.
i
3
.
p
p
1
0
3
3
-
1
0
4
3
.
[
6
]
A
.
Jad
h
a
v
,
S
.
K
.
S
h
a
n
d
i
l
y
a
,
I
.
I
z
o
n
i
n
,
a
n
d
R
.
M
u
z
y
k
a
,
“
M
u
l
t
i
-
s
t
e
p
d
y
n
a
m
i
c
e
n
s
e
mb
l
e
s
e
l
e
c
t
i
o
n
t
o
e
s
t
i
mat
e
s
o
f
t
w
a
r
e
e
f
f
o
r
t
,
”
Ap
p
l
i
e
d
Art
i
f
i
c
i
a
l
I
n
t
e
l
l
i
g
e
n
c
e
,
v
o
l
.
3
8
,
n
o
.
1
,
2
0
2
4
,
d
o
i
:
1
0
.
1
0
8
0
/
0
8
8
3
9
5
1
4
.
2
0
2
4
.
2
3
5
1
7
1
8
.
[
7
]
M
.
P
.
A
.
F
.
K
i
k
i
,
S
.
A
.
R
.
M
.
A
h
o
u
a
n
d
j
i
n
o
u
,
K
.
M
.
A
ss
o
g
b
a
,
a
n
d
T.
S
u
t
i
k
n
o
,
“
B
i
b
l
i
o
me
t
r
i
c
a
n
a
l
y
si
s
a
n
d
s
u
r
v
e
y
o
n
e
l
e
c
t
r
o
n
i
c
n
o
se
u
se
d
i
n
a
g
r
i
c
u
l
t
u
r
e
,
”
I
n
t
e
r
n
a
t
i
o
n
a
l
J
o
u
rn
a
l
o
f
El
e
c
t
ri
c
a
l
a
n
d
C
o
m
p
u
t
e
r
E
n
g
i
n
e
e
ri
n
g
,
v
o
l
.
1
4
,
n
o
.
2
,
p
p
.
1
3
6
9
–
1
3
8
1
,
2
0
2
4
,
d
o
i
:
1
0
.
1
1
5
9
1
/
i
j
e
c
e
.
v
1
4
i
2
.
p
p
1
3
6
9
-
1
3
8
1
.
Evaluation Warning : The document was created with Spire.PDF for Python.