ERK'2022, Portorož, 242-245 242
Navigacija robota v zemljevidu kvadratnih celic s pomoˇ cjo
bilinearne interpolacije diskretnega potencialnega polja
Andrej Zdeˇ sar
1
, Matevˇ z Boˇ snak
1
, Rok Vrabiˇ c
2
, Gaˇ sper
ˇ
Skulj
2
, Gregor Klanˇ car
1
1
Univerza v Ljubljani, Fakulteta za elektrotehniko, Trˇ zaˇ ska cesta 25, 1000 Ljubljana, Slovenija
2
Univerza v Ljubljani, Fakulteta za strojniˇ stvo, Aˇ skerˇ ceva cesta 6, 1000 Ljubljana, Slovenija
E-poˇ sta: andrej.zdesar@fe.uni-lj.si
Robot navigation based on a grid map using
bilinear interpolation of a discrete potential
field
In this paper a smooth navigation function combining the
Dijkstra-based discrete static potential field with bilinear
interpolation is proposed. We present the necessary mod-
ifications of the bilinear interpolation method to make
it applicable to the path-planning application. The pro-
posed navigation strategy solves the problem of the local
minima and generates smooth paths with moderate com-
putational complexity. Results from several initial robot
configurations are presented to illustrate the advantages
of the developed navigation method.
1 Uvod
Glavni cilj planiranja poti je doloˇ citi izvedljive in varne
poti, ki se izognejo oviram in omogoˇ cajo voˇ znjo robota
od zaˇ cetne do ciljne konfiguracije [1]. To delo zdruˇ zuje
iskanje poti v grafu, ki je predstavljen z mreˇ zo celic, in
nadgradnjo umetnih potencialnih polj [2] za doloˇ citev
gladkih poti v prostem prostoru. Predlagani pristop uvaja
interpolacijo, ki doloˇ ci gladke poti tudi pri grobi loˇ cljivosti
diskretnega zemljevida.
Ravninski zemljevid okolja najpogosteje zapiˇ semo
z razcepom prostora na mreˇ zo kvadratnih celic, kjer je
prostorska kompleksnost odvisna predvsem od ˇ stevila ce-
lic. Celica mora biti dovolj majhna, da lahko zadovoljivo
opiˇ semo pomembne detajle okolja. Za iskanje moˇ znih poti
med zaˇ cetno in ciljno lokacijo se pogosto uporabljata algo-
ritma Dijkstra [3] in A* [4] ter njune ˇ stevilne nadgradnje,
kot je D*Lite [5] in podobno. Koncept umetnih ali navi-
deznih potencialnih polj za naˇ crtovanje poti do ˇ zelenega
cilja je bil prviˇ c predlagan v [2]. Priljubljenost pristopa je
posledica njegove intuitivne formulacije, njegova glavna
pomanjkljivost pa je prisotnost lokalnih minimumov, za
premagovanje katerih je bilo predlaganih veˇ c reˇ sitev.
V predlaganem pristopu zemljevid okolja predstavimo
z diskretno mreˇ zo (s prostimi in zasedenimi celicami),
ki jo uporabimo za doloˇ citev diskretnega potencialnega
polja. Z metodo bilinearne interpolacije doloˇ cimo zve-
zni gradient potencialnega polja, ki nam sluˇ zi za iskanje
optimalne poti s potovanjem v smeri padajoˇ cega gradi-
enta.
ˇ
Ceprav je bilinearna interpolacija znana metoda na
podroˇ cju digitalne obdelave slik, je ni moˇ c direktno upo-
rabiti za interpolacijo potencialnega polja in njegovega
gradienta pri naˇ crtovanju poti. V ˇ clanku predstavljamo
izboljˇ save, ki omogoˇ cajo obravnavo zasedenih celic (brez
definiranih vrednosti potencialnega polja) in interpolacijo
na mejah okolja ter zagotavljajo monotono padanje gra-
dienta potencialnega polja. Tako se pri iskanju poti ne
pojavljajo lokalni minimumi, ki so pogosti pri sploˇ snih
metodah, ki temeljijo na potencialnem polju. Pristop je
raˇ cunsko uˇ cinkovit, saj temelji na zemljevidu z diskre-
tnim potencialnim poljem, ki ga je za statiˇ cno okolje in
znane cilje mogoˇ ce izraˇ cunati vnaprej ter ga je mogoˇ ce
znova uporabiti, ˇ ce se bodisi cilj bodisi start ne spreme-
nita. Rezultat naˇ crtovanja je gladka zvezna pot v prostem
prostoru, ki je blizu optimalne, ˇ ceprav je lahko diskretna
predstavitev okolja precej groba.
2 Predstavitev problema
Za doloˇ cen cilj z Dijkstrovim algoritmom izraˇ cunamo
ceno do cilja za vsako prosto celico v mreˇ zi zemljevida.
Na sliki 1 so na primeru okolja s ˇ stirimi ovirami za vse
celice prikazane cene do ciljaG (ciljna celica ima ceno0,
zaˇ cetna celicaS pa10, 8).
0 2 4 6 8 10
0
1
2
3
4
5
6
7
8
9
10
11.8
11.3
10.8
10.3
9.78
9.57
9.36
9.16
8.95
8.74
8.54
8.62
8.12
7.91
7.71
7.5
7.71
7.91
11.3
11.1
10.6
10.1
9.57
9.07
8.86
8.66
8.45
8.24
8.04
8.24
7.91
7.41
7.21
7
7.21
7.41
10.8
10.6
10.4
9.86
9.36
8.86
8.36
8.16
7.95
7.74
7.54
7.74
7.71
7.21
6.71
6.5
6.71
6.91
10.3
10.1
9.86
7.66
7.45
7.24
7.04
6
6.21
6.41
9.78
9.57
9.36
7.45
6.95
6.74
6.54
5.5
5.71
5.91
9.57
9.07
8.86
7.24
6.74
6.24
6.04
5
5.21
5.41
9.36
8.86
8.36
7.04
6.54
6.04
5.54
4.5
4.71
4.91
9.16
8.66
8.16
7.66
7.45
7.24
7.04
6.83
6.33
5.83
5.33
4.83
4.62
4.41
4.21
4
4.21
4.41
8.95
8.45
7.95
7.45
6.95
6.74
6.54
6.33
6.12
5.62
5.12
4.62
4.12
3.91
3.71
3.5
3.71
3.91
8.74
8.24
7.74
7.24
6.74
6.24
6.04
5.83
5.62
5.41
4.91
4.41
3.91
3.41
3.21
3
3.21
3.41
8.54
8.04
7.54
7.04
6.54
6.04
5.54
5.33
5.12
4.91
4.71
4.21
3.71
3.21
2.71
2.5
2.71
2.91
8.62
8.24
7.74
4.83
4.62
4.41
4.21
2
2.21
2.41
8.12
7.91
7.71
4.62
4.12
3.91
3.71
1.5
1.71
1.91
7.91
7.41
7.21
4.41
3.91
3.41
3.21
1
1.21
1.41
7.71
7.21
6.71
4.21
3.71
3.21
2.71
0.5
0.707
1.21
7.5
7
6.5
6
5.5
5
4.5
4
3.5
3
2.5
2
1.5
1
0.5
0
0.5
1
7.71
7.21
6.71
6.21
5.71
5.21
4.71
4.21
3.71
3.21
2.71
2.21
1.71
1.21
0.707
0.5
0.707
1.21
7.91
7.41
6.91
6.41
5.91
5.41
4.91
4.41
3.91
3.41
2.91
2.41
1.91
1.41
1.21
1
1.21
1.41
Zglajena Dijkstrova pot 1
Zglajena Dijkstrova pot 2
Dubinsova pot (RRT)
Zglajena Dubinsova pot (RRT)
Pot s predlaganim pristopom
Slika 1: Primer zemljevida okolja z oznaˇ ceno lokacijo startaS
in ciljaG, cenami do cilja v prostih celicah (bele celice so proste,
sive so zasedene) in primeri nekaj razliˇ cnih poti medS inG
Na sliki 1 je optimalna diskretna pot med startom
S in ciljem G, ki jo dobimo z Dijkstrovim algoritmom,

