text:
examples in the domain. We focus here on active learning for multi-view domains, in which there are several disjoint subsets of features (views), each of which is sufficient to learn the target concept. In this paper we make several contributions. First, we introduce Co-Testing, which is the first approach to multi-view active learning. Second, we extend the multi-view learning framework by also exploiting weak views, which are adequate only for learning a concept that is more general/specific than the target concept. Finally, we empirically show that Co-Testing outperforms existing active learners on a variety of real world domains such as wrapper induction, Web page classification, advertisement removal, and discourse tree parsing.},
journal = {J. Artif. Int. Res.},
month = oct,
pages = {203–233},
numpages = {31}
}

@article{10.5555/1622572.1622578,
author = {Kveton, Branislav and Hauskrecht, Milos and Guestrin, Carlos},
title = {Solving Factored MDPs with Hybrid State and Action Variables},
year = {2006},
issue_date = {September 2006},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {27},
number = {1},
issn = {1076-9757},
abstract = {Efficient representations and solutions for large decision problems with continuous and discrete variables are among the most important challenges faced by the designers of automated decision support systems. In this paper, we describe a novel hybrid factored Markov decision process (MDP) model that allows for a compact representation of these problems, and a new hybrid approximate linear programming (HALP) framework that permits their efficient solutions. The central idea of HALP is to approximate the optimal value function by a linear combination of basis functions and optimize its weights by linear programming. We analyze both theoretical and computational aspects of this approach, and demonstrate its scale-up potential on several hybrid optimization problems.},
journal = {J. Artif. Int. Res.},
month = oct,
pages = {153–201},
numpages = {49}
}

@article{10.5555/1622572.1622577,
author = {Oh, Jong-Hoon and Choi, Key-Sun and Isahara, Hitoshi},
title = {A Comparison of Different Machine Transliteration Models},
year = {2006},
issue_date = {September 2006},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {27},
number = {1},
issn = {1076-9757},
abstract = {Machine transliteration is a method for automatically converting words in one language into phonetically equivalent ones in another language. Machine transliteration plays an important role in natural language applications such as information retrieval and machine translation, especially for handling proper nouns and technical terms. Four machine transliteration models - grapheme-based transliteration model, phoneme-based transliteration model, hybrid transliteration model, and correspondence-based transliteration model - have been proposed by several researchers. To date, however, there has been little research on a framework in which multiple transliteration models can operate simultaneously. Furthermore, there has been no comparison of the four models within the same framework and using the same data. We addressed these problems by 1) modeling the four models within the same framework, 2) comparing them under the same conditions, and 3) developing a way to improve machine transliteration through this comparison. Our comparison showed that the hybrid and correspondence-based models were the most effective and that the four models can be used in a complementary manner to improve machine transliteration performance.},
journal = {J. Artif. Int. Res.},
month = oct,
pages = {119–151},
numpages = {33}
}

@article{10.5555/1622572.1622576,
author = {Lapata, Mirella and Lascarides, Alex},
title = {Learning Sentence-Internal Temporal Relations},
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 propose a data intensive approach for inferring sentence-internal temporal relations. Temporal inference is relevant for practical NLP applications which either extract or synthesize temporal information (e.g., summarisation, question answering). Our method bypasses the need for manual coding by exploiting the presence of markers like after, which overtly signal a temporal relation. We first show that models trained on main and subordinate clauses connected with a temporal marker achieve good performance on a pseudo-disambiguation task simulating temporal inference (during testing the temporal marker is treated as unseen and the models must select the right marker from a set of possible candidates). Secondly, we assess whether the proposed approach holds promise for the semi-automatic creation of temporal annotations. Specifically, we use a model trained on noisy and approximate data (i.e., main and subordinate clauses) to predict intra-sentential relations present in TimeBank, a corpus annotated rich temporal information. Our experiments compare and contrast several probabilistic models differing in their feature space, linguistic assumptions and data requirements. We evaluate performance against gold standard corpora and also against human subjects.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {85–117},
numpages = {33}
}

