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
Optimal task planning in multi-vehicle systems under syntactically co-safe Linear Temporal Logic
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
Optimal planering av uppdrag i multi-fordonssystem under syntaktiskt samsäkrad linjär temporal logik (Swedish)
Abstract [en]

Autonomous vehicles need to be able to perform different instructions during different missions and situations. For task specification, logical languages are often used. Depending on desired expressiveness, there are different methods of task specification and planning. In this paper we explore the case of multi-agent systems performing tasks specified by co-safe Linear Temporal Logic (scLTL) formulas in relation to three cost functions. Specifically, we make use of the Vehicle Routing Problem to define our problem domain. Semantics for scLTL-formulas of multiple vehicles are introduced, as well as translations of scLTL-formulas into MILP constraints. We discuss use-cases and show how missions can be specified for both entire fleets, subgroups and single vehicles. The resulting method consists of several steps, from scLTL-formulas, into MILP constrains, ready to be solved by an already established MILP-solver. The complexity of the algorithm is discussed, as the algorithm is shown costly when problem instances grow.

Abstract [sv]

Autonoma fordon behöver kunna genomföra olika instruktioner beroende på uppdrag och situation. Logiska språk används ofta för uppdragsspecifikationer. Beroende på önskad uttrycksfullhet kan olika metoder för uppdragsspecifikation och planeringen användas. I denna uppsats utforskar vi metoder för uppdragsplanering i multi-robotsystem, i relation till ett antal olika kostnadsfuntioner under co-safe Linear Temporal Logic. Mer specifikt använder vi oss av definitionen av VRP för att formulera problemet. Semantik för multi-robotsystems tolkning av scLTL-formler introduceras, tillsammans med översättning av dessa formler till MILP restriktioner. Vi disskuterar användarfall och visar hur uppdrag kan anges för både hela grupper, delgrupper och enskilda robotar. Den resulterande metoden består av flera steg, från scLTL-formler, till MILP restriktioner, som sedan kan lösas av tillgänglig MILP-lösare. Komplexiteten av presenterad algoritm diskuteras, eftersom att algoritmen visar sig dyr när probleminstanser växer.

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

Open Access in DiVA

fulltext(568 kB)20 downloads
File information
File name FULLTEXT01.pdfFile size 568 kBChecksum SHA-512
947ab2c9405c1c458f4eadfffc560d80f70cfb5dabb64f8754a0b7b4b1caf726c8d6ea52ab20fb3c0e44d3baaad80396d131c6af69903216812e9bb315c8c033
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Hedengran, Gustav
By organisation
School of Electrical Engineering and Computer Science (EECS)
Computer Sciences

Search outside of DiVA

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