Design Space Exploration (DSE) is the exploration of a space of possible designs with the goal of finding some optimal design according to some constraints and criteria. Within embedded systems design, automated DSE in particular can allow the system designer to efficiently find good solutions in highly complex design spaces. One particular tool for performing automated DSE is IDeSyDe which uses Constraint Programming (CP) and constraint optimization for modelling and optimization. The constraint models of DSE often include some real-valued parameters, but optimized CP-solvers typically require integer arguments. This makes it necessary to discretize the problem in order to make the approach useful in practice, effectively limiting the size of the search space significantly. The effects of this discretization procedure on the quality of the solutions have not previously been well studied. An investigation into how this kind of discretization affects the approximate solutions could make the approach more rigorous, and possibly also uncover exploitable details that could facilitate the development of even more efficient algorithms. This project presents a convergence proof based in CP and Multiresolutional analysis (MRA), including a practically useful error bound for solutions obtained with different discretizations. In particular, the mapping and scheduling of Syncronous Data Flow (SDF) models for streaming applications onto tile-based multiple processor system-on-chip platforms with a common time-division multiplexing bus interconnect is studied. The theoretical results are also verified using IDeSyDe for a few different configurations of applications and platforms. It can be seen that the experiments behave as predicted, with first order convergence in total error and adherence to the bound. / Designrymdsutforskning är benämningen för en systematisk utforskning av en rymd av möjliga designer i syfte att hitta bra eller optimala lösningar som optimerar något mål och som uppfyller krav och begränsningar. Automatiserad designrymdsutforskning har i synnerhet sett utveckling för tillämpningar inom design av inbyggda system, där den ständigt ökande komplexiteten hos moderna plattformar motiverat utvecklingen av nya metoder. Två stora delar är nödvändiga för att kunna tillämpa designrymdsutforskning för design av inbyggda system: en modell av systemet och en optimiseringsprocess. Beroende på situation kan systemmodeller variera från detaljerade simuleringar på transistornivå till övergripande analytiska modeller på applikationsnivå eller högre. Detaljerade simuleringar gör det möjligt att utvärdera en viss lösning mycket noggrant, men till en hög beräkningskostnad. Med analytiska modeller är det istället billigt att utvärdera enskilda lösningar, men på bekostnad av noggrannhet. På samma sätt kan olika optimeringsprocesser också användas: snabbare approximativa algoritmer kan användas för att hitta lösningar relativt snabbt men utan garantier för optimalitet, medans mer uttömmande algoritmer typiskt kräver mycket beräkningskraft. Ett verktyg för automatiserad designrymdsutforskning är IDeSyDe. IDeSyDe använder villkorsbaserade modeller och uttömmande sökning genom Branch and Bound. Optimerade algoritmiska lösare för villkorsprogrammeringsproblem kräver ofta heltalsparametrar. Modeller för designrymdsutforskning innehåller å andra sidan ofta kontinuerliga parametrar. På grund av detta är det ofta nödvändigt att disktretisera problemet för att effektivt kunna hitta lösningar. Eftersom en diskretisering begränsar mängden lösningar i sökrymden riskerar en sådan omformulering att ta bort även optimala lösningar. En designrymdsutforskningsalgoritm som utnyttjar diskretisering av designrymden måste på grund av detta generellt ses som en approximativ algoritm. Hur en sådan diskretisering påverkar lösningarna -- dvs. hur nära de approximativa lösningarna kan förväntas komma den optimala lösningen utan diskretisering -- har dock inte studerats i närmare detalj. En bättre förståelse för hur diskreta, approximativa problem och lösningar relaterar till sina exakta motsvarigheter kan ge metoden mer rigör. En undersökning av den underliggande matematiken har också potential att belysa andra samband och strukturer som potentiellt skulle kunna användas för att utveckla bättre eller mer effektiva algoritmer. I den här rapporten presenteras ett konvergensbevis baserat på villkorsprogrammering och multiupplösningsanalys med ett begränsat felintervall i termer av probleminstansspecifika parametrar och en diskretiseringsparameter. Beviset är framtaget för tillämpning med IDeSyDe och är därför begränsat till en kombination av modeller som verktyget för närvarande stödjer, nämligen strömmande-dataflödesapplikationer beskrivna som synkrona dataflödesmodeller (Synchronous Data Flow, SDF) samt en ''tile''-baserad modell för system med flera processorer på ett chip (MPSoC) med en gemensam tidspartitionerad multiplexor-bus för kommunikation mellan processor-''tiles''. De teoretiska resultaten är verifierade och tillämpade på ett flertal exempelfall beräknade med IDeSyDe, där konvergensen studerats experimentellt.

