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 Heuristic Approach to the Multiagent Pursuit and Evasion Problem in Polygonal Enviroments
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Optimization and Systems Theory.
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Optimization and Systems Theory.
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Optimization and Systems Theory.
2011 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
Abstract [en]

In this paper heursitic algorithms are developed for the pursuit evasion problem in polygonal enviroments.

In this problem, continuous trajectories shall be constructed for a group of pursuers, searching for an

evader, in such a way that the evader is guaranteed to be seen at some time during the search. Three

fundamentaly dierent heuristic methods are considered: tabu search, genetic algorithms and greedy

methods. The result is three heuristic algorithms. Two algorithms are readily implemented in ANSI C,

yielding solutions of high quality compared to previous work. The report attains and evaluates statistics

on runtime of the algorithms. The algorithms are compared considering the quality and e-ciency for a

vast amount of randomly generated enviroments.

Key-words

: Pursuit and Evasion, Heuristic algorithms, tabu search, greedy methods, genetic algorithms.

Abstract [sv]

I detta arbete utvecklas heuristiska algoritmer för ett avsökningsproblem i polygonmiljöer med mobila

robotar. Problemet består i att konstruera kontinuerliga banor för en grupp av robotar, sökande efter en

inkräktare, så att inkräktaren garanterat blir sedd vid någon tidpunkt under sökningen. Tre i grunden

olika heuristiska metoder behandlas för att skapa algoritmer: tabusökning, genetiska algoritmer och giriga

metoder. Resultatet är tre algoritmer, varav två har implementerats i ANSI C, som snabbt ger lösningar

av hög kvalitet jämfört med tidigare arbete. Statistik på körtider och lösningskvalitet för ett stort antal

slumpmässigt genererade områden har tagits fram och utvärderats.

Nyckelord

: Pursuit and evasion, sökalgoritmer, Heuristiska algoritmer, tabu, giriga metoder, genetiska

algoritmer.

Place, publisher, year, edition, pages
2011. , 39 p.
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:kth:diva-105488OAI: oai:DiVA.org:kth-105488DiVA: diva2:571139
Uppsok
Technology
Supervisors
Available from: 2012-11-21 Created: 2012-11-21 Last updated: 2013-02-18Bibliographically approved

Open Access in DiVA

fulltext(1104 kB)614 downloads
File information
File name FULLTEXT01.pdfFile size 1104 kBChecksum SHA-512
574e4434fb4317fa8453473bfed4dac12599702f71cf60ac29830e257a0be5fa7ceb4b89d5a5038ecd83b064e742d0ac403e8f9e514287791b2432c756342d25
Type fulltextMimetype application/pdf

By organisation
Optimization and Systems Theory
Engineering and Technology

Search outside of DiVA

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