JINT manusc ip No.
(will be inse ed by he edi o )
Applying on ie cells based explo a ion and Lazy The a*
pa h planning o e single g id-based wo ld ep esen a ion o
au onomous inspec ion o la ge 3D s uc u es wi h an UAS*
Ma ga ida Fa ia, I an Maza and An idio Vigu ia
Recei ed: da e / Accep ed: da e
Abs ac Ae ial obo s a e a p omising pla o m o pe o m au onomous inspec ion o in-
as uc u es. Fo his applica ion, he wo ld is a la ge and unknown space, equi ing ligh
da a s uc u es o s o e i s ep esen a ion while pe o ming au onomous explo a ion and pa h
planning o obs acle a oidance. In his pape , we combine on ie cells based explo a ion
wi h he Lazy The a* pa h planning algo i hm o e he same ligh spa se g id - he oc ee
implemen a ion o oc omap. Tes -d i en de elopmen has been adop ed o he so wa e im-
plemen a ion and he subsequen au oma ed es ing p ocess. These es s p o ided insigh
in o he amoun o i e a ions needed o gene a e a pa h wi h di e en oxel con igu a ions.
The esul s o syn he ic and eal da ase s a e analyzed ha ing as baseline a egula g id
wi h he same esolu ion as he maximum esolu ion o he oc ee. The numbe o i e a ions
needed o ind on ie cells o explo a ion was smalle in all cases by, a leas , one o de o
magni ude. Fo he Lazy The a* algo i hm he e was a educ ion in he numbe o i e a ions
needed o ind he solu ion in 75% o he cases. These educ ions can be explained bo h by
he exis en g ouping o egions wi h he same s a us and by he abili y o con ine inspec ion
o he known oxels o he oc ee.
Keywo ds S uc u e Inspec ion ·UAS Applica ions ·Pa h Planning ·Au onomous
Explo a ion
1 In oduc ion
The inc easing need o UAS usage o emo e o -sho e moni o ing ac i i ies has aised di -
e en challenges. The Eu opean S a egy o Ma ine and Ma i ime Resea ch s a es he need
*The i s au ho has been unded by he Eu opean Union´
s Ho izon 2020 esea ch and inno a ion p og amme
unde he Ma ie Sklodowska-Cu ie g an ag eemen No 64215 and he o he wo au ho s ecei ed unding
om he MULTIDRONE (H2020-ICT-731667) and AEROARMS (H2020-ICT-644271) Eu opean p ojec s
Ma ga ida Fa ia E-mail: [email p o ec ed] and An idio Vigu ia E-mail: [email p o ec ed]
Cen e o Ad anced Ae ospace Technologies, Calle Wilbu y O ille W igh , 19, 41300 La Rinconada,
Se illa, Spain
I an Maza E-mail: [email p o ec ed]
in he Robo ics, Vision and Con ol G oup, Uni e si y o Se ille, A da. de los Descub imien os s/n, 41092,
Se illa, Spain
This e sion o he a icle has been accep ed o publica ion, a e pee e iew and is subjec o Sp inge Na u e’s AM e ms o use, bu is no he Ve sion o Reco d and does no e lec pos -accep ance imp o emen s, o
any co ec ions. The Ve sion o Reco d is a ailable online a : h ps://doi.o g/10.1007/s10846-018-0798-4
2 Ma ga ida Fa ia, I an Maza and An idio Vigu ia
o p o ec he ulne able na u al en i onmen and ma ine esou ces sus ainably. The use o
UAS p o ides inc eased endu ance and lexibili y while educing en i onmen al impac , he
isk o human ope a o s and he o al cos o ope a ions. The wo k in his pape has been de-
eloped in he amewo k o he Ma ineUAS 1ini ia i e, a Eu opean Union unded doc o al
p og am which s a egically s eng hens esea ch aining on Unmanned Ae ial Sys ems o
Ma ine and Coas al Moni o ing.
Se e al cons ain s come wi h his ype o scena io. One such limi a ion is he la ge size
o he olume o be explo ed, as i can be seen in Fig. 1. The acili ies ha need inspec ion
a e se e al o de s o magni ude la ge han he size o he UAS. In some cases, he e is no
“a p io i” 3D a ailable map usable by he UAS o na iga ion pu poses. Pe o-s a ions and
windmill a ms a e examples o o sho e acili ies ha would bene i om egula sys ema ic
and au onomous inspec ion. Bo h ha e se e al s uc u al ea u es ha need o be examined
e ically, calling o a ull 3D explo a ion. Ano he cons ain is ime. The ope a ion mus
be done as as as possible since i may equi e he ac i i y o he acili y o be suspended.
Any ope a ion done o sho e is ex emely expensi e and has inhe en ly oughe con-
di ions. Enabling sys ema ic and au onomous inspec ion will shi o machines he wo k
a which hey excel: epe i ion wi hou de ia ion aking in o accoun many ac o s and pa-
ame e s. Addi ionally, by simpli ying inspec ions hey will ge done mo e o en. Sa e y
inc eases, as humans need o do less hands-on wo k and hey became less exposed o isky
si ua ions.
Fig. 1 Inspec ing unde his o sho e pe o-s a ion o e s an example o inspec ion ha canno ely on any
global posi ioning sys em localiza ion.
As i has been p e iously men ioned, his wo k is ocused on he au onomous explo a ion
and pa h planning le els o he UAS. Lowe le els such as he ajec o y gene a o and he
con olle will handle wi h empo al cons ain s o he mission and kinema ic and dynamic
limi a ions o he ehicle.
The o ien a ion o he mul i o o is no conside ed in ei he he explo a ion o he pa h
planning algo i hm. The eason why his impo an pa ame e can be dis ega ded is wo old.
A mo ion le el, he mul i o o can mo e in all di ec ions. A he senso le el, he e a e
a ailable senso s wi h a 360 ange, as is he case o o a ing LIDARs.
The i s s ep o achie e e icien au onomous explo a ion is o choose he p ope da a
s uc u e o wo ld ep esen a ion. The cha ac e is ics o eal-wo ld scena ios need o be
aken in o accoun as hey will s ain he memo y capaci y o he sys em. In eal-wo ld
1h p://ma ineuas.eu
Ti le Supp essed Due o Excessi e Leng h 3
en i onmen s, he ee space is usually g ouped. Pa icula ly in o sho e s uc u es, i is also
likely o occupy mos o he a ea. Also, he occupied space is o en clus e ed, like he pilla s
in an o sho e pla o m, he windmill’s owe o i s blades.
The cha ac e is ics o he ea u es used o au onomous na iga ion should also be aken
in o accoun . The d i ing goal o he UAS is o explo e a gi en olume. Many op ions a e
a ailable, bu his wo k is ocused on he classical and widely used on ie explo a ion
app oach.
This explo a ion has he ad an age o simplici y. By i s in eg a ing a simple algo i hm
we c ea e he possibili y o checking i s limi a ions o he pa icula applica ion expe imen-
ally. Ano he ad an age is ha allows o keep down he compu a ional load. A on ie cell
is a loca ion in he wo ld ep esen a ion map ha is explo ed and unoccupied bu has unex-
plo ed space in i s icini y. These places a e o pa icula in e es as hey yield he highes
in o ma ion gain.
Due bo h o he ocus on low memo y equi emen s and in o ma ion o ganiza ion, he
da a s uc u e selec ed will be he oc ee implemen a ion done in he oc omap [1] amewo k.
Techniques om so wa e de elopmen will be adop ed in he implemen a ion o enable
ep oducibili y. Namely es -d i en de elopmen , suppo ed by au oma ed uni es s. In his
me hodology, a uni es is i s designed o asse he implemen a ion o a ea u e. Then
he ea u e is de eloped un il he es is passed, a which poin ano he uni es is designed
o ano he ea u e. This p ocess con inues i e a i ely un il he ull desi ed unc ionali y is
achie ed. To e i y he esul o he algo i hm unde di e en ini ial condi ions his o m
o es ing will be used whene e possible. Fu he mo e, bo h algo i hms will be applied o
simula ed and expe imen al da a.
This pape ex ends p e ious wo k p esen ed in [2]. The no el y o his wo k elies on
he implemen a ion o bo h he on ie cells explo a ion algo i hm and he Lazy The a*
pa h planning algo i hm o e he same da a s uc u e o he ep esen a ion o he 3D en-
i onmen . This da a s uc u e can scale o la ge scena ios. No local educ ion o a egula
g id will be used a any poin . The on ie cell algo i hm was chosen o i s simplici y. The
g oup o sui able pa h planning algo i hms is educed as his is a single que y p oblem. By
choosing an Any-angle pa h planning algo i hm he need o pos -p ocessing is signi ican ly
dec eased, and in pa icula , Lazy The a* is u he op imized o educe he numbe o line
o sigh checks. In addi ion, his algo i hm has been applied success ully in compe i ions
wi h au onomous mul i o o s [3].
The pape is o ganized as ollows. Sec ion 2 e iews ela ed wo k in da a s uc u es o
en i onmen ep esen a ion, explo a ion algo i hms and pa h planning echniques. Sec ion 3
epo s ele an aspec s o inding on ie cells on he di e en da a s uc u es unde anal-
ysis. Sec ion 4 desc ibes he challenges and solu ions adop ed o he implemen a ion, a
modi ica ion o he baseline algo i hm as well as he me hods chosen o de elop he code.
In Sec . 5, he esul s ob ained bo h wi h simula ed and expe imen al da a wi h each o he
algo i hms a e de ailed. Finally, sec ion 6 closes he pape wi h he conclusions and u u e
wo k.
2 Rela ed Wo k
This sec ion p esen s he da a s uc u es conside ed o s o ing he ep esen a ion o he
wo ld, s a e o he a algo i hms o au onomous explo a ion and pa h planning echniques
wi h pa icula a en ion o he suppo ing da a s uc u es.
s ill call i g id based a e adding isibili y g aphs and kd ees?
4 Ma ga ida Fa ia, I an Maza and An idio Vigu ia
2.1 E icien da a s uc u es o wo ld ep esen a ion
In his pape , se e al da a s uc u es ha e been analyzed, wi h a g ea e ocus on hose which
a e eadily a ailable as o he shel lib a ies. The amoun o da a ansla ed in o poin clouds
om mos senso s is excep ionally high. Thus, i is c ucial o iden i y da a s uc u es ha
mo e han jus comp ess da a, also a ange in o ma ion in an use ul and e icien manne .
One echnique o o ganize he in o ma ion is o c ea e meshes. A popula algo i hm is he
Delaunay iangula ion. Bo h PCL and CGAL [4] lib a ies p o ide implemen a ions ha
cons uc meshes om he poin s clouds. This echnique has he d awback o being depen-
den on he o de he poin s a e analyzed, in oducing one addi ional sou ce o a iabili y.
[5] o e comes his issue by c ea ing a mesh o he isibili y g aph, a ound ound obs acles,
showing he compu a ional ime ad an ages o cons uc ing isibili y g aphs o mul iple
que y cases. Visibili y g aphs simpli y he ask o sea ching o neighbo s by quan i ying
he ela ionship be ween samples acco ding o he adop ed me ic. In [6], a so wa e pack-
age o hei gene a ion is p esen ed. This package b ings in o Ma lab a ool o compu e
obs acle a oiding pa hs in a known wo ld.
Ano he op ion is o disc e ize he wo ld in o spaces o he same dimension. C ea ing a
egula g id can be done e en wi hou a dedica ed lib a y, in less elabo a ed cases. In hese
simple cases, andom access can ha e a complexi y o O(1). Any in o ma ion can be s o ed
pe cell, al hough wi h mo e in o ma ion comes inc eased memo y usage.
To make he sea ch mo e e icien , ees (wi h all hei mul i ude o implemen a ions
and a ia ions) a e ano he op ion. The kd- ees a e one op ion o he ep esen a ion o he
wo ld [7]. In his ep esen a ion, he sepa a ion o space is a e lexion o he opology o
he exis ing objec s esul ing in a ee ha p ecisely ma ches i . The PCL lib a y o e s one
implemen a ion in eg a ing he FLANN lib a y, whe e he kd- ee is used [8].
The oc ee is a la e ee compa ed o he bina y kd- ee due o i s eigh child en. The
opology is less closely e lec ed bu has he ad an age o a smalle hie a chical a e sal
o nodes when inding nodes in he neighbo hood. Two no able implemen a ions o his
s uc u e a e a ailable: he oc omap lib a y [9] and he PCL lib a y. The la e o e s se e al
s uc u es; his pape is ocused on Oc eePoin CloudOccupancy [10]. Bo h o e andom
access wi h O(1)complexi y and mul i esolu ion que ies. Howe e , hey di e in impo an
de ails. The PCL lib a y has a signi ican ocus on he comp ession needed o s eaming,
while he oc omap lib a y a ge s na iga ion and explo a ion. In he PCL lib a y, new mea-
su emen s a e added by summing poin s whe eas he oc omap lib a y in eg a es hem in a
p obabilis ic manne . The concep o unknown space is also sligh ly di e en in each imple-
men a ion. In he PCL lib a y, space is ei he occupied o ee. In he oc omap lib a y, only
loca ions wi h in o ma ion a e c ea ed hus implici ly encoding unknown space. Bo h PCL
and oc omap lib a ies conce n hemsel es wi h e iciency: he o me ocuses on ead/w i e
e iciency and o his eason, goes so a as o include a double bu e ed e sion o he s uc-
u e. In he la e , he ocus lies on memo y e iciency wi h (almos ) lossless comp ession
ega ding occupancy. Fo his eason, each node s o es only he occupancy p obabili y and
one child poin e - o ei ing oxel size, coo dina es, and he ull child en a ay.
2.2 Explo a ion
The concep o a on ie and a on ie cell epea edly appea s in he li e a u e wi h he same
basic idea. F on ie loca ions o cells a e poin s in he wo ld ep esen a ions ha sa is y wo
condi ions: hey a e in ee space and a e connec ed o unexplo ed space. Due o he ocus
Ti le Supp essed Due o Excessi e Leng h 5
on he unde lying da a s uc u es and wo ld ep esen a ion, each wo k will be analyzed wi h
hese aspec s in mind, keeping in sigh how o iden i y he loca ions ha yield he highe
in o ma ion gain.
Unmanned G ound Vehicles (UGVs) a e pa icula ly well sui ed o educe he sea ch
space o 2D, due o hei mo ion cons ain s. Many applica ions use p obabilis ic occupancy
g ids o ackle he ask o explo ing unknown (o pa ially unknown) spaces in a 2D sea ch
space. Re e ence [11] explains he concep o on ie cells o e a egula g id in he con ex
o p obabilis ic occupancy. This concep is no new, i was p esen ed in [12], bu due o
i s simplici y, i is s ill in use nowadays. In [13] an UGV is di ec ed o he nea es on ie
egion, lea ing he ask o pa h planning o a lowe le el o he a chi ec u e wi h pu ely
eac i e obs acle a oidance. In [14], an UGV also a els o he nea es unexplo ed cell bu
c ea es oadmaps, i.e., Vo onoi diag ams gene a ed om he occupancy g id.
Many app oaches [13,15–17] encode he s a us o he cells as ee, unknown and oc-
cupied ei he explici ly o by p obabili y h esholds. He e each cell encodes a somewha
di e en app oach o s a us: ee, wa ning, a el and a . In [18] his app oach is ex ended
o mul iple ehicles. Each on ie cell is sco ed acco ding o a heu is ic combina ion o
occupancy p obabili y and dis ance a eled. Wi h his combina ion, he pa h planning p ob-
lem is sol ed wi h he s eepes descen o he heu is ic unc ion. In [19] he concep o a
on ie is combined wi h a opological map: hese edges a e calcula ed as equidis an poin s
o obs acles, he obo hen a els his edges ma king hem as explo ed. The p ocess con-
inues o as long as he e a e unexplo ed edges. Re e ence [13] is an example o applying
his app oach o UAS by se ing a sa e al i ude. The on ie cells ound a his al i ude a e
hen clus e ed in o labeled egions, dis ega ding he small and inaccessible on ie s. The
emaining ones a e conside ed as goals o he UAS, inding he nex goal by applying a
ec o ield his og am.
In 3D space, he e a e some applica ions o p obabilis ic occupancy g ids o sol e he
nex bes iew p oblem o obo ic a ms. In [17], o dis inguish be ween unknown and un-
occupied cells a ay cas ing algo i hm is used o ex apola e ee egions om he senso
loca ion and occupied poin s. Holes in senso measu emen s a e ex apola ed wi h Ma ko
Random Fields. The on ie cells a e sco ed in eg a ing all his in o ma ion in o he gain o
be la e selec ed as bes iew. One example whe e he mission objec i es a e hea ily aken
in o accoun is [16]. F om he p obabilis ic g id, a mesh is c ea ed as a ool o ind oid
egions. Unknown cells a e se a he cen e o ellipsoids, which expand while main aining a
minimum i ing quali y. The ellipsoids a e hen combined wi h on ie s and sco ed acco d-
ing o neighbo ing oids. The heu is ic unc ion maximizes he in o ma ion gain aking in o
accoun he p io i y each egion has o he mission. Knowledge abou he a ea c i ical o
obs acle a oidance has he highes p io i y, ollowed by he egions a ec ed by he obo ’s
ools.
Ano he s uc u e used o 3D space is he oc ee, being i s mul i- esolu ion quali y one
o i s de ining cha ac e is ics. In [15] he lis o on ie cells is comp essed as clus e s wi h
an union- inding algo i hm. The unknown spaces a e handled as mac o- egions h ough el-
lipsoid expansion. Finally, he clus e s a e combined wi h he ellipsoids o sco e on ie s
acco ding o unknown egion dimension. Ano he pape using he oc ee as i s unde lying
s uc u e is [20]. Howe e , he con igu a ion space is sea ched employing a Rapidly Ex-
plo ing Random T ee, g own i e a i ely h ough sa e con igu a ions in he di ec ion o he
on ie . In [21] he in o ma ion o he known space is s o ed in a map s uc u e simila o an
ele a ion map, al hough o o he pu poses he associa ed poin cloud is s o ed in di e en
da a s uc u es. The sea ch o a eas wi h highe in o ma ion gain is done h ough sample
gene a ion, o add ess he issue o sea ch space explosion in 3D. F om a sample o known

6 Ma ga ida Fa ia, I an Maza and An idio Vigu ia
poin s o he en i onmen , o he poin s a e gene a ed and added o he pool. The model dy-
namics o he expansion o he molecules o a pe ec gas is used o gene a e hese poin s.
Then, change a e be ween pa icle expansions is e alua ed o ind on ie s in egions.
2.3 Pa h Planning
In he ield o mo ion planning, he p oblem o pa h planning has been ex ensi ely s udied.
Re e ence [7] p esen s di e en echniques wi hin sampling-based mo ion planning, upda -
ing he mo ion planning algo i hms p esen ed in classical e e ences such as [22,23].
To plan pa hs in 3D en i onmen s is complex and di e en me hods ha e been p oposed
o online and o line planning. A e conside ing he esou ce limi a ions (bo h ega ding
ime and o compu a ion) o an ae ial obo , wo app oaches s and ou as mos equen ly
used: de e minis ic and non-de e minis ic, each one encompassing se e al me hods. When
gene a ing pa hs wi h he de e minis ic app oach is common o use p obabili y as well as
sampling. Wi h he non-de e minis ic app oach, bo h heu is ic and g aph-based me hods a e
equen .
The cos o building a ully connec ed g aph is a good ade-o when sol ing a mul i-
que y p oblem. One op ion when in a single que y p oblem is o upda e he connec i i y o
he g aphs aking in o accoun he changes in he en i onmen . In [24] his implemen a ion
is made d ama ically educing he cos o ebuilding he isibili y g aph. Ano he gene al-
iza ion o he isibili y g aphs om 2D o 3D is ound in [25]. In his implemen a ion, he
isibili y g aph is composed o one obs acle g aph and wo suppo ing g aphs. This app oach
elies on a wo ld ha is p e iously known.
Sampling-based algo i hms like Rapidly-Explo ing Random T ees (RRT) [26], [27]
and P obabilis ic Rad Maps (PRM) [28], a e speci ically designed o handle non-holonomic
cons ain s (e.g., wheeled obo s), high deg ees o eedom and la ge spaces ha equi e be-
ing apidly and uni o mly explo ed. A ypical use case is a big manu ac u ing plan . Se e al
a ia ions o he RRT ha e been p oposed. RRT* [29] p oduces e y op imal pa hs a he
expense o eal- ime a es. RRT-Connec [30] esol es he ime issue, achie ing as e solu-
ions bu gene a ing longe pa hs. In [31], di e en p obabilis ic me hods a e used o sol e
he mo ion planning p oblem wi h UAVs. A con inuous- ime ajec o y op imiza ion me hod
is used o eal- ime collision a oidance on mul i o o UAVs.
The heu is ic algo i hms a e specially designed o ob ain he sho es pa h, explo ing
di ec ly om he ini ial s a e o he a ge s a e. Examples a e A* [32], The a* [33] and
D* [34]. These es ic he explo ed a eas and ge a un ime ha is highly con igu able and
dependen on he numbe o a iables and hei esolu ion. The usual d awback imposed
by disc e e sea ch echniques is ha pa hs a e o med by g id edges, so hey a e o en no
he sho es pa h in he con inuous space. Fo una ely, his issue was sol ed by he any-
angle pa h planning The a* and i s Lazy The a* a ia ion [35], which also op imizes he
compu a ional load o he algo i hm. One example o he applica ion o a g aph algo i hm
o a 3D sea ch space is [36]. He e a simula ed mic o-UAS ehicle goes om s a o goal
using an AD* sea ch algo i hm o eplanning. The unde lying wo ld ep esen a ion is a
3D occupancy g id ha is sampled whe e he samples a e a anged as a mul i-dimensional
la ice.
O he solu ions o gene a e 3D pa hs o ae ial ehicles ha e been p esen ed aking com-
ple ely di e en app oaches [37]. The e a e some examples o bio-inspi ed algo i hms using
neu al ne wo ks [38], e olu iona y algo i hms [39] [40]. O he s combine se e al algo-
i hms in one a chi ec u e o bene i om he s eng hs o each one [41], [42], [43].
Ti le Supp essed Due o Excessi e Leng h 7
This wo k analysis a solu ion ha needs a minimum amoun o wo ld ep esen a ions
and p ocessing powe compa ible wi h online planning on-boa d a mul i o o . The adop ed
wo ld ep esen a ion mus ha e a memo y oo p in small enough o s o e he ep esen a ion
o la ge s uc u es. Fo explo a ion, on ie cells will be used, whe eas o pa h planning
Lazy The a* is applied as i can be implemen ed di ec ly o e oc ees and has a smalle need
o pos -p ocessing. The oc omap implemen s oc ees wi h li le memo y oo p in while
o ganizing loca ion in o ma ion wi h s a es sui able o explo a ion.
3 Explo a ion Algo i hm based on F on ie Cells
In his sec ion, he ocus will be on he implemen a ion de ails o he explo a ion algo i hm.
I s pu pose is o iden i y poin s in he sea ch space ha will enable he collec ion o in o ma-
ion. The on ie cell algo i hm is used and elies hea ily on knowing he neighbo s o each
cell. I will be implemen ed o e wo di e en da a s uc u es: a egula g id and a spa se
g id.
A amewo k was c ea ed o assess he impac o he sea ch space explosion in 3D in
he di e en combina ions o da a s uc u es unde he same exac condi ions. Each da a
s uc u e needs o p o ide a unc ion ha e u ns i s neighbo s (ge Neighbo s) and a se o
unc ions o implemen i e a ion (ini I e a ion and endI e a ion). In Algo i hm 1 we can see
when hese gene ic unc ions a e called o abs ac om he wo ld ep esen a ion. The algo-
i hm sea ches o on ie cells om he ini ial i e a ion condi ion un il he end condi ion.
The e alua ion made o each cell selec s loca ions ha mee he ollowing equi emen s:
a e in known space, a e unoccupied and ha e a leas one neighbo ha is unexplo ed. The
dimension lexibili y (2D o 3D) is gi en by he bounding box se a he beginning o he
i e a ion and by adjus ing he di ec ions conside ed o he neighbo s. In all cases, he neigh-
bo s a e in adjacen cells. The diagonal neighbo s we e dis ega ded a e some p elimina y
es s since all he on ie egions we e iden i ied wi h and wi hou hem.
The algo i hms ha e been implemen ed in C++ using he Robo Ope a ing Sys em
(ROS) [44] as middlewa e. The open sou ce implemen a ion is eely a ailable in he o m
o a sel -con ained Robo Ope a ing Sys em (ROS) uni es s. I was eleased unde he MIT-
license and can be ob ained om he p ojec da aS uc u eAnalysis2. Mo e da a s uc u es
can be in eg a ed s aigh o wa dly, being he only equi emen o ha e he ou gene ic
unc ions: neighbo gene a ion, i e a ion ini ializa ion, iden i ica ion o he end condi ion
and p o ide he nex cell. They will be hen called in he manne shown in Algo i hm 1.
3.1 Regula G id
The egula g id makes a disc e iza ion o he con inuous space in o cells ha always ha e
he same dimensions. This classical app oach is equen ly s ill used due o i s simplici y.
The ull analysis o such a g id will always equi e a numbe o i e a ions gi en by mul-
iplying he leng h, wid h and heigh o he 3D space conside ed. This implemen a ion is
based on a simple egula inc emen o he coo dina es. The neighbo s a e always a he
same dis ance.
2h ps://gi hub.com/ma ga idaCF/da aS uc u eAnalysis
8 Ma ga ida Fa ia, I an Maza and An idio Vigu ia
Algo i hm 1 Gene ic p ocedu e o ind on ie cells, highligh ing how o make he abs ac-
ion among da a s uc u es wi h unc ions ini I e a ion, isExplo ed, isOccupied, ge Neigh-
bo s, and ge Nex Cell. Fo each cell i s , i is de e mined i he cell is explo ed and in ee
space. When hese equi emen s a e me , i s neighbo s a e e alua ed. I he e is a leas one
neighbo ha is in unknown space, he cell will be classi ied as a on ie .
Inpu : dimensions, a ia ion spec
Ou pu : on ie cells
1: cell = a ia ion spec.ini I e a ion(min,max)
2: while cell != a ia ion spec.endI e a ion() do
3: i isExplo ed(cell) && !isOccupied(cell) hen
4: on ie = alse
5: neighbo s = a ia ion spec.ge Neighbo s(dimensions)
6: o all neighbo s :ndo
7: i !isExplo ed(n) hen
8: on ie =isExplo ed(n)k on ie
9: end i
10: end o
11: i on ie hen
12: on ie cells.add(cell)
13: end i
14: end i
15: cell = a ia ion spec.ge Nex Cell()
16: end while
17: e u n on ie cells
3.2 Spa se G id
The spa se g id ex ends he concep o he egula g id by g ouping same alue egions. I s
ee-like app oach di ides he space in di e en sizes, c ea ing a high- esolu ion cell only o
accommoda e known poin s ex ac ed om he poin cloud.
In he oc omap implemen a ion, in o ma ion is added no only o de ec ed occupied
loca ions bu also o he ee space. The ee space is ex apola ed om he loca ions o
he senso and o he obs acle. Ano he use ul ea u e is he abili y o ans e se he g id
passing only h ough known lea s, skipping all unexplo ed cells. This is qui e con enien as
by de ini ion any unknown cell can ne e be a on ie cell.
The s a e o each loca ion is s o ed in log-odds no a ion o enable p obabilis ic usion o
each new poin cloud ga he ed by he on-boa d senso . The comp ession is nea ly lossless
and he e is only a imming o he maximum and minimum alues. Addi ionally, mac o-
egions wi h he same s a e will be analyzed only once. This will also educe he numbe o
cells ha need o be examined o ind on ie s, as he maximum size o each cell is always
lowe han he senso limi . I is he egula g id equi alen o analyzing se e al cells a he
same ime.
The algo i hm o ad ance o he nex lea loca ion is de ailed in [9]. To calcula e he
neighbo s, a simila algo i hm o egula g ids is applied, wi h one main di e ence: he
coo dina es o each cell e e o he cen e o he loca ion.
4 Lazy The a* Implemen a ion De ails
The wo ld ep esen a ion will be cons uc ed as he explo a ion de elops. Fo his eason,
he pa h planning p oblem is conside ed as a single que y one. Wi hin he se e al me hods
Ti le Supp essed Due o Excessi e Leng h 9
iden i ied as bes pe o ming in single que y p oblems, he Lazy The a* algo i hm was cho-
sen bo h because o he educed need o pos -p ocessing smoo hing and he educed amoun
o line o sigh checks needed. In pa icula , a a ia ion o he Lazy The a* algo i hm has
been implemen ed and es ed wi h mul i o o s a he EUROC [45] compe i ion showing i s
usabili y unde eal- ime condi ions and ealis ic cons ain s. The algo i hm is desc ibed in
[3] as a weigh ed heu is ics o op imize he sea ch space wi h an asymme ic olume, due
o senso es ic ions. One ele an aspec o he implemen a ion is he di e en app oaches
in he global planne and he local planne . The i s applies he concep o a egula g id
o access neighbo s o e an oc ee. The second also employs he idea o a egula g id bu
o e a poin cloud. He e he incoming poin cloud was e ined by emo ing he ou lie s and
in eg a ing he senso e o only a e mul iple con i ma ions. The local map was u he up-
da ed by elimina ing occupied poin s i no in o ma ion o hem was con inuously ecei ed.
Addi ionally, eplanning is used h oughou he mission o op imiza ion pu poses. Howe e
one o he iden i ied bo lenecks is eplanning o o e come la ge obs acles. This wo k ac s
as a ollow-up o he p omising esul s p esen ed in [3] o he eal- ime gene a ion o pa hs
wi h obs acle a oidance.
Ou implemen a ion o he Lazy The a* algo i hm akes a di e en app oach by di ec ly
implemen ing he algo i hm o e a 3D spa se g id ep esen a ion o he wo ld. Again, he
da a s uc u e used is he oc ee implemen a ion o he oc omap amewo k. Aiming o an
impo an educ ion o he memo y equi emen s, his will allow sha ing he same wo ld
ep esen a ion o explo a ion and pa h planning.
In his wo k, one o he challenges is o abandon he egula g id mindse en i ely o
ake ull ad an age o he spacial clus e ing wi h spa se g ids. The algo i hm has been im-
plemen ed in C++ unde he Robo Ope a ing Sys em (ROS) [44] as middlewa e. The open
sou ce implemen a ion is eely a ailable including he uni es s. I is eleased unde he
MIT-license and can be ob ained om he gi hub p ojec FlyingOc omap3. In he ollow-
ing he implemen a ion me hodology adop ed and he adap a ion o he algo i hm o use
Oc omap a e desc ibed.
4.1 So wa e Implemen a ion De ails
One ecu ing issue in obo ics esea ch is he di icul y o ga he ing he same condi ions
o e ime o ep oduce he same expe imen . The se up is no s aigh o wa d, so wa e
e sions change and he ha dwa e becomes una ailable. Some o hese issues ha e been
deal wi h in he a ea o so wa e de elopmen and can be mi iga ed wi h ools om ha
ield. The adop ion o so wa e de elopmen me hodologies, p ac ices and echniques is
s a ing o sp ead among he obo ics ield.
One example is he Eu opean p ojec RobMoSys. Some o i s key ocus is on simpli-
ying he se up and con igu a ion so wa e, p edic able and aceable p ope ies, ce i iable
sys ems, and be e compa abili y h ough app op ia e me ics (benchma king) [46]. Fo he
lexible gene al-pu pose modeling o sys ems, he Uni ied Modeling Language was aken as
e e ence [47].
Ano he example is he use o a ool ha appea ed in he las yea s as a esponse o
he con inuous in eg a ion o so wa e de elopmen s, especially in he web de elopmen
a ea. This ool is docke . I enables a p ecise accoun o all he so wa e packages necessa y
3h ps://gi hub.com/ma ga idaCF/FlyingOc omap
16 Ma ga ida Fa ia, I an Maza and An idio Vigu ia
Fig. 3 The UAS model used in simula ion wi h i s VLP-16 LIDAR in on .
he lowe pa o an o sho e pe o-s a ion. In his scena io, he g ound is ep esen ing he sea
le el and he loo o he s a ion is abo e he UAS - oo a o be sensed. F om hese wo lds
wo da ase s we e ex ac ed, one whe e he UAS inspec s wo pilla s and he second one
whe e he UAS inspec s h ee pilla s. The compa ison o wo in o ma ion s a es in he same
wo ld will b ing insigh in o he e ec o unknown space in he iden i ica ion o on ie
cells.
5.1.2 Analysis o he Resul s in he Simula ion En i onmen
In all he scena ios, bo h in 2D and 3D, he on ie egions a e oughly he same. This esul
is illus a ed in Fig. 5. In zoom A, wi h he egula g id, all he oxels quali ying o on ie
oxels a e iden i ies in black, gene a ing lines a ound he ee space. In zoom B his line
becomes do ed. The same posi ions a e classi ied as on ie oxels, bu hey a e now o
a iable size. When he image is analyzed aking in o conside a ion bo h he oxel cen e
and i s co esponding olume i is possible o see ha he iden i ied egions a e he same.
The same egions a e de ec ed, howe e he numbe o cells needed o ep esen hem is
smalle . This di e ence ends o be small using a LIDAR as he edge o he senso is o en
imes i egula due o he inc eased angula in e al be ween ays. Howe e , when in la ge
scena ios (as wo pilla s o h ee pilla s), i s a s o gain mo e ele ance. In addi ion, he
geome ical disposi ion o he oxels and how neighbo s a e compu ed explains his esul .
When a la ge explo ed oxel is adjacen o he same unknown oxel, i s whole olume is
conside ed a on ie . Howe e , in a egula g id, he added olume is always he size o he
g id esolu ion. Compu ed esul s a e shown in Fig. 2.
Fo each scena io ou combina ions a e un: a egula g id in 2D, a egula g id in 3D,
a spa se g id in 2D and a spa se g id in 3D. Only he po ion o he wo ld abo e he g ound
was conside ed, mo e accu a ely be ween ze o and one me e al i ude. This in e al was
chosen o s udy o make he compa isons wi h he 2D space wi hin he same magni ude.

