1 UVOD
V naravi pogosto opazimo živali, ki se zadržujejo v
skupinah. Najbolj tipični primeri so jate ptic in rib, roji
žuželk, črede kopitarjev itd. Proučevanje skupin živali
že dalj časa ni samo domena biologov, s tem področjem
se ukvarjajo tudi znanstveniki iz drugih ved – od fizike
in medicine do družbenih ved in računalništva [1], [2],
[3], [4].
Računalničarji na tem področju sodelujemo večinoma
skozi izdelavo računalniških modelov, ki posnemajo
obnašanje skupin živali v naravi. Tovrstni modeli so se
izkazali za uporabno metodo pri proučevanju vedenja
skupin živali [5], [6], [7], [8], [9], [10], [3], [11],
pri simuliranju evolucije skupinskega vedenja [12], [2],
[13], [14], [15], [16] in pri izdelavi slikovitih animacij
za potrebe računalniških iger in filmov [17], [18], [19],
[20]. V vseh primerih je hitrost procesiranja ključnega
pomena – pri znanstvenih raziskavah nam višja hitrost
omogoča hitrejše pridobivanje rezultatov, medtem ko je
pri igrah in filmih visoka hitrost procesiranja po navadi
potrebna za izris simulacij skupin živih bitij v realnem
času.
Najpogostejši način za računalniško simuliranje sku-
pin živali so modeli, zasnovani na ravni posameznika
(angl. individual-based models). V tovrstnih modelih je
vsaka žival simulirana kot samostojen, avtonomen agent,
ki je sposoben zaznavati svet okoli sebe. S pomočjo
informacij, pridobljenih skozi zaznavanje sveta, nato
PRIMERJAVA ALGORITMOV ZA ISKANJE METRIČNIH SOSEDOV PRI SIMULACIJAH SKUPIN ŽIVIH BITIJ 215
b ca
Slika 1: Vizualizacija treh osnovnih teženj: a) kohezije, b) razmika in c) poravnave. Črni agent je opazovani posameznik, sivi
agenti pa so sosedi, ki neposredno vplivajo na njegovo vedenje. Beli agenti so zunaj radija zaznave opazovanega posameznika
in posledično nimajo neposrednega vpliva na njegovo vedenje.
posamezen agent prilagodi svoje vedenje z namenom,
da bi čim bolje zadovoljil svoje težnje (angl. drives).
Ker so tovrstni modeli zgrajeni na najnižji ravni (na
ravni posameznega agenta), pri načrtovanju vedenja
simuliranih živih bitij omogočajo veliko fleksibilnost
in natančnost [17], [21]. Za visoko natančnostjo pa
se skriva tudi največja težava modelov, zasnovanih na
ravni posameznika – visoka računska zahtevnost [17].
Zaradi visoke računske zahtevnosti se pogosto zgodi,
da načrtovani računalniški model ni sposoben v real-
nem času simulirati tako velikih skupin živali, kot jih
lahko najdemo v naravi. Zelo velike skupine živali v
naravi niso redkost, saj velikanske skupine (tisoč in več
posameznikov) najdemo pri pticah [22], ribah [23] in
kopitarjih [24].
V želji, da bi v realnem času lahko simulirali čim
večje skupine živali, se raziskovalci poslužujejo različnih
tehnik za pohitritev izvajanja simulacij. Najpogostejša
izmed njih je verjetno vzporedno procesiranje [25], [26],
[27]. Pri najpogostejši načinih vzporednega procesiranja
se za pohitritev uporabljajo grafične kartice, vendar ta
način pohitritve razvijalcem ni vedno na voljo – primer
so mobilne aplikacije oziroma igre, kjer večina mobilnih
naprav ne podpira vzporednega procesiranja na grafičnih
karticah. Poleg vzporednega procesiranja obstajajo tudi
tehnike modeliranja, ki so sicer hitrejše, vendar tudi
precej manj natančne kot modeli, zasnovani na ravni
posameznika. Najpogostejša izmed teh tehnik se imenuje
modeliranje na principu tokov (angl. flow-based models)
[28], [17], [29], [21], [20]. Ta tehnika se največkrat upo-
rablja, kadar raziskovalce zanimajo predvsem globalni
vzorci, ki se pojavijo na ravni skupine in ne lokalne
interakcije med posameznimi člani skupine. Gibanje
skupin v tovrstnih modelih spominja na tok tekočine,
od koder izhaja tudi ime tehnike. Računsko so tovrstni
modeli precej manj zahtevni kot modeli, zasnovani na
ravni posameznika, saj je vedenje zasnovano na ravni
skupin in ne na ravni posameznih agentov. Posledica
modeliranja na višji ravni pa je precej nižja natančnost in
s tem tudi dvomljiva biološka relevanca vedenja. Modeli,
ki združujejo tehnike obeh svetov, se imenujejo hibri-
dni modeli (angl. hybrid models) [17], [30]. Hibridni
modeli skušajo združiti natančnost modelov zasnovanih
na ravni posameznikov, s hitrostjo modelov, zasnovanih
na principu tokov. Rezultat so modeli, ki omogočajo
modeliranje razmeroma velikih skupin z dokaj visoko
natančnostjo [31], [17], [30]. Tako kot pri modelih na
principu tokov je tudi pri hibridnih modelih biološka
relevanca dvomljiva.
Ker je v številnih primerih modeliranja visoka bi-
ološka relevanca ključnega pomena, smo velikokrat pri-
siljeni uporabiti modele, zasnovane na ravni posame-
znika. Največji računski zalogaj je pri tovrstnih modelih
preiskovanje okolice. Da lahko agent pravočasno reagira
na spremembe v okolici, jo mora ves čas preiskovati. V
večini primerov gre pri preiskovanju okolice za iskanje
bližnjih sosedov, saj le-ti po navadi vplivajo na vedenje
opazovanega posameznika. Več avtorjev [25], [27], [32]
je s pomočjo uporabe različnih podatkovnih struktur
uspešno pohitrilo postopek iskanja sosedov.
Raziskave biologov nakazujejo, da na obnašanje opa-
zovanega posameznika v skupini vpliva bodisi določeno
število najbližjih sosedov (topološki sosedi) [33] bodisi
vsi sosedi v določenem radiju (metrični sosedi) [34].
Vermeulen in sod. [32] so pokazali, da pri iskanju
topoloških sosedov le-te najhitreje najdemo s pomočjo
k-d drevesa [35]. Ker se metode za iskanje metričnih
sosedov v določenih primerih razlikujejo od metod za
iskanje topoloških sosedov, v tej raziskavi empirično pri-
merjam tri pogoste tehnike iskanja metričnih sosedov –
216 DEMŠAR
Tabela 1: Opis in vrednosti uporabljenih parametrov modela.
Parameter Opis Vrednost
T Število korakov 1200
N Število agentov 100 – 3000
rr Radij območja gnezdenja 50 m
wr Utež gnezdenja 5
rs Radij razmika 1 m
ws Utež razmika 10
ra Radij poravnave 3 m
wa Utež poravnave 3
rc Radij zaznavanja/kohezije 5 m, 10 m
wc Utež kohezije 3
vmax Najvišja hitrost agentov 20 m/s
m Masa agentov 1 kg
naivno iskanje, k-d drevesa (angl. k-d tree) in razdelitev
prostora (angl. spatial partitioning).
2 METODE
Za izhodišče pri testiranju hitrosti iskanja metričnih so-
sedov sem si izbral najbolj znan in razširjen računalniški
model za simulacijo letenja ptic v jati BOIDS [19]. To
je model, zasnovan na ravni posameznika, pri katerem
vsak od simuliranih agentov skuša zadovoljiti tri težnje:
razmik (angl. separation), poravnavo (angl. alignment)
in kohezijo (angl. cohesion). S pomočjo težnje razmika
agenti preprečujejo medsebojne trke in ohranjajo osebni
prostor, s pomočjo poravnave usklajujejo hitrost in smer
gibanja s svojimi sosedi, s pomočjo kohezije pa tvorijo
skupine. Na sliki 1 je grafični prikaz teženj.
V razvitem računalniškem modelu je vsak agent defi-
niran s svojo pozicijo (~pi(t), pomeni pozicijo agenta i v
nekem trenutku v času) in vektorjem hitrosti (~vi(t)). Si-
mulacija deluje tako, da vsak simulirani agent v vsakem
časovnem koraku (angl. update step) prilagodi svoje ve-
denje glede na stanje sveta okoli njega, da bi zadovoljil
svoje težnje. Stanje sveta s stališča opazovanega agenta
je definirano skozi njegove metrične sosede – agente, ki
se nahajajo v radiju zaznave (rc) opazovanega agenta.
Vsak agent se skuša gibati tako, da bo stanje sveta okoli
njega čim bolje zadovoljevalo njegove težnje.
Za zadovoljitev težnje razmika se skuša opazovani
agent oddaljiti od vseh sosednjih agentov, ki so mu
preblizu (bliže od radija razmika, rs):
~fs,i(t) =
∑
j∈Ns,i(t)
ôij(t) · (r2s − |~oij(t)|
2
), (1)
kjer je fs,i(t) sila separacije opazovanega agenta i v
danem časovnem koraku, Ns,i(t) množica vseh i-jevih
sosedov, ki so v radiju razmika, in oij(t):
~oij(t) = ~pi(t)− ~pj(t). (2)
Skozi težnjo poravnave opazovani agent poskuša
uskladiti hitrost in smer gibanja z agenti, ki niso preblizu
(dalj od radija razmika) in hkrati ne predaleč (bliže od
radija poravnave, ra):
~fa,i(t) =
∑
j∈Na,i(t) ~vj(t)
|Na,i(t)|
, (3)
kjer je fs,i(t) sila poravnave in Na,i(t) množica
agentov, s katerimi opazovani agent skuša uskladiti
svoje gibanje. Skozi težnjo kohezije se opazovani agent
približa agentom, ki se mu zdijo predaleč (dalj od ra):
~fc,i(t) =
∑
j∈Nc,i(t) ~pj(t)
|Nc,i(t)|
− pi(t), (4)
fc,i(t) pomeni silo približevanja, Nc,i(t) pa množico
agentov, katerim se opazovani agent poskuša približati.
Poleg treh osnovnih teženj, ki jih je definiral Reynolds
[19], sem dodal še težnjo po zadrževanju v območju
gnezdenja (angl. roosting area). Če simulirana ptica
zapusti območje gnezdenja, se s pomočjo te težnje vrne
“domov”:
~fr,i(t) = −p̂i · (|pi| − rr), (5)
kjer fr,i(t) pomeni silo zadrževanja v območju gnez-
denja in rr radij, ki določa velikost območja gnezdenja.
Končna sila, ki se uporabi pri izračunu nove pozicije
agenta, se izračuna kot:
~fi(t) = ~fs,i(t) · ws + ~fa,i(t) · wa+
~fc,i(t) · wc + ~fr,i(t) · wr,
(6)
kjer so ws, wa, wc in wr uteži, ki določajo pomemb-
nost posamezne težnje. Dobljena sila se nato uporabi za
izračun nove hitrosti agenta:
~vi(t) = ~vi(t−∆t) +
~fi(t)
m
·∆t, (7)
kjer je m masa agenta. Dolžina vektorja hitrosti je
navzgor omejena z maksimalno hitrostjo (vmax). Nova
pozicija agenta tako postane:
~pi(t + ∆t) = ~pi(t) + ~vi(t) ·∆t. (8)
Kratek opis in vrednost uporabljenih parametrov naj-
demo v tabeli 1.
Poleg same primerjave hitrosti iskanja metričnih so-
sedov med iskanjem s k-d drevesom in razdelitvijo
prostora me je zanimalo tudi, kakšna je pohitritev obeh
metod v primerjavi z naivnim pristopom. Pri naivnem
pristopu vsak agent v vsakem časovnem koraku izračuna
oddaljenost do preostalih N − 1 agentov ter tako poišče
tiste, ki so od njega oddaljeni manj od radija zaznave.
Pri naivnem preiskovanju metričnih sosedov imamo torej
časovno zahtevnost O(N2).
K-d drevo je posebna oblika binarnega preiskovalnega
drevesa, pri kateri je vsako vozlišče k-dimenzionalna
točka [35]. Vsako notranje vozlišče v drevesu razdeli
prostor na dva dela s pomočjo hiperravnine. Točke, ki se
PRIMERJAVA ALGORITMOV ZA ISKANJE METRIČNIH SOSEDOV PRI SIMULACIJAH SKUPIN ŽIVIH BITIJ 217
Slika 2: Posnetek zaslona iz ene izmed simulacij. Nastavitev radija zaznave je bila tukaj manjša (rc = 5 m). Kot vidimo na sliki,
se v tem primeru tvori več manjših skupin agentov.
Slika 3: Prikaz iskanja sosedov pri uporabi razdelitve prostora.
Agent v črnem je opazovani posameznik, krog s črno obrobo
je njegov radij zaznavanja. Pri iskanju sosedov mora opazovani
agent preiskati zgolj celico, v kateri se trenutno nahaja (celica
s črno obrobo), in sosednje celice (modre celice). Sivi agenti
so sosedi, ki so v radiju zaznave in vplivajo na vedenje
opazovanega posameznika, medtem ko beli agenti na vedenje
opazovanega posameznika ne vplivajo, saj so od njega preveč
oddaljeni.
v virtualnem svetu nahajajo na levi strani opazovanega
vozlišča, najdemo v levem poddrevesu, tiste, ki se na-
hajajo desno, pa v desnem poddrevesu. Delitev prostora
poteka ciklično po vseh dimenzijah prostora, v katerem
se nahajajo točke. Pri treh dimenzijah je tako po navadi v
korenu drevesa delitev po x-osi, torej je hiperravnina za
delitev pravokotna na x-os. V levem poddrevesu bodo
tako točke, ki imajo x manjši od točke v korenu, v
desnem pa tiste, ki imajo večji x. Na naslednji ravni se
prostor razdeli po naslednji dimenziji (v našem primeru
je to y), na naslednji ravni po z, nato zopet po x itd. Pri
delitvi prostora je orientacija hiperploskve pravokotna
na os, po kateri delimo prostor. Gradnja drevesa ima
časovno zahtevnost O(n · log n), enako časovno zahtev-
nost ima tudi iskanje metričnih sosedov s pomočjo k-d
drevesa [36]. K-d drevo je prvotno namenjeno hranjenju
statičnih točk, ker se agenti v našem primeru premikajo,
to pomeni, da moramo v vsakem časovni korak najprej
zgraditi k-d drevo, nato pa ga uporabiti za iskanje
sosedov. Graditev drevesa v vsakem koraku je dodatna
računska obremenitev, v nasprotju z naivnim pristopom,
kjer so agenti in njihovo stanje po navadi že shranjeni v
seznamu, ki ga nato pregledujemo pri iskanju sosedov.
Pri razdelitvi prostora za pohitritev iskanja metričnih
sosedov je izkoriščeno dejstvo, da mora vsak agent
pri iskanju metričnih sosedov preiskati zgolj bližnjo
okolico in ne celotnega virtualnega sveta [27], [32].
Pri razdelitvi prostora se virtualni svet najprej razdeli
na manjša območja, v obliki kocke (celice). Stranica
kockaste celice je po navadi enaka kot radij, v katerem
218 DEMŠAR
0
30
60
90
120
0 1000 2000 3000
Število agentov
F
P
S
rc = 5 m
0
30
60
90
120
0 1000 2000 3000
Število agentov
F
P
S
rc = 10 m
Naivno iskanje KD Drevo Razdelitev prostora
Slika 4: Vizualizacija hitrosti izvajanja simulacij v odvisnosti od števila agentov pri dveh različnih velikostih radija zaznavanja.
Prikazano je povprečno število sličic na sekundo (FPS) pri določenem številu agentov in 95-odstoten interval zaupanja (obarvan
pas okoli črte). Pri manjšem radiju (zgornji graf) se v simulaciji tvori več manjših skupin, pri večjem radiju pa so skupine večje,
a jih je manj. Opazimo, da je pri bolj enakomerni porazdelitvi agentov po prostoru (večje število manjših skupin) algoritem,
ki išče metrične sosede na podlagi razdelitve prostora, hitrejši kot uporaba k-d drevesa. Kadar pa so agenti zgoščeni v večje
skupine, postane uporaba k-d drevesa bolj smiselna kot razdelitev prostora.
iščemo metrične sosede. Tako opazovani agent med
iskanjem svoje metrične sosede išče zgolj v celici, v
kateri se trenutno nahaja, in v celicah, ki so sosednje
trenutni celici. V najslabšem primeru (ko so vsi agenti
v eni celici) je časovna zahtevnost enaka kot pri na-
ivnem pristopu, ampak ker do tega scenarija v praksi
po navadi ne pride, je pohitritev iskanja sosedov s to
tehniko občutna [27], [32]. Princip razdelitve prostora
pri dvodimenzionalnem svetu je prikazan na sliki 3.
Primerjavo algoritmov sem izvedel s pomočjo merje-
nja hitrosti izrisa simulacij. Izris se po navadi meri skozi
število slik na sekundo (angl. frames per second, FPS),
ki jih je simulacija sposobna izrisati pri določenem
številu agentov. Model je bil razvit s pomočjo pogona
Unity [37]. Simulacije so bila zagnane na računalniku
z naslednjo konfiguracijo: procesor Intel Core i7-6700
(3,40 GHz), 32 GB RAM in grafična kartica NVIDIA
GeForce GTX 1070. Simulacije so tekle pri resoluciji 4K
(3840x2160). Da bi dosegel največje mogoče število slik
na sekundo ter da grafične nastavitvne ne bi pretirano
vplivale na rezultate, je bila kakovost izrisa najslabša
mogoča (brez senčenja in glajenja robov). Pri simu-
lacijah sem spreminjal algoritem za iskanje metričnih
sosedov in število agentov v modelu. Vsaka simulacija
je tekla 60 sekund – prvih 15 sekund je bilo namenjenih
inicializaciji, naslednjih 45 pa merjenju števila slik na
sekundo. Algoritme iskanja sosedov sem primerjal skozi
povprečno število slik na sekundo, doseženih v teh 45
sekundah.
Pri razdelitvi prostora na hitrost iskanja sosedov vpli-
vata tudi porazdelitev agentov po prostoru in velikost
celice pri razdelitvi prostora. Tako razdelitev agentov po
prostoru, kot tudi velikost celice, sta v mojem primeru
odvisna od radija zaznave/kohezije (rc). Pri manjših
vrednostih radija je razporeditev agentov po prostoru
bolj enakomerna, saj se tvori več manjših skupin agen-
tov. Pri večjem radiju se nasprotno tvori manjše število
večjih skupin, torej so agenti zgoščeni na manjšem
PRIMERJAVA ALGORITMOV ZA ISKANJE METRIČNIH SOSEDOV PRI SIMULACIJAH SKUPIN ŽIVIH BITIJ 219
delu celotnega prostora. Pri testiranju hitrosti iskanja
metričnih sosedov sem uporabil dve vrednosti radija
zaznave, vsaka od njiju pokrije enega od prej opisanih
scenarijev. Slika 2 prikazuje primer ene od simulacij za
prvi scenarij – tvori se večje število manjših skupin.
3 REZULTATI
Rezultati meritev so prikazani na sliki 4. Pri prvem sce-
nariju (manjši radij zaznave) je bila za iskanje metričnih
sosedov najhitrejša metoda razdelitve prostora. Sledilo je
iskanje sosedov z uporabo k-d drevesa, pričakovano je
bil najpočasnejši naivni pristop. Pri razdelitvi prostora je
za hitrost iskanja metričnih sosedov ključna porazdelitev
agentov po virtualnem svetu. Do najslabših rezultatov
pridemo, če se vsi agenti nahajajo v eni celici. V tem
primeru mora vsak agent izračunati razdaljo do vseh
drugih agentov ter preveriti, ali je ta razdalja manjša od
radija zaznave. Rezultat je enaka hitrost iskanja sosedov
kot pri naivni metodi. Če je razporeditev agentov po
prostoru bolj enakomerna, mora vsak agent pri iskanju
metričnih sosedov izračunati razdaljo zgolj do majhne
podmnožice vseh agentov, zato takrat pride to občutljive
pohitritve iskanja metričnih sosedov. To lepo prikazuje
slika 4 – uporaba razdelitve prostora pri bolj enakomerni
razporeditvi agentov (zgornji graf) je precej hitrejša kot
pri scenariju, ko se večina agentov zgosti na določenem
območju (spodnji graf).
Pri načrtovanju realnočasovnih simulacij težimo k
hitrostim izrisa, ki so večje od 60 sličic na sekundo
[38]. Pri manjšem radiju zaznave je simulacija, ki upora-
blja razdelitev prostora, sposobna procesirati s hitrostjo
60 sličic na sekundo pri 1500 agentih, k-d drevo je
sposobno procesirati 1300 agentov pri 60 sličicah na
sekundo, medtem ko naivna metoda doseže hitrost izrisa
več kot 60 sličic na sekundo pri zgolj 400 agentih.
Pri večjem radiju zaznave se je za najboljšo izkazala
metoda iskanja metričnih sosedov s pomočjo k-d dre-
vesa, sledila je uporaba razdelitve prostora, na zadnjem
mestu pa je bil zopet naivni pristop. K-d drevo je zmožno
procesirati 900 agentov s hitrostjo izrisa, višjo od 60
sličic na sekundo, razdelitev prostora lahko procesira
800 agentov, naivna metoda pa zopet zgolj 400 agentov.
4 SKLEP
V raziskavi sem primerjal hitrost iskanja metričnih so-
sedov v računalniških simulacijah živih bitij pri treh
različnih metodah. Primerjal sem najpreprostejšo, naivno
metodo in dve metodi za pohitritev iskanja – k-d drevo in
razdelitev prostora. Obstoječe raziskave [32] nakazujejo,
da je za iskanje topoloških sosedov (določeno število
najbližjih agentov) nejhitrejša uporaba k-d dreves. Pri
iskanju metričnih sosedov pa ta metoda ne da vedno naj-
boljših rezultatov, saj je optimalna metoda pri metričnih
sosedih odvisna od vedenja agentov. Če se tvori manjše
število večjih skupin agentov, je uporaba k-d drevesa
najboljša možnost. V nasprotnem primeru, ko se tvori
večje število manjših skupin, pa se je za najprimernejšo
izkazala uporaba razdelitve prostora.