bluuebunny/crossref_metadata_2025 huggingface dataset:
Multi-modal Predicate Identification using Dynamically Learned Robot Controllers
Authors: Amiri Saeid , Wei Suhua , Zhang Shiqi , Sinapov Jivko , Thomason Jesse , Stone Peter
Published: July 2018

Intelligent robots frequently need to explore the objects in their working environments. Modern sensors have enabled robots to learn object properties via perception of multiple modalities. However, object exploration in the real world poses a challenging trade-off between information gains and exploration action costs. Mixed observability Markov decision process (MOMDP) is a framework for planning under uncertainty, while accounting for both fully and partially observable components of the state. Robot perception frequently has to face such mixed observability. This work enables a robot equipped with an arm to dynamically construct query-oriented MOMDPs for multi-modal predicate identification (MPI) of objects. The robot's behavioral policy is learned from two datasets collected using real robots. Our approach enables a robot to explore object properties in a way that is significantly faster while improving accuracies in comparison to existing methods that rely on hand-coded exploration strategies.
Variable-Delay Controllability
Authors: Bhargava Nikhil , Muise Christian , Williams Brian
Published: July 2018

In temporal planning, agents must schedule a set of events satisfying a set of predetermined constraints. These scheduling problems become more difficult when the duration of certain actions are outside the agent's control. Delay controllability is the generalized notion of whether a schedule can be constructed in the face of uncertainty if the agent eventually learns when events occur. Our work introduces the substantially more complex setting of determining variable-delay controllability, where an agent learns about events after some unknown but bounded amount of time has passed. We provide an efficient O(n^3) variable-delay controllability checker and show how to create an execution strategy for variable-delay controllability problems. To our knowledge, these essential capabilities are absent from existing controllability checking algorithms. We conclude by providing empirical evaluations of the quality of variable-delay controllability results as compared to approximations that use fixed delays to model the same problems.
Features, Projections, and Representation Change for Generalized Planning
Authors: Bonet Blai , Geffner Hector
Published: July 2018

Generalized planning is concerned with the characterization and computation of plans that solve many instances at once. In the standard formulation, a generalized plan is a mapping from fea- ture or observation histories into actions, assuming that the instances share a common pool of features and actions. This assumption, however, excludes the standard relational planning domains where actions and objects change across instances. In this work, we extend the standard formulation of generalized planning to such domains. This is achieved by projecting the actions over the features, resulting in a common set of abstract actions which can be tested for soundness and completeness, and which can be used for generating general policies such as “if the gripper is empty, pick the clear block above x and place it on the table” that achieve the goal clear(x) in any Blocksworld instance. In this policy, “pick the clear block above x” is an abstract action that may represent the action Unstack(a, b) in one situation and the action Unstack(b, c) in another. Transformations are also introduced for computing such policies by means of fully observable non-deterministic (FOND) planners. The value of generalized representations for learning general policies is also discussed.
Goal-Based Collective Decisions: Axiomatics and Computational Complexity
Authors: Novaro Arianna , Grandi Umberto , Longin Dominique , Lorini Emiliano
Published: July 2018

We study agents expressing propositional goals over a set of binary issues to reach a collective decision. We adapt properties and rules from the literature on Social Choice Theory to our setting, providing an axiomatic characterisation of a majority rule for goal-based voting. We study the computational complexity of finding the outcome of our rules (i.e., winner determination), showing that it ranges from Nondeterministic Polynomial Time (NP) to Probabilistic Polynomial Time (PP).
Local Minima, Heavy Tails, and Search Effort for GBFS
Authors: Cohen Eldan , Beck J. Christopher
Published: July 2018

Problem difficulty for greedy best first search (GBFS) is not entirely understood, though existing work points to deep local minima and poor correlation between the h-values and the distance to goal as factors that have significant negative effect on the search effort. In this work, we show that there is a very strong exponential correlation between the depth of the single deepest local minima encountered in a search and the overall search effort. Furthermore, we find that the distribution of local minima depth changes dramatically based on the constrainedness of problems, suggesting an explanation for the previously observed heavy-tailed behavior in GBFS. In combinatorial search, a similar result led to the use of randomized restarts to escape deep subtrees with no solution and corresponding significant speed-ups. We adapt this method and propose a randomized restarting GBFS variant that improves GBFS performance by escaping deep local minima, and does so even in the presence of other, randomization-based, search enhancements.
Emergency Response Optimization using Online Hybrid Planning
Authors: Dayapule Durga Harish , Raghavan Aswin , Tadepalli Prasad , Fern Alan
Published: July 2018

This paper poses the planning problem faced by the dispatcher responding to urban emergencies as a Hybrid (Discrete and Continuous) State and Action Markov Decision Process (HSA-MDP). We evaluate the performance of three online planning algorithms based on hindsight optimization for HSA- MDPs on real-world emergency data in the city of Corvallis, USA. The approach takes into account and respects the policy constraints imposed by the emergency department. We show that our algorithms outperform a heuristic policy commonly used by dispatchers by significantly reducing the average response time as well as lowering the fraction of unanswered calls. Our results give new insights into the problem such as withholding of resources for future emergencies in some situations.
Complexity of Scheduling Charging in the Smart Grid
Authors: de Weerdt Mathijs , Albert Michael , Conitzer Vincent , van der Linden Koos
Published: July 2018

The problem of optimally scheduling the charging demand of electric vehicles within the constraints of the electricity infrastructure is called the charge scheduling problem. The models of the charging speed, horizon, and charging demand determine the computational complexity of the charge scheduling problem. We show that for about 20 variants the problem is either in P or weakly NP-hard and dynamic programs exist to compute optimal solutions. About 10 other variants of the problem are strongly NP-hard, presenting a potentially significant obstacle to their use in practical situations of scale. An experimental study establishes up to what parameter values the dynamic programs can determine optimal solutions in a couple of minutes.
Deontic Sensors
Authors: Padget Julian , De Vos Marina , Page Charlie Ann
Published: July 2018

Normative capabilities in multi-agent systems (MAS) can be represented within agents, separately as institutions, or a blend of the two. This paper addresses how to extend the principles of open MAS to the provision of normative reasoning capabilities, which are currently either embedded in existing MAS platforms - tightly coupled and inaccessible - or not present. We use a resource-oriented architecture (ROA) pattern, that we call deontic sensors, to make normative reasoning part of an open MAS architecture. The pattern specifies how to loosely couple MAS and normative frameworks, such that each is agnostic of the other, while augmenting the brute facts that an agent perceives with institutional facts, that capture each institution's interpretation of an agent's action. In consequence, a MAS without normative capabilities can acquire them, and an embedded normative framework can be de-coupled and opened to other MAS platforms. More importantly, the deontic sensor pattern allows normative reasoning to be published as services, opening routes to certification and re-use, creation of (formalized) trust and non-specialist access to "on demand'' normative reasoning.
Unchaining the Power of Partial Delete Relaxation, Part II: Finding Plans with Red-Black State Space Search
Authors: Fickert Maximilian , Gnad Daniel , Hoffmann Joerg
Published: July 2018

Red-black relaxation in classical planning allows to interpolate between delete-relaxed and real planning. Yet the traditional use of relaxations to generate heuristics restricts relaxation usage to tractable fragments. How to actually tap into the red-black relaxation's interpolation power? Prior work has devised red-black state space search (RBS) for intractable red-black planning, and has explored two uses: proving unsolvability, generating seed plans for plan repair. Here, we explore the generation of plans directly through RBS. We design two enhancements to this end: (A) use a known tractable fragment where possible, use RBS for the intractable parts; (B) check RBS state transitions for realizability, spawn relaxation refinements where the check fails. We show the potential merits of both techniques on IPC benchmarks.
Model Checking Probabilistic Epistemic Logic for Probabilistic Multiagent Systems
Authors: Fu Chen , Turrini Andrea , Huang Xiaowei , Song Lei , Feng Yuan , Zhang Lijun
Published: July 2018

In this work we study the model checking problem for probabilistic multiagent systems with respect to the probabilistic epistemic logic PETL, which can specify both temporal and epistemic properties. We show that under the realistic assumption of uniform schedulers, i.e., the choice of every agent depends only on its observation history, PETL model checking is undecidable. By restricting the class of schedulers to be memoryless schedulers, we show that the problem becomes decidable. More importantly, we design a novel algorithm which reduces the model checking problem into a mixed integer non-linear programming problem, which can then be solved by using an SMT solver. The algorithm has been implemented in an existing model checker and experiments are conducted on examples from the IPPC competitions.
Learning to Infer Final Plans in Human Team Planning
Authors: Kim Joseph , Woicik Matthew E. , Gombolay Matthew C. , Son Sung-Hyun , Shah Julie A.
Published: July 2018

We envision an intelligent agent that analyzes conversations during human team meetings in order to infer the team’s plan, with the purpose of providing decision support to strengthen that plan. We present a novel learning technique to infer teams' final plans directly from a processed form of their planning conversation. Our method employs reinforcement learning to train a model that maps features of the discussed plan and patterns of dialogue exchange among participants to a final, agreed-upon plan. We employ planning domain models to efficiently search the large space of possible plans, and the costs of candidate plans serve as the reinforcement signal. We demonstrate that our technique successfully infers plans within a variety of challenging domains, with higher accuracy than prior art. With our domain-independent feature set, we empirically demonstrate that our model trained on one planning domain can be applied to successfully infer team plans within a novel planning domain.
Effect-Abstraction Based Relaxation for Linear Numeric Planning
Authors: Li Dongxu , Scala Enrico , Haslum Patrik , Bogomolov Sergiy
Published: July 2018

This paper studies an effect-abstraction based relaxation

for reasoning about linear numeric planning problems. The effect-abstraction

decomposes non-constant linear numeric effects into actions with conditional

effects over additive constant numeric effects. With little effort, on this

compiled version, it is possible to use known subgoaling based relaxations

and relative heuristics. The combination of these two steps leads to a novel

relaxation based heuristic. Theoretically, the relaxation is proved tighter

than previous interval based relaxation and leading to safe-pruning

heuristics. Empirically, a heuristic developed on this relaxation leads to

substantial improvements for a class of problems that are currently out of

the reach of state-of-the-art numeric planners.
Scalable Initial State Interdiction for Factored MDPs
Authors: Panda Swetasudha , Vorobeychik Yevgeniy
Published: July 2018

We propose a novel Stackelberg game model of MDP interdiction in which the defender modifies the initial state of the planner, who then responds

by computing an optimal policy starting with that state. We first develop a novel approach for MDP interdiction in factored state space that allows the defender to modify the initial state. The resulting approach can be computationally expensive for large factored MDPs. To address this, we develop several interdiction algorithms that leverage variations of reinforcement learning using both linear and non-linear function approximation. Finally, we extend the interdiction framework to consider a Bayesian interdiction problem in which the interdictor is uncertain about some of the planner's initial state features.

Extensive experiments demonstrate the effectiveness of our approaches.
Counterplanning using Goal Recognition and Landmarks
Authors: Pozanco Alberto , E-Martín Yolanda , Fernández Susana , Borrajo Daniel
Published: July 2018

In non-cooperative multi-agent systems, agents might want to prevent the opponents from achieving their goals. One alternative to solve this task would be using counterplanning to generate a plan that allows an agent to block other's to reach their goals. In this paper, we introduce a fully automated domain-independent approach for counterplanning. It combines; goal recognition to infer an opponent's goal; landmarks' computation to identify subgoals that can be used to block opponents' goals achievement; and classical automated planning to generate plans that prevent the opponent's goals achievement. Experimental results in several domains show the benefits of our novel approach.
Minimax-Regret Querying on Side Effects for Safe Optimality in Factored Markov Decision Processes
Authors: Zhang Shun , Durfee Edmund H. , Singh Satinder
Published: July 2018

As it achieves a goal on behalf of its human user, an autonomous agent's actions may have side effects that change features of its environment in ways that negatively surprise its user. An agent that can be trusted to operate safely should thus only change features the user has explicitly permitted. We formalize this problem, and develop a planning algorithm that avoids potentially negative side effects given what the agent knows about (un)changeable features. Further, we formulate a provably minimax-regret querying strategy for the agent to selectively ask the user about features that it hasn't explicitly been told about. We empirically show how much faster it is than a more exhaustive approach and how much better its queries are than those found by the best known heuristic.
Implicit Non-linear Similarity Scoring for Recognizing Unseen Classes
Authors: Guo Yuchen , Ding Guiguang , Han Jungong , Zhao Sicheng , Wang Bin
Published: July 2018

Recognizing unseen classes is an important task for real-world applications, due to: 1) it is common that some classes in reality have no labeled image exemplar for training; and 2) novel classes emerge rapidly. Recently, to address this task many zero-shot learning (ZSL) approaches have been proposed where explicit linear scores, like inner product score, are employed to measure the similarity between a class and an image. We argue that explicit linear scoring (ELS) seems too weak to capture complicated image-class correspondence. We propose a simple yet effective framework, called Implicit Non-linear Similarity Scoring (ICINESS). In particular, we train a scoring network which uses image and class features as input, fuses them by hidden layers, and outputs the similarity. Based on the universal approximation theorem, it can approximate the true similarity function between images and classes if a proper structure is used in an implicit non-linear way, which is more flexible and powerful. With ICINESS framework, we implement ZSL algorithms by shallow and deep networks, which yield consistently superior results.
An Appearance-and-Structure Fusion Network for Object Viewpoint Estimation
Authors: Kao Yueying , Li Weiming , Wang Zairan , Zou Dongqing , He Ran , Wang Qiang , Ahn Minsu , Hong Sunghoon
Published: July 2018

Automatic object viewpoint estimation from a single image is an important but challenging problem in machine intelligence community. Although impressive performance has been achieved, current state-of-the-art methods still have difficulty to deal with the visual ambiguity and structure ambiguity in real world images. To tackle these problems, a novel Appearance-and-Structure Fusion network, which we call it ASFnet that estimates viewpoint by fusing both appearance and structure information, is proposed in this paper. The structure information is encoded by precise semantic keypoints and can help address the visual ambiguity. Meanwhile, distinguishable appearance features contribute to overcoming the structure ambiguity. Our ASFnet integrates an appearance path and a structure path to an end-to-end network and allows deep features effectively share supervision from both the two complementary aspects. A convolutional layer is learned to fuse the two path results adaptively. To balance the influence from the two supervision sources, a piecewise loss weight strategy is employed during training. Experimentally, our proposed network outperforms state-of-the-art methods on a public PASCAL 3D+ dataset, which verifies the effectiveness of our method and further corroborates the above proposition.
3D-PhysNet: Learning the Intuitive Physics of Non-Rigid Object Deformations
Authors: Wang Zhihua , Rosa Stefano , Yang Bo , Wang Sen , Trigoni Niki , Markham Andrew
Published: July 2018

The ability to interact and understand the environment is a fundamental prerequisite for a wide range of applications from robotics to augmented reality. In particular, predicting how deformable objects will react to applied forces in real time is a significant challenge. This is further confounded by the fact that shape information about encountered objects in the real world is often impaired by occlusions, noise and missing regions e.g. a robot manipulating an object will only be able to observe a partial view of the entire solid. In this work we present a framework, 3D-PhysNet, which is able to predict how a three-dimensional solid will deform under an applied force using intuitive physics modelling. In particular, we propose a new method to encode the physical properties of the material and the applied force, enabling generalisation over materials. The key is to combine deep variational autoencoders with adversarial training, conditioned on the applied force and the material properties.We further propose a cascaded architecture that takes a single 2.5D depth view of the object and predicts its deformation. Training data is provided by a physics simulator. The network is fast enough to be used in real-time applications from partial views. Experimental results show the viability and the generalisation properties of the proposed architecture.
Redividing the Cake
Authors: Segal-Halevi Erel
Published: July 2018

A heterogeneous resource, such as a land-estate, is already divided among several agents in an unfair way.The challenge is to re-divide it among the agents in a way that balances fairness with ownership rights.We present re-division protocols that attain various combinations of fairness and ownership rights, in various settings differing in the geometric constraints on the allotments: (a) no geometric constraints; (b) connectivity --- the cake is a one-dimensional interval and each piece must be a contiguous interval; (c) rectangularity --- the cake is a two-dimensional rectangle and the pieces should be rectangles; (d) convexity --- the cake is a two-dimensional convex polygon and the pieces should be convex.
Efficient Localized Inference for Large Graphical Models
Authors: Chen Jinglin , Peng Jian , Liu Qiang
Published: July 2018

We propose a new localized inference algorithm for answering marginalization queries in large graphical models with the correlation decay property. Given a query variable and a large graphical model, we define a much smaller model in a local region around the query variable in the target model so that the marginal distribution of the query variable can be accurately approximated. We introduce two approximation error bounds based on the Dobrushin’s comparison theorem and apply our bounds to derive a greedy expansion algorithm that efficiently guides the selection of neighbor nodes for localized inference. We verify our theoretical bounds on various datasets and demonstrate that our localized inference algorithm can provide fast and accurate approximation for large graphical models.
On Robust Trimming of Bayesian Network Classifiers
Authors: Choi YooJung , Van den Broeck Guy
Published: July 2018

This paper considers the problem of removing costly features from a Bayesian network classifier. We want the classifier to be robust to these changes, and maintain its classification behavior. To this end, we propose a closeness metric between Bayesian classifiers, called the expected classification agreement (ECA). Our corresponding trimming algorithm finds an optimal subset of features and a new classification threshold that maximize the expected agreement, subject to a budgetary constraint. It utilizes new theoretical insights to perform branch-and-bound search in the space of feature sets, while computing bounds on the ECA. Our experiments investigate both the runtime cost of trimming and its effect on the robustness and accuracy of the final classifier.
Efficient Symbolic Integration for Probabilistic Inference
Authors: Kolb Samuel , Mladenov Martin , Sanner Scott , Belle Vaishak , Kersting Kristian
Published: July 2018

Weighted model integration (WMI) extends weighted model counting (WMC) to the integration of functions over mixed discrete-continuous probability spaces. It has shown tremendous promise for solving inference problems in graphical models and probabilistic programs. Yet, state-of-the-art tools for WMI are generally limited either by the range of amenable theories, or in terms of performance. To address both limitations, we propose the use of extended algebraic decision diagrams (XADDs) as a compilation language for WMI.

Aside from tackling typical WMI problems, XADDs also enable partial WMI yielding parametrized solutions. To overcome the main roadblock of XADDs -- the computational cost of integration -- we formulate a novel and powerful exact symbolic dynamic programming (SDP) algorithm that seamlessly handles Boolean, integer-valued and real variables, and is able to effectively cache partial computations, unlike its predecessor. Our empirical results demonstrate that these contributions can lead to a significant computational reduction

over existing probabilistic inference algorithms.
Lifted Filtering via Exchangeable Decomposition
Authors: Lüdtke Stefan , Schröder Max , Bader Sebastian , Kersting Kristian , Kirste Thomas
Published: July 2018

We present a model for exact recursive Bayesian filtering based on lifted multiset states. Combining multisets with lifting makes it possible to simultaneously exploit multiple strategies for reducing inference complexity when compared to list-based grounded state representations. The core idea is to borrow the concept of Maximally Parallel Multiset Rewriting Systems and to enhance it by concepts from Rao-Blackwellization and Lifted Inference, giving a representation of state distributions that enables efficient inference. In worlds where the random variables that define the system state are exchangeable -- where the identity of entities does not matter -- it automatically uses a representation that abstracts from ordering (achieving an exponential reduction in complexity) -- and it automatically adapts when observations or system dynamics destroy exchangeability by breaking symmetry.
Estimation with Incomplete Data: The Linear Case
Authors: Mohan Karthika , Thoemmes Felix , Pearl Judea
Published: July 2018

Traditional methods for handling incomplete data, including Multiple Imputation and Maximum Likelihood, require that the data be Missing At Random (MAR). In most cases, however, missingness in a variable depends on the underlying value of that variable. In this work, we devise model-based methods to consistently estimate mean, variance and covariance given data that are Missing Not At Random (MNAR). While previous work on MNAR data require variables to be discrete, we extend the analysis to continuous variables drawn from Gaussian distributions. We demonstrate the merits of our techniques by comparing it empirically to state of the art software packages.
Reliable Multi-class Classification based on Pairwise Epistemic and Aleatoric Uncertainty
Authors: Nguyen Vu-Linh , Destercke Sébastien , Masson Marie-Hélène , Hüllermeier Eyke
Published: July 2018

We propose a method for reliable prediction in multi-class classification, where reliability refers to the possibility of partial abstention in cases of uncertainty. More specifically, we allow for predictions in the form of preorder relations on the set of classes, thereby generalizing the idea of set-valued predictions. Our approach relies on combining learning by pairwise comparison with a recent proposal for modeling uncertainty in classification, in which a distinction is made between reducible (a.k.a. epistemic) uncertainty caused by a lack of information and irreducible (a.k.a. aleatoric) uncertainty due to intrinsic randomness. The problem of combining uncertain pairwise predictions into a most plausible preorder is then formalized as an integer programming problem. Experimentally, we show that our method is able to appropriately balance reliability and precision of predictions.
Designing the Game to Play: Optimizing Payoff Structure in Security Games
Authors: Shi Zheyuan Ryan , Tang Ziye , Tran-Thanh Long , Singh Rohit , Fang Fei
Published: July 2018

We study Stackelberg Security Games where the defender, in addition to allocating defensive resources to protect targets from the attacker, can strategically manipulate the attacker’s payoff under budget constraints in weighted L^p-norm form regarding the amount of change. For the case of weighted L^1-norm constraint, we present (i) a mixed integer linear program-based algorithm with approximation guarantee; (ii) a branch-and-bound based algorithm with improved efficiency achieved by effective pruning; (iii) a polynomial time approximation scheme for a special but practical class of problems. In addition, we show that problems under budget constraints in L^0 and weighted L^\infty-norm form can be solved in polynomial time.
A Scalable Scheme for Counting Linear Extensions
Authors: Talvitie Topi , Kangas Kustaa , Niinimäki Teppo , Koivisto Mikko
Published: July 2018

Counting the linear extensions of a given partial order not only has several applications in artificial intelligence but also represents a hard problem that challenges modern paradigms for approximate counting. Recently, Talvitie et al. (AAAI 2018) showed that an exponential time scheme beats the fastest known polynomial time schemes in practice, even if allowing hours of running time. Here, we present a novel scheme, relaxation Tootsie Pop, which in our experiments exhibits polynomial characteristics and significantly outperforms previous schemes. We also instantiate state-of-the-art model counters for CNF formulas; two natural encodings yield schemes that, however, are inferior to the more specialized schemes.
Artificial Intelligence Conferences Closeness
Authors: Konieczny Sébastien , Lonca Emmanuel
Published: July 2018

We study the evolution of Artificial Intelligence conference closeness, using the coscinus tool. Coscinus computes the closeness between publication supports using the co-publication habits of authors: the more authors publish in two conferences, the closer these two conferences. In this paper we perform an analysis of the main Artificial Intelligence conferences based on principal components analysis and clustering performed on this closeness relation.
Weighted Bipolar Argumentation Graphs: Axioms and Semantics
Authors: Amgoud Leila , Ben-Naim Jonathan
Published: July 2018

The paper studies how arguments can be evaluated in weighted bipolar argumentation graphs (i.e., graphs whose arguments have basic weights and may be supported and attacked). It introduces principles that an evaluation method (or semantics) would satisfy, analyzes existing semantics with respect to them, and finally proposes a new semantics for the class of non-maximal acyclic graphs.
Reduced Cost Fixing for Maximum Satisfiability
Authors: Bacchus Fahiem , Hyttinen Antti , Järvisalo Matti , Saikko Paul
Published: July 2018

Maximum satisfiability (MaxSAT) offers a competitive approach to solving NP-hard real-world optimization problems. While state-of-the-art MaxSAT

solvers rely heavily on Boolean satisfiability (SAT) solvers, a recent trend, brought on by MaxSAT solvers implementing the so-called implicit hitting

set (IHS) approach, is to integrate techniques from the realm of integer programming (IP) into the solving process. This allows for making use of additional

IP solving techniques to further speed up MaxSAT solving. In this line of work, we investigate the integration of the technique of reduced cost

fixing from the IP realm into IHS solvers, and empirically show that reduced cost fixing considerable speeds up a state-of-the-art MaxSAT solver implementing

the IHS approach.
Learning with Sparse and Biased Feedback for Personal Search
Authors: Bendersky Michael , Wang Xuanhui , Najork Marc , Metzler Donald
Published: July 2018

Personal search, including email, on-device, and personal media search, has recently attracted a considerable attention from the information retrieval community. In this paper, we provide an overview of challenges and opportunities of learning with implicit user feedback (e.g., click data) in personal search. Implicit user feedback provides a convenient source of supervision for ranking models in personal search. This feedback, however, has two major drawbacks: it is highly sparse and biased due to the personal nature of queries and documents. We demonstrate how these drawbacks can be overcome, and empirically demonstrate the benefits of learning with implicit feedback in the context of a large-scale email search engine.
The Finite Model Theory of Bayesian Networks: Descriptive Complexity
Authors: Cozman Fabio Gagliardi , Mauá Denis Deratani
Published: July 2018

We adapt the theory of descriptive complexity to Bayesian networks, to quantify the expressivity of specifications based on predicates and quantifiers. We show that Bayesian network specifications that employ first-order quantification capture the complexity class PP; by allowing quantification over predicates, the resulting Bayesian network specifications capture each class in the hierarchy PP^(NP^...^NP), a result that does not seem to have equivalent in the literature.
Inductive Certificates of Unsolvability for Domain-Independent Planning
Authors: Eriksson Salomé , Röger Gabriele , Helmert Malte
Published: July 2018

If a planning system outputs a solution for a given problem, it is simple to verify that the solution is valid. However, if a planner claims that a task is unsolvable, we currently have no choice but to trust the planner blindly. We propose a sound and complete class of certificates of unsolvability which can be verified efficiently by an independent program. To highlight their practical use, we show how these certificates can be generated for a wide range of state-of-the-art planning techniques with only polynomial overhead for the planner.
A Model of Distributed Query Computation in Client-Server Scenarios on the Semantic Web
Authors: Hartig Olaf , Letter Ian , Pérez Jorge
Published: July 2018

This paper provides an overview of a model for capturing properties of client-server-based query computation setups. This model can be used to formally analyze different combinations of client and server capabilities, and compare them in terms of various fine-grain complexity measures. While the motivations and the focus of the presented work are related to querying the Semantic Web, the main concepts of the model are general enough to be applied in other contexts as well.
Orchestrating a Network of Mereotopological Theories: An Abridged Report
Authors: Keet C. Maria , Kutz Oliver
Published: July 2018

Parthood is used widely in ontologies across subject domains, specified in a multitude of mereological theories, and even more when combined with topology. To complicate the landscape, decidable languages put restrictions on the language features, so that only fragments of the mereo(topo)logical theories can be represented, even though those full features may be needed to check correctness during modelling. We address these issues by specifying a structured network of theories formulated in multiple logics that are glued together by the various linking constructs of the Distributed Ontology Language, DOL. For the KGEMT mereotopology and its five sub-theories, together with the DL-based OWL species and first- and second-order logic, this network in DOL orchestrates 28 ontologies.
Counterexample-Driven Genetic Programming: Stochastic Synthesis of Provably Correct Programs
Authors: Krawiec Krzysztof , Błądek Iwo , Swan Jerry , Drake John H.
Published: July 2018

Genetic programming is an effective technique for inductive synthesis of programs from tests, i.e. training examples of desired input-output behavior. Programs synthesized in this way are not guaranteed to generalize beyond the training set, which is unacceptable in many applications. We present Counterexample-Driven Genetic Programming (CDGP) that employs evolutionary search to synthesize provably correct programs from formal specifications. CDGP employs a Satisfiability Modulo Theories (SMT) solver to formally verify programs in the evaluation phase. A failed verification produces counterexamples that are in turn used to calculate fitness and thereby drive the search process. When compared with a range of approaches on a suite of state-of-the-art specification-based synthesis benchmarks, CDGP systematically outperforms them, typically synthesizing correct programs faster and using fewer tests.
Multi-Robot Motion Planning with Dynamics Guided by Multi-Agent Search
Authors: Le Duong , Plaku Erion
Published: July 2018

This paper presents an effective multi-robot motion planner that

enables each robot to reach its desired location while avoiding

collisions with the other robots and the obstacles. The approach takes

into account the differential constraints imposed by the underlying

dynamics of each robot and generates dynamically-feasible motions that

can be executed in the physical world. The crux of the approach is

the sampling-based expansion of a motion tree in the continuous state

space of all the robots guided by multi-agent search over a discrete

abstraction. Experiments using vehicle models with nonlinear dynamics

operating in complex environments show significant speedups over

related work.
Completeness-aware Rule Learning from Knowledge Graphs
Authors: Pellissier Tanon Thomas , Stepanova Daria , Razniewski Simon , Mirza Paramita , Weikum Gerhard
Published: July 2018

Knowledge graphs (KGs) are huge collections of primarily encyclopedic facts that are widely used in entity recognition, structured search, question answering, and similar. Rule mining is commonly applied to discover patterns in KGs. However, unlike in traditional association rule mining, KGs provide a setting with a high degree of incompleteness, which may result in the wrong estimation of the quality of mined rules, leading to erroneous beliefs such as all artists have won an award. In this paper we propose to use (in-)completeness meta-information to better assess the quality of rules learned from incomplete KGs. We introduce completeness-aware scoring functions for relational association rules. Experimental evaluation both on real and synthetic datasets shows that the proposed rule ranking approaches have remarkably higher accuracy than the state-of-the-art methods in uncovering missing facts.
A Cloaking Mechanism to Mitigate Market Manipulation
Authors: Wang Xintong , Vorobeychik Yevgeniy , Wellman Michael P.
Published: July 2018

We propose a cloaking mechanism to deter spoofing, a form of manipulation in financial markets. The mechanism works by symmetrically concealing a specified number of price levels from the inside of the order book. To study the effectiveness of cloaking, we simulate markets populated with background traders and an exploiter, who strategically spoofs to profit. The traders follow two representative bidding strategies: the non-spoofable zero intelligence and the manipulable heuristic belief learning. Through empirical game-theoretic analysis across parametrically different environments, we evaluate surplus accrued by traders, and characterize the conditions under which cloaking mitigates manipulation and benefits market welfare. We further design sophisticated spoofing strategies that probe to reveal cloaked information, and find that the effort and risk exceed the gains.
An Efficient Minibatch Acceptance Test for Metropolis-Hastings
Authors: Seita Daniel , Pan Xinlei , Chen Haoyu , Canny John
Published: July 2018

We present a novel Metropolis-Hastings method for large datasets that uses small expected-size mini-batches of data. Previous work on reducing the cost of Metropolis-Hastings tests yields only constant factor reductions versus using the full dataset for each sample. Here we present a method that can be tuned to provide arbitrarily small batch sizes, by adjusting either proposal step size or temperature. Our test uses the noise-tolerant Barker acceptance test with a novel additive correction variable. The resulting test has similar cost to a normal SGD update. Our experiments demonstrate several order-of-magnitude speedups over previous work.
Generating High Resolution Climate Change Projections through Single Image Super-Resolution: An Abridged Version
Authors: Vandal Thomas , Kodra Evan , Ganguly Sangram , Michaelis Andrew , Nemani Ramakrishna , Ganguly Auroop R
Published: July 2018

The impacts of climate change are felt by most critical systems, such as infrastructure, ecological systems, and power-plants. However, contemporary Earth System Models (ESM) are run at spatial resolutions too coarse for assessing effects this localized. Local scale projections can be obtained using statistical downscaling, a technique which uses historical climate observations to learn a low-resolution to high-resolution mapping. The spatio-temporal nature of the climate system motivates the adaptation of super-resolution image processing techniques to statistical downscaling. In our work, we present DeepSD, a generalized stacked super resolution convolutional neural network (SRCNN) framework with multi-scale input channels for statistical downscaling of climate variables. A comparison of DeepSD to four state-of-the-art methods downscaling daily precipitation from 1 degree (~100km) to 1/8 degrees (~12.5km) over the Continental United States. Furthermore, a framework using the NASA Earth Exchange (NEX) platform is discussed for downscaling more than 20 ESM models with multiple emission scenarios.
Budget-feasible Procurement Mechanisms in Two-sided Markets
Authors: Wu Weiwei , Liu Xiang , Li Minming
Published: July 2018

This paper considers the mechanism design problem in two-sided markets where multiple strategic buyers come with budgets to procure as much value of items  as possible from the strategic sellers. Each seller holds an item with public value and is allowed to bid its private cost.  Buyers could claim their budgets, not necessarily the true ones.  The goal is to seek budget-feasible mechanisms that ensure sellers are rewarded enough payment and buyers' budgets are not exceeded.  Our main contribution  is a random  mechanism  that guarantees various desired theoretical guarantees like the budget feasibility,  the truthfulness on the sellers' side and the buyers' side simultaneously, and constant approximation to the optimal total procured value of buyers.
Robust Multi-view Representation: A Unified Perspective from Multi-view Learning to Domain Adaption
Authors: Ding Zhengming , Shao Ming , Fu Yun
Published: July 2018

Multi-view data are extensively accessible nowadays thanks to various types of features, different view-points and sensors which tend to facilitate better representation in many key applications. This survey covers the topic of robust multi-view data representation, centered around several major visual applications. First of all, we formulate a unified learning framework which is able to model most existing multi-view learning and domain adaptation in this line. Following this, we conduct a comprehensive discussion across these two problems by reviewing the algorithms along these two topics, including multi-view clustering, multi-view classification, zero-shot learning, and domain adaption. We further present more practical challenges in multi-view data analysis. Finally, we discuss future research including incomplete, unbalance, large-scale multi-view learning. This would benefit AI community from literature review to future direction.
MCTS-Minimax Hybrids with State Evaluations (Extended Abstract)
Authors: Baier Hendrik , Winands Mark H. M.
Published: July 2018

Monte-Carlo Tree Search (MCTS) has been found to show weaker play than minimax-based search in some tactical game domains. In order to combine the tactical strength of minimax and the strategic strength of MCTS, MCTS-minimax hybrids have been proposed in prior work. This article continues this line of research for the case where heuristic state evaluation functions are available. Three different approaches are considered, employing minimax in the rollout phase of MCTS, as a replacement for the rollout phase, and as a node prior to bias move selection. The latter two approaches are newly proposed. Results show that the use of enhanced minimax for computing node priors results in the strongest MCTS-minimax hybrid in the three test domains of Othello, Breakthrough, and Catch the Lion. This hybrid also outperforms enhanced minimax as a standalone player in Breakthrough, demonstrating that at least in this domain, MCTS and minimax can be combined to an algorithm stronger than its parts.
Enhancing Context Knowledge Repositories with Justifiable Exceptions (Extended Abstract)
Authors: Bozzato Loris , Eiter Thomas , Serafini Luciano
Published: July 2018

The Contextualized Knowledge Repository (CKR) framework was conceived as a logic-based approach for representing context dependent knowledge, which is a well-known area of study in AI. The framework has a two-layer structure with a global context that contains context-independent knowledge and meta-information about the contexts, and a set of local contexts with specific knowledge bases. In many practical cases, it is desirable that inherited global knowledge can be "overridden" at the local level. In order to address this need, we present an extension of CKR with global defeasible axioms: these axioms locally apply to (tuples of) individuals unless an exception for overriding exists; such an exception, however, requires a justification that is provable from the knowledge base. We formalize this intuition and study its semantic and computational properties. Furthermore, we present a translation of extended CKRs to datalog programs under the answer set (i.e., stable) semantics and we present an implementation prototype. Our work adds to the body of results on using deductive database technology in these areas, and provides an expressive formalism for exception handling by overriding.
Complexity of n-Queens Completion (Extended Abstract)
Authors: Gent Ian P. , Jefferson Christopher , Nightingale Peter
Published: July 2018

The n-Queens problem is to place n chess queens on an n by n chessboard so that no two queens are on the same row, column or diagonal. The n-Queens Completion problem is a variant, dating to 1850, in which some queens are already placed and the solver is asked to place the rest, if possible. We show that n-Queens Completion is both NP-Complete and #P-Complete. A corollary is that any non-attacking arrangement of queens can be included as a part of a solution to a larger n-Queens problem. We introduce generators of random instances for n-Queens Completion and the closely related Blocked n-Queens and Excluded Diagonals Problem. We describe three solvers for these problems, and empirically analyse the hardness of randomly generated instances. For Blocked n-Queens and the Excluded Diagonals Problem, we show the existence of a phase transition associated with hard instances as has been seen in other NP-Complete problems, but a natural generator for n-Queens Completion did not generate consistently hard instances. The significance of this work is that the n-Queens problem has been very widely used as a benchmark in Artificial Intelligence, but conclusions on it are often disputable because of the simple complexity of the decision problem. Our results give alternative benchmarks which are hard theoretically and empirically, but for which solving techniques designed for n-Queens need minimal or no change.
Constrained Coalition Formation on Valuation Structures: Formal Framework, Applications, and Islands of Tractability (Extended Abstract)
Authors: Greco Gianluigi , Guzzo Antonella
Published: July 2018

Coalition structure generation is considered in a setting where feasible coalition structures must satisfy constraints of two different kinds modeled in terms of a valuation structure, which consists of a set of pivotal agents that are pairwise incompatible, plus an interaction graph prescribing that a coalition C can form only if the subgraph induced over the nodes/agents in C is connected. It is shown that valuation structures can be used to model a number of relevant problems in real-world applications. Moreover, complexity issues arising with them are studied, by focusing in particular on identifying islands of tractability based on topological properties of the underlying interaction graph. Stability issues on valuation structures are studied too.