Abstract: This chapter gives an overview of the state of the art in decision-theoretic models to describe cooperation between multiple agents in a dynamic environment.
Making (near-) optimal decisions in such settings gets harder when the number of agents grows or the uncertainty about the environment increases. It is essential to have compact models, because otherwise just representing the decision problem
becomes intractable. Several such model descriptions and approximate solution methods, studied in the Interactive Collaborative Information Systems project, are presented and illustrated in the context of crisis management.
Abstract: This paper presents a sampling strategy for
mobile gas sensors. Sampling points are selected using a modified artificial potential field (APF) approach, which balances multiple criteria to direct sensor measurements towards locations of high mean concentration, high concentration variance and areas for which the uncertainty about the gas distribution model is still large. By selecting in each step the most often suggested close-by easurement
location, the proposed approach introduces a locality constraint that allows planning suitable paths for mobile gas sensors. Initial results in simulation and in real-world experiments with a gas-sensitive micro-drone demonstrate the suitability of the proposed sampling strategy for gas distribution mapping and its use for gas source localization.
Abstract: This paper appeared at the ISCRAM 2010  and presents an intelligent system facilitating better in-
formed decision making under severe uncertainty, as often found in emergency management. The
construction of decision-relevant scenarios, being plausible descriptions of a situation and its future
development, is used as a rationale for collecting, organizing, filtering and processing information for
decision making. The development of scenarios is geared to assessing decision alternatives, thus avoiding
time-consuming analysis and processing of irrelevant information.
The scenarios are constructed in a distributed setting allowing for a flexible adaptation of reasoning (prin-
ciples and processes) to the problem at hand and the information available. Each decision can be founded
on a coherent set of scenarios, which was constructed using the best expertise available within a limited
timeframe. Our theoretical framework is demonstrated in a distributed decision support system by
orchestrating both automated systems and human experts into workflows tailored to each specific problem.
Abstract: Probabilistic graphical models, and in particular Bayesian networks, are nowa-
days well established as a modeling tool for domains with uncertainty. The capability of dealing with uncertainty is essential for any intelligent system. With BayesLib, we provide a JAVA library for creating, editing and querying Bayesian networks in software applications. Comparing to our previous Bayesian-net libraries, one important difference is that it is now implemented in Java. Therefore, it can be run on any platform with an installed Java Runtime Environment (jre) without recompilation. It has an internal xml parser to parse xml formatted files. This XML format is based on Microsoft Research’s XBN (for "Bayesian network in XML") standard format, and therefore facilitates communication with other systems. Thus, with this software, the Bayesian net can now be easily embedded in an Enterprise or web application stacks, and can be used in a multi user environment.
Abstract: In complex strategic decision-making situations the need for well-structured support arises. To evaluate decision alternatives, information about the situation and its development must be determined, managed and processed by the best available experts. For various types of information different reasoning principles have been developed: deterministic, probabilistic, fuzzy and techniques for reasoning under ignorance (i.e., the likelihood of an event cannot be quantified). We propose a new approach based on Decision Maps supporting decision makers under fundamental uncertainty by generating descriptions of different possible situation developments (scenarios) in a distributed manner. The scenarios are evaluated using Multi-Criteria Decision Analysis techniques.
Abstract: In this work we consider the problem of multiagent planning under sensing and acting uncertainty with a one time-step delay in communication. We adopt decentralized partially observable Markov processes (Dec-POMDPs) as our planning framework. When instantaneous and noise-free communication is available, agents can instantly share local observations. This eﬀectively reduces the decentralized planning problem to a centralized one, with a signiﬁcant decrease in planning complexity. However, instantaneous communication is a strong assumption, as it requires the agents to synchronize at every time step. Therefore, we explore planning in Dec-POMDP settings in which communication is delayed by one time step. We show that such situations can be modeled by Bayesian games in which the types of the agents are deﬁned by their last private observation. We will apply Bayesian games to deﬁne a value function QBG on the joint belief space, and we will show that it is the optimal payoﬀ function for our Dec-POMDP setting with one time-step delayed communication. The QBG -value function is piecewise linear and convex over the joint belief space, which we will use to deﬁne QBG -value iteration. Finally, we will adapt Perseus, an approximate POMDP solver, to compute QBG -value functions, and we will use it to perform some proof-of-concept experiments.
Abstract: This paper presents a distributed system facilitating robust decision-making under uncertainty in complex situations often found in strategic emergency management. The construction of decision-relevant scenarios, each being a consistent, coherent and plausible description of a situation and its future development, is used as a rationale for collecting, organizing, filtering and processing information for decision-making. The construction of scenarios is targeted at assessing decision alternatives avoiding time-consuming processing of irrelevant information. The scenarios are constructed in a distributed setting ensuring that each decision can be founded on a coherent and consistent set of assessments and assumptions provided by the best (human or artificial) experts available within limited time. Our theoretical framework is illustrated by means of an emergency management example.
Abstract: Probabilistic graphical models, and in particular Bayesian networks, are nowadays well established as a modeling tool for domains with
uncertainty. In the SHELL outreach project, we have build a Bayesian network model for petrophysical decision support: the system estimates mineral composition based on borehole estimates. The system uses advanced hybrid Monte Carlo methods for inference. Unfortunately, we cannot disclose the system for Shell. Therefore, to demonstrate the method we have built a demonstrator for similar kind of inference in a toy-domain. What is the chemical composition of wine, given taste observations?
Note that this is a toy model for demonstration purposes. The model does not pretend to be realistic in any way.
Abstract: Decentralized partially observable Markov decision processes (Dec-POMDPs) constitute a generic and expressive framework for multiagent planning under uncertainty. However, planning optimally is difficult because solutions map local observation histories to actions, and the number of such histories grows exponentially in the planning horizon. In this work, we identify a criterion that allows for lossless clustering of observation histories: i.e., we prove that when two histories satisfy the criterion, they have the same optimal value and thus can be treated as one. We show how this result can be exploited in optimal policy search and demonstrate empirically that it can provide a speed-up of multiple orders of magnitude, allowing the optimal solution of significantly larger problems. We also perform an empirical analysis of the generality of our clustering method, which suggests that it may also be useful in other (approximate) Dec-POMDP solution methods.
Abstract: We consider the problem of cooperative multiagent planning under uncertainty, formalized as a decentralized partially observable Markov decision process (Dec-POMDP). Unfortunately, in these models optimal planning is provably intractable. By communicating their local observations before they take actions, agents synchronize their knowledge of the environment, and the planning problem reduces to a centralized POMDP. As such, relying on communication significantly reduces the complexity of planning. In the real world however, such communication might fail temporarily. We present a step towards more realistic communication models for Dec-POMDPs by proposing a model that: (1) allows that communication might be delayed by one or more time steps, and (2) explicitly considers future probabilities of successful communication. For our model, we discuss how to efﬁciently compute an (approximate) value function and corresponding policies, and we demonstrate our theoretical results with encouraging experiments.
Abstract: Results from disaster research suggest that methods for coordination between individual emergency responders and organizations should recognize the independence and autonomy of these actors. These actor features are key factors in effective adaptation and improvisation of response to emergency situations which are inherently uncertain. Autonomy and adaptability are also well-known aspects of a multi-agent system (MAS). In this paper we present two MAS strategies that can effectively handle aircraft deicing incidents. These MAS strategies help improve to prevent and reduce e.g. airplane delays at deicing stations due to changing weather conditions or incidents at the station, where aircraft agents adopting pre-made plans that would act on behalf of aircraft pilots or companies, would only create havoc. Herein each agent using its own decision mechanism deliberates about the uncertainty in the problem domain and the preferences (or priorities) of the agents. Furthermore, taking both these issues into account each proposed MAS strategy outperforms a naive first-come, first-served coordination strategy. The simulation results help pilots and companies taking decisions with respect to the scheduling of the aircraft for deicing when unexpected incidents occur: they provide insights in the impacts and means for robust selection of incident-specific strategies on e.g. deicing station delays of (individual) aircraft.
Abstract: Probabilistic graphical models, and in particular Bayesian networks, are nowadays well established as a modeling tool for domains with
uncertainty. A drawback is that large, complex graphical models are intractable for exact computation. Therefore there is a lot of research interest in approximate inference.
The lack of open source "reference" implementations hampers progress in research on approximate inference. Methods differ widely in terms of quality and performance characteristics, which also depend in different ways on various properties of the graphical models. Finding the best approximate inference method for a particular application therefore often requires empirical comparisons. However, implementing and debugging these methods takes a lot of time which could otherwise be spent on research. Therefore we have developed libDAI. libDAI is a free/open source C++ library (licensed under GPL) that provides implementations of various (deterministic) approximate inference methods for discrete graphical models. libDAI supports arbitrary `factor graphs` with discrete variables (this includes discrete Markov Random Fields and Bayesian Networks).
This release is an additional contribution to the LibDAI library. This code implements the Z2 algorithm, a particular way of correcting the Belief Propagation (BP) solution, developed in the ICIS project SNN1 (see Gomez (2009), Approximate inference on planar graphs using Loop Calculus and Belief Propagation).
Abstract: The Dec-POMDP is a model for multi-agent planning under uncertainty that has received increasingly more attention over the recent years. In this work we propose a new heuristic QBG that can be used in various algorithms for Dec-POMDPs and describe differences and similarities with QMDP and QPOMDP. An experimental evaluation shows that, at the price of some computation, QBG gives a consistently tighter upper bound to the maximum value obtainable.
Abstract: Decision making under uncertainty is fraught with
pitfalls for human thinking: biases prevail. The combination of
a scenario-based approach with multi-criteria decision analysis
assists in making value judgements, trade-offs and uncertainties
explicit. Scenarios, which are constructed in a distributedmanner
involving multiple experts from different domains, assist in over-coming e.g. the prominence effect and confirmation bias. Further-more, support is provided to handle the uncertainty associated
with each scenario without imposing unjustified assumptions
on each piece of information. We develop a relative reliability
concept,which differs from standard probability assessments as
it is sensitive to the context, such as the decision problem at hand,
the decision makers’ requirements and the available information.
This approach maintains the flexibility of the distributed system
by allowing the experts to adapt the information they provide and
the likelihood assessments thereof to the situation. Our approach
is illustrated by an emergency management exampl
Abstract: Decentralized POMDPs (Dec-POMDPs) are becoming increasingly popular as models for multiagent planning under uncertainty, but solving a Dec-POMDP exactly is known to be an intractable combinatorial optimization problem. In this paper we apply the Cross-Entropy (CE) method, a recently introduced method for combinatorial optimization, to Dec-POMDPs, resulting in a randomized (sampling-based) algorithm for approximately solving Dec-POMDPs. This algorithm operates by sampling
pure policies from an appropriately parametrized stochastic policy, and then evaluates these policies either exactly or approximately in order to define the next stochastic policy to sample from, and so on until
convergence. Experimental results demonstrate that the CE method can search huge spaces efficiently, supporting our claim that combinatorial optimization methods can bring leverage to the approximate solution of Dec-POMDPs.
Abstract: In this position paper a number of hypotheses are outlined concerning the effect of three measurable human factors, namely subjective stress, arousal and mood, on human decision making performance; taking into account the amount of risk involved in the decision. The proposed domain of application involves critical situations: situations in which time-limits, uncertainty and possibly dire consequences provide an ideal context to apply the results. A tangible objective is to provide the basis for a demonstrator which can measure subjective stress, arousal and mood on the job, provide runtime feedback and positively influence the human decision making process.
Abstract: In this position paper a number of hypotheses are posited concerning the effect of measurable human factors, such as subjective stress, arousal and mood, on the performance of human decision making; taking into account the amount of risk involved in the decision. The proposed domain of application is crisis management: a situation in which time-limits, uncertainty and possibly dire consequences provide an ideal context to assess the validity of our hypotheses. Experimentation involves both people in management functions and non-management functions. The final objective is to provide the basis for a demonstrator which can measure mood, arousal and subjective stress on the job, provide runtime feedback and ergo positively influence human decision making processes.
Abstract: This paper introduces the MultiAgent Decision Process software toolbox, an open source C++ library for decision-theoretic planning under uncertainty in multiagent systems. It provides support for several multiagent models, such as POSGs, Dec-POMDPs and MMDPs. The toolbox aims to reduce development time for planning algorithms and to provide a benchmarking platform by providing a number of commonly used problem descriptions. It features a parser for a text-based ﬁle format for discrete Dec-POMDPs, shared functionality for planning algorithms, as well as the implementation of several Dec-POMDP planners. We describe design goals and architecture of the toolbox, and provide an overview of its functionality, illustrated by some usage examples. Finally we report on current and future work.
Abstract: Research in the area of Multi-Agent System (MAS) organization has shown that the ability for a MAS to adapt its organizational structure can be beneficial when coping with dynamics and uncertainty in the MASs environment. Different types of reorganization exist, such as changing relations and interaction patterns between agents, changing agent roles and changing the coordination style in the MAS. In this paper we propose a framework for agent Coordination and Reorganization (AgentCoRe) that incorporates each of these aspects of reorganization. We describe both declarative and procedural knowledge an agent uses to decompose and assign tasks, and to reorganize. The RoboCupRescue simulation environment is used to demonstrate how AgentCoRe is used to build a MAS that is capable of reorganizing itself by changing relations, interaction patterns and agent roles.