Maritime navigation heaviliy relies on GNSS and related technologies for positioning and navigiation. Since these technologies are vulnerable to external threats such as signal spoofing, alternatives are needed for backup purposes. Our proposal is to use radar to construct polar amplitude gridmaps tailored for the intended route, and using a particle filter for position estimation. The proposed approach has been successfully demonstrated on data from a surface vessel in the harbor of Helsinki. / Navigation i marina miljöer är idag mycket beroende av GNSS och relaterad teknologier. Eftersom dessa GNSS teknologier är föremål för terrorism och sabotage finns behov av alternativ. I detta examenarbete föreslås att använda radar ombord på ett fartyg för att konstruera amplitudrutnätskartor av omgivningen, och därefter använda ett partikelfilter för estimering av fartygets position.Fartygets position kunde framgångsrikt estimeras med data från ett fartyg i Helsingfors hamn.

This project aims to develop a simulator for generating realistic data from vehicles operating in underground mines, encompassing positional data and sensor values of the velocity and angle. The project addresses the challenge of analyzing the Hybrid Positioning algorithm within Mobilaris Onboard, a navigation system for underground mines. The absence of the 100% ground truth for vehicle positions in the post-analysis of sensor log files necessitates the creation of this simulator. The project's mission includes generating vehicle paths and corresponding sensor readings, focusing on realism. Additional considerations include introducing realistic noise and integrating the simulator's output with visualization tools. Furthermore, the project aims to develop a tool for comparing simulated sensor values with actual sensor data, facilitating algorithm refinement and development. The project also incorporates time series analysis to interpret the sensor data generated by the simulator. This approach is crucial for understanding patterns and trends in the vehicle's positional and velocity data over time, providing valuable insights for refining the navigation algorithm.

Detta examensarbete presenterar en utvärdering av konsekvenser som kan uppstå vid Införandet av Multiplex Power-mättmetoden för att kontrollera FM-deviation vid radiosändningar i Sverige. Metoden är beskriven i en publicerad standard från ITU: ITU-R BS.412-9. Metoden, även kallad Multiplex Power, är en begränsningsstandard för analog (terrestrial) FM sändning på VHF band. Skälet att införa Multiplex Power mätning är att man genom metoden både kan minska grannkanalinterferenserna och samtidigt jämna ut de stora variationerna i de upplevda ljudnivåerna som finns mellan de olika FM-stationerna. Denna mätmetod går ut på att man samplar värden på deviation, lagrar samplen och räknar ut ett medelvärde av energin under ett intervall av 60 sekunder. Detta energivärde jämförs med en referensnivå, som i ITU-normen definieras som +/-19kHz toppdeviation vid 400 Hz modulationssignal. Skillnaden detta referensvärde kan anges i dB av instrumentet, som en enskild siffra vilkets värde skrivs dynamiskt över tid. För att kunna utvärdera metoden genomfördes ett lyssningsexperiment. I experimentet användes ljudfiler som är processade enligt hur dagens normer tillämpas i Sverige och ljudfiler som är processade för att följa BS.412-9-normen. Som tillvägagångssätt användes ett webbformulär och en databas. Testpersoner kunde utföra lyssningen och notera resultatet som sedan lagrades för vidare beräkningar. Ljudfilerna och tillhörande mätningsvärden från lyssningsexperimentet användes sedan för att utvärdera resultatet. / QC 20100707

