Snapshot GNSS is a more energy-efficient approach to location estimation than traditional GNSS positioning methods. This is beneficial for applications with long deployments on battery such as wildlife tracking. However, only a few snapshot GNSS implementations have been presented so far and all have disadvantages. Most significantly, they typically require the GNSS signals to be captured with a certain minimum resolution, which demands complex receiver hardware capable of capturing multi-bit data at sampling rates of 16 MHz and more. By contrast, we develop fast algorithms that reliably estimate locations from twelve-millisecond signals that are sampled at just 4 MHz and quantised with only a single bit per sample. This allows us to build a snapshot receiver at an unmatched low cost of $14, which can acquire one position per hour for a year. On a challenging public dataset with thousands of snapshots from real-world scenarios, our system achieves 97% reliability and 11 m median accuracy, comparable to existing solutions with more complex and expensive hardware and higher energy consumption. We provide an open implementation of the algorithms as well as a public web service for cloud-based location estimation from low-quality GNSS signal snapshots.

Mosquitoes are considered one of the more severe worldwide health hazards. Their populations vary heterogeneously in urban and rural landscapes, and fluctuate with seasonal or climatic trends and human activities. Thus, frequent widespread high-resolution surveillance of mosquitoes is essential for both understanding their complex ecology and behavior, and also predicting disease risk and formulating effective control strategies against mosquito-borne diseases such as malaria, dengue and Zika. To this end, in this paper, we present LOCOMOBIS, a LOw-COst MOsquito BIoacoustic Sensor where the wingbeat sounds produced by mosquitoes in flapping-wing flight are used to identify different species automatically. The sensor has been deployed and tested in a real field deployment and our results demonstrate the practical feasibility of this low-cost nonintrusive approach for monitoring mosquitoes in places requiring vector monitoring aimed at mosquito control or eradication. Moreover, to make the system more ubiquitous and easy to interact with, we implemented a web-based application where it is possible to check the collected data and the automatic species and gender classification.

Computer vision and pattern recognition are increasingly being employed by smartphone and tablet applications targeted at lay-users. An open design challenge is to make such systems intelligible without requiring users to become technical experts. This paper reports a lab study examining the role of visual feedback. Our findings indicate that the stage of processing from which feedback is derived plays an important role in users' ability to develop coherent and correct understandings of a system's operation. Participants in our study showed a tendency to misunderstand the meaning being conveyed by the feedback, relating it to processing outcomes and higher level concepts, when in reality the feedback represented low level features. Drawing on the experimental results and the qualitative data collected, we discuss the challenges of designing interactions around pattern matching algorithms.

In this article, we address the interrelated challenges of predicting user comfort and using this to reduce energy consumption in smart heating, ventilation, and air conditioning (HVAC) systems. At present, such systems use simple models of user comfort when deciding on a set-point temperature. Being built using broad population statistics, these models generally fail to represent individual users’ preferences, resulting in poor estimates of the users’ preferred temperatures. To address this issue, we propose the Bayesian Comfort Model (BCM). This personalised thermal comfort model uses a Bayesian network to learn from a user’s feedback, allowing it to adapt to the users’ individual preferences over time. We further propose an alternative to the ASHRAE 7-point scale used to assess user comfort. Using this model, we create an optimal HVAC control algorithm that minimizes energy consumption while preserving user comfort. Through an empirical evaluation based on the ASHRAE RP-884 dataset and data collected in a separate deployment by us, we show that our model is consistently 13.2% to 25.8% more accurate than current models and how using our alternative comfort scale can increase our model’s accuracy. Through simulations we show that using this model, our HVAC control algorithm can reduce energy consumption by 7.3% to 13.5% while decreasing user discomfort by 24.8% simultaneously.

A key problem in crowdsourcing is the aggregation of judgments of proportions. For example, workers might be presented with a news article or an image, and be asked to identify the proportion of each topic, sentiment, object, or colour present in it. These varying judgments then need to be aggregated to form a consensus view of the document’s or image’s contents. Often, however, these judgments are skewed by workers who provide judgments randomly. Such spammers make the cost of acquiring judgments more expensive and degrade the accuracy of the aggregation. For such cases, we provide a new Bayesian framework for aggregating these responses (expressed in the form of categorical distributions) that for the first time accounts for spammers. We elicit 796 judgments about proportions of objects and coloursin images. Experimental results show comparable aggregation accuracy when 60% of the workers are spammers, as other state of the art approaches do when there are no spammers.

Over the past few years, Domestic Heating Automation Systems (DHASs) that optimize the domestic space heating control process with minimum user input, utilizing appropriate occupancy prediction technology, have emerged as commercial products (e.g., the smart thermostats from Nest and Honeywell). At the same time, many houses are being equipped with, potentially grid-connected, Intermittent Energy Resources (IERs), such as rooftop photovoltaic systems and/or small wind turbine generators. Now, in many regions of the world, such houses can sell energy to the grid but at a lower price than the price of buying it. In this context, and given the anticipated increase in electrification of heating, the next generation DHASs need to incorporate Advanced Economic Control (AEC). Such AEC can exploit the energy buffer that heating loads provide, in order to shift the consumption of electricity-based heating systems to follow the intermittent energy generation of the house. By so doing, the energy imported from the grid can be minimized and considerable monetary gains for the household can be achieved, without affecting the occupants’ schedule. These benefits can be amplified still further in domestic coalitions, where a number of houses come together and share their IER generation to minimize their cumulative grid energy import. Given the above, in this work we extend a state-of-the-art DHAS, to propose AdaHeat+, a practical DHAS, that, for the first time, incorporates AEC. Our work is applicable to both individual houses and domestic coalitions and comes complete with an allocation mechanism to share the coalition gains. Importantly, we propose an effective heuristic heating schedule planning approach for collective AEC that (i) has a complexity that scales in a linear and parallelizable manner with the coalition size, and (ii) enables AdaHeat+ to handle the distinct preferences, in balancing heating cost and thermal discomfort, of the households. Our approach relies on stochastic IER power output predictions. In this context, we propose a simple and effective formulation for the site-specific calibration of such predictions based on adaptive Gaussian process modeling. Finally, we demonstrate the effectiveness of AdaHeat+ through real data evaluation, to show that collective AEC can improve heating cost-efficiency by up to 60%, compared to independent AEC (and even more when compared to no-AEC).

