1,720,972 research outputs found
Coordinating Teams of Mobile Sensors for Monitoring Environmental Phenomena
No full textMobile wireless sensors can play a vital role in achieving situational awareness in uncertain and changing environments by keeping track of environmental phenomena, such as temperature, gas concentration and radiation, that exhibit spatial and temporal correlations. Examples of such environments are commonly found in disaster response, where the safety and effectiveness of response units critically depends on the accuracy of estimation of the state of the world. In these environments, mobile sensors operating in a team can improve situational awareness by offering a high sensing resolution in a timely and efficient way. In order to do this efficiently, however, they need to coordinate their movements. This coordination is a challenging task, since the sensors operate in an environment that is highly uncertain and dynamic, have a limited perception of their surroundings, and have limited communication with adjacent sensors. Consequently, coordination mechanisms need to address the challenges involved in maximising the collective information gain of the entire team, in the presence of uncertainty and different world views. Previous work in this area has focused on the use mobile and fixed wireless sensors for environmental monitoring, but fails to provide a principled online, decentralised coordination mechanism for such settings. In this report, we study the challenge of coordinating teams of mobile sensors for monitoring environmental phenomena. In order to do so, we review the literature on wireless (mobile) sensor networks, information processing, target tracking, and localisation and mapping. In particular, we focus on the key concept of adaptive sampling, which encompasses a set of techniques that aim to maximise information gain subject to movement constraints and the limited resources at a sensor's disposal. Based on this review, we present a general architecture for a sensor that makes a clear distinction between information processing, information valuing and maximising information gain. In more detail, we show that the state of the art in adaptive sampling falls short of providing robust, scalable, decentralised coordination algorithms. To address these shortcomings, we develop two online, decentralised coordination algorithms for monitoring spatial phenomena. The first algorithm operates in an un-negotiated coordination mode, in which coordination is achieved exclusively through the exchange of observations; sensors need not coordinate (negotiate) about the actions they are about to take, but base their decisions solely on the picture of the state of the environment that they compiled using their own observations and those received from their neighbours. This algorithm is based on two techniques found in previous work. Firstly, Gaussian process regression (Rasmussen2006a, Osborne2008), which is used for processing the raw observations obtained by the sensors and for predicting unobserved measurements. Secondly, myopic information-theoretic control (as found in Grocholsky2002), which is used for maximising the informativeness of the samples that are obtained by moving the sensors to locations where the environment is more uncertain. The second algorithm extends the first by adding a negotiation stage, which results in negotiated coordination. This algorithm is based on the max-sum message passing algorithm for decentralised control (Farinelli2008), which allows the sensors to maximise a team objective function in a decentralised fashion. To make the max-sum algorithm suitable for solving the mobile sensor coordination problem, we develop two pruning algorithms that drastically reduce the amount of computation required. These pruning algorithms are generic in the context of applying the max-sum algorithm, and are thus not limited to the mobile sensor setting. Finally, we extend the negotiated algorithm for sensors that are characterised by continuous control parameters (for example their heading and velocity). To this end, we generalise the discrete max-sum algorithm to the continuous case in which the interactions between sensors are characterised by continuous piecewise linear functions
Decentralised coordination of information gathering agents
No full textUnmanned sensors are rapidly becoming the de facto means of achieving situational awareness — the ability to make sense of, and predict what is happening in an environment — in disaster management, military reconnaissance, space exploration, and climate research. In these domains, and many others besides, their use reduces the need for exposing humans to hostile, impassable or polluted environments. Whilst these sensors are currently often pre-programmed or remotely controlled by human operators, there is a clear trend toward making these sensors fully autonomous, thus enabling them to make decisions without human intervention.Full autonomy has two clear benefits over pre-programming and human remote control. First, in contrast to sensors with pre-programmed motion paths, autonomous sensors are better able to adapt to their environment, and react to a priori unknown external events or hardware failure. Second, autonomous sensors can operate in large teams that would otherwise be too complex to control by human operators. The key benefit of this is that a team of cheap, small sensors can achieve through cooperation the same results as individual large, expensive sensors — with more flexibility and robustness.In light of the importance of autonomy and cooperation, we adopt an agent-based perspective on the operation of the sensors. Within this view, each sensor becomes an information gathering agent. As a team, these agents can then direct their collective activity towards collecting information from their environment with the aim of providingaccurate and up-to-date situational awareness.Against this background, the central problem we address in this thesis is that of achieving accurate situational awareness through the coordination of multiple information gathering agents. To achieve general and principled solutions to this problem, we formulate a generic problem definition, which captures the essential properties of dynamic environments. Specific instantiations of this generic problem span a broad spectrum of concrete application domains, of which we study three canonical examples: monitoring environmental phenomena, wide area surveillance, and search and patrol.The main contributions of this thesis are decentralised coordination algorithms that solve this general problem with additional constraints and requirements, and can be grouped into two categories. The first category pertains to decentralised coordination of fixed information gathering agents. For these agents, we study the application of decentralised coordination during two distinct phases of the agents’ life cycle: deployment and operation. For the former, we develop an efficient algorithm for maximising the quality of situational awareness, while simultaneously constructing a reliable communication network between the agents. Specifically, we present a novel approach to the NP-hard problem of frequency allocation, which deactivates certain agents such that the problem can be provably solved in polynomial time. For the latter, we address the challenge of coordinating these agents under the additional assumption that their control parameters are continuous. In so doing, we develop two extensions to the max-sum message passing algorithm for decentralised welfare maximisation, which constitute the first two algorithms for distributed constraint optimisation problems (DCOPs) with continuous variables—CPLF-MS (for linear utility functions) and HCMS (for non-linear utility functions).The second category relates to decentralised coordination of mobile information gathering agents whose motion is constrained by their environment. For these agents, we develop algorithms with a receding planning horizon, and a non-myopic planning horizon. The former is based on the max-sum algorithm, thus ensuring an efficient and scalable solution, and constitutes the first online agent-based algorithm for the domains of pursuit-evasion, patrolling and monitoring environmental phenomena. The second uses sequential decision making techniques for the offline computation of patrols — infinitely long paths designed to continuously monitor a dynamic environment — which are subsequently improved on at runtime through decentralised coordination.For both topics, the algorithms are designed to satisfy our design requirements of quality of situational awareness, adaptiveness (the ability to respond to a priori unknown events), robustness (the ability to degrade gracefully), autonomy (the ability of agents to make decisions without the intervention of a centralised controller), modularity (the ability to support heterogeneous agents) and performance guarantees (the ability to give a lower bound on the quality of the achieved situational awareness). When taken together, the contributions presented in this thesis represent an advance in the state of the art of decentralised coordination of information gathering agents, and a step towards achieving autonomous control of unmanned sensors
A Decentralised Coordination Algorithm for Maximising Sensor Coverage in Large Sensor Networks
No full textIn large wireless sensor networks, the problem of assigning radio frequencies to sensing agents such that no two connected sensors are assigned the same value (and will thus interfere with one another) is a major challenge. To tackle this problem, we develop a novel decentralised coordination algorithm that activates only a subset of the deployed agents, subject to the connectivity graph of this subset being provably 3-colourable in linear time, hence allowing the use of a simple decentralised graph colouring algorithm. Crucially, while doing this, our algorithm maximises the sensing coverage achieved by the selected sensing agents, which is given by an arbitrary non-decreasing submodular set function. We empirically evaluate our algorithm by benchmarking it against a centralised greedy algorithm and an optimal one, and show that the selected sensing agents manage to achieve 90% of the coverage provided by the optimal algorithm, and 85% of the coverage provided by activating all sensors. Moreover, we use a simple decentralised graph colouring algorithm to show the frequency assignment problem is easy in the resulting graphs; in all considered problem instances, this algorithm managed to find a colouring in less than 5 iterations on average. We then show how the algorithm can be used in dynamic settings, in which sensors can fail or new sensors can be deployed. In this setting, our algorithm provides 250% more coverage over time compared to activating all available sensors simultaneously
A Decentralized, On-line Coordination Mechanism for Monitoring Spatial Phenomena with Mobile Sensors
No full textDecentralised Control of Continuously Valued Control Parameters using the Max-Sum Algorithm
No full textIn this paper we address the problem of decentralised coordination for agents that must make coordinated decisions over continuously valued control parameters (as is required in many real world applications). In particular, we tackle the social welfare maximisation problem, and derive a novelcontinuous version of the max-sum algorithm. In order to do so, we represent the utility functionof the agents by multivariate piecewise linear functions, which in turn are encoded as simplexes.We then derive analytical solutions for the fundamental operations required to implement the max-sum algorithm (specifically, addition and marginal maximisation of general n-ary piecewise linearfunctions). We empirically evaluate our approach on a simulated network of wireless, energy constrained sensors that must coordinate their sense/sleep cycles in order to maximise the system-wide probability of event detection. We compare the conventional discrete max-sum algorithm with our novel continuous version, and show that the continuous approach obtains more accurate solutions (up to a 10% increase) with a lower communication overhead (up to half of the total message size)
A Hybrid Continuous Max-Sum Algorithm for Decentralised Coordination
No full textRecent advances in decentralised coordination of multiple agents have led to the proposal of the max-sum algorithm for solving distributed constraint optimisation problems (DCOPs). The max-sum algorithm is fully decentralised, converges to optimality for problems with acyclic constraint graphs and otherwise performs well in empirical studies. However, it requires agents to have discrete state spaces, which are of practical size to conduct repeated searches over. In contrast, there are decentralised non-linear optimisation methods that are capable of accurately finding local optima over multi-dimensional continuous state spaces, however these methods are not designed to navigate complex interactions between local constraints in order to find globally optimal solutions. Given this background, in this paper we tackle the problem of coordinating multiple decentralised agents with continuous state variables. Specifically we propose a hybrid approach, which combines the max-sum algorithm with continuous non-linear optimisation methods. We show that, for problems with acyclic factor graph representations, for suitable parameter choices, our proposed algorithm converges to a state with utility close to the global optimum. We empirically evaluate our approach for cyclic constraint graphs in a multi-sensor target classification problem, and compare its performance to the discrete max-sum algorithm, as well as a non-coordinated approach and the distributed stochastic algorithm (DSA). We show that our hybrid max-sum algorithm outperforms the non-coordinated algorithm, DSA and discrete max-sum considerably. Furthermore, the improvements in outcome over discrete max-sum come without significant increases in running time nor communication cost
U-GDL: A decentralised algorithm for DCOPs with Uncertainty
No full textIn this paper, we introduce DCOPs with uncertainty (U-DCOPs), a novel generalisation of the canonical DCOP framework where the outcomes of local functions are represented by random variables, and the global objective is to maximise the expectation of an arbitrary utility function (that represents the agents' risk-profile) applied over the sum of these local functions. We then develop U-GDL, a novel decentralised algorithm derived from Generalised Distributive Law (GDL) that optimally solves U-DCOPs. A key property of U-GDL that we show is necessary for optimality is that it keeps track of multiple non-dominated alternatives, and only discards those that are dominated (i.e. local partial solutions that can never turn into an expected global maximum regardless of the realisation of the random variables). As a direct consequence, we show that applying a standard DCOP algorithm to U-DCOP can result in arbitrarily poor solutions. We empirically evaluate U-GDL to determine its computational overhead and bandwidth requirements compared to a standard DCOP algorithm
Twiage: a game for finding good advice on Twitter
No full textMillions of recommendations, opinions and experiences are shared across popular microblogging platforms and services each day. Yet much of this content becomes quickly lost in the stream shortly after being posted. This paper looks at the feasibility of identifying useful content in microblog streams so that it might be archived to facilitate wider access and reference. Towards this goal, we present an experiment with a game-with-a-purpose called Twiage that we designed to determine how well the deluge of content in “raw” microblog streams could be turned into filtered and ranked collections using ratings from players. Experiments with Twiage validate the feasibility of applying human-computation to this problem, finding strong agreement about what constitutes the “most useful” content in our test dataset. Second, we compare the effectiveness of various methods of eliciting such ratings, finding that a “choose-best” interface and Elo rating ranking scheme yield the greatest agreement in the fewest rounds. External validation of resulting top-rated twitter content with a domain expert found that while the top Twiageranked “tweets” were among the best of the set, there was a tendency for players to also select what we term “weak spam” – e.g., promotional content disguised as articles or reviews, indicating a need for more stringent content filtering
CollabMap: Augmenting Maps using the Wisdom of Crowds
No full textThe creation of high fidelity scenarios for disaster simulation is a major challenge for a number of reasons. First, the maps supplied by existing map providers tend to provide only road or building shapes and do not accurately model open spaces which people use to evacuate buildings, homes, or industrial facilities. Secondly, even if some of the data about evacuation routes is available, the real-world connection points between these spaces and roads and buildings is usually not well defined unless data from buildings’ owners can be obtained. Finally, in order to augment current maps with accurate spatial data, it would require either a good set of training data for a computer vision algorithm to define evacuation routes using pictures or a significant amount of manpower to directly survey a vast area. Against this background, we develop a novel model of geospatial data creation, called CollabMap, that relies on human computation. CollabMap is a crowdsourcing tool to get users contracted via Amazon Mechanical Turk or a similar service to perform micro-tasks that involve augmenting existing maps by drawing evacuation routes, using satellite imagery from Google Maps and panoramic views from Google Street-View. We use human computation to complete tasks that are hard for a computer vision algorithm to perform or to generate training data that could be used by a computer vision algorithm to automatically define evacuation routes
A Decentralised Coordination Algorithm for Mobile Sensors
No full textWe present an on-line decentralised algorithm for coordinating mobile sensors for a broad class of information gathering tasks. These sensors can be deployed in unknown and possibly hostile environments, where uncertainty and dynamism are endemic. Such environments are common in the areas of disaster response and military surveillance. Our coordination approach itself is based on work by Stranders et al. (2009), that uses the max-sum algorithm to coordinate mobile sensors for monitoring spatial phenomena. In particular, we generalise and extend their approach to any domain where measurements can be valued. Also, we introduce a clustering approach that allows sensors to negotiate over paths to the most relevant locations, as opposed to a set of fixed directions, which results in a significantly improved performance. We demonstrate our algorithm by applying it to two challenging and distinct information gathering tasks. In the first–pursuit-evasion (PE)–sensors need to capture a target whose movement might be unknown. In the second–patrolling (P)–sensors need to minimise loss from intrusions that occur within their environment. In doing so, we obtain the first decentralised coordination algorithms for these domains. Finally, in each domain, we empirically evaluate our approach in a simulated environment, and show that it outperforms two state of the art greedy algorithms by 30% (PE) and 44% (P), and an existing approach based on the Travelling Salesman Problem by 52% (PE) and 30% (P)
- …
