Primerjava algoritmov za porazdeljeno preiskovanje prostora v simulacijskem okolju

Cikač, Jaka (author), 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.

• Language: Slovenian
• Keywords: večagentni sistemi, optimizacija roja delcev, preiskovanje prostora, gridland
• Work type: Bachelor thesis/paper
• Organization: FRI - Faculty of Computer and Information Science
• Year: 2014
• PID: 20.500.12556/RUL-29525
• Publication date in RUL: 19.09.2014

Secondary language

• Language: English
• Title: Comparison of algorithms for distributed space exploration in a simulated environment

Abstract

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.

• Keywords: multi-agent systems, particle swarm optimisation, space exploration, gridland