With the proliferation of fairly powerful mobile devices and ubiquitous wireless technology, traditional mobile ad hoc networks (MANETs) now migrate into a new era of service-oriented MANETs wherein a node can provide and receive service from other nodes it encounters and interacts with. This dissertation research concerns trust management and its applications for service-oriented MANETs to answer the challenges of MANET environments, including no centralized authority, dynamically changing topology, limited bandwidth and battery power, limited observations, unreliable communication, and the presence of malicious nodes who act to break the system functionality as well as selfish nodes who act to maximize their own gain. We propose a context-aware trust management model called CATrust for service-oriented ad hoc networks. The novelty of our design lies in the use of logit regression to dynamically estimate trustworthiness of a service provider based on its service behavior patterns in a context environment, treating channel conditions, node status, service payoff, and social disposition as 'context' information. We develop a recommendation filtering mechanism to effectively screen out false recommendations even in extremely hostile environments in which the majority recommenders are malicious. We demonstrate desirable convergence, accuracy, and resiliency properties of CATrust. We also demonstrate that CATrust outperforms contemporary peer-to-peer and Internet of Things trust models in terms of service trust prediction accuracy against collusion recommendation attacks. We validate the design of trust-based service management based on CATrust with a node-to-service composition and binding MANET application and a node-to-task assignment MANET application with multi-objective optimization (MOO) requirements. For either application, we propose a trust-based algorithm to effectively filter out malicious nodes exhibiting various attack behaviors by penalizing them with trust loss, which ultimately leads to high user satisfaction. Our trust-based algorithm is efficient with polynomial runtime complexity while achieving a close-to-optimal solution. We demonstrate that our trust-based algorithm built on CATrust outperforms a non-trust-based counterpart using blacklisting techniques and trust-based counterparts built on contemporary peer-to-peer trust protocols. We also develop a dynamic table-lookup method to apply the best trust model parameter settings upon detection of rapid MANET environment changes to maximize MOO performance. / Ph. D.

Multi-criteria scheduling provides the opportunity to create mathematical optimization models that are applicable to a diverse set of problem domains in the business world. This research addresses two different employee scheduling applications using multi-criteria objectives that present decision makers with trade-offs between global optimality and the level of disruption to current operating resources. Additionally, it investigates a scheduling problem from the product testing domain and proposes a heuristic solution technique for the problem that is shown to produce very high-quality solutions in short amounts of time. Chapter 2 addresses a grant administration workload-to-staff assignment problem that occurs in the Office of Research and Sponsored Programs at land-grant universities. We identify the optimal workload assignment plan which differs considerably due to multiple reassignments from the current state. To achieve the optimal workload reassignment plan we demonstrate a technique to identify the n best reassignments from the current state that provides the greatest progress toward the utopian solution. Solving this problem over several values of n and plotting the results allows the decision maker to visualize the reassignments and the progress achieved toward the utopian balanced workload solution. Chapter 3 identifies a weekly schedule that seeks the most cost-effective set of coach-to-program assignments in a gymnastics facility. We identify the optimal assignment plan using an integer linear programming model. The optimal assignment plan differs greatly from the status quo; therefore, we utilize a similar approach from Chapter 2 and use a multiple objective optimization technique to identify the n best staff reassignments. Again, the decision maker can visualize the trade-off between the number of reassignments and the resulting progress toward the utopian staffing cost solution and make an informed decision about the best number of reassignments. Chapter 4 focuses on product test scheduling in the presence of in-process and at-completion inspection constraints. Such testing arises in the context of the manufacture of products that must perform reliably in extreme environmental conditions. Each product receives a certification at the successful completion of a predetermined series of tests. Operational efficiency is enhanced by determining the optimal order and start times of tests so as to minimize the make span while ensuring that technicians are available when needed to complete in-process and at-completion inspections We first formulate a mixed-integer programming model (MILP) to identify the optimal solution to this problem using IBM ILOG CPLEX Interactive Optimizer 12.7. We also present a genetic algorithm (GA) solution that is implemented and solved in Microsoft Excel. Computational results are presented demonstrating the relative merits of the MILP and GA solution approaches across a number of scenarios. / Ph. D. / Multi-criteria scheduling provides the opportunity to create mathematical optimization models that are applicable to a diverse set of problem domains in the business world. This research addresses two different employee scheduling applications using multi-criteria objectives that present decision makers with trade-offs between global optimality and the level of disruption to current operating resources. Additionally, it investigates a scheduling problem from the product testing domain and proposes a heuristic solution technique for the problem that is shown to produce very high-quality solutions in short amounts of time. Chapter 2 addresses a grant administration workload-to-staff assignment problem that occurs in the Office of Research and Sponsored Programs at land-grant universities. Solving this problem and plotting the results allows the decision maker to visualize the number of reassignments and the progress achieved toward the utopian balanced workload solution. Chapter 3 identifies a weekly schedule that seeks the most cost-effective set of coach-to-program assignments in a gymnastics facility. Again, the decision maker can visualize the trade-off between the number of reassignments and the resulting progress toward the utopian staffing cost solution and make an informed decision about the best number of reassignments. Chapter 4 focuses on product test scheduling in the presence of in-process and at-completion inspection constraints. Such testing arises in the context of the manufacture of products that must perform reliably in extreme environmental conditions. Each product receives a certification at the successful completion of a predetermined series of tests. Computational results are presented demonstrating the relative merits of the mixed integer linear programming model and the genetic algorithm solution approaches across a number of scenarios.