243
oznaˇ cena s svetlo modrimi celicami. Gladko pot lahko do-
bimo tako, da ˇ cez centre celic, ki sestavljajo pot, napnemo
zlepek parametriˇ cnih krivulj (npr. B´ ezierjeve krivulje ali
klotoide). Na sliki 1 sta prikazani dve gladkih poti (zgla-
jena Dijkstrova pot 1 in 2), ki smo ju na ta naˇ cin dobili
s pomoˇ cja paketa Automated Driving Toolbox v okolju
Matlab. Na sliki 1 je prikazana tudi (zglajena) Dubinsova
pot, ki smo jo dobili z metodo hitro-rastoˇ cega nakljuˇ cnega
drevesa (RRT*) [6]. Omenjeni pristopi sami po sebi ne
zagotavljajo varnega poteka dobljenih gladkih poti mimo
ovir z dovolj velikim odmikom in brez trkov. V ta namen
je potrebno pri glajenju poti upoˇ stevati tudi omejitve, ki
trke prepreˇ cijo. Nekatere zglajene poti so lahko zelo osci-
latorne (z velikimi zavoji mimo ovir), lahko pa so dobljene
poti tudi neizvedljive, ˇ ce trˇ cijo ob ovire.
Slika 1 prikazuje tudi primer poti dobljen s predlaga-
nim pristopom. To je gladka pot, doloˇ cena na podlagi
interpoliranega gradienta potencialnega polja, ki implici-
tno upoˇ steva ovire. Predlagani pristop je deterministiˇ cen
in vraˇ ca gladke in skoraj optimalne poti, ki zagotavljajo
minimalno varno razdaljo do ovir. Pristop je tudi raˇ cunsko
uˇ cinkovit, saj daje zadovoljive rezultate, tudi ˇ ce je velikost
celic relativno velika.
3 Interpolacija in glajenje potencialov in
gradientov za naˇ crtovanje poti
Diskretizacija okolja je potreben korak za omejitev raˇ cunske
zahtevnosti kot tudi za poenostavitev upoˇ stevanja zasede-
nosti prostora z ovirami. Na diskretni mreˇ zi se vrednost
potencialnega polja (cena do cilja) izraˇ cuna za vsako ce-
lico. Loˇ cljivost doloˇ canja gradienta je tako omejena, kar
vpliva na gladkost navigacije. Za reˇ sitev tega problema
je uvedena izboljˇ sava z uporabo uveljavljenega pristopa
ponovnega vzorˇ cenja slike, znanega kot bilinearna inter-
polacija (BiLI) [7, 8]. Ta deluje na slikovnih elementih, ki
so v naˇ sem primeru celice.
3.1 Bilinearna interpolacija
Ideja delovanja metode BiLI je ponazorjena s pomoˇ cjo
slike 2 [8]. Z interpolacijo ustvarimo nove podatkovne
toˇ cke z uporabo linearnih funkcij, kar je v bistvu ravninska
razˇ siritev 1D linearne interpolacije. Interpolirana funk-
cija na osnovi zlepkov potrebuje ˇ stiri parametre, katerih
vrednosti je potrebno oceniti. V ta namen uporabimo
vrednosti potenciala na ogliˇ sˇ cih interpoliranega obmoˇ cja.
Glede na lokacijo toˇ cke [x,y ]
T
v celiciM je za in-
terpolacijo izbrano obmoˇ cje ˇ stirih sosednjih celic, katerih
srediˇ sˇ ca so povezana s ˇ crtkanim kvadratom na sliki 2.
Normirane koordinate so doloˇ cene s srediˇ sˇ ci teh celic kot:
x
n
=
x− x0
dc
, y
n
=
y− y0
dc
, kjer je [x
0
,y
0
] izhodiˇ sˇ ce normaliziranih koordinat, ki je
v spodnjem levem ogliˇ sˇ cu ˇ crtkanega kvadrata, d
c
pa je
velikost celice. Interpolirani in diskretni potencial v normi-
ranih koordinatah sta izraˇ zena kotP
n
(x
n
,y
n
) =P(x,y )
inU
n
(x
n
,y
n
) =U(x,y ). Potenciali ustreznih ˇ stirih sose-
dnjih centrov celic (ogliˇ sˇ ca ˇ crtkanega kvadrata na sliki 2)
so
p
cr
=U
n
(x
n
,y
n
)
    xn=c,y n=r
