To see the other types of publications on this topic, follow the link: Task allocation to sensors.
Dissertations / Theses on the topic 'Task allocation to sensors'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Task allocation to sensors.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Pizzocaro, Diego. "Instantaneous multi-sensor task allocation in static and dynamic environments." Thesis, Cardiff University, 2011. http://orca.cf.ac.uk/31333/.
Full textAbstract:
A sensor network often consists of a large number of sensing devices of different types. Upon deployment in the field, these sensing devices form an ad hoc network using wireless links or cables to communicate with each other. Sensor networks are increasingly used to support emergency responders in the field usually requiring many sensing tasks to be supported at the same time. By a sensing task we mean any job that requires some amount of sensing resources to be accomplished such as localizing persons in need of help or detecting an event. Tasks might share the usage of a sensor, but more often compete to exclusively control it because of the limited number of sensors and overlapping needs with other tasks. Sensors are in fact scarce and in high demand. In such cases, it might not be possible to satisfy the requirements of all tasks using available sensors. Therefore, the fundamental question to answer is: “Which sensor should be allocated to which task?", which summarizes the Multi-Sensor Task Allocation (MSTA) problem. We focus on a particular MSTA instance where the environment does not provide enough information to plan for future allocations constraining us to perform instantaneous allocation. We look at this problem in both static setting, where all task requests from emergency responders arrive at once, and dynamic setting, where tasks arrive and depart over time. We provide novel solutions based on centralized and distributed approaches. We evaluate their performance using mainly simulations on randomly generated problem instances; moreover, for the dynamic setting, we consider also feasibility of deploying part of the distributed allocation system on user mobile devices. Our solutions scale well with different number of task requests and manage to improve the utility of the network, prioritizing the most important tasks.
2
Viguria, Jimenez Luis Antidio. "Distributed Task Allocation Methodologies for Solving the Initial Formation Problem." Thesis, Georgia Institute of Technology, 2008. http://hdl.handle.net/1853/24731.
Full textAbstract:
Mobile sensor networks have been shown to be a powerful tool for enabling a number of activities that require recording of environmental parameters at various spatial and temporal distributions. These mobile sensor networks could be implemented using a team of robots, usually called robotic sensor networks.
This type of sensor network involves the coordinated control of multiple robots to achieve specific measurements separated by varied distances. In most formation measurement applications, initialization involves identifying a number of interesting sites to which mobility platforms, instrumented with a variety of sensors, are tasked. This process of determining which
instrumented robot should be tasked to which location can be viewed as solving the task allocation problem.
Unfortunately, a centralized approach does not fit in this type of application due to the fault tolerance requirements. Moreover, as the size of the network grows, limitations in bandwidth severely limits the possibility of conveying and using global information. As such, the utilization of decentralized techniques for forming new sensor topologies and configurations is a highly desired quality of robotic sensor networks.
In this thesis, several distributed task allocation algorithms will be explained and compared in different scenarios. They are based on a market approach since our interest is not only to obtain a feasible solution, but also an efficient one. Also, an analysis of the efficiency of those algorithms using probabilistic techniques will be explained.
Finally, the task allocation algorithms will be implemented on a real system consisted of a team of six robots and integrated in a complete robotic system that considers obstacle avoidance and path planning. The results will be validated in both simulations and real experiments.
3
PILLONI, VIRGINIA. "Dynamic deployment of applications in wireless sensor networks." Doctoral thesis, Università degli Studi di Cagliari, 2013. http://hdl.handle.net/11584/266095.
Full textAbstract:
Over the past decades, the progress inWirelss Sensor Network (WSN) technology, both in terms of processing capability and energy consumption reduction, has evolved WSNs into complex systems that can gather information about the monitored environment and make prompt and intelligent decisions. In the beginning, military applications drove the research and development of WSNs, with large-scale acoustic systems for underwater surveillance, radar systems
for the collection of data on air targets, and Unattended Ground Sensor (UGS) systems for ground target detection. Typical civil WSNs are basically not complex monitoring systems, whose applications encompass environment and habitat monitoring, infrastructure security and
terror threat alerts, industrial sensing for machine health monitoring, and traffic control. In these WSNs, sensors gather the required information, mostly according to a fixed temporal schedule, and send it to the sink, which interfaces with a server or a computer. Only at this point data from sensors can be processed, before being stored.
Recent advances in Micro-Eletro-Mechanical Systems (MEMS), low power transceivers and microprocessor dimensions have led to cost effective tiny sensor devices that combine sensing with computation, storage and communication. These developments have contributed to the efforts on interfacing WSNs with other technologies, enabling them to be one of the pillars of the Internet of Things (IoT) paradigm. In this context, WSNs take a key role in application
areas such as domotics, assisted living, e-health, enhanced learning automation and industrial manufacturing logistics, business/process management, and intelligent transportation of people and goods. In doing so, a horizontal ambient intelligent infrastructure is made possible, wherein
the sensing, computing and communicating tasks can be completed using programmable middleware that enables quick deployment of different applications and services.
One of the major issues with WSNs is the energy scarcity, due to the fact that sensors are mainly battery powered. In several cases, nodes are deployed in hostile or unpractical environments, such as underground or underwater, where replacing battery could be an unfeasible operation. Therefore, extending the network lifetime is a crucial concern. Lifetime improvement has been approached by many recent studies, from different points of view, including
node deployment, routing schemes, and data aggregation Recently, with the consistent increase in WSN application complexity, the way distributed applications are deployed in WSNs is another important component that affects the network lifetime. For instance, incorrect execution of data processing in some nodes or the transmission
of big amounts of data with low entropy in some nodes could heavily deplete battery energy without any benefit. Indeed, application tasks are usually assigned statically to WSN nodes, which is an approach in contrast with the dynamic nature of future WSNs, where nodes frequently join and leave the network and applications change over the time. This brings to issue talked in this thesis, which is defined as follows. Dynamic deployment of distributed applications in WSNs: given the requirements of WSN
applications, mostly in terms of execution time and data processing, the optimal allocation of tasks among the nodes should be identified so as to reach the application target and to satisfy the requirements while optimizing the network performance in terms of network lifetime. This
issue should be continuously addressed to dynamically adapt the system to changes in terms of application requirements and network topology.
4
Quentel, Paul. "Architecture multi-agent distribuée et collaborative pour l’allocation de tâches à des senseurs : application aux systèmes navals." Electronic Thesis or Diss., Ecole nationale supérieure Mines-Télécom Atlantique Bretagne Pays de la Loire, 2024. http://www.theses.fr/2024IMTA0406.
Full textAbstract:
L’évolution du contexte de défense aéronaval nécessite une modification majeure de l’architecture des systèmes de senseurs actuels afin de maitriser les futures menaces et d’intégrer les nouveaux dispositifs et senseurs à venir. Ces senseurs, hétérogènes, complémentaires et embarqués sur des plateformes navales ou aériennes, sont essentiels pour l’acquisition de données de l’environnement et l’établissement de la situation tactique. Dans ce contexte, les plateformes peuvent collaborer et partager leurs ressources senseurs pour accomplir de nouvelles fonctionnalités et établir un panorama global de la situation. Dans cette thèse, nous avons conçu et développé un système multi-agent pour l’allocation de tâches à des ressources distribuées sur des plateformes distinctes dans le but d’accomplir des capacités collaboratives. Nous présentons des scénarios illustrant les besoins opérationnels auxquels l’architecture doit répondre, établissant ainsi un cahier des charges. Ensuite, nous détaillons les étapes de la conception et de l’implémentation de cette nouvelle architecture, en décrivant chaque type d’agent et les interactions possibles entre eux. Nous proposons un algorithme d’enchère nécessitant des échanges entre les agents, soumis aux contraintes de bande passante et de latence. Enfin, nous présentons un banc d’essai intégrant des outils de capture et de visualisation de métriques du système, permettant l’évaluation des concepts d’agents et de leurs mécanismes de communication. L’objectif est de démontrer que notre architecture répond aux besoins opérationnels spécifiés, notamment le passage à l’échelle des algorithmes et des interfaces de communications des agents, la résistance aux pannes et la performance du systèmeThe changing context of naval and aerial defense requires a major modification of current sensor system architectures to overcome future threats and to integrate next generation devices and sensors. These sensors, heterogeneous, complementary, and embedded on naval or aerial platforms, are essential for acquiring data from the environment in order to establish the tactical situation. In this context, platforms can collaborate and share their sensor resources to achieve new functionalities and set up a global overview of the situation. In this thesis, we have designed and developed a multi-agent system for allocating tasks to distributed resources on distinct platforms in order to accomplish collaborative capabilities. We present scenarios illustrating the operational needs that the architecture must meet, thus establishing a set of specifications. Then, we detail the steps involved in designing and implementing this new architecture, describing each type of agent and the possible interactions between them. We propose an auction algorithm requiring exchanges between agents, subject to bandwidth and latency constraints. Finally, we present a test bed integrating tools for capturing and display system metrics, allowing the evaluation of agent concepts and their communication mechanisms. The objective is to demonstrate that our architecture meets the specified operational requirements, in particular the scalability of the agents’ algorithms and communication interfaces, fault tolerance, and system performance
5
Yu, Wanli [Verfasser], Alberto [Akademischer Betreuer] Garcia-Ortiz, Alberto [Gutachter] Garcia-Ortiz, and Karl-Ludwig [Gutachter] Krieger. "Energy aware task allocation algorithms for wireless sensor networks / Wanli Yu ; Gutachter: Alberto Garcia-Ortiz, Karl-Ludwig Krieger ; Betreuer: Alberto Garcia-Ortiz." Bremen : Staats- und Universitätsbibliothek Bremen, 2018. http://d-nb.info/1161844562/34.
Full text
6
Havens, Michael E. "Dynamic allocation of fires and sensors." Thesis, Monterey, Calif. : Springfield, Va. : Naval Postgraduate School ; Available from National Technical Information Service, 2002. http://library.nps.navy.mil/uhtbin/hyperion-image/02sep%5FHavens.pdf.
Full text
7
Norman, Victoria Catherine. "Caste and task allocation in ants." Thesis, University of Sussex, 2016. http://sro.sussex.ac.uk/id/eprint/63780/.
Full textAbstract:
Group living is a widely adopted strategy by many organisms and given the advantages offered by a social lifestyle, such as increased protection from predators or increased ability for resource exploitation, a wide variety of animals have adopted a social lifestyle. Arguably none have done this more successfully than the social insects. Indeed their efficient division of labour is often cited as a key attribute for the remarkable ecological and evolutionary success of these societies. Within the social insects the most obvious division of labour is reproductive, in which one or a few individuals monopolise reproduction while the majority of essentially sterile workers carry out the remaining tasks essential for colony survival. In almost all social insects, in particular ants, the age of a worker will predispose it to certain tasks, and in some social insects the workers vary in size such that task is associated with worker morphology. In this thesis I explore the proximate and ultimate causes of worker and reproductive division of labour in ant societies, which span a range of social complexities. I predominantly focus on both the highly derived leaf-cutting ants – a so-called ‘pinnacle' of evolution within the social insects, with a complex division of labour and a strong worker caste system – and in the more basal primitive societies of the queenless ponerine dinosaur ants, which can offer an insight in to the evolution of division of labour at the earliest stages of social lifestyles. This work demonstrates the environmental and genetic determinants of division of labour in group-living societies outside of the classical honey bee model system. This is important as it helps us to better understand the broader processes shaping behaviour and phenotype in the animal kingdom.
8
Johnson, Luke B. "Decentralized task allocation for dynamic environments." Thesis, Massachusetts Institute of Technology, 2012. http://hdl.handle.net/1721.1/71458.
Full textAbstract:
Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Aeronautics and Astronautics, 2012.Cataloged from PDF version of thesis.
Includes bibliographical references (p. 93-98).
This thesis presents an overview of the design process for creating greedy decentralized task allocation algorithms and outlines the main decisions that progressed the algorithm through three different forms. The first form was called the Sequential Greedy Algorithm (SGA). This algorithm, although fast, relied on a large number of iterations to converge, which slowed convergence in decentralized environments. The second form was called the Consensus Based Bundle Algorithm (CBBA). CBBA required significantly fewer iterations than SGA but it is noted that both still rely on global synchronization mechanisms. These synchronization mechanisms end up being difficult to enforce in decentralized environments. The main result of this thesis is the creation of the Asynchronous Consensus Based Bundle Algorithm (ACBBA). ACBBA broke the global synchronous assumptions of CBBA and SGA to allow each agent more autonomy and thus provided more robustness to the task allocation solutions in these decentralized environments.
by Luke B. Johnson.
S.M.
9
Sarker, Md Omar Faruque. "Self-regulated multi-robot task allocation." Thesis, University of South Wales, 2010. https://pure.southwales.ac.uk/en/studentthesis/selfregulated-multirobot-task-allocation(4b92f28f-c712-4e75-955f-97b4e5bf12dd).html.
Full textAbstract:
To deploy a large group of autonomous robots in dynamic multi-tasking environments, a suitable multi-robot task-allocation (MRTA) solution is required. This must be scalable to variable number of robots and tasks. Recent studies show that biology-inspired self-organized approaches can effectively handle task-allocation in large multi-robot systems. However most existing MRTA approaches have overlooked the role of different communication and sensing strategies found in selfregulated biological societies. This dissertation proposes to solve the MRTA problem using a set of previously published generic rules for division of labour derived from the observation of ant,human and robotic social systems. The concrete form of these rules, the attractive field model (AFM), provides sufficient abstraction to local communication and sensing which is uncommon in existing MRTA solutions. This dissertation validates the effectiveness of AFM to address MRTA using two bio-inspired communication and sensing strategies: "global sensing - no communication" and "local sensing - local communication". The former is realized using a centralized communication system and the latter is emulated under a peer-topeer local communication scheme. They are applied in a manufacturing shop-floor scenario using 16 e-puck robots. A robotic interpretation of AFM is presented that maps the generic parameters of AFM to the properties of a manufacturing shopfloor. A flexible multi-robot control architecture, hybrid event-driven architecture on D-Bus, has been outlined which uses the state-of-the-art D-Bus interprocess communication to integrate heterogeneous software components. Based-on the organization of task-allocation, communication and interaction among robots, a novel taxonomy of MRTA solutions has been proposed to remove the ambiguities found in existing MRTA solutions. Besides, a set of domainindependent metrics, e.g., plasticity, task-specialization and energy usage, has been formalized to compare the performances of the above two strategies. The presented comparisons extend our general understanding of the role of information exchange strategies to achieve the distributed task-allocations among various social groups.
10
Hawley, John. "Hierarchical task allocation in robotic exploration /." Online version of thesis, 2009. http://hdl.handle.net/1850/10650.
Full text
11
Gage, Aaron. "Multi-robot task allocation using affect." [Tampa, Fla.] : University of South Florida, 2004. http://purl.fcla.edu/fcla/etd/SFE0000465.
Full text
12
Schneider, E. "Mechanism selection for multi-robot task allocation." Thesis, University of Liverpool, 2018. http://livrepository.liverpool.ac.uk/3018369/.
Full textAbstract:
There is increasing interest in fielding multi-robot teams for applications such as search and rescue, warehouse automation, and delivery of consumer goods. Task allocation is an important problem to solve in such multi-robot settings. Given a mission that can be decomposed into discrete tasks, the Multi-Robot Task Allocation (MRTA) problem looks for an assignment of tasks to robots that ultimately results in efficient execution of the mission. There is a range of approaches to this optimisation problem, from centralised solvers to fully distributed methods that involve no explicit coordination between team members. Somewhere in the middle of this range lie market-based approaches, where tasks can be treated as goods, robots as "buyers" who can compute and express their own preferences for tasks in a virtual marketplace, and some clearing mechanism exists to match tasks to robots according to these preferences. The most common type of market-based mechanism for multi-robot task allocation is an auction, in which tasks are announced to the team, robots compute and place bids that encode some measure of cost or utility of performing the tasks, and tasks are awarded to robots over a number of rounds, according to the particular rules of the mechanism. Many different auction mechanisms exist, and they vary in the trade-offs that they make between computation time and space on the one hand, and performance of the execution of the mission on the other. In addition, the performance that results from a mechanism's allocation can be greatly affected by properties of task environments---the spatial and temporal arrangements of tasks, as well as other properties like precedence constraints, whether tasks require the simultaneous cooperation of multiple robots, and so on---in which it is employed. A simple mechanism that is inexpensive to compute and scales well may perform well in some environments, but not in others. The work presented in this thesis focuses on this relationship between auction-based task allocation mechanisms and properties of task environments, with the goal of developing a method of selecting, from a portfolio, a mechanism that is appropriate for a given task environment. The first part of this work is an empirical performance evaluation of a range of mechanisms employed in a series of environments of increasing complexity. The second part of this work uses results from this evaluation to develop and train a data-driven method of mechanism selection using properties of environments that can be measured at the start of a mission. The results show that, under certain conditions, this method of mechanism selection can lead to significant performance improvements compared to using a single mechanism alone.
13
Johnson, Luke B. "Decentralized task allocation in communication contested environments." Thesis, Massachusetts Institute of Technology, 2016. http://hdl.handle.net/1721.1/105606.
Full textAbstract:
Thesis: Sc. D., Massachusetts Institute of Technology, Department of Aeronautics and Astronautics, 2016.Cataloged from PDF version of thesis.
Includes bibliographical references (pages 157-162).
This thesis explores the topic of decentralized task allocation. Specific emphasis is placed on how and when decentralized task allocation should be applied as a decision making tool for autonomous multi-agent missions. Even though the focus is on the decentralized aspect of task allocation, care is taken to identify the environments that do not actually benefit from decentralization, and what task allocation solutions are more appropriate for these environments. Chapter 2 provides a brief overview of the precise problem formulation and surveys the large number of task allocation approaches available. The result of this is an understanding when different classes of decentralized task allocation algorithms should be used. Chapters 3 and 4 introduce new algorithms that address fundamental issues with the past approaches to decentralized task allocation, and provide analysis of why these new approaches work. Specifically, Chapter 3 identifies a class of algorithms that utilize local information consistency assumptions (LICA), and an algorithm called Bid Warped Consensus Based Bundle Building Algorithm (BW-CBBA) is introduced to improve the state of art performance for this class of algorithms. Chapter 4 introduces an algorithm called the Hybrid Information and Plan Consensus (HIPC) algorithm, which uses LICA and two domains of information consensus in order to improve algorithmic performance over algorithms that exclusively perform consensus in a single domain. Chapter 5 introduces hardware experiments that verify and demonstrate the challenges associated with decentralized planning that are described throughout the thesis. Among other things, these experiments involved running a large number of planning algorithms onboard remote agents, and analyzing their performance in different communication and mission environments. Chapter 6 concludes the thesis with a summary of the contributions which highlights promising directions for new research.
by Luke B. Johnson.
Sc. D.
14
Siew, Christine Chiu Hsia. "Task allocation policies for State Dependent queues." Thesis, Massachusetts Institute of Technology, 2011. http://hdl.handle.net/1721.1/63041.
Full textAbstract:
Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Aeronautics and Astronautics, 2011.Cataloged from PDF version of thesis.
Includes bibliographical references (p. 108-111).
Consider a model of a dynamical queue with deterministic arrival and service rates, where the service rate depends on the server utilization history. This proposed queueing model occurs in many practical situations. for example in human-in-the-loop systems where widely accepted empirical laws describe human performance as a function of mental arousal, which increases when the human is working on a task and decreases otherwise. Formal methods for task management in state-dependent dynamical queues are gathering increasing attention to improve the efficiency of such systems. The focus of this research is hence to design maximally stabilizing task release control policies to maximize the useful throughput of such a system. Assuming that the error probability of a server is also related to its state., the useful throughput can be defined as the number of successfully completed tasks per unit time. Monitoring of both service and error rates is particularly typical in the realm of human-in-the-loop and production systems. This research focuses on developing policies to minimize both these penalty measures. For a server with deterministic service rate, the optimal policy is found to be a threshold policy that releases a task to the server only when the server state is less than or equal to a certain threshold. Assuming homogeneous tasks that bring in the same deterministic amount of work to be done, it can be shown that an appropriate threshold policy is maximally stabilizing and that this threshold value can be uniquely determined. This work is then further extended to the case when the server behaves stochastically and verified using simulation. Finally, a proof-of-concept experiment is proposed and developed to test the feasibility of the proposed theoretical policies in real-world settings. The experiment consisted of completing multiple-choice verbal analogy questions and the results confirm the effect of workload control in improving human performance.
by Christine Chiu Hsia Siew.
S.M.
15
Feljan, Juraj. "Task Allocation Optimization for Multicore Embedded Systems." Doctoral thesis, Mälardalens högskola, Inbyggda system, 2015. http://urn.kb.se/resolve?urn=urn:nbn:se:mdh:diva-29407.
Full textAbstract:
Modern embedded systems are becoming increasingly performance intensive, since, on the one hand, they include more complex functionality than before, and one the other hand, the functionality that was typically realized with hardware is often moved to software. Multicore technology, previously successfully used for general-purpose systems, is penetrating into the domain of embedded systems. While it does increase the performance capacity, it also introduces the problem of how to allocate software tasks to the cores of the hardware platform, as different allocations exhibit different extra-functional properties. An intuitive example is allocating too many tasks to a core --- the core will be overloaded and tasks will miss their deadlines. This thesis addresses the issue of task allocation in multicore embedded systems. The overall goal of the thesis is to advance the way soft real-time multicore systems are developed, by providing new methods and tools that enable deciding already at design-time which task to run on which core, with respect to a number of timing-related extra-functional properties. To achieve this goal, we developed a model-based framework for task allocation optimization. The framework uses model simulation in order to obtain performance predictions for particular task allocations. This in turn enables testing a large number of allocation candidates in search for one that exhibits good timing-related performance. Apart from defining and implementing the framework, three additional contributions are provided, each tackling a particular aspect of the framework: the influence of task allocation on communication duration is studied and interpreted in the context of design-time model-based analysis; a novel heuristic for guiding task allocation optimization is defined; and finally, a novel optimization method combining performance prediction and performance measurement is defined.
16
Das, Gautham Panamoottil. "Task allocation strategies for multi-robot systems." Thesis, Ulster University, 2015. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.667759.
Full text
17
Bakker, Tim. "Dynamic Task-Allocation for Unmanned Aircraft Systems." VCU Scholars Compass, 2014. http://scholarscompass.vcu.edu/etd/3394.
Full textAbstract:
This dissertation addresses improvements to a consensus based task allocation algorithms for improving the Quality of Service in multi-task and multi-agent environments. Research in the past has led to many centralized task allocation algorithms where a central computation unit is calculating the global optimum task allocation solution. The centralized algorithms are plagued by creating a single point of failure and the bandwidth needed for creating consistent and accurate situational awareness off all agents. This work will extend upon a widely researched decentralized task assignment algorithm based on the consensus principle. Although many extensions have led to improvements of the original algorithm, there is still much opportunity for improvement in providing sufficient and reliable task assignments in real-world dynamic conditions and changing environments. This research addresses practical changes made to the consensus based task allocation algorithms for improving the Quality of Service in multi-task and multi-agent environments.
18
COLISTRA, GIUSEPPE. "Task allocation in the Internet of Things." Doctoral thesis, Università degli Studi di Cagliari, 2015. http://hdl.handle.net/11584/266602.
Full textAbstract:
The last few years have been involved by the technological revolution represented by the Internet of Things (IoT). The IoT vision aims to interconnect devices with different capabilities such as sensors, actuators, Radio Frequency Identification (RFID) tags, smart objects (e.g. smartphones), and servers, within the same heterogeneous network. The aim is to enable the network objects to dynamically cooperate and make their resources available, in order to reach a goal, i.e. the execution of one or more applications assigned to the network. As known since its invention, the Internet interconnects nodes with dissimilar characteristics without central authorities by introducing some simple yet effective protocols that allow for nodes' interoperability so that information is successfully exchanged and services are provided by servers to clients and among peers. Fortunately, the same happens among objects in the IoT so that interoperability is assured and the data sensed by objects distributed and connected to the physical world is now available for the benefit of the human users. The realization of the IoT paradigm relies on the implementation of systems of cooperative intelligent objects with key interoperability capabilities. However, to reach this goal, it's important to consider some key features that characterize many IoT objects: i) available nodes' resources (electrical energy, memory, processing, node capability to perform a given task) are often limited. This is the case, for example, of battery powered nodes, which have limited energy amounts. ii) sensors may provide information that is not unique but can be generated by set of different objects which for example are capable to sense the same physical measure of the same geographical. iii) the number of nodes in the IoT is quickly overcoming the number of hosts in the 'traditional' Internet and most of these have a low reliability due mostly to the mobility and energy. This entails for a new paradigm of communication according to which objects coordinate with the other objects in groups and provide a unified service to the external world (the application that requires the service), with the intent to distribute the load of the requested services according to specific community defined rules, which could be: lifetime extension, QoS (Quality of Service) maximization, reward maximization, or others. It is evident that an appropriate coordination of objects' resources utilization would consistently improve their performance. This foreword is necessary to introduce this thesis, which is defined as follows. Task allocation in the IoT: given the IoT paradigm and the requirements of IoT applications, the nodes involved in the execution of the same application should cooperate to reach the optimal allocation of tasks among them. They should execute tasks to reach the global application target and to satisfy the relevant requirements while optimizing the network performance in terms of resources used. This issue should be continuously addressed to dynamically adapt the system to changes in terms of application requirements and network topology
19
Staffolani, Alessandro. "A Reinforcement Learning Agent for Distributed Task Allocation." Master's thesis, Alma Mater Studiorum - Università di Bologna, 2020. http://amslaurea.unibo.it/20051/.
Full textAbstract:
Al giorno d'oggi il reinforcement learning ha dimostrato di essere davvero molto efficace nel machine learning in svariati campi, come ad esempio i giochi, il riconoscimento vocale e molti altri. Perciò, abbiamo deciso di applicare il reinforcement learning ai problemi di allocazione, in quanto sono un campo di ricerca non ancora studiato con questa tecnica e perchè questi problemi racchiudono nella loro formulazione un vasto insieme di sotto-problemi con simili caratteristiche, per cui una soluzione per uno di essi si estende ad ognuno di questi sotto-problemi.
In questo progetto abbiamo realizzato un applicativo chiamato Service Broker, il quale, attraverso il reinforcement learning, apprende come distribuire l'esecuzione di tasks su dei lavoratori asincroni e distribuiti. L'analogia è quella di un cloud data center, il quale possiede delle risorse interne - possibilmente distribuite nella server farm -, riceve dei tasks dai suoi clienti e li esegue su queste risorse. L'obiettivo dell'applicativo, e quindi del data center, è quello di allocare questi tasks in maniera da minimizzare il costo di esecuzione.
Inoltre, al fine di testare gli agenti del reinforcement learning sviluppati è stato creato un environment, un simulatore, che permettesse di concentrarsi nello sviluppo dei componenti necessari agli agenti, invece che doversi anche occupare di eventuali aspetti implementativi necessari in un vero data center, come ad esempio la comunicazione con i vari nodi e i tempi di latenza di quest'ultima.
I risultati ottenuti hanno dunque confermato la teoria studiata, riuscendo a ottenere prestazioni migliori di alcuni dei metodi classici per il task allocation.
20
Porteous, J. M. "Dynamic task allocation in a distributed multiprocessor system." Thesis, University of Cambridge, 1985. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.374266.
Full textAbstract:
The dynamic scheduling of the workload of a distributed multiprocessor system was considered in order to identify a scheduling algorithm which was tolerant of variations in the transmission delays between the constituent processing nodes. The workload was considered to comprise a large number of tasks which arrived at random and which had a negative exponential service time distribution.A theoretical comparison was undertaken of a number of alternative, commonly used algorithms, particular emphasis being given to the effect on their performance of increasing inter-processor communications link delay.A complex simulation model was constructed on a direct shared memory multi-processor (CYBA-M) and the performance of various scheduling algorithms was investigated over a range of inter-processor delays and system configurations. The results obtained confirmed and quantified theoretical considerations and enabled a new algorithm to be devoloped.This new algorithm involves two stages of queuing. All tasks are initially transferred to one (or more) first stage, common queue(s). They are then transferred to the second stage queues (one on each processing node) using a batch service algorithm which employs dynamic (run-time) determination of the batch size. The transfer is initiated by a batch request issued by each second stage queue whenever its size falls below a threshold.The algorithm was evaluated for various simulated multi-processor configurations and was shown to be superior to conventional algorithms for a wider range of workloads and inter-processor delays (relative to the expected service time). It was also shown to be relatively insensitive to the values of the parameters used.
21
Jin, Yichao. "Intelligent task allocation in multi-hop wireless networks." Thesis, University of Surrey, 2011. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.543926.
Full text
22
Buckman, Noam (Noam M. ). "Decentralized task allocation for dynamic, time-sensitive tasks." Thesis, Massachusetts Institute of Technology, 2018. http://hdl.handle.net/1721.1/120195.
Full textAbstract:
Thesis: S.M., Massachusetts Institute of Technology, Department of Mechanical Engineering, 2018.This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.
Cataloged from student-submitted PDF version of thesis.
Includes bibliographical references (pages 103-110).
In time-sensitive and dynamic missions, autonomous vehicles must respond quickly to new information and objectives. In the case of dynamic task allocation, a team of agents are presented with a new, unknown task that must be allocated with their original allocations. This is exacerbated further in decentralized settings where agents are limited to utilizing local information during the allocation process. This thesis presents a fully decentralized, dynamic task allocation algorithm that extends the Consensus-Based Bundle Algorithm (CBBA) to allow for allocating new tasks. Whereas static CBBA requires a full resetting of previous allocations, CBBA with Partial Replanning (CBBA-PR) enables the agents to only partially reset their allocations to efficiently and quickly allocate a new task. By varying the number of existing tasks that are reset during replan, the team can trade-off convergence speed with amount of coordination. By specifically choosing the lowest bid tasks for resetting, CBBA-PR is shown to converge linearly with the number of tasks reset and the network diameter of the team. In addition, limited replanning methods are presented for scenarios without sufficient replanning time. These include a single reset bidding procedure for agents at capacity, a no-replanning heuristic that can identify scenarios that does not require replanning, and a subteam formation algorithm for reducing the network diameter. Finally, this thesis describes hardware and simulation experiments used to explore the effects of ad-hoc, decentralized communication on consensus algorithms and to validate the performance of CBBA-PR.
by Noam Buckman.
S.M.
23
Sung, Cynthia Rueyi. "Data-driven task allocation for multi-robot deliveries." Thesis, Massachusetts Institute of Technology, 2013. http://hdl.handle.net/1721.1/84717.
Full textAbstract:
Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2013.This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.
Cataloged from student-submitted PDF version of thesis.
Includes bibliographical references (pages 93-97).
In this thesis, we present a distributed task allocation system for a team of robots serving queues of tasks in an environment. We consider how historical information about such a system's performance could be used to improve future allocations. Our model is representative of a multi-robot mail delivery service, in which teams of robots would have to cooperate to pick up and deliver packages in an environment. We provide a framework for task allocation, planning, and control of the system and analyze task switching as a method for improving a task allocation as the system is running. We first treat a system where robots exchange tasks as they encounter each other in the environment. We consider both cases where the number of robots matches the number of task queues being served and where it does not. Most importantly, for situations where an optimal task switching policy would be too computationally expensive, we provide heuristics that nonetheless guarantee task completion. Our simulations show that our heuristics also generally lower the costs of task completion. We incorporate historical data about system performance by looking at a spatial allocation of tasks to robots in the system. We propose an algorithm for partitioning the environment into regions of equal workload for the robots. In order to overcome communication constraints, we introduce hubs, locations where robots can pass tasks to each other. We simulate the system with this additional infrastructure and compare its performance to that without hubs. We find that hubs can significantly improve performance when the task queues themselves follow some spatial structure.
by Cynthia Rueyi Sung.
S.M.
24
Macarthur, Kathryn. "Multi-agent coordination for dynamic decentralised task allocation." Thesis, University of Southampton, 2011. https://eprints.soton.ac.uk/209737/.
Full textAbstract:
Coordination of multiple agents for dynamic task allocation is an important and challenging problem, which involves deciding how to assign a set of agents to a set of tasks, both of which may change over time (i.e., it is a dynamic environment). Moreover, it is often necessary for heterogeneous agents to form teams to complete certain tasks in the environment. In these teams, agents can often complete tasks more efficiently or accurately, as a result of their synergistic abilities. In this thesis we view these dynamic task allocation problems as a multi-agent system and investigate coordination techniques for such systems. In more detail, we focus specially on the distributed constraint optimisation problem (DCOP) formalism as our coordination technique. Now, a DCOP consists of agents, variables and functions agents must work together to find the optimal configuration of variable values. Given its ubiquity, a number of decentralised algorithms for solving such problems exist, including DPOP, ADOPT, and the GDL family of algorithms. In this thesis, we examine the anatomy of the above-mentioned DCOP algorithms and highlight their shortcomings with regard to their application to dynamic task allocation scenarios. We then explain why the max-sum algorithm (a member of the GDL family) is the most appropriate for our setting, and define specific requirements for performing multi-agent coordination in a dynamic task allocation scenario: namely, scalability, robustness, efficiency in communication, adaptiveness, solution quality, and boundedness. In particular, we present three dynamic task allocation algorithms: fast-max-sum, branchand-bound fast-max-sum and bounded fast-max-sum, which build on the basic max-sum algorithm. The former introduces storage and decision rules at each agent to reduce overheads incurred by re-running the algorithm every time the environment changes. However, the overall computational complexity of fast-max-sum is exponential in the number of agents that could complete a task in the environment. Hence, in branchand- bound fast-max-sum, we give fast-max-sum significant new capabilities: namely, an online pruning procedure that simplifies the problem, and a branch-and-bound technique that reduces the search space. This allows us to scale to problems with hundreds of tasks and agents, at the expense of additional storage. Despite this, fast-max-sum is only proven to converge to an optimal solution on instances where the underlying graph contains no cycles. In contrast, bounded fast-max-sum builds on techniques found in bounded max-sum, another extension of max-sum, to find bounded approximate solutions on arbitrary graphs. Given such a graph, bounded fast-max-sum will run our iGHS algorithm, which computes a maximum spanning tree on subsections of a graph, in order to reduce overheads when there is a change in the environment. Bounded fast-max-sum will then run fast-max-sum on this maximum spanning tree in order to find a solution. We have found that fast-max-sum reduces the size of messages communicated and the amount of computation by up to 99% compared with the original max-sum. We also found that, even in large environments, branch-and-bound fast-max-sum finds a solution using 99% less computation and up to 58% fewer messages than fast-max-sum. Finally, we found bounded fast-max-sum reduces the communication and computation cost of bounded max-sum by up to 99%, while obtaining 60{88% of the optimal utility, at the expense of needing additional communication than using fast-max-sum alone. Thus, fast-max-sum or branch-and-bound fast-max-sum should be used where communication is expensive and provable solution quality is not necessary, and bounded fast-max-sum where communication is less expensive, and provable solution quality is required. Now, in order to achieve such improvements over max-sum, fast-max-sum exploits a particularly expressive model of the environment by modelling tasks in the environment as function nodes in a factor graph, which need to have some communication and computation performed for them. An equivalent problem to this can be found in operations research, and is known as scheduling jobs on unrelated parallel machines (also known as RjjCmax). In this thesis, we draw parallels between unrelated parallel machine scheduling and the computation distribution problem, and, in so doing, we present the spanning tree decentralised task distribution algorithm (ST-DTDA), the first decentralised solution to RjjCmax. Empirical evaluation of a number of heuristics for ST-DTDA shows solution quality achieved is up to 90% of the optimal on sparse graphs, in the best case, whilst worst-case quality bounds can be estimated within 5% of the solution found, in the best case
25
Van, Der Horst Johannes. "Market-based task allocation in distributed satellite systems." Thesis, University of Southampton, 2012. https://eprints.soton.ac.uk/339034/.
Full textAbstract:
This thesis addresses the problem of task allocation in a distributed satellite system. These spacecraft specialise in different functions, and must collaborate to complete the mission objectives. The energy available for task execution and communication is, however, extremely limited, which poses a challenging design problem. I propose the use of a market-based, multi-agent approach to achieve the necessary macro-level behaviour. The development and verification of this allocation mechanism constitutes the first major objective of this thesis. Although numerous examples of task allocation in related systems exist, I found a worrying disconnect between our general, theoretical knowledge of task allocation, and the specific application thereof. General analyses of abstracted task allocation exist, and specific implementations have been constructed in a heuristic way, but very little work navigates between these two extremes. My second major objective therefore contributes to mapping the problem space. The proposed task allocation mechanism is based on human labour markets in order to obtain similar robustness and flexibility. It uses fully distributed auctions to efficiently allocate tasks in volatile networks, without any global knowledge of the system state. The energy required for communication is constant, irrespective of the size of the network, resulting in a highly scalable allocation mechanism. To find the area in parameter space where market-based control is the more suitable solution, when compared to a centralised approach, I characterised the allocation mechanism in terms of network size, node failure rate, and robustness. The relationship between communication cost and topology is explored by looking at the overheads associated with different static topologies, and the impact of communication distance. The ability of the allocation mechanism to cope with realistic Keplerian dynamics is also confirmed. Finally, I investigate the difference in performance between the allocation mechanism, as an example of a cooperative market, and a competitive scenario where adaptive agents compete to maximise their revenue. Results show that competitive markets are subject to positive feedback loops which can result in inferior performance for sparsely connected and heavily loaded networks. This exploration of the system parameters is treated as a traversal of the problem space, resulting in an emergent taxonomy of both problem and solution elements.
26
Ercal, Fikret. "Heuristic approaches to task allocation for parallel computing /." The Ohio State University, 1988. http://rave.ohiolink.edu/etdc/view?acc_num=osu1487588939087747.
Full text
27
Emberson, Paul. "Searching for flexible solutions to task allocation problems." Thesis, University of York, 2009. http://etheses.whiterose.ac.uk/988/.
Full textAbstract:
Consumers of modern avionics and automotive systems expect many, well integrated features. Efforts are continually being made to make engineering processes better equipped to adapt to enhancement requests. Within both the avionics and automotive industries, standardisation of hardware and interfaces has allowed software to be mapped to hardware at a later stage of the design process and for this mapping to be more easily changed. Tools which automatically perform the mapping of tasks and messages onto a hardware platform are called task allocation tools. The primary requirement of a task allocation tool for hard real-time systems is to find a mapping and schedule such that all tasks and messages respond before their deadlines. However, there are other qualities which can be used to further differentiate between solutions, two of the most important being flexibility and adaptability. This thesis builds on previous task allocation work by extending a heuristic search algorithm to produce solutions with improved flexibility. Inspiration is drawn from scenario based architecture analysis methods. These methods interrogate an architecture model to see how it will react to different change scenarios. This idea is used within a search algorithm to encourage it to produce solutions which can meet the needs of provided scenarios with no or very few changes. It is shown that these solutions are also more flexible with respect to upgrades which differ from the scenarios. Run-time adaptability is another quality which can be affected by the choice of task allocation. Real-time systems can specify multiple task sets representing different modes of operation. The system will switch between modes at run-time to adapt to environmental changes and must do so efficiently. The task allocation algorithm is adapted for multi-moded systems and it is shown that solutions can be found which allow the system to transition between modes with minimal disruption. Safety-critical real-time systems have become dependent on software to provide critical functionality such as fly-by-wire control and engine emission regulation. These systems must be fault-tolerant and support graceful degradation, another form of adaptability. In the final part of this thesis, the task allocation algorithm is modified to select a number of replicas for each task as well as their allocation so that the system can withstand as many processor failures as possible before the level of service provided by the system falls below a safe threshold.
28
Duffy, Kristin Brooke. "COLONY SIZE AND TASK ALLOCATION IN CAMPONOTUS FESTINATUS." Thesis, The University of Arizona, 2008. http://hdl.handle.net/10150/192332.
Full text
29
Shetty, Deepti. "A Computational Task Allocation Model for Disaster Response." OpenSIUC, 2010. https://opensiuc.lib.siu.edu/theses/271.
Full textAbstract:
Motivated by shortcomings in recent natural disaster responses; this paper reports on a computational approach that offers techniques for matching social demands of a disaster type with the strengths of cultural traits among rescue teams.
30
Kumar, Nandeesh. "Automated task allocation for network processors using genetic algorithm /." Available to subscribers only, 2007. http://proquest.umi.com/pqdweb?did=1324381471&sid=4&Fmt=2&clientId=1509&RQT=309&VName=PQD.
Full text
31
Turner, Joanna. "Distributed task allocation optimisation techniques in multi-agent systems." Thesis, Loughborough University, 2018. https://dspace.lboro.ac.uk/2134/36202.
Full textAbstract:
A multi-agent system consists of a number of agents, which may include software agents, robots, or even humans, in some application environment. Multi-robot systems are increasingly being employed to complete jobs and missions in various fields including search and rescue, space and underwater exploration, support in healthcare facilities, surveillance and target tracking, product manufacturing, pick-up and delivery, and logistics. Multi-agent task allocation is a complex problem compounded by various constraints such as deadlines, agent capabilities, and communication delays. In high-stake real-time environments, such as rescue missions, it is difficult to predict in advance what the requirements of the mission will be, what resources will be available, and how to optimally employ such resources. Yet, a fast response and speedy execution are critical to the outcome. This thesis proposes distributed optimisation techniques to tackle the following questions: how to maximise the number of assigned tasks in time restricted environments with limited resources; how to reach consensus on an execution plan across many agents, within a reasonable time-frame; and how to maintain robustness and optimality when factors change, e.g. the number of agents changes. Three novel approaches are proposed to address each of these questions. A novel algorithm is proposed to reassign tasks and free resources that allow the completion of more tasks. The introduction of a rank-based system for conflict resolution is shown to reduce the time for the agents to reach consensus while maintaining equal number of allocations. Finally, this thesis proposes an adaptive data-driven algorithm to learn optimal strategies from experience in different scenarios, and to enable individual agents to adapt their strategy during execution. A simulated rescue scenario is used to demonstrate the performance of the proposed methods compared with existing baseline methods.
32
Wang, Lan. "Traffic and task allocation in networks and the cloud." Thesis, Imperial College London, 2018. http://hdl.handle.net/10044/1/60651.
Full textAbstract:
Communication services such as telephony, broadband and TV are increasingly migrating into Internet Protocol(IP) based networks because of the consolidation of telephone and data networks. Meanwhile, the increasingly wide application of Cloud Computing enables the accommodation of tens of thousands of applications from the general public or enterprise users which make use of Cloud services on-demand through IP networks such as the Internet. Real-Time services over IP (RTIP) have also been increasingly significant due to the convergence of network services, and the real-time needs of the Internet of Things (IoT) will strengthen this trend. Such Real-Time applications have strict Quality of Service (QoS) constraints, posing a major challenge for IP networks. The Cognitive Packet Network (CPN) has been designed as a QoS-driven protocol that addresses user-oriented QoS demands by adaptively routing packets based on online sensing and measurement. Thus in this thesis we first describe our design for a novel ''Real-Time (RT) traffic over CPN'' protocol which uses QoS goals that match the needs of voice packet delivery in the presence of other background traffic under varied traffic conditions; we present its experimental evaluation via measurements of key QoS metrics such as packet delay, delay variation (jitter) and packet loss ratio. Pursuing our investigation of packet routing in the Internet, we then propose a novel Big Data and Machine Learning approach for real-time Internet scale Route Optimisation based on Quality-of-Service using an overlay network, and evaluate is performance. Based on the collection of data sampled each $2$ minutes over a large number of source-destinations pairs, we observe that intercontinental Internet Protocol (IP) paths are far from optimal with respect to metrics such as end-to-end round-trip delay. On the other hand, our machine learning based overlay network routing scheme exploits large scale data collected from communicating node pairs to select overlay paths, while it uses IP between neighbouring overlay nodes. We report measurements over a week long experiment with several million data points shows substantially better end-to-end QoS than is observed with pure IP routing. Pursuing the machine learning approach, we then address the challenging problem of dispatching incoming tasks to servers in Cloud systems so as to offer the best QoS and reliable job execution; an experimental system (the Task Allocation Platform) that we have developed is presented and used to compare several task allocation schemes, including a model driven algorithm, a reinforcement learning based scheme, and a ''sensible’’ allocation algorithm that assigns tasks to sub-systems that are observed to provide lower response time. These schemes are compared via measurements both among themselves and against a standard round-robin scheduler, with two architectures (with homogenous and heterogenous hosts having different processing capacities) and the conditions under which the different schemes offer better QoS are discussed. Since Cloud systems include both locally based servers at user premises and remote servers and multiple Clouds that can be reached over the Internet, we also describe a smart distributed system that combines local and remote Cloud facilities, allocating tasks dynamically to the service that offers the best overall QoS, and it includes a routing overlay which minimizes network delay for data transfer between Clouds. Internet-scale experiments that we report exhibit the effectiveness of our approach in adaptively distributing workload across multiple Clouds.
33
Ezeaka, Chidubem L. "Tournament based task allocation in a parallel MIS algorithm." Thesis, Massachusetts Institute of Technology, 2014. http://hdl.handle.net/1721.1/91440.
Full textAbstract:
Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2014.2
Cataloged from PDF version of thesis.
Includes bibliographical references (page 16).
This paper explores the use of a tournament data structure for task allocation and dependency tracking in a parallel Maximal Independent Set (MIS) algorithm as a way to reduce contention in counter updates and improve runtime. The tournament data structure adds a noticeable overhead to the algorithm that causes T time of the algorithm to increase but then there is a steady improvement in performance as we increase the number of worker threads. Running the tournament algorithm with 12 threads in our experimental setup, we are able to get an average speedup of 1.13 for our test suite of 7 real-world graphs.
by Chidubem L. Ezeaka.
M. Eng.
34
Lee, Chonghwan. "Task allocation for efficient performance of a decentralized organization." Thesis, Massachusetts Institute of Technology, 1987. http://hdl.handle.net/1721.1/14631.
Full text
35
Landén, David. "Complex Task Allocation for Delegation : From Theory to Practice." Licentiate thesis, Linköpings universitet, KPLAB - Laboratoriet för kunskapsbearbetning, 2011. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-70536.
Full textAbstract:
The problem of determining who should do what given a set of tasks and a set of agents is called the task allocation problem. The problem occurs in many multi-agent system applications where a workload of tasks should be shared by a number of agents. In our case, the task allocation problem occurs as an integral part of a larger problem of determining if a task can be delegated from one agent to another. Delegation is the act of handing over the responsibility for something to someone. Previously, a theory for delegation including a delegation speech act has been specified. The speech act specifies the preconditions that must be fulfilled before the delegation can be carried out, and the postconditions that will be true afterward. To actually use the speech act in a multi-agent system, there must be a practical way of determining if the preconditions are true. This can be done by a process that includes solving a complex task allocation problem by the agents involved in the delegation. In this thesis a constraint-based task specification formalism, a complex task allocation algorithm for allocating tasks to unmanned aerial vehicles and a generic collaborative system shell for robotic systems are developed. The three components are used as the basis for a collaborative unmanned aircraft system that uses delegation for distributing and coordinating the agents' execution of complex tasks.
36
Bhal, Siddharth. "Fog computing for robotics system with adaptive task allocation." Thesis, Virginia Tech, 2017. http://hdl.handle.net/10919/78723.
Full textAbstract:
The evolution of cloud computing has finally started to affect robotics.
Indeed, there have been several real-time cloud applications making their way into robotics as of late. Inherent benefits of cloud robotics include providing virtually infinite
computational power and enabling collaboration of a multitude of connected devices.
However, its drawbacks include higher latency and overall higher energy consumption.
Moreover, local devices in proximity incur higher latency when communicating among themselves via the cloud. At the same time, the cloud is a single point of failure in the network. Fog Computing is an extension of the cloud computing paradigm providing data, compute, storage and application services to end-users on a so-called edge layer. Distinguishing characteristics are its support for mobility and dense geographical distribution. We propose to study the implications of applying fog computing concepts in robotics by developing a middle-ware solution for Robotic Fog Computing Cluster solution for enabling adaptive distributed computation in heterogeneous multi-robot systems interacting with the Internet of Things (IoT). The developed middle-ware has a modular plug-in architecture based on micro-services and facilitates communication of IOT devices with the multi-robot systems.
In addition, the developed middle-ware solutions support different load balancing or task allocation algorithms. In particular, we establish that we can enhance the performance of distributed system by decreasing overall system latency by using already established multi-criteria decision-making algorithms like TOPSIS and TODIM with naive Q-learning and with Neural Network based Q-learning.Master of Science
37
AL-Buraiki, Omar S. M. "Specialized Agents Task Allocation in Autonomous Multi-Robot Systems." Thesis, Université d'Ottawa / University of Ottawa, 2020. http://hdl.handle.net/10393/41504.
Full textAbstract:
With the promise to shape the future of industry, multi-agent robotic technologies have the potential to change many aspects of daily life. Over the coming decade, they are expected to impact transportation systems, military applications such as reconnaissance and surveillance, search-and-rescue operations, or space missions, as well as provide support to emergency first responders.
Motivated by the latest developments in the field of robotics, this thesis contributes to the evolution of the future generation of multi-agent robotic systems as they become smarter, more accurate, and diversified in terms of applications. But in order to achieve these goals, the individual agents forming cooperative robotic systems need to be specialized in what they can accomplish, while ensuring accuracy and preserving the ability to perform diverse tasks.
This thesis addresses the problem of task allocation in swarm robotics in the specific context where specialized capabilities of the individual agents are considered. Based on the assumption that each individual agent possesses specialized functional capabilities and that the expected tasks, which are distributed in the surrounding environment, impose specific requirements, the proposed task allocation mechanisms are formulated in two different spaces. First, a rudimentary form of the team members’ specialization is formulated as a cooperative control problem embedded in the agents’ dynamics control space. Second, an advanced formulation of agents’ specialization is defined to estimate the individual agents’ task allocation probabilities in a dedicated specialization space, which represents the core contribution of this thesis to the advancement and practice in the area of swarm robotics.
The original task allocation process formulated in the specialization space evolves through four stages of development. First, a task features recognition stage is conceptually introduced to leverage the output of a sensing layer embedded in robotic agents to drive the proposed task allocation scheme. Second, a matching scheme is developed to best match each agent’s specialized capabilities with the corresponding detected tasks. At this stage, a general binary definition of agents’ specialization serves as the basis for task-agent association. Third, the task-agent matching scheme is expanded to an innovative probabilistic specialty-based task-agent allocation framework to generalize the concept and exploit the potential of agents’ specialization consideration. Fourth, the general framework is further refined with a modulated definition of the agents’ specialization based on their mechanical, physical structure, and embedded resources. The original framework is extended and a prioritization layer is also introduced to improve the system’s response to complex tasks that are characterized based on the recognition of multiple classes.
Experimental validation of the proposed specialty-based task allocation approach is conducted in simulation and on real-world experiments, and the results are presented and discussed in light of potential applications to demonstrate the effectiveness and efficiency of the proposed framework.
38
Zhang, Kaiyi. "Task Offloading and Resource Allocation Using Deep Reinforcement Learning." Thesis, Université d'Ottawa / University of Ottawa, 2020. http://hdl.handle.net/10393/41525.
Full textAbstract:
Rapid urbanization poses huge challenges to people's daily lives, such as traffic congestion, environmental pollution, and public safety. Mobile Internet of things (MIoT) applications serving smart cities bring the promise of innovative and enhanced public services such as air pollution monitoring, enhanced road safety and city resources metering and management. These applications rely on a number of energy constrained MIoT units (MUs) (e.g., robots and drones) to continuously sense, capture and process data and images from their environments to produce immediate adaptive actions (e.g., triggering alarms, controlling machinery and communicating with citizens). In this thesis, we consider a scenario where a battery constrained MU executes a number of time-sensitive data processing tasks whose arrival times and sizes are stochastic in nature. These tasks can be executed locally on the device, offloaded to one of the nearby edge servers or to a cloud data center within a mobile edge computing (MEC) infrastructure. We first formulate the problem of making optimal offloading decisions that minimize the cost of current and future tasks as a constrained Markov decision process (CMDP) that accounts for the constraints of the MU battery and the limited reserved resources on the MEC infrastructure by the application providers. Then, we relax the CMDP problem into regular Markov decision process (MDP) using Lagrangian primal-dual optimization. We then develop advantage actor-critic (A2C) algorithm, one of the model-free deep reinforcement learning (DRL) method to train the MU to solve the relaxed problem. The training of the MU can be carried-out once to learn optimal offloading policies that are repeatedly employed as long as there are no large changes in the MU environment. Simulation results are presented to show that the proposed algorithm can achieve performance improvement over offloading decisions schemes that aim at optimizing instantaneous costs.
39
Kivelevitch, Elad H. "Robust, Real Time, and Scalable Multi-Agent Task Allocation." University of Cincinnati / OhioLINK, 2012. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1337007279.
Full text
40
Lechliter, Matthew C. "Decentralized control for UAV path planning and task allocation." Morgantown, W. Va. : [West Virginia University Libraries], 2004. https://etd.wvu.edu/etd/controller.jsp?moduleName=documentdata&jsp%5FetdId=3314.
Full textAbstract:
Thesis (M.S.)--West Virginia University, 2004.Title from document title page. Document formatted into pages; contains x, 198 p. : ill. (some col.). Includes abstract. Includes bibliographical references (p. 134-138).
41
Spencer, Andrew. "Short-term task allocation in small social insect groups." Thesis, University of Bath, 2000. https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.341102.
Full text
42
Suárez, Barón Silvia Andrea. "Dynamic task allocation and coordination in cooperative multi-agent environments." Doctoral thesis, Universitat de Girona, 2011. http://hdl.handle.net/10803/7754.
Full textAbstract:
La coordinació i assignació de tasques en entorns distribuïts ha estat un punt important de la recerca en els últims anys i aquests temes són el cor dels sistemes multi-agent. Els agents en aquests sistemes necessiten cooperar i considerar els altres agents en les seves accions i decisions. A més a més, els agents han de coordinar-se ells mateixos per complir tasques complexes que necessiten més d'un agent per ser complerta. Aquestes tasques poden ser tan complexes que els agents poden no saber la ubicació de les tasques o el temps que resta abans de que les tasques quedin obsoletes. Els agents poden necessitar utilitzar la comunicació amb l'objectiu de conèixer la tasca en l'entorn, en cas contrari, poden perdre molt de temps per trobar la tasca dins de l'escenari. De forma similar, el procés de presa de decisions distribuït pot ser encara més complexa si l'entorn és dinàmic, amb incertesa i en temps real. En aquesta dissertació, considerem entorns amb sistemes multi-agent amb restriccions i cooperatius (dinàmics, amb incertesa i en temps real). En aquest sentit es proposen dues aproximacions que permeten la coordinació dels agents. La primera és un mecanisme semi-centralitzat basat en tècniques de subhastes combinatòries i la idea principal es minimitzar el cost de les tasques assignades des de l'agent central cap als equips d'agents. Aquest algoritme té en compte les preferències dels agents sobre les tasques. Aquestes preferències estan incloses en el bid enviat per l'agent. La segona és un aproximació d'scheduling totalment descentralitzat. Això permet als agents assignar les seves tasques tenint en compte les preferències temporals sobre les tasques dels agents. En aquest cas, el rendiment del sistema no només depèn de la maximització o del criteri d'optimització, sinó que també depèn de la capacitat dels agents per adaptar les seves assignacions eficientment. Addicionalment, en un entorn dinàmic, els errors d'execució poden succeir a qualsevol pla degut a la incertesa i error de accions individuals. A més, una part indispensable d'un sistema de planificació és la capacitat de re-planificar. Aquesta dissertació també proveeix una aproximació amb re-planificació amb l'objectiu de permetre als agent re-coordinar els seus plans quan els problemes en l'entorn no permeti la execució del pla. Totes aquestes aproximacions s'han portat a terme per permetre als agents assignar i coordinar de forma eficient totes les tasques complexes en un entorn multi-agent cooperatiu, dinàmic i amb incertesa. Totes aquestes aproximacions han demostrat la seva eficiència en experiments duts a terme en l'entorn de simulació RoboCup Rescue.Distributed task allocation and coordination have been the focus of recent research in last years and these topics are the heart of multi-agent systems. Agents in these systems need to cooperate and consider the other agents in their actions and decisions. Moreover, agents may have to coordinate themselves to accomplish complex tasks that need more than one agent to be accomplished. These tasks may be so complicated that the agents may not know the location of them or the time they have before the tasks become obsolete. Agents may need to use communication in order to know the tasks in the environment, otherwise, it may take a long time to find the tasks into the scenario. Similarly, the distributed decisionmaking process may be even more complex if the environment is dynamic, uncertain and real-time. In this dissertation, we consider constrained cooperative multi-agent environments (dynamic, uncertain and real-time). In this regard, we propose two approaches that enable the agents to coordinate themselves. The first one is a semi-centralized mechanism based on combinatorial auction techniques and the main idea is minimizing the cost of assigned tasks from the central agent to the agent teams. This algorithm takes into account the tasks' preferences of the agents. These preferences are included into the bid sent by the agent. The second one is a completely decentralized scheduling approach. It permits agents schedule their tasks taking into account temporal tasks' preferences of the agents. In this case, the system's performance depends not only on the maximization or the optimization criterion, but also on the agents' capacity to adapt their schedule efficiently. Furthermore, in a dynamic environment, execution errors may happen to any plan due to uncertainty and failure of individual actions. Therefore, an indispensable part of a planning system is the capability of replanning. This dissertation is also providing a replanning approach in order to allow agents recoordinate his plans when the environmental problems avoid fulfil them. All these approaches have been carried out to enable the agents to efficiently allocate and coordinate all their complex tasks in a cooperative, dynamic and uncertain multi-agent scenario. All these approaches have demonstrated their effectiveness in experiments performed in the RoboCup Rescue simulation environment.
43
Alahmad, Bader Naim. "Approximation algorithms for task allocation with QoS and energy considerations." Thesis, University of British Columbia, 2011. http://hdl.handle.net/2429/35081.
Full textAbstract:
We consider general problems of allocating tasks to processors where each
task is associated with a set of service classes. A service class is a tuple:
the first element represents the resource utilization and the second element
the quality of service associated with that resource utilization. Before allocating
a task to a processor, we need to assign it to a service class. We
consider some elementary problems that arise from this setting. What is the
minimum number of processors needed if we also need to attain a minimum
aggregate QoS level? Given a fixed set of processors, what is the maximum
attainable aggregate QoS? Such questions apply to the partitioned scheduling
of real-time tasks on multiprocessors and to other resource allocation
problems. The basic questions are NP-Hard, and we present polynomial
time approximation algorithms for certain special, but practical, cases. We
make interesting use of maximum flows in a bipartite graph while developing
the polynomial time approximation schemes. We then integrate energy expenditure
to the model above and address the problem of partitioning a set
of independent, periodic, real-time tasks over a fixed set of heterogeneous
processors while minimizing the energy consumption of the computing platform
subject to a guaranteed quality of service requirement. This problem
is NP-Hard and we present a fully polynomial time approximation scheme
for this problem. The main contribution of our work is in tackling the problem
in a completely discrete, and possibly arbitrarily structured, setting. In
other words, each processor has a discrete set of speed choices. Each task
has a computation time that is dependent on the processor that is chosen
to execute the task and on the speed at which that processor is operated. Further, the energy consumption of the system is dependent on the decisions
regarding task allocation and speed settings.
44
Vander, Weide Scott. "DYNAMIC TASK ALLOCATION IN MOBILE ROBOT SYSTEMS USING UTILITY FUNTIONS." Master's thesis, University of Central Florida, 2008. http://digital.library.ucf.edu/cdm/ref/collection/ETD/id/2927.
Full textAbstract:
We define a novel algorithm based on utility functions for dynamically allocating tasks to mobile robots in a multi-robot system. The algorithm attempts to maximize the performance of the mobile robot while minimizing inter-robot communications. The algorithm takes into consideration the proximity of the mobile robot to the task, the priority of the task, the capability required by the task, the capabilities of the mobile robot, and the rarity of the capability within the population of mobile robots. We evaluate the proposed algorithm in a simulation study and compare it to alternative approaches, including the contract net protocol, an approach based on the knapsack problem, and random task selection. We find that our algorithm outperforms the alternatives in most metrics measured including percent of tasks complete, distance traveled per completed task, fairness of execution, number of communications, and utility achieved.M.S.Cp.E.
School of Electrical Engineering and Computer Science
Engineering and Computer Science
Computer Engineering MSCpE
45
Wen, Hui Ying. "Human-automation task allocation in lunar landing: simulation and experiments." Thesis, Massachusetts Institute of Technology, 2011. http://hdl.handle.net/1721.1/85813.
Full textAbstract:
Thesis: S.M., Massachusetts Institute of Technology, Department of Aeronautics and Astronautics, 2011.Cataloged from PDF version of thesis.
Includes bibliographical references (pages 59-62).
Task allocation, or how tasks are assigned to the human operator(s) versus to automation, is an important aspect of designing a complex vehicle or system for use in human space exploration. The performance implications of alternative task allocations between human and automation can be simulated, allowing high-level analysis of a large task allocation design space. Human subject experiments can then be conducted to uncover human behaviors not modeled in simulation but need to be considered in making the task allocation decision. These methods were applied here to the case scenario of lunar landing with a single human pilot. A task analysis was performed on a hypothetical generic lunar landing mission, focusing on decisions and actions that could be assigned to the pilot or to automation during the braking, approach, and touchdown phases. Models of human and automation task completion behavior were implemented within a closed-loop pilot-vehicle simulation for three subtasks within the landing point designation (LPD) and final approach tasks, creating a simulation framework tailored for the analysis of a task allocation design space. Results from 160 simulation runs showed that system performance, measured by fuel usage and landing accuracy, was predicted to be optimized if the human performs decision making tasks, and manual tasks such as flying the vehicle are automated. Variability in fuel use can be attributed to human performance of the flying task. Variability in landing accuracy appears to result from human performance of the LPD and flying tasks. Next, a human subject experiment (11 subjects, 68 trials per subject) was conducted to study subjects' risk-taking strategy in designating the landing point. Results showed that subjects designated landing points that compensated for estimated touchdown dispersions and system-level knowledge of the probabilities of manual versus automated flight. Also, subjects made more complete LPD compensations when estimating touchdown dispersion from graphical plots rather than from memories of previous simulated landings. The way in which dispersion information is presented affected the consistency with which subjects adhered to a risk level in making landing point selections. These effects could then be incorporated in future human performance models and task allocation simulations.
by Hui Ying Wen.
S.M.
46
Wu, Wenbo. "Object Recognition with Progressive Refinement for Collaborative Robots Task Allocation." Thesis, Université d'Ottawa / University of Ottawa, 2020. http://hdl.handle.net/10393/41581.
Full textAbstract:
With the rapid development of deep learning techniques, the application of Convolutional Neural Network (CNN) has benefited the task of target object recognition. Several state-of-the-art object detectors have achieved excellent performance on the precision for object recognition. When it comes to applying the detection results for the real world application of collaborative robots, the reliability and robustness of the target object detection stage is essential to support efficient task allocation. In this work, collaborative robots task allocation is based on the assumption that each individual robotic agent possesses specialized capabilities to be matched with detected targets representing tasks to be performed in the surrounding environment which impose specific requirements. The goal is to reach a specialized labor distribution among the individual robots based on best matching their specialized capabilities with the corresponding requirements imposed by the tasks. In order to further improve task recognition with convolutional neural networks in the context of robotic task allocation, this thesis proposes an innovative approach for progressively refining the target detection process by taking advantage of the fact that additional images can be collected by mobile cameras installed on robotic vehicles. The proposed methodology combines a CNN-based object detection module with a refinement module. For the detection module, a two-stage object detector, Mask RCNN, for which some adaptations on region proposal generation are introduced, and a one-stage object detector, YOLO, are experimentally investigated in the context considered. The generated recognition scores serve as input for the refinement module. In the latter, the current detection result is considered as the a priori evidence to enhance the next detection for the same target with the goal to iteratively improve the target recognition scores. Both the Bayesian method and the Dempster-Shafer theory are experimentally investigated to achieve the data fusion process involved in the refinement process. The experimental validation is conducted on indoor search-and-rescue (SAR) scenarios and the results presented in this work demonstrate the feasibility and reliability of the proposed progressive refinement framework, especially when the combination of adapted Mask RCNN and D-S theory data fusion is exploited.
47
Raja, Sharan. "Learning communication policies for decentralized task allocation under communication constraints." Thesis, Massachusetts Institute of Technology, 2020. https://hdl.handle.net/1721.1/128998.
Full textAbstract:
Thesis: S.M., Massachusetts Institute of Technology, Computation for Design and Optimization Program, 2020Cataloged from student-submitted PDF version of thesis.
Includes bibliographical references (pages 57-60).
Multi-UAS teams often operate in ad-hoc communication networks where blind application of consensus algorithms perform poorly because of message intensive nature of such algorithms. Important messages can get lost due to interference or collisions with other messages, and the broadcasting of less important messages can limit the effective bandwidth available for the team. This thesis presents a novel algorithm - Communication-aware CBBA (CA-CBBA) that learns a cooperative communication policy for agents performing decentralized task allocation using consensus based bundle algorithm (CBBA) by accounting for these communication issues. In our approach, agents learn to use features, such as local communication graph density and value of their own messages, to both censor and schedule themselves amongst the other agents competing for shared communication medium. Experiments show that the learned communication policy enables more efficient utilization of the shared medium by prioritizing agents with important messages and more frequently censoring agents in denser parts of the network to alleviate the "hidden node problem." The approach is shown to lead to better task allocation outcomes with faster convergence time and conflict resolution rates compared to CBBA in communication-constrained environments. Policy learnt by agents trained on a specific team size and task number is shown to generalize to larger team sizes in task allocation problems with varying task numbers. To our knowledge, this is the first task allocation algorithm to co-design planning algorithm and communication protocol by incorporating communication constraints into the design process; resulting in better task allocation outcomes in communication-constrained environments.
by Sharan Raja.
S.M.
S.M. Massachusetts Institute of Technology, Computation for Design and Optimization Program
48
KARAMI, HOSSEIN. "Task planning and allocation for multi-agent collaborative robot systems." Doctoral thesis, Università degli studi di Genova, 2022. http://hdl.handle.net/11567/1083925.
Full textAbstract:
In this thesis we address the problem of human robot interaction in industrial environments from collaboration perspective. This thesis, in particular, focuses on introducing novel
frameworks for coordination of heterogeneous teams made of humans and robots that collaboratively aim to reach to a common goal.
In the last decade, robots has received enormous attentions for being employed in both industrial environments and workplaces. Thin is mainly because of a number of reasons: (I)
the shift of mass production industries toward autonomous industry units, (II) huge amount of financial and scientific investments on robotics, and (III) substitution of humans with robots to accomplish hazardous and stressful tasks. However Due to the limited cognitive knowledge and reasoning of the robots in accomplishing complex operations, they still are not able to operate in a fully autonomous fashion and independently from their human counterparts. Therefore presence of human operators, as a complementary counterparts, in workplaces becomes fundamental for robots to become utterly safe, reliable and operative. The goal of this thesis is to design and implement a framework whereby humans and/or robots can together play a complementary role, while applying their individual skills to accomplish a
task. Human-robot collaboration (HRC) is defined as the purposeful interaction among humans and robots in a shared space, and it is aimed at a common goal. The design of such framework for HRC problems, requires to satisfy many requirements from which flexibility, adaptability and safety, are the primary characteristics of such framework.
In this thesis we mainly focus on multi-agent robot systems task allocation and planning. We consider two main aspects in defining our objectives: on one hand we investigate on
HRC, and implement alternative frameworks to model and study collaborations in industrial scenarios considering various roles of humans in coordination and collaboration with robots.
On the other hand, the presence of humans is neglected and it is assumed that robots are able to fully precept the environment independently from human cognitive support, as this can be the case of future where Artificial intelligence might substitute the skills of humans. To model a HRC scenario, a smart framework is required to start, coordinate and terminate
a collaborative process. This framework, in particular has to be aware of agents and their types, determine their responsibilities and roles, be aware of their physical structure, define
the logical relationship among the agent and handle the collaboration process fluently. In this thesis, to address the framework described above, we propose different frameworks
and evaluate their effectiveness in solving HRC problems. To formulate task planning and allocation problem , we introduce and implement three variants of AND/OR graphs,
namely, c-layer AND/OR graphs, Branched AND/OR graphs, and Iteratively deepened AND/OR graphs. The first two variants aim at addressing the problem of task allocation
among humans and collaborative robots in object defect inspection (ODI) scenarios in HRC context. Instead, the third variant targets Task and motion planning (TAMP) problems for
heterogeneous robots. TAMP problems, compared to HRC problem, is not only responsible for allocating task among agents at higher-level, but also at lower level, it plans motions for
agents and ultimately, interconnects higher levels of task planning to lower levels of motion planning and control to achieve a complete planning framework. To validate the applicability
and scalability of our proposed frameworks, we design and implement various real-world and simulation experiments and we also evaluate their effectiveness in terms of achieving
desired objectives, and quantitatively with other available methods in the literature.
49
De, Mel Geeth R. "Intelligent resource selection for sensor-task assignment : a knowledge-based approach." Thesis, University of Aberdeen, 2014. http://digitool.abdn.ac.uk:80/webclient/DeliveryManager?pid=215104.
Full textAbstract:
Today, sensing resources play a crucial role in the success of critical tasks such as border monitoring and surveillance. Although there are various types of resources available, each with different capabilities, only a subset of these resources are useful for a specific task. This is due to the dynamism in tasks' environment and the heterogeneity of the resources. Thus, an effective mechanism to select resources for tasks is needed so that the selected resources cater for the needs of the tasks. Though a considerable amount of research has already been done in different communities to efficiently allocate resources to tasks, we argue that there is little work done to guarantee the effectiveness of the section with respect to the context of operation. In this thesis, we propose a knowledge-based approach in which the context of operation is introduced to the resource selection process. First, we present a formalism to represent a sensor domain. We then introduce sound and complete mechanisms through which effective resource solutions for tasks are discovered. An extension to the representation is then proposed so that the agility in resource selection is increased. Finally, we present an architecture whereby a multitude of such knowledge bases are exposed as services so that a coalition can fully benefit from its networked resources; a query language – and its semantics – to discover appropriate service collections for user requirements are also presented. We have evaluated our work through controlled experiments and critical arguments. Through these evaluations, we have shown that our approach can indeed improve the resource selection process and can augment resource allocation mechanisms. Our approach is general in that, it can be applied in many other domains.
50
Byrd, Trevor G. "Prioritizing Effort Allocation in a Multiple-Goal Environment." Diss., Virginia Tech, 2009. http://hdl.handle.net/10919/28237.
Full textAbstract:
This study replicated and extended existing research concerning task prioritization in multiple-goal scenarios. The theoretical perspectives on which hypotheses were based was a combination of Banduraâ s self-efficacy theory (1986) and rational models of control theory (Klein, 1989; Lord & Levy, 1994). Participants were 216 college students who received extra-credit points for their involvement. They performed six repeated trials on a computerized task consisting of two simultaneous sub-tasks. Participants pursued an assigned long-term goal on each task, and goal achievement was rewarded with additional extra-credit points as an incentive. Task prioritization was assessed with four separate measures of effort allocation, including the time spent on each task, the number of computer mouse-clicks made within each task, scores on a self-report assessment of exerted effort, and responses to a self-report task prioritization assessment. Results indicated that participants prioritized tasks on which they were closer to goal attainment, tasks on which they were more efficacious, tasks on which they were experiencing a faster rate of progress, and tasks on which they reported greater goal commitment. Results also indicated that the effect of goal-performance discrepancies (GPDs) on task prioritization was mediated by self-efficacy. Further the amount of time remaining before a deadline moderated the relationship between GPD and task prioritization, although the form of this relationship was not in the proposed direction. Achievement goals were examined as moderators of the relationship between GPDs and task prioritization, but results were non-significant. Overall, these findings provide additional evidence that expectancies are often central to understanding self-regulation in multiple-goal scenarios, as first asserted by Kernan and Lord (1990). The current study also provides additional evidence concerning the importance of temporal factors in determining resource allocation in multiple-goal scenarios. Results from the current study point toward multiple issues for exploration in future research, such as an integrated model focusing in part on the pivotal role of self-efficacy or other expectancy-related constructs. Results also demonstrate implications for applied work, including clear evidence that employees should be expected to allocate their finite resources toward goals on which they believe success is most likely.Ph. D.