text:
the issue of probabilistic reasoning with abstract argumentation frameworks. Moreover, we consider the scenario when assessments on the probabilities of a subset of the arguments are given and the probabilities of the remaining arguments have to be derived, taking both the topology of the argumentation framework and principles of probabilistic reasoning into account. We generalise this scenario by also considering inconsistent assessments, i.e., assessments that contradict the topology of the argumentation framework. Building on approaches to inconsistency measurement, we present a general framework to measure the amount of conict of these assessments and provide a method for inconsistency-tolerant reasoning.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {565–611},
numpages = {47}
}

@article{10.5555/3176788.3176801,
author = {Hew, Patrick Chisan},
title = {The Length of Shortest Vertex Paths in Binary Occupancy Grids Compared to Shortest R-Constrained Ones},
year = {2017},
issue_date = {May 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {59},
number = {1},
issn = {1076-9757},
abstract = {We study the problem of finding a short path from a start to a goal within a two-dimensional continuous and isotropic terrain that has been discretized into an array of accessible and blocked cells. A classic approach obtains a grid path where each step is along the edge of an accessible cell or diagonally across one. Grid paths su_er from 'digitization bias' - even if two locations have line-of-sight, the minimum travelling cost between them can be greater than the distance along the line-of-sight. In a vertex path, steps are allowed from a cell corner to any other cell corner if they have line-of-sight. While the 'digitization bias' is smaller, shortest vertex paths are impractical to find by brute force. Recent research has thus turned to methods for finding short (but not necessarily shortest) vertex paths. To establish the methods' potential utility, we calculate upper bounds on the difference in length between the shortest vertex paths versus the shortest r-constrained ones where an r-constrained path consists of line segments that each traverse at most r rows and at most r columns of cells. The difference in length reduces as r increases - indeed the shortest vertex paths are at most 1 percent shorter than the shortest 4-constrained ones. This article will be useful to developers and users of short(est) vertex paths algorithms who want to trade path length for improved runtimes in a predictable manner.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {543–563},
numpages = {21}
}

@article{10.5555/3176788.3176800,
author = {Ramakrishnan, Ramya and Zhang, Chongjie and Shah, Julie},
title = {Perturbation Training for Human-Robot Teams},
year = {2017},
issue_date = {May 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {59},
number = {1},
issn = {1076-9757},
abstract = {In this work, we design and evaluate a computational learning model that enables a human-robot team to co-develop joint strategies for performing novel tasks that require coordination. The joint strategies are learned through "perturbation training," a human team-training strategy that requires team members to practice variations of a given task to help their team generalize to new variants of that task. We formally define the problem of human-robot perturbation training and develop and evaluate the first end-to-end framework for such training, which incorporates a multi-agent transfer learning algorithm, human-robot co-learning framework and communication protocol. Our transfer learning algorithm, Adaptive Perturbation Training (AdaPT), is a hybrid of transfer and reinforcement learning techniques that learns quickly and robustly for new task variants. We empirically validate the benefits of AdaPT through comparison to other hybrid reinforcement and transfer learning techniques aimed at transferring knowledge from multiple source tasks to a single target task.We also demonstrate that AdaPT's rapid learning supports live interaction between a person and a robot, during which the human-robot team trains to achieve a high level of performance for new task variants. We augment AdaPT with a co-learning framework and a computational bi-directional communication protocol so that the robot can co-train with a person during live interaction. Results from large-scale human subject experiments (n=48) indicate that AdaPT enables an agent to learn in a manner compatible with a human's own learning process, and that a robot undergoing perturbation training with a human results in a high level of team performance. Finally, we demonstrate that human-robot training using AdaPT in a simulation environment produces effective performance for a team incorporating an embodied robot partner.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {495–541},
numpages = {47}
}

@article{10.5555/3176788.3176799,
author = {Cai, Shaowei and Lin, Jinkun and Luo, Chuan},
title = {Finding a Small Vertex Cover in Massive Sparse Graphs: Construct, Local Search, and Preprocess},
year = {2017},
issue_date = {May 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {59},
number = {1},
issn = {1076-9757},
abstract = {The problem of finding a minimum vertex cover (MinVC) in a graph is a well known NP-hard combinatorial optimization problem of great importance in theory and practice. Due to its NP-hardness, there has been much interest in developing heuristic algorithms for finding a small vertex cover in reasonable time. Previously, heuristic algorithms for MinVC have focused on solving graphs of relatively small size, and they are not suitable for solving massive graphs as they usually have high-complexity heuristics. This paper explores techniques for solving MinVC in very large scale real-world graphs, including a construction algorithm, a local search algorithm and a preprocessing algorithm. Both the construction and search algorithms are based on low-complexity heuristics, and we combine them to develop a heuristic algorithm for MinVC called FastVC. Experimental results on a broad range of real-world massive graphs show that, our algorithms are very fast and have better performance than previous heuristic algorithms for MinVC. We also develop a preprocessing algorithm to simplify graphs for MinVC algorithms. By applying the preprocessing algorithm to local search algorithms, we obtain two efficient MinVC solvers called NuMVC2+p and FastVC2+p, which show further improvement on the massive graphs.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {463–494},
numpages = {32}
}

@article{10.5555/3176788.3176798,
author = {Li, Yuqian and Conitzer, Vincent},
title = {Game-Theoretic Question Selection for Tests},
year = {2017},
issue_date = {May 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {59},
number = {1},
issn = {1076-9757},
abstract = {Conventionally, the questions on a test are assumed to be kept secret from test takers until the test. However, for tests that are taken on a large scale, particularly asynchronously, this is very hard to achieve. For example, TOEFL iBT and driver's license test questions are easily found online. This also appears likely to become an issue for Massive Open Online Courses (MOOCs, as offered for example by Coursera, Udacity, and edX). Specifically, the test result may not reflect the true ability of a test taker if questions are leaked beforehand.In this paper, we take the loss of confidentiality as a fact. Even so, not all hope is lost as the test taker can memorize only a limited set of questions' answers, and the tester can randomize which questions to let appear on the test. We model this as a Stackelberg game, where the tester commits to a mixed strategy and the follower responds. Informally, the goal of the tester is to best reveal the true ability of a test taker, while the test taker tries to maximize the test result (pass probability or score). We provide an exponential-size linear program formulation that computes the optimal test strategy, prove several NP-hardness results on computing optimal test strategies in general, and give efficient algorithms for special cases (scored tests and single-question tests). Experiments are also provided for those proposed algorithms to show their scalability and the increase of the tester's utility relative to that of the uniform-at-random strategy. The increase is quite significant when questions have some correlation--for example, when a test taker who can solve a harder question can always solve easier questions.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {437–462},
numpages = {26}
}

@article{10.5555/3176788.3176797,
author = {Otten, Lars and Dechter, Rina},
title = {AND/OR Branch-and-Bound on a Computational Grid},
year = {2017},
issue_date = {May 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {59},
number = {1},
issn = {1076-9757},
abstract = {We present a parallel AND/OR Branch-and-Bound scheme that uses the power of a computational grid to push the boundaries of feasibility for combinatorial optimization. Two variants of the scheme are described, one of which aims to use machine learning techniques for parallel load balancing. In-depth analysis identifies two inherent sources of parallel search space redundancies that, together with general parallel execution overhead, can impede parallelization and render the problem far from embarrassingly parallel. We conduct extensive empirical evaluation on hundreds of CPUs, the first of its kind, with overall positive results. In a significant number of cases parallel speedup is close to the theoretical maximum and we are able to solve many very complex problem instances orders of magnitude faster than before; yet analysis of certain results also serves to demonstrate the inherent limitations of the approach due to the aforementioned redundancies.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {351–435},
numpages = {85}
}

@article{10.5555/3176788.3176796,
author = {Tassa, Tamir and Grinshpoun, Tal and Zivan, Roie},
title = {Privacy Preserving Implementation of the Max-Sum Algorithm and Its Variants},
year = {2017},
issue_date = {May 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {59},
number = {1},
issn = {1076-9757},
abstract = {One of the basic motivations for solving DCOPs is maintaining agents' privacy. Thus, researchers have evaluated the privacy loss of DCOP algorithms and defined corresponding notions of privacy preservation for secured DCOP algorithms. However, no secured protocol was proposed for MAX-SUM, which is among the most studied DCOP algorithms. As part of the ongoing effort of designing secure DCOP algorithms, we propose P-MAX-SUM, the first private algorithm that is based on Max-Sum. The proposed algorithm has multiple agents preforming the role of each node in the factor graph, on which the MAX-SUM algorithm operates. P-MAX-SUM preserves three types of privacy: topology privacy, constraint privacy, and assignment/decision privacy. By allowing a single call to a trusted coordinator, P-MAX-SUM also preserves agent privacy. The two main cryptographic means that enable this privacy preservation are secret sharing and homomorphic encryption. In addition, we design privacy-preserving implementations of four variants of Max-Sum. We conclude by analyzing the price of privacy in terns of runtime overhead, both theoretically and by extensive experimentation.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {311–349},
numpages = {39}
}

@article{10.5555/3176788.3176795,
author = {Farina, Gabriele and Gatti, Nicola},
title = {Adopting the Cascade Model in Ad Auctions: Efficiency Bounds and Truthful Algorithmic Mechanisms},
year = {2017},
issue_date = {May 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {59},
number = {1},
issn = {1076-9757},
abstract = {Sponsored Search Auctions (SSAs) are one of the most successful applications of microeconomic mechanisms, with a revenue of about $72 billion in the US alone in 2016. However, the problem of designing the best economic mechanism for sponsored search auctions is far from being solved, and, given the amount at stake, it is no surprise that it has received growing attention over the past few years. The most common auction mechanism for SSAs is the Generalized Second Price (GSP). However, the GSP is known not to be truthful: the agents participating in the auction might have an incentive to report false values, generating economic inefficiency and suboptimal revenues in turn. Superior, efficient truthful mechanisms, such as the Vickrey-Clarke-Groves (VCG) auction, are well known in the literature. However, while the VCG auction is currently adopted for the strictly related scenario of contextual advertising, e.g., by Google and Facebook, companies are reluctant to extend it to SSAs, fearing prohibitive switching costs. Other than truthfulness, two issues are of paramount importance in designing effective SSAs. First, the choice of the user model; not only does an accurate user model better target ads to users, it also is a critical factor in reducing the inefficiency of the mechanism. Often an antagonist to this, the second issue is the running time of the mechanism, given the performance pressure these mechanisms undertake in real-world applications. In our work, we argue in favor of adopting the VCG mechanism based on the cascade model with ad/position externalities (APDC-VCG). Our study includes both the derivation of inefficiency bounds and the design and the experimental evaluation of exact and approximate algorithms.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {265–310},
numpages = {46}
}

@article{10.5555/3176788.3176794,
author = {Ahmed, Asrar and Varakantham, Pradeep and Lowalekar, Meghna and Adulyasak, Yossiri and Jaillet, Patrick},
title = {Sampling Based Approaches for Minimizing Regret in Uncertain Markov Decision Processes (MDPs)},
year = {2017},
issue_date = {May 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {59},
number = {1},
issn = {1076-9757},
abstract = {Markov Decision Processes (MDPs) are an effective model to represent decision processes in the presence of transitional uncertainty and reward tradeoffs. However, due to the difficulty in exactly specifying the transition and reward functions in MDPs, researchers have proposed uncertain MDP models and robustness objectives in solving those models. Most approaches for computing robust policies have focused on the computation of maximin policies which maximize the value in the worst case amongst all realisations of uncertainty. Given the overly conservative nature of maximin policies, recent work has proposed minimax regret as an ideal alternative to the maximin objective for robust optimization. However, existing algorithms for handling minimax regret are restricted to models with uncertainty over rewards only and they are also limited in their scalability. Therefore, we provide a general model of uncertain MDPs that considers uncertainty over both transition and reward functions. Furthermore, we also consider dependence of the uncertainty across different states and decision epochs. We also provide a mixed integer linear program formulation for minimizing regret given a set of samples of the transition and reward functions in the uncertain MDP. In addition, we provide two myopic variants of regret, namely Cumulative Expected Myopic Regret (CEMR) and One Step Regret (OSR) that can be optimized in a scalable manner. Specifically, we provide dynamic programming and policy iteration based algorithms to optimize CEMR and OSR respectively. Finally, to demonstrate the effectiveness of our approaches, we provide comparisons on two benchmark problems from literature. We observe that optimizing the myopic variants of regret, OSR and CEMR are better than directly optimizing the regret.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {229–264},
numpages = {36}
}

@article{10.5555/3176788.3176793,
author = {Stein, Sebastian and Gerding, Enrico H. and Nedea, Adrian and Rosenfeld, Avi and Jennings, Nicholas R.},
title = {Market Interfaces for Electric Vehicle Charging},
year = {2017},
issue_date = {May 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {59},
number = {1},
issn = {1076-9757},
abstract = {We consider settings where owners of electric vehicles (EVs) participate in a market mechanism to charge their vehicles. Existing work on such mechanisms has typically assumed that participants are fully rational and can report their preferences accurately via some interface to the mechanism or to a software agent participating on their behalf. However, this may not be reasonable in settings with non-expert human end-users. Thus, our overarching aim in this paper is to determine experimentally if a fully expressive market interface that enables accurate preference reports is suitable for the EV charging domain, or, alternatively, if a simpler, restricted interface that reduces the space of possible options is preferable. In doing this, we measure the performance of an interface both in terms of how it helps participants maximise their utility and how it affects deliberation time. Our secondary objective is to contrast two different types of restricted interfaces that vary in how they restrict the space of preferences that can be reported. To enable this analysis, we develop a novel game that replicates key features of an abstract EV charging scenario. In two experiments with over 300 users, we show that restricting the users' preferences significantly reduces the time they spend deliberating (by up to half in some cases). An extensive usability survey confirms that this restriction is furthermore associated with a lower perceived cognitive burden on the users. More surprisingly, at the same time, using restricted interfaces leads to an increase in the users' performance compared to the fully expressive interface (by up to 70%). We also show that some restricted interfaces have the desirable effect of reducing the energy consumption of their users by up to 20% while achieving the same utility as other interfaces. Finally, we find that a reinforcement learning agent displays similar performance trends to human users, enabling a novel methodology for evaluating market interfaces.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {175–227},
numpages = {53}
}

@article{10.5555/3176788.3176792,
author = {Bredereck, Robert and Chen, Jiehua and Niedermeier, Rolf and Walsh, Toby},
title = {Parliamentary Voting Procedures: Agenda Control, Manipulation, and Uncertainty},
year = {2017},
issue_date = {May 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {59},
number = {1},
issn = {1076-9757},
abstract = {We study computational problems for two popular parliamentary voting procedures: the amendment procedure and the successive procedure. They work in multiple stages where the result of each stage may influence the result of the next stage. Both procedures proceed according to a given linear order of the alternatives, an agenda. We obtain the following results for both voting procedures: On the one hand, deciding whether one can make a specific alternative win by reporting insincere preferences by the fewest number of voters, the Coalitional Manipulation problem, or whether there is a suitable ordering of the agenda, the Agenda Control problem, takes polynomial time. On the other hand, our experimental studies with real-world data indicate that most preference profiles cannot be manipulated by only few voters and a successful agenda control is typically impossible. If the voters' preferences are incomplete, then deciding whether an alternative can possibly win is NP-hard for both procedures. Whilst deciding whether an alternative necessarily wins is coNP-hard for the amendment procedure, it is polynomial-time solvable for the successive procedure.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {133–173},
numpages = {41}
}

@article{10.5555/3176788.3176791,
author = {Chen, Yi-Chun and Wheeler, Tim A. and Kochenderfer, Mykel J.},
title = {Learning Discrete Bayesian Networks from Continuous Data},
year = {2017},
issue_date = {May 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {59},
number = {1},
issn = {1076-9757},
abstract = {Learning Bayesian networks from raw data can help provide insights into the relationships between variables. While real data often contains a mixture of discrete and continuous-valued variables, many Bayesian network structure learning algorithms assume all random variables are discrete. Thus, continuous variables are often discretized when learning a Bayesian network. However, the choice of discretization policy has significant impact on the accuracy, speed, and interpretability of the resulting models. This paper introduces a principled Bayesian discretization method for continuous variables in Bayesian networks with quadratic complexity instead of the cubic complexity of other standard techniques. Empirical demonstrations show that the proposed method is superior to the established minimum description length algorithm. In addition, this paper shows how to incorporate existing methods into the structure learning process to discretize all continuous variables and simultaneously learn Bayesian network structures.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {103–132},
numpages = {30}
}

@article{10.5555/3176788.3176790,
author = {Roughgarden, Tim and Syrgkanis, Vasilis and Tardos, \'{E}va},
title = {The Price of Anarchy in Auctions},
year = {2017},
issue_date = {May 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {59},
number = {1},
issn = {1076-9757},
abstract = {This survey outlines a general and modular theory for proving approximation guarantees for equilibria of auctions in complex settings. This theory complements traditional economic techniques, which generally focus on exact and optimal solutions and are accordingly limited to relatively stylized settings.We highlight three user-friendly analytical tools: smoothness-type inequalities, which immediately yield approximation guarantees for many auction formats of interest in the special case of complete information and deterministic strategies; extension theorems, which extend such guarantees to randomized strategies, no-regret learning outcomes, and incomplete-information settings; and composition theorems, which extend such guarantees from simpler to more complex auctions. Combining these tools yields tight worst-case approximation guarantees for the equilibria of many widely-used auction formats.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {59–101},
numpages = {43}
}

@article{10.5555/3176788.3176789,
author = {Motzek, Alexander and M\"{o}ller, Ralf},
title = {Indirect Causes in Dynamic Bayesian Networks Revisited},
year = {2017},
issue_date = {May 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {59},
number = {1},
issn = {1076-9757},
abstract = {Modeling causal dependencies often demands cycles at a coarse-grained temporal scale. If Bayesian networks are to be used for modeling uncertainties, cycles are eliminated with dynamic Bayesian networks, spreading indirect dependencies over time and enforcing an infinitesimal resolution of time. Without a "causal design," i.e., without anticipating indirect influences appropriately in time, we argue that such networks return spurious results. By identifying activator random variables, we propose activator dynamic Bayesian networks (ADBNs) which are able to rapidly adapt to contexts under a causal use of time, anticipating indirect influences on a solid mathematical basis using familiar Bayesian network semantics. ADBNs are well-defined dynamic probabilistic graphical models allowing one to model cyclic dependencies from local and causal perspectives while preserving a classical, familiar calculus and classically known algorithms, without introducing any overhead in modeling or inference.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {1–58},
numpages = {58}
}

@article{10.5555/3176764.3176787,
author = {Ghooshchi, Nina Ghanbari and Namazi, Majid and Newton, M. A. Hakim and Sattar, Abdul},
title = {Encoding Domain Transitions for Constraint-Based Planning},
year = {2017},
issue_date = {January 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {58},
number = {1},
issn = {1076-9757},
abstract = {We describe a constraint-based automated planner named Transition Constraints for Parallel Planning (TCPP). TCPP constructs its constraint model from a redefined version of the domain transition graphs (DTG) of a given planning problem. TCPP encodes state transitions in the redefined DTGs by using table constraints with cells containing don't cares or wild cards. TCPP uses Minion the constraint solver to solve the constraint model and returns a parallel plan. We empirically compare TCPP with the other state-of-theart constraint-based parallel planner PaP2. PaP2 encodes action successions in the finite state automata (FSA) as table constraints with cells containing sets of values. PaP2 uses SICStus Prolog as its constraint solver. We also improve PaP2 by using don't cares and mutex constraints. Our experiments on a number of standard classical planning benchmark domains demonstrate TCPP's efficiency over the original PaP2 running on SICStus Prolog and our reconstructed and enhanced versions of PaP2 running on Minion.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {905–966},
numpages = {62}
}

@article{10.5555/3176764.3176786,
author = {Miller, Tim and Pfau, Jens and Sonenberg, Liz and Kashima, Yoshihisa},
title = {Logics of Common Ground},
year = {2017},
issue_date = {January 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {58},
number = {1},
issn = {1076-9757},
abstract = {According to Clark's seminal work on common ground and grounding, participants collaborating in a joint activity rely on their shared information, known as common ground, to perform that activity successfully, and continually align and augment this information during their collaboration. Similarly, teams of human and artificial agents require common ground to successfully participate in joint activities. Indeed, without appropriate information being shared, using agent autonomy to reduce the workload on humans may actually increase workload as the humans seek to understand why the agents are behaving as they are. While many researchers have identified the importance of common ground in artificial intelligence, there is no precise definition of common ground on which to build the foundational aspects of multi-agent collaboration. In this paper, building on previously-defined modal logics of belief, we present logic definitions for four different types of common ground. We define modal logics for three existing notions of common ground and introduce a new notion of common ground, called salient common ground. Salient common ground captures the common ground of a group participating in an activity and is based on the common ground that arises from that activity as well as on the common ground they shared prior to the activity. We show that the four definitions share some properties, and our analysis suggests possible refinements of the existing informal and semi-formal definitions.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {859–904},
numpages = {46}
}

@article{10.5555/3176764.3176785,
author = {Abseher, Michael and Musliu, Nysret and Woltran, Stefan},
title = {Improving the Efficiency of Dynamic Programming on Tree Decompositions via Machine Learning},
year = {2017},
issue_date = {January 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {58},
number = {1},
issn = {1076-9757},
abstract = {Dynamic Programming (DP) over tree decompositions is a well-established method to solve problems - that are in general NP-hard - efficiently for instances of small treewidth. Experience shows that (i) heuristically computing a tree decomposition has negligible runtime compared to the DP step; and (ii) DP algorithms exhibit a high variance in runtime when using different tree decompositions; in fact, given an instance of the problem at hand, even decompositions of the same width might yield extremely diverging runtimes. We thus propose here a novel and general method that is based on selection of the best decomposition from an available pool of heuristically generated ones. For this purpose, we require machine learning techniques that provide automated selection based on features of the decomposition rather than on the actual problem instance. Thus, one main contribution of this work is to propose novel features for tree decompositions. Moreover, we report on extensive experiments in different problem domains which show a significant speedup when choosing the tree decomposition according to this concept over simply using an arbitrary one of the same width.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {829–858},
numpages = {30}
}

@article{10.5555/3176764.3176784,
author = {Anshelevich, Elliot and Postl, John},
title = {Randomized Social Choice Functions under Metric Preferences},
year = {2017},
issue_date = {January 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {58},
number = {1},
issn = {1076-9757},
abstract = {We determine the quality of randomized social choice algorithms in a setting in which the agents have metric preferences: every agent has a cost for each alternative, and these costs form a metric. We assume that these costs are unknown to the algorithms (and possibly even to the agents themselves), which means we cannot simply select the optimal alternative, i.e. the alternative that minimizes the total agent cost (or median agent cost). However, we do assume that the agents know their ordinal preferences that are induced by the metric space. We examine randomized social choice functions that require only this ordinal information and select an alternative that is good in expectation with respect to the costs from the metric. To quantify how good a randomized social choice function is, we bound the distortion, which is the worst-case ratio between the expected cost of the alternative selected and the cost of the optimal alternative. We provide new distortion bounds for a variety of randomized algorithms, for both general metrics and for important special cases. Our results show a sizable improvement in distortion over deterministic algorithms.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {797–827},
numpages = {31}
}

@article{10.5555/3176764.3176783,
author = {Shperberg, Shahaf S. and Shimony, Solomon Eyal},
title = {Some Properties of Batch Value of Information in the Selection Problem},
year = {2017},
issue_date = {January 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {58},
number = {1},
issn = {1076-9757},
abstract = {Given a set of items of unknown utility, we need to select one with a utility as high as possible ("the selection problem"). Measurements (possibly noisy) of item values prior to selection are allowed, at a known cost. The goal is to optimize the overall sequential decision process of measurements and selection.Value of information (VOI) is a well-known scheme for selecting measurements, but the intractability of the problem typically leads to using myopic VOI estimates. Other schemes have also been proposed, some with approximation guarantees, based on submodularity criteria. However, it was observed that the VOI is not submodular in general. In this paper we examine theoretical properties of VOI for the selection problem, and identify cases of submodularity and supermodularity. We suggest how to use these properties to compute approximately optimal measurement batch policies, with an example based on a "wine selection problem".},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {777–796},
numpages = {20}
}

@article{10.5555/3176764.3176782,
author = {Bauters, Kim and McAreavey, Kevin and Liu, Weiru and Hong, Jun and Godo, Llu\'{\i}s},
title = {Managing Different Sources of Uncertainty in a BDI Framework in a Principled Way with Tractable Fragments},
year = {2017},
issue_date = {January 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {58},
number = {1},
issn = {1076-9757},
abstract = {The Belief-Desire-Intention (BDI) architecture is a practical approach for modelling large-scale intelligent systems. In the BDI setting, a complex system is represented as a network of interacting agents - or components - each one modelled based on its beliefs, desires and intentions. However, current BDI implementations are not well-suited for modelling more realistic intelligent systems which operate in environments pervaded by different types of uncertainty. Furthermore, existing approaches for dealing with uncertainty typically do not offer syntactical or tractable ways of reasoning about uncertainty. This complicates their integration with BDI implementations, which heavily rely on fast and reactive decisions. In this paper, we advance the state-of-the-art w.r.t. handling different types of uncertainty in BDI agents. The contributions of this paper are, first, a new way of modelling the beliefs of an agent as a set of epistemic states. Each epistemic state can use a distinct underlying uncertainty theory and revision strategy, and commensurability between epistemic states is achieved through a stratification approach. Second, we present a novel syntactic approach to revising beliefs given unreliable input. We prove that this syntactic approach agrees with the semantic definition, and we identify expressive fragments that are particularly useful for resource-bounded agents. Third, we introduce full operational semantics that extend Can, a popular semantics for BDI, to establish how reasoning about uncertainty can be tightly integrated into the BDI framework. Fourth, we provide comprehensive experimental results to highlight the usefulness and feasibility of our approach, and explain how the generic epistemic state can be instantiated into various representations.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {731–775},
numpages = {45}
}

@article{10.5555/3176764.3176781,
author = {Zhou, Hao and Zhang, Yue and Cheng, Chuan and Huang, Shujian and Dai, Xinyu and Chen, Jiajun},
title = {A Neural Probabilistic Structured-Prediction Method for Transition-Based Natural Language Processing},
year = {2017},
issue_date = {January 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {58},
number = {1},
issn = {1076-9757},
abstract = {We propose a neural probabilistic structured-prediction method for transition-based natural language processing, which integrates beam search and contrastive learning. The method uses a global optimization model, which can leverage arbitrary features over nonlocal context. Beam search is used for efficient heuristic decoding, and contrastive learning is performed for adjusting the model according to search errors. When evaluated on both chunking and dependency parsing tasks, the proposed method achieves significant accuracy improvements over the locally normalized greedy baseline on the two tasks, respectively.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {703–729},
numpages = {27}
}

@article{10.5555/3176764.3176780,
author = {Onta\~{n}\'{o}n, Santiago},
title = {Combinatorial Multi-Armed Bandits for Real-Time Strategy Games},
year = {2017},
issue_date = {January 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {58},
number = {1},
issn = {1076-9757},
abstract = {Games with large branching factors pose a significant challenge for game tree search algorithms. In this paper, we address this problem with a sampling strategy for Monte Carlo Tree Search (MCTS) algorithms called na\"{\i}ve sampling, based on a variant of the Multiarmed Bandit problem called Combinatorial Multi-armed Bandits (CMAB). We analyze the theoretical properties of several variants of na\"{\i}ve sampling, and empirically compare it against the other existing strategies in the literature for CMABs. We then evaluate these strategies in the context of real-time strategy (RTS) games, a genre of computer games characterized by their very large branching factors. Our results show that as the branching factor grows, na\"{\i}ve sampling outperforms the other sampling strategies.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {665–702},
numpages = {38}
}

@article{10.5555/3176764.3176779,
author = {Gluz, Jo\~{a}o and Jaques, Patricia A.},
title = {A Probabilistic Formalization of the Appraisal for the OCC Event-Based Emotions},
year = {2017},
issue_date = {January 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {58},
number = {1},
issn = {1076-9757},
abstract = {This article presents a logical formalization of the emotional appraisal theory, i.e., it formalizes the cognitive process of evaluation that elicits an emotion. This formalization is psychologically grounded on the OCC cognitive model of emotions. More specifically, we are interested in event-based emotions, i.e., emotions that are elicited by the evaluation of the consequences of an event that either happened or will happen. The formal modelling presented here is based on the AfPL Probabilistic Logic, a BDI-like probabilistic modal logic, which allows our model to verify whether the variables that determine the elicitation of emotions achieved the necessary threshold or not. The proposed logical formalization aims at addressing how the emotions are elicited by the agent cognitive mental states (desires, beliefs and intentions), and how to represent the intensity of the emotions. These are important initial points in the investigation of the dynamic interaction among emotions and other mental states.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {627–664},
numpages = {38}
}

@article{10.5555/3176764.3176778,
author = {Pappas, Nikolaos and Popescu-Belis, Andrei},
title = {Explicit Document Modeling through Weighted Multiple-Instance Learning},
year = {2017},
issue_date = {January 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {58},
number = {1},
issn = {1076-9757},
abstract = {Representing documents is a crucial component in many NLP tasks, for instance predicting aspect ratings in reviews. Previous methods for this task treat documents globally, and do not acknowledge that target categories are often assigned by their authors with generally no indication of the specific sentences that motivate them. To address this issue, we adopt a weakly supervised learning model, which jointly learns to focus on relevant parts of a document according to the context along with a classifier for the target categories. Derived from the weighted multiple-instance regression (MIR) framework, the model learns decomposable document vectors for each individual category and thus overcomes the representational bottleneck in previous methods due to a fixed-length document vector. During prediction, the estimated relevance or saliency weights explicitly capture the contribution of each sentence to the predicted rating, thus offering an explanation of the rating. Our model achieves state-of-the-art performance on multi-aspect sentiment analysis, improving over several baselines. Moreover, the predicted saliency weights are close to human estimates obtained by crowdsourcing, and increase the performance of lexical and topical features for review segmentation and summarization.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {591–626},
numpages = {36}
}

@article{10.5555/3176764.3176777,
author = {Tran, Tony T. and Vaquero, Tiago and Nejat, Goldie and Beck, J. Christopher},
title = {Robots in Retirement Homes: Applying off-the-Shelf Planning and Scheduling to a Team of Assistive Robots},
year = {2017},
issue_date = {January 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {58},
number = {1},
issn = {1076-9757},
abstract = {This paper investigates three different technologies for solving a planning and scheduling problem of deploying multiple robots in a retirement home environment to assist elderly residents. The models proposed make use of standard techniques and solvers developed in AI planning and scheduling, with two primary motivations. First, to find a planning and scheduling solution that we can deploy in our real-world application. Second, to evaluate planning and scheduling technology in terms of the "model-and-solve" functionality that forms a major research goal in both domain-independent planning and constraint programming. Seven variations of our application are studied using the following three technologies: PDDL-based planning, time-line planning and scheduling, and constraint-based scheduling. The variations address specific aspects of the problem that we believe can impact the performance of the technologies while also representing reasonable abstractions of the real world application. We evaluate the capabilities of each technology and conclude that a constraint-based scheduling approach, specifically a decomposition using constraint programming, provides the most promising results for our application. PDDL-based planning is able to find mostly low quality solutions while the timeline approach was unable to model the full problem without alterations to the solver code, thus moving away from the model-and-solve paradigm. It would be misleading to conclude that constraint programming is "better" than PDDL-based planning in a general sense, both because we have examined a single application and because the approaches make different assumptions about the knowledge one is allowed to embed in a model. Nonetheless, we believe our investigation is valuable for AI planning and scheduling researchers as it highlights these different modelling assumptions and provides insight into avenues for the application of AI planning and scheduling for similar robotics problems. In particular, as constraint programming has not been widely applied to robot planning and scheduling in the literature, our results suggest significant untapped potential in doing so.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {523–590},
numpages = {68}
}

@article{10.5555/3176764.3176776,
author = {Lai, Yong and Liu, Dayou and Yin, Minghao},
title = {New Canonical Representations by Augmenting OBDDs with Conjunctive Decomposition},
year = {2017},
issue_date = {January 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {58},
number = {1},
issn = {1076-9757},
abstract = {We identify two families of canonical knowledge compilation languages. Both families augment ROBDD with conjunctive decomposition bounded by an integer i ranging from 0 to ∞. In the former, the decomposition is finest and the decision respects a chain C of variables, while both the decomposition and decision of the latter respect a tree τ of variables. In particular, these two families cover three existing languages ROBDD, ROBDD with as many implied literals as possible, and AND/OR BDD. We demonstrate that each language in the first family is complete, while each one in the second family is incomplete with expressivity that does not decrease with incremental i. We also demonstrate that the succinctness does not decrease from the i-th language in the second family to the i-th language in the first family, and then to the (i+1)-th language in the first family. For the operating efficiency, on the one hand, we show that the two families of languages support a rich class of tractable logical operations, and particularly the tractability of each language in the second family is not less than that of ROBDD; and on the other hand, we introduce a new time efficiency criterion called rapidity which reflects the idea that exponential operations may be preferable if the language can be exponentially more succinct, and we demonstrate that the rapidity of each operation does not decrease from the i-th language in the second family to the i-th language in the first family, and then to the (i + 1)-th language in the first family. Furthermore, we develop a compiler for the last language in the first family (i = ∞). Empirical results show that the compiler significantly advances the compiling efficiency of canonical representations. In fact, its compiling efficiency is comparable with that of the state-of-the-art compilers of non-canonical representations. We also provide a compiler for the i-th language in the first family by translating the last language in the first family into the i-th language (i < ∞). Empirical results show that we can sometimes use the i-th language instead of the last language without any obvious loss of space efficiency.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {453–521},
numpages = {69}
}

@article{10.5555/3176764.3176775,
author = {Aleksandrowicz, Gadi and Chockler, Hana and Halpern, Joseph Y. and Ivrii, Alexander},
title = {The Computational Complexity of Structure-Based Causality},
year = {2017},
issue_date = {January 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {58},
number = {1},
issn = {1076-9757},
abstract = {Halpern and Pearl introduced a definition of actual causality; Eiter and Lukasiewicz showed that computing whether X = x is a cause of Y = y is NP-complete in binary models (where all variables can take on only two values) and Σ2P-complete in general models. In the final version of their paper, Halpern and Pearl slightly modified the definition of actual cause, in order to deal with problems pointed out by Hopkins and Pearl. As we show, this modification has a nontrivial impact on the complexity of computing whether X = x is a cause of Y = y. To characterize the complexity, a new family DkP, k = 1, 2, 3, . . ., of complexity classes is introduced, which generalizes the class DP introduced by Papadimitriou and Yannakakis (DP is just D1P). We show that the complexity of computing causality under the updated definition is D2P-complete.Chockler and Halpern extended the definition of causality by introducing notions of responsibility and blame, and characterized the complexity of determining the degree of responsibility and blame using the original definition of causality. Here, we completely characterize the complexity using the updated definition of causality. In contrast to the results on causality, we show that moving to the updated definition does not result in a difference in the complexity of computing responsibility and blame.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {431–451},
numpages = {21}
}

@article{10.5555/3176764.3176774,
author = {Ghosh, Supriyo and Varakantham, Pradeep and Adulyasak, Yossiri and Jaillet, Patrick},
title = {Dynamic Repositioning to Reduce Lost Demand in Bike Sharing Systems},
year = {2017},
issue_date = {January 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {58},
number = {1},
issn = {1076-9757},
abstract = {Bike Sharing Systems (BSSs) are widely adopted in major cities of the world due to concerns associated with extensive private vehicle usage, namely, increased carbon emissions, traffic congestion and usage of non-renewable resources. In a BSS, base stations are strategically placed throughout a city and each station is stocked with a pre-determined number of bikes at the beginning of the day. Customers hire the bikes from one station and return them at another station. Due to unpredictable movements of customers hiring bikes, there is either congestion (more than required) or starvation (fewer than required) of bikes at base stations. Existing data has shown that congestion/starvation is a common phenomenon that leads to a large number of unsatisfied customers resulting in a significant loss in customer demand. In order to tackle this problem, we propose an optimisation formulation to reposition bikes using vehicles while also considering the routes for vehicles and future expected demand. Furthermore, we contribute two approaches that rely on decomposability in the problem (bike repositioning and vehicle routing) and aggregation of base stations to reduce the computation time significantly. Finally, we demonstrate the utility of our approach by comparing against two benchmark approaches on two real-world data sets of bike sharing systems. These approaches are evaluated using a simulation where the movements of customers are generated from real-world data sets.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {387–430},
numpages = {44}
}

@article{10.5555/3176764.3176773,
author = {Bodirsky, Manuel and Jonsson, Peter},
title = {A Model-Theoretic View on Qualitative Constraint Reasoning},
year = {2017},
issue_date = {January 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {58},
number = {1},
issn = {1076-9757},
abstract = {Qualitative reasoning formalisms are an active research topic in artificial intelligence. In this survey we present a model-theoretic perspective on qualitative constraint reasoning and explain some of the basic concepts and results in an accessible way. In particular, we discuss the significance of ω-categoricity for qualitative reasoning, of primitive positive interpretations for complexity analysis, and of Datalog as a unifying language for describing local consistency algorithms.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {339–385},
numpages = {47}
}

@article{10.5555/3176764.3176772,
author = {Erd\'{e}lyi, G\'{a}bor and Lackner, Martin and Pfandler, Andreas},
title = {Computational Aspects of Nearly Single-Peaked Electorates},
year = {2017},
issue_date = {January 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {58},
number = {1},
issn = {1076-9757},
abstract = {Manipulation, bribery, and control are well-studied ways of changing the outcome of an election. Many voting rules are, in the general case, computationally resistant to some of these manipulative actions. However when restricted to single-peaked electorates, these rules suddenly become easy to manipulate. Recently, Faliszewski, Hemaspaandra, and Hemaspaandra studied the computational complexity of strategic behavior in nearly single-peaked electorates. These are electorates that are not single-peaked but close to it according to some distance measure.In this paper we introduce several new distance measures regarding single-peakedness. We prove that determining whether a given profile is nearly single-peaked is NP-complete in many cases. For one case we present a polynomial-time algorithm. In case the singlepeaked axis is given, we show that determining the distance is always possible in polynomial time. Furthermore, we explore the relations between the new notions introduced in this paper and existing notions from the literature.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {297–337},
numpages = {41}
}

@article{10.5555/3176764.3176771,
author = {Wang, Yiyuan and Cai, Shaowei and Yin, Minghao},
title = {Local Search for Minimum Weight Dominating Set with Two-Level Configuration Checking and Frequency Based Scoring Function},
year = {2017},
issue_date = {January 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {58},
number = {1},
issn = {1076-9757},
abstract = {The Minimum Weight Dominating Set (MWDS) problem is an important generalization of the Minimum Dominating Set (MDS) problem with extensive applications. This paper proposes a new local search algorithm for the MWDS problem, which is based on two new ideas. The first idea is a heuristic called two-level configuration checking (CC2), which is a new variant of a recent powerful configuration checking strategy (CC) for effectively avoiding the recent search paths. The second idea is a novel scoring function based on the frequency of being uncovered of vertices. Our algorithm is called CC2FS, according to the names of the two ideas. The experimental results show that, CC2FS performs much better than some state-of-the-art algorithms in terms of solution quality on a broad range of MWDS benchmarks.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {267–295},
numpages = {29}
}

@article{10.5555/3176764.3176770,
author = {Ye, Nan and Somani, Adhiraj and Hsu, David and Lee, Wee Sun},
title = {DESPOT: Online POMDP Planning with Regularization},
year = {2017},
issue_date = {January 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {58},
number = {1},
issn = {1076-9757},
abstract = {The partially observable Markov decision process (POMDP) provides a principled general framework for planning under uncertainty, but solving POMDPs optimally is computationally intractable, due to the "curse of dimensionality" and the "curse of history". To overcome these challenges, we introduce the Determinized Sparse Partially Observable Tree (DESPOT), a sparse approximation of the standard belief tree, for online planning under uncertainty. A DESPOT focuses online planning on a set of randomly sampled scenarios and compactly captures the "execution" of all policies under these scenarios. We show that the best policy obtained from a DESPOT is near-optimal, with a regret bound that depends on the representation size of the optimal policy. Leveraging this result, we give an anytime online planning algorithm, which searches a DESPOT for a policy that optimizes a regularized objective function. Regularization balances the estimated value of a policy under the sampled scenarios and the policy size, thus avoiding overfitting. The algorithm demonstrates strong experimental results, compared with some of the best online POMDP algorithms available. It has also been incorporated into an autonomous driving system for real-time vehicle control. The source code for the algorithm is available online.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {231–266},
numpages = {36}
}

@article{10.5555/3176764.3176769,
author = {Cussens, James and J\'{a}rvisalo, Matti and Korhonen, Janne H. and Bartlett, Mark},
title = {Bayesian Network Structure Learning with Integer Programming: Polytopes, Facets and Complexity},
year = {2017},
issue_date = {January 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {58},
number = {1},
issn = {1076-9757},
abstract = {The challenging task of learning structures of probabilistic graphical models is an important problem within modern AI research. Recent years have witnessed several major algorithmic advances in structure learning for Bayesian networks--arguably the most central class of graphical models--especially in what is known as the score-based setting. A successful generic approach to optimal Bayesian network structure learning (BNSL), based on integer programming (IP), is implemented in the gobnilp system. Despite the recent algorithmic advances, current understanding of foundational aspects underlying the IP based approach to BNSL is still somewhat lacking. Understanding fundamental aspects of cutting planes and the related separation problem is important not only from a purely theoretical perspective, but also since it holds out the promise of further improving the efficiency of state-of-the-art approaches to solving BNSL exactly. In this paper, we make several theoretical contributions towards these goals: (i) we study the computational complexity of the separation problem, proving that the problem is NP-hard; (ii) we formalise and analyse the relationship between three key polytopes underlying the IP-based approach to BNSL; (iii) we study the facets of the three polytopes both from the theoretical and practical perspective, providing, via exhaustive computation, a complete enumeration of facets for low-dimensional family-variable polytopes; and, furthermore, (iv) we establish a tight connection of the BNSL problem to the acyclic subgraph problem.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {185–229},
numpages = {45}
}

@article{10.5555/3176764.3176768,
author = {Kurata, Ryoji and Hamada, Naoto and Iwasaki, Atsushi and Yokoo, Makoto},
title = {Controlled School Choice with Soft Bounds and Overlapping Types},
year = {2017},
issue_date = {January 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {58},
number = {1},
issn = {1076-9757},
abstract = {School choice programs are implemented to give students/parents an opportunity to choose the public school the students attend. Controlled school choice programs need to provide choices for students/parents while maintaining distributional constraints on the composition of students, typically in terms of socioeconomic status. Previous works show that setting soft-bounds, which exibly change the priorities of students based on their types, is more appropriate than setting hard-bounds, which strictly limit the number of accepted students for each type. We consider a case where soft-bounds are imposed and one student can belong to multiple types, e.g., "financially-distressed" and "minority" types. We first show that when we apply a model that is a straightforward extension of an existing model for disjoint types, there is a chance that no stable matching exists. Thus we propose an alternative model and an alternative stability definition, where a school has reserved seats for each type. We show that a stable matching is guaranteed to exist in this model and develop a mechanism called Deferred Acceptance for Overlapping Types (DA-OT). The DA-OT mechanism is strategy-proof and obtains the student-optimal matching within all stable matchings. Furthermore, we introduce an extended model that can handle both type-specific ceilings and oors and propose a extended mechanism DA-OT* to handle the extended model. Computer simulation results illustrate that DA-OT outperforms an artificial cap mechanism where we set a hard-bound for each type in each school. DA-OT* can achieve stability in the extended model without sacrificing students' welfare.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {153–184},
numpages = {32}
}

@article{10.1613/jair.5282,
author = {Caragiannis, Ioannis and Nath, Swaprava and Procaccia, Ariel D. and Shah, Nisarg},
title = {Subset Selection via Implicit Utilitarian Voting},
year = {2017},
issue_date = {January 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {58},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.5282},
doi = {10.1613/jair.5282},
abstract = {How should one aggregate ordinal preferences expressed by voters into a measurably superior social choice? A well-established approach -- which we refer to as implicit utilitarian voting -- assumes that voters have latent utility functions that induce the reported rankings, and seeks voting rules that approximately maximize utilitarian social welfare. We extend this approach to the design of rules that select a subset of alternatives. We derive analytical bounds on the performance of optimal (deterministic as well as randomized) rules in terms of two measures, distortion and regret. Empirical results show that regret-based rules are more compelling than distortion-based rules, leading us to focus on developing a scalable implementation for the optimal (deterministic) regret-based rule. Our methods underlie the design and implementation of RoboVote.org, a not-for-profit website that helps users make group decisions via AI-driven voting methods.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {123–152},
numpages = {30}
}

@article{10.1613/jair.5249,
author = {Asai, Masataro and Fukunaga, Alex},
title = {Tie-Breaking Strategies for Cost-Optimal Best First Search},
year = {2017},
issue_date = {January 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {58},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.5249},
doi = {10.1613/jair.5249},
abstract = {Best-first search algorithms such as A* need to apply tie-breaking strategies in order to decide which node to expand when multiple search nodes have the same evaluation score. We investigate and improve tie-breaking strategies for cost-optimal search using A*. We first experimentally analyze the performance of common tie-breaking strategies that break ties according to the heuristic value of the nodes. We find that the tie-breaking strategy has a significant impact on search algorithm performance when there are 0-cost operators that induce large plateau regions in the search space. Based on this, we develop two new classes of tie-breaking strategies. We first propose a depth diversification strategy which breaks ties according to the distance from the entrance to the plateau, and then show that this new strategy significantly outperforms standard strategies on domains with 0-cost actions. Next, we propose a new framework for interpreting A* search as a series of satisficing searches within plateaus consisting of nodes with the same f-cost. Based on this framework, we investigate a second, new class of tie-breaking strategy, a multi-heuristic tie-breaking strategy which embeds inadmissible, distance-to-go variations of various heuristics within an admissible search. This is shown to further improve the performance in combination with the depth metric.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {67–121},
numpages = {55}
}

@article{10.1613/jair.5222,
author = {Guti\'{e}rrez-Basulto, V\'{\i}ctor and Jung, Jean Christoph and Lutz, Carsten and Schr\"{o}der, Lutz},
title = {Probabilistic Description Logics for Subjective Uncertainty},
year = {2017},
issue_date = {January 2017},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {58},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.5222},
doi = {10.1613/jair.5222},
abstract = {We propose a family of probabilistic description logics (DLs) that are derived in a principled way from Halpern's probabilistic first-order logic. The resulting probabilistic DLs have a two-dimensional semantics similar to temporal DLs and are well-suited for representing subjective probabilities. We carry out a detailed study of reasoning in the new family of logics, concentrating on probabilistic extensions of the DLs ALC and EL, and showing that the complexity ranges from PTime via ExpTime and 2ExpTime to undecidable.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {1–66},
numpages = {66}
}

@article{10.5555/3176748.3176763,
author = {Ramchurn, Sarvapali D. and Huynh, Trung Dong and Wu, Feng and Ikuno, Yuki and Flann, Jack and Moreau, Luc and Fischer, Joel E. and Jiang, Wenchao and Rodden, Tom and Simpson, Edwin and Reece, Steven and Roberts, Stephen and Jennings, Nicholas R.},
title = {A Disaster Response System Based on Human-Agent Collectives},
year = {2016},
issue_date = {September 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {57},
number = {1},
issn = {1076-9757},
abstract = {Major natural or man-made disasters such as Hurricane Katrina or the 9/11 terror attacks pose significant challenges for emergency responders. First, they have to develop an understanding of the unfolding event either using their own resources or through third-parties such as the local population and agencies. Second, based on the information gathered, they need to deploy their teams in a flexible manner, ensuring that each team performs tasks in the most effective way. Third, given the dynamic nature of a disaster space, and the uncertainties involved in performing rescue missions, information about the disaster space and the actors within it needs to be managed to ensure that responders are always acting on up-to-date and trusted information. Against this background, this paper proposes a novel disaster response system called HAC-ER. Thus HAC-ER interweaves humans and agents, both robotic and software, in social relationships that augment their individual and collective capabilities. To design HAC-ER, we involved end-users including both experts and volunteers in a several participatory design workshops, lab studies, and field trials of increasingly advanced prototypes of individual components of HAC-ER as well as the overall system. This process generated a number of new quantitative and qualitative results but also raised a number of new research questions. HAC-ER thus demonstrates how such Human-Agent Collectives (HACs) can address key challenges in disaster response. Specifically, we show how HAC-ER utilises crowd-sourcing combined with machine learning to obtain most important situational awareness from large streams of reports posted by members of the public and trusted organisations. We then show how this information can inform human-agent teams in coordinating multi-UAV deployments, as well as task planning for responders on the ground. Finally, HAC-ER incorporates an infrastructure and the associated intelligence for tracking and utilising the provenance of information shared across the entire system to ensure its accountability. We individually validate each of these elements of HAC-ER and show how they perform against standard (non-HAC) baselines and also elaborate on the evaluation of the overall system.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {661–708},
numpages = {48}
}

@article{10.5555/3176748.3176762,
author = {Grinshpoun, Tal and Tassa, Tamir},
title = {P-SyncBB: A Privacy Preserving Branch and Bound DCOP Algorithm},
year = {2016},
issue_date = {September 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {57},
number = {1},
issn = {1076-9757},
abstract = {Distributed constraint optimization problems enable the representation of many combinatorial problems that are distributed by nature. An important motivation for such problems is to preserve the privacy of the participating agents during the solving process. The present paper introduces a novel privacy-preserving branch and bound algorithm for this purpose. The proposed algorithm, P-SyncBB, preserves constraint, topology and decision privacy. The algorithm requires secure solutions to several multi-party computation problems. Consequently, appropriate novel secure protocols are devised and analyzed. An extensive experimental evaluation on different benchmarks, problem sizes, and constraint densities shows that P-SyncBB exhibits superior performance to other privacy-preserving complete DCOP algorithms.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {621–660},
numpages = {40}
}

@article{10.5555/3176748.3176761,
author = {Lev, Omer and Rosenschein, Jeffrey S.},
title = {Convergence of Iterative Scoring Rules},
year = {2016},
issue_date = {September 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {57},
number = {1},
issn = {1076-9757},
abstract = {In multiagent systems, social choice functions can help aggregate the distinct preferences that agents have over alternatives, enabling them to settle on a single choice. Despite the basic manipulability of all reasonable voting systems, it would still be desirable to find ways to reach plausible outcomes, which are stable states, i.e., a situation where no agent would wish to change its vote. One possibility is an iterative process in which, after everyone initially votes, participants may change their votes, one voter at a time. This technique, explored in previous work, converges to a Nash equilibrium when Plurality voting is used, along with a tie-breaking rule that chooses a winner according to a linear order of preferences over candidates.In this paper, we both consider limitations of the iterative voting method, as well as expanding upon it. We demonstrate the significance of tie-breaking rules, showing that no iterative scoring rule converges for all tie-breaking. However, using a restricted tie-breaking rule (such as the linear order rule used in previous work) does not by itself ensure convergence. We prove that in addition to plurality, the veto voting rule converges as well using a linear order tie-breaking rule. However, we show that these two voting rules are the only scoring rules that converge, regardless of tie-breaking mechanism.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {573–591},
numpages = {19}
}

@article{10.5555/3176748.3176760,
author = {Shehu, Amarda and Plaku, Erion},
title = {A Survey of Computational Treatments of Biomolecules by Robotics-Inspired Methods Modeling Equilibrium Structure and Dynamics},
year = {2016},
issue_date = {September 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {57},
number = {1},
issn = {1076-9757},
abstract = {More than fifty years of research in molecular biology have demonstrated that the ability of small and large molecules to interact with one another and propagate the cellular processes in the living cell lies in the ability of these molecules to assume and switch between specific structures under physiological conditions. Elucidating biomolecular structure and dynamics at equilibrium is therefore fundamental to furthering our understanding of biological function, molecular mechanisms in the cell, our own biology, disease, and disease treatments. By now, there is a wealth of methods designed to elucidate biomolecular structure and dynamics contributed from diverse scientific communities. In this survey, we focus on recent methods contributed from the Robotics community that promise to address outstanding challenges regarding the disparate length and time scales that characterize dynamic molecular processes in the cell. In particular, we survey robotics-inspired methods designed to obtain efficient representations of structure spaces of molecules in isolation or in assemblies for the purpose of characterizing equilibrium structure and dynamics. While an exhaustive review is an impossible endeavor, this survey balances the description of important algorithmic contributions with a critical discussion of outstanding computational challenges. The objective is to spur further research to address outstanding challenges in modeling equilibrium biomolecular structure and dynamics.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {509–572},
numpages = {64}
}

@article{10.5555/3176748.3176759,
author = {G\"{u}nay, Akin and Liu, Yang and Zhang, Jie},
title = {PROMOCA: Probabilistic Modeling and Analysis of Agents in Commitment Protocols},
year = {2016},
issue_date = {September 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {57},
number = {1},
issn = {1076-9757},
abstract = {Social commitment protocols regulate interactions of agents in multiagent systems. Several methods have been developed to analyze properties of commitment protocols. However, analysis of an agent's behavior in a commitment protocol, which should take into account the agent's goals and beliefs, has received less attention. In this paper we present ProMoca framework to address this issue. Firstly, we develop an expressive formal language to model agents with respect to their commitments. Our language provides dedicated elements to define commitment protocols, and model agents in terms of their goals, behaviors, and beliefs. Furthermore, our language provides probabilistic and non-deterministic elements to model uncertainty in agents' beliefs. Secondly, we identify two essential properties of an agent with respect to a commitment protocol, namely compliance and goal satisfaction. We formalize these properties using a probabilistic variant of linear temporal logic. Thirdly, we adapt a probabilistic model checking algorithm to automatically analyze compliance and goal satisfaction properties. Finally, we present empirical results about efficiency and scalability of ProMoca.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {465–508},
numpages = {44}
}

@article{10.5555/3176748.3176758,
author = {Malapert, Arnaud and R\'{e}gin, Jean-Charles and Rezgui, Mohamed},
title = {Embarrassingly Parallel Search in Constraint Programming},
year = {2016},
issue_date = {September 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {57},
number = {1},
issn = {1076-9757},
abstract = {We introduce an Embarrassingly Parallel Search (EPS) method for solving constraint problems in parallel, and we show that this method matches or even outperforms state-of-the-art algorithms on a number of problems using various computing infrastructures. EPS is a simple method in which a master decomposes the problem into many disjoint subproblems which are then solved independently by workers. Our approach has three advantages: it is an efficient method; it involves almost no communication or synchronization between workers; and its implementation is made easy because the master and the workers rely on an underlying constraint solver, but does not require to modify it. This paper describes the method, and its applications to various constraint problems (satisfaction, enumeration, optimization). We show that our method can be adapted to different underlying solvers (Gecode, Choco2, OR-tools) on different computing infrastructures (multi-core, data centers, cloud computing). The experiments cover unsatisfiable, enumeration and optimization problems, but do not cover first solution search because it makes the results hard to analyze. The same variability can be observed for optimization problems, but at a lesser extent because the optimality proof is required. EPS offers good average performance, and matches or outperforms other available parallel implementations of Gecode as well as some solvers portfolios. Moreover, we perform an in-depth analysis of the various factors that make this approach efficient as well as the anomalies that can occur. Last, we show that the decomposition is a key component for efficiency and load balancing.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {421–464},
numpages = {44}
}

@article{10.5555/3176748.3176757,
author = {Goldberg, Yoav},
title = {A Primer on Neural Network Models for Natural Language Processing},
year = {2016},
issue_date = {September 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {57},
number = {1},
issn = {1076-9757},
abstract = {Over the past few years, neural networks have re-emerged as powerful machine-learning models, yielding state-of-the-art results in fields such as image recognition and speech processing. More recently, neural network models started to be applied also to textual natural language signals, again with very promising results. This tutorial surveys neural network models from the perspective of natural language processing research, in an attempt to bring natural-language researchers up to speed with the neural techniques. The tutorial covers input encoding for natural language tasks, feed-forward networks, convolutional networks, recurrent networks and recursive networks, as well as the computation graph abstraction for automatic gradient computation.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {345–420},
numpages = {76}
}

@article{10.5555/3176748.3176756,
author = {Sturtevant, Nathan R. and Bulitko, Vadim},
title = {Scrubbing during Learning in Real-Time Heuristic Search},
year = {2016},
issue_date = {September 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {57},
number = {1},
issn = {1076-9757},
abstract = {Real-time agent-centered heuristic search is a well-studied problem where an agent that can only reason locally about the world must travel to a goal location using bounded computation and memory at each step. Many algorithms have been proposed for this problem and theoretical results have also been derived for the worst-case performance with simple examples demonstrating worst-case performance in practice. Lower bounds, however, have not been widely studied. In this paper we study best-case performance more generally and derive theoretical lower bounds for reaching the goal using LRTA*, a canonical example of a real-time agent-centered heuristic search algorithm. The results show that, given some reasonable restrictions on the state space and the heuristic function, the number of steps an LRTA*-like algorithm requires to reach the goal will grow asymptotically faster than the state space, resulting in "scrubbing" where the agent repeatedly visits the same state. We then show that while the asymptotic analysis does not hold for more complex realtime search algorithms, experimental results suggest that it is still descriptive of practical performance.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {307–343},
numpages = {37}
}

@article{10.5555/3176748.3176755,
author = {Wilt, Christopher and Ruml, Wheeler},
title = {Effective Heuristics for Suboptimal Best-First Search},
year = {2016},
issue_date = {September 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {57},
number = {1},
issn = {1076-9757},
abstract = {Suboptimal heuristic search algorithms such as weighted A* and greedy best-first search are widely used to solve problems for which guaranteed optimal solutions are too expensive to obtain. These algorithms crucially rely on a heuristic function to guide their search. However, most research on building heuristics addresses optimal solving. In this paper, we illustrate how established wisdom for constructing heuristics for optimal search can fail when considering suboptimal search. We consider the behavior of greedy best-first search in detail and we test several hypotheses for predicting when a heuristic will be effective for it. Our results suggest that a predictive characteristic is a heuristic's goal distance rank correlation (GDRC), a robust measure of whether it orders nodes according to distance to a goal. We demonstrate that GDRC can be used to automatically construct abstraction-based heuristics for greedy best-first search that are more effective than those built by methods oriented toward optimal search. These results reinforce the point that suboptimal search deserves sustained attention and specialized methods of its own.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {273–306},
numpages = {34}
}

@article{10.5555/3176748.3176754,
author = {Steinmetz, Marcel and Hoffmann, J\"{o}rg and Buffet, Olivier},
title = {Goal Probability Analysis in MDP Probabilistic Planning: Exploring and Enhancing the State of the Art},
year = {2016},
issue_date = {September 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {57},
number = {1},
issn = {1076-9757},
abstract = {Unavoidable dead-ends are common in many probabilistic planning problems, e.g. when actions may fail or when operating under resource constraints. An important objective in such settings is MaxProb, determining the maximal probability with which the goal can be reached, and a policy achieving that probability. Yet algorithms for MaxProb probabilistic planning are severely under-explored, to the extent that there is scant evidence of what the empirical state of the art actually is. We close this gap with a comprehensive empirical analysis. We design and explore a large space of heuristic search algorithms, systematizing known algorithms and contributing several new algorithm variants. We consider MaxProb, as well as weaker objectives that we baptize AtLeastProb (requiring to achieve a given goal probabilty threshold) and ApproxProb (requiring to compute the maximum goal probability up to a given accuracy). We explore both the general case where there may be 0-reward cycles, and the practically relevant special case of acyclic planning, such as planning with a limited action-cost budget. We design suitable termination criteria, search algorithm variants, dead-end pruning methods using classical planning heuristics, and node selection strategies. We design a benchmark suite comprising more than 1000 instances adapted from the IPPC, resource-constrained planning, and simulated penetration testing. Our evaluation clarifies the state of the art, characterizes the behavior of a wide range of heuristic search algorithms, and demonstrates significant benefits of our new algorithm variants.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {229–271},
numpages = {43}
}

@article{10.5555/3176748.3176753,
author = {Parisi, Simone and Pirotta, Matteo and Restelli, Marcello},
title = {Multi-Objective Reinforcement Learning through Continuous Pareto Manifold Approximation},
year = {2016},
issue_date = {September 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {57},
number = {1},
issn = {1076-9757},
abstract = {Many real-world control applications, from economics to robotics, are characterized by the presence of multiple conflicting objectives. In these problems, the standard concept of optimality is replaced by Pareto-optimality and the goal is to find the Pareto frontier, a set of solutions representing different compromises among the objectives. Despite recent advances in multi-objective optimization, achieving an accurate representation of the Pareto frontier is still an important challenge. In this paper, we propose a reinforcement learning policy gradient approach to learn a continuous approximation of the Pareto frontier in multi-objective Markov Decision Problems (MOMDPs). Differently from previous policy gradient algorithms, where n optimization routines are executed to have n solutions, our approach performs a single gradient ascent run, generating at each step an improved continuous approximation of the Pareto frontier. The idea is to optimize the parameters of a function defining a manifold in the policy parameters space, so that the corresponding image in the objectives space gets as close as possible to the true Pareto frontier. Besides deriving how to compute and estimate such gradient, we will also discuss the non-trivial issue of defining a metric to assess the quality of the candidate Pareto frontiers. Finally, the properties of the proposed approach are empirically evaluated on two problems, a linear-quadratic Gaussian regulator and a water reservoir control task.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {187–227},
numpages = {41}
}

@article{10.5555/3176748.3176752,
author = {Fern\'{a}ndez, Alejandro Moreo and Esuli, Andrea and Sebastiani, Fabrizio},
title = {Lightweight Random Indexing for Polylingual Text Classification},
year = {2016},
issue_date = {September 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {57},
number = {1},
issn = {1076-9757},
abstract = {Multilingual Text Classification (MLTC) is a text classification task in which documents are written each in one among a set L of natural languages, and in which all documents must be classified under the same classification scheme, irrespective of language. There are two main variants of MLTC, namely Cross-Lingual Text Classification (CLTC) and Polylingual Text Classification (PLTC). In PLTC, which is the focus of this paper, we assume (differently from CLTC) that for each language in L there is a representative set of training documents; PLTC consists of improving the accuracy of each of the |L| monolingual classifiers by also leveraging the training documents written in the other (|L| - 1) languages. The obvious solution, consisting of generating a single polylingual classifier from the juxtaposed monolingual vector spaces, is usually infeasible, since the dimensionality of the resulting vector space is roughly |L| times that of a monolingual one, and is thus often unmanageable. As a response, the use of machine translation tools or multilingual dictionaries has been proposed. However, these resources are not always available, or are not always free to use.One machine-translation-free and dictionary-free method that, to the best of our knowledge, has never been applied to PLTC before, is Random Indexing (RI). We analyse RI in terms of space and time efficiency, and propose a particular configuration of it (that we dub Lightweight Random Indexing - LRI). By running experiments on two well known public benchmarks, Reuters RCV1/RCV2 (a comparable corpus) and JRC-Acquis (a parallel one), we show LRI to outperform (both in terms of effectiveness and efficiency) a number of previously proposed machine-translation-free and dictionary-free PLTC methods that we use as baselines.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {151–185},
numpages = {35}
}

@article{10.5555/3176748.3176751,
author = {Muise, Christian and Beck, J. Christopher and McIlraith, Sheila A.},
title = {Optimal Partial-Order Plan Relaxation via MaxSAT},
year = {2016},
issue_date = {September 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {57},
number = {1},
issn = {1076-9757},
abstract = {Partial-order plans (POPs) are attractive because of their least-commitment nature, which provides enhanced plan flexibility at execution time relative to sequential plans. Current research on automated plan generation focuses on producing sequential plans, despite the appeal of POPs. In this paper we examine POP generation by relaxing or modifying the action orderings of a sequential plan to optimize for plan criteria that promote flexibility. Our approach relies on a novel partial weighted MaxSAT encoding of a sequential plan that supports the minimization of deordering or reordering of actions. Using a similar technique, we further demonstrate how to remove redundant actions from the plan, and how to combine this criterion with the objective of maximizing a POP's flexibility. Our partial weighted MaxSAT encoding allows us to compute a POP from a sequential plan effectively. We compare the efficiency of our approach to previous methods for POP generation via sequential-plan relaxation. Our results show that while an existing heuristic approach consistently produces the optimal deordering of a sequential plan, our approach has greater flexibility when we consider reordering the actions in the plan while also providing a guarantee of optimality. We also investigate and confirm the accuracy of the standard flex metric typically used to predict the true flexibility of a POP as measured by the number of linearizations it represents.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {113–149},
numpages = {37}
}

@article{10.5555/3176748.3176750,
author = {Martiny, Karsten and M\"{o}ller, Ralf},
title = {PDT Logic: A Probabilistic Doxastic Temporal Logic for Reasoning about Beliefs in Multi-Agent Systems},
year = {2016},
issue_date = {September 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {57},
number = {1},
issn = {1076-9757},
abstract = {We present Probabilistic Doxastic Temporal (PDT) Logic, a formalism to represent and reason about probabilistic beliefs and their temporal evolution in multi-agent systems. This formalism enables the quantification of agents' beliefs through probability intervals and incorporates an explicit notion of time. We discuss how over time agents dynamically change their beliefs in facts, temporal rules, and other agents' beliefs with respect to any new information they receive. We introduce an appropriate formal semantics for PDT Logic and show that it is decidable. Alternative options of specifying problems in PDT Logic are possible. For these problem specifications, we develop different satisfiability checking algorithms and provide complexity results for the respective decision problems. The use of probability intervals enables a formal representation of probabilistic knowledge without enforcing (possibly incorrect) exact probability values. By incorporating an explicit notion of time, PDT Logic provides enriched possibilities to represent and reason about temporal relations.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {39–112},
numpages = {74}
}

@article{10.5555/3176748.3176749,
author = {Villa, Simone and Stella, Fabio},
title = {Learning Continuous Time Bayesian Networks in Non-Stationary Domains},
year = {2016},
issue_date = {September 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {57},
number = {1},
issn = {1076-9757},
abstract = {Non-stationary continuous time Bayesian networks are introduced. They allow the parents set of each node to change over continuous time. Three settings are developed for learning non-stationary continuous time Bayesian networks from data: known transition times, known number of epochs and unknown number of epochs. A score function for each setting is derived and the corresponding learning algorithm is developed. A set of numerical experiments on synthetic data is used to compare the effectiveness of non-stationary continuous time Bayesian networks to that of non-stationary dynamic Bayesian networks. Furthermore, the performance achieved by non-stationary continuous time Bayesian networks is compared to that achieved by state-of-the-art algorithms on four real-world datasets, namely drosophila, saccharomyces cerevisiae, songbird and macroeconomics.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {1–37},
numpages = {37}
}

@article{10.5555/3013589.3013608,
author = {Du, Heshan and Alechina, Natasha},
title = {Qualitative Spatial Logics for Buffered Geometries},
year = {2016},
issue_date = {May 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {56},
number = {1},
issn = {1076-9757},
abstract = {This paper describes a series of new qualitative spatial logics for checking consistency of sameAs and partOf matches between spatial objects from different geospatial datasets, especially from crowd-sourced datasets. Since geometries in crowd-sourced data are usually not very accurate or precise, we buffer geometries by a margin of error or a level of tolerance σ ∈ R≥0, and define spatial relations for buffered geometries. The spatial logics formalize the notions of 'buffered equal' (intuitively corresponding to 'possibly sameAs'), 'buffered part of' ('possibly partOf'), 'near' ('possibly connected') and 'far' ('definitely disconnected'). A sound and complete axiomatisation of each logic is provided with respect to models based on metric spaces. For each of the logics, the satisfiability problem is shown to be NP-complete. Finally, we briefl y describe how the logics are used in a system for generating and debugging matches between spatial objects, and report positive experimental evaluation results for the system.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {693–745},
numpages = {53}
}

@article{10.5555/3013589.3013607,
author = {Cenamor, Isabel and De La Rosa, Tom\'{a}s and Fern\'{a}ndez, Fernando},
title = {The IBaCoP Planning System: Instance-Based Configured Portfolios},
year = {2016},
issue_date = {May 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {56},
number = {1},
issn = {1076-9757},
abstract = {Sequential planning portfolios are very powerful in exploiting the complementary strength of different automated planners. The main challenge of a portfolio planner is to define which base planners to run, to assign the running time for each planner and to decide in what order they should be carried out to optimize a planning metric. Portfolio configurations are usually derived empirically from training benchmarks and remain fixed for an evaluation phase. In this work, we create a per-instance configurable portfolio, which is able to adapt itself to every planning task. The proposed system pre-selects a group of candidate planners using a Pareto-dominance filtering approach and then it decides which planners to include and the time assigned according to predictive models. These models estimate whether a base planner will be able to solve the given problem and, if so, how long it will take. We define different portfolio strategies to combine the knowledge generated by the models. The experimental evaluation shows that the resulting portfolios provide an improvement when compared with non-informed strategies. One of the proposed portfolios was the winner of the Sequential Satisficing Track of the International Planning Competition held in 2014.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {657–691},
numpages = {35}
}

@article{10.5555/3013589.3013606,
author = {Deagustini, Cristhian Ariel D. and Mart\'{\i}nez, Mar\'{\i}a Vanina and Falappa, Marcelo A. and Simari, Guillermo R.},
title = {Datalog± Ontology Consolidation},
year = {2016},
issue_date = {May 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {56},
number = {1},
issn = {1076-9757},
abstract = {Knowledge bases in the form of ontologies are receiving increasing attention as they allow to clearly represent both the available knowledge, which includes the knowledge in itself and the constraints imposed to it by the domain or the users. In particular, Datalog± ontologies are attractive because of their property of decidability and the possibility of dealing with the massive amounts of data in real world environments; however, as it is the case with many other ontological languages, their application in collaborative environments often lead to inconsistency related issues. In this paper we introduce the notion of incoherence regarding Datalog± ontologies, in terms of satisfiability of sets of constraints, and show how under specific conditions incoherence leads to inconsistent Datalog± ontologies. The main contribution of this work is a novel approach to restore both consistency and coherence in Datalog± ontologies. The proposed approach is based on kernel contraction and restoration is performed by the application of incision functions that select formulas to delete. Nevertheless, instead of working over minimal incoherent/inconsistent sets encountered in the ontologies, our operators produce incisions over non-minimal structures called clusters. We present a construction for consolidation operators, along with the properties expected to be satisfied by them. Finally, we establish the relation between the construction and the properties by means of a representation theorem. Although this proposal is presented for Datalog± ontologies consolidation, these operators can be applied to other types of ontological languages, such as Description Logics, making them apt to be used in collaborative environments like the Semantic Web.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {613–656},
numpages = {44}
}

@article{10.5555/3013589.3013605,
author = {Aziz, Haris and Cahan, Casey and Gretton, Charles and Kilby, Philip and Mattei, Nicholas and Walsh, Toby},
title = {A Study of Proxies for Shapley Allocations of Transport Costs},
year = {2016},
issue_date = {May 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {56},
number = {1},
issn = {1076-9757},
abstract = {We survey existing rules of thumb, propose novel methods, and comprehensively evaluate a number of solutions to the problem of calculating the cost to serve each location in a single-vehicle transport setting. Cost to serve analysis has applications both strategically and operationally in transportation settings. The problem is formally modeled as the traveling salesperson game (TSG), a cooperative transferable utility game in which agents correspond to locations in a traveling salesperson problem (TSP). The total cost to serve all locations in the TSP is the length of an optimal tour. An allocation divides the total cost among individual locations, thus providing the cost to serve each of them. As one of the most important normative division schemes in cooperative games, the Shapley value gives a principled and fair allocation for a broad variety of games including the TSG. We consider a number of direct and sampling-based procedures for calculating the Shapley value, and prove that approximating the Shapley value of the TSG within a constant factor is NP-hard. Treating the Shapley value as an ideal baseline allocation, we survey six proxies for it that are each relatively easy to compute. Some of these proxies are rules of thumb and some are procedures international delivery companies use(d) as cost allocation methods. We perform an experimental evaluation using synthetic Euclidean games as well as games derived from real-world tours calculated for scenarios involving fast-moving goods; where deliveries are made on a road network every day. We explore several computationally tractable allocation techniques that are good proxies for the Shapley value in problem instances of a size and complexity that is commercially relevant.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {573–611},
numpages = {39}
}

@article{10.5555/3013589.3013604,
author = {Hern\'{a}ndez, Carlos and Baier, Jorge A. and As\'{\i}n, Roberto},
title = {Time-Bounded Best-First Search for Reversible and Non-Reversible Search Graphs},
year = {2016},
issue_date = {May 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {56},
number = {1},
issn = {1076-9757},
abstract = {Time-Bounded A* is a real-time, single-agent, deterministic search algorithm that expands states of a graph in the same order as A* does, but that unlike A* interleaves search and action execution. Known to outperform state-of-the-art real-time search algorithms based on Korf's Learning Real-Time A* (LRTA*) in some benchmarks, it has not been studied in detail and is sometimes not considered as a "true" real-time search algorithm since it fails in non-reversible problems even it the goal is still reachable from the current state. In this paper we propose and study Time-Bounded Best-First Search (TB(BFS)) a straightforward generalization of the time-bounded approach to any best-first search algorithm. Furthermore, we propose Restarting Time-Bounded Weighted A* (TBR (WA*)), an algorithm that deals more adequately with non-reversible search graphs, eliminating "backtracking moves" and incorporating search restarts and heuristic learning. In nonreversible problems we prove that TB(BFS) terminates and we deduce cost bounds for the solutions returned by Time-Bounded Weighted A* (TB(WA*)), an instance of TB(BFS). Furthermore, we prove TBR (WA*), under reasonable conditions, terminates. We evaluate TB(WA) in both grid pathfinding and the 15-puzzle. In addition, we evaluate TBR (WA*) on the racetrack problem. We compare our algorithms to LSS-LRTWA*, a variant of LRTA* that can exploit lookahead search and a weighted heuristic. A general observation is that the performance of both TB(WA*) and TBR (WA*) improves as the weight parameter is increased. In addition, our time-bounded algorithms almost always outperform LSS-LRTWA* by a significant margin.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {547–571},
numpages = {25}
}

@article{10.5555/3013589.3013603,
author = {Venanzi, Matteo and Guiver, John and Kohli, Pushmeet and Jennings, Nicholas R.},
title = {Time-Sensitive Bayesian Information Aggregation for Crowdsourcing Systems},
year = {2016},
issue_date = {May 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {56},
number = {1},
issn = {1076-9757},
abstract = {Many aspects of the design of efficient crowdsourcing processes, such as defining worker's bonuses, fair prices and time limits of the tasks, involve knowledge of the likely duration of the task at hand. In this work we introduce a new time-sensitive Bayesian aggregation method that simultaneously estimates a task's duration and obtains reliable aggregations of crowdsourced judgments. Our method, called BCCTime, uses latent variables to represent the uncertainty about the workers' completion time, the tasks' duration and the workers' accuracy. To relate the quality of a judgment to the time a worker spends on a task, our model assumes that each task is completed within a latent time window within which all workers with a propensity to genuinely attempt the labelling task (i.e., no spammers) are expected to submit their judgments. In contrast, workers with a lower propensity to valid labelling, such as spammers, bots or lazy labellers, are assumed to perform tasks considerably faster or slower than the time required by normal workers. Specifically, we use efficient message-passing Bayesian inference to learn approximate posterior probabilities of (i) the confusion matrix of each worker, (ii) the propensity to valid labelling of each worker, (iii) the unbiased duration of each task and (iv) the true label of each task. Using two real-world public datasets for entity linking tasks, we show that BCCTime produces up to 11% more accurate classifications and up to 100% more informative estimates of a task's duration compared to state-of-the-art methods.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {517–545},
numpages = {29}
}

@article{10.5555/3013589.3013602,
author = {Eiter, Thomas and Fink, Michael and Stepanova, Daria},
title = {Computing Repairs of Inconsistent DL-Programs over EL Ontologies},
year = {2016},
issue_date = {May 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {56},
number = {1},
issn = {1076-9757},
abstract = {Description Logic (DL) ontologies and non-monotonic rules are two prominent Knowledge Representation (KR) formalisms with complementary features that are essential for various applications. Nonmonotonic Description Logic (DL) programs combine these formalisms thus providing support for rule-based reasoning on top of DL ontologies using a well-defined query interface represented by so-called DL-atoms. Unfortunately, interaction of the rules and the ontology may incur inconsistencies such that a DL-program lacks answer sets (i.e., models), and thus yields no information. This issue is addressed by recently defined repair answer sets, for computing which an effective practical algorithm was proposed for DL-LiteA ontologies that reduces a repair computation to constraint matching based on so-called support sets. However, the algorithm exploits particular features of DL-LiteA and can not be readily applied to repairing DL-programs over other prominent DLs like EL. Compared to DL-LiteA, in EL support sets may neither be small nor only few support sets might exist, and completeness of the algorithm may need to be given up when the support information is bounded. We thus provide an approach for computing repairs for DL-programs over EL ontologies based on partial (incomplete) support families. The latter are constructed using datalog query rewriting techniques as well as ontology approximation based on logical difference between EL-terminologies. We show how the maximal size and number of support sets for a given DL-atom can be estimated by analyzing the properties of a support hypergraph, which characterizes a relevant set of TBox axioms needed for query derivation. We present a declarative implementation of the repair approach and experimentally evaluate it on a set of benchmark problems; the promising results witness practical feasibility of our repair approach.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {463–515},
numpages = {53}
}

@article{10.5555/3013589.3013601,
author = {Chen, Xujin and Hu, Xiaodong and Liu, Tie-Yan and Ma, Weidong and Qin, Tao and Tang, Pingzhong and Wang, Changjun and Zheng, Bo},
title = {Efficient Mechanism Design for Online Scheduling},
year = {2016},
issue_date = {May 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {56},
number = {1},
issn = {1076-9757},
abstract = {This paper 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 κ/ln κ + 1-o(1), which holds for unequal-length jobs, where κ 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 (1/(1-ε)2 + o(1))κ/ln κ for unequal-length jobs, where 0 < ε < 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.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {429–461},
numpages = {33}
}

@article{10.5555/3013589.3013600,
author = {Zhang, Xiaowang and Van Den Bussche, Jan and Picalausa, Fran\c{c}ois},
title = {On the Satisfiability Problem for SPARQL Patterns},
year = {2016},
issue_date = {May 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {56},
number = {1},
issn = {1076-9757},
abstract = {The satisfiability problem for SPARQL 1.0 patterns is undecidable in general, since the relational algebra can be emulated using such patterns. The goal of this paper is to delineate the boundary of decidability of satisfiability in terms of the constraints allowed in filter conditions. The classes of constraints considered are bound-constraints, negated bound-constraints, equalities, nonequalities, constant-equalities, and constant-nonequalities. The main result of the paper can be summarized by saying that, as soon as inconsistent filter conditions can be formed, satisfiability is undecidable. The key insight in each case is to find a way to emulate the set difference operation. Undecidability can then be obtained from a known undecidability result for the algebra of binary relations with union, composition, and set difference. When no inconsistent filter conditions can be formed, satisfiability is decidable by syntactic checks on bound variables and on the use of literals. Although the problem is shown to be NP-complete, it is experimentally shown that the checks can be implemented efficiently in practice. The paper also points out that satisfiability for the so-called 'well-designed' patterns can be decided by a check on bound variables and a check for inconsistent filter conditions.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {403–428},
numpages = {26}
}

@article{10.5555/3013589.3013599,
author = {Savicky, Petr and Ku\v{c}era, Petr},
title = {Generating Models of a Matched Formula with a Polynomial Delay},
year = {2016},
issue_date = {May 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {56},
number = {1},
issn = {1076-9757},
abstract = {A matched formula is a CNF formula whose incidence graph admits a matching which matches a distinct variable to every clause. Such a formula is always satisfiable. Matched formulas are used, for example, in the area of parametrized complexity. We prove that the problem of counting the number of the models (satisfying assignments) of a matched formula is #P-complete. On the other hand, we define a class of formulas generalizing the matched formulas and prove that for a formula in this class one can choose in polynomial time a variable suitable for splitting the tree for the search of the models of the formula. As a consequence, the models of a formula from this class, in particular of any matched formula, can be generated sequentially with a delay polynomial in the size of the input. On the other hand, we prove that this task cannot be performed efficiently for linearly satisfiable formulas, which is a generalization of matched formulas containing the class considered above.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {379–402},
numpages = {24}
}

@article{10.5555/3013589.3013598,
author = {Zhuang, Zhiqiang and Wang, Zhe and Wang, Kewen and Qi, Guilin},
title = {DL-Lite Contraction and Revision},
year = {2016},
issue_date = {May 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {56},
number = {1},
issn = {1076-9757},
abstract = {Two essential tasks in managing description logic knowledge bases are eliminating problematic axioms and incorporating newly formed ones. Such elimination and incorporation are formalised as the operations of contraction and revision in belief change. In this paper, we deal with contraction and revision for the DL-Lite family through a model-theoretic approach. Standard description logic semantics yields an infinite number of models for DL-Lite knowledge bases, thus it is difficult to develop algorithms for contraction and revision that involve DL models. The key to our approach is the introduction of an alternative semantics called type semantics which can replace the standard semantics in characterising the standard inference tasks of DL-Lite. Type semantics has several advantages over the standard one. It is more succinct and importantly, with a finite signature, the semantics always yields a finite number of models. We then define model-based contraction and revision functions for DL-Lite knowledge bases under type semantics and provide representation theorems for them. Finally, the finiteness and succinctness of type semantics allow us to develop tractable algorithms for instantiating the functions.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {329–378},
numpages = {50}
}

@article{10.5555/3013589.3013597,
author = {Fickert, Maximilian and Hoffmann, J\"{o}rg and Steinmetz, Marcel},
title = {Combining the Delete Relaxation with Critical-Path Heuristics: A Direct Characterization},
year = {2016},
issue_date = {May 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {56},
number = {1},
issn = {1076-9757},
abstract = {Recent work has shown how to improve delete relaxation heuristics by computing relaxed plans, i. e., the hFF heuristic, in a compiled planning task ΠC which represents a given set C of fact conjunctions explicitly. While this compilation view of such partial delete relaxation is simple and elegant, its meaning with respect to the original planning task is opaque, and the size of ΠC grows exponentially in |C|. We herein provide a direct characterization, without compilation, making explicit how the approach arises from a combination of the delete-relaxation with critical-path heuristics. Designing equations characterizing a novel view on h+ on the one hand, and a generalized version hC of hm on the other hand, we show that h+(ΠC) can be characterized in terms of a combined hC+ equation. This naturally generalizes the standard delete-relaxation framework: understanding that framework as a relaxation over singleton facts as atomic subgoals, one can refine the relaxation by using the conjunctions C as atomic subgoals instead. Thanks to this explicit view, we identify the precise source of complexity in hFF(ΠC), namely maximization of sets of supported atomic subgoals during relaxed plan extraction, which is easy for singleton-fact subgoals but is NP-complete in the general case. Approximating that problem greedily, we obtain a polynomial-time hCFF version of hFF(ΠC), superseding the ΠC compilation, and superseding the modified ΠceC compilation which achieves the same complexity reduction but at an information loss. Experiments on IPC benchmarks show that these theoretical advantages can translate into empirical ones.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {269–327},
numpages = {59}
}

@article{10.5555/3013589.3013596,
author = {Xu, Zenglin and Zhe, Shandian and Qi, Yuan and Yu, Peng},
title = {Association Discovery and Diagnosis of Alzheimer's Disease with Bayesian Multiview Learning},
year = {2016},
issue_date = {May 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {56},
number = {1},
issn = {1076-9757},
abstract = {The analysis and diagnosis of Alzheimer's disease (AD) can be based on genetic variations, e.g., single nucleotide polymorphisms (SNPs) and phenotypic traits, e.g., Magnetic Resonance Imaging (MRI) features. We consider two important and related tasks: i) to select genetic and phenotypical markers for AD diagnosis and ii) to identify associations between genetic and phenotypical data. While previous studies treat these two tasks separately, they are tightly coupled because underlying associations between genetic variations and phenotypical features contain the biological basis for a disease. Here we present a new sparse Bayesian approach for joint association study and disease diagnosis. In this approach, common latent features are extracted from different data sources based on sparse projection matrices and used to predict multiple disease severity levels; in return, the disease status can guide the discovery of relationships between data sources. The sparse projection matrices not only reveal interactions between data sources but also select groups of biomarkers related to the disease. Moreover, to take advantage of the linkage disequilibrium (LD) measuring the non-random association of alleles, we incorporate a graph Laplacian type of prior in the model. To learn the model from data, we develop an efficient variational inference algorithm. Analysis on an imaging genetics dataset for the study of Alzheimer's Disease (AD) indicates that our model identifies biologically meaningful associations between genetic variations and MRI features, and achieves significantly higher accuracy for predicting ordinal AD stages than the competing methods.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {247–268},
numpages = {22}
}

@article{10.5555/3013589.3013595,
author = {Grooters, Diana and Prakken, Henry},
title = {Two Aspects of Relevance in Structured Argumentation: Minimality and Paraconsistency},
year = {2016},
issue_date = {May 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {56},
number = {1},
issn = {1076-9757},
abstract = {This paper studies two issues concerning relevance in structured argumentation in the context of the ASPIC+ framework, arising from the combined use of strict and defeasible inference rules. One issue arises if the strict inference rules correspond to classical logic. A longstanding problem is how the trivialising effect of the classical Ex Falso principle can be avoided while satisfying consistency and closure postulates. In this paper, this problem is solved by disallowing chaining of strict rules, resulting in a variant of the ASPIC+ framework called ASPIC*, and then disallowing the application of strict rules to inconsistent sets of formulas. Thus in effect Rescher & Manor's paraconsistent notion of weak consequence is embedded in ASPIC*.Another issue is minimality of arguments. If arguments can apply defeasible inference rules, then they cannot be required to have subset-minimal premises, since defeasible rules based on more information may well make an argument stronger. In this paper instead minimality is required of applications of strict rules throughout an argument. It is shown that under some plausible assumptions this does not affect the set of conclusions. In addition, circular arguments are in the new ASPIC* framework excluded in a way that satisfies closure and consistency postulates and that generates finitary argumentation frameworks if the knowledge base and set of defeasible rules are finite. For the latter result the exclusion of chaining of strict rules is essential.Finally, the combined results of this paper are shown to be a proper extension of classical-logic argumentation with preferences and defeasible rules.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {197–245},
numpages = {49}
}

@article{10.5555/3013589.3013594,
author = {Kawaguchi, Kenji and Maruyama, Yu and Zheng, Xiaoyu},
title = {Global Continuous Optimization with Error Bound and Fast Convergence},
year = {2016},
issue_date = {May 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {56},
number = {1},
issn = {1076-9757},
abstract = {This paper considers global optimization with a black-box unknown objective function that can be non-convex and non-differentiable. Such a difficult optimization problem arises in many real-world applications, such as parameter tuning in machine learning, engineering design problem, and planning with a complex physics simulator. This paper proposes a new global optimization algorithm, called Locally Oriented Global Optimization (LOGO), to aim for both fast convergence in practice and finite-time error bound in theory. The advantage and usage of the new algorithm are illustrated via theoretical analysis and an experiment conducted with 11 benchmark test functions. Further, we modify the LOGO algorithm to specifically solve a planning problem via policy search with continuous state/action space and long time horizon while maintaining its finite-time error bound. We apply the proposed planning method to accident management of a nuclear power plant. The result of the application study demonstrates the practical utility of our method.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {153–195},
numpages = {43}
}

@article{10.5555/3013589.3013593,
author = {Azimi, Javad and Fern, Xiaoli Z. and Fern, Alan},
title = {Budgeted Optimization with Constrained Experiments},
year = {2016},
issue_date = {May 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {56},
number = {1},
issn = {1076-9757},
abstract = {Motivated by a real-world problem, we study a novel budgeted optimization problem where the goal is to optimize an unknown function f(undefined) given a budget by requesting a sequence of samples from the function. In our setting, however, evaluating the function at precisely specified points is not practically possible due to prohibitive costs. Instead, we can only request constrained experiments. A constrained experiment, denoted by Q, specifies a subset of the input space for the experimenter to sample the function from. The outcome of Q includes a sampled experiment x, and its function output f(x). Importantly, as the constraints of Q become looser, the cost of fulfilling the request decreases, but the uncertainty about the location x increases. Our goal is to manage this trade-off by selecting a set of constrained experiments that best optimize f(undefined) within the budget. We study this problem in two different settings, the non-sequential (or batch) setting where a set of constrained experiments is selected at once, and the sequential setting where experiments are selected one at a time. We evaluate our proposed methods for both settings using synthetic and real functions. The experimental results demonstrate the efficacy of the proposed methods.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {119–152},
numpages = {34}
}

@article{10.5555/3013589.3013592,
author = {Harabor, Daniel and Grastien, Alban and \"{O}z, Dindar and Aksakalli, Vural},
title = {Optimal Any-Angle Pathfinding in Practice},
year = {2016},
issue_date = {May 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {56},
number = {1},
issn = {1076-9757},
abstract = {Any-angle pathfinding is a fundamental problem in robotics and computer games. The goal is to find a shortest path between a pair of points on a grid map such that the path is not artificially constrained to the points of the grid. Prior research has focused on approximate online solutions. A number of exact methods exist but they all require super-linear space and pre-processing time. In this study, we describe Anya: a new and optimal any-angle pathfinding algorithm. Where other works find approximate any-angle paths by searching over individual points from the grid, Anya finds optimal paths by searching over sets of states represented as intervals. Each interval is identified on-the-fly. From each interval Anya selects a single representative point that it uses to compute an admissible cost estimate for the entire set. Anya always returns an optimal path if one exists. Moreover it does so without any offine pre-processing or the introduction of additional memory overheads. In a range of empirical comparisons we show that Anya is competitive with several recent (sub-optimal) online and pre-processing based techniques and is up to an order of magnitude faster than the most common benchmark algorithm, a grid-based implementation of A.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {89–118},
numpages = {30}
}

@article{10.5555/3013589.3013591,
author = {Taghizadeh, Nasrin and Faili, Hesham},
title = {Automatic Wordnet Development for Low-Resource Languages Using Cross-Lingual WSD},
year = {2016},
issue_date = {May 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {56},
number = {1},
issn = {1076-9757},
abstract = {Wordnets are an effective resource for natural language processing and information retrieval, especially for semantic processing and meaning related tasks. So far, wordnets have been constructed for many languages. However, the automatic development of wordnets for low-resource languages has not been well studied. In this paper, an Expectation-Maximization algorithm is used to create high quality and large scale wordnets for poor-resource languages. The proposed method benefits from possessing cross-lingual word sense disambiguation and develops a wordnet by only using a bi-lingual dictionary and a monolingual corpus. The proposed method has been executed with Persian language and the resulting wordnet has been evaluated through several experiments. The results show that the induced wordnet has a precision score of 90% and a recall score of 35%.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {61–87},
numpages = {27}
}

@article{10.5555/3013589.3013590,
author = {Baader, Franz and Bienvenu, Meghyn and Lutz, Carsten and Wolter, Frank},
title = {Query and Predicate Emptiness in Ontology-Based Data Access},
year = {2016},
issue_date = {May 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {56},
number = {1},
issn = {1076-9757},
abstract = {In ontology-based data access (OBDA), database querying is enriched with an ontology that provides domain knowledge and additional vocabulary for query formulation. We identify query emptiness and predicate emptiness as two central reasoning services in this context. Query emptiness asks whether a given query has an empty answer over all databases formulated in a given vocabulary. Predicate emptiness is defined analogously, but quantifies universally over all queries that contain a given predicate. In this paper, we determine the computational complexity of query emptiness and predicate emptiness in the EL, DL-Lite, and ALC-families of description logics, investigate the connection to ontology modules, and perform a practical case study to evaluate the new reasoning services.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {1–59},
numpages = {59}
}

@article{10.5555/3013558.3013588,
author = {Albrecht, Stefano V. and Ramamoorthy, Subramanian},
title = {Exploiting Causality for Selective Belief Filtering in Dynamic Bayesian Networks},
year = {2016},
issue_date = {January 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {55},
number = {1},
issn = {1076-9757},
abstract = {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 noisy observations. This can be a hard problem in complex processes with large state spaces. 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 produces exact belief states under certain assumptions and approximate belief states otherwise, where the approximation error is bounded by the degree of uncertainty in the process. We show empirically, in synthetic processes with varying sizes and degrees of passivity, that PSBF is faster than several alternative methods while achieving competitive accuracy. Furthermore, we demonstrate how passivity occurs naturally in a complex system such as a multi-robot warehouse, and how PSBF can exploit this to accelerate the filtering task.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {1135–1178},
numpages = {44}
}

@article{10.5555/3013558.3013587,
author = {Le, Tuan M. V. and Lauw, Hady W.},
title = {Semantic Visualization with Neighborhood Graph Regularization},
year = {2016},
issue_date = {January 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {55},
number = {1},
issn = {1076-9757},
abstract = {Visualization of high-dimensional data, such as text documents, is useful to map out the similarities among various data points. In the high-dimensional space, documents are commonly represented as bags of words, with dimensionality equal to the vocabulary size. Classical approaches to document visualization directly reduce this into visualizable two or three dimensions. Recent approaches consider an intermediate representation in topic space, between word space and visualization space, which preserves the semantics by topic modeling. While aiming for a good fit between the model parameters and the observed data, previous approaches have not considered the local consistency among data instances. We consider the problem of semantic visualization by jointly modeling topics and visualization on the intrinsic document manifold, modeled using a neighborhood graph. Each document has both a topic distribution and visualization coordinate. Specifically, we propose an unsupervised probabilistic model, called Semafore, which aims to preserve the manifold in the lower-dimensional spaces through a neighborhood regularization framework designed for the semantic visualization task. To validate the efficacy of SEMAFORE, our comprehensive experiments on a number of real-life text datasets of news articles and Web pages show that the proposed methods outperform the state-of-the-art baselines on objective evaluation metrics.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {1091–1133},
numpages = {43}
}

@article{10.5555/3013558.3013586,
author = {Liu, Hanxiao and Ma, Wanli and Yang, Yiming and Carbonell, Jaime},
title = {Learning Concept Graphs from Online Educational Data},
year = {2016},
issue_date = {January 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {55},
number = {1},
issn = {1076-9757},
abstract = {This paper addresses an open challenge in educational data mining, i.e., the problem of automatically mapping online courses from different providers (universities, MOOCs, etc.) onto a universal space of concepts, and predicting latent prerequisite dependencies (directed links) among both concepts and courses. We propose a novel approach for inference within and across course-level and concept-level directed graphs. In the training phase, our system projects partially observed course-level prerequisite links onto directed concept-level links; in the testing phase, the induced concept-level links are used to infer the unknown course-level prerequisite links. Whereas courses may be specific to one institution, concepts are shared across different providers. The bi-directional mappings enable our system to perform interlingua-style transfer learning, e.g. treating the concept graph as the interlingua and transferring the prerequisite relations across universities via the interlingua. Experiments on our newly collected datasets of courses from MIT, Caltech, Princeton and CMU show promising results.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {1059–1090},
numpages = {32}
}

@article{10.5555/3013558.3013585,
author = {Baskaya, Osman and Jurgens, David},
title = {Semi-Supervised Learning with Induced Word Senses for State of the Art Word Sense Disambiguation},
year = {2016},
issue_date = {January 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {55},
number = {1},
issn = {1076-9757},
abstract = {Word Sense Disambiguation (WSD) aims to determine the meaning of a word in context, and successful approaches are known to benefit many applications in Natural Language Processing. Although supervised learning has been shown to provide superior WSD performance, current sense-annotated corpora do not contain a sufficient number of instances per word type to train supervised systems for all words. While unsupervised techniques have been proposed to overcome this data sparsity problem, such techniques have not outperformed supervised methods. In this paper, we propose a new approach to building semi-supervised WSD systems that combines a small amount of sense-annotated data with information from Word Sense Induction, a fully-unsupervised technique that automatically learns the different senses of a word based on how it is used. In three experiments, we show how sense induction models may be effectively combined to ultimately produce high-performance semi-supervised WSD systems that exceed the performance of state-of-the-art supervised WSD techniques trained on the same sense-annotated data. We anticipate that our results and released software will also benefit evaluation practices for sense induction systems and those working in low-resource languages by demonstrating how to quickly produce accurate WSD systems with minimal annotation effort.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {1025–1058},
numpages = {34}
}

@article{10.5555/3013558.3013584,
author = {Guo, Jiang and Che, Wanxiang and Yarowsky, David and Wang, Haifeng and Liu, Ting},
title = {A Distributed Representation-Based Framework for Cross-Lingual Transfer Parsing},
year = {2016},
issue_date = {January 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {55},
number = {1},
issn = {1076-9757},
abstract = {This paper investigates the problem of cross-lingual transfer parsing, aiming at inducing dependency parsers for low-resource languages while using only training data from a resource-rich language (e.g., English). Existing model transfer approaches typically don't include lexical features, which are not transferable across languages. In this paper, we bridge the lexical feature gap by using distributed feature representations and their composition. We provide two algorithms for inducing cross-lingual distributed representations of words, which map vocabularies from two different languages into a common vector space. Consequently, both lexical features and nonlexical features can be used in our model for cross-lingual transfer. Furthermore, our framework is flexible enough to incorporate additional useful features such as cross-lingual word clusters. Our combined contributions achieve an average relative error reduction of 10.9% in labeled attachment score as compared with the delexicalized parser, trained on English universal treebank and transferred to three other languages. It also significantly outperforms state-of-the-art delexicalized models augmented with projected cluster features on identical data. Finally, we demonstrate that our models can be further boosted with minimal supervision (e.g., 100 annotated sentences) from target languages, which is of great significance for practical usage.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {995–1023},
numpages = {29}
}

@article{10.5555/3013558.3013583,
author = {Vulic, Ivan and Moens, Marie-Francine},
title = {Bilingual Distributed Word Representations from Document-Aligned Comparable Data},
year = {2016},
issue_date = {January 2016},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {55},
number = {1},
issn = {1076-9757},
abstract = {We propose a new model for learning bilingual word representations from nonparallel document-aligned data. Following the recent advances in word representation learning, our model learns dense real-valued word vectors, that is, bilingual word embeddings (BWEs). Unlike prior work on inducing BWEs which heavily relied on parallel sentence-aligned corpora and/or readily available translation resources such as dictionaries, the article reveals that BWEs may be learned solely on the basis of document-aligned comparable data without any additional lexical resources nor syntactic information. We present a comparison of our approach with previous state-of-the-art models for learning bilingual word representations from comparable data that rely on the framework of multilingual probabilistic topic modeling (MuPTM), as well as with distributional local context-counting models. We demonstrate the utility of the induced BWEs in two semantic tasks: (1) bilingual lexicon extraction, (2) suggesting word translations in context for polysemous words. Our simple yet effective BWE-based models significantly outperform the MuPTM-based and context-counting representation models from comparable data

license_type: permissive

branch_name: refs/heads/main

extension: bib