Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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
The Monk Problem: Verifier, heuristics and graph decompositions for a pursuit-evasion problem with a node-located evader
KTH, School of Computer Science and Communication (CSC).
KTH, School of Computer Science and Communication (CSC).
2015 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
Abstract [en]

This paper concerns a specific pursuit-evasion problem with a node-located evader which we call the monk problem. First, we propose a way of verifying a strategy using a new kind of recursive systems, called EL-systems. We show how an EL-system representing a graph-instance of the problem can be represented using matrices, and we give an example of how this can be used to efficiently implement a verifier.

In the later parts we propose heuristics to construct a strategy, based on a greedy algorithm. Our main focus is to minimise the number of pursuers needed, called the search number. The heuristics rely on properties of minimal stable components.

We show that the minimal stable components are equivalent to the strongly connected components of a graph, and prove that the search number is equal to the maximum search number of its strongly connected components. We also establish lower and upper bounds for the search number to narrow the search space.

Abstract [sv]

Denna rapport avhandlar ett specifikt pursuit-evasion problem med en hörnplacerad flykting, som vi kallar för munkproblemet. Först föreslår vi ett sätt att verifiera en strategi med en ny typ av rekursivt system, kallat EL-system. Vi visar hur ett EL-system som representerar en grafinstans av munkproblemet kan representeras med matriser, och vi ger ett exempel på hur detta kan användas för att effektivt implementera en verifikator.

I de senare delarna föreslår vi heuristiker för att konstruera en strategi, baserad på giriga algoritmer. Vårt huvudfokus är att minimera antalet förföljare som krävs för att dekontaminera grafen, det så kallade söktalet. Vår heuristik förlitar sig på egenskaper för minimala stabila komponenter.

Vi visar att minimala stabila komponenter är ekvivalenta med de starka komponenterna i en graf, och härleder att söktalet är lika med det maximala söktalet för grafens starka komponenter. Vi etablerar också undre och övre gränser för söktalet i syfte att minska sökintervallet.

Place, publisher, year, edition, pages
2015.
Series
Kandidatexjobb CSC
Keyword [en]
graph decomposition, strongly connected component, pursuit-evasion, search number, el-system, formal grammar, greedy heuristic
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-166442OAI: oai:DiVA.org:kth-166442DiVA: diva2:811055
Educational program
Bachelor of Science - Information and Communication Technology
Presentation
2015-05-06, E32, Lindstedtsvägen 4, Stockholm, 11:45 (English)
Supervisors
Examiners
Available from: 2015-05-28 Created: 2015-05-10 Last updated: 2015-05-28Bibliographically approved

Open Access in DiVA

Fredriksson B., Lundberg E., The Monk Problem(1318 kB)184 downloads
File information
File name FULLTEXT01.pdfFile size 1318 kBChecksum SHA-512
737daef9058340d0e86f2289f377975a8165315995f1d0f2b32f38a79097eeacfef04ade52ad4ac809d429a4fc4cbce5ad667a10197980b56a89fbdd7f5cba24
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Fredriksson, Bastian
By organisation
School of Computer Science and Communication (CSC)
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 184 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: 751 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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