Optimal Search Strategies for Pollutant Source Localization

This paper is aimed at developing optimal motion planning for a single autonomous surface vehicle (ASV) equipped with an on-board pollutant sensor that will maximize the sensor-related information available for source seeking. The ASV uses a nonlinear diffusion model of the pollutant source to estimate the intensity/level of the pollution at the present ASV location. The rate of detection of particles depends on the relative distance between the ASV and the source. First, we use a probabilistic map of the source location built through the sensor information for a dynamic motion planning of source seeking based on an entropy reduction formulation, where an appropriately defined Fisher information matrix (FIM) is used for entropy reduction or information gain. We derive the FIM for the set-up and investigate optimal trajectories. Next, we present an online nonlinear Monte Carlo algorithm that uses the obtained sensor information about pollutant at different vehicle locations to update a probabilistic uncertainty map of pollutant source location. As the mission unfolds the ASV motion is computed by considering a moving-horizon interval of decision, which will allow for the inclusion of new information available for optimal motion planning. The proposed motion planning approach is extended to take into account external disturbances and it is able to minimize the uncertainty in the pollutant source. Finally, we provide two case studies to demonstrate efficacy of the proposed motion planning algorithm.

Assessing Digital Surface Models by Verifying Shadows: A Sensor Network Approach

François Golay, Mina Karzand, Claudio Magalhaes Carneiro, Martin Vetterli

We propose to use wireless sensor networks to assess the accuracy and application of Digital Surface Models (DSM) for the study of shadowing and solar radiation over the built environment. Using the ability of sensor network data to provide information about solar radiation and predicting the exact time of the day that the Sun starts radiating a sensor, a comparative study and statistical analysis can be undertaken in order to evaluate the accuracy of the DSM for shadowing and radiation studies using image processing techniques. Two DSMs of the EPFL campus with different cell resolutions (1 meter and 0.5 meters), considering only information about ground, buildings with vertical walls and trees, are constructed step by step and employed. Three DSMs of the same campus with a cell resolution of 1 meter derived from raw LIDAR data and common interpolation techniques, such as Triangulated Irregular Network (TIN), kriging, Inverse Distance Weighting (IDW), are also used for comparison.

2009

Distributed Constraint Optimization

Thomas Léauté

Distributed Constraint Satisfaction (DisCSP) and Distributed Constraint Optimization (DCOP) are formal frameworks that can be used to model a variety of problems in which multiple decision-makers cooperate towards a common goal: from computing an equilibrium of a game, to vehicle routing problems, to combinatorial auctions. In this thesis, we independently address two important issues in such multi-agent problems: 1) how to provide strong guarantees on the protection of the privacy of the participants, and 2) how to anticipate future, uncontrollable events. On the privacy front, our contributions depart from previous work in two ways. First, we consider not only constraint privacy (the agents' private costs) and decision privacy (keeping the complete solution secret), but also two other types of privacy that have been largely overlooked in the literature: agent privacy, which has to do with protecting the identities of the participants, and topology privacy, which covers information about the agents' co-dependencies. Second, while previous work focused mainly on quantitatively measuring and reducing privacy loss, our algorithms provide stronger, qualitative guarantees on what information will remain secret. Our experiments show that it is possible to provide such privacy guarantees, while still scaling to much larger problems than the previous state of the art. When it comes to reasoning under uncertainty, we propose an extension to the DCOP framework, called DCOP under Stochastic Uncertainty (StochDCOP), which includes uncontrollable, random variables with known probability distributions that model uncertain, future events. The problem becomes one of making "optimal" offline decisions, before the true values of the random variables can be observed. We consider three possible concepts of optimality: minimizing the expected cost, minimizing the worst-case cost, or maximizing the probability of a-posteriori optimality. We propose a new family of StochDCOP algorithms, exploring the tradeoffs between solution quality, computational and message complexity, and privacy. In particular, we show how discovering and reasoning about co-dependencies on common random variables can yield higher-quality solutions.

EPFL2011

Distributed Constraint Optimization under Stochastic Uncertainty

Boi Faltings, Thomas Léauté

In many real-life optimization problems involving multiple agents, the rewards are not necessarily known exactly in advance, but rather depend on sources of exogenous uncertainty. For instance, delivery companies might have to coordinate to choose who should serve which foreseen customer, under uncertainty in the locations of the customers. The framework of Distributed Constraint Optimization under Stochastic Uncertainty was proposed to model such problems; in this paper, we generalize this formalism by introducing the concept of evaluation functions that model various optimization criteria. We take the example of three such evaluation functions, expectation, consensus, and robustness, and we adapt and generalize two previous algorithms accordingly. Our experimental results on a class of Vehicle Routing Problems show that incomplete algorithms are not only cheaper than complete ones (in terms of simulated time, Non-Concurrent Constraint Checks, and information exchange), but they are also often able to find the optimal solution. We also show that exchanging more information about the dependencies of their respective cost functions on the sources of uncertainty can help the agents discover higher-quality solutions.

2011

Distributed Constraint Optimization

Thomas Léauté

EPFL2011