, (1)
kjer jec,r ∈{ 0, 1} inU
n
(x
n
,y
n
) =U(x,y ).
Interpolirani potencialU
n
(x
n
,y
n
) katerekoli normi-
rane lokacije[x
n
,y
n
)]
T
znotraj kvadranta celiceM, ome-
jene z enotskim kvadratom, je definiran kot [8]:
P
n
(x
n
,y
n
) =w
00
p
00
+w
01
p
01
+w
10
p
10
+w
11
p
11
, (2)
kjer so uteˇ zi BiLI doloˇ cene kot: w
00
= (1− x
n
)(1− y
n
),
w
01
= (1− x
n
)y
n
,w
10
=x
n
(1− y
n
) inw
11
=x
n
y
n
.
Slika 2: Interpolirani potencial v dani toˇ cki[x,y ]
T
je definiran
z diskretnim potencialom v srediˇ sˇ cih (ˇ crnih pikah) ˇ stirih celic,
povezanih s ˇ crtkanim kvadratom
ˇ
Ce sledimo negativnemu gradientu interpoliranega po-
tencialnega polja P(x,y ) = P
n
(x
n
,y
n
), lahko dobimo
varno pot od kjerkoli v okolju do ciljne lokacije (s potenci-
alom0). Negativni gradient potencialaP(x,y ) v[x,y ]
T
je mogoˇ ce dobiti kot:
g(x,y ) =−∇ P(x,y ) =
1
d
c
 p
