bluuebunny/crossref_metadata_2025 huggingface dataset:
New Metrics and Algorithms for Stochastic Goal Recognition Design Problems
Authors: Wayllace Christabel , Hou Ping , Yeoh William
Published: July 2017

Goal Recognition Design (GRD) problems involve identifying the best ways to modify the underlying environment that agents operate in, typically by making a subset of feasible actions infeasible, in such a way that agents are forced to reveal their goals as early as possible. The Stochastic GRD (S-GRD) model is an important extension that introduced stochasticity to the outcome of agent actions. Unfortunately, the worst-case distinctiveness (wcd) metric proposed for S-GRDs has a formal definition that is inconsistent with its intuitive definition, which is the maximal number of actions an agent can take, in the expectation, before its goal is revealed. In this paper, we make the following contributions: (1) We propose a new wcd metric, called all-goals wcd (wcdag), that remedies this inconsistency; (2) We introduce a new metric, called expected-case distinctiveness (ecd), that weighs the possible goals based on their importance; (3) We provide theoretical results comparing these different metrics as well as the complexity of computing them optimally; and (4) We describe new efficient algorithms to compute the wcdag and ecd values.
A Scalable Approach to Chasing Multiple Moving Targets with Multiple Agents
Authors: Xie Fan , Botea Adi , Kishimoto Akihiro
Published: July 2017

Chasing multiple mobile targets with multiple agents is important in several applications, such as computer games and police chasing scenarios. Existing approaches can compute optimal policies. However, they have a limited scalability, as they implement expensive minimax searches. We introduce a sub-optimal but scalable approach that assigns individual agents to individual targets and that can dynamically re-compute such assignments. We provide a theoretical analysis, including upper bounds on the number of time steps required to solve an instance. In a detailed empirical evaluation on grid maps, our algorithm scales up very convincingly beyond the limits of previous methods. On small problems, where a comparison to a minimax approach is possible, the results demonstrate a good solution quality for our method.
Bridging the Gap between Observation and Decision Making: Goal Recognition and Flexible Resource Allocation in Dynamic Network Interdiction
Authors: Xu Kai , Xiao Kaiming , Yin Quanjun , Zha Yabing , Zhu Cheng
Published: July 2017

Goal recognition, which is the task of inferring an agent’s goals given some or all of the agent’s observed actions, is one of the important approaches in bridging the gap between the observation and decision making within an observe-orient-decide-act cycle. Unfortunately, few researches focus on how to improve the utilization of knowledge produced by a goal recognition system. In this work, we propose a Markov Decision Process-based goal recognition approach tailored to a dynamic shortest-path local network interdiction (DSPLNI) problem. We first introduce a novel DSPLNI model and its solvable dual form so as to incorporate real-time knowledge acquired from goal recognition system. Then a Markov Decision Process-based goal recognition model along with its dynamic Bayesian network representation and the applied goal inference method is proposed to identify the evader’s real goal within the DSPLNI context. Based on that, we further propose an efficient scalable technique in maintaining action utility map used in fast goal inference, and develop a flexible resource assignment mechanism in DSPLNI using knowledge from goal recognition system. Experimental results show the effectiveness and accuracy of our methods both in goal recognition and dynamic network interdiction.
Dual Track Multimodal Automatic Learning through Human-Robot Interaction
Authors: Jiang Shuqiang , Min Weiqing , Li Xue , Wang Huayang , Sun Jian , Zhou Jiaqi
Published: July 2017

Human beings are constantly improving their cognitive ability via automatic learning from the interaction with the environment. Two important aspects of automatic learning are the visual perception and knowledge acquisition. The fusion of these two aspects is vital for improving the intelligence and interaction performance of robots. Many automatic knowledge extraction and recognition methods have been widely studied. However, little work focuses on integrating automatic knowledge extraction and recognition into a unified framework to enable jointly visual perception and knowledge acquisition. To solve this problem, we propose a Dual Track Multimodal Automatic Learning (DTMAL) system, which consists of two components: Hybrid Incremental Learning (HIL) from the vision track and Multimodal Knowledge Extraction (MKE) from the knowledge track. HIL can incrementally improve recognition ability of the system by learning new object samples and new object concepts. MKE is capable of constructing and updating the multimodal knowledge items based on the recognized new objects from HIL and other knowledge by exploring the multimodal signals. The fusion of the two tracks is a mutual promotion process and jointly devote to the dual track learning. We have conducted the experiments through human-machine interaction and the experimental results validated the effectiveness of our proposed system.
Temporal Grounding Graphs for Language Understanding with Accrued Visual-Linguistic Context
Authors: Paul Rohan , Barbu Andrei , Felshin Sue , Katz Boris , Roy Nicholas
Published: July 2017

A robot’s ability to understand or ground natural language instructions is fundamentally tied to its knowledge about the surrounding world. We present an approach to grounding natural language utterances in the context of factual information gathered through natural-language interactions and past visual observations. A probabilistic model estimates, from a natural language utterance, the objects, relations, and actions that the utterance refers to, the objectives for future robotic actions it implies, and generates a plan to execute those actions while updating a state representation to include newly acquired knowledge from the visual-linguistic context. Grounding a command necessitates a representation for past observations and interactions; however, maintaining the full context consisting of all possible observed objects, attributes, spatial relations, actions, etc., over time is intractable. Instead, our model, Temporal Grounding Graphs, maintains a learned state representation for a belief over factual groundings, those derived from natural-language interactions, and lazily infers new groundings from visual observations using the context implied by the utterance. This work significantly expands the range of language that a robot can understand by incorporating factual knowledge and observations of its workspace into its inference about the meaning and grounding of natural-language utterances.
Maintaining Communication in Multi-Robot Tree Coverage
Authors: Sinay Mor , Agmon Noa , Maksimov Oleg , Kraus Sarit , Peleg David
Published: July 2017

Area coverage is an important task for mobile robots, mainly due to its applicability in many domains, such as search and rescue. In this paper we study the problem of multi-robot coverage, in which the robots must obey a strong communication restriction: they should maintain connectivity between teammates throughout the coverage. We formally describe the Multi-Robot Connected Tree Coverage problem, and an algorithm for covering perfect N-ary trees while adhering to the communication requirement. The algorithm is analyzed theoretically, providing guarantees for coverage time by the notion of speedup factor. We enhance the theoretically-proven solution with a dripping heuristic algorithm, and show in extensive simulations that it significantly decreases the coverage time. The algorithm is then adjusted to general (not necessarily perfect) N-ary trees and additional experiments prove its efficiency. Furthermore, we show the use of our solution in a simulated officebuilding scenario. Finally, we deploy our algorithm on real robots in a real office building setting, showing efficient coverage time in practice.
Cross-Granularity Graph Inference for Semantic Video Object Segmentation
Authors: Wang Huiling , Wang Tinghuai , Chen Ke , Kämäräinen Joni-Kristian
Published: July 2017

We address semantic video object segmentation via a novel cross-granularity hierarchical graphical model to integrate tracklet and object proposal reasoning with superpixel labeling. Tracklet characterizes varying spatial-temporal relations of video object which, however, quite often suffers from sporadic local outliers. In order to acquire high-quality tracklets, we propose a transductive inference model which is capable of calibrating short-range noisy object tracklets with respect to long-range dependencies and high-level context cues. In the center of this work lies a new paradigm of semantic video object segmentation beyond modeling appearance and motion of objects locally, where the semantic label is inferred by jointly exploiting multi-scale contextual information and spatial-temporal relations of video object. We evaluate our method on two popular semantic video object segmentation benchmarks and demonstrate that it advances the state-of-the-art by achieving superior accuracy performance than other leading methods.
Is My Object in This Video? Reconstruction-based Object Search in Videos
Authors: Yu Tan , Meng Jingjing , Yuan Junsong
Published: July 2017

This paper addresses the problem of video-level object instance search, which aims to retrieve the videos in the database that contain a given query object instance. Without prior knowledge about "when" and "where" an object of interest may appear in a video, determining "whether" a video contains the target object is computationally prohibitive, as it requires exhaustively matching the query against all possible spatial-temporal locations in each video that an object may appear. To alleviate the computational and memory cost, we propose the Reconstruction-based Object SEarch (ROSE) method.It characterizes a huge corpus of features of possible spatial-temporal locations in the video into the parameters of the reconstruction model. Since the memory cost of storing reconstruction model is much less than that of storing features of possible spatial-temporal locations in the video, the efficiency of the search is significantly boosted. Comprehensive experiments on three benchmark datasets demonstrate the promising performance of the proposed ROSE method.
Efficient Inference for Untied MLNs
Authors: Sarkhel Somdeb , Venugopal Deepak , Ruozzi Nicholas , Gogate Vibhav
Published: July 2017

We address the problem of scaling up local-search or sampling-based inference in Markov logic networks (MLNs) that have large shared sub-structures but no (or few) tied weights. Such untied MLNs are ubiquitous in practical applications. However, they have very few symmetries, and as a result lifted inference algorithms--the dominant approach for scaling up inference--perform poorly on them. The key idea in our approach is to reduce the hard, time-consuming sub-task in sampling algorithms, computing the sum of weights of features that satisfy a full assignment, to the problem of computing a set of partition functions of graphical models, each defined over the logical variables in a first-order formula. The importance of this reduction is that when the treewidth of all the graphical models is small, it yields an order of magnitude speedup. When the treewidth is large, we propose an over-symmetric approximation and experimentally demonstrate that it is both fast and accurate.
Scalable Estimation of Dirichlet Process Mixture Models on Distributed Data
Authors: Wang Ruohui , Lin Dahua
Published: July 2017

We consider the estimation of Dirichlet Process Mixture Models (DPMMs) in distributed environments, where data are distributed across multiple computing nodes. A key advantage of Bayesian nonparametric models such as DPMMs is that they allow new components to be introduced on the fly as needed. This, however, posts an important challenge to distributed estimation -- how to handle new components efficiently and consistently. To tackle this problem, we propose a new estimation method, which allows new components to be created locally in individual computing nodes. Components corresponding to the same cluster will be identified and merged via a probabilistic consolidation scheme. In this way, we can maintain the consistency of estimation with very low communication cost. Experiments on large real-world data sets show that the proposed method can achieve high scalability in distributed and asynchronous environments without compromising the mixing performance.
Dynamic Programming Bipartite Belief Propagation For Hyper Graph Matching
Authors: Zhang Zhen , McAuley Julian , Li Yong , Wei Wei , Zhang Yanning , Shi Qinfeng
Published: July 2017

Hyper graph matching problems have drawn attention recently due to their ability to embed higher order relations between nodes. In this paper, we formulate hyper graph matching problems as constrained MAP inference problems in graphical models. Whereas previous discrete approaches introduce several global correspondence vectors, we introduce only one global correspondence vector, but several local correspondence vectors. This allows us to decompose the problem into a (linear) bipartite matching problem and several belief propagation sub-problems. Bipartite matching can be solved by traditional approaches, while the belief propagation sub-problem is further decomposed as two sub-problems with optimal substructure. Then a newly proposed dynamic programming procedure is used to solve the belief propagation sub-problem. Experiments show that the proposed methods outperform state-of-the-art techniques for hyper graph matching.
How to Form Winning Coalitions in Mixed Human-Computer Settings
Authors: Zick Yair , Gal Kobi , Bachrach Yoram , Mash Moshe
Published: July 2017

Despite the prevalence of weighted voting in the real world, there has been relatively little work studying real people's behavior in such settings. This paper proposes a new negotiation game, based on the weighted voting paradigm in cooperative games, where players need to form coalitions and agree on how to share the gains. We show that solution concepts from cooperative game theory (in particular, an extension of the Deegan-Packel Index) provide a good prediction of people's decisions to join a given coalition. With this insight in mind, we design an agent that combines predictive analytics with decision theory to make offers to people in the game. We show that the agent was able to obtain higher shares from coalitions than did people playing other people, without reducing the acceptance rate of its offers. These results demonstrate the potential of incorporating concepts from cooperative game theory in the design of negotiating agents.
Privacy and Autonomous Systems
Authors: Such Jose M.
Published: July 2017

We discuss the problem of privacy in autonomous systems, introducing different conceptualizations and perspectives on privacy to assess the threats that autonomous systems may pose to privacy. After this, we outline socio-technical and legal measures that should be put in place to mitigate these threats. Beyond privacy threats and countermeasures, we also argue how autonomous systems may be, at the same time, the key to address some of the most challenging and pressing privacy problems nowadays and in the near future.
Estimating the size of search trees by sampling with domain knowledge
Authors: Belov Gleb , Esler Samuel , Fernando Dylan , Le Bodic Pierre , Nemhauser George L.
Published: July 2017

We show how recently-defined abstract models of the Branch-and-Bound algorithm can be used to obtain information on how the nodes are distributed in B&B search trees. This can be directly exploited in the form of probabilities in a sampling algorithm given by Knuth that estimates the size of a search tree. This method reduces the offline estimation error by a factor of two on search trees from Mixed-Integer Programming instances.
Efficient Techniques for Crowdsourced Top-k Lists
Authors: de Alfaro Luca , Polychronopoulos Vassilis , Polyzotis Neoklis
Published: July 2017

We focus on the problem of obtaining top-k lists of items from larger itemsets, using human workers for doing comparisons among items.An example application is short-listing a large set of college applications using advanced students as workers. We describe novel efficient techniques and explore their tolerance to adversarial behavior and the tradeoffs among different measures of performance (latency, expense and quality of results). We empirically evaluate the proposed techniques against prior art using simulations as well as real crowds in Amazon Mechanical Turk. A randomized variant of the proposed algorithms achieves significant budget saves, especially for very large itemsets and large top-k lists, with negligible risk of lowering the quality of the output.
Ensuring Rapid Mixing and Low Bias for Asynchronous Gibbs Sampling
Authors: De Sa Christopher , Olukotun Kunle , Ré Christopher
Published: July 2017

Gibbs sampling is a Markov chain Monte Carlo technique commonly used for estimating marginal distributions. To speed up Gibbs sampling, there has recently been interest in parallelizing it by executing asynchronously. While empirical results suggest that many models can be efficiently sampled asynchronously, traditional Markov chain analysis does not apply to the asynchronous case, and thus asynchronous Gibbs sampling is poorly understood. In this paper, we derive a better understanding of the two main challenges of asynchronous Gibbs: bias and mixing time. We show experimentally that our theoretical results match practical outcomes.
Intuitionistic Layered Graph Logic
Authors: Docherty Simon , Pym David
Published: July 2017

Models of complex systems are widely used in the physical and social sciences, and the concept of layering, typically building upon graph-theoretic structure, is a common feature. We describe an intuitionistic substructural logic that gives an account of layering. As in other bunched systems, the logic includes the usual intuitionistic connectives, together with a non-commutative, non-associative conjunction (used to capture layering) and its associated implications. We give a soundness and completeness theorem for a labelled tableaux system with respect to a Kripke semantics on graphs. To demonstrate the utility of the logic, we show how to represent systems and security examples, illuminating the relationship between services/policies and the infrastructures/architectures to which they are applied.
Using Constraint Programming to solve a Cryptanalytic Problem
Authors: Gerault David , Minier Marine , Solnon Christine
Published: July 2017

We describe Constraint Programming (CP) models to solve a cryptanalytic problem: the chosen key differential attack against the standard block cipher AES. We show that CP solvers are able to solve these problems quicker than dedicated cryptanalysis tools, and we prove that a solution claimed to be optimal in two recent cryptanalysis papers is not optimal by providing a better solution.
First-Order Modular Logic Programs and their Conservative Extensions (Extended Abstract)
Authors: Harrison Amelia , Lierler Yuliya
Published: July 2017

This paper introduces first-order modular logic programs, which provide a way of viewing answer set programs as consisting of many independent, meaningful modules. We also present conservative extensions of such programs. This concept helps to identify strong relationships between modular programs as well as between traditional programs. For example, we illustrate how the notion of a conservative extension can be used to justify the common projection rewriting. This is a short version of a paper was presented at the 32nd International Conference on Logic Programming (Harrison and Lierler, 2016).
Solving Very Hard Problems: Cube-and-Conquer, a Hybrid SAT Solving Method
Authors: Heule Marijn J.H. , Kullmann Oliver , Marek Victor W.
Published: July 2017

A recent success of SAT solving has been the solution of the boolean Pythagorean Triples problem [Heule et al., 2016], delivering the largest proof yet, of 200 terabytes in size. We present this and the underlying paradigm Cube-and-Conquer, a powerful general method to solve big SAT problems, based on integrating the “old” and “new” methods of SAT solving.
Learning and Applying Case Adaptation Rules for Classification: An Ensemble Approach
Authors: Jalali Vahid , Leake David , Forouzandehmehr Najmeh
Published: July 2017

The ability of case-based reasoning systems to solve novel problems depends on their capability to adapt past solutions to new circumstances. However, acquiring the knowledge required for case adaptation is a classic challenge for CBR. This motivates the use of machine learning methods to generate adaptation knowledge. A popular approach uses the case difference heuristic (CDH) to generate adaptation rules from pairs of cases in the case base, based on the premise that the observed differences in case solutions result from the differences in the problems they solve, so can form the basic of rules to adapt cases with similar problem differences. Extensive research has successfully applied the CDH approach to adaptation rule learning for case-based regression (numerical prediction) tasks. However, classification tasks have been outside of its scope. The work presented in this paper addresses that gap by extending CDH-based learning of adaptation rules to apply to cases with categorical features and solutions. It presents the generalized case value heuristic to assess case and solution differences and applies it in an ensemble-based case-based classification method, ensembles of adaptations for classification (EAC), built on the authors' previous work on ensembles of adaptations for regression (EAR). Experimental results support the effectiveness of EAC.
Dynamical System-Based Motion Planning for Multi-Arm Systems: Reaching for Moving Objects
Authors: Mirrazavi Salehian Seyed Sina , Figueroa Nadia , Billard Aude
Published: July 2017

The use of coordinated multi-arm robotic systems allows to preform manipulations of heavy or bulky objects that would otherwise be infeasible for a single-arm robot. This paper concisely introduces our work on coordinated multi-arm control [Salehian et al., 2016a], where we proposed a virtual object based dynamical systems (DS) control law to generate autonomous and synchronized motions for a multi-arm robot system. We show theoretically and empirically that the multi-arm + virtual object system converges asymptotically to a moving object. The proposed framework is validated on a dual-arm robotic system. We demonstrate that it can re-synchronize and adapt the motion of each arm in a fraction of a second, even when the object’s motion is fast and not accurately predictable.
Evaluating Market User Interfaces for Electric Vehicle Charging using Bid2Charge
Authors: Stein Sebastian , Gerding Enrico H. , Nedea Adrian , Rosenfeld Avi , Jennings Nicholas R.
Published: July 2017

We consider settings where electric vehicle drivers participate in a market mechanism to charge their vehicles. Existing work typically assumes that participants are fully rational and can report their charging preferences accurately. However, this may not be reasonable in settings with non-experts. To explore this, we design a novel game called Bid2Charge and compare a fully expressive interface that covers the entire space of preferences to two restricted interfaces that offer fewer possible reports. We show that restricting the users' preferences significantly reduces deliberation times while also leading to an increase in utility by up to 70%.
Pure Nash Equilibria in Online Fair Division
Authors: Aleksandrov Martin , Walsh Toby
Published: July 2017

We consider a fair division setting in which items arrive one by one and are allocated to agents via two existing mechanisms: LIKE and BALANCED LIKE. The LIKE mechanism is strategy-proof whereas the BALANCED LIKE mechanism is not. Whilst LIKE is strategy-proof, we show that it is not group strategy-proof. Indeed, our first main result is that no online mechanism is group strategy-proof. We then focus on pure Nash equilibria of these two mechanisms. Our second main result is that computing a pure Nash equilibrium is tractable for LIKE and intractable for BALANCED LIKE. Our third main result is that there could be multiple such profiles and counting them is also intractable even when we restrict our attention to equilibria with a specific property (e.g. envy-freeness, Pareto efficiency).
Compromise-free Pathfinding on a Navigation Mesh
Authors: Cui Michael , Harabor Daniel D. , Grastien Alban
Published: July 2017

We want to compute geometric shortest paths in a collection of convex traversable polygons, also known as a navigation mesh. Simple to compute and easy to update, navigation meshes are widely used for pathfinding in computer games. When the mesh is static, shortest path problems can be solved exactly and very fast but only after a costly preprocessing step. When the mesh is dynamic, practitioners turn to online methods which typically compute only approximately shortest paths. In this work we present a new pathfinding algorithm which is compromise-free; i.e. it is simultaneously fast, online and optimal. Our method, Polyanya, extends and generalises Anya; a recent and related interval-based search technique developed for computing geometric shortest paths in grids. We show how that algorithm can be modified to support search over arbitrary sets of convex polygons and then evaluate its performance on a range of realistic and synthetic benchmark problems.
I-dual: Solving Constrained SSPs via Heuristic Search in the Dual Space
Authors: Trevizan Felipe , Thiebaux Sylvie , Santana Pedro , Williams Brian
Published: July 2017

We consider the problem of generating optimal stochastic policies for Constrained Stochastic Shortest Path problems, which are a natural model for planning under uncertainty for resource-bounded agents with multiple competing objectives. While unconstrained SSPs enjoy a multitude of efficient heuristic search solution methods with the ability to focus on promising areas reachable from the initial state, the state of the art for constrained SSPs revolves around linear and dynamic programming algorithms which explore the entire state space. In this paper, we present i-dual, the first heuristic search algorithm for constrained SSPs. To concisely represent constraints and efficiently decide their violation, i-dual operates in the space of dual variables describing the policy occupation measures. It does so while retaining the ability to use standard value function heuristics computed by well-known methods. Our experiments show that these features enable i-dual to achieve up to two orders of magnitude improvement in run-time and memory over linear programming algorithms.
On Minimum Representations of Matched Formulas (Extended Abstract)
Authors: Čepek Ondřej , Gurský Štefan , Kučera Petr
Published: July 2017

A Boolean formula in conjunctive normal form (CNF) is called matched if the system of sets of variables which appear in individual clauses has a system of distinct representatives. We present here two results for matched CNFs: The first result is a shorter and simpler proof of the fact that Boolean minimization remains complete for the second level of polynomial hierarchy even if the input is restricted to matched CNFs. The second result is structural --- we show that if a Boolean function f admits a representation by a matched CNF then every clause minimum CNF representation of f is matched.
Efficient Mechanism Design for Online Scheduling (Extended Abstract)
Authors: Chen Xujin , Hu Xiaodong , Liu Tie-Yan , Ma Weidong , Qin Tao , Tang Pingzhong , Wang Changjun , Zheng Bo
Published: July 2017

This work concerns the mechanism design for online scheduling in a strategic setting. In this setting, each job is owned by a self-interested agent who may misreport the release time, deadline, length, and value of her job, while we need to determine not only the schedule of the jobs, but also the payment of each agent. We focus on the design of incentive compatible (IC) mechanisms, and study the maximization of social welfare (i.e., the aggregated value of completed jobs) by competitive analysis. We first derive two lower bounds on the competitive ratio of any deterministic IC mechanism to characterize the landscape of our research: one bound is 5, which holds for equal-length jobs; the other bound is $\frac{\kappa}{\ln\kappa}+1-o(1)$, which holds for unequal-length jobs, where $\kappa$ is the maximum ratio between lengths of any two jobs. We then propose a deterministic IC mechanism and show that such a simple mechanism works very well for two models: (1) In the preemption-restart model, the mechanism can achieve the optimal competitive ratio of 5 for equal-length jobs and a near optimal ratio of $(\frac{1}{(1-\epsilon)^2}+o(1)) \frac{\kappa}{\ln\kappa}$ for unequal-length jobs, where $0<\epsilon<1$ is a small constant; (2) In the preemption-resume model, the mechanism can achieve the optimal competitive ratio of 5 for equal-length jobs and a near optimal competitive ratio (within factor 2) for unequal-length jobs.
Coherent Predictive Inference under Exchangeability with Imprecise Probabilities (Extended Abstract)
Authors: de Cooman Gert , De Bock Jasper , Alves Diniz Márcio
Published: July 2017

Coherent reasoning under uncertainty can be represented in a very general manner by coherent sets of desirable gambles. This leads to a more general foundation for coherent (imprecise-)probabilistic inference that allows for indecision. In this framework, and for a given finite category set, coherent predictive inference under exchangeability can be represented using Bernstein coherent cones of multivariate polynomials on the simplex generated by this category set. We define an inference system as a map that associates a Bernstein coherent cone of polynomials with every finite category set. Inference principles can then be represented mathematically as restrictions on such maps, which allows us to develop a notion of conservative inference under such inference principles. We discuss, as particular examples, representation insensitivity and specificity, and show that there is an infinity of inference systems that satisfy these two principles.
On Redundant Topological Constraints (Extended Abstract)
Authors: Li Sanjiang , Long Zhiguo , Liu Weiming , Duckham Matt , Both Alan
Published: July 2017

Redundancy checking is an important task in AI subfields such as knowledge representation and constraint solving. This paper considers redundant topological constraints, defined in the region connection calculus RCC8. We say a constraint in a set C of RCC8 constraints is redundant if it is entailed by the rest of C. A prime subnetwork of C is a subset of C which contains no redundant constraints and has the same solution set as C. It is natural to ask how to compute such a prime subnetwork, and when it is unique. While this problem is in general intractable, we show that, if S is a subalgebra of RCC8 in which weak composition distributes over nonempty intersections, then C has a unique prime subnetwork, which can be obtained in cubic time by removing all redundant constraints simultaneously from C. As a by-product, we show that any path-consistent network over such a distributive subalgebra is minimal.
Relations Between Spatial Calculi About Directions and Orientations (Extended Abstract)
Authors: Mossakowski Till , Moratz Reinhard
Published: July 2017

A qualitative representation of space and/or time provides mechanisms

which characterize the essential properties of objects or

configurations. The advantages over quantitative representations can be:

(1) a better match with human concepts related to natural language,

and (2) better efficiency for reasoning.

The two main trends in qualitative spatial constraint

reasoning are topological reasoning about regions

and reasoning about directions between points and straight lines and orientations of

straight lines or configurations derived from points.

In this work, we apply universal algebraic tools to binary qualitative calculi and their relations.
Construction of System of Spheres-based Transitively Relational Partial Meet Multiple Contractions: An Impossibility Result (Extended Abstract)
Authors: Reis Maurício D. L. , Fermé Eduardo , Peppas Pavlos
Published: July 2017

In this paper we show that, contrary to what is the case in what concerns contractions by a single sentence, there is not a system of spheres-based construction of multiple contractions which generates each and every transitively relational partial meet multiple contraction.

Furthermore, we propose two system of spheres-based constructions of multiple contractions which generate (only) transitively relational partial meet multiple contractions.
Exploiting Causality for Selective Belief Filtering in Dynamic Bayesian Networks (Extended Abstract)
Authors: V. Albrecht Stefano , Ramamoorthy Subramanian
Published: July 2017

Dynamic Bayesian networks (DBNs) are a general model for stochastic processes with partially observed states. Belief filtering in DBNs is the task of inferring the belief state (i.e. the probability distribution over process states) based on incomplete and uncertain observations. In this article, we explore the idea of accelerating the filtering task by automatically exploiting causality in the process. We consider a specific type of causal relation, called passivity, which pertains to how state variables cause changes in other variables. We present the Passivity-based Selective Belief Filtering (PSBF) method, which maintains a factored belief representation and exploits passivity to perform selective updates over the belief factors. PSBF is evaluated in both synthetic processes and a simulated multi-robot warehouse, where it outperformed alternative filtering methods by exploiting passivity.
Text Rewriting Improves Semantic Role Labeling (Extended Abstract)
Authors: Woodsend Kristian , Lapata Mirella
Published: July 2017

Large-scale annotated corpora are a prerequisite to developing high-performance NLP systems. Such corpora are expensive to produce, limited in size, often demanding linguistic expertise. In this paper we use text rewriting as a means of increasing the amount of labeled data available for model training. Our method uses automatically extracted rewrite rules from comparable corpora and bitexts to generate multiple versions of sentences annotated with gold standard labels. We apply this idea to semantic role labeling and show that a model trained on rewritten data outperforms the state of the art on the CoNLL-2009 benchmark dataset.
A Reduction based Method for Coloring Very Large Graphs
Authors: Lin Jinkun , Cai Shaowei , Luo Chuan , Su Kaile
Published: July 2017

The graph coloring problem (GCP) is one of the most studied NP hard problems and has numerous applications. Despite the practical importance of GCP, there are limited works in solving GCP for very large graphs. This paper explores techniques for solving GCP on very large real world graphs.We first propose a reduction rule for GCP, which is based on a novel concept called degree bounded independent set.The rule is iteratively executed by interleaving between lower bound computation and graph reduction. Based on this rule, we develop a novel method called FastColor, which also exploits fast clique and coloring heuristics. We carry out experiments to compare our method FastColor with two best algorithms for coloring large graphs we could find. Experiments on a broad range of real world large graphs show the superiority of our method. Additionally, our method maintains both upper bound and lower bound on the optimal solution, and thus it proves an optimal solution when the upper bound meets the lower bound. In our experiments, it proves the optimal solution for 97 out of 142 instances.
Knowledge Engineering for Intelligent Decision Support
Authors: Martínez María Vanina
Published: July 2017

Knowledge can be seen as the collection of skills and information an individual (or group) has acquired through experience, while intelligence as the ability to apply such knowledge. In many areas of Artificial Intelligence, we have been focusing for the last 40 years on the formalization and development of automated ways of finding and collecting data, as well as on the construction of models to represent that data adequately in a way that an automated system can make sense of it. However, in order to achieve real artificial intelligence we need to go beyond data and knowledge representation, and deeper into how such a system could, and would, use available knowledge in order to empower and enhance the capabilities of humans in making decisions in real-world applications. From my point of view, an AI should be able to combine automatically acquired data and knowledge together with specific domain expertise from the users that the tool is expected to help.
Towards Certified Unsolvability in Classical Planning
Authors: Röger Gabriele
Published: July 2017

While it is easy to verify that an action sequence is a solution for a classical planning task, there is no such verification capability if a task is reported unsolvable. We are therefore interested in certificates that allow an independent verification of the absence of solutions. We identify promising concepts for certificates that can be generated by a wide range of planning approaches. We present a first proposal of unsolvability certificates and sketch ideas how the underlying concepts can be used as part of a more flexible unsolvability proof system.
Unsupervised Learning via Total Correlation Explanation
Authors: Ver Steeg Greg
Published: July 2017

Learning by children and animals occurs effortlessly and largely without obvious supervision. Successes in automating supervised learning have not translated to the more ambiguous realm of unsupervised learning where goals and labels are not provided. Barlow (1961) suggested that the signal that brains leverage for unsupervised learning is dependence, or redundancy, in the sensory environment. Dependence can be characterized using the information-theoretic multivariate mutual information measure called total correlation. The principle of Total Cor-relation Ex-planation (CorEx) is to learn representations of data that "explain" as much dependence in the data as possible. We review some manifestations of this principle along with successes in unsupervised learning problems across diverse domains including human behavior, biology, and language.
Online Algorithm Selection
Authors: Degroote Hans
Published: July 2017

Algorithm selection approaches have achieved impressive performance improvements in many areas of AI. Most of the literature considers the offline algorithm selection problem, where the initial selection model is never updated after training. However, new data from running algorithms on instances becomes available while an algorithm selection method is in use. In this extended abstract, the online algorithm selection problem is considered. In online algorithm selection, additional data can be processed, and the selection model can change over time. This abstract details the online algorithm setting, shows that it is a contextual multi-armed bandit, proposes a solution methodology, and empirically validates it.
Constructive Recommendation
Authors: Dragone Paolo
Published: July 2017

Constructive recommendation is the task of recommending object “configurations”, i.e. objects that can be assembled from their components on the basis of the user preferences. Examples include: PC configurations, recipes, travel plans, layouts, and other structured objects. Recommended objects are created by maximizing a learned utility function over an exponentially (or even infinitely) large combinatorial space of configurations. The utility function is learned through preference elicitation, an interactive process for collecting user feedback about recommended objects. Constructive recommendation brings up a wide range of possible applications as well as many untackled research problems, ranging from the unprecedented complexity of the inference problem to the nontrivial choice of the type of user interaction.
Efficient Algorithms And Representations For Chance-constrained Mixed Constraint Programming
Authors: Fang Cheng
Published: July 2017

Resistance to adoption of autonomous systems comes in part from the perceived unreliability of the systems. Concerns can be addressed by approaches that guarantee the probability of success. This is achieved in chance-constrained constraint programming (CC-CP) by imposing constraints required for success, and providing upper-bounds on the probability of violating constraints. This extended abstract reports on novel uncertainty representations to address problems prevalent in current methods.
Generating Hard Random Boolean Formulas and Disjunctive Logic Programs
Authors: Amendola Giovanni , Ricca Francesco , Truszczynski Miroslaw
Published: July 2017

We propose a model of random quantified boolean formulas and their natural random disjunctive logic program counterparts. The model extends the standard models for random SAT and 2QBF. We provide theoretical bounds for the phase transition region in the new model, and show experimentally the presence of the easy-hard-easy pattern. Importantly, we show that the model is well suited for assessing solvers tuned to real-world instances. Moreover, to the best of our knowledge, our model and results on random disjunctive logic programs are the first of their kind.
Stochastic Constraint Programming
Authors: Hemmi David
Published: July 2017

Combinatorial optimisation problems often contain uncertainty that has to be taken into account to pro- duce realistic solutions. One way of describing the uncertainty is using scenarios, where each sce- nario describes different potential sets of problem parameters based on random distributions or his- torical data. While efficient algorithmic techniques exist for specific problem classes such as linear pro- grams, there are very few approaches that can han- dle general Constraint Programming formulations with uncertainty. The goal of my PhD is to develop generic methods for solving stochastic combina- torial optimisation problems formulated in a Con- straint Programming framework.
Machine Learning Techniques for MultiAgent Systems
Authors: Lewenberg Yoad
Published: July 2017

Research in artificial intelligence ranges over many subdisciplines, such as Natural Language Processing, Computer Vision, Machine Learning, and MultiAgent Systems. Recently, AI techniques have become increasingly robust and complex, and there has been enhanced interest in research at the intersection of seemingly disparate research areas. Such work is motivated by the observation that there is actually a great deal of commonality among areas, that can be exploited within subfields. One example of a successful combination is the intersection of machine learning and multiagent systems. For example ,Kearns et al. [2001] proposed an efficient graphical model-based algorithm for calculating Nash equilibria. Going in the other direction, Datta et al. [2015] showed that solution concepts from cooperative game theory can be used to uniquely characterize the influence measure of classifiers.
Human-Like Agents for Repeated Negotiation
Authors: Mell Johnathan
Published: July 2017

Virtual agents have been used as tools in negotiation—from acting as mediators to manifesting as full-fledged conversational partners. Virtual agents are a powerful tool for teaching negotiation skills, but require an accurate model of human behavior to perform well both as partners and teachers. The work proposed here aims to expand the current horizon of virtual negotiating agents to utilize human-like strategies. Further agents developed using this framework should be cognizant of the social factors influencing negotiation, including reputation effects and the implications of long-term repeated relationships. A roadmap of current efforts to develop agent platforms and future expansions is discussed.
Multi-Agent Systems of Inverse Reinforcement Learners in Complex Games
Authors: Mobley Dave
Published: July 2017

Real-world problems exhibit a few defining criteria that make them hard for computers to solve. Problems such as driving a car or flying a helicopter have primary goals of reaching a destination as well as doing it safely and timely. These problems must each manage many resources and tasks to achieve their primary goals. The tasks themselves are made up of states that are represented by variables or features. As the feature set grows, the problems become intractable. Computer games are smaller problems but also are representative of real-world problems of this type. In my research, I will look at a particular class of computer game, namely computer role-playing games (RPGs), which are made up of a collection of overarching goals such as improving the player avatar, navigating a virtual world, and keeping the avatar alive. While playing there are also subtasks such as combatting other characters and managing inventory which are not primary, but yet important to overall game play. I will be exploring tiered Reinforcement Learning techniques coupled with training from expert policies using Inverse Reinforcement Learning as a starting point on learning how to play a complex game while attempting to extrapolate ideal goals and rewards.
Nonparametric Online Machine Learning with Kernels
Authors: Nguyen Khanh
Published: July 2017

Max-margin and kernel methods are dominant approaches to solve many tasks in machine learning. However, the paramount question is how to solve model selection problem in these methods. It becomes urgent in online learning context. Grid search is a common approach, but it turns out to be highly problematic in real-world applications. Our approach is to view max-margin and kernel methods under a Bayesian setting, then use Bayesian inference tools to learn model parameters and infer hyper-parameters in principle ways for both batch and online setting.
Operationalizing Operational Logics: Semiotic Knowledge Representations for Interactive Systems
Authors: Osborn Joseph C.
Published: July 2017

All projects in AI begin by selecting or devising knowledge representations suitable for the project's functional requirements. Interactive systems (including games) have semiotic considerations on top of their functional requirements: they must be legible to users, players, and their own designers. AI working within or around interactive systems must acknowledge and support the concerns of human users. These concerns are generally phrased as inductive bias or domain knowledge and handled in an ad hoc way; I argue that it is possible and useful to represent them explicitly within a unifying approach. This work refines and extends operational logics, an interpretive framework describing how interactive systems communicate their own mechanisms to users. Making this move yields formal notations for interactive systems that are useful for humans and machines, with applications in modeling, verification, general game-playing, reverse-engineering, and automatic self-documentation.
Teaching Robots through Situated Interactive Dialogue and Visual Demonstrations
Authors: Part Jose L. , Lemon Oliver
Published: July 2017

The ability to quickly adapt to new environments and incorporate new knowledge is of great importance for robots operating in unstructured environments and interacting with non-expert users. This paper reports on our current progress in tackling this problem. We propose the development of a framework for teaching robots to perform tasks using natural language instructions, visual demonstrations and interactive dialogue. Moreover, we present a module for learning objects incrementally and on-the-fly that would enable robots to ground referents in the natural language instructions and reason about the state of the world.