ERK'2021, Portorož, 167-170 167
Lokalizacija nakupovalnega voziˇ cka v trgovini
Aljaˇ z Trebuˇ sak, Peter Krapeˇ z
Fakulteta za elektrotehniko, Univerza v Ljubljani, Trˇ zaˇ ska c. 25, 1000 Ljubljana
E-poˇ sta: at2337@student.uni-lj.si
Localization of a shopping cart in a
supermarket
A method of localization of a shopping cart in a super-
market is proposed. Online shops have become very pop-
ular nowadays, even grocery shopping. We developed
a system that helps workers navigate through the super-
market when gathering groceries for online orders to help
speed up the process. The system consists of five Ultra-
wideband beacons for rough localization. Four of them
are placed in four store corners, and the fifth is mounted
on the shopping cart. For precise localization and orien-
tation of the cart, Aruco markers on the store shelves are
used. We detect them with a camera that is mounted on
a shopping cart. A graphical user interface for a 7-inch
touchscreen was also developed. The worker is presented
with information about his/her position in a store. The
interface also shows the surrounding shelves, which are
coloured green when their markers are detected. The en-
tire system can be modified to adapt to a specific store or
customer demand.
1 Uvod
Trgovine z meˇ sanim blagom se, zaradi novih tehnolo-
gij in s tem tudi drugaˇ cnih navad ljudi, sreˇ cujejo z no-
vimi oblikami poslovanja. S tem pa tudi z novimi izzivi.
Sploh v ˇ casu korona krize, ko je dostop do trgovin ome-
jen. Ena izmed teh oblik je tudi prodaja preko spletnih
trgovin. Kupci torej preko spletne strani trgovca naroˇ cijo
izdelke na dom. Ideja je sama po sebi precej enostavna,
vendar se v ozadju skriva veliko dela in priprav. Da lahko
spletno poslovanje sploh funkcionira, mora biti celoten
sistem med seboj usklajen in ˇ casovno uˇ cinkovit.
Eden od delov tega sistema, je tudi nabiranje in pri-
prava izdelkov za poˇ siljanje na dom. Zaenkrat, prej ome-
njena naloga poteka podobno kot ˇ ce bi mi priˇ sli v trgo-
vino, le da to za nas opravi nekdo drug. Zaposleni torej
dobi nakupovalni seznam ˇ zivil, ki smo jih kupili v sple-
tni trgovini. Nato se z nakupovalnim voziˇ ckom poda v
trgovino in po trgovini nabira naroˇ cene izdelke. Pri pla-
niranju poti, ki jo prehodi se lahko zanaˇ sa le na lastne
izkuˇ snje o tem, kje se doloˇ ceni izdelki nahajajo. Takˇ sno
delo je zato precej naporno, tako fiziˇ cno kot psihiˇ cno.
Pri podjetju SPAR Slovenija, so se zato odloˇ cili, da
bodo zaposlenim skuˇ sali olajˇ sati delo, obenem pa skrajˇ sa-
ti dobavne roke pri naroˇ canju iz njihove spletne trgovine.
Podjetje je podalo pobudo za izdelavo sistema, ki ga bomo
predstavili v nadaljevanju.
2 Naloga
Naˇ sa naloga je bila, da v sodelovanju s podjetjem SPAR
Slovenija in Robolabom, razvijemo sistem za lokaliza-
cijo nakupovalnega voziˇ cka v trgovini. Takˇ sen sistem
bi omogoˇ cal doloˇ citev pozicije nakupovalnega voziˇ cka
kjerkoli znotraj trgovine. S tem bi zaposleni, ki izpol-
njuje spletne nakupovalne sezname toˇ cno vedel kje se
nahaja in kje se nahajajo izdelki iz seznama. Sistem bi
izraˇ cunal tudi optimalno pot po trgovini, kar bi skrajˇ salo
ˇ cas za izpolnitev posameznega naroˇ cila. Obenem se na
voziˇ cku nahajal tudi grafiˇ cni vmesnik z vsemi potreb-
nimi informacijami (npr. izpolnjenost nakupovalnega se-
znama, trenutna pozicija na zemljevidu trgovine, pot, lo-
kacija izdelka). Prilagojen sistem bi lahko uporabljali
tudi kupci. V tem primeru bi lahko le spremenili grafiˇ cni
prikazovalnik, da bi prikazoval recimo tudi ceno in popu-
ste, omogoˇ cal iskanje izdelkov. Tudi pot po trgovini bi
lahko spremenili iz ˇ casovno optimalne na poslovno opti-
malno.
Pri izvedbi naloge smo se odloˇ cili za uporabo ˇ siroko
pasovne radijske tehnologije (ang. Ultra-wideband,
UWB) za doloˇ citev absolutne pozicije v prostoru ter Aru-
co markerjev za doloˇ citev natanˇ cne lege v okolici polic.
2.1 UWB tehnologija
UWB je radijska tehnologija za komunikacijo na kratkih
razdaljah, podobno kot Bluetooth ali WiFi. Za razliko od
njiju, deluje na razmeroma visokih sredinskih frekvencah
nad 2,5 GHz in s pasovno ˇ sirino vsaj 500 MHz oziroma
20 % sredinske frekvence. Zaradi velike pasovne ˇ sirine je
lahko oddan signal v ˇ casovnem prostoru zelo kratek, kar
omogoˇ ca visoko ˇ casovno loˇ cljivost. Uporablja se za hitro
komunikacijo in lokalizacijo z veliko toˇ cnostjo. Razdalje
med napravami izraˇ cunava algoritem, ki temelji na mer-
jenju ˇ casa preleta (angl. Time-of-Flight).
ˇ
Se ena lastnost,
ki jo velja poudariti, je zelo majhna poraba energije [1, 2].
2.2 Aruco markerji
Aruco marker je digitalno ustvarjen kvadrat s ˇ crnim ro-
bom, njegova notranjost pa je sestavljena iz ˇ crno-bele
matrike, ki izgleda kot nekakˇ sen vzorec.
ˇ
Crni rob mar-
kerja omogoˇ ca hitro detekcijo, iz vzorca pa razberemo ID

168
[3]. Algoritem detekcije markerjev deluje tako, da najprej
doloˇ ci moˇ zne kandidate. Nato preveri, ˇ ce njihova notra-
njost ustreza binarni kodi Aruco markerjev. Kandidatom,
ki ustrezajo tem pogojem priredi ID ˇ stevilke. Nazadnje z
znanimi parametri kamere, markerjem doloˇ ci ˇ se njihove
koordinatne sisteme.
3 Eksperimentalni sistem
Eksperimentalni sistem sestoji iz petih UWB modulov
(Slika 1), mikro raˇ cunalnika Raspberry Pi 4b, 7 palˇ cnega
zaslona na dotik, kamere in Aruco markerjev. Za komu-
nikacijo med komponentami uporabljamo USB vodilo.
Slika 1: UWB modul s plastiˇ cnim ohiˇ sjem.
ˇ
Stirje UWB moduli so uporabljeni kot stacionarni mo-
duli - svetilniki z znano pozicijo. Peti UWB modul je mo-
bilni modul – uporabnik, ki ga lokaliziramo v prostoru
(Slika 2). Svetilnike postavimo v ˇ stiri vogale prostora
(npr. trgovine) znotraj dometa meritve razdalje tako, da
so veˇ cino ˇ casa v vidnem polju mobilnega modula. To
najlaˇ zje doseˇ zemo tako, da jih namestimo ˇ cim viˇ sje pod
strop. Uporabniˇ ski modul je nameˇ sˇ cen na nakupovalni
voziˇ cek in se z njim premika po prostoru. Razdalje med
uporabnikom in svetilniki se izraˇ cuna z dvosmernim do-
loˇ canjem ˇ casa preleta [4] na uporabniˇ ski strani. Izmer-
jene razdalje se preko USB vodila poˇ silja na raˇ cunalnik,
na katerega je uporabnik priklopljen. Raˇ cunalnik na pod-
lagi pridobljenih razdalj sproti izraˇ cunava lego voziˇ cka,
z uporabo trilateracije, obenem pa skrbi za nadzor in ne-
moten potek komunikacije med oddajniki.
S trilateracijo izraˇ cunamo absolutno pozicijo voziˇ cka
v prostoru s toˇ cnostjo do 20 cm. V drugem koraku z upo-
rabo kamere in Aruco markerjev pridobimo informacijo
o tem ali se nahajamo pred doloˇ ceno polico znotraj nekaj
cm. Z voziˇ ckom, na katerega je pritrjena kamera, se pre-
mikamo po prostoru in zaznamo marker na polici. S tem
pridobimo informacije, ki nam omogoˇ cajo doloˇ citev na-
tanˇ cne lege voziˇ cka glede na marker. Obenem izvemo
tudi pri kateri polici se nahajamo saj ima vsak Aruco
marker unikatno identifikacijsko ˇ stevilko (ID). Detekcijo
markerjev bomo podrobneje predstavili v poglavju 4.
Pozicijo uporabnika v prostoru in prikazujemo na 7
palˇ cnem zaslonu na dotik. Ta je preko mini HDMI kabla
povezan z raˇ cunalnikom, na katerem se izvaja algoritem
za lokalizacijo. Zaslon nam sluˇ zi kot uporabniˇ ski vme-
snik. Zaenkrat le prikazuje informacije o poziciji in nima
moˇ znosti vnosa. V kolikor bi ˇ zeleli v prihodnosti dodati
x
y
1
2
3
4
5
Slika 2: Shema sistema UWB modulov.
recimo iskalnik izdelkov, priklic prodajalca ali kaj podob-
nega, imamo tudi moˇ znost takˇ sne nadgradnje.
Sprva smo sistem zasilno postavili doma v dnevni
sobi. Postavitev ni bila optimalna (majhne razdalje, sis-
tem postavljen na tleh), kar se je odraˇ zalo v toˇ cnosti meri-
tev. Nato smo sistem postavili ˇ se v Laboratoriju za robo-
tiko. Svetilnike smo pritrdili pribliˇ zno 1,8 metra od tal in
s pomoˇ cjo referenˇ cnega sistema Optotrak ter testnih polic
izvedli meritve. Rezultati sledijo v poglavju 5.
4 Metodologija
Celoten algoritem lokalizacije in tudi grafiˇ cni vmesnik
smo sprogramirali v programskem jeziku Python 3 z upo-
rabo podpornih knjiˇ znic Scipy, Numpy, Serial v program-
skem okolju Visual Studio Code. Poleg tega smo upora-
bljali tudi program za oddaljeni dostop do Raspberry Pi-
ja – Putty ter program za prenos datotek med Raspberry
Pi-jem in osebnim raˇ cunalnikom – FileZilla. Zajem Aru-
co markerjev smo izvedli z uporabo navadne spletne ka-
mere in openCV knjiˇ znice. Grafiˇ cni vmesnik smo izdelali
z uporabo Python paketa TKinter.
4.1 Trilateracija
Prvi korak pri naˇ sem algoritmu, je bila izvedba trilatera-
cije. Trilateracija je postopek doloˇ canja neznane pozicije
uporabniˇ skega modulau, na podlagi znanih pozicij vsaj
treh svetilnikova
i
v 2D prostoru in izmerjenih razdaljd
1
,
d
2
ind
3
med svetilniki in uporabnikom (Slika 3). Vsaka
od teh razdalj nam pove, koliko stran od njih se mobilni
modul nahaja. Torej, ko izmeri razdaljo d
1
, lahko skle-
pamo, da se nahaja nekje na kroˇ znici s srediˇ sˇ cem v a
1
in polmerom d
1
. Podobno velja za razdalji d
2
in d
3
.
Na podlagi teh treh kroˇ znic uporabnik izraˇ cuna njihovo
preseˇ ciˇ sˇ ce in s tem doloˇ ci svojo pozicijo [5]. Relacijo
med izmerjenimi razdaljami, znanimi pozicijami svetil-
nikova
i
in neznano pozicijo uporabnikau zapiˇ semo z:
d
i
=ku a
i
k; (1)