The paper and the graphics industries use two instruments with different optical geometry (d/0 and 45/0) to measure the quality of paper prints. The instruments have been reported to yield incompatible measurements and even rank samples differently in some cases, causing communication problems between these sectors of industry.A preliminary investigation concluded that the inter-instrument difference could be significantly influenced by external factors (background, calibration, heterogeneity of the medium). A simple methodology for eliminating these external factors and thereby minimizing the instrument differences has been derived. The measurements showed that, when the external factors are eliminated, and there is no fluorescence or gloss influence, the inter-instrument difference becomes small, depends on the instrument geometry, and varies systematically with the scattering, absorption, and transmittance properties of the sample.A detailed description of the impact of the geometry on the results has been presented regarding a large sample range. Simulations with the radiative transfer model DORT2002 showed that the instruments measurements follow the physical radiative transfer model except in cases of samples with extreme properties. The conclusion is that the physical explanation of the geometrical inter-instrument differences is based on the different degree of light permeation from the two geometries, which eventually results in a different degree of influence from near-surface bulk scattering. It was also shown that the d/0 instrument fulfils the assumptions of a diffuse field of reflected light from the medium only for samples that resemble the perfect diffuser but it yields an anisotropic field of reflected light when there is significant absorption or transmittance. In the latter case, the 45/0 proves to be less anisotropic than the d/0.In the process, the computational performance of the DORT2002 has been significantly improved. After the modification of the DORT2002 in order to include the 45/0 geometry, the Gauss-Newton optimization algorithm for the solution of the inverse problem was qualified as the most appropriate one, after testing different optimization methods for performance, stability and accuracy. Finally, a new homotopic initial-value algorithm for routine tasks (spectral calculations) was introduced, which resulted in a further three-fold speedup of the whole algorithm.The paper and the graphics industries use two instruments with different optical geometry (d/0 and 45/0) to measure the quality of paper prints. The instruments have been reported to yield incompatible measurements and even rank samples differently in some cases, causing communication problems between these sectors of industry.A preliminary investigation concluded that the inter-instrument difference could be significantly influenced by external factors (background, calibration, heterogeneity of the medium). A simple methodology for eliminating these external factors and thereby minimizing the instrument differences has been derived. The measurements showed that, when the external factors are eliminated, and there is no fluorescence or gloss influence, the inter-instrument difference becomes small, depends on the instrument geometry, and varies systematically with the scattering, absorption, and transmittance properties of the sample.A detailed description of the impact of the geometry on the results has been presented regarding a large sample range. Simulations with the radiative transfer model DORT2002 showed that the instruments measurements follow the physical radiative transfer model except in cases of samples with extreme properties. The conclusion is that the physical explanation of the geometrical inter-instrument differences is based on the different degree of light permeation from the two geometries, which eventually results in a different degree of influence from near-surface bulk scattering. It was also shown that the d/0 instrument fulfils the assumptions of a diffuse field of reflected light from the medium only for samples that resemble the perfect diffuser but it yields an anisotropic field of reflected light when there is significant absorption or transmittance. In the latter case, the 45/0 proves to be less anisotropic than the d/0.In the process, the computational performance of the DORT2002 has been significantly improved. After the modification of the DORT2002 in order to include the 45/0 geometry, the Gauss-Newton optimization algorithm for the solution of the inverse problem was qualified as the most appropriate one, after testing different optimization methods for performance, stability and accuracy. Finally, a new homotopic initial-value algorithm for routine tasks (spectral calculations) was introduced, which resulted in a further three-fold speedup of the whole algorithm. / QC 20100707 / PaperOpt, Paper Optics and Colour

Finite difference approximations are methods for solving differential equations by approximating derivatives. This work will begin with how to solve a partial differential equation (PDE) called the advection equation, ut + cux = 0. Both analytically, and approximately with three different finite difference methods for the spatial part of the equation: • Central in space, • First order upwind in space, • Beam-Warming in space, and forward Euler for the temporal part. We then use the theoretical approximations considered for the advection equation and apply it on Maxwell’s equations for electromagnetism in 1D. This is a system of advection equations that describes how electromagnetic waves propagate through a dielectric material. In the end of this work we will model this electromagnetic wave, or wave of light moving through materials with different refraction indexes.

