text:
@article{10.5555/2051237.2051248,
author = {Kurland, Oren and Krikon, Eyal},
title = {The Opposite of Smoothing: A Language Model Approach to Ranking Query-Specific Document Clusters},
year = {2011},
issue_date = {May 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {41},
number = {2},
issn = {1076-9757},
abstract = {Exploiting information induced from (query-specific) clustering of top-retrieved documents has long been proposed as a means for improving precision at the very top ranks of the returned results. We present a novel language model approach to ranking query-specific clusters by the presumed percentage of relevant documents that they contain. While most previous cluster ranking approaches focus on the cluster as a whole, our model utilizes also information induced from documents associated with the cluster. Our model substantially outperforms previous approaches for identifying clusters containing a high relevant-document percentage. Furthermore, using the model to produce document ranking yields precision-at-top-ranks performance that is consistently better than that of the initial ranking upon which clustering is performed. The performance also favorably compares with that of a state-of-the-art pseudo-feedback-based retrieval method.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {367–395},
numpages = {29}
}

@article{10.5555/2051237.2051247,
author = {Siddiqi, Sajjad and Huang, Jinbo},
title = {Sequential Diagnosis by Abstraction},
year = {2011},
issue_date = {May 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {41},
number = {2},
issn = {1076-9757},
abstract = {When a system behaves abnormally, sequential diagnosis takes a sequence of measurements of the system until the faults causing the abnormality are identified, and the goal is to reduce the diagnostic cost, defined here as the number of measurements. To propose measurement points, previous work employs a heuristic based on reducing the entropy over a computed set of diagnoses. This approach generally has good performance in terms of diagnostic cost, but can fail to diagnose large systems when the set of diagnoses is too large. Focusing on a smaller set of probable diagnoses scales the approach but generally leads to increased average diagnostic costs. In this paper, we propose a new diagnostic framework employing four new techniques, which scales to much larger systems with good performance in terms of diagnostic cost. First, we propose a new heuristic for measurement point selection that can be computed efficiently, without requiring the set of diagnoses, once the system is modeled as a Bayesian network and compiled into a logical form known as d-DNNF. Second, we extend hierarchical diagnosis, a technique based on system abstraction from our previous work, to handle probabilities so that it can be applied to sequential diagnosis to allow larger systems to be diagnosed. Third, for the largest systems where even hierarchical diagnosis fails, we propose a novel method that converts the system into one that has a smaller abstraction and whose diagnoses form a superset of those of the original system; the new system can then be diagnosed and the result mapped back to the original system. Finally, we propose a novel cost estimation function which can be used to choose an abstraction of the system that is more likely to provide optimal average cost. Experiments with ISCAS-85 benchmark circuits indicate that our approach scales to all circuits in the suite except one that has a flat structure not susceptible to useful abstraction.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {329–365},
numpages = {37}
}

@article{10.5555/2051237.2051246,
author = {Korzhyk, Dmytro and Yin, Zhengyu and Kiekintveld, Christopher and Conitzer, Vincent and Tambe, Milind},
title = {Stackelberg vs. Nash in Security Games: An Extended Investigation of Interchangeability, Equivalence, and Uniqueness},
year = {2011},
issue_date = {May 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {41},
number = {2},
issn = {1076-9757},
abstract = {There has been significant recent interest in game-theoretic approaches to security, with much of the recent research focused on utilizing the leader-follower Stackelberg game model. Among the major applications are the ARMOR program deployed at LAX Airport and the IRIS program in use by the US Federal Air Marshals (FAMS). The foundational assumption for using Stackelberg games is that security forces (leaders), acting first, commit to a randomized strategy; while their adversaries (followers) choose their best response after surveillance of this randomized strategy. Yet, in many situations, a leader may face uncertainty about the follower's surveillance capability. Previous work fails to address how a leader should compute her strategy given such uncertainty.We provide five contributions in the context of a general class of security games. First, we show that the Nash equilibria in security games are interchangeable, thus alleviating the equilibrium selection problem. Second, under a natural restriction on security games, any Stackelberg strategy is also a Nash equilibrium strategy; and furthermore, the solution is unique in a class of security games of which ARMOR is a key exemplar. Third, when faced with a follower that can attack multiple targets, many of these properties no longer hold. Fourth, we show experimentally that in most (but not all) games where the restriction does not hold, the Stackelberg strategy is still a Nash equilibrium strategy, but this is no longer true when the attacker can attack multiple targets. Finally, as a possible direction for future research, we propose an extensive-form game model that makes the defender's uncertainty about the attacker's ability to observe explicit.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {297–327},
numpages = {31}
}

@article{10.5555/2051237.2051245,
author = {Kozorovitsky, Anna Khudyak and Kurland, Oren},
title = {From "Identical" to "Similar": Fusing Retrieved Lists Based on Inter-Document Similarities},
year = {2011},
issue_date = {May 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {41},
number = {2},
issn = {1076-9757},
abstract = {Methods for fusing document lists that were retrieved in response to a query often utilize the retrieval scores and/or ranks of documents in the lists. We present a novel fusion approach that is based on using, in addition, information induced from inter-document similarities. Specifically, our methods let similar documents from different lists provide relevance-status support to each other. We use a graph-based method to model relevance-status propagation between documents. The propagation is governed by inter-document-similarities and by retrieval scores of documents in the lists. Empirical evaluation demonstrates the effectiveness of our methods in fusing TREC runs. The performance of our most effective methods transcends that of effective fusion methods that utilize only retrieval scores or ranks.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {267–296},
numpages = {30}
}

@article{10.5555/2051237.2051244,
author = {Joshi, Saket and Khardon, Roni},
title = {Probabilistic Relational Planning with First Order Decision Diagrams},
year = {2011},
issue_date = {May 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {41},
number = {2},
issn = {1076-9757},
abstract = {Dynamic programming algorithms have been successfully applied to propositional stochastic planning problems by using compact representations, in particular algebraic decision diagrams, to capture domain dynamics and value functions. Work on symbolic dynamic programming lifted these ideas to first order logic using several representation schemes. Recent work introduced a first order variant of decision diagrams (FODD) and developed a value iteration algorithm for this representation. This paper develops several improvements to the FODD algorithm that make the approach practical. These include, new reduction operators that decrease the size of the representation, several speedup techniques, and techniques for value approximation. Incorporating these, the paper presents a planning system, FODD-PLANNER, for solving relational stochastic planning problems. The system is evaluated on several domains, including problems from the recent international planning competition, and shows competitive performance with top ranking systems. This is the first demonstration of feasibility of this approach and it shows that abstraction through compact representation is a promising approach to stochastic planning.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {231–266},
numpages = {36}
}

@article{10.5555/2051237.2051243,
author = {Hoffmann, J\"{o}rg},
title = {Analyzing Search Topology without Running Any Search: On the Connection between Causal Graphs and h<sup>+</sup>},
year = {2011},
issue_date = {May 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {41},
number = {2},
issn = {1076-9757},
abstract = {The ignoring delete lists relaxation is of paramount importance for both satisficing and optimal planning. In earlier work, it was observed that the optimal relaxation heuristic h+ has amazing qualities in many classical planning benchmarks, in particular pertaining to the complete absence of local minima. The proofs of this are hand-made, raising the question whether such proofs can be lead automatically by domain analysis techniques. In contrast to earlier disappointing results - the analysis method has exponential runtime and succeeds only in two extremely simple benchmark domains - we herein answer this question in the afirmative. We establish connections between causal graph structure and h+ topology. This results in low-order polynomial time analysis methods, implemented in a tool we call TorchLight. Of the 12 domains where the absence of local minima has been proved, TorchLight gives strong success guarantees in 8 domains. Empirically, its analysis exhibits strong performance in a further 2 of these domains, plus in 4 more domains where local minima may exist but are rare. In this way, TorchLight can distinguish "easy" domains from "hard" ones. By summarizing structural reasons for analysis failure, TorchLight also provides diagnostic output indicating domain aspects that may cause local minima.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {155–229},
numpages = {75}
}

@article{10.5555/2051237.2051242,
author = {Gujar, Sujit and Narahari, Y.},
title = {Redistribution Mechanisms for Assignment of Heterogeneous Objects},
year = {2011},
issue_date = {May 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {41},
number = {2},
issn = {1076-9757},
abstract = {There are p heterogeneous objects to be assigned to n competing agents (n > p) each with unit demand. It is required to design a Groves mechanism for this assignment problem satisfying weak budget balance, individual rationality, and minimizing the budget imbalance. This calls for designing an appropriate rebate function. When the objects are identical, this problem has been solved which we refer as WCO mechanism. We measure the performance of such mechanisms by the redistribution index. We first prove an impossibility theorem which rules out linear rebate functions with non-zero redistribution index in heterogeneous object assignment. Motivated by this theorem, we explore two approaches to get around this impossibility. In the first approach, we show that linear rebate functions with non-zero redistribution index are possible when the valuations for the objects have a certain type of relationship and we design a mechanism with linear rebate function that is worst case optimal. In the second approach, we show that rebate functions with non-zero efficiency are possible if linearity is relaxed. We extend the rebate functions of the WCO mechanism to heterogeneous objects assignment and conjecture them to be worst case optimal.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {131–154},
numpages = {24}
}

@article{10.5555/2051237.2051241,
author = {Hebrard, Emmanuel and Marx, D\'{a}niel and O'Sullivan, Barry and Razgon, Igor},
title = {Soft Constraints of Difference and Equality},
year = {2011},
issue_date = {May 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {41},
number = {2},
issn = {1076-9757},
abstract = {In many combinatorial problems one may need to model the diversity or similarity of sets of assignments. For example, one may wish to maximise or minimise the number of distinct values in a solution. To formulate problems of this type we can use soft variants of the well known ALLDIFFERENT and ALLEQUAL constraints. We present a taxonomy of six soft global constraints, generated by combining the two latter ones and the two standard cost functions, which are either maximised or minimised. We characterise the complexity of achieving arc and bounds consistency on these constraints, resolving those cases for which NP-hardness was neither proven nor disproven. In particular, we explore in depth the constraint ensuring that at least k pairs of variables have a common value. We show that achieving arc consistency is NP-hard, however bounds consistency can be achieved in polynomial time through dynamic programming. Moreover, we show that the maximum number of pairs of equal variables can be approximated by a factor of 1/2 with a linear time greedy algorithm. Finally, we provide a fixed parameter tractable algorithm with respect to the number of values appearing in more than two distinct domains. Interestingly, this taxonomy shows that enforcing equality is harder than enforcing difference.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {97–130},
numpages = {34}
}

@article{10.5555/2051237.2051240,
author = {Bilgic, Mustafa and Getoor, Lise},
title = {Value of Information Lattice: Exploiting Probabilistic Independence for Effective Feature Subset Acquisition},
year = {2011},
issue_date = {May 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {41},
number = {2},
issn = {1076-9757},
abstract = {We address the cost-sensitive feature acquisition problem, where misclassifying an instance is costly but the expected misclassification cost can be reduced by acquiring the values of the missing features. Because acquiring the features is costly as well, the objective is to acquire the right set of features so that the sum of the feature acquisition cost and misclassification cost is minimized. We describe the Value of Information Lattice (VOILA), an optimal and eficient feature subset acquisition framework. Unlike the common practice, which is to acquire features greedily, VOILA can reason with subsets of features. VOILA eficiently searches the space of possible feature subsets by discovering and exploiting conditional independence properties between the features and it reuses probabilistic inference computations to further speed up the process. Through empirical evaluation on five medical datasets, we show that the greedy strategy is often reluctant to acquire features, as it cannot forecast the benefit of acquiring multiple features in combination.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {69–95},
numpages = {27}
}

@article{10.5555/2051237.2051239,
author = {Xia, Lirong and Conitzer, Vincent},
title = {Determining Possible and Necessary Winners under Common Voting Rules given Partial Orders},
year = {2011},
issue_date = {May 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {41},
number = {2},
issn = {1076-9757},
abstract = {Usually a voting rule requires agents to give their preferences as linear orders. However, in some cases it is impractical for an agent to give a linear order over all the alternatives. It has been suggested to let agents submit partial orders instead. Then, given a voting rule, a profile of partial orders, and an alternative (candidate) c, two important questions arise: first, is it still possible for c to win, and second, is c guaranteed to win? These are the possible winner and necessary winner problems, respectively. Each of these two problems is further divided into two sub-problems: determining whether c is a unique winner (that is, c is the only winner), or determining whether c is a co-winner (that is, c is in the set of winners).We consider the setting where the number of alternatives is unbounded and the votes are unweighted. We completely characterize the complexity of possible/necessary winner problems for the following common voting rules: a class of positional scoring rules (including Borda), Copeland, maximin, Bucklin, ranked pairs, voting trees, and plurality with runoff.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {25–67},
numpages = {43}
}

@article{10.5555/2051237.2051238,
author = {Cseke, Botond and Heskes, Tom},
title = {Properties of Bethe Free Energies and Message Passing in Gaussian Models},
year = {2011},
issue_date = {May 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {41},
number = {2},
issn = {1076-9757},
abstract = {We address the problem of computing approximate marginals in Gaussian probabilistic models by using mean field and fractional Bethe approximations. We define the Gaussian fractional Bethe free energy in terms of the moment parameters of the approximate marginals, derive a lower and an upper bound on the fractional Bethe free energy and establish a necessary condition for the lower bound to be bounded from below. It turns out that the condition is identical to the pairwise normalizability condition, which is known to be a sufficient condition for the convergence of the message passing algorithm. We show that stable fixed points of the Gaussian message passing algorithm are local minima of the Gaussian Bethe free energy. By a counterexample, we disprove the conjecture stating that the unboundedness of the free energy implies the divergence of the message passing algorithm.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {1–24},
numpages = {24}
}

@article{10.5555/2016945.2016967,
author = {Papadopoulos, Harris and Vovk, Vladimir and Gammerman, Alex},
title = {Regression Conformal Prediction with Nearest Neighbours},
year = {2011},
issue_date = {January 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {40},
number = {1},
issn = {1076-9757},
abstract = {In this paper we apply Conformal Prediction (CP) to the k-Nearest Neighbours Regression (k-NNR) algorithm and propose ways of extending the typical nonconformity measure used for regression so far. Unlike traditional regression methods which produce point predictions, Conformal Predictors output predictive regions that satisfy a given confidence level. The regions produced by any Conformal Predictor are automatically valid, however their tightness and therefore usefulness depends on the nonconformity measure used by each CP. In effect a nonconformity measure evaluates how strange a given example is compared to a set of other examples based on some traditional machine learning algorithm. We define six novel nonconformity measures based on the k-Nearest Neighbours Regression algorithm and develop the corresponding CPs following both the original (transductive) and the inductive CP approaches. A comparison of the predictive regions produced by our measures with those of the typical regression measure suggests that a major improvement in terms of predictive region tightness is achieved by the new measures.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {815–840},
numpages = {26}
}

@article{10.5555/2016945.2016966,
author = {de la Rosa, Tom\'{a}s and Jim\'{e}nez, Sergio and Fuentetaja, Raquel and Borrajo, Daniel},
title = {Scaling up Heuristic Planning with Relational Decision Trees},
year = {2011},
issue_date = {January 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {40},
number = {1},
issn = {1076-9757},
abstract = {Current evaluation functions for heuristic planning are expensive to compute. In numerous planning problems these functions provide good guidance to the solution, so they are worth the expense. However, when evaluation functions are misguiding or when planning problems are large enough, lots of node evaluations must be computed, which severely limits the scalability of heuristic planners. In this paper, we present a novel solution for reducing node evaluations in heuristic planning based on machine learning. Particularly, we define the task of learning search control for heuristic planning as a relational classification task, and we use an off-the-shelf relational classification tool to address this learning task. Our relational classification task captures the preferred action to select in the different planning contexts of a specific planning domain. These planning contexts are defined by the set of helpful actions of the current state, the goals remaining to be achieved, and the static predicates of the planning task. This paper shows two methods for guiding the search of a heuristic planner with the learned classifiers. The first one consists of using the resulting classifier as an action policy. The second one consists of applying the classifier to generate lookahead states within a Best First Search algorithm. Experiments over a variety of domains reveal that our heuristic planner using the learned classifiers solves larger problems than state-of-the-art planners.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {767–813},
numpages = {47}
}

@article{10.5555/2016945.2016965,
author = {Li, Wei and Poupart, Pascal and van Beek, Peter},
title = {Exploiting Structure in Weighted Model Counting Approaches to Probabilistic Inference},
year = {2011},
issue_date = {January 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {40},
number = {1},
issn = {1076-9757},
abstract = {Previous studies have demonstrated that encoding a Bayesian network into a SAT formula and then performing weighted model counting using a backtracking search algorithm can be an effective method for exact inference. In this paper, we present techniques for improving this approach for Bayesian networks with noisy-OR and noisy-MAX relations-- two relations that are widely used in practice as they can dramatically reduce the number of probabilities one needs to specify. In particular, we present two SAT encodings for noisy-OR and two encodings for noisy-MAX that exploit the structure or semantics of the relations to improve both time and space efficiency, and we prove the correctness of the encodings. We experimentally evaluated our techniques on large-scale real and randomly generated Bayesian networks. On these benchmarks, our techniques gave speedups of up to two orders of magnitude over the best previous approaches for networks with noisy-OR/MAX relations and scaled up to larger networks. As well, our techniques extend the weighted model counting approach for exact inference to networks that were previously intractable for the approach.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {729–765},
numpages = {37}
}

@article{10.5555/2016945.2016964,
author = {Cimatti, Alessandro and Griggio, Alberto and Sebastiani, Roberto},
title = {Computing Small Unsatisfiable Cores in Satisfiability modulo Theories},
year = {2011},
issue_date = {January 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {40},
number = {1},
issn = {1076-9757},
abstract = {The problem of finding small unsatisfiable cores for SAT formulas has recently received a lot of interest, mostly for its applications in formal verification. However, propositional logic is often not expressive enough for representing many interesting verification problems, which can be more naturally addressed in the framework of Satisfiability Modulo Theories, SMT. Surprisingly, the problem of finding unsatisfiable cores in SMT has received very little attention in the literature.In this paper we present a novel approach to this problem, called the Lemma-Lifting approach. The main idea is to combine an SMT solver with an external propositional core extractor. The SMT solver produces the theory lemmas found during the search, dynamically lifting the suitable amount of theory information to the Boolean level. The core extractor is then called on the Boolean abstraction of the original SMT problem and of the theory lemmas. This results in an unsatisfiable core for the original SMT problem, once the remaining theory lemmas are removed.The approach is conceptually interesting, and has several advantages in practice. In fact, it is extremely simple to implement and to update, and it can be interfaced with every propositional core extractor in a plug-and-play manner, so as to benefit for free of all unsat-core reduction techniques which have been or will be made available.We have evaluated our algorithm with a very extensive empirical test on SMT-LIB benchmarks, which confirms the validity and potential of this approach.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {701–728},
numpages = {28}
}

@article{10.5555/2016945.2016963,
author = {Wu, Fei and Madhavan, Jayant and Halevy, Alon},
title = {Identifying Aspects for Web-Search Queries},
year = {2011},
issue_date = {January 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {40},
number = {1},
issn = {1076-9757},
abstract = {Many web-search queries serve as the beginning of an exploration of an unknown space of information, rather than looking for a specific web page. To answer such queries effectively, the search engine should attempt to organize the space of relevant information in a way that facilitates exploration.We describe the ASPECTOR system that computes aspects for a given query. Each aspect is a set of search queries that together represent a distinct information need relevant to the original search query. To serve as an effective means to explore the space, ASPECTOR computes aspects that are orthogonal to each other and to have high combined coverage.ASPECTOR combines two sources of information to compute aspects. We discover candidate aspects by analyzing query logs, and cluster them to eliminate redundancies. We then use a mass-collaboration knowledge base (e.g., Wikipedia) to compute candidate aspects for queries that occur less frequently and to group together aspects that are likely to be "semantically" related. We present a user study that indicates that the aspects we compute are rated favorably against three competing alternatives - related searches proposed by Google, cluster labels assigned by the Clusty search engine, and navigational searches proposed by Bing.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {677–700},
numpages = {24}
}

@article{10.5555/2016945.2016962,
author = {Bordeaux, Lucas and Katsirelos, George and Narodytska, Nina and Vardi, Moshe Y.},
title = {The Complexity of Integer Bound Propagation},
year = {2011},
issue_date = {January 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {40},
number = {1},
issn = {1076-9757},
abstract = {Bound propagation is an important Artificial Intelligence technique used in Constraint Programming tools to deal with numerical constraints. It is typically embedded within a search procedure ("branch and prune") and used at every node of the search tree to narrow down the search space, so it is critical that it be fast. The procedure invokes constraint propagators until a common fixpoint is reached, but the known algorithms for this have a pseudo-polynomial worst-case time complexity: they are fast indeed when the variables have a small numerical range, but they have the well-known problem of being prohibitively slow when these ranges are large. An important question is therefore whether strongly-polynomial algorithms exist that compute the common bound consistent fixpoint of a set of constraints. This paper answers this question. In particular we show that this fixpoint computation is in fact NP-complete, even when restricted to binary linear constraints.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {657–676},
numpages = {20}
}

@article{10.5555/2016945.2016961,
author = {Aravantinos, Vincent and Caferra, Ricardo and Peltier, Nicolas},
title = {Decidability and Undecidability Results for Propositional Schemata},
year = {2011},
issue_date = {January 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {40},
number = {1},
issn = {1076-9757},
abstract = {We define a logic of propositional formula schemata adding to the syntax of propositional logic indexed propositions (e.g., pi) and iterated connectives ∨ or ∧ ranging over intervals parameterized by arithmetic variables (e.g., ∧i-1n pi, where n is a parameter). The satisfiability problem is shown to be undecidable for this new logic, but we introduce a very general class of schemata, called bound-linear, for which this problem becomes decidable. This result is obtained by reduction to a particular class of schemata called regular, for which we provide a sound and complete terminating proof procedure. This schemata calculus (called STAB) allows one to capture proof patterns corresponding to a large class of problems specified in propositional logic. We also show that the satisfiability problem becomes again undecidable for slight extensions of this class, thus demonstrating that bound-linear schemata represent a good compromise between expressivity and decidability},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {599–656},
numpages = {58}
}

@article{10.5555/2016945.2016960,
author = {Kash, Ian A. and Friedman, Eric J. and Halpern, Joseph Y.},
title = {Multiagent Learning in Large Anonymous Games},
year = {2011},
issue_date = {January 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {40},
number = {1},
issn = {1076-9757},
abstract = {In large systems, it is important for agents to learn to act effectively, but sophisticated multi-agent learning algorithms generally do not scale. An alternative approach is to find restricted classes of games where simple, efficient algorithms converge. It is shown that stage learning efficiently converges to Nash equilibria in large anonymous games if bestreply dynamics converge. Two features are identified that improve convergence. First, rather than making learning more difficult, more agents are actually beneficial in many settings. Second, providing agents with statistical information about the behavior of others can significantly reduce the number of observations needed.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {571–598},
numpages = {28}
}

@article{10.5555/2016945.2016959,
author = {He, Ruijie and Brunskill, Emma and Roy, Nicholas},
title = {Efficient Planning under Uncertainty with Macro-Actions},
year = {2011},
issue_date = {January 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {40},
number = {1},
issn = {1076-9757},
abstract = {Deciding how to act in partially observable environments remains an active area of research. Identifying good sequences of decisions is particularly challenging when good control performance requires planning multiple steps into the future in domains with many states. Towards addressing this challenge, we present an online, forward-search algorithm called the Posterior Belief Distribution (PBD). PBD leverages a novel method for calculating the posterior distribution over beliefs that result after a sequence of actions is taken, given the set of observation sequences that could be received during this process. This method allows us to efficiently evaluate the expected reward of a sequence of primitive actions, which we refer to as macro-actions. We present a formal analysis of our approach, and examine its performance on two very large simulation experiments: scientific exploration and a target monitoring domain. We also demonstrate our algorithm being used to control a real robotic helicopter in a target monitoring experiment, which suggests that our approach has practical potential for planning in real-world, large partially observable domains where a multistep lookahead is required to achieve good performance.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {523–570},
numpages = {48}
}

@article{10.5555/2016945.2016958,
author = {Rahman, Altaf and Ng, Vincent},
title = {Narrowing the Modeling Gap: A Cluster-Ranking Approach to Coreference Resolution},
year = {2011},
issue_date = {January 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {40},
number = {1},
issn = {1076-9757},
abstract = {Traditional learning-based coreference resolvers operate by training the mention-pair model for determining whether two mentions are coreferent or not. Though conceptually simple and easy to understand, the mention-pair model is linguistically rather unappealing and lags far behind the heuristic-based coreference models proposed in the prestatistical NLP era in terms of sophistication. Two independent lines of recent research have attempted to improve the mention-pair model, one by acquiring the mention-ranking model to rank preceding mentions for a given anaphor, and the other by training the entity-mention model to determine whether a preceding cluster is coreferent with a given mention. We propose a cluster-ranking approach to coreference resolution, which combines the strengths of the mention-ranking model and the entity-mention model, and is therefore theoretically more appealing than both of these models. In addition, we seek to improve cluster rankers via two extensions: (1) lexicalization and (2) incorporating knowledge of anaphoricity by jointly modeling anaphoricity determination and coreference resolution. Experimental results on the ACE data sets demonstrate the superior performance of cluster rankers to competing approaches as well as the effectiveness of our two extensions.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {469–521},
numpages = {53}
}

@article{10.5555/2016945.2016957,
author = {Ruml, Wheeler and Do, Minh Binh and Zhou, Rong and Fromherz, Markus P. J.},
title = {On-Line Planning and Scheduling: An Application to Controlling Modular Printers},
year = {2011},
issue_date = {January 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {40},
number = {1},
issn = {1076-9757},
abstract = {We present a case study of artificial intelligence techniques applied to the control of production printing equipment. Like many other real-world applications, this complex domain requires high-speed autonomous decision-making and robust continual operation. To our knowledge, this work represents the first successful industrial application of embedded domain-independent temporal planning. Our system handles execution failures and multi-objective preferences. At its heart is an on-line algorithm that combines techniques from state-space planning and partial-order scheduling. We suggest that this general architecture may prove useful in other applications as more intelligent systems operate in continual, on-line settings. Our system has been used to drive several commercial prototypes and has enabled a new product architecture for our industrial partner. When compared with state-of-the-art off-line planners, our system is hundreds of times faster and often finds better plans. Our experience demonstrates that domain-independent AI planning based on heuristic search can flexibly handle time, resources, replanning, and multiple objectives in a high-speed practical application without requiring hand-coded control knowledge.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {415–468},
numpages = {54}
}

@article{10.5555/2016945.2016956,
author = {Tannier, Xavier and Muller, Philippe},
title = {Evaluating Temporal Graphs Built from Texts via Transitive Reduction},
year = {2011},
issue_date = {January 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {40},
number = {1},
issn = {1076-9757},
abstract = {Temporal information has been the focus of recent attention in information extraction, leading to some standardization effort, in particular for the task of relating events in a text. This task raises the problem of comparing two annotations of a given text, because relations between events in a story are intrinsically interdependent and cannot be evaluated separately. A proper evaluation measure is also crucial in the context of a machine learning approach to the problem. Finding a common comparison referent at the text level is not obvious, and we argue here in favor of a shift from eventbased measures to measures on a unique textual object, a minimal underlying temporal graph, or more formally the transitive reduction of the graph of relations between event boundaries. We support it by an investigation of its properties on synthetic data and on a well-know temporal corpus.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {375–413},
numpages = {39}
}

@article{10.5555/2016945.2016955,
author = {Atserias, Albert and Fichte, Johannes Klaus and Thurley, Marc},
title = {Clause-Learning Algorithms with Many Restarts and Bounded-Width Resolution},
year = {2011},
issue_date = {January 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {40},
number = {1},
issn = {1076-9757},
abstract = {We offer a new understanding of some aspects of practical SAT-solvers that are based on DPLL with unit-clause propagation, clause-learning, and restarts. We do so by analyzing a concrete algorithm which we claim is faithful to what practical solvers do. In particular, before making any new decision or restart, the solver repeatedly applies the unit-resolution rule until saturation, and leaves no component to the mercy of non-determinism except for some internal randomness. We prove the perhaps surprising fact that, although the solver is not explicitly designed for it, with high probability it ends up behaving as width-k resolution after no more than O(n2k+2) conflicts and restarts, where n is the number of variables. In other words, width-k resolution can be thought of as O(n2k+2) restarts of the unit-resolution rule with learning.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {353–373},
numpages = {21}
}

@article{10.5555/2016945.2016954,
author = {Faliszewski, Piotr and Hemaspaandra, Edith and Hemaspaandra, Lane A.},
title = {Multimode Control Attacks on Elections},
year = {2011},
issue_date = {January 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {40},
number = {1},
issn = {1076-9757},
abstract = {In 1992, Bartholdi, Tovey, and Trick opened the study of control attacks on elections-- attempts to improve the election outcome by such actions as adding/deleting candidates or voters. That work has led to many results on how algorithms can be used to find attacks on elections and how complexity-theoretic hardness results can be used as shields against attacks. However, all the work in this line has assumed that the attacker employs just a single type of attack. In this paper, we model and study the case in which the attacker launches a multipronged (i.e., multimode) attack. We do so to more realistically capture the richness of real-life settings. For example, an attacker might simultaneously try to suppress some voters, attract new voters into the election, and introduce a spoiler candidate. Our model provides a unified framework for such varied attacks. By constructing polynomialtime multiprong attack algorithms we prove that for various election systems even such concerted, flexible attacks can be perfectly planned in deterministic polynomial time.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {305–351},
numpages = {47}
}

@article{10.5555/2016945.2016953,
author = {Hunter, Aaron and Delgrande, James P.},
title = {Iterated Belief Change Due to Actions and Observations},
year = {2011},
issue_date = {January 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {40},
number = {1},
issn = {1076-9757},
abstract = {In action domains where agents may have erroneous beliefs, reasoning about the effects of actions involves reasoning about belief change. In this paper, we use a transition system approach to reason about the evolution of an agent's beliefs as actions are executed. Some actions cause an agent to perform belief revision while others cause an agent to perform belief update, but the interaction between revision and update can be nonelementary. We present a set of rationality properties describing the interaction between revision and update, and we introduce a new class of belief change operators for reasoning about alternating sequences of revisions and updates. Our belief change operators can be characterized in terms of a natural shifting operation on total pre-orderings over interpretations. We compare our approach with related work on iterated belief change due to action, and we conclude with some directions for future research.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {269–304},
numpages = {36}
}

@article{10.5555/2016945.2016952,
author = {Wang, Yonghong and Hang, Chung-Wei and Singh, Munindar P.},
title = {A Probabilistic Approach for Maintaining Trust Based on Evidence},
year = {2011},
issue_date = {January 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {40},
number = {1},
issn = {1076-9757},
abstract = {Leading agent-based trust models address two important needs. First, they show how an agent may estimate the trustworthiness of another agent based on prior interactions. Second, they show how agents may share their knowledge in order to cooperatively assess the trustworthiness of others. However, in real-life settings, information relevant to trust is usually obtained piecemeal, not all at once. Unfortunately, the problem of maintaining trust has drawn little attention. Existing approaches handle trust updates in a heuristic, not a principled, manner.This paper builds on a formal model that considers probability and certainty as two dimensions of trust. It proposes a mechanism using which an agent can update the amount of trust it places in other agents on an ongoing basis. This paper shows via simulation that the proposed approach (a) provides accurate estimates of the trustworthiness of agents that change behavior frequently; and (b) captures the dynamic behavior of the agents. This paper includes an evaluation based on a real dataset drawn from Amazon Marketplace, a leading e-commerce site.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {221–267},
numpages = {47}
}

@article{10.5555/2016945.2016951,
author = {Lecoutre, Christophe and Cardon, St\'{e}phane and Vion, Julien},
title = {Second-Order Consistencies},
year = {2011},
issue_date = {January 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {40},
number = {1},
issn = {1076-9757},
abstract = {In this paper, we propose a comprehensive study of second-order consistencies (i.e., consistencies identifying inconsistent pairs of values) for constraint satisfaction. We build a full picture of the relationships existing between four basic second-order consistencies, namely path consistency (PC), 3-consistency (3C), dual consistency (DC) and 2-singleton arc consistency (2SAC), as well as their conservative and strong variants. Interestingly, dual consistency is an original property that can be established by using the outcome of the enforcement of generalized arc consistency (GAC), which makes it rather easy to obtain since constraint solvers typically maintain GAC during search. On binary constraint networks, DC is equivalent to PC, but its restriction to existing constraints, called conservative dual consistency (CDC), is strictly stronger than traditional conservative consistencies derived from path consistency, namely partial path consistency (PPC) and conservative path consistency (CPC). After introducing a general algorithm to enforce strong (C)DC, we present the results of an experimentation over a wide range of benchmarks that demonstrate the interest of (conservative) dual consistency. In particular, we show that enforcing (C)DC before search clearly improves the performance of MAC (the algorithm that maintains GAC during search) on several binary and non-binary structured problems.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {175–219},
numpages = {45}
}

@article{10.5555/2016945.2016950,
author = {Geist, Christian and Endriss, Ulle},
title = {Automated Search for Impossibility Theorems in Social Choice Theory: Ranking Sets of Objects},
year = {2011},
issue_date = {January 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {40},
number = {1},
issn = {1076-9757},
abstract = {We present a method for using standard techniques from satisfiability checking to automatically verify and discover theorems in an area of economic theory known as ranking sets of objects. The key question in this area, which has important applications in social choice theory and decision making under uncertainty, is how to extend an agent's preferences over a number of objects to a preference relation over nonempty sets of such objects. Certain combinations of seemingly natural principles for this kind of preference extension can result in logical inconsistencies, which has led to a number of important impossibility theorems. We first prove a general result that shows that for a wide range of such principles, characterised by their syntactic form when expressed in a many-sorted first-order logic, any impossibility exhibited at a fixed (small) domain size will necessarily extend to the general case. We then show how to formulate candidates for impossibility theorems at a fixed domain size in propositional logic, which in turn enables us to automatically search for (general) impossibility theorems using a SAT solver. When applied to a space of 20 principles for preference extension familiar from the literature, this method yields a total of 84 impossibility theorems, including both known and nontrivial new results.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {143–174},
numpages = {32}
}

@article{10.5555/2016945.2016949,
author = {Veness, Joel and Ng, Kee Siong and Hutter, Marcus and Uther, William and Silver, David},
title = {A Monte-Carlo AIXI Approximation},
year = {2011},
issue_date = {January 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {40},
number = {1},
issn = {1076-9757},
abstract = {This paper introduces a principled approach for the design of a scalable general reinforcement learning agent. Our approach is based on a direct approximation of AIXI, a Bayesian optimality notion for general reinforcement learning agents. Previously, it has been unclear whether the theory of AIXI could motivate the design of practical algorithms. We answer this hitherto open question in the affirmative, by providing the first computationally feasible approximation to the AIXI agent. To develop our approximation, we introduce a new Monte-Carlo Tree Search algorithm along with an agent-specific extension to the Context Tree Weighting algorithm. Empirically, we present a set of encouraging results on a variety of stochastic and partially observable domains. We conclude by proposing a number of directions for future research.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {95–142},
numpages = {48}
}

@article{10.5555/2016945.2016948,
author = {Aziz, Haris and Bachrach, Yoram and Elkind, Edith and Paterson, Mike},
title = {False-Name Manipulations in Weighted Voting Games},
year = {2011},
issue_date = {January 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {40},
number = {1},
issn = {1076-9757},
abstract = {Weighted voting is a classic model of cooperation among agents in decision-making domains. In such games, each player has a weight, and a coalition of players wins the game if its total weight meets or exceeds a given quota. A player's power in such games is usually not directly proportional to his weight, and is measured by a power index, the most prominent among which are the Shapley-Shubik index and the Banzhaf index.In this paper, we investigate by how much a player can change his power, as measured by the Shapley-Shubik index or the Banzhaf index, by means of a false-name manipulation, i.e., splitting his weight among two or more identities. For both indices, we provide upper and lower bounds on the effect of weight-splitting. We then show that checking whether a beneficial split exists is NP-hard, and discuss efficient algorithms for restricted cases of this problem, as well as randomized algorithms for the general case. We also provide an experimental evaluation of these algorithms.Finally, we examine related forms of manipulative behavior, such as annexation, where a player subsumes other players, or merging, where several players unite into one. We characterize the computational complexity of such manipulations and provide limits on their effects. For the Banzhaf index, we describe a new paradox, which we term the Annexation Non-monotonicity Paradox.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {57–93},
numpages = {37}
}

@article{10.5555/2016945.2016947,
author = {Zhou, Yi and Zhang, Yan},
title = {A Logical Study of Partial Entailment},
year = {2011},
issue_date = {January 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {40},
number = {1},
issn = {1076-9757},
abstract = {We introduce a novel logical notion-partial entailment-to propositional logic. In contrast with classical entailment, that a formula P partially entails another formula Q with respect to a background formula set Γ intuitively means that under the circumstance of Γ, if P is true then some "part" of Q will also be true. We distinguish three different kinds of partial entailments and formalize them by using an extended notion of prime implicant. We study their semantic properties, which show that, surprisingly, partial entailments fail for many simple inference rules. Then, we study the related computational properties, which indicate that partial entailments are relatively difficult to be computed. Finally, we consider a potential application of partial entailments in reasoning about rational agents.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {25–56},
numpages = {32}
}

@article{10.5555/2016945.2016946,
author = {Fard, Mahdi Milani and Pineau, Joelle},
title = {Non-Deterministic Policies in Markovian Decision Processes},
year = {2011},
issue_date = {January 2011},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {40},
number = {1},
issn = {1076-9757},
abstract = {Markovian processes have long been used to model stochastic environments. Reinforcement learning has emerged as a framework to solve sequential planning and decision-making problems in such environments. In recent years, attempts were made to apply methods from reinforcement learning to construct decision support systems for action selection in Markovian environments. Although conventional methods in reinforcement learning have proved to be useful in problems concerning sequential decision-making, they cannot be applied in their current form to decision support systems, such as those in medical domains, as they suggest policies that are often highly prescriptive and leave little room for the user's input. Without the ability to provide flexible guidelines, it is unlikely that these methods can gain ground with users of such systems.This paper introduces the new concept of non-deterministic policies to allow more flexibility in the user's decision-making process, while constraining decisions to remain near optimal solutions. We provide two algorithms to compute non-deterministic policies in discrete domains. We study the output and running time of these method on a set of synthetic and real-world problems. In an experiment with human subjects, we show that humans assisted by hints based on non-deterministic policies outperform both human-only and computer-only agents in a web navigation task.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {1–24},
numpages = {24}
}

@article{10.5555/1946417.1946434,
author = {Xu, Jing and Shelton, Christian R.},
title = {Intrusion Detection Using Continuous Time Bayesian Networks},
year = {2010},
issue_date = {September 2010},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {39},
number = {1},
issn = {1076-9757},
abstract = {Intrusion detection systems (IDSs) fall into two high-level categories: network-based systems (NIDS) that monitor network behaviors, and host-based systems (HIDS) that monitor system calls. In this work, we present a general technique for both systems. We use anomaly detection, which identifies patterns not conforming to a historic norm. In both types of systems, the rates of change vary dramatically over time (due to burstiness) and over components (due to service difference). To efficiently model such systems, we use continuous time Bayesian networks (CTBNs) and avoid specifying a fixed update interval common to discrete-time models. We build generative models from the normal training data, and abnormal behaviors are flagged based on their likelihood under this norm. For NIDS, we construct a hierarchical CTBN model for the network packet traces and use Rao-Blackwellized particle filtering to learn the parameters. We illustrate the power of our method through experiments on detecting real worms and identifying hosts on two publicly available network traces, the MAWI dataset and the LBNL dataset. For HIDS, we develop a novel learning method to deal with the finite resolution of system log file time stamps, without losing the benefits of our continuous time model. We demonstrate the method by detecting intrusions in the DARPA 1998 BSM dataset.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {745–774},
numpages = {30}
}

@article{10.5555/1946417.1946433,
author = {Burns, Ethan and Lemons, Sofia and Ruml, Wheeler and Zhou, Rong},
title = {Best-First Heuristic Search for Multicore Machines},
year = {2010},
issue_date = {September 2010},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {39},
number = {1},
issn = {1076-9757},
abstract = {To harness modern multicore processors, it is imperative to develop parallel versions of fundamental algorithms. In this paper, we compare different approaches to parallel best-first search in a shared-memory setting. We present a new method, PBNF, that uses abstraction to partition the state space and to detect duplicate states without requiring frequent locking. PBNF allows speculative expansions when necessary to keep threads busy. We identify and fix potential livelock conditions in our approach, proving its correctness using temporal logic. Our approach is general, allowing it to extend easily to suboptimal and anytime heuristic search. In an empirical comparison on STRIPS planning, grid pathfinding, and sliding tile puzzle problems using 8-core machines, we show that A*, weighted A* and Anytime weighted A* implemented using PBNF yield faster search than improved versions of previous parallel search proposals.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {689–743},
numpages = {55}
}

@article{10.5555/1946417.1946432,
author = {J\"{a}ger, Gerold and Zhang, Weixiong},
title = {An Effective Algorithm for and Phase Transitions of the Directed Hamiltonian Cycle Problem},
year = {2010},
issue_date = {September 2010},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {39},
number = {1},
issn = {1076-9757},
abstract = {The Hamiltonian cycle problem (HCP) is an important combinatorial problem with applications in many areas. It is among the first problems used for studying intrinsic properties, including phase transitions, of combinatorial problems. While thorough theoretical and experimental analyses have been made on the HCP in undirected graphs, a limited amount of work has been done for the HCP in directed graphs (DHCP). The main contribution of this work is an effective algorithm for the DHCP. Our algorithm explores and exploits the close relationship between the DHCP and the Assignment Problem (AP) and utilizes a technique based on Boolean satisfiability (SAT). By combining effective algorithms for the AP and SAT, our algorithm significantly outperforms previous exact DHCP algorithms, including an algorithm based on the award-winning Concorde TSP algorithm. The second result of the current study is an experimental analysis of phase transitions of the DHCP, verifying and refining a known phase transition of the DHCP.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {663–687},
numpages = {25}
}

@article{10.5555/1946417.1946431,
author = {Krause, Andreas and Horvitz, Eric},
title = {A Utility-Theoretic Approach to Privacy in Online Services},
year = {2010},
issue_date = {September 2010},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {39},
number = {1},
issn = {1076-9757},
abstract = {Online offerings such as web search, news portals, and e-commerce applications face the challenge of providing high-quality service to a large, heterogeneous user base. Recent efforts have highlighted the potential to improve performance by introducing methods to personalize services based on special knowledge about users and their context. For example, a user's demographics, location, and past search and browsing may be useful in enhancing the results offered in response to web search queries. However, reasonable concerns about privacy by both users, providers, and government agencies acting on behalf of citizens, may limit access by services to such information. We introduce and explore an economics of privacy in personalization, where people can opt to share personal information, in a standing or on-demand manner, in return for expected enhancements in the quality of an online service. We focus on the example of web search and formulate realistic objective functions for search efficacy and privacy. We demonstrate how we can find a provably near-optimal optimization of the utility-privacy tradeoff in an efficient manner. We evaluate our methodology on data drawn from a log of the search activity of volunteer participants. We separately assess users preferences about privacy and utility via a large-scale survey, aimed at eliciting preferences about peoples willingness to trade the sharing of personal data in returns for gains in search efficiency. We show that a significant level of personalization can be achieved using a relatively small amount of information about users.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {633–662},
numpages = {30}
}

@article{10.5555/1946417.1946430,
author = {Dasgupta, Sajib and Ng, Vincent},
title = {Which Clustering Do You Want? Inducing Your Ideal Clustering with Minimal Feedback},
year = {2010},
issue_date = {September 2010},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {39},
number = {1},
issn = {1076-9757},
abstract = {While traditional research on text clustering has largely focused on grouping documents by topic, it is conceivable that a user may want to cluster documents along other dimensions, such as the author's mood, gender, age, or sentiment. Without knowing the user's intention, a clustering algorithm will only group documents along the most prominent dimension, which may not be the one the user desires. To address the problem of clustering documents along the user-desired dimension, previous work has focused on learning a similarity metric from data manually annotated with the user's intention or having a human construct a feature space in an interactive manner during the clustering process. With the goal of reducing reliance on human knowledge for fine-tuning the similarity function or selecting the relevant features required by these approaches, we propose a novel active clustering algorithm, which allows a user to easily select the dimension along which she wants to cluster the documents by inspecting only a small number of words. We demonstrate the viability of our algorithm on a variety of commonly-used sentiment datasets.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {581–632},
numpages = {52}
}

@article{10.5555/1946417.1946429,
author = {Daniel, Kenny and Nash, Alex and Koenig, Sven and Felner, Ariel},
title = {Theta*: Any-Angle Path Planning on Grids},
year = {2010},
issue_date = {September 2010},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {39},
number = {1},
issn = {1076-9757},
abstract = {Grids with blocked and unblocked cells are often used to represent terrain in robotics and video games. However, paths formed by grid edges can be longer than true shortest paths in the terrain since their headings are artificially constrained. We present two new correct and complete anyangle path-planning algorithms that avoid this shortcoming. Basic Theta* and Angle-Propagation Theta* are both variants of A* that propagate information along grid edges without constraining paths to grid edges. Basic Theta* is simple to understand and implement, fast and finds short paths. However, it is not guaranteed to find true shortest paths. Angle-Propagation Theta* achieves a better worst-case complexity per vertex expansion than Basic Theta* by propagating angle ranges when it expands vertices, but is more complex, not as fast and finds slightly longer paths. We refer to Basic Theta* and Angle-Propagation Theta* collectively as Theta*. Theta* has unique properties, which we analyze in detail. We show experimentally that it finds shorter paths than both A* with post-smoothed paths and Field D* (the only other version of A* we know of that propagates information along grid edges without constraining paths to grid edges) with a runtime comparable to that of A* on grids. Finally, we extend Theta* to grids that contain unblocked cells with non-uniformtraversal costs and introduce variants of Theta* which provide different tradeoffs between path length and runtime.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {533–579},
numpages = {47}
}

@article{10.5555/1946417.1946428,
author = {Geist, Matthieu and Pietquin, Olivier},
title = {Kalman Temporal Differences},
year = {2010},
issue_date = {September 2010},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {39},
number = {1},
issn = {1076-9757},
abstract = {Because reinforcement learning suffers from a lack of scalability, online value (and Q-) function approximation has received increasing interest this last decade. This contribution introduces a novel approximation scheme, namely the Kalman Temporal Differences (KTD) framework, that exhibits the following features: sample-efficiency, non-linear approximation, non-stationarity handling and uncertainty management. A first KTD-based algorithm is provided for deterministic Markov Decision Processes (MDP) which produces biased estimates in the case of stochastic transitions. Than the eXtended KTD framework (XKTD), solving stochastic MDP, is described. Convergence is analyzed for special cases for both deterministic and stochastic transitions. Related algorithms are experimented on classical benchmarks. They compare favorably to the state of the art while exhibiting the announced features.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {483–532},
numpages = {50}
}

@article{10.5555/1946417.1946427,
author = {Rudolph, Sebastian and Glimm, Birte},
title = {Nominals, Inverses, Counting, and Conjunctive Queries or: Why Infinity is Your Friend!},
year = {2010},
issue_date = {September 2010},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {39},
number = {1},
issn = {1076-9757},
abstract = {Description Logics are knowledge representation formalisms that provide, for example, the logical underpinning of the W3C OWL standards. Conjunctive queries, the standard query language in databases, have recently gained significant attention as an expressive formalism for querying Description Logic knowledge bases. Several different techniques for deciding conjunctive query entailment are available for a wide range of DLs. Nevertheless, the combination of nominals, inverse roles, and number restrictions in OWL 1 and OWL 2 DL causes unsolvable problems for the techniques hitherto available. We tackle this problem and present a decidability result for entailment of unions of conjunctive queries in the DL ALCHOIQb that contains all three problematic constructors simultaneously. Provided that queries contain only simple roles, our result also shows decidability of entailment of (unions of) conjunctive queries in the logic that underpins OWL 1 DL and we believe that the presented results will pave the way for further progress towards conjunctive query entailment decision procedures for the Description Logics underlying the OWL standards.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {429–481},
numpages = {53}
}

@article{10.5555/1946417.1946426,
author = {Banerjee, Bonny and Chandrasekaran, B.},
title = {A Constraint Satisfaction Framework for Executing Perceptions and Actions in Diagrammatic Reasoning},
year = {2010},
issue_date = {September 2010},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {39},
number = {1},
issn = {1076-9757},
abstract = {Diagrammatic reasoning (DR) is pervasive in human problem solving as a powerful adjunct to symbolic reasoning based on language-like representations. The research reported in this paper is a contribution to building a general purpose DR system as an extension to a soar-like problem solving architecture. The work is in a framework in which DR is modeled as a process where subtasks are solved, as appropriate, either by inference from symbolic representations or by interaction with a diagram, i.e., perceiving specified information from a diagram or modifying/creating objects in a diagram in specified ways according to problem solving needs. The perceptions and actions in most DR systems built so far are hand-coded for the specific application, even when the rest of the system is built using the general architecture. The absence of a general framework for executing perceptions/ actions poses as a major hindrance to using them opportunistically - the essence of open-ended search in problem solving.Our goal is to develop a framework for executing a wide variety of specified perceptions and actions across tasks/domains without human intervention. We observe that the domain/task-specific visual perceptions/actions can be transformed into domain/taskindependent spatial problems. We specify a spatial problem as a quantified constraint satisfaction problem in the real domain using an open-ended vocabulary of properties, relations and actions involving three kinds of diagrammatic objects - points, curves, regions. Solving a spatial problem from this specification requires computing the equivalent simplified quantifier-free expression, the complexity of which is inherently doubly exponential. We represent objects as configuration of simple elements to facilitate decomposition of complex problems into simpler and similar subproblems. We show that, if the symbolic solution to a subproblem can be expressed concisely, quantifiers can be eliminated from spatial problems in low-order polynomial time using similar previously solved subproblems. This requires determining the similarity of two problems, the existence of a mapping between them computable in polynomial time, and designing a memory for storing previously solved problems so as to facilitate search. The efficacy of the idea is shown by time complexity analysis. We demonstrate the proposed approach by executing perceptions and actions involved in DR tasks in two army applications.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {373–427},
numpages = {55}
}

@article{10.5555/1946417.1946425,
author = {Bidyuk, Bozhena and Dechter, Rina and Rollon, Emma},
title = {Active Tuples-Based Scheme for Bounding Posterior Beliefs},
year = {2010},
issue_date = {September 2010},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {39},
number = {1},
issn = {1076-9757},
abstract = {The paper presents a scheme for computing lower and upper bounds on the posterior marginals in Bayesian networks with discrete variables. Its power lies in its ability to use any available scheme that bounds the probability of evidence or posterior marginals and enhance its performance in an anytime manner. The scheme uses the cutset conditioning principle to tighten existing bounding schemes and to facilitate anytime behavior, utilizing a fixed number of cutset tuples. The accuracy of the bounds improves as the number of used cutset tuples increases and so does the computation time. We demonstrate empirically the value of our scheme for bounding posterior marginals and probability of evidence using a variant of the bound propagation algorithm as a plug-in scheme.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {335–371},
numpages = {37}
}

@article{10.5555/1946417.1946424,
author = {Feldman, Alexander and Provan, Gregory and van Gemund, Arjan},
title = {A Model-Based Active Testing Approach to Sequential Diagnosis},
year = {2010},
issue_date = {September 2010},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {39},
number = {1},
issn = {1076-9757},
abstract = {Model-based diagnostic reasoning often leads to a large number of diagnostic hypotheses. The set of diagnoses can be reduced by taking into account extra observations (passive monitoring), measuring additional variables (probing) or executing additional tests (sequential diagnosis/test sequencing). In this paper we combine the above approaches with techniques from Automated Test Pattern Generation (ATPG) and Model-Based Diagnosis (MBD) into a framework called Fractal (FRamework for ACtive Testing ALgorithms). Apart from the inputs and outputs that connect a system to its environment, in active testing we consider additional input variables to which a sequence of test vectors can be supplied. We address the computationally hard problem of computing optimal control assignments (as defined in Fractal) in terms of a greedy approximation algorithm called FractalG. We compare the decrease in the number of remaining minimal cardinality diagnoses of FractalG to that of two more Fractal algorithms: FractalATPG and FractalP. FractalATPG is based on ATPG and sequential diagnosis while FractalP is based on probing and, although not an active testing algorithm, provides a baseline for comparing the lower bound on the number of reachable diagnoses for the Fractal algorithms. We empirically evaluate the trade-offs of the three Fractal algorithms by performing extensive experimentation on the ISCAS85/74XXX benchmark of combinational circuits.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {301–334},
numpages = {34}
}

@article{10.5555/1946417.1946423,
author = {Bulitko, Vadim and Bj\"{o}rnsson, Yngvi and Lawrence, Ramon},
title = {Case-Based Subgoaling in Real-Time Heuristic Search for Video Game Pathfinding},
year = {2010},
issue_date = {September 2010},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {39},
number = {1},
issn = {1076-9757},
abstract = {Real-time heuristic search algorithms satisfy a constant bound on the amount of planning per action, independent of problem size. As a result, they scale up well as problems become larger. This property would make them well suited for video games where Artificial Intelligence controlled agents must react quickly to user commands and to other agents. actions. On the downside, real-time search algorithms employ learning methods that frequently lead to poor solution quality and cause the agent to appear irrational by re-visiting the same problem states repeatedly. The situation changed recently with a new algorithm, D LRTA*, which attempted to eliminate learning by automatically selecting subgoals. D LRTA* is well poised for video games, except it has a complex and memory-demanding pre-computation phase during which it builds a database of subgoals. In this paper, we propose a simpler and more memory-efficient way of pre-computering subgoals thereby eliminating the main obstacle to applying state-of-the-art real-time search methods in video games. The new algorithm solves a number of randomly chosen problems off-line, compresses the solutions into a series of subgoals and stores them in a database. When presented with a novel problem on-line, it queries the database for the most similar previously solved case and uses its subgoals to solve the problem. In the domain of pathfinding on four large video game maps, the new algorithm delivers solutions eight times better while using 57 times less memory and requiring 14% less pre-computation time.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {269–300},
numpages = {32}
}

@article{10.5555/1946417.1946422,
author = {Riedl, Mark O. and Young, R. Michael},
title = {Narrative Planning: Balancing Plot and Character},
year = {2010},
issue_date = {September 2010},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {39},
number = {1},
issn = {1076-9757},
abstract = {Narrative, and in particular storytelling, is an important part of the human experience. Consequently, computational systems that can reason about narrative can be more effective communicators, entertainers, educators, and trainers. One of the central challenges in computational narrative reasoning is narrative generation, the automated creation of meaningful event sequences. There are many factors - logical and aesthetic - that contribute to the success of a narrative artifact. Central to this success is its understandability. We argue that the following two attributes of narratives are universal: (a) the logical causal progression of plot, and (b) character believability. Character believability is the perception by the audience that the actions performed by characters do not negatively impact the audience's suspension of disbelief. Specifically, characters must be perceived by the audience to be intentional agents. In this article, we explore the use of refinement search as a technique for solving the narrative generation problem - to find a sound and believable sequence of character actions that transforms an initial world state into a world state in which goal propositions hold. We describe a novel refinement search planning algorithm - the Intent-based Partial Order Causal Link (IPOCL) planner - that, in addition to creating causally sound plot progression, reasons about character intentionality by identifying possible character goals that explain their actions and creating plan structures that explain why those characters commit to their goals. We present the results of an empirical evaluation that demonstrates that narrative plans generated by the IPOCL algorithm support audience comprehension of character intentions better than plans generated by conventional partial-order planners.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {217–268},
numpages = {52}
}

@article{10.5555/1946417.1946421,
author = {Chalkiadakis, Georgios and Elkind, Edith and Markakis, Evangelos and Polukarov, Maria and Jennings, Nicholas R.},
title = {Cooperative Games with Overlapping Coalitions},
year = {2010},
issue_date = {September 2010},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {39},
number = {1},
issn = {1076-9757},
abstract = {In the usual models of cooperative game theory, the outcome of a coalition formation process is either the grand coalition or a coalition structure that consists of disjoint coalitions. However, in many domains where coalitions are associated with tasks, an agent may be involved in executing more than one task, and thus may distribute his resources among several coalitions. To tackle such scenarios, we introduce a model for cooperative games with overlapping coalitions-or overlapping coalition formation (OCF) games. We then explore the issue of stability in this setting. In particular, we introduce a notion of the core, which generalizes the corresponding notion in the traditional (non-overlapping) scenario. Then, under some quite general conditions, we characterize the elements of the core, and show that any element of the core maximizes the social welfare. We also introduce a concept of balancedness for overlapping coalitional games, and use it to characterize coalition structures that can be extended to elements of the core. Finally, we generalize the notion of convexity to our setting, and show that under some natural assumptions convex games have a non-empty core. Moreover, we introduce two alternative notions of stability in OCF that allow a wider range of deviations, and explore the relationships among the corresponding definitions of the core, as well as the classic (non-overlapping) core and the Aubin core. We illustrate the general properties of the three cores, and also study them from a computational perspective, thus obtaining additional insights into their fundamental structure.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {179–216},
numpages = {38}
}

@article{10.5555/1946417.1946420,
author = {Richter, Silvia and Westphal, Matthias},
title = {The LAMA Planner: Guiding Cost-Based Anytime Planning with Landmarks},
year = {2010},
issue_date = {September 2010},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {39},
number = {1},
issn = {1076-9757},
abstract = {LAMA is a classical planning system based on heuristic forward search. Its core feature is the use of a pseudo-heuristic derived from landmarks, propositional formulas that must be true in every solution of a planning task. LAMA builds on the Fast Downward planning system, using finite-domain rather than binary state variables and multi-heuristic search. The latter is employed to combine the landmark heuristic with a variant of the well-known FF heuristic. Both heuristics are cost-sensitive, focusing on high-quality solutions in the case where actions have non-uniform cost. A weighted A* search is used with iteratively decreasing weights, so that the planner continues to search for plans of better quality until the search is terminated.LAMA showed best performance among all planners in the sequential satisficing track of the International Planning Competition 2008. In this paper we present the system in detail and investigate which features of LAMA are crucial for its performance. We present individual results for some of the domains used at the competition, demonstrating good and bad cases for the techniques implemented in LAMA. Overall, we find that using landmarks improves performance, whereas the incorporation of action costs into the heuristic estimators proves not to be beneficial. We show that in some domains a search that ignores cost solves far more problems, raising the question of how to deal with action costs more effectively in the future. The iterated weighted A* search greatly improves results, and shows synergy effects with the use of landmarks.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {127–177},
numpages = {51}
}

@article{10.5555/1946417.1946419,
author = {Katz, Michael and Domshlak, Carmel},
title = {Implicit Abstraction Heuristics},
year = {2010},
issue_date = {September 2010},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {39},
number = {1},
issn = {1076-9757},
abstract = {State-space search with explicit abstraction heuristics is at the state of the art of cost-optimal planning. These heuristics are inherently limited, nonetheless, because the size of the abstract space must be bounded by some, even if a very large, constant. Targeting this shortcoming, we introduce the notion of (additive) implicit abstractions, in which the planning task is abstracted by instances of tractable fragments of optimal planning. We then introduce a concrete setting of this framework, called fork-decomposition, that is based on two novel fragments of tractable cost-optimal planning. The induced admissible heuristics are then studied formally and empirically. This study testifies for the accuracy of the fork decomposition heuristics, yet our empirical evaluation also stresses the tradeoff between their accuracy and the runtime complexity of computing them. Indeed, some of the power of the explicit abstraction heuristics comes from precomputing the heuristic function offine and then determining h(s) for each evaluated state s by a very fast lookup in a "database." By contrast, while fork-decomposition heuristics can be calculated in polynomial time, computing them is far from being fast. To address this problem, we show that the time-per-node complexity bottleneck of the fork-decomposition heuristics can be successfully overcome. We demonstrate that an equivalent of the explicit abstraction notion of a "database" exists for the fork-decomposition abstractions as well, despite their exponential-size abstract spaces. We then verify empirically that heuristic search with the "databased" fork-decomposition heuristics favorably competes with the state of the art of cost-optimal planning.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {51–126},
numpages = {76}
}

@article{10.5555/1946417.1946418,
author = {Lang, Tobias and Toussaint, Marc},
title = {Planning with Noisy Probabilistic Relational Rules},
year = {2010},
issue_date = {September 2010},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {39},
number = {1},
issn = {1076-9757},
abstract = {Noisy probabilistic relational rules are a promising world model representation for several reasons. They are compact and generalize over world instantiations. They are usually interpretable and they can be learned effectively from the action experiences in complex worlds. We investigate reasoning with such rules in grounded relational domains. Our algorithms exploit the compactness of rules for efficient and fexible decision-theoretic planning. As a first approach, we combine these rules with the Upper Confidence Bounds applied to Trees (UCT) algorithm based on look-ahead trees. Our second approach converts these rules into a structured dynamic Bayesian network representation and predicts the effects of action sequences using approximate inference and beliefs over world states. We evaluate the effectiveness of our approaches for planning in a simulated complex 3D robot manipulation scenario with an articulated manipulator and realistic physics and in domains of the probabilistic planning competition. Empirical results show that our methods can solve problems where existing methods fail.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {1–49},
numpages = {49}
}

@article{10.5555/1892211.1892228,
author = {Wu, Jia-Hong and Givan, Robert},
title = {Automatic Induction of Bellman-Error Features for Probabilistic Planning},
year = {2010},
issue_date = {May 2010},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {38},
number = {1},
issn = {1076-9757},
abstract = {Domain-specific features are important in representing problem structure throughout machine learning and decision-theoretic planning. In planning, once state features are provided, domain-independent algorithms such as approximate value iteration can learn weighted combinations of those features that often perform well as heuristic estimates of state value (e.g., distance to the goal). Successful applications in real-world domains often require features crafted by human experts. Here, we propose automatic processes for learning useful domain-specific feature sets with little or no human intervention. Our methods select and add features that describe state-space regions of high inconsistency in the Bellman equation (statewise Bellman error) during approximate value iteration. Our method can be applied using any real-valued-feature hypothesis space and corresponding learning method for selecting features from training sets of state-value pairs. We evaluate the method with hypothesis spaces defined by both relational and propositional feature languages, using nine probabilistic planning domains. We show that approximate value iteration using a relational feature space performs at the state-of-the-art in domain-independent stochastic relational planning. Our method provides the first domain-independent approach that plays Tetris successfully (without human-engineered features).},
journal = {J. Artif. Int. Res.},
month = may,
pages = {687–755},
numpages = {69}
}

@article{10.5555/1892211.1892227,
author = {Greco, Gianluigi and Malizia, Enrico and Palopoli, Luigi and Scarcello, Francesco},
title = {Non-Transferable Utility Coalitional Games via Mixed-Integer Linear Constraints},
year = {2010},
issue_date = {May 2010},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {38},
number = {1},
issn = {1076-9757},
abstract = {Coalitional games serve the purpose of modeling payoff distribution problems in scenarios where agents can collaborate by forming coalitions in order to obtain higher worths than by acting in isolation. In the classical Transferable Utility (TU) setting, coalition worths can be freely distributed amongst agents. However, in several application scenarios, this is not the case and the Non-Transferable Utility setting (NTU) must be considered, where additional application-oriented constraints are imposed on the possible worth distributions.In this paper, an approach to define NTU games is proposed which is based on describing allowed distributions via a set of mixed-integer linear constraints applied to an underlying TU game. It is shown that such games allow non-transferable conditions on worth distributions to be specified in a natural and succinct way. The properties and the relationships among the most prominent solution concepts for NTU games that hold when they are applied on (mixed-integer) constrained games are investigated. Finally, a thorough analysis is carried out to assess the impact of issuing constraints on the computational complexity of some of these solution concepts.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {633–685},
numpages = {53}
}

@article{10.5555/1892211.1892226,
author = {Abedin, Muhammad Arshad Ul and Ng, Vincent and Khan, Latifur},
title = {Cause Identification from Aviation Safety Incident Reports via Weakly Supervised Semantic Lexicon Construction},
year = {2010},
issue_date = {May 2010},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {38},
number = {1},
issn = {1076-9757},
abstract = {The Aviation Safety Reporting System collects voluntarily submitted reports on aviation safety incidents to facilitate research work aiming to reduce such incidents. To effectively reduce these incidents, it is vital to accurately identify why these incidents occurred. More precisely, given a set of possible causes, or shaping factors, this task of cause identification involves identifying all and only those shaping factors that are responsible for the incidents described in a report. We investigate two approaches to cause identification. Both approaches exploit information provided by a semantic lexicon, which is automatically constructed via Thelen and Riloff's Basilisk framework augmented with our linguistic and algorithmic modifications. The first approach labels a report using a simple heuristic, which looks for the words and phrases acquired during the semantic lexicon learning process in the report. The second approach recasts cause identification as a text classification problem, employing supervised and transductive text classification algorithms to learn models from incident reports labeled with shaping factors and using the models to label unseen reports. Our experiments show that both the heuristic-based approach and the learning-based approach (when given sufficient training data) outperform the baseline system significantly.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {569–631},
numpages = {63}
}

@article{10.5555/1892211.1892225,
author = {de Bruijn, Jos and Heymans, Stijn},
title = {Logical Foundations of RDF(S) with Datatypes},
year = {2010},
issue_date = {May 2010},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {38},
number = {1},
issn = {1076-9757},
abstract = {The Resource Description Framework (RDF) is a Semantic Web standard that provides a data language, simply called RDF, as well as a lightweight ontology language, called RDF Schema. We investigate embeddings of RDF in logic and show how standard logic programming and description logic technology can be used for reasoning with RDF. We subsequently consider extensions of RDF with datatype support, considering D entailment, defined in the RDF semantics specification, and D* entailment, a semantic weakening of D entailment, introduced by ter Horst. We use the embeddings and properties of the logics to establish novel upper bounds for the complexity of deciding entailment. We subsequently establish two novel lower bounds, establishing that RDFS entailment is PTime-complete and that simple-D entailment is coNP-hard, when considering arbitrary datatypes, both in the size of the entailing graph. The results indicate that RDFS may not be as lightweight as one may expect.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {535–568},
numpages = {34}
}

@article{10.5555/1892211.1892224,
author = {Benisch, Michael and Davis, George B. and Sandholm, Tuomas},
title = {Algorithms for Closed under Rational Behavior (CURB) Sets},
year = {2010},
issue_date = {May 2010},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {38},
number = {1},
issn = {1076-9757},
abstract = {We provide a series of algorithms demonstrating that solutions according to the fundamental game-theoretic solution concept of closed under rational behavior (CURB) sets in two-player, normal-form games can be computed in polynomial time (we also discuss extensions to n-player games). First, we describe an algorithm that identifies all of a player's best responses conditioned on the belief that the other player will play from within a given subset of its strategy space. This algorithm serves as a subroutine in a series of polynomial-time algorithms for finding all minimal CURB sets, one minimal CURB set, and the smallest minimal CURB set in a game. We then show that the complexity of finding a Nash equilibrium can be exponential only in the size of a game's smallest CURB set. Related to this, we show that the smallest CURB set can be an arbitrarily small portion of the game, but it can also be arbitrarily larger than the supports of its only enclosed Nash equilibrium. We test our algorithms empirically and find that most commonly studied academic games tend to have either very large or very small minimal CURB sets.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {513–534},
numpages = {22}
}

@article{10.5555/1892211.1892223,
author = {Ortega, Pedro A. and Braun, Daniel A.},
title = {A Minimum Relative Entropy Principle for Learning and Acting},
year = {2010},
issue_date = {May 2010},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {38},
number = {1},
issn = {1076-9757},
abstract = {This paper proposes a method to construct an adaptive agent that is universal with respect to a given class of experts, where each expert is designed specifically for a particular environment. This adaptive control problem is formalized as the problem of minimizing the relative entropy of the adaptive agent from the expert that is most suitable for the unknown environment. If the agent is a passive observer, then the optimal solution is the well-known Bayesian predictor. However, if the agent is active, then its past actions need to be treated as causal interventions on the I/O stream rather than normal probability conditions. Here it is shown that the solution to this new variational problem is given by a stochastic controller called the Bayesian control rule, which implements adaptive behavior as a mixture of experts. Furthermore, it is shown that under mild assumptions, the Bayesian control rule converges to the control law of the most suitable expert.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {475–511},
numpages = {37}
}

@article{10.5555/1892211.1892222,
author = {Wu, Jianhui and Durfee, Edmund H.},
title = {Resource-Driven Mission-Phasing Techniques for Constrained Agents in Stochastic Environments},
year = {2010},
issue_date = {May 2010},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {38},
number = {1},
issn = {1076-9757},
abstract = {Because an agent's resources dictate what actions it can possibly take, it should plan which resources it holds over time carefully, considering its inherent limitations (such as power or payload restrictions), the competing needs of other agents for the same resources, and the stochastic nature of the environment. Such agents can, in general, achieve more of their objectives if they can use -- and even create -- opportunities to change which resources they hold at various times. Driven by resource constraints, the agents could break their overall missions into an optimal series of phases, optimally reconfiguring their resources at each phase, and optimally using their assigned resources in each phase, given their knowledge of the stochastic environment.In this paper, we formally define and analyze this constrained, sequential optimization problem in both the single-agent and multi-agent contexts. We present a family of mixed integer linear programming (MILP) formulations of this problem that can optimally create phases (when phases are not predefined) accounting for costs and limitations in phase creation. Because our formulations simultaneously also find the optimal allocations of resources at each phase and the optimal policies for using the allocated resources at each phase, they exploit structure across these coupled problems. This allows them to find solutions significantly faster (orders of magnitude faster in larger problems) than alternative solution techniques, as we demonstrate empirically.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {415–473},
numpages = {59}
}

@article{10.5555/1892211.1892221,
author = {Feldman, Alexander and Provan, Gregory and van Gemund, Arjan},
title = {Approximate Model-Based Diagnosis Using Greedy Stochastic Search},
year = {2010},
issue_date = {May 2010},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {38},
number = {1},
issn = {1076-9757},
abstract = {We propose a StochAstic Fault diagnosis AlgoRIthm, called SAFARI, which trades off guarantees of computing minimal diagnoses for computational efficiency. We empirically demonstrate, using the 74XXX and ISCAS85 suites of benchmark combinatorial circuits, that SAFARI achieves several orders-of-magnitude speedup over two well-known deterministic algorithms, CDA* and HA*, for multiple-fault diagnoses; further, SAFARI can compute a range of multiple-fault diagnoses that CDA* and HA* cannot. We also prove that SAFARI is optimal for a range of propositional fault models, such as the widely-used weak-fault models (models with ignorance of abnormal behavior). We discuss the optimality of SAFARI in a class of strong-fault circuit models with stuck-at failure modes. By modeling the algorithm itself as a Markov chain, we provide exact bounds on the minimality of the diagnosis computed. SAFARI also displays strong anytime behavior, and will return a diagnosis after any non-trivial inference time.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {371–413},
numpages = {43}
}

@article{10.5555/1892211.1892220,
author = {Babaioff, Moshe and Feldman, Michal and Nisan, Noam},
title = {Mixed Strategies in Combinatorial Agency},
year = {2010},
issue_date = {May 2010},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {38},
number = {1},
issn = {1076-9757},
abstract = {In many multiagent domains a set of agents exert effort towards a joint outcome, yet the individual effort levels cannot be easily observed. A typical example for such a scenario is routing in communication networks, where the sender can only observe whether the packet reached its destination, but often has no information about the actions of the intermediate routers, which influences the final outcome. We study a setting where a principal needs to motivate a team of agents whose combination of hidden efforts stochastically determines an outcome. In a companion paper we devise and study a basic "combinatorial agency" model for this setting, where the principal is restricted to inducing a pure Nash equilibrium. Here we study various implications of this restriction. First, we show that, in contrast to the case of observable efforts, inducing a mixed-strategies equilibrium may be beneficial for the principal. Second, we present a sufficient condition for technologies for which no gain can be generated. Third, we bound the principal's gain for various families of technologies. Finally, we study the robustness of mixed equilibria to coalitional deviations and the computational hardness of the optimal mixed equilibria.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {339–369},
numpages = {31}
}

@article{10.5555/1892211.1892219,
author = {Gange, Graeme and Stuckey, Peter J. and Lagoon, Vitaly},
title = {Fast Set Bounds Propagation Using a BDD-SAT Hybrid},
year = {2010},
issue_date = {May 2010},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {38},
number = {1},
issn = {1076-9757},
abstract = {Binary Decision Diagram (BDD) based set bounds propagation is a powerful approach to solving set-constraint satisfaction problems. However, prior BDD based techniques incur the significant overhead of constructing and manipulating graphs during search. We present a set-constraint solver which combines BDD-based set-bounds propagators with the learning abilities of a modern SAT solver. Together with a number of improvements beyond the basic algorithm, this solver is highly competitive with existing propagation based set constraint solvers.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {307–338},
numpages = {32}
}

@article{10.5555/1892211.1892218,
author = {Lesaint, David and Mehta, Deepak and O'Sullivan, Barry and Quesada, Luis and Wilson, Nic},
title = {Developing Approaches for Solving a Telecommunications Feature Subscription Problem},
year = {2010},
issue_date = {May 2010},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {38},
number = {1},
issn = {1076-9757},
abstract = {Call control features (e.g., call-divert, voice-mail) are primitive options to which users can subscribe off-line to personalise their service. The configuration of a feature subscription involves choosing and sequencing features from a catalogue and is subject to constraints that prevent undesirable feature interactions at run-time. When the subscription requested by a user is inconsistent, one problem is to find an optimal relaxation, which is a generalisation of the feedback vertex set problem on directed graphs, and thus it is an NP-hard task. We present several constraint programming formulations of the problem. We also present formulations using partial weighted maximum Boolean satisfiability and mixed integer linear programming. We study all these formulations by experimentally comparing them on a variety of randomly generated instances of the feature subscription problem.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {271–305},
numpages = {35}
}

@article{10.5555/1892211.1892217,
author = {Wittocx, Johan and Mari\"{e}n, Maarten and Denecker, Marc},
title = {Grounding FO and FO(ID) with Bounds},
year = {2010},
issue_date = {May 2010},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {38},
number = {1},
issn = {1076-9757},
abstract = {Grounding is the task of reducing a first-order theory and finite domain to an equivalent propositional theory. It is used as preprocessing phase in many logic-based reasoning systems. Such systems provide a rich first-order input language to a user and can rely on efficient propositional solvers to perform the actual reasoning.Besides a first-order theory and finite domain, the input for grounders contains in many applications also additional data. By exploiting this data, the size of the grounder's output can often be reduced significantly. A common practice to improve the efficiency of a grounder in this context is by manually adding semantically redundant information to the input theory, indicating where and when the grounder should exploit the data. In this paper we present a method to compute and add such redundant information automatically. Our method therefore simplifies the task of writing input theories that can be grounded efficiently by current systems.We first present our method for classical first-order logic (FO) theories. Then we extend it to FO(ID), the extension of FO with inductive definitions, which allows for more concise and comprehensive input theories. We discuss implementation issues and experimentally validate the practical applicability of our method.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {223–269},
numpages = {47}
}

@article{10.5555/1892211.1892216,
author = {Michelson, Matthew and Knoblock, Craig A.},
title = {Constructing Reference Sets from Unstructured, Ungrammatical Text},
year = {2010},
issue_date = {May 2010},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {38},
number = {1},
issn = {1076-9757},
abstract = {Vast amounts of text on the Web are unstructured and ungrammatical, such as classified ads, auction listings, forum postings, etc. We call such text "posts." Despite their inconsistent structure and lack of grammar, posts are full of useful information. This paper presents work on semi-automatically building tables of relational information, called "reference sets," by analyzing such posts directly. Reference sets can be applied to a number of tasks such as ontology maintenance and information extraction. Our reference-set construction method starts with just a small amount of background knowledge, and constructs tuples representing the entities in the posts to form a reference set. We also describe an extension to this approach for the special case where even this small amount of background knowledge is impossible to discover and use. To evaluate the utility of the machine-constructed reference sets, we compare them to manually constructed reference sets in the context of reference-set-based information extraction. Our results show the reference sets constructed by our method outperform manually constructed reference sets. We also compare the reference-set-based extraction approach using the machine-constructed reference set to supervised extraction approaches using generic features. These results demonstrate that using machine-constructed reference sets outperforms the supervised methods, even though the supervised methods require training data.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {189–221},
numpages = {33}
}

@article{10.5555/1892211.1892215,
author = {Androutsopoulos, Ion and Malakasiotis, Prodromos},
title = {A Survey of Paraphrasing and Textual Entailment Methods},
year = {2010},
issue_date = {May 2010},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {38},
number = {1},
issn = {1076-9757},
abstract = {Paraphrasing methods recognize, generate, or extract phrases, sentences, or longer natural language expressions that convey almost the same information. Textual entailment methods, on the other hand, recognize, generate, or extract pairs of natural language expressions, such that a human who reads (and trusts) the first element of a pair would most likely infer that the other element is also true. Paraphrasing can be seen as bidirectional textual entailment and methods from the two areas are often similar. Both kinds of methods are useful, at least in principle, in a wide range of natural language processing applications, including question answering, summarization, text generation, and machine translation. We summarize key ideas from the two areas by considering in turn recognition, generation, and extraction methods, also pointing to prominent articles and resources.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {135–187},
numpages = {53}
}

@article{10.5555/1892211.1892214,
author = {Yeoh, William and Felner, Ariel and Koenig, Sven},
title = {BnB-ADOPT: An Asynchronous Branch-and-Bound DCOP Algorithm},
year = {2010},
issue_date = {May 2010},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {38},
number = {1},
issn = {1076-9757},
abstract = {Distributed constraint optimization (DCOP) problems are a popular way of formulating and solving agent-coordination problems. A DCOP problem is a problem where several agents coordinate their values such that the sum of the resulting constraint costs is minimal. It is often desirable to solve DCOP problems with memory-bounded and asynchronous algorithms. We introduce Branch-and-Bound ADOPT (BnB-ADOPT), a memory-bounded asynchronous DCOP search algorithm that uses the message-passing and communication framework of ADOPT (Modi, Shen, Tambe, & Yokoo, 2005), a well known memory-bounded asynchronous DCOP search algorithm, but changes the search strategy of ADOPT from best-first search to depth-first branch-and-bound search. Our experimental results show that BnB-ADOPT finds cost-minimal solutions up to one order of magnitude faster than ADOPT for a variety of large DCOP problems and is as fast as NCBB, a memory-bounded synchronous DCOP search algorithm, for most of these DCOP problems. Additionally, it is often desirable to find bounded-error solutions for DCOP problems within a reasonable amount of time since finding cost-minimal solutions is NP-hard. The existing bounded-error approximation mechanism allows users only to specify an absolute error bound on the solution cost but a relative error bound is often more intuitive. Thus, we present two new bounded-error approximation mechanisms that allow for relative error bounds and implement them on top of BnB-ADOPT.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {85–133},
numpages = {49}
}

@article{10.5555/1892211.1892213,
author = {Cayrol, Claudette and de Saint-Cyr, Florence Dupin and Lagasquie-Schiex, Marie-Christine},
title = {Change in Abstract Argumentation Frameworks: Adding an Argument},
year = {2010},
issue_date = {May 2010},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {38},
number = {1},
issn = {1076-9757},
abstract = {In this paper, we address the problem of change in an abstract argumentation system. We focus on a particular change: the addition of a new argument which interacts with previous arguments. We study the impact of such an addition on the outcome of the argumentation system, more particularly on the set of its extensions. Several properties for this change operation are defined by comparing the new set of extensions to the initial one, these properties are called "structural" when the comparisons are based on set-cardinality or set-inclusion relations. Several other properties are proposed where comparisons are based on the status of some particular arguments: the accepted arguments; these properties refer to the "evolution of this status" during the change, e.g., Monotony and Priority to Recency. All these properties may be more or less desirable according to specific applications. They are studied under two particular semantics: the grounded and preferred semantics.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {49–84},
numpages = {36}
}

@article{10.5555/1892211.1892212,
author = {Katrenko, Sophia and Adriaans, Pieter and van Someren, Maarten},
title = {Using Local Alignments for Relation Recognition},
year = {2010},
issue_date = {May 2010},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {38},
number = {1},
issn = {1076-9757},
abstract = {This paper discusses the problem of marrying structural similarity with semantic relatedness for Information Extraction from text. Aiming at accurate recognition of relations, we introduce local alignment kernels and explore various possibilities of using them for this task. We give a definition of a local alignment (LA) kernel based on the Smith-Waterman score as a sequence similarity measure and proceed with a range of possibilities for computing similarity between elements of sequences. We show how distributional similarity measures obtained from unlabeled data can be incorporated into the learning task as semantic knowledge. Our experiments suggest that the LA kernel yields promising results on various biomedical corpora outperforming two baselines by a large margin. Additional series of experiments have been conducted on the data sets of seven general relation types, where the performance of the LA kernel is comparable to the current state-of-the-art results.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {1–48},
numpages = {48}
}

@article{10.5555/1861751.1861763,
author = {Engel, Yagil and Wellman, Michael P.},
title = {Multiattribute Auctions Based on Generalized Additive Independence},
year = {2010},
issue_date = {January 2010},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {37},
number = {1},
issn = {1076-9757},
abstract = {We develop multiattribute auctions that accommodate generalized additive independent (GAI) preferences. We propose an iterative auction mechanism that maintains prices on potentially overlapping GAI clusters of attributes, thus decreases elicitation and computational burden, and creates an open competition among suppliers over a multidimensional domain. Most significantly, the auction is guaranteed to achieve surplus which approximates optimal welfare up to a small additive factor, under reasonable equilibrium strategies of traders. The main departure of GAI auctions from previous literature is to accommodate non-additive trader preferences, hence allowing traders to condition their evaluation of specific attributes on the value of other attributes. At the same time, the GAI structure supports a compact representation of prices, enabling a tractable auction process. We perform a simulation study, demonstrating and quantifying the significant efficiency advantage of more expressive preference modeling. We draw random GAI-structured utility functions with various internal structures, generate additive functions that approximate the GAI utility, and compare the performance of the auctions using the two representations. We find that allowing traders to express existing dependencies among attributes improves the economic efficiency of multiattribute auctions.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {479–526},
numpages = {48}
}

@article{10.5555/1861751.1861762,
author = {van der Hoek, Wiebe and Walther, Dirk and Wooldridge, Michael},
title = {Reasoning about the Transfer of Control},
year = {2010},
issue_date = {January 2010},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {37},
number = {1},
issn = {1076-9757},
abstract = {We present DCL-PC: a logic for reasoning about how the abilities of agents and coalitions of agents are altered by transferring control from one agent to another. The logical foundation of DCL-PC is CL-PC, a logic for reasoning about cooperation in which the abilities of agents and coalitions of agents stem from a distribution of atomic Boolean variables to individual agents - the choices available to a coalition correspond to assignments to the variables the coalition controls. The basic modal constructs of CL-PC are of the form 'coalition C can cooperate to bring about ϕ'. DCL-PC extends CL-PC with dynamic logic modalities in which atomic programs are of the form 'agent i gives control of variable p to agent j'; as usual in dynamic logic, these atomic programs may be combined using sequence, iteration, choice, and test operators to form complex programs. By combining such dynamic transfer programs with cooperation modalities, it becomes possible to reason about how the power of agents and coalitions is affected by the transfer of control. We give two alternative semantics for the logic: a 'direct' semantics, in which we capture the distributions of Boolean variables to agents; and a more conventional Kripke semantics. We prove that these semantics are equivalent, and then present an axiomatization for the logic. We investigate the computational complexity of model checking and satisfiability for DCL-PC, and show that both problems are PSPACE-complete (and hence no worse than the underlying logic CL-PC). Finally, we investigate the characterisation of control in DCL-PC. We distinguish between first-order control - the ability of an agent or coalition to control some state of affairs through the assignment of values to the variables under the control of the agent or coalition - and second-order control - the ability of an agent to exert control over the control that other agents have by transferring variables to other agents. We give a logical characterisation of second-order control.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {437–478},
numpages = {42}
}

@article{10.5555/1861751.1861761,
author = {Chen, David L. and Kim, Joohyun and Mooney, Raymond J.},
title = {Training a Multilingual Sportscaster: Using Perceptual Context to Learn Language},
year = {2010},
issue_date = {January 2010},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {37},
number = {1},
issn = {1076-9757},
abstract = {We present a novel framework for learning to interpret and generate language using only perceptual context as supervision. We demonstrate its capabilities by developing a system that learns to sportscast simulated robot soccer games in both English and Korean without any language-specific prior knowledge. Training employs only ambiguous supervision consisting of a stream of descriptive textual comments and a sequence of events extracted from the simulation trace. The system simultaneously establishes correspondences between individual comments and the events that they describe while building a translation model that supports both parsing and generation. We also present a novel algorithm for learning which events are worth describing. Human evaluations of the generated commentaries indicate they are of reasonable quality and in some cases even on par with those produced by humans for our limited domain.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {397–436},
numpages = {40}
}

@article{10.5555/1861751.1861760,
author = {Aras, Raghav and Dutech, Alain},
title = {An Investigation into Mathematical Programming for Finite Horizon Decentralized POMDPs},
year = {2010},
issue_date = {January 2010},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {37},
number = {1},
issn = {1076-9757},
abstract = {Decentralized planning in uncertain environments is a complex task generally dealt with by using a decision-theoretic approach, mainly through the framework of Decentralized Partially Observable Markov Decision Processes (DEC-POMDPs). Although DEC-POMDPS are a general and powerful modeling tool, solving them is a task with an overwhelming complexity that can be doubly exponential. In this paper, we study an alternate formulation of DEC-POMDPs relying on a sequence-form representation of policies. From this formulation, we show how to derive Mixed Integer Linear Programming (MILP) problems that, once solved, give exact optimal solutions to the DEC-POMDPs. We show that these MILPs can be derived either by using some combinatorial characteristics of the optimal solutions of the DEC-POMDPs or by using concepts borrowed from game theory. Through an experimental validation on classical test problems from the DEC-POMDP literature, we compare our approach to existing algorithms. Results show that mathematical programming outperforms dynamic programming but is less efficient than forward search, except for some particular problems.The main contributions of this work are the use of mathematical programming for DEC-POMDPs and a better understanding of DEC-POMDPs and of their solutions. Besides, we argue that our alternate representation of DEC-POMDPs could be helpful for designing novel algorithms looking for approximate solutions to DEC-POMDPs.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {329–396},
numpages = {68}
}

@article{10.5555/1861751.1861759,
author = {Mateescu, Robert and Kask, Kalev and Gogate, Vibhav and Dechter, Rina},
title = {Join-Graph Propagation Algorithms},
year = {2010},
issue_date = {January 2010},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {37},
number = {1},
issn = {1076-9757},
abstract = {The paper investigates parameterized approximate message-passing schemes that are based on bounded inference and are inspired by Pearl's belief propagation algorithm (BP). We start with the bounded inference mini-clustering algorithm and then move to the iterative scheme called Iterative Join-Graph Propagation (IJGP), that combines both iteration and bounded inference. Algorithm IJGP belongs to the class of Generalized Belief Propagation algorithms, a framework that allowed connections with approximate algorithms from statistical physics and is shown empirically to surpass the performance of mini-clustering and belief propagation, as well as a number of other state-of-the-art algorithms on several classes of networks. We also provide insight into the accuracy of iterative BP and IJGP by relating these algorithms to well known classes of constraint propagation schemes},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {279–328},
numpages = {50}
}

@article{10.5555/1861751.1861758,
author = {Qu, Shaolin and Chai, Joyce Y.},
title = {Context-Based Word Acquisition for Situated Dialogue in a Virtual World},
year = {2010},
issue_date = {January 2010},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {37},
number = {1},
issn = {1076-9757},
abstract = {To tackle the vocabulary problem in conversational systems, previous work has applied unsupervised learning approaches on co-occurring speech and eye gaze during interaction to automatically acquire new words. Although these approaches have shown promise, several issues related to human language behavior and human-machine conversation have not been addressed. First, psycholinguistic studies have shown certain temporal regularities between human eye movement and language production. While these regularities can potentially guide the acquisition process, they have not been incorporated in the previous unsupervised approaches. Second, conversational systems generally have an existing knowledge base about the domain and vocabulary. While the existing knowledge can potentially help bootstrap and constrain the acquired new words, it has not been incorporated in the previous models. Third, eye gaze could serve different functions in human-machine conversation. Some gaze streams may not be closely coupled with speech stream, and thus are potentially detrimental to word acquisition. Automated recognition of closely-coupled speech-gaze streams based on conversation context is important. To address these issues, we developed new approaches that incorporate user language behavior, domain knowledge, and conversation context in word acquisition. We evaluated these approaches in the context of situated dialogue in a virtual world. Our experimental results have shown that incorporating the above three types of contextual information significantly improves word acquisition performance.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {247–278},
numpages = {32}
}

@article{10.5555/1861751.1861757,
author = {Varzinczak, Ivan Jos\'{e}},
title = {On Action Theory Change},
year = {2010},
issue_date = {January 2010},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {37},
number = {1},
issn = {1076-9757},
abstract = {As historically acknowledged in the Reasoning about Actions and Change community, intuitiveness of a logical domain description cannot be fully automated. Moreover, like any other logical theory, action theories may also evolve, and thus knowledge engineers need revision methods to help in accommodating new incoming information about the behavior of actions in an adequate manner. The present work is about changing action domain descriptions in multimodal logic. Its contribution is threefold: first we revisit the semantics of action theory contraction proposed in previous work, giving more robust operators that express minimal change based on a notion of distance between Kripke-models. Second we give algorithms for syntactical action theory contraction and establish their correctness with respect to our semantics for those action theories that satisfy a principle of modularity investigated in previous work. Since modularity can be ensured for every action theory and, as we show here, needs to be computed at most once during the evolution of a domain description, it does not represent a limitation at all to the method here studied. Finally we state AGM-like postulates for action theory contraction and assess the behavior of our operators with respect to them. Moreover, we also address the revision counterpart of action theory change, showing that it benefits from our semantics for contraction.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {189–246},
numpages = {58}
}

@article{10.5555/1861751.1861756,
author = {Turney, Peter D. and Pantel, Patrick},
title = {From Frequency to Meaning: Vector Space Models of Semantics},
year = {2010},
issue_date = {January 2010},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {37},
number = {1},
issn = {1076-9757},
abstract = {Computers understand very little of the meaning of human language. This profoundly limits our ability to give instructions to computers, the ability of computers to explain their actions to us, and the ability of computers to analyse and process text. Vector space models (VSMs) of semantics are beginning to address these limits. This paper surveys the use of VSMs for semantic processing of text. We organize the literature on VSMs according to the structure of the matrix in a VSM. There are currently three broad classes of VSMs, based on term-document, word-context, and pair-pattern matrices, yielding three classes of applications. We survey a broad range of applications in these three categories and we take a detailed look at a specific open source project in each category. Our goal in this survey is to show the breadth of applications of VSMs for semantics, to provide a new perspective on VSMs for those who are already familiar with the area, and to provide pointers into the literature for those who are less familiar with the field.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {141–188},
numpages = {48}
}

@article{10.5555/1861751.1861755,
author = {Andersen, Henrik Reif and Hadzic, Tarik and Pisinger, David},
title = {Interactive Cost Configuration over Decision Diagrams},
year = {2010},
issue_date = {January 2010},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {37},
number = {1},
issn = {1076-9757},
abstract = {In many AI domains such as product configuration, a user should interactively specify a solution that must satisfy a set of constraints. In such scenarios, offline compilation of feasible solutions into a tractable representation is an important approach to delivering efficient backtrack-free user interaction online. In particular, binary decision diagrams (BDDs) have been successfully used as a compilation target for product and service configuration. In this paper we discuss how to extend BDD-based configuration to scenarios involving cost functions which express user preferences.We first show that an efficient, robust and easy to implement extension is possible if the cost function is additive, and feasible solutions are represented using multi-valued decision diagrams (MDDs). We also discuss the effect on MDD size if the cost function is non-additive or if it is encoded explicitly into MDD. We then discuss interactive configuration in the presence of multiple cost functions. We prove that even in its simplest form, multiple-cost configuration is NP-hard in the input MDD. However, for solving two-cost configuration we develop a pseudo-polynomial scheme and a fully polynomial approximation scheme. The applicability of our approach is demonstrated through experiments over real-world configuration models and product-catalogue datasets. Response times are generally within a fraction of a second even for very large instances.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {99–140},
numpages = {42}
}

@article{10.5555/1861751.1861754,
author = {Dobzinski, Shahar and Nisan, Noam},
title = {Mechanisms for Multi-Unit Auctions},
year = {2010},
issue_date = {January 2010},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {37},
number = {1},
issn = {1076-9757},
abstract = {We present an incentive-compatible polynomial-time approximation scheme for multiunit auctions with general k-minded player valuations. The mechanism fully optimizes over an appropriately chosen sub-range of possible allocations and then uses VCG payments over this sub-range. We show that obtaining a fully polynomial-time incentive-compatible approximation scheme, at least using VCG payments, is NP-hard. For the case of valuations given by black boxes, we give a polynomial-time incentive-compatible 2-approximation mechanism and show that no better is possible, at least using VCG payments.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {85–98},
numpages = {14}
}

@article{10.5555/1861751.1861753,
author = {Zahavi, Uzi and Felner, Ariel and Burch, Neil and Holte, Robert C.},
title = {Predicting the Performance of IDA* Using Conditional Distributions},
year = {2010},
issue_date = {January 2010},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {37},
number = {1},
issn = {1076-9757},
abstract = {Korf, Reid, and Edelkamp introduced a formula to predict the number of nodes IDA* will expand on a single iteration for a given consistent heuristic, and experimentally demonstrated that it could make very accurate predictions. In this paper we show that, in addition to requiring the heuristic to be consistent, their formula's predictions are accurate only at levels of the brute-force search tree where the heuristic values obey the unconditional distribution that they defined and then used in their formula. We then propose a new formula that works well without these requirements, i.e., it can make accurate predictions of IDA*'s performance for inconsistent heuristics and if the heuristic values in any level do not obey the unconditional distribution. In order to achieve this we introduce the conditional distribution of heuristic values which is a generalization of their unconditional heuristic distribution. We also provide extensions of our formula that handle individual start states and the augmentation of IDA* with bidirectional pathmax (BPMX), a tech nique for propagating heuristic values when inconsistent heuristics are used. Experimental results demonstrate the accuracy of our new method and all its variations.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {41–84},
numpages = {44}
}

@article{10.5555/1861751.1861752,
author = {Tsatsaronis, George and Varlamis, Iraklis and Vazirgiannis, Michalis},
title = {Text Relatedness Based on a Word Thesaurus},
year = {2010},
issue_date = {January 2010},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {37},
number = {1},
issn = {1076-9757},
abstract = {The computation of relatedness between two fragments of text in an automated manner requires taking into account a wide range of factors pertaining to the meaning the two fragments convey, and the pairwise relations between their words. Without doubt, a measure of relatedness between text segments must take into account both the lexical and the semantic relatedness between words. Such a measure that captures well both aspects of text relatedness may help in many tasks, such as text retrieval, classification and clustering. In this paper we present a new approach for measuring the semantic relatedness between words based on their implicit semantic links. The approach exploits only a word thesaurus in order to devise implicit semantic links between words. Based on this approach, we introduce Omiotis, a new measure of semantic relatedness between texts which capitalizes on the word-to-word semantic relatedness measure (SR) and extends it to measure the relatedness between texts. We gradually validate our method: we first evaluate the performance of the semantic relatedness measure between individual words, covering word-to-word similarity and relatedness, synonym identification and word analogy; then, we proceed with evaluating the performance of our method in measuring text-to-text semantic relatedness in two tasks, namely sentence-to-sentence similarity and paraphrase recognition. Experimental evaluation shows that the proposed method outperforms every lexicon-based method of semantic relatedness in the selected tasks and the used data sets, and competes well against corpus-based and hybrid approaches.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {1–40},
numpages = {40}
}

@article{10.5555/1734953.1734966,
author = {Keyder, Emil and Geffner, Hector},
title = {Soft Goals Can Be Compiled Away},
year = {2009},
issue_date = {September 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {36},
number = {1},
issn = {1076-9757},
abstract = {Soft goals extend the classical model of planning with a simple model of preferences. The best plans are then not the ones with least cost but the ones with maximum utility, where the utility of a plan is the sum of the utilities of the soft goals achieved minus the plan cost. Finding plans with high utility appears to involve two linked problems: choosing a subset of soft goals to achieve and finding a low-cost plan to achieve them. New search algorithms and heuristics have been developed for planning with soft goals, and a new track has been introduced in the International Planning Competition (IPC) to test their performance. In this note, we show however that these extensions are not needed: soft goals do not increase the expressive power of the basic model of planning with action costs, as they can easily be compiled away. We apply this compilation to the problems of the net-benefit track of the most recent IPC, and show that optimal and satisficing cost-based planners do better on the compiled problems than optimal and satisficing netbenefit planners on the original problems with explicit soft goals. Furthermore, we show that penalties, or negative preferences expressing conditions to avoid, can also be compiled away using a similar idea.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {547–556},
numpages = {10}
}

@article{10.5555/1734953.1734965,
author = {Greenwald, Amy and Lee, Seong Jae and Naroditskiy, Victor},
title = {RoxyBot-06: Stochastic Prediction and Optimization in TAC Travel},
year = {2009},
issue_date = {September 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {36},
number = {1},
issn = {1076-9757},
abstract = {In this paper, we describe our autonomous bidding agent, RoxyBot, who emerged victorious in the travel division of the 2006 Trading Agent Competition in a photo finish. At a high level, the design of many successful trading agents can be summarized as follows: (i) price prediction: build a model of market prices; and (ii) optimization: solve for an approximately optimal set of bids, given this model. To predict, RoxyBot builds a stochastic model of market prices by simulating simultaneous ascending auctions. To optimize, RoxyBot relies on the sample average approximation method, a stochastic optimization technique.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {513–546},
numpages = {34}
}

@article{10.5555/1734953.1734964,
author = {Jonsson, Anders},
title = {The Role of Macros in Tractable Planning},
year = {2009},
issue_date = {September 2009},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {36},
number = {1},
issn = {1076-9757},
abstract = {This paper presents several new tractability results for planning based on macros. We describe an algorithm that optimally solves planning problems in a class that we call inverted tree reducible, and is provably tractable for several subclasses of this class. By using macros to store partial plans that recur frequently in the solution, the algorithm is polynomial in time and space even for exponentially long plans. We generalize the inverted tree reducible class in several ways and describe modifications of the algorithm to deal

license: Unlicense

repository: goyalkaraniit/acm-cr

repo_name: goyalkaraniit/acm-cr