00
− p
10
− Cy
n
p
00
− p
01
− Cx
n
 , (3)
kjer jeC =p
00
− p
01
− p
10
+p
11
.
3.2 Prilagoditve bilinearne interpolacije za namen
planiranja poti
Pred uporabo interpolacije z enaˇ cbo (2) moramo preveriti,
ˇ ce je katera od treh sosednjih celic, vkljuˇ cenih v inter-
polacijo celiceM (glej sliko 2), zasedena. CelicaM ni
nikoli zasedena, saj interpoliramo potencial v toˇ cki[x,y ]
T
znotraj nje. Za zasedene celice je potencial obiˇ cajno ne-
skonˇ cen ali nedefiniran, saj gibanje ˇ cez ovire proti cilju
ni moˇ zno ali dovoljeno. Potencial U(x
m
,y
m
) za zase-
deno celico s srediˇ sˇ cem pri(x
m
,y
m
) lahko doloˇ cimo iz
najveˇ cjega potenciala nezasedene celice v soseˇ sˇ cini osmih
celic:
(c,r ) = argmax
(i,j )
{ U(x
m
+d
c
i,y
m
+d
c
j)̸=∞} , U(x
m
,y
m
) =U(x
m
+d
c
c,y
m
+d
c
r)+d
c
√ c
2
+r
2
, kjeri,j ∈{− 1, 0, 1} .
Dodatno je potrebno preveriti ali je katera od ˇ stirih ce-
lic vkljuˇ cenih v interpolacijo (krajˇ se interpolacijska celica,

244
glej enaˇ cbo (2) in sliko 2) zunaj okolja. Preprosta reˇ sitev
za to bi lahko bila, da je obmoˇ cje mreˇ ze celic vsaj za eno
celico veˇ cje od obmoˇ cja, ki ga interpoliramo. Sploˇ snejˇ sa
reˇ sitev uporablja za izraˇ cun potenciala in gradienta bliˇ znjo
lokacijo [x
t
,y
t
]
T
, kjer so vse ˇ stiri interpolacijske celice
znotraj okolja. Za poloˇ zaj[x,y ]
T
, kjer je ena ali veˇ c inter-
polacijskih celic zunaj okolja, se bliˇ znja lokacija doloˇ ci s
translacijo poloˇ zaja z meje za
dc
2
v smerix in/aliy proti
notranjosti okolja, kot sledi:
x
t
=
   x ; x
min
≤ x≤ x
max
x
min
+
dc
2
; x<x
min
x
max
− dc
2
; x>x
max
, y
t
=
   y ; y