We present an open-source toolkit that allows the easy comparison of the performance of active learning methods over a series of datasets. The toolkit allows such strategies to be constructed by combining a judgement aggregation model, task selection method and worker selection method.The toolkit also provides a user interface which allows researchers to gain insight into worker performance and task classification at runtime.

Minimizing the energy consumed by heating, ventilation, and air conditioning (HVAC) systems of residential buildings without impacting occupants’ comfort has been highlighted as an important artificial intelligence (AI) challenge. Typically, approaches that seek to address this challenge use a model that captures the thermal dynamics within a building, also referred to as a thermal model. Among thermal models, gray-box models are a popular choice for modeling the thermal dynamics of buildings. They combine knowledge of the physical structure of a building with various data-driven inputs and are accurate estimators of the state (internal temperature). However, existing gray-box models require a detailed specification of all the physical elements that can affect the thermal dynamics of a building a priori. This limits their applicability, particularly in residential buildings, where additional dynamics can be induced by human activities such as cooking, which contributes additional heat, or opening of windows, which leads to additional leakage of heat. Since the incidence of these additional dynamics is rarely known, their combined effects cannot readily be accommodated within existing models. To overcome this limitation and improve the general applicability of gray-box models, we introduce a novel model, which we refer to as a latent force thermal model of the thermal dynamics of a building, or LFM-TM. Our model is derived from an existing gray-box thermal model, which is augmented with an extra term referred to as the learned residual. This term is capable of modeling the effect of any a priori unknown additional dynamic, which, if not captured, appears as a structure in a thermal model’s residual (the error induced by the model). More importantly, the learned residual can also capture the effects of physical elements such as a building’s envelope or the lags in a heating system, leading to a significant reduction in complexity compared to existing models. To evaluate the performance of LFM-TM, we apply it to two independent data sources. The first is an established dataset, referred to as the FlexHouse data, which was previously used for evaluating the efficacy of existing gray-box models [Bacher and Madsen 2011]. The second dataset consists of heating data logged within homes located on the University of Southampton campus, which were specifically instrumented to collect data for our thermal modeling experiments. On both datasets, we show that LFM-TM outperforms existing models in its ability to accurately fit the observed data, generate accurate day-ahead internal temperature predictions, and explain a large amount of the variability in the future observations. This, along with the fact that we also use a corresponding efficient sequential inference scheme for LFM-TM, makes it an ideal candidate for model-based predictive control, where having accurate online predictions of internal temperatures is essential for high-quality solutions.

Current electricity tariffs do not reflect the real cost that customers incur to suppliers, as units are charged at the same rate, regardless of how predictable each customer's consumption is. A recent proposal to address this problem are prediction-of-use tariffs. In such tariffs, a customer is asked in advance to predict her future consumption, and is charged based both on her actual consumption and the deviation from her prediction. Prior work {aamas2014} studied the cost game induced by a single such tariff, and showed customers would have an incentive to minimize their risk, by joining together when buying electricity as a grand coalition. In this work we study the efficient (i.e. cost-minimizing) structure of buying groups for the more realistic setting when multiple, competing prediction-of-use tariffs are available. We propose a polynomial time algorithm to compute efficient buyer groups, and validate our approach experimentally, using a large-scale data set of domestic electricity consumers in the UK.

Our natural environment is complex and sensitive, and is home to a number of species on the verge of extinction. Surveying is one approach to their preservation, and can be supported by technology. This paper presents the deployment of a smartphone-based citizen science biodiversity application. Our findings from interviews with members of the biodiversity community revealed a tension between the technology and their established working practices. From our experience, we present a series of general guidelines for those designing citizen science apps.

This paper demonstrates a decentralized method for optimization using game-theoretic multi-agent techniques, applied to a sensor network management problem. Our first major contribution is to show how the marginal contribution utility design is used to construct an unknown-reward potential game formulation of the problem. This formulation exploits the sparse structure of sensor network problems, and allows us to apply a bound to the price of anarchy of the Nash equilibria of the induced game. Furthermore, since the game is a potential game, solutions can be found using multi-agent learning techniques. The techniques we derive use Q-learning to estimate an agent's rewards, while an action adaptation process responds to an agent's opponents’ behaviour. However, there are many different algorithmic configurations that could be used to solve these games. Thus, our second major contribution is an extensive evaluation of several action adaptation processes. Specifically, we compare six algorithms across a variety of parameter settings to ascertain the quality of the solutions they produce, their speed of convergence and their robustness to pre-specified parameter choices. Our results show that they each perform similarly across a wide range of parameters. There is, however, a significant effect from moving to a learning policy with sampling probabilities that go to zero too quickly for rewards to be accurately estimated.

In recent years, the field of computational sustainability has striven to apply artificial intelligence techniques to solve ecological and environmental problems. In ecology, a key issue for the safeguarding of our planet is the monitoring of biodiversity. Automated acoustic recognition of species aims to provide a cost-effective method for biodiversity monitoring. This is particularly appealing for detecting endangered animals with a distinctive call, such as the New Forest cicada. To this end, we pursue a crowdsourcing approach, whereby the millions of visitors to the New Forest, where this insect was historically found, will help to monitor its presence by means of a smartphone app that can detect its mating call. Existing research in the field of acoustic insect detection has typically focused upon the classification of recordings collected from fixed field microphones. Such approaches segment a lengthy audio recording into individual segments of insect activity, which are independently classified using cepstral coefficients extracted from the recording as features. This paper reports on a contrasting approach, whereby we use crowdsourcing to collect recordings via a smartphone app, and present an immediate feedback to the users as to whether an insect has been found. Our classification approach does not remove silent parts of the recording via segmentation, but instead uses the temporal patterns throughout each recording to classify the insects present. We show that our approach can successfully discriminate between the call of the New Forest cicada and similar insects found in the New Forest, and is robust to common types of environment noise. A large scale trial deployment of our smartphone app collected over 6000 reports of insect activity from over 1000 users. Despite the cicada not having been rediscovered in the New Forest, the effectiveness of this approach was confirmed for both the detection algorithm, which successfully identified the same cicada through the app in countries where the same species is still present, and of the crowdsourcing methodology, which collected a vast number of recordings and involved thousands of contributors.

Many crowdsourcing applications require spatial data modelling to make sense of location-based observations provided by multiple users. In this context, we propose a new spatial function modelling approach to address the problem of fusing multiple spatial observations reported by possibly untrustworthy users in the domains of participatory sensing and crowdsourcing applications. Specifically, we use a heteroskedastic Gaussian process model to incorporate user trust modelling into Bayesian spatial regression. In particular, by training the model with the reports gathered from the crowd, we are able to estimate the spatial function at any location of interest and also learn the level of trustworthiness of each user. We show that our method outperforms other standard homoskedastic and heteroskedastic Gaussian processes by up to 23% on a crowdsourced radiation dataset collected during the 2011 Fukushima earthquake in Japan. We also show that our method is able to improve the quality of spatial predictions on synthetic data by up to 70% and is robust in settings of up to 30% presence of untrustworthy users within the crowd.

In recent years, researchers have sought to capture the daily life location behaviour of groups of people for exploratory, inference, and predictive purposes. However, development of such approaches has been limited by the requirement of personal semantic labels for locations or social/spatial overlap between individuals in the group. To address this shortcoming, we present a Bayesian model of mobility in populations (i.e., groups without spatial or social interconnections) that is not subject to any of these requirements. The model intelligently shares temporal parameters between people, but keeps the spatial parameters specific to individuals. To illustrate the advantages of population modelling, we apply our model to the difficult problem of overcoming data sparsity in location prediction systems, using the Nokia dataset comprising 38 individuals, and find a factor of 2.4 improvement in location prediction performance against a state-of-the-art model when training on only 20 hours of observations.

Driven by real-world applications such as fitness, wellbeing and healthcare, accelerometry-based activity recognition has been widely studied to provide context-awareness to future pervasive technologies. Accurate recognition and energy efficiency are key issues in enabling long-term and unobtrusive monitoring. While the majority of accelerometry-based activity recognition systems stream data to a central point for processing, some solutions process data locally on the sensor node to save energy. In this paper, we investigate the trade-offs between classification accuracy and energy efficiency by comparing on- and off-node schemes. An empirical energy model is presented and used to evaluate the energy efficiency of both systems, and a practical case study (monitoring the physical activities of office workers) is developed to evaluate the effect on classification accuracy. The results show a 40% energy saving can be obtained with a 13% reduction in classification accuracy, but this performance depends heavily on the wearer's activity.

We develop an online mechanism for the allocation of an expiring resource to a dynamic agent population. Each agent has a non-increasing marginal valuation function for the resource, and an upper limit on the number of units that can be allocated in any period. We propose two versions on a truthful allocation mechanism. Each modifies the decisions of a greedy online assignment algorithm by sometimes cancelling an allocation of resources. One version makes this modification immediately upon an allocation decision while a second waits until the point at which an agent departs the market. Adopting a prior-free framework, we show that the second approach has better worst-case allocative efficiency and is more scalable. On the other hand, the first approach (with immediate cancellation) may be easier in practice because it does not need to reclaim units previously allocated. We consider an application to recharging plug-in hybrid electric vehicles (PHEVs). Using data from a real-world trial of PHEVs in the UK, we demonstrate higher system performance than a fixed price system, performance comparable with a standard, but non-truthful scheduling heuristic, and the ability to support 50% more vehicles at the same fuel cost than a simple randomized policy.

Non-intrusive appliance load monitoring is the process of disaggregating a household's total electricity consumption into its contributing appliances. In this paper we propose an approach by which individual appliances can be iteratively separated from an aggregate load. Unlike existing approaches, our approach does not require training data to be collected by sub-metering individual appliances, nor does it assume complete knowledge of the appliances present in the household. Instead, we propose an approach in which prior models of general appliance types are tuned to specific appliance instances using only signatures extracted from the aggregate load. The tuned appliance models are then used to estimate each appliance's load, which is subsequently subtracted from the aggregate load. This process is applied iteratively until all appliances for which prior behaviour models are known have been disaggregated. We evaluate the accuracy of our approach using the REDD data set, and show the disaggregation performance when using our training approach is comparable to when sub-metered training data is used. We also present a deployment of our system as a live application and demonstrate the potential for personalised energy saving feedback.

Virtual Power Plants (VPPs) are fast emerging as a suitable means of integrating small and distributed energy resources (DERs), like wind and solar, into the electricity supply network (Grid). VPPs are formed via the aggregation of a large number of such DERs, so that they exhibit the characteristics of a traditional generator in terms of predictability and robustness. In this work, we promote the formation of such "cooperative'' VPPs (CVPPs) using multi-agent technology. In particular, we design a payment mechanism that encourages DERs to join CVPPs with large overall production. Our method is based on strictly proper scoring rules and incentivises the provision of accurate predictions from the CVPPs---and in turn, the member DERs---which aids in the planning of the supply schedule at the Grid. We empirically evaluate our approach using the real-world setting of 16 commercial wind farms in the UK. We show that our mechanism incentivises real DERs to form CVPPs, and outperforms the current state of the art payment mechanism developed for this problem.

Restructuring electricity grids to meet the increased demand caused by the electrification of transport and heating, while making greater use of intermittent renewable energy sources, represents one of the greatest engineering challenges of our day. This modern electricity grid, in which both electricity and information flow in two directions between large numbers of widely distributed suppliers and generators — commonly termed the ‘smart grid’ — represents a radical reengineering of infrastructure which has changed little over the last hundred years. However, the autonomous behaviour expected of the smart grid, its distributed nature, and the existence of multiple stakeholders each with their own incentives and interests, challenges existing engineering approaches. In this challenge paper, we describe why we believe that artificial intelligence, and particularly, the fields of autonomous agents and multi-agent systems are essential for delivering the smart grid as it is envisioned. We present some recent work in this area and describe many of the challenges that still remain.

In budget–limited multi–armed bandit (MAB) problems, thelearner’s actions are costly and constrained by a fixed budget.Consequently, an optimal exploitation policy may not be topull the optimal arm repeatedly, as is the case in other variantsof MAB, but rather to pull the sequence of different arms thatmaximises the agent’s total reward within the budget. Thisdifference from existing MABs means that new approachesto maximising the total reward are required. Given this, wedevelop two pulling policies, namely: (i) KUBE; and (ii)fractional KUBE. Whereas the former provides better performanceup to 40% in our experimental settings, the latteris computationally less expensive. We also prove logarithmicupper bounds for the regret of both policies, and show thatthese bounds are asymptotically optimal (i.e. they only differfrom the best possible regret by a constant factor).

Location prediction systems that attempt to determine the mobility patterns of individuals in their daily lives have become increasingly common in recent years. Approaches to this prediction task include eigenvalue decomposition [5], non-linear time series analysis of arrival times [10], and variable order Markov models [1]. However, these approaches all assume sufficient sets of training data. For new users, by definition, this data is typically not available, leading to poor predictive performance. Given that mobility is a highly personal behaviour, this represents a significant barrier to entry. Against this background, we present a novel framework to enhance prediction using information about the mobility habits of existing users. At the core of the framework is a hierarchical Bayesian model, a type of probabilistic semantic analysis [7], representing the intuition that the temporal features of the new user's location habits are likely to be similar to those of an existing user in the system. We evaluate this framework on the real life location habits of 38 users in the Nokia Lausanne dataset, showing that accuracy is improved by 16%, relative to the state of the art, when predicting the next location of new users.

We present a methodology for the deployment of the maxsum algorithm, a well known decentralised algorithm for coordinating autonomous agents, for problems related to situational awareness. In these settings, unmanned autonomous vehicles are deployed to collect information about an unknown environment. Our methodology then helps identify the choices that need to be made to apply the algorithm to these problems. Next, we present a case study where the methodology is used to develop a system for disaster management in which a team of unmanned aerial vehicles coordinate to provide the first responders of the area of a disaster with live aerial imagery. To evaluate this system, we deploy it on two unmanned hexacopters in a variety of scenarios. Our tests show that the system performs well when confronted with the dynamism and the heterogeneity of the real world.

We introduce a new technique for coordinating teams of unmanned aerial vehicles (UAVs) when deployed to collect live aerial imagery of the scene of a disaster. We define this problem as one of task assignment where the UAVs dynamically coordinate over tasks representing the imagery collection requests. To measure the quality of the assignment of one or more UAVs to a task, we propose a novel utility function which encompasses several constraints, such as the task's importance and the UAVs' battery capacity so as to maximise performance. We then solve the resulting optimisation problem using a fully asynchronous and decentralised implementation of the max-sum algorithm, a well known message passing algorithm previously used only in simulated domains. Finally, we evaluate our approach both in simulation and on real hardware. First, we empirically evaluate our utility and show that it yields a better trade off between the quantity and quality of completed tasks than similar utilities that do not take all the constraints into account. Second, we deploy it on two hexacopters and assess its practical viability in the real world.

In this article, we consider the problem faced by a sensor network operator who must infer, in real time, the value of some environmental parameter that is being monitored at discrete points in space and time by a sensor network. We describe a powerful and generic approach built upon an efficient multi-output Gaussian process that facilitates this information acquisition and processing. Our algorithm allows effective inference even with minimal domain knowledge, and we further introduce a formulation of Bayesian Monte Carlo to permit the principled management of the hyperparameters introduced by our flexible models. We demonstrate how our methods can be applied in cases where the data is delayed, intermittently missing, censored, and/or correlated. We validate our approach using data collected from three networks of weather sensors and show that it yields better inference performance than both conventional independent Gaussian processes and the Kalman filter. Finally, we show that our formalism efficiently reuses previous computations by following an online update procedure as new data sequentially arrives, and that this results in a four-fold increase in computational speed in the largest cases considered.

In this paper, we propose a novel decentralised control mechanism to manage micro-storage in the smart grid. Our approach uses an adaptive pricing scheme that energy suppliers apply to home smart agents controlling micro-storage devices. In particular, we prove that the interaction between a supplier using our pricing scheme and the actions of selfish micro-storage agents forms a globally stable feedback loop that converges to an efficient equilibrium. We further propose a market strategy that allows the supplier to reduce wholesale purchasing costs without increasing the uncertainty and variance for its aggregate consumer demand. Moreover, we empirically evaluate our mechanism (based on the UK grid data) and show that it yields savings of up to 16% in energy cost for consumers using storage devices with average capacity 10 kWh. Furthermore, we show that it is robust against extreme system changes.

The development of agent technologies for sensor networks has received increasing research attention within both the sensor network and multi-agent systems research communities. The International Workshops on Agent Technologies for Sensor Networks (ATSN) held in 2007, 2008 and 2009 sought to bring these communities together, and this special issue of The Computer Journal presents extended versions of some of the papers that appeared at these workshops, along with new submissions specifically for this journal.

In this paper, we present a novel decentralised management technique that allows electricity micro-storage devices, deployed within individual homes as part of a smart electricity grid, to converge to profitable and efficient behaviours. Specifically, we propose the use of software agents, residing on the users' smart meters, to automate and optimise the charging cycle of micro-storage devices in the home to minimise its costs, and we present a study of both the theoretical underpinnings and the implications of a practical solution, of using software agents for such micro-storage management. First, by formalising the strategic choice each agent makes in deciding when to charge its battery, we develop a game-theoretic framework within which we can analyse the competitive equilibria of an electricity grid populated by such agents and hence predict the best consumption profile for that population given their battery properties and individual load profiles. Our framework also allows us to compute theoretical bounds on the amount of storage that will be adopted by the population. Second, to analyse the practical implications of micro-storage deployments in the grid, we present a novel algorithm that each agent can use to optimise its battery storage profile in order to minimise its owner's costs. This algorithm uses a learning strategy that allows it to adapt as the price of electricity changes in real-time, and we show that the adoption of these strategies results in the system converging to the theoretical equilibria. Finally, we empirically evaluate the adoption of our micro-storage management technique within a complex setting, based on the UK electricity market, where agents may have widely varying load profiles, battery types, and learning rates. In this case, our approach yields savings of up to 14% in energy cost for an average consumer using a storage device with a capacity of less than 4.5 kWh and up to a 7% reduction in carbon emissions resulting from electricity generation (with only domestic consumers adopting micro-storage and, commercial and industrial consumers not changing their demand). Moreover, corroborating our theoretical bound, an equilibrium is shown to exist where no more than 48% of households would wish to own storage devices and where social welfare would also be improved (yielding overall annual savings of nearly £1.5B).

With dwindling nonrenewable energy reserves and the adverse effects of climate change, the development of the smart electricity grid is seen as key to solving global energy security issues and to reducing carbon emissions. In this respect, there is a growing need to integrate renewable (or green) energy sources in the grid. However, the intermittency of these energy sources requires that demand must also be made more responsive to changes in supply, and a number of smart grid technologies are being developed, such as high-capacity batteries and smart meters for the home, to enable consumers to be more responsive to conditions on the grid in real time. Traditional solutions based on these technologies, however, tend to ignore the fact that individual consumers will behave in such a way that best satisfies their own preferences to use or store energy (as opposed to that of the supplier or the grid operator). Hence, in practice, it is unclear how these solutions will cope with large numbers of consumers using their devices in this way. Against this background, in this article, we develop novel control mechanisms based on the use of autonomous agents to better incorporate consumer preferences in managing demand. These agents, residing on consumers' smart meters, can both communicate with the grid and optimize their owner's energy consumption to satisfy their preferences. More specifically, we provide a novel control mechanism that models and controls a system comprising of a green energy supplier operating within the grid and a number of individual homes (each possibly owning a storage device). This control mechanism is based on the concept of homeostasis whereby control signals are sent to individual components of a system, based on their continuous feedback, in order to change their state so that the system may reach a stable equilibrium. Thus, we define a new carbon-based pricing mechanism for this green energy supplier that takes advantage of carbon-intensity signals available on the Internet in order to provide real-time pricing. The pricing scheme is designed in such a way that it can be readily implemented using existing communication technologies and is easily understandable by consumers. Building upon this, we develop new control signals that the supplier can use to incentivize agents to shift demand (using their storage device) to times when green energy is available. Moreover, we show how these signals can be adapted according to changes in supply and to various degrees of penetration of storage in the system. We empirically evaluate our system and show that, when all homes are equipped with storage devices, the supplier can significantly reduce its reliance on other carbon-emitting power sources to cater for its own shortfalls. By so doing, the supplier reduces the carbon emission of the system by up to 25% while the consumer reduces its costs by up to 14.5%. Finally, we demonstrate that our homeostatic control mechanism is not sensitive to small prediction errors and the supplier is incentivized to accurately predict its green production to minimize costs.

We develop an efficient algorithm for computing pure strategy Nash equilibria that satisfy various criteria (such as the utilitarian or Nash-Bernoulli social welfare functions) in games with sparse interaction structure. Our algorithm, called Valued Nash Propagation (VNP), integrates the optimisation problem of maximising a criterion with the constraint satisfaction problem of finding a game's equilibria to construct a criterion that defines a c-semiring. Given a suitably compact game structure, this criterion can be efficiently optimised using message-passing. To this end, we first show that VNP is complete in games whose interaction structure forms a hypertree. Then, we go on to provide theoretic and empirical results justifying its use on games with arbitrary structure; in particular, we show that it computes the optimum >82% of the time and otherwise selects an equilibrium that is always within 2% of the optimum on average.

We introduce the budget–limited multi–armed bandit (MAB), which captures situations where a learner’s actions are costly and constrained by a fixed budget that is incommensurable with the rewards earned from the bandit machine, and then describe a first algorithm for solving it. Since the learner has a budget, the problem’s duration is finite. Consequently an optimal exploitation policy is not to pull the optimal arm repeatedly, but to pull the combination of arms that maximises the agent’s total reward within the budget. As such, the rewards for all arms must be estimated, because any of them may appear in the optimal combination. This difference from existing MABs means that new approaches to maximising the total reward are required. To this end, we propose an epsilon–first algorithm, in which the first epsilon of the budget is used solely to learn the arms’ rewards (exploration), while the remaining 1 − epsilon is used to maximise the received reward based on those estimates (exploitation). We derive bounds on the algorithm’s loss for generic and uniform exploration methods, and compare its performance with traditional MAB algorithms under various distributions of rewards and costs, showing that it outperforms the others by up to 50%.

We 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).

We introduce a new sequential algorithm for making robust predictions in the presence of changepoints. Unlike previous approaches, which focus on the problem of detecting and locating changepoints, our algorithm focuses on the problem of making predictions even when such changes might be present. We introduce nonstationary covariance functions to be used in Gaussian process prediction that model such changes, and then proceed to demonstrate how to effectively manage the hyperparameters associated with those covariance functions. We further introduce covariance functions to be used in situations where our observation model undergoes changes, as is the case for sensor faults. By using Bayesian quadrature, we can integrate out the hyperparameters, allowing us to calculate the full marginal predictive distribution. Furthermore, if desired, the posterior distribution over putative changepoint locations can be calculated as a natural byproduct of our prediction algorithm.

This special issue is devoted to papers that have emerged from the ALADDIN (Autonomous Learning Agents for Decentralized Data and Information Networks) project (http://www.aladdinproject.org/). ALADDIN is concerned with developing techniques, methods and architectures for modelling, designing and building decentralized systems that can bring together information from a variety of heterogeneous sources in order to take informed actions in a timely manner. To do this, we have taken a total systems view on information and knowledge fusion and considered the feedback that exists between sensing, decision making and acting in such systems. Moreover, we have tackled these objectives in environments in which: control is distributed; uncertainty, ambiguity, imprecision and bias are endemic; multiple stakeholders with different aims and objectives are present; and resources are limited and continually vary during the systems operation.

The efficient management of the limited energy resources of a wireless visual sensor network is central to its successful operation. Within this context, this article focuses on the adaptive sampling, forwarding and routing actions of each node in order to maximize the information value of the data collected. These actions are inter-related in a multi-hop routing scenario because each node's energy consumption must be optimally allocated between sampling and transmitting its own data, receiving and forwarding the data of other nodes, and routing any data. Thus, we develop two optimal agent-based decentralized algorithms to solve this distributed constraint optimization problem. The first assumes that the route by which data is forwarded to the base station is fixed, and then calculates the optimal sampling, transmitting and forwarding actions that each node should perform. The second assumes flexible routing, and makes optimal decisions regarding both the integration of actions that each node should choose and also the route by which the data should be forwarded to the base station. The two algorithms represent a trade-off in optimality, communication cost and processing time. In an empirical evaluation on sensor networks (whose underlying communication networks exhibit loops), we show that the algorithm with flexible routing is able to deliver approximately twice the quantity of information to the base station compared with the algorithm using fixed routing (where an arbitrary choice of route is made). However, this gain comes at a considerable communication and computational cost (increasing both by a factor of 100 times). Thus, while the algorithm with flexible routing is suitable for networks with a small number of nodes, it scales poorly, and as the size of the network increases, the algorithm with fixed routing is favoured.

The efficient allocation of the limited energy resources of a wireless sensor network in a way that maximizes the information value of the data collected is a significant research challenge. Within this context, this article concentrates on adaptive sampling as a means of focusing a sensor's energy consumption on obtaining the most important data. Specifically, we develop a principled information metric based upon Fisher information and Gaussian process regression that allows the information content of a sensor's observations to be expressed. We then use this metric to derive three novel decentralized control algorithms for information-based adaptive sampling which represent a trade-off in computational cost and optimality. These algorithms are evaluated in the context of a deployed sensor network in the domain of flood monitoring. The most computationally efficient of the three is shown to increase the value of information gathered by approximately 83%, 27%, and 8% per day compared to benchmarks that sample in a naïve nonadaptive manner, in a uniform nonadaptive manner, and using a state-of-the-art adaptive sampling heuristic (USAC) correspondingly. Moreover, our algorithm collects information whose total value is approximately 75% of the optimal solution (which requires an exponential, and thus impractical, amount of time to compute).

This paper reports on the design of a novel two-stage mechanism, based on strictly proper scoring rules, that motivates selfish rational agents to make a costly probabilistic estimate or forecast of a specified precision and report it truthfully to a centre. Our mechanism is applied in a setting where the centre is faced with multiple agents, and has no knowledge about their costs. Thus, in the first stage of the mechanism, the centre uses a reverse second price auction to allocate the estimation task to the agent who reveals the lowest cost. While, in the second stage, the centre issues a payment based on a strictly proper scoring rule. When taken together, the two stages motivate agents to reveal their true costs, and then to truthfully reveal their estimate. We prove that this mechanism is incentive compatible and individually rational, and then present empirical results comparing the performance of the well known quadratic, spherical and logarithmic scoring rules. We show that the quadratic and the logarithmic rules result in the centre making the highest and the lowest expected payment to agents respectively. At the same time, however, the payments of the latter rule are unbounded, and thus the spherical rule proves to be the best candidate in this setting.

In this paper, we describe a novel, computationally efficient algorithm that facilitates the autonomous acquisition of readings from sensor networks (deciding when and which sensor to acquire readings from at any time), and which can, with minimal domain knowledge, perform a range of information processing tasks including modelling the accuracy of the sensor readings, predicting the value of missing sensor readings, and predicting how the monitored environmental variables will evolve into the future. Our motivating scenario is the need to provide situational awareness support to first responders at the scene of a large scale incident, and to this end, we describe a novel iterative formulation of a multi-output Gaussian process that can build and exploit a probabilistic model of the environmental variables being measured (including the correlations and delays that exist between them). We validate our approach using data collected from a network of weather sensors located on the south coast of England.

In this paper, we describe an information agent, that resides on a mobile computer or personal digital assistant (PDA), that can autonomously acquire sensor readings from pervasive sensor networks (deciding when and which sensor to acquire readings from at any time). Moreover, it can perform a range of information processing tasks including modelling the accuracy of the sensor readings, predicting the value of missing sensor readings, and predicting how the monitored environmental parameters will evolve into the future. Our motivating scenario is the need to provide situational awareness support to first responders at the scene of a large scale incident, and we describe how we use an iterative formulation of a multi-output Gaussian process to build a probabilistic model of the environmental parameters being measured by local sensors, and the correlations and delays that exist between them. We validate our approach using data collected from a network of weather sensors located on the south coast of England.

In this paper, we elucidate the equivalence between inference in game theory and machine learning. Our aim in so doing is to establish an equivalent vocabulary between the two domains so as to facilitate developments at the intersection of both fields, and as proof of the usefulness of this approach, we use recent developments in each field to make useful improvements to the other. More specifically, we consider the analogies between smooth best responses in fictitious play and Bayesian inference methods. Initially, we use these insights to develop and demonstrate an improved algorithm for learning in games based on probabilistic moderation. That is, by integrating over the distribution of opponent strategies (a Bayesian approach within machine learning) rather than taking a simple empirical average (the approach used in standard fictitious play) we derive a novel moderated fictitious play algorithm and show that it is more likely than standard fictitious play to converge to a payoff-dominant but risk-dominated Nash equilibrium in a simple coordination game. Furthermore we consider the converse case, and show how insights from game theory can be used to derive two improved mean field variational learning algorithms. We first show that the standard update rule of mean field variational learning is analogous to a Cournot adjustment within game theory. By analogy with fictitious play, we then suggest an improved update rule, and show that this results in fictitious variational play, an improved mean field variational learning algorithm that exhibits better convergence in highly or strongly connected graphical models. Second, we use a recent advance in fictitious play, namely dynamic fictitious play, to derive a derivative action variational learning algorithm, that exhibits superior convergence properties on a canonical machine learning problem (clustering a mixture distribution).

This article considers a canonical auction protocol that forms the basis of nearly all current online auctions. Such discrete bid auctions require that the bidders submit bids at predetermined discrete bid levels, and thus, there exists a minimal increment by which the bid price may be raised. In contrast, the academic literature of optimal auction design deals almost solely with continuous bid auctions. As a result, there is little practical guidance as to how an auctioneer, seeking to maximize its revenue, should determine the number and value of these discrete bid levels, and it is this omission that is addressed here. To this end, a model of an ascending price English auction with discrete bid levels is considered. An expression for the expected revenue of this auction is derived and used to determine numerical and analytical solutions for the optimal bid levels in the case of uniform and exponential bidder's valuation distributions. Finally, in order to develop an intuitive understanding of how these optimal bid levels are distributed, the limiting case where the number of discrete bid levels is large is considered, and an analytical expression for their distribution is derived.

This paper reports on the design and comparison of two economically inspired mechanisms for task allocation in environments where sellers have finite production capacities and a cost structure composed of a fixed overhead cost and a constant marginal cost. Such mechanisms are required when a system consists of multiple self-interested stakeholders that each possess private information that is relevant to solving a systemwide problem. Against this background, we first develop a computationally tractable centralized mechanism that finds the set of producers that have the lowest total cost in providing a certain demand (i.e., it is efficient). We achieve this by extending the standard Vickrey-Clarke-Groves mechanism to allow for multiattribute bids and by introducing a novel penalty scheme such that producers are incentivized to truthfully report their capacities and their costs. Furthermore, our extended mechanism is able to handle sellers' uncertainty about their production capacity and ensures that individual agents find it profitable to participate in the mechanism. However, since this first mechanism is centralized, we also develop a complementary decentralized mechanism based around the continuous double auction. Again, because of the characteristics of our domain, we need to extend the standard form of this protocol by introducing a novel clearing rule based around an order book. With this modified protocol, we empirically demonstrate (with simple trading strategies) that the mechanism achieves high efficiency. In particular, despite this simplicity, the traders can still derive a profit from the market which makes our mechanism attractive since these results are a likely lower bound on their expected returns

We present a mathematical model of the eBay auction protocol and perform a detailed analysis of the effects that the eBay proxy bidding system and the minimum bid increment have on the auction properties. We first consider the revenue of the auction, and we show analytically that when two bidders with independent private valuations use the eBay proxy bidding system there exists an optimal value for the minimum bid increment at which the auctioneer's revenue is maximized. We then consider the sequential way in which bids are placed within the auction, and we show analytically that independent of assumptions regarding the bidders' valuation distribution or bidding strategy the number of visible bids placed is related to the logarithm of the number of potential bidders. Thus, in many cases, it is only a minority of the potential bidders that are able to submit bids and are visible in the auction bid history (despite the fact that the other hidden bidders are still effectively competing for the item). Furthermore, we show through simulation that the minimum bid increment also introduces an inefficiency to the auction, whereby a bidder who enters the auction late may find that its valuation is insufficient to allow them to advance the current bid by the minimum bid increment despite them actually having the highest valuation for the item. Finally, we use these results to consider appropriate strategies for bidders within real world eBay auctions. We show that while last-minute bidding (sniping) is an effective strategy against bidders engaging in incremental bidding (and against those with common values), in general, delaying bidding is disadvantageous even if delayed bids are sure to be received before the auction closes. Thus, when several bidders submit last-minute bids, we show that rather than seeking to bid as late as possible, a bidder should try to be the first sniper to bid (i.e., it should “snipe before the snipers”).

Conventional centralised information fusion and control architectures will be challenged by developments in sensor networks that allow sophisticated autonomous sensors, owned by different stakeholders with individual goals, to interact and share information. Given this, we advocate the use of tools and techniques from computational mechanism design (CMD), a field at the intersection of computer science, game theory and economics, to address the challenges posed by these networks. In particular, CMD allows us to engineer networks with desirable system-wide properties, in which sensors act as rational selfish agents, each attempting to fulfil their own individuals goals through the exchange of observations and information. In this paper, we present our work developing such networks. Specifically, we discuss our development of a generic and principled information valuation metric for sensor networks and we report our experiences applying it within a real world information fusion sensor network scenario

In this paper we consider a common form of the English auction that is widely used in online Internet auctions. This discrete bid auction requires that the bidders may only submit bids which meet some predetermined discrete bid levels and, thus, there exists a minimal increment with which a bidder may raise the current price. In contrast, the academic literature of optimal auction design deals almost solely with continuous bid auctions, and, as a result, there is little practical guidance as to how an auctioneer, who is seeking to maximise his revenue, should determine the number and value of these discrete bid levels. Consequently, in current online auctions, a fixed bid increment is commonly implemented, despite this having been shown to be optimal in only limited cases.Given this background, in this paper, our aim is to provide the optimal auction design for an English auction with discrete bid levels. To this end, we derive an expression that relates the expected revenue of the auction, to the actual discrete bid levels im-plemented, the number of bidders participating, and the distribution from which the bidders draw their private independent valuations. We use this expression to derive numerical and analytical solutions for the optimal bid levels in the general case. To compare these results with previous work, we apply these solutions to an example, where bidders' valuations are drawn from a uniform distribution. In this case, we prove that when there are more than two bidders, a decreasing bid increment is optimal and we show that the optimal reserve price of the auction increases as the number of bidders increases. Finally, we compare the properties of an auction in which optimal bid levels are used, to the standard auction approach which implements a fixed bid increment. In so doing, we show that the optimal bid levels result in improvements in the revenue, duration and allocative efficiency of the auction.

In this paper, we develop an energy-aware self-organized routing algorithm for the networking of simple battery-powered wireless microsensors (as found, for example, in security or environmental monitoring applications). In these networks, the battery life of individual sensors is typically limited by the power required to transmit their data to a receiver or sink. Thus, effective network-routing algorithms allow us to reduce this power and extend both the lifetime and the coverage of the sensor network as a whole. However, implementing such routing algorithms with a centralized controller is undesirable due to the physical distribution of the sensors, their limited localization ability, and the dynamic nature of such networks (given that sensors may fail, move, or be added at any time and the communication links between sensors are subject to noise and interference). Against this background, we present a distributed mechanism that enables individual sensors to follow locally selfish strategies, which, in turn, result in the self-organization of a routing network with desirable global properties. We show that our mechanism performs close to the optimal solution (as computed by a centralized optimizer), it deals adaptively with changing sensor numbers and topology, and it extends the useful life of the network by a factor of three over the traditional approach.

A method for calculating genetic drift in terms of changing population fitness variance is presented. The method allows for an easy comparison of different selection schemes and exact analytical results are derived for traditional generational selection, steady-state selection with varying generation gap, a simple model of Eshelman's CHC algorithm (1991), and (/spl mu/+/spl lambda/) evolution strategies. The effects of changing genetic drift on the convergence of a GA are demonstrated empirically.