Workforce scheduling is widely used within most industries. A well-outlined and efficient schedule gives cost savings, such as reduced number of overtime hours, increases overall utilization, and facilitates meeting demands. A large and complex schedule, for example, scheduling of a health care workforce, needs to consider many parameters when constructed; it is essential to account for all critical constraints regarding who can dispense a particular medicine, laws restricting the health care system, etcetera. This thesis evaluates two different methods for implementing a workforce scheduling system for one of Linköping’s most well-known restaurants and bars for students, using mixed integer programming and heuristics. Flamman Pub & Disco recruits new employees prior to every semester. Usually, the workforce consists of around 100 employees, and the vast majority of them work either in the bar or in the kitchen. Historically, the scheduling process has been handled manually using Excel. This does, however, take up much time for the operations manager, something considered frowned upon. Therefore, this thesis suggests an automated scheme for future scheduling processes. Because Flamman is a student organization, they do not hold the capital to invest in expensive licensed optimization software. However, literature studies have shown that heuristics such as large neighborhood search can generate sufficient performance, and therefore the investigation of free-of-charge software using a heuristic approach is conducted. The constructed framework uses a mixed integer programming model, which also lays the cornerstone for the two heuristics: a reverse constructive heuristic and a large neighborhood search. The results retrieved from the analysis prove that a heuristic can be a helpful tool for upcoming recruitment periods. There are, however, recommended areas for improvement regarding the current state of the heuristic.

For larger instances of multi-objective optimisation problems, the exact Pareto frontier can be both difficult and time-consuming to calculate. There is a wide range of methods to find feasible solutions to such problems, but techniques for finding good optimistic bounds to compare the feasible solutions with are missing. In this study, we investigate the use of Lagrangian relaxation to create optimistic bounds to bi-objective optimisation problems with complicating side constraints. The aim is to develop an effective method to produce optimistic bounds that are closer to the Pareto frontier than the commonly used linear programming bounds.  In order to use Lagrangian relaxation on the bi-objective problem, the objectives are combined using the weighted sum method. A Lagrangian dual function is then constructed by relaxing the complicating constraints and the subgradient method is used to optimise the dual problem in order to find an optimistic solution. By solving the single-objective problem for multiple weights, an optimistic bound to the Pareto frontier can be constructed. The subgradient method also includes a heuristic to find feasible solutions. The feasible solutions found by the heuristic form a pessimistic bound to the frontier. The method has been implemented and tested on several instances of a capacitated facility location problem with cost and CO2 emission as objectives. The results indicate that, by using Lagrangian relaxation, an optimistic bound close to the Pareto frontier can be found in a relatively short time. The heuristic used also manages to produce good pessimistic bounds, and hence the Pareto frontier can be tightly enclosed. The optimistic bounds found by Lagrangian relaxation are better and more consistent along the Pareto frontier than the bounds found by linear programming.

