text:
{In this paper, we present algorithms that perform gradient ascent of the average reward in a partially observable Markov decision process (POMDP). These algorithms are based on GPOMDP, an algorithm introduced in a companion paper (Baxter & Bartlett, 2001), which computes biased estimates of the performance gradient in POMDPs. The algorithm's chief advantages are that it uses only one free parameter β ∈ [0, 1], which has a natural interpretation in terms of bias-variance trade-off, it requires no knowledge of the underlying state, and it can be applied to infinite state, control and observation spaces. We show how the gradient estimates produced by GPOMDP can be used to perform gradient ascent, both with a traditional stochastic-gradient algorithm, and with an algorithm based on conjugate-gradients that utilizes gradient information to bracket maxima in line searches. Experimental results are presented illustrating both the theoretical results of Baxter and Bartlett (2001) on a toy problem, and practical aspects of the algorithms on a number of more realistic problems.},
journal = {J. Artif. Int. Res.},
month = nov,
pages = {351–381},
numpages = {31}
}

@article{10.5555/1622845.1622855,
author = {Baxter, Jonathan and Bartlett, Peter L.},
title = {Infinite-Horizon Policy-Gradient Estimation},
year = {2001},
issue_date = {July 2001},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {15},
number = {1},
issn = {1076-9757},
abstract = {Gradient-based approaches to direct policy search in reinforcement learning have received much recent attention as a means to solve problems of partial observability and to avoid some of the problems associated with policy degradation in value-function methods. In this paper we introduce GPOMDP, a simulation-based algorithm for generating a biased estimate of the gradient of the average reward in Partially Observable Markov Decision Processes (POMDPs) controlled by parameterized stochastic policies. A similar algorithm was proposed by Kimura, Yamamura, and Kobayashi (1995). The algorithm's chief advantages are that it requires storage of only twice the number of policy parameters, uses one free parameter β ∈ [0, 1] (which has a natural interpretation in terms of bias-variance trade-off), and requires no knowledge of the underlying state. We prove convergence of GPOMDP, and show how the correct choice of the parameter β is related to the mixing time of the controlled POMDP. We briefly describe extensions of GPOMDP to controlled Markov chains, continuous state, observation and control spaces, multiple-agents, higher-order derivatives, and a version for training stochastic policies with internal states. In a companion paper (Baxter, Bartlett, & Weaver, 2001) we show how the gradient estimates generated by GPOMDP can be used in both a traditional stochastic gradient algorithm and a conjugate-gradient procedure to find local optima of the average reward.},
journal = {J. Artif. Int. Res.},
month = nov,
pages = {319–350},
numpages = {32}
}

@article{10.5555/1622845.1622854,
author = {Renz, Jochen and Nebel, Bernhard},
title = {Efficient Methods for Qualitative Spatial Reasoning},
year = {2001},
issue_date = {July 2001},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {15},
number = {1},
issn = {1076-9757},
abstract = {The theoretical properties of qualitative spatial reasoning in the RCC-8 framework have been analyzed extensively. However, no empirical investigation has been made yet. Our experiments show that the adaption of the algorithms used for qualitative temporal reasoning can solve large RCC-8 instances, even if they are in the phase transition region - provided that one uses the maximal tractable subsets of RCC-8 that have been identified by us. In particular, we demonstrate that the orthogonal combination of heuristic methods is successful in solving almost all apparently hard instances in the phase transition region up to a certain size in reasonable time.},
journal = {J. Artif. Int. Res.},
month = oct,
pages = {289–318},
numpages = {30}
}

@article{10.5555/1622845.1622853,
author = {Palomar, Manuel and Mart\'{\i}nez-Barco, Patricio},
title = {Computational Approach to Anaphora Resolution in Spanish Dialogues},
year = {2001},
issue_date = {July 2001},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {15},
number = {1},
issn = {1076-9757},
abstract = {This paper presents an algorithm for identifying noun-phrase antecedents of pronouns and adjectival anaphors in Spanish dialogues. We believe that anaphora resolution requires numerous sources of information in order to find the correct antecedent of the anaphor. These sources can be of different kinds, e.g., linguistic information, discourse/dialogue structure information, or topic information. For this reason, our algorithm uses various different kinds of information (hybrid information). The algorithm is based on linguistic constraints and preferences and uses an anaphoric accessibility space within which the algorithm finds the noun phrase. We present some experiments related to this algorithm and this space using a corpus of 204 dialogues. The algorithm is implemented in Prolog. According to this study, 95.9% of antecedents were located in the proposed space, a precision of 81.3% was obtained for pronominal anaphora resolution, and 81.5% for adjectival anaphora.},
journal = {J. Artif. Int. Res.},
month = oct,
pages = {263–287},
numpages = {25}
}

@article{10.5555/1622845.1622852,
author = {Ambite, Jos\'{e} Luis and Knoblock, Craig A.},
title = {Planning by Rewriting},
year = {2001},
issue_date = {July 2001},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {15},
number = {1},
issn = {1076-9757},
abstract = {Domain-independent planning is a hard combinatorial problem. Taking into account plan quality makes the task even more dificult. This article introduces Planning by Rewriting (PbR), a new paradigm for efficient high-quality domain-independent planning. PbR exploits declarative plan-rewriting rules and efficient local search techniques to transform an easy-to-generate, but possibly suboptimal, initial plan into a high-quality plan. In addition to addressing the issues of planning efficiency and plan quality, this framework offers a new anytime planning algorithm. We have implemented this planner and applied it to several existing domains. The experimental results show that the PbR approach provides significant savings in planning effort while generating high-quality plans.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {207–261},
numpages = {55}
}

@article{10.5555/1622845.1622851,
author = {Stone, Peter and Littman, Michael L. and Singh, Satinder and Kearns, Michael},
title = {ATTac-2000: An Adaptive Autonomous Bidding Agent},
year = {2001},
issue_date = {July 2001},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {15},
number = {1},
issn = {1076-9757},
abstract = {The First Trading Agent Competition (TAC) was held from June 22nd to July 8th, 2000. TAC was designed to create a benchmark problem in the complex domain of e-marketplaces and to motivate researchers to apply unique approaches to a common task. This article describes ATTac-2000, the first-place finisher in TAC. ATTac-2000 uses a principled bidding strategy that includes several elements of adaptivity. In addition to the success at the competition, isolated empirical results are presented indicating the robustness and effectiveness of ATTac-2000's adaptive strategy.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {189–206},
numpages = {18}
}

@article{10.5555/1622845.1622850,
author = {Elomaa, Tapio and K\"{a}\"{a}ri\"{a}inen, Matti},
title = {An Analysis of Reduced Error Pruning},
year = {2001},
issue_date = {July 2001},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {15},
number = {1},
issn = {1076-9757},
abstract = {Top-down induction of decision trees has been observed to suffer from the inadequate functioning of the pruning phase. In particular, it is known that the size of the resulting tree grows linearly with the sample size, even though the accuracy of the tree does not improve. Reduced Error Pruning is an algorithm that has been used as a representative technique in attempts to explain the problems of decision tree learning.In this paper we present analyses of Reduced Error Pruning in three different settings. First we study the basic algorithmic properties of the method, properties that hold independent of the input decision tree and pruning examples. Then we examine a situation that intuitively should lead to the subtree under consideration to be replaced by a leaf node, one in which the class label and attribute values of the pruning examples are independent of each other. This analysis is conducted under two different assumptions. The general analysis shows that the pruning probability of a node fitting pure noise is bounded by a function that decreases exponentially as the size of the tree grows. In a specific analysis we assume that the examples are distributed uniformly to the tree. This assumption lets us approximate the number of subtrees that are pruned because they do not receive any pruning examples.This paper clarifies the different variants of the Reduced Error Pruning algorithm, brings new insight to its algorithmic properties, analyses the algorithm with less imposed assumptions than before, and includes the previously overlooked empty subtrees to the analysis.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {163–187},
numpages = {25}
}

@article{10.5555/1622845.1622849,
author = {Refanidis, Ioannis and Vlahavas, Ioannis},
title = {The GRT Planning System: Backward Heuristic Construction in Forward State-Space Planning},
year = {2001},
issue_date = {July 2001},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {15},
number = {1},
issn = {1076-9757},
abstract = {This paper presents GRT, a domain-independent heuristic planning system for STRIPS worlds. GRT solves problems in two phases. In the pre-processing phase, it estimates the distance between each fact and the goals of the problem, in a backward direction. Then, in the search phase, these estimates are used in order to further estimate the distance between each intermediate state and the goals, guiding so the search process in a forward direction and on a best-first basis. The paper presents the benefits from the adoption of opposite directions between the preprocessing and the search phases, discusses some difficulties that arise in the pre-processing phase and introduces techniques to cope with them. Moreover, it presents several methods of improving the efficiency of the heuristic, by enriching the representation and by reducing the size of the problem. Finally, a method of overcoming local optimal states, based on domain axioms, is proposed. According to it, difficult problems are decomposed into easier sub-problems that have to be solved sequentially. The performance results from various domains, including those of the recent planning competitions, show that GRT is among the fastest planners.},
journal = {J. Artif. Int. Res.},
month = aug,
pages = {115–161},
numpages = {47}
}

@article{10.5555/1622845.1622848,
author = {Bhattacharyya, Chiranjib and Keerthi, S. Sathiya},
title = {Mean-Field Methods for a Special Class of Belief Networks},
year = {2001},
issue_date = {July 2001},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {15},
number = {1},
issn = {1076-9757},
abstract = {The chief aim of this paper is to propose mean-field approximations for a broad class of Belief networks, of which sigmoid and noisy-or networks can be seen as special cases. The approximations are based on a powerful mean-field theory suggested by Plefka. We show that Saul, Jaakkola, and Jordan's approach is the first order approximation in Plefka's approach, via a variational derivation. The application of Plefka's theory to belief networks is not computationally tractable. To tackle this problem we propose new approximations based on Taylor series. Small scale experiments show that the proposed schemes are attractive.},
journal = {J. Artif. Int. Res.},
month = aug,
pages = {91–114},
numpages = {24}
}

@article{10.5555/1622845.1622846,
author = {Hong, Jun},
title = {Goal Recognition through Goal Graph Analysis},
year = {2001},
issue_date = {July 2001},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {15},
number = {1},
issn = {1076-9757},
abstract = {We present a novel approach to goal recognition based on a two-stage paradigm of graph construction and analysis. First, a graph structure called a Goal Graph is constructed to represent the observed actions, the state of the world, and the achieved goals as well as various connections between these nodes at consecutive time steps. Then, the Goal Graph is analysed at each time step to recognise those partially or fully achieved goals that are consistent with the actions observed so far. The Goal Graph analysis also reveals valid plans for the recognised goals or part of these goals.Our approach to goal recognition does not need a plan library. It does not suffer from the problems in the acquisition and hand-coding of large plan libraries, neither does it have the problems in searching the plan space of exponential size. We describe two algorithms for Goal Graph construction and analysis in this paradigm. These algorithms are both provably sound, polynomial-time, and polynomial-space. The number of goals recognised by our algorithms is usually very small after a sequence of observed actions has been processed. Thus the sequence of observed actions is well explained by the recognised goals with little ambiguity. We have evaluated these algorithms in the UNIX domain, in which excellent performance has been achieved in terms of accuracy, efficiency, and scalability.},
journal = {J. Artif. Int. Res.},
month = jul,
pages = {1–30},
numpages = {30}
}

@article{10.5555/1622394.1622406,
author = {Halpern, Joseph Y.},
title = {Conditional Plausibility Measures and Bayesian Networks},
year = {2001},
issue_date = {January 2001},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {14},
number = {1},
issn = {1076-9757},
abstract = {A general notion of algebraic conditional plausibility measures is defined. Probability measures, ranking functions, possibility measures, and (under the appropriate definitions) sets of probability measures can all be viewed as defining algebraic conditional plausibility measures. It is shown that algebraic conditional plausibility measures can be represented using Bayesian networks.},
journal = {J. Artif. Int. Res.},
month = jun,
pages = {359–389},
numpages = {31}
}

@article{10.5555/1622394.1622405,
author = {Ginsberg, Matthew L.},
title = {GIB: Imperfect Information in a Computationally Challenging Game},
year = {2001},
issue_date = {January 2001},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {14},
number = {1},
issn = {1076-9757},
abstract = {This paper investigates the problems arising in the construction of a program to play the game of contract bridge. These problems include both the difficulty of solving the game's perfect information variant, and techniques needed to address the fact that bridge is not, in fact, a perfect information game. GIB, the program being described, involves five separate technical advances: partition search, the practical application of Monte Carlo techniques to realistic problems, a focus on achievable sets to solve problems inherent in the Monte Carlo approach, an extension of alpha-beta pruning from total orders to arbitrary distributive lattices, and the use of squeaky wheel optimization to find approximately optimal solutions to cardplay problems.GIB is currently believed to be of approximately expert caliber, and is currently the strongest computer bridge program in the world.},
journal = {J. Artif. Int. Res.},
month = jun,
pages = {303–358},
numpages = {56}
}

@article{10.5555/1622394.1622404,
author = {Hoffmann, J\"{o}rg and Nebel, Bernhard},
title = {The FF Planning System: Fast Plan Generation through Heuristic Search},
year = {2001},
issue_date = {January 2001},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {14},
number = {1},
issn = {1076-9757},
abstract = {We describe and evaluate the algorithmic techniques that are used in the FF planning system. Like the HSP system, FF relies on forward state space search, using a heuristic that estimates goal distances by ignoring delete lists. Unlike HSP's heuristic, our method does not assume facts to be independent. We introduce a novel search strategy that combines hill-climbing with systematic search, and we show how other powerful heuristic information can be extracted and used to prune the search space. FF was the most successful automatic planner at the recent AIPS-2000 planning competition. We review the results of the competition, give data for other benchmark domains, and investigate the reasons for the runtime performance of FF compared to HSP.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {253–302},
numpages = {50}
}

@article{10.5555/1622394.1622403,
author = {Basu, Chumki and Hirsh, Haym and Cohen, William W. and Nevill-Manning, Craig},
title = {Technical Paper Recommendation: A Study in Combining Multiple Information Sources},
year = {2001},
issue_date = {January 2001},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {14},
number = {1},
issn = {1076-9757},
abstract = {The growing need to manage and exploit the proliferation of online data sources is opening up new opportunities for bringing people closer to the resources they need. For instance, consider a recommendation service through which researchers can receive daily pointers to journal papers in their fields of interest. We survey some of the known approaches to the problem of technical paper recommendation and ask how they can be extended to deal with multiple information sources. More specifically, we focus on a variant of this problem - recommending conference paper submissions to reviewing committee members - which offers us a testbed to try different approaches. Using WHIRL - an information integration system - we are able to implement different recommendation algorithms derived from information retrieval principles. We also use a novel autonomous procedure for gathering reviewer interest information from the Web. We evaluate our approach and compare it to other methods using preference data provided by members of the AAAI-98 conference reviewing committee along with data about the actual submissions.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {231–252},
numpages = {22}
}

@article{10.5555/1622394.1622402,
author = {Debruyne, Romuald and Bessi\'{e}re, Christian},
title = {Domain Filtering Consistencies},
year = {2001},
issue_date = {January 2001},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {14},
number = {1},
issn = {1076-9757},
abstract = {Enforcing local consistencies is one of the main features of constraint reasoning. Which level of local consistency should be used when searching for solutions in a constraint network is a basic question. Arc consistency and partial forms of arc consistency have been widely studied, and have been known for sometime through the forward checking or the MAC search algorithms. Until recently, stronger forms of local consistency remained limited to those that change the structure of the constraint graph, and thus, could not be used in practice, especially on large networks. This paper focuses on the local consistencies that are stronger than arc consistency, without changing the structure of the network, i.e., only removing inconsistent values from the domains. In the last five years, several such local consistencies have been proposed by us or by others. We make an overview of all of them, and highlight some relations between them. We compare them both theoretically and experimentally, considering their pruning efficiency and the time required to enforce them.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {205–230},
numpages = {26}
}

@article{10.5555/1622394.1622401,
author = {K\"{u}sters, Ralf and Borgida, Alex},
title = {What's in an Attribute? Consequences for the Least Common Subsumer},
year = {2001},
issue_date = {January 2001},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {14},
number = {1},
issn = {1076-9757},
abstract = {Functional relationships between objects, called "attributes", are of considerable importance in knowledge representation languages, including Description Logics (DLs). A study of the literature indicates that papers have made, often implicitly, different assumptions about the nature of attributes: whether they are always required to have a value, or whether they can be partial functions. The work presented here is the first explicit study of this difference for subclasses of the CLASSIC DL, involving the same-as concept constructor. It is shown that although determining subsumption between concept descriptions has the same complexity (though requiring different algorithms), the story is different in the case of determining the least common subsumer (lcs). For attributes interpreted as partial functions, the lcs exists and can be computed relatively easily; even in this case our results correct and extend three previous papers about the lcs of DLs. In the case where attributes must have a value, the lcs may not exist, and even if it exists it may be of exponential size. Interestingly, it is possible to decide in polynomial time if the lcs exists.},
journal = {J. Artif. Int. Res.},
month = apr,
pages = {167–203},
numpages = {37}
}

@article{10.5555/1622394.1622400,
author = {Straccia, Umberto},
title = {Reasoning within Fuzzy Description Logics},
year = {2001},
issue_date = {January 2001},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {14},
number = {1},
issn = {1076-9757},
abstract = {Description Logics (DLs) are suitable, well-known, logics for managing structured knowledge. They allow reasoning about individuals and well defined concepts, i.e. set of individuals with common properties. The experience in using DLs in applications has shown that in many cases we would like to extend their capabilities. In particular, their use in the context of Multimedia Information Retrieval (MIR) leads to the convincement that such DLs should allow the treatment of the inherent imprecision in multimedia object content representation and retrieval.In this paper we will present a fuzzy extension of ALC, combining Zadeh's fuzzy logic with a classical DL. In particular, concepts becomes fuzzy and, thus, reasoning about imprecise concepts is supported. We will define its syntax, its semantics, describe its properties and present a constraint propagation calculus for reasoning in it.},
journal = {J. Artif. Int. Res.},
month = apr,
pages = {137–166},
numpages = {30}
}

@article{10.5555/1622394.1622399,
author = {Boutilier, Craig and Brafman, Ronen I.},
title = {Partial-Order Planning with Concurrent Interacting Actions},
year = {2001},
issue_date = {January 2001},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {14},
number = {1},
issn = {1076-9757},
abstract = {In order to generate plans for agents with multiple actuators, agent teams, or distributed controllers, we must be able to represent and plan using concurrent actions with interacting effects. This has historically been considered a challenging task requiring a temporal planner with the ability to reason explicitly about time. We show that with simple modifications, the STRIPS action representation language can be used to represent interacting actions. Moreover, algorithms for partial-order planning require only small modifications in order to be applied in such multiagent domains. We demonstrate this fact by developing a sound and complete partial-order planner for planning with concurrent interacting actions, POMP, that extends existing partial-order planners in a straightforward way. These results open the way to the use of partial-order planners for the centralized control of cooperative multiagent systems.},
journal = {J. Artif. Int. Res.},
month = apr,
pages = {105–136},
numpages = {32}
}

@article{10.5555/1622394.1622398,
author = {Lusena, Christopher and Goldsmith, Judy and Mundhenk, Martin},
title = {Nonapproximability Results for Partially Observable Markov Decision Processes},
year = {2001},
issue_date = {January 2001},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {14},
number = {1},
issn = {1076-9757},
abstract = {We show that for several variations of partially observable Markov decision processes, polynomial-time algorithms for finding control policies are unlikely to or simply don't have guarantees of finding policies within a constant factor or a constant summand of optimal. Here "unlikely" means "unless some complexity classes collapse," where the collapses considered are P = NP, P = PSPACE, or P = EXP. Until or unless these collapses are shown to hold, any control-policy designer must choose between such performance guarantees and efficient computation.},
journal = {J. Artif. Int. Res.},
month = mar,
pages = {83–103},
numpages = {21}
}

@article{10.5555/1622394.1622397,
author = {Chen, Xinguang and van Beek, Peter},
title = {Conflict-Directed Backjumping Revisited},
year = {2001},
issue_date = {January 2001},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {14},
number = {1},
issn = {1076-9757},
abstract = {In recent years, many improvements to backtracking algorithms for solving constraint satisfaction problems have been proposed. The techniques for improving backtracking algorithms can be conveniently classified as look-ahead schemes and look-back schemes. Unfortunately, look-ahead and look-back schemes are not entirely orthogonal as it has been observed empirically that the enhancement of look-ahead techniques is sometimes counterproductive to the effects of look-back techniques. In this paper, we focus on the relationship between the two most important look-ahead techniques--using a variable ordering heuristic and maintaining a level of local consistency during the backtracking search--and the look-back technique of conflict-directed backjumping (CBJ). We show that there exists a "perfect" dynamic variable ordering such that CBJ becomes redundant. We also show theoretically that as the level of local consistency that is maintained in the backtracking search is increased, the less that backjumping will be an improvement. Our theoretical results partially explain why a backtracking algorithm doing more in the look-ahead phase cannot benefit more from the backjumping look-back scheme. Finally, we show empirically that adding CBJ to a backtracking algorithm that maintains generalized arc consistency (GAC), an algorithm that we refer to as GAC-CBJ, can still provide orders of magnitude speedups. Our empirical results contrast with Bessi\`{e}re and R\'{e}gin's conclusion (1996) that CBJ is useless to an algorithm that maintains arc consistency.},
journal = {J. Artif. Int. Res.},
month = mar,
pages = {53–81},
numpages = {29}
}

@article{10.5555/1622394.1622396,
author = {Zhang, Nevin L. and Zhang, Weihong},
title = {Speeding up the Convergence of Value Iteration in Partially Observable Markov Decision Processes},
year = {2001},
issue_date = {January 2001},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {14},
number = {1},
issn = {1076-9757},
abstract = {Partially observable Markov decision processes (POMDPs) have recently become popular among many AI researchers because they serve as a natural model for planning under uncertainty. Value iteration is a well-known algorithm for finding optimal policies for POMDPs. It typically takes a large number of iterations to converge. This paper proposes a method for accelerating the convergence of value iteration. The method has been evaluated on an array of benchmark problems and was found to be very effective: It enabled value iteration to converge after only a few iterations on all the test problems.},
journal = {J. Artif. Int. Res.},
month = feb,
pages = {29–51},
numpages = {23}
}

@article{10.5555/1622394.1622395,
author = {Brafman, Ronen I.},
title = {On Reachability, Relevance, and Resolution in the Planning as Satisfiability Approach},
year = {2001},
issue_date = {January 2001},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {14},
number = {1},
issn = {1076-9757},
abstract = {In recent years, there is a growing awareness of the importance of reachability and relevance-based pruning techniques for planning, but little work specifically targets these techniques. In this paper, we compare the ability of two classes of algorithms to propagate and discover reachability and relevance constraints in classical planning problems. The first class of algorithms operates on SAT encoded planning problems obtained using the linear and GRAPHPLAN encoding schemes. It applies unit-propagation and more general resolution steps (involving larger clauses) to these plan encodings. The second class operates at the plan level and contains two families of pruning algorithms: Reachable-k and Relevant-k . Reachable-k provides a coherent description of a number of existing forward pruning techniques used in numerous algorithms, while Relevant-k captures different grades of backward pruning. Our results shed light on the ability of different plan-encoding schemes to propagate information forward and backward and on the relative merit of plan-level and SAT-level pruning methods.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {1–28},
numpages = {28}
}

@article{10.5555/1622262.1622269,
author = {Cimatti, Alessandro and Roveri, Marco},
title = {Conformant Planning via Symbolic Model Checking},
year = {2000},
issue_date = {August 2000},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {13},
number = {1},
issn = {1076-9757},
abstract = {We tackle the problem of planning in nondeterministic domains, by presenting a new approach to conformant planning. Conformant planning is the problem of finding a sequence of actions that is guaranteed to achieve the goal despite the nondeterminism of the domain. Our approach is based on the representation of the planning domain as a finite state automaton. We use Symbolic Model Checking techniques, in particular Binary Decision Diagrams, to compactly represent and efficiently search the automaton. In this paper we make the following contributions. First, we present a general planning algorithm for conformant planning, which applies to fully nondeterministic domains, with uncertainty in the initial condition and in action effects. The algorithm is based on a breadth-first, backward search, and returns conformant plans of minimal length, if a solution to the planning problem exists, otherwise it terminates concluding that the problem admits no conformant solution. Second, we provide a symbolic representation of the search space based on Binary Decision Diagrams (BDDs), which is the basis for search techniques derived from symbolic model checking. The symbolic representation makes it possible to analyze potentially large sets of states and transitions in a single computation step, thus providing for an efficient implementation. Third, we present CMBP (Conformant Model Based Planner), an efficient implementation of the data structures and algorithm described above, directly based on BDD manipulations, which allows for a compact representation of the search layers and an efficient implementation of the search steps. Finally, we present an experimental comparison of our approach with the state-of-the-art conformant planners CGP, QBFPLAN and GPT. Our analysis includes all the planning problems from the distribution packages of these systems, plus other problems defined to stress a number of specific factors. Our approach appears to be the most effective: CMBP is strictly more expressive than QBFPLAN and CGP and, in all the problems where a comparison is possible, CMBP outperforms its competitors, sometimes by orders of magnitude.},
journal = {J. Artif. Int. Res.},
month = dec,
pages = {305–338},
numpages = {34}
}

@article{10.5555/1622262.1622268,
author = {Dietterich, Thomas G.},
title = {Hierarchical Reinforcement Learning with the MAXQ Value Function Decomposition},
year = {2000},
issue_date = {August 2000},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {13},
number = {1},
issn = {1076-9757},
abstract = {This paper presents a new approach to hierarchical reinforcement learning based on decomposing the target Markov decision process (MDP) into a hierarchy of smaller MDPs and decomposing the value function of the target MDP into an additive combination of the value functions of the smaller MDPs. The decomposition, known as the MAXQ decomposition, has both a procedural semantics--as a subroutine hierarchy--and a declarative semantics--as a representation of the value function of a hierarchical policy. MAXQ unifies and extends previous work on hierarchical reinforcement learning by Singh, Kaelbling, and Dayan and Hinton. It is based on the assumption that the programmer can identify useful subgoals and define subtasks that achieve these subgoals. By defining such subgoals, the programmer constrains the set of policies that need to be considered during reinforcement learning. The MAXQ value function decomposition can represent the value function of any policy that is consistent with the given hierarchy. The decomposition also creates opportunities to exploit state abstractions, so that individual MDPs within the hierarchy can ignore large parts of the state space. This is important for the practical application of the method. This paper defines the MAXQ hierarchy, proves formal results on its representational power, and establishes five conditions for the safe use of state abstractions. The paper presents an online model-free learning algorithm, MAXQ-Q, and proves that it converges with probability 1 to a kind of locally-optimal policy known as a recursively optimal policy, even in the presence of the five kinds of state abstraction. The paper evaluates the MAXQ representation and MAXQ-Q through a series of experiments in three domains and shows experimentally that MAXQ-Q (with state abstractions) converges to a recursively optimal policy much faster than flat Q learning. The fact that MAXQ learns a representation of the value function has an important benefit: it makes it possible to compute and execute an improved, non-hierarchical policy via a procedure similar to the policy improvement step of policy iteration. The paper demonstrates the effectiveness of this nonhierarchical execution experimentally. Finally, the paper concludes with a comparison to related work and a discussion of the design tradeoffs in hierarchical reinforcement learning.},
journal = {J. Artif. Int. Res.},
month = nov,
pages = {227–303},
numpages = {77}
}

@article{10.5555/1622262.1622267,
author = {Jensen, Rune M. and Veloso, Manuela M.},
title = {OBDD-Based Universal Planning for Synchronized Agents in Non-Deterministic Domains},
year = {2000},
issue_date = {August 2000},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {13},
number = {1},
issn = {1076-9757},
abstract = {Recently model checking representation and search techniques were shown to be efficiently applicable to planning, in particular to non-deterministic planning. Such planning approaches use Ordered Binary Decision Diagrams (OBDDS) to encode a planning domain as a non-deterministic finite automaton and then apply fast algorithms from model checking to search for a solution. OBDDS can effectively scale and can provide universal plans for complex planning domains. We are particularly interested in addressing the complexities arising in non-deterministic, multi-agent domains. In this article, we present UMOP, a new universal OBDD-based planning framework for non-deterministic, multi-agent domains. We introduce a new planning domain description language, NADL, to specify non-deterministic, multi-agent domains. The language contributes the explicit definition of controllable agents and uncontrollable environment agents. We describe the syntax and semantics of NADL and show how to build an efficient OBDD-based representation of an NADL description. The UMOP planning system uses NADL and different OBDD-based universal planning algorithms. It includes the previously developed strong and strong cyclic planning algorithms. In addition, we introduce our new optimistic planning algorithm that relaxes optimality guarantees and generates plausible universal plans in some domains where no strong nor strong cyclic solution exists. We present empirical results applying UMOP to domains ranging from deterministic and single-agent with no environment actions to non-deterministic and multi-agent with complex environment actions. UMOP is shown to be a rich and efficient planning system.},
journal = {J. Artif. Int. Res.},
month = oct,
pages = {189–226},
numpages = {38}
}

@article{10.5555/1622262.1622266,
author = {Cheng, Jian and Druzdzel, Marek J.},
title = {AIS-BN: An Adaptive Importance Sampling Algorithm for Evidential Reasoning in Large Bayesian Networks},
year = {2000},
issue_date = {August 2000},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {13},
number = {1},
issn = {1076-9757},
abstract = {Stochastic sampling algorithms, while an attractive alternative to exact algorithms in very large Bayesian network models, have been observed to perform poorly in evidential reasoning with extremely unlikely evidence. To address this problem, we propose an adaptive importance sampling algorithm, AIS-BN, that shows promising convergence rates even under extreme conditions and seems to outperform the existing sampling algorithms consistently. Three sources of this performance improvement are (1) two heuristics for initialization of the importance function that are based on the theoretical properties of importance sampling in finite-dimensional integrals and the structural advantages of Bayesian networks, (2) a smooth learning method for the importance function, and (3) a dynamic weighting function for combining samples from different stages of the algorithm.We tested the performance of the AIS-BN algorithm along with two state of the art general purpose sampling algorithms, likelihood weighting (Fung & Chang, 1989; Shachter & Peot, 1989) and self-importance sampling (Shachter & Peot, 1989). We used in our tests three large real Bayesian network models available to the scientific community: the CPCS network (Pradhan et al., 1994), the PATHFINDER network (Heckerman, Horvitz, & Nathwani, 1990), and the ANDES network (Conati, Gertner, VanLehn, & Druzdzel, 1997), with evidence as unlikely as 10-41. While the AIS-BN algorithm always performed better than the other two algorithms, in the majority of the test cases it achieved orders of magnitude improvement in precision of the results. Improvement in speed given a desired precision is even more dramatic, although we are unable to report numerical results here, as the other algorithms almost never achieved the precision reached even by the first few iterations of the AIS-BN algorithm.},
journal = {J. Artif. Int. Res.},
month = oct,
pages = {155–188},
numpages = {34}
}

@article{10.5555/1622262.1622265,
author = {Gordon, Diana F.},
title = {Asimovian Adaptive Agents},
year = {2000},
issue_date = {August 2000},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {13},
number = {1},
issn = {1076-9757},
abstract = {The goal of this research is to develop agents that are adaptive and predictable and timely. At first blush, these three requirements seem contradictory. For example, adaptation risks introducing undesirable side effects, thereby making agents' behavior less predictable. Furthermore, although formal verification can assist in ensuring behavioral predictability, it is known to be time-consuming.Our solution to the challenge of satisfying all three requirements is the following. Agents have finite-state automaton plans, which are adapted online via evolutionary learning (perturbation) operators. To ensure that critical behavioral constraints are always satisfied, agents' plans are first formally verified. They are then reverified after every adaptation. If reverification concludes that constraints are violated, the plans are repaired. The main objective of this paper is to improve the efficiency of reverification after learning, so that agents have a sufficiently rapid response time. We present two solutions: positive results that certain learning operators are a priori guaranteed to preserve useful classes of behavioral assurance constraints (which implies that no reverification is needed for these operators), and efficient incremental reverification algorithms for those learning operators that have negative a priori results.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {95–153},
numpages = {59}
}

@article{10.5555/1622262.1622264,
author = {Hauskrecht, Milos},
title = {Value-Function Approximations for Partially Observable Markov Decision Processes},
year = {2000},
issue_date = {August 2000},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {13},
number = {1},
issn = {1076-9757},
abstract = {Partially observable Markov decision processes (POMDPs) provide an elegant mathematical framework for modeling complex decision and planning problems in stochastic domains in which states of the system are observable only indirectly, via a set of imperfect or noisy observations. The modeling advantage of POMDPs, however, comes at a price -- exact methods for solving them are computationally very expensive and thus applicable in practice only to very simple problems. We focus on efficient approximation (heuristic) methods that attempt to alleviate the computational problem and trade off accuracy for speed. We have two objectives here. First, we survey various approximation methods, analyze their properties and relations and provide some new insights into their differences. Second, we present a number of new approximation methods and novel refinements of existing techniques. The theoretical results are supported by experiments on a problem from the agent navigation domain.},
journal = {J. Artif. Int. Res.},
month = aug,
pages = {33–94},
numpages = {62}
}

@article{10.5555/1622262.1622263,
author = {Cadoli, Marco and Donini, Francesco M. and Liberatore, Paolo and Schaerf, Marco},
title = {Space Efficiency of Propositional Knowledge Representation Formalisms},
year = {2000},
issue_date = {August 2000},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {13},
number = {1},
issn = {1076-9757},
abstract = {We investigate the space efficiency of a Propositional Knowledge Representation (PKR) formalism. Intuitively, the space efficiency of a formalism F in representing a certain piece of knowledge α, is the size of the shortest formula of F that represents α. In this paper we assume that knowledge is either a set of propositional interpretations (models) or a set of propositional formulae (theorems). We provide a formal way of talking about the relative ability of PKR formalisms to compactly represent a set of models or a set of theorems. We introduce two new compactness measures, the corresponding classes, and show that the relative space efficiency of a PKR formalism in representing models/theorems is directly related to such classes. In particular, we consider formalisms for nonmonotonic reasoning, such as circumscription and default logic, as well as belief revision operators and the stable model semantics for logic programs with negation. One interesting result is that formalisms with the same time complexity do not necessarily belong to the same space efficiency class.},
journal = {J. Artif. Int. Res.},
month = aug,
pages = {1–31},
numpages = {31}
}

@article{10.5555/1622248.1622261,
author = {Walker, Marilyn A.},
title = {An Application of Reinforcement Learning to Dialogue Strategy Selection in a Spoken Dialogue System for Email},
year = {2000},
issue_date = {February 2000},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {12},
number = {1},
issn = {1076-9757},
abstract = {This paper describes a novel method by which a spoken dialogue system can learn to choose an optimal dialogue strategy from its experience interacting with human users. The method is based on a combination of reinforcement learning and performance modeling of spoken dialogue systems. The reinforcement learning component applies Q-learning (Watkins, 1989), while the performance modeling component applies the PARADISE evaluation framework (Walker et al., 1997) to learn the performance function (reward) used in reinforcement learning. We illustrate the method with a spoken dialogue system named elvis (EmaiL Voice Interactive System), that supports access to email over the phone. We conduct a set of experiments for training an optimal dialogue strategy on a corpus of 219 dialogues in which human users interact with elvis over the phone. We then test that strategy on a corpus of 18 dialogues. We show that elvis can learn to optimize its strategy selection for agent initiative, for reading messages, and for summarizing email folders.},
journal = {J. Artif. Int. Res.},
month = jun,
pages = {387–416},
numpages = {30}
}

@article{10.5555/1622248.1622260,
author = {Koehler, Jana and Hoffmann, J\"{o}rg},
title = {On Reasonable and Forced Goal Orderings and Their Use in an Agenda-Driven Planning Algorithm},
year = {2000},
issue_date = {February 2000},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {12},
number = {1},
issn = {1076-9757},
abstract = {The paper addresses the problem of computing goal orderings, which is one of the longstanding issues in AI planning. It makes two new contributions. First, it formally defines and discusses two different goal orderings, which are called the reasonable and the forced ordering. Both orderings are defined for simple STRIPS operators as well as for more complex ADL operators supporting negation and conditional effects. The complexity of these orderings is investigated and their practical relevance is discussed. Secondly, two different methods to compute reasonable goal orderings are developed. One of them is based on planning graphs, while the other investigates the set of actions directly. Finally, it is shown how the ordering relations, which have been derived for a given set of goals G, can be used to compute a so-called goal agenda that divides G into an ordered set of subgoals. Any planner can then, in principle, use the goal agenda to plan for increasing sets of subgoals. This can lead to an exponential complexity reduction, as the solution to a complex planning problem is found by solving easier subproblems. Since only a polynomial overhead is caused by the goal agenda computation, a potential exists to dramatically speed up planning algorithms as we demonstrate in the empirical evaluation, where we use this method in the IPP planner.},
journal = {J. Artif. Int. Res.},
month = jun,
pages = {339–386},
numpages = {48}
}

@article{10.5555/1622248.1622259,
author = {Halpern, Joseph Y.},
title = {Axiomatizing Causal Reasoning},
year = {2000},
issue_date = {February 2000},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {12},
number = {1},
issn = {1076-9757},
abstract = {Causal models defined in terms of a collection of equations, as defined by Pearl, are axiomatized here. Axiomatizations are provided for three successively more general classes of causal models: (1) the class of recursive theories (those without feedback), (2) the class of theories where the solutions to the equations are unique, (3) arbitrary theories (where the equations may not have solutions and, if they do, they are not necessarily unique). It is shown that to reason about causality in the most general third class, we must extend the language used by Galles and Pearl (1997, 1998). In addition, the complexity of the decision procedures is characterized for all the languages and classes of models considered.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {317–337},
numpages = {21}
}

@article{10.5555/1622248.1622258,
author = {Nebel, Bernhard},
title = {On the Compilability and Expressive Power of Propositional Planning Formalisms},
year = {2000},
issue_date = {February 2000},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {12},
number = {1},
issn = {1076-9757},
abstract = {The recent approaches of extending the GRAPHPLAN algorithm to handle more expressive planning formalisms raise the question of what the formal meaning of "expressive power" is. We formalize the intuition that expressive power is a measure of how concisely planning domains and plans can be expressed in a particular formalism by introducing the notion of "compilation schemes" between planning formalisms. Using this notion, we analyze the expressiveness of a large family of propositional planning formalisms, ranging from basic STRIPS to a formalism with conditional effects, partial state specifications, and propositional formulae in the preconditions. One of the results is that conditional effects cannot be compiled away if plan size should grow only linearly but can be compiled away if we allow for polynomial growth of the resulting plans. This result confirms that the recently proposed extensions to the GRAPHPLAN algorithm concerning conditional effects are optimal with respect to the "compilability" framework. Another result is that general propositional formulae cannot be compiled into conditional effects if the plan size should be preserved linearly. This implies that allowing general propositional formulae in preconditions and effect conditions adds another level of difficulty in generating a plan.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {271–315},
numpages = {45}
}

@article{10.5555/1622248.1622257,
author = {Singer, Josh and Gent, Ian P. and Smaill, Alan},
title = {Backbone Fragility and the Local Search Cost Peak},
year = {2000},
issue_date = {February 2000},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {12},
number = {1},
issn = {1076-9757},
abstract = {The local search algorithm WSAT is one of the most successful algorithms for solving the satisfiability (SAT) problem. It is notably effective at solving hard Random 3-SAT instances near the so-called 'satisfiability threshold', but still shows a peak in search cost near the threshold and large variations in cost over different instances. We make a number of significant contributions to the analysis of WSAT on high-cost random instances, using the recently-introduced concept of the backbone of a SAT instance. The backbone is the set of literals which are entailed by an instance. We find that the number of solutions predicts the cost well for small-backbone instances but is much less relevant for the large-backbone instances which appear near the threshold and dominate in the overconstrained region. We show a very strong correlation between search cost and the Hamming distance to the nearest solution early in WSAT's search. This pattern leads us to introduce a measure of the backbone fragility of an instance, which indicates how persistent the backbone is as clauses are removed. We propose that high-cost random instances for local search are those with very large backbones which are also backbone-fragile. We suggest that the decay in cost beyond the satisfiability threshold is due to increasing backbone robustness (the opposite of backbone fragility). Our hypothesis makes three correct predictions. First, that the backbone robustness of an instance is negatively correlated with the local search cost when other factors are controlled for. Second, that backbone-minimal instances (which are 3-SAT instances altered so as to be more backbone-fragile) are unusually hard for WSAT. Third, that the clauses most often unsatisfied during search are those whose deletion has the most effect on the backbone. In understanding the pathologies of local search methods, we hope to contribute to the development of new and better techniques.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {235–270},
numpages = {36}
}

@article{10.5555/1622248.1622256,
author = {Becker, Ann and Bar-Yehuda, Reuven and Geiger, Dan},
title = {Randomized Algorithms for the Loop Cutset Problem},
year = {2000},
issue_date = {February 2000},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {12},
number = {1},
issn = {1076-9757},
abstract = {We show how to find a minimum weight loop cutset in a Bayesian network with high probability. Finding such a loop cutset is the first step in the method of conditioning for inference. Our randomized algorithm for finding a loop cutset outputs a minimum loop cutset after O(c 6kkn) steps with probability at least 1 - (1 - 1/6k)c6k, where c > 1 is a constant specified by the user, k is the minimal size of a minimum weight loop cutset, and n is the number of vertices. We also show empirically that a variant of this algorithm often finds a loop cutset that is closer to the minimum weight loop cutset than the ones found by the best deterministic algorithms known.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {219–234},
numpages = {16}
}

@article{10.5555/1622248.1622255,
author = {Tobies, Stephan},
title = {The Complexity of Reasoning with Cardinality Restrictions and Nominals in Expressive Description Logics},
year = {2000},
issue_date = {February 2000},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {12},
number = {1},
issn = {1076-9757},
abstract = {We study the complexity of the combination of the Description Logics ALCQ and ALCQI with a terminological formalism based on cardinality restrictions on concepts. These combinations can naturally be embedded into C2, the two variable fragment of predicate logic with counting quantifiers, which yields decidability in NExpTime. We show that this approach leads to an optimal solution for ALCQI, as ALCQI with cardinality restrictions has the same complexity as C2 (NExpTime-complete). In contrast, we show that for ALCQ, the problem can be solved in ExpTime. This result is obtained by a reduction of reasoning with cardinality restrictions to reasoning with the (in general weaker) terminological formalism of general axioms for ALCQ extended with nominals. Using the same reduction, we show that, for the extension of ALCQI with nominals, reasoning with general axioms is a NExpTime-complete problem. Finally, we sharpen this result and show that pure concept satisfiability for ALCQI with nominals is NExpTime-complete. Without nominals, this problem is known to be PSpace-complete.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {199–217},
numpages = {19}
}

@article{10.5555/1622248.1622254,
author = {Baxter, Jonathan},
title = {A Model of Inductive Bias Learning},
year = {2000},
issue_date = {February 2000},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {12},
number = {1},
issn = {1076-9757},
abstract = {A major problem in machine learning is that of inductive bias: how to choose a learner's hypothesis space so that it is large enough to contain a solution to the problem being learnt, yet small enough to ensure reliable generalization from reasonably-sized training sets. Typically such bias is supplied by hand through the skill and insights of experts. In this paper a model for automatically learning bias is investigated. The central assumption of the model is that the learner is embedded within an environment of related learning tasks. Within such an environment the learner can sample from multiple tasks, and hence it can search for a hypothesis space that contains good solutions to many of the problems in the environment. Under certain restrictions on the set of all hypothesis spaces available to the learner, we show that a hypothesis space that performs well on a sufficiently large number of training tasks will also perform well when learning novel tasks in the same environment. Explicit bounds are also derived demonstrating that learning multiple tasks within an environment of related tasks can potentially give much better generalization than learning a single task.},
journal = {J. Artif. Int. Res.},
month = mar,
pages = {149–198},
numpages = {50}
}

@article{10.5555/1622248.1622253,
author = {Kaminka, Gal A. and Tambe, Milind},
title = {Robust Agent Teams via Socially-Attentive Monitoring},
year = {2000},
issue_date = {February 2000},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {12},
number = {1},
issn = {1076-9757},
abstract = {Agents in dynamic multi-agent environments must monitor their peers to execute individual and group plans. A key open question is how much monitoring of other agents' states is required to be effective: The Monitoring Selectivity Problem. We investigate this question in the context of detecting failures in teams of cooperating agents, via Socially-Attentive Monitoring, which focuses on monitoring for failures in the social relationships between the agents. We empirically and analytically explore a family of socially-attentive teamwork monitoring algorithms in two dynamic, complex, multi-agent domains, under varying conditions of task distribution and uncertainty. We show that a centralized scheme using a complex algorithm trades correctness for completeness and requires monitoring all teammates. In contrast, a simple distributed teamwork monitoring algorithm results in correct and complete detection of teamwork failures, despite relying on limited, uncertain knowledge, and monitoring only key agents in a team. In addition, we report on the design of a socially-attentive monitoring system and demonstrate its generality in monitoring several coordination relationships, diagnosing detected failures, and both on-line and off-line applications.},
journal = {J. Artif. Int. Res.},
month = mar,
pages = {105–147},
numpages = {43}
}

@article{10.5555/1622248.1622252,
author = {Xu, Ke and Li, Wei},
title = {Exact Phase Transitions in Random Constraint Satisfaction Problems},
year = {2000},
issue_date = {February 2000},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {12},
number = {1},
issn = {1076-9757},
abstract = {In this paper we propose a new type of random CSP model, called Model RB, which is a revision to the standard Model B. It is proved that phase transitions from a region where almost all problems are satisfiable to a region where almost all problems are unsatisfiable do exist for Model RB as the number of variables approaches infinity. Moreover, the critical values at which the phase transitions occur are also known exactly. By relating the hardness of Model RB to Model B, it is shown that there exist a lot of hard instances in Model RB.},
journal = {J. Artif. Int. Res.},
month = mar,
pages = {93–103},
numpages = {11}
}

@article{10.5555/1622248.1622251,
author = {Neal, Radford M.},
title = {On Deducing Conditional Independence from D-Separation in Causal Graphs with Feedback},
year = {2000},
issue_date = {February 2000},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {12},
number = {1},
issn = {1076-9757},
abstract = {Pearl and Dechter (1996) claimed that the d-separation criterion for conditional independence in acyclic causal networks also applies to networks of discrete variables that have feedback cycles, provided that the variables of the system are uniquely determined by the random disturbances. I show by example that this is not true in general. Some condition stronger than uniqueness is needed, such as the existence of a causal dynamics guaranteed to lead to the unique solution.},
journal = {J. Artif. Int. Res.},
month = mar,
pages = {87–91},
numpages = {5}
}

@article{10.5555/1622248.1622250,
author = {Barber, Federico},
title = {Reasoning on Interval and Point-Based Disjunctive Metric Constraints in Temporal Contexts},
year = {2000},
issue_date = {February 2000},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {12},
number = {1},
issn = {1076-9757},
abstract = {We introduce a temporal model for reasoning on disjunctive metric constraints on intervals and time points in temporal contexts. This temporal model is composed of a labeled temporal algebra and its reasoning algorithms. The labeled temporal algebra defines labeled disjunctive metric point-based constraints, where each disjunct in each input disjunctive constraint is univocally associated to a label. Reasoning algorithms manage labeled constraints, associated label lists, and sets of mutually inconsistent disjuncts. These algorithms guarantee consistency and obtain a minimal network. Additionally, constraints can be organized in a hierarchy of alternative temporal contexts. Therefore, we can reason on context-dependent disjunctive metric constraints on intervals and points. Moreover, the model is able to represent non-binary constraints, such that logical dependencies on disjuncts in constraints can be handled. The computational cost of reasoning algorithms is exponential in accordance with the underlying problem complexity, although some improvements are proposed.},
journal = {J. Artif. Int. Res.},
month = feb,
pages = {35–86},
numpages = {52}
}

@article{10.5555/1622248.1622249,
author = {Kambhampati, Subbarao},
title = {Planning Graph as a (Dynamic) CSP: Exploiting EBL, DDB and Other CSP Search Techniques in Graphplan},
year = {2000},
issue_date = {February 2000},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {12},
number = {1},
issn = {1076-9757},
abstract = {This paper reviews the connections between Graphplan's planning-graph and the dynamic constraint satisfaction problem and motivates the need for adapting CSP search techniques to the Graphplan algorithm. It then describes how explanation based learning, dependency directed backtracking, dynamic variable ordering, forward checking, sticky values and random-restart search strategies can be adapted to Graphplan. Empirical results are provided to demonstrate that these augmentations improve Graphplan's performance significantly (up to 1000x speedups) on several benchmark problems. Special attention is paid to the explanation-based learning and dependency directed backtracking techniques as they are empirically found to be most useful in improving the performance of Graphplan.},
journal = {J. Artif. Int. Res.},
month = feb,
pages = {1–34},
numpages = {34}
}

@article{10.5555/3013545.3013557,
author = {Halpern, Joseph Y.},
title = {Cox's Theorem Revisited},
year = {1999},
issue_date = {July 1999},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {11},
number = {1},
issn = {1076-9757},
abstract = {The assumptions needed to prove Cox's Theorem are discussed and examined. Various sets of assumptions under which a Cox-style theorem can be proved are provided, although all are rather strong and, arguably, not natural.},
journal = {J. Artif. Int. Res.},
month = jul,
pages = {429–435},
numpages = {7}
}

@article{10.5555/3013545.3013556,
author = {Fox, Dieter and Burgard, Wolfram and Thrun, Sebastian},
title = {Markov Localization for Mobile Robots in Dynamic Environments},
year = {1999},
issue_date = {July 1999},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {11},
number = {1},
issn = {1076-9757},
abstract = {Localization, that is the estimation of a robot's location from sensor data, is a fundamental problem in mobile robotics. This papers presents a version of Markov localization which provides accurate position estimates and which is tailored towards dynamic environments. The key idea of Markov localization is to maintain a probability density over the space of all locations of a robot in its environment. Our approach represents this space metrically, using a fine-grained grid to approximate densities. It is able to globally localize the robot from scratch and to recover from localization failures. It is robust to approximate models of the environment (such as occupancy grid maps) and noisy sensors (such as ultrasound sensors). Our approach also includes a filtering technique which allows a mobile robot to reliably estimate its position even in densely populated environments in which crowds of people block the robot's sensors for extended periods of time. The method described here has been implemented and tested in several real-world applications of mobile robots, including the deployments of two mobile robots as interactive museum tour-guides.},
journal = {J. Artif. Int. Res.},
month = jul,
pages = {391–427},
numpages = {37}
}

@article{10.5555/3013545.3013555,
author = {Cristani, Matteo},
title = {The Complexity of Reasoning about Spatial Congruence},
year = {1999},
issue_date = {July 1999},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {11},
number = {1},
issn = {1076-9757},
abstract = {In the recent literature of Artificial Intelligence, an intensive research effort has been spent, for various algebras of qualitative relations used in the representation of temporal and spatial knowledge, on the problem of classifying the computational complexity of reasoning problems for subsets of algebras. The main purpose of these researches is to describe a restricted set of maximal tractable subalgebras, ideally in an exhaustive fashion with respect to the hosting algebras.In this paper we introduce a novel algebra for reasoning about Spatial Congruence, show that the satisfiability problem in the spatial algebra MC-4 is NP-complete, and present a complete classification of tractability in the algebra, based on the individuation of three maximal tractable subclasses, one containing the basic relations. The three algebras are formed by 14, 10 and 9 relations out of 16 which form the full algebra.},
journal = {J. Artif. Int. Res.},
month = jul,
pages = {361–390},
numpages = {30}
}

@article{10.5555/3013545.3013554,
author = {Argamon-Engelson, Shlomo and Dagan, Ido},
title = {Committee-Based Sample Selection for Probabilistic Classifiers},
year = {1999},
issue_date = {July 1999},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {11},
number = {1},
issn = {1076-9757},
abstract = {In many real-world learning tasks it is expensive to acquire a sufficient number of labeled examples for training. This paper investigates methods for reducing annotation cost by sample selection. In this approach, during training the learning program examines many unlabeled examples and selects for labeling only those that are most informative at each stage. This avoids redundantly labeling examples that contribute little new information.Our work follows on previous research on Query By Committee, and extends the committee-based paradigm to the context of probabilistic classification. We describe a family of empirical methods for committee-based sample selection in probabilistic classification models, which evaluate the informativeness of an example by measuring the degree of disagreement between several model variants. These variants (the committee) are drawn randomly from a probability distribution conditioned by the training set labeled so far.The method was applied to the real-world natural language processing task of stochastic part-of-speech tagging. We find that all variants of the method achieve a significant reduction in annotation cost, although their computational efficiency differs. In particular, the simplest variant, a two member committee with no parameters to tune, gives excellent results. We also show that sample selection yields a significant reduction in the size of the model used by the tagger.},
journal = {J. Artif. Int. Res.},
month = jul,
pages = {335–360},
numpages = {26}
}

@article{10.5555/3013545.3013553,
author = {Ygge, Fredrik and Akkermans, Hans},
title = {Decentralized Markets versus Central Control: A Comparative Study},
year = {1999},
issue_date = {July 1999},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {11},
number = {1},
issn = {1076-9757},
abstract = {Multi-Agent Systems (MAS) promise to offer solutions to problems where established, older paradigms fall short. In order to validate such claims that are repeatedly made in software agent publications, empirical in-depth studies of advantages and weaknesses of multi-agent solutions versus conventional ones in practical applications are needed. Climate control in large buildings is one application area where multi-agent systems, and market-oriented programming in particular, have been reported to be very successful, although central control solutions are still the standard practice. We have therefore constructed and implemented a variety of market designs for this problem, as well as different standard control engineering solutions. This article gives a detailed analysis and comparison, so as to learn about differences between standard versus agent approaches, and yielding new insights about benefits and limitations of computational markets. An important outcome is that "local information plus market communication produces global control".},
journal = {J. Artif. Int. Res.},
month = jul,
pages = {301–333},
numpages = {33}
}

@article{10.5555/3013545.3013552,
author = {Rosati, Riccardo},
title = {Reasoning about Minimal Belief and Negation as Failure},
year = {1999},
issue_date = {July 1999},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {11},
number = {1},
issn = {1076-9757},
abstract = {We investigate the problem of reasoning in the propositional fragment of MBNF, the logic of minimal belief and negation as failure introduced by Lifschitz, which can be considered as a unifying framework for several nonmonotonic formalisms, including default logic, autoepistemic logic, circumscription, epistemic queries, and logic programming. We characterize the complexity and provide algorithms for reasoning in propositional MBNF. In particular, we show that skeptical entailment in propositional MBNF is Π3p-complete, hence it is harder than reasoning in all the above mentioned propositional formalisms for nonmonotonic reasoning. We also prove the exact correspondence between negation as failure in MBNF and negative introspection in Moore's autoepistemic logic.},
journal = {J. Artif. Int. Res.},
month = jul,
pages = {277–300},
numpages = {24}
}

@article{10.5555/3013545.3013551,
author = {Moriarty, David E. and Schultz, Alan C. and Grefenstette, John J.},
title = {Evolutionary Algorithms for Reinforcement Learning},
year = {1999},
issue_date = {July 1999},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {11},
number = {1},
issn = {1076-9757},
abstract = {There are two distinct approaches to solving reinforcement learning problems, namely, searching in value function space and searching in policy space. Temporal difference methods and evolutionary algorithms are well-known examples of these approaches. Kaelbling, Littman and Moore recently provided an informative survey of temporal difference methods. This article focuses on the application of evolutionary algorithms to the reinforcement learning problem, emphasizing alternative policy representations, credit assignment methods, and problem-specific genetic operators. Strengths and weaknesses of the evolutionary approach to reinforcement learning are presented, along with a survey of representative applications.},
journal = {J. Artif. Int. Res.},
month = jul,
pages = {241–276},
numpages = {36}
}

@article{10.5555/3013545.3013550,
author = {Calvanese, Diego and Lenzerini, Maurizio and Nardi, Daniele},
title = {Unifying Class-Based Representation Formalisms},
year = {1999},
issue_date = {July 1999},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {11},
number = {1},
issn = {1076-9757},
abstract = {The notion of class is ubiquitous in computer science and is central in many formalisms for the representation of structured knowledge used both in knowledge representation and in databases. In this paper we study the basic issues underlying such representation formalisms and single out both their common characteristics and their distinguishing features. Such investigation leads us to propose a unifying framework in which we are able to capture the fundamental aspects of several representation languages used in different contexts. The proposed formalism is expressed in the style of description logics, which have been introduced in knowledge representation as a means to provide a semantically well-founded basis for the structural aspects of knowledge representation systems. The description logic considered in this paper is a subset of first order logic with nice computational characteristics. It is quite expressive and features a novel combination of constructs that has not been studied before. The distinguishing constructs are number restrictions, which generalize existence and functional dependencies, inverse roles, which allow one to refer to the inverse of a relationship, and possibly cyclic assertions, which are necessary for capturing real world domains. We are able to show that it is precisely such combination of constructs that makes our logic powerful enough to model the essential set of features for defining class structures that are common to frame systems, object-oriented database languages, and semantic data models. As a consequence of the established correspondences, several significant extensions of each of the above formalisms become available. The high expressiveness of the logic we propose and the need for capturing the reasoning in different contexts forces us to distinguish between unrestricted and finite model reasoning. A notable feature of our proposal is that reasoning in both cases is decidable. We argue that, by virtue of the high expressive power and of the associated reasoning capabilities on both unrestricted and finite models, our logic provides a common core for class-based representation formalisms.},
journal = {J. Artif. Int. Res.},
month = jul,
pages = {199–240},
numpages = {42}
}

@article{10.5555/3013545.3013549,
author = {Opitz, David and Maclin, Richard},
title = {Popular Ensemble Methods: An Empirical Study},
year = {1999},
issue_date = {July 1999},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {11},
number = {1},
issn = {1076-9757},
abstract = {An ensemble consists of a set of individually trained classifiers (such as neural networks or decision trees) whose predictions are combined when classifying novel instances. Previous research has shown that an ensemble is often more accurate than any of the single classifiers in the ensemble. Bagging (Breiman, 1996c) and Boosting (Freund & Schapire, 1996; Schapire, 1990) are two relatively new but popular methods for producing ensembles. In this paper we evaluate these methods on 23 data sets using both neural networks and decision trees as our classification algorithm. Our results clearly indicate a number of conclusions. First, while Bagging is almost always more accurate than a single classifier, it is sometimes much less accurate than Boosting. On the other hand, Boosting can create ensembles that are less accurate than a single classifier - especially when using neural networks. Analysis indicates that the performance of the Boosting methods is dependent on the characteristics of the data set being examined. In fact, further results show that Boosting ensembles may overfit noisy data sets, thus decreasing its performance. Finally, consistent with previous studies, our work suggests that most of the gain in an ensemble's performance comes in the first few classifiers combined; however, relatively large gains can be seen up to 25 classifiers when Boosting decision trees.},
journal = {J. Artif. Int. Res.},
month = jul,
pages = {169–198},
numpages = {30}
}

@article{10.5555/3013545.3013548,
author = {Brodley, Carla E. and Friedl, Mark A.},
title = {Identifying Mislabeled Training Data},
year = {1999},
issue_date = {July 1999},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {11},
number = {1},
issn = {1076-9757},
abstract = {This paper presents a new approach to identifying and eliminating mislabeled training instances for supervised learning. The goal of this approach is to improve classification accuracies produced by learning algorithms by improving the quality of the training data. Our approach uses a set of learning algorithms to create classifiers that serve as noise filters for the training data. We evaluate single algorithm, majority vote and consensus filters on five datasets that are prone to labeling errors. Our experiments illustrate that filtering significantly improves classification accuracy for noise levels up to 30%. An analytical and empirical evaluation of the precision of our approach shows that consensus filters are conservative at throwing away good data at the expense of retaining bad data and that majority filters are better at detecting bad data at the expense of throwing away good data. This suggests that for situations in which there is a paucity of data, consensus filters are preferable, whereas majority vote filters are preferable for situations with an abundance of data.},
journal = {J. Artif. Int. Res.},
month = jul,
pages = {131–167},
numpages = {37}
}

@article{10.5555/3013545.3013547,
author = {Resnik, Philip},
title = {Semantic Similarity in a Taxonomy: An Information-Based Measure and Its Application to Problems of Ambiguity in Natural Language},
year = {1999},
issue_date = {July 1999},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {11},
number = {1},
issn = {1076-9757},
abstract = {This article presents a measure of semantic similarity in an IS-A taxonomy based on the notion of shared information content. Experimental evaluation against a benchmark set of human similarity judgments demonstrates that the measure performs better than the traditional edge-counting approach. The article presents algorithms that take advantage of taxonomic similarity in resolving syntactic and semantic ambiguity, along with experimental results demonstrating their effectiveness.},
journal = {J. Artif. Int. Res.},
month = jul,
pages = {95–130},
numpages = {36}
}

@article{10.5555/3013545.3013546,
author = {Boutilier, Craig and Dean, Thomas and Hanks, Steve},
title = {Decision-Theoretic Planning: Structural Assumptions and Computational Leverage},
year = {1999},
issue_date = {July 1999},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {11},
number = {1},
issn = {1076-9757},
abstract = {Planning under uncertainty is a central problem in the study of automated sequential decision making, and has been addressed by researchers in many different fields, including AI planning, decision analysis, operations research, control theory and economics. While the assumptions and perspectives adopted in these areas often differ in substantial ways, many planning problems of interest to researchers in these fields can be modeled as Markov decision processes (MDPs) and analyzed using the techniques of decision theory.This paper presents an overview and synthesis of MDP-related methods, showing how they provide a unifying framework for modeling many classes of planning problems studied in AI. It also describes structural properties of MDPs that, when exhibited by particular classes of problems, can be exploited in the construction of optimal or approximately optimal policies or plans. Planning problems commonly possess structure in the reward and value functions used to describe performance criteria, in the functions used to describe state transitions and observations, and in the relationships among features used to describe states, actions, rewards, and observations.Specialized representations, and algorithms employing these representations, can achieve computational leverage by exploiting these various forms of structure. Certain AI techniques-- in particular those based on the use of structured, intensional representations--can be viewed in this way. This paper surveys several types of representations for both classical and decision-theoretic planning problems, and planning algorithms that exploit these representations in a number of different ways to ease the computational burden of constructing policies or plans. It focuses primarily on abstraction, aggregation and decomposition techniques based on AI-style representations.},
journal = {J. Artif. Int. Res.},
month = jul,
pages = {1–94},
numpages = {94}
}

@article{10.5555/1622859.1622875,
author = {Birnbaum, Elazar and Lozinskii, Eliezer L.},
title = {The Good Old Davis-Putnam Procedure Helps Counting Models},
year = {1999},
issue_date = {January 1999},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {10},
number = {1},
issn = {1076-9757},
abstract = {As was shown recently, many important AI problems require counting the number of models of propositional formulas. The problem of counting models of such formulas is, according to present knowledge, computationally intractable in a worst case. Based on the Davis-Putnam procedure, we present an algorithm, CDP, that computes the exact number of models of a propositional CNF or DNF formula F. Let m and n be the number of clauses and variables of F, respectively, and let p denote the probability that a literal l of F occurs in a clause C of F, then the average running time of CDP is shown to be O(mdn), where d=[-1/log2(1-p)].The practical performance of CDP has been estimated in a series of experiments on a wide variety of CNF formulas.},
journal = {J. Artif. Int. Res.},
month = jun,
pages = {457–477},
numpages = {21}
}

@article{10.5555/1622859.1622874,
author = {Barber, David and van de Laar, Pi\"{e}rre},
title = {Variational Cumulant Expansions for Intractable Distributions},
year = {1999},
issue_date = {January 1999},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {10},
number = {1},
issn = {1076-9757},
abstract = {Intractable distributions present a common difficulty in inference within the probabilistic knowledge representation framework and variational methods have recently been popular in providing an approximate solution. In this article, we describe a perturbational approach in the form of a cumulant expansion which, to lowest order, recovers the standdard Kullback-Leibler variational bound. Higher-order terms describe corrections on the variational approach without incurring much further computational cost. The relationship to other perturbational approaches such as TAP is also elucidated. We demonstrate the method on a particular class of undirected graphical models, Boltzmann machines, for which our simulation results confirm improved accuracy and enhanced stability during learning.},
journal = {J. Artif. Int. Res.},
month = jun,
pages = {435–455},
numpages = {21}
}

@article{10.5555/1622859.1622873,
author = {Borgida, Alex},
title = {Extensible Knowledge Representation: The Case of Description Reasoners},
year = {1999},
issue_date = {January 1999},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {10},
number = {1},
issn = {1076-9757},
abstract = {This paper offers an approach to extensible knowledge representation and reasoning for the Description Logic family of formalisms. The approach is based on the notion of adding new concept constructors, and includes a heuristic methodology for specifying the desired extensions, as well as a modularized software architecture that supports implementing extensions. The architecture detailed here falls in the normalize-compared paradigm, and supports both intentional reasoning (subsumption) involving concepts, and extensional reasoning involving individuals after incremental updates to the knowledge base.The resulting approach can be used to extend the reasoner with specialized notions that are motivated by specific problems or application areas, such as reasoning about dates, plans, etc. In addition, it provides an opportunity to implement constructors that are not currently yet sufficiently well understood theoretically, but are needed in practice. Also, for constructors that are provably hard to reason with (e.g., ones whose presence would lead to undecidability), it allows the implementation of incomplete reasoners where the incompleteness is tailored to be acceptable for the application at hand.},
journal = {J. Artif. Int. Res.},
month = jun,
pages = {399–434},
numpages = {36}
}

@article{10.5555/1622859.1622872,
author = {Chien, Steve and Stechert, Andre and Mutz, Darren},
title = {Efficient Heuristic Hypothesis Ranking},
year = {1999},
issue_date = {January 1999},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {10},
number = {1},
issn = {1076-9757},
abstract = {This paper considers the problem of learning the ranking of a set of stochastic alternatives based upon incomplete information (i.e., a limited number of samples). We describe a system that, at each decision cycle, outputs either a complete ordering on the hypotheses or decides to gather additional information (i.e., observations) at some cost. The ranking problem is a generalization of the previously studied hypothesis selection problem -- in selection, an algorithm must select the single best hypothesis, while in ranking, an algorithm must order all the hypotheses.The central problem we address is achieving the desired ranking quality while minimizing the cost of acquiring additional samples. We describe two algorithms for hypothesis ranking and their application for the probably approximately correct (PAC) and expected loss (EL) learning criteria. Empirical results are provided to demonstrate the effectiveness of these ranking procedures on both synthetic and real-world datasets.},
journal = {J. Artif. Int. Res.},
month = jun,
pages = {375–397},
numpages = {23}
}

@article{10.5555/1622859.1622871,
author = {Joslin, David E. and Clements, David P.},
title = {"Squeaky Wheel" Optimization},
year = {1999},
issue_date = {January 1999},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {10},
number = {1},
issn = {1076-9757},
abstract = {We describe a general approach to optimization which we term "Squeaky Wheel" Optimization (SWO). In SWO, a greedy algorithm is used to construct a solution which is then analyzed to find the trouble spots, i.e., those elements, that, if improved, are likely to improve the objective function score. The results of the analysis are used to generate new priorities that determine the order in which the greedy algorithm constructs the next solution. This Construct/Analyze/Prioritize cycle continues until some limit is reached, or an acceptable solution is found.SWO can be viewed as operating on two search spaces: solutions and prioritizations. Successive solutions are only indirectly related, via the re-prioritization that results from analyzing the prior solution. Similarly, successive prioritizations are generated by constructing and analyzing solutions. This "coupled search" has some interesting properties, which we discuss.We report encouraging experimental results on two domains, scheduling problems that arise in fiber-optic cable manufacturing, and graph coloring problems. The fact that these domains are very different supports our claim that SWO is a general technique for optimization.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {353–373},
numpages = {21}
}

@article{10.5555/1622859.1622870,
author = {Rintanen, Jussi},
title = {Constructing Conditional Plans by a Theorem-Prover},
year = {1999},
issue_date = {January 1999},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {10},
number = {1},
issn = {1076-9757},
abstract = {The research on conditional planning rejects the assumptions that there is no uncertainty or incompleteness of knowledge with respect to the state and changes of the system the plans operate on. Without these assumptions the sequences of operations that achieve the goals depend on the initial state and the outcomes of nondeterministic changes in the system. This setting raises the questions of how to represent the plans and how to perform plan search. The answers are quite different from those in the simpler classical framework. In this paper, we approach conditional planning from a new viewpoint that is motivated by the use of satisfiability algorithms in classical planning. Translating conditional planning to formulae in the propositional logic is not feasible because of inherent computational limitations. Instead, we translate conditional planning to quantified Boolean formulae. We discuss three formalizations of conditional planning as quantified Boolean formulae, and present experimental results obtained with a theorem-prover.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {323–352},
numpages = {30}
}

@article{10.5555/1622859.1622869,
author = {Jaakkola, Tommi S. and Jordan, Michael I.},
title = {Variational Probabilistic Inference and the QMR-DT Network},
year = {1999},
issue_date = {January 1999},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {10},
number = {1},
issn = {1076-9757},
abstract = {We describe a variational approximation method for efficient inference in large-scale probabilistic models. Variational methods are deterministic procedures that provide approximations to marginal and conditional probabilities of interest. They provide alternatives to approximate inference methods based on stochastic sampling or search. We describe a variational approach to the problem of diagnostic inference in the "Quick Medical Reference" (QMR) network. The QMR network is a large-scale probabilistic graphical model built on statistical and expert knowledge. Exact probabilistic inference is infeasible in this model for all but a small set of cases. We evaluate our variational inference algorithm on a large set of diagnostic test cases, comparing the algorithm to a state-of-the-art stochastic sampling method.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {291–322},
numpages = {32}
}

@article{10.5555/1622859.1622868,
author = {Ting, Kai Ming and Witten, Ian H.},
title = {Issues in Stacked Generalization},
year = {1999},
issue_date = {January 1999},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {10},
number = {1},
issn = {1076-9757},
abstract = {Stacked generalization is a general method of using a high-level model to combine lower-level models to achieve greater predictive accuracy. In this paper we address two crucial issues which have been considered to be a 'black art' in classification tasks ever since the introduction of stacked generalization in 1992 by Wolpert: the type of generalizer that is suitable to derive the higher-level model, and the kind of attributes that should be used as its input. We find that best results are obtained when the higher-level model combines the confidence (and not just the predictions) of the lower-level ones.We demonstrate the effectiveness of stacked generalization for combining three different types of learning algorithms for classification tasks. We also compare the performance of stacked generalization with majority vote and published results of arcing and bagging.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {271–289},
numpages = {19}
}

@article{10.5555/1622859.1622867,
author = {Cohen, William W. and Schapire, Robert E. and Singer, Yoram},
title = {Learning to Order Things},
year = {1999},
issue_date = {January 1999},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {10},
number = {1},
issn = {1076-9757},
abstract = {There are many applications in which it is desirable to order rather than classify instances. Here we consider the problem of learning how to order instances given feedback in the form of preference judgments, i.e., statements to the effect that one instance should be ranked ahead of another. We outline a two-stage approach in which one first learns by conventional means a binary preference function indicating whether it is advisable to rank one instance before another. Here we consider an on-line algorithm for learning preference functions that is based on Freund and Schapire's "Hedge" algorithm. In the second stage, new instances are ordered so as to maximize agreement with the learned preference function. We show that the problem of finding the ordering that agrees best with a learned preference function is NP-complete. Nevertheless, we describe simple greedy algorithms that are guaranteed to find a good approximation. Finally, we show how metasearch can be formulated as an ordering problem, and present experimental results on learning a combination of "search experts," each of which is a domain-specific query expansion strategy for a web search engine.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {243–270},
numpages = {28}
}

@article{10.5555/1622859.1622866,
author = {Lukasiewicz, Thomas},
title = {Probabilistic Deduction with Conditional Constraints over Basic Events},
year = {1999},
issue_date = {January 1999},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {10},
number = {1},
issn = {1076-9757},
abstract = {We study the problem of probabilistic deduction with conditional constraints over basic events. We show that globally complete probabilistic deduction with conditional constraints over basic events is NP-hard. We then concentrate on the special case of probabilistic deduction in conditional constraint trees. We elaborate very efficient techniques for globally complete probabilistic deduction. In detail, for conditional constraint trees with point probabilities, we present a local approach to globally complete probabilistic deduction, which runs in linear time in the size of the conditional constraint trees. For conditional constraint trees with interval probabilities, we show that globally complete probabilistic deduction can be done in a global approach by solving nonlinear programs. We show how these nonlinear programs can be transformed into equivalent linear programs, which are solvable in polynomial time in the size of the conditional constraint trees.},
journal = {J. Artif. Int. Res.},
month = apr,
pages = {199–241},
numpages = {43}
}

@article{10.5555/1622859.1622865,
author = {Fuchs, Dirk and Fuchs, Marc},
title = {Cooperation between Top-down and Bottom-up Theorem Provers},
year = {1999},
issue_date = {January 1999},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {10},
number = {1},
issn = {1076-9757},
abstract = {Top-down and bottom-up theorem proving approaches each have specific advantages and disadvantages. Bottom-up provers profit from strong redundancy control but suffer from the lack of goal-orientation, whereas top-down provers are goal-oriented but often have weak calculi when their proof lengths are considered. In order to integrate both approaches, we try to achieve cooperation between a top-down and a bottom-up prover in two different ways: The first technique aims at supporting a bottom-up with a top-down prover. A top-down prover generates subgoal clauses, they are then processed by a bottom-up prover. The second technique deals with the use of bottom-up generated lemmas in a top-down prover. We apply our concept to the areas of model elimination and superposition. We discuss the ability of our techniques to shorten proofs as well as to reorder the search space in an appropriate manner. Furthermore, in order to identify subgoal clauses and lemmas which are actually relevant for the proof task, we develop methods for a relevancy-based filtering. Experiments with the provers SETHEO and SPASS performed in the problem library TPTP reveal the high potential of our cooperation approaches.},
journal = {J. Artif. Int. Res.},
month = mar,
pages = {169–198},
numpages = {30}
}

@article{10.5555/1622859.1622864,
author = {Friedman, Nir and Halpern, Joseph Y.},
title = {Modeling Belief in Dynamic Systems Part II: Revision and Update},
year = {1999},
issue_date = {January 1999},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {10},
number = {1},
issn = {1076-9757},
abstract = {The study of belief change has been an active area in philosophy and AI. In recent years two special cases of belief change, belief revision and belief update, have been studied in detail. In a companion paper (Friedman & Halpern, 1997), we introduce a new framework to model belief change. This framework combines temporal and epistemic modalities with a notion of plausibility, allowing us to examine the change of beliefs over time. In this paper, we show how belief revision and belief update can be captured in our framework. This allows us to compare the assumptions made by each method, and to better understand the principles underlying them. In particular, it shows that Katsuno and Mendelzon's notion of belief update (Katsuno & Mendelzon, 1991a) depends on several strong assumptions that may limit its applicability in artificial intelligence. Finally, our analysis allow us to identify a notion of minimal change that underlies a broad range of belief change operations including revision and update.},
journal = {J. Artif. Int. Res.},
month = mar,
pages = {117–167},
numpages = {51}
}

@article{10.5555/1622859.1622863,
author = {Long, Derek and Fox, Maria},
title = {Efficient Implementation of the Plan Graph in STAN},
year = {1999},
issue_date = {January 1999},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {10},
number = {1},
issn = {1076-9757},
abstract = {STAN is a Graphplan-based planner, so-called because it uses a variety of STate ANalysis techniques to enhance its performance. STAN competed in the AIPS-98 planning competition where it compared well with the other competitors in terms of speed, finding solutions fastest to many of the problems posed. Although the domain analysis techniques STAN exploits are an important factor in its overall performance, we believe that the speed at which STAN solved the competition problems is largely due to the implementation of its plan graph. The implementation is based on two insights: that many of the graph construction operations can be implemented as bit-level logical operations on bit vectors, and that the graph should not be explicitly constructed beyond the fix point. This paper describes the implementation of STAN's plan graph and provides experimental results which demonstrate the circumstances under which advantages can be obtained from using this implementation.},
journal = {J. Artif. Int. Res.},
month = feb,
pages = {87–115},
numpages = {29}
}

@article{10.5555/1622859.1622862,
author = {Halpern, Joseph Y.},
title = {A Counterexample to Theorems of Cox and Fine},
year = {1999},
issue_date = {January 1999},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {10},
number = {1},
issn = {1076-9757},
abstract = {Cox's well-known theorem justifying the use of probability is shown not to hold in finite domains. The counterexample also suggests that Cox's assumptions are insufficient to prove the result even in infinite domains. The same counterexample is used to disprove a result of Fine on comparative conditional probability.},
journal = {J. Artif. Int. Res.},
month = feb,
pages = {67–85},
numpages = {19}
}

@article{10.1613/jair.790,
author = {Siskind, Jeffrey Mark},
title = {Grounding the Lexical Semantics of Verbs in Visual Perception Using Force Dynamics and Event Logic},
year = {1999},
issue_date = {July 2001},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {15},
number = {1},
issn = {1076-9757},
url = {https://doi.org/10.1613/jair.790},
doi = {10.1613/jair.790},
abstract = {This paper presents an implemented system for recognizing the occurrence of events described by simple spatial-motion verbs in short image sequences. The semantics of these verbs is specified with event-logic expressions that describe changes in the state of force-dynamic relations between the participants of the event. An efficient finite representation is introduced for the infinite sets of intervals that occur when describing liquid and semi-liquid events. Additionally, an efficient procedure using this representation is presented for inferring occurrences of compound events, described with event-logic expressions, from occurrences of primitive events. Using force dynamics and event logic to specify the lexical semantics of events allows the system to be more robust than prior systems based on motion profile.},
journal = {J. Artif. Int. Res.},
month = feb,
pages = {31–90},
numpages = {60}
}

@article{10.5555/1622859.1622860,
author = {Davis, Ernest},
title = {Order of Magnitude Comparisons of Distance},
year = {1999},
issue_date = {January 1999},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {10},
number = {1},
issn = {1076-9757},
abstract = {Order of magnitude reasoning -- reasoning by rough comparisons of the sizes of quantities -- is often called "back of the envelope calculation", with the implication that the calculations are quick though approximate. This paper exhibits an interesting class of constraint sets in which order of magnitude reasoning is demonstrably fast. Specifically, we present a polynomial-time algorithm that can solve a set of constraints of the form "Points a and b are much closer together than points c and d". We prove that this algorithm can be applied if "much closer together" is interpreted either as referring to an infinite difference in scale or as referring to a finite difference in scale, as long as the difference in scale is greater than the number of variables in the constraint set. We also prove that the first-order theory over such constraints is decidable.},
journal = {J. Artif. Int. Res.},
month = jan,
pages = {1–38},
numpages = {38}
}

@article{10.5555/1622797.1622808,
author = {Rintanen, Jussi},
title = {Complexity of Prioritized Default Logics},
year = {1998},
issue_date = {August 1998},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {9},
number = {1},
issn = {1076-9757},
abstract = {In default reasoning, usually not all possible ways of resolving conflicts between default rules are acceptable. Criteria expressing acceptable ways of resolving the conflicts may be hardwired in the inference mechanism, for example specificity in inheritance reasoning can be handled this way, or they may be given abstractly as an ordering on the default rules. In this article we investigate formalizations of the latter approach in Reiter's default logic. Our goal is to analyze and compare the computational properties of three such formalizations in terms of their computational complexity: the prioritized default logics of Baader and Hollunder, and Brewka, and a prioritized default logic that is based on lexicographic comparison. The analysis locates the propositional variants of these logics on the second and third levels of the polynomial hierarchy, and identifies the boundary between tractable and intractable inference for restricted classes of prioritized default theories.},
journal = {J. Artif. Int. Res.},
month = dec,
pages = {423–461},
numpages = {39}
}

@article{10.5555/1622797.1622807,
author = {Fox, Maria and Long, Derek},
title = {The Automatic Inference of State Invariants in TIM},
year = {1998},
issue_date = {August 1998},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {9},
number = {1},
issn = {1076-9757},
abstract = {As planning is applied to larger and richer domains the effort involved in constructing domain descriptions increases and becomes a significant burden on the human application designer. If general planners are to be applied successfully to large and complex domains it is necessary to provide the domain designer with some assistance in building correctly encoded domains. One way of doing this is to provide domain-independent techniques for extracting, from a domain description, knowledge that is implicit in that description and that can assist domain designers in debugging domain descriptions. This knowledge can also be exploited to improve the performance of planners: several researchers have explored the potential of state invariants in speeding up the performance of domain-independent planners. In this paper we describe a process by which state invariants can be extracted from the automatically inferred type structure of a domain. These techniques are being developed for exploitation by STAN, a Graphplan based planner that employs state analysis techniques to enhance its performance.},
journal = {J. Artif. Int. Res.},
month = dec,
pages = {367–421},
numpages = {55}
}

@article{10.5555/1622797.1622806,
author = {Di Caro, Gianni and Dorigo, Marco},
title = {AntNet: Distributed Stigmergetic Control for Communications Networks},
year = {1998},
issue_date = {August 1998},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {9},
number = {1},
issn = {1076-9757},
abstract = {This paper introduces AntNet, a novel approach to the adaptive learning of routing tables in communications networks. AntNet is a distributed, mobile agents based Monte Carlo system that was inspired by recent work on the ant colony metaphor for solving optimization problems. AntNet's agents concurrently explore the network and exchange collected information. The communication among the agents is indirect and asynchronous, mediated by the network itself. This form of communication is typical of social insects and is called stigmergy. We compare our algorithm with six state-of-the-art routing algorithms coming from the telecommunications and machine learning fields. The algorithms' performance is evaluated over a set of realistic testbeds. We run many experiments over real and artificial IP datagram networks with increasing number of nodes and under several paradigmatic spatial and temporal traffic distributions. Results are very encouraging. AntNet showed superior performance under all the experimental conditions with respect to its competitors. We analyze the main characteristics of the algorithm and try to explain the reasons for its superiority.},
journal = {J. Artif. Int. Res.},
month = dec,
pages = {317–365},
numpages = {49}
}

@article{10.5555/1622797.1622805,
author = {Mazer, Emmanuel and Ahuactzin, Juan Manuel and Bessi\'{e}re, Pierre},
title = {The Ariadne's Clew Algorithm},
year = {1998},
issue_date = {August 1998},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {9},
number = {1},
issn = {1076-9757},
abstract = {We present a new approach to path planning, called the "Ariadne's clew algorithm". It is designed to find paths in high-dimensional continuous spaces and applies to robots with many degrees of freedom in static, as well as dynamic environments -- ones where obstacles may move. The Ariadne's clew algorithm comprises two sub-algorithms, called SEARCH and EXPLORE, applied in an interleaved manner. EXPLORE builds a representation of the accessible space while SEARCH looks for the target. Both are posed as optimization problems. We describe a real implementation of the algorithm to plan paths for a six degrees of freedom arm in a dynamic environment where another six degrees of freedom arm is used as a moving obstacle. Experimental results show that a path is found in about one second without any pre-processing.},
journal = {J. Artif. Int. Res.},
month = dec,
pages = {295–316},
numpages = {22}
}

@article{10.5555/1622797.1622804,
author = {Wiebe, Janyce M. and O'Hara, Thomas P. and \"{O}hrstr\"{o}m-Sandgren, Thorsten and McKeever, Kenneth J.},
title = {An Empirical Approach to Temporal Reference Resolution},
year = {1998},
issue_date = {August 1998},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {9},
number = {1},
issn = {1076-9757},
abstract = {Scheduling dialogs, during which people negotiate the times of appointments, are common in everyday life. This paper reports the results of an in-depth empirical investigation of resolving explicit temporal references in scheduling dialogs. There are four phases of this work: data annotation and evaluation, model development, system implementation and evaluation, and model evaluation and analysis. The system and model were developed primarily on one set of data, and then applied later to a much more complex data set, to assess the generalizability of the model for the task being performed. Many different types of empirical methods are applied to pinpoint the strengths and weaknesses of the approach. Detailed annotation instructions were developed and an intercoder reliability study was performed, showing that naive annotators can reliably perform the targeted annotations. A fully automatic system has been developed and evaluated on unseen test data, with good results on both data sets. We adopt a pure realization of a recency-based focus model to identify precisely when it is and is not adequate for the task being addressed. In addition to system results, an in-depth evaluation of the model itself is presented, based on detailed manual annotations. The results are that few errors occur specifically due to the model of focus being used, and the set of anaphoric relations defined in the model are low in ambiguity for both data sets.},
journal = {J. Artif. Int. Res.},
month = nov,
pages = {247–294},
numpages = {48}
}

@article{10.5555/1622797.1622803,
author = {Vandegriend, Basil and Culberson, Joseph},
title = {The G<sub>n,m</sub>Phase Transition is Not Hard for the Hamiltonian Cycle Problem},
year = {1998},
issue_date = {August 1998},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {9},
number = {1},
issn = {1076-9757},
abstract = {Using an improved backtrack algorithm with sophisticated pruning techniques, we revise previous observations correlating a high frequency of hard to solve Hamiltonian cycle instances with the Gn,m phase transition between Hamiltonicity and non-Hamiltonicity. Instead all tested graphs of 100 to 1500 vertices are easily solved.When we artificially restrict the degree sequence with a bounded maximum degree, although there is some increase in difficulty, the frequency of hard graphs is still low. When we consider more regular graphs based on a generalization of knight's tours, we observe frequent instances of really hard graphs, but on these the average degree is bounded by a constant. We design a set of graphs with a feature our algorithm is unable to detect and so are very hard for our algorithm, but in these we can vary the average degree from O(1) to O(n). We have so far found no class of graphs correlated with the Gn,m phase transition which asymptotically produces a high frequency of hard instances.},
journal = {J. Artif. Int. Res.},
month = nov,
pages = {219–245},
numpages = {27}
}

@article{10.5555/1622797.1622802,
author = {Ruiz, Alberto and L\'{o}pez-de-Teruel, Pedro E. and Garrido, M. Carmen},
title = {Probabilistic Inference from Arbitrary Uncertainty Using Mixtures of Factorized Generalized Gaussians},
year = {1998},
issue_date = {August 1998},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {9},
number = {1},
issn = {1076-9757},
abstract = {This paper presents a general and efficient framework for probabilistic inference and learning from arbitrary uncertain information. It exploits the calculation properties of finite mixture models, conjugate families and factorization. Both the joint probability density of the variables and the likelihood function of the (objective or subjective) observation are approximated by a special mixture model, in such a way that any desired conditional distribution can be directly obtained without numerical integration. We have developed an extended version of the expectation maximization (EM) algorithm to estimate the parameters of mixture models from uncertain training examples (indirect observations). As a consequence, any piece of exact or uncertain information about both input and output values is consistently handled in the inference and learning stages. This ability, extremely useful in certain situations, is not found in most alternative methods. The proposed framework is formally justified from standard probabilistic principles and illustrative examples are provided in the fields of nonparametric pattern classification, nonlinear regression and pattern completion. Finally, experiments on a real application and comparative results over standard databases provide empirical evidence of the utility of the method in a wide range of applications.},
journal = {J. Artif. Int. Res.},
month = oct,
pages = {167–217},
numpages = {51}
}

@article{10.5555/1622797.1622801,
author = {Cook, Diane J. and Varnell, R. Craig},
title = {Adaptive Parallel Iterative Deepening Search},
year = {1998},
issue_date = {August 1998},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {9},
number = {1},
issn = {1076-9757},
abstract = {Many of the artificial intelligence techniques developed to date rely on heuristic search through large spaces. Unfortunately, the size of these spaces and the corresponding computational effort reduce the applicability of otherwise novel and effective algorithms. A number of parallel and distributed approaches to search have considerably improved the performance of the search process.Our goal is to develop an architecture that automatically selects parallel search strategies for optimal performance on a variety of search problems. In this paper we describe one such architecture realized in the EUREKA system, which combines the benefits of many different approaches to parallel heuristic search. Through empirical and theoretical analyses we observe that features of the problem space directly affect the choice of optimal parallel search strategy. We then employ machine learning techniques to select the optimal parallel search strategy for a given problem space. When a new search task is input to the system, EUREKA uses features describing the search space and the chosen architecture to automatically select the appropriate search strategy. EUREKA has been tested on a MIMD parallel processor, a distributed network of workstations, and a single workstation using multithreading. Results generated from fifteen puzzle problems, robot arm motion problems, artificial search spaces, and planning problems indicate that EUREKA outperforms any of the tested strategies used exclusively for all problem instances and is able to greatly reduce the search time for these applications.},
journal = {J. Artif. Int. Res.},
month = oct,
pages = {139–166},
numpages = {28}
}

@article{10.5555/1622797.1622800,
author = {B\"{a}ckstr\"{o}m, Christer},
title = {Computational Aspects of Reordering Plans},
year = {1998},
issue_date = {August 1998},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {9},
number = {1},
issn = {1076-9757},
abstract = {This article studies the problem of modifying the action ordering of a plan in order to optimise the plan according to various criteria. One of these criteria is to make a plan less constrained and the other is to minimize its parallel execution time. Three candidate definitions are proposed for the first of these criteria, constituting a sequence of increasing optimality guarantees. Two of these are based on deordering plans, which means that ordering relations may only be removed, not added, while the third one uses reordering, where arbitrary modifications to the ordering are allowed. It is shown that only the weakest one of the three criteria is tractable to achieve, the other two being NP-hard and even difficult to approximate. Similarly, optimising the parallel execution time of a plan is studied both for deordering and reordering of plans. In the general case, both of these computations are NP-hard. However, it is shown that optimal deorderings can be computed in polynomial time for a class of planning languages based on the notions of producers, consumers and threats, which includes most of the commonly used planning languages. Computing optimal reorderings can potentially lead to even faster parallel executions, but this problem remains NP-hard and difficult to approximate even under quite severe restrictions.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {99–137},
numpages = {39}
}

@article{10.5555/1622797.1622799,
author = {Ledeniov, Oleg and Markovitch, Shaul},
title = {The Divide-and-Conquer Subgoal-Ordering Algorithm for Speeding up Logic Inference},
year = {1998},
issue_date = {August 1998},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {9},
number = {1},
issn = {1076-9757},
abstract = {It is common to view programs as a combination of logic and control: the logic part defines what the program must do, the control part - how to do it. The Logic Programming paradigm was developed with the intention of separating the logic from the control. Recently, extensive research has been conducted on automatic generation of control for logic programs. Only a few of these works considered the issue of automatic generation of control for improving the efficiency of logic programs. In this paper we present a novel algorithm for automatic finding of lowest-cost subgoal orderings. The algorithm works using the divide-and-conquer strategy. The given set of subgoals is partitioned into smaller sets, based on co-occurrence of free variables. The subsets are ordered recursively and merged, yielding a provably optimal order. We experimentally demonstrate the utility of the algorithm by testing it in several domains, and discuss the possibilities of its cooperation with other existing methods.},
journal = {J. Artif. Int. Res.},
month = sep,
pages = {37–97},
numpages = {61}
}

@article{10.5555/1622797.1622809,
author = {Artale, Alessandro and Franconi, Enrico},
title = {A Temporal Description Logic for Reasoning about Actions and Plans},
year = {1998},
issue_date = {August 1998},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {9},
number = {1},
issn = {1076-9757},
abstract = {A class of interval-based temporal languages for uniformly representing and reasoning about actions and plans is presented. Actions are represented by describing what is true while the action itself is occurring, and plans are constructed by temporally relating actions and world states. The temporal languages are members of the family of Description Logics, which are characterized by high expressivity combined with good computational properties. The subsumption problem for a class of temporal Description Logics is investigated and sound and complete decision procedures are given. The basic language TL-F is considered first: it is the composition of a temporal logic TL - able to express interval temporal networks - together with the non-temporal logic F - a Feature Description Logic. It is proven that subsumption in this language is an NP-complete problem. Then it is shown how to reason with the more expressive languages TLU-FU and TL-ALCF. The former adds disjunction both at the temporal and non-temporal sides of the language, the latter extends the non-temporal side with set-valued features (i.e., roles) and a propositionally complete language.},
journal = {J. Artif. Int. Res.},
month = aug,
pages = {463–506},
numpages = {44}
}

@article{10.5555/1622797.1622798,
author = {Littman, Michael L. and Goldsmith, Judy and Mundhenk, Martin},
title = {The Computational Complexity of Probabilistic Planning},
year = {1998},
issue_date = {August 1998},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {9},
number = {1},
issn = {1076-9757},
abstract = {We examine the computational complexity of testing and finding small plans in probabilistic planning domains with both flat and propositional representations. The complexity of plan evaluation and existence varies with the plan type sought; we examine totally ordered plans, acyclic plans, and looping plans, and partially ordered plans under three natural definitions of plan value. We show that problems of interest are complete for a variety of complexity classes: PL, P, NP, co-NP, PP, NPPP, co-NPPP, and PSPACE. In the process of proving that certain planning problems are complete for NPPP, we introduce a new basic NPPP -complete problem, E-MAJSAT, which generalizes the standard Boolean satisfiability problem to computations involving probabilistic quantities; our results suggest that the development of good heuristics for E-MAJSAT could be important for the creation of efficient algorithms for a wide variety of problems.},
journal = {J. Artif. Int. Res.},
month = aug,
pages = {1–36},
numpages = {36}
}

@article{10.5555/1622788.1622796,
author = {Finkelstein, Lev and Markovitch, Shaul},
title = {A Selective Macro-Learning Algorithm and Its Application to the N \texttimes{} N Sliding-Tile Puzzle},
year = {1998},
issue_date = {January 1998},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {8},
number = {1},
issn = {1076-9757},
abstract = {One of the most common mechanisms used for speeding up problem solvers is macro-learning. Macros are sequences of basic operators acquired during problem solving. Macros are used by the problem solver as if they were basic operators. The major problem that macro-learning presents is the vast number of macros that are available for acquisition. Macros increase the branching factor of the search space and can severely degrade problem-solving efficiency. To make macro learning useful, a program must be selective in acquiring and utilizing macros. This paper describes a general method for selective acquisition of macros. Solvable training problems are generated in increasing order of difficulty. The only macros acquired are those that take the problem solver out of a local minimum to a better state. The utility of the method is demonstrated in several domains, including the domain of N \texttimes{} N sliding-tile puzzles. After learning on small puzzles, the system is able to efficiently solve puzzles of any size.},
journal = {J. Artif. Int. Res.},
month = jun,
pages = {223–263},
numpages = {41}
}

@article{10.5555/1622788.1622795,
author = {Darwiche, Adnan},
title = {Model-Based Diagnosis Using Structured System Descriptions},
year = {1998},
issue_date = {January 1998},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {8},
number = {1},
issn = {1076-9757},
abstract = {This paper presents a comprehensive approach for model-based diagnosis which includes proposals for characterizing and computing preferred diagnoses, assuming that the system description is augmented with a system structure (a directed graph explicating the interconnections between system components). Specifically, we first introduce the notion of a consequence, which is a syntactically unconstrained propositional sentence that characterizes all consistency-based diagnoses and show that standard characterizations of diagnoses, such as minimal conflicts, correspond to syntactic variations on a consequence. Second, we propose a new syntactic variation on the consequence known as negation normal form (NNF) and discuss its merits compared to standard variations. Third, we introduce a basic algorithm for computing consequences in NNF given a structured system description. We show that if the system structure does not contain cycles, then there is always a linear-size consequence in NNF which can be computed in linear time. For arbitrary system structures, we show a precise connection between the complexity of computing consequences and the topology of the underlying system structure. Finally, we present an algorithm that enumerates the preferred diagnoses characterized by a consequence. The algorithm is shown to take linear time in the size of the consequence if the preference criterion satisfies some general conditions.},
journal = {J. Artif. Int. Res.},
month = jun,
pages = {165–222},
numpages = {58}
}

@article{10.5555/1622788.1622794,
author = {F\"{u}rnkranz, Johannes},
title = {Integrative Windowing},
year = {1998},
issue_date = {January 1998},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {8},
number = {1},
issn = {1076-9757},
abstract = {In this paper we re-investigate windowing for rule learning algorithms. We show that, contrary to previous results for decision tree learning, windowing can in fact achieve significant run-time gains in noise-free domains and explain the different behaviour of rule learning algorithms by the fact that they learn each rule independently. The main contribution of this paper is integrative windowing, a new type of algorithm that further exploits this property by integrating good rules into the final theory right after they have been discovered. Thus it avoids re-learning these rules in subsequent iterations of the windowing process. Experimental evidence in a variety of noise-free domains shows that integrative windowing can in fact achieve substantial run-time gains. Furthermore, we discuss the problem of noise in windowing and present an algorithm that is able to archieve run-time gains in a set of experiments in a simple domain with artificial noise.},
journal = {J. Artif. Int. Res.},
month = may,
pages = {129–164},
numpages = {36}
}

@article{10.5555/1622788.1622793,
author = {Srivastava, Biplav and Kambhampati, Subbarao},
title = {Synthesizing Customized Planners from Specifications},
year = {1998},
issue_date = {January 1998},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {8},
number = {1},
issn = {1076-9757},
abstract = {Existing plan synthesis approaches in artificial intelligence fall into two categories - domain independent and domain dependent. The domain independent approaches are applicable across a variety of domains, but may not be very efficient in any one given domain. The domain dependent approaches need to be (re)designed for each domain separately, but can be very efficient in the domain for which they are designed. One enticing alternative to these approaches is to automatically synthesize domain independent planners given the knowledge about the domain and the theory of planning. In this paper, we investigate the feasibility of using existing automated software synthesis tools to support such synthesis. Specifically, we describe an architecture called CLAY in which the Kestrel Interactive Development System (KIDS) is used to derive a domain-customized planner through a semi-automatic combination of a declarative theory of planning, and the declarative control knowledge specific to a given domain, to semi-automatically combine them to derive domain-customized planners. We discuss what it means to write a declarative theory of planning and control knowledge for KIDS, and illustrate our approach by generating a class of domain-specific planners using state space refinements. Our experiments show that the synthesized planners can outperform classical refinement planners (implemented as instantiations of UCP, Kambhampati & Srivastava, 1995), using the same control knowledge. We will contrast the costs and benefits of the synthesis approach with conventional methods for customizing domain independent planners.},
journal = {J. Artif. Int. Res.},
month = mar,
pages = {93–128},
numpages = {36}
}

@article{10.5555/1622788.1622792,
author = {Moore, Andrew and Lee, Mary Soon},
title = {Cached Sufficient Statistics for Efficient Machine Learning with Large Datasets},
year = {1998},
issue_date = {January 1998},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {8},
number = {1},
issn = {1076-9757},
abstract = {This paper introduces new algorithms and data structures for quick counting for machine learning datasets. We focus on the counting task of constructing contingency tables, but our approach is also applicable to counting the number of records in a dataset that match conjunctive queries. Subject to certain assumptions, the costs of these operations can be shown to be independent of the number of records in the dataset and loglinear in the number of non-zero entries in the contingency table.We provide a very sparse data structure, the ADtree, to minimize memory use. We provide analytical worst-case bounds for this structure for several models of data distribution. We empirically demonstrate that tractably-sized data structures can be produced for large real-world datasets by (a) using a sparse tree structure that never allocates memory for counts of zero, (b) never allocating memory for counts that can be deduced from other counts, and (c) not bothering to expand the tree fully near its leaves.We show how the ADtree can be used to accelerate Bayes net structure finding algorithms, rule learning algorithms, and feature selection algorithms, and we provide a number of empirical results comparing ADtree methods against traditional direct counting approaches. We also discuss the possible uses of ADtrees in other machine learning methods, and discuss the merits of ADtrees in comparison with alternative representations such as kd-trees, R-trees and Frequent Sets.},
journal = {J. Artif. Int. Res.},
month = mar,
pages = {67–91},
numpages = {25}
}

@article{10.5555/1622788.1622791,
author = {Argamon-Engelson, Shlomo and Koppel, Moshe},
title = {Tractability of Theory Patching},
year = {1998},
issue_date = {January 1998},
publisher = {AI Access Foundation},
address = {El Segundo, CA, USA},
volume = {8},
number = {1},
issn = {1076-9757},
abstract = {In this paper we consider the problem of theory patching, in which we are given a domain theory, some of whose components are indicated to be possibly flawed, and a set of labeled training examples for the domain concept. The theory patching problem is to revise only the indicated components of the theory, such that the resulting theory correctly classifies all the training examples. Theory patching is thus a type of theory revision in which revisions are made to individual components of the theory. Our concern in this paper is to determine for which classes of logical domain theories the theory patching problem is tractable. We consider both propositional and first-order domain theories, and show that the theory patching problem is equivalent to that of determining what information contained in a theory is stable regardless of what revisions might be performed to the theory. We show that determining stability is tractable if the input

license_type: permissive

branch_name: refs/heads/main

extension: bib