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
Towards Arc Consistency in PLAS
KTH, School of Electrical Engineering and Computer Science (EECS).
2018 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

The Planning And Scheduling (PLAS) module of ICE (Intelligent Control Environment) is responsible for planning and scheduling a large fleet of vehicles. This process involves the creation of tasks to be executed by the vehicles. Using this information, PLAS decides which vehicles should execute which tasks, which are modelled as constraint satisfaction problems. Solving the constraint satisfaction problems is slow. To improve efficiency, a number of different techniques exist. One of these is arc consistency, that entails taking a constraint satisfaction problem and evaluating its variables pairwise by applying the constraints among them. Using arc consistency, we can discern the candidate solutions to constraint satisfaction problems faster than doing a pure search. In addition, arc consistency allows us to detect and act early on inconsistencies in constraint satisfaction problems.

The work in this master thesis includes the implementation of a constraint solver for symbolic constraints, containing the arc consistency algorithm AC3. Furthermore, it encompasses the implementation of a constraint satisfaction problem generator, based on the Erdős-Rényi graph model, inspired by the quasigroup completion problem with holes, that allows the evaluation of the constraint solver on large-sized problems. Using the constraint satisfaction problem generator, a set of experiments were performed to evaluate the constraint solver. Furthermore, a set of complementary scenarios using manually created constraint satisfaction problems were performed to augment the experiments. The results show that the performance scales up well.

Abstract [sv]

Schemaläggningsmodulen PLAS som är en del av ICE (Intelligent Control Environment) är ansvarig för planering och schemaläggning av stora mängder fordonsflottor. Denna process involverar skapandet av uppgifter som behöver utföras av fordonen. Utifrån denna information bestämmer PLAS vilka fordon som ska utföra vilka uppgifter, vilket är modellerat som villkorsuppfyllelseproblem. Att lösa villkorsuppfyllelseproblem är långsamt. För att förbättra prestandan, så finns det en mängd olika tekniker. En av dessa är bågkonsekvens, vilket involverar att betrakta ett villkorsuppfyllelseproblem och utvärdera dess variabler parvis genom att tillämpa villkoren mellan dem. Med hjälp av bågkonsekvens kan vi utröna kandidatlösningar för villkorsuppfyllelseproblemen snabbare, jämfört med ren sökning. Vidare, bågkonsenvens möjliggör upptäckande och bearbetning av inkonsekvenser i villkorsuppfyllelseproblem.

Arbetet i denna masteruppsats omfattar genomförandet av en villkorslösare för symboliska villkor, innehållandes bågkonsekvensalgoritmen AC3. Vidare, så innefattar det genomförandet av en villkorsuppfyllelseproblemgenerator, baserad på grafmodellen Erdős-Rényi, inspirerad av kvasigruppkompletteringsproblem med hål, villket möjliggör utvärdering av villkorslösaren på stora problem. Med hjälp av villkorsuppfyllelseproblemgeneratorn så utfördes en mängd experiment för att utvärdera villkorslösaren. Vidare så kompletterades experimenten av en mängd scenarion utförda på manuellt skapade villkorsuppfyllelseproblem. Resultaten visar att prestandan skalar upp bra.

Place, publisher, year, edition, pages
2018. , p. 70
Series
TRITA-EECS-EX ; 2018:172
Keywords [en]
Constraint Programming, Scheduling, Planning, Symbolic constraints, Arc consistency
Keywords [sv]
Villkorsprogrammering, Schemaläggning, Planering, Symboliska villkor, Bågkonsekvens
National Category
Computer and Information Sciences
Identifiers
URN: urn:nbn:se:kth:diva-232081OAI: oai:DiVA.org:kth-232081DiVA, id: diva2:1232130
Subject / course
Computer Science
Educational program
Master of Science - Software Engineering of Distributed Systems
Supervisors
Examiners
Available from: 2018-07-10 Created: 2018-07-10 Last updated: 2018-07-10Bibliographically approved

Open Access in DiVA

fulltext(1043 kB)19 downloads
File information
File name FULLTEXT01.pdfFile size 1043 kBChecksum SHA-512
487ee0fdbabbc17ac6cd0dc7df2da6dd3803ffd6af5cb7e289327852696fbaf980c099cba42beffbb974babd4fe4e389491a773b5b2036fe21ab7f506d363ae9
Type fulltextMimetype application/pdf

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

Search outside of DiVA

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