Primerjava algoritmov za porazdeljeno preiskovanje prostora v simulacijskem okolju : diplomsko delo

Cikač, Jaka (avtor), Skočaj, Danijel (mentor)

Cilj algoritmov za preiskovanje prostora je odkriti čim več neodkritega prostora v čim krajšem času in čim bolj učinkovito. Da bi to dosegli, se poslužimo porazdeljenih algoritmov, ki jih uprabimo na večagentnih sistemih. V delu želimo odkriti, kateri izmed algoritmov lahko učinkovito preiščejo prostor v simulacijskem okolju Gridland. Ker okolje v originalni različici ni namenjeno preiskovanju prostora, je bilo okolje potrebno prilagoditi in omogočiti spremljanje zgodovine premikov ter akcij večagentnega sistema za kasnejšo analizo učinkovitosti algoritmov. Za referenčno oceno smo implementirali naključnega agenta, tega pa primerjali z algoritmom, ki zastopa skupino tako imenovanih "pseudo-naključnih" algoritmov in z algoritmom, ki temelji na optimizaciji roja delcev. Pokazali smo, da so pseudo-naključni algoritmi veliko boljši od naključnih, kljub njihovi enostavnosti. Algoritem RDPSO, ki temelji na optimizaciji roja delcev, pa se je izkazal za učinkovitega, čeprav ni najhitrejši.

• Jezik: Slovenski jezik
• Ključne besede: večagentni sistemi, optimizacija roja delcev, preiskovanje prostora, gridland, računalništvo, računalništvo in informatika, univerzitetni študij, diplomske naloge
• Vrsta gradiva: Diplomsko delo/naloga
• Tipologija: 2.11 - Diplomsko delo
• Organizacija: FRI - Fakulteta za računalništvo in informatiko
• Založnik: J. Cikač
• Leto izida: 2014
• Št. strani: 79 str.
• PID: 20.500.12556/RUL-29525
• ISSN: 1536076739
• COBISS.SI-ID: 1536076739
• Datum objave v RUL: 19.09.2014

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: Comparison of algorithms for distributed space exploration in a simulated environment

Izvleček

Space exploration algorithms aim to discover as much unknown space as possible as efficiently as possible in the shortest possible time. To achieve this goal, we use distributed algorithms, implemented on multi-agent systems. In this work, we explore, which of the algorithms can efficiently explore space in a simulated environment Gridland. Since Gridland, in it's original release, was not meant for simulating space exploration, we had to make some modifications and enable movement history and action tracking for a multi-agent system with the purpose of algorithm efficiency analysis. A random agent was implemented for reference and compared with an algorithm, that represents a group of so called "pseudo-random" algorithms, and a particle swarm based algorithm. We show that pseudo-random algorithms are much better than random algorithms, despite their simplicity. Algorithm RDPSO, based on particle swarm optimisation, proved to be efficient, despite not being the fastest.

• Ključne besede: multi-agent systems, particle swarm optimisation, space exploration, gridland, computer science, computer and information science, diploma