Dans cette thèse, nous étudions des algorithmes pour le monitoring des traces d’activité à grande échelle. Le monitoring est une aptitude clé dans plusieurs domaines, permettant d’extraire de la valeur des données ou d’améliorer les performances d’un système. Nous explorons d’abord le monitoring de données temporelles. Nous présentons un nouveau type de jointure sur des intervalles, qui inclut des fonctions de score caractérisant le degré de satisfaction de prédicats temporels. Nous étudions ces jointures dans le contexte du batch processing (traitement par lots). Nous formalisons la Ranked Temporal Join (RTJ), une jointure qui combine des collections d’intervalles et retourne les k meilleurs résultats. Nous montrons comment exploiter les propriétés des prédicats temporels et de la sémantique de score associée afin de concevoir TKIJ , une méthode d’évaluation de requête distribuée basée sur Map-Reduce. Nos expériences sur des données synthétiques et réelles montrent que TKIJ est plus performant que les techniques de l’état de l’art et démontre de bonnes performances sur des requêtes RTJ n-aires sur des données temporelles. Nous proposons également une étude préliminaire afin d’étendre nos travaux sur TKIJ au domaine du stream processing (traitement de flots). Nous explorons ensuite le monitoring dans le crowdsourcing (production participative). Nous soutenons la nécessité d’intégrer la motivation des travailleurs dans le processus d’affectation des tâches. Nous proposons d’étudier une approche adaptative, qui évalue la motivation des travailleurs lors de l’exécution des tâches et l’exploite afin d’améliorer l’affectation de tâches qui est réalisée de manière itérative. Nous explorons une première variante nommée Individual Task Assignment (Ita), dans laquelle les tâches sont affectées individuellement, un travailleur à la fois. Nous modélisons Ita et montrons que ce problème est NP-Difficile. Nous proposons trois méthodes d’affectation de tâches qui poursuivent différents objectifs. Nos expériences en ligne étudient l’impact de chaque méthode sur la performance globale dans l’exécution de tâches. Nous observons que différentes stratégies sont dominantes sur les différentes dimensions de performance. En particulier, la méthode affectant des tâches aléatoires et correspondant aux intérêts d’un travailleur donne le meilleur flux d’exécution de tâches. La méthode affectant des tâches correspondant au compromis d’un travailleur entre diversité et niveau de rémunération des tâches donne le meilleur niveau de qualité. Nos expériences confirment l’utilité d’une affectation de tâches adaptative et tenant compte de la motivation. Nous étudions une deuxième variante nommée Holistic Task Assignment (Hta), où les tâches sont affectées à tous les travailleurs disponibles, de manière holistique. Nous modélisons Hta et montrons que ce problème est NP-Difficile et MaxSNP-Difficile. Nous développons des algorithmes d’approximation pour Hta. Nous menons des expériences sur des données synthétiques pour évaluer l’efficacité de nos algorithmes. Nous conduisons également des expériences en ligne et comparons notre approche avec d’autres stratégies non adaptatives. Nous observons que notre approche présente le meilleur compromis sur les différentes dimensions de performance. / In this thesis, we study scalable algorithms for monitoring activity traces. In several domains, monitoring is a key ability to extract value from data and improve a system. This thesis aims to design algorithms for monitoring two kinds of activity traces. First, we investigate temporal data monitoring. We introduce a new kind of interval join, that features scoring functions reflecting the degree of satisfaction of temporal predicates. We study these joins in the context of batch processing: we formalize Ranked Temporal Join (RTJ), that combine collections of intervals and return the k best results. We show how to exploit the nature of temporal predicates and the properties of their associated scored semantics to design TKIJ , an efficient query evaluation approach on a distributed Map-Reduce architecture. Our extensive experiments on synthetic and real datasets show that TKIJ outperforms state-of-the-art competitors and provides very good performance for n-ary RTJ queries on temporal data. We also propose a preliminary study to extend our work on TKIJ to stream processing. Second, we investigate monitoring in crowdsourcing. We advocate the need to incorporate motivation in task assignment. We propose to study an adaptive approach, that captures workers’ motivation during task completion and use it to revise task assignment accordingly across iterations. We study two variants of motivation-aware task assignment: Individual Task Assignment (Ita) and Holistic Task Assignment (Hta). First, we investigate Ita, where we assign tasks to workers individually, one worker at a time. We model Ita and show it is NP-Hard. We design three task assignment strategies that exploit various objectives. Our live experiments study the impact of each strategy on overall performance. We find that different strategies prevail for different performance dimensions. In particular, the strategy that assigns random and relevant tasks offers the best task throughput and the strategy that assigns tasks that best match a worker’s compromise between task diversity and task payment has the best outcome quality. Our experiments confirm the need for adaptive motivation-aware task assignment. Then, we study Hta, where we assign tasks to all available workers, holistically. We model Hta and show it is both NP-Hard and MaxSNP-Hard. We develop efficient approximation algorithms with provable guarantees. We conduct offline experiments to verify the efficiency of our algorithms. We also conduct online experiments with real workers and compare our approach with various non-adaptive assignment strategies. We find that our approach offers the best compromise between performance dimensions thereby assessing the need for adaptability.

