text:
by integrating local search solvers as candidate solvers, by predicting performance score instead of runtime, and by using hierarchical hardness models that take into account different types of SAT instances. We demonstrate the effectiveness of these new techniques in extensive experimental results on data sets including instances from the most recent SAT competition.},
journal = {J. Artif. Int. Res.},
month = jun,
pages = {565–606},
numpages = {42}
}

@article{10.5555/1622673.1622686,
author = {Bouveret, Sylvain and Lang, J\'{e}r\^{o}me},
title = {Efficiency and Envy-Freeness in Fair Division of Indivisible Goods: Logical Representation and Complexity},
year = {2008},
issue_date = {May 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {32},
number = {1},
issn = {1076-9757},
abstract = {We consider the problem of allocating fairly a set of indivisible goods among agents from the point of view of compact representation and computational complexity. We start by assuming that agents have dichotomous preferences expressed by propositional formulae. We express efficiency and envy-freeness in a logical setting, which reveals unexpected connections to nonmonotonic reasoning. Then we identify the complexity of determining whether there exists an efficient and envy-free allocation, for several notions of efficiency, when preferences are represented in a succinct way (as well as restrictions of this problem). We first study the problem under the assumption that preferences are dichotomous, and then in the general case.},
journal = {J. Artif. Int. Res.},
month = jun,
pages = {525–564},
numpages = {40}
}

@article{10.5555/1622673.1622685,
author = {Stulp, Freek and Beetz, Michael},
title = {Refining the Execution of Abstract Actions with Learned Action Models},
year = {2008},
issue_date = {May 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {32},
number = {1},
issn = {1076-9757},
abstract = {Robots reason about abstract actions, such as go to position 'l', in order to decide what to do or to generate plans for their intended course of action. The use of abstract actions enables robots to employ small action libraries, which reduces the search space for decision making. When executing the actions, however, the robot must tailor the abstract actions to the specific task and situation context at hand.In this article we propose a novel robot action execution system that learns success and performance models for possible specializations of abstract actions. At execution time, the robot uses these models to optimize the execution of abstract actions to the respective task contexts. The robot can so use abstract actions for efficient reasoning, without compromising the performance of action execution. We show the impact of our action execution model in three robotic domains and on two kinds of action execution problems: (1) the instantiation of free action parameters to optimize the expected performance of action sequences; (2) the automatic introduction of additional subgoals to make action sequences more reliable.},
journal = {J. Artif. Int. Res.},
month = jun,
pages = {487–523},
numpages = {37}
}

@article{10.5555/1622673.1622684,
author = {Cs\'{a}ji, Bal\'{a}zs Csan\'{a}d and Monostori, L\'{a}szl\'{o}},
title = {Adaptive Stochastic Resource Control: A Machine Learning Approach},
year = {2008},
issue_date = {May 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {32},
number = {1},
issn = {1076-9757},
abstract = {The paper investigates stochastic resource allocation problems with scarce, reusable resources and non-preemtive, time-dependent, interconnected tasks. This approach is a natural generalization of several standard resource management problems, such as scheduling and transportation problems. First, reactive solutions are considered and defined as control policies of suitably reformulated Markov decision processes (MDPs). We argue that this reformulation has several favorable properties, such as it has finite state and action spaces, it is aperiodic, hence all policies are proper and the space of control policies can be safely restricted. Next, approximate dynamic programming (ADP) methods, such as fitted Q-learning, are suggested for computing an efficient control policy. In order to compactly maintain the cost-to-go function, two representations are studied: hash tables and support vector regression (SVR), particularly, ν-SVRs. Several additional improvements, such as the application of limited-lookahead rollout algorithms in the initial phases, action space decomposition, task clustering and distributed sampling are investigated, too. Finally, experimental results on both benchmark and industry-related data are presented.},
journal = {J. Artif. Int. Res.},
month = jun,
pages = {453–486},
numpages = {34}
}

@article{10.5555/1622673.1622683,
author = {Bulitko, Vadim and Lu\v{s}trek, Mitja and Schaeffer, Jonathan and Bj\"{o}rnsson, Yngvi and Sigmundarson, Sverrir},
title = {Dynamic Control in Real-Time Heuristic Search},
year = {2008},
issue_date = {May 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {32},
number = {1},
issn = {1076-9757},
abstract = {Real-time heuristic search is a challenging type of agent-centered search because the agent's planning time per action is bounded by a constant independent of problem size. A common problem that imposes such restrictions is pathfinding in modern computer games where a large number of units must plan their paths simultaneously over large maps. Common search algorithms (e.g., A*, IDA*, D*, ARA*, AD*) are inherently not real-time and may lose completeness when a constant bound is imposed on per-action planning time. Real-time search algorithms retain completeness but frequently produce unacceptably suboptimal solutions. In this paper, we extend classic and modern real-time search algorithms with an automated mechanism for dynamic depth and subgoal selection. The new algorithms remain real-time and complete. On large computer game maps, they find paths within 7% of optimal while on average expanding roughly a single state per action. This is nearly a three-fold improvement in suboptimality over the existing state-of-the-art algorithms and, at the same time, a 15-fold improvement in the amount of planning per action.},
journal = {J. Artif. Int. Res.},
month = jun,
pages = {419–452},
numpages = {34}
}

@article{10.5555/1622673.1622682,
author = {Dubois, Didier and Fargier, H\'{e}l\`{e}ne and Bonnefon, Jean-Fran\c{c}ois},
title = {On the Qualitative Comparison of Decisions Having Positive and Negative Features},
year = {2008},
issue_date = {May 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {32},
number = {1},
issn = {1076-9757},
abstract = {Making a decision is often a matter of listing and comparing positive and negative arguments. In such cases, the evaluation scale for decisions should be considered bipolar, that is, negative and positive values should be explicitly distinguished. That is what is done, for example, in Cumulative Prospect Theory. However, contrary to the latter framework that presupposes genuine numerical assessments, human agents often decide on the basis of an ordinal ranking of the pros and the cons, and by focusing on the most salient arguments. In other terms, the decision process is qualitative as well as bipolar. In this article, based on a bipolar extension of possibility theory, we define and axiomatically characterize several decision rules tailored for the joint handling of positive and negative arguments in an ordinal setting. The simplest rules can be viewed as extensions of the maximin and maximax criteria to the bipolar case, and consequently suffer from poor decisive power. More decisive rules that refine the former are also proposed. These refinements agree both with principles of efficiency and with the spirit of order-of-magnitude reasoning, that prevails in qualitative decision theory. The most refined decision rule uses leximin rankings of the pros and the cons, and the ideas of counting arguments of equal strength and cancelling pros by cons. It is shown to come down to a special case of Cumulative Prospect Theory, and to subsume the "Take the Best" heuristic studied by cognitive psychologists.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {385–417},
numpages = {33}
}

@article{10.5555/1622673.1622681,
author = {Liu, Fei Tony and Ting, Kai Ming and Yu, Yang and Zhou, Zhi-Hua},
title = {Spectrum of Variable-Random Trees},
year = {2008},
issue_date = {May 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {32},
number = {1},
issn = {1076-9757},
abstract = {In this paper, we show that a continuous spectrum of randomisation exists, in which most existing tree randomisations are only operating around the two ends of the spectrum. That leaves a huge part of the spectrum largely unexplored. We propose a base learner VR-Tree which generates trees with variable-randomness. VR-Trees are able to span from the conventional deterministic trees to the complete-random trees using a probabilistic parameter. Using VR-Trees as the base models, we explore the entire spectrum of randomised ensembles, together with Bagging and Random Subspace. We discover that the two halves of the spectrum have their distinct characteristics; and the understanding of which allows us to propose a new approach in building better decision tree ensembles. We name this approach Coalescence, which coalesces a number of points in the random-half of the spectrum. Coalescence acts as a committee of "experts" to cater for unforeseeable conditions presented in training data. Coalescence is found to perform better than any single operating point in the spectrum, without the need to tune to a specific level of randomness. In our empirical study, Coalescence ranks top among the benchmarking ensemble methods including Random Forests, Random Subspace and C5 Boosting; and only Coalescence is significantly better than Bagging and Max-Diverse Ensemble among all the methods in the comparison. Although Coalescence is not significantly better than Random Forests, we have identified conditions under which one will perform better than the other.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {355–384},
numpages = {30}
}

@article{10.5555/1622673.1622680,
author = {Oliehoek, Frans A. and Spaan, Matthijs T. J. and Vlassis, Nikos},
title = {Optimal and Approximate Q-Value Functions for Decentralized POMDPs},
year = {2008},
issue_date = {May 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {32},
number = {1},
issn = {1076-9757},
abstract = {Decision-theoretic planning is a popular approach to sequential decision making problems, because it treats uncertainty in sensing and acting in a principled way. In single-agent frameworks like MDPs and POMDPs, planning can be carried out by resorting to Q-value functions: an optimal Q-value function Q* is computed in a recursive manner by dynamic programming, and then an optimal policy is extracted from Q*. In this paper we study whether similar Q-value functions can be defined for decentralized POMDP models (Dec-POMDPs), and how policies can be extracted from such value functions. We define two forms of the optimal Q-value function for Dec-POMDPs: one that gives a normative description as the Q-value function of an optimal pure joint policy and another one that is sequentially rational and thus gives a recipe for computation. This computation, however, is infeasible for all but the smallest problems. Therefore, we analyze various approximate Q-value functions that allow for efficient computation. We describe how they relate, and we prove that they all provide an upper bound to the optimal Q-value function Q*. Finally, unifying some previous approaches for solving Dec-POMDPs, we describe a family of algorithms for extracting policies from such Q-value functions, and perform an experimental evaluation on existing test problems, including a new firefighting benchmark problem.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {289–353},
numpages = {65}
}

@article{10.5555/1622673.1622679,
author = {Katz, Michael and Domshlak, Carmel},
title = {New Islands of Tractability of Cost-Optimal Planning},
year = {2008},
issue_date = {May 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {32},
number = {1},
issn = {1076-9757},
abstract = {We study the complexity of cost-optimal classical planning over propositional state variables and unary-effect actions. We discover novel problem fragments for which such optimization is tractable, and identify certain conditions that differentiate between tractable and intractable problems. These results are based on exploiting both structural and syntactic characteristics of planning problems. Specifically, following Brafman and Domshlak (2003), we relate the complexity of planning and the topology of the causal graph. The main results correspond to tractability of cost-optimal planning for propositional problems with polytree causal graphs that either have O(1)-bounded in-degree, or are induced by actions having at most one prevail condition each. Almost all our tractability results are based on a constructive proof technique that connects between certain tools from planning and tractable constraint optimization, and we believe this technique is of interest on its own due to a clear evidence for its robustness.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {203–288},
numpages = {86}
}

@article{10.5555/1622673.1622678,
author = {Goldman, Claudia V. and Zilberstein, Shlomo},
title = {Communication-Based Decomposition Mechanisms for Decentralized MDPs},
year = {2008},
issue_date = {May 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {32},
number = {1},
issn = {1076-9757},
abstract = {Multi-agent planning in stochastic environments can be framed formally as a decentralized Markov decision problem. Many real-life distributed problems that arise in manufacturing, multi-robot coordination and information gathering scenarios can be formalized using this framework. However, finding the optimal solution in the general case is hard, limiting the applicability of recently developed algorithms. This paper provides a practical approach for solving decentralized control problems when communication among the decision makers is possible, but costly. We develop the notion of communication-based mechanism that allows us to decompose a decentralized MDP into multiple single-agent problems. In this framework, referred to as decentralized semi-Markov decision process with direct communication (Dec-SMDP-Com), agents operate separately between communications. We show that finding an optimal mechanism is equivalent to solving optimally a Dec-SMDP-Com. We also provide a heuristic search algorithm that converges on the optimal decomposition. Restricting the decomposition to some specific types of local behaviors reduces significantly the complexity of planning. In particular, we present a polynomial-time algorithm for the case in which individual agents perform goal-oriented behaviors between communications. The paper concludes with an additional tractable algorithm that enables the introduction of human knowledge, thereby reducing the overall problem to finding the best time to communicate. Empirical results show that these approaches provide good approximate solutions.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {169–202},
numpages = {34}
}

@article{10.5555/1622673.1622677,
author = {Terekhov, Daria and Beck, J. Christopher},
title = {A Constraint Programming Approach for Solving a Queueing Control Problem},
year = {2008},
issue_date = {May 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {32},
number = {1},
issn = {1076-9757},
abstract = {In a facility with front room and back room operations, it is useful to switch workers between the rooms in order to cope with changing customer demand. Assuming stochastic customer arrival and service times, we seek a policy for switching workers such that the expected customer waiting time is minimized while the expected back room staffing is sufficient to perform all work. Three novel constraint programming models and several shaving procedures for these models are presented. Experimental results show that a model based on closed-form expressions together with a combination of shaving procedures is the most efficient. This model is able to find and prove optimal solutions for many problem instances within a reasonable run-time. Previously, the only available approach was a heuristic algorithm. Furthermore, a hybrid method combining the heuristic and the best constraint programming method is shown to perform as well as the heuristic in terms of solution quality over time, while achieving the same performance in terms of proving optimality as the pure constraint programming model. This is the first work of which we are aware that solves such queueing-based problems with constraint programming.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {123–167},
numpages = {45}
}

@article{10.5555/1622673.1622676,
author = {van den Broek, Bart and Wiegerinck, Wim and Kappen, Bert},
title = {Graphical Model Inference in Optimal Control of Stochastic Multi-Agent Systems},
year = {2008},
issue_date = {May 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {32},
number = {1},
issn = {1076-9757},
abstract = {In this article we consider the issue of optimal control in collaborative multi-agent systems with stochastic dynamics. The agents have a joint task in which they have to reach a number of target states. The dynamics of the agents contains additive control and additive noise, and the autonomous part factorizes over the agents. Full observation of the global state is assumed. The goal is to minimize the accumulated joint cost, which consists of integrated instantaneous costs and a joint end cost. The joint end cost expresses the joint task of the agents. The instantaneous costs are quadratic in the control and factorize over the agents. The optimal control is given as a weighted linear combination of single-agent to single-target controls. The single-agent to single-target controls are expressed in terms of diffusion processes. These controls, when not closed form expressions, are formulated in terms of path integrals, which are calculated approximately by Metropolis-Hastings sampling. The weights in the control are interpreted as marginals of a joint distribution over agent to target assignments. The structure of the latter is represented by a graphical model, and the marginals are obtained by graphical model inference. Exact inference of the graphical model will break down in large systems, and so approximate inference methods are needed. We use naive mean field approximation and belief propagation to approximate the optimal control in systems with linear dynamics. We compare the approximate inference methods with the exact solution, and we show that they can accurately compute the optimal control. Finally, we demonstrate the control method in multi-agent systems with nonlinear dynamics consisting of up to 80 agents that have to reach an equal number of target states.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {95–122},
numpages = {28}
}

@article{10.5555/1622673.1622675,
author = {Analyti, Anastasia and Antoniou, Grigoris and Dam\'{a}sio, Carlos Viegas and Wagner, Gerd},
title = {Extended RDF as a Semantic Foundation of Rule Markup Languages},
year = {2008},
issue_date = {May 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {32},
number = {1},
issn = {1076-9757},
abstract = {Ontologies and automated reasoning are the building blocks of the Semantic Web initiative. Derivation rules can be included in an ontology to define derived concepts, based on base concepts. For example, rules allow to define the extension of a class or property, based on a complex relation between the extensions of the same or other classes and properties. On the other hand, the inclusion of negative information both in the form of negation-as-failure and explicit negative information is also needed to enable various forms of reasoning. In this paper, we extend RDF graphs with weak and strong negation, as well as derivation rules. The ERDF stable model semantics of the extended framework (Extended RDF) is defined, extending RDF(S) semantics. A distinctive feature of our theory, which is based on Partial Logic, is that both truth and falsity extensions of properties and classes are considered, allowing for truth value gaps. Our framework supports both closed-world and open-world reasoning through the explicit representation of the particular closed-world assumptions and the ERDF ontological categories of total properties and total classes.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {37–94},
numpages = {58}
}

@article{10.5555/1622673.1622674,
author = {Manisterski, Efrat and Sarne, David and Kraus, Sarit},
title = {Enhancing Cooperative Search with Concurrent Interactions},
year = {2008},
issue_date = {May 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {32},
number = {1},
issn = {1076-9757},
abstract = {In this paper we show how taking advantage of autonomous agents' capability to maintain parallel interactions with others, and incorporating it into the cooperative economic search model results in a new search strategy which outperforms current strategies in use. As a framework for our analysis we use the electronic marketplace, where buyer agents have the incentive to search cooperatively. The new search technique is quite intuitive, however its analysis and the process of extracting the optimal search strategy are associated with several significant complexities. These difficulties are derived mainly from the unbounded search space and simultaneous dual affects of decisions taken along the search. We provide a comprehensive analysis of the model, highlighting, demonstrating and proving important characteristics of the optimal search strategy. Consequently, we manage to come up with an efficient modular algorithm for extracting the optimal cooperative search strategy for any given environment. A computational based comparative illustration of the system performance using the new search technique versus the traditional methods is given, emphasizing the main differences in the optimal strategy's structure and the advantage of using the proposed model.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {1–36},
numpages = {36}
}

@article{10.5555/1622655.1622672,
author = {Dresner, Kurt and Stone, Peter},
title = {A Multiagent Approach to Autonomous Intersection Management},
year = {2008},
issue_date = {January 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {31},
number = {1},
issn = {1076-9757},
abstract = {Artificial intelligence research is ushering in a new era of sophisticated, mass-market transportation technology. While computers can already fly a passenger jet better than a trained human pilot, people are still faced with the dangerous yet tedious task of driving automobiles. Intelligent Transportation Systems (ITS) is the field that focuses on integrating information technology with vehicles and transportation infrastructure to make transportation safer, cheaper, and more efficient. Recent advances in ITS point to a future in which vehicles themselves handle the vast majority of the driving task. Once autonomous vehicles become popular, autonomous interactions amongst multiple vehicles will be possible. Current methods of vehicle coordination, which are all designed to work with human drivers, will be outdated. The bottleneck for roadway efficiency will no longer be the drivers, but rather the mechanism by which those drivers' actions are coordinated. While open-road driving is a well-studied and more-or-less-solved problem, urban traffic scenarios, especially intersections, are much more challenging.We believe current methods for controlling traffic, specifically at intersections, will not be able to take advantage of the increased sensitivity and precision of autonomous vehicles as compared to human drivers. In this article, we suggest an alternative mechanism for coordinating the movement of autonomous vehicles through intersections. Drivers and intersections in this mechanism are treated as autonomous agents in a multiagent system. In this multiagent system, intersections use a new reservation-based approach built around a detailed communication protocol, which we also present. We demonstrate in simulation that our new mechanism has the potential to significantly outperform current intersection control technology--traffic lights and stop signs. Because our mechanism can emulate a traffic light or stop sign, it subsumes the most popular current methods of intersection control. This article also presents two extensions to the mechanism. The first extension allows the system to control human-driven vehicles in addition to autonomous vehicles. The second gives priority to emergency vehicles without significant cost to civilian vehicles. The mechanism, including both extensions, is implemented and tested in simulation, and we present experimental results that strongly attest to the efficacy of this approach.},
journal = {J. Artif. Int. Res.},
month = mar,
pages = {591–656},
numpages = {66}
}

@article{10.5555/1622655.1622671,
author = {Michelson, Matthew and Knoblock, Craig A.},
title = {Creating Relational Data from Unstructured and Ungrammatical Data Sources},
year = {2008},
issue_date = {January 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {31},
number = {1},
issn = {1076-9757},
abstract = {In order for agents to act on behalf of users, they will have to retrieve and integrate vast amounts of textual data on the World Wide Web. However, much of the useful data on the Web is neither grammatical nor formally structured, making querying dificult. Examples of these types of data sources are online classifieds like Craigslist1 and auction item listings like eBay.2 We call this unstructured, ungrammatical data "posts." The unstructured nature of posts makes query and integration dificult because the attributes are embedded within the text. Also, these attributes do not conform to standardized values, which prevents queries based on a common attribute value. The schema is unknown and the values may vary dramatically making accurate search dificult. Creating relational data for easy querying requires that we define a schema for the embedded attributes and extract values from the posts while standardizing these values. Traditional information extraction (IE) is inadequate to perform this task because it relies on clues from the data, such as structure or natural language, neither of which are found in posts. Furthermore, traditional information extraction does not incorporate data cleaning, which is necessary to accurately query and integrate the source. The two-step approach described in this paper creates relational data sets from unstructured and ungrammatical text by addressing both issues. To do this, we require a set of known entities called a "reference set." The first step aligns each post to each member of each reference set. This allows our algorithm to define a schema over the post and include standard values for the attributes defined by this schema. The second step performs information extraction for the attributes, including attributes not easily represented by reference sets, such as a price. In this manner we create a relational structure over previously unstructured data, supporting deep and accurate queries over the data as well as standard values for integration. Our experimental results show that our technique matches the posts to the reference set accurately and eficiently and outperforms state-of-the-art extraction systems on the extraction task from posts.},
journal = {J. Artif. Int. Res.},
month = mar,
pages = {543–590},
numpages = {48}
}

@article{10.5555/1622655.1622670,
author = {Ryan, Malcolm R. K.},
title = {Exploiting Subgraph Structure in Multi-Robot Path Planning},
year = {2008},
issue_date = {January 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {31},
number = {1},
issn = {1076-9757},
abstract = {Multi-robot path planning is dificult due to the combinatorial explosion of the search space with every new robot added. Complete search of the combined state-space soon becomes intractable. In this paper we present a novel form of abstraction that allows us to plan much more eficiently. The key to this abstraction is the partitioning of the map into subgraphs of known structure with entry and exit restrictions which we can represent compactly. Planning then becomes a search in the much smaller space of subgraph configurations. Once an abstract plan is found, it can be quickly resolved into a correct (but possibly sub-optimal) concrete plan without the need for further search. We prove that this technique is sound and complete and demonstrate its practical effiectiveness on a real map.A contending solution, prioritised planning, is also evaluated and shown to have similar performance albeit at the cost of completeness. The two approaches are not necessarily conflicting; we demonstrate how they can be combined into a single algorithm which out-performs either approach alone.},
journal = {J. Artif. Int. Res.},
month = mar,
pages = {497–542},
numpages = {46}
}

@article{10.5555/1622655.1622669,
author = {Altman, Alon and Tennenholtz, Moshe},
title = {Axiomatic Foundations for Ranking Systems},
year = {2008},
issue_date = {January 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {31},
number = {1},
issn = {1076-9757},
abstract = {Reasoning about agent preferences on a set of alternatives, and the aggregation of such preferences into some social ranking is a fundamental issue in reasoning about multi-agent systems. When the set of agents and the set of alternatives coincide, we get the ranking systems setting. A famous type of ranking systems are page ranking systems in the context of search engines. In this paper we present an extensive axiomatic study of ranking systems. In particular, we consider two fundamental axioms: Transitivity, and Ranked Independence of Irrelevant Alternatives. Surprisingly, we find that there is no general social ranking rule that satisfies both requirements. Furthermore, we show that our impossibility result holds under various restrictions on the class of ranking problems considered. However, when transitivity is weakened, an interesting possibility result is obtained. In addition, we show a complete axiomatization of approval voting using ranked IIA.},
journal = {J. Artif. Int. Res.},
month = mar,
pages = {473–495},
numpages = {23}
}

@article{10.5555/1622655.1622668,
author = {Wang, Chenggang and Joshi, Saket and Khardon, Roni},
title = {First Order Decision Diagrams for Relational MDPs},
year = {2008},
issue_date = {January 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {31},
number = {1},
issn = {1076-9757},
abstract = {Markov decision processes capture sequential decision making under uncertainty, where an agent must choose actions so as to optimize long term reward. The paper studies efficient reasoning mechanisms for Relational Markov Decision Processes (RMDP) where world states have an internal relational structure that can be naturally described in terms of objects and relations among them. Two contributions are presented. First, the paper develops First Order Decision Diagrams (FODD), a new compact representation for functions over relational structures, together with a set of operators to combine FODDs, and novel reduction techniques to keep the representation small. Second, the paper shows how FODDs can be used to develop solutions for RMDPs, where reasoning is performed at the abstract level and the resulting optimal policy is independent of domain size (number of objects) or instantiation. In particular, a variant of the value iteration algorithm is developed by using special operations over FODDs, and the algorithm is shown to converge to the optimal policy.},
journal = {J. Artif. Int. Res.},
month = mar,
pages = {431–472},
numpages = {42}
}

@article{10.5555/1622655.1622667,
author = {Clarke, James and Lapata, Mirella},
title = {Global Inference for Sentence Compression an Integer Linear Programming Approach},
year = {2008},
issue_date = {January 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {31},
number = {1},
issn = {1076-9757},
abstract = {Sentence compression holds promise for many applications ranging from summarization to subtitle generation. Our work views sentence compression as an optimization problem and uses integer linear programming (ILP) to infer globally optimal compressions in the presence of linguistically motivated constraints. We show how previous formulations of sentence compression can be recast as ILPs and extend these models with novel global constraints. Experimental results on written and spoken texts demonstrate improvements over state-of-the-art models.},
journal = {J. Artif. Int. Res.},
month = mar,
pages = {399–429},
numpages = {31}
}

@article{10.5555/1622655.1622666,
author = {Eisenstein, Jacob and Barzilay, Regina and Davis, Randall},
title = {Gesture Salience as a Hidden Variable for Coreference Resolution and Keyframe Extraction},
year = {2008},
issue_date = {January 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {31},
number = {1},
issn = {1076-9757},
abstract = {Gesture is a non-verbal modality that can contribute crucial information to the understanding of natural language. But not all gestures are informative, and noncommunicative hand motions may confuse natural language processing (NLP) and impede learning. People have little difficulty ignoring irrelevant hand movements and focusing on meaningful gestures, suggesting that an automatic system could also be trained to perform this task. However, the informativeness of a gesture is context-dependent and labeling enough data to cover all cases would be expensive. We present conditional modality fusion, a conditional hidden-variable model that learns to predict which gestures are salient for coreference resolution, the task of determining whether two noun phrases refer to the same semantic entity. Moreover, our approach uses only coreference annotations, and not annotations of gesture salience itself. We show that gesture features improve performance on coreference resolution, and that by attending only to gestures that are salient, our method achieves further significant gains. In addition, we show that the model of gesture salience learned in the context of coreference accords with human intuition, by demonstrating that gestures judged to be salient by our model can be used successfully to create multimedia keyframe summaries of video. These summaries are similar to those created by human raters, and significantly outperform summaries produced by baselines from the literature.},
journal = {J. Artif. Int. Res.},
month = feb,
pages = {353–398},
numpages = {46}
}

@article{10.5555/1622655.1622665,
author = {Gim\'{e}nez, Omer and Jonsson, Anders},
title = {The Complexity of Planning Problems with Simple Causal Graphs},
year = {2008},
issue_date = {January 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {31},
number = {1},
issn = {1076-9757},
abstract = {We present three new complexity results for classes of planning problems with simple causal graphs. First, we describe a polynomial-time algorithm that uses macros to generate plans for the class 3S of planning problems with binary state variables and acyclic causal graphs. This implies that plan generation may be tractable even when a planning problem has an exponentially long minimal solution. We also prove that the problem of plan existence for planning problems with multi-valued variables and chain causal graphs is NP-hard. Finally, we show that plan existence for planning problems with binary state variables and polytree causal graphs is NP-complete.},
journal = {J. Artif. Int. Res.},
month = feb,
pages = {319–351},
numpages = {33}
}

@article{10.5555/1622655.1622664,
author = {Grau, Bernardo Cuenca and Horrocks, Ian and Kazakov, Yevgeny and Sattler, Ulrike},
title = {Modular Reuse of Ontologies: Theory and Practice},
year = {2008},
issue_date = {January 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {31},
number = {1},
issn = {1076-9757},
abstract = {In this paper, we propose a set of tasks that are relevant for the modular reuse of ontologies. In order to formalize these tasks as reasoning problems, we introduce the notions of conservative extension, safety and module for a very general class of logic-based ontology languages. We investigate the general properties of and relationships between these notions and study the relationships between the relevant reasoning problems we have previously identified. To study the computability of these problems, we consider, in particular, Description Logics (DLs), which provide the formal underpinning of the W3C Web Ontology Language (OWL), and show that all the problems we consider are undecidable or algorithmically unsolvable for the description logic underlying OWL DL. In order to achieve a practical solution, we identify conditions sufficient for an ontology to reuse a set of symbols "safely"--that is, without changing their meaning. We provide the notion of a safety class, which characterizes any sufficient condition for safety, and identify a family of safety classes-called locality--which enjoys a collection of desirable properties. We use the notion of a safety class to extract modules from ontologies, and we provide various modularization algorithms that are appropriate to the properties of the particular safety class in use. Finally, we show practical benefits of our safety checking and module extraction algorithms.},
journal = {J. Artif. Int. Res.},
month = feb,
pages = {273–318},
numpages = {46}
}

@article{10.5555/1622655.1622663,
author = {Liu, Yongmei and Lakemeyer, Gerhard},
title = {On the Expressiveness of Levesque's Normal Form},
year = {2008},
issue_date = {January 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {31},
number = {1},
issn = {1076-9757},
abstract = {Levesque proposed a generalization of a database called a proper knowledge base (KB), which is equivalent to a possibly infinite consistent set of ground literals. In contrast to databases, proper KBs do not make the closed-world assumption and hence the entailment problem becomes undecidable. Levesque then proposed a limited but efficient inference method V for proper KBs, which is sound and, when the query is in a certain normal form, also logically complete. He conjectured that for every first-order query there is an equivalent one in normal form. In this note, we show that this conjecture is false. In fact, we show that any class of formulas for which V is complete must be strictly less expressive than full first-order logic. Moreover, in the propositional case it is very unlikely that a formula always has a polynomial-size normal form.},
journal = {J. Artif. Int. Res.},
month = feb,
pages = {259–272},
numpages = {14}
}

@article{10.5555/1622655.1622662,
author = {van den Briel, Menkes H. L. and Vossen, Thomas and Kambhampati, Subbarao},
title = {Loosely Coupled Formulations for Automated Planning: An Integer Programming Perspective},
year = {2008},
issue_date = {January 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {31},
number = {1},
issn = {1076-9757},
abstract = {We represent planning as a set of loosely coupled network flow problems, where each network corresponds to one of the state variables in the planning domain. The network nodes correspond to the state variable values and the network arcs correspond to the value transitions. The planning problem is to find a path (a sequence of actions) in each network such that, when merged, they constitute a feasible plan. In this paper we present a number of integer programming formulations that model these loosely coupled networks with varying degrees of flexibility. Since merging may introduce exponentially many ordering constraints we implement a so-called branch-and-cut algorithm, in which these constraints are dynamically generated and added to the formulation when needed. Our results are very promising, they improve upon previous planning as integer programming approaches and lay the foundation for integer programming approaches for cost optimal planning.},
journal = {J. Artif. Int. Res.},
month = feb,
pages = {217–257},
numpages = {41}
}

@article{10.5555/1622655.1622661,
author = {Wong, Ka-Shu},
title = {Sound and Complete Inference Rules for SE-Consequence},
year = {2008},
issue_date = {January 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {31},
number = {1},
issn = {1076-9757},
abstract = {The notion of strong equivalence on logic programs with answer set semantics gives rise to a consequence relation on logic program rules, called SE-consequence. We present a sound and complete set of inference rules for SE-consequence on disjunctive logic programs.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {205–216},
numpages = {12}
}

@article{10.5555/1622655.1622660,
author = {Glimm, Birte and Horrocks, Ian and Lutz, Carsten and Sattler, Ulrike},
title = {Conjunctive Query Answering for the Description Logic SHIQ},
year = {2008},
issue_date = {January 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {31},
number = {1},
issn = {1076-9757},
abstract = {Conjunctive queries play an important role as an expressive query language for Description Logics (DLs). Although modern DLs usually provide for transitive roles, conjunctive query answering over DL knowledge bases is only poorly understood if transitive roles are admitted in the query. In this paper, we consider unions of conjunctive queries over knowledge bases formulated in the prominent DL SHIQ and allow transitive roles in both the query and the knowledge base. We show decidability of query answering in this setting and establish two tight complexity bounds: regarding combined complexity, we prove that there is a deterministic algorithm for query answering that needs time single exponential in the size of the KB and double exponential in the size of the query, which is optimal. Regarding data complexity, we prove containment in co-NP.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {157–204},
numpages = {48}
}

@article{10.5555/1622655.1622659,
author = {Zhang, Yan and Ding, Yulin},
title = {CTL Model Update for System Modifications},
year = {2008},
issue_date = {January 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {31},
number = {1},
issn = {1076-9757},
abstract = {Model checking is a promising technology, which has been applied for verification of many hardware and software systems. In this paper, we introduce the concept of model update towards the development of an automatic system modification tool that extends model checking functions. We define primitive update operations on the models of Computation Tree Logic (CTL) and formalize the principle of minimal change for CTL model update. These primitive update operations, together with the underlying minimal change principle, serve as the foundation for CTL model update. Essential semantic and computational characterizations are provided for our CTL model update approach. We then describe a formal algorithm that implements this approach. We also illustrate two case studies of CTL model updates for the well-known microwave oven example and the Andrew File System 1, from which we further propose a method to optimize the update results in complex system modifications.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {113–155},
numpages = {43}
}

@article{10.5555/1622655.1622658,
author = {Engel, Yagil and Wellman, Michael P.},
title = {CUI Networks: A Graphical Representation for Conditional Utility Independence},
year = {2008},
issue_date = {January 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {31},
number = {1},
issn = {1076-9757},
abstract = {We introduce CUI networks, a compact graphical representation of utility functions over multiple attributes. CUI networks model multiattribute utility functions using the well-studied and widely applicable utility independence concept. We show how conditional utility independence leads to an effective functional decomposition that can be exhibited graphically, and how local, compact data at the graph nodes can be used to calculate joint utility. We discuss aspects of elicitation, network construction, and optimization, and contrast our new representation with previous graphical preference modeling.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {83–112},
numpages = {30}
}

@article{10.5555/1622655.1622657,
author = {Mausam and Weld, Daniel S.},
title = {Planning with Durative Actions in Stochastic Domains},
year = {2008},
issue_date = {January 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {31},
number = {1},
issn = {1076-9757},
abstract = {Probabilistic planning problems are typically modeled as a Markov Decision Process (MDP). MDPs, while an otherwise expressive model, allow only for sequential, non-durative actions. This poses severe restrictions in modeling and solving a real world planning problem. We extend the MDP model to incorporate-1) simultaneous action execution, 2) durative actions, and 3) stochastic durations. We develop several algorithms to combat the computational explosion introduced by these features. The key theoretical ideas used in building these algorithms are -- modeling a complex problem as an MDP in extended state/action space, pruning of irrelevant actions, sampling of relevant actions, using informed heuristics to guide the search, hybridizing different planners to achieve benefits of both, approximating the problem and replanning. Our empirical evaluation illuminates the different merits in using various algorithms, viz., optimality, empirical closeness to optimality, theoretical error bounds, and speed.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {33–82},
numpages = {50}
}

@article{10.5555/1622655.1622656,
author = {Heras, Federico and Larrosa, Javier and Oliveras, Albert},
title = {MINIMAXSAT: An Efficient Weighted Max-SAT Solver},
year = {2008},
issue_date = {January 2008},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {31},
number = {1},
issn = {1076-9757},
abstract = {In this paper we introduce MINIMAXSAT, a new Max-SAT solver that is built on top of MIN-ISAT+.It incorporates the best current SAT and Max-SAT techniques. It can handle hard clauses (clauses of mandatory satisfaction as in SAT), soft clauses (clauses whose falsification is penalized by a cost as in Max-SAT) as well as pseudo-boolean objective functions and constraints. Its main features are: learning and backjumping on hard clauses; resolution-based and substraction-based lower bounding; and lazy propagation with the two-watched literal scheme. Our empirical evaluation comparing a wide set of solving alternatives on a broad set of optimization benchmarks indicates that the performance of MINIMAXSAT is usually close to the best specialized alternative and, in some cases, even better.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {1–32},
numpages = {32}
}

@article{10.5555/1622637.1622654,
author = {Szita, Istv\'{a}n and L\~{o}rincz, Andr\'{a}s},
title = {Learning to Play Using Low-Complexity Rule-Based Policies: Illustrations through Ms. Pac-Man},
year = {2007},
issue_date = {September 2007},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {30},
number = {1},
issn = {1076-9757},
abstract = {In this article we propose a method that can deal with certain combinatorial reinforcement learning tasks. We demonstrate the approach in the popular Ms. Pac-Man game. We define a set of high-level observation and action modules, from which rule-based policies are constructed automatically. In these policies, actions are temporally extended, and may work concurrently. The policy of the agent is encoded by a compact decision list. The components of the list are selected from a large pool of rules, which can be either handcrafted or generated automatically. A suitable selection of rules is learnt by the cross-entropy method, a recent global optimization algorithm that fits our framework smoothly. Cross-entropy-optimized policies perform better than our hand-crafted policy, and reach the score of average human players. We argue that learning is successful mainly because (i) policies may apply concurrent actions and thus the policy space is sufficiently rich, (ii) the search is biased towards low-complexity policies and therefore, solutions with a compact description can be found quickly if they exist.},
journal = {J. Artif. Int. Res.},
month = dec,
pages = {659–684},
numpages = {26}
}

@article{10.5555/1622637.1622653,
author = {Bhattacharya, Indrajit and Getoor, Lise},
title = {Query-Time Entity Resolution},
year = {2007},
issue_date = {September 2007},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {30},
number = {1},
issn = {1076-9757},
abstract = {Entity resolution is the problem of reconciling database references corresponding to the same real-world entities. Given the abundance of publicly available databases that have unresolved entities, we motivate the problem of query-time entity resolution: quick and accurate resolution for answering queries over such 'unclean' databases at query-time. Since collective entity resolution approaches -- where related references are resolved jointly -- have been shown to be more accurate than independent attribute-based resolution for off-line entity resolution, we focus on developing new algorithms for collective resolution for answering entity resolution queries at query-time. For this purpose, we first formally show that, for collective resolution, precision and recall for individual entities follow a geometric progression as neighbors at increasing distances are considered. Unfolding this progression leads naturally to a two stage 'expand and resolve' query processing strategy. In this strategy, we first extract the related records for a query using two novel expansion operators, and then resolve the extracted records collectively. We then show how the same strategy can be adapted for query-time entity resolution by identifying and resolving only those database references that are the most helpful for processing the query. We validate our approach on two large real-world publication databases where we show the usefulness of collective resolution and at the same time demonstrate the need for adaptive strategies for query processing. We then show how the same queries can be answered in real-time using our adaptive approach while preserving the gains of collective resolution. In addition to experiments on real datasets, we use synthetically generated data to empirically demonstrate the validity of the performance trends predicted by our analysis of collective entity resolution over a wide range of structural characteristics in the data.},
journal = {J. Artif. Int. Res.},
month = dec,
pages = {621–657},
numpages = {37}
}

@article{10.5555/1622637.1622652,
author = {Domshlak, Carmel and Hoffmann, J\"{o}rg},
title = {Probabilistic Planning via Heuristic Forward Search and Weighted Model Counting},
year = {2007},
issue_date = {September 2007},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {30},
number = {1},
issn = {1076-9757},
abstract = {We present a new algorithm for probabilistic planning with no observability. Our algorithm, called Probabilistic-FF, extends the heuristic forward-searchmachinery of Conformant-FF to problems with probabilistic uncertainty about both the initial state and action effects. Specifically, Probabilistic-FF combines Conformant-FF's techniques with a powerful machinery for weighted model counting in (weighted) CNFs, serving to elegantly define both the search space and the heuristic function. Our evaluation of Probabilistic-FF shows its fine scalability in a range of probabilistic domains, constituting a several orders of magnitude improvement over previous results in this area. We use a problematic case to point out the main open issue to be addressed by further research.},
journal = {J. Artif. Int. Res.},
month = dec,
pages = {565–620},
numpages = {56}
}

@article{10.5555/1622637.1622651,
author = {Hill, Simon I. and Doucet, Arnaud},
title = {A Framework for Kernel-Based Multi-Category Classification},
year = {2007},
issue_date = {September 2007},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {30},
number = {1},
issn = {1076-9757},
abstract = {A geometric framework for understanding multi-category classification is introduced, through which many existing 'all-together' algorithms can be understood. The structure enables parsimonious optimisation, through a direct extension of the binary methodology. The focus is on Support Vector Classification, with parallels drawn to related methods.The ability of the framework to compare algorithms is illustrated by a brief discussion of Fisher consistency. Its utility in improving understanding of multi-category analysis is demonstrated through a derivation of improved generalisation bounds.It is also described how this architecture provides insights regarding how to further improve on the speed of existing multi-category classification algorithms. An initial example of how this might be achieved is developed in the formulation of a straightforward multi-category Sequential Minimal Optimisation algorithm. Proof-of-concept experimental results have shown that this, combined with the mapping of pairwise results, is comparable with benchmark optimisation speeds.},
journal = {J. Artif. Int. Res.},
month = dec,
pages = {525–564},
numpages = {40}
}

@article{10.5555/1622637.1622650,
author = {Greco, Sergio and Trubitsyna, Irina and Zumpano, Ester},
title = {On the Semantics of Logic Programs with Preferences},
year = {2007},
issue_date = {September 2007},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {30},
number = {1},
issn = {1076-9757},
abstract = {This work is a contribution to prioritized reasoning in logic programming in the presence of preference relations involving atoms. The technique, providing a new interpretation for prioritized logic programs, is inspired by the semantics of Prioritized Logic Programming and enriched with the use of structural information of preference of Answer Set Optimization Programming. Specifically, the analysis of the logic program is carried out together with the analysis of preferences in order to determine the choice order and the sets of comparable models. The new semantics is compared with other approaches known in the literature and complexity analysis is also performed, showing that, with respect to other similar approaches previously proposed, the complexity of computing preferred stable models does not increase.},
journal = {J. Artif. Int. Res.},
month = dec,
pages = {501–523},
numpages = {23}
}

@article{10.5555/1622637.1622649,
author = {Mairesse, Fran\c{c}ois and Walker, Marilyn A. and Mehl, Matthias R. and Moore, Roger K.},
title = {Using Linguistic Cues for the Automatic Recognition of Personality in Conversation and Text},
year = {2007},
issue_date = {September 2007},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {30},
number = {1},
issn = {1076-9757},
abstract = {It is well known that utterances convey a great deal of information about the speaker in addition to their semantic content. One such type of information consists of cues to the speaker's personality traits, the most fundamental dimension of variation between humans. Recent work explores the automatic detection of other types of pragmatic variation in text and conversation, such as emotion, deception, speaker charisma, dominance, point of view, subjectivity, opinion and sentiment. Personality affects these other aspects of linguistic production, and thus personality recognition may be useful for these tasks, in addition to many other potential applications. However, to date, there is little work on the automatic recognition of personality traits. This article reports experimental results for recognition of all Big Five personality traits, in both conversation and text, utilising both self and observer ratings of personality. While other work reports classification results, we experiment with classification, regression and ranking models. For each model, we analyse the effect of different feature sets on accuracy. Results show that for some traits, any type of statistical model performs significantly better than the baseline, but ranking models perform best overall. We also present an experiment suggesting that ranking models are more accurate than multi-class classifiers for modelling personality. In addition, recognition models trained on observed personality perform better than models trained using self-reports, and the optimal feature set depends on the personality trait. A qualitative analysis of the learned models confirms previous findings linking language and personality, while revealing many new linguistic markers.},
journal = {J. Artif. Int. Res.},
month = nov,
pages = {457–500},
numpages = {44}
}

@article{10.5555/1622637.1622648,
author = {Walker, Marilyn and Stent, Amanda and Mairesse, Fran\c{c}ois and Prasad, Rashmi},
title = {Individual and Domain Adaptation in Sentence Planning for Dialogue},
year = {2007},
issue_date = {September 2007},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {30},
number = {1},
issn = {1076-9757},
abstract = {One of the biggest challenges in the development and deployment of spoken dialogue systems is the design of the spoken language generation module. This challenge arises from the need for the generator to adapt to many features of the dialogue domain, user population, and dialogue context. A promising approach is trainable generation, which uses general-purpose linguistic knowledge that is automatically adapted to the features of interest, such as the application domain, individual user, or user group. In this paper we present and evaluate a trainable sentence planner for providing restaurant information in the MATCH dialogue system. We show that trainable sentence planning can produce complex information presentations whose quality is comparable to the output of a template-based generator tuned to this domain. We also show that our method easily supports adapting the sentence planner to individuals, and that the individualized sentence planners generally perform better than models trained and tested on a population of individuals. Previous work has documented and utilized individual preferences for content selection, but to our knowledge, these results provide the first demonstration of individual preferences for sentence planning operations, affecting the content order, discourse structure and sentence structure of system responses. Finally, we evaluate the contribution of different feature sets, and show that, in our application, n-gram features often do as well as features based on higher-level linguistic representations.},
journal = {J. Artif. Int. Res.},
month = nov,
pages = {413–456},
numpages = {44}
}

@article{10.5555/1622637.1622647,
author = {Bell, John},
title = {Natural Events},
year = {2007},
issue_date = {September 2007},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {30},
number = {1},
issn = {1076-9757},
abstract = {This paper develops an inductive theory of predictive common sense reasoning. The theory provides the basis for an integrated solution to the three traditional problems of reasoning about change; the frame, qualification, and ramification problems. The theory is also capable of representing non-deterministic events, and it provides a means for stating defeasible preferences over the outcomes of conflicting simultaneous events.},
journal = {J. Artif. Int. Res.},
month = nov,
pages = {361–412},
numpages = {52}
}

@article{10.5555/1622637.1622646,
author = {Li, Chu Min and Many\`{a}, Felip and Planes, Jordi},
title = {New Inference Rules for Max-SAT},
year = {2007},
issue_date = {September 2007},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {30},
number = {1},
issn = {1076-9757},
abstract = {Exact Max-SAT solvers, compared with SAT solvers, apply little inference at each node of the proof tree. Commonly used SAT inference rules like unit propagation produce a simplified formula that preserves satisfiability but, unfortunately, solving the Max-SAT problem for the simplified formula is not equivalent to solving it for the original formula. In this paper, we define a number of original inference rules that, besides being applied efficiently, transform Max-SAT instances into equivalent Max-SAT instances which are easier to solve. The soundness of the rules, that can be seen as refinements of unit resolution adapted to Max-SAT, are proved in a novel and simple way via an integer programming transformation. With the aim of finding out how powerful the inference rules are in practice, we have developed a new Max-SAT solver, called MaxSatz, which incorporates those rules, and performed an experimental investigation. The results provide empirical evidence that MaxSatz is very competitive, at least, on random Max-2SAT, random Max-3SAT, Max-Cut, and Graph 3-coloring instances, as well as on the benchmarks from the Max-SAT Evaluation 2006.},
journal = {J. Artif. Int. Res.},
month = oct,
pages = {321–359},
numpages = {39}
}

@article{10.5555/1622637.1622645,
author = {Stoilos, Giorgos and Stamou, Giorgos and Pan, Jeff Z. and Tzouvaras, Vassilis and Horrocks, Ian},
title = {Reasoning with Very Expressive Fuzzy Description Logics},
year = {2007},
issue_date = {September 2007},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {30},
number = {1},
issn = {1076-9757},
abstract = {It is widely recognized today that the management of imprecision and vagueness will yield more intelligent and realistic knowledge-based applications. Description Logics (DLs) are a family of knowledge representation languages that have gained considerable attention the last decade, mainly due to their decidability and the existence of empirically high performance of reasoning algorithms. In this paper, we extend the well known fuzzy ALC DL to the fuzzy SHIN DL, which extends the fuzzy ALC DL with transitive role axioms (S), inverse roles (I), role hierarchies (H) and number restrictions (N). We illustrate why transitive role axioms are difficult to handle in the presence of fuzzy interpretations and how to handle them properly. Then we extend these results by adding role hierarchies and finally number restrictions. The main contributions of the paper are the decidability proof of the fuzzy DL languages fuzzy-SI and fuzzy-SHIN, as well as decision procedures for the knowledge base satisfiability problem of the fuzzy-SI and fuzzy-SHIN.},
journal = {J. Artif. Int. Res.},
month = oct,
pages = {273–320},
numpages = {48}
}

@article{10.5555/1622637.1622644,
author = {McCallum, Andrew and Wang, Xuerui and Corrada-Emmanuel, Andr\'{e}s},
title = {Topic and Role Discovery in Social Networks with Experiments on Enron and Academic Email},
year = {2007},
issue_date = {September 2007},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {30},
number = {1},
issn = {1076-9757},
abstract = {Previous work in social network analysis (SNA) has modeled the existence of links from one entity to another, but not the attributes such as language content or topics on those links. We present the Author-Recipient-Topic (ART) model for social network analysis, which learns topic distributions based on the direction-sensitive messages sent between entities. The model builds on Latent Dirichlet Allocation (LDA) and the Author-Topic (AT) model, adding the key attribute that distribution over topics is conditioned distinctly on both the sender and recipient--steering the discovery of topics according to the relationships between people. We give results on both the Enron email corpus and a researcher's email archive, providing evidence not only that clearly relevant topics are discovered, but that the ART model better predicts people's roles and gives lower perplexity on previously unseen messages. We also present the Role-Author-Recipient-Topic (RART) model, an extension to ART that explicitly represents people's roles.},
journal = {J. Artif. Int. Res.},
month = oct,
pages = {249–272},
numpages = {24}
}

@article{10.5555/1622637.1622643,
author = {Felner, Ariel and Korf, Richard E. and Meshulam, Ram and Holte, Robert},
title = {Compressed Pattern Databases},
year = {2007},
issue_date = {September 2007},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {30},
number = {1},
issn = {1076-9757},
abstract = {A pattern database (PDB) is a heuristic function implemented as a lookup table that stores the lengths of optimal solutions for subproblem instances. Standard PDBs have a distinct entry in the table for each subproblem instance. In this paper we investigate compressing PDBs by merging several entries into one, thereby allowing the use of PDBs that exceed available memory in their uncompressed form. We introduce a number of methods for determining which entries to merge and discuss their relative merits. These vary from domain-independent approaches that allow any set of entries in the PDB to be merged, to more intelligent methods that take into account the structure of the problem. The choice of the best compression method is based on domain-dependent attributes. We present experimental results on a number of combinatorial problems, including the four-peg Towers of Hanoi problem, the sliding-tile puzzles, and the Top-Spin puzzle. For the Towers of Hanoi, we show that the search time can be reduced by up to three orders of magnitude by using compressed PDBs compared to uncompressed PDBs of the same size. More modest improvements were observed for the other domains.},
journal = {J. Artif. Int. Res.},
month = oct,
pages = {213–247},
numpages = {35}
}

@article{10.5555/1622637.1622642,
author = {Ponzetto, Simone Paolo and Strube, Michael},
title = {Knowledge Derived from Wikipedia for Computing Semantic Relatedness},
year = {2007},
issue_date = {September 2007},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {30},
number = {1},
issn = {1076-9757},
abstract = {Wikipedia provides a semantic network for computing semantic relatedness in a more structured fashion than a search engine and with more coverage than WordNet. We present experiments on using Wikipedia for computing semantic relatedness and compare it to WordNet on various benchmarking datasets. Existing relatedness measures perform better using Wikipedia than a baseline given by Google counts, and we show that Wikipedia outperforms WordNet on some datasets. We also address the question whether and how Wikipedia can be integrated into NLP applications as a knowledge base. Including Wikipedia improves the performance of a machine learning based coreference resolution system, indicating that it represents a valuable resource for NLP applications. Finally, we show that our method can be easily used for languages other than English by computing semantic relatedness for a German dataset.},
journal = {J. Artif. Int. Res.},
month = oct,
pages = {181–212},
numpages = {32}
}

@article{10.5555/1622637.1622641,
author = {Bredin, Jonathan and Parkes, David C. and Duong, Quang},
title = {Chain: A Dynamic Double Auction Framework for Matching Patient Agents},
year = {2007},
issue_date = {September 2007},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {30},
number = {1},
issn = {1076-9757},
abstract = {In this paper we present and evaluate a general framework for the design of truthful auctions for matching agents in a dynamic, two-sided market. A single commodity, such as a resource or a task, is bought and sold by multiple buyers and sellers that arrive and depart over time. Our algorithm, CHAIN, provides the first framework that allows a truthful dynamic double auction (DA) to be constructed from a truthful, single-period (i.e. static) double-auction rule. The pricing and matching method of the CHAIN construction is unique amongst dynamic-auction rules that adopt the same building block. We examine experimentally the allocative efficiency of CHAIN when instantiated on various single-period rules, including the canonical McAfee double-auction rule. For a baseline we also consider non-truthful double auctions populated with "zero-intelligence plus"-style learning agents. CHAIN-based auctions perform well in comparison with other schemes, especially as arrival intensity falls and agent valuations become more volatile.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {133–179},
numpages = {47}
}

@article{10.5555/1622637.1622640,
author = {Pistore, Marco and Vardi, Moshe Y.},
title = {The Planning Spectrum: One, Two, Three, Infinity},
year = {2007},
issue_date = {September 2007},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {30},
number = {1},
issn = {1076-9757},
abstract = {Linear Temporal Logic (LTL) is widely used for defining conditions on the execution paths of dynamic systems. In the case of dynamic systems that allow for nondeterministic evolutions, one has to specify, along with an LTL formula ϕ, which are the paths that are required to satisfy the formula. Two extreme cases are the universal interpretation A.ϕ, which requires that the formula be satisfied for all execution paths, and the existential interpretation Ε.ϕ, which requires that the formula be satisfied for some execution path.When LTL is applied to the definition of goals in planning problems on nondeterministic domains, these two extreme cases are too restrictive. It is often impossible to develop plans that achieve the goal in all the nondeterministic evolutions of a system, and it is too weak to require that the goal is satisfied by some execution.In this paper we explore alternative interpretations of an LTL formula that are between these extreme cases. We define a new language that permits an arbitrary combination of the A and Ε quantifiers, thus allowing, for instance, to require that each finite execution can be extended to an execution satisfying an LTL formula (AΕ.ϕ), or that there is some finite execution whose extensions all satisfy an LTL formula (ΕA.ϕ). We show that only eight of these combinations of path quantifiers are relevant, corresponding to an alternation of the quantifiers of length one (A and Ε), two (AΕ and ΕA), three (AΕA and ΕAΕ), and infinity ((AΕ)ω and (ΕA)ω). We also present a planning algorithm for the new language that is based on an automata-theoretic approach, and study its complexity.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {101–132},
numpages = {32}
}

@article{10.5555/1622637.1622639,
author = {Bulitko, Vadim and Sturtevant, Nathan and Lu, Jieshan and Yau, Timothy},
title = {Graph Abstraction in Real-Time Heuristic Search},
year = {2007},
issue_date = {September 2007},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {30},
number = {1},
issn = {1076-9757},
abstract = {Real-time heuristic search methods are used by situated agents in applications that require the amount of planning per move to be independent of the problem size. Such agents plan only a few actions at a time in a local search space and avoid getting trapped in local minima by improving their heuristic function over time. We extend a wide class of real-time search algorithms with automatically-built state abstraction and prove completeness and convergence of the resulting family of algorithms. We then analyze the impact of abstraction in an extensive empirical study in real-time pathfinding. Abstraction is found to improve efficiency by providing better trading offs between planning time, learning speed and other negatively correlated performance measures.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {51–100},
numpages = {50},
keywords = {state abstraction, goal-directed navigation, learning real-time heuristic search}
}

@article{10.5555/1622637.1622638,
author = {Carman, Mark James and Knoblock, Craig A.},
title = {Learning Semantic Definitions of Online Information Sources},
year = {2007},
issue_date = {September 2007},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {30},
number = {1},
issn = {1076-9757},
abstract = {The Internet contains a very large number of information sources providing many types of data from weather forecasts to travel deals and financial information. These sources can be accessed via Web-forms, Web Services, RSS feeds and so on. In order to make automated use of these sources, we need to model them semantically, but writing semantic descriptions for Web Services is both tedious and error prone. In this paper we investigate the problem of automatically generating such models. We introduce a framework for learning Datalog definitions of Web sources. In order to learn these definitions, our system actively invokes the sources and compares the data they produce with that of known sources of information. It then performs an inductive logic search through the space of plausible source definitions in order to learn the best possible semantic model for each new source. In this paper we perform an empirical evaluation of the system using real-world Web sources. The evaluation demonstrates the effectiveness of the approach, showing that we can automatically learn complex models for real sources in reasonable time. We also compare our system with a complex schema matching system, showing that our approach can handle the kinds of problems tackled by the latter.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {1–50},
numpages = {50}
}

@article{10.5555/1622606.1622619,
author = {Pralet, C\'{e}dric and Verfaillie, G\'{e}rard and Schiex, Thomas},
title = {An Algebraic Graphical Model for Decision with Uncertainties, Feasibilities, and Utilities},
year = {2007},
issue_date = {May 2007},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {29},
number = {1},
issn = {1076-9757},
abstract = {Numerous formalisms and dedicated algorithms have been designed in the last decades to model and solve decision making problems. Some formalisms, such as constraint networks, can express "simple" decision problems, while others are designed to take into account uncertainties, unfeasible decisions, and utilities. Even in a single formalism, several variants are often proposed to model different types of uncertainty (probability, possibility...) or utility (additive or not). In this article, we introduce an algebraic graphical model that encompasses a large number of such formalisms: (1) we first adapt previous structures from Friedman, Chu and Halpern for representing uncertainty, utility, and expected utility in order to deal with generic forms of sequential decision making; (2) on these structures, we then introduce composite graphical models that express information via variables linked by "local" functions, thanks to conditional independence; (3) on these graphical models, we finally define a simple class of queries which can represent various scenarios in terms of observabilities and controllabilities. A natural decision-tree semantics for such queries is completed by an equivalent operational semantics, which induces generic algorithms. The proposed framework, called the Plausibility-Feasibility-Utility (PFU) framework, not only provides a better understanding of the links between existing formalisms, but it also covers yet unpublished frameworks (such as possibilistic influence diagrams) and unifies formalisms such as quantified boolean formulas and influence diagrams. Our backtrack and variable elimination generic algorithms are a first step towards unified algorithms.},
journal = {J. Artif. Int. Res.},
month = aug,
pages = {421–489},
numpages = {69}
}

@article{10.5555/1622606.1622618,
author = {Jurca, Radu and Faltings, Boi},
title = {Obtaining Reliable Feedback for Sanctioning Reputation Mechanisms},
year = {2007},
issue_date = {May 2007},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {29},
number = {1},
issn = {1076-9757},
abstract = {Reputation mechanisms offer an effective alternative to verification authorities for building trust in electronic markets with moral hazard. Future clients guide their business decisions by considering the feedback from past transactions; if truthfully exposed, cheating behavior is sanctioned and thus becomes irrational.It therefore becomes important to ensure that rational clients have the right incentives to report honestly. As an alternative to side-payment schemes that explicitly reward truthful reports, we show that honesty can emerge as a rational behavior when clients have a repeated presence in the market. To this end we describe a mechanism that supports an equilibrium where truthful feedback is obtained. Then we characterize the set of pareto-optimal equilibria of the mechanism, and derive an upper bound on the percentage of false reports that can be recorded by the mechanism. An important role in the existence of this bound is played by the fact that rational clients can establish a reputation for reporting honestly.},
journal = {J. Artif. Int. Res.},
month = aug,
pages = {391–419},
numpages = {29}
}

@article{10.5555/1622606.1622617,
author = {Son, Tran Cao and Pontelli, Enrico and Tu, Phan Huy},
title = {Answer Sets for Logic Programs with Arbitrary Abstract Constraint Atoms},
year = {2007},
issue_date = {May 2007},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {29},
number = {1},
issn = {1076-9757},
abstract = {In this paper, we present two alternative approaches to defining answer sets for logic programs with arbitrary types of abstract constraint atoms (c-atoms). These approaches generalize the fixpoint-based and the level mapping based answer set semantics of normal logic programs to the case of logic programs with arbitrary types of c-atoms. The results are four different answer set definitions which are equivalent when applied to normal logic programs.The standard fixpoint-based semantics of logic programs is generalized in two directions, called answer set by reduct and answer set by complement. These definitions, which differ from each other in the treatment of negation-as-failure (naf) atoms, make use of an immediate consequence operator to perform answer set checking, whose definition relies on the notion of conditional satisfaction of c-atoms w.r.t. a pair of interpretations.The other two definitions, called strongly and weakly well-supported models, are generalizations of the notion of well-supported models of normal logic programs to the case of programs with c-atoms. As for the case of fixpoint-based semantics, the difference between these two definitions is rooted in the treatment of naf atoms.We prove that answer sets by reduct (resp. by complement) are equivalent to weakly (resp. strongly) well-supported models of a program, thus generalizing the theorem on the correspondence between stable models and well-supported models of a normal logic program to the class of programs with c-atoms.We show that the newly defined semantics coincide with previously introduced semantics for logic programs with monotone c-atoms, and they extend the original answer set semantics of normal logic programs. We also study some properties of answer sets of programs with c-atoms, and relate our definitions to several semantics for logic programs with aggregates presented in the literature.},
journal = {J. Artif. Int. Res.},
month = aug,
pages = {353–389},
numpages = {37}
}

@article{10.5555/1622606.1622616,
author = {Pasula, Hanna M. and Zettlemoyer, Luke S. and Kaelbling, Leslie Pack},
title = {Learning Symbolic Models of Stochastic Domains},
year = {2007},
issue_date = {May 2007},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {29},
number = {1},
issn = {1076-9757},
abstract = {In this article, we work towards the goal of developing agents that can learn to act in complex worlds. We develop a probabilistic, relational planning rule representation that compactly models noisy, nondeterministic action effects, and show how such rules can be effectively learned. Through experiments in simple planning domains and a 3D simulated blocks world with realistic physics, we demonstrate that this learning algorithm allows agents to effectively model world dynamics.},
journal = {J. Artif. Int. Res.},
month = jul,
pages = {309–352},
numpages = {44}
}

@article{10.5555/1622606.1622615,
author = {Di Noia, Tommaso and Di Sciascio, Eugenio and Donini, Francesco M.},
title = {Semantic Matchmaking as Non-Monotonic Reasoning: A Description Logic Approach},
year = {2007},
issue_date = {May 2007},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {29},
number = {1},
issn = {1076-9757},
abstract = {Matchmaking arises when supply and demand meet in an electronic marketplace, or when agents search for a web service to perform some task, or even when recruiting agencies match curricula and job profiles. In such open environments, the objective of a matchmaking process is to discover best available offers to a given request.We address the problem of matchmaking from a knowledge representation perspective, with a formalization based on Description Logics. We devise Concept Abduction and Concept Contraction as non-monotonic inferences in Description Logics suitable for modeling matchmaking in a logical framework, and prove some related complexity results. We also present reasonable algorithms for semantic matchmaking based on the devised inferences, and prove that they obey to some commonsense properties.Finally, we report on the implementation of the proposed matchmaking framework, which has been used both as a mediator in e-marketplaces and for semantic web services discovery.},
journal = {J. Artif. Int. Res.},
month = jul,
pages = {269–307},
numpages = {39}
}

@article{10.5555/1622606.1622614,
author = {Vieira, Renata and Moreira, \'{A}lvaro and Wooldridge, Michael and Bordini, Rafael H.},
title = {On the Formal Semantics of Speech-Act Based Communication in an Agent-Oriented Programming Language},
year = {2007},
issue_date = {May 2007},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {29},
number = {1},
issn = {1076-9757},
abstract = {Research on agent communication languages has typically taken the speech acts paradigm as its starting point. Despite their manifest attractions, speech-act models of communication have several serious disadvantages as a foundation for communication in artificial agent systems. In particular, it has proved to be extremely difficult to give a satisfactory semantics to speech-act based agent communication languages. In part, the problem is that speech-act semantics typically make reference to the "mental states" of agents (their beliefs, desires, and intentions), and there is in general no way to attribute such attitudes to arbitrary computational agents. In addition, agent programming languages have only had their semantics formalised for abstract, stand-alone versions, neglecting aspects such as communication primitives. With respect to communication, implemented agent programming languages have tended to be rather ad hoc. This paper addresses both of these problems, by giving semantics to speech-act based messages received by an AgentSpeak agent. AgentSpeak is a logic-based agent programming language which incorporates the main features of the PRS model of reactive planning systems. The paper builds upon a structural operational semantics to AgentSpeak that we developed in previous work. The main contributions of this paper are as follows: an extension of our earlier work on the theoretical foundations of AgentSpeak interpreters; a computationally grounded semantics for (the core) performatives used in speech-act based agent communication languages; and a well-defined extension of AgentSpeak that supports agent communication.},
journal = {J. Artif. Int. Res.},
month = jun,
pages = {221–267},
numpages = {47}
}

@article{10.5555/1622606.1622613,
author = {Huang, Jinbo and Darwiche, Adnan},
title = {The Language of Search},
year = {2007},
issue_date = {May 2007},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {29},
number = {1},
issn = {1076-9757},
abstract = {This paper is concerned with a class of algorithms that perform exhaustive search on propositional knowledge bases. We show that each of these algorithms defines and generates a propositional language. Specifically, we show that the trace of a search can be interpreted as a combinational circuit, and a search algorithm then defines a propositional language consisting of circuits that are generated across all possible executions of the algorithm. In particular, we show that several versions of exhaustive DPLL search correspond to such well-known languages as FBDD, OBDD, and a precisely-defined subset of d-DNNF. By thus mapping search algorithms to propositional languages, we provide a uniform and practical framework in which successful search techniques can be harnessed for compilation of knowledge into various languages of interest, and a new methodology whereby the power and limitations of search algorithms can be understood by looking up the tractability and succinctness of the corresponding propositional languages.},
journal = {J. Artif. Int. Res.},
month = jun,
pages = {191–219},
numpages = {29}
}

@article{10.5555/1622606.1622612,
author = {Felzenszwalb, Pedro F. and McAllester, David},
title = {The Generalized A* Architecture},
year = {2007},
issue_date = {May 2007},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {29},
number = {1},
issn = {1076-9757},
abstract = {We consider the problem of computing a lightest derivation of a global structure using a set of weighted rules. A large variety of inference problems in AI can be formulated in this framework. We generalize A* search and heuristics derived from abstractions to a broad class of lightest derivation problems. We also describe a new algorithm that searches for lightest derivations using a hierarchy of abstractions. Our generalization of A* gives a new algorithm for searching AND/OR graphs in a bottom-up fashion.We discuss how the algorithms described here provide a general architecture for addressing the pipeline problem -- the problem of passing information back and forth between various stages of processing in a perceptual system. We consider examples in computer vision and natural language processing. We apply the hierarchical search algorithm to the problem of estimating the boundaries of convex objects in grayscale images and compare it to other search methods. A second set of experiments demonstrate the use of a new compositional model for finding salient curves in images.},
journal = {J. Artif. Int. Res.},
month = jun,
pages = {153–190},
numpages = {38}
}

@article{10.5555/1622606.1622611,
author = {Surdeanu, Mihai and M\`{a}rquez, Llu\'{\i}s and Carreras, Xavier and Comas, Pere R.},
title = {Combination Strategies for Semantic Role Labeling},
year = {2007},
issue_date = {May 2007},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {29},
number = {1},
issn = {1076-9757},
abstract = {This paper introduces and analyzes a battery of inference models for the problem of semantic role labeling: one based on constraint satisfaction, and several strategies that model the inference as a meta-learning problem using discriminative classifiers. These classifiers are developed with a rich set of novel features that encode proposition and sentence-level information. To our knowledge, this is the first work that: (a) performs a thorough analysis of learning-based inference models for semantic role labeling, and (b) compares several inference strategies in this context. We evaluate the proposed inference strategies in the framework of the CoNLL-2005 shared task using only automatically-generated syntactic information. The extensive experimental evaluation and analysis indicates that all the proposed inference strategies are successful - they all outperform the current best results reported in the CoNLL-2005 evaluation exercise - but each of the proposed approaches has its advantages and disadvantages. Several important traits of a state-of-the-art SRL combination strategy emerge from this analysis: (i) individual models should be combined at the granularity of candidate arguments rather than at the granularity of complete solutions; (ii) the best combination strategy uses an inference model based in learning; and (iii) the learning-based inference benefits from max-margin classifiers and global feedback.},
journal = {J. Artif. Int. Res.},
month = jun,
pages = {105–151},
numpages = {47}
}

@article{10.5555/1622606.1622610,
author = {Orasan, Constantin and Evans, Richard},
title = {NP Animacy Identification for Anaphora Resolution},
year = {2007},
issue_date = {May 2007},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {29},
number = {1},
issn = {1076-9757},
abstract = {In anaphora resolution for English, animacy identification can play an integral role in the application of agreement restrictions between pronouns and candidates, and as a result, can improve the accuracy of anaphora resolution systems. In this paper, two methods for animacy identification are proposed and evaluated using intrinsic and extrinsic measures. The first method is a rule-based one which uses information about the unique beginners in WordNet to classify NPs on the basis of their animacy. The second method relies on a machine learning algorithm which exploits a WordNet enriched with animacy information for each sense. The effect of word sense disambiguation on the two methods is also assessed. The intrinsic evaluation reveals that the machine learning method reaches human levels of performance. The extrinsic evaluation demonstrates that animacy identification can be beneficial in anaphora resolution, especially in the cases where animate entities are identified with high precision.},
journal = {J. Artif. Int. Res.},
month = jun,
pages = {79–103},
numpages = {25}
}

@article{10.5555/1622606.1622609,
author = {Beck, J. Christopher},
title = {Solution-Guided Multi-Point Constructive Search for Job Shop Scheduling},
year = {2007},
issue_date = {May 2007},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {29},
number = {1},
issn = {1076-9757},
abstract = {Solution-Guided Multi-Point Constructive Search (SGMPCS) is a novel constructive search technique that performs a series of resource-limited tree searches where each search begins either from an empty solution (as in randomized restart) or from a solution that has been encountered during the search. A small number of these "elite" solutions is maintained during the search. We introduce the technique and perform three sets of experiments on the job shop scheduling problem. First, a systematic, fully crossed study of SGMPCS is carried out to evaluate the performance impact of various parameter settings. Second, we inquire into the diversity of the elite solution set, showing, contrary to expectations, that a less diverse set leads to stronger performance. Finally, we compare the best parameter setting of SGMPCS from the first two experiments to chronological backtracking, limited discrepancy search, randomized restart, and a sophisticated tabu search algorithm on a set of well-known benchmark problems. Results demonstrate that SGMPCS is significantly better than the other constructive techniques tested, though lags behind the tabu search.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {49–77},
numpages = {29}
}

@article{10.5555/1622606.1622608,
author = {Nisan, Noam and Ronen, Amir},
title = {Computationally Feasible VCG Mechanisms},
year = {2007},
issue_date = {May 2007},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {29},
number = {1},
issn = {1076-9757},
abstract = {A major achievement of mechanism design theory is a general method for the construction of truthful mechanisms called VCG (Vickrey, Clarke, Groves). When applying this method to complex problems such as combinatorial auctions, a difficulty arises: VCG mechanisms are required to compute optimal outcomes and are, therefore, computationally infeasible. However, if the optimal outcome is replaced by the results of a sub-optimal algorithm, the resulting mechanism (termed VCG-based) is no longer necessarily truthful. The first part of this paper studies this phenomenon in depth and shows that it is near universal. Specifically, we prove that essentially all reasonable approximations or heuristics for combinatorial auctions as well as a wide class of cost minimization problems yield non-truthful VCG-based mechanisms. We generalize these results for affine maximizers.The second part of this paper proposes a general method for circumventing the above problem. We introduce a modification of VCG-based mechanisms in which the agents are given a chance to improve the output of the underlying algorithm. When the agents behave truthfully, the welfare obtained by the mechanism is at least as good as the one obtained by the algorithm's output. We provide a strong rationale for truth-telling behavior. Our method satisfies individual rationality as well.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {19–47},
numpages = {29}
}

@article{10.5555/1622606.1622607,
author = {Creignou, Nadia and Daud\'{e}, Herv\'{e} and Egly, Uwe},
title = {Phase Transition for Random Quantified XOR-Formulas},
year = {2007},
issue_date = {May 2007},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {29},
number = {1},
issn = {1076-9757},
abstract = {The QXOR-SAT problem is the quantified version of the satisfiability problem XOR-SAT in which the connective exclusive-or is used instead of the usual or. We study the phase transition associated with random QXOR-SAT instances. We give a description of this phase transition in the case of one alternation of quantifiers, thus performing an advanced practical and theoretical study on the phase transition of a quantified problem.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {1–18},
numpages = {18}
}

@article{10.5555/1622591.1622605,
author = {Gao, Yong and Culberson, Joseph},
title = {Consistency and Random Constraint Satisfaction Models},
year = {2007},
issue_date = {January 2007},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {28},
number = {1},
issn = {1076-9757},
abstract = {In this paper, we study the possibility of designing non-trivial random CSP models by exploiting the intrinsic connection between structures and typical-case hardness. We show that constraint consistency, a notion that has been developed to improve the efficiency of CSP algorithms, is in fact the key to the design of random CSP models that have interesting phase transition behavior and guaranteed exponential resolution complexity without putting much restriction on the parameter of constraint tightness or the domain size of the problem. We propose a very flexible framework for constructing problem instances with interesting behavior and develop a variety of concrete methods to construct specific random CSP models that enforce different levels of constraint consistency.A series of experimental studies with interesting observations are carried out to illustrate the effectiveness of introducing structural elements in random instances, to verify the robustness of our proposal, and to investigate features of some specific models based on our framework that are highly related to the behavior of backtracking search algorithms.},
journal = {J. Artif. Int. Res.},
month = apr,
pages = {517–557},
numpages = {41}
}

@article{10.5555/1622591.1622604,
author = {Clement, Bradley J. and Durfee, Edmund H. and Barrett, Anthony C.},
title = {Abstract Reasoning for Planning and Coordination},
year = {2007},
issue_date = {January 2007},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {28},
number = {1},
issn = {1076-9757},
abstract = {The judicious use of abstraction can help planning agents to identify key interactions between actions, and resolve them, without getting bogged down in details. However, ignoring the wrong details can lead agents into building plans that do not work, or into costly backtracking and replanning once overlooked interdependencies come to light. We claim that associating systematically-generated summary information with plans' abstract operators can ensure plan correctness, even for asynchronously-executed plans that must be coordinated across multiple agents, while still achieving valuable efficiency gains. In this paper, we formally characterize hierarchical plans whose actions have temporal extent, and describe a principled method for deriving summarized state and metric resource information for such actions. We provide sound and complete algorithms, along with heuristics, to exploit summary information during hierarchical refinement planning and plan coordination. Our analyses and experiments show that, under clearcut and reasonable conditions, using summary information can speed planning as much as doubly exponentially even for plans involving interacting subproblems.},
journal = {J. Artif. Int. Res.},
month = apr,
pages = {453–515},
numpages = {63}
}

@article{10.5555/1622591.1622603,
author = {Lin, Fangzhen and Chen, Yin},
title = {Discovering Classes of Strongly Equivalent Logic Programs},
year = {2007},
issue_date = {January 2007},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {28},
number = {1},
issn = {1076-9757},
abstract = {In this paper we apply computer-aided theorem discovery technique to discover theorems about strongly equivalent logic programs under the answer set semantics. Our discovered theorems capture new classes of strongly equivalent logic programs that can lead to new program simplification rules that preserve strong equivalence. Specifically, with the help of computers, we discovered exact conditions that capture the strong equivalence between a rule and the empty set, between two rules, between two rules and one of the two rules, between two rules and another rule, and between three rules and two of the three rules.},
journal = {J. Artif. Int. Res.},
month = apr,
pages = {431–451},
numpages = {21}
}

@article{10.5555/1622591.1622602,
author = {Fukunaga, Alex S. and Korf, Richard E.},
title = {Bin Completion Algorithms for Multicontainer Packing, Knapsack, and Covering Problems},
year = {2007},
issue_date = {January 2007},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {28},
number = {1},
issn = {1076-9757},
abstract = {Many combinatorial optimization problems such as the bin packing and multiple knapsack problems involve assigning a set of discrete objects to multiple containers. These problems can be used to model task and resource allocation problems in multi-agent systems and distributed systms, and can also be found as subproblems of scheduling problems. We propose bin completion, a branch-and-bound strategy for one-dimensional, multicontainer packing problems. Bin completion combines a bin-oriented search space with a powerful dominance criterion that enables us to prune much of the space. The performance of the basic bin completion framework can be enhanced by using a number of extensions, including nogood-based pruning techniques that allow further exploitation of the dominance criterion. Bin completion is applied to four problems: multiple knapsack, bin covering, min-cost covering, and bin packing. We show that our bin completion algorithms yield new, state-of-the-art results for the multiple knapsack, bin covering, and min-cost covering problems, outperforming previous algorithms by several orders of magnitude with respect to runtime on some classes of hard, random problem instances. For the bin packing problem, we demonstrate significant improvements compared to most previous results, but show that bin completion is not competitive with current state-of-the-art cutting-stock based approaches.},
journal = {J. Artif. Int. Res.},
month = mar,
pages = {393–429},
numpages = {37}
}

@article{10.5555/1622591.1622601,
author = {Jodogne, S\'{e}bastien and Piater, Justus H.},
title = {Closed-Loop Learning of Visual Control Policies},
year = {2007},
issue_date = {January 2007},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {28},
number = {1},
issn = {1076-9757},
abstract = {In this paper we present a general, flexible framework for learning mappings from images to actions by interacting with the environment. The basic idea is to introduce a feature-based image classifier in front of a reinforcement learning algorithm. The classifier partitions the visual space according to the presence or absence of few highly informative local descriptors that are incrementally selected in a sequence of attempts to remove perceptual aliasing. We also address the problem of fighting overfitting in such a greedy algorithm. Finally, we show how high-level visual features can be generated when the power of local descriptors is insufficient for completely disambiguating the aliased states. This is done by building a hierarchy of composite features that consist of recursive spatial combinations of visual features. We demonstrate the efficacy of our algorithms by solving three visual navigation tasks and a visual version of the classical "Car on the Hill" control problem.},
journal = {J. Artif. Int. Res.},
month = mar,
pages = {349–391},
numpages = {43}
}

@article{10.5555/1622591.1622600,
author = {Bettini, Claudio and Mascetti, Sergio and Wang, X. Sean},
title = {Supporting Temporal Reasoning by Mapping Calendar Expressions to Minimal Periodic Sets},
year = {2007},
issue_date = {January 2007},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {28},
number = {1},
issn = {1076-9757},
abstract = {In the recent years several research efforts have focused on the concept of time granularity and its applications. A first stream of research investigated the mathematical models behind the notion of granularity and the algorithms to manage temporal data based on those models. A second stream of research investigated symbolic formalisms providing a set of algebraic operators to define granularities in a compact and compositional way. However, only very limited manipulation algorithms have been proposed to operate directly on the algebraic representation making it unsuitable to use the symbolic formalisms in applications that need manipulation of granularities.This paper aims at filling the gap between the results from these two streams of research, by providing an efficient conversion from the algebraic representation to the equivalent low-level representation based on the mathematical models. In addition, the conversion returns a minimal representation in terms of period length. Our results have a major practical impact: users can more easily define arbitrary granularities in terms of algebraic operators, and then access granularity reasoning and other services operating efficiently on the equivalent, minimal low-level representation. As an example, we illustrate the application to temporal constraint reasoning with multiple granularities.From a technical point of view, we propose an hybrid algorithm that interleaves the conversion of calendar subexpressions into periodical sets with the minimization of the period length. The algorithm returns set-based granularity representations having minimal period length, which is the most relevant parameter for the performance of the considered reasoning services. Extensive experimental work supports the techniques used in the algorithm, and shows the efficiency and effectiveness of the algorithm.},
journal = {J. Artif. Int. Res.},
month = mar,
pages = {299–348},
numpages = {50}
}

@article{10.5555/1622591.1622599,
author = {Hansen, Eric A. and Zhou, Rong},
title = {Anytime Heuristic Search},
year = {2007},
issue_date = {January 2007},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {28},
number = {1},
issn = {1076-9757},
abstract = {We describe how to convert the heuristic search algorithm A* into an anytime algorithm that finds a sequence of improved solutions and eventually converges to an optimal solution. The approach we adopt uses weighted heuristic search to find an approximate solution quickly, and then continues the weighted search to find improved solutions as well as to improve a bound on the suboptimality of the current solution. When the time available to solve a search problem is limited or uncertain, this creates an anytime heuristic search algorithm that allows a flexible tradeoff between search time and solution quality. We analyze the properties of the resulting Anytime A* algorithm, and consider its performance in three domains; sliding-tile puzzles, STRIPS planning, and multiple sequence alignment. To illustrate the generality of this approach, we also describe how to transform the memory-efficient search algorithm Recursive Best-First Search (RBFS) into an anytime algorithm.},
journal = {J. Artif. Int. Res.},
month = mar,
pages = {267–297},
numpages = {31}
}

@article{10.5555/1622591.1622598,
author = {Blumrosen, Liad and Nisan, Noam and Segal, Ilya},
title = {Auctions with Severely Bounded Communication},
year = {2007},
issue_date = {January 2007},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {28},
number = {1},
issn = {1076-9757},
abstract = {We study auctions with severe bounds on the communication allowed: each bidder may only transmit t bits of information to the auctioneer. We consider both welfare- and profit-maximizing auctions under this communication restriction. For both measures, we determine the optimal auction and show that the loss incurred relative to unconstrained auctions is mild. We prove non-surprising properties of these kinds of auctions, e.g., that in optimal mechanisms bidders simply report the interval in which their valuation lies in, as well as some surprising properties, e.g., that asymmetric auctions are better than symmetric ones and that multi-round auctions reduce the communication complexity only by a linear factor.},
journal = {J. Artif. Int. Res.},
month = mar,
pages = {233–266},
numpages = {34}
}

@article{10.5555/1622591.1622597,
author = {Beck, J. Christopher and Wilson, Nic},
title = {Proactive Algorithms for Job Shop Scheduling with Probabilistic Durations},
year = {2007},
issue_date = {January 2007},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {28},
number = {1},
issn = {1076-9757},
abstract = {Most classical scheduling formulations assume a fixed and known duration for each activity. In this paper, we weaken this assumption, requiring instead that each duration can be represented by an independent random variable with a known mean and variance. The best solutions are ones which have a high probability of achieving a good makespan. We first create a theoretical framework, formally showing how Monte Carlo simulation can be combined with deterministic scheduling algorithms to solve this problem. We propose an associated deterministic scheduling problem whose solution is proved, under certain conditions, to be a lower bound for the probabilistic problem. We then propose and investigate a number of techniques for solving such problems based on combinations of Monte Carlo simulation, solutions to the associated deterministic problem, and either constraint programming or tabu search. Our empirical results demonstrate that a combination of the use of the associated deterministic problem and Monte Carlo simulation results in algorithms that scale best both in terms of problem size and uncertainty. Further experiments point to the correlation between the quality of the deterministic solution and the quality of the probabilistic solution as a major factor responsible for this success.},
journal = {J. Artif. Int. Res.},
month = mar,
pages = {183–232},
numpages = {50}
}

@article{10.5555/1622591.1622596,
author = {Procaccia, Ariel D. and Rosenschein, Jeffrey S.},
title = {Junta Distributions and the Average-Case Complexity of Manipulating Elections},
year = {2007},
issue_date = {January 2007},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {28},
number = {1},
issn = {1076-9757},
abstract = {Encouraging voters to truthfully reveal their preferences in an election has long been an important issue. Recently, computational complexity has been suggested as a means of precluding strategic behavior. Previous studies have shown that some voting protocols are hard to manipulate, but used NP-hardness as the complexity measure. Such a worst-case analysis may be an insufficient guarantee of resistance to manipulation.Indeed, we demonstrate that NP-hard manipulations may be tractable in the average-case. For this purpose, we augment the existing theory of average-case complexity with some new concepts. In particular, we consider elections distributed with respect to junta distributions, which concentrate on hard instances. We use our techniques to prove that scoring protocols are susceptible to manipulation by coalitions, when the number of candidates is constant.},
journal = {J. Artif. Int. Res.},
month = feb,
pages = {157–181},
numpages = {25}
}

@article{10.5555/1622591.1622595,
author = {Coles, Andrew and Smith, Amanda},
title = {Marvin: A Heuristic Search Planner with Online Macro-Action Learning},
year = {2007},
issue_date = {January 2007},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {28},
number = {1},
issn = {1076-9757},
abstract = {This paper describes Marvin, a planner that competed in the Fourth International Planning Competition (IPC 4). Marvin uses action-sequence-memoisation techniques to generate macro-actions, which are then used during search for a solution plan. We provide an overview of its architecture and search behaviour, detailing the algorithms used. We also empirically demonstrate the effectiveness of its features in various planning domains; in particular, the effects on performance due to the use of macro-actions, the novel features of its search behaviour, and the native support of ADL and Derived Predicates.},
journal = {J. Artif. Int. Res.},
month = feb,
pages = {119–156},
numpages = {38}
}

@article{10.5555/1622591.1622594,
author = {Jia, Haixia and Moore, Cristopher and Strain, Doug},
title = {Generating Hard Satisfiable Formulas by Hiding Solutions Deceptively},
year = {2007},
issue_date = {January 2007},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {28},
number = {1},
issn = {1076-9757},
abstract = {To test incomplete search algorithms for constraint satisfaction problems such as 3- SAT, we need a source of hard, but satisfiable, benchmark instances. A simple way to do this is to choose a random truth assignment A, and then choose clauses randomly from among those satisfied by A. However, this method tends to produce easy problems, since the majority of literals point toward the "hidden" assignment A. Last year, Achlioptas, Jia and Moore proposed a problem generator that cancels this effect by hiding both A and its complement A (Achlioptas, Jia, & Moore, 2004). While the resulting formulas appear to be just as hard for DPLL algorithms as random 3-SAT formulas with no hidden assignment, they can be solved by WalkSAT in only polynomial time.Here we propose a new method to cancel the attraction to A, by choosing a clause with t > 0 literals satisfied by A with probability proportional to q>t for some q < 1. By varying q, we can generate formulas whose variables have no bias, i.e., which are equally likely to be true or false; we can even cause the formula to "deceptively" point away from A. We present theoretical and experimental results suggesting that these formulas are exponentially hard both for DPLL algorithms and for incomplete algorithms such as WalkSAT.},
journal = {J. Artif. Int. Res.},
month = feb,
pages = {107–118},
numpages = {12}
}

@article{10.5555/1622591.1622593,
author = {Everaere, Patricia and Konieczny, S\'{e}bastien and Marquis, Pierre},
title = {The Strategy-Proofness Landscape of Merging},
year = {2007},
issue_date = {January 2007},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {28},
number = {1},
issn = {1076-9757},
abstract = {Merging operators aim at defining the beliefs/goals of a group of agents from the beliefs/goals of each member of the group. Whenever an agent of the group has preferences over the possible results of the merging process (i.e., the possible merged bases), she can try to rig the merging process by lying on her true beliefs/goals if this leads to a better merged base according to her point of view. Obviously, strategy-proof operators are highly desirable in order to guarantee equity among agents even when some of them are not sincere. In this paper, we draw the strategy-proof landscape for many merging operators from the literature, including model-based ones and formula-based ones. Both the general case and several restrictions on the merging process are considered.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {49–105},
numpages = {57}
}

@article{10.5555/1622591.1622592,
author = {Bidyuk, Bozhena and Dechter, Rina},
title = {Cutset Sampling for Bayesian Networks},
year = {2007},
issue_date = {January 2007},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {28},
number = {1},
issn = {1076-9757},
abstract = {The paper presents a new sampling methodology for Bayesian networks that samples only a subset of variables and applies exact inference to the rest. Cutset sampling is a network structure-exploiting application of the Rao-Blackwellisation principle to sampling in Bayesian networks. It improves convergence by exploiting memory-based inference algorithms. It can also be viewed as an anytime approximation of the exact cutset-conditioning algorithm developed by Pearl. Cutset sampling can be implemented efficiently when the sampled variables constitute a loop-cutset of the Bayesian network and, more generally, when the induced width of the network's graph conditioned on the observed sampled variables is bounded by a constant w. We demonstrate empirically the benefit of this scheme on a range of benchmarks.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {1–48},
numpages = {48}
}

@article{10.5555/1622572.1622590,
author = {Rossi, Francesca and Venable, Kristen Brent and Yorke-Smith, Neil},
title = {Uncertainty in Soft Temporal Constraint Problems: A General Framework and Controllability Algorithms for the Fuzzy Case},
year = {2006},
issue_date = {September 2006},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {27},
number = {1},
issn = {1076-9757},
abstract = {In real-life temporal scenarios, uncertainty and preferences are often essential and coexisting aspects. We present a formalism where quantitative temporal constraints with both preferences and uncertainty can be defined. We show how three classical notions of controllability (that is, strong, weak, and dynamic), which have been developed for uncertain temporal problems, can be generalized to handle preferences as well. After defining this general framework, we focus on problems where preferences follow the fuzzy approach, and with properties that assure tractability. For such problems, we propose algorithms to check the presence of the controllability properties. In particular, we show that in such a setting dealing simultaneously with preferences and uncertainty does not increase the complexity of controllability testing. We also develop a dynamic execution algorithm, of polynomial complexity, that produces temporal plans under uncertainty that are optimal with respect to fuzzy preferences.},
journal = {J. Artif. Int. Res.},
month = dec,
pages = {617–674},
numpages = {58}
}

@article{10.5555/1622572.1622589,
author = {Barbulescu, Laura and Howe, Adele E. and Whitley, L. Darrell and Roberts, Mark},
title = {Understanding Algorithm Performance on an Oversubscribed Scheduling Application},
year = {2006},
issue_date = {September 2006},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {27},
number = {1},
issn = {1076-9757},
abstract = {The best performing algorithms for a particular oversubscribed scheduling application, Air Force Satellite Control Network (AFSCN) scheduling, appear to have little in common. Yet, through careful experimentation and modeling of performance in real problem instances, we can relate characteristics of the best algorithms to characteristics of the application. In particular, we find that plateaus dominate the search spaces (thus favoring algorithms that make larger changes to solutions) and that some randomization in exploration is critical to good performance (due to the lack of gradient information on the plateaus). Based on our explanations of algorithm performance, we develop a new algorithm that combines characteristics of the best performers; the new algorithm's performance is better than the previous best. We show how hypothesis driven experimentation and search modeling can both explain algorithm performance and motivate the design of a new algorithm.},
journal = {J. Artif. Int. Res.},
month = dec,
pages = {577–615},
numpages = {39}
}

@article{10.5555/1622572.1622588,
author = {Yilmaz, \"{O}zg\"{u}r and Say, A. C. Cem},
title = {Causes of Ineradicable Spurious Predictions in Qualitative Simulation},
year = {2006},
issue_date = {September 2006},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {27},
number = {1},
issn = {1076-9757},
abstract = {It was recently proved that a sound and complete qualitative simulator does not exist, that is, as long as the input-output vocabulary of the state-of-the-art QSIM algorithm is used, there will always be input models which cause any simulator with a coverage guarantee to make spurious predictions in its output. In this paper, we examine whether a meaningfully expressive restriction of this vocabulary is possible so that one can build a simulator with both the soundness and completeness properties. We prove several negative results: All sound qualitative simulators, employing subsets of the QSIM representation which retain the operating region transition feature, and support at least the addition and constancy constraints, are shown to be inherently incomplete. Even when the simulations are restricted to run in a single operating region, a constraint vocabulary containing just the addition, constancy, derivative, and multiplication relations makes the construction of sound and complete qualitative simulators impossible.},
journal = {J. Artif. Int. Res.},
month = dec,
pages = {551–575},
numpages = {25}
}

@article{10.5555/1622572.1622587,
author = {Dolgov, Dmitri A. and Durfee, Edmund H.},
title = {Resource Allocation among Agents with MDP-Induced Preferences},
year = {2006},
issue_date = {September 2006},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {27},
number = {1},
issn = {1076-9757},
abstract = {Allocating scarce resources among agents to maximize global utility is, in general, computationally challenging. We focus on problems where resources enable agents to execute actions in stochastic environments, modeled as Markov decision processes (MDPs), such that the value of a resource bundle is defined as the expected value of the optimal MDP policy realizable given these resources. We present an algorithm that simultaneously solves the resource-allocation and the policy-optimization problems. This allows us to avoid explicitly representing utilities over exponentially many resource bundles, leading to drastic (often exponential) reductions in computational complexity. We then use this algorithm in the context of self-interested agents to design a combinatorial auction for allocating resources. We empirically demonstrate the effectiveness of our approach by showing that it can, in minutes, optimally solve problems for which a straightforward combinatorial resource-allocation technique would require the agents to enumerate up to 2100 resource bundles and the auctioneer to solve an NP-complete problem with an input of that size.},
journal = {J. Artif. Int. Res.},
month = dec,
pages = {505–549},
numpages = {45}
}

@article{10.5555/1622572.1622586,
author = {Viappiani, Paolo and Faltings, Boi and Pu, Pearl},
title = {Preference-Based Search Using Example-Critiquing with Suggestions},
year = {2006},
issue_date = {September 2006},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {27},
number = {1},
issn = {1076-9757},
abstract = {We consider interactive tools that help users search for their most preferred item in a large collection of options. In particular, we examine example-critiquing, a technique for enabling users to incrementally construct preference models by critiquing example options that are presented to them. We present novel techniques for improving the example-critiquing technology by adding suggestions to its displayed options. Such suggestions are calculated based on an analysis of users' current preference model and their potential hidden preferences. We evaluate the performance of our model-based suggestion techniques with both synthetic and real users. Results show that such suggestions are highly attractive to users and can stimulate them to express more preferences to improve the chance of identifying their most preferred item by up to 78%.},
journal = {J. Artif. Int. Res.},
month = dec,
pages = {465–503},
numpages = {39}
}

@article{10.5555/1622572.1622585,
author = {Zhang, Yuanlin and Yap, Roland H. C.},
title = {Set Intersection and Consistency in Constraint Networks},
year = {2006},
issue_date = {September 2006},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {27},
number = {1},
issn = {1076-9757},
abstract = {In this paper, we show that there is a close relation between consistency in a constraint network and set intersection. A proof schema is provided as a generic way to obtain consistency properties from properties on set intersection. This approach not only simplifies the understanding of and unifies many existing consistency results, but also directs the study of consistency to that of set intersection properties in many situations, as demonstrated by the results on the convexity and tightness of constraints in this paper. Specifically, we identify a new class of tree convex constraints where local consistency ensures global consistency. This generalizes row convex constraints. Various consistency results are also obtained on constraint networks where only some, in contrast to all in the existing work, constraints are tight.},
journal = {J. Artif. Int. Res.},
month = dec,
pages = {441–464},
numpages = {24}
}

@article{10.5555/1622572.1622584,
author = {H\"{o}lldobler, Steffen and Karabaev, Eldar and Skvortsova, Olga},
title = {FLUCAP: A Heuristic Search Planner for First-Order MDPs},
year = {2006},
issue_date = {September 2006},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {27},
number = {1},
issn = {1076-9757},
abstract = {We present a heuristic search algorithm for solving first-order Markov Decision Processes (FOMDPs). Our approach combines first-order state abstraction that avoids evaluating states individually, and heuristic search that avoids evaluating all states. Firstly, in contrast to existing systems, which start with propositionalizing the FOMDP and then perform state abstraction on its propositionalized version we apply state abstraction directly on the FOMDP avoiding propositionalization. This kind of abstraction is referred to as first-order state abstraction. Secondly, guided by an admissible heuristic, the search is restricted to those states that are reachable from the initial state. We demonstrate the usefulness of the above techniques for solving FOMDPs with a system, referred to as FluCaP (formerly, FCPlanner), that entered the probabilistic track of the 2004 International Planning Competition (IPC'2004) and demonstrated an advantage over other planners on the problems represented in first-order terms.},
journal = {J. Artif. Int. Res.},
month = dec,
pages = {419–439},
numpages = {21}
}

@article{10.5555/1622572.1622583,
author = {Fatima, Shaheen S. and Wooldridge, Michael and Jennings, Nicholas R.},
title = {Multi-Issue Negotiation with Deadlines},
year = {2006},
issue_date = {September 2006},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {27},
number = {1},
issn = {1076-9757},
abstract = {This paper studies bilateral multi-issue negotiation between self-interested autonomous agents. Now, there are a number of different procedures that can be used for this process; the three main ones being the package deal procedure in which all the issues are bundled and discussed together, the simultaneous procedure in which the issues are discussed simultaneously but independently of each other, and the sequential procedure in which the issues are discussed one after another. Since each of them yields a different outcome, a key problem is to decide which one to use in which circumstances. Specifically, we consider this question for a model in which the agents have time constraints (in the form of both deadlines and discount factors) and information uncertainty (in that the agents do not know the opponent's utility function). For this model, we consider issues that are both independent and those that are interdependent and determine equilibria for each case for each procedure. In so doing, we show that the package deal is in fact the optimal procedure for each party. We then go on to show that, although the package deal may be computationally more complex than the other two procedures, it generates Pareto optimal outcomes (unlike the other two), it has similar earliest and latest possible times of agreement to the simultaneous procedure (which is better than the sequential procedure), and that it (like the other two procedures) generates a unique outcome only under certain conditions (which we define).},
journal = {J. Artif. Int. Res.},
month = nov,
pages = {381–417},
numpages = {37}
}

@article{10.5555/1622572.1622582,
author = {Pineau, Joelle and Gordon, Geoffrey and Thrun, Sebastian},
title = {Anytime Point-Based Approximations for Large POMDPs},
year = {2006},
issue_date = {September 2006},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {27},
number = {1},
issn = {1076-9757},
abstract = {The Partially Observable Markov Decision Process has long been recognized as a rich framework for real-world planning and control problems, especially in robotics. However exact solutions in this framework are typically computationally intractable for all but the smallest problems. A well-known technique for speeding up POMDP solving involves performing value backups at specific belief points, rather than over the entire belief simplex. The efficiency of this approach, however, depends greatly on the selection of points. This paper presents a set of novel techniques for selecting informative belief points which work well in practice. The point selection procedure is combined with point-based value backups to form an effective anytime POMDP algorithm called Point-Based Value Iteration (PBVI). The first aim of this paper is to introduce this algorithm and present a theoretical analysis justifying the choice of belief selection technique. The second aim of this paper is to provide a thorough empirical comparison between PBVI and other state-of-the-art POMDP methods, in particular the Perseus algorithm, in an effort to highlight their similarities and differences. Evaluation is performed using both standard POMDP domains and realistic robotic tasks.},
journal = {J. Artif. Int. Res.},
month = nov,
pages = {335–380},
numpages = {46}
}

@article{10.5555/1622572.1622581,
author = {Liu, Lengning and Truszczynski, Miros\law},
title = {Properties and Applications of Programs with Monotone and Convex Constraints},
year = {2006},
issue_date = {September 2006},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {27},
number = {1},
issn = {1076-9757},
abstract = {We study properties of programs with monotone and convex constraints. We extend to these formalisms concepts and results from normal logic programming. They include the notions of strong and uniform equivalence with their characterizations, tight programs and Fages Lemma, program completion and loop formulas. Our results provide an abstract account of properties of some recent extensions of logic programming with aggregates, especially the formalism of lparse programs. They imply a method to compute stable models of lparse programs by means of off-the-shelf solvers of pseudo-boolean constraints, which is often much faster than the smodels system.},
journal = {J. Artif. Int. Res.},
month = nov,
pages = {299–334},
numpages = {36}
}

@article{10.5555/1622572.1622580,
author = {Fox, Maria and Long, Derek},
title = {Modelling Mixed Discrete-Continuous Domains for Planning},
year = {2006},
issue_date = {September 2006},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {27},
number = {1},
issn = {1076-9757},
abstract = {In this paper we present PDDL+, a planning domain description language for modelling mixed discrete-continuous planning domains. We describe the syntax and modelling style of PDDL+, showing that the language makes convenient the modelling of complex time-dependent effects. We provide a formal semantics for PDDL+ by mapping planning instances into constructs of hybrid automata. Using the syntax of HAs as our semantic model we construct a semantic mapping to labelled transition systems to complete the formal interpretation of PDDL+ planning instances.An advantage of building a mapping from PDDL+ to HA theory is that it forms a bridge between the Planning and Real Time Systems research communities. One consequence is that we can expect to make use of some of the theoretical properties of HAs. For example, for a restricted class of HAs the Reachability problem (which is equivalent to Plan Existence) is decidable.PDDL+ provides an alternative to the continuous durative action model of PDDL2.1, adding a more flexible and robust model of time-dependent behaviour.},
journal = {J. Artif. Int. Res.},
month = oct,
pages = {235–297},
numpages = {63}
}

@article{10.5555/1622572.1622579,
author = {Muslea, Ion and Minton, Steven and Knoblock, Craig A.},
title = {Active Learning with Multiple Views},
year = {2006},
issue_date = {September 2006},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {27},
number = {1},
issn = {1076-9757},
abstract = {Active learners alleviate the burden of labeling large amounts of data by detecting and asking the user to label only the most informative

license: Unlicense

repository: goyalkaraniit/acm-cr

repo_name: goyalkaraniit/acm-cr