min
≤ y≤ y
max
y
min
+
dc
2
; y <y
min
y
max
− dc
2
; y >y
max
, kjer so meje okolja doloˇ cene zx
min
,x
max
,y
min
iny
max
.
Za premaknjeno bliˇ znjo lokacijo se interpolirani poten-
cialP(x
t
,y
t
) izraˇ cuna iz (2) in gradientg
t
(x
t
,y
t
) iz (3).
Konˇ cno se ustrezen potencial za vsako interpolacijsko
celico zunaj okolja (oznaˇ ceno kotP
∗ ) rekonstruira z upo-
rabo Liejevega odvoda (tudi smerni odvod):
P
∗ =P(x
t
,y
t
)+g
t
(x
t
,y
t
)× [x− x
t
,y − y
t
]
T
. (4)
Slika 3 prikazuje nastalo potencialno polje, prido-
bljeno z uporabo pristopa BiLI, ki ustreza okolju na sliki
1. Vidno je, kako se potencialno polje zvezno spuˇ sˇ ca
od zaˇ cetne do ciljne toˇ cke mimo ˇ stirih ovir, ki nimajo
doloˇ cenega potenciala. To izhaja iz dejstva, da vredno-
sti potenciala monotono padajo od katere koli celice v
okolju proti cilju. Dodatno je na sliki 4 z modro ˇ crto pri-
kazanih nekaj vzorˇ cnih poti, pridobljenih s sledenjem v
smeri negativnega gradienta (izraˇ cunan iz enaˇ cbe (3)) za
nekaj razliˇ cnih zaˇ cetnih lokacij proti cilju. Opazimo, da
so moˇ zne nezvezne spremembe smeri gradienta v bliˇ zini
zasedenih celic. Da bi nezveznosti smeri odpravili in do-
bili bolj gladke poti (kot je na sliki 4 prikazano z vijoliˇ cno
ˇ crto), v poglavju 3.3 dodatno predlagamo interpolacijo
gradienta.
3.3 Interpolacija gradienta
Dobljeni potencial na sliki 3 je zvezen, vendar je njegov
negativni gradient lahko nezvezen, zlasti v bliˇ zini ovir, kot
je razvidno s slike 4 na poti negativnega gradienta (modra
ˇ crta). Negativni gradient oznaˇ cuje zahtevano smer voˇ znje
za doseg cilja na optimalen naˇ cin. Vsaka nezveznost
gradienta je problematiˇ cna, saj bi se robot s kolesi moral
ustaviti in zavrteti na mestu, da bi lahko zanesljivo ˇ sel v
smeri parajoˇ cega gradienta proti cilju. Da bi to izboljˇ sali,
predlagamo interpolacijo gradienta, podobno kot je to
izvedeno za potencialno polje v poglavju 3.1.
Za izbrano lokacijo [x,y ]
T
v celiciM ocenimo in-
terpolirani potencialP(x,y ) in njegov negativni gradient
g z uporabo enaˇ cb (2) in (3). Interpolirani potencial se
doloˇ ci iz srediˇ sˇ cnih potencialov ˇ stirih interpolacijskih ce-
lic, kot je prikazano na sliki 2. Isti princip interpolacije
uporabimo za izraˇ cun interpoliranega gradientah(x,y ), ki
omogoˇ ca doloˇ citev poti z zveznim potekom, kot je prika-
zano na sliki 4 z vijoliˇ cno ˇ crto. Gradient za srediˇ sˇ ca ˇ stirih
interpoliranih celic je mogoˇ ce oceniti iz (3), ki za vsako
celico upoˇ steva samo levega soseda (x
n
= 0), da dobimo
elementx gradientag ali samo zgornjega soseda (y
n
= 0),
da dobimo elementy odg. Zato ocenimo gradient centra
celice ob upoˇ stevanju najmanjˇ sega diskretnega potenciala,
ki velja za center celice na podlagi obeh sosednjih celic
na osix aliy.
Oznaˇ cimo interpoliran gradient za center celice (po-
dobno kot interpoliran potencial v (1)) zh
cr
= [hx
cr
,hy
cr
]
T
,
kjer velja c,r ∈{ 0, 1} . Za celico s srediˇ sˇ cnimi koordi-
natami x
m
= x
0
+d
c
c, y
m
= y
0
+d
c
r se gradient za
U (x
m
,y
m
)<∞ glasi
h
cr
=− 1
d
c
 e(U (x
m
+d
c
e,y
m
)− p
cr
)
f (U (x
m
,y
m
+d
c
e)− p
cr
)
 , (5)
