pwc-archive/papers-with-abstracts huggingface dataset:
Best-First Heuristic Search for Multicore Machines
Authors: Ethan Burns, Sofia Lemons, Wheeler Ruml, Rong Zhou
Date: 2014-01-16 00:00:00
Tasks: Heuristic Search

To harness modern multicore processors, it is imperative to develop parallel
versions of fundamental algorithms. In this paper, we compare different
approaches to parallel best-first search in a shared-memory setting. We present
a new method, PBNF, that uses abstraction to partition the state space and to
detect duplicate states without requiring frequent locking. PBNF allows
speculative expansions when necessary to keep threads busy. We identify and fix
potential livelock conditions in our approach, proving its correctness using
temporal logic. Our approach is general, allowing it to extend easily to
suboptimal and anytime heuristic search. In an empirical comparison on STRIPS
planning, grid pathfinding, and sliding tile puzzle problems using 8-core
machines, we show that A*, weighted A* and Anytime weighted A* implemented
using PBNF yield faster search than improved versions of previous parallel
search proposals.
Planning with Noisy Probabilistic Relational Rules
Authors: Tobias Lang, Marc Toussaint
Date: 2014-01-16 00:00:00
Tasks: Robot Manipulation

Noisy probabilistic relational rules are a promising world model
representation for several reasons. They are compact and generalize over world
instantiations. They are usually interpretable and they can be learned
effectively from the action experiences in complex worlds. We investigate
reasoning with such rules in grounded relational domains. Our algorithms
exploit the compactness of rules for efficient and flexible decision-theoretic
planning. As a first approach, we combine these rules with the Upper Confidence
Bounds applied to Trees (UCT) algorithm based on look-ahead trees. Our second
approach converts these rules into a structured dynamic Bayesian network
representation and predicts the effects of action sequences using approximate
inference and beliefs over world states. We evaluate the effectiveness of our
approaches for planning in a simulated complex 3D robot manipulation scenario
with an articulated manipulator and realistic physics and in domains of the
probabilistic planning competition. Empirical results show that our methods can
solve problems where existing methods fail.
A Utility-Theoretic Approach to Privacy in Online Services
Authors: Andreas Krause, Eric Horvitz
Date: 2014-01-16 00:00:00

Online offerings such as web search, news portals, and e-commerce
applications face the challenge of providing high-quality service to a large,
heterogeneous user base. Recent efforts have highlighted the potential to
improve performance by introducing methods to personalize services based on
special knowledge about users and their context. For example, a users
demographics, location, and past search and browsing may be useful in enhancing
the results offered in response to web search queries. However, reasonable
concerns about privacy by both users, providers, and government agencies acting
on behalf of citizens, may limit access by services to such information. We
introduce and explore an economics of privacy in personalization, where people
can opt to share personal information, in a standing or on-demand manner, in
return for expected enhancements in the quality of an online service. We focus
on the example of web search and formulate realistic objective functions for
search efficacy and privacy. We demonstrate how we can find a provably
near-optimal optimization of the utility-privacy tradeoff in an efficient
manner. We evaluate our methodology on data drawn from a log of the search
activity of volunteer participants. We separately assess users' preferences
about privacy and utility via a large-scale survey, aimed at eliciting
preferences about peoples' willingness to trade the sharing of personal data in
returns for gains in search efficiency. We show that a significant level of
personalization can be achieved using a relatively small amount of information
about users.
Logical Foundations of RDF(S) with Datatypes
Authors: Jos de Bruijn, Stijn Heymans
Date: 2014-01-16 00:00:00

The Resource Description Framework (RDF) is a Semantic Web standard that
provides a data language, simply called RDF, as well as a lightweight ontology
language, called RDF Schema. We investigate embeddings of RDF in logic and show
how standard logic programming and description logic technology can be used for
reasoning with RDF. We subsequently consider extensions of RDF with datatype
support, considering D entailment, defined in the RDF semantics specification,
and D* entailment, a semantic weakening of D entailment, introduced by ter
Horst. We use the embeddings and properties of the logics to establish novel
upper bounds for the complexity of deciding entailment. We subsequently
establish two novel lower bounds, establishing that RDFS entailment is
PTime-complete and that simple-D entailment is coNP-hard, when considering
arbitrary datatypes, both in the size of the entailing graph. The results
indicate that RDFS may not be as lightweight as one may expect.
Kalman Temporal Differences
Authors: Matthieu Geist, Olivier Pietquin
Date: 2014-01-16 00:00:00
Tasks: Management, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Because reinforcement learning suffers from a lack of scalability, online
value (and Q-) function approximation has received increasing interest this
last decade. This contribution introduces a novel approximation scheme, namely
the Kalman Temporal Differences (KTD) framework, that exhibits the following
features: sample-efficiency, non-linear approximation, non-stationarity
handling and uncertainty management. A first KTD-based algorithm is provided
for deterministic Markov Decision Processes (MDP) which produces biased
estimates in the case of stochastic transitions. Than the eXtended KTD
framework (XKTD), solving stochastic MDP, is described. Convergence is analyzed
for special cases for both deterministic and stochastic transitions. Related
algorithms are experimented on classical benchmarks. They compare favorably to
the state of the art while exhibiting the announced features.
Case-Based Subgoaling in Real-Time Heuristic Search for Video Game Pathfinding
Authors: Vadim Bulitko, Yngvi Björnsson, Ramon Lawrence
Date: 2014-01-16 00:00:00
Tasks: Heuristic Search

Real-time heuristic search algorithms satisfy a constant bound on the amount
of planning per action, independent of problem size. As a result, they scale up
well as problems become larger. This property would make them well suited for
video games where Artificial Intelligence controlled agents must react quickly
to user commands and to other agents actions. On the downside, real-time search
algorithms employ learning methods that frequently lead to poor solution
quality and cause the agent to appear irrational by re-visiting the same
problem states repeatedly. The situation changed recently with a new algorithm,
D LRTA*, which attempted to eliminate learning by automatically selecting
subgoals. D LRTA* is well poised for video games, except it has a complex and
memory-demanding pre-computation phase during which it builds a database of
subgoals. In this paper, we propose a simpler and more memory-efficient way of
pre-computing subgoals thereby eliminating the main obstacle to applying
state-of-the-art real-time search methods in video games. The new algorithm
solves a number of randomly chosen problems off-line, compresses the solutions
into a series of subgoals and stores them in a database. When presented with a
novel problem on-line, it queries the database for the most similar previously
solved case and uses its subgoals to solve the problem. In the domain of
pathfinding on four large video game maps, the new algorithm delivers solutions
eight times better while using 57 times less memory and requiring 14% less
pre-computation time.
Algorithms for Closed Under Rational Behavior (CURB) Sets
Authors: Michael Benisch, George B. Davis, Tuomas Sandholm
Date: 2014-01-16 00:00:00

We provide a series of algorithms demonstrating that solutions according to
the fundamental game-theoretic solution concept of closed under rational
behavior (CURB) sets in two-player, normal-form games can be computed in
polynomial time (we also discuss extensions to n-player games). First, we
describe an algorithm that identifies all of a player's best responses
conditioned on the belief that the other player will play from within a given
subset of its strategy space. This algorithm serves as a subroutine in a series
of polynomial-time algorithms for finding all minimal CURB sets, one minimal
CURB set, and the smallest minimal CURB set in a game. We then show that the
complexity of finding a Nash equilibrium can be exponential only in the size of
a game's smallest CURB set. Related to this, we show that the smallest CURB set
can be an arbitrarily small portion of the game, but it can also be arbitrarily
larger than the supports of its only enclosed Nash equilibrium. We test our
algorithms empirically and find that most commonly studied academic games tend
to have either very large or very small minimal CURB sets.
A Constraint Satisfaction Framework for Executing Perceptions and Actions in Diagrammatic Reasoning
Authors: Bonny Banerjee, B. Chandrasekaran
Date: 2014-01-16 00:00:00

Diagrammatic reasoning (DR) is pervasive in human problem solving as a
powerful adjunct to symbolic reasoning based on language-like representations.
The research reported in this paper is a contribution to building a general
purpose DR system as an extension to a SOAR-like problem solving architecture.
The work is in a framework in which DR is modeled as a process where subtasks
are solved, as appropriate, either by inference from symbolic representations
or by interaction with a diagram, i.e., perceiving specified information from a
diagram or modifying/creating objects in a diagram in specified ways according
to problem solving needs. The perceptions and actions in most DR systems built
so far are hand-coded for the specific application, even when the rest of the
system is built using the general architecture. The absence of a general
framework for executing perceptions/actions poses as a major hindrance to using
them opportunistically -- the essence of open-ended search in problem solving.
Our goal is to develop a framework for executing a wide variety of specified
perceptions and actions across tasks/domains without human intervention. We
observe that the domain/task-specific visual perceptions/actions can be
transformed into domain/task-independent spatial problems. We specify a spatial
problem as a quantified constraint satisfaction problem in the real domain
using an open-ended vocabulary of properties, relations and actions involving
three kinds of diagrammatic objects -- points, curves, regions. Solving a
spatial problem from this specification requires computing the equivalent
simplified quantifier-free expression, the complexity of which is inherently
doubly exponential. We represent objects as configuration of simple elements to
facilitate decomposition of complex problems into simpler and similar
subproblems. We show that, if the symbolic solution to a subproblem can be
expressed concisely, quantifiers can be eliminated from spatial problems in
low-order polynomial time using similar previously solved subproblems. This
requires determining the similarity of two problems, the existence of a mapping
between them computable in polynomial time, and designing a memory for storing
previously solved problems so as to facilitate search. The efficacy of the idea
is shown by time complexity analysis. We demonstrate the proposed approach by
executing perceptions and actions involved in DR tasks in two army
applications.
Implicit Abstraction Heuristics
Authors: Michael Katz, Carmel Domshlak
Date: 2014-01-16 00:00:00
Tasks: Heuristic Search

State-space search with explicit abstraction heuristics is at the state of
the art of cost-optimal planning. These heuristics are inherently limited,
nonetheless, because the size of the abstract space must be bounded by some,
even if a very large, constant. Targeting this shortcoming, we introduce the
notion of (additive) implicit abstractions, in which the planning task is
abstracted by instances of tractable fragments of optimal planning. We then
introduce a concrete setting of this framework, called fork-decomposition, that
is based on two novel fragments of tractable cost-optimal planning. The induced
admissible heuristics are then studied formally and empirically. This study
testifies for the accuracy of the fork decomposition heuristics, yet our
empirical evaluation also stresses the tradeoff between their accuracy and the
runtime complexity of computing them. Indeed, some of the power of the explicit
abstraction heuristics comes from precomputing the heuristic function offline
and then determining h(s) for each evaluated state s by a very fast lookup in a
database. By contrast, while fork-decomposition heuristics can be calculated in
polynomial time, computing them is far from being fast. To address this
problem, we show that the time-per-node complexity bottleneck of the
fork-decomposition heuristics can be successfully overcome. We demonstrate that
an equivalent of the explicit abstraction notion of a database exists for the
fork-decomposition abstractions as well, despite their exponential-size
abstract spaces. We then verify empirically that heuristic search with the
databased" fork-decomposition heuristics favorably competes with the state of
the art of cost-optimal planning.
Intrusion Detection using Continuous Time Bayesian Networks
Authors: Jing Xu, Christian R. Shelton
Date: 2014-01-16 00:00:00
Tasks: Anomaly Detection, Intrusion Detection

Intrusion detection systems (IDSs) fall into two high-level categories:
network-based systems (NIDS) that monitor network behaviors, and host-based
systems (HIDS) that monitor system calls. In this work, we present a general
technique for both systems. We use anomaly detection, which identifies patterns
not conforming to a historic norm. In both types of systems, the rates of
change vary dramatically over time (due to burstiness) and over components (due
to service difference). To efficiently model such systems, we use continuous
time Bayesian networks (CTBNs) and avoid specifying a fixed update interval
common to discrete-time models. We build generative models from the normal
training data, and abnormal behaviors are flagged based on their likelihood
under this norm. For NIDS, we construct a hierarchical CTBN model for the
network packet traces and use Rao-Blackwellized particle filtering to learn the
parameters. We illustrate the power of our method through experiments on
detecting real worms and identifying hosts on two publicly available network
traces, the MAWI dataset and the LBNL dataset. For HIDS, we develop a novel
learning method to deal with the finite resolution of system log file time
stamps, without losing the benefits of our continuous time model. We
demonstrate the method by detecting intrusions in the DARPA 1998 BSM dataset.
A Model-Based Active Testing Approach to Sequential Diagnosis
Authors: Alexander Feldman, Gregory Provan, Arjan van Gemund
Date: 2014-01-16 00:00:00
Tasks: Diagnostic, Sequential Diagnosis

Model-based diagnostic reasoning often leads to a large number of diagnostic
hypotheses. The set of diagnoses can be reduced by taking into account extra
observations (passive monitoring), measuring additional variables (probing) or
executing additional tests (sequential diagnosis/test sequencing). In this
paper we combine the above approaches with techniques from Automated Test
Pattern Generation (ATPG) and Model-Based Diagnosis (MBD) into a framework
called FRACTAL (FRamework for ACtive Testing ALgorithms). Apart from the inputs
and outputs that connect a system to its environment, in active testing we
consider additional input variables to which a sequence of test vectors can be
supplied. We address the computationally hard problem of computing optimal
control assignments (as defined in FRACTAL) in terms of a greedy approximation
algorithm called FRACTAL-G. We compare the decrease in the number of remaining
minimal cardinality diagnoses of FRACTAL-G to that of two more FRACTAL
algorithms: FRACTAL-ATPG and FRACTAL-P. FRACTAL-ATPG is based on ATPG and
sequential diagnosis while FRACTAL-P is based on probing and, although not an
active testing algorithm, provides a baseline for comparing the lower bound on
the number of reachable diagnoses for the FRACTAL algorithms. We empirically
evaluate the trade-offs of the three FRACTAL algorithms by performing extensive
experimentation on the ISCAS85/74XXX benchmark of combinational circuits.
Nominals, Inverses, Counting, and Conjunctive Queries or: Why Infinity is your Friend!
Authors: Sebastian Rudolph, Birte Glimm
Date: 2014-01-16 00:00:00

Description Logics are knowledge representation formalisms that provide, for
example, the logical underpinning of the W3C OWL standards. Conjunctive
queries, the standard query language in databases, have recently gained
significant attention as an expressive formalism for querying Description Logic
knowledge bases. Several different techniques for deciding conjunctive query
entailment are available for a wide range of DLs. Nevertheless, the combination
of nominals, inverse roles, and number restrictions in OWL 1 and OWL 2 DL
causes unsolvable problems for the techniques hitherto available. We tackle
this problem and present a decidability result for entailment of unions of
conjunctive queries in the DL ALCHOIQb that contains all three problematic
constructors simultaneously. Provided that queries contain only simple roles,
our result also shows decidability of entailment of (unions of) conjunctive
queries in the logic that underpins OWL 1 DL and we believe that the presented
results will pave the way for further progress towards conjunctive query
entailment decision procedures for the Description Logics underlying the OWL
standards.
Approximate Model-Based Diagnosis Using Greedy Stochastic Search
Authors: Alexander Feldman, Gregory Provan, Arjan van Gemund
Date: 2014-01-16 00:00:00
Tasks: Computational Efficiency, Fault Diagnosis

We propose a StochAstic Fault diagnosis AlgoRIthm, called SAFARI, which
trades off guarantees of computing minimal diagnoses for computational
efficiency. We empirically demonstrate, using the 74XXX and ISCAS-85 suites of
benchmark combinatorial circuits, that SAFARI achieves several
orders-of-magnitude speedup over two well-known deterministic algorithms, CDA*
and HA*, for multiple-fault diagnoses; further, SAFARI can compute a range of
multiple-fault diagnoses that CDA* and HA* cannot. We also prove that SAFARI is
optimal for a range of propositional fault models, such as the widely-used
weak-fault models (models with ignorance of abnormal behavior). We discuss the
optimality of SAFARI in a class of strong-fault circuit models with stuck-at
failure modes. By modeling the algorithm itself as a Markov chain, we provide
exact bounds on the minimality of the diagnosis computed. SAFARI also displays
strong anytime behavior, and will return a diagnosis after any non-trivial
inference time.
Automatic Induction of Bellman-Error Features for Probabilistic Planning
Authors: Jia-Hong Wu, Robert Givan
Date: 2014-01-16 00:00:00

Domain-specific features are important in representing problem structure
throughout machine learning and decision-theoretic planning. In planning, once
state features are provided, domain-independent algorithms such as approximate
value iteration can learn weighted combinations of those features that often
perform well as heuristic estimates of state value (e.g., distance to the
goal). Successful applications in real-world domains often require features
crafted by human experts. Here, we propose automatic processes for learning
useful domain-specific feature sets with little or no human intervention. Our
methods select and add features that describe state-space regions of high
inconsistency in the Bellman equation (statewise Bellman error) during
approximate value iteration. Our method can be applied using any
real-valued-feature hypothesis space and corresponding learning method for
selecting features from training sets of state-value pairs. We evaluate the
method with hypothesis spaces defined by both relational and propositional
feature languages, using nine probabilistic planning domains. We show that
approximate value iteration using a relational feature space performs at the
state-of-the-art in domain-independent stochastic relational planning. Our
method provides the first domain-independent approach that plays Tetris
successfully (without human-engineered features).
Fast Set Bounds Propagation Using a BDD-SAT Hybrid
Authors: Graeme Gange, Peter James Stuckey, Vitaly Lagoon
Date: 2014-01-16 00:00:00

Binary Decision Diagram (BDD) based set bounds propagation is a powerful
approach to solving set-constraint satisfaction problems. However, prior BDD
based techniques in- cur the significant overhead of constructing and
manipulating graphs during search. We present a set-constraint solver which
combines BDD-based set-bounds propagators with the learning abilities of a
modern SAT solver. Together with a number of improvements beyond the basic
algorithm, this solver is highly competitive with existing propagation based
set constraint solvers.
Resource-Driven Mission-Phasing Techniques for Constrained Agents in Stochastic Environments
Authors: Jianhui Wu, Edmund H. Durfee
Date: 2014-01-16 00:00:00

Because an agents resources dictate what actions it can possibly take, it
should plan which resources it holds over time carefully, considering its
inherent limitations (such as power or payload restrictions), the competing
needs of other agents for the same resources, and the stochastic nature of the
environment. Such agents can, in general, achieve more of their objectives if
they can use --- and even create --- opportunities to change which resources
they hold at various times. Driven by resource constraints, the agents could
break their overall missions into an optimal series of phases, optimally
reconfiguring their resources at each phase, and optimally using their assigned
resources in each phase, given their knowledge of the stochastic environment.
In this paper, we formally define and analyze this constrained, sequential
optimization problem in both the single-agent and multi-agent contexts. We
present a family of mixed integer linear programming (MILP) formulations of
this problem that can optimally create phases (when phases are not predefined)
accounting for costs and limitations in phase creation. Because our
formulations multaneously also find the optimal allocations of resources at
each phase and the optimal policies for using the allocated resources at each
phase, they exploit structure across these coupled problems. This allows them
to find solutions significantly faster(orders of magnitude faster in larger
problems) than alternative solution techniques, as we demonstrate empirically.