TY - THES
AB - We study partially observable Markov decision processes (POMDPs) with objectives used in verification and artificial intelligence. The qualitative analysis problem given a POMDP and an objective asks whether there is a strategy (policy) to ensure that the objective is satisfied almost surely (with probability 1), resp. with positive probability (with probability greater than 0). For POMDPs with limit-average payoff, where a reward value in the interval [0,1] is associated to every transition, and the payoff of an infinite path is the long-run average of the rewards, we consider two types of path constraints: (i) a quantitative limit-average constraint defines the set of paths where the payoff is at least a given threshold L1 = 1. Our main results for qualitative limit-average constraint under almost-sure winning are as follows: (i) the problem of deciding the existence of a finite-memory controller is EXPTIME-complete; and (ii) the problem of deciding the existence of an infinite-memory controller is undecidable. For quantitative limit-average constraints we show that the problem of deciding the existence of a finite-memory controller is undecidable. We present a prototype implementation of our EXPTIME algorithm. For POMDPs with w-regular conditions specified as parity objectives, while the qualitative analysis problems are known to be undecidable even for very special case of parity objectives, we establish decidability (with optimal complexity) of the qualitative analysis problems for POMDPs with parity objectives under finite-memory strategies. We establish optimal (exponential) memory bounds and EXPTIME-completeness of the qualitative analysis problems under finite-memory strategies for POMDPs with parity objectives. Based on our theoretical algorithms we also present a practical approach, where we design heuristics to deal with the exponential complexity, and have applied our implementation on a number of well-known POMDP examples for robotics applications. For POMDPs with a set of target states and an integer cost associated with every transition, we study the optimization objective that asks to minimize the expected total cost of reaching a state in the target set, while ensuring that the target set is reached almost surely. We show that for general integer costs approximating the optimal cost is undecidable. For positive costs, our results are as follows: (i) we establish matching lower and upper bounds for the optimal cost, both double and exponential in the POMDP state space size; (ii) we show that the problem of approximating the optimal cost is decidable and present approximation algorithms that extend existing algorithms for POMDPs with finite-horizon objectives. We show experimentally that it performs well in many examples of interest. We study more deeply the problem of almost-sure reachability, where given a set of target states, the question is to decide whether there is a strategy to ensure that the target set is reached almost surely. While in general the problem EXPTIME-complete, in many practical cases strategies with a small amount of memory suffice. Moreover, the existing solution to the problem is explicit, which first requires to construct explicitly an exponential reduction to a belief-support MDP. We first study the existence of observation-stationary strategies, which is NP-complete, and then small-memory strategies. We present a symbolic algorithm by an efficient encoding to SAT and using a SAT solver for the problem. We report experimental results demonstrating the scalability of our symbolic (SAT-based) approach. Decentralized POMDPs (DEC-POMDPs) extend POMDPs to a multi-agent setting, where several agents operate in an uncertain environment independently to achieve a joint objective. In this work we consider Goal DEC-POMDPs, where given a set of target states, the objective is to ensure that the target set is reached with minimal cost. We consider the indefinite-horizon (infinite-horizon with either discounted-sum, or undiscounted-sum, where absorbing goal states have zero-cost) problem. We present a new and novel method to solve the problem that extends methods for finite-horizon DEC-POMDPs and the real-time dynamic programming approach for POMDPs. We present experimental results on several examples, and show that our approach presents promising results. In the end we present a short summary of a few other results related to verification of MDPs and POMDPs.
AU - Chmelik, Martin
ID - 1397
TI - Algorithms for partially observable markov decision processes
ER -
TY - THES
AB - Hybrid zones represent evolutionary laboratories, where recombination brings together alleles in combinations which have not previously been tested by selection. This provides an excellent opportunity to test the effect of molecular variation on fitness, and how this variation is able to spread through populations in a natural context. The snapdragon Antirrhinum majus is polymorphic in the wild for two loci controlling the distribution of yellow and magenta floral pigments. Where the yellow A. m. striatum and the magenta A. m. pseudomajus meet along a valley in the Spanish Pyrenees they form a stable hybrid zone Alleles at these loci recombine to give striking transgressive variation for flower colour. The sharp transition in phenotype over ~1km implies strong selection maintaining the hybrid zone. An indirect assay of pollinator visitation in the field found that pollinators forage in a positive-frequency dependent manner on Antirrhinum, matching previous data on fruit set. Experimental arrays and paternity analysis of wild-pollinated seeds demonstrated assortative mating for pigmentation alleles, and that pollinator behaviour alone is sufficient to explain this pattern. Selection by pollinators should be sufficiently strong to maintain the hybrid zone, although other mechanisms may be at work. At a broader scale I examined evolutionary transitions between yellow and anthocyanin pigmentation in the tribe Antirrhinae, and found that selection has acted strate that pollinators are a major determinant of reproductive success and mating patterns in wild Antirrhinum.
AU - Ellis, Thomas
ID - 1398
TI - The role of pollinator-mediated selection in the maintenance of a flower color polymorphism in an Antirrhinum majus hybrid zone
ER -
TY - THES
AB - Horizontal gene transfer (HGT), the lateral acquisition of genes across existing species
boundaries, is a major evolutionary force shaping microbial genomes that facilitates
adaptation to new environments as well as resistance to antimicrobial drugs. As such,
understanding the mechanisms and constraints that determine the outcomes of HGT
events is crucial to understand the dynamics of HGT and to design better strategies to
overcome the challenges that originate from it.
Following the insertion and expression of a newly transferred gene, the success of an
HGT event will depend on the fitness effect it has on the recipient (host) cell. Therefore,
predicting the impact of HGT on the genetic composition of a population critically
depends on the distribution of fitness effects (DFE) of horizontally transferred genes.
However, to date, we have little knowledge of the DFE of newly transferred genes, and
hence little is known about the shape and scale of this distribution.
It is particularly important to better understand the selective barriers that determine
the fitness effects of newly transferred genes. In spite of substantial bioinformatics
efforts to identify horizontally transferred genes and selective barriers, a systematic
experimental approach to elucidate the roles of different selective barriers in defining
the fate of a transfer event has largely been absent. Similarly, although the fact that
environment might alter the fitness effect of a horizontally transferred gene may seem
obvious, little attention has been given to it in a systematic experimental manner.
In this study, we developed a systematic experimental approach that consists of
transferring 44 arbitrarily selected Salmonella typhimurium orthologous genes into an
Escherichia coli host, and estimating the fitness effects of these transferred genes at a
constant expression level by performing competition assays against the wild type.
In chapter 2, we performed one-to-one competition assays between a mutant strain
carrying a transferred gene and the wild type strain. By using flow cytometry we
estimated selection coefficients for the transferred genes with a precision level of 10-3,and obtained the DFE of horizontally transferred genes. We then investigated if these
fitness effects could be predicted by any of the intrinsic properties of the genes, namely,
functional category, degree of complexity (protein-protein interactions), GC content,
codon usage and length. Our analyses revealed that the functional category and length
of the genes act as potential selective barriers. Finally, using the same procedure with
the endogenous E. coli orthologs of these 44 genes, we demonstrated that gene dosage is
the most prominent selective barrier to HGT.
In chapter 3, using the same set of genes we investigated the role of environment on the
success of HGT events. Under six different environments with different levels of stress
we performed more complex competition assays, where we mixed all 44 mutant strains
carrying transferred genes with the wild type strain. To estimate the fitness effects of
genes relative to wild type we used next generation sequencing. We found that the DFEs
of horizontally transferred genes are highly dependent on the environment, with
abundant gene–by-environment interactions. Furthermore, we demonstrated a
relationship between average fitness effect of a gene across all environments and its
environmental variance, and thus its predictability. Finally, in spite of the fitness effects
of genes being highly environment-dependent, we still observed a common shape of
DFEs across all tested environments.
AU - Acar, Hande
ID - 1121
TI - Selective barriers to horizontal gene transfer
ER -
TY - THES
AB - Computer graphics is an extremely exciting field for two reasons. On the one hand,
there is a healthy injection of pragmatism coming from the visual effects industry
that want robust algorithms that work so they can produce results at an increasingly
frantic pace. On the other hand, they must always try to push the envelope and
achieve the impossible to wow their audiences in the next blockbuster, which means
that the industry has not succumb to conservatism, and there is plenty of room to
try out new and crazy ideas if there is a chance that it will pan into something
useful.
Water simulation has been in visual effects for decades, however it still remains
extremely challenging because of its high computational cost and difficult artdirectability.
The work in this thesis tries to address some of these difficulties.
Specifically, we make the following three novel contributions to the state-of-the-art
in water simulation for visual effects.
First, we develop the first algorithm that can convert any sequence of closed
surfaces in time into a moving triangle mesh. State-of-the-art methods at the time
could only handle surfaces with fixed connectivity, but we are the first to be able to
handle surfaces that merge and split apart. This is important for water simulation
practitioners, because it allows them to convert splashy water surfaces extracted
from particles or simulated using grid-based level sets into triangle meshes that can
be either textured and enhanced with extra surface dynamics as a post-process.
We also apply our algorithm to other phenomena that merge and split apart, such
as morphs and noisy reconstructions of human performances.
Second, we formulate a surface-based energy that measures the deviation of a
water surface froma physically valid state. Such discrepancies arise when there is a
mismatch in the degrees of freedom between the water surface and the underlying
physics solver. This commonly happens when practitioners use a moving triangle
mesh with a grid-based physics solver, or when high-resolution grid-based surfaces
are combined with low-resolution physics. Following the direction of steepest
descent on our surface-based energy, we can either smooth these artifacts or turn
them into high-resolution waves by interpreting the energy as a physical potential.
Third, we extend state-of-the-art techniques in non-reflecting boundaries to handle spatially and time-varying background flows. This allows a novel new
workflow where practitioners can re-simulate part of an existing simulation, such
as removing a solid obstacle, adding a new splash or locally changing the resolution.
Such changes can easily lead to new waves in the re-simulated region that would
reflect off of the new simulation boundary, effectively ruining the illusion of a
seamless simulation boundary between the existing and new simulations. Our
non-reflecting boundaries makes sure that such waves are absorbed.
AU - Bojsen-Hansen, Morten
ID - 1122
TI - Tracking, correcting and absorbing water surface waves
ER -
TY - THES
AB - Motivated by topological Tverberg-type problems in topological combinatorics and by classical
results about embeddings (maps without double points), we study the question whether a finite
simplicial complex K can be mapped into Rd without triple, quadruple, or, more generally, r-fold points (image points with at least r distinct preimages), for a given multiplicity r ≤ 2. In particular, we are interested in maps f : K → Rd that have no global r -fold intersection points, i.e., no r -fold points with preimages in r pairwise disjoint simplices of K , and we seek necessary and sufficient conditions for the existence of such maps.
We present higher-multiplicity analogues of several classical results for embeddings, in particular of the completeness of the Van Kampen obstruction for embeddability of k -dimensional
complexes into R2k , k ≥ 3. Speciffically, we show that under suitable restrictions on the dimensions(viz., if dimK = (r ≥ 1)k and d = rk \ for some k ≥ 3), a well-known deleted product criterion (DPC ) is not only necessary but also sufficient for the existence of maps without global r -fold points. Our main technical tool is a higher-multiplicity version of the classical Whitney trick , by which pairs of isolated r -fold points of opposite sign can be eliminated by local modiffications of the map, assuming codimension d – dimK ≥ 3.
An important guiding idea for our work was that suffciency of the DPC, together with an old
result of Özaydin's on the existence of equivariant maps, might yield an approach to disproving the remaining open cases of the the long-standing topological Tverberg conjecture , i.e., to construct maps from the N -simplex σN to Rd without r-Tverberg points when r not a prime power and
N = (d + 1)(r – 1). Unfortunately, our proof of the sufficiency of the DPC requires codimension d – dimK ≥ 3, which is not satisfied for K = σN .
In 2015, Frick [16] found a very elegant way to overcome this \codimension 3 obstacle" and
to construct the first counterexamples to the topological Tverberg conjecture for all parameters(d; r ) with d ≥ 3r + 1 and r not a prime power, by a reduction1 to a suitable lower-dimensional skeleton, for which the codimension 3 restriction is satisfied and maps without r -Tverberg points exist by Özaydin's result and sufficiency of the DPC.
In this thesis, we present a different construction (which does not use the constraint method) that yields counterexamples for d ≥ 3r , r not a prime power.
AU - Mabillard, Isaac
ID - 1123
TI - Eliminating higher-multiplicity intersections: an r-fold Whitney trick for the topological Tverberg conjecture
ER -