v primeruU (x
m
,y
m
) =∞ pa je
h
cr
=− 1
d
c
 S
x
(U (x
m
+d
c
S
x
,y
m
)− p
∗ cr
)
S
y
(U (x
m
,y
m
+d
c
S
y
)− p
∗ cr
)
 , (6)
pri ˇ cemer je
e = argmin
s
U(x
m
+d
c
s,y
m
);s∈{− 1, 0, 1} , f = argmin
s
U(x
m
,y
m
+d
c
s);s∈{− 1, 0, 1} , (7)
S
x
= sgn(x− x
m
) in S
y
= sgn(y− y
m
) ter sgn(· )
oznaˇ cuje funkcijo predznaka. Enaˇ cba (5) se nanaˇ sa na pri-
mer, ko je celica prosta, enaˇ cba (6) pa na primer, ko je ce-
lica zasedena.
ˇ
Ce je celica zasedena (U (x
m
,y
m
) =∞ ),
se njen potencial posodobi, oznaˇ ceno kotp
∗ cr
v (6), iz ˇ ze
znanega potencila P(x,y ) in gradientag(x,y ) v trenu-
tnem poloˇ zaju[x,y ]
T
:
p
∗ cr
=P(x,y )+g(x,y )× [x
m
− x,y
m
− y]
T
. 0
8
6
5
4
8
2
6
4
2
10
Slika 3: Interpolirano potencialno poljePn(xn,y n) s konturami
enakega potenciala (temnejˇ se barve oznaˇ cujejo niˇ zje vrednosti),
dobljeno z bilinearno interpolacijo za okolje na sliki 1
Pred izraˇ cunom gradientov celic v enaˇ cbah (5) do (7)
moramo preveriti, ali je katera od sosednjih celic zunaj
okolja.
ˇ
Ce je temu tako, se potencial te celice rekonstruira