@article{10.5555/1622572.1622575,
author = {Chai, Joyce Y. and Prasov, Zahar and Qu, Shaolin},
title = {Cognitive Principles in Robust Multimodal Interpretation},
year = {2006},
issue_date = {September 2006},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {27},
number = {1},
issn = {1076-9757},
abstract = {Multimodal conversational interfaces provide a natural means for users to communicate with computer systems through multiple modalities such as speech and gesture. To build effective multimodal interfaces, automated interpretation of user multimodal inputs is important. Inspired by the previous investigation on cognitive status in multimodal human machine interaction, we have developed a greedy algorithm for interpreting user referring expressions (i.e., multimodal reference resolution). This algorithm incorporates the cognitive principles of Conversational Implicature and Givenness Hierarchy and applies constraints from various sources (e.g., temporal, semantic, and contextual) to resolve references. Our empirical results have shown the advantage of this algorithm in efficiently resolving a variety of user references. Because of its simplicity and generality, this approach has the potential to improve the robustness of multimodal input interpretation.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {55–83},
numpages = {29}
}

@article{10.5555/1622572.1622574,
author = {Epshteyn, Arkady and DeJong, Gerald},
title = {Generative Prior Knowledge for Discriminative Classification},
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 novel framework for integrating prior knowledge into discriminative classifiers. Our framework allows discriminative classifiers such as Support Vector Machines (SVMs) to utilize prior knowledge specified in the generative setting. The dual objective of fitting the data and respecting prior knowledge is formulated as a bilevel program, which is solved (approximately) via iterative application of second-order cone programming. To test our approach, we consider the problem of using WordNet (a semantic database of English language) to improve low-sample classification accuracy of newsgroup categorization. WordNet is viewed as an approximate, but readily available source of background knowledge, and our framework is capable of utilizing it in a flexible way.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {25–53},
numpages = {29}
}

@article{10.5555/1622572.1622573,
author = {Geiger, Dan and Meek, Christopher and Wexler, Ydo},
title = {A Variational Inference Procedure Allowing Internal Structure for Overlapping Clusters and Deterministic 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 develop a novel algorithm, called VIP*, for structured variational approximate inference. This algorithm extends known algorithms to allow efficient multiple potential updates for overlapping clusters, and overcomes the difficulties imposed by deterministic constraints. The algorithm's convergence is proven and its applicability demonstrated for genetic linkage analysis.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {1–23},
numpages = {23}
}

@article{10.5555/1622559.1622571,
author = {Hoffmann, J\"{o}rg and Edelkamp, Stefan and Thi\'{e}baux, Sylvie and Englert, Roman and dos Santos Liporace, Frederico and Tr\"{u}g, Sebastian},
title = {Engineering Benchmarks for Planning: The Domains Used in the Deterministic Part of IPC-4},
year = {2006},
issue_date = {May 2006},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {26},
number = {1},
issn = {1076-9757},
abstract = {In a field of research about general reasoning mechanisms, it is essential to have appropriate benchmarks. Ideally, the benchmarks should reflect possible applications of the developed technology. In AI Planning, researchers more and more tend to draw their testing examples from the benchmark collections used in the International Planning Competition (IPC). In the organization of (the deterministic part of) the fourth IPC, IPC-4, the authors therefore invested significant effort to create a useful set of benchmarks. They come from five different (potential) real-world applications of planning: airport ground traffic control, oil derivative transportation in pipeline networks, model-checking safety properties, power supply restoration, and UMTS call setup. Adapting and preparing such an application for use as a benchmark in the IPC involves, at the time, inevitable (often drastic) simplifications, as well as careful choice between, and engineering of, domain encodings. For the first time in the IPC, we used compilations to formulate complex domain features in simple languages such as STRIPS, rather than just dropping the more interesting problem constraints in the simpler language subsets. The article explains and discusses the five application domains and their adaptation to form the PDDL test suites used in IPC-4. We summarize known theoretical results on structural properties of the domains, regarding their computational complexity and provable properties of their topology under the h+ function (an idealized version of the relaxed plan heuristic). We present new (empirical) results illuminating properties such as the quality of the most wide-spread heuristic functions (planning graph, serial planning graph, and relaxed plan), the growth of propositional representations over instance size, and the number of actions available to achieve each fact; we discuss these data in conjunction with the best results achieved by the different kinds of planners participating in IPC-4.},
journal = {J. Artif. Int. Res.},
month = aug,
pages = {453–541},
numpages = {89}
}

@article{10.5555/1622559.1622570,
author = {Davidov, Dmitry and Markovitch, Shaul},
title = {Multiple-Goal Heuristic Search},
year = {2006},
issue_date = {May 2006},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {26},
number = {1},
issn = {1076-9757},
abstract = {This paper presents a new framework for anytime heuristic search where the task is to achieve as many goals as possible within the allocated resources. We show the inadequacy of traditional distance-estimation heuristics for tasks of this type and present alternative heuristics that are more appropriate for multiple-goal search. In particular, we introduce the marginal-utility heuristic, which estimates the cost and the benefit of exploring a subtree below a search node. We developed two methods for online learning of the marginal-utility heuristic. One is based on local similarity of the partial marginal utility of sibling nodes, and the other generalizes marginal-utility over the state feature space. We apply our adaptive and non-adaptive multiple-goal search algorithms to several problems, including focused crawling, and show their superiority over existing methods.},
journal = {J. Artif. Int. Res.},
month = aug,
pages = {417–451},
numpages = {35}
}

@article{10.5555/1622559.1622569,
author = {Giunchiglia, Enrico and Narizzano, Massimo and Tacchella, Armando},
title = {Clause/Term Resolution and Learning in the Evaluation of Quantified Boolean Formulas},
year = {2006},
issue_date = {May 2006},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {26},
number = {1},
issn = {1076-9757},
abstract = {Resolution is the rule of inference at the basis of most procedures for automated reasoning. In these procedures, the input formula is first translated into an equisatisfiable formula in conjunctive normal form (CNF) and then represented as a set of clauses. Deduction starts by inferring new clauses by resolution, and goes on until the empty clause is generated or satisfiability of the set of clauses is proven, e.g., because no new clauses can be generated.In this paper, we restrict our attention to the problem of evaluating Quantified Boolean Formulas (QBFs). In this setting, the above outlined deduction process is known to be sound and complete if given a formula in CNF and if a form of resolution, called "Q-resolution", is used. We introduce Q-resolution on terms, to be used for formulas in disjunctive normal form. We show that the computation performed by most of the available procedures for QBFs -based on the Davis-Logemann-Loveland procedure (DLL) for propositional satisfiability- corresponds to a tree in which Q-resolution on terms and clauses alternate. This poses the theoretical bases for the introduction of learning, corresponding to recording Q-resolution formulas associated with the nodes of the tree. We discuss the problems related to the introduction of learning in DLL based procedures, and present solutions extending state-of-the-art proposals coming from the literature on propositional satisfiability. Finally, we show that our DLL based solver extended with learning, performs significantly better on benchmarks used in the 2003 QBF solvers comparative evaluation.},
journal = {J. Artif. Int. Res.},
month = aug,
pages = {371–416},
numpages = {46}
}

@article{10.5555/1622559.1622568,
author = {Chen, Yixin and Wah, Benjamin W. and Hsu, Chih-Wei},
title = {Temporal Planning Using Subgoal Partitioning and Resolution in SGPlan},
year = {2006},
issue_date = {May 2006},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {26},
number = {1},
issn = {1076-9757},
abstract = {In this paper, we present the partitioning of mutual-exclusion (mutex) constraints in temporal planning problems and its implementation in the SGPlan4 planner. Based on the strong locality of mutex constraints observed in many benchmarks of the Fourth International Planning Competition (IPC4), we propose to partition the constraints of a planning problem into groups based on their subgoals. Constraint partitioning leads to significantly easier subproblems that are similar to the original problem and that can be efficiently solved by the same planner with some modifications to its objective function. We present a partition-and-resolve strategy that looks for locally optimal subplans in constraint-partitioned temporal planning subproblems and that resolves those inconsistent global constraints across the subproblems. We also discuss some implementation details of SGPlan4, which include the resolution of violated global constraints, techniques for handling producible resources, landmark analysis, path finding and optimization, search-space reduction, and modifications of Metric-FF when used as a basic planner in SGPlan4. Last, we show results on the sensitivity of each of these techniques in quality-time trade-offs and experimentally demonstrate that SGPlan4 is effective for solving the IPC3 and IPC4 benchmarks.},
journal = {J. Artif. Int. Res.},
month = aug,
pages = {323–369},
numpages = {47}
}

@article{10.5555/1622559.1622567,
author = {Ramani, Arathi and Markov, Igor L. and Sakallah, Karem A. and Aloul, Fadi A.},
title = {Breaking Instance-Independent Symmetries in Exact Graph Coloring},
year = {2006},
issue_date = {May 2006},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {26},
number = {1},
issn = {1076-9757},
abstract = {Code optimization and high level synthesis can be posed as constraint satisfaction and optimization problems, such as graph coloring used in register allocation. Graph coloring is also used to model more traditional CSPs relevant to AI, such as planning, time-tabling and scheduling. Provably optimal solutions may be desirable for commercial and defense applications. Additionally, for applications such as register allocation and code optimization, naturally-occurring instances of graph coloring are often small and can be solved optimally. A recent wave of improvements in algorithms for Boolean satisfiability (SAT) and 0-1 Integer Linear Programming (ILP) suggests generic problem-reduction methods, rather than problem-specific heuristics, because (1) heuristics may be upset by new constraints, (2) heuristics tend to ignore structure, and (3) many relevant problems are provably inapproximable.Problem reductions often lead to highly symmetric SAT instances, and symmetries are known to slow down SAT solvers. In this work, we compare several avenues for symmetry breaking, in particular when certain kinds of symmetry are present in all generated instances. Our focus on reducing CSPs to SAT allows us to leverage recent dramatic improvement in SAT solvers and automatically benefit from future progress. We can use a variety of black-box SAT solvers without modifying their source code because our symmetry-breaking techniques are static, i.e., we detect symmetries and add symmetry breaking predicates (SBPs) during pre-processing.An important result of our work is that among the types of instance-independent SBPs we studied and their combinations, the simplest and least complete constructions are the most effective. Our experiments also clearly indicate that instance-independent symmetries should mostly be processed together with instance-specific symmetries rather than at the specification level, contrary to what has been suggested in the literature.},
journal = {J. Artif. Int. Res.},
month = jul,
pages = {289–322},
numpages = {34}
}

@article{10.5555/1622559.1622566,
author = {Streeter, Matthew J. and Smith, Stephen F.},
title = {How the Landscape of Random Job Shop Scheduling Instances Depends on the Ratio of Jobs to Machines},
year = {2006},
issue_date = {May 2006},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {26},
number = {1},
issn = {1076-9757},
abstract = {We characterize the search landscape of random instances of the job shop scheduling problem (JSP). Specifically, we investigate how the expected values of (1) backbone size, (2) distance between near-optimal schedules, and (3) makespan of random schedules vary as a function of the job to machine ratio (N/M). For the limiting cases N/M → 0 and N/M → ∞ we provide analytical results, while for intermediate values of N/M we perform experiments. We prove that as N/M → 0, backbone size approaches 100%, while as N/M → ∞ the backbone vanishes. In the process we show that as N/M → 0 (resp. N/M → ∞), simple priority rules almost surely generate an optimal schedule, providing theoretical evidence of an "easy-hard-easy" pattern of typical-case instance difficulty in job shop scheduling. We also draw connections between our theoretical results and the "big valley" picture of JSP landscapes.},
journal = {J. Artif. Int. Res.},
month = jul,
pages = {247–287},
numpages = {41}
}

@article{10.5555/1622559.1622565,
author = {Helmert, Malte},
title = {The Fast Downward Planning System},
year = {2006},
issue_date = {May 2006},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {26},
number = {1},
issn = {1076-9757},
abstract = {Fast Downward is a classical planning system based on heuristic search. It can deal with general deterministic planning problems encoded in the propositional fragment of PDDL2.2, including advanced features like ADL conditions and effects and derived predicates (axioms). Like other well-known planners such as HSP and FF, Fast Downward is a progression planner, searching the space of world states of a planning task in the forward direction. However, unlike other PDDL planning systems, Fast Downward does not use the propositional PDDL representation of a planning task directly. Instead, the input is first translated into an alternative representation called multivalued planning tasks, which makes many of the implicit constraints of a propositional planning task explicit. Exploiting this alternative representation, Fast Downward uses hierarchical decompositions of planning tasks for computing its heuristic function, called the causal graph heuristic, which is very different from traditional HSP-like heuristics based on ignoring negative interactions of operators.In this article, we give a full account of Fast Downward's approach to solving multivalued planning tasks. We extend our earlier discussion of the causal graph heuristic to tasks involving axioms and conditional effects and present some novel techniques for search control that are used within Fast Downward's best-first search algorithm: preferred operators transfer the idea of helpful actions from local search to global best-first search, deferred evaluation of heuristic functions mitigates the negative effect of large branching factors on search performance, and multiheuristic best-first search combines several heuristic evaluation functions within a single search algorithm in an orthogonal way. We also describe efficient data structures for fast state expansion (successor generators and axiom evaluators) and present a new non-heuristic search algorithm called focused iterative-broadening search, which utilizes the information encoded in causal graphs in a novel way.Fast Downward has proven remarkably successful: It won the "classical" (i. e., propositional, non-optimising) track of the 4th International Planning Competition at ICAPS 2004, following in the footsteps of planners such as FF and LPG. Our experiments show that it also performs very well on the benchmarks of the earlier planning competitions and provide some insights about the usefulness of the new search enhancements.},
journal = {J. Artif. Int. Res.},
month = jul,
pages = {191–246},
numpages = {56}
}

@article{10.5555/1622559.1622564,
author = {Heskes, Tom},
title = {Convexity Arguments for Efficient Minimization of the Bethe and Kikuchi Free Energies},
year = {2006},
issue_date = {May 2006},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {26},
number = {1},
issn = {1076-9757},
abstract = {Loopy and generalized belief propagation are popular algorithms for approximate inference in Markov random fields and Bayesian networks. Fixed points of these algorithms have been shown to correspond to extrema of the Bethe and Kikuchi free energy, both of which are approximations of the exact Helmholtz free energy. However, belief propagation does not always converge, which motivates approaches that explicitly minimize the Kikuchi/Bethe free energy, such as CCCP and UPS.Here we describe a class of algorithms that solves this typically non-convex constrained minimization problem through a sequence of convex constrained minimizations of upper bounds on the Kikuchi free energy. Intuitively one would expect tighter bounds to lead to faster algorithms, which is indeed convincingly demonstrated in our simulations. Several ideas are applied to obtain tight convex bounds that yield dramatic speed-ups over CCCP.},
journal = {J. Artif. Int. Res.},
month = jun,
pages = {153–190},
numpages = {38}
}

@article{10.5555/1622559.1622563,
author = {Booth, Richard and Meyer, Thomas},
title = {Admissible and Restrained Revision},
year = {2006},
issue_date = {May 2006},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {26},
number = {1},
issn = {1076-9757},
abstract = {As partial justification of their framework for iterated belief revision Darwiche and Pearl convincingly argued against Boutilier's natural revision and provided a prototypical revision operator that fits into their scheme. We show that the Darwiche-Pearl arguments lead naturally to the acceptance of a smaller class of operators which we refer to as admissible. Admissible revision ensures that the penultimate input is not ignored completely, thereby eliminating natural revision, but includes the Darwiche-Pearl operator, Nayak's lexicographic revision operator, and a newly introduced operator called restrained revision. We demonstrate that restrained revision is the most conservative of admissible revision operators, effecting as few changes as possible, while lexicographic revision is the least conservative, and point out that restrained revision can also be viewed as a composite operator, consisting of natural revision preceded by an application of a "backwards revision" operator previously studied by Papini. Finally, we propose the establishment of a principled approach for choosing an appropriate revision operator in different contexts and discuss future work.},
journal = {J. Artif. Int. Res.},
month = jun,
pages = {127–151},
numpages = {25}
}

@article{10.5555/1622559.1622562,
author = {Daum\'{e}, Hal and Marcu, Daniel},
title = {Domain Adaptation for Statistical Classifiers},
year = {2006},
issue_date = {May 2006},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {26},
number = {1},
issn = {1076-9757},
abstract = {The most basic assumption used in statistical learning theory is that training data and test data are drawn from the same underlying distribution. Unfortunately, in many applications, the "in-domain" test data is drawn from a distribution that is related, but not identical, to the "out-of-domain" distribution of the training data. We consider the common case in which labeled out-of-domain data is plentiful, but labeled in-domain data is scarce. We introduce a statistical formulation of this problem in terms of a simple mixture model and present an instantiation of this framework to maximum entropy classifiers and their linear chain counterparts. We present efficient inference algorithms for this special case based on the technique of conditional expectation maximization. Our experimental results show that our approach leads to improved performance on three real world tasks on four different data sets from the natural language processing domain.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {101–126},
numpages = {26}
}

@article{10.5555/1622559.1622561,
author = {Bryce, Daniel and Kambhampati, Subbarao and Smith, David E.},
title = {Planning Graph Heuristics for Belief Space Search},
year = {2006},
issue_date = {May 2006},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {26},
number = {1},
issn = {1076-9757},
abstract = {Some recent works in conditional planning have proposed reachability heuristics to improve planner scalability, but many lack a formal description of the properties of their distance estimates. To place previous work in context and extend work on heuristics for conditional planning, we provide a formal basis for distance estimates between belief states. We give a definition for the distance between belief states that relies on aggregating underlying state distance measures. We give several techniques to aggregate state distances and their associated properties. Many existing heuristics exhibit a subset of the properties, but in order to provide a standardized comparison we present several generalizations of planning graph heuristics that are used in a single planner. We compliment our belief state distance estimate framework by also investigating efficient planning graph data structures that incorporate BDDs to compute the most effective heuristics.We developed two planners to serve as test-beds for our investigation. The first, CAltAlt, is a conformant regression planner that uses A* search. The second, POND, is a conditional progression planner that uses AO* search. We show the relative effectiveness of our heuristic techniques within these planners. We also compare the performance of these planners with several state of the art approaches in conditional planning.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {35–99},
numpages = {65}
}

@article{10.5555/1622559.1622560,
author = {Halpern, Joseph Y. and Pucella, Riccardo},
title = {A Logic for Reasoning about Evidence},
year = {2006},
issue_date = {May 2006},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {26},
number = {1},
issn = {1076-9757},
abstract = {We introduce a logic for reasoning about evidence that essentially views evidence as a function from prior beliefs (before making an observation) to posterior beliefs (after making the observation). We provide a sound and complete axiomatization for the logic, and consider the complexity of the decision problem. Although the reasoning in the logic is mainly propositional, we allow variables representing numbers and quantification over them. This expressive power seems necessary to capture important properties of evidence.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {1–34},
numpages = {34}
}

@article{10.5555/1622543.1622558,
author = {Mailler, Roger and Lesser, Victor R.},
title = {Asynchronous Partial Overlay: A New Algorithm for Solving Distributed Constraint Satisfaction Problems},
year = {2006},
issue_date = {January 2006},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {25},
number = {1},
issn = {1076-9757},
abstract = {Distributed Constraint Satisfaction (DCSP) has long been considered an important problem in multi-agent systems research. This is because many real-world problems can be represented as constraint satisfaction and these problems often present themselves in a distributed form. In this article, we present a new complete, distributed algorithm called asynchronous partial overlay (APO) for solving DCSPs that is based on a cooperative mediation process. The primary ideas behind this algorithm are that agents, when acting as a mediator, centralize small, relevant portions of the DCSP, that these centralized subproblems overlap, and that agents increase the size of their subproblems along critical paths within the DCSP as the problem solving unfolds. We present empirical evidence that shows that APO outperforms other known, complete DCSP techniques.},
journal = {J. Artif. Int. Res.},
month = apr,
pages = {529–576},
numpages = {48}
}

@article{10.5555/1622543.1622557,
author = {Roy, Amitabha},
title = {Fault Tolerant Boolean Satisfiability},
year = {2006},
issue_date = {January 2006},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {25},
number = {1},
issn = {1076-9757},
abstract = {A δ-model is a satisfying assignment of a Boolean formula for which any small alteration, such as a single bit flip, can be repaired by flips to some small number of other bits, yielding a new satisfying assignment. These satisfying assignments represent robust solutions to optimization problems (e.g., scheduling) where it is possible to recover from unforeseen events (e.g., a resource becoming unavailable). The concept of δ-models was introduced by Ginsberg, Parkes, and Roy (1998), where it was proved that finding δ-models for general Boolean formulas is NP-complete. In this paper, we extend that result by studying the complexity of finding δ-models for classes of Boolean formulas which are known to have polynomial time satisfiability solvers. In particular, we examine 2-SAT, Horn-SAT, Affine-SAT, dual-Horn-SAT, 0-valid and 1-valid SAT. We see a wide variation in the complexity of finding δ-models, e.g., while 2-SAT and Affine-SAT have polynomial time tests for δ-models, testing whether a Horn-SAT formula has one is NP-complete.},
journal = {J. Artif. Int. Res.},
month = apr,
pages = {503–527},
numpages = {25}
}

@article{10.5555/1622543.1622556,
author = {Blum, Ben and Shelton, Christian R. and Koller, Daphne},
title = {A Continuation Method for Nash Equilibria in Structured Games},
year = {2006},
issue_date = {January 2006},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {25},
number = {1},
issn = {1076-9757},
abstract = {Structured game representations have recently attracted interest as models for multi-agent artificial intelligence scenarios, with rational behavior most commonly characterized by Nash equilibria. This paper presents efficient, exact algorithms for computing Nash equilibria in structured game representations, including both graphical games and multi-agent influence diagrams (MAIDs). The algorithms are derived from a continuation method for normal-form and extensive-form games due to Govindan and Wilson; they follow a trajectory through a space of perturbed games and their equilibria, exploiting game structure through fast computation of the Jacobian of the payoff function. They are theoretically guaranteed to find at least one equilibrium of the game, and may find more. Our approach provides the first efficient algorithm for computing exact equilibria in graphical games with arbitrary topology, and the first algorithm to exploit fine-grained structural properties of MAIDs. Experimental results are presented demonstrating the effectiveness of the algorithms and comparing them to predecessors. The running time of the graphical game algorithm is similar to, and often better than, the running time of previous approximate algorithms. The algorithm for MAIDs can effectively solve games that are much larger than those solvable by previous methods.},
journal = {J. Artif. Int. Res.},
month = apr,
pages = {457–502},
numpages = {46}
}

@article{10.5555/1622543.1622555,
author = {Kersting, Kristian and De Raedt, Luc and Raiko, Tapani},
title = {Logical Hidden Markov Models},
year = {2006},
issue_date = {January 2006},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {25},
number = {1},
issn = {1076-9757},
abstract = {Logical hidden Markov models (LOHMMs) upgrade traditional hidden Markov models to deal with sequences of structured symbols in the form of logical atoms, rather than flat characters.This note formally introduces LOHMMs and presents solutions to the three central inference problems for LOHMMs: evaluation, most likely hidden state sequence and parameter estimation. The resulting representation and algorithms are experimentally evaluated on problems from the domain of bioinformatics.},
journal = {J. Artif. Int. Res.},
month = apr,
pages = {425–456},
numpages = {32}
}

@article{10.5555/1622543.1622554,
author = {Brafman, Ronen I. and Domshlak, Carmel and Shimony, Solomon E.},
title = {On Graphical Modeling of Preference and Importance},
year = {2006},
issue_date = {January 2006},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {25},
number = {1},
issn = {1076-9757},
abstract = {In recent years, CP-nets have emerged as a useful tool for supporting preference elicitation, reasoning, and representation. CP-nets capture and support reasoning with qualitative conditional preference statements, statements that are relatively natural for users to express. In this paper, we extend the CP-nets formalism to handle another class of very natural qualitative statements one often uses in expressing preferences in daily life - statements of relative importance of attributes. The resulting formalism, TCP-nets, maintains the spirit of CP-nets, in that it remains focused on using only simple and natural preference statements, uses the ceteris paribus semantics, and utilizes a graphical representation of this information to reason about its consistency and to perform, possibly constrained, optimization using it. The extra expressiveness it provides allows us to better model tradeoffs users would like to make, more faithfully representing their preferences.},
journal = {J. Artif. Int. Res.},
month = mar,
pages = {389–424},
numpages = {36}
}

@article{10.5555/1622543.1622553,
author = {Gutnik, Gery and Kaminka, Gal A.},
title = {Representing Conversations for Scalable Overhearing},
year = {2006},
issue_date = {January 2006},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {25},
number = {1},
issn = {1076-9757},
abstract = {Open distributed multi-agent systems are gaining interest in the academic community and in industry. In such open settings, agents are often coordinated using standardized agent conversation protocols. The representation of such protocols (for analysis, validation, monitoring, etc) is an important aspect of multi-agent applications. Recently, Petri nets have been shown to be an interesting approach to such representation, and radically different approaches using Petri nets have been proposed. However, their relative strengths and weaknesses have not been examined. Moreover, their scalability and suitability for different tasks have not been addressed. This paper addresses both these challenges. First, we analyze existing Petri net representations in terms of their scalability and appropriateness for overhearing, an important task in monitoring open multi-agent systems. Then, building on the insights gained, we introduce a novel representation using Colored Petri nets that explicitly represent legal joint conversation states and messages. This representation approach offers significant improvements in scalability and is particularly suitable for overhearing. Furthermore, we show that this new representation offers a comprehensive coverage of all conversation features of FIPA conversation standards. We also present a procedure for transforming AUML conversation protocol diagrams (a standard human-readable representation), to our Colored Petri net representation.},
journal = {J. Artif. Int. Res.},
month = mar,
pages = {349–387},
numpages = {39}
}

@article{10.5555/1622543.1622552,
author = {Endriss, Ulle and Maudet, Nicolas and Sadri, Fariba and Toni, Francesca},
title = {Negotiating Socially Optimal Allocations of Resources},
year = {2006},
issue_date = {January 2006},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {25},
number = {1},
issn = {1076-9757},
abstract = {A multiagent system may be thought of as an artificial society of autonomous software agents and we can apply concepts borrowed from welfare economics and social choice theory to assess the social welfare of such an agent society. In this paper, we study an abstract negotiation framework where agents can agree on multilateral deals to exchange bundles of indivisible resources. We then analyse how these deals affect social welfare for different instances of the basic framework and different interpretations of the concept of social welfare itself. In particular, we show how certain classes of deals are both sufficient and necessary to guarantee that a socially optimal allocation of resources will be reached eventually.},
journal = {J. Artif. Int. Res.},
month = mar,
pages = {315–348},
numpages = {34}
}

@article{10.5555/1622543.1622551,
author = {Adjiman, Philippe and Chatalic, Philippe and Goasdou\'{e}, Fran\c{c}ois and Rousset, Marie-Christine and Simon, Laurent},
title = {Distributed Reasoning in a Peer-to-Peer Setting: Application to the Semantic Web},
year = {2006},
issue_date = {January 2006},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {25},
number = {1},
issn = {1076-9757},
abstract = {In a peer-to-peer inference system, each peer can reason locally but can also solicit some of its acquaintances, which are peers sharing part of its vocabulary. In this paper, we consider peer-to-peer inference systems in which the local theory of each peer is a set of propositional clauses defined upon a local vocabulary. An important characteristic of peer-to-peer inference systems is that the global theory (the union of all peer theories) is not known (as opposed to partition-based reasoning systems). The main contribution of this paper is to provide the first consequence finding algorithm in a peer-to-peer setting: DECA. It is anytime and computes consequences gradually from the solicited peer to peers that are more and more distant. We exhibit a sufficient condition on the acquaintance graph of the peer-to-peer inference system for guaranteeing the completeness of this algorithm. Another important contribution is to apply this general distributed reasoning setting to the setting of the Semantic Web through the SOMEWHERE semantic peer-to-peer data management system. The last contribution of this paper is to provide an experimental analysis of the scalability of the peer-to-peer infrastructure that we propose, on large networks of 1000 peers.},
journal = {J. Artif. Int. Res.},
month = feb,
pages = {269–314},
numpages = {46}
}

@article{10.5555/1622543.1622550,
author = {Haslum, Patrik},
title = {Improving Heuristics through Relaxed Search: An Analysis of TP4 and HSP<sub>a</sub>* in the 2004 Planning Competition},
year = {2006},
issue_date = {January 2006},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {25},
number = {1},
issn = {1076-9757},
abstract = {The hm admissible heuristics for (sequential and temporal) regression planning are defined by a parameterized relaxation of the optimal cost function in the regression search space, where the parameter m offers a trade-off between the accuracy and computational cost of the heuristic. Existing methods for computing the hm heuristic require time exponential in m, limiting them to small values (m ≤ 2). The hm heuristic can also be viewed as the optimal cost funciton in a relaxation of the search space: this paper presents relaxed search, a method for computing this function partially by searching in the relaxed space. The relaxed search method, because it computes hm only partially, is computationally cheaper and therefore usable for higher values of m. The (complete) h2 heuristic is combined with partial hm heuristics, for m = 3,..., computed by relaxed search, resulting in a more accurate heuristic.This use of the relaxed search method to improve on the h2 heuristic is evaluated by comparing two optimal temporal planners: TP4, which does not use it, and HSP*a, which uses it but is otherwise identical to TP4. The comparison is made on the domains used in the 2004 International Planning Competition, in which both planners participated. Relaxed search is found to be cost effective in some of these domains, but not all. Analysis reveals a characterization of the domains in which relaxed search can be expected to be cost effective, in terms of two measures on the original and relaxed search spaces. In the domains where relaxed search is cost effective, expanding small states is computationally cheaper than expanding large states and small states tend to have small successor states.},
journal = {J. Artif. Int. Res.},
month = feb,
pages = {233–267},
numpages = {35}
}

@article{10.5555/1622543.1622549,
author = {Gerevini, Alfonso and Saetti, Alessandro and Serina, Ivan},
title = {An Approach to Temporal Planning and Scheduling in Domains with Predictable Exogenous Events},
year = {2006},
issue_date = {January 2006},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {25},
number = {1},
issn = {1076-9757},
abstract = {The treatment of exogenous events in planning is practically important in many real-world domains where the preconditions of certain plan actions are affected by such events. In this paper we focus on planning in temporal domains with exogenous events that happen at known times, imposing the constraint that certain actions in the plan must be executed during some predefined time windows. When actions have durations, handling such temporal constraints adds an extra difficulty to planning. We propose an approach to planning in these domains which integrates constraint-based temporal reasoning into a graph-based planning framework using local search. Our techniques are implemented in a planner that took part in the 4th International Planning Competition (IPC-4). A statistical analysis of the results of IPC-4 demonstrates the effectiveness of our approach in terms of both CPU-time and plan quality. Additional experiments show the good performance of the temporal reasoning techniques integrated into our planner.},
journal = {J. Artif. Int. Res.},
month = feb,
pages = {187–231},
numpages = {45}
}

@article{10.5555/1622543.1622548,
author = {Pullan, Wayne and Hoos, Holger H.},
title = {Dynamic Local Search for the Maximum Clique Problem},
year = {2006},
issue_date = {January 2006},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {25},
number = {1},
issn = {1076-9757},
abstract = {In this paper, we introduce DLS-MC, a new stochastic local search algorithm for the maximum clique problem. DLS-MC alternates between phases of iterative improvement, during which suitable vertices are added to the current clique, and plateau search, during which vertices of the current clique are swapped with vertices not contained in the current clique. The selection of vertices is solely based on vertex penalties that are dynamically adjusted during the search, and a perturbation mechanism is used to overcome search stagnation. The behaviour of DLS-MC is controlled by a single parameter, penalty delay, which controls the frequency at which vertex penalties are reduced. We show empirically that DLSMC achieves substantial performance improvements over state-of-the-art algorithms for the maximum clique problem over a large range of the commonly used DIMACS benchmark instances.},
journal = {J. Artif. Int. Res.},
month = feb,
pages = {159–185},
numpages = {27}
}

@article{10.5555/1622543.1622547,
author = {Bulitko, Vadim and Lee, Greg},
title = {Learning in Real-Time Search: A Unifying Framework},
year = {2006},
issue_date = {January 2006},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {25},
number = {1},
issn = {1076-9757},
abstract = {Real-time search methods are suited for tasks in which the agent is interacting with an initially unknown environment in real time. In such simultaneous planning and learning problems, the agent has to select its actions in a limited amount of time, while sensing only a local part of the environment centered at the agent's current location. Real-time heuristic search agents select actions using a limited lookahead search and evaluating the frontier states with a heuristic function. Over repeated experiences, they refine heuristic values of states to avoid infinite loops and to converge to better solutions. The wide spread of such settings in autonomous software and hardware agents has led to an explosion of real-time search algorithms over the last two decades. Not only is a potential user confronted with a hodgepodge of algorithms, but he also faces the choice of control parameters they use. In this paper we address both problems. The first contribution is an introduction of a simple three-parameter framework (named LRTS) which extracts the core ideas behind many existing algorithms. We then prove that LRTA*, Ε-LRTA* , SLA*, and γ-Trap algorithms are special cases of our framework. Thus, they are unified and extended with additional features. Second, we prove completeness and convergence of any algorithm covered by the LRTS framework. Third, we prove several upper-bounds relating the control parameters and solution quality. Finally, we analyze the influence of the three control parameters empirically in the realistic scalable domains of real-time navigation on initially unknown maps from a commercial role-playing game as well as routing in ad hoc sensor networks.},
journal = {J. Artif. Int. Res.},
month = feb,
pages = {119–157},
numpages = {39}
}

@article{10.5555/1622543.1622546,
author = {Fern, Alan and Yoon, Sungwook and Givan, Robert},
title = {Approximate Policy Iteration with a Policy Language Bias: Solving Relational Markov Decision Processes},
year = {2006},
issue_date = {January 2006},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {25},
number = {1},
issn = {1076-9757},
abstract = {We study an approach to policy selection for large relational Markov Decision Processes (MDPs). We consider a variant of approximate policy iteration (API) that replaces the usual value-function learning step with a learning step in policy space. This is advantageous in domains where good policies are easier to represent and learn than the corresponding value functions, which is often the case for the relational MDPs we are interested in. In order to apply API to such problems, we introduce a relational policy language and corresponding learner. In addition, we introduce a new bootstrapping routine for goal-based planning domains, based on random walks. Such bootstrapping is necessary for many large relational MDPs, where reward is extremely sparse, as API is ineffective in such domains when initialized with an uninformed policy. Our experiments show that the resulting system is able to find good policies for a number of classical planning domains and their stochastic variants by solving them as extremely large relational MDPs. The experiments also point to some limitations of our approach, suggesting future work.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {75–118},
numpages = {44}
}

@article{10.5555/1622543.1622545,
author = {Thi\'{e}baux, Sylvie and Gretton, Charles and Slaney, John and Price, David and Kabanza, Froduald},
title = {Decision-Theoretic Planning with Non-Markovian Rewards},
year = {2006},
issue_date = {January 2006},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {25},
number = {1},
issn = {1076-9757},
abstract = {A decision process in which rewards depend on history rather than merely on the current state is called a decision process with non-Markovian rewards (NMRDP). In decision-theoretic planning, where many desirable behaviours are more naturally expressed as properties of execution sequences rather than as properties of states, NMRDPs form a more natural model than the commonly adopted fully Markovian decision process (MDP) model. While the more tractable solution methods developed for MDPs do not directly apply in the presence of non-Markovian rewards, a number of solution methods for NMRDPs have been proposed in the literature. These all exploit a compact specification of the non-Markovian reward function in temporal logic, to automatically translate the NMRDP into an equivalent MDP which is solved using efficient MDP solution methods. This paper presents NMRDPP(Non-Markovian Reward Decision Process Planner), a software platform for the development and experimentation of methods for decision-theoretic planning with non-Markovian rewards. The current version of NMRDPP implements, under a single interface, a family of methods based on existing as well as new approaches which we describe in detail. These include dynamic programming, heuristic search, and structured methods. Using NMRDPP, we compare the methods and identify certain problem features that affect their performance. NMRDPP's treatment of non-Markovian rewards is inspired by the treatment of domain-specific search control knowledge in the TLPlan planner, which it incorporates as a special case. In the First International Probabilistic Planning Competition, NMRDPP was able to compete and perform well in both the domain-independent and hand-coded tracks, using search control knowledge in the latter.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {17–74},
numpages = {58}
}

@article{10.5555/1622543.1622544,
author = {Onder, Nilufer and Whelan, Garrett C. and Li, Li},
title = {Engineering a Conformant Probabilistic Planner},
year = {2006},
issue_date = {January 2006},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {25},
number = {1},
issn = {1076-9757},
abstract = {We present a partial-order, conformant, probabilistic planner, Probapop which competed in the blind track of the Probabilistic Planning Competition in IPC-4. We explain how we adapt distance based heuristics for use with probabilistic domains. Probapop also incorporates heuristics based on probability of success. We explain the successes and diefficulties encountered during the design and implementation of Probapop.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {1–15},
numpages = {15}
}

@article{10.5555/1622519.1622542,
author = {Bonet, Blai and Geffner, H\'{e}ctor},
title = {MGPT: A Probabilistic Planner Based on Heuristic Search},
year = {2005},
issue_date = {July 2005},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {24},
number = {1},
issn = {1076-9757},
abstract = {We describe the version of the GPT planner used in the probabilistic track of the 4th International Planning Competition (IPC-4). This version, called mGPT, solves Markov Decision Processes specified in the PPDDL language by extracting and using different classes of lower bounds along with various heuristic-search algorithms. The lower bounds are extracted from deterministic relaxations where the alternative probabilistic effects of an action are mapped into different, independent, deterministic actions. The heuristic-search algorithms use these lower bounds for focusing the updates and delivering a consistent value function over all states reachable from the initial state and the greedy policy.},
journal = {J. Artif. Int. Res.},
month = dec,
pages = {933–944},
numpages = {12}
}

@article{10.5555/1622519.1622541,
author = {van den Briel, Menkes H. L. and Kambhampati, Subbarao},
title = {Optiplan: Unifying IP-Based and Graph-Based Planning},
year = {2005},
issue_date = {July 2005},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {24},
number = {1},
issn = {1076-9757},
abstract = {The Optiplan planning system is the first integer programming-based planner that successfully participated in the international planning competition. This engineering note describes the architecture of Optiplan and provides the integer programming formulation that enabled it to perform reasonably well in the competition. We also touch upon some recent developments that make integer programming encodings significantly more competitive.},
journal = {J. Artif. Int. Res.},
month = dec,
pages = {919–931},
numpages = {13}
}

@article{10.5555/1622519.1622540,
author = {Jaeger, Manfred},
title = {Ignorability in Statistical and Probabilistic Inference},
year = {2005},
issue_date = {July 2005},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {24},
number = {1},
issn = {1076-9757},
abstract = {When dealing with incomplete data in statistical learning, or incomplete observations in probabilistic inference, one needs to distinguish the fact that a certain event is observed from the fact that the observed event has happened. Since the modeling and computational complexities entailed by maintaining this proper distinction are often prohibitive, one asks for conditions under which it can be safely ignored. Such conditions are given by the missing at random (mar) and coarsened at random (car) assumptions. In this paper we provide an in-depth analysis of several questions relating to mar/car assumptions. Main purpose of our study is to provide criteria by which one may evaluate whether a car assumption is reasonable for a particular data collecting or observational process. This question is complicated by the fact that several distinct versions of mar/car assumptions exist. We therefore first provide an overview over these different versions, in which we highlight the distinction between distributional and coarsening variable induced versions. We show that distributional versions are less restrictive and sufficient for most applications. We then address from two different perspectives the question of when the mar/car assumption is warranted. First we provide a "static" analysis that characterizes the admissibility of the car assumption in terms of the support structure of the joint probability distribution of complete data and incomplete observations. Here we obtain an equivalence characterization that improves and extends a recent result by Gr\"{u}nwald and Halpern. We then turn to a "procedural" analysis that characterizes the admissibility of the car assumption in terms of procedural models for the actual data (or observation) generating process. The main result of this analysis is that the stronger coarsened completely at random (ccar) condition is arguably the most reasonable assumption, as it alone corresponds to data coarsening procedures that satisfy a natural robustness property.},
journal = {J. Artif. Int. Res.},
month = dec,
pages = {889–917},
numpages = {29}
}

@article{10.5555/1622519.1622539,
author = {Younes, H\r{a}kan L. S. and Littman, Michael L. and Weissman, David and Asmuth, John},
title = {The First Probabilistic Track of the International Planning Competition},
year = {2005},
issue_date = {July 2005},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {24},
number = {1},
issn = {1076-9757},
abstract = {The 2004 International Planning Competition, IPC-4, included a probabilistic planning track for the first time. We describe the new domain specification language we created for the track, our evaluation methodology, the competition domains we developed, and the results of the participating teams.},
journal = {J. Artif. Int. Res.},
month = dec,
pages = {851–887},
numpages = {37}
}

@article{10.5555/1622519.1622538,
author = {Beetz, Michael and Grosskreutz, Henrik},
title = {Probabilistic Hybrid Action Models for Predicting Concurrent Percept-Driven Robot Behavior},
year = {2005},
issue_date = {July 2005},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {24},
number = {1},
issn = {1076-9757},
abstract = {This article develops Probabilistic Hybrid Action Models (PHAMs), a realistic causal model for predicting the behavior generated by modern percept-driven robot plans. PHAMs represent aspects of robot behavior that cannot be represented by most action models used in AI planning: the temporal structure of continuous control processes, their non-deterministic effects, several modes of their interferences, and the achievement of triggering conditions in closed-loop robot plans.The main contributions of this article are: (1) PHAMs, a model of concurrent percept-driven behavior, its formalization, and proofs that the model generates probably, qualitatively accurate predictions; and (2) a resource-efficient inference method for PHAMs based on sampling projections from probabilistic action models and state descriptions. We show how PHAMs can be applied to planning the course of action of an autonomous robot office courier based on analytical and experimental results.},
journal = {J. Artif. Int. Res.},
month = dec,
pages = {799–849},
numpages = {51}
}

@article{10.5555/1622519.1622537,
author = {Hoffmann, J\"{o}rg},
title = {Where "Ignoring Delete Lists" Works: Local Search Topology in Planning Benchmarks},
year = {2005},
issue_date = {July 2005},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {24},
number = {1},
issn = {1076-9757},
abstract = {Between 1998 and 2004, the planning community has seen vast progress in terms of the sizes of benchmark examples that domain-independent planners can tackle successfully. The key technique behind this progress is the use of heuristic functions based on relaxing the planning task at hand, where the relaxation is to assume that all delete lists are empty. The unprecedented success of such methods, in many commonly used benchmark examples, calls for an understanding of what classes of domains these methods are well suited for.In the investigation at hand, we derive a formal background to such an understanding. We perform a case study covering a range of 30 commonly used STRIPS and ADL benchmark domains, including all examples used in the first four international planning competitions. We prove connections between domain structure and local search topology - heuristic cost surface properties - under an idealized version of the heuristic functions used in modern planners. The idealized heuristic function is called h+, and differs from the practically used functions in that it returns the length of an optimal relaxed plan, which is NP-hard to compute. We identify several key characteristics of the topology under h+, concerning the existence/non-existence of unrecognized dead ends, as well as the existence/non-existence of constant upper bounds on the difficulty of escaping local minima and benches. These distinctions divide the (set of all) planning domains into a taxonomy of classes of varying h+ topology. As it turns out, many of the 30 investigated domains lie in classes with a relatively easy topology. Most particularly, 12 of the domains lie in classes where FF's search algorithm, provided with h+, is a polynomial solving mechanism.We also present results relating h+ to its approximation as implemented in FF. The behavior regarding dead ends is provably the same. We summarize the results of an empirical investigation showing that, in many domains, the topological qualities of h+ are largely inherited by the approximation. The overall investigation gives a rare example of a successful analysis of the connections between typical-case problem structure, and search performance. The theoretical investigation also gives hints on how the topological phenomena might be automatically recognizable by domain analysis techniques. We outline some preliminary steps we made into that direction.},
journal = {J. Artif. Int. Res.},
month = nov,
pages = {685–758},
numpages = {74}
}

@article{10.5555/1622519.1622536,
author = {Samaras, Nikolaos and Stergiou, Kostas},
title = {Binary Encodings of Non-Binary Constraint Satisfaction Problems: Algorithms and Experimental Results},
year = {2005},
issue_date = {July 2005},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {24},
number = {1},
issn = {1076-9757},
abstract = {A non-binary Constraint Satisfaction Problem (CSP) can be solved directly using extended versions of binary techniques. Alternatively, the non-binary problem can be translated into an equivalent binary one. In this case, it is generally accepted that the translated problem can be solved by applying well-established techniques for binary CSPs. In this paper we evaluate the applicability of the latter approach. We demonstrate that the use of standard techniques for binary CSPs in the encodings of non-binary problems is problematic and results in models that are very rarely competitive with the non-binary representation. To overcome this, we propose specialized arc consistency and search algorithms for binary encodings, and we evaluate them theoretically and empirically. We consider three binary representations; the hidden variable encoding, the dual encoding, and the double encoding. Theoretical and empirical results show that, for certain classes of non-binary constraints, binary encodings are a competitive option, and in many cases, a better one than the non-binary representation.},
journal = {J. Artif. Int. Res.},
month = nov,
pages = {641–684},
numpages = {44}
}

@article{10.5555/1622519.1622535,
author = {Achlioptas, Dimitris and Jia, Haixia and Moore, Cristopher},
title = {Hiding Satisfying Assignments: Two Are Better than One},
year = {2005},
issue_date = {July 2005},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {24},
number = {1},
issn = {1076-9757},
abstract = {The evaluation of incomplete satisfiability solvers depends critically on the availability of hard satisfiable instances. A plausible source of such instances consists of random k- SAT formulas whose clauses are chosen uniformly from among all clauses satisfying some randomly chosen truth assignment A. Unfortunately, instances generated in this manner tend to be relatively easy and can be solved efficiently by practical heuristics. Roughly speaking, for a number of different algorithms, A acts as a stronger and stronger attractor as the formula's density increases. Motivated by recent results on the geometry of the space of satisfying truth assignments of random k-SAT and NAE-k-SAT formulas, we introduce a simple twist on this basic model, which appears to dramatically increase its hardness. Namely, in addition to forbidding the clauses violated by the hidden assignment A, we also forbid the clauses violated by its complement, so that both A and A are satisfying. It appears that under this "symmetrization" the effects of the two attractors largely cancel out, making it much harder for algorithms to find any truth assignment. We give theoretical and experimental evidence supporting this assertion.},
journal = {J. Artif. Int. Res.},
month = nov,
pages = {623–639},
numpages = {17}
}

@article{10.5555/1622519.1622534,
author = {Botea, Adi and Enzenberger, Markus and M\"{u}ller, Martin and Schaeffer, Jonathan},
title = {Macro-FF: Improving AI Planning with Automatically Learned Macro-Operators},
year = {2005},
issue_date = {July 2005},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {24},
number = {1},
issn = {1076-9757},
abstract = {Despite recent progress in AI planning, many benchmarks remain challenging for current planners. In many domains, the performance of a planner can greatly be improved by discovering and exploiting information about the domain structure that is not explicitly encoded in the initial PDDL formulation. In this paper we present and compare two automated methods that learn relevant information from previous experience in a domain and use it to solve new problem instances. Our methods share a common four-step strategy. First, a domain is analyzed and structural information is extracted, then macro-operators are generated based on the previously discovered structure. A filtering and ranking procedure selects the most useful macro-operators. Finally, the selected macros are used to speed up future searches.We have successfully used such an approach in the fourth international planning competition IPC-4. Our system, Macro-FF, extends Hoffmann's state-of-the-art planner FF 2.3 with support for two kinds of macro-operators, and with engineering enhancements. We demonstrate the effectiveness of our ideas on benchmarks from international planning competitions. Our results indicate a large reduction in search effort in those complex domains where structural information can be inferred.},
journal = {J. Artif. Int. Res.},
month = oct,
pages = {581–621},
numpages = {41}
}

@article{10.5555/1622519.1622533,
author = {Hoffmann, J\"{o}rg and Edelkamp, Stefan},
title = {The Deterministic Part of IPC-4: An Overview},
year = {2005},
issue_date = {July 2005},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {24},
number = {1},
issn = {1076-9757},
abstract = {We provide an overview of the organization and results of the deterministic part of the 4th International Planning Competition, i.e., of the part concerned with evaluating systems doing deterministic planning. IPC-4 attracted even more competing systems than its already large predecessors, and the competition event was revised in several important respects. After giving an introduction to the IPC, we briefly explain the main differences between the deterministic part of IPC-4 and its predecessors. We then introduce formally the language used, called PDDL2.2 that extends PDDL2.1 by derived predicates and timed initial literals. We list the competing systems and overview the results of the competition. The entire set of data is far too large to be presented in full. We provide a detailed summary; the complete data is available in an online appendix. We explain how we awarded the competition prizes.},
journal = {J. Artif. Int. Res.},
month = oct,
pages = {519–579},
numpages = {61}
}

@article{10.5555/1622519.1622532,
author = {Vo, Quoc Bao and Foo, Norman Y.},
title = {Reasoning about Action: An Argumentation-Theoretic Approach},
year = {2005},
issue_date = {July 2005},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {24},
number = {1},
issn = {1076-9757},
abstract = {We present a uniform non-monotonic solution to the problems of reasoning about action on the basis of an argumentation-theoretic approach. Our theory is provably correct relative to a sensible minimisation policy introduced on top of a temporal propositional logic. Sophisticated problem domains can be formalised in our framework. As much attention of researchers in the field has been paid to the traditional and basic problems in reasoning about actions such as the frame, the qualification and the ramification problems, approaches to these problems within our formalisation lie at heart of the expositions presented in this paper.},
journal = {J. Artif. Int. Res.},
month = oct,
pages = {465–518},
numpages = {54}
}

@article{10.5555/1622519.1622531,
author = {Dutta, Partha S. and Jennings, Nicholas R. and Moreau, Luc},
title = {Cooperative Information Sharing to Improve Distributed Learning in Multi-Agent Systems},
year = {2005},
issue_date = {July 2005},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {24},
number = {1},
issn = {1076-9757},
abstract = {Effective coordination of agents' actions in partially-observable domains is a major challenge of multi-agent systems research. To address this, many researchers have developed techniques that allow the agents to make decisions based on estimates of the states and actions of other agents that are typically learnt using some form of machine learning algorithm. Nevertheless, many of these approaches fail to provide an actual means by which the necessary information is made available so that the estimates can be learnt. To this end, we argue that cooperative communication of state information between agents is one such mechanism. However, in a dynamically changing environment, the accuracy and timeliness of this communicated information determine the fidelity of the learned estimates and the usefulness of the actions taken based on these. Given this, we propose a novel information-sharing protocol, post-task-completion sharing, for the distribution of state information. vVe then show, through a formal analysis, the improvement in the quality of estimates produced using our strategy over the widely used protocol of sharing information between nearest neighbours. Moreover, communication heuristics designed around our information-sharing principle are subjected to empirical evaluation along with other benchmark strategies (including Littman's Q-routing and Stone's TPOT-RL) in a simulated call-routing application. These studies, conducted across a range of environmental settings, show that, compared to the different benchmarks used, our strategy generates an improvement of up to 60% in the call connection rate; of more than 1000% in the ability to connect long-distance calls; and incurs as low as 0.25 of the message overhead.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {407–463},
numpages = {57}
}

@article{10.5555/1622519.1622530,
author = {Gottlob, Georg and Greco, Gianluigi and Scarcello, Francesco},
title = {Pure Nash Equilibria: Hard and Easy Games},
year = {2005},
issue_date = {July 2005},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {24},
number = {1},
issn = {1076-9757},
abstract = {We investigate complexity issues related to pure Nash equilibria of strategic games. We show that, even in very restrictive settings, determining whether a game has a pure Nash Equilibrium is NP-hard, while deciding whether a game has a strong Nash equilibrium is Σ2P-complete. We then study practically relevant restrictions that lower the complexity. In particular, we are interested in quantitative and qualitative restrictions of the way each player's payoff depends on moves of other players. We say that a game has small neighborhood if the utility function for each player depends only on (the actions of) a logarithmically small number of other players. The dependency structure of a game G can be expressed by a graph G(G) or by a hypergraph H(G). By relating Nash equilibrium problems to constraint satisfaction problems (CSPs), we show that if G has small neighborhood and if H(G) has bounded hypertree width (or if G(G) has bounded treewidth), then finding pure Nash and Pareto equilibria is feasible in polynomial time. If the game is graphical, then these problems are LOGCFL-complete and thus in the class NC2 of highly parallelizable problems.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {357–406},
numpages = {50}
}

@article{10.5555/1622519.1622529,
author = {Khardon, Roni and Roth, Dan and Servedio, Rocco A.},
title = {Efficiency versus Convergence of Boolean Kernels for On-Line Learning Algorithms},
year = {2005},
issue_date = {July 2005},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {24},
number = {1},
issn = {1076-9757},
abstract = {The paper studies machine learning problems where each example is described using a set of Boolean features and where hypotheses are represented by linear threshold elements. One method of increasing the expressiveness of learned hypotheses in this context is to expand the feature set to include conjunctions of basic features. This can be done explicitly or where possible by using a kernel function. Focusing on the well known Perceptron and Winnow algorithms, the paper demonstrates a tradeoff between the computational efficiency with which the algorithm can be run over the expanded feature space and the generalization ability of the corresponding learning algorithm.We first describe several kernel functions which capture either limited forms of conjunctions or all conjunctions. We show that these kernels can be used to efficiently run the Perceptron algorithm over a feature space of exponentially many conjunctions; however we also show that using such kernels, the Perceptron algorithm can provably make an exponential number of mistakes even when learning simple functions.We then consider the question of whether kernel functions can analogously be used to run the multiplicative-update Winnow algorithm over an expanded feature space of exponentially many conjunctions. Known upper bounds imply that the Winnow algorithm can learn Disjunctive Normal Form (DNF) formulae with a polynomial mistake bound in this setting. However, we prove that it is computationally hard to simulate Winnow's behavior for learning DNF over such a feature set. This implies that the kernel functions which correspond to running Winnow for this problem are not efficiently computable, and that there is no general construction that can run Winnow with kernels.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {341–356},
numpages = {16}
}

@article{10.5555/1622519.1622528,
author = {Cimiano, Philipp and Hotho, Andreas and Staab, Steffen},
title = {Learning Concept Hierarchies from Text Corpora Using Formal Concept Analysis},
year = {2005},
issue_date = {July 2005},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {24},
number = {1},
issn = {1076-9757},
abstract = {We present a novel approach to the automatic acquisition of taxonomies or concept hierarchies from a text corpus. The approach is based on Formal Concept Analysis (FCA), a method mainly used for the analysis of data, i.e. for investigating and processing explicitly given information. We follow Harris' distributional hypothesis and model the context of a certain term as a vector representing syntactic dependencies which are automatically acquired from the text corpus with a linguistic parser. On the basis of this context information, FCA produces a lattice that we convert into a special kind of partial order constituting a concept hierarchy. The approach is evaluated by comparing the resulting concept hierarchies with hand-crafted taxonomies for two domains: tourism and finance. We also directly compare our approach with hierarchical agglomerative clustering as well as with Bi-Section-KMeans as an instance of a divisive clustering algorithm. Furthermore, we investigate the impact of using different measures weighting the contribution of each attribute as well as of applying a particular smoothing technique to cope with data sparseness.},
journal = {J. Artif. Int. Res.},
month = aug,
pages = {305–339},
numpages = {35}
}

@article{10.5555/1622519.1622527,
author = {Bayer-Zubek, Valentina and Dietterich, Thomas G.},
title = {Integrating Learning from Examples into the Search for Diagnostic Policies},
year = {2005},
issue_date = {July 2005},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {24},
number = {1},
issn = {1076-9757},
abstract = {This paper studies the problem of learning diagnostic policies from training examples. A diagnostic policy is a complete description of the decision-making actions of a diagnostician (i.e., tests followed by a diagnostic decision) for all possible combinations of test results. An optimal diagnostic policy is one that minimizes the expected total cost, which is the sum of measurement costs and misdiagnosis costs. In most diagnostic settings, there is a tradeoff between these two kinds of costs.This paper formalizes diagnostic decision making as a Markov Decision Process (MDP). The paper introduces a new family of systematic search algorithms based on the AO* algorithm to solve this MDP. To make AO* efficient, the paper describes an admissible heuristic that enables AO* to prune large parts of the search space. The paper also introduces several greedy algorithms including some improvements over previously-published methods. The paper then addresses the question of learning diagnostic policies from examples. When the probabilities of diseases and test results are computed from training data, there is a great danger of overfitting. To reduce overfitting, regularizers are integrated into the search algorithms. Finally, the paper compares the proposed methods on five benchmark diagnostic data sets. The studies show that in most cases the systematic search methods produce better diagnostic policies than the greedy methods. In addition, the studies show that for training sets of realistic size, the systematic search algorithms are practical on today's desktop computers.},
journal = {J. Artif. Int. Res.},
month = aug,
pages = {263–303},
numpages = {41}
}

@article{10.5555/1622519.1622526,
author = {Watson, Jean-Paul and Whitley, L. Darrell and Howe, Adele E.},
title = {Linking Search Space Structure, Run-Time Dynamics, and Problem Difficulty: A Step toward Demystifying Tabu Search},
year = {2005},
issue_date = {July 2005},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {24},
number = {1},
issn = {1076-9757},
abstract = {Tabu search is one of the most effective heuristics for locating high-quality solutions to a diverse array of NP-hard combinatorial optimization problems. Despite the widespread success of tabu search, researchers have a poor understanding of many key theoretical aspects of this algorithm, including models of the high-level run-time dynamics and identification of those search space features that influence problem difficulty. We consider these questions in the context of the job-shop scheduling problem (JSP), a domain where tabu search algorithms have been shown to be remarkably effective. Previously, we demonstrated that the mean distance between random local optima and the nearest optimal solution is highly correlated with problem difficulty for a well-known tabu search algorithm for the JSP introduced by Taillard. In this paper, we discuss various shortcomings of this measure and develop a new model of problem difficulty that corrects these deficiencies. We show that Taillard's algorithm can be modeled with high fidelity as a simple variant of a straightforward random walk. The random walk model accounts for nearly all of the variability in the cost required to locate both optimal and sub-optimal solutions to random JSPs, and provides an explanation for differences in the difficulty of random versus structured JSPs. Finally, we discuss and empirically substantiate two novel predictions regarding tabu search algorithm behavior. First, the method for constructing the initial solution is highly unlikely to impact the performance of tabu search. Second, tabu tenure should be selected to be as small as possible while simultaneously avoiding search stagnation; values larger than necessary lead to significant degradations in performance.},
journal = {J. Artif. Int. Res.},
month = aug,
pages = {221–261},
numpages = {41}
}

@article{10.5555/1622519.1622525,
author = {Spaan, Matthijs T. J. and Vlassis, Nikos},
title = {Perseus: Randomized Point-Based Value Iteration for POMDPs},
year = {2005},
issue_date = {July 2005},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {24},
number = {1},
issn = {1076-9757},
abstract = {Partially observable Markov decision processes (POMDPs) form an attractive and principled framework for agent planning under uncertainty. Point-based approximate techniques for POMDPs compute a policy based on a finite set of points collected in advance from the agent's belief space. We present a randomized point-based value iteration algorithm called PERSEUS. The algorithm performs approximate value backup stages, ensuring that in each backup stage the value of each point in the belief set is improved; the key observation is that a single backup may improve the value of many belief points. Contrary to other point-based methods, PERSEUS backs up only a (randomly selected) subset of points in the belief set, sufficient for improving the value of each belief point in the set. We show how the same idea can be extended to dealing with continuous action spaces. Experimental results show the potential of PERSEUS in large scale POMDP problems.},
journal = {J. Artif. Int. Res.},
month = aug,
pages = {195–220},
numpages = {26}
}

@article{10.5555/1622519.1622524,
author = {Jordan, Pamela W. and Walker, Marilyn A.},
title = {Learning Content Selection Rules for Generating Object Descriptions in Dialogue},
year = {2005},
issue_date = {July 2005},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {24},
number = {1},
issn = {1076-9757},
abstract = {A fundamental requirement of any task-oriented dialogue system is the ability to generate object descriptions that refer to objects in the task domain. The subproblem of content selection for object descriptions in task-oriented dialogue has been the focus of much previous work and a large number of models have been proposed. In this paper, we use the annotated COCONUT corpus of task-oriented design dialogues to develop feature sets based on Dale and Reiter's (1995) incremental model, Brennan and Clark's (1996) conceptual pact model, and Jordan's (2000b) intentional influences model, and use these feature sets in a machine learning experiment to automatically learn a model of content selection for object descriptions. Since Dale and Reiter's model requires a representation of discourse structure, the corpus annotations are used to derive a representation based on Grosz and Sidner's (1986) theory of the intentional structure of discourse, as well as two very simple representations of discourse structure based purely on recency. We then apply the rule-induction program RIPPER to train and test the content selection component of an object description generator on a set of 393 object descriptions from the corpus. To our knowledge, this is the first reported experiment of a trainable content selection component for object description generation in dialogue. Three separate content selection models that are based on the three theoretical models, all independently achieve accuracies significantly above the MAJORITY CLASS baseline (17%) on unseen test data, with the intentional influences model (42.4%) performing significantly better than either the incremental model (30.4%) or the conceptual pact model (28.9%). But the best performing models combine all the feature sets, achieving accuracies near 60%. Surprisingly, a simple recency-based representation of discourse structure does as well as one based on intentional structure. To our knowledge, this is also the first empirical comparison of a representation of Grosz and Sidner's model of discourse structure with a simpler model for any generation task.},
journal = {J. Artif. Int. Res.},
month = jul,
pages = {157–194},
numpages = {38}
}

@article{10.5555/1622519.1622523,
author = {Hawkins, Peter and Lagoon, Vitaly and Stuckey, Peter J.},
title = {Solving Set Constraint Satisfaction Problems Using ROBDDs},
year = {2005},
issue_date = {July 2005},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {24},
number = {1},
issn = {1076-9757},
abstract = {In this paper we present a new approach to modeling finite set domain constraint problems using Reduced Ordered Binary Decision Diagrams (ROBDDs). We show that it is possible to construct an efficient set domain propagator which compactly represents many set domains and set constraints using ROBDDs. We demonstrate that the ROBDD-based approach provides unprecedented flexibility in modeling constraint satisfaction problems, leading to performance improvements. We also show that the ROBDD-based modeling approach can be extended to the modeling of integer and multiset constraint problems in a straightforward manner. Since domain propagation is not always practical, we also show how to incorporate less strict consistency notions into the ROBDD framework, such as set bounds, cardinality bounds and lexicographic bounds consistency. Finally, we present experimental results that demonstrate the ROBDD-based solver performs better than various more conventional constraint solvers on several standard set constraint problems.},
journal = {J. Artif. Int. Res.},
month = jul,
pages = {109–156},
numpages = {48}
}

@article{10.5555/1622519.1622522,
author = {Geibel, Peter and Wysotzki, Fritz},
title = {Risk-Sensitive Reinforcement Learning Applied to Control under Constraints},
year = {2005},
issue_date = {July 2005},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {24},
number = {1},
issn = {1076-9757},
abstract = {In this paper, we consider Markov Decision Processes (MDPs) with error states. Error states are those states entering which is undesirable or dangerous. We define the risk with respect to a policy as the probability of entering such a state when the policy is pursued. We consider the problem of finding good policies whose risk is smaller than some user-specified threshold, and formalize it as a constrained MDP with two criteria. The first criterion corresponds to the value function originally given. We will show that the risk can be formulated as a second criterion function based on a cumulative return, whose definition is independent of the original value function. We present a model free, heuristic reinforcement learning algorithm that aims at finding good deterministic policies. It is based on weighting the original value function and the risk. The weight parameter is adapted in order to find a feasible solution for the constrained problem that has a good performance with respect to the value function. The algorithm was successfully applied to the control of a feed tank with stochastic inflows that lies upstream of a distillation column. This control task was originally formulated as an optimal control problem with chance constraints, and it was solved under certain assumptions on the model to obtain an optimal solution. The power of our learning algorithm is that it can be used even when some of these restrictive assumptions are relaxed.},
journal = {J. Artif. Int. Res.},
month = jul,
pages = {81–108},
numpages = {28}
}

@article{10.5555/1622519.1622521,
author = {Gmytrasiewicz, Piotr J. and Doshi, Prashant},
title = {A Framework for Sequential Planning in Multi-Agent Settings},
year = {2005},
issue_date = {July 2005},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {24},
number = {1},
issn = {1076-9757},
abstract = {This paper extends the framework of partially observable Markov decision processes (POMDPs) to multi-agent settings by incorporating the notion of agent models into the state space. Agents maintain beliefs over physical states of the environment and over models of other agents, and they use Bayesian updates to maintain their beliefs over time. The solutions map belief states to actions. Models of other agents may include their belief states and are related to agent types considered in games of incomplete information. We express the agents' autonomy by postulating that their models are not directly manipulable or observable by other agents. We show that important properties of POMDPs, such as convergence of value iteration, the rate of convergence, and piece-wise linearity and convexity of the value functions carry over to our framework. Our approach complements a more traditional approach to interactive settings which uses Nash equilibria as a solution paradigm. We seek to avoid some of the drawbacks of equilibria which may be non-unique and do not capture off-equilibrium behaviors. We do so at the cost of having to represent, process and continuously revise models of other agents. Since the agent's beliefs may be arbitrarily nested, the optimal solutions to decision making problems are only asymptotically computable. However, approximate belief updates and approximately optimal plans are computable. We illustrate our framework using a simple application domain, and we show examples of belief updates and value functions.},
journal = {J. Artif. Int. Res.},
month = jul,
pages = {49–79},
numpages = {31}
}

@article{10.5555/1622519.1622520,
author = {Ortiz-Boyer, Domingo and Herv\'{a}Mart\'{\i}nez, C\'{e}sar and Garc\'{\i}a-Pedrajas, Nicol\'{a}s},
title = {CIXL2: A Crossover Operator for Evolutionary Algorithms Based on Population Features},
year = {2005},
issue_date = {July 2005},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {24},
number = {1},
issn = {1076-9757},
abstract = {In this paper we propose a crossover operator for evolutionary algorithms with real values that is based on the statistical theory of population distributions. The operator is based on the theoretical distribution of the values of the genes of the best individuals in the population. The proposed operator takes into account the localization and dispersion features of the best individuals of the population with the objective that these features would be inherited by the offspring. Our aim is the optimization of the balance between exploration and exploitation in the search process.In order to test the efficiency and robustness of this crossover, we have used a set of functions to be optimized with regard to different criteria, such as, multimodality, separability, regularity and epistasis. With this set of functions we can extract conclusions in function of the problem at hand. We analyze the results using ANOVA and multiple comparison statistical tests.As an example of how our crossover can be used to solve artificial intelligence problems, we have applied the proposed model to the problem of obtaining the weight of each network in a ensemble of neural networks. The results obtained are above the performance of standard methods.},
journal = {J. Artif. Int. Res.},
month = jul,
pages = {1–48},
numpages = {48}
}

@article{10.5555/1622503.1622518,
author = {Lutz, Carsten and Areces, Carlos and Horrocks, Ian and Sattler, Ulrike},
title = {Keys, Nominals, and Concrete Domains},
year = {2005},
issue_date = {January 2005},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {23},
number = {1},
issn = {1076-9757},
abstract = {Many description logics (DLs) combine knowledge representation on an abstract, logical level with an interface to "concrete" domains like numbers and strings with built-in predicates such as <, +, and prefix-of. These hybrid DLs have turned out to be useful in several application areas, such as reasoning about conceptual database models. We propose to further extend such DLs with key constraints that allow the expression of statements like "US citizens are uniquely identified by their social security number". Based on this idea, we introduce a number of natural description logics and perform a detailed analysis of their decidability and computational complexity. It turns out that naive extensions with key constraints easily lead to undecidability, whereas more careful extensions yield NExp-Time-complete DLs for a variety of useful concrete domains.},
journal = {J. Artif. Int. Res.},
month = jun,
pages = {667–726},
numpages = {60}
}

@article{10.5555/1622503.1622517,
author = {Barish, Greg and Knoblock, Craig A.},
title = {An Expressive Language and Efficient Execution System for Software Agents},
year = {2005},
issue_date = {January 2005},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {23},
number = {1},
issn = {1076-9757},
abstract = {Software agents can be used to automate many of the tedious, time-consuming information processing tasks that humans currently have to complete manually. However, to do so, agent plans must be capable of representing the myriad of actions and control flows required to perform those tasks. In addition, since these tasks can require integrating multiple sources of remote information -- typically, a slow, I/O-bound process -- it is desirable to make execution as efficient as possible. To address both of these needs, we present a flexible software agent plan language and a highly parallel execution system that enable the efficient execution of expressive agent plans. The plan language allows complex tasks to be more easily expressed by providing a variety of operators for flexibly processing the data as well as supporting subplans (for modularity) and recursion (for indeterminate looping). The executor is based on a streaming dataflow model of execution to maximize the amount of operator and data parallelism possible at runtime. We have implemented both the language and executor in a system called THESEUS. Our results from testing THESEUS show that streaming dataflow execution can yield significant speedups over both traditional serial (von Neumann) as well as nonstreaming dataflow-style execution that existing software and robot agent execution systems currently support. In addition, we show how plans written in the language we present can represent certain types of subtasks that cannot be accomplished using the languages supported by network query engines. Finally, we demonstrate that the increased expressivity of our plan language does not hamper performance; specifically, we show how data can be integrated from multiple remote sources just as efficiently using our architecture as is possible with a state-of-the-art streaming-dataflow network query engine.},
journal = {J. Artif. Int. Res.},
month = jun,
pages = {625–666},
numpages = {42}
}

@article{10.5555/1622503.1622516,
author = {Schroedl, Stefan},
title = {An Improved Search Algorithm for Optimal Multiple-Sequence Alignment},
year = {2005},
issue_date = {January 2005},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {23},
number = {1},
issn = {1076-9757},
abstract = {Multiple sequence alignment (MSA) is a ubiquitous problem in computational biology. Although it is NP-hard to find an optimal solution for an arbitrary number of sequences, due to the importance of this problem researchers are trying to push the limits of exact algorithms further. Since MSA can be cast as a classical path finding problem, it is attracting a growing number of AI researchers interested in heuristic search algorithms as a challenge with actual practical relevance.In this paper, we first review two previous, complementary lines of research. Based on Hirschberg's algorithm, Dynamic Programming needs O(kNk-1) space to store both the search frontier and the nodes needed to reconstruct the solution path, for k sequences of length N. Best first search, on the other hand, has the advantage of bounding the search space that has to be explored using a heuristic. However, it is necessary to maintain all explored nodes up to the final solution in order to prevent the search from re-expanding them at higher cost. Earlier approaches to reduce the Closed list are either incompatible with pruning methods for the Open list, or must retain at least the boundary of the Closed list.In this article, we present an algorithm that attempts at combining the respective advantages; like A* it uses a heuristic for pruning the search space, but reduces both the maximum Open and Closed size to O(kNk-1), as in Dynamic Programming. The underlying idea is to conduct a series of searches with successively increasing upper bounds, but using the DP ordering as the key for the Open priority queue. With a suitable choice of thresholds, in practice, a running time below four times that of A* can be expected.In our experiments we show that our algorithm outperforms one of the currently most successful algorithms for optimal multiple sequence alignments, Partial Expansion A*, both in time and memory. Moreover, we apply a refined heuristic based on optimal alignments not only of pairs of sequences, but of larger subsets. This idea is not new; however, to make it practically relevant we show that it is equally important to bound the heuristic computation appropriately, or the overhead can obliterate any possible gain.Furthermore, we discuss a number of improvements in time and space efficiency with regard to practical implementations.Our algorithm, used in conjunction with higher-dimensional heuristics, is able to calculate for the first time the optimal alignment for almost all of the problems in Reference 1 of the benchmark database BAliBASE.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {587–623},
numpages = {37}
}

@article{10.5555/1622503.1622515,
author = {Zimmerman, Terry and Kambhampati, Subbarao},
title = {Using Memory to Transform Search on the Planning Graph},
year = {2005},
issue_date = {January 2005},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {23},
number = {1},
issn = {1076-9757},
abstract = {The Graphplan algorithm for generating optimal make-span plans containing parallel sets of actions remains one of the most effective ways to generate such plans. However, despite enhancements on a range of fronts, the approach is currently dominated in terms of speed, by state space planners that employ distance-based heuristics to quickly generate serial plans. We report on a family of strategies that employ available memory to construct a search trace so as to learn from various aspects of Graphplan's iterative search episodes in order to expedite search in subsequent episodes. The planning approaches can be partitioned into two classes according to the type and extent of search experience captured in the trace. The planners using the more aggressive tracing method are able to avoid much of Graphplan's redundant search effort, while planners in the second class trade off this aspect in favor of a much higher degree of freedom than Graphplan in traversing the space of 'states' generated during regression search on the planning graph. The tactic favored by the second approach, exploiting the search trace to transform the depth-first, IDA* nature of Graphplan's search into an iterative state space view, is shown to be the more powerful. We demonstrate that distance-based, state space heuristics can be adapted to informed traversal of the search trace used by the second class of planners and develop an augmentation targeted specifically at planning graph search. Guided by such a heuristic, the step-optimal version of the planner in this class clearly dominates even a highly enhanced version of Graphplan. By adopting beam search on the search trace we then show that virtually optimal parallel plans can be generated at speeds quite competitive with a modern heuristic state space planner.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {533–585},
numpages = {53}
}

@article{10.5555/1622503.1622514,
author = {Dixon, Heidi E. and Ginsberg, Matthew L. and Hofer, David and Luks, Eugene M. and Parkes, Andrew J.},
title = {Generalizing Boolean Satisfiability III: Implementation},
year = {2005},
issue_date = {January 2005},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {23},
number = {1},
issn = {1076-9757},
abstract = {This is the third of three papers describing ZAP, a satisfiability engine that substantially generalizes existing tools while retaining the performance characteristics of modern high-performance solvers. The fundamental idea underlying ZAP is that many problems passed to such engines contain rich internal structure that is obscured by the Boolean representation used; our goal has been to define a representation in which this structure is apparent and can be exploited to improve computational performance. The first paper surveyed existing work that (knowingly or not) exploited problem structure to improve the performance of satisfiability engines, and the second paper showed that this structure could be understood in terms of groups of permutations acting on individual clauses in any particular Boolean theory. We conclude the series by discussing the techniques needed to implement our ideas, and by reporting on their performance on a variety of problem instances.},
journal = {J. Artif. Int. Res.},
month = apr,
pages = {441–531},
numpages = {91}
}

@article{10.5555/1622503.1622513,
author = {Larrosa, Javier and Morancho, Enric and Niso, David},
title = {On the Practical Use of Variable Elimination in Constraint Optimization Problems: 'still-Life' as a Case Study},
year = {2005},
issue_date = {January 2005},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {23},
number = {1},
issn = {1076-9757},
abstract = {Variable elimination is a general technique for constraint processing. It is often discarded because of its high space complexity. However, it can be extremely useful when combined with other techniques. In this paper we study the applicability of variable elimination to the challenging problem of finding still-lifes. We illustrate several alternatives: variable elimination as a stand-alone algorithm, interleaved with search, and as a source of good quality lower bounds. We show that these techniques are the best known option both theoretically and empirically. In our experiments we have been able to solve the n = 20 instance, which is far beyond reach with alternative approaches.},
journal = {J. Artif. Int. Res.},
month = apr,
pages = {421–440},
numpages = {20}
}

@article{10.5555/1622503.1622512,
author = {Nair, Ranjit and Tambe, Milind},
title = {Hybrid BDI-POMDP Framework for Multiagent Teaming},
year = {2005},
issue_date = {January 2005},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {23},
number = {1},
issn = {1076-9757},
abstract = {Many current large-scale multiagent team implementations can be characterized as following the "belief-desire-intention" (BDI) paradigm, with explicit representation of team plans. Despite their promise, current BDI team approaches lack tools for quantitative performance analysis under uncertainty. Distributed partially observable Markov decision problems (POMDPs) are well suited for such analysis, but the complexity of finding optimal policies in such models is highly intractable. The key contribution of this article is a hybrid BDI-POMDP approach, where BDI team plans are exploited to improve POMDP tractability and POMDP analysis improves BDI team plan performance.Concretely, we focus on role allocation, a fundamental problem in BDI teams: which agents to allocate to the different roles in the team. The article provides three key contributions. First, we describe a role allocation technique that takes into account future uncertainties in the domain; prior work in multiagent role allocation has failed to address such uncertainties. To that end, we introduce RMTDP (Role-based Markov Team Decision Problem), a new distributed POMDP model for analysis of role allocations. Our technique gains in tractability by significantly curtailing RMTDP policy search; in particular, BDI team plans provide incomplete RMTDP policies, and the RMTDP policy search fills the gaps in such incomplete policies by searching for the best role allocation. Our second key contribution is a novel decomposition technique to further improve RMTDP policy search efficiency. Even though limited to searching role allocations, there are still combinatorially many role allocations, and evaluating each in RMTDP to identify the best is extremely difficult. Our decomposition technique exploits the structure in the BDI team plans to significantly prune the search space of role allocations. Our third key contribution is a significantly faster policy evaluation algorithm suited for our BDI-POMDP hybrid approach. Finally, we also present experimental results from two domains: mission rehearsal simulation and RoboCupRescue disaster rescue simulation.},
journal = {J. Artif. Int. Res.},
month = apr,
pages = {367–420},
numpages = {54}
}

@article{10.5555/1622503.1622511,
author = {Chawla, Nitesh V. and Karakoulas, Grigoris},
title = {Learning from Labeled and Unlabeled Data: An Empirical Study across Techniques and Domains},
year = {2005},
issue_date = {January 2005},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {23},
number = {1},
issn = {1076-9757},
abstract = {There has been increased interest in devising learning techniques that combine unlabeled data with labeled data -- i.e. semi-supervised learning. However, to the best of our knowledge, no study has been performed across various techniques and different types and amounts of labeled and unlabeled data. Moreover, most of the published work on semi-supervised learning techniques assumes that the labeled and unlabeled data come from the same distribution. It is possible for the labeling process to be associated with a selection bias such that the distributions of data points in the labeled and unlabeled sets are different. Not correcting for such bias can result in biased function approximation with potentially poor performance. In this paper, we present an empirical study of various semi-supervised learning techniques on a variety of datasets. We attempt to answer various questions such as the effect of independence or relevance amongst features, the effect of the size of the labeled and unlabeled sets and the effect of noise. We also investigate the impact of sample-selection bias on the semi -supervised learning techniques under study and implement a bivariate probit technique particularly designed to correct for such bias.},
journal = {J. Artif. Int. Res.},
month = mar,
pages = {331–366},
numpages = {36}
}

@article{10.5555/1622503.1622510,
author = {Montoyo, Andres and Su\'{a}rez, Armando and Rigau, German and Palomar, Manuel},
title = {Combining Knowledge- and Corpus-Based Word-Sense-Disambiguation Methods},
year = {2005},
issue_date = {January 2005},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {23},
number = {1},
issn = {1076-9757},
abstract = {In this paper we concentrate on the resolution of the lexical ambiguity that arises when a given word has several different meanings. This specific task is commonly referred to as word sense disambiguation (WSD). The task of WSD consists of assigning the correct sense to words using an electronic dictionary as the source of word definitions. We present two WSD methods based on two main methodological approaches in this research area: a knowledge-based method and a corpus-based method. Our hypothesis is that word-sense disambiguation requires several knowledge sources in order to solve the semantic ambiguity of the words. These sources can be of different kinds-- for example, syntagmatic, paradigmatic or statistical information. Our approach combines various sources of knowledge, through combinations of the two WSD methods mentioned above. Mainly, the paper concentrates on how to combine these methods and sources of information in order to achieve good results in the disambiguation. Finally, this paper presents a comprehensive study and experimental work on evaluation of the methods and their combinations.},
journal = {J. Artif. Int. Res.},
month = mar,
pages = {299–330},
numpages = {32}
}

@article{10.5555/1622503.1622509,
author = {Cayrol, Claudette and Lagasquie-Schiex, Marie-Christine},
title = {Graduality in Argumentation},
year = {2005},
issue_date = {January 2005},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {23},
number = {1},
issn = {1076-9757},
abstract = {Argumentation is based on the exchange and valuation of interacting arguments, followed by the selection of the most acceptable of them (for example, in order to take a decision, to make a choice). Starting from the framework proposed by Dung in 1995, our purpose is to introduce "graduality" in the selection of the best arguments, i.e. to be able to partition the set of the arguments in more than the two usual subsets of "selected" and "non-selected" arguments in order to represent different levels of selection. Our basic idea is that an argument is all the more acceptable if it can be preferred to its attackers. First, we discuss general principles underlying a "gradual" valuation of arguments based on their interactions. Following these principles, we define several valuation models for an abstract argumentation system. Then, we introduce "graduality" in the concept of acceptability of arguments. We propose new acceptability classes and a refinement of existing classes taking advantage of an available "gradual" valuation.},
journal = {J. Artif. Int. Res.},
month = mar,
pages = {245–297},
numpages = {53}
}

@article{10.5555/1622503.1622508,
author = {Gabelaia, David and Kontchakov, Roman and Kurucz, Agi and Wolter, Frank and Zakharyaschev, Michael},
title = {Combining Spatial and Temporal Logics: Expressiveness vs. Complexity},
year = {2005},
issue_date = {January 2005},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {23},
number = {1},
issn = {1076-9757},
abstract = {In this paper, we construct and investigate a hierarchy of spatio-temporal formalisms that result from various combinations of propositional spatial and temporal logics such as the propositional temporal logic PT L, the spatial logics RCC-8, BRCC-8, S4u and their fragments. The obtained results give a clear picture of the trade-off between expressiveness and 'computational realisability' within the hierarchy. We demonstrate how different combining principles as well as spatial and temporal primitives can produce NP-, PSPACE-, EXPSPACE-, 2EXPSPACE-complete, and even undecidable spatio-temporal logics out of components that are at most NP- or PSPACE-complete.},
journal = {J. Artif. Int. Res.},
month = feb,
pages = {167–243},
numpages = {77}
}

@article{10.5555/1622503.1622507,
author = {Zhang, Weihong and Zhang, Nevin L.},
title = {Restricted Value Iteration: Theory and Algorithms},
year = {2005},
issue_date = {January 2005},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {23},
number = {1},
issn = {1076-9757},
abstract = {Value iteration is a popular algorithm for finding near optimal policies for POMDPs. It is ineffcient due to the need to account for the entire belief space, which necessitates the solution of large numbers of linear programs. In this paper, we study value iteration restricted to belief subsets. We show that, together with properly chosen belief subsets, restricted value iteration yields near-optimal policies and we give a condition for determining whether a given belief subset would bring about savings in space and time. We also apply restricted value iteration to two interesting classes of POMDPs, namely informative POMDPs and near-discernible POMDPs.},
journal = {J. Artif. Int. Res.},
month = feb,
pages = {123–165},
numpages = {43}
}

@article{10.5555/1622503.1622506,
author = {Porta, Josep M. and Celaya, Enric},
title = {Reinforcement Learning for Agents with Many Sensors and Actuators Acting in Categorizable Environments},
year = {2005},
issue_date = {January 2005},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {23},
number = {1},
issn = {1076-9757},
abstract = {In this paper, we confront the problem of applying reinforcement learning to agents that perceive the environment through many sensors and that can perform parallel actions using many actuators as is the case in complex autonomous robots. We argue that reinforcement learning can only be successfully applied to this case if strong assumptions are made on the characteristics of the environment in which the learning is performed, so that the relevant sensor readings and motor commands can be readily identified. The introduction of such assumptions leads to strongly-biased learning systems that can eventually lose the generality of traditional reinforcement-learning algorithms.In this line, we observe that, in realistic situations, the reward received by the robot depends only on a reduced subset of all the executed actions and that only a reduced subset of the sensor inputs (possibly different in each situation and for each action) are relevant to predict the reward. We formalize this property in the so called categorizability assumption and we present an algorithm that takes advantage of the categorizability of the environment, allowing a decrease in the learning time with respect to existing reinforcement-learning algorithms. Results of the application of the algorithm to a couple of simulated realistic-] robotic problems (landmark-based navigation and the six-legged robot gait generation) are reported to validate our approach and to compare it to existing flat and generalization-based reinforcement-learning approaches.},
journal = {J. Artif. Int. Res.},
month = feb,
pages = {79–122},
numpages = {44}
}

@article{10.5555/1622503.1622505,
author = {Dunne, Paul E.},
title = {Extremal Behaviour in Multiagent Contract Negotiation},
year = {2005},
issue_date = {January 2005},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {23},
number = {1},
issn = {1076-9757},
abstract = {We examine properties of a model of resource allocation in which several agents exchange resources in order to optimise their individual holdings. The schemes discussed relate to well-known negotiation protocols proposed in earlier work and we consider a number of alternative notions of "rationality" covering both quantitative measures, e.g. cooperative and individual rationality and more qualitative forms, e.g. Pigou-Dalton transfers. While it is known that imposing particular rationality and structural restrictions may result in some reallocations of the resource set becoming unrealisable, in this paper we address the issue of the number of restricted rational deals that may be required to implement a particular reallocation when it is possible to do so. We construct examples showing that this number may be exponential (in the number of resources m), even when all of the agent utility functions are monotonic. We further show that k agents may achieve in a single deal a reallocation requiring exponentially many rational deals if at most k - 1 agents can participate, this same reallocation being unrealisable by any sequences of rational deals in which at most k - 2 agents are involved.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {41–78},
numpages = {38}
}

@article{10.5555/1622503.1622504,
author = {Roy, Nicholas and Gordon, Geoffrey and Thrun, Sebastian},
title = {Finding Approximate POMDP Solutions through Belief Compression},
year = {2005},
issue_date = {January 2005},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {23},
number = {1},
issn = {1076-9757},
abstract = {Standard value function approaches to finding policies for Partially Observable Markov Decision Processes (POMDPs) are generally considered to be intractable for large models. The intractability of these algorithms is to a large extent a consequence of computing an exact, optimal policy over the entire belief space. However, in real-world POMDP problems, computing the optimal policy for the full belief space is often unnecessary for good control even for problems with complicated policy classes. The beliefs experienced by the controller often lie near a structured, low-dimensional subspace embedded in the high-dimensional belief space. Finding a good approximation to the optimal value function for only this subspace can be much easier than computing the full value function.We introduce a new method for solving large-scale POMDPs by reducing the dimensionality of the belief space. We use Exponential family Principal Components Analysis (Collins, Dasgupta, & Schapire, 2002) to represent sparse, high-dimensional belief spaces using small sets of learned features of the belief state. We then plan only in terms of the low-dimensional belief features. By planning in this low-dimensional space, we can find policies for POMDP models that are orders of magnitude larger than models that can be handled by conventional techniques.We demonstrate the use of this algorithm on a synthetic problem and on mobile robot navigation tasks.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {1–40},
numpages = {40}
}

@article{10.5555/1622487.1622502,
author = {Dixon, Heidi E. and Ginsberg, Matthew L. and Luks, Eugene M. and Parkes, Andrew J.},
title = {Generalizing Boolean Satisfiability II: Theory},
year = {2004},
issue_date = {July 2004},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {22},
number = {1},
issn = {1076-9757},
abstract = {This is the second of three planned papers describing ZAP, a satisfiability engine that substantially generalizes existing tools while retaining the performance characteristics of modern high performance solvers. The fundamental idea underlying ZAP is that many problems passed to such engines contain rich internal structure that is obscured by the Boolean representation used; our goal is to define a representation in which this structure is apparent and can easily be exploited to improve computational performance. This paper presents the theoretical basis for the ideas underlying ZAP, arguing that existing ideas in this area exploit a single, recurring structure in that multiple database axioms can be obtained by operating on a single axiom using a subgroup of the group of permutations on the literals in the problem. We argue that the group structure precisely captures the general structure at which earlier approaches hinted, and give numerous examples of its use. We go on to extend the Davis-Putnam-Logemann-Loveland inference procedure to this broader setting, and show that earlier computational improvements are either subsumed or left intact by the new method. The third paper in this series discusses ZAP's implementation and presents experimental performance results.},
journal = {J. Artif. Int. Res.},
month = dec,
pages = {481–534},
numpages = {54}
}

@article{10.5555/1622487.1622501,
author = {Erkan, G\"{u}nes and Radev, Dragomir R.},
title = {LexRank: Graph-Based Lexical Centrality as Salience in Text Summarization},
year = {2004},
issue_date = {July 2004},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {22},
number = {1},
issn = {1076-9757},
abstract = {We introduce a stochastic graph-based method for computing relative importance of textual units for Natural Language Processing. We test the technique on the problem of Text Summarization (TS). Extractive TS relies on the concept of sentence salience to identify the most important sentences in a document or set of documents. Salience is typically defined in terms of the presence of particular important words or in terms of similarity to a centroid pseudo-sentence. We consider a new approach, LexRank, for computing sentence importance based on the concept of eigenvector centrality in a graph representation of sentences. In this model, a connectivity matrix based on intra-sentence cosine similarity is used as the adjacency matrix of the graph representation of sentences. Our system, based on LexRank ranked in first place in more than one task in the recent DUC 2004 evaluation. In this paper we present a detailed analysis of our approach and apply it to a larger data set including data from earlier DUC evaluations. We discuss several methods to compute centrality using the similarity graph. The results show that degree-based methods (including LexRank) outperform both centroid-based methods and other systems participating in DUC in most of the cases. Furthermore, the LexRank with threshold method outperforms the other degree-based techniques including continuous LexRank. We also show that our approach is quite insensitive to the noise in the data that may result from an imperfect topical clustering of documents.},
journal = {J. Artif. Int. Res.},
month = dec,
pages = {457–479},
numpages = {23}
}

@article{10.5555/1622487.1622500,
author = {Becker, Raphen and Zilberstein, Shlomo and Lesser, Victor and Goldman, Claudia V.},
title = {Solving Transition Independent Decentralized Markov Decision Processes},
year = {2004},
issue_date = {July 2004},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {22},
number = {1},
issn = {1076-9757},
abstract = {Formal treatment of collaborative multi-agent systems has been lagging behind the rapid progress in sequential decision making by individual agents. Recent work in the area of decentralized Markov Decision Processes (MDPs) has contributed to closing this gap, but the computational complexity of these models remains a serious obstacle. To overcome this complexity barrier, we identify a specific class of decentralized MDPs in which the agents' transitions are independent. The class consists of independent collaborating agents that are tied together through a structured global reward function that depends on all of their histories of states and actions. We present a novel algorithm for solving this class of problems and examine its properties, both as an optimal algorithm and as an anytime algorithm. To the best of our knowledge, this is the first algorithm to optimally solve a non-trivial subclass of decentralized MDPs. It lays the foundation for further work in this area on both exact and approximate algorithms.},
journal = {J. Artif. Int. Res.},
month = dec,
pages = {423–455},
numpages = {33}
}

@article{10.5555/1622487.1622499,
author = {Begleiter, Ron and El-Yaniv, Ran and Yona, Golan},
title = {On Prediction Using Variable Order Markov Models},
year = {2004},
issue_date = {July 2004},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {22},
number = {1},
issn = {1076-9757},
abstract = {This paper is concerned with algorithms for prediction of discrete sequences over a finite alphabet, using variable order Markov models. The class of such algorithms is large and in principle includes any lossless compression algorithm. We focus on six prominent prediction algorithms, including Context Tree Weighting (CTW), Prediction by Partial Match (PPM) and Probabilistic Suffix Trees (PSTs). We discuss the properties of these algorithms and compare their performance using real life sequences from three domains: proteins, English text and music pieces. The comparison is made with respect to prediction quality as measured by the average log-loss. We also compare classification algorithms based on these predictors with respect to a number of large protein classification tasks. Our results indicate that a "decomposed" CTW (a variant of the CTW algorithm) and PPM outperform all other algorithms in sequence prediction tasks. Somewhat surprisingly, a different algorithm, which is a modification of the Lempel-Ziv compression algorithm, significantly outperforms all algorithms on the protein classification problems.},
journal = {J. Artif. Int. Res.},
month = dec,
pages = {385–421},
numpages = {37}
}

@article{10.5555/1622487.1622498,
author = {Bowling, Michael and Veloso, Manuela},
title = {Existence of Multiagent Equilibria with Limited Agents},
year = {2004},
issue_date = {July 2004},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {22},
number = {1},
issn = {1076-9757},
abstract = {Multiagent learning is a necessary yet challenging problem as multiagent systems become more prevalent and environments become more dynamic. Much of the groundbreaking work in this area draws on notable results from game theory, in particular, the concept of Nash equilibria. Learners that directly learn an equilibrium obviously rely on their existence. Learners that instead seek to play optimally with respect to the other players also depend upon equilibria since equilibria are fixed points for learning. From another perspective, agents with limitations are real and common. These may be undesired physical limitations as well as self-imposed rational limitations, such as abstraction and approximation techniques, used to make learning tractable. This article explores the interactions of these two important concepts: equilibria and limitations in learning. We introduce the question of whether equilibria continue to exist when agents have limitations. We look at the general effects limitations can have on agent behavior, and define a natural extension of equilibria that accounts for these limitations. Using this formalization, we make three major contributions: (i) a counterexample for the general existence of equilibria with limitations, (ii) sufficient conditions on limitations that preserve their existence, (iii) three general classes of games and limitations that satisfy these conditions. We then present empirical results from a specific multiagent learning algorithm applied to a specific instance of limited agents. These results demonstrate that learning with limitations is feasible, when the conditions outlined by our theoretical analysis hold.},
journal = {J. Artif. Int. Res.},
month = dec,
pages = {353–384},
numpages = {32}
}

@article{10.5555/1622487.1622497,
author = {Beame, Paul and Kautz, Henry and Sabharwal, Ashish},
title = {Towards Understanding and Harnessing the Potential of Clause Learning},
year = {2004},
issue_date = {July 2004},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {22},
number = {1},
issn = {1076-9757},
abstract = {Effcient implementations of DPLL with the addition of clause learning are the fastest complete Boolean satisfiability solvers and can handle many significant real-world problems, such as verification, planning and design. Despite its importance, little is known of the ultimate strengths and limitations of the technique. This paper presents the first precise characterization of clause learning as a proof system (CL), and begins the task of understanding its power by relating it to the well-studied resolution proof system. In particular, we show that with a new learning scheme, CL can provide exponentially shorter proofs than many proper refinements of general resolution (RES) satisfying a natural property. These include regular and Davis-Putnam resolution, which are already known to be much stronger than ordinary DPLL. We also show that a slight variant of CL with unlimited restarts is as powerful as RES itself. Translating these analytical results to practice, however, presents a challenge because of the nondeterministic nature of clause learning algorithms. We propose a novel way of exploiting the underlying problem structure, in the form of a high level problem description such as a graph or PDDL specification, to guide clause learning algorithms toward faster solutions. We show that this leads to exponential speed-ups on grid and randomized pebbling problems, as well as substantial improvements on certain ordering formulas.},
journal = {J. Artif. Int. Res.},
month = dec,
pages = {319–351},
numpages = {33}
}

@article{10.5555/1622487.1622496,
author = {Felner, Ariel and Korf, Richard E. and Hanan, Sarit},
title = {Additive Pattern Database Heuristics},
year = {2004},
issue_date = {July 2004},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {22},
number = {1},
issn = {1076-9757},
abstract = {We explore a method for computing admissible heuristic evaluation functions for search problems. It utilizes pattern databases (Culberson & Schaeffer, 1998), which are precomputed tables of the exact cost of solving various subproblems of an existing problem. Unlike standard pattern database heuristics, however, we partition our problems into disjoint sub-problems, so that the costs of solving the different subproblems can be added together without overestimating the cost of solving the original problem. Previously (Korf & Felner, 2002) we showed how to statically partition the sliding-tile puzzles into disjoint groups of tiles to compute an admissible heuristic, using the same partition for each state and problem instance. Here we extend the method and show that it applies to other domains as well. We also present another method for additive heuristics which we call dynamically partitioned pattern databases. Here we partition the problem into disjoint subproblems for each state of the search dynamically. We discuss the pros and cons of each of these methods and apply both methods to three different problem domains: the sliding-tile puzzles, the 4-peg Towers of Hanoi problem, and finding an optimal vertex cover of a graph. We find that in some problem domains, static partitioning is most effective. while in others dynamic partitioning is a better choice. In each of these problem domains, either statically partitioned or dynamically partitioned pattern database heuristics are the best known heuristics for the problem.},
journal = {J. Artif. Int. Res.},
month = nov,
pages = {279–318},
numpages = {40}
}

@article{10.5555/1622487.1622495,
author = {Hoffmann, J\"{o}rg and Porteous, Julie and Sebastia, Laura},
title = {Ordered Landmarks in Planning},
year = {2004},
issue_date = {July 2004},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {22},
number = {1},
issn = {1076-9757},
abstract = {Many known planning tasks have inherent constraints concerning the best order in which to achieve the goals. A number of research efiorts have been made to detect such constraints and to use them for guiding search, in the hope of speeding up the planning process.We go beyond the previous approaches by considering ordering constraints not only over the (top-level) goals, but also over the sub-goals that will necessarily arise during planning. Landmarks are facts that must be true at some point in every valid solution plan. We extend Koehler and Hoffmann's definition of reasonable orders between top level goals to the more general case of landmarks. We show how landmarks can be found, how their reasonable orders can be approximated, and how this information can be used to decompose a given planning task into several smaller sub-tasks. Our methodology is completely domain- and planner-independent. The implementation demonstrates that the approach can yield significant runtime performance improvements when used as a control loop around state-of-the-art sub-optimal planning systems, as exemplified by FF and LPG.},
journal = {J. Artif. Int. Res.},
month = nov,
pages = {215–278},
numpages = {64}
}

@article{10.5555/1622487.1622494,
author = {Park, Sunju and Durfee, Edmund H. and Birmingham, William P.},
title = {Use of Markov Chains to Design an Agent Bidding Strategy for Continuous Double Auctions},
year = {2004},
issue_date = {July 2004},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {22},
number = {1},
issn = {1076-9757},
abstract = {As computational agents are developed for increasingly complicated e-commerce applications, the complexity of the decisions they face demands advances in artificial intelligence techniques. For example, an agent representing a seller in an auction should try to maximize the seller's profit by reasoning about a variety of possibly uncertain pieces of information, such as the maximum prices various buyers might be willing to pay, the possible prices being offered by competing sellers, the rules by which the auction operates, the dynamic arrival and matching of offers to buy and sell, and so on. A na\"{\i}ve application of multiagent reasoning techniques would require the seller's agent to explicitly model all of the other agents through an extended time horizon, rendering the problem intractable for many realistically-sized problems. We have instead devised a new strategy that an agent can use to determine its bid price based on a more tractable Markov chain model

license_type: permissive

branch_name: refs/heads/main

extension: bib