1 |
Motion Planning for Unmanned Aerial Vehicles with Resource ConstraintsSundar, Kaarthik 2012 August 1900 (has links)
Small Unmanned Aerial Vehicles (UAVs) are currently used in several surveillance applications to monitor a set of targets and collect relevant data. One of the main constraints that characterize a small UAV is the maximum amount of fuel the vehicle can carry. In the thesis, we consider a single UAV routing problem where there are multiple depots and the vehicle is allowed to refuel at any depot. The objective of the problem is to find a path for the UAV such that each target is visited at least once by the vehicle, the fuel constraint is never violated along the path for the UAV, and the total length of the path is a minimum. Mixed integer, linear programming formulations are proposed to solve the problem optimally. As solving these formulations to optimality may take a large amount of time, fast and efficient construction and improvement heuristics are developed to find good sub-optimal solutions to the problem. Simulation results are also presented to corroborate the performance of all the algorithms. In addition to the above contributions, this thesis develops an approximation algorithm for a multiple UAV routing problem with fuel constraints.
|
2 |
Multi-Agent Planning and Coordination Under Resource ConstraintsPecora, Federico January 2007 (has links)
The research described in this thesis stems from ROBOCARE1, a three year research project aimed at developing software and robotic technology for providing intelligent support for elderly people. This thesis deals with two problems which have emerged in the course of the project’s development: Multi-agent coordination with scarce resources. Multi-agent planning is concerned with automatically devising plans or strategies for the coordinated enactment of concurrently executing agents. A common realistic constraint in applications which require the coordination of multiple agents is the scarcity of resources for execution. In these cases, concurrency is affected by limited capacity resources, the presence of which modifies the structure of the planning/coordination problem. Specifically, the first part of this thesis tackles this problem in two contexts, namely when planning is carried out centrally (planning from first principles), and in the context of distributed multi-agent coordination. Domain modeling for scheduling applications. It is often the case that the products of research in AI problem solving are employed to develop applications for supporting human decision processes. Our experience in ROBOCARE as well as other domains has often called for the customization of prototypical software for real applications. Yet the gap between what is often a research prototype and a complete decision support system is seldom easy to bridge.The second part of the thesis focuses on this issue from the point of view of scheduling software deployment.Overall, this thesis presents three contributions within the two problems mentioned above. First, we address the issue of planning in concurrent domains in which the complexity of coordination is dominated by resource constraints. To this end, an integrated planning and scheduling architecture is presented and employed to explore the structural trademarks of multi-agent coordination problems in function of their resource-related characteristics. Theoretical and experimental analyses are carried out revealing which planning strategies are most fit for achieving plans which prescribe efficient coordination subject to scarce resources.We then turn our attention to distributed multi-agent coordination techniques (specifically, a distributed constraint optimization (DCOP) reduction of the coordination problem). Again, we consider the issue of achieving coordinated action in the presence of limited resources. Specifically, resource constraints impose n-ary relations among tasks. In addition, as the number of n-ary relations due to resource contention are exponential in the size of the problem, they cannot be extensionally represented in the DCOP representation of the coordination problem. Thus, we propose an algorithm for DCOP which retains the capability to dynamically post n-ary constraints during problem resolution in order to guarantee resource-feasible solutions. Although the approach is motivated by the multi-agent coordination problem, the algorithm is employed to realize a general architecture for n-ary constraint reasoning and posting.Third, we focus on a somewhat separate issue stemming from ROBOCARE, namely a software engineering methodology for facilitating the process of customizing scheduling components in real-world applications. This work is motivated by the strong applicative requirements of ROBOCARE. We propose a software engineering methodology specific to scheduling technology development. Our experience in ROBOCARE as well as other application scenarios has fostered the development of a modeling framework which subsumes the process of component customization for scheduling applications. The framework aims to minimize the effort involved in deploying automated reasoning technology in practise, and is grounded on the use of a modeling language for defining how domain-level concepts are grounded into elements of a technology-specific scheduling ontology.
|
3 |
CONTINUOUSLY IMPROVING IN TOUGH TIMES: OVERCOMING RESOURCE CONSTRAINTS WITH POSITIVE PSYCHOLOGICAL RESOURCESChadwick, Ingrid C. 01 October 2013 (has links)
Individuals and organizations must continuously improve to succeed in today’s competitive economic climate, yet a major dilemma in tough economic conditions is that the resources needed to support such proactive improvement behaviors are limited. Existing theories on organizational resources, stressors, and continuous improvement are relevant yet insufficient for answering the important question of how individuals remain motivated to pursue continuous improvement activities despite minimal organizational resources to support them. Therefore, the goal of this dissertation was to build and test theory on this phenomenon. Inspired by full-cycle research, I began this program of research with a phenomenological study of employees in a manufacturing environment to better understand their appraisals regarding continuous improvement under resource-constrained conditions. The results highlighted the ways in which employees interpret constraints as either a threat or a challenge, and how positive psychological capital (PsyCap) guides these interpretations and subsequent continuous improvement. Informed by this rich data, I proposed a synthesized theoretical model which was tested in two separate contexts. First, I conducted a time-lagged survey study in another resource-constrained environment that demands continuous improvement, namely entrepreneurs launching a new business. To exert more control and to enhance the generalizability of this research, I then conducted an online experiment with participants from various industries and backgrounds. The results of these studies largely supported the theoretical model, documenting in particular the importance of individuals’ challenge appraisals for their ensuing continuous improvement behaviors. The benefits of individuals’ positive psychological resources as a way to enhance the perceived learning opportunities from resource constraints (i.e., challenge appraisal) were also illustrated. Threat appraisals did not produce the expected effects in this context of continuous improvement, and as such, the theoretical model was refined further. Collectively, this research provides answers to the important question of how individuals can find ways to proactively improve in the face of resource constraints, which is a timely and relevant topic across contemporary organizational contexts today. / Thesis (Ph.D, Management) -- Queen's University, 2013-09-27 18:02:23.883
|
4 |
Sensor Control and Scheduling Strategies for Sensor NetworksManfredi, Victoria U. 01 September 2009 (has links)
We investigate sensor control and scheduling strategies to most effectively use the limited resources of an ad hoc network or closed-loop sensor network. In this context, we examine the following three problems. Where to focus sensing? Certain types of sensors, such as cameras or radars, are unable to simultaneously collect high fidelity data from all environmental locations, and thus require some sort of sensing strategy. Considering a meteorological radar network, we show that the main benefits of optimizing sensing over expected future states of the environment are when there are multiple small phenomena in the environment. Considering multiple users, we show that the problem of call admission control (i.e., deciding which sensing requests to satisfy) in the context of a virtualized private sensor network can be solved in polynomial time when sensor requests are divisible or fixed in time. When sensor requests are indivisible but may be shifted in time, we show that the call admission control problem is NP-complete. How to make sensing robust to delayed and dropped packets? In a closed-loop sensor network, data collected by the sensors determines each sensor's future data collection strategy. Network delays, however, constrain the quantity of data received by the time a control decision must be made, and consequently affect the quality of the computed sensor control. We investigate the value of separate handling of sensor control and data traffc, during times of congestion, in a closed-loop sensor network. Grounding our analysis in a meteorological radar network, we show that prioritizing sensor control traffc decreases the round-trip control-loop delay, and thus increases the quantity and quality of the collected data and improves application performance. How to make routing robust to network changes? In wireless sensor and mobile ad-hoc networks, variable link characteristics and node mobility give rise to changing network conditions. We propose a routing algorithm that selects a type of routing subgraph (a braid) that is robust to changes in the network topology. We analytically characterize the reliability of a class of braids and their optimality properties, and give counter-examples to other conjectured optimality properties in a well-structured (grid) network. Comparing with dynamic source routing, we show that braid routing can significantly decrease control overhead while only minimally degrading the number of packets delivered, with gains dependent on node density.
|
5 |
Test Scheduling with Power and Resource Constraints for IEEE P1687Asani, Golnaz January 2012 (has links)
IEEE P1687 (IJTAG) is proposed to add more exibility|compared with IEEE 1149.1 JTAG|for accessing on-chip embedded test features called instruments. This exibility makes it possible to include and exclude instruments from the scan path. To reach a minimal test time, all instruments should be accessed concurrently. However, constraints such as power and resource constraints might limit concurrency. There is a need to consider power and resource constraints while developing the test schedule. This thesis consists of two parts. In the rst part, three test time calculation approaches, namely session-based test schedule with a xed scan path, session-based test schedule with a recongurable scan path, and session-less test schedule with a recongurable scan path are proposed. In the second part, three test scheduling approaches, namely session-based test scheduling, optimized session-based test scheduling, and optimized session-less test scheduling are studied and three algorithms are presented for each of the test scheduling approaches. Experiments are carried out using the test scheduling approaches and the results show that optimized sessionless test scheduling can signicantly reduce the test time compared with session-based test scheduling.
|
6 |
A Genetic Algorithm For The Resource Constrained Project Scheduling ProblemOzleyen, Erdem 01 October 2011 (has links) (PDF)
The resource-constrained project scheduling problem (RCPSP) aims to find a
schedule of minimum makespan by starting each activity such that resource
constraints and precedence constraints are respected. However, as the problem
is NP-hard (Non-Deterministic Polynomial-Time Hard) in the strong sense, the
performance of exact procedures is limited and can only solve small-sized
project networks. In this study a genetic algorithm is proposed for the RCPSP.
The proposed genetic algorithm (GA) aims to find near-optimal solutions and
also overcomes the poor performance of the exact procedures for large-sized
project networks. Contrarily to a traditional GA, the proposed algorithm
employs two independent populations: left population that consist of leftjustified
(forward) schedules and right population that consist of right-justified
(backward) schedules. The repeated cycle updates the left (right) population by
maintaining it with transformed right (left) individuals. By doing so, the
algorithm uses two different scheduling characteristics. Moreover, the
algorithm provides a new two-point crossover operator that selects the parents
according to their resource requirement mechanism. The algorithm also
includes a modified mutation operator which just accepts the improved
solutions. Experiment results show that the suggested algorithm outperforms the well
known commercial software packages / Primavera Project Planner (P6 version
7.0) and Microsoft Project 2010 for the RCPSP. In addition, the algorithm is
tested with problems obtained from literature as well as the benchmark
PSPLIB (Project Scheduling Problem Library) problems. The proposed
algorithm obtained satisfactory results especially for the problems with 120 and
300 activities. Limitations of the proposed genetic algorithm are addressed and
possible further studies are advised.
|
7 |
Resource constraints and sustainable entrepreneurship in sub-Saharan Africa: An effectual viewDawa, Samuel G. January 2018 (has links)
The study seeks to explain how sustainable entrepreneurship occurs in a resource constrained setting. This is important as it improves our understanding of how entrepreneurs respond to adversity and develop opportunities that jointly address the social, environmental and economic dimensions of entrepreneurship.
Previous research has discussed the antecedents, outcomes and contextual conditions that drive sustainable entrepreneurship. However, what is absent from this growing research body is knowledge of the mechanisms through which individuals engage in this type of entrepreneurship.
The study seeks to answer the following research question: “How do individuals faced with resource constraints engage in sustainable entrepreneurship?” Using effectuation as a lens, a multi-method qualitative approach based on multiple case studies was adopted in this research and a mix of inductive and deductive analyses, also referred to as abductive analysis was employed. A sample of 5 sustainable enterprises were purposively selected in Uganda, located in sub-Saharan Africa.
The results show that resource constraints compel the entrepreneurs to seek expertise and resources from others with mutual goals while controlling expenses. In the process the entrepreneur learns and adapts to the emergent opportunity. The entrepreneur’s actions are further influenced by passion that sustains the activity in the face of challenges. In this research, sustainable entrepreneurship is further explicated showing that the social, economic and environmental objectives exist in a state of shifting, supportive interaction of one another.
The study clarifies our understanding of how entrepreneurs cope with inadequate resources. It explains the mechanisms through which individuals contending with resource constraints employ control as opposed to prediction strategies to exploit entrepreneurship opportunities. In this way the study contributes to the literature by proposing the fusion of cognitive and affective dimensions in realizing sustainable entrepreneurship goals. The study further suggests that the multiple objectives that typify the pursuits of sustainable entrepreneurs serve as supportive mechanisms and this puts into question arguments that these firms face comparatively larger challenges than those that singularly pursue economic objectives. / Thesis (PhD)--University of Pretoria, 2018. / Gordon Institute of Business Science (GIBS) / PhD / Unrestricted
|
8 |
Deployment and Integrity Verification of Streaming IoT Applications on Edge ComputingLou, Shuangsheng 09 August 2022 (has links)
No description available.
|
9 |
Adaptive Middleware for Self-Configurable Embedded Real-Time Systems : Experiences from the DySCAS Project and Remaining ChallengesPersson, Magnus January 2009 (has links)
<p>Development of software for embedded real-time systems poses severalchallenges. Hard and soft constraints on timing, and usually considerableresource limitations, put important constraints on the development. Thetraditional way of coping with these issues is to produce a fully static design,i.e. one that is fully fixed already during design time.Current trends in the area of embedded systems, including the emergingopenness in these types of systems, are providing new challenges for theirdesigners – e.g. integration of new software during runtime, software upgradeor run-time adaptation of application behavior to facilitate better performancecombined with more ecient resource usage. One way to reach these goals is tobuild self-configurable systems, i.e. systems that can resolve such issues withouthuman intervention. Such mechanisms may be used to promote increasedsystem openness.This thesis covers some of the challenges involved in that development.An overview of the current situation is given, with a extensive review ofdi erent concepts that are applicable to the problem, including adaptivitymechanisms (incluing QoS and load balancing), middleware and relevantdesign approaches (component-based, model-based and architectural design).A middleware is a software layer that can be used in distributed systems,with the purpose of abstracting away distribution, and possibly other aspects,for the application developers. The DySCAS project had as a major goaldevelopment of middleware for self-configurable systems in the automotivesector. Such development is complicated by the special requirements thatapply to these platforms.Work on the implementation of an adaptive middleware, DyLite, providingself-configurability to small-scale microcontrollers, is described andcovered in detail. DyLite is a partial implementation of the concepts developedin DySCAS.Another area given significant focus is formal modeling of QoS andresource management. Currently, applications in these types of systems arenot given a fully formal definition, at least not one also covering real-timeaspects. Using formal modeling would extend the possibilities for verificationof not only system functionality, but also of resource usage, timing and otherextra-functional requirements. This thesis includes a proposal of a formalismto be used for these purposes.Several challenges in providing methodology and tools that are usablein a production development still remain. Several key issues in this areaare described, e.g. version/configuration management, access control, andintegration between di erent tools, together with proposals for future workin the other areas covered by the thesis.</p> / <p>Utveckling av mjukvara för inbyggda realtidssystem innebär flera utmaningar.Hårda och mjuka tidskrav, och vanligtvis betydande resursbegränsningar,innebär viktiga inskränkningar på utvecklingen. Det traditionellasättet att hantera dessa utmaningar är att skapa en helt statisk design, d.v.s.en som är helt fix efter utvecklingsskedet.Dagens trender i området inbyggda system, inräknat trenden mot systemöppenhet,skapar nya utmaningar för systemens konstruktörer – exempelvisintegration av ny mjukvara under körskedet, uppgradering av mjukvaraeller anpassning av applikationsbeteende under körskedet för att nå bättreprestanda kombinerat med e ektivare resursutnyttjande. Ett sätt att nå dessamål är att bygga självkonfigurerande system, d.v.s. system som kan lösa sådanautmaningar utan mänsklig inblandning. Sådana mekanismer kan användas föratt öka systemens öppenhet.Denna avhandling täcker några av utmaningarna i denna utveckling. Enöversikt av den nuvarande situationen ges, med en omfattande genomgångav olika koncept som är relevanta för problemet, inklusive anpassningsmekanismer(inklusive QoS och lastbalansering), mellanprogramvara och relevantadesignansatser (komponentbaserad, modellbaserad och arkitekturell design).En mellanprogramvara är ett mjukvarulager som kan användas i distribueradesystem, med syfte att abstrahera bort fördelning av en applikation överett nätverk, och möjligtvis även andra aspekter, för applikationsutvecklarna.DySCAS-projektet hade utveckling av mellanprogramvara för självkonfigurerbarasystem i bilbranschen som ett huvudmål. Sådan utveckling försvåras avde särskilda krav som ställs på dessa plattformarArbete på implementeringen av en adaptiv mellanprogramvara, DyLite,som tillhandahåller självkonfigurerbarhet till småskaliga mikrokontroller,beskrivs och täcks i detalj. DyLite är en delvis implementering av konceptensom utvecklats i DySCAS.Ett annat område som får särskild fokus är formell modellering av QoSoch resurshantering. Idag beskrivs applikationer i dessa områden inte heltformellt, i varje fall inte i den mån att realtidsaspekter täcks in. Att användaformell modellering skulle utöka möjligheterna för verifiering av inte barasystemfunktionalitet, men även resursutnyttjande, tidsaspekter och andraicke-funktionella krav. Denna avhandling innehåller ett förslag på en formalismsom kan användas för dessa syften.Det återstår många utmaningar innan metodik och verktyg som är användbarai en produktionsmiljö kan erbjudas. Många nyckelproblem i områdetbeskrivs, t.ex. versions- och konfigurationshantering, åtkomststyrning ochintegration av olika verktyg, tillsammans med förslag på framtida arbete iövriga områden som täcks av avhandlingen.</p> / DySCAS
|
10 |
Passage à l'échelle pour les contraintes d'ordonnancement multi-ressources / Scalable multi-dimensional resources scheduling constraintsLetort, Arnaud 28 October 2013 (has links)
La programmation par contraintes est une approche régulièrement utilisée pour résoudre des problèmes combinatoires d’origines diverses. Dans cette thèse nous nous focalisons sur les problèmes d’ordonnancement cumulatif. Un problème d’ordonnancement consiste à déterminer les dates de débuts et de fins d’un ensemble de tâches, tout en respectant certaines contraintes de capacité et de précédence. Les contraintes de capacité concernent aussi bien des contraintes cumulatives classiques où l’on restreint la somme des hauteurs des tâches intersectant un instant donné, que des contraintes cumulatives colorées où l’on restreint le nombre maximum de couleurs distinctes prises par les tâches. Un des objectifs récemment identifiés pour la programmation par contraintes est de traiter des problèmes de grandes tailles, habituellement résolus à l’aide d’algorithmes dédiés et de métaheuristiques. Par exemple, l’utilisation croissante de centres de données virtualisés laisse apparaitre des problèmes d’ordonnancement et de placement multi-dimensionnels de plusieurs milliers de tâches. Pour atteindre cet objectif, nous utilisons l’idée de balayage synchronisé considérant simultanément une conjonction de contraintes cumulative et des précédences, ce qui nous permet d’accélérer la convergence au point fixe. De plus, de ces algorithmes de filtrage nous dérivons des procédures gloutonnes qui peuvent être appelées à chaque nœud de l’arbre de recherche pour tenter de trouver plus rapidement une solution au problème. Cette approche permet de traiter des problèmes impliquant plus d’un million de tâches et 64 ressources cumulatives. Ces algorithmes ont été implémentés dans les solveurs de contraintes Choco et SICStus, et évalués sur divers problèmes déplacement et d’ordonnancement. / Constraint programming is an approach often used to solve combinatorial problems in different application areas. In this thesis we focus on the cumulative scheduling problems. A scheduling problem is to determine the starting dates of a set of tasks while respecting capacity and precedence constraints. Capacity constraints affect both conventional cumulative constraints where the sum of the heights of tasks intersecting a given time point is limited, and colored cumulative constraints where the number of distinct colors assigned to the tasks intersecting a given time point is limited. A newly identified challenge for constraint programming is to deal with large problems, usually solved by dedicated algorithms and metaheuristics. For example, the increasing use of virtualized datacenters leads to multi dimensional placement problems of thousand of jobs. Scalability is achieved by using a synchronized sweep algorithm over the different cumulative and precedence constraints that allows to speed up convergence to the fix point. In addition, from these filtering algorithms we derive greedy procedures that can be called at each node of the search tree to find a solution more quickly. This approach allows to deal with scheduling problems involving more than one million jobs and 64 cumulative resources. These algorithms have been implemented within Choco and SICStussolvers and evaluated on a variety of placement and scheduling problems.
|
Page generated in 0.1 seconds