This dissertation is concerned with three problems within the field of optimization for agent--based systems. Firstly, the inverse optimal control problem is investigated for the single-agent system. Given a dynamic process, the goal is to recover the quadratic cost function from the observation of optimal control sequences. Such estimation could then help us develop a better understanding of the physical system and reproduce a similar optimal controller in other applications. Next, problems of optimization over networked systems are considered. A novel differential game approach is proposed for the optimal intrinsic formation control of multi-agent systems. As for the credit scoring problem, an optimal filtering framework is utilized to recursively improve the scoring accuracy based on dynamic network information. In paper A, the problem of finite horizon inverse optimal control problem is investigated, where the linear quadratic (LQ) cost function is required to be estimated from the optimal feedback controller. Although the infinite-horizon inverse LQ problem is well-studied with numerous results, the finite-horizon case is still an open problem. To the best of our knowledge, we propose the first complete result of the necessary and sufficient condition for the existence of corresponding LQ cost functions. Under feasible cases, the analytic expression of the whole solution space is derived and the equivalence of weighting matrices is discussed. For infeasible problems, an infinite dimensional convex problem is formulated to obtain a best-fit approximate solution with minimal control residual, where the optimality condition is solved under a static quadratic programming framework to facilitate the computation. In paper B, the optimal formation control problem of a multi-agent system is studied. The foraging behavior of N agents is modeled as a finite-horizon non-cooperative differential game under local information, and its Nash equilibrium is studied. The collaborative swarming behaviour derived from non-cooperative individual actions also sheds new light on understanding such phenomenon in the nature. The proposed framework has a tutorial meaning since a systematic approach for formation control is proposed, where the desired formation can be obtained by only intrinsically adjusting individual costs and network topology. In contrast to most of the existing methodologies based on regulating formation errors to the pre-defined pattern, the proposed method does not need to involve any information of the desired pattern beforehand. We refer to this type of formation control as intrinsic formation control. Patterns of regular polygons, antipodal formations and Platonic solids can be achieved as Nash equilibria of the game while inter-agent collisions are naturally avoided. Paper C considers the credit scoring problem by incorporating dynamic network information, where the advantages of such incorporation are investigated in two scenarios. Firstly, when the scoring publishment is merely individual--dependent, an optimal Bayesian filter is designed for risk prediction, where network observations are utilized to provide a reference for the bank on future financial decisions. Furthermore, a recursive Bayes estimator is proposed to improve the accuracy of score publishment by incorporating the dynamic network topology as well. It is shown that under the proposed evolution framework, the designed estimator has a higher precision than all the efficient estimators, and the mean square errors are strictly smaller than the Cramér-Rao lower bound for clients within a certain range of scores. / I denna avhandling behandlas tre problem inom optimering för agentbaserade system. Inledningsvis undersöks problemet rörande invers optimal styrning för ett system med en agent. Målet är att, givet en dynamisk process, återskapa den kvadratiska kostnadsfunktionen från observationer av sekvenser av optimal styrning. En sådan uppskattning kan ge ökad förståelse av det underliggande fysikaliska systemet, samt vara behjälplig vid konstruktion av en liknande optimal regulator för andra tillämpningar. Vidare betraktas problem rörande optimering över nätverkssystem. Ett nytt angreppssätt, baserat på differentialspel, föreslås för optimal intrinsisk formationsstyrning av system med fler agenter. För kreditutvärderingsproblemet utnyttjas ett filtreringsramverk för att rekursivt förbättra kreditvärderingens noggrannhet baserat på dynamisk nätverksinformation. I artikel A undersöks problemet med invers optimal styrning med ändlig tidshorisont, där den linjärkvadratiska (LQ) kostnadsfunktionen måste uppskattas från den optimala återkopplingsregulatorn. Trots att det inversa LQ-problemet med oändlig tidshorisont är välstuderat och med flertalet resultat, är fallet med ändlig tidshorisont fortfarande ett öppet problem. Så vitt vi vet presenterar vi det första kompletta resultatet med både tillräckliga och nödvändiga villkor för existens av en motsvarande LQ-kostnadsfunktion. I fallet med lösbara problem härleds ett analytiskt uttryck för hela lösningsrummet och frågan om ekvivalens med viktmatriser behandlas. För de olösbara problemen formuleras ett oändligtdimensionellt konvext optimeringsproblem för att hitta den bästa approximativa lösningen med den minsta styrresidualen. För att underlätta beräkningarna löses optimalitetsvillkoren i ett ramverk för statisk kvadratisk programmering. I artikel B studeras problemet rörande optimal formationsstyrning av ett multiagentsystem. Agenternas svärmbeteende modelleras som ett icke-kooperativt differentialspel med ändlig tidshorisont och enbart lokal information. Vi studerar detta spels Nashjämvikt. Att, ur icke-kooperativa individuella handlingar, härleda ett kollaborativt svärmbeteende kastar nytt ljus på vår förståelse av sådana, i naturen förekommande, fenomen. Det föreslagna ramverket är vägledande i den meningen att det är ett systematiskt tillvägagångssätt för formationsstyrning, där den önskade formeringen kan erhållas genom att endast inbördes justera individuella kostnader samt nätverkstopologin. I motstat till de flesta befintliga metoder, vilka baseras på att reglera felet i formeringen relativt det fördefinierade mönstret, så behöver den föreslagna metoden inte på förhand ta hänsyn till det önskade mönstret. Vi kallar denna typ av formationsstyrning för intrinsisk formationsstyrning. Mönster så som regelbundna polygoner, antipodala formeringar och Platonska kroppar kan uppnås som Nashjämvikter i spelet, samtidigt som kollisioner mellan agenter undviks på ett naturligt sätt. Artikel C behandlar kreditutvärderingsproblemet genom att lägga till dynamisk nätverksinformation. Fördelarna med en sådan integrering undersöks i två scenarier. Då kreditvärdigheten enbart är individberoende utformas ett optimalt Bayesiskt filter för riskvärdering, där observationer från nätverket används för att tillhandahålla en referens för banken på framtida finansiella beslut. Vidare föreslås en rekursiv Bayesisk estimator (stickprovsvariabel) för att förbättra noggrannheten på den skattade kreditvärdigheten genom att integrera även den dynamiska nätverkstopologin. Inom den föreslagna ramverket för tidsutveckling kan vi visa att, för kunder inom ett visst intervall av värderingar, har den utformade estimatorn högre precision än alla effektiva estimatorer och medelkvadrafelet är strikt mindre än den nedre gränsen från Cramér-Raos olikhet. / <p>QC 20190603</p>

Technological advancements have opened up the possibility of digitizing the pathological landscape, enabling deep learning-based methods to analyze digitized tissue samples, i.e., whole slide images (WSIs). Attention has recently shifted toward modeling WSIs as graphs since graph representations can capture dynamic relationships. This thesis investigates different graph construction techniques in conjunction with graph-based deep learning to classify WSIs as breast cancer histological grade 1 versus histological grade 3. To that extent, multiple graph representation techniques and two graph convolutional networks, GCN and GraphSAGE, were utilized. Finally, by evaluating the proposed models on an external test set originating from a separate cohort, it is clear that both models have the capacity for binary histological grading, yielding AUC scores of 0.791 (95% CI 0.756 − 0.825) and 0.838 (95% CI 0.808 − 0.869) for the GCN and GraphSAGE models. Modeling WSIs as graphs is an exciting and emerging field; however, further work is needed to evaluate alternative graph representation techniques and graph convolutional networks. / Teknologiska framsteg har öppnat upp möjligheten att digitalisera det patologiska landskapet, och möjliggjort djupinlärningsbaserade metoder att analysera digitala vävnadsprover; whole slide images (WSIs). Uppmärksamhet har skiftats mot modellering av WSIs som grafer, då grafrepresentationer är dynamiska. Den här uppsatsen undersöker diverse tekniker för grafkonstruktion tillsammans med grafbaserad djupinlärning för att klassificera WSIs som histologisk gradering 1 kontra histologisk gradering 3. För detta ändamål användes flertalet olika grafrepresentationer samt två distinkta grafbaserade faltningsnätverk, GCN och GraphSAGE. Slutligen, genom att evaluera de föreslagna modellerna på ett externt test set, härstammande från en separat kohort, så är det tydligt att båda modellerna har kapacitet för binär histologisk gradering, med AUC-värden på 0.791 (95% CI 0.756 − 0.825) samt 0.838 (95% CI 0.808 − 0.869) för GCN och GraphSAGE. Att modellera WSIs som grafer är ett spännande och framväxande område. Det behövs emellertid mer forskning för att evaluera alternativa tekniker för grafrepresentationer samt grafbaserade faltningsnätverk.