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
Estetisk vägplanering: Förutsägbarhet i Genetiska Algoritmer och Theta* i dynamiska miljöer
University of Skövde, School of Informatics.
2018 (Swedish)Independent thesis Basic level (degree of Bachelor), 20 credits / 30 HE creditsStudent thesisAlternative title
Aesthetic pathfinding : Predictability in Genetic Algorithms and Theta* in dynamic environments (English)
Abstract [sv]

Detta arbete jämför Theta* och en genetisk algoritm för att undersöka ifall en genetisk algoritm ger mer förutsägbara vägar i dynamiska miljöer än en deterministisk sökteknik. Den valda genetiska algoritmen är inte begränsad till vägval till närliggande noder, den nod som är näst i tur kan ligga var som helst i miljön. Theta* valdes för att matcha detta beteende och anses vara en bra representation av en deterministisk sökteknik då den är en vidareutveckling av standarden A*. Resultaten angående förutsägbarheten samlades in genom en enkätundersökning där fyra aspekter efterfrågades i jämförelser mellan Theta* och den genetiska algoritmen: vilken väg är mjukast, vilken väg är rakast, vilken väg är mest direkt, och vilken väg är kortast. Resultaten visade att den genetiska algoritmen presterat 0,6-2,0% bättre än Theta* och anses därför kunna ge mer förutsägbara vägar. Dock krävs mer forskning för att fastställa hur väsentliga de olika kriterierna är för förutsägbarheten.

Abstract [en]

This work compares Theta* and a genetic algorithm in order to investigate whether a genetic algorithm gives more predictable paths in dynamic environments than a deterministic search algorithm. The chosen genetic algorithm is not restricted to moving to nearby nodes - the next node may be located anywhere in the environment. Theta* was chosen to match this behaviour and is considered to be a good representation of a deterministic search technique as it is based upon the industry standard A*. Results related to the predictability were collected through a survey where four aspects were asked in comparisons between Theta* and the genetic algorithm: which path is smoother, which path is straighter, which path is more direct, and which path is shorter. The results showed that the genetic algorithm performed 0,6-2,0% better than Theta* and is thereby considered to be able to give more predictable paths. There is however a need for further studies in order to establish how important the criteria are for the predictability.

Place, publisher, year, edition, pages
2018. , p. 30
Keywords [en]
genetic algorithms, Theta*, predictability, pathfinding, aesthetics
Keywords [sv]
genetiska algoritmer, theta*, förutsägbarhet, vägplanering, estetik
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:his:diva-15441OAI: oai:DiVA.org:his-15441DiVA, id: diva2:1215258
Subject / course
Computer Science
Educational program
Computer Game Development - Programming
Supervisors
Examiners
Available from: 2018-06-20 Created: 2018-06-08 Last updated: 2018-06-20Bibliographically approved

Open Access in DiVA

fulltext(3072 kB)7 downloads
File information
File name FULLTEXT01.pdfFile size 3072 kBChecksum SHA-512
ca3c28702d90d8905b39fcb9a7f053ba4a2a7d885204951471dd2a8570140ec0980608031ab744dc39ed19c7796dfa76927db7147c15b90cb4261ae58f5b65e3
Type fulltextMimetype application/pdf

By organisation
School of Informatics
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 7 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: 15 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