245
0 2 4 6 8 10
0
1
2
3
4
5
6
7
8
9
10
Slika 4: Dobljene poti s potovanjem v smeri negativnega gra-
dienta (modra ˇ crta) in interpoliranega negativnega gradienta
(vijoliˇ cna ˇ crta) potencialnega polja s slike 3
podobno kot v (4) ob upoˇ stevanju znanega interpoliranega
potencialaP(x,y ) in gradientag(x,y ) za toˇ cko[x,y ]
T
.
Iz ocenjenih gradientov celich
00
, h
01
, h
10
inh
11
(enaˇ cbi (5) in (6)), se konˇ cni interpolirani gradient v tre-
nutnem poloˇ zaju doloˇ ci z
h(x,y ) =w
00
h
00
+w
01
h
01
+w
10
h
10
+w
11
h
11
, kjer so uporabljene enake uteˇ zi w
00
, w
01
, w
10
, w
11
kot
v (2). Primerjava dobljenih poti z gradientom g in iz-
boljˇ sanim interpoliranim gradientomh je prikazana na
sliki 4. Dobljene poti s sledenjem interpoliranega gradi-
enta potencialnega polja so gladke in ne trˇ cijo ob ovire.
Bilinearno interpolacijo je torej mogoˇ ce elegantno upo-
rabiti za doloˇ citev zveznega potencialnega polja in njego-
vega gradienta na podlagi zemljevida z mreˇ zo diskretnih
cen (diskretno potencialno polje). To omogoˇ ca doloˇ citev
ustreznih smeri voˇ znje, brez lokalnih minimumov, in poti,
ki ne trˇ cijo ob ovire in imajo zvezni potek, kar je po-
membno za robotska vozila. Omeniti velja, da bi lahko
bikubiˇ cna interpolacija [9, 10] ustvarila tudi bolj gladko
interpolacijo, vendar zahteva soseˇ sˇ cino ˇ sestnajstih celic,
kar je problematiˇ cno v bliˇ zini ovir ali v ozkih koridorjih,
saj zahtevajo zasedene celice posebno obdelavo, preden
se uporabijo v interpolaciji. In tudi sicer lahko v tem pri-
meru pride do lokalnih minimumov. Zato za naˇ crtovanje
gladkih poti predlagamo uporabo bilinearne interpolacije
z ustrezno predobdelavo zasedenih celic in z dodatno in-
terpolacijo gradienta. Dobljena pot je gladka, hkrati je
tudi intuitivna in skoraj optimalna. Kot smo ˇ ze omenili, v
potencialnem polju, zaradi izbranega naˇ cina njegove kon-
strukcije, ne bo lokalnih minimumov, ki so lahko prisotni
v klasiˇ cni formulaciji umetnega potencialnega polja.
4 Zakljuˇ cek
Delo predlaga nov pristop za doloˇ citev navigacijske funk-
cije, ki je razliˇ cica umetnega potencialnega polja. Mogoˇ ce
jo je uporabiti za navigacijo, naˇ crtovanje poti in vodenje
mobilnega robota. Navigacijska funkcija zagotavlja varno
vodenje do cilja brez lokalnih minimumov potencialnega
polja, kar je pogosta teˇ zava pri umetnih potencialnih poljih.
Optimalnost in konvergenca sta podedovani iz optimal-
nega iskanja na mreˇ zi celic, ki vrne diskretno potencialno
polje.
Za dosego gladke navigacijske funkcije in ustrezne
smeri voˇ znje v smeri padajoˇ cega gradienta, predlagamo
bilinearno interpolacijo z veˇ c novimi razˇ siritvami, kar
omogoˇ ca uˇ cinkovito uporabo pri naˇ crtovanju poti. Najprej
predlagamo doloˇ citev diskretnega potenciala za celice, ki
jih potrebujemo za interpolacijo in pripadajo oviram ali
so zunaj okolja, na podlagi njihove soseˇ sˇ cine. Nadalje
uvedemo dodatno interpolacijo gradienta iz ocenjenega
diskretnega gradienta interpoliranih celic. To vodi do
gladke in skoraj optimalne poti brez trkov oziroma navi-
gacije robota proti cilju. Predlagani interpolacijski pristop
je mogoˇ ce izvajati v sprotnem naˇ cinu, saj je raˇ cunsko
uˇ cinkovit, ker lahko interpolira tudi le diskretne potenci-
ale celic vzdolˇ z naˇ crtovane poti.
Zahvala
Avtorji se zahvaljujejo za finanˇ cno podporo Agencije Re-
publike Slovenije za raziskovalno dejavnost in podjetju
Epilog d.o.o. (ˇ st. L2-3168 in P2-0219).
Literatura
[1] S. M. LaValle, Planning algorithms. Cambridge University
Press, 2006.
[2] O. Khatib, “Real-time obstacle avoidance for manipulators
and mobile robots,” The International Journal of Robotics
Research, vol. 5, no. 1, pp. 90–98, 1986.
[3] E. W. Dijkstra, “A note on two problems in connexion with
graphs,” Numer. Math., vol. 1, p. 269–271, dec 1959.
[4] P. E. Hart, N. J. Nilsson, and B. Raphael, “A formal basis
for the heuristic determination of minimum cost paths,”
IEEE Transactions on Systems Science and Cybernetics,
vol. 4, no. 2, pp. 100–107, 1968.
[5] S. Koenig and M. Likhachev, “Fast replanning for naviga-
tion in unknown terrain,” IEEE Transactions on Robotics,
vol. 21, no. 3, pp. 354–363, 2005.
[6] S. Karaman and E. Frazzoli, “Optimal kinodynamic mo-
tion planning using incremental sampling-based methods,”
in 49th IEEE conference on decision and control (CDC),
pp. 7681–7687, IEEE, 2010.
[7] W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P.
Flannery, Numerical recipes in C: the art of scientific
computing (2nd ed.). New York, USA, 1992.
[8] “Bilinear interpolation.” https://en.wikipedia.
org/wiki/Bilinear_interpolation. dosto-
pano: 15. 2. 2022.
[9] R. Keys, “Cubic convolution interpolation for digital image
processing,” IEEE Transactions on Acoustics, Speech, and
Signal Processing, vol. 29, no. 6, pp. 1153–1160, 1981.
[10] G. Klanˇ car and M. Seder, “Coordinated multi-robotic ve-
hicles navigation and control in shop floor automation,”
Sensors, vol. 22, no. 4, 2022.