Ti le Supp essed Due o Excessi e Leng h 17
Fig. 4 The di e en used scena ios in a 2D p ojec ion o he oc ee. The images p esen a 2D cu o he
wo ld by ixing he z-axis alue. The p ojec ion is gene a ed by ex ac ing he s a e o he oxel a a cons an
al i ude. I is shown he comple e a ea ha he oc ee could map (in he xand yaxes). The wo lds (and
espec i e abb e ia ions) a e he ollowing: (A) Z co ido , Z. (B) O sho e pe o-oil s uc u e, wo pilla s
sensed. 2 (C) Ci cula co ido , C. (D) Room, R. (E) Same s uc u e one addi ional pilla sensed, 3.
Table 2 F on ie ep esen a ion each simula ion da ase : oom, R; ci cula co ido , C; Z co ido , Z; o sho e
pe o-oil s uc u e, wo pilla s sensed, 2; same s uc u e one addi ional pilla sensed, 3. The uni s o space a e
m2and m3 o wo and h ee dimensions espec i ely.
2D 3D
S uc u e Regula Spa se Di e ence Regula Spa se Di e ence
RF on ie cells 236.0 221.0 15.0 50,903.0 47,460.0 3,443.0
Space 9.4 9.7 -0.2 407.1 407.0 0.1
CF on ie cells 137.0 110.0 27.0 5,729.0 1,951.0 3,778.0
Space 5.5 5.8 -0.4 45.8 22.8 23.1
ZF on ie cells 67.0 61.0 6.0 24,210.0 20,873.0 3,337.0
Space 2.7 2.9 -0.2 193.7 185.1 8.5
2F on ie cells 9,000.0 6,809.0 2,191.0 845,091.0 790,015.0 55,076.0
Space 360.0 386.2 -26.2 6,718.9 7,028.2 -309.3
3F on ie cells 28,627.0 21,724.0 6,903.0 1,273,737.0 1,156,968.0 116,769.0
Space 1,145.0 1,165.6 -20.7 10,067.7 11,047.3 -979.6
18 Ma ga ida Fa ia, I an Maza and An idio Vigu ia
(a)
Fig. 5 The on ie cells ound in he wo pilla scena io using he spa se g id da a s uc u e. (a) Shows he
esul s using he egula g id. (b) Shows he esul s using he spa se g id.
By compa ing he execu ion ime o each un depic ed in Fig. 6, i is clea ha he spa se
g id needs less ime o ind he on ie cells.
To analyze he compu a ional load o compiling he lis o on ie s posi ions le us look
in o he i e a ion coun and he amoun o space analyzed by he on ie algo i hm. In an
online a chi ec u e, hese calcula ions would be pe o med e e y ime signi ican al e a ions
a e done o he wo ld ep esen a ion. The numbe o i e a ions needed o p ocess he whole
s uc u e is always lowe in a spa se g id. Mo e speci ically, he numbe o i e a ions is one
o de o magni ude highe o egula g ids in he 2D case and wo o de s o magni ude
highe in he 3D case, as i can be seen in Fig. 7. The linea g ow h on a loga i hmic scale
shows he exponen ial p og ession o he i e a ions amoun . The g anula i y a o ded by he
hie a chical na u e o he s uc u e indeed p edisposes his sequence since he wo s case
scena io o he spa se g id is a egula g id. Howe e , he dispa i y o he esul s can no be
explained only by i s hie a chical na u e.
Ti le Supp essed Due o Excessi e Leng h 19
Fig. 6 Analysis o he in luence o he sea ch space explosion on he execu ion ime. Each scena io appea s
i s as 2D and hen as 3D, using a loga i hmic scale o bo h axis. The uni s o space a e m2and m3 o wo
and h ee dimensions espec i ely.
Fig. 7 A compa ison o he i e a ions amoun needed o ans e se he wo ld ep esen a ion o each o he
da a s uc u es, bo h in wo dimensions and h ee dimensions using a loga i hmic scale o he space axis. The
s a e o he g id ep esen ing he wo ld is d awn om he da ase s used o es ing.
Ano he ac o o be aken in o accoun is he numbe o unknown cells. As i can be
seen in Fig. 8, he unknown space is wha composes he as majo i y o he su eyed a ea
a ha momen , opening he possibili y o es ic ing he analyzed cells o he known cells.
The size o he space ep esen ed a ec s he numbe o i e a ions and he e o e he exe-
cu ion ime. The esul s o he scena ios wi h wo and ou pilla s e lec i . He e he wo ld is
exac ly he same - only he amoun o in o ma ion changes. Howe e , in he scena ios Room,
Co ido and Z, he inc ease in space does no co ela e o he i e a ions amoun o execu ion
ime. As he wo ld con igu a ion in each scena io changes d as ically, he dis ibu ion o he
sizes o he oxels gene a ion o i s ep esen a ion changes wi h i .
5.1.3 Expe imen al Da a
The algo i hms ha e been applied o a da ase cap u ed in a ligh done by he UAS shown in
Fig. 9, al hough in a mo e con ined space. The used au opillo was a Pixhawk ( i s e sion).
20 Ma ga ida Fa ia, I an Maza and An idio Vigu ia
Fig. 8 The amoun o space be ween unknown space du ing explo a ion is e y la ge, in any scena io, in
any dimension. This g aph is using a loga i hmic scale o he space axis. The s a e o he g id ep esen ing
he wo ld is d awn om he da ase s used o es ing. The uni s o space a e m2and m3 o wo and h ee
dimensions espec i ely.
Fig. 9 UAS pla o m used o da a acquisi ion. I was equipped wi h wo RGB-D came as Asus X ion P o
Li e, one acing o wa ds and ano he acing backwa ds.
Lazy The a* was un on an In el NUC wi h ROS indigo ins alled. Posi ioning was supplied
by a Vicon sys em ins alled in he es bed. I was equipped wi h wo RGB-D came as Asus
X ion P o Li e, one acing o wa ds and ano he acing backwa ds. The images cap u ed
by he came a we e hen combined and analyzed o gene a e he poin cloud. This da a was
eco ded in an indoo es bed wi h dimensions 15x15x5 me e s a he Cen e o Ad anced
Ae ospace Technologies (CATEC) loca ed in Se ille (Spain). Fig. 10 shows he poin cloud
cap u ed in he es bed.
5.1.4 Analysis o he Resul s wi h Expe imen al Da a
The da ase cap u ed in he eal scena io was analyzed using he same sou ce code (bo h
2D and 3D in each da a s uc u e). Again only he po ion o he wo ld abo e he g ound
be ween ze o and one me e al i ude was conside ed. The esul s a e consis en wi h he
ones obse ed wi h da ase s cap u ed in simula ion. Conce ning he execu ion ime, he oc-
ee keeps pe o ming signi ican ly be e as i can be seen in Fig. 11. Ano he measu e o
compu a ional load b ough in by on ie sea ch is he numbe o oxels inspec ed a each
Ti le Supp essed Due o Excessi e Leng h 21
Fig. 10 Poin cloud cap u ed in an indoo es bed wi h he UAS shown in Fig. 9 a he Cen e o Ad anced
Ae ospace Technologies (CATEC) loca ed in Se ille (Spain).
Fig. 11 Visual compa ison o execu ion ime be ween da a s uc u es and dimensions o he expe imen al
da ase . This g aphical po ay o he da a illus a es he magni ude o di e ence in execu ion imes be ween
he egula g id and he spa se g id. In he g aph a loga i hmic scale is used o he ime axis.
sweep o he wo ld ep esen a ion. In Fig. 12 again i can be seen he high p opo ion o
unknown cells which co obo a es he explana ion o he e iciency gain by he amoun o
skipped cells.
Ano he in e es ing esul e e s o he on ie space and he amoun o cells needed o
ep esen i . In Table 3, al hough he on ie space ep esen ed by he oc ee de ia es by
a ound 1.3 (squa e and cubic me e s espec i ely), i is educed he numbe o cells ha
ep esen i .
I is hypo hesized ha his is no a a ia ion ha will g ea ly impac he u he p ocess-
ing o he on ie cells o selec ing a goal, bu i is a educ ion none heless.

22 Ma ga ida Fa ia, I an Maza and An idio Vigu ia
Fig. 12 Rela ion be ween he o al amoun o cells, he cells i e a ed h ough wi h he spa se da a s uc u e
and a numbe o on ie cells ound. The numbe o unknown cells can be ex apola ed as he blue a ea since
he alues a e no s acked. In he g aph a loga i hmic scale is used o he e ical axis.
Table 3 F on ie ep esen a ion o he expe imen al da ase . The uni s o space a e m2and m3 o wo and
h ee dimensions espec i ely.
2D 3D
Regula Spa se Change Regula Spa se Change
Cells 1341 1067 274 10394 8652 1742
Space 13.4 12.0 1.4 10.4 11.7 -1.3
5.2 Lazy The a* Resul s
This sec ion desc ibes he da ase s used o he es s, he common poin s be ween bo h algo-
i hms, a s a is ical da a om he simple use case and he esul s o obs acle a oidance pa h
planning.
5.2.1 Da ase s
In he in e es o s anda diza ion, he da ase s used o es ing his implemen a ion o Lazy
The a* we e collec ed om he same wo lds as he ones used o es ing he on ie cells
algo i hm. Two da ase s a e he e analyzed: one collec ed om a simula ed wo ld and one
collec ed in an expe imen .
In ac , he da ase gene a ed om simula ion is one o he i e used wi h he on ie
cells algo i hms. Fo a g ea e olume o explo ed space, he inspec ion o 3 pilla s in a wo ld
ha emula es he lowe pa o an o sho e pe o-s a ion was selec ed. Fo mo e de ails, e e
o subsec ion 5.1.1 whe e he dimensions o he wo ld a e included in Table 5.1.1.
Rega ding he expe imen al da a, a new da ase is used. I was gene a ed in he same
es bed as he p e ious expe imen al da ase and wi h he same pla o m and senso s (see
Fig. 9). The e is one di e ence howe e , he da ase was collec ed a e a longe ligh and
a la ge amoun o known space. This ligh was one o he h ee in he e alua ion o phase
wo o he EUROC compe i ion [45].
Ti le Supp essed Due o Excessi e Leng h 23
Fig. 13 Spacial ep esen a ion o he cen e o he neighbo ing oxels gene a ed a an i e a ion o he Lazy
The a*. This amoun a ies acco ding o he size o he oxel analyzed. (a) P elimina y gene a ion assumes
all neighbo s ha e he minimum size. (b) This is hen upda ed o he ac ual size o he neighbo . (c) Bo h se s
o neighbo s jux aposed.
5.2.2 Neighbo s
In Lazy The a*, o each analyzed poin , i s neighbo s a e needed wice: i s o gene a e
waypoin candida es and hen o he inal alidi y upda e be o e adding o he g oup o
inspec ed poin s. The p ocess o gene a ing hese neighbo s is iden ical o he one used in
he on ie cells algo i hm. The diagonal neighbo s a e also disca ded and now he oxel
g ouping is exploi ed.
Fig. 13 shows he educ ion o neighbo s by compa ing he nai e gene a ion o a egula
g id and ha ing jus one poin pe oxel. In his case, he numbe o neighbo s is educed.
This is especially ob ious on he le and on sides o he oxel. In each case, he numbe o
neighbo s is educed om 64 o 1. This educ ion is na u ally dependen on he composi ion
o he oc ee: he uppe side changes om 64 o 4 and he bo om om 64 o 61.
An in ui ion eme ges: he ype o he e ain p esen in he scena io will dic a e how
much his si ua ion will occu . I solid la ge obs acles a e p esen (like a wall o example) i
will happen mo e. In se ings wi h small, de ailed objec s o con ined spaces i will happen
less.
5.2.3 S a is ical da a om ee pa hs
The simple use case o inding he pa h be ween wo poin s in ee known space is used o
ga he in o ma ion abou he numbe o i e a ions needed o ind a pa h. I is possible o do
his in an au oma ed way using he p e and pos condi ions desc ibed in Algo i hm 4.1.2.
A e inding and co ec ing all he cases ha did no pass his es , i can be used o pe -
o mance analysis. I is possible o assess he pe o mance change be ween he egula g id
and he oc ee by compa ing how many i e a ions a e used o ind a solu ion wi h he oc ee
and wi h he egula g id.
The baseline is de ined as he numbe o i e a ions needed using a egula g id wi h
pe ec heu is ics. In o he wo ds, he numbe o cells e alua ed i all he wo ld equi ed
maximum esolu ion oxels and he heu is ic always su aces he nex waypoin o he co -
ec solu ion.
Fi s he esul s a e p esen ed in Fig. 14. Fo all he uns, each amoun o i e a ions
used in a un is signaled below as a dash. The ba s abo e show he p obabili y o each one
happening. This iew p esen s bo h he clus e ing among he esul e en s and he epe i ion
o each esul . In bo h cases he mos equen amoun is a li le o e one- i h o he baseline.
24 Ma ga ida Fa ia, I an Maza and An idio Vigu ia
Fig. 14 The p obabili y ha a pa icula amoun o i e a ions is needed o ind a pa h in ee space, o each
o he amoun s. These esul s we e collec ed while sea ching he same oc ee, o wo di e en pa h leng hs.
The whole space is scanned o sui able poin s. Each s a and end poin uple is gi en o Lazy The a* o ind
he s aigh line pa h be ween he wo poin s. Each case consis s o a a ia ion o s a and/o goal. A - Fo
one-me e lines. B - Fo en-me e lines.
Howe e , he e is a much highe p obabili y o ha being exac ly he numbe o i e a ions
in pa hs 1 me e long.
A mo e p ac ical insigh is he p obabili y o he new implemen a ion ou pe o ming he
baseline, wi h any numbe o i e a ions. This obse a ion is wha is po ayed in Fig. 15. Fo
a mo e de ailed o e iew, he uns we e g ouped in o he ollowing g oups:
–Use hal he i e a ions o he baseline o less;
–Use be ween hal he i e a ions o he baseline, up o he same amoun ;
–Use exac ly he same amoun o i e a ions as he baseline;
–Use o e same i e a ions as he baseline up o double ha amoun ;
–Use mo e han double he numbe o i e a ions as he baseline.
Al hough o a pa h o 10 me e s he p obabili y o using p ecisely 13 i e a ions ( he mos
equen amoun ) is as low as 24%, by combining close occu ences i ge s much close o
he alues ound o he 1-me e pa hs. In bo h si ua ions, in a ound 75% o he cases, less
han hal he i e a ions a e needed.
5.2.4 Obs acle a oidance
To es he abili y o gene a e pa hs ha a oid obs acles, he expe imen al da ase used is
desc ibed in Sec . 5.2.1.
Fig. 16 shows an example o a pa h calcula ed by he implemen a ion o he Lazy The a*
o e he oc ee da a s uc u e. As i can be seen, he esul ing pa h a oids he many obs acles.
The scena io is composed by he a o emen ioned da ase , a s a poin and a goal ha a e 10
me e s apa bu ha e se e al obs acles be ween hem.
The esul ing pa h (in g een) does no c oss any obs acles. On he o he hand, he s a
and end poin s a e no he same in he inpu poin s (in blue) and in he esul ing pa h. A less
ob ious ea u e o he esul ing pa h is ha he dis ance kep om he obs acles is a iable.
Ti le Supp essed Due o Excessi e Leng h 25
(a) (b)
Fig. 15 Amoun o i e a ions used in he same oc ee, o wo di e en pa h leng hs o di e en composi ions
o oxel space. Each case consis s on a a ia ion o s a and/o goal. (a) Fo one me e lines. (b) Fo en me e
lines.
The o se be ween he s a and end o each line e lec s ha each poin is iden i ied
by he cen e o he oxel i is con ained by. Ano he consequence is he i egula dis ance
he pa h main ains om he obs acles. A he i s obs acle, he waypoin is e y close while
a he second obs acle he chosen waypoin is much u he away, c ea ing a s eep di e. A
he i s obs acle, he ee oxel is small while in he second obs acle i is much la ge . As
bo h a e pa o he ee space, his is no di ec ly obse able in he igu e bu is e i ied
nume ically. The e ec is obse able in he oxels ep esen ing he occupied space. As each
cube ep esen s he cen e o he oxels, i o en c ea es he illusion o holes in his ype o
isualiza ion. Examples a e he holes in he g ound o he le o he pa h and he loa ing
blocks in he middle o he solid shape in line wi h he i s obs acle.
6 Conclusions and Fu u e Wo k
In his pape , he impac o he unde lying da a s uc u e on p ocessing he wo ld ep esen-
a ion has been analyzed bo h o ind on ie cells o explo a ion and o gene a e pa hs ha
a oid obs acles. The ocused da a s uc u e is he implemen a ion o an oc ee done by he
oc omap amewo k.
In he con ex o he on ie cells, some cha ac e is ics eme ge as bene icial o e i-
ciency. The baseline used was a egula g id wi h he same esolu ion as he oc ee. The
numbe o i e a ions needed o ind on ie cells was smalle in all cases by, a leas , one
o de o magni ude. G ouping egions wi h he same s a us and skipping he unknown cells
explain hese esul s. The numbe o on ie cells is smalle o he spa se g id in all o he
da ase s while co e ing a simila amoun o space. This ac indica es ha hese cells be e