93,172 research outputs found
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)
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
Fuzzy argumentation for trust
No full textIn an open Multi-Agent System, the goals of agents acting on behalf of their owners often conflict with each other. Therefore, a personal agent protecting the interest of a single user cannot always rely on them. Consequently, such a personal agent needs to be able to reason about trusting (information or services provided by) other agents. Existing algorithms that perform such reasoning mainly focus on the immediate utility of a trusting decision, but do not provide an explanation of their actions to the user. This may hinder the acceptance of agent-based technologies in sensitive applications where users need to rely on their personal agents. Against this background, we propose a new approach to trust based on argumentation that aims to expose the rationale behind such trusting decisions. Our solution features a separation of opponent modeling and decision making. It uses possibilistic logic to model behavior of opponents, and we propose an extension of the argumentation framework by Amgoud and Prade to use the fuzzy rules within these models for well-supported decisions
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
Production of fungal lipids : kinetic modeling and process design
No full text Finding alternatives for fossil fuels is currently urgent. One of the new processes in this field is the production of biodiesel from lipids accumulated by microorganisms. Some yeasts and fungi accumulate lipids when a component needed for growth, usually the N-source, is limiting while the C-source is in excess. These oleaginous yeasts and fungi were previously mainly used for unsaturated fatty acid production, but now also come into view for production of lipids as a source of biodiesel. This thesis takes the first steps in the development of a new process to produce lipids with an oleaginous fungus in solid-state fermentation on agro-industrial waste. Solid-state fermentation is the cultivation on solid substrate particles without (free) flowing water, and has several advantages over submerged fermentation such as less waste water production, less energy use for oxygen transfer and lower production costs. In this thesis, we focused on growth and lipid production kinetics in submerged as well as solid-state fermentation. The models developed for these systems provide insight in the lipid production mechanism, needed to develop the new process based on solid-state fermentation. The thesis starts with the selection of a model strain (Chapter 2). With this strain, the kinetics of growth and lipid accumulation were studied and modeled. We started with a steady-state model (Chapter 3 and 4) in submerged chemostat culture, and extended this to a dynamic model for submerged batch culture (Chapter 5). As the next step towards solid-state fermentation, we developed a model for growth and lipid accumulation on κ-carrageenan plates with monomers (Chapter 6). These three models were finally used to calculate potential lipid yield and energy use in a biodiesel production system (Chapter 7). For the system we want to develop, we need a fungus that can utilize different substrates and can produce lipids. For this purpose, we tested two oleaginous fungi: Mortierella alpina and Umbelopsis isabellina, which is described in Chapter 2. We cultivated both fungi on agar plates containing glucose, xylose, starch, cellulose or pectin, and on sugar beet pulp in a packed bed. M. alpina did not utilize xylose, cellulose and pectin, utilized starch much slower than glucose and only consumed approximately 40% of the sugar beet pulp in 20 days. This shows that M. alpina is not a suitable organism for our production system. U. isabellina utilized pectin and xylose with the same rate as glucose, but used starch slower and (crystalline) cellulose not at all. It consumed approximately 75% of the sugar beet pulp after 8 days and approximately 100% after 20 days. Also, it accumulated some lipids (3% of remaining dry mass) in the culture on sugar beet pulp; optimization of this process by addition of enzymes increased the lipid content to 9% of remaining dry mass. This shows that U. isabellina is a promising strain for lipid production from agro-industrial waste, and is therefore a good strain to use in our research. The lipid concentrations found in SSF culture were quite low; we therefore decided to look in more depth into the kinetics of lipid production in different model systems. The first model system was a submerged chemostat culture, because the substrate supply rates can be varied in this system by varying the dilution rate as well as the concentrations in the feed. Chapter 3 describes the development of a mathematical model that includes growth, lipid accumulation and substrate consumption of oleaginous fungi in submerged chemostat cultures. Key points of the model are: (1) If the C-source supply rate is limited, maintenance has a higher priority than growth, which has a higher priority than lipid production; (2) the maximum specific lipid production rate of the fungus is independent of the actual specific growth rate. This model was validated with chemostat cultures of U. isabellina grown on mineral media with glucose and NH4+. Because of practical problems at low dilution rates, the model could only be validated for D>0.04 h‑1. For further validation, published data sets for chemostat cultures of oleaginous yeasts and a published data set for a poly-hydroxyalkanoate accumulating bacterial species were used, which is described in Chapter 4. All data sets could be described well by the model. Analysis of all data showed that the maximum specific lipid production rate is in most cases very close to the specific production rate of membrane and other functional lipids for cells growing at their maximum specific growth rate. The limiting factor suggested by Ykema et al.(1986, Antonie van Leeuwenhoek 52: 491-506), i.e. the maximum glucose uptake rate, did not give good predictions of the maximum lipid production rate. The model shows that both the C/N-ratio of the feed as well as the dilution rate has a large influence on the lipid production rate. When these data are translated to SSF, it means that a low substrate supply rate can prevent lipid production, even when the C/N-ratio of the substrate is high. The next step towards understanding lipid accumulation was a model that also describes changes in time. Therefore, we developed a model for growth, lipid production and lipid turnover in submerged batch fermentation, which is shown in Chapter 5. This model describes three subsequent phases: exponential growth when both a C-source and an N-source are available, carbohydrate and lipid production when the N-source is exhausted, and turnover of accumulated lipids when the C-source is exhausted. The model was validated with submerged batch cultures of U. isabellina with two different initial C/N-ratios. In batch culture, the specific lipid production rate was almost four times higher than in chemostat cultures and it decreased exponentially in time. This indicates that different mechanisms for lipid production are active in batch and chemostat cultures. The model could also describe several data sets from literature very well. Furthermore, the model shows that local limitation of C-source in SSF can cause lipid turnover before the average C-source concentration in the substrate is zero. The next step towards an SSF system is the inclusion of diffusion in the batch model. We did this by developing a model that describes growth, lipid production and lipid turnover in a culture on κ-carrageenan plates containing the monomers glucose and alanine as C-source and N-source, respectively. This is described in Chapter 6. The model includes reaction kinetics and diffusion of glucose, alanine and oxygen. It was validated with U. isabellina and describes the different phases of the culture very well: exponential growth, linear growth because of oxygen limitation, accumulation of lipids and carbohydrates after local N-depletion and turnover of lipids after local C-depletion. Extending the model with an unidentified extracellular product improved the fit of the model to the data. The model shows that oxygen limitation is extremely important in solid-state cultures using monomers. Together with the low specific lipid production rate found in SSF, it explains the difference in production rate with submerged cultures. In Chapter 7, we used the models from Chapter 3, 5 and 6 together with basic engineering principles to calculate lipid yield and energy use in the modeled systems. We evaluated a process including pretreatment, cultivation and down-stream processing with sugar beet pulp and wheat straw as substrate, described different reactor types, and considered both a yeast and a fungus as microorganisms. According to the models, lipid yields on substrate were between 5% w/w and 19% w/w, depending on the culture system. With the same models, improvement of the yield to 25-30% w/w was shown to be possible, for example by genetic modification of the microorganism. The net energy ratio of the non-optimized systems varied between 0.8 and 2.5 MJ produced per MJ used; energy use for pretreatment and for oxygen transfer were most important. For the optimized systems, the net energy ratio increased to 2.9 – 5.5 MJ produced per MJ used, which can compete very well with other biofuels such as bioethanol or algal biodiesel. So although there is still quite some work to be done, microbial lipids have the potential to be tomorrow’s source of biodiesel. </p
Oxidation of azaheterocycles by free and immobilized xanthine oxidase and xanthine dehydrogenase
No full textThe objective of the study described in this thesis was to show that enzymes, especially immobilized enzymes, can be advantageously used in synthetic organic chemistry.In Chapter 1 enzymes are introduced and the advantages discussed when these highly active and specific biocatalysts are immobilized, i.e. , attached to a solid support. Criteria for general acceptation of a specific enzyme as a routine catalyst in the organic-chemistry laboratory are stated. The reasons for the choice of xanthine oxidase as a model enzyme and some relevant properties are given.The solid support used for the immobilization determines to a large extent the ultimate characteristics of the immobilized enzyme. In Chapter 2 properties of an ideal support and guidelines for the evaluation of a specific support arediscussed. Various supports are treated in some detail.The mode of immobilization is also very important, especially with respect to the eventual specific activity of the immobilized enzyme. In Chapter 3 the various methods of immobilization are discussed. Just as with the supports (Chapter 2), special attention is given to the ones investigated in this study.In Chapter 4 various properties of immobilized milk xantine oxidase are described, as well as the stabilization by coimmobilization with protein, superoxide dismutase and catalase. It is concluded that conversion of substrate on a preparativescale can be performed conveniently, but that for efficient application a more stable enzyme preparation is desired.Chicken-liver xanthine dehydrogenase is an enzyme very similar to milk xanthine oxidase. In Chapter 5 the reasons are given why it was expected that the liver enzyme would be more stable and practical for synthetic application. The immobilization and the properties of the free and immobilized enzyme are described. Analogous to the milk enzyme, the operational stability of xanthine dehydrogenase is much lower than the storage stability.In order to determine the substrate limits of xanthine oxidase more systematical ly, so that more-reliable predictions would be possible, series of substrates were synthesized for this purpose. In Chapter 6 the synthesis of 7-(p-X-phenyl) pteridin-4-ones and the oxidation by free and immobilized xanthine oxidase are presented. As X becomes more electron withdrawing, the rate of oxidation decreases. It is therefore concluded that the electron donation from substrate to enzyme must be the rate-limiting step.Convenient oxidation of the above substrates and easy product isolation was possible on a small preparative scale. The limited stability of xanthine oxidase demanded however a relatively large amount of enzyme. In Chapter 7 an easy and mild immobilization procedure, using gelatin as support and glutaraldehyde as cross-linking agent, is presented. Whole milk can be used as starting enzyme solution and no isolation is required. The resulting preparation of immobilized xanthine oxidase is very cheap, highly active, relatively stable and suitable for application in organic synthesis in a continuous manner.In Chapter 8 the improvement of the immobilization method with gelatin is described and the extension to the immobilization of whole cells, i.e. , Arthrobacter cells containing xanthine-oxidase activity. These cells were chosen because of their high specific activity, their substrate activation instead of inhibition and their expected higher stability. Immobilized Arthrobacter xanthineoxidase is indeed highly active, more stable and has a different substrate specificity than milk xanthine oxidase. Therefore, a wider spectrum of substrates can be conveniently and efficiently oxidized.In the final Chapter 9 additional information, mostly gathered at a later stage than the time of publication, is given and discussed.The end conclusion is: Xanthine oxidase, either from whole milk or Arthrobacter, when immobilized in glutaraldehyde-crosslinked gelatin, can be conveniently used for the oxidation of a wide range of substrates in a continuous fashion.<p/
DCOPS and bandits: Exploration and exploitation in decentralised coordination
No full textReal life coordination problems are characterised by stochasticity and a lack of a priori knowledge about the interactions between agents. However, decentralised constraint optimisation problems (DCOPs), a widely adopted framework for modelling decentralised coordination tasks, assumes perfect knowledge of these factors, thus limiting its practical applicability. To address this shortcoming, we introduce the MAB–DCOP, in which the interactions between agents are modelled by multi-armed bandits (MABs). Unlike canonical DCOPs, a MAB–DCOP is not a single shot optimisation problem. Rather, it is a sequential one in which agents need to coordinate in order to strike a balance between acquiring knowledge about the a priori unknown and stochastic interactions (exploration), and taking the currently believed optimal joint action (exploitation), so as to maximise the cumulative global utility over a finite time horizon. We propose Heist, the first asymptotically optimal algorithm for coordination under stochasticity and lack of prior knowledge. Heist solves MAB–DCOPs in a decentralised fashion using a generalised distributive law (GDL) message passing phase to find the joint action with the highest upper confidence bound (UCB) on global utility. We demonstrate that Heist outperforms other state of the art techniques from the MAB and DCOP literature by up to 1.5 orders of magnitude on MAB–DCOPs in experimental settings
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
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
Development of Systems to Improve Cotton Module Shape
Get PDFProperly constructed modules will prevent reduced lint value and increased ginning costs when significant rainfall occurs. Additionally, cotton producers often have difficulty finding adequate labor during harvest. These issues were addressed by developing a graphical operator feedback system, a biomass package measurement system, a powered tramper, and an autonomous module forming system. A system that provided feedback on the module shape by recording the position of the tramper and carriage was used to direct the operator to move cotton to appropriate locations. The system correctly predicted the height of 67% of data points. Use of the feedback system resulted in a 55% reduction in water collection area of the modules. The module builder operators indicated that the system was useful. The module builder feedback system is a simple, useful, and inexpensive tool that can have a rapid payback for producers. A powered tramper, with an auger to move cotton to the center of the module, was developed to replace the conventional tramper. The powered tramper operated automatically without affecting the operating speed or pressure of the tramper cylinder. During testing, the powered tramper was observed moving cotton to the center and crowned modules were produced. A biomass package measurement system was developed to record the height at multiple points on the top surface of modules. The system was found to produce repeatable measurements with an error of 5 cm. Data collected with this system did not indicate a difference in module shape when using the powered tramper; however, during these tests the powered tramper was turned off prematurely due to an improperly sized valve on the module builder. An automated module building system capable of both moving and tramping cotton was developed. This system utilized the feedback system sensors and photoelectric sensors to determine the location of cotton in the builder. A wireless display allowed the boll buggy operator to control the automatic system. The automatic system constructed modules with 64% less water collection area in an average time of 37.4 min. Cotton producers indicated that the system was easy to use and of significant value in reducing labor requirements
- …