169
zan svetilnikov zapiˇ semo sistem linernih enaˇ cb
Au=b
A=
0
B
@
a
2
 a
1
.
.
.
a
n
 a
1
1
C
A;b=
0
B
@
d
2
1
 d
2
2
k a
1
k
2
+ka
2
k
2
.
.
.
d
2
1
 d
2
n
k a
1
k
2
+ka
n
k
2
1
C
A;
(2)
pozicija uporabnikau se nato izraˇ cuna [6]
u=(A
T
A)
 1
Ab: (3)
Enako razmiˇ sljanje velja tudi za tri dimenzije, le da
imamo v tem primeru namesto kroˇ znic krogle, za enoliˇ cno
doloˇ citev pozicije mobilnega modula pa potrebujemo naj-
manj ˇ stiri stacionarne module.
ˇ
Ceprav smo izvajali izraˇ cun le v dveh dimenzijah,
smo tudi mi uporabljali ˇ stiri svetilnike zaradi veˇ cje na-
tanˇ cnosti. Uporabnik (na Sliki 2 oznaˇ cen s ˇ stevilko 5) to-
rej ves ˇ cas meri razdalje do ˇ stirih svetilnikov. V program
smo zapisali funkcijo, ki z uporabo trilateracije izraˇ cuna
pozicijo uporabnika in s tem tudi pozicijo voziˇ cka v pro-
storu.
4.2 Kalmanov filter
Izvedli smo tri verzije lokalizacje s uporabo UWB mo-
dulov. Prva verzija uporablja za doloˇ citev pozicije upo-
rabnika le izraˇ cun trilateracije. Drugi dve poleg trilate-
racije vsebujeta tudi razˇ sirjen Kalmanov filter, kjer ne-
linearno funkcijo, ki opisuje sistem prehajanja stanj ali
proces meritev, aproksimiramo z linearnim modelom [7].
Lokalizacijo s Kalmanovim filtrom smo torej izvedli na
dva naˇ cina. Obema je skupno to, da se zaˇ cetna stanja
izraˇ cunajo preko trilateracije. Enaka sta tudi izraˇ cuna
predikcije in korekcije. Razlikujeta se v izraˇ cunu kova-
rianˇ cne matrike ˇ suma meritve (R). Namen spreminjanja
vrednostiR je v zmanjˇ sevanju vpliva izmerjenih razdalj
za katere lahko predpostavimo, da so napaˇ cne zaradi ovir
med uporabnikom in svetilnikom. V prvem primeru pre-
verjamo inovacijo, ˇ ce je veˇ cja od doloˇ cene meje, sma-
tramo da ima izmerjena razdalja napako in pomnoˇ zimo
pripadajoˇ c element vR z inovacijo in dodatnim faktor-
jem. V drugem primeru primerjamo standardno deviacijo
u
a
2
a
1
a
3
d
1
d
2
d
3
Slika 3: Shema lokalizacije s trilateracijo.
inovacije ^  k
v premiˇ cnem oknu. Predpostavljamo, da je
vrednost ^  k
v primeru ovir med svetilnikom in uporab-
nikom veˇ cja kot pri pogojih brez ovir. Ko je ^  k
veˇ cja od
izbrane vrednosti, se pripadajoˇ ci elementi vR pomnoˇ zijo
z v naprej doloˇ cenim faktorjem.
4.3 Detekcija Aruco markerjev
Drugi del algoritma lokalizacije predstavlja detekcija Aru-
co markerjev. V sploˇ snem se pozicija voziˇ cka med gi-
banjem po trgovini izraˇ cunava s trilateracijo. Kadar pri-
demo mimo police z markerjem, ga s kamero zaznamo ter
preberemo njegov ID in podatke o koordinatnem sistemu.
Ker poznamo parametre kamere, lahko naredimo presli-
kavo v koordinatni sistem kamere, nato pa ˇ se v koordi-
natni sistem voziˇ cka. Na ta naˇ cin voziˇ cku doloˇ cimo na-
tanˇ cno lego in orientacijo v prostoru in s tem izboljˇ samo
rezultate trilateracije.
5 Rezultati
V Laboratoriju za robotiko smo postavili celoten eksperi-
mentalni sistem z dvema testnima policama in voziˇ ckom.
Na voziˇ cek smo pritrdili uporabniˇ ski modul in kamero
ter na police nalepili markerje.
ˇ
Stiri svetilnike smo pritr-
dili na stojala in jih razporedili v vogale testnega prostora
(slika 4). Pritrjeni so bili na viˇ sini pribliˇ zno 1,8 metra,
uporabnik pa je bil ves ˇ cas v njihovem vidnem polju, z
izjemo nekaj trenutkov, ko je operater potiskal voziˇ cek
in je stal med uporabnikom in posameznim svetilnikom.
Referenˇ cno pozicijo voziˇ cka smo doloˇ cili s sistemom Op-
totrak.
Izvedli smo dvoje meritev. Prviˇ c smo voziˇ cek pre-
mikali ob policah od zaˇ cetka polic do konca v eno smer
(Slika 4). Premik je prikazan s ˇ crno ˇ crto na Slika 4 (re-
ferenˇ cna pozicija). Zaˇ cetek polic se nahaja na levi strani
slike, konec pa na desni.
ˇ
Crne pike na sliki predstavljajo
izraˇ cune pozicije s trilateracijo, brez filtriranja. Koren
povpreˇ cne kvadratne napake teh meritev znaˇ sa 0,193 me-
tra. Temno sive pike predstavljajo izraˇ cune pozicije fil-
trirane s Kalmanovim filtrom. Vidimo, da bolj odstopajo
od reference, kar potrdi tudi vrednost korena povpreˇ cne
kvadratne napake, ki tokrat znaˇ sa 0,349 metra.
x / m
y / m
1
2
3
4
−0,5
0,0
0,0 0,5
1,0
1,0 1,5 2,0
−0,6
−0,4
−0,2
0,2
0,4
0,6
0,8
1,2
OPTO
UWB
KAL1
KAL2
Slika 4: Premik voziˇ cka iz leve proti desni.

170
x / m
y / m
1
2
3
−0,5
0,0
0,0 0,5
1,0
1,0 1,5 2,0
−0,6
−0,4
−0,2
0,2
0,4
0,6
0,8
1,2
1,4
OPTO1
OPTO2
UWB1
UWB2
Slika 5: Premik voziˇ cka iz leve (ˇ crna) proti desni in nazaj (siva).
Drugiˇ c smo voziˇ cek premikali od zaˇ cetka polic do
konca in nazaj (Slika 5). Tokrat smo prikazovali le izra-
ˇ cune pozicije s trilateracijo, brez filtriranja.
ˇ
Crne pike
na sliki predstavljajo izraˇ cune pozicije pri premiku od
zaˇ cetka polic, do konca. Sive pike predstavljajo izraˇ cune
pozicije pri premiku nazaj na zaˇ cetek polic.
ˇ
Crna in siva
ˇ crta predstavljata referenˇ cne pozicije voziˇ cka pri istih pre-
mikih. Koren povpreˇ cne kvadratne napake zdruˇ zenih me-
ritev znaˇ sa 0,206 metra.
Ugotovili smo, da natanˇ cnost izraˇ cuna pozicije s trila-
teracijo znaˇ sa pribliˇ zno 20 centimetrov. V primeru filtri-
ranja s Kalmanovim filtrom, bi se morala napaka zmanjˇ sa-
ti vendar se ta ˇ se poveˇ ca, na pribliˇ zno 35 centimetrov.
Najverjetnejˇ si vzrok je algoritem detekcije napake v iz-
merjeni razdalji. Predvidevamo, da so bile napake pri
meritvah takˇ sne, da ni bilo mogoˇ ce nastaviti parametrov
filtra tako, da bi uspeˇ sno duˇ sil izmerjene razdalje z na-
pako. Pri lokaliziranju voziˇ cka z Aruco markerji smo do-
segli povpreˇ cno napako 3 cm.
Grafiˇ cni vmesnik je zasnovan tako, da je enostaven
za uporabo, prikazuje pa le najpomembnejˇ se informacije.
Z njim ˇ zelimo prikazati pozicijo nakupovalnega voziˇ cka
glede na njegovo okolico in informacije o tem, kateri iz-
delki se nahajajo v njegovi bliˇ zini. Spodaj je prikazana
grafiˇ cna podoba vmesnika (Slika 6).
Slika 6: Grafiˇ cni vmesnik.
Na sredini vmesnika se nahaja shema nakupovalnega
voziˇ cka, okrog nje pa police oznaˇ cene s ˇ stevilkami od 1
do 6. Polici 2 in 5 se nahajata levo in desno od voziˇ cka.
Z njih lahko vzamemo izdelke, saj sta v naˇ sem dosegu.
Na voziˇ cku je pritrjena kamera, ki spremlja okolico in
iˇ sˇ ce markerje, narisane na policah. V trenutku, ko ka-
mera zazna marker na polici, se na grafiˇ cnem vmesniku
s sivo barvo pobarva polica, na kateri je zaznani marker
(v naˇ sem primeru je to polica ˇ stevilka 2). Na ta naˇ cin
dobimo informacijo o tem, kje se trenutno nahajamo.
Pika prikazuje pozicijo voziˇ cka glede na celoten pro-
stor (Slika 6), katerega dimenzije smo linearno presli-
kali na grafiˇ cni vmesnik. V danem primeru to pomeni,
da se nahajamo pribliˇ zno na sredini trgovine, ob polici
ˇ stevilka 2.
6 Zakljuˇ cek
Predstavili smo reˇ sitev, ki temelji na tehnologiji UWB in
detekciji Aruco markerjev. S pomoˇ cjo UWB oddajni-
kov smo doloˇ cili absolutno pozicijo voziˇ cka v prostoru,
detekcija markerjev pa sluˇ zi kot nadgradnja. Z njo na-
tanˇ cneje doloˇ cimo pozicijo, moˇ zno pa je tudi orientacijo
voziˇ cka. Razvili smo tudi grafiˇ cni vmesnik, ki uporab-
niku prikazuje informacije o tem, kje v trgovini se nahaja
in katere police so v njegovi bliˇ zini. Oznaˇ ci tudi polico
na kateri se nahaja ˇ zeleni izdelek.
Obstaja ˇ se ogromno moˇ znosti za nadgradnje naˇ sega
sistema. Trenutno se kamera nahaja na voziˇ cku, mar-
kerji pa na policah. Moˇ zno bi bilo narediti tudi obratno,
tako da bi se kamere nahajale pod stropom in iz ptiˇ cje
perspektive opazovale nakupovalne voziˇ cke. Markerji bi
bili nameˇ sˇ ceni na voziˇ cke tako, da bi bili obrnjeni proti
stropu. S tem bi se izognili problemu nezaznavanja mar-
kerjev zaradi orientacije voziˇ cka. Moˇ znosti nadgradenj
in personalizacije grafiˇ cnega vmesnika pa so tako rekoˇ c
neskonˇ cne. Sistem bi lahko v veliki meri prilagajali glede
na velikost trgovine in potrebe trgovca.
Literatura
[1] M. Stone, Insights: Phones, Samsung Electronics
America, https://insights.samsung.com/2020/08/21/what-
is-ultra-wideband-and-how-does-it-work
[2] A. Alarifi, A. Al-Salman, M. Alsaleh, A. Alnafessah, S. Al-
Hadhrami, M. Al-Almmar in H. Al-Khalifa, ”Ultra wide-
band indoor positioning technologies: Analysis and recent
advances”, Sensors, vol. 16, ˇ st. 5, str 707, 2016.
[3] OpenCV docs, https://docs.opencv.org/master/d5/dae/tutorial -
aruco detection.html
[4] D. Neirynck, E. Luk in M. McLaughlin, ”An alternative
double-sided two-way ranging method”, 2016 13st Wor-
kshop Positioning, Navigation and Communications
[5] OXTS trilateration, Oxford Technical Solutions Ltd., ht-
tps://www.oxts.com/trilateration
[6] S. A. Van De Geer, ”Least-Squares Estimation”, Encyclo-
pedia of Statistics in Quality and Reliability, Wiley Online
Library, vol. 2, 2008
[7] G. Klanˇ car, Avtonomni mobilni sistemi, Univerza v Lju-
bljani, Fakulteta za elektrotehniko, 2014.