No description available.

The security of multi-robot systems is critical in various applications such as patrol, transportation, and search and rescue operations, where they face threats from adversaries attempting to gain control of the robots. These compromised robots are significant threats as they allow attackers to steer robots towards forbidden areas without being detected, potentially causing harm or compromising the mission. To address this problem, we propose a resilient planning, task assignment, and control framework. The proposed framework builds a multi-robot plan where robots are designed to get close enough to other robots according to a co-observation schedule, in order to mutually check for abnormal behaviors. For the first part of the thesis, we propose an optimal trajectory solver based on the alternating direction method of multipliers (ADMM) to generate multi-agent trajectories that satisfy spatio-temporal requirements introduced by the co-observation schedules. As part of the formulation, we provide a new reachability constraint to guarantee that, despite adversarial movement by the attacker, a compromised robot cannot reach forbidden areas between co-observations without being detected. In the second part of the thesis, to further enhance the system's performance, reliability, and robustness, we propose to deploy multiple robots on each route to form sub-teams. A new cross-trajectory co-observation scheme between sub-teams is introduced that preserves the optimal unsecured trajectories. The new planner ensures that at least one robot in each sub-team sticks to the planned trajectories, while sub-teams can constantly exchange robots during the task introducing additional co-observations that can secure originally unsecured routes. We show that the planning of cross-trajectory co-observations can be transformed into a network flow problem and solved using traditional linear program technique. In the final part of the thesis, we show that the introduction of sub-teams also improves the multi-robot system's robustness to unplanned situations, allowing servicing unplanned online events without breaking the security requirements. This is achieved by a distributed task assignment algorithm based on consensus ADMM which can handle tasks with different priorities. The assignment result and security requirements are formulated as spatio-temporal schedules and guaranteed through control barrier function (CBF) based controls.

<p>Polazeći od prostog aukcijskog algoritma (SAP) za izbor izvršioca u<br />bežičnim senzorskim i aktuatorskim mrežama u ovoj disertaciji su<br />uvedena dva poboljšanja tog algoritma (multi-hop komunikacija i<br />lokalizacija). Predloženo je i pet novih aukcijskih agregacionih<br />algoritama koji koriste tehniku agregacije da bi smanjili<br />komunikacione troškove. Treća grupa doprinosa ove disertacije se<br />odnosi na primenu aukcija za poboljšanje postojećeg iMesh algoritma<br />za pronalaženje izvršioca. Eksperimentalni rezultati pokazuju<br />svojstva algoritama i njihove prednosti u odnosu na postojeće.</p> / <p>Two improvements of the simple auction protocol (SAP) for the task<br />assignment in wireless sensor and actuator networks is proposed in this<br />dissertation (multi-hop communications and localization). Five new auction<br />aggregation algorithms for the task assignment are proposed with the goal to<br />minimize the communication costs. One of the auction aggregation algorithms<br />is also used to improve existing iMesh service discovery algorithm.<br />Experimental results show the characteristics of the proposed algorithms and<br />advantages over the existing ones.</p>

The main problem analyzed in this work was the need to design and create an internal management system for small and medium enterprices, that would meet their particular requests on usability, extensibility and adaptability at available costs. As solution to this problem was deep analysis of available systems of that kind, and creation of our own system, that had met necessary requirements and even more – had some technological improvements, such as reduced number of users actions, necessary to make things done. This was implemented with the help of AJAX programming technique and a special framework, created for this system. This system can be used to manage projects in a small or medium enterprice, collect statistics about projects, staff work, distribute project tasks to staff and monitor the implementation. There also is an oportunity to generate various reports, such as summary of accomplished tasks for every employee, lists of project tasks and their status and so on. This system can be easily installed in any enterprice because of it‘s client – server architecture, where client connects to the server with the help of a web browser, that can be found in every computer, so there is no need to install system in all computers in enterprice. In that way maintenance costs are reduced, because all you have to look after is server with a system on it.

Made available in DSpace on 2016-06-02T19:52:03Z (GMT). No. of bitstreams: 1 DissFSS.pdf: 471874 bytes, checksum: 52bc0458fea36b975556da8d0d9d80ca (MD5) Previous issue date: 2003-08-14 / This work consists in the development of genetic algorithms for the Task-to-Processo Assignment Problem in multiprocessor applications. Specifically, the objective is to find the task-to-processor assignment that minimizes the total delay in a particular multiprocessor digital signal processing architecture. We present a description of our algorithm implementations and the results found with a set of 117 randomly generated and real-life instances. The algorithms performance is compared with the results provided by a competitive dynamic list heuristic and a multiple start search algorithm. The results indicate lower delays in more than 68% of the instances, at a higher computational cost. / O objetivo deste projeto consiste no desenvolvimento de algoritmos genéticos para resolução do problema de designação de tarefas em multiprocessadores de processamento digital de sinal (PDS). Especificamente, busca-se minimizar o atraso total em uma arquitetura de multiprocessadores particular, bastante utilizada em sistemas reais. Neste trabalho são apresentadas implementações de algoritmos genéticos, e os resultados computacionais decorrentes de sua aplicação a um conjunto de 117 exemplos gerados aleatoriamente e extraídos de contextos reais. O desempenho dos algoritmos é analisado, comparando-se a qualidade das soluções e os tempos computacionais requeridos com os obtidos por uma heurística competitiva da literatura e por um algoritmo de busca multiple starts. Os algoritmos genéticos obtiveram menores valores de atraso em mais de 68% dos exemplos, a um tempo computacional maior.

<div>The goal of this research is to develop a method of control for a team of unmanned aerial and ground robots that is resilient, robust, and scalable given both complete and incomplete information of the environment. The method presented in this paper integrates approximate and optimal methods of path planning integrated with a market-based task allocation strategy. Further work presents a solution to unmanned ground vehicle path planning within the developed mission planning system framework under incomplete information. Deep reinforcement learning is proposed to solve movement through unknown terrain environment. The final demonstration for Advantage-Actor Critic deep reinforcement learning elicits successful implementation of the proposed model.</div>

For unmanned vehicles, autonomy means that the vehicle’s route can be planned and executed according to some pre-defined rules in the absence of human intervention. Autonomous vehicles (AVs) have become a common type of vehicle for various kinds of transport, for example autonomous forklifts within a warehouse environment. Volvo Autonomous Solution (VAS) works with autonomous vehicles in different areas. To better understand how different methods can be used for planning of autonomous vehicles, VAS initiated this project. To increase the efficiency of AVs, several problems can be examined. One such problem is the allocation problem, also called Multi-Robot Task Allocation, which aims to find out which vehicle should execute which task to achieve a global goal cooperatively. The AVs used by VAS handle Planning Missions (PMs). A PM is, for example, to move goods from a loading point to an unloading point. So, the problem examined in this study is how to assign PMs to vehicles in the most efficient way. The thesis also includes a collection of publications on the area. The problem is solved by using three methods: Mixed Integer Linear Programming (MILP), a Genetic Algorithm that was originally proposed for task assignment in a warehouse environment (GA – Warehouse), and a Genetic Algorithm that was initially proposed for train scheduling (GA – Train). With the MILP method, the problem has been formulated mathematically and the method guarantees an optimal solution. However, the major drawback of this approach is the large computational time required to retrieve a solution. The GA – Warehouse method has a quite simple allocation process but a more complicated path planning part and is, in its entirety, not as flexible as the other methods. The GA – Train method has a lower computational time and can consider many different aspects. All three methods generate similar solutions for the limited set of simple scenarios in this study, but an optimal solution can only be guaranteed by the MILP method. Regardless of which method is used, there is always a trade-off: a guarantee of the optimal solution at the expense of high computational time or a result where no optimal solution can be guaranteed but can be generated quickly. Which method to use depends on the context, what resources are available, and what requirements are placed on the solution. / <p>Examensarbetet är utfört vid Institutionen för teknik och naturvetenskap (ITN) vid Tekniska fakulteten, Linköpings universitet</p>