Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A comparative study between algorithms solving Ants Nearby Treasure Search problem for multiple treasures
KTH, School of Electrical Engineering and Computer Science (EECS).
KTH, School of Electrical Engineering and Computer Science (EECS).
2018 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesisAlternative title
En jämförelse mellan algoritmer som löser Ants Nearby Treasure Search för flera skatter (Swedish)
Abstract [en]

There is a need for fast and resource effective algorithms that can find people in need. This can be achieved using bio-inspired autonomous agents. One problem that is similar to the one of a rescue mission is Ants Nearby Treasure Search (ANTS). In this problem, a number of ants work together towards a common goal on a grid, for example finding a treasure. To make the problem more similar to a rescue mission, it is expanded to include multiple treasures. We name this problem Ants Nearby Treasures Search (ANTSS). ANTSS is solved using Parallel Diamond Search algorithm. We propose an addition to this solution. By changing the search origin we see if our algorithm performs better, mostly in cases where treasures are grouped up. Results show how changing the origin has a significant advantage in cases were treasures are grouped up. However, there is also huge disadvantages in general test cases.

Abstract [sv]

Det finns ett behov av snabba och resurseffektiva algoritmer som kan hitta personer i nöd. Detta kan uppnås med hjälp av biologiskt inspirerade autonoma agenter. Ett problem som liknar det utav ett räddningsuppdrag är Ants Nearby Treasure Search (ANTS). I detta problem arbetar myror mot ett gemensamt mål på ett rutnät, till exempel att hitta en skatt. För att göra problemet mer likt ett räddningsuppdrag utvidgas det till att omfatta flera skatter. Vi döper det nya problemet Ants Nearby Treasures Search (ANTSS). För att lösa ANTSS används Parallel Diamond Search-algoritmen. Vi föreslår en utvidgning till denna algoritm. Genom att ändra sökningens ursprung undersöks ifall vår algoritm fungerar bättre, mestadels i fall där skatter är grupperade. Resultaten visar hur förändringen av ursprunget har en stor fördel i de fall där skatter grupperas. Det finns däremot också stora nackdelar i allmänna testfall.

Place, publisher, year, edition, pages
2018.
Series
TRITA-EECS-EX ; 2018:212
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:kth:diva-229748OAI: oai:DiVA.org:kth-229748DiVA, id: diva2:1214312
Supervisors
Examiners
Available from: 2018-07-10 Created: 2018-06-06 Last updated: 2018-07-10Bibliographically approved

Open Access in DiVA

fulltext(490 kB)16 downloads
File information
File name FULLTEXT02.pdfFile size 490 kBChecksum SHA-512
ab5f225aea90aa93102278b87782c66877611c0f3c8a0edc92d81a03f691d18ae48e4b61a0bf9a3ef7826629aec83bf29a41e3c8a5c8a7a87c2fb1325e2ef71e
Type fulltextMimetype application/pdf

By organisation
School of Electrical Engineering and Computer Science (EECS)
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 16 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 34 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf