| Abstract (croatian) | U svrhu omogućavanja dugoročne autonomije heterogenog roja morskih robota, u postupke upravljanja energijom sustava i interakcije među agentima uvode se algoritmi raspoređivanja zadataka. U scenariju u kojem višerobotski sustav treba samostalno provoditi dugoročnu nadzornu misiju, raspoloživi maksimalni kapacitet od pet autonomnih površinskih vozila - aPad platformi koje predstavljaju punjače sustava - je obično nadmašen brojem aktivnih zahtjeva za punjenjem, što dovodi do potrebe za pažljivim planiranjem i optimizacijom robotskih aktivnosti. U okviru ovog istraživanja razvija se dvoslojni sustav algoritama za donošenje odluka: na nižoj razini je niz algoritama baziranih na različitim paradigmama strojnog učenja usmjerenih na specifične situacije i rješenja dok je na višoj razini hiperheuristički algoritam koji odabire između njih. Predloženi predmet istraživanja i primjene je višeslojno društvo podvodnih i pomorskih robota razvijeno kao dio Horizon 2020 FET projekta subCULTron. Cilj ovog istraživanja je postizanje dugoročne autonomije u učećem, samoregulirajućem i samoodrživom roju pomorskih robota koji izvršava nadzornu i istraživačku misiju u izazovnom pomorskom okruženju venecijanske lagune. Heterogeni robotski sustav sastoji se od tri zasebne vrste agenata, od kojih su ovdje dva najznačajnija umjetne školjke (aMussels) koje putuju između morskog dna (gdje djeluju kao senzorske jedinice) i površine, te umjetni lopoči (aPads) na površini vode koji omogućuju razmjenu informacije i energije, a sadrže i mehaničke priključne stanice za punjenje baterija aMussel robota. aPad je preaktuirana površinska platforma opremljena s četiri potisnika, što mu daje značajnu slobodu gibanja, dok aMussel nema aktuatora osim sustava za upravljanje uzgonom. Komunikacija je vrlo važna u distribuiranoj strukturi roja, što znači da se tijekom rada moraju poštovati ograničenja koja se temelje na dometu dvaju dostupnih primarnih načina komunikacije (WiFi i akustički signal). Nadalje, roj mora biti sposoban prilagoditi se promjenama u okolini i stvarnim morskim uvjetima, kako borbom protiv tako i iskorištavanjem utjecaja pojava kao što su morske struje i vjetar. Naglasak na nenadziranom radu roja i prilagodbi promjenama okoline sugerira primjenu metoda strojnog učenja. Područje umjetne inteligencije može se podijeliti prema mnogim kriterijima, no pet paradigmi strojnog učenja uključuju: • spojne metode (neuronske mreže) • genetske algoritme i klasifikatore • empirijske metode za stvaranje pravila i stabla odlučivanja • analitičke metode učenja • pristupe na temelju slučajeva Predložena struktura sustava za donošenje odluka ima dva glavna sloja: na nižoj razini nalazi se skup algoritama (heuristika) za dodjelu zadataka temeljenih na aspektima nekoliko od gore navedenih paradigmi strojnog učenja, dok algoritam na višoj razini (hiperheuristika) odabire između njih. Hiperheuristika je općenito definirana kao automatizirana metodologija za odabir ili generiranje heuristike za rješavanje teških računskih problema pretraživanja. Izvorno nazvana "heuristika za odabir heuristika", ona predstavlja pristup na visokoj razini koji može odabrati i na konkretan problem primijeniti odgovarajuću heuristiku na nižoj razini, te to učiniti u svakoj točki odlučivanja. Heurističke i metaheurističke metode uspješne su u rješavanju problema pretraživanja u stvarnom svijetu, međutim nailaze na poteškoće u primjeni na nove probleme ili čak na nove slučajeve vrlo sličnih problema. Glavni uzrok tih poteškoća je širok raspon algoritama i parametara koji su uključeni u rješavanje problema, kao i nedostatak smjernica o tome kako odabrati između njih i kako ih podesiti. Osim toga, razina razumijevanja zašto pojedine heuristike rade u određenim situacijama, a ne u drugima često nije dostatna za jednostavno donošenje izbora, a teškoće u preciznom modeliranju problema i realnih situacija znače da strogo matematički optimalna rješenja možda zapravo i nisu najbolja moguća rješenja u primjeni. Cilj korištenja hiperheuristike jest povećanje razine općenitosti na kojoj optimizacijski sustavi mogu djelovati. Doktorski rad podijeljen je na uvodni dio ("1. Introduction") u kojem je dan opis glavne motivacije iza teme istraživanja – autonomnog dugoročnog nadzora izazovnih pomorskih ekosustava – i uključuje kratki pregled istraživanja umjetnog života i robotskih društava, s naglaskom na evolucijske algoritme i učenje potkrepljenjem. Poglavlje završava pregledom strukture rada, temeljnih hipoteza i izvornog znanstvenog doprinosa. Sam robotski roj korišten u radu opisan je u drugom poglavlju ("2. Heterogeneous marine swarm agents and interactions"). Poglavlje sadrži pregled robotskih agenata koji čine heterogeni pomorski roj s naglaskom na agente aPad i aMussel, opisujući hardverska i softverska rješenja koja su razvijena i korištena kako bi se ispunili svi preduvjeti za cilj nenadzirane dugoročne misije praćenja i istraživanja okoliša, uključujući modeliranje agenata koje omogućava testiranje sustava u simulacijama i eksperimentima sa stvarnim vozilima. Poglavlje također opisuje interakcije agenata s ciljem povećanja autonomije roja, posebno naglašavajući kako je postignuta razmjena energije između agenata, zaključno s eksperimentalnom validacijom razvijenih algoritama za autonomno međusobno sakupljanje i punjenje agenata. Treće poglavlje ("3. Multi-robot task assignment and low-level heuristics") fokusira se na specifični problem raspoređivanja interakcija i zadataka među agentima koji je glavni predmet rada, kao i na razvijenu strukturu sustava za donošenje odluka. Detaljno se opisuju metode podjele i klasteriranja koje se koriste za dodjeljivanje početnih područja odgovornosti agentima i niža razina sustava donošenja odluka koja se sastoji od situacijskih heuristika koje uključuju znanje o okolini. Poglavlje opisuje i pokazatelje učinkovitosti odabrane za evaluaciju željenih aspekata i mogućnosti sustava. Opisane su i rane simulacije robotskog roja temeljene na diskretnim događajima, kao i početni eksperimenti za validaciju komunikacije i metode postizanja konsenzusa među agentima u roju. U svrhu osmišljavanja heuristika niže razine, problem dodjeljivanja zadataka aPadima može se opisati kao vrsta problema usmjeravanja vozila. Heurističke metode rješavanja koje su usmjerene na specifične varijante problema usmjeravanja vozila, kao što su problem usmjeravanja vozila s vremenskim prozorima, kapacitirani problem usmjeravanja vozila, problem usmjeravanja vozila s više opskrbnih mjesta ili problem usmjeravanja vozila sa stohastičkim zahtjevima, intenzivno su proučavane, uz razvoj, implementaciju i detaljno prilagođavanje heuristika kako bi odgovarale određenoj vrsti problema. Budući da se obilježja problema mogu znatno razlikovati, nije nužno uvijek sasvim jasno koja će metoda dati najbolje rješenje za određeni slučaj problema. Ovdje je cilj osmisliti nekoliko kontekstualno specifičnih heuristika s dobrim ponašanjem u određenoj situaciji, a zatim odabirati između njih i kombinirati pristupe prema potrebi. Neki od pristupa uključuju korak odvajanja aMussel robota u grupe ili klastere koji odgovaraju parametrima kao što su ukupna raspoloživa energija, snaga signala ili izvediva udaljenost kretanja, a zatim dodjeljivanje aPadova pojedinačnim klasterima kao oblik određivanja "područja interesa" kako bi se osigurala pokrivenost i u smislu komunikacije i u smislu punjenja. Klasteriranje je problem prisutan u rudarenju podataka, bazama podataka, kompresiji podataka i strojnom učenju. Ono uključuje podjelu skupova opažanja u klastere tako da su intra-klasterska opažanja što je moguće sličnija (ili bliža, u odabranoj metrici), a inter-klasterska opažanja što različitija (ili dalja). Drugi je cilj klasteriranja smanjiti složenost podataka zamjenom skupine opažanja jednim reprezentativnim opažanjem, što dovodi do lakšeg i bržeg računanja i analize. Algoritmi bazirani na particioniranju, kao što je široko korišteni k-means algoritam, su specifični podtip klasteriranja koji organizira objekte u određeni broj particija, gdje svaka od njih predstavlja jedan klaster. Klasteri se formiraju na temelju funkcije udaljenosti, što dovodi do formiranja samo sfernih klastera i dozvoljava utjecaj šuma na rezultate klasteriranja. Ako se razmatra specifičan problem dodjele zadataka za komunikacijsko pokrivanje i punjenje robota, ovo svojstvo nije osobito problematično, jer su konveksni i sferni klasteri zaista željeni rezultat. K-means algoritam zahtijeva da broj klastera bude unaprijed poznat i zadan, ali se inače može smatrati potpuno nenadziranim ili, u slučaju uključivanja nekih prethodno poznatih saznanja o željenim ishodima, djelomično nenadziranim. Diferencijalna evolucija je još jedan predstavnik heurističkih pristupa niže razine dodjele zadataka i odlučivanja unutar roja. Izvorno je predložena kao iterativna heuristika za globalnu optimizaciju u kontinuiranom prostoru temeljena na populaciji, a kasnije je prilagođena za upotrebu u diskretnim prostorima i u problemima sekvenciranja, permutacije i raspoređivanja, uključujući i problem usmjeravanja vozila. Uvođenjem specifičnog kodiranja gena i populacije i stvaranjem prikladnih funkcija troška, kazni i uvjeta zaustavljanja, moguće je predstaviti i uvesti ograničenja u prostoru rješenja. U ovom će se slučaju kriteriji podudarati s čimbenicima iz stvarnog svijeta kao što su snaga morske struje i razina napona baterije robota, s genima koji kodiraju nizove zadataka za pojedina vozila. Razvoj prvog sloja sustava za donošenje odluka uključuje razvoj skupa algoritama za dodjelu zadataka koji koriste ili kombiniraju različite paradigme strojnog učenja ili ih koriste na različite načine, s ciljem osmišljavanja rasporeda kretanja i plana izvršavanja zadataka za dostupna vozila, prvenstveno u smislu punjenja ili premještanja drugih robota unutar roja. Ovo uključuje metodu klasteriranja, metodu klasteriranja s ograničenjima, metodu diferencijalne evolucije i hibridne metode. Osim toga, prisutne su vrlo jednostavne i situacijske heuristike razvijene tijekom rada s robotskim sustavom i koje odgovaraju na specifične probleme koji su uočeni. To su Greedy heuristika, koja u svakom koraku odabire najbližu mušulu kako bi se minimiziralo kretanje aPada; Cautious heuristika, koja u svakom koraku bira mušulu s najpraznijom baterijom kojoj je hitno potrebno punjenje; Rescue heuristika, koja bira mušulu najudaljeniju od centroida klastera kako bi se izbjegao gubitak robota i očuvali outlieri roja, te Rush heuristika, koja bira mušulu s najviše baterije, a koja je još uvijek kandidat za punjenje, kako bi se minimiziralo gubljenje korisnog vremena rada mušula. Posebna se pozornost posvećuje rubnim slučajevima u kojima se pojedine metode u određenim uvjetima ponašaju veoma dobro, a u drugima veoma loše (uključujući i uopće ne ostvarivanje konvergencije na valjano rješenje) jer će to biti vrijedan budući pokazatelj uspješnosti za hiperheuristički dio biranja algoritama. Drugi sloj sadrži hiperheuristički algoritam koji odabire između heuristika implementiranih u donjem sloju ovisno o situaciji u okolini i unutar roja, s krajnjim ciljem autonomnog i nenadziranog planiranja zadataka i istovremenog optimiranja potrošnje i distribucije energije. Pokazatelji učinkovitosti kojima se ocjenjuje rad sustava uključuju broj aktivnih i prisutnih agenata, prostornu raspodjelu agenata unutar roja, te praćenje ukupne količine vremena koje su agenti proveli radeći "koristan" posao, kao i raspodjelu tog vremena. Viša razina sustava odlučivanja - drugi sloj - opisana je u četvrtom poglavlju ("4. High-level heuristics - hyper-heuristics"). Poglavlje počinje pregledom hiperheuristike u literaturi, uključujući klasifikaciju i općeprihvaćene oblike izvedbe. Zatim se opisuje odabrana i implementirana viša razina strukture odlučivanja, uključujući detaljni opis metode odabira, donošenja odluka i učenja potkrepljenjem koji se koriste kako bi se sustavu dala prilagodljivost i autonomija. Definirane su metode vrednovanja rješenja koje koriste bodovanje i rangiranje, a u poglavlju su opisane i analizirane i simulirane i eksperimentalne varijante validacijskog referentnog scenarija. Hiperheuristike se dijele na tri kategorije ovisno o tome uče li tijekom pretraživanja ili prije pretraživanja, ili uopće ne dobivaju povratne informacije iz prostora pretraživanja: hiperheuristika s on-line učenjem, s off-line učenjem i bez učenja. Mogu biti klasificirane i kao selekcijske ili generacijske hiperheuristike, ovisno o tome odabiru li heuristiku iz skupa postojećih heuristika ili generiraju nove heuristike iz komponenti postojećih heuristika niže razine. Hiperheuristika korištena u ovom radu je selekcijska hiperheuristika s online učenjem. Selekcijska hiperheuristika bavi se problemima neizravno, pregledavanjem skupa dostupnih heuristika za svaki korak pretraživanja i odabirom one metode koju će se primijeniti na problem na temelju statistike prethodnih performansi svih metoda prema danom skupu metrika i pokazatelja. Strategija odabira ruletom često se koristi u evolucijskim algoritmima. Primijenjeno na hiperheuristički okvir, rulet odabire heuristiku s vjerojatnošću proporcionalnom njezinoj sposobnosti. Modificiranjem parametara sposobnosti metoda na temelju povratnih informacija primljenih iz prostora problema korištenjem više pokazatelja učinkovitosti, online učenje s potkrepljenjem uvodi se u sustav donošenja odluka. Nakon svake primjene heuristike niže razine, ona se ocjenjuje na temelju odabranih pokazatelja. Ako je heuristika imala bolju učinkovitost od dotadašnjeg prosjeka s obzirom na određeni pokazatelj, ona se pozitivno ocjenjuje za taj pokazatelj i njezina se sposobnost povećava za svaki takav "uspjeh". U suprotnom, ako heuristika ima lošiju učinkovitost, smatra se da nije uspjela i dobiva fiksnu "kaznu" koja umanjuje njezinu sposobnost i time joj smanjuje vjerojatnost ponovnog odabira. Hiperheuristička struktura znači rad odvojen od problemske domene, sa svim aspektima stvarnog svijeta apstrahiranim u pokazatelje koji se nakon implementacije i evaluacije vraćaju hiperheuristici. Ako, na primjer, tijekom eksperimenta struja, vjetar ili kvar na vozilu otežaju aPadu da se pomakne i dosegne aMussele odabrane u predloženom rješenju, trošak kretanja bit će znatno veći nego ranije u eksperimentu, a heuristika niže razine koja je proizvela ovo rješenje bit će kažnjena, dok će ona metoda koja predloži rješenje koje može na bilo koji način zaobići ili kompenzirati ovu smetnju i smanjiti troškove kretanja biti nagrađena, čime se postiže postupna adaptacija čitavog sustava. Zbog prirode sustava na koji se primjenjuje, učenje s potkrepljenjem mora biti u stanju donositi zaključke i odgovarajuće prilagodbe sposobnosti na temelju relativno oskudnih i rijetkih povratnih informacija. Budući da optimalno rješenje ovdje nije poznato i računalno ga je previše zahtjevno pronaći, kako bi se ocijenila izvedba implementirane hiperheuristike, usporedbe se rade pomoću najboljeg postignutog rješenja. Hiperheuristički odabir s učenjem s potkrepljenjem trebao bi biti bolji od jednostavnog odabira jedne od heuristika i njezine kontinuirane upotrebe ili nasumične primjene dostupnih heuristika. Učinkovitost se procjenjuje na temelju četiri odabrana pokazatelja: vrijeme rada aMussel robota, troškovi kretanja aPada, očuvanje outliera među aMussel robotima i (ne)uravnoteženost distribucije rada aMussela. U slučaju neravnoteže troškova kretanja i vremena rada, niža ocjena je bolja (što implicira da su kretanje i potrošnja energije aPada minimizirani, a koristan rad i vrijeme rada bili su ravnomjernije raspoređeni među svim agentima), dok je viša ocjena bolja za očuvanje outliera i postignuto ukupno vrijeme rada aMussela (što znači da su mjerenja konzistentno dobivana i od udaljenih agenata). Različiti eksperimenti ocjenjuju se korištenjem metoda rangiranja. Metoda koja pronalazi najbolje rješenje u skupu eksperimenata koji se ocjenjuju dobiva najnižu vrijednost, dok metoda s najlošijom izvedbom dobiva najveću vrijednost, a sve ostale se nalaze između. Metoda s ukupnim najnižim rangom stoga se može smatrati metodom s najboljim ostvarenim uspjehom. Tako su predstavljena i vrednovana četiri simulirana eksperimenta/scenarija: osnovna simulacija roja bez smetnji ili ekstrema, dvije instance u kojima se smetnja javlja u tijeku eksperimenta što dovodi do promjene u sposobnostima agenata, a time i ponašanja cjelokupnog roja, i jedna instanca u kojoj postoji jedan aMussel agent postavljen na znatnoj udaljenosti od ostatka roja. Eksperimentalni scenarij ekvivalentan osnovnoj simulaciji bez smetnji izveden je i sa stvarnim aPad vozilom. Rezultati simulacija i eksperimenata potvrđuju hipotezu da je moguće kontinuirano generirati nizove jednostavnih i računski nezahtjevnih heuristika koje su po definiranim pokazateljima učinkovitosti uspješnije od opetovane primjene svake pojedinačne heuristike, kao i njihove nasumične primjene. Kao hiperheuristička struktura s čvrsto postavljenom domenskom barijerom, sustav može generalizirati na različite nove situacije koje se pojavljuju u problemskom prostoru, npr. promjene u vrstama, broju i mogućnostima agenata roja, promjene u uvjetima u okolini roja i rad u različitim okolinama općenito. Temeljem upravljačkih algoritama i metodologija za validaciju algoritama razvijenih unutar doktorata izdvojena su tri znanstvena doprinosa: 1. Metoda dodjele i nizanja zadataka za više robota koji osiguravaju dugoročnu autonomiju heterogenog roja pomorskih robota uzimajući u obzir ograničenja okoline. 2. Hiperheuristička metoda za donošenje odluka unutar heterogenog roja pomorskih robota temeljena na nenadziranom odabiru između metoda dodjele i nizanja zadataka. 3. Metoda vrednovanja rješenja i definicija pokazatelja učinkovitosti i referentnog scenarija za procjenu valjanosti metoda donošenja odluka i dodjele zadataka primijenjenih na heterogenom roju pomorskih robota. Doktorski rad završava pregledom hipoteza i gore navedenih doprinosa te sažetkom najvažnijih točaka disertacije. Na temelju prezentiranog sadržaja ponovno se postavljaju te detaljnije razrađuju hipoteze i kao dokaz inovativnosti istraživanja nudi se popis publiciranih znanstvenih radova. |
