Department of Knowledge Engineer

Abstract: Multiagent lanning under uncertainty has seen important progress in recent years. Two techniques, in particular, have substantially advanced efficiency and scalability of multiagent planning. First, heuristic search gains traction by pruning large portions of the joint policy space. Second, influence-based abstraction reformulates the search space of joint policies into a smaller space of influences, which represent the probabilistic effects that agents' policies may exert on one another.
These techniques have been used independently, but never together, to solve solve larger problems (for Dec-POMDPs and subclasses) than was previously possible.
In this talk, I will explain how we combine multiagent A* search and influence-based abstraction into a single algorithm. This enables an initial investigation into whether or not the two techniques bring complementary gains. Our empirical results indicate that, even with a relatively simple heuristic, A* can provide significant computational savings on top of those already afforded by influence-space search, thereby bringing a significant contribution to the field of multiagent planning under uncertainty.

September 21, 2011, 16:00
Kateřina Stañková, Delft Center for Systems and Control, Delft University of Technology, The Netherlands.
Game-Theoretical and Optimal Control Methods in Systems Biology

Abstract: In this talk we will discuss game-theoretical and optimal control methods to deal with predator-prey hybrid problems.
We will consider a specific predator-prey system in which predatory mites (Typhlodromus pyri, the predator) forage red spider mites (Panonychus ulmi, the prey) residing over fruit trees.
During the warm season, which lasts for about 5 months, both predatory mites and red spider mites can be in an active state (reproducing, feeding, moving around) or in a diapause state (unable to reproduce of to feed, but protected from either bad weather conditions or predation). In between seasons (during winter) all fruit-tree red spider mites that were active at the end of the season die, while a portion of those which entered diapause in the previous season survives. On the other hand, predatory mites are less vulnerable to the winter: a portion of all of those being active in the end of the previous season survives.
The main research questions we put forward are: what behavior is optimal for either population, how does this behavior influences the inter-seasonal dynamics of the system, and whether this behavior is evolutionary stable. We propose a game-theoretical framework to describe the dynamics of the system. The intra-seasonal interaction is modeled as a non-cooperative continuous-time game played over a season (over a finite horizon), with players representing the population levels of predator and of prey, respectively. The time-dependent decision variables of the players are their active/diapause ratio, that is the portion of individuals being in the active phase and in diapause (quiescent, passive phase). Unlike in the standard Lotka-Volterra formulation, the player’s state is defined by both time-varying population size and associated energy: this allows a more realistic description of predator-prey interactions.
The goal of each player is to maximize its fitness, a function of both population size and energy. Encompassing the inter-seasonal dynamics into the model transforms the problem into a more complex hybrid game. In this talk the current results of the studies will be presented: we first investigate optimal behavior of the prey, the decisions of the predator being fixed; we then look at more general optimal strategies in the two-player game; and we investigate the dynamics of the system and its long-term behavior.

August 29, 2011, 16:00
Roeland Merks, Centrum Wiskunde & Informatica, Amsterdam, The Netherlands.
Cell-based modeling of angiogenic blood vessel sprouting: cell-ECM interaction and tip-cell selection

Abstract: Angiogenesis is a topic of intensive experimental investigation, so its phenomenology and the molecular signals contributing to it have been well characterized. Yet it is poorly understood how the biological components fit together dynamically to drive the outgrowth of blood vessels.
Cell-based simulation models of angiogenesis describe endothelial cell behaviour in detail, help analyze how cells assemble into blood vessels, and reveal how cell behaviour depends on the microenvironment the cells themselves produce. Our previous simulation models, based on the Cellular Potts model, have shown that the elongated shape of endothelial cells is key to correct spatiotemporal in silico replication of vascular network growth. We also identified a new stochastic mechanism for angiogenic sprouting.
Here, I will briefly discuss new insights into the role of cell shape and stochastic motility during vascular branching. Then I will present recent results on the role of tip cells, suggesting that tip cell-stalk cell interactions accelerate angiogenic sprouting. I will also discuss our recent cell-based modeling studies of cell-extracellular matrix interactions during angiogenesis.

August 26, 2011, 11:00
Tamar Keasar, Dept. of Science Education - Biology, University of Haifa, Israel.
Joint parent-offspring control of brood size in a parasitoid wasp

Abstract: Polyembryony is a unique mode of development that involves the production of a clone of genetically identical embryos from a single egg. This development style appears to carry a high price tag, because it clones an unproven genotype at the expense of genetic diversity in a brood. The following advantages have been proposed to balance this cost: polyembryony may enable the offspring to adjust their own brood size to environmental conditions during development; it may promote parental fitness by reducing resource competition among the developing offspring; or it may compensate for constraints on maternal egg number.
We tested these hypotheses with the tiny polyembryonic parasitoid wasp Copidosoma koehleri. Brood sizes of parasitoids that developed in starved hosts were not lower than in fed ones, providing no support for adjustment of brood size to conditions during development. We did find evidence, however, for decreased resource competition between genetically related offspring.
Thus, polyembryony may induce cooperation among developing young, thereby reducing parent-offspring conflict regarding resource allocation. Indirect and comparative evidence also supports the hypothesis that polyembryony may allow increased fecundity in small-bodied parasitoids.
We conclude that the study of insect polyembryony can provide unique insights into the determination of animal brood sizes.

June 28, 2011, 16:00
Rene Sitters, Dept. of Econometrics and Operations Research, VU Amsterdam (http://personal.vu.nl/r.a.sitters/)
TSP on Cubic and Subcubic Graphs

Abstract: (joint work with Sylvia Boyd, Suzanne van der Ster and Leen Stougie) We study the Travelling Salesman Problem (TSP) on the metric completion of cubic and subcubic graphs, which is known to be NP-hard. The problem is of interest because of its relation to the famous 4/3 conjecture for metric TSP, which says that the integrality gap, i.e., the worst case ratio between the optimal values of the TSP and its linear programming relaxation, is $4/3$. Using polyhedral techniques in an interesting way, we obtain a polynomial-time 4/3-approximation algorithm for this problem on cubic graphs, improving upon Christofides' 3/2-approximation, and upon the $3/2-5/389 \approx 1.487$-approximation ratio by Gamarnik, Lewenstein and Svirdenko for the case the graphs are also 3-edge connected. We also prove that, as an upper bound, the 4/3 conjecture is true for this problem on cubic graphs. For subcubic graphs we obtain a polynomial-time 7/5-approximation algorithm and a 7/5 bound on the integrality gap.

June 23, 2011, 16:00
TES Raghavan, University of Illinois at Chicago
Core stability, Shapley value and modiclus for assignment games
Abstract: We prove that the core of an assignment game is stable if and only if there is a matching between the two types of players such that the corresponding entries in the underlying matrix are all row and column maximums.
We identify other easily verifiable matrix properties and show their equivalence to various known sufficient conditions for core-stability.
By these matrix characterizations we found that on the class of assignment games, largeness of the core, extendability and exactness of the game are all equivalent conditions, and strictly imply the stability of the core.
As a consequence Shapley value lies in the core of any exact assignment game.
The modiclus, a relative of the prenucleolus, assigns a singleton to any cooperative TU game. We show that the modiclus selects a member of the core for any assignment game that has a stable core.

June 1, 2011, 16:00
T. Parthasarathy, Indian Statistical Institute, Chennai Centre, India
Semidefinite linear complemetarity problem
Abstract: Semidefinite linear complementarity problem (SDLCP) is a natural generalization of Linear complementarity problem (LCP). Let S-n denote the space of real symmetric matrices of order n. Let L be a linear transformation from S-n to S-n. Let Q be an element of S-n. Then the SDLCP(L,Q) is to find a symmetric positive semidefinite matrix X such that L(X)+Q is also positive semidefinite with trace X(L(X)+Q)=0. We will consder three linear transformations, Lyapunov, Stein and Multiplicative transformations and show solutions exist under some assumptions. We want to see how far the results from LCP can be proved in the SDLCP setting.
We will mention some open problems at the end.

May 12, 2011, 16:00
David Morrison, Swedish University of Agricultural Sciences
Is there enough biology in bioinformatics?
Abstract: There is a long tradition of mathematicians and computer scientists collaborating with people in the life sciences (eg. most medical research is a collaboration between medical practitioners and statisticians), but in the past 20 years this tradition has taken a quantitative leap with the development of bioinformatics, which is a nexus between mathematicians, computer scientists and biologists the like of which has not been seen before. The biological insights gained through bioinformatics are truly impressive, especially in molecular genetics. Nevertheless, it is pertinent to note that biologists are clearly the junior partner in this exercise, with most of the work being driven by computational interests (and restrictions) rather than long-established requirements of biologists. In this talk I will present two examples from my own research experience, in which key biological pre-requisites have been overlooked by all of the parties concerned: multiple sequence alignment, and phylogenetic networks. This has lead to the production of bioinformatic techniques that are inappropriate for some purposes, although the associated computer programs have been widely used (and therefore misused). It seems that biologists are not yet communicating clearly enough with the mathematicians and computer scientists (or vice versa), at least with regard to clearly recognizing and enunciating all issues that may be of importance in developing computational methods.

March 2, 2011, 16:00
Arturo Tejada Ruiz, Delft University of Technology
Towards Automatic Control of Transmission Electron Microscopes: Modeling, Sensors, and Control Strategies
Abstract: For the past few years, the Delft Center of Systems and Control has been part of the Condor Project Condor, an academic-industrial effort managed by the Embedded Systems Institute in Eindhoven in partnership with FEI Company. Condor seeks to set the foundations for the development of autonomous Transmission Electron Microscopes (TEMs) capable of performing high-throughput nano-measurements, tools that are needed for biology, materials science, and semiconductor research.
The presentation will summarize Measure-by-Wire, the control oriented TEM modeling and analysis architecture that frames our work. As will be argued, most control loops in a TEM are image-based and have slow, sporadic sensing rates, which requires the development of both image-based sensors and a theoretical framework for slow, sporadic feedback control. Our recent efforts on both areas will also be presented, emphasizing our contributions on defocus control and specimen drift control.
This presentation should be of interest for researchers interested in TEM technology, stochastic signal analysis, Markov jump linear systems, image-based control systems and related topics.

February 23, 2011, 16:00
Akihiro Kishimoto, Tokyo Institute of Technology
Depth-First Proof-Number Search in the Presence of Repetitions
Abstract: Depth-first proof-number search (df-pn) is a powerful AND/OR tree search algorithm proven to be effective in solving positions in games. However, df-pn has a notorious problem of infinite loops when applied to domains with repetitions. Df-pn(r) practically cures it by ignoring proof and disproof numbers that may lead to infinite loops.
In this talk, I point out that df-pn(r) has a serious issue of underestimating proof and disproof numbers, while it also suffers from the overestimation problem occurring in directed acyclic graph. I present two practical solutions to these problems. While bypassing infinite loops, the threshold controlling algorithm (TCA) solves the underestimation problem by increasing the thresholds of df-pn.
The source node detection algorithm (SNDA) detects the cause of overestimation and modifies the computation of proof and disproof numbers. Both TCA and SNDA are implemented on top of df-pn to solve tsume-shogi (checkmating problem in Japanese chess). Results show that df-pn with TCA and SNDA is far superior to df-pn(r). Our tsume-shogi solver is able to solve several difficult positions previously unsolved by any other solvers.

March 17, 2011, 16:00
Frank Kirschnick, Ph.D., CEO, Cassantec Ltd., and Katerina Stamou, M.Sc., Solution Architect, Cassantec Ltd.
Fleet Intelligence: Industrial Asset Management meets Machine Learning
Abstract: Operation of mission-critical industrial assets, such as turbines, generators, transformers, pumps, compressors, oscillators or pulverizers, is a challenging task. Commercial objectives of operators are jeopardized by the risk and costs of downtime and lost output, in a trade-off with preventive maintenance and insurance costs. To ensure safe and reliable operation of assets in the power and processing industries, operators rely on condition monitoring and diagnostic techniques. These techniques are primarily based on recorded asset condition and process data, such as vibration, lubricant, thermal, acoustic, ultrasonic, electrical, pressure, flow or speed parameters. With this data, diagnostic techniques allow inferring and reporting malfunction before failure and damage occurs. This may significantly reduce the risk and costs of unscheduled downtime.
Typically, the earlier a malfunction warning is given, the higher the benefits for the asset operator. In many circumstances, the prognostic horizon of condition data is key to commercially optimal asset management. Yet, malfunction prognostics require more disciplined condition and process data management, more sophisticated stochastic modelling and more computational intelligence than pure diagnostics. So far, most "predictive diagnostic" approaches ask for operator gut feel rather than considering the full prognostic horizon of the available data histories, often archived over several years.
We present a new approach to intelligent malfunction prognostics, utilizing the prognostic horizon of the available data histories and exploiting complementary operator experience and manufacturer know-how. Based on a novel combination of best practice techniques from Operations Research, Artificial Intelligence and Data Mining, we show how to drive a fleet-wide automated, distributed learning process allowing detection and prevention of mechanical and electrical malfunctions earlier and with higher accuracy than traditional condition monitoring and diagnostic systems did.
The presentation will be supported by an online demo of recent practice applications in the power industries.

January 26, 2011, 16.00
Tomas Klos, Delft University of Technology
Enumeration and Exact Design of Weighted Voting Games
Abstract: In many multiagent settings, situations arise in which agents must collectively make decisions while not every agent is supposed to have an equal amount of influence in the outcome of such a decision.
Weighted voting games are often used to deal with these situations. The amount of influence that an agent has in a weighted voting game can be measured by means of various power indices.
This paper studies the problem of finding a weighted voting game in which the distribution of the influence among the agents is as close as possible to a given target value. We propose a method to exactly solve this problem. This method relies on a new efficient procedure for enumerating weighted voting games of a fixed number of agents.
The enumeration algorithm we propose works by exploiting the properties of a specific partial order over the class of weighted voting games. The algorithm enumerates weighted voting games of a fixed number of agents in time exponential in the number of agents, and polynomial in the number of games output. As a consequence we obtain an exact anytime algorithm for designing weighted voting games.(Joint work with Bart de Keizer en Yingqian Zhang)

February 9, 2011, 16.00
Krzysztof Apt, Universiteit van Amsterdam
Diffusion in Social Networks with Competing Products
Abstract: We study a threshold model in social networks, in which the nodes influenced by their neighbours can adopt one out of several alternatives. We provide polynomial time algorithms that allow us to determine whether in a given social network a specific alternative can, respectively has to, be adopted by all nodes. We also provide a polynomial time algorithm that allows us to determine whether a given social network yields a unique outcome. Finally, we exhibit a class of social networks that possess a unique outcome. Our algorithms are obtained by first providing a characterization of the class of graphs that result in possible (respectively necessary) adoption of a product by the whole network and a characterization of the networks that admit a unique outcome.

January 12, 2011, 16.00
Reinoud Joosten, University of Twente
Stochastic games with endogenous transitions
Abstract: We introduce a stochastic game in which transition probabilities depend on the history of the play, i.e., the players' past action choices. To solve this new type of game under the limiting average reward criterion, we determine the set of jointly-convergent pure-strategy rewards which can be supported by equilibria involving threats. For motivational and expository purposes, we examine the following setting. Each period, two agents exploiting a fishery choose between catching with restraint or without. The fish stock is in either of two states, High or Low, and in the latter each action pair yields lower payoffs. Restraint is harmless to the fish, but it is a dominated strategy in each stage game. Absence of restraint damages the resource, i.e., the less restraint the agents show, the higher the probablities that Low occurs at the next stage of the play. This state may even become 'absorbing', i.e., transitions to High become impossible.