text:
13},
issue_date = {October 2013},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {48},
number = {1},
issn = {1076-9757},
abstract = {I prove that an implementation technique for scanning lists in backtracking search algorithms is optimal. The result applies to a simple general framework, which I present: applications include watched literal unit propagation in SAT and a number of examples in constraint satisfaction. Techniques like watched literals are known to be highly space efficient and effective in practice. When implemented in the 'circular' approach described here, these techniques also have optimal run time per branch in big-O terms when amortized across a search tree. This also applies when multiple list elements must be found. The constant factor overhead of the worst case is only 2. Replacing the existing nonoptimal implementation of unit propagation in MiniSat speeds up propagation by 29%, though this is not enough to improve overall run time significantly.},
journal = {J. Artif. Int. Res.},
month = oct,
pages = {231–252},
numpages = {22}
}

@article{10.5555/2591248.2591253,
author = {Robu, Valentin and Gerding, Enrico H. and Stein, Sebastian and Parkes, David C. and Rogers, Alex and Jennings, Nicholas R.},
title = {An Online Mechanism for Multi-Unit Demand and Its Application to Plug-in Hybrid Electric Vehicle Charging},
year = {2013},
issue_date = {October 2013},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {48},
number = {1},
issn = {1076-9757},
abstract = {We develop an online mechanism for the allocation of an expiring resource to a dynamic agent population. Each agent has a non-increasing marginal valuation function for the resource, and an upper limit on the number of units that can be allocated in any period. We propose two versions on a truthful allocation mechanism. Each modifies the decisions of a greedy online assignment algorithm by sometimes cancelling an allocation of resources. One version makes this modification immediately upon an allocation decision while a second waits until the point at which an agent departs the market. Adopting a prior-free framework, we show that the second approach has better worst-case allocative efficiency and is more scalable. On the other hand, the first approach (with immediate cancellation) may be easier in practice because it does not need to reclaim units previously allocated. We consider an application to recharging plug-in hybrid electric vehicles (PHEVs). Using data from a real-world trial of PHEVs in the UK, we demonstrate higher system performance than a fixed price system, performance comparable with a standard, but non-truthful scheduling heuristic, and the ability to support 50% more vehicles at the same fuel cost than a simple randomized policy.},
journal = {J. Artif. Int. Res.},
month = oct,
pages = {175–230},
numpages = {56}
}

@article{10.5555/2591248.2591252,
author = {Cal\`{\i}, Andrea and Gottlob, Georg and Kifer, Michael},
title = {Taming the Infinite Chase: Query Answering under Expressive Relational Constraints},
year = {2013},
issue_date = {October 2013},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {48},
number = {1},
issn = {1076-9757},
abstract = {The chase algorithm is a fundamental tool for query evaluation and for testing query containment under tuple-generating dependencies (TGDs) and equality-generating dependencies (EGDs). So far, most of the research on this topic has focused on cases where the chase procedure terminates. This paper introduces expressive classes of TGDs defined via syntactic restrictions: guarded TGDs (GTGDs) and weakly guarded sets of TGDs (WGT-GDs). For these classes, the chase procedure is not guaranteed to terminate and thus may have an infinite outcome. Nevertheless, we prove that the problems of conjunctive-query answering and query containment under such TGDs are decidable. We provide decision procedures and tight complexity bounds for these problems. Then we show how EGDs can be incorporated into our results by providing conditions under which EGDs do not harmfully interact with TGDs and do not affect the decidability and complexity of query answering. We show applications of the aforesaid classes of constraints to the problem of answering conjunctive queries in F-Logic Lite, an object-oriented ontology language, and in some tractable Description Logics.},
journal = {J. Artif. Int. Res.},
month = oct,
pages = {115–174},
numpages = {60}
}

@article{10.5555/2591248.2591251,
author = {Roijers, Diederik M. and Vamplew, Peter and Whiteson, Shimon and Dazeley, Richard},
title = {A Survey of Multi-Objective Sequential Decision-Making},
year = {2013},
issue_date = {October 2013},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {48},
number = {1},
issn = {1076-9757},
abstract = {Sequential decision-making problems with multiple objectives arise naturally in practice and pose unique challenges for research in decision-theoretic planning and learning, which has largely focused on single-objective settings. This article surveys algorithms designed for sequential decision-making problems with multiple objectives. Though there is a growing body of literature on this subject, little of it makes explicit under what circumstances special methods are needed to solve multi-objective problems. Therefore, we identify three distinct scenarios in which converting such a problem to a single-objective one is impossible, infeasible, or undesirable. Furthermore, we propose a taxonomy that classifies multi-objective methods according to the applicable scenario, the nature of the scalarization function (which projects multi-objective values to scalar ones), and the type of policies considered. We show how these factors determine the nature of an optimal solution, which can be a single policy, a convex hull, or a Pareto front. Using this taxonomy, we survey the literature on multi-objective methods for planning and learning. Finally, we discuss key applications of such methods and outline opportunities for future work.},
journal = {J. Artif. Int. Res.},
month = oct,
pages = {67–113},
numpages = {47}
}

@article{10.5555/2591248.2591250,
author = {Yuan, Changhe and Malone, Brandon},
title = {Learning Optimal Bayesian Networks: A Shortest Path Perspective},
year = {2013},
issue_date = {October 2013},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {48},
number = {1},
issn = {1076-9757},
abstract = {In this paper, learning a Bayesian network structure that optimizes a scoring function for a given dataset is viewed as a shortest path problem in an implicit state-space search graph. This perspective highlights the importance of two research issues: the development of search strategies for solving the shortest path problem, and the design of heuristic functions for guiding the search. This paper introduces several techniques for addressing the issues. One is an A* search algorithm that learns an optimal Bayesian network structure by only searching the most promising part of the solution space. The others are mainly two heuristic functions. The first heuristic function represents a simple relaxation of the acyclicity constraint of a Bayesian network. Although admissible and consistent, the heuristic may introduce too much relaxation and result in a loose bound. The second heuristic function reduces the amount of relaxation by avoiding directed cycles within some groups of variables. Empirical results show that these methods constitute a promising approach to learning optimal Bayesian network structures.},
journal = {J. Artif. Int. Res.},
month = oct,
pages = {23–65},
numpages = {43}
}

@article{10.5555/2591248.2591249,
author = {Alabbas, Maytham and Ramsay, Allan},
title = {Natural Language Inference for Arabic Using Extended Tree Edit Distance with Subtrees},
year = {2013},
issue_date = {October 2013},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {48},
number = {1},
issn = {1076-9757},
abstract = {Many natural language processing (NLP) applications require the computation of similarities between pairs of syntactic or semantic trees. Many researchers have used tree edit distance for this task, but this technique suffers from the drawback that it deals with single node operations only. We have extended the standard tree edit distance algorithm to deal with subtree transformation operations as well as single nodes. The extended algorithm with subtree operations, TED+ST, is more effective and flexible than the standard algorithm, especially for applications that pay attention to relations among nodes (e.g. in linguistic trees, deleting a modifier subtree should be cheaper than the sum of deleting its components individually). We describe the use of TED+ST for checking entailment between two Arabic text snippets. The preliminary results of using TED+ST were encouraging when compared with two string-based approaches and with the standard algorithm.},
journal = {J. Artif. Int. Res.},
month = oct,
pages = {1–22},
numpages = {22}
}

@article{10.5555/2566972.2566993,
author = {Hodosh, Micah and Young, Peter and Hockenmaier, Julia},
title = {Framing Image Description as a Ranking Task: Data, Models and Evaluation Metrics},
year = {2013},
issue_date = {May 2013},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {47},
number = {1},
issn = {1076-9757},
abstract = {The ability to associate images with natural language sentences that describe what is depicted in them is a hallmark of image understanding, and a prerequisite for applications such as sentence-based image search. In analogy to image search, we propose to frame sentence-based image annotation as the task of ranking a given pool of captions. We introduce a new benchmark collection for sentence-based image description and search, consisting of 8,000 images that are each paired with five different captions which provide clear descriptions of the salient entities and events. We introduce a number of systems that perform quite well on this task, even though they are only based on features that can be obtained with minimal supervision. Our results clearly indicate the importance of training on multiple captions per image, and of capturing syntactic (word order-based) and semantic features of these captions. We also perform an in-depth comparison of human and automatic evaluation metrics for this task, and propose strategies for collecting human judgments cheaply and on a very large scale, allowing us to augment our collection with additional relevance judgments of which captions describe which image. Our analysis shows that metrics that consider the ranked list of results for each query image or sentence are significantly more robust than metrics that are based on a single response per query. Moreover, our study suggests that the evaluation of ranking-based image description systems may be fully automated.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {853–899},
numpages = {47}
}

@article{10.5555/2566972.2566992,
author = {Mosurovic, Milenko and Krdzavac, Nenad and Graves, Henson and Zakharyaschev, Michael},
title = {A Decidable Extension of SROIQ with Complex Role Chains and Unions},
year = {2013},
issue_date = {May 2013},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {47},
number = {1},
issn = {1076-9757},
abstract = {We design a decidable extension of the description logic SROIQ underlying the Web Ontology Language OWL2. The new logic, called SR+OIQ, supports a controlled use of role axioms whose right-hand side may contain role chains or role unions. We give a tableau algorithm for checking concept satisfiability with respect to SR+OIQ ontologies and prove its soundness, completeness and termination.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {809–851},
numpages = {43}
}

@article{10.5555/2566972.2566991,
author = {Grau, Bernardo Cuenca and Horrocks, Ian and Kr\"{o}tzsch, Markus and Kupke, Clemens and Magka, Despoina and Motik, Boris and Wang, Zhe},
title = {Acyclicity Notions for Existential Rules and Their Application to Query Answering in Ontologies},
year = {2013},
issue_date = {May 2013},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {47},
number = {1},
issn = {1076-9757},
abstract = {Answering conjunctive queries (CQs) over a set of facts extended with existential rules is a prominent problem in knowledge representation and databases. This problem can be solved using the chase algorithm, which extends the given set of facts with fresh facts in order to satisfy the rules. If the chase terminates, then CQs can be evaluated directly in the resulting set of facts. The chase, however, does not terminate necessarily, and checking whether the chase terminates on a given set of rules and facts is undecidable. Numerous acyclicity notions were proposed as sufficient conditions for chase termination. In this paper, we present two new acyclicity notions called model-faithful acyclicity (MFA) and model-summarising acyclicity (MSA). Furthermore, we investigate the landscape of the known acyclicity notions and establish a complete taxonomy of all notions known to us. Finally, we show that MFA and MSA generalise most of these notions.Existential rules are closely related to the Horn fragments of the OWL 2 ontology language; furthermore, several prominent OWL 2 reasoners implement CQ answering by using the chase to materialise all relevant facts. In order to avoid termination problems, many of these systems handle only the OWL 2 RL profile of OWL 2; furthermore, some systems go beyond OWL 2 RL, but without any termination guarantees. In this paper we also investigate whether various acyclicity notions can provide a principled and practical solution to these problems. On the theoretical side, we show that query answering for acyclic ontologies is of lower complexity than for general ontologies. On the practical side, we show that many of the commonly used OWL 2 ontologies are MSA, and that the number of facts obtained by materialisation is not too large. Our results thus suggest that principled development of materialisation-based OWL 2 reasoners is practically feasible.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {741–808},
numpages = {68}
}

@article{10.5555/2566972.2566990,
author = {Burns, Ethan and Ruml, Wheeler and Do, Minh B.},
title = {Heuristic Search When Time Matters},
year = {2013},
issue_date = {May 2013},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {47},
number = {1},
issn = {1076-9757},
abstract = {In many applications of shortest-path algorithms, it is impractical to find a provably optimal solution; one can only hope to achieve an appropriate balance between search time and solution cost that respects the user's preferences. Preferences come in many forms; we consider utility functions that linearly trade-off search time and solution cost. Many natural utility functions can be expressed in this form. For example, when solution cost represents the makespan of a plan, equally weighting search time and plan makespan minimizes the time from the arrival of a goal until it is achieved. Current state-of-theart approaches to optimizing utility functions rely on anytime algorithms, and the use of extensive training data to compute a termination policy. We propose a more direct approach, called Bugsy, that incorporates the utility function directly into the search, obviating the need for a separate termination policy. We describe a new method based on off-line parameter tuning and a novel benchmark domain for planning under time pressure based on platform-style video games. We then present what we believe to be the first empirical study of applying anytime monitoring to heuristic search, and we compare it with our proposals. Our results suggest that the parameter tuning technique can give the best performance if a representative set of training instances is available. If not, then Bugsy is the algorithm of choice, as it performs well and does not require any off-line training. This work extends the tradition of research on metareasoning for search by illustrating the benefits of embedding lightweight reasoning about time into the search algorithm itself.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {697–740},
numpages = {44}
}

@article{10.5555/2566972.2566989,
author = {L\'{e}aut\'{e}, Thomas and Faltings, Boi},
title = {Protecting Privacy through Distributed Computation in Multi-Agent Decision Making},
year = {2013},
issue_date = {May 2013},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {47},
number = {1},
issn = {1076-9757},
abstract = {As large-scale theft of data from corporate servers is becoming increasingly common, it becomes interesting to examine alternatives to the paradigm of centralizing sensitive data into large databases. Instead, one could use cryptography and distributed computation so that sensitive data can be supplied and processed in encrypted form, and only the final result is made known. In this paper, we examine how such a paradigm can be used to implement constraint satisfaction, a technique that can solve a broad class of AI problems such as resource allocation, planning, scheduling, and diagnosis. Most previous work on privacy in constraint satisfaction only attempted to protect specific types of information, in particular the feasibility of particular combinations of decisions. We formalize and extend these restricted notions of privacy by introducing four types of private information, including the feasibility of decisions and the final decisions made, but also the identities of the participants and the topology of the problem. We present distributed algorithms that allow computing solutions to constraint satisfaction problems while maintaining these four types of privacy. We formally prove the privacy properties of these algorithms, and show experiments that compare their respective performance on benchmark problems.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {649–695},
numpages = {47}
}

@article{10.5555/2566972.2566988,
author = {Grinshpoun, Tal and Grubshtein, Alon and Zivan, Roie and Netzer, Arnon and Meisels, Amnon},
title = {Asymmetric Distributed Constraint Optimization Problems},
year = {2013},
issue_date = {May 2013},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {47},
number = {1},
issn = {1076-9757},
abstract = {Distributed Constraint Optimization (DCOP) is a powerful framework for representing and solving distributed combinatorial problems, where the variables of the problem are owned by different agents. Many multi-agent problems include constraints that produce different gains (or costs) for the participating agents. Asymmetric gains of constrained agents cannot be naturally represented by the standard DCOP model.The present paper proposes a general framework for Asymmetric DCOPs (ADCOPs). In ADCOPs different agents may have different valuations for constraints that they are involved in. The new framework bridges the gap between multi-agent problems which tend to have asymmetric structure and the standard symmetric DCOP model. The benefits of the proposed model over previous attempts to generalize the DCOP model are discussed and evaluated.Innovative algorithms that apply to the special properties of the proposed ADCOP model are presented in detail. These include complete algorithms that have a substantial advantage in terms of runtime and network load over existing algorithms (for standard DCOPs) which use alternative representations. Moreover, standard incomplete algorithms (i.e., local search algorithms) are inapplicable to the existing DCOP representations of asymmetric constraints and when they are applied to the new ADCOP framework they often fail to converge to a local optimum and yield poor results. The local search algorithms proposed in the present paper converge to high quality solutions. The experimental evidence that is presented reveals that the proposed local search algorithms for ADCOPs achieve high quality solutions while preserving a high level of privacy.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {613–647},
numpages = {35}
}

@article{10.5555/2566972.2566987,
author = {B\"{a}ckstr\"{o}m, Christer and Jonsson, Peter},
title = {A Refined View of Causal Graphs and Component Sizes: SP-Closed Graph Classes and Beyond},
year = {2013},
issue_date = {May 2013},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {47},
number = {1},
issn = {1076-9757},
abstract = {The causal graph of a planning instance is an important tool for planning both in practice and in theory. The theoretical studies of causal graphs have largely analysed the computational complexity of planning for instances where the causal graph has a certain structure, often in combination with other parameters like the domain size of the variables. Chen and Gim\'{e}nez ignored even the structure and considered only the size of the weakly connected components. They proved that planning is tractable if the components are bounded by a constant and otherwise intractable. Their intractability result was, however, conditioned by an assumption from parameterised complexity theory that has no known useful relationship with the standard complexity classes. We approach the same problem from the perspective of standard complexity classes, and prove that planning is NP-hard for classes with unbounded components under an additional restriction we refer to as SP-closed. We then argue that most NP-hardness theorems for causal graphs are difficult to apply and, thus, prove a more general result; even if the component sizes grow slowly and the class is not densely populated with graphs, planning still cannot be tractable unless the polynomial hierachy collapses. Both these results still hold when restricted to the class of acyclic causal graphs. We finally give a partial characterization of the borderline between NP-hard and NP-intermediate classes, giving further insight into the problem.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {575–611},
numpages = {37}
}

@article{10.5555/2566972.2566986,
author = {Joty, Shafiq and Carenini, Giuseppe and Ng, Raymond T.},
title = {Topic Segmentation and Labeling in Asynchronous Conversations},
year = {2013},
issue_date = {May 2013},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {47},
number = {1},
issn = {1076-9757},
abstract = {Topic segmentation and labeling is often considered a prerequisite for higher-level conversation analysis and has been shown to be useful in many Natural Language Processing (NLP) applications. We present two new corpora of email and blog conversations annotated with topics, and evaluate annotator reliability for the segmentation and labeling tasks in these asynchronous conversations. We propose a complete computational framework for topic segmentation and labeling in asynchronous conversations. Our approach extends state-of-the-art methods by considering a fine-grained structure of an asynchronous conversation, along with other conversational features by applying recent graph-based methods for NLP. For topic segmentation, we propose two novel unsupervised models that exploit the fine-grained conversational structure, and a novel graph-theoretic supervised model that combines lexical, conversational and topic features. For topic labeling, we propose two novel (unsupervised) random walk models that respectively capture conversation specific clues from two different sources: the leading sentences and the fine-grained conversational structure. Empirical evaluation shows that the segmentation and the labeling performed by our best models beat the state-of-the-art, and are highly correlated with human annotations.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {521–573},
numpages = {53}
}

@article{10.5555/2566972.2566985,
author = {Betzler, Nadja and Slinko, Arkadii and Uhlmann, Johannes},
title = {On the Computation of Fully Proportional Representation},
year = {2013},
issue_date = {May 2013},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {47},
number = {1},
issn = {1076-9757},
abstract = {We investigate two systems of fully proportional representation suggested by Chamberlin & Courant and Monroe. Both systems assign a representative to each voter so that the "sum of misrepresentations" is minimized. The winner determination problem for both systems is known to be NP-hard, hence this work aims at investigating whether there are variants of the proposed rules and/or specific electorates for which these problems can be solved efficiently. As a variation of these rules, instead of minimizing the sum of misrepresentations, we considered minimizing the maximal misrepresentation introducing effectively two new rules. In the general case these "minimax" versions of classical rules appeared to be still NP-hard.We investigated the parameterized complexity of winner determination of the two classical and two new rules with respect to several parameters. Here we have a mixture of positive and negative results: e.g., we proved fixed-parameter tractability for the parameter the number of candidates but fixed-parameter intractability for the number of winners.For single-peaked electorates our results are overwhelmingly positive: we provide polynomial-time algorithms for most of the considered problems. The only rule that remains NP-hard for single-peaked electorates is the classical Monroe rule.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {475–519},
numpages = {45}
}

@article{10.5555/2566972.2566984,
author = {Cigler, Ludek and Faltings, Boi},
title = {Decentralized Anti-Coordination through Multi-Agent Learning},
year = {2013},
issue_date = {May 2013},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {47},
number = {1},
issn = {1076-9757},
abstract = {To achieve an optimal outcome in many situations, agents need to choose distinct actions from one another. This is the case notably in many resource allocation problems, where a single resource can only be used by one agent at a time. How shall a designer of a multi-agent system program its identical agents to behave each in a different way?From a game theoretic perspective, such situations lead to undesirable Nash equilibria. For example consider a resource allocation game in that two players compete for an exclusive access to a single resource. It has three Nash equilibria. The two pure-strategy NE are efficient, but not fair. The one mixed-strategy NE is fair, but not efficient. Aumann's notion of correlated equilibrium fixes this problem: It assumes a correlation device that suggests each agent an action to take.However, such a "smart" coordination device might not be available. We propose using a randomly chosen, "stupid" integer coordination signal. "Smart" agents learn which action they should use for each value of the coordination signal.We present a multi-agent learning algorithm that converges in polynomial number of steps to a correlated equilibrium of a channel allocation game, a variant of the resource allocation game. We show that the agents learn to play for each coordination signal value a randomly chosen pure-strategy Nash equilibrium of the game. Therefore, the outcome is an efficient correlated equilibrium. This CE becomes more fair as the number of the available coordination signal values increases.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {441–473},
numpages = {33}
}

@article{10.5555/2566972.2566983,
author = {Taghipour, Nima and Fierens, Daan and Davis, Jesse and Blockeel, Hendrik},
title = {Lifted Variable Elimination: Decoupling the Operators from the Constraint Language},
year = {2013},
issue_date = {May 2013},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {47},
number = {1},
issn = {1076-9757},
abstract = {Lifted probabilistic inference algorithms exploit regularities in the structure of graphical models to perform inference more efficiently. More specifically, they identify groups of interchangeable variables and perform inference once per group, as opposed to once per variable. The groups are defined by means of constraints, so the flexibility of the grouping is determined by the expressivity of the constraint language. Existing approaches for exact lifted inference use specific languages for (in)equality constraints, which often have limited expressivity. In this article, we decouple lifted inference from the constraint language. We define operators for lifted inference in terms of relational algebra operators, so that they operate on the semantic level (the constraints' extension) rather than on the syntactic level, making them language-independent. As a result, lifted inference can be performed using more powerful constraint languages, which provide more opportunities for lifting. We empirically demonstrate that this can improve inference efficiency by orders of magnitude, allowing exact inference where until now only approximate inference was feasible.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {393–439},
numpages = {47}
}

@article{10.5555/2566972.2566982,
author = {Faber, Wolfgang and Truszczy\'{n}ski, Miros\l{}aw and Woltran, Stefan},
title = {Strong Equivalence of Qualitative Optimization Problems},
year = {2013},
issue_date = {May 2013},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {47},
number = {1},
issn = {1076-9757},
abstract = {We introduce the framework of qualitative optimization problems (or, simply, optimization problems) to represent preference theories. The formalism uses separate modules to describe the space of outcomes to be compared (the generator) and the preferences on outcomes (the selector). We consider two types of optimization problems. They differ in the way the generator, which we model by a propositional theory, is interpreted: by the standard propositional logic semantics, and by the equilibrium-model (answer-set) semantics. Under the latter interpretation of generators, optimization problems directly generalize answer-set optimization programs proposed previously. We study strong equivalence of optimization problems, which guarantees their interchangeability within any larger context. We characterize several versions of strong equivalence obtained by restricting the class of optimization problems that can be used as extensions and establish the complexity of associated reasoning tasks. Understanding strong equivalence is essential for modular representation of optimization problems and rewriting techniques to simplify them without changing their inherent properties.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {351–391},
numpages = {41}
}

@article{10.5555/2566972.2566981,
author = {Costa, Paulo and Botelho, Luis},
title = {Learning by Observation of Agent Software Images},
year = {2013},
issue_date = {May 2013},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {47},
number = {1},
issn = {1076-9757},
abstract = {Learning by observation can be of key importance whenever agents sharing similar features want to learn from each other. This paper presents an agent architecture that enables software agents to learn by direct observation of the actions executed by expert agents while they are performing a task. This is possible because the proposed architecture displays information that is essential for observation, making it possible for software agents to observe each other.The agent architecture supports a learning process that covers all aspects of learning by observation, such as discovering and observing experts, learning from the observed data, applying the acquired knowledge and evaluating the agent's progress. The evaluation provides control over the decision to obtain new knowledge or apply the acquired knowledge to new problems.We combine two methods for learning from the observed information. The first one, the recall method, uses the sequence on which the actions were observed to solve new problems. The second one, the classification method, categorizes the information in the observed data and determines to which set of categories the new problems belong.Results show that agents are able to learn in conditions where common supervised learning algorithms fail, such as when agents do not know the results of their actions a priori or when not all the effects of the actions are visible. The results also show that our approach provides better results than other learning methods since it requires shorter learning periods.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {313–349},
numpages = {37}
}

@article{10.5555/2566972.2566980,
author = {Bachrach, Yoram and Porat, Ely and Rosenschein, Jeffrey S.},
title = {Sharing Rewards in Cooperative Connectivity Games},
year = {2013},
issue_date = {May 2013},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {47},
number = {1},
issn = {1076-9757},
abstract = {We consider how selfish agents are likely to share revenues derived from maintaining connectivity between important network servers. We model a network where a failure of one node may disrupt communication between other nodes as a cooperative game called the vertex Connectivity Game (CG). In this game, each agent owns a vertex, and controls all the edges going to and from that vertex. A coalition of agents wins if it fully connects a certain subset of vertices in the graph, called the primary vertices.Power indices measure an agent's ability to affect the outcome of the game. We show that in our domain, such indices can be used to both determine the fair share of the revenues an agent is entitled to, and identify significant possible points of failure affecting the reliability of communication in the network. We show that in general graphs, calculating the Shapley and Banzhaf power indices is #P-complete, but suggest a polynomial algorithm for calculating them in trees.We also investigate finding stable payoff divisions of the revenues in CGs, captured by the game theoretic solution of the core, and its relaxations, the ε-core and least core. We show a polynomial algorithm for computing the core of a CG, but show that testing whether an imputation is in theε-core is coNP-complete. Finally, we show that for trees, it is possible to test for ε-core imputations in polynomial time.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {281–311},
numpages = {31}
}

@article{10.5555/2566972.2566979,
author = {Bellemare, Marc G. and Naddaf, Yavar and Veness, Joel and Bowling, Michael},
title = {The Arcade Learning Environment: An Evaluation Platform for General Agents},
year = {2013},
issue_date = {May 2013},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {47},
number = {1},
issn = {1076-9757},
abstract = {In this article we introduce the Arcade Learning Environment (ALE): both a challenge problem and a platform and methodology for evaluating the development of general, domain-independent AI technology. ALE provides an interface to hundreds of Atari 2600 game environments, each one different, interesting, and designed to be a challenge for human players. ALE presents significant research challenges for reinforcement learning, model learning, model-based planning, imitation learning, transfer learning, and intrinsic motivation. Most importantly, it provides a rigorous testbed for evaluating and comparing approaches to these problems. We illustrate the promise of ALE by developing and benchmarking domain-independent agents designed using well-established AI techniques for both reinforcement learning and planning. In doing so, we also propose an evaluation methodology made possible by ALE, reporting empirical results on over 55 different games. All of the software, including the benchmark agents, is publicly available.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {253–279},
numpages = {27}
}

@article{10.5555/2566972.2566978,
author = {Tesauro, Gerald and Gondek, David C. and Lenchner, Jonathan and Fan, James and Prager, John M.},
title = {Analysis of Watson's Strategies for Playing Jeopardy!},
year = {2013},
issue_date = {May 2013},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {47},
number = {1},
issn = {1076-9757},
abstract = {Major advances in Question Answering technology were needed for IBM Watson1 to play Jeopardy! at championship level - the show requires rapid-fire answers to challenging natural language questions, broad general knowledge, high precision, and accurate confidence estimates. In addition, Jeopardy! features four types of decision making carrying great strategic importance: (1) Daily Double wagering; (2) Final Jeopardy wagering; (3) selecting the next square when in control of the board; (4) deciding whether to attempt to answer, i.e., "buzz in." Using sophisticated strategies for these decisions, that properly account for the game state and future event probabilities, can significantly boost a player's overall chances to win, when compared with simple "rule of thumb" strategies.This article presents our approach to developing Watson's game-playing strategies, comprising development of a faithful simulation model, and then using learning and Monte-Carlo methods within the simulator to optimize Watson's strategic decision-making. After giving a detailed description of each of our game-strategy algorithms, we then focus in particular on validating the accuracy of the simulator's predictions, and documenting performance improvements using our methods. Quantitative performance benefits are shown with respect to both simple heuristic strategies, and actual human contestant performance in historical episodes. We further extend our analysis of human play to derive a number of valuable and counterintuitive examples illustrating how human contestants may improve their performance on the show.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {205–251},
numpages = {47}
}

@article{10.5555/2566972.2566977,
author = {Mourad, Rapha\"{e}l and Sinoquet, Christine and Zhang, Nevin L. and Liu, Tengfei and Leray, Philippe},
title = {A Survey on Latent Tree Models and Applications},
year = {2013},
issue_date = {May 2013},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {47},
number = {1},
issn = {1076-9757},
abstract = {In data analysis, latent variables play a central role because they help provide powerful insights into a wide variety of phenomena, ranging from biological to human sciences. The latent tree model, a particular type of probabilistic graphical models, deserves attention. Its simple structure - a tree - allows simple and efficient inference, while its latent variables capture complex relationships. In the past decade, the latent tree model has been subject to significant theoretical and methodological developments. In this review, we propose a comprehensive study of this model. First we summarize key ideas underlying the model. Second we explain how it can be efficiently learned from data. Third we illustrate its use within three types of applications: latent structure discovery, multidimensional clustering, and probabilistic inference. Finally, we conclude and give promising directions for future researches in this field.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {157–203},
numpages = {47}
}

@article{10.5555/2566972.2566976,
author = {Boerkoel, James C. and Durfee, Edmund H.},
title = {Distributed Reasoning for Multiagent Simple Temporal Problems},
year = {2013},
issue_date = {May 2013},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {47},
number = {1},
issn = {1076-9757},
abstract = {This research focuses on building foundational algorithms for scheduling agents that assist people in managing their activities in environments where tempo and complex activity interdependencies outstrip people's cognitive capacity. We address the critical challenge of reasoning over individuals' interacting schedules to efficiently answer queries about how to meet scheduling goals while respecting individual privacy and autonomy to the extent possible. We formally define the Multiagent Simple Temporal Problem for naturally capturing and reasoning over the distributed but interconnected scheduling problems of multiple individuals. Our hypothesis is that combining bottom-up and top-down approaches will lead to effective solution techniques. In our bottom-up phase, an agent externalizes constraints that compactly summarize how its local subproblem affects other agents' subproblems, whereas in our top-down phase an agent proactively constructs and internalizes new local constraints that decouple its subproblem from others'. We confirm this hypothesis by devising distributed algorithms that calculate summaries of the joint solution space for multiagent scheduling problems, without centralizing or otherwise redistributing the problems. The distributed algorithms permit concurrent execution to achieve significant speedup over the current art and also increase the level of privacy and independence in individual agent reasoning. These algorithms are most advantageous for problems where interactions between the agents are sparse compared to the complexity of agents' individual problems.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {95–156},
numpages = {62}
}

@article{10.5555/2566972.2566975,
author = {Vesic, Srdjan},
title = {Identifying the Class of Maxi-Consistent Operators in Argumentation},
year = {2013},
issue_date = {May 2013},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {47},
number = {1},
issn = {1076-9757},
abstract = {Dung's abstract argumentation theory can be seen as a general framework for nonmonotonic reasoning. An important question is then: what is the class of logics that can be subsumed as instantiations of this theory? The goal of this paper is to identify and study the large class of logic-based instantiations of Dung's theory which correspond to the maxi-consistent operator, i.e. to the function which returns maximal consistent subsets of an inconsistent knowledge base. In other words, we study the class of instantiations where every extension of the argumentation system corresponds to exactly one maximal consistent subset of the knowledge base. We show that an attack relation belonging to this class must be conflict-dependent, must not be valid, must not be conflict-complete, must not be symmetric etc. Then, we show that some attack relations serve as lower or upper bounds of the class (e.g. if an attack relation contains canonical undercut then it is not a member of this class). By using our results, we show for all existing attack relations whether or not they belong to this class. We also define new attack relations which are members of this class. Finally, we interpret our results and discuss more general questions, like: what is the added value of argumentation in such a setting? We believe that this work is a first step towards achieving our long-term goal, which is to better understand the role of argumentation and, particularly, the expressivity of logic-based instantiations of Dung-style argumentation frameworks.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {71–93},
numpages = {23}
}

@article{10.5555/2566972.2566974,
author = {Bajestani, Maliheh Aramon and Beck, J. Christopher},
title = {Scheduling a Dynamic Aircraft Repair Shop with Limited Repair Resources},
year = {2013},
issue_date = {May 2013},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {47},
number = {1},
issn = {1076-9757},
abstract = {We address a dynamic repair shop scheduling problem in the context of military aircraft fleet management where the goal is to maintain a full complement of aircraft over the longterm. A number of flights, each with a requirement for a specific number and type of aircraft, are already scheduled over a long horizon. We need to assign aircraft to flights and schedule repair activities while considering the flights requirements, repair capacity, and aircraft failures. The number of aircraft awaiting repair dynamically changes over time due to failures and it is therefore necessary to rebuild the repair schedule online. To solve the problem, we view the dynamic repair shop as successive static repair scheduling sub-problems over shorter time periods. We propose a complete approach based on the logic-based Benders decomposition to solve the static sub-problems, and design different rescheduling policies to schedule the dynamic repair shop. Computational experiments demonstrate that the Benders model is able to find and prove optimal solutions on average four times faster than a mixed integer programming model. The rescheduling approach having both aspects of scheduling over a longer horizon and quickly adjusting the schedule increases aircraft available in the long term by 10% compared to the approaches having either one of the aspects alone.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {35–70},
numpages = {36}
}

@article{10.5555/2566972.2566973,
author = {Wang, Guangtao and Song, Qinbao and Sun, Heli and Zhang, Xueying and Xu, Baowen and Zhou, Yuming},
title = {A Feature Subset Selection Algorithm Automatic Recommendation Method},
year = {2013},
issue_date = {May 2013},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {47},
number = {1},
issn = {1076-9757},
abstract = {Many feature subset selection (FSS) algorithms have been proposed, but not all of them are appropriate for a given feature selection problem. At the same time, so far there is rarely a good way to choose appropriate FSS algorithms for the problem at hand. Thus, FSS algorithm automatic recommendation is very important and practically useful. In this paper, a meta learning based FSS algorithm automatic recommendation method is presented. The proposed method first identifies the data sets that are most similar to the one at hand by the k-nearest neighbor classification algorithm, and the distances among these data sets are calculated based on the commonly-used data set characteristics. Then, it ranks all the candidate FSS algorithms according to their performance on these similar data sets, and chooses the algorithms with best performance as the appropriate ones. The performance of the candidate FSS algorithms is evaluated by a multi-criteria metric that takes into account not only the classification accuracy over the selected features, but also the runtime of feature selection and the number of selected features. The proposed recommendation method is extensively tested on 115 real world data sets with 22 well-known and frequently-used different FSS algorithms for five representative classifiers. The results show the effectiveness of our proposed FSS algorithm recommendation method.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {1–34},
numpages = {34}
}

@article{10.5555/2512538.2512555,
author = {Cai, Shaowei and Su, Kaile and Luo, Chuan and Sattar, Abdul},
title = {NuMVC: An Efficient Local Search Algorithm for Minimum Vertex Cover},
year = {2013},
issue_date = {January 2013},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {46},
number = {1},
issn = {1076-9757},
abstract = {The Minimum Vertex Cover (MVC) problem is a prominent NP-hard combinatorial optimization problem of great importance in both theory and application. Local search has proved successful for this problem. However, there are two main drawbacks in state-of-the-art MVC local search algorithms. First, they select a pair of vertices to exchange simultaneously, which is timeconsuming. Secondly, although using edge weighting techniques to diversify the search, these algorithms lack mechanisms for decreasing the weights. To address these issues, we propose two new strategies: two-stage exchange and edge weighting with forgetting. The two-stage exchange strategy selects two vertices to exchange separately and performs the exchange in two stages. The strategy of edge weighting with forgetting not only increases weights of uncovered edges, but also decreases some weights for each edge periodically. These two strategies are used in designing a new MVC local search algorithm, which is referred to as NuMVC.We conduct extensive experimental studies on the standard benchmarks, namely DIMACS and BHOSLIB. The experiment comparing NuMVC with state-of-the-art heuristic algorithms show that NuMVC is at least competitive with the nearest competitor namely PLS on the DIMACS benchmark, and clearly dominates all competitors on the BHOSLIB benchmark. Also, experimental results indicate that NuMVC finds an optimal solution much faster than the current best exact algorithm for Maximum Clique on random instances as well as some structured ones. Moreover, we study the effectiveness of the two strategies and the run-time behaviour through experimental analysis.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {687–716},
numpages = {30}
}

@article{10.5555/2512538.2512554,
author = {Hariri, Babak Bagheri and Calvanese, Diego and Montali, Marco and De Giacomo, Giuseppe and De Masellis, Riccardo and Felli, Paolo},
title = {Description Logic Knowledge and Action Bases},
year = {2013},
issue_date = {January 2013},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {46},
number = {1},
issn = {1076-9757},
abstract = {Description logic Knowledge and Action Bases (KAB) are a mechanism for providing both a semantically rich representation of the information on the domain of interest in terms of a description logic knowledge base and actions to change such information over time, possibly introducing new objects. We resort to a variant of DL-Lite where the unique name assumption is not enforced and where equality between objects may be asserted and inferred. Actions are specified as sets of conditional effects, where conditions are based on epistemic queries over the knowledge base (TBox and ABox), and effects are expressed in terms of new ABoxes. In this setting, we address verification of temporal properties expressed in a variant of first-order µ-calculus with quantification across states. Notably, we show decidability of verification, under a suitable restriction inspired by the notion of weak acyclicity in data exchange.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {651–686},
numpages = {36}
}

@article{10.5555/2512538.2512553,
author = {Michalak, Tomasz P. and Aadithya, Karthik V. and Szczepanski, Piotr L. and Ravindran, Balaraman and Jennings, Nicholas R.},
title = {Efficient Computation of the Shapley Value for Game-Theoretic Network Centrality},
year = {2013},
issue_date = {January 2013},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {46},
number = {1},
issn = {1076-9757},
abstract = {The Shapley value--probably the most important normative payoff division scheme in coalitional games--has recently been advocated as a useful measure of centrality in networks. However, although this approach has a variety of real-world applications (including social and organisational networks, biological networks and communication networks), its computational properties have not been widely studied. To date, the only practicable approach to compute Shapley value-based centrality has been via Monte Carlo simulations which are computationally expensive and not guaranteed to give an exact answer. Against this background, this paper presents the first study of the computational aspects of the Shapley value for network centralities. Specifically, we develop exact analytical formulae for Shapley value-based centrality in both weighted and unweighted networks and develop efficient (polynomial time) and exact algorithms based on them. We empirically evaluate these algorithms on two real-life examples (an infrastructure network representing the topology of the Western States Power Grid and a collaboration network from the field of astrophysics) and demonstrate that they deliver significant speedups over the Monte Carlo approach. For instance, in the case of unweighted networks our algorithms are able to return the exact solution about 1600 times faster than the Monte Carlo approximation, even if we allow for a generous 10% error margin for the latter method.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {607–650},
numpages = {44}
}

@article{10.5555/2512538.2512552,
author = {Wolpert, David H. and Bono, James W.},
title = {Predicting Behavior in Unstructured Bargaining with a Probability Distribution},
year = {2013},
issue_date = {January 2013},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {46},
number = {1},
issn = {1076-9757},
abstract = {In experimental tests of human behavior in unstructured bargaining games, typically many joint utility outcomes are found to occur, not just one. This suggests we predict the outcome of such a game as a probability distribution. This is in contrast to what is conventionally done (e.g, in the Nash bargaining solution), which is predict a single outcome. We show how to translate Nash's bargaining axioms to provide a distribution over outcomes rather than a single outcome. We then prove that a subset of those axioms forces the distribution over utility outcomes to be a power-law distribution. Unlike Nash's original result, our result holds even if the feasible set is finite. When the feasible set is convex and comprehensive, the mode of the power law distribution is the Harsanyi bargaining solution, and if we require symmetry it is the Nash bargaining solution. However, in general these modes of the joint utility distribution are not the experimentalist's Bayesoptimal predictions for the joint utility. Nor are the bargains corresponding to the modes of those joint utility distributions the modes of the distribution over bargains in general, since more than one bargain may result in the same joint utility. After introducing distributional bargaining solution concepts, we show how an external regulator can use them to optimally design an unstructured bargaining scenario. Throughout we demonstrate our analysis in computational experiments involving flight rerouting negotiations in the National Airspace System. We emphasize that while our results are formulated for unstructured bargaining, they can also be used to make predictions for noncooperative games where the modeler knows the utility functions of the players over possible outcomes of the game, but does not know the move spaces the players use to determine those outcomes.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {579–605},
numpages = {27}
}

@article{10.5555/2512538.2512551,
author = {Ono, Masahiro and Williams, Brian C. and Blackmore, Lars},
title = {Probabilistic Planning for Continuous Dynamic Systems under Bounded Risk},
year = {2013},
issue_date = {January 2013},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {46},
number = {1},
issn = {1076-9757},
abstract = {This paper presents a model-based planner called the Probabilistic Sulu Planner or the p-Sulu Planner, which controls stochastic systems in a goal directed manner within user-specified risk bounds. The objective of the p-Sulu Planner is to allow users to command continuous, stochastic systems, such as unmanned aerial and space vehicles, in a manner that is both intuitive and safe. To this end, we first develop a new plan representation called a chance-constrained qualitative state plan (CCQSP), through which users can specify the desired evolution of the plant state as well as the acceptable level of risk. An example of a CCQSP statement is "go to A through B within 30 minutes, with less than 0.001% probability of failure." We then develop the p-Sulu Planner, which can tractably solve a CCQSP planning problem. In order to enable CCQSP planning, we develop the following two capabilities in this paper: 1) risk-sensitive planning with risk bounds, and 2) goal-directed planning in a continuous domain with temporal constraints. The first capability is to ensures that the probability of failure is bounded. The second capability is essential for the planner to solve problems with a continuous state space such as vehicle path planning. We demonstrate the capabilities of the p-Sulu Planner by simulations on two real-world scenarios: the path planning and scheduling of a personal aerial vehicle as well as the space rendezvous of an autonomous cargo spacecraft.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {511–577},
numpages = {67}
}

@article{10.5555/2512538.2512550,
author = {Oliehoek, Frans A. and Spaan, Matthijs T. J. and Amato, Christopher and Whiteson, Shimon},
title = {Incremental Clustering and Expansion for Faster Optimal Planning in Decentralized POMDPs},
year = {2013},
issue_date = {January 2013},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {46},
number = {1},
issn = {1076-9757},
abstract = {This article presents the state-of-the-art in optimal solution methods for decentralized partially observable Markov decision processes (Dec-POMDPs), which are general models for collaborative multiagent planning under uncertainty. Building off the generalized multiagent A* (GMAA*) algorithm, which reduces the problem to a tree of one-shot collaborative Bayesian games (CBGs), we describe several advances that greatly expand the range of Dec-POMDPs that can be solved optimally. First, we introduce lossless incremental clustering of the CBGs solved by GMAA*, which achieves exponential speedups without sacrificing optimality. Second, we introduce incremental expansion of nodes in the GMAA* search tree, which avoids the need to expand all children, the number of which is in the worst case doubly exponential in the node's depth. This is particularly beneficial when little clustering is possible. In addition, we introduce new hybrid heuristic representations that are more compact and thereby enable the solution of larger Dec-POMDPs. We provide theoretical guarantees that, when a suitable heuristic is used, both incremental clustering and incremental expansion yield algorithms that are both complete and search equivalent. Finally, we present extensive empirical results demonstrating that GMAA*-ICE, an algorithm that synthesizes these advances, can optimally solve Dec-POMDPs of unprecedented size.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {449–509},
numpages = {61}
}

@article{10.5555/2512538.2512549,
author = {Snooke, Neal and Lee, Mark},
title = {Qualitative Order of Magnitude Energy-Flow-Based Failure Modes and Effects Analysis},
year = {2013},
issue_date = {January 2013},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {46},
number = {1},
issn = {1076-9757},
abstract = {This paper presents a structured power and energy-flow-based qualitative modelling approach that is applicable to a variety of system types including electrical and fluid flow. The modelling is split into two parts. Power flow is a global phenomenon and is therefore naturally represented and analysed by a network comprised of the relevant structural elements from the components of a system. The power flow analysis is a platform for higher-level behaviour prediction of energy related aspects using local component behaviour models to capture a state-based representation with a global time. The primary application is Failure Modes and Effects Analysis (FMEA) and a form of exaggeration reasoning is used, combined with an order of magnitude representation to derive the worst case failure modes. The novel aspects of the work are an order of magnitude(OM) qualitative network analyser to represent any power domain and topology, including multiple power sources, a feature that was not required for earlier specialised electrical versions of the approach. Secondly, the representation of generalised energy related behaviour as state-based local models is presented as a modelling strategy that can be more vivid and intuitive for a range of topologically complex applications than qualitative equation-based representations. The two-level modelling strategy allows the broad system behaviour coverage of qualitative simulation to be exploited for the FMEA task, while limiting the difficulties of qualitative ambiguity explanation that can arise from abstracted numerical models. We have used the method to support an automated FMEA system with examples of an aircraft fuel system and domestic a heating system discussed in this paper.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {413–447},
numpages = {35}
}

@article{10.5555/2512538.2512548,
author = {Coles, Amanda and Coles, Andrew and Fox, Maria and Long, Derek},
title = {A Hybrid LP-RPG Heuristic for Modelling Numeric Resource Flows in Planning},
year = {2013},
issue_date = {January 2013},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {46},
number = {1},
issn = {1076-9757},
abstract = {Although the use of metric uents is fundamental to many practical planning problems, the study of heuristics to support fully automated planners working with these fluents remains relatively unexplored. The most widely used heuristic is the relaxation of metric uents into interval-valued variables|an idea first proposed a decade ago. Other heuristics depend on domain encodings that supply additional information about fluents, such as capacity constraints or other resource-related annotations.A particular challenge to these approaches is in handling interactions between metric uents that represent exchange, such as the transformation of quantities of raw materials into quantities of processed goods, or trading of money for materials. The usual relaxation of metric fluents is often very poor in these situations, since it does not recognise that resources, once spent, are no longer available to be spent again.We present a heuristic for numeric planning problems building on the propositional relaxed planning graph, but using a mathematical program for numeric reasoning. We define a class of producer-consumer planning problems and demonstrate how the numeric constraints in these can be modelled in a mixed integer program (MIP). This MIP is then combined with a metric Relaxed Planning Graph (RPG) heuristic to produce an integrated hybrid heuristic. The MIP tracks resource use more accurately than the usual relaxation, but relaxes the ordering of actions, while the RPG captures the causal propositional aspects of the problem. We discuss how these two components interact to produce a single unified heuristic and go on to explore how further numeric features of planning problems can be integrated into the MIP. We show that encoding a limited subset of the propositional problem to augment the MIP can yield more accurate guidance, partly by exploiting structure such as propositional landmarks and propositional resources. Our results show that the use of this heuristic enhances scalability on problems where numeric resource interaction is key in finding a solution.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {343–412},
numpages = {70}
}

@article{10.5555/2512538.2512547,
author = {Metodi, Amit and Codish, Michael and Stuckey, Peter J.},
title = {Boolean Equi-Propagation for Concise and Efficient SAT Encodings of Combinatorial Problems},
year = {2013},
issue_date = {January 2013},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {46},
number = {1},
issn = {1076-9757},
abstract = {We present an approach to propagation-based SAT encoding of combinatorial problems, Boolean equi-propagation, where constraints are modeled as Boolean functions which propagate information about equalities between Boolean literals. This information is then applied to simplify the CNF encoding of the constraints. A key factor is that considering only a small fragment of a constraint model at one time enables us to apply stronger, and even complete, reasoning to detect equivalent literals in that fragment. Once detected, equivalences apply to simplify the entire constraint model and facilitate further reasoning on other fragments. Equi-propagation in combination with partial evaluation and constraint simplification provide the foundation for a powerful approach to SAT-based finite domain constraint solving. We introduce a tool called BEE (Ben-Gurion Equi-propagation Encoder) based on these ideas and demonstrate for a variety of benchmarks that our approach leads to a considerable reduction in the size of CNF encodings and subsequent speed-ups in SAT solving times.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {303–341},
numpages = {39}
}

@article{10.5555/2512538.2512546,
author = {Ordyniak, Sebastian and Szeider, Stefan},
title = {Parameterized Complexity Results for Exact Bayesian Network Structure Learning},
year = {2013},
issue_date = {January 2013},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {46},
number = {1},
issn = {1076-9757},
abstract = {Bayesian network structure learning is the notoriously difficult problem of discovering a Bayesian network that optimally represents a given set of training data. In this paper we study the computational worst-case complexity of exact Bayesian network structure learning under graph theoretic restrictions on the (directed) super-structure. The super-structure is an undirected graph that contains as subgraphs the skeletons of solution networks. We introduce the directed super-structure as a natural generalization of its undirected counterpart. Our results apply to several variants of score-based Bayesian network structure learning where the score of a network decomposes into local scores of its nodes.Results: We show that exact Bayesian network structure learning can be carried out in non-uniform polynomial time if the super-structure has bounded treewidth, and in linear time if in addition the super-structure has bounded maximum degree. Furthermore, we show that if the directed super-structure is acyclic, then exact Bayesian network structure learning can be carried out in quadratic time. We complement these positive results with a number of hardness results. We show that both restrictions (treewidth and degree) are essential and cannot be dropped without loosing uniform polynomial time tractability (subject to a complexity-theoretic assumption). Similarly, exact Bayesian network structure learning remains NP-hard for "almost acyclic" directed super-structures. Furthermore, we show that the restrictions remain essential if we do not search for a globally optimal network but aim to improve a given network by means of at most k arc additions, arc deletions, or arc reversals (k-neighborhood local search).},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {263–302},
numpages = {40}
}

@article{10.5555/2512538.2512545,
author = {G\"{o}rnitz, Nico and Kloft, Marius and Rieck, Konrad and Brefeld, Ulf},
title = {Toward Supervised Anomaly Detection},
year = {2013},
issue_date = {January 2013},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {46},
number = {1},
issn = {1076-9757},
abstract = {Anomaly detection is being regarded as an unsupervised learning task as anomalies stem from adversarial or unlikely events with unknown distributions. However, the predictive performance of purely unsupervised anomaly detection often fails to match the required detection rates in many tasks and there exists a need for labeled data to guide the model generation. Our first contribution shows that classical semi-supervised approaches, originating from a supervised classifier, are inappropriate and hardly detect new and unknown anomalies. We argue that semi-supervised anomaly detection needs to ground on the unsupervised learning paradigm and devise a novel algorithm that meets this requirement. Although being intrinsically non-convex, we further show that the optimization problem has a convex equivalent under relatively mild assumptions. Additionally, we propose an active learning strategy to automatically filter candidates for labeling. In an empirical study on network intrusion detection data, we observe that the proposed learning methodology requires much less labeled data than the state-of-the-art, while achieving higher detection accuracies.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {235–262},
numpages = {28}
}

@article{10.5555/2512538.2512544,
author = {Zhao, Hai and Zhang, Xiaotian and Kit, Chunyu},
title = {Integrative Semantic Dependency Parsing via Efficient Large-Scale Feature Selection},
year = {2013},
issue_date = {January 2013},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {46},
number = {1},
issn = {1076-9757},
abstract = {Semantic parsing, i.e., the automatic derivation of meaning representation such as an instantiated predicate-argument structure for a sentence, plays a critical role in deep processing of natural language. Unlike all other top systems of semantic dependency parsing that have to rely on a pipeline framework to chain up a series of submodels each specialized for a specific subtask, the one presented in this article integrates everything into one model, in hopes of achieving desirable integrity and practicality for real applications while maintaining a competitive performance. This integrative approach tackles semantic parsing as a word pair classification problem using a maximum entropy classifier. We leverage adaptive pruning of argument candidates and large-scale feature selection engineering to allow the largest feature space ever in use so far in this field, it achieves a state-of-the-art performance on the evaluation data set for CoNLL-2008 shared task, on top of all but one top pipeline system, confirming its feasibility and effectiveness.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {203–233},
numpages = {31}
}

@article{10.5555/2512538.2512543,
author = {Qazvinian, Vahed and Radev, Dragomir R. and Mohammad, Saif M. and Dorr, Bonnie and Zajic, David and Whidby, Michael and Moon, Taesun},
title = {Generating Extractive Summaries of Scientific Paradigms},
year = {2013},
issue_date = {January 2013},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {46},
number = {1},
issn = {1076-9757},
abstract = {Researchers and scientists increasingly find themselves in the position of having to quickly understand large amounts of technical material. Our goal is to effectively serve this need by using bibliometric text mining and summarization techniques to generate summaries of scientific literature. We show how we can use citations to produce automatically generated, readily consumable, technical extractive summaries. We first propose C-LexRank, a model for summarizing single scientific articles based on citations, which employs community detection and extracts salient information-rich sentences. Next, we further extend our experiments to summarize a set of papers, which cover the same scienti fic topic. We generate extractive summaries of a set of Question Answering (QA) and Dependency Parsing (DP) papers, their abstracts, and their citation sentences and show that citations have unique information amenable to creating a summary.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {165–201},
numpages = {37}
}

@article{10.5555/2512538.2512542,
author = {Guo, Mingyu and Markakis, Evangelos and Apt, Krzysztof R. and Conitzer, Vincent},
title = {Undominated Groves Mechanisms},
year = {2013},
issue_date = {January 2013},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {46},
number = {1},
issn = {1076-9757},
abstract = {The family of Groves mechanisms, which includes the well-known VCG mechanism (also known as the Clarke mechanism), is a family of efficient and strategy-proof mechanisms. Unfortunately, the Groves mechanisms are generally not budget balanced. That is, under such mechanisms, payments may flow into or out of the system of the agents, resulting in deficits or reduced utilities for the agents. We consider the following problem: within the family of Groves mechanisms, we want to identify mechanisms that give the agents the highest utilities, under the constraint that these mechanisms must never incur deficits.We adopt a prior-free approach. We introduce two general measures for comparing mechanisms in prior-free settings. We say that a non-deficit Groves mechanism M individually dominates another non-deficit Groves mechanism M' if for every type profile, every agent's utility under M is no less than that under M', and this holds with strict inequality for at least one type profile and one agent. We say that a non-deficit Groves mechanism M collectively dominates another non-deficit Groves mechanism M' if for every type profile, the agents' total utility under M is no less than that under M', and this holds with strict inequality for at least one type profile. The above definitions induce two partial orders on non-deficit Groves mechanisms. We study the maximal elements corresponding to these two partial orders, which we call the individually undominated mechanisms and the collectively undominated mechanisms, respectively.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {129–163},
numpages = {35}
}

@article{10.5555/2512538.2512541,
author = {Sauper, Christina and Barzilay, Regina},
title = {Automatic Aggregation by Joint Modeling of Aspects and Values},
year = {2013},
issue_date = {January 2013},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {46},
number = {1},
issn = {1076-9757},
abstract = {We present a model for aggregation of product review snippets by joint aspect identification and sentiment analysis. Our model simultaneously identifies an underlying set of ratable aspects presented in the reviews of a product (e.g., sushi and miso for a Japanese restaurant) and determines the corresponding sentiment of each aspect. This approach directly enables discovery of highly-rated or inconsistent aspects of a product. Our generative model admits an efficient variational mean-field inference algorithm. It is also easily extensible, and we describe several modifications and their effects on model structure and inference. We test our model on two tasks, joint aspect identification and sentiment analysis on a set of Yelp reviews and aspect identification alone on a set of medical summaries. We evaluate the performance of the model on aspect identification, sentiment analysis, and per-word labeling accuracy. We demonstrate that our model outperforms applicable baselines by a considerable margin, yielding up to 32% relative error reduction on aspect identification and up to 20% relative error reduction on sentiment analysis.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {89–127},
numpages = {39}
}

@article{10.5555/2512538.2512540,
author = {Huang, Eric and Korf, Richard E.},
title = {Optimal Rectangle Packing: An Absolute Placement Approach},
year = {2013},
issue_date = {January 2013},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {46},
number = {1},
issn = {1076-9757},
abstract = {We consider the problem of finding all enclosing rectangles of minimum area that can contain a given set of rectangles without overlap. Our rectangle packer chooses the x-coordinates of all the rectangles before any of the y-coordinates. We then transform the problem into a perfect-packing problem with no empty space by adding additional rectangles. To determine the y-coordinates, we branch on the different rectangles that can be placed in each empty position. Our packer allows us to extend the known solutions for a consecutive-square benchmark from 27 to 32 squares. We also introduce three new benchmarks, avoiding properties that make a benchmark easy, such as rectangles with shared dimensions. Our third benchmark consists of rectangles of increasingly high precision. To pack them efficiently, we limit the rectangles' coordinates and the bounding box dimensions to the set of subset sums of the rectangles' dimensions. Overall, our algorithms represent the current state-of-the-art for this problem, outperforming other algorithms by orders of magnitude, depending on the benchmark.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {47–87},
numpages = {41}
}

@article{10.5555/2512538.2512539,
author = {Nightingale, Peter and Gent, Ian P. and Jefferson, Christopher and Miguel, Ian},
title = {Short and Long Supports for Constraint Propagation},
year = {2013},
issue_date = {January 2013},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {46},
number = {1},
issn = {1076-9757},
abstract = {Special-purpose constraint propagation algorithms frequently make implicit use of short supports | by examining a subset of the variables, they can infer support (a justification that a variable-value pair may still form part of an assignment that satisfies the constraint) for all other variables and values and save substantial work - but short supports have not been studied in their own right. The two main contributions of this paper are the identification of short supports as important for constraint propagation, and the introduction of HaggisGAC, an efficient and effective general purpose propagation algorithm for exploiting short supports. Given the complexity of HAGGISGAC, we present it as an optimised version of a simpler algorithm ShortGAC. Although experiments demonstrate the efficiency of ShortGAC compared with other general-purpose propagation algorithms where a compact set of short supports is available, we show theoretically and experimentally that HaggisGAC is even better. We also find that HaggisGAC performs better than GAC-Schema on full-length supports. We also introduce a variant algorithm HaggisGAC-Stable, which is adapted to avoid work on backtracking and in some cases can be faster and have significant reductions in memory use. All the proposed algorithms are excellent for propagating disjunctions of constraints. In all experiments with disjunctions we found our algorithms to be faster than Constructive Or and GAC-Schema by at least an order of magnitude, and up to three orders of magnitude.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {1–45},
numpages = {45}
}

@article{10.5555/2444851.2444870,
author = {Costa-juss\`{a}, Marta R. and Henr\'{\i}quez Q, Carlos A. and Banchs, Rafael E.},
title = {Evaluating Indirect Strategies for Chinese-Spanish Statistical Machine Translation},
year = {2012},
issue_date = {September 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {45},
number = {1},
issn = {1076-9757},
abstract = {Although, Chinese and Spanish are two of the most spoken languages in the world, not much research has been done in machine translation for this language pair. This paper focuses on investigating the state-of-the-art of Chinese-to-Spanish statistical machine translation (SMT), which nowadays is one of the most popular approaches to machine translation. For this purpose, we report details of the available parallel corpus which are Basic Traveller Expressions Corpus (BTEC), Holy Bible and United Nations (UN). Additionally, we conduct experimental work with the largest of these three corpora to explore alternative Smt strategies by means of using a pivot language. Three alternatives are considered for pivoting: cascading, pseudo-corpus and triangulation. As pivot language, we use either English, Arabic or French. Results show that, for a phrase-based Smt system, English is the best pivot language between Chinese and Spanish. We propose a system output combination using the pivot strategies which is capable of outperforming the direct translation strategy. The main objective of this work is motivating and involving the research community to work in this important pair of languages given their demographic impact.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {761–780},
numpages = {20}
}

@article{10.5555/2444851.2444869,
author = {Bodirsky, Manuel and Hils, Martin},
title = {Tractable Set Constraints},
year = {2012},
issue_date = {September 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {45},
number = {1},
issn = {1076-9757},
abstract = {Many fundamental problems in artificial intelligence, knowledge representation, and verification involve reasoning about sets and relations between sets and can be modeled as set constraint satisfaction problems (set CSPs). Such problems are frequently intractable, but there are several important set CSPs that are known to be polynomial-time tractable. We introduce a large class of set CSPs that can be solved in quadratic time. Our class, which we call EI, contains all previously known tractable set CSPs, but also some new ones that are of crucial importance for example in description logics. The class of EI set constraints has an elegant universal-algebraic characterization, which we use to show that every set constraint language that properly contains all EI set constraints already has a finite sublanguage with an NP-hard constraint satisfaction problem.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {731–759},
numpages = {29}
}

@article{10.5555/2444851.2444868,
author = {Dinh, Hang and Dinh, Hieu and Michel, Laurent and Russell, Alexander},
title = {The Time Complexity of <i>A</i>* with Approximate Heuristics on Multiple-Solution Search Spaces},
year = {2012},
issue_date = {September 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {45},
number = {1},
issn = {1076-9757},
abstract = {We study the behavior of the We then experimentally explore to what extent our rigorous upper bounds predict the behavior of },
journal = {J. Artif. Int. Res.},
month = sep,
pages = {685–729},
numpages = {45}
}

@article{10.5555/2444851.2444867,
author = {Radinsky, Kira and Davidovich, Sagie},
title = {Learning to Predict from Textual Data},
year = {2012},
issue_date = {September 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {45},
number = {1},
issn = {1076-9757},
abstract = {Given a current news event, we tackle the problem of generating plausible predictions of future events it might cause. We present a new methodology for modeling and predicting such future news events using machine learning and data mining techniques. Our Pundit algorithm generalizes examples of causality pairs to infer a causality predictor. To obtain precisely labeled causality examples, we mine 150 years of news articles and apply semantic natural language modeling techniques to headlines containing certain predefined causality patterns. For generalization, the model uses a vast number of world knowledge ontologies. Empirical evaluation on real news articles shows that our Pundit algorithm performs as well as non-expert humans.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {641–684},
numpages = {44}
}

@article{10.5555/2444851.2444866,
author = {de Cooman, Gert and Miranda, Enrique},
title = {Irrelevant and Independent Natural Extension for Sets of Desirable Gambles},
year = {2012},
issue_date = {September 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {45},
number = {1},
issn = {1076-9757},
abstract = {The results in this paper add useful tools to the theory of sets of desirable gambles, a growing toolbox for reasoning with partial probability assessments. We investigate how to combine a number of marginal coherent sets of desirable gambles into a joint set using the properties of epistemic irrelevance and independence. We provide formulas for the smallest such joint, called their independent natural extension, and study its main properties. The independent natural extension of maximal coherent sets of desirable gambles allows us to define the strong product of sets of desirable gambles. Finally, we explore an easy way to generalise these results to also apply for the conditional versions of epistemic irrelevance and independence. Having such a set of tools that are easily implemented in computer programs is clearly beneficial to fields, like AI, with a clear interest in coherent reasoning under uncertainty using general and robust uncertainty models that require no full specification.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {601–640},
numpages = {40}
}

@article{10.5555/2444851.2444865,
author = {Brafman, Ronen I. and Shani, Guy},
title = {Replanning in Domains with Partial Information and Sensing Actions},
year = {2012},
issue_date = {September 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {45},
number = {1},
issn = {1076-9757},
abstract = {Replanning via determinization is a recent, popular approach for online planning in MDPs. In this paper we adapt this idea to classical, non-stochastic domains with partial information and sensing actions, presenting a new planner: SDR (Sample, Determinize, Replan). At each step we generate a solution plan to a classical planning problem induced by the original problem. We execute this plan as long as it is safe to do so. When this is no longer the case, we replan. The classical planning problem we generate is based on the translation-based approach for conformant planning introduced by Palacios and Geffner. The state of the classical planning problem generated in this approach captures the belief state of the agent in the original problem. Unfortunately, when this method is applied to planning problems with sensing, it yields a non-deterministic planning problem that is typically very large. Our main contribution is the introduction of state sampling techniques for overcoming these two problems. In addition, we introduce a novel, lazy, regressionbased method for querying the agent's belief state during run-time. We provide a comprehensive experimental evaluation of the planner, showing that it scales better than the state-of-the-art CLG planner on existing benchmark problems, but also highlighting its weaknesses with new domains. We also discuss its theoretical guarantees.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {565–600},
numpages = {36}
}

@article{10.5555/2444851.2444864,
author = {Garc\'{\i}a, Javier and Fern\'{a}ndez, Fernando},
title = {Safe Exploration of State and Action Spaces in Reinforcement Learning},
year = {2012},
issue_date = {September 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {45},
number = {1},
issn = {1076-9757},
abstract = {In this paper, we consider the important problem of safe exploration in reinforcement learning. While reinforcement learning is well-suited to domains with complex transition dynamics and high-dimensional state-action spaces, an additional challenge is posed by the need for safe and efficient exploration. Traditional exploration techniques are not particularly useful for solving dangerous tasks, where the trial and error process may lead to the selection of actions whose execution in some states may result in damage to the learning system (or any other system). Consequently, when an agent begins an interaction with a dangerous and high-dimensional state-action space, an important question arises; namely, that of how to avoid (or at least minimize) damage caused by the exploration of the state-action space. We introduce the PI-SRL algorithm which safely improves suboptimal albeit robust behaviors for continuous state and action control tasks and which efficiently learns from the experience gained from the environment. We evaluate the proposed method in four complex tasks: automatic car parking, pole-balancing, helicopter hovering, and business management.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {515–564},
numpages = {50}
}

@article{10.5555/2444851.2444863,
author = {Endriss, Ulle and Grandi, Umberto and Porello, Daniele},
title = {Complexity of Judgment Aggregation},
year = {2012},
issue_date = {September 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {45},
number = {1},
issn = {1076-9757},
abstract = {We analyse the computational complexity of three problems in judgment aggregation: (1) computing a collective judgment from a profile of individual judgments (the winner determination problem); (2) deciding whether a given agent can influence the outcome of a judgment aggregation procedure in her favour by reporting insincere judgments (the strategic manipulation problem); and (3) deciding whether a given judgment aggregation scenario is guaranteed to result in a logically consistent outcome, independently from what the judgments supplied by the individuals are (the problem of the safety of the agenda). We provide results both for specific aggregation procedures (the quota rules, the premisebased procedure, and a distance-based procedure) and for classes of aggregation procedures characterised in terms of fundamental axioms.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {481–514},
numpages = {34}
}

@article{10.5555/2444851.2444862,
author = {Ab\'{\i}o, Ignasi and Nieuwenhuis, Robert and Oliveras, Albert and Rodr\'{\i}guez-Carbonell, Enric and Mayer-Eichberger, Valentin},
title = {A New Look at BDDs for Pseudo-Boolean Constraints},
year = {2012},
issue_date = {September 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {45},
number = {1},
issn = {1076-9757},
abstract = {Pseudo-Boolean constraints are omnipresent in practical applications, and thus a significant effort has been devoted to the development of good SAT encoding techniques for them. Some of these encodings first construct a Binary Decision Diagram (BDD) for the constraint, and then encode the BDD into a propositional formula. These BDD-based approaches have some important advantages, such as not being dependent on the size of the coefficients, or being able to share the same BDD for representing many constraints. We first focus on the size of the resulting BDDs, which was considered to be an open problem in our research community. We report on previous work where it was proved that there are Pseudo-Boolean constraints for which no polynomial BDD exists. We also give an alternative and simpler proof assuming that NP is different from Co-NP. More interestingly, here we also show how to overcome the possible exponential blowup of BDDs by coefficient decomposition. This allows us to give the first polynomial generalized arc-consistent ROBDD-based encoding for Pseudo-Boolean constraints. Finally, we focus on practical issues: we show how to efficiently construct such ROBDDs, how to encode them into SAT with only 2 clauses per node, and present experimental results that confirm that our approach is competitive with other encodings and state-of-the-art Pseudo-Boolean solvers.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {443–480},
numpages = {38}
}

@article{10.5555/2444851.2444861,
author = {Rossi, Ryan A. and McDowell, Luke K. and Aha, David W. and Neville, Jennifer},
title = {Transforming Graph Data for Statistical Relational Learning},
year = {2012},
issue_date = {September 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {45},
number = {1},
issn = {1076-9757},
abstract = {Relational data representations have become an increasingly important topic due to the recent proliferation of network datasets (e.g., social, biological, information networks) and a corresponding increase in the application of Statistical Relational Learning (SRL) algorithms to these domains. In this article, we examine and categorize techniques for transforming graph-based relational data to improve SRL algorithms. In particular, appropriate transformations of the nodes, links, and/or features of the data can dramatically affect the capabilities and results of SRL algorithms. We introduce an intuitive taxonomy for data representation transformations in relational domains that incorporates link transformation and node transformation as symmetric representation tasks. More specifically, the transformation tasks for both nodes and links include (i) predicting their existence, (ii) predicting their label or type, (iii) estimating their weight or importance, and (iv) systematically constructing their relevant features. We motivate our taxonomy through detailed examples and use it to survey competing approaches for each of these tasks. We also discuss general conditions for transforming links, nodes, and features. Finally, we highlight challenges that remain to be addressed.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {363–441},
numpages = {79}
}

@article{10.5555/2444851.2444860,
author = {Rush, Alexander M. and Collins, Michael},
title = {A Tutorial on Dual Decomposition and Lagrangian Relaxation for Inference in Natural Language Processing},
year = {2012},
issue_date = {September 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {45},
number = {1},
issn = {1076-9757},
abstract = {Dual decomposition, and more generally Lagrangian relaxation, is a classical method for combinatorial optimization; it has recently been applied to several inference problems in natural language processing (NLP). This tutorial gives an overview of the technique. We describe example algorithms, describe formal guarantees for the method, and describe practical issues in implementing the algorithms. While our examples are predominantly drawn from the NLP literature, the material should be of general relevance to inference problems in machine learning. A central theme of this tutorial is that Lagrangian relaxation is naturally applied in conjunction with a broad class of combinatorial algorithms, allowing inference in models that go significantly beyond previous work on Lagrangian relaxation for inference in graphical models.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {305–362},
numpages = {58}
}

@article{10.5555/2444851.2444859,
author = {Gutierrez, Patricia and Meseguer, Pedro},
title = {Removing Redundant Messages in N-Ary BnB-ADOPT},
year = {2012},
issue_date = {September 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {45},
number = {1},
issn = {1076-9757},
abstract = {This note considers how to modify BnB-ADOPT, a well-known algorithm for optimally solving distributed constraint optimization problems, with a double aim: (i) to avoid sending most of the redundant messages and (ii) to handle cost functions of any arity. Some of the messages exchanged by BnB-ADOPT turned out to be redundant. Removing most of the redundant messages increases substantially communication efficiency: the number of exchanged messages is -in most cases-at least three times fewer (keeping the other measures almost unchanged), and termination and optimality are maintained. On the other hand, handling n-ary cost functions was addressed in the original work, but the presence of thresholds makes their practical usage more complex. Both issues -removing most of the redundant messages and efficiently handling n-ary cost functions- can be combined, producing the new version BnB-ADOPT+. Experimentally, we show the benefits of this version over the original one.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {287–304},
numpages = {18}
}

@article{10.5555/2444851.2444858,
author = {Hoshino, Richard and Kawarabayashi, Ken-ichi},
title = {Generating Approximate Solutions to the Traveling Tournament Problem Using a Linear Distance Relaxation},
year = {2012},
issue_date = {September 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {45},
number = {1},
issn = {1076-9757},
abstract = {In some domestic professional sports leagues, the home stadiums are located in cities connected by a common train line running in one direction. For these instances, we can incorporate this geographical information to determine optimal or nearly-optimal solutions to the We introduce the Linear Distance Traveling Tournament Problem (LD-TTP), and solve it for We conclude the paper by applying this linear distance relaxation to general (non-linear) },
journal = {J. Artif. Int. Res.},
month = sep,
pages = {257–286},
numpages = {30}
}

@article{10.5555/2444851.2444857,
author = {Grau, Bernardo Cuenca and Motik, Boris},
title = {Reasoning over Ontologies with Hidden Content: The Import-by-Query Approach},
year = {2012},
issue_date = {September 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {45},
number = {1},
issn = {1076-9757},
abstract = {There is currently a growing interest in techniques for hiding parts of the signature of an ontology κ },
journal = {J. Artif. Int. Res.},
month = sep,
pages = {197–255},
numpages = {59}
}

@article{10.5555/2444851.2444856,
author = {Voice, Thomas and Polukarov, Maria and Jennings, Nicholas R.},
title = {Coalition Structure Generation over Graphs},
year = {2012},
issue_date = {September 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {45},
number = {1},
issn = {1076-9757},
abstract = {We give the analysis of the computational complexity of coalition structure generation over graphs. Given an undirected graph },
journal = {J. Artif. Int. Res.},
month = sep,
pages = {165–196},
numpages = {32}
}

@article{10.5555/2444851.2444855,
author = {Mirroshandel, Seyed Abolghasem and Ghassem-Sani, Gholamreza},
title = {Towards Unsupervised Learning of Temporal Relations between Events},
year = {2012},
issue_date = {September 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {45},
number = {1},
issn = {1076-9757},
abstract = {Automatic extraction of temporal relations between event pairs is an important task for several natural language processing applications such as Question Answering, Information Extraction, and Summarization. Since most existing methods are supervised and require large corpora, which for many languages do not exist, we have concentrated our efforts to reduce the need for annotated data as much as possible. This paper presents two different algorithms towards this goal. The first algorithm is a weakly supervised machine learning approach for classification of temporal relations between events. In the first stage, the algorithm learns a general classifier from an annotated corpus. Then, inspired by the hypothesis of "one type of temporal relation per discourse", it extracts useful information from a cluster of topically related documents. We show that by combining the global information of such a cluster with local decisions of a general classifier, a bootstrapping cross-document classifier can be built to extract temporal relations between events. Our experiments show that without any additional annotated data, the accuracy of the proposed algorithm is higher than that of several previous successful systems. The second proposed method for temporal relation extraction is based on the expectation maximization (EM) algorithm. Within EM, we used different techniques such as a greedy best-first search and integer linear programming for temporal inconsistency removal. We think that the experimental results of our EM based algorithm, as a first step toward a fully unsupervised temporal relation extraction method, is encouraging.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {125–163},
numpages = {39}
}

@article{10.5555/2444851.2444854,
author = {Vlaeminck, Hanne and Vennekens, Joost and Denecker, Marc and Bruynooghe, Maurice},
title = {An Approximative Inference Method for Solving ∃∀SO Satisfiability Problems},
year = {2012},
issue_date = {September 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {45},
number = {1},
issn = {1076-9757},
abstract = {This paper considers the fragment ∃∀SO of second-order logic. Many interesting problems, such as conformant planning, can be naturally expressed as finite domain satisfiability problems of this logic. Such satisfiability problems are computationally hard (Σ },
journal = {J. Artif. Int. Res.},
month = sep,
pages = {79–124},
numpages = {46}
}

@article{10.5555/2444851.2444853,
author = {Cohen, David A. and Cooper, Martin C. and Creed, P\'{a}id\'{\i} and Marx, D\'{a}niel and Salamon, Andr\'{a}s Z.},
title = {The Tractability of CSP Classes Defined by Forbidden Patterns},
year = {2012},
issue_date = {September 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {45},
number = {1},
issn = {1076-9757},
abstract = {The constraint satisfaction problem (CSP) is a general problem central to computer science and artificial intelligence. Although the CSP is NP-hard in general, considerable effort has been spent on identifying tractable subclasses. The main two approaches consider structural properties (restrictions on the hypergraph of constraint scopes) and relational properties (restrictions on the language of constraint relations). Recently, some authors have considered hybrid properties that restrict the constraint hypergraph and the relations simultaneously.Our key contribution is the novel concept of a CSP pattern and classes of problems defined by forbidden patterns (which can be viewed as forbidding generic sub-problems). We describe the theoretical framework which can be used to reason about classes of problems defined by forbidden patterns. We show that this framework generalises certain known hybrid tractable classes.Although we are not close to obtaining a complete characterisation concerning the tractability of general forbidden patterns, we prove a dichotomy in a special case: classes of problems that arise when we can only forbid binary negative patterns (generic subproblems in which only disallowed tuples are specified). In this case we show that all (finite sets of) forbidden patterns define either polynomial-time solvable or NP-complete classes of instances.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {47–78},
numpages = {32}
}

@article{10.5555/2444851.2444852,
author = {Belardinelli, F. and Lomuscio, A.},
title = {Interactions between Knowledge and Time in a First-Order Logic for Multi-Agent Systems: Completeness Results},
year = {2012},
issue_date = {September 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {45},
number = {1},
issn = {1076-9757},
abstract = {We investigate a class of first-order temporal-epistemic logics for reasoning about multiagent systems. We encode typical properties of systems including perfect recall, synchronicity, no learning, and having a unique initial state in terms of variants of quantified interpreted systems, a first-order extension of interpreted systems. We identify several monodic fragments of first-order temporal-epistemic logic and show their completeness with respect to their corresponding classes of quantified interpreted systems.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {1–45},
numpages = {45}
}

@article{10.5555/2387933.2387948,
author = {Domshlak, Carmel and Karpas, Erez and Markovitch, Shaul},
title = {Online Speedup Learning for Optimal Planning},
year = {2012},
issue_date = {May 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {44},
number = {1},
issn = {1076-9757},
abstract = {Domain-independent planning is one of the foundational areas in the field of Artificial Intelligence. A description of a planning task consists of an initial world state, a goal, and a set of actions for modifying the world state. The objective is to find a sequence of actions, that is, a plan, that transforms the initial world state into a goal state. In optimal planning, we are interested in finding not just a plan, but one of the cheapest plans. A prominent approach to optimal planning these days is heuristic state-space search, guided by admissible heuristic functions. Numerous admissible heuristics have been developed, each with its own strengths and weaknesses, and it is well known that there is no single "best" heuristic for optimal planning in general. Thus, which heuristic to choose for a given planning task is a difficult question. This difficulty can be avoided by combining several heuristics, but that requires computing numerous heuristic estimates at each state, and the tradeoff between the time spent doing so and the time saved by the combined advantages of the different heuristics might be high. We present a novel method that reduces the cost of combining admissible heuristics for optimal planning, while maintaining its benefits. Using an idealized search space model, we formulate a decision rule for choosing the best heuristic to compute at each state. We then present an active online learning approach for learning a classifier with that decision rule as the target concept, and employ the learned classifier to decide which heuristic to compute at each state. We evaluate this technique empirically, and show that it substantially outperforms the standard method for combining several heuristics via their pointwise maximum.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {709–755},
numpages = {47}
}

@article{10.5555/2387933.2387947,
author = {Konev, Boris and Ludwig, Michel and Walther, Dirk and Wolter, Frank},
title = {The Logical Difference for the Lightweight Description Logic EL},
year = {2012},
issue_date = {May 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {44},
number = {1},
issn = {1076-9757},
abstract = {We study a logic-based approach to versioning of ontologies. Under this view, ontologies provide answers to queries about some vocabulary of interest. The difference between two versions of an ontology is given by the set of queries that receive difierent answers. We investigate this approach for terminologies given in the description logic EL extended with role inclusions and domain and range restrictions for three distinct types of queries: subsumption, instance, and conjunctive queries. In all three cases, we present polynomialtime algorithms that decide whether two terminologies give the same answers to queries over a given vocabulary and compute a succinct representation of the difference if it is nonempty. We present an implementation, CEX2, of the developed algorithms for subsumption and instance queries and apply it to distinct versions of Snomed CT and the NCI ontology.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {633–708},
numpages = {76}
}

@article{10.5555/2387933.2387946,
author = {Hoffmann, J\"{o}rg and Weber, Ingo and Kraft, Frank Michael},
title = {SAP Speaks PDDL: Exploiting a Software-Engineering Model for Planning in Business Process Management},
year = {2012},
issue_date = {May 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {44},
number = {1},
issn = {1076-9757},
abstract = {Planning is concerned with the automated solution of action sequencing problems described in declarative languages giving the action preconditions and effects. One important application area for such technology is the creation of new processes in Business Process Management (BPM), which is essential in an ever more dynamic business environment. A major obstacle for the application of Planning in this area lies in the modeling. Obtaining a suitable model to plan with - ideally a description in PDDL, the most commonly used planning language - is often prohibitively complicated and/or costly. Our core observation in this work is that this problem can be ameliorated by leveraging synergies with model-based software development. Our application at SAP, one of the leading vendors of enterprise software, demonstrates that even one-to-one model re-use is possible.The model in question is called Status and Action Management (SAM). It describes the behavior of Business Objects (BO), i.e., large-scale data structures, at a level of abstraction corresponding to the language of business experts. SAM covers more than 400 kinds of BOs, each of which is described in terms of a set of status variables and how their values are required for, and affected by, processing steps (actions) that are atomic from a business perspective. SAM was developed by SAP as part of a major model-based software engineering effort. We show herein that one can use this same model for planning, thus obtaining a BPM planning application that incurs no modeling overhead at all.We compile SAM into a variant of PDDL, and adapt an off-the-shelf planner to solve this kind of problem. Thanks to the resulting technology, business experts may create new processes simply by specifying the desired behavior in terms of status variable value changes: effectively, by describing the process in their own language.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {587–632},
numpages = {46}
}

@article{10.5555/2387933.2387945,
author = {Turney, Peter D.},
title = {Domain and Function: A Dual-Space Model of Semantic Relations and Compositions},
year = {2012},
issue_date = {May 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {44},
number = {1},
issn = {1076-9757},
abstract = {Given appropriate representations of the semantic relations between carpenter and wood and between mason and stone (for example, vectors in a vector space model), a suitable algorithm should be able to recognize that these relations are highly similar (carpenter is to wood as mason is to stone; the relations are analogous). Likewise, with representations of dog, house, and kennel, an algorithm should be able to recognize that the semantic composition of dog and house, dog house, is highly similar to kennel (dog house and kennel are synonymous). It seems that these two tasks, recognizing relations and compositions, are closely connected. However, up to now, the best models for relations are significantly different from the best models for compositions. In this paper, we introduce a dual-space model that unifies these two tasks. This model matches the performance of the best previous models for relations and compositions. The dual-space model consists of a space for measuring domain similarity and a space for measuring function similarity. Carpenter and wood share the same domain, the domain of carpentry. Mason and stone share the same domain, the domain of masonry. Carpenter and mason share the same function, the function of artisans. Wood and stone share the same function, the function of materials. In the composition dog house, kennel has some domain overlap with both dog and house (the domains of pets and buildings). The function of kennel is similar to the function of house (the function of shelters). By combining domain and function similarities in various ways, we can model relations, compositions, and other aspects of semantics.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {533–585},
numpages = {53}
}

@article{10.5555/2387933.2387944,
author = {Huang, Jonathan and Kapoor, Ashish and Guestrin, Carlos},
title = {Riffled Independence for Efficient Inference with Partial Rankings},
year = {2012},
issue_date = {May 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {44},
number = {1},
issn = {1076-9757},
abstract = {Distributions over rankings are used to model data in a multitude of real world settings such as preference analysis and political elections. Modeling such distributions presents several computational challenges, however, due to the factorial size of the set of rankings over an item set. Some of these challenges are quite familiar to the artificial intelligence community, such as how to compactly represent a distribution over a combinatorially large space, and how to efficiently perform probabilistic inference with these representations. With respect to ranking, however, there is the additional challenge of what we refer to as human task complexity -- users are rarely willing to provide a full ranking over a long list of candidates, instead often preferring to provide partial ranking information.Simultaneously addressing all of these challenges -- i.e., designing a compactly representable model which is amenable to efficient inference and can be learned using partial ranking data -- is a difficult task, but is necessary if we would like to scale to problems with nontrivial size. In this paper, we show that the recently proposed riffled independence assumptions cleanly and efficiently address each of the above challenges. In particular, we establish a tight mathematical connection between the concepts of riffled independence and of partial rankings. This correspondence not only allows us to then develop efficient and exact algorithms for performing inference tasks using riffled independence based representations with partial rankings, but somewhat surprisingly, also shows that efficient inference is not possible for riffle independent models (in a certain sense) with observations which do not take the form of partial rankings. Finally, using our inference algorithm, we introduce the first method for learning riffled independence based models from partially ranked data.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {491–532},
numpages = {42}
}

@article{10.5555/2387933.2387943,
author = {Cooper, Martin C. and \v{Z}ivn\'{y}, Stanislav},
title = {Tractable Triangles and Cross-Free Convexity in Discrete Optimisation},
year = {2012},
issue_date = {May 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {44},
number = {1},
issn = {1076-9757},
abstract = {The minimisation problem of a sum of unary and pairwise functions of discrete variables is a general NP-hard problem with wide applications such as computing MAP configurations in Markov Random Fields (MRF), minimising Gibbs energy, or solving binary Valued Constraint Satisfaction Problems (VCSPs).We study the computational complexity of classes of discrete optimisation problems given by allowing only certain types of costs in every triangle of variable-value assignments to three distinct variables. We show that for several computational problems, the only non-trivial tractable classes are the well known maximum matching problem and the recently discovered joint-winner property. Our results, apart from giving complete classifications in the studied cases, provide guidance in the search for hybrid tractable classes; that is, classes of problems that are not captured by restrictions on the functions (such as submodularity) or the structure of the problem graph (such as bounded treewidth).Furthermore, we introduce a class of problems with convex cardinality functions on cross-free sets of assignments. We prove that while imposing only one of the two conditions renders the problem NP-hard, the conjunction of the two gives rise to a novel tractable class satisfying the cross-free convexity property, which generalises the joint-winner property to problems of unbounded arity.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {455–490},
numpages = {36}
}

@article{10.5555/2387933.2387942,
author = {Albacete, Esperanza and Calle, Javier and Castro, Elena and Cuadra, Dolores},
title = {Semantic Similarity Measures Applied to an Ontology for Human-like Interaction},
year = {2012},
issue_date = {May 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {44},
number = {1},
issn = {1076-9757},
abstract = {The focus of this paper is the calculation of similarity between two concepts from an ontology for a Human-Like Interaction system. In order to facilitate this calculation, a similarity function is proposed based on five dimensions (sort, compositional, essential, restrictive and descriptive) constituting the structure of ontological knowledge. The paper includes a proposal for computing a similarity function for each dimension of knowledge. Later on, the similarity values obtained are weighted and aggregated to obtain a global similarity measure. In order to calculate those weights associated to each dimension, four training methods have been proposed. The training methods differ in the element to fit: the user, concepts or pairs of concepts, and a hybrid approach. For evaluating the proposal, the knowledge base was fed from Word Net and extended by using a knowledge editing toolkit (Cognos). The evaluation of the proposal is carried out through the comparison of system responses with those given by human test subjects, both providing a measure of the soundness of the procedure and revealing ways in which the proposal may be improved.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {397–421},
numpages = {25}
}

@article{10.5555/2387933.2387941,
author = {Haslum, Patrik},
title = {Narrative Planning: Compilations to Classical Planning},
year = {2012},
issue_date = {May 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {44},
number = {1},
issn = {1076-9757},
abstract = {A model of story generation recently proposed by Riedl and Young casts it as planning, with the additional condition that story characters behave intentionally. This means that characters have perceivable motivation for the actions they take. I show that this condition can be compiled away (in more ways than one) to produce a classical planning problem that can be solved by an off-the-shelf classical planner, more efficiently than by Riedl and Young's specialised planner.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {383–395},
numpages = {13}
}

@article{10.5555/2387933.2387940,
author = {Fox, Maria and Long, Derek and Magazzeni, Daniele},
title = {Plan-Based Policies for Efficient Multiple Battery Load Management},
year = {2012},
issue_date = {May 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {44},
number = {1},
issn = {1076-9757},
abstract = {Efficient use of multiple batteries is a practical problem with wide and growing application. The problem can be cast as a planning problem under uncertainty. We describe the approach we have adopted to modelling and solving this problem, seen as a Markov Decision Problem, building effective policies for battery switching in the face of stochastic load profiles.Our solution exploits and adapts several existing techniques: planning for deterministic mixed discrete-continuous problems and Monte Carlo sampling for policy learning. The paper describes the development of planning techniques to allow solution of the non-linear continuous dynamic models capturing the battery behaviours. This approach depends on carefully handled discretisation of the temporal dimension. The construction of policies is performed using a classification approach and this idea offers opportunities for wider exploitation in other problems. The approach and its generality are described in the paper.Application of the approach leads to construction of policies that, in simulation, significantly outperform those that are currently in use and the best published solutions to the battery management problem. We achieve solutions that achieve more than 99% efficiency in simulation compared with the theoretical limit and do so with far fewer battery switches than existing policies. Behaviour of physical batteries does not exactly match the simulated models for many reasons, so to confirm that our theoretical results can lead to real measured improvements in performance we also conduct and report experiments using a physical test system. These results demonstrate that we can obtain 5%-15% improvement in lifetimes in the case of a two battery system.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {335–382},
numpages = {48}
}

@article{10.5555/2387933.2387939,
author = {Ghosh, Priyankar and Sharma, Amit and Chakrabarti, P. P. and Dasgupta, Pallab},
title = {Algorithms for Generating Ordered Solutions for Explicit and/or Structures},
year = {2012},
issue_date = {May 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {44},
number = {1},
issn = {1076-9757},
abstract = {We present algorithms for generating alternative solutions for explicit acyclic AND/OR structures in non-decreasing order of cost. The proposed algorithms use a best first search technique and report the solutions using an implicit representation ordered by cost. In this paper, we present two versions of the search algorithm - (a) an initial version of the best first search algorithm, ASG, which may present one solution more than once while generating the ordered solutions, and (b) another version, LASG, which avoids the construction of the duplicate solutions. The actual solutions can be reconstructed quickly from the implicit compact representation used. We have applied the methods on a few test domains, some of them are synthetic while the others are based on well known problems including the search space of the 5-peg Tower of Hanoi problem, the matrix-chain multiplication problem and the problem of finding secondary structure of RNA. Experimental results show the efficacy of the proposed algorithms over the existing approach. Our proposed algorithms have potential use in various domains ranging from knowledge based frameworks to service composition, where the AND/OR structure is widely used for representing problems.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {275–333},
numpages = {59}
}

@article{10.5555/2387933.2387938,
author = {Mao, Wenji and Gratch, Jonathan},
title = {Modeling Social Causality and Responsibility Judgment in Multi-Agent Interactions},
year = {2012},
issue_date = {May 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {44},
number = {1},
issn = {1076-9757},
abstract = {Social causality is the inference an entity makes about the social behavior of other entities and self. Besides physical cause and effect, social causality involves reasoning about epistemic states of agents and coercive circumstances. Based on such inference, responsibility judgment is the process whereby one singles out individuals to assign responsibility, credit or blame for multi-agent activities. Social causality and responsibility judgment are a key aspect of social intelligence, and a model for them facilitates the design and development of a variety of multi-agent interactive systems. Based on psychological attribution theory, this paper presents a domain-independent computational model to automate social inference and judgment process according to an agent's causal knowledge and observations of interaction. We conduct experimental studies to empirically validate the computational model. The experimental results show that our model predicts human judgments of social attributions and makes inferences consistent with what most people do in their judgments. Therefore, the proposed model can be generically incorporated into an intelligent system to augment its social and cognitive functionality.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {223–273},
numpages = {51}
}

@article{10.5555/2387933.2387937,
author = {Nakov, Preslav and Ng, Hwee Tou},
title = {Improving Statistical Machine Translation for a Resource-Poor Language Using Related Resource-Rich Languages},
year = {2012},
issue_date = {May 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {44},
number = {1},
issn = {1076-9757},
abstract = {We propose a novel language-independent approach for improving machine translation for resource-poor languages by exploiting their similarity to resource-rich ones. More precisely, we improve the translation from a resource-poor source language X1 into a resourcerich language Y given a bi-text containing a limited number of parallel sentences for X1-Y and a larger bi-text for X2-Y for some resource-rich language X2 that is closely related to X1. This is achieved by taking advantage of the opportunities that vocabulary overlap and similarities between the languages X1 and X2 in spelling, word order, and syntax offer: (1) we improve the word alignments for the resource-poor language, (2) we further augment it with additional translation options, and (3) we take care of potential spelling differences through appropriate transliteration. The evaluation for Indonesian → English using Malay and for Spanish → English using Portuguese and pretending Spanish is resource-poor shows an absolute gain of up to 1.35 and 3.37 BLEU points, respectively, which is an improvement over the best rivaling approaches, while using much less additional data. Overall, our method cuts the amount of necessary "real" training data by a factor of 2-5.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {179–222},
numpages = {44}
}

@article{10.5555/2387933.2387936,
author = {B\"{a}ckstr\"{o}m, Christer and Jonsson, Peter},
title = {Algorithms and Limits for Compact Plan Representations},
year = {2012},
issue_date = {May 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {44},
number = {1},
issn = {1076-9757},
abstract = {Compact representations of objects is a common concept in computer science. Automated planning can be viewed as a case of this concept: a planning instance is a compact implicit representation of a graph and the problem is to find a path (a plan) in this graph. While the graphs themselves are represented compactly as planning instances, the paths are usually represented explicitly as sequences of actions. Some cases are known where the plans always have compact representations, for example, using macros. We show that these results do not extend to the general case, by proving a number of bounds for compact representations of plans under various criteria, like efficient sequential or random access of actions. In addition to this, we show that our results have consequences for what can be gained from reformulating planning into some other problem. As a contrast to this we also prove a number of positive results, demonstrating restricted cases where plans do have useful compact representations, as well as proving that macro plans have favourable access properties. Our results are finally discussed in relation to other relevant contexts.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {141–177},
numpages = {37}
}

@article{10.5555/2387933.2387935,
author = {Mau\'{a}, Denis Deratani and de Campos, Cassio Polpo and Zaffalon, Marco},
title = {Solving Limited Memory Influence Diagrams},
year = {2012},
issue_date = {May 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {44},
number = {1},
issn = {1076-9757},
abstract = {We present a new algorithm for exactly solving decision making problems represented as influence diagrams. We do not require the usual assumptions of no forgetting and regularity; this allows us to solve problems with simultaneous decisions and limited information. The algorithm is empirically shown to outperform a state-of-the-art algorithm on randomly generated problems of up to 150 variables and 1064 solutions. We show that these problems are NP-hard even if the underlying graph structure of the problem has low treewidth and the variables take on a bounded number of states, and that they admit no provably good approximation if variables can take on an arbitrary number of states.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {97–140},
numpages = {44}
}

@article{10.5555/2387933.2387934,
author = {Coles, Amanda and Coles, Andrew and Fox, Maria and Long, Derek},
title = {COLIN: Planning with Continuous Linear Numeric Change},
year = {2012},
issue_date = {May 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {44},
number = {1},
issn = {1076-9757},
abstract = {In this paper we describe COLIN, a forward-chaining heuristic search planner, capable of reasoning with COntinuous LINear numeric change, in addition to the full temporal semantics of PDDL2.1. Through this work we make two advances to the state-of-the-art in terms of expressive reasoning capabilities of planners: the handling of continuous linear change, and the handling of duration-dependent effects in combination with duration inequalities, both of which require tightly coupled temporal and numeric reasoning during planning. COLIN combines FF-style forward chaining search, with the use of a Linear Program (LP) to check the consistency of the interacting temporal and numeric constraints at each state. The LP is used to compute bounds on the values of variables in each state, reducing the range of actions that need to be considered for application. In addition, we develop an extension of the Temporal Relaxed Planning Graph heuristic of CRIKEY3, to support reasoning directly with continuous change. We extend the range of task variables considered to be suitable candidates for specifying the gradient of the continuous numeric change effected by an action. Finally, we explore the potential for employing mixed integer programming as a tool for optimising the timestamps of the actions in the plan, once a solution has been found. To support this, we further contribute a selection of extended benchmark domains that include continuous numeric effects. We present results for COLIN that demonstrate its scalability on a range of benchmarks, and compare to existing state-of-the-art planners.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {1–96},
numpages = {96}
}

@article{10.5555/2387915.2387932,
author = {Branavan, S. R. K. and Silver, David and Barzilay, Regina},
title = {Learning to Win by Reading Manuals in a Monte-Carlo Framework},
year = {2012},
issue_date = {January 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {43},
number = {1},
issn = {1076-9757},
abstract = {Domain knowledge is crucial for effective performance in autonomous control systems. Typically, human effort is required to encode this knowledge into a control algorithm. In this paper, we present an approach to language grounding which automatically interprets text in the context of a complex control application, such as a game, and uses domain knowledge extracted from the text to improve control performance. Both text analysis and control strategies are learned jointly using only a feedback signal inherent to the application. To effectively leverage textual information, our method automatically extracts the text segment most relevant to the current game state, and labels it with a task-centric predicate structure. This labeled text is then used to bias an action selection policy for the game, guiding it towards promising regions of the action space. We encode our model for text analysis and game playing in a multi-layer neural network, representing linguistic decisions via latent variables in the hidden layers, and game action quality via the output layer. Operating within the Monte-Carlo Search framework, we estimate model parameters using feedback from simulated games. We apply our approach to the complex strategy game Civilization II using the official game manual as the text guide. Our results show that a linguistically-informed game-playing agent significantly outperforms its language-unaware counterpart, yielding a 34% absolute improvement and winning over 65% of games when playing against the built-in AI of Civilization.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {661–704},
numpages = {44}
}

@article{10.5555/2387915.2387931,
author = {Vasirani, Matteo and Ossowski, Sascha},
title = {A Market-Inspired Approach for Intersection Management in Urban Road Traffic Networks},
year = {2012},
issue_date = {January 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {43},
number = {1},
issn = {1076-9757},
abstract = {Traffic congestion in urban road networks is a costly problem that affects all major cities in developed countries. To tackle this problem, it is possible (i) to act on the supply side, increasing the number of roads or lanes in a network, (ii) to reduce the demand, restricting the access to urban areas at specific hours or to specific vehicles, or (iii) to improve the efficiency of the existing network, by means of a widespread use of so-called Intelligent Transportation Systems (ITS). In line with the recent advances in smart transportation management infrastructures, ITS has turned out to be a promising field of application for artificial intelligence techniques. In particular, multiagent systems seem to be the ideal candidates for the design and implementation of ITS. In fact, drivers can be naturally modelled as autonomous agents that interact with the transportation management infrastructure, thereby generating a large-scale, open, agent-based system. To regulate such a system and maintain a smooth and efficient flow of traffic, decentralised mechanisms for the management of the transportation infrastructure are needed.In this article we propose a distributed, market-inspired, mechanism for the management of a future urban road network, where intelligent autonomous vehicles, operated by software agents on behalf of their human owners, interact with the infrastructure in order to travel safely and efficiently through the road network. Building on the reservationbased intersection control model proposed by Dresner and Stone, we consider two different scenarios: one with a single intersection and one with a network of intersections. In the former, we analyse the performance of a novel policy based on combinatorial auctions for the allocation of reservations. In the latter, we analyse the impact that a traffic assignment strategy inspired by competitive markets has on the drivers' route choices. Finally we propose an adaptive management mechanism that integrates the auction-based traffic control policy with the competitive traffic assignment strategy.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {621–659},
numpages = {39}
}

@article{10.5555/2387915.2387930,
author = {Lee, Joohyung and Palla, Ravi},
title = {Reformulating the Situation Calculus and the Event Calculus in the General Theory of Stable Models and in Answer Set Programming},
year = {2012},
issue_date = {January 2012},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {43},
number = {1},
issn = {1076-9757},
abstract = {Circumscription and logic programs under the stable model semantics are two wellknown nonmonotonic formalisms. The former has served as a basis of classical logic based action formalisms, such as the situation calculus, the event calculus and temporal action logics; the latter has served as a basis of a family of action languages, such as language A and several of its descendants. Based on the discovery that circumscription and the stable model semantics coincide on a class

license: Unlicense

repository: goyalkaraniit/acm-cr

repo_name: goyalkaraniit/acm-cr