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
Probabilistic Least-violating Control Strategy Synthesis with Safety Rules
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
Probabilistisk minst-brytande kontrollstrategisyntes med säkerhetsregler (Swedish)
Abstract [en]

We consider the problem of automatic control strategy synthesis for discrete models of robotic systems, where the goal is to travel from some region to another while obeying a given set of safety rules in an environment with uncertain properties. This is a probabilistic extension of the work by Jana Tumová et al.  that is able to handle uncertainty by modifying the least-violating strategy synthesis algorithm. The first novel contribution is a way of modelling uncertain events in a map as a Markov decision process with a specific structure, using what we call "Ghost States". We then introduce a way of constructing a Product Automaton analogous to the original work, on which a modified probabilistic version of Dijkstra's algorithm can be run to synthesize the least-violating plan. The result is a synthesis algorithm that works similarly to the original, but can handle probabilistic uncertainty. It could be used in cases where e.g. uncertain weather conditions or the behaviour of external actors can be modelled as stochastic variables.

Abstract [sv]

Vi undersöker automatisk kontrollstrategisyntes (automatic control strategy synthesis) av diskreta robotsystem där målet för roboten är att färdas från en region till en annan medan den följer en mängd säkerhetsregler i en miljö med probabilistiskt osäkra egenskaper. Detta är en uppföljning av arbete gjort av Jana Tumová et al. Vi utvidgar deras arbete genom att modifiera strategisyntesalgoritmen så att den kan hantera probabilistiska situationer. Vårt första bidrag är ett sätt att modellera probabilistiska situationer i en karta genom en så kallad "markov decision process" med en specifik struktur som vi kallar för "Ghost States" (spöktillstånd). Vi bidrar även med ett sätt att konstruera en produktautomat som är analog till originalarbetets produktautomat. På vår produktautomat kan en probabilistisk variant av Dijkstras algoritm köras för att framställa en plan som är "least-violating" (bryter mot säkerhetsreglerna minst). Resultatet är en syntesalgorithm som fungerar som originalet men som även kan hantera stokastiska osäkerheter. Syntesalgoritmen skulle till exempel kunna användas i de fall där ovissa väderlekar eller beteendet av externa aktörer kan modelleras som stokastiska variabler.

Place, publisher, year, edition, pages
2018.
Series
TRITA-EECS-EX ; 2018:193
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:kth:diva-229867OAI: oai:DiVA.org:kth-229867DiVA, id: diva2:1215050
Subject / course
Computer Science
Supervisors
Examiners
Available from: 2018-06-20 Created: 2018-06-07 Last updated: 2018-06-20Bibliographically approved

Open Access in DiVA

fulltext(695 kB)37 downloads
File information
File name FULLTEXT02.pdfFile size 695 kBChecksum SHA-512
e59bd4b18e1c0383b49e7817e12ba420dc8f739b2b8d576b059252df89014820e1a4cd8d721f1b955dc69fdec693cf250084531da948a0d612aed033a1eecddc
Type fulltextMimetype application/pdf

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

Search outside of DiVA

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