title: Democratic Representations

abstract:
  Minimization of the $\ell_{\infty}$ (or maximum) norm subject to a constraint
that imposes consistency to an underdetermined system of linear equations finds
use in a large number of practical applications, including vector quantization,
approximate nearest neighbor search, peak-to-average power ratio (or "crest
factor") reduction in communication systems, and peak force minimization in
robotics and control. This paper analyzes the fundamental properties of signal
representations obtained by solving such a convex optimization problem. We
develop bounds on the maximum magnitude of such representations using the
uncertainty principle (UP) introduced by Lyubarskii and Vershynin, and study
the efficacy of $\ell_{\infty}$-norm-based dynamic range reduction. Our
analysis shows that matrices satisfying the UP, such as randomly subsampled
Fourier or i.i.d. Gaussian matrices, enable the computation of what we call
democratic representations, whose entries all have small and similar magnitude,
as well as low dynamic range. To compute democratic representations at low
computational complexity, we present two new, efficient convex optimization
algorithms. We finally demonstrate the efficacy of democratic representations
for dynamic range reduction in a DVB-T2-based broadcast system.


title:
Performance Evaluation of ECC in Single and Multi Processor
  Architectures on FPGA Based Embedded System

abstract:
  Cryptographic algorithms are computationally costly and the challenge is more
if we need to execute them in resource constrained embedded systems. Field
Programmable Gate Arrays (FPGAs) having programmable logic de- vices and
processing cores, have proven to be highly feasible implementation platforms
for embedded systems providing lesser design time and reconfig- urability.
Design parameters like throughput, resource utilization and power requirements
are the key issues. The popular Elliptic Curve Cryptography (ECC), which is
superior over other public-key crypto-systems like RSA in many ways, such as
providing greater security for a smaller key size, is cho- sen in this work and
the possibilities of its implementation in FPGA based embedded systems for both
single and dual processor core architectures in- volving task parallelization
have been explored. This exploration, which is first of its kind considering
the other existing works, is a needed activity for evaluating the best possible
architectural environment for ECC implementa- tion on FPGA (Virtex4 XC4VFX12,
FF668, -10) based embedded platform.


title: Monte Carlo Study of a wide range of Molecular Spintronics Devices

abstract:
  Molecular spintronics devices (MSDs) are highly promising candidates for
enabling quantum computation and revolutionizing computer logic and memory. An
advanced MSD will require the placement of magnetic molecules between the two
ferromagnetic (FM) electrodes. Recent experimental studies showed that some
magnetic molecules produced unprecedented strong exchange couplings between the
two FM electrodes leading to intriguing magnetic and transport properties in a
MSD. Future development of MSDs will critically depend on obtaining an in-depth
understanding of the molecule induced exchange coupling, and its impact on
switchability, functional temperature range, and stability. However, the large
size of MSD systems and fragile device fabrication scheme continue to limit the
theoretical and experimental studies of magnetic attributes produced by
molecules in a MSD. This paper theoretically studies the MSD by performing
Monte Carlo simulations (MCS). Our MCS encompasses the full range of MSDs that
can be realized by establishing different kinds of magnetic interaction between
magnetic molecules and FM electrodes. Our MSDs are represented by a 2D Ising
model. We studied the effect of a wide range of molecule-FM electrode couplings
on the basic properties of MSDs. This wide range covered (i) molecule
possessing ferromagnetic coupling with both FM electrodes, (ii) molecule
possessing antiferromagnetic coupling with both FM electrodes, and (iii)
molecule possessing ferromagnetic coupling with one electrode and
antiferromagnetic coupling with another FM electrode. Our MCS will enable the
fundamental understanding and designing of a wide range of novel MSDs utilizing
a variety of molecules and FM electrodes; these studies will also benefits
nanomaterials based spintronics devices employing nanoclusters and quantum dots
as the device elements.


title:
Long Time Results for a Weakly Interacting Particle System in Discrete
  Time

abstract:
  We study long time behavior of a discrete time weakly interacting particle
system, and the corresponding nonlinear Markov process in $\mathbb{R}^d$,
described in terms of a general stochastic evolution equation. In a setting
where the state space of the particles is compact such questions have been
studied in previous works, however for the case of an unbounded state space
very few results are available. Under suitable assumptions on the problem data
we study several time asymptotic properties of the $N$-particle system and the
associated nonlinear Markov chain. In particular we show that the evolution
equation for the law of the nonlinear Markov chain has a unique fixed point and
starting from an arbitrary initial condition convergence to the fixed point
occurs at an exponential rate. The empirical measure $\mu_{n}^{N}$ of the
$N$-particles at time $n$ is shown to converge to the law $\mu_{n}$ of the
nonlinear Markov process at time $n$, in the Wasserstein-1 distance, in
$L^{1}$, as $N\to \infty$, uniformly in $n$. Several consequences of this
uniform convergence are studied, including the interchangeability of the limits
$n\to \infty$ and $N\to\infty$ and the propagation of chaos property at $n =
\infty$. Rate of convergence of $\mu_{n}^{N}$ to $\mu_{n}$ is studied by
establishing uniform in time polynomial and exponential probability
concentration estimates.


title: Marchenko-Pastur Law for Tyler's M-estimator

abstract:
  This paper studies the limiting behavior of Tyler's M-estimator for the
scatter matrix, in the regime that the number of samples $n$ and their
dimension $p$ both go to infinity, and $p/n$ converges to a constant $y$ with
$0<y<1$. We prove that when the data samples $x_1, \ldots, x_n$ are identically
and independently generated from the Gaussian distribution $\mathcal{N}(0, I)$,
the operator norm of the difference between a properly scaled Tyler's
M-estimator and $\sum_{i=1}^n x_i x_i^\top/n$ tends to zero. As a result, the
spectral distribution of Tyler's M-estimator converges weakly to the
Mar\v{c}enko-Pastur distribution.


title: On the distribution of orbits in affine varieties

abstract:
  Given an affine variety $X$, a morphism $\phi:X\to X$, a point $\alpha\in X$,
and a Zariski closed subset $V$ of $X$, we show that the forward $\phi$-orbit
of $\alpha$ meets $V$ in at most finitely many infinite arithmetic
progressions, and the remaining points lie in a set of Banach density zero.
This may be viewed as a weak asymptotic version of the Dynamical Mordell-Lang
Conjecture for affine varieties. The results hold in arbitrary characteristic,
and the proof uses methods of ergodic theory applied to compact Berkovich
spaces.


title:
Networks of Influence Diagrams: A Formalism for Representing Agents'
  Beliefs and Decision-Making Processes

abstract:
  This paper presents Networks of Influence Diagrams (NID), a compact, natural
and highly expressive language for reasoning about agents beliefs and
decision-making processes. NIDs are graphical structures in which agents mental
models are represented as nodes in a network; a mental model for an agent may
itself use descriptions of the mental models of other agents. NIDs are
demonstrated by examples, showing how they can be used to describe conflicting
and cyclic belief structures, and certain forms of bounded rationality. In an
opponent modeling domain, NIDs were able to outperform other computational
agents whose strategies were not known in advance. NIDs are equivalent in
representation to Bayesian games but they are more compact and structured than
this formalism. In particular, the equilibrium definition for NIDs makes an
explicit distinction between agents optimal strategies, and how they actually
behave in reality.


title:
Analogical Dissimilarity: Definition, Algorithms and Two Experiments in
  Machine Learning

abstract:
  This paper defines the notion of analogical dissimilarity between four
objects, with a special focus on objects structured as sequences. Firstly, it
studies the case where the four objects have a null analogical dissimilarity,
i.e. are in analogical proportion. Secondly, when one of these objects is
unknown, it gives algorithms to compute it. Thirdly, it tackles the problem of
defining analogical dissimilarity, which is a measure of how far four objects
are from being in analogical proportion. In particular, when objects are
sequences, it gives a definition and an algorithm based on an optimal alignment
of the four sequences. It gives also learning algorithms, i.e. methods to find
the triple of objects in a learning sample which has the least analogical
dissimilarity with a given object. Two practical experiments are described: the
first is a classification problem on benchmarks of binary and nominal data, the
second shows how the generation of sequences by solving analogical equations
enables a handwritten character recognition system to rapidly be adapted to a
new writer.


title:
A Heuristic Search Approach to Planning with Continuous Resources in
  Stochastic Domains

abstract:
  We consider the problem of optimal planning in stochastic domains with
resource constraints, where the resources are continuous and the choice of
action at each step depends on resource availability. We introduce the HAO*
algorithm, a generalization of the AO* algorithm that performs search in a
hybrid state space that is modeled using both discrete and continuous state
variables, where the continuous variables represent monotonic resources. Like
other heuristic search algorithms, HAO* leverages knowledge of the start state
and an admissible heuristic to focus computational effort on those parts of the
state space that could be reached from the start state by following an optimal
policy. We show that this approach is especially effective when resource
constraints limit how much of the state space is reachable. Experimental
results demonstrate its effectiveness in the domain that motivates our
research: automated planning for planetary exploration rovers.


title: Latent Tree Models and Approximate Inference in Bayesian Networks

abstract:
  We propose a novel method for approximate inference in Bayesian networks
(BNs). The idea is to sample data from a BN, learn a latent tree model (LTM)
from the data offline, and when online, make inference with the LTM instead of
the original BN. Because LTMs are tree-structured, inference takes linear time.
In the meantime, they can represent complex relationship among leaf nodes and
hence the approximation accuracy is often good. Empirical evidence shows that
our method can achieve good approximation accuracy at low online computational
cost.


title:
A Unifying Framework for Structural Properties of CSPs: Definitions,
  Complexity, Tractability

abstract:
  Literature on Constraint Satisfaction exhibits the definition of several
structural properties that can be possessed by CSPs, like (in)consistency,
substitutability or interchangeability. Current tools for constraint solving
typically detect such properties efficiently by means of incomplete yet
effective algorithms, and use them to reduce the search space and boost search.
  In this paper, we provide a unifying framework encompassing most of the
properties known so far, both in CSP and other fields literature, and shed
light on the semantical relationships among them. This gives a unified and
comprehensive view of the topic, allows new, unknown, properties to emerge, and
clarifies the computational complexity of the various detection problems.
  In particular, among the others, two new concepts, fixability and
removability emerge, that come out to be the ideal characterisations of values
that may be safely assigned or removed from a variables domain, while
preserving problem satisfiability. These two notions subsume a large number of
known properties, including inconsistency, substitutability and others.
  Because of the computational intractability of all the property-detection
problems, by following the CSP approach we then determine a number of
relaxations which provide sufficient conditions for their tractability. In
particular, we exploit forms of language restrictions and local reasoning.


title: Compositional Belief Update

abstract:
  In this paper we explore a class of belief update operators, in which the
definition of the operator is compositional with respect to the sentence to be
added. The goal is to provide an update operator that is intuitive, in that its
definition is based on a recursive decomposition of the update sentences
structure, and that may be reasonably implemented. In addressing update, we
first provide a definition phrased in terms of the models of a knowledge base.
While this operator satisfies a core group of the benchmark Katsuno-Mendelzon
update postulates, not all of the postulates are satisfied. Other
Katsuno-Mendelzon postulates can be obtained by suitably restricting the
syntactic form of the sentence for update, as we show. In restricting the
syntactic form of the sentence for update, we also obtain a hierarchy of update
operators with Winsletts standard semantics as the most basic interesting
approach captured. We subsequently give an algorithm which captures this
approach; in the general case the algorithm is exponential, but with some
not-unreasonable assumptions we obtain an algorithm that is linear in the size
of the knowledge base. Hence the resulting approach has much better complexity
characteristics than other operators in some situations. We also explore other
compositional belief change operators: erasure is developed as a dual operator
to update; we show that a forget operator is definable in terms of update; and
we give a definition of the compositional revision operator. We obtain that
compositional revision, under the most natural definition, yields the Satoh
revision operator.


title:
A Rigorously Bayesian Beam Model and an Adaptive Full Scan Model for
  Range Finders in Dynamic Environments

abstract:
  This paper proposes and experimentally validates a Bayesian network model of
a range finder adapted to dynamic environments. All modeling assumptions are
rigorously explained, and all model parameters have a physical interpretation.
This approach results in a transparent and intuitive model. With respect to the
state of the art beam model this paper: (i) proposes a different functional
form for the probability of range measurements caused by unmodeled objects,
(ii) intuitively explains the discontinuity encountered in te state of the art
beam model, and (iii) reduces the number of model parameters, while maintaining
the same representational power for experimental data. The proposed beam model
is called RBBM, short for Rigorously Bayesian Beam Model. A maximum likelihood
and a variational Bayesian estimator (both based on expectation-maximization)
are proposed to learn the model parameters.
  Furthermore, the RBBM is extended to a full scan model in two steps: first,
to a full scan model for static environments and next, to a full scan model for
general, dynamic environments. The full scan model accounts for the dependency
between beams and adapts to the local sample density when using a particle
filter. In contrast to Gaussian-based state of the art models, the proposed
full scan model uses a sample-based approximation. This sample-based
approximation enables handling dynamic environments and capturing
multi-modality, which occurs even in simple static environments.


title:
Optimal Strategies for Simultaneous Vickrey Auctions with Perfect
  Substitutes

abstract:
  We derive optimal strategies for a bidding agent that participates in
multiple, simultaneous second-price auctions with perfect substitutes. We prove
that, if everyone else bids locally in a single auction, the global bidder
should always place non-zero bids in all available auctions, provided there are
no budget constraints. With a budget, however, the optimal strategy is to bid
locally if this budget is equal or less than the valuation. Furthermore, for a
wide range of valuation distributions, we prove that the problem of finding the
optimal bids reduces to two dimensions if all auctions are identical. Finally,
we address markets with both sequential and simultaneous auctions,
non-identical auctions, and the allocative efficiency of the market.


title: Adaptive Stochastic Resource Control: A Machine Learning Approach

abstract:
  The paper investigates stochastic resource allocation problems with scarce,
reusable resources and non-preemtive, time-dependent, interconnected tasks.
This approach is a natural generalization of several standard resource
management problems, such as scheduling and transportation problems. First,
reactive solutions are considered and defined as control policies of suitably
reformulated Markov decision processes (MDPs). We argue that this reformulation
has several favorable properties, such as it has finite state and action
spaces, it is aperiodic, hence all policies are proper and the space of control
policies can be safely restricted. Next, approximate dynamic programming (ADP)
methods, such as fitted Q-learning, are suggested for computing an efficient
control policy. In order to compactly maintain the cost-to-go function, two
representations are studied: hash tables and support vector regression (SVR),
particularly, nu-SVRs. Several additional improvements, such as the application
of limited-lookahead rollout algorithms in the initial phases, action space
decomposition, task clustering and distributed sampling are investigated, too.
Finally, experimental results on both benchmark and industry-related data are
presented.


title:
Overcoming Auger recombination in nanocrystal quantum dot laser using
  spontaneous emission enhancement

abstract:
  We propose a method to overcome Auger recombination in nanocrystal quantum
dot lasers using cavity-enhanced spontaneous emission. We derive a numerical
model for a laser composed of nanocrystal quantum dots coupled to optical
nanocavities with small mode-volume. Using this model, we demonstrate that
spontaneous emission enhancement of the biexciton transition lowers the lasing
threshold by reducing the effect of Auger recombination. We analyze a photonic
crystal nanobeam cavity laser as a realistic device structure that implements
the proposed approach.


title: Online Planning Algorithms for POMDPs

abstract:
  Partially Observable Markov Decision Processes (POMDPs) provide a rich
framework for sequential decision-making under uncertainty in stochastic
domains. However, solving a POMDP is often intractable except for small
problems due to their complexity. Here, we focus on online approaches that
alleviate the computational complexity by computing good local policies at each
decision step during the execution. Online algorithms generally consist of a
lookahead search to find the best action to execute at each time step in an
environment. Our objectives here are to survey the various existing online
POMDP methods, analyze their properties and discuss their advantages and
disadvantages; and to thoroughly evaluate these online approaches in different
environments under various metrics (return, error bound reduction, lower bound
improvement). Our experimental results indicate that state-of-the-art online
heuristic search methods can handle large POMDP domains efficiently.


title: Learning Partially Observable Deterministic Action Models

abstract:
  We present exact algorithms for identifying deterministic-actions effects and
preconditions in dynamic partially observable domains. They apply when one does
not know the action model(the way actions affect the world) of a domain and
must learn it from partial observations over time. Such scenarios are common in
real world applications. They are challenging for AI tasks because traditional
domain structures that underly tractability (e.g., conditional independence)
fail there (e.g., world features become correlated). Our work departs from
traditional assumptions about partial observations and action models. In
particular, it focuses on problems in which actions are deterministic of simple
logical structure and observation models have all features observed with some
frequency. We yield tractable algorithms for the modified problem for such
domains.
  Our algorithms take sequences of partial observations over time as input, and
output deterministic action models that could have lead to those observations.
The algorithms output all or one of those models (depending on our choice), and
are exact in that no model is misclassified given the observations. Our
algorithms take polynomial time in the number of time steps and state features
for some traditional action classes examined in the AI-planning literature,
e.g., STRIPS actions. In contrast, traditional approaches for HMMs and
Reinforcement Learning are inexact and exponentially intractable for such
domains. Our experiments verify the theoretical tractability guarantees, and
show that we identify action models exactly. Several applications in planning,
autonomous exploration, and adventure-game playing already use these results.
They are also promising for probabilistic settings, partially observable
reinforcement learning, and diagnosis.


title: The Ultrametric Constraint and its Application to Phylogenetics

abstract:
  A phylogenetic tree shows the evolutionary relationships among species.
Internal nodes of the tree represent speciation events and leaf nodes
correspond to species. A goal of phylogenetics is to combine such trees into
larger trees, called supertrees, whilst respecting the relationships in the
original trees. A rooted tree exhibits an ultrametric property; that is, for
any three leaves of the tree it must be that one pair has a deeper most recent
common ancestor than the other pairs, or that all three have the same most
recent common ancestor. This inspires a constraint programming encoding for
rooted trees. We present an efficient constraint that enforces the ultrametric
property over a symmetric array of constrained integer variables, with the
inevitable property that the lower bounds of any three variables are mutually
supportive. We show that this allows an efficient constraint-based solution to
the supertree construction problem. We demonstrate that the versatility of
constraint programming can be exploited to allow solutions to variants of the
supertree construction problem.


title: Interactive Policy Learning through Confidence-Based Autonomy

abstract:
  We present Confidence-Based Autonomy (CBA), an interactive algorithm for
policy learning from demonstration. The CBA algorithm consists of two
components which take advantage of the complimentary abilities of humans and
computer agents. The first component, Confident Execution, enables the agent to
identify states in which demonstration is required, to request a demonstration
from the human teacher and to learn a policy based on the acquired data. The
algorithm selects demonstrations based on a measure of action selection
confidence, and our results show that using Confident Execution the agent
requires fewer demonstrations to learn the policy than when demonstrations are
selected by a human teacher. The second algorithmic component, Corrective
Demonstration, enables the teacher to correct any mistakes made by the agent
through additional demonstrations in order to improve the policy and future
task performance. CBA and its individual components are compared and evaluated
in a complex simulated driving domain. The complete CBA algorithm results in
the best overall learning performance, successfully reproducing the behavior of
the teacher while balancing the tradeoff between number of demonstrations and
number of incorrect actions during learning.


title:
Asymptotic behavior of critical indecomposable multi-type branching
  processes with immigration

abstract:
  In this paper the asymptotic behavior of a critical multi-type branching
process with immigration is described when the offspring mean matrix is
irreducible, in other words, when the process is indecomposable. It is proved
that sequences of appropriately scaled random step functions formed from
periodic subsequences of a critical indecomposable multi-type branching process
with immigration converge weakly towards a process supported by a ray
determined by the Perron vector of the offspring mean matrix. The types can be
partitioned into nonempty mutually disjoint subsets (according to communication
of types) such that the coordinate processes belonging to the same subset are
multiples of the same squared Bessel process, and the coordinate processes
belonging to different subsets are independent.


title: Transductive Rademacher Complexity and its Applications

abstract:
  We develop a technique for deriving data-dependent error bounds for
transductive learning algorithms based on transductive Rademacher complexity.
Our technique is based on a novel general error bound for transduction in terms
of transductive Rademacher complexity, together with a novel bounding technique
for Rademacher averages for particular algorithms, in terms of their
"unlabeled-labeled" representation. This technique is relevant to many advanced
graph-based transductive algorithms and we demonstrate its effectiveness by
deriving error bounds to three well known algorithms. Finally, we present a new
PAC-Bayesian bound for mixtures of transductive algorithms based on our
Rademacher bounds.


title: Asynchronous Forward Bounding for Distributed COPs

abstract:
  A new search algorithm for solving distributed constraint optimization
problems (DisCOPs) is presented. Agents assign variables sequentially and
compute bounds on partial assignments asynchronously. The asynchronous bounds
computation is based on the propagation of partial assignments. The
asynchronous forward-bounding algorithm (AFB) is a distributed optimization
search algorithm that keeps one consistent partial assignment at all times. The
algorithm is described in detail and its correctness proven. Experimental
evaluation shows that AFB outperforms synchronous branch and bound by many
orders of magnitude, and produces a phase transition as the tightness of the
problem increases. This is an analogous effect to the phase transition that has
been observed when local consistency maintenance is applied to MaxCSPs. The AFB
algorithm is further enhanced by the addition of a backjumping mechanism,
resulting in the AFB-BJ algorithm. Distributed backjumping is based on
accumulated information on bounds of all values and on processing concurrently
a queue of candidate goals for the next move back. The AFB-BJ algorithm is
compared experimentally to other DisCOP algorithms (ADOPT, DPOP, OptAPO) and is
shown to be a very efficient algorithm for DisCOPs.


title: Computational Logic Foundations of KGP Agents

abstract:
  This paper presents the computational logic foundations of a model of agency
called the KGP (Knowledge, Goals and Plan model. This model allows the
specification of heterogeneous agents that can interact with each other, and
can exhibit both proactive and reactive behaviour allowing them to function in
dynamic environments by adjusting their goals and plans when changes happen in
such environments. KGP provides a highly modular agent architecture that
integrates a collection of reasoning and physical capabilities, synthesised
within transitions that update the agents state in response to reasoning,
sensing and acting. Transitions are orchestrated by cycle theories that specify
the order in which transitions are executed while taking into account the
dynamic context and agent preferences, as well as selection operators for
providing inputs to transitions.


title:
On the Qualitative Comparison of Decisions Having Positive and Negative
  Features

abstract:
  Making a decision is often a matter of listing and comparing positive and
negative arguments. In such cases, the evaluation scale for decisions should be
considered bipolar, that is, negative and positive values should be explicitly
distinguished. That is what is done, for example, in Cumulative Prospect
Theory. However, contraryto the latter framework that presupposes genuine
numerical assessments, human agents often decide on the basis of an ordinal
ranking of the pros and the cons, and by focusing on the most salient
arguments. In other terms, the decision process is qualitative as well as
bipolar. In this article, based on a bipolar extension of possibility theory,
we define and axiomatically characterize several decision rules tailored for
the joint handling of positive and negative arguments in an ordinal setting.
The simplest rules can be viewed as extensions of the maximin and maximax
criteria to the bipolar case, and consequently suffer from poor decisive power.
More decisive rules that refine the former are also proposed. These refinements
agree both with principles of efficiency and with the spirit of
order-of-magnitude reasoning, that prevails in qualitative decision theory. The
most refined decision rule uses leximin rankings of the pros and the cons, and
the ideas of counting arguments of equal strength and cancelling pros by cons.
It is shown to come down to a special case of Cumulative Prospect Theory, and
to subsume the Take the Best heuristic studied by cognitive psychologists.


title: Extrinsic spin Hall effects measured with lateral spin valve structures

abstract:
  The spin Hall effect (SHE), induced by spin-orbit interaction in nonmagnetic
materials, is one of the promising phenomena for conversion between charge and
spin currents in spintronic devices. The spin Hall (SH) angle is the
characteristic parameter of this conversion. We have performed experiments of
the conversion from spin into charge currents by the SHE in lateral spin valve
structures. We present experimental results on the extrinsic SHEs induced by
doping nonmagnetic metals, Cu or Ag, with impurities having a large spin-orbit
coupling, Bi or Pb, as well as results on the intrinsic SHE of Au. The SH angle
induced by Bi in Cu or Ag is negative and particularly large for Bi in Cu, 10
times larger than the intrinsic SH angle in Au. We also observed a large SH
angle for CuPb but the SHE signal disappeared in a few days. Such an aging
effect could be related to a fast mobility of Pb in Cu and has not been
observed in CuBi alloys.


title:
Amino Acid Interaction Network Prediction using Multi-objective
  Optimization

abstract:
  Protein can be represented by amino acid interaction network. This network is
a graph whose vertices are the proteins amino acids and whose edges are the
interactions between them. This interaction network is the first step of
proteins three-dimensional structure prediction. In this paper we present a
multi-objective evolutionary algorithm for interaction prediction and ant
colony probabilistic optimization algorithm is used to confirm the interaction.


title:
Anytime Induction of Low-cost, Low-error Classifiers: a Sampling-based
  Approach

abstract:
  Machine learning techniques are gaining prevalence in the production of a
wide range of classifiers for complex real-world applications with nonuniform
testing and misclassification costs. The increasing complexity of these
applications poses a real challenge to resource management during learning and
classification. In this work we introduce ACT (anytime cost-sensitive tree
learner), a novel framework for operating in such complex environments. ACT is
an anytime algorithm that allows learning time to be increased in return for
lower classification costs. It builds a tree top-down and exploits additional
time resources to obtain better estimations for the utility of the different
candidate splits. Using sampling techniques, ACT approximates the cost of the
subtree under each candidate split and favors the one with a minimal cost. As a
stochastic algorithm, ACT is expected to be able to escape local minima, into
which greedy methods may be trapped. Experiments with a variety of datasets
were conducted to compare ACT to the state-of-the-art cost-sensitive tree
learners. The results show that for the majority of domains ACT produces
significantly less costly trees. ACT also exhibits good anytime behavior with
diminishing returns.


title: AND/OR Multi-Valued Decision Diagrams (AOMDDs) for Graphical Models

abstract:
  Inspired by the recently introduced framework of AND/OR search spaces for
graphical models, we propose to augment Multi-Valued Decision Diagrams (MDD)
with AND nodes, in order to capture function decomposition structure and to
extend these compiled data structures to general weighted graphical models
(e.g., probabilistic models). We present the AND/OR Multi-Valued Decision
Diagram (AOMDD) which compiles a graphical model into a canonical form that
supports polynomial (e.g., solution counting, belief updating) or constant time
(e.g. equivalence of graphical models) queries. We provide two algorithms for
compiling the AOMDD of a graphical model. The first is search-based, and works
by applying reduction rules to the trace of the memory intensive AND/OR search
algorithm. The second is inference-based and uses a Bucket Elimination schedule
to combine the AOMDDs of the input functions via the the APPLY operator. For
both algorithms, the compilation time and the size of the AOMDD are, in the
worst case, exponential in the treewidth of the graphical model, rather than
pathwidth as is known for ordered binary decision diagrams (OBDDs). We
introduce the concept of semantic treewidth, which helps explain why the size
of a decision diagram is often much smaller than the worst case bound. We
provide an experimental evaluation that demonstrates the potential of AOMDDs.


title: Eliciting Single-Peaked Preferences Using Comparison Queries

abstract:
  Voting is a general method for aggregating the preferences of multiple
agents. Each agent ranks all the possible alternatives, and based on this, an
aggregate ranking of the alternatives (or at least a winning alternative) is
produced. However, when there are many alternatives, it is impractical to
simply ask agents to report their complete preferences. Rather, the agents
preferences, or at least the relevant parts thereof, need to be elicited. This
is done by asking the agents a (hopefully small) number of simple queries about
their preferences, such as comparison queries, which ask an agent to compare
two of the alternatives. Prior work on preference elicitation in voting has
focused on the case of unrestricted preferences. It has been shown that in this
setting, it is sometimes necessary to ask each agent (almost) as many queries
as would be required to determine an arbitrary ranking of the alternatives. In
contrast, in this paper, we focus on single-peaked preferences. We show that
such preferences can be elicited using only a linear number of comparison
queries, if either the order with respect to which preferences are
single-peaked is known, or at least one other agents complete preferences are
known. We show that using a sublinear number of queries does not suffice. We
also consider the case of cardinally single-peaked preferences. For this case,
we show that if the alternatives cardinal positions are known, then an agents
preferences can be elicited using only a logarithmic number of queries;
however, we also show that if the cardinal positions are not known, then a
sublinear number of queries does not suffice. We present experimental results
for all elicitation algorithms. We also consider the problem of only eliciting
enough information to determine the aggregate ranking, and show that even for
this more modest objective, a sublinear number of queries per agent does not
suffice for known ordinal or unknown cardinal positions. Finally, we discuss
whether and how these techniques can be applied when preferences are almost
single-peaked.


title: Completeness and Performance Of The APO Algorithm

abstract:
  Asynchronous Partial Overlay (APO) is a search algorithm that uses
cooperative mediation to solve Distributed Constraint Satisfaction Problems
(DisCSPs). The algorithm partitions the search into different subproblems of
the DisCSP. The original proof of completeness of the APO algorithm is based on
the growth of the size of the subproblems. The present paper demonstrates that
this expected growth of subproblems does not occur in some situations, leading
to a termination problem of the algorithm. The problematic parts in the APO
algorithm that interfere with its completeness are identified and necessary
modifications to the algorithm that fix these problematic parts are given. The
resulting version of the algorithm, Complete Asynchronous Partial Overlay
(CompAPO), ensures its completeness. Formal proofs for the soundness and
completeness of CompAPO are given. A detailed performance evaluation of CompAPO
comparing it to other DisCSP algorithms is presented, along with an extensive
experimental evaluation of the algorithm's unique behavior. Additionally, an
optimization version of the algorithm, CompOptAPO, is presented, discussed, and
evaluated.


title: Mechanisms for Making Crowds Truthful

abstract:
  We consider schemes for obtaining truthful reports on a common but hidden
signal from large groups of rational, self-interested agents. One example are
online feedback mechanisms, where users provide observations about the quality
of a product or service so that other users can have an accurate idea of what
quality they can expect. However, (i) providing such feedback is costly, and
(ii) there are many motivations for providing incorrect feedback.
  Both problems can be addressed by reward schemes which (i) cover the cost of
obtaining and reporting feedback, and (ii) maximize the expected reward of a
rational agent who reports truthfully. We address the design of such
incentive-compatible rewards for feedback generated in environments with pure
adverse selection. Here, the correlation between the true knowledge of an agent
and her beliefs regarding the likelihoods of reports of other agents can be
exploited to make honest reporting a Nash equilibrium.
  In this paper we extend existing methods for designing incentive-compatible
rewards by also considering collusion. We analyze different scenarios, where,
for example, some or all of the agents collude. For each scenario we
investigate whether a collusion-resistant, incentive-compatible reward scheme
exists, and use automated mechanism design to specify an algorithm for deriving
an efficient reward mechanism.


title:
Whole Exome Sequencing to Estimate Alloreactivity Potential Between
  Donors and Recipients in Stem Cell Transplantation

abstract:
  Whole exome sequencing was performed on HLA-matched stem cell donors and
transplant recipients to measure sequence variation contributing to minor
histocompatibility antigen differences between the two. A large number of
nonsynonymous single nucleotide polymorphisms were identified in each of the
nine unique donor-recipient pairs tested. This variation was greater in
magnitude in unrelated donors as compared with matched related donors.
Knowledge of the magnitude of exome variation between stem cell transplant
recipients and donors may allow more accurate titration of immunosuppressive
therapy following stem cell transplantation.


title: The Computational Complexity of Dominance and Consistency in CP-Nets

abstract:
  We investigate the computational complexity of testing dominance and
consistency in CP-nets. Previously, the complexity of dominance has been
determined for restricted classes in which the dependency graph of the CP-net
is acyclic. However, there are preferences of interest that define cyclic
dependency graphs; these are modeled with general CP-nets. In our main results,
we show here that both dominance and consistency for general CP-nets are
PSPACE-complete. We then consider the concept of strong dominance, dominance
equivalence and dominance incomparability, and several notions of optimality,
and identify the complexity of the corresponding decision problems. The
reductions used in the proofs are from STRIPS planning, and thus reinforce the
earlier established connections between both areas.


title: A Multiagent Reinforcement Learning Algorithm with Non-linear Dynamics

abstract:
  Several multiagent reinforcement learning (MARL) algorithms have been
proposed to optimize agents decisions. Due to the complexity of the problem,
the majority of the previously developed MARL algorithms assumed agents either
had some knowledge of the underlying game (such as Nash equilibria) and/or
observed other agents actions and the rewards they received.
  We introduce a new MARL algorithm called the Weighted Policy Learner (WPL),
which allows agents to reach a Nash Equilibrium (NE) in benchmark
2-player-2-action games with minimum knowledge. Using WPL, the only feedback an
agent needs is its own local reward (the agent does not observe other agents
actions or rewards). Furthermore, WPL does not assume that agents know the
underlying game or the corresponding Nash Equilibrium a priori. We
experimentally show that our algorithm converges in benchmark
two-player-two-action games. We also show that our algorithm converges in the
challenging Shapleys game where previous MARL algorithms failed to converge
without knowing the underlying game or the NE. Furthermore, we show that WPL
outperforms the state-of-the-art algorithms in a more realistic setting of 100
agents interacting and learning concurrently.
  An important aspect of understanding the behavior of a MARL algorithm is
analyzing the dynamics of the algorithm: how the policies of multiple learning
agents evolve over time as agents interact with one another. Such an analysis
not only verifies whether agents using a given MARL algorithm will eventually
converge, but also reveals the behavior of the MARL algorithm prior to
convergence. We analyze our algorithm in two-player-two-action games and show
that symbolically proving WPLs convergence is difficult, because of the
non-linear nature of WPLs dynamics, unlike previous MARL algorithms that had
either linear or piece-wise-linear dynamics. Instead, we numerically solve WPLs
dynamics differential equations and compare the solution to the dynamics of
previous MARL algorithms.


title: Monte Carlo Sampling Methods for Approximating Interactive POMDPs

abstract:
  Partially observable Markov decision processes (POMDPs) provide a principled
framework for sequential planning in uncertain single agent settings. An
extension of POMDPs to multiagent settings, called interactive POMDPs
(I-POMDPs), replaces POMDP belief spaces with interactive hierarchical belief
systems which represent an agent's belief about the physical world, about
beliefs of other agents, and about their beliefs about others' beliefs. This
modification makes the difficulties of obtaining solutions due to complexity of
the belief and policy spaces even more acute. We describe a general method for
obtaining approximate solutions of I-POMDPs based on particle filtering (PF).
We introduce the interactive PF, which descends the levels of the interactive
belief hierarchies and samples and propagates beliefs at each level. The
interactive PF is able to mitigate the belief space complexity, but it does not
address the policy space complexity. To mitigate the policy space complexity --
sometimes also called the curse of history -- we utilize a complementary method
based on sampling likely observations while building the look ahead
reachability tree. While this approach does not completely address the curse of
history, it beats back the curse's impact substantially. We provide
experimental results and chart future work.


title: From Molecular Dynamics to Brownian Dynamics

abstract:
  Three coarse-grained molecular dynamics (MD) models are investigated with the
aim of developing and analyzing multiscale methods which use MD simulations in
parts of the computational domain and (less detailed) Brownian dynamics (BD)
simulations in the remainder of the domain. The first MD model is formulated in
one spatial dimension. It is based on elastic collisions of heavy molecules
(e.g. proteins) with light point particles (e.g. water molecules). Two
three-dimensional MD models are then investigated. The obtained results are
applied to a simplified model of protein binding to receptors on the cellular
membrane. It is shown that modern BD simulators of intracellular processes can
be used in the bulk and accurately coupled with a (more detailed) MD model of
protein binding which is used close to the membrane.


title: Learning Document-Level Semantic Properties from Free-Text Annotations

abstract:
  This paper presents a new method for inferring the semantic properties of
documents by leveraging free-text keyphrase annotations. Such annotations are
becoming increasingly abundant due to the recent dramatic growth in
semi-structured, user-generated online content. One especially relevant domain
is product reviews, which are often annotated by their authors with pros/cons
keyphrases such as a real bargain or good value. These annotations are
representative of the underlying semantic properties; however, unlike expert
annotations, they are noisy: lay authors may use different labels to denote the
same property, and some labels may be missing. To learn using such noisy
annotations, we find a hidden paraphrase structure which clusters the
keyphrases. The paraphrase structure is linked with a latent topic model of the
review texts, enabling the system to predict the properties of unannotated
documents and to effectively aggregate the semantic properties of multiple
reviews. Our approach is implemented as a hierarchical Bayesian model with
joint inference. We find that joint inference increases the robustness of the
keyphrase clustering and encourages the latent topics to correlate with
semantically meaningful properties. Multiple evaluations demonstrate that our
model substantially outperforms alternative approaches for summarizing single
and multiple documents into a set of semantically salient keyphrases.


title: Solving #SAT and Bayesian Inference with Backtracking Search

abstract:
  Inference in Bayes Nets (BAYES) is an important problem with numerous
applications in probabilistic reasoning. Counting the number of satisfying
assignments of a propositional formula (#SAT) is a closely related problem of
fundamental theoretical importance. Both these problems, and others, are
members of the class of sum-of-products (SUMPROD) problems. In this paper we
show that standard backtracking search when augmented with a simple memoization
scheme (caching) can solve any sum-of-products problem with time complexity
that is at least as good any other state-of-the-art exact algorithm, and that
it can also achieve the best known time-space tradeoff. Furthermore,
backtracking's ability to utilize more flexible variable orderings allows us to
prove that it can achieve an exponential speedup over other standard algorithms
for SUMPROD on some instances.
  The ideas presented here have been utilized in a number of solvers that have
been applied to various types of sum-of-product problems. These system's have
exploited the fact that backtracking can naturally exploit more of the
problem's structure to achieve improved performance on a range of
probleminstances. Empirical evidence of this performance gain has appeared in
published works describing these solvers, and we provide references to these
works.


title: Generic Preferences over Subsets of Structured Objects

abstract:
  Various tasks in decision making and decision support systems require
selecting a preferred subset of a given set of items. Here we focus on problems
where the individual items are described using a set of characterizing
attributes, and a generic preference specification is required, that is, a
specification that can work with an arbitrary set of items. For example,
preferences over the content of an online newspaper should have this form: At
each viewing, the newspaper contains a subset of the set of articles currently
available. Our preference specification over this subset should be provided
offline, but we should be able to use it to select a subset of any currently
available set of articles, e.g., based on their tags. We present a general
approach for lifting formalisms for specifying preferences over objects with
multiple attributes into ones that specify preferences over subsets of such
objects. We also show how we can compute an optimal subset given such a
specification in a relatively efficient manner. We provide an empirical
evaluation of the approach as well as some worst-case complexity results.


title: Policy Iteration for Decentralized Control of Markov Decision Processes

abstract:
  Coordination of distributed agents is required for problems arising in many
areas, including multi-robot systems, networking and e-commerce. As a formal
framework for such problems, we use the decentralized partially observable
Markov decision process (DEC-POMDP). Though much work has been done on optimal
dynamic programming algorithms for the single-agent version of the problem,
optimal algorithms for the multiagent case have been elusive. The main
contribution of this paper is an optimal policy iteration algorithm for solving
DEC-POMDPs. The algorithm uses stochastic finite-state controllers to represent
policies. The solution can include a correlation device, which allows agents to
correlate their actions without communicating. This approach alternates between
expanding the controller and performing value-preserving transformations, which
modify the controller without sacrificing value. We present two efficient
value-preserving transformations: one can reduce the size of the controller and
the other can improve its value while keeping the size fixed. Empirical results
demonstrate the usefulness of value-preserving transformations in increasing
value while keeping controller size to a minimum. To broaden the applicability
of the approach, we also present a heuristic version of the policy iteration
algorithm, which sacrifices convergence to optimality. This algorithm further
reduces the size of the controllers at each step by assuming that probability
distributions over the other agents actions are known. While this assumption
may not hold in general, it helps produce higher quality solutions in our test
problems.


title: A Bilinear Programming Approach for Multiagent Planning

abstract:
  Multiagent planning and coordination problems are common and known to be
computationally hard. We show that a wide range of two-agent problems can be
formulated as bilinear programs. We present a successive approximation
algorithm that significantly outperforms the coverage set algorithm, which is
the state-of-the-art method for this class of multiagent problems. Because the
algorithm is formulated for bilinear programs, it is more general and simpler
to implement. The new algorithm can be terminated at any time and-unlike the
coverage set algorithm-it facilitates the derivation of a useful online
performance bound. It is also much more efficient, on average reducing the
computation time of the optimal solution by about four orders of magnitude.
Finally, we introduce an automatic dimensionality reduction method that
improves the effectiveness of the algorithm, extending its applicability to new
domains and providing a new way to analyze a subclass of bilinear programs.


title: Efficient Informative Sensing using Multiple Robots

abstract:
  The need for efficient monitoring of spatio-temporal dynamics in large
environmental applications, such as the water quality monitoring in rivers and
lakes, motivates the use of robotic sensors in order to achieve sufficient
spatial coverage. Typically, these robots have bounded resources, such as
limited battery or limited amounts of time to obtain measurements. Thus,
careful coordination of their paths is required in order to maximize the amount
of information collected, while respecting the resource constraints. In this
paper, we present an efficient approach for near-optimally solving the NP-hard
optimization problem of planning such informative paths. In particular, we
first develop eSIP (efficient Single-robot Informative Path planning), an
approximation algorithm for optimizing the path of a single robot. Hereby, we
use a Gaussian Process to model the underlying phenomenon, and use the mutual
information between the visited locations and remainder of the space to
quantify the amount of information collected. We prove that the mutual
information collected using paths obtained by using eSIP is close to the
information obtained by an optimal solution. We then provide a general
technique, sequential allocation, which can be used to extend any single robot
planning algorithm, such as eSIP, for the multi-robot problem. This procedure
approximately generalizes any guarantees for the single-robot problem to the
multi-robot case. We extensively evaluate the effectiveness of our approach on
several experiments performed in-field for two important environmental sensing
applications, lake and river monitoring, and simulation experiments performed
using several real world sensor network data sets.


title:
Automated Reasoning in Modal and Description Logics via SAT Encoding:
  the Case Study of K(m)/ALC-Satisfiability

abstract:
  In the last two decades, modal and description logics have been applied to
numerous areas of computer science, including knowledge representation, formal
verification, database theory, distributed computing and, more recently,
semantic web and ontologies. For this reason, the problem of automated
reasoning in modal and description logics has been thoroughly investigated. In
particular, many approaches have been proposed for efficiently handling the
satisfiability of the core normal modal logic K(m), and of its notational
variant, the description logic ALC. Although simple in structure, K(m)/ALC is
computationally very hard to reason on, its satisfiability being
PSPACE-complete.
  In this paper we start exploring the idea of performing automated reasoning
tasks in modal and description logics by encoding them into SAT, so that to be
handled by state-of-the-art SAT tools; as with most previous approaches, we
begin our investigation from the satisfiability in K(m). We propose an
efficient encoding, and we test it on an extensive set of benchmarks, comparing
the approach with the main state-of-the-art tools available. Although the
encoding is necessarily worst-case exponential, from our experiments we notice
that, in practice, this approach can handle most or all the problems which are
at the reach of the other approaches, with performances which are comparable
with, or even better than, those of the current state-of-the-art tools.


title:
Learning Bayesian Network Equivalence Classes with Ant Colony
  Optimization

abstract:
  Bayesian networks are a useful tool in the representation of uncertain
knowledge. This paper proposes a new algorithm called ACO-E, to learn the
structure of a Bayesian network. It does this by conducting a search through
the space of equivalence classes of Bayesian networks using Ant Colony
Optimization (ACO). To this end, two novel extensions of traditional ACO
techniques are proposed and implemented. Firstly, multiple types of moves are
allowed. Secondly, moves can be given in terms of indices that are not based on
construction graph nodes. The results of testing show that ACO-E performs
better than a greedy search and other state-of-the-art and metaheuristic
algorithms whilst searching in the space of equivalence classes.


title: Learning to Reach Agreement in a Continuous Ultimatum Game

abstract:
  It is well-known that acting in an individually rational manner, according to
the principles of classical game theory, may lead to sub-optimal solutions in a
class of problems named social dilemmas. In contrast, humans generally do not
have much difficulty with social dilemmas, as they are able to balance personal
benefit and group benefit. As agents in multi-agent systems are regularly
confronted with social dilemmas, for instance in tasks such as resource
allocation, these agents may benefit from the inclusion of mechanisms thought
to facilitate human fairness. Although many of such mechanisms have already
been implemented in a multi-agent systems context, their application is usually
limited to rather abstract social dilemmas with a discrete set of available
strategies (usually two). Given that many real-world examples of social
dilemmas are actually continuous in nature, we extend this previous work to
more general dilemmas, in which agents operate in a continuous strategy space.
The social dilemma under study here is the well-known Ultimatum Game, in which
an optimal solution is achieved if agents agree on a common strategy. We
investigate whether a scale-free interaction network facilitates agents to
reach agreement, especially in the presence of fixed-strategy agents that
represent a desired (e.g. human) outcome. Moreover, we study the influence of
rewiring in the interaction network. The agents are equipped with
continuous-action learning automata and play a large number of random pairwise
games in order to establish a common strategy. From our experiments, we may
conclude that results obtained in discrete-strategy games can be generalized to
continuous-strategy games to a certain extent: a scale-free interaction network
structure allows agents to achieve agreement on a common strategy, and rewiring
in the interaction network greatly enhances the agents ability to reach
agreement. However, it also becomes clear that some alternative mechanisms,
such as reputation and volunteering, have many subtleties involved and do not
have convincing beneficial effects in the continuous case.


title: An Anytime Algorithm for Optimal Coalition Structure Generation

abstract:
  Coalition formation is a fundamental type of interaction that involves the
creation of coherent groupings of distinct, autonomous, agents in order to
efficiently achieve their individual or collective goals. Forming effective
coalitions is a major research challenge in the field of multi-agent systems.
Central to this endeavour is the problem of determining which of the many
possible coalitions to form in order to achieve some goal. This usually
requires calculating a value for every possible coalition, known as the
coalition value, which indicates how beneficial that coalition would be if it
was formed. Once these values are calculated, the agents usually need to find a
combination of coalitions, in which every agent belongs to exactly one
coalition, and by which the overall outcome of the system is maximized.
However, this coalition structure generation problem is extremely challenging
due to the number of possible solutions that need to be examined, which grows
exponentially with the number of agents involved. To date, therefore, many
algorithms have been proposed to solve this problem using different techniques
ranging from dynamic programming, to integer programming, to stochastic search
all of which suffer from major limitations relating to execution time, solution
quality, and memory requirements.
  With this in mind, we develop an anytime algorithm to solve the coalition
structure generation problem. Specifically, the algorithm uses a novel
representation of the search space, which partitions the space of possible
solutions into sub-spaces such that it is possible to compute upper and lower
bounds on the values of the best coalition structures in them. These bounds are
then used to identify the sub-spaces that have no potential of containing the
optimal solution so that they can be pruned. The algorithm, then, searches
through the remaining sub-spaces very efficiently using a branch-and-bound
technique to avoid examining all the solutions within the searched subspace(s).
In this setting, we prove that our algorithm enumerates all coalition
structures efficiently by avoiding redundant and invalid solutions
automatically. Moreover, in order to effectively test our algorithm we develop
a new type of input distribution which allows us to generate more reliable
benchmarks compared to the input distributions previously used in the field.
Given this new distribution, we show that for 27 agents our algorithm is able
to find solutions that are optimal in 0.175% of the time required by the
fastest available algorithm in the literature. The algorithm is anytime, and if
interrupted before it would have normally terminated, it can still provide a
solution that is guaranteed to be within a bound from the optimal one.
Moreover, the guarantees we provide on the quality of the solution are
significantly better than those provided by the previous state of the art
algorithms designed for this purpose. For example, for the worst case
distribution given 25 agents, our algorithm is able to find a 90% efficient
solution in around 10% of time it takes to find the optimal solution.


title:
Planning over Chain Causal Graphs for Variables with Domains of Size 5
  Is NP-Hard

abstract:
  Recently, considerable focus has been given to the problem of determining the
boundary between tractable and intractable planning problems. In this paper, we
study the complexity of planning in the class C_n of planning problems,
characterized by unary operators and directed path causal graphs. Although this
is one of the simplest forms of causal graphs a planning problem can have, we
show that planning is intractable for C_n (unless P = NP), even if the domains
of state variables have bounded size. In particular, we show that plan
existence for C_n^k is NP-hard for k>=5 by reduction from CNFSAT. Here, k
denotes the upper bound on the size of the state variable domains. Our result
reduces the complexity gap for the class C_n^k to cases k=3 and k=4 only, since
C_n^2 is known to be tractable.


title:
Compiling Uncertainty Away in Conformant Planning Problems with Bounded
  Width

abstract:
  Conformant planning is the problem of finding a sequence of actions for
achieving a goal in the presence of uncertainty in the initial state or action
effects. The problem has been approached as a path-finding problem in belief
space where good belief representations and heuristics are critical for scaling
up. In this work, a different formulation is introduced for conformant problems
with deterministic actions where they are automatically converted into
classical ones and solved by an off-the-shelf classical planner. The
translation maps literals L and sets of assumptions t about the initial
situation, into new literals KL/t that represent that L must be true if t is
initially true. We lay out a general translation scheme that is sound and
establish the conditions under which the translation is also complete. We show
that the complexity of the complete translation is exponential in a parameter
of the problem called the conformant width, which for most benchmarks is
bounded. The planner based on this translation exhibits good performance in
comparison with existing planners, and is the basis for T0, the best performing
planner in the Conformant Track of the 2006 International Planning Competition.


title: Exploiting Single-Cycle Symmetries in Continuous Constraint Problems

abstract:
  Symmetries in discrete constraint satisfaction problems have been explored
and exploited in the last years, but symmetries in continuous constraint
problems have not received the same attention. Here we focus on permutations of
the variables consisting of one single cycle. We propose a procedure that takes
advantage of these symmetries by interacting with a continuous constraint
solver without interfering with it. A key concept in this procedure are the
classes of symmetric boxes formed by bisecting a n-dimensional cube at the same
point in all dimensions at the same time. We analyze these classes and quantify
them as a function of the cube dimensionality. Moreover, we propose a simple
algorithm to generate the representatives of all these classes for any number
of variables at very high rates. A problem example from the chemical
and#64257;eld and the cyclic n-roots problem are used to show the performance
of the approach in practice.


title:
Message-Based Web Service Composition, Integrity Constraints, and
  Planning under Uncertainty: A New Connection

abstract:
  Thanks to recent advances, AI Planning has become the underlying technique
for several applications. Figuring prominently among these is automated Web
Service Composition (WSC) at the "capability" level, where services are
described in terms of preconditions and effects over ontological concepts. A
key issue in addressing WSC as planning is that ontologies are not only formal
vocabularies; they also axiomatize the possible relationships between concepts.
Such axioms correspond to what has been termed "integrity constraints" in the
actions and change literature, and applying a web service is essentially a
belief update operation. The reasoning required for belief update is known to
be harder than reasoning in the ontology itself. The support for belief update
is severely limited in current planning tools.
  Our first contribution consists in identifying an interesting special case of
WSC which is both significant and more tractable. The special case, which we
term "forward effects", is characterized by the fact that every ramification of
a web service application involves at least one new constant generated as
output by the web service. We show that, in this setting, the reasoning
required for belief update simplifies to standard reasoning in the ontology
itself. This relates to, and extends, current notions of "message-based" WSC,
where the need for belief update is removed by a strong (often implicit or
informal) assumption of "locality" of the individual messages. We clarify the
computational properties of the forward effects case, and point out a strong
relation to standard notions of planning under uncertainty, suggesting that
effective tools for the latter can be successfully adapted to address the
former.
  Furthermore, we identify a significant sub-case, named "strictly forward
effects", where an actual compilation into planning under uncertainty exists.
This enables us to exploit off-the-shelf planning tools to solve message-based
WSC in a general form that involves powerful ontologies, and requires reasoning
about partial matches between concepts. We provide empirical evidence that this
approach may be quite effective, using Conformant-FF as the underlying planner.


title: Conservative Inference Rule for Uncertain Reasoning under Incompleteness

abstract:
  In this paper we formulate the problem of inference under incomplete
information in very general terms. This includes modelling the process
responsible for the incompleteness, which we call the incompleteness process.
We allow the process behaviour to be partly unknown. Then we use Walleys theory
of coherent lower previsions, a generalisation of the Bayesian theory to
imprecision, to derive the rule to update beliefs under incompleteness that
logically follows from our assumptions, and that we call conservative inference
rule. This rule has some remarkable properties: it is an abstract rule to
update beliefs that can be applied in any situation or domain; it gives us the
opportunity to be neither too optimistic nor too pessimistic about the
incompleteness process, which is a necessary condition to draw reliable while
strong enough conclusions; and it is a coherent rule, in the sense that it
cannot lead to inconsistencies. We give examples to show how the new rule can
be applied in expert systems, in parametric statistical inference, and in
pattern classification, and discuss more generally the view of incompleteness
processes defended here as well as some of its consequences.


title: Variable Forgetting in Reasoning about Knowledge

abstract:
  In this paper, we investigate knowledge reasoning within a simple framework
called knowledge structure. We use variable forgetting as a basic operation for
one agent to reason about its own or other agents\ knowledge. In our framework,
two notions namely agents\ observable variables and the weakest sufficient
condition play important roles in knowledge reasoning. Given a background
knowledge base and a set of observable variables for each agent, we show that
the notion of an agent knowing a formula can be defined as a weakest sufficient
condition of the formula under background knowledge base. Moreover, we show how
to capture the notion of common knowledge by using a generalized notion of
weakest sufficient condition. Also, we show that public announcement operator
can be conveniently dealt with via our notion of knowledge structure. Further,
we explore the computational complexity of the problem whether an epistemic
formula is realized in a knowledge structure. In the general case, this problem
is PSPACE-hard; however, for some interesting subcases, it can be reduced to
co-NP. Finally, we discuss possible applications of our framework in some
interesting domains such as the automated analysis of the well-known muddy
children puzzle and the verification of the revised Needham-Schroeder protocol.
We believe that there are many scenarios where the natural presentation of the
available information about knowledge is under the form of a knowledge
structure. What makes it valuable compared with the corresponding multi-agent
S5 Kripke structure is that it can be much more succinct.


title:
Trust-Based Mechanisms for Robust and Efficient Task Allocation in the
  Presence of Execution Uncertainty

abstract:
  Vickrey-Clarke-Groves (VCG) mechanisms are often used to allocate tasks to
selfish and rational agents. VCG mechanisms are incentive compatible, direct
mechanisms that are efficient (i.e., maximise social utility) and individually
rational (i.e., agents prefer to join rather than opt out). However, an
important assumption of these mechanisms is that the agents will "always"
successfully complete their allocated tasks. Clearly, this assumption is
unrealistic in many real-world applications, where agents can, and often do,
fail in their endeavours. Moreover, whether an agent is deemed to have failed
may be perceived differently by different agents. Such subjective perceptions
about an agents probability of succeeding at a given task are often captured
and reasoned about using the notion of "trust". Given this background, in this
paper we investigate the design of novel mechanisms that take into account the
trust between agents when allocating tasks.
  Specifically, we develop a new class of mechanisms, called "trust-based
mechanisms", that can take into account multiple subjective measures of the
probability of an agent succeeding at a given task and produce allocations that
maximise social utility, whilst ensuring that no agent obtains a negative
utility. We then show that such mechanisms pose a challenging new combinatorial
optimisation problem (that is NP-complete), devise a novel representation for
solving the problem, and develop an effective integer programming solution
(that can solve instances with about 2x10^5 possible allocations in 40
seconds).


title: Optimal Value of Information in Graphical Models

abstract:
  Many real-world decision making tasks require us to choose among several
expensive observations. In a sensor network, for example, it is important to
select the subset of sensors that is expected to provide the strongest
reduction in uncertainty. In medical decision making tasks, one needs to select
which tests to administer before deciding on the most effective treatment. It
has been general practice to use heuristic-guided procedures for selecting
observations. In this paper, we present the first efficient optimal algorithms
for selecting observations for a class of probabilistic graphical models. For
example, our algorithms allow to optimally label hidden variables in Hidden
Markov Models (HMMs). We provide results for both selecting the optimal subset
of observations, and for obtaining an optimal conditional observation plan.
  Furthermore we prove a surprising result: In most graphical models tasks, if
one designs an efficient algorithm for chain graphs, such as HMMs, this
procedure can be generalized to polytree graphical models. We prove that the
optimizing value of information is $NP^{PP}$-hard even for polytrees. It also
follows from our results that just computing decision theoretic value of
information objective functions, which are commonly used in practice, is a
#P-complete problem even on Naive Bayes models (a simple special case of
polytrees).
  In addition, we consider several extensions, such as using our algorithms for
scheduling observation selection for multiple sensors. We demonstrate the
effectiveness of our approach on several real-world datasets, including a
prototype sensor network deployment for energy conservation in buildings.


title: Prime Implicates and Prime Implicants: From Propositional to Modal Logic

abstract:
  Prime implicates and prime implicants have proven relevant to a number of
areas of artificial intelligence, most notably abductive reasoning and
knowledge compilation. The purpose of this paper is to examine how these
notions might be appropriately extended from propositional logic to the modal
logic K. We begin the paper by considering a number of potential definitions of
clauses and terms for K. The different definitions are evaluated with respect
to a set of syntactic, semantic, and complexity-theoretic properties
characteristic of the propositional definition. We then compare the definitions
with respect to the properties of the notions of prime implicates and prime
implicants that they induce. While there is no definition that perfectly
generalizes the propositional notions, we show that there does exist one
definition which satisfies many of the desirable properties of the
propositional case. In the second half of the paper, we consider the
computational properties of the selected definition. To this end, we provide
sound and complete algorithms for generating and recognizing prime implicates,
and we show the prime implicate recognition task to be PSPACE-complete. We also
prove upper and lower bounds on the size and number of prime implicates. While
the paper focuses on the logic K, all of our results hold equally well for
multi-modal K and for concept expressions in the description logic ALC.


title: The Complexity of Circumscription in DLs

abstract:
  As fragments of first-order logic, Description logics (DLs) do not provide
nonmonotonic features such as defeasible inheritance and default rules. Since
many applications would benefit from the availability of such features, several
families of nonmonotonic DLs have been developed that are mostly based on
default logic and autoepistemic logic. In this paper, we consider
circumscription as an interesting alternative approach to nonmonotonic DLs
that, in particular, supports defeasible inheritance in a natural way. We study
DLs extended with circumscription under different language restrictions and
under different constraints on the sets of minimized, fixed, and varying
predicates, and pinpoint the exact computational complexity of reasoning for
DLs ranging from ALC to ALCIO and ALCQO. When the minimized and fixed
predicates include only concept names but no role names, then reasoning is
complete for NExpTime^NP. It becomes complete for NP^NExpTime when the number
of minimized and fixed predicates is bounded by a constant. If roles can be
minimized or fixed, then complexity ranges from NExpTime^NP to undecidability.


title:
Solving Weighted Constraint Satisfaction Problems with Memetic/Exact
  Hybrid Algorithms

abstract:
  A weighted constraint satisfaction problem (WCSP) is a constraint
satisfaction problem in which preferences among solutions can be expressed.
Bucket elimination is a complete technique commonly used to solve this kind of
constraint satisfaction problem. When the memory required to apply bucket
elimination is too high, a heuristic method based on it (denominated
mini-buckets) can be used to calculate bounds for the optimal solution.
Nevertheless, the curse of dimensionality makes these techniques impractical on
large scale problems. In response to this situation, we present a memetic
algorithm for WCSPs in which bucket elimination is used as a mechanism for
recombining solutions, providing the best possible child from the parental set.
Subsequently, a multi-level model in which this exact/metaheuristic hybrid is
further hybridized with branch-and-bound techniques and mini-buckets is
studied. As a case study, we have applied these algorithms to the resolution of
the maximum density still life problem, a hard constraint optimization problem
based on Conways game of life. The resulting algorithm consistently finds
optimal patterns for up to date solved instances in less time than current
approaches. Moreover, it is shown that this proposal provides new best known
solutions for very large instances.


title: Efficient Markov Network Structure Discovery Using Independence Tests

abstract:
  We present two algorithms for learning the structure of a Markov network from
data: GSMN* and GSIMN. Both algorithms use statistical independence tests to
infer the structure by successively constraining the set of structures
consistent with the results of these tests. Until very recently, algorithms for
structure learning were based on maximum likelihood estimation, which has been
proved to be NP-hard for Markov networks due to the difficulty of estimating
the parameters of the network, needed for the computation of the data
likelihood. The independence-based approach does not require the computation of
the likelihood, and thus both GSMN* and GSIMN can compute the structure
efficiently (as shown in our experiments). GSMN* is an adaptation of the
Grow-Shrink algorithm of Margaritis and Thrun for learning the structure of
Bayesian networks. GSIMN extends GSMN* by additionally exploiting Pearls
well-known properties of the conditional independence relation to infer novel
independences from known ones, thus avoiding the performance of statistical
tests to estimate them. To accomplish this efficiently GSIMN uses the Triangle
theorem, also introduced in this work, which is a simplified version of the set
of Markov axioms. Experimental comparisons on artificial and real-world data
sets show GSIMN can yield significant savings with respect to GSMN*, while
generating a Markov network with comparable or in some cases improved quality.
We also compare GSIMN to a forward-chaining implementation, called GSIMN-FCH,
that produces all possible conditional independences resulting from repeatedly
applying Pearls theorems on the known conditional independence tests. The
results of this comparison show that GSIMN, by the sole use of the Triangle
theorem, is nearly optimal in terms of the set of independences tests that it
infers.


title:
Complex Question Answering: Unsupervised Learning Approaches and
  Experiments

abstract:
  Complex questions that require inferencing and synthesizing information from
multiple documents can be seen as a kind of topic-oriented, informative
multi-document summarization where the goal is to produce a single text as a
compressed version of a set of documents with a minimum loss of relevant
information. In this paper, we experiment with one empirical method and two
unsupervised statistical machine learning techniques: K-means and Expectation
Maximization (EM), for computing relative importance of the sentences. We
compare the results of these approaches. Our experiments show that the
empirical approach outperforms the other two techniques and EM performs better
than K-means. However, the performance of these approaches depends entirely on
the feature set used and the weighting of these features. In order to measure
the importance and relevance to the user query we extract different kinds of
features (i.e. lexical, lexical semantic, cosine similarity, basic element,
tree kernel based syntactic and shallow-semantic) for each of the document
sentences. We use a local search technique to learn the weights of the
features. To the best of our knowledge, no study has used tree kernel functions
to encode syntactic/semantic information for more complex tasks such as
computing the relatedness between the query sentences and the document
sentences in order to generate query-focused summaries (or answers to complex
questions). For each of our methods of generating summaries (i.e. empirical,
K-means and EM) we show the effects of syntactic and shallow-semantic features
over the bag-of-words (BOW) features.


title: Scattering of Scalar Field by an Extended Black Hole in F(R) gravity

abstract:
  In this work we have studied the scattering of scalar field around an
extended black hole in F(R) gravity using WKB method. We have obtained the wave
function in different regions such as near the horizon region, away from
horizon and far away from horizon and the absorption cross section are
calculated. We find that the absorption cross section is inversely proportional
to the cube of Hawking temperature. We have also evaluated the Hawking
temperature of the black hole via tunneling method.


title: Bounds Arc Consistency for Weighted CSPs

abstract:
  The Weighted Constraint Satisfaction Problem (WCSP) framework allows
representing and solving problems involving both hard constraints and cost
functions. It has been applied to various problems, including resource
allocation, bioinformatics, scheduling, etc. To solve such problems, solvers
usually rely on branch-and-bound algorithms equipped with local consistency
filtering, mostly soft arc consistency. However, these techniques are not well
suited to solve problems with very large domains. Motivated by the resolution
of an RNA gene localization problem inside large genomic sequences, and in the
spirit of bounds consistency for large domains in crisp CSPs, we introduce soft
bounds arc consistency, a new weighted local consistency specifically designed
for WCSP with very large domains. Compared to soft arc consistency, BAC
provides significantly improved time and space asymptotic complexity. In this
paper, we show how the semantics of cost functions can be exploited to further
improve the time complexity of BAC. We also compare both in theory and in
practice the efficiency of BAC on a WCSP with bounds consistency enforced on a
crisp CSP using cost variables. On two different real problems modeled as WCSP,
including our RNA gene localization problem, we observe that maintaining bounds
arc consistency outperforms arc consistency and also improves over bounds
consistency enforced on a constraint model with cost variables.


title:
Enhancing QA Systems with Complex Temporal Question Processing
  Capabilities

abstract:
  This paper presents a multilayered architecture that enhances the
capabilities of current QA systems and allows different types of complex
questions or queries to be processed. The answers to these questions need to be
gathered from factual information scattered throughout different documents.
Specifically, we designed a specialized layer to process the different types of
temporal questions. Complex temporal questions are first decomposed into simple
questions, according to the temporal relations expressed in the original
question. In the same way, the answers to the resulting simple questions are
recomposed, fulfilling the temporal restrictions of the original complex
question. A novel aspect of this approach resides in the decomposition which
uses a minimal quantity of resources, with the final aim of obtaining a
portable platform that is easily extensible to other languages. In this paper
we also present a methodology for evaluation of the decomposition of the
questions as well as the ability of the implemented temporal layer to perform
at a multilingual level. The temporal layer was first performed for English,
then evaluated and compared with: a) a general purpose QA system (F-measure
65.47% for QA plus English temporal layer vs. 38.01% for the general QA
system), and b) a well-known QA system. Much better results were obtained for
temporal questions with the multilayered system. This system was therefore
extended to Spanish and very good results were again obtained in the evaluation
(F-measure 40.36% for QA plus Spanish temporal layer vs. 22.94% for the general
QA system).


title:
Relaxed Survey Propagation for The Weighted Maximum Satisfiability
  Problem

abstract:
  The survey propagation (SP) algorithm has been shown to work well on large
instances of the random 3-SAT problem near its phase transition. It was shown
that SP estimates marginals over covers that represent clusters of solutions.
The SP-y algorithm generalizes SP to work on the maximum satisfiability
(Max-SAT) problem, but the cover interpretation of SP does not generalize to
SP-y. In this paper, we formulate the relaxed survey propagation (RSP)
algorithm, which extends the SP algorithm to apply to the weighted Max-SAT
problem. We show that RSP has an interpretation of estimating marginals over
covers violating a set of clauses with minimal weight. This naturally
generalizes the cover interpretation of SP. Empirically, we show that RSP
outperforms SP-y and other state-of-the-art Max-SAT solvers on random Max-SAT
instances. RSP also outperforms state-of-the-art weighted Max-SAT solvers on
random weighted Max-SAT instances.


title: Modularity Aspects of Disjunctive Stable Models

abstract:
  Practically all programming languages allow the programmer to split a program
into several modules which brings along several advantages in software
development. In this paper, we are interested in the area of answer-set
programming where fully declarative and nonmonotonic languages are applied. In
this context, obtaining a modular structure for programs is by no means
straightforward since the output of an entire program cannot in general be
composed from the output of its components. To better understand the effects of
disjunctive information on modularity we restrict the scope of analysis to the
case of disjunctive logic programs (DLPs) subject to stable-model semantics. We
define the notion of a DLP-function, where a well-defined input/output
interface is provided, and establish a novel module theorem which indicates the
compositionality of stable-model semantics for DLP-functions. The module
theorem extends the well-known splitting-set theorem and enables the
decomposition of DLP-functions given their strongly connected components based
on positive dependencies induced by rules. In this setting, it is also possible
to split shared disjunctive rules among components using a generalized shifting
technique. The concept of modular equivalence is introduced for the mutual
comparison of DLP-functions using a generalization of a translation-based
verification method.


title: Hypertableau Reasoning for Description Logics

abstract:
  We present a novel reasoning calculus for the description logic SHOIQ^+---a
knowledge representation formalism with applications in areas such as the
Semantic Web. Unnecessary nondeterminism and the construction of large models
are two primary sources of inefficiency in the tableau-based reasoning calculi
used in state-of-the-art reasoners. In order to reduce nondeterminism, we base
our calculus on hypertableau and hyperresolution calculi, which we extend with
a blocking condition to ensure termination. In order to reduce the size of the
constructed models, we introduce anywhere pairwise blocking. We also present an
improved nominal introduction rule that ensures termination in the presence of
nominals, inverse roles, and number restrictions---a combination of DL
constructs that has proven notoriously difficult to handle. Our implementation
shows significant performance improvements over state-of-the-art reasoners on
several well-known ontologies.


title: The Role of Macros in Tractable Planning

abstract:
  This paper presents several new tractability results for planning based on
macros. We describe an algorithm that optimally solves planning problems in a
class that we call inverted tree reducible, and is provably tractable for
several subclasses of this class. By using macros to store partial plans that
recur frequently in the solution, the algorithm is polynomial in time and space
even for exponentially long plans. We generalize the inverted tree reducible
class in several ways and describe modifications of the algorithm to deal with
these new classes. Theoretical results are validated in experiments.


title: The DL-Lite Family and Relations

abstract:
  The recently introduced series of description logics under the common moniker
DL-Lite has attracted attention of the description logic and semantic web
communities due to the low computational complexity of inference, on the one
hand, and the ability to represent conceptual modeling formalisms, on the
other. The main aim of this article is to carry out a thorough and systematic
investigation of inference in extensions of the original DL-Lite logics along
five axes: by (i) adding the Boolean connectives and (ii) number restrictions
to concept constructs, (iii) allowing role hierarchies, (iv) allowing role
disjointness, symmetry, asymmetry, reflexivity, irreflexivity and transitivity
constraints, and (v) adopting or dropping the unique same assumption. We
analyze the combined complexity of satisfiability for the resulting logics, as
well as the data complexity of instance checking and answering positive
existential queries. Our approach is based on embedding DL-Lite logics in
suitable fragments of the one-variable first-order logic, which provides useful
insights into their properties and, in particular, computational behavior.


title: Content Modeling Using Latent Permutations

abstract:
  We present a novel Bayesian topic model for learning discourse-level document
structure. Our model leverages insights from discourse theory to constrain
latent topic assignments in a way that reflects the underlying organization of
document topics. We propose a global model in which both topic selection and
ordering are biased to be similar across a collection of related documents. We
show that this space of orderings can be effectively represented using a
distribution over permutations called the Generalized Mallows Model. We apply
our method to three complementary discourse-level tasks: cross-document
alignment, document segmentation, and information ordering. Our experiments
show that incorporating our permutation-based model in these applications
yields substantial improvements in performance over previously proposed
methods.


title: Join-Graph Propagation Algorithms

abstract:
  The paper investigates parameterized approximate message-passing schemes that
are based on bounded inference and are inspired by Pearl's belief propagation
algorithm (BP). We start with the bounded inference mini-clustering algorithm
and then move to the iterative scheme called Iterative Join-Graph Propagation
(IJGP), that combines both iteration and bounded inference. Algorithm IJGP
belongs to the class of Generalized Belief Propagation algorithms, a framework
that allowed connections with approximate algorithms from statistical physics
and is shown empirically to surpass the performance of mini-clustering and
belief propagation, as well as a number of other state-of-the-art algorithms on
several classes of networks. We also provide insight into the accuracy of
iterative BP and IJGP by relating these algorithms to well known classes of
constraint propagation schemes.


title: BnB-ADOPT: An Asynchronous Branch-and-Bound DCOP Algorithm

abstract:
  Distributed constraint optimization (DCOP) problems are a popular way of
formulating and solving agent-coordination problems. A DCOP problem is a
problem where several agents coordinate their values such that the sum of the
resulting constraint costs is minimal. It is often desirable to solve DCOP
problems with memory-bounded and asynchronous algorithms. We introduce
Branch-and-Bound ADOPT (BnB-ADOPT), a memory-bounded asynchronous DCOP search
algorithm that uses the message-passing and communication framework of ADOPT
(Modi, Shen, Tambe, and Yokoo, 2005), a well known memory-bounded asynchronous
DCOP search algorithm, but changes the search strategy of ADOPT from best-first
search to depth-first branch-and-bound search. Our experimental results show
that BnB-ADOPT finds cost-minimal solutions up to one order of magnitude faster
than ADOPT for a variety of large DCOP problems and is as fast as NCBB, a
memory-bounded synchronous DCOP search algorithm, for most of these DCOP
problems. Additionally, it is often desirable to find bounded-error solutions
for DCOP problems within a reasonable amount of time since finding cost-minimal
solutions is NP-hard. The existing bounded-error approximation mechanism allows
users only to specify an absolute error bound on the solution cost but a
relative error bound is often more intuitive. Thus, we present two new
bounded-error approximation mechanisms that allow for relative error bounds and
implement them on top of BnB-ADOPT.


title: Soft Goals Can Be Compiled Away

abstract:
  Soft goals extend the classical model of planning with a simple model of
preferences. The best plans are then not the ones with least cost but the ones
with maximum utility, where the utility of a plan is the sum of the utilities
of the soft goals achieved minus the plan cost. Finding plans with high utility
appears to involve two linked problems: choosing a subset of soft goals to
achieve and finding a low-cost plan to achieve them. New search algorithms and
heuristics have been developed for planning with soft goals, and a new track
has been introduced in the International Planning Competition (IPC) to test
their performance. In this note, we show however that these extensions are not
needed: soft goals do not increase the expressive power of the basic model of
planning with action costs, as they can easily be compiled away. We apply this
compilation to the problems of the net-benefit track of the most recent IPC,
and show that optimal and satisficing cost-based planners do better on the
compiled problems than optimal and satisficing net-benefit planners on the
original problems with explicit soft goals. Furthermore, we show that
penalties, or negative preferences expressing conditions to avoid, can also be
compiled away using a similar idea.


title: ParamILS: An Automatic Algorithm Configuration Framework

abstract:
  The identification of performance-optimizing parameter settings is an
important part of the development and application of algorithms. We describe an
automatic framework for this algorithm configuration problem. More formally, we
provide methods for optimizing a target algorithm's performance on a given
class of problem instances by varying a set of ordinal and/or categorical
parameters. We review a family of local-search-based algorithm configuration
procedures and present novel techniques for accelerating them by adaptively
limiting the time spent for evaluating individual configurations. We describe
the results of a comprehensive experimental evaluation of our methods, based on
the configuration of prominent complete and incomplete algorithms for SAT. We
also present what is, to our knowledge, the first published work on
automatically configuring the CPLEX mixed integer programming solver. All the
algorithms we considered had default parameter settings that were manually
identified with considerable effort. Nevertheless, using our automated
algorithm configuration procedures, we achieved substantial and consistent
performance improvements.


title: Predicting the Performance of IDA* using Conditional Distributions

abstract:
  Korf, Reid, and Edelkamp introduced a formula to predict the number of nodes
IDA* will expand on a single iteration for a given consistent heuristic, and
experimentally demonstrated that it could make very accurate predictions. In
this paper we show that, in addition to requiring the heuristic to be
consistent, their formulas predictions are accurate only at levels of the
brute-force search tree where the heuristic values obey the unconditional
distribution that they defined and then used in their formula. We then propose
a new formula that works well without these requirements, i.e., it can make
accurate predictions of IDA*s performance for inconsistent heuristics and if
the heuristic values in any level do not obey the unconditional distribution.
In order to achieve this we introduce the conditional distribution of heuristic
values which is a generalization of their unconditional heuristic distribution.
We also provide extensions of our formula that handle individual start states
and the augmentation of IDA* with bidirectional pathmax (BPMX), a technique for
propagating heuristic values when inconsistent heuristics are used.
Experimental results demonstrate the accuracy of our new method and all its
variations.