Department of
Knowledge Engineering

SIKS-DKE Colloquia

201**1**

Frans Oliehoek, MIT, Boston

Heuristic Search of Multiagent Influence Space

__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.

Background: www.cassantec.com

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.