Journal of Artificial Intelligence
		 Complete Table of Contents (with abstracts)

   			       Volume1

Wellman, M.P. (1993)
  "A Market-Oriented Programming Environment and its Application to
   Distributed Multicommodity Flow Problems", Volume 1, pages 1-23.
   PostScript: volume1/wellman93a.ps (348K)
   PDF: volume1/wellman93a.pdf (265K)

   Abstract: Market price systems constitute a well-understood class of
   mechanisms that under certain conditions provide effective
   decentralization of decision making with minimal communication
   overhead.  In a {\em market-oriented programming\/} approach to
   distributed problem solving, we derive the activities and resource
   allocations for a set of computational agents by computing the
   competitive equilibrium of an artificial economy.  {\sc Walras}
   provides basic constructs for defining computational market
   structures, and protocols for deriving their corresponding price
   equilibria.  In a particular realization of this approach for a form
   of multicommodity flow problem, we see that careful construction of
   the decision process according to economic principles can lead to
   efficient distributed resource allocation, and that the behavior of
   the system can be meaningfully analyzed in economic terms.


Ginsberg, M.L. (1993)
  "Dynamic Backtracking", Volume 1, pages 25-46.
   PostScript: volume1/ginsberg93a.ps (211K)
   Online Appendix: volume1/ginsberg93a-appendix.lisp (7K), Crossword data
   PDF: volume1/ginsberg93a.pdf (244K)

   Abstract: Because of their occasional need to return to shallow points
   in a search tree, existing backtracking methods can sometimes erase
   meaningful progress toward solving a search problem.  In this paper,
   we present a method by which backtrack points can be moved deeper in
   the search space, thereby avoiding this difficulty.  The technique
   developed is a variant of dependency-directed backtracking that uses
   only polynomial space while still providing useful control information
   and retaining the completeness guarantees provided by earlier
   approaches.

   
Gent, I.P. and Walsh, T. (1993)
  "An Empirical Analysis of Search in GSAT",  Volume 1, pages 47-59.
   PostScript: volume1/gent93a.ps (500K)
   PDF: volume1/gent93a.pdf (234K)
  
   Abstract: We describe an extensive study of search in GSAT, an
   approximation procedure for propositional satisfiability. GSAT
   performs greedy hill-climbing on the number of satisfied clauses in a
   truth assignment.  Our experiments provide a more complete picture of
   GSAT's search than previous accounts. We describe in detail the two
   phases of search: rapid hill-climbing followed by a long plateau
   search.  We demonstrate that when applied to randomly generated 3SAT
   problems, there is a very simple scaling with problem size for both
   the mean number of satisfied clauses and the mean branching rate.  Our
   results allow us to make detailed numerical conjectures about the
   length of the hill-climbing phase, the average gradient of this phase,
   and to conjecture that both the average score and average branching
   rate decay exponentially during plateau search.  We end by showing how
   these results can be used to direct future theoretical analysis.  This
   work provides a case study of how computer experiments can be used to
   improve understanding of the theoretical properties of algorithms.


Schlimmer, J.C. and Hermens, L.A. (1993)
  "Software Agents: Completing Patterns and Constructing User Interfaces",
   Volume 1, pages 61-89.
   PostScript: volume1/schlimmer93a.ps (1.2 M)
               compressed, volume1/schlimmer93a.ps.Z (278K)
   Online Appendix: volume1/schlimmer93a-appendix.hqx (1.3M), Quicktime Demo
   PDF: volume1/schlimmer93a.pdf (160K)

   Abstract: To support the goal of allowing users to record and retrieve
   information, this paper describes an interactive note-taking system
   for pen-based computers with two distinctive features. First, it
   actively predicts what the user is going to write. Second, it
   automatically constructs a custom, button-box user interface on
   request. The system is an example of a learning-apprentice software-
   agent. A machine learning component characterizes the syntax and
   semantics of the user's information. A performance system uses this
   learned information to generate completion strings and construct a
   user interface.

   Description of Online Appendix: People like to record information. Doing 
   this on paper is initially efficient, but lacks flexibility. Recording
   information on a computer is less efficient but more powerful. In our
   new note taking softwre, the user records information directly on a
   computer. Behind the interface, an agent acts for the user. To help,
   it provides defaults and constructs a custom user interface.
       The demonstration is a QuickTime movie of the note taking agent in
   action.  The file is a binhexed self-extracting archive. Macintosh
   utilities for binhex are available from mac.archive.umich.edu. QuickTime 
   is available from ftp.apple.com in the dts/mac/sys.soft/quicktime.


Bergadano, F., Gunetti, D. and Trinchero, U. (1993)
  "The Difficulties of Learning Logic Programs with Cut", Volume 1, 
   pages 91-107.
   PostScript: volume1/bergadano93a.ps (185K)
   PDF: volume1/bergadano93a.pdf (214K)

   Abstract: As real logic programmers normally use cut (!), an
   effective learning procedure for logic programs should be able to deal
   with it.  Because the cut predicate has only a procedural meaning,
   clauses containing cut cannot be learned using an extensional
   evaluation method, as is done in most learning systems.  On the other
   hand, searching a space of possible programs (instead of a space of
   independent clauses) is unfeasible.  An alternative solution is to
   generate first a candidate base program which covers the positive
   examples, and then make it consistent by inserting cut where
   appropriate.  The problem of learning programs with cut has not been
   investigated before and this seems to be a natural and reasonable
   approach. We generalize this scheme and investigate the difficulties
   that arise.  Some of the major shortcomings are actually caused, in
   general, by the need for intensional evaluation. As a conclusion, the
   analysis of this paper suggests, on precise and technical grounds,
   that learning cut is difficult, and current induction techniques
   should probably be restricted to purely declarative logic languages.
   

Buchheit, M., Donini, F.M. and Schaerf, A.  (1993)
  "Decidable Reasoning in Terminological Knowledge Representation Systems",
   Volume 1, pages 109-138.
   PostScript: volume1/buchheit93a.ps (311K)
   PDF: volume1/buchheit93a.pdf (336K)

   Abstract: Terminological knowledge representation systems (TKRSs) are
   tools for designing and using knowledge bases that make use of
   terminological languages (or concept languages).  We analyze from a
   theoretical point of view a TKRS whose capabilities go beyond the ones
   of presently available TKRSs. The new features studied, often required
   in practical applications, can be summarized in three main points.
   First, we consider a highly expressive terminological language, called
   ALCNR, including general complements of concepts, number restrictions
   and role conjunction. Second, we allow to express inclusion statements
   between general concepts, and terminological cycles as a particular
   case.  Third, we prove the decidability of a number of desirable
   TKRS-deduction services (like satisfiability, subsumption and instance
   checking) through a sound, complete and terminating calculus for
   reasoning in ALCNR-knowledge bases. Our calculus extends the general
   technique of constraint systems.  As a byproduct of the proof, we get
   also the result that inclusion statements in ALCNR can be simulated
   by terminological cycles, if descriptive semantics is adopted.


Nilsson, N. (1994)
  "Teleo-Reactive Programs for Agent Control", Volume 1, pages 139-158.
   PostScript: volume1/nilsson94a.ps (477K)
               compressed, volume1/nilsson94a.ps.Z (155K)
   PDF: volume1/nilsson94a.pdf (259K)

   Abstract: A formalism is presented for computing and organizing actions 
   for autonomous agents in dynamic environments. We introduce the notion 
   of {\it teleo-reactive (T-R) programs} whose execution entails the
   construction of circuitry for the continuous computation of the
   parameters and conditions on which agent action is based.  In addition
   to continuous feedback, T-R programs support parameter binding and
   recursion.  A primary difference between T-R programs and many other
   circuit-based systems is that the circuitry of T-R programs is more
   compact; it is constructed at run time and thus does not have to
   anticipate all the contingencies that might arise over all possible
   runs.  In addition, T-R programs are intuitive and easy to write and
   are written in a form that is compatible with automatic planning and
   learning methods.  We briefly describe some experimental applications
   of T-R programs in the control of simulated and actual mobile robots.


Koppel, M., Feldman R. and Segre, A.M.  (1994)
  "Bias-Driven Revision of Logical Domain Theories", Volume 1, pages 159-208.
   PostScript: volume1/koppel94a.ps (465K)
               compressed, volume1/koppel94a.ps.Z (203K)
   PDF: volume1/koppel94a.pdf (257K)

   Abstract: The theory revision problem is the problem of how best to
   go about revising a deficient domain theory using information
   contained in examples that expose inaccuracies.  In this paper we
   present our approach to the theory revision problem for propositional
   domain theories.  The approach described here, called PTR, uses
   probabilities associated with domain theory elements to numerically
   track the ``flow'' of proof through the theory.  This allows us to
   measure the precise role of a clause or literal in allowing or
   preventing a (desired or undesired) derivation for a given example.
   This information is used to efficiently locate and repair flawed
   elements of the theory.  PTR is proved to converge to a theory which
   correctly classifies all examples, and shown experimentally to be fast
   and accurate even for deep theories.

Ling, C.X.  (1994)
  "Learning the Past Tense of English Verbs: The Symbolic Pattern Associator
   vs. Connectionist Models", Volume 1, pages 209-229.
   PostScript: volume1/ling94a.ps (247K)
   Online Appendix: volume1/ling94a-appendix.Z (109K) data file, compressed
   PDF: volume1/ling94a.pdf (268K)

   Abstract: Learning the past tense of English verbs - a seemingly minor
   aspect of language acquisition - has generated heated debates since
   1986, and has become a landmark task for testing the adequacy of
   cognitive modeling. Several artificial neural networks (ANNs) have
   been implemented, and a challenge for better symbolic models has been
   posed.  In this paper, we present a general-purpose Symbolic Pattern
   Associator (SPA) based upon the decision-tree learning algorithm ID3.
   We conduct extensive head-to-head comparisons on the generalization
   ability between ANN models and the SPA under different
   representations. We conclude that the SPA generalizes the past tense
   of unseen verbs better than ANN models by a wide margin, and we offer
   insights as to why this should be the case.  We also discuss a new
   default strategy for decision-tree learning algorithms.


Cook, D.J. and Holder, L.B. (1994)
  "Substructure Discovery Using Minimum Description Length and Background
   Knowledge", Volume 1, pages 231-255.
   PostScript: volume1/cook94a.ps (750K)
	       compressed, volume1/cook94a.ps.Z (266K)
   Online Appendix: volume1/cook94a-appendix.tar.Z (36K), SUBDUE source code
   PDF: volume1/cook94a.pdf (285K)

   Abstract: The ability to identify interesting and repetitive
   substructures is an essential component to discovering knowledge in
   structural data.  We describe a new version of our SUBDUE substructure
   discovery system based on the minimum description length principle.
   The SUBDUE system discovers substructures that compress the original
   data and represent structural concepts in the data.  By replacing
   previously-discovered substructures in the data, multiple passes of
   SUBDUE produce a hierarchical description of the structural
   regularities in the data.  SUBDUE uses a computationally-bounded
   inexact graph match that identifies similar, but not identical,
   instances of a substructure and finds an approximate measure of
   closeness of two substructures when under computational constraints.
   In addition to the minimum description length principle, other
   background knowledge can be used by SUBDUE to guide the search towards
   more appropriate substructures.  Experiments in a variety of domains
   demonstrate SUBDUE's ability to find substructures capable of
   compressing the original data and to discover structural concepts
   important to the domain.

   Description of Online Appendix: This is a compressed tar file containing
   the SUBDUE discovery system, written in C.  The program accepts as
   input databases represented in graph form, and will output discovered
   substructures with their corresponding value.


Murphy, P.M. and Pazzani, M.J. (1994)
  "Exploring the Decision Forest: An Empirical Investigation of Occam's 
   Razor in Decision Tree Induction", Volume 1, pages 257-275.
   PostScript: volume1/murphy94a.ps (868K)
	       compressed, volume1/murphy94a.ps.Z (215K)
   PDF: volume1/murphy94a.pdf (480K)

   Abstract: We report on a series of experiments in which all decision
   trees consistent with the training data are constructed. These
   experiments were run to gain an understanding of the properties of the
   set of consistent decision trees and the factors that affect the
   accuracy of individual trees. In particular, we investigated the
   relationship between the size of a decision tree consistent with some
   training data and the accuracy of the tree on test data. The
   experiments were performed on a massively parallel Maspar computer.
   The results of the experiments on several artificial and two real
   world problems indicate that, for many of the problems investigated,
   smaller consistent decision trees are on average less accurate than
   the average accuracy of slightly larger trees.


Borgida, A. and Patel-Schneider, P.F. (1994)
  "A Semantics and Complete Algorithm for Subsumption in the CLASSIC 
   Description Logic", Volume 1, pages 277-308.
   PostScript: volume1/borgida94a.ps (319K)
   PDF: volume1/borgida94a.pdf (349K)

   Abstract: This paper analyzes the correctness of the subsumption
   algorithm used in CLASSIC, a description logic-based knowledge
   representation system that is being used in practical applications.
   In order to deal efficiently with individuals in CLASSIC descriptions,
   the developers have had to use an algorithm that is incomplete with
   respect to the standard, model-theoretic semantics for description
   logics. We provide a variant semantics for descriptions with respect
   to which the current implementation is complete, and which can be
   independently motivated.  The soundness and completeness of the
   polynomial-time subsumption algorithm is established using description
   graphs, which are an abstracted version of the implementation
   structures used in CLASSIC, and are of independent interest.


Sebastiani, R. (1994)
  "Applying GSAT to Non-Clausal Formulas" (Research Note), Volume 1, 
   pages 309-314.
   PostScript: volume1/sebastiani94a.ps (144K)
   PDF: volume1/sebastiani94a.pdf (175K)

   Abstract: In this paper we describe how to modify GSAT so that it can
   be applied to non-clausal formulas. The idea is to use a particular
   ``score'' function which gives the number of clauses of the CNF
   conversion of a formula which are false under a given truth assignment. 
   Its value is computed in linear time, without constructing the CNF
   conversion itself.  The proposed methodology applies to most of the
   variants of GSAT proposed so far.



	  		          Volume2


Murthy, S.K., Kasif, S. and Salzberg, S. (1994)
  "A System for Induction of Oblique Decision Trees", Volume 2, pages 1-32.
   PostScript: volume2/murthy94a.ps (475K)
   Online Appendix: volume2/murthy94a-appendix.tar.Z (297K), OC1 source code
   PDF: volume2/murthy94a.pdf (373K)

   Abstract: This article describes a new system for induction of oblique
   decision trees.  This system, OC1, combines deterministic
   hill-climbing with two forms of randomization to find a good oblique
   split (in the form of a hyperplane) at each node of a decision tree.
   Oblique decision tree methods are tuned especially for domains in
   which the attributes are numeric, although they can be adapted to
   symbolic or mixed symbolic/numeric attributes.  We present extensive
   empirical studies, using both real and artificial data, that analyze
   OC1's ability to construct oblique trees that are smaller and more
   accurate than their axis-parallel counterparts.  We also examine the
   benefits of randomization for the construction of oblique decision trees.
   

Grove, A.J., Halpern, J.Y. and Koller, D. (1994)
  "Random Worlds and Maximum Entropy", Volume 2, pages 33-88.
   PostScript: volume2/grove94a.ps (624K)
	       compressed, volume2/grove94a.ps.Z (243K)
   PDF: volume2/grove94a.pdf (2.6M)

   Abstract: Given a knowledge base KB containing first-order and
   statistical facts, we consider a principled method, called the
   random-worlds method, for computing a degree of belief that some
   formula Phi holds given KB.  If we are reasoning about a world or
   system consisting of N individuals, then we can consider all possible
   worlds, or first-order models, with domain {1,...,N} that satisfy KB,
   and compute the fraction of them in which Phi is true. We define the
   degree of belief to be the asymptotic value of this fraction as N
   grows large.  We show that when the vocabulary underlying Phi and KB
   uses constants and unary predicates only, we can naturally associate
   an entropy with each world. As N grows larger, there are many more
   worlds with higher entropy.  Therefore, we can use a maximum-entropy
   computation to compute the degree of belief.  This result is in a
   similar spirit to previous work in physics and artificial
   intelligence, but is far more general.  Of equal interest to the
   result itself are the limitations on its scope.  Most importantly, the
   restriction to unary predicates seems necessary.  Although the
   random-worlds method makes sense in general, the connection to maximum
   entropy seems to disappear in the non-unary case.  These observations
   suggest unexpected limitations to the applicability of maximum-entropy 
   methods.


Kitani, T., Eriguchi, Y. and Hara, M. (1994)
  "Pattern Matching and Discourse Processing in Information Extraction
   from Japanese Text", Volume 2, pages 89-110.
   PostScript: volume2/kitani94a.ps (465K)
   PDF: volume2/kitani94a.pdf (547K)

   Abstract: Information extraction is the task of automatically picking
   up information of interest from an unconstrained text.  Information of
   interest is usually extracted in two steps.  First, sentence level
   processing locates relevant pieces of information scattered throughout
   the text; second, discourse processing merges coreferential
   information to generate the output.  In the first step, pieces of
   information are locally identified without recognizing any
   relationships among them.  A key word search or simple pattern search
   can achieve this purpose.  The second step requires deeper knowledge
   in order to understand relationships among separately identified
   pieces of information.  Previous information extraction systems
   focused on the first step, partly because they were not required to
   link up each piece of information with other pieces.  To link the
   extracted pieces of information and map them onto a structured output
   format, complex discourse processing is essential.  This paper reports
   on a Japanese information extraction system that merges information
   using a pattern matcher and discourse processor.  Evaluation results
   show a high level of system performance which approaches human performance.


Safra, S. and Tennenholtz, M. (1994)
  "On Planning while Learning", Volume 2, pages 111-129.
   PostScript: volume2/safra94a.ps (202K)
   PDF: volume2/safra94a.pdf (733K)

   Abstract: This paper introduces a framework for Planning while
   Learning where an agent is given a goal to achieve in an environment
   whose behavior is only partially known to the agent.
      We discuss the tractability of various plan-design processes. We
   show that for a large natural class of Planning while Learning
   systems, a plan can be presented and verified in a reasonable time.
   However, coming up algorithmically with a plan, even for simple
   classes of systems is apparently intractable.
      We emphasize the role of off-line plan-design processes, and show
   that, in most natural cases, the verification (projection) part can be
   carried out in an efficient algorithmic manner.


Soderland, S. and Lehnert. W. (1994)
  "Wrap-Up: a Trainable Discourse Module for Information Extraction", 
   Volume 2, pages 131-158.
   PostScript: volume2/soderland4a.ps (442K)
   PDF: volume2/soderland94a.pdf (234K)

   Abstract: The vast amounts of on-line text now available have led to
   renewed interest in information extraction (IE) systems that analyze
   unrestricted text, producing a structured representation of selected
   information from the text. This paper presents a novel approach that
   uses machine learning to acquire knowledge for some of the higher
   level IE processing.  Wrap-Up is a trainable IE discourse component
   that makes intersentential inferences and identifies logical relations
   among information extracted from the text.  Previous corpus-based
   approaches were limited to lower level processing such as
   part-of-speech tagging, lexical disambiguation, and dictionary
   construction.  Wrap-Up is fully trainable, and not only automatically
   decides what classifiers are needed, but even derives the feature set
   for each classifier automatically. Performance equals that of a
   partially trainable discourse module requiring manual customization
   for each domain.


Buntine, W.L. (1994)
  "Operations for Learning with Graphical Models", Volume 2, pages 159-225.
   PostScript: volume2/buntine94a.ps (1.53M)
               compressed, volume2/buntine94a.ps.Z (568K)
   PDF: volume2/buntine94a.pdf (2.9M)

   Abstract: This paper is a multidisciplinary review of empirical,
   statistical learning from a graphical model perspective.  Well-known
   examples of graphical models include Bayesian networks, directed
   graphs representing a Markov chain, and undirected networks
   representing a Markov field.  These graphical models are extended to
   model data analysis and empirical learning using the notation of
   plates.  Graphical operations for simplifying and manipulating a
   problem are provided including decomposition, differentiation, and the
   manipulation of probability models from the exponential family.  Two
   standard algorithm schemas for learning are reviewed in a graphical
   framework: Gibbs sampling and the expectation maximization algorithm.
   Using these operations and schemas, some popular algorithms can be
   synthesized from their graphical specification.  This includes
   versions of linear regression, techniques for feed-forward networks,
   and learning Gaussian and discrete Bayesian networks from data.  The
   paper concludes by sketching some implications for data analysis and
   summarizing how some popular algorithms fall within the framework
   presented.
  
   The main original contributions here are the decomposition techniques
   and the demonstration that graphical models provide a framework for
   understanding and developing complex learning algorithms.


Minton, S., Bresina, J. and Drummond, M. (1994)
  "Total-Order and Partial-Order Planning: A Comparative Analysis",
   Volume 2, pages 227-262.
   PostScript: volume2/minton94a.ps (520K)
   Online Appendix: volume2/minton94a-appendix.tar.Z (64K), source code & data
   HTML: www.cs.washington.edu/research/jair/volume2/minton94a-html/paper.html
   PDF: volume2/minton94a.pdf (391K)

   Abstract: For many years, the intuitions underlying partial-order
   planning were largely taken for granted. Only in the past few years
   has there been renewed interest in the fundamental principles
   underlying this paradigm.  In this paper, we present a rigorous
   comparative analysis of partial-order and total-order planning by
   focusing on two specific planners that can be directly compared. We
   show that there are some subtle assumptions that underly the
   wide-spread intuitions regarding the supposed efficiency of
   partial-order planning. For instance, the superiority of partial-order
   planning can depend critically upon the search strategy and the
   structure of the search space.  Understanding the underlying
   assumptions is crucial for constructing efficient planners.


Dietterich, T.G. and Bakiri, G. (1995)
  "Solving Multiclass Learning Problems via Error-Correcting Output Codes",
   Volume 2, pages 263-286.
   PostScript: volume2/dietterich95a.ps (265K)
   PDF: volume2/dietterich95a.pdf (259K)
  
   Abstract: Multiclass learning problems involve finding a definition
   for an unknown function f(x) whose range is a discrete set containing
   k>2 values (i.e., k ``classes'').  The definition is acquired by
   studying collections of training examples of the form <x_i, f(x_i)>.
   Existing approaches to multiclass learning problems include direct
   application of multiclass algorithms such as the decision-tree
   algorithms C4.5 and CART, application of binary concept learning
   algorithms to learn individual binary functions for each of the k
   classes, and application of binary concept learning algorithms with
   distributed output representations.  This paper compares these three
   approaches to a new technique in which error-correcting codes are
   employed as a distributed output representation.  We show that these
   output representations improve the generalization performance of both
   C4.5 and backpropagation on a wide range of multiclass learning tasks.
   We also demonstrate that this approach is robust with respect to
   changes in the size of the training sample, the assignment of
   distributed representations to particular classes, and the application
   of overfitting avoidance techniques such as decision-tree pruning.
   Finally, we show that---like the other methods---the error-correcting
   code technique can provide reliable class probability estimates.
   Taken together, these results demonstrate that error-correcting output
   codes provide a general-purpose method for improving the performance
   of inductive learning programs on multiclass problems.


Cichosz, P. (1995)
  "Truncating Temporal Differences: On the Efficient Implementation of 
   TD(lambda) for Reinforcement Learning", Volume 2, pages 287-318.
   PostScript: volume2/cichosz95a.ps (313K)
   PDF: volume2/cichosz95a.pdf (350K)

   Abstract: Temporal difference (TD) methods constitute a class of
   methods for learning predictions in multi-step prediction problems,
   parameterized by a recency factor lambda. Currently the most important
   application of these methods is to temporal credit assignment in
   reinforcement learning. Well known reinforcement learning algorithms,
   such as AHC or Q-learning, may be viewed as instances of TD learning.
   This paper examines the issues of the efficient and general
   implementation of TD(lambda) for arbitrary lambda, for use with
   reinforcement learning algorithms optimizing the discounted sum of
   rewards. The traditional approach, based on eligibility traces, is
   argued to suffer from both inefficiency and lack of generality. The
   TTD (Truncated Temporal Differences) procedure is proposed as an
   alternative, that indeed only approximates TD(lambda), but requires
   very little computation per action and can be used with arbitrary
   function representation methods.  The idea from which it is derived is
   fairly simple and not new, but probably unexplored so far. Encouraging
   experimental results are presented, suggesting that using lambda>0
   with the TTD procedure allows one to obtain a significant learning
   speedup at essentially the same cost as usual TD(0) learning.

   
Hanks, S. and Weld, D.S. (1995)
  "A Domain-Independent Algorithm for Plan Adaptation", Volume 2, 
   pages 319-360. 
   PostScript:  volume2/hanks95a.ps (500K)
   PDF:  volume2/hanks95a.ps (234K)

   Abstract: The paradigms of transformational planning, case-based
   planning, and plan debugging all involve a process known as plan
   adaptation --- modifying or repairing an old plan so it solves a new
   problem.  In this paper we provide a domain-independent algorithm for
   plan adaptation, demonstrate that it is sound, complete, and
   systematic, and compare it to other adaptation algorithms in the
   literature.
   
   Our approach is based on a view of planning as searching a graph of
   partial plans.  Generative planning starts at the graph's root and
   moves from node to node using plan-refinement operators.  In planning
   by adaptation, a library plan---an arbitrary node in the plan
   graph---is the starting point for the search, and the plan-adaptation
   algorithm can apply both the same refinement operators available to a
   generative planner and can also retract constraints and steps from the
   plan.  Our algorithm's completeness ensures that the adaptation
   algorithm will eventually search the entire graph and its systematicity 
   ensures that it will do so without redundantly searching any parts of
   the graph.


Ortega, J. (1995)
  "On the Informativeness of the DNA Promoter Sequences Domain Theory"
   (Research Note), Volume 2, pages 361-367.
   PostScript: volume2/ortega95a.ps (134K)
   PDF: volume2/ortega95a.pdf (149K)

   Abstract: The DNA promoter sequences domain theory and database have
   become popular for testing systems that integrate empirical and
   analytical learning.  This note reports a simple change and
   reinterpretation of the domain theory in terms of M-of-N concepts,
   involving no learning, that results in an accuracy of 93.4% on the 106
   items of the database.  Moreover, an exhaustive search of the space of
   M-of-N domain theory interpretations indicates that the expected
   accuracy of a randomly chosen interpretation is 76.5%, and that a
   maximum accuracy of 97.2% is achieved in 12 cases.  This demonstrates
   the informativeness of the domain theory, without the complications of
   understanding the interactions between various learning algorithms and
   the theory.  In addition, our results help characterize the difficulty
   of learning using the DNA promoters theory.


Turney, P.D. (1995)
  "Cost-Sensitive Classification: Empirical Evaluation of a Hybrid 
   Genetic Decision Tree Induction Algorithm", Volume 2, pages 369-409.
   PostScript: volume2/turney95a.ps (474K)
               compressed, volume2/turney95a.ps.Z (183K)
   PDF: volume2/turney95a.pdf (203K)

   Abstract: This paper introduces ICET, a new algorithm for
   cost-sensitive classification. ICET uses a genetic algorithm to evolve
   a population of biases for a decision tree induction algorithm. The
   fitness function of the genetic algorithm is the average cost of
   classification when using the decision tree, including both the costs
   of tests (features, measurements) and the costs of classification
   errors. ICET is compared here with three other algorithms for
   cost-sensitive classification - EG2, CS-ID3, and IDX - and also with
   C4.5, which classifies without regard to cost. The five algorithms are
   evaluated empirically on five real-world medical datasets. Three sets
   of experiments are performed.  The first set examines the baseline
   performance of the five algorithms on the five datasets and
   establishes that ICET performs significantly better than its
   competitors. The second set tests the robustness of ICET under a
   variety of conditions and shows that ICET maintains its advantage. The
   third set looks at ICET's search in bias space and discovers a way to
   improve the search.


Donoho, S.K. and Rendell, L.A. (1995)
  "Rerepresenting and Restructuring Domain Theories:  A Constructive 
   Induction Approach", Volume 2, pages 411-446.
   PostScript: volume2/donoho95a.ps (501K)
               compressed, volume2/donoho95a.ps.Z (179K)	
   Online Appendix: volume2/donoho94a-appendix.tar.Z (150K), source code & data
   PDF: volume2/donoho95a.pdf (343K)

   Abstract: Theory revision integrates inductive learning and background
   knowledge by combining training examples with a coarse domain theory
   to produce a more accurate theory.  There are two challenges that
   theory revision and other theory-guided systems face.  First, a
   representation language appropriate for the initial theory may be
   inappropriate for an improved theory.  While the original
   representation may concisely express the initial theory, a more
   accurate theory forced to use that same representation may be bulky,
   cumbersome, and difficult to reach.  Second, a theory structure
   suitable for a coarse domain theory may be insufficient for a
   fine-tuned theory.  Systems that produce only small, local changes to
   a theory have limited value for accomplishing complex structural
   alterations that may be required.
   
   Consequently, advanced theory-guided learning systems require flexible 
   representation and flexible structure.  An analysis of various theory 
   revision systems and theory-guided learning systems reveals specific 
   strengths and weaknesses in terms of these two desired properties.  
   Designed to capture the underlying qualities of each system, a new 
   system uses theory-guided constructive induction.  Experiments in 
   three domains show improvement over previous theory-guided systems.  
   This leads to a study of the behavior, limitations, and potential of 
   theory-guided constructive induction.


David, P. (1995)
  "Using Pivot Consistency to Decompose and Solve Functional CSPs", 
   Volume 2, pages 447-474.
   PostScript: volume2/david95a.ps (489K)
               compressed, volume2/david95a.ps.Z (220K)
   PDF: volume2/david95a.pdf (1.3M)
 
   Abstract: Many studies have been carried out in order to increase the
   search efficiency of constraint satisfaction problems; among them,
   some make use of structural properties of the constraint
   network; others take into account semantic properties of the
   constraints, generally assuming that all the constraints possess
   the given property.  In this paper, we propose a new decomposition
   method benefiting from both semantic properties of functional
   constraints (not bijective constraints) and structural
   properties of the network; furthermore, not all the constraints need
   to be functional.  We show that under some conditions, the existence
   of solutions can be guaranteed.  We first characterize a particular
   subset of the variables, which we name a root set.  We then
   introduce pivot consistency, a new local consistency which is a
   weak form of path consistency and can be achieved in O(n^2d^2)
   complexity (instead of O(n^3d^3) for path consistency), and we
   present associated properties; in particular, we show that any
   consistent instantiation of the root set can be linearly extended to a
   solution, which leads to the presentation of the aforementioned new
   method for solving by decomposing functional CSPs.


Schaerf, A., Shoham, Y. and Tennenholtz, M. (1995)
  "Adaptive Load Balancing: A Study in Multi-Agent Learning", 
   Volume 2, pages 475-500.
   PostScript: volume2/schaerf95a.ps (265K)
	       compressed, volume2/schaerf95a.ps.Z (107K)
   PDF: volume2/schaerf95a.pdf (286K)

   Abstract: We study the process of multi-agent reinforcement learning
   in the context of load balancing in a distributed system, without use
   of either central coordination or explicit communication.  We first
   define a precise framework in which to study adaptive load balancing,
   important features of which are its stochastic nature and the purely
   local information available to individual agents.  Given this
   framework, we show illuminating results on the interplay between basic
   adaptive behavior parameters and their effect on system efficiency.
   We then investigate the properties of adaptive load balancing in
   heterogeneous populations, and address the issue of exploration vs.
   exploitation in that context.  Finally, we show that naive use of
   communication may not improve, and might even harm system efficiency.


Cohen, W.W. (1995a)
  "Pac-Learning Recursive Logic Programs: Efficient Algorithms", 
   Volume 2, pages 501-539.
   PostScript: volume2/cohen95a.ps (339K)
	       compressed, volume2/cohen95a.ps.Z (135K)
   PDF: volume2/cohen95a.pdf (367K)

   Abstract: We present algorithms that learn certain classes of
   function-free recursive logic programs in polynomial time from
   equivalence queries.  In particular, we show that a single k-ary
   recursive constant-depth determinate clause is learnable. Two-clause
   programs consisting of one learnable recursive clause and one
   constant-depth determinate non-recursive clause are also learnable, if
   an additional ``basecase'' oracle is assumed.  These results
   immediately imply the pac-learnability of these classes.  Although
   these classes of learnable recursive programs are very constrained, it
   is shown in a companion paper that they are maximally general, in that
   generalizing either class in any natural way leads to a
   computationally difficult learning problem.  Thus, taken together with
   its companion paper, this paper establishes a boundary of efficient
   learnability for recursive logic programs.


Cohen, W.W. (1995b)
  "Pac-learning Recursive Logic Programs: Negative Results", 
   Volume 2, pages 541-573.
   PostScript: volume2/cohen95b.ps (342K)
	       compressed, volume2/cohen95b.ps.Z (136K)
   PDF: volume2/cohen95b.pdf (375K)

   Abstract: In a companion paper it was shown that the class of
   constant-depth determinate k-ary recursive clauses is efficiently
   learnable.  In this paper we present negative results showing that any
   natural generalization of this class is hard to learn in Valiant's
   model of pac-learnability.  In particular, we show that the following
   program classes are cryptographically hard to learn: programs with an
   unbounded number of constant-depth linear recursive clauses; programs
   with one constant-depth determinate clause containing an unbounded
   number of recursive calls; and programs with one linear recursive
   clause of constant locality.  These results immediately imply the
   non-learnability of any more general class of programs. We also show
   that learning a constant-depth determinate program with either two
   linear recursive clauses or one linear recursive clause and one
   non-recursive clause is as hard as learning boolean DNF.  Together
   with positive results from the companion paper, these negative results
   establish a boundary of efficient learnability for recursive
   function-free clauses.


Russell, S.J., and Subramanian, D. (1995)
  "Provably Bounded-Optimal Agents", 
   Volume 2, pages 575-609.
   PostScript: volume2/russell95a.ps (513K)
	       compressed, volume2/russell95a.ps.Z (195K)
   PDF: volume2/russell95a.pdf (394K)

   Abstract: Since its inception, artificial intelligence has relied
   upon a theoretical foundation centered around perfect rationality as
   the desired property of intelligent systems. We argue, as others have
   done, that this foundation is inadequate because it imposes
   fundamentally unsatisfiable requirements. As a result, there has
   arisen a wide gap between theory and practice in AI, hindering
   progress in the field. We propose instead a property called bounded
   optimality. Roughly speaking, an agent is bounded-optimal if its
   program is a solution to the constrained optimization problem
   presented by its architecture and the task environment. We show how to
   construct agents with this property for a simple class of machine
   architectures in a broad class of real-time environments. We
   illustrate these results using a simple model of an automated mail
   sorting facility.  We also define a weaker property, asymptotic
   bounded optimality (ABO), that generalizes the notion of optimality in
   classical complexity theory.  We then construct universal ABO
   programs, i.e., programs that are ABO no matter what real-time
   constraints are applied.  Universal ABO programs can be used as
   building blocks for more complex systems. We conclude with a
   discussion of the prospects for bounded optimality as a theoretical
   basis for AI, and relate it to similar trends in philosophy,
   economics, and game theory.



	  		          Volume3


Mooney, R.J. and Califf, M.E. (1995)
  "Induction of First-Order Decision Lists: Results on Learning the Past 
   Tense of English Verbs", Volume 3, pages 1-24.
   PostScript: volume3/mooney95a.ps (252K)
	       compressed, volume3/mooney95a.ps.Z (102K)
   PDF: volume3/mooney95a.pdf (277K)

   Abstract: This paper presents a method for inducing logic programs
   from examples that learns a new class of concepts called first-order
   decision lists, defined as ordered lists of clauses each ending in a
   cut.  The method, called FOIDL, is based on FOIL (Quinlan, 1990) but
   employs intensional background knowledge and avoids the need for
   explicit negative examples.  It is particularly useful for problems
   that involve rules with specific exceptions, such as learning the
   past-tense of English verbs, a task widely studied in the context of
   the symbolic/connectionist debate.  FOIDL is able to learn concise,
   accurate programs for this problem from significantly fewer examples
   than previous methods (both connectionist and symbolic).  


Veloso, M. and Stone, P. (1995)
  "FLECS: Planning with a Flexible Commitment Strategy", 
   Volume 3, pages 25-52.
   PostScript: volume3/veloso95a.ps (294K)
	       compressed, volume3/veloso95a.ps.Z (126K)
   Online Appendix: volume3/veloso95a-appendix.tar.Z (20K) data file
   PDF: volume3/veloso95a.pdf (341K)

   Abstract: There has been evidence that least-commitment planners can
   efficiently handle planning problems that involve difficult goal
   interactions.  This evidence has led to the common belief that
   delayed-commitment is the "best" possible planning strategy.  However,
   we recently found evidence that eager-commitment planners can handle a
   variety of planning problems more efficiently, in particular those
   with difficult operator choices.  Resigned to the futility of trying
   to find a universally successful planning strategy, we devised a
   planner that can be used to study which domains and problems are best
   for which planning strategies. In this article we introduce this new
   planning algorithm, FLECS, which uses a FLExible Commitment Strategy
   with respect to plan-step orderings.  It is able to use any strategy
   from delayed-commitment to eager-commitment.  The combination of
   delayed and eager operator-ordering commitments allows FLECS to take
   advantage of the benefits of explicitly using a simulated execution
   state and reasoning about planning constraints.  FLECS can vary its
   commitment strategy across different problems and domains, and also
   during the course of a single planning problem.  FLECS represents a
   novel contribution to planning in that it explicitly provides the
   choice of which commitment strategy to use while planning.  FLECS
   provides a framework to investigate the mapping from planning domains
   and problems to efficient planning strategies.


Bergmann, R. and Wilke, W. (1995)
  "Building and Refining Abstract Planning Cases by Change of 
   Representation Language", Volume 3, pages 53-118.
   PostScript: volume3/bergmann95a.ps (850K)
	       compressed, volume3/bergmann95a.ps.Z (302K)
   Online Appendix: volume3/bergmann95a-appendix (11K) data file
   PDF: volume3/bergmann95a.pdf (586K)

   Abstract: Abstraction is one of the most promising approaches to improve the
   performance of problem solvers. In several domains abstraction by
   dropping sentences of a domain description -- as used in most
   hierarchical planners -- has proven useful. In this paper we present
   examples which illustrate significant drawbacks of abstraction by
   dropping sentences. To overcome these drawbacks, we propose a more
   general view of abstraction involving the change of representation
   language. We have developed a new abstraction methodology and a
   related sound and complete learning algorithm that allows the complete
   change of representation language of planning cases from concrete to
   abstract.  However, to achieve a powerful change of the representation
   language, the abstract language itself as well as rules which describe
   admissible ways of abstracting states must be provided in the domain
   model. This new abstraction approach is the core of Paris (Plan
   Abstraction and Refinement in an Integrated System), a system in which
   abstract planning cases are automatically learned from given concrete
   cases. An empirical study in the domain of process planning in
   mechanical engineering shows significant advantages of the proposed
   reasoning from abstract cases over classical hierarchical planning.
   

Zhao, Q. and Nishida, T. (1995)
  "Using Qualitative Hypotheses to Identify Inaccurate Data", 
   Volume 3, pages 119-145.
   PostScript: volume3/zhao95a.ps (626K)
	       compressed, volume3/zhao95a.ps.Z (200K)
   PDF: volume3/zhao95a.pdf (383K)

   Abstract: Identifying inaccurate data has long been regarded as a
   significant and difficult problem in AI. In this paper, we present a
   new method for identifying inaccurate data on the basis of qualitative
   correlations among related data. First, we introduce the definitions
   of related data and qualitative correlations among related data.  Then
   we put forward a new concept called support coefficient function
   (SCF). SCF can be used to extract, represent, and calculate
   qualitative correlations among related data within a dataset. We
   propose an approach to determining dynamic shift intervals of
   inaccurate data, and an approach to calculating possibility of
   identifying inaccurate data, respectively. Both of the approaches are
   based on SCF. Finally we present an algorithm for identifying
   inaccurate data by using qualitative correlations among related data
   as confirmatory or disconfirmatory evidence. We have developed a
   practical system for interpreting infrared spectra by applying the
   method, and have fully tested the system against several hundred real
   spectra. The experimental results show that the method is
   significantly better than the conventional methods used in many
   similar systems.


Giraud-Carrier, C.G. and Martinez, T.R. (1995)
  "An Integrated Framework for Learning and Reasoning", 
   Volume 3, pages 147-185.
   Online Appendix: volume3/giraud-carrier95a-appendix.tar (90K) source, data
   PostScript: volume3/giraud-carrier95a.ps (375K)
	       compressed, volume3/giraud-carrier95a.ps.Z (152K)

   Abstract: Learning and reasoning are both aspects of what is
   considered to be intelligence. Their studies within AI have been
   separated historically, learning being the topic of machine learning
   and neural networks, and reasoning falling under classical (or
   symbolic) AI.  However, learning and reasoning are in many ways
   interdependent. This paper discusses the nature of some of these
   interdependencies and proposes a general framework called FLARE, that
   combines inductive learning using prior knowledge together with
   reasoning in a propositional setting. Several examples that test the
   framework are presented, including classical induction, many important
   reasoning protocols and two simple expert systems.


Woods, K., Cook, D., Hall, L., Bowyer, K. and Stark, L. (1995)
  "Learning Membership Functions in a Function-Based Object Recognition 
   System", Volume 3, pages 187-222.
   PostScript: volume3/woods95a.ps (1.4M)
	       compressed, volume3/woods95a.ps.Z (463K)
   HTML: http://seraphim.csee.usf.edu/omlet/omlet-JAIR.html
   PDF: volume3/woods95a.pdf (544K)


   Abstract: Functionality-based recognition systems recognize objects at
   the category level by reasoning about how well the objects support the
   expected function. Such systems naturally associate a ``measure of
   goodness'' or ``membership value'' with a recognized object.  This
   measure of goodness is the result of combining individual measures, or
   membership values, from potentially many primitive evaluations of
   different properties of the object's shape. A membership function is
   used to compute the membership value when evaluating a primitive of a
   particular physical property of an object.  In previous versions of a
   recognition system known as Gruff, the membership function for each of
   the primitive evaluations was hand-crafted by the system designer.  In
   this paper, we provide a learning component for the Gruff system,
   called Omlet, that automatically learns membership functions given a
   set of example objects labeled with their desired category measure.
   The learning algorithm is generally applicable to any problem in which
   low-level membership values are combined through an and-or tree
   structure to give a final overall membership value.


Pinkas, G. and Dechter, R. (1995)
  "Improving Connectionist Energy Minimization", Volume 3, pages 223-248.
   PostScript: volume3/pinkas95a.ps (358K)
	       compressed, volume3/pinkas95a.ps.Z (138K)
   PDF: volume3/pinkas95a.pdf (293K)

   Abstract: Symmetric networks designed for energy minimization such as
   Boltzman machines and Hopfield nets are frequently investigated for
   use in optimization, constraint satisfaction and approximation of
   NP-hard problems. Nevertheless, finding a global solution (i.e., a
   global minimum for the energy function) is not guaranteed and even a
   local solution may take an exponential number of steps.  We propose an
   improvement to the standard local activation function used for such
   networks.  The improved algorithm guarantees that a global minimum is
   found in linear time for tree-like subnetworks. The algorithm, called
   activate, is uniform and does not assume that the network is
   tree-like.  It can identify tree-like subnetworks even in cyclic
   topologies (arbitrary networks) and avoid local minima along these
   trees.  For acyclic networks, the algorithm is guaranteed to converge
   to a global minimum from any initial state of the system
   (self-stabilization) and remains correct under various types of
   schedulers.  On the negative side, we show that in the presence of
   cycles, no uniform algorithm exists that guarantees optimality even
   under a sequential asynchronous scheduler.  An asynchronous scheduler
   can activate only one unit at a time while a synchronous scheduler can
   activate any number of units in a single time step.  In addition, no
   uniform algorithm exists to optimize even acyclic networks when the
   scheduler is synchronous.  Finally, we show how the algorithm can be
   improved using the cycle-cutset scheme.  The general algorithm, called
   activate-with-cutset, improves over activate and has some performance
   guarantees that are related to the size of the network's cycle-cutset.


Bengio, Y. and Frasconi, P. (1995)
  "Diffusion of Context and Credit Information in Markovian Models", 
   Volume 3, pages 249-270.
   PostScript: volume3/bengio95a.ps (397K)
	       compressed, volume3/bengio95a.ps.Z (158K)
   PDF: volume3/bengio95a.pdf (1.2M)

   Abstract: This paper studies the problem of ergodicity of transition
   probability matrices in Markovian models, such as hidden Markov models
   (HMMs), and how it makes very difficult the task of learning to
   represent long-term context for sequential data.  This phenomenon
   hurts the forward propagation of long-term context information, as
   well as learning a hidden state representation to represent long-term
   context, which depends on propagating credit information backwards in
   time.  Using results from Markov chain theory, we show that this
   problem of diffusion of context and credit is reduced when the
   transition probabilities approach 0 or 1, i.e., the transition
   probability matrices are sparse and the model essentially
   deterministic.  The results found in this paper apply to learning
   approaches based on continuous optimization, such as gradient descent
   and the Baum-Welch algorithm.


Huffman, S.B. and Laird, J.E. (1995)
  "Flexibly Instructable Agents", Volume 3, pages 271-324.
   PostScript: volume3/huffman95a.ps (1599K)
	       compressed, volume3/huffman95a.ps.Z (476K)
   PDF: volume3/huffman95a.pdf (539K)

   Abstract: This paper presents an approach to learning from situated,
   interactive tutorial instruction within an ongoing agent.  Tutorial
   instruction is a flexible (and thus powerful) paradigm for teaching
   tasks because it allows an instructor to communicate whatever types of
   knowledge an agent might need in whatever situations might arise.  To
   support this flexibility, however, the agent must be able to learn
   multiple kinds of knowledge from a broad range of instructional
   interactions.  Our approach, called situated explanation, achieves
   such learning through a combination of analytic and inductive
   techniques.  It combines a form of explanation-based learning that is
   situated for each instruction with a full suite of contextually guided
   responses to incomplete explanations.  The approach is implemented in
   an agent called Instructo-Soar that learns hierarchies of new tasks
   and other domain knowledge from interactive natural language
   instructions.  Instructo-Soar meets three key requirements of flexible
   instructability that distinguish it from previous systems: (1) it can
   take known or unknown commands at any instruction point; (2) it can
   handle instructions that apply to either its current situation or to a
   hypothetical situation specified in language (as in, for instance,
   conditional instructions); and (3) it can learn, from instructions,
   each class of knowledge it uses to perform tasks.


Broggi, A. and Berte, S. (1995)
  "Vision-Based Road Detection in Automotive Systems: A Real-Time 
   Expectation-Driven Approach", Volume 3, pages 325-348.
   PostScript: volume3/broggi95a.ps (1762K)
	       compressed, volume3/broggi95a.ps.Z (620K)
   PDF: volume3/broggi95a.pdf (430K)

   Abstract: The main aim of this work is the development of a
   vision-based road detection system fast enough to cope with the
   difficult real-time constraints imposed by moving vehicle
   applications.  The hardware platform, a special-purpose massively
   parallel system, has been chosen to minimize system production and
   operational costs.
   
   This paper presents a novel approach to expectation-driven low-level
   image segmentation, which can be mapped naturally onto mesh-connected
   massively parallel SIMD architectures capable of handling hierarchical
   data structures.  The input image is assumed to contain a distorted
   version of a given template; a multiresolution stretching process is
   used to reshape the original template in accordance with the acquired
   image content, minimizing a potential function.  The distorted
   template is the process output.


Khardon, R. (1995)
  "Translating between Horn Representations and their Characteristic Models", 
   Volume 3, pages 349-372.
   PostScript: volume3/khardon95a.ps (284K)
	       compressed, volume3/khardon95a.ps.Z (114K)
   PDF: volume3/khardon95a.pdf (1.0M)

   Abstract: Characteristic models are an alternative, model based,
   representation for Horn expressions. It has been shown that these two
   representations are incomparable and each has its advantages over the
   other. It is therefore natural to ask what is the cost of translating,
   back and forth, between these representations. Interestingly, the same
   translation questions arise in database theory, where it has
   applications to the design of relational databases. This paper studies
   the computational complexity of these problems.
   
   Our main result is that the two translation problems are equivalent under
   polynomial reductions, and that they are equivalent to the corresponding
   decision problem. Namely, translating is equivalent to deciding whether a
   given set of models is the set of characteristic models for a given Horn
   expression. 
   
   We also relate these problems to the hypergraph transversal problem, a
   well known problem which is related to other applications in AI and for
   which no polynomial time algorithm is known. It is shown that in general
   our translation problems are at least as hard as the hypergraph
   transversal problem, and in a special case they are equivalent to it. 


Buro, M. (1995)
  "Statistical Feature Combination for the Evaluation of Game Positions", 
   Volume 3, pages 373-382.
   PostScript: volume3/buro95a.ps (178K)
	       compressed, volume3/buro95a.ps.Z (80K)
   PDF: volume3/buro95a.pdf (240K)

   Abstract: This article describes an application of three well-known
   statistical methods in the field of game-tree search: using a large
   number of classified Othello positions, feature weights for evaluation
   functions with a game-phase-independent meaning are estimated by means
   of logistic regression, Fisher's linear discriminant, and the
   quadratic discriminant function for normally distributed
   features. Thereafter, the playing strengths are compared by means of
   tournaments between the resulting versions of a world-class Othello
   program. In this application, logistic regression - which is used here
   for the first time in the context of game playing - leads to better
   results than the other approaches.


Weiss, S.M. and Indurkhya, N. (1995)
  "Rule-based Machine Learning Methods for Functional Prediction", 
   Volume 3, pages 383-403.
   PostScript: volume3/weiss95a.ps (527K)
	       compressed, volume3/weiss95a.ps.Z (166K)
   PDF: volume3/weiss95a.pdf (304K)

   Abstract: We describe a machine learning method for predicting the
   value of a real-valued function, given the values of multiple input
   variables. The method induces solutions from samples in the form of
   ordered disjunctive normal form (DNF) decision rules. A central
   objective of the method and representation is the induction of
   compact, easily interpretable solutions.  This rule-based decision
   model can be extended to search efficiently for similar cases prior to
   approximating function values. Experimental results on real-world data
   demonstrate that the new techniques are competitive with existing
   machine learning and statistical methods and can sometimes yield
   superior regression performance.


Heckerman, D. and Shachter, R. (1995)
  "Decision-Theoretic Foundations for Causal Reasoning", 
   Volume 3, pages 405-430.
   PostScript: volume3/heckerman95a.ps (327K)
	       compressed, volume3/heckerman95a.ps.Z (136K)
   PDF: volume3/heckerman95a.pdf (307K)

   Abstract: We present a definition of cause and effect in terms of
   decision-theoretic primitives and thereby provide a principled
   foundation for causal reasoning.  Our definition departs from the
   traditional view of causation in that causal assertions may vary with
   the set of decisions available.  We argue that this approach provides
   added clarity to the notion of cause.  Also in this paper, we examine
   the encoding of causal relationships in directed acyclic graphs.  We
   describe a special class of influence diagrams, those in canonical
   form, and show its relationship to Pearl's representation of cause and
   effect.  Finally, we show how canonical form facilitates
   counterfactual reasoning.


Webb, G.I. (1995)
  "OPUS: An Efficient Admissible Algorithm for Unordered Search", 
   Volume 3, pages 431-465.
   PostScript: volume3/webb95a.ps (1503K)
	       compressed, volume3/webb95a.ps.Z (769K)
   HTML: http://www.cs.washington.edu/research/jair/volume4/webb96a-html/webb96a.html
   PDF: volume3/webb95a.pdf (373K)

   Abstract: OPUS is a branch and bound search algorithm that enables
   efficient admissible search through spaces for which the order of
   search operator application is not significant.  The algorithm's
   search efficiency is demonstrated with respect to very large machine
   learning search spaces.  The use of admissible search is of potential
   value to the machine learning community as it means that the exact
   learning biases to be employed for complex learning tasks can be
   precisely specified and manipulated.  OPUS also has potential for
   application in other areas of artificial intelligence, notably, truth
   maintenance.


Idestam-Almquist, P. (1995)
  "Generalization of Clauses under Implication", 
   Volume 3, pages 467-489.
   PostScript: volume3/idestam95a.ps (273K)
	       compressed, volume3/idestam95a.ps.Z (101K)
   PDF: volume3/idestam95a.pdf (1.0M)

   Abstract: In the area of inductive learning, generalization is a main
   operation, and the usual definition of induction is based on logical
   implication.  Recently there has been a rising interest in clausal
   representation of knowledge in machine learning. Almost all inductive
   learning systems that perform generalization of clauses use the
   relation theta-subsumption instead of implication. The main reason is
   that there is a well-known and simple technique to compute least
   general generalizations under theta-subsumption, but not under
   implication.  However generalization under theta-subsumption is
   inappropriate for learning recursive clauses, which is a crucial
   problem since recursion is the basic program structure of logic
   programs.
   
   We note that implication between clauses is undecidable, and we
   therefore introduce a stronger form of implication, called
   T-implication, which is decidable between clauses. We show that for
   every finite set of clauses there exists a least general
   generalization under T-implication.  We describe a technique to reduce
   generalizations under implication of a clause to generalizations under
   theta-subsumption of what we call an expansion of the original
   clause. Moreover we show that for every non-tautological clause there
   exists a T-complete expansion, which means that every generalization
   under T-implication of the clause is reduced to a generalization under
   theta-subsumption of the expansion.



   			       Volume4


van Beek, P. and Manchak, D.W. (1996)
  "The Design and Experimental Analysis of Algorithms for Temporal Reasoning", 
   Volume 4, pages 1-18.
   PostScript: volume4/vanbeek96a.ps (219K)
	       compressed, volume4/vanbeek96a.ps.Z (90K)
   HTML: http://www.cs.washington.edu/research/jair/volume4/vanbeek96a-html/paper.html
   PDF: volume4/vanbeek96a.pdf (228K)


   Abstract: Many applications -- from planning and scheduling to
   problems in molecular biology -- rely heavily on a temporal reasoning
   component.  In this paper, we discuss the design and empirical
   analysis of algorithms for a temporal reasoning system based on
   Allen's influential interval-based framework for representing temporal
   information.  At the core of the system are algorithms for determining
   whether the temporal information is consistent, and, if so, finding
   one or more scenarios that are consistent with the temporal
   information.  Two important algorithms for these tasks are a path
   consistency algorithm and a backtracking algorithm.  For the path
   consistency algorithm, we develop techniques that can result in up to
   a ten-fold speedup over an already highly optimized implementation.
   For the backtracking algorithm, we develop variable and value ordering
   heuristics that are shown empirically to dramatically improve the
   performance of the algorithm.  As well, we show that a previously
   suggested reformulation of the backtracking search problem can reduce
   the time and space requirements of the backtracking search.  Taken
   together, the techniques we develop allow a temporal reasoning
   component to solve problems that are of practical size.


Brewka, G. (1996)
  "Well-Founded Semantics for Extended Logic Programs with Dynamic 
   Preferences", Volume 4, pages 19-36.
   PostScript: volume4/brewka96a.ps (464K)
	       compressed, volume4/brewka96a.ps.Z (135K)
   PDF: volume4/brewka96a.pdf (776K)
   HTML:  http://www.cs.washington.edu/research/jair/volume4/brewka96a-html/LPR.html

   Abstract: The paper describes an extension of well-founded
   semantics for logic programs with two types of negation. In this
   extension information about preferences between rules can be expressed
   in the logical language and derived dynamically. This is achieved by
   using a reserved predicate symbol and a naming technique. Conflicts
   among rules are resolved whenever possible on the basis of derived
   preference information. The well-founded conclusions of prioritized
   logic programs can be computed in polynomial time. A legal reasoning
   example illustrates the usefulness of the approach.


Delcher, A.L., Grove, A.J., Kasif, S. and Pearl, J. (1996)
  "Logarithmic-Time Updates and Queries in Probabilistic Networks", 
   Volume 4, pages 37-59.
   PostScript: volume4/delcher96a.ps (277K)
	       compressed, volume4/delcher96a.ps.Z (107K)
   PDF: volume4/delcher96a.pdf (309K)

   Abstract: Traditional databases commonly support efficient query and
   update procedures that operate in time which is sublinear in the size
   of the database.  Our goal in this paper is to take a first step
   toward dynamic reasoning in probabilistic databases with comparable
   efficiency.  We propose a dynamic data structure that supports
   efficient algorithms for updating and querying singly connected
   Bayesian networks.  In the conventional algorithm, new evidence is
   absorbed in O(1) time and queries are processed in time O(N), where N
   is the size of the network.  We propose an algorithm which, after a
   preprocessing phase, allows us to answer queries in time O(log N) at
   the expense of O(log N) time per evidence absorption.  The usefulness
   of sub-linear processing time manifests itself in applications
   requiring (near) real-time response over large probabilistic
   databases. We briefly discuss a potential application of dynamic
   probabilistic reasoning in computational biology.


Saul, L.K., Jaakkola, T. and Jordan, M.I. (1996)
  "Mean Field Theory for Sigmoid Belief Networks", 
   Volume 4, pages 61-76.
   PostScript: volume4/saul96a.ps (302K)
	       compressed, volume4/saul96a.ps.Z (123K)
   PDF: volume4/saul96a.pdf (260K)

   Abstract: We develop a mean field theory for sigmoid belief networks
   based on ideas from statistical mechanics.  Our mean field theory
   provides a tractable approximation to the true probability
   distribution in these networks; it also yields a lower bound on the
   likelihood of evidence.  We demonstrate the utility of this framework
   on a benchmark problem in statistical pattern recognition---the
   classification of handwritten digits.


Quinlan, J.R. (1996)
  "Improved Use of Continuous Attributes in C4.5", 
   Volume 4, pages 77-90.
   PostScript: volume4/quinlan96a.ps (414K)
	       compressed, volume4/quinlan96a.ps.Z (124K)
   PDF: volume4/quinlan96a.pdf (259K)

   Abstract: A reported weakness of C4.5 in domains with continuous
   attributes is addressed by modifying the formation and evaluation of
   tests on continuous attributes.  An MDL-inspired penalty is applied to
   such tests, eliminating some of them from consideration and altering
   the relative desirability of all tests.  Empirical trials show that
   the modifications lead to smaller decision trees with higher
   predictive accuracies.  Results also confirm that a new version of
   C4.5 incorporating these changes is superior to recent approaches that
   use global discretization and that construct small trees with
   multi-interval splits.


Hogg, T. (1996)
  "Quantum Computing and Phase Transitions in Combinatorial Search", 
   Volume 4, pages 91-128.
   PostScript: volume4/hogg96a.ps (565K)
	       compressed, volume4/hogg96a.ps.Z (230K)
   Online Appendix: volume4/hogg96a-appendix.txt (32K) contains matrix values
   HTML:  http://www.cs.washington.edu/research/jair/volume4/hogg96a-html/quantumHTML.html
   PDF: volume4/hogg96a.pdf (385K)

   Abstract: We introduce an algorithm for combinatorial search on
   quantum computers that is capable of significantly concentrating
   amplitude into solutions for some NP search problems, on average. This
   is done by exploiting the same aspects of problem structure as used by
   classical backtrack methods to avoid unproductive search choices. This
   quantum algorithm is much more likely to find solutions than the
   simple direct use of quantum parallelism. Furthermore, empirical
   evaluation on small problems shows this quantum algorithm displays the
   same phase transition behavior, and at the same location, as seen in
   many previously studied classical search methods. Specifically,
   difficult problem instances are concentrated near the abrupt change
   from underconstrained to overconstrained problems.


Cohn, D.A., Ghahramani, Z., and Jordan, M.I. (1996)
  "Active Learning with Statistical Models", 
   Volume 4, pages 129-145.
   PostScript: volume4/cohn96a.ps (325K)
	       compressed, volume4/cohn96a.ps.Z (121K)
   HTML:  http://www.cs.washington.edu/research/jair/volume4/cohn96a-html/statmodels.html
   PDF: volume4/cohn96a.pdf (269K)

   Abstract: For many types of machine learning algorithms, one can
   compute the statistically `optimal' way to select training data.  In
   this paper, we review how optimal data selection techniques have been
   used with feedforward neural networks.  We then show how the same
   principles may be used to select data for two alternative,
   statistically-based learning architectures: mixtures of Gaussians and
   locally weighted regression.  While the techniques for neural networks
   are computationally expensive and approximate, the techniques for
   mixtures of Gaussians and locally weighted regression are both
   efficient and accurate.  Empirically, we observe that the optimality
   criterion sharply decreases the number of training examples the
   learner needs in order to achieve good performance.


Fisher, D. (1996)
  "Iterative Optimization and Simplification of Hierarchical Clusterings", 
   Volume 4, pages 147-178.
   PostScript: volume4/fisher96a.ps (286K)
	       compressed, volume4/fisher96a.ps.Z (130K)
   HTML:  http://www.cs.washington.edu/research/jair/volume4/fisher96a-html/html-final.html
   PDF: volume4/fisher96a.pdf (347K)

   Abstract: Clustering is often used for discovering structure in data.
   Clustering systems differ in the objective function used to evaluate
   clustering quality and the control strategy used to search the space
   of clusterings. Ideally, the search strategy should consistently
   construct clusterings of high quality, but be computationally
   inexpensive as well. In general, we cannot have it both ways, but we
   can partition the search so that a system inexpensively constructs a
   `tentative' clustering for initial examination, followed by iterative
   optimization, which continues to search in background for improved
   clusterings. Given this motivation, we evaluate an inexpensive
   strategy for creating initial clusterings, coupled with several
   control strategies for iterative optimization, each of which
   repeatedly modifies an initial clustering in search of a better
   one. One of these methods appears novel as an iterative optimization
   strategy in clustering contexts. Once a clustering has been
   constructed it is judged by analysts -- often according to
   task-specific criteria. Several authors have abstracted these criteria
   and posited a generic performance task akin to pattern completion,
   where the error rate over completed patterns is used to `externally'
   judge clustering utility. Given this performance task, we adapt
   resampling-based pruning strategies used by supervised learning
   systems to the task of simplifying hierarchical clusterings, thus
   promising to ease post-clustering analysis. Finally, we propose a
   number of objective functions, based on attribute-selection measures
   for decision-tree induction, that might perform well on the error rate
   and simplicity dimensions.


Marchiori, E. (1996)
  "Practical Methods for Proving Termination of General Logic Programs", 
   Volume 4, pages 179-208.
   PostScript: volume4/marchiori96a.ps (331K)
	       compressed, volume4/marchiori96a.ps.Z (154K)
   PDF: volume4/marchiori96a.pdf (1.3M)

   Abstract: Termination of logic programs with negated body atoms (here
   called general logic programs) is an important topic. One reason is
   that many computational mechanisms used to process negated atoms, like
   Clark's negation as failure and Chan's constructive negation, are
   based on termination conditions.  This paper introduces a methodology
   for proving termination of general logic programs w.r.t. the Prolog
   selection rule.  The idea is to distinguish parts of the program
   depending on whether or not their termination depends on the selection
   rule. To this end, the notions of low-, weakly up-, and up-acceptable
   program are introduced.  We use these notions to develop a methodology
   for proving termination of general logic programs, and show how
   interesting problems in non-monotonic reasoning can be formalized and
   implemented by means of terminating general logic programs.


Walsh, T. (1996)
  "A Divergence Critic for Inductive Proof", 
   Volume 4, pages 209-235.
   PostScript: volume4/walsh96a.ps (242K)
	       compressed, volume4/walsh96a.ps.Z (96K)
   HTML:  http://www.cs.washington.edu/research/jair/volume4/walsh96a-html/Final.html
   PDF: volume4/walsh96a.pdf (282K)

   Abstract: Inductive theorem provers often diverge. This paper
   describes a simple critic, a computer program which monitors the
   construction of inductive proofs attempting to identify diverging
   proof attempts. Divergence is recognized by means of a ``difference
   matching'' procedure. The critic then proposes lemmas and
   generalizations which ``ripple'' these differences away so that the
   proof can go through without divergence. The critic enables the
   theorem prover Spike to prove many theorems completely automatically
   from the definitions alone.


Kaelbling, L.P., Littman, M.L., and Moore, A.W. (1996)
  "Reinforcement Learning:  A Survey", 
   Volume 4, pages 237-285.
   PostScript: volume4/kaelbling96a.ps (903K)
	       compressed, volume4/kaelbling96a.ps.Z (362K)
   HTML:  http://www.cs.washington.edu/research/jair/volume4/kaelbling96a-html/rl-survey.html
   PDF: volume4/kaelbling96a.pdf (523K)

   Abstract: This paper surveys the field of reinforcement learning from
   a computer-science perspective. It is written to be accessible to
   researchers familiar with machine learning.  Both the historical basis
   of the field and a broad selection of current work are summarized.
   Reinforcement learning is the problem faced by an agent that learns
   behavior through trial-and-error interactions with a dynamic
   environment.  The work described here has a resemblance to work in
   psychology, but differs considerably in the details and in the use of
   the word ``reinforcement.''  The paper discusses central issues of
   reinforcement learning, including trading off exploration and
   exploitation, establishing the foundations of the field via Markov
   decision theory, learning from delayed reinforcement, constructing
   empirical models to accelerate learning, making use of generalization
   and hierarchy, and coping with hidden state.  It concludes with a
   survey of some implemented systems and an assessment of the practical
   utility of current methods for reinforcement learning.


Pryor, L. and Collins, G. (1996)
  "Planning for Contingencies: A Decision-based Approach", 
   Volume 4, pages 287-339.
   PostScript: volume4/pryor96a.ps (544K)
	       compressed, volume4/pryor96a.ps.Z (239K)
   HTML:  http://www.cs.washington.edu/research/jair/volume4/pryor96a-html/final-jair.html
   PDF: volume4/pryor96a.pdf (509K)

   Abstract: A fundamental assumption made by classical AI planners is
   that there is no uncertainty in the world: the planner has full
   knowledge of the conditions under which the plan will be executed and
   the outcome of every action is fully predictable.  These planners
   cannot therefore construct contingency plans, i.e., plans in which
   different actions are performed in different circumstances.  In this
   paper we discuss some issues that arise in the representation and
   construction of contingency plans and describe Cassandra, a
   partial-order contingency planner.  Cassandra uses explicit
   decision-steps that enable the agent executing the plan to decide
   which plan branch to follow.  The decision-steps in a plan result in
   subgoals to acquire knowledge, which are planned for in the same way
   as any other subgoals.  Cassandra thus distinguishes the process of
   gathering information from the process of making decisions.  The
   explicit representation of decisions in Cassandra allows a coherent
   approach to the problems of contingent planning, and provides a solid
   base for extensions such as the use of different decision-making
   procedures.


Nienhuys-Cheng, S.-H. and de Wolf, R. (1996)
  "Least Generalizations and Greatest Specializations of Sets of Clauses", 
   Volume 4, pages 341-363.
   PostScript: volume4/cheng96a.ps (281K)
	       compressed, volume4/cheng96a.ps.Z (109K)
   PDF: volume4/cheng96a.pdf (1.1M)

   Abstract: The main operations in Inductive Logic Programming (ILP) are
   generalization and specialization, which only make sense in a
   generality order.  In ILP, the three most important generality orders
   are subsumption, implication and implication relative to background
   knowledge.  The two languages used most often are languages of clauses
   and languages of only Horn clauses. This gives a total of six
   different ordered languages.  In this paper, we give a systematic
   treatment of the existence or non-existence of least generalizations
   and greatest specializations of finite sets of clauses in each of
   these six ordered sets.  We survey results already obtained by others
   and also contribute some answers of our own.
   
   Our main new results are, firstly, the existence of a computable least
   generalization under implication of every finite set of clauses
   containing at least one non-tautologous function-free clause (among
   other, not necessarily function-free clauses).  Secondly, we show that
   such a least generalization need not exist under relative implication,
   not even if both the set that is to be generalized and the background
   knowledge are function-free.  Thirdly, we give a complete discussion
   of existence and non-existence of greatest specializations in each of
   the six ordered languages.


Gratch, J. and Chien, S. (1996)
  "Adaptive Problem-solving for Large-scale Scheduling Problems: A Case Study", 
   Volume 4, pages 365-396.
   PostScript: volume4/gratch96a.ps (595K)
	       compressed, volume4/gratch96a.ps.Z (180K)
   PDF: volume4/gratch96a.pdf (172K)

   Abstract: Although most scheduling problems are NP-hard, domain
   specific techniques perform well in practice but are quite expensive
   to construct.  In adaptive problem-solving solving, domain specific
   knowledge is acquired automatically for a general problem solver with
   a flexible control architecture.  In this approach, a learning system
   explores a space of possible heuristic methods for one well-suited to
   the eccentricities of the given domain and problem distribution.  In
   this article, we discuss an application of the approach to scheduling
   satellite communications.  Using problem distributions based on actual
   mission requirements, our approach identifies strategies that not only
   decrease the amount of CPU time required to produce schedules, but
   also increase the percentage of problems that are solvable within
   computational resource limitations.


Webb, G.I. (1996)
  "Further Experimental Evidence against the Utility of Occam's Razor", 
   Volume 4, pages 397-417.
   PostScript: volume4/webb96a.ps (217K)
	       compressed, volume4/webb96a.ps.Z (89K)
   Online Appendix: volume4/webb96a-appendix.tar (41K) source code
   PDF: volume4/webb96a.pdf (250K)

   Abstract: This paper presents new experimental evidence against the
   utility of Occam's razor.  A~systematic procedure is presented for
   post-processing decision trees produced by C4.5.  This procedure was
   derived by rejecting Occam's razor and instead attending to the
   assumption that similar objects are likely to belong to the same
   class.  It increases a decision tree's complexity without altering the
   performance of that tree on the training data from which it is
   inferred.  The resulting more complex decision trees are demonstrated
   to have, on average, for a variety of common learning tasks, higher
   predictive accuracy than the less complex original decision trees.
   This result raises considerable doubt about the utility of Occam's
   razor as it is commonly applied in modern machine learning.


Bhansali, S., Kramer, G.A. and Hoar, T.J. (1996)
  "A Principled Approach Towards Symbolic Geometric Constraint Satisfaction", 
   Volume 4, pages 419-443.
   PostScript: volume4/bhansali96a.ps (933K)
	       compressed, volume4/bhansali96a.ps.Z (325K)
   Online Appendix: volume4/bhansali96a-appendix.txt (7K) example plan fragment
   HTML:  http://www.cs.washington.edu/research/jair/volume4/bhansali96a-html/paper.htm
   PDF: volume4/bhansali96a.pdf (100K)

   Abstract: An important problem in geometric reasoning is to find the
   configuration of a collection of geometric bodies so as to satisfy a
   set of given constraints. Recently, it has been suggested that this
   problem can be solved efficiently by symbolically reasoning about
   geometry. This approach, called degrees of freedom analysis, employs a
   set of specialized routines called plan fragments that specify how to
   change the configuration of a set of bodies to satisfy a new
   constraint while preserving existing constraints. A potential
   drawback, which limits the scalability of this approach, is concerned
   with the difficulty of writing plan fragments.  In this paper we
   address this limitation by showing how these plan fragments can be
   automatically synthesized using first principles about geometric
   bodies, actions, and topology.


Tadepalli, P. and Natarajan, B.K. (1996)
  "A Formal Framework for Speedup Learning from Problems and Solutions", 
   Volume 4, pages 445-475.
   PostScript: volume4/tadepalli96a.ps (333K)
	       compressed, volume4/tadepalli96a.ps.Z (132K)
   PDF: volume4/tadepalli96a.pdf (1.2M)

   Abstract: Speedup learning seeks to improve the computational
   efficiency of problem solving with experience. In this paper, we
   develop a formal framework for learning efficient problem solving from
   random problems and their solutions. We apply this framework to two
   different representations of learned knowledge, namely control rules
   and macro-operators, and prove theorems that identify sufficient
   conditions for learning in each representation. Our proofs are
   constructive in that they are accompanied with learning algorithms. 
   Our framework captures both empirical and explanation-based 
   speedup learning in a unified fashion.  We illustrate our framework
   with implementations in two domains: symbolic integration and Eight
   Puzzle. This work integrates many strands of experimental and
   theoretical work in machine learning, including empirical learning of
   control rules, macro-operator learning, Explanation-Based Learning
   (EBL), and Probably Approximately Correct (PAC) Learning.


Brafman, R.I. and Tennenholtz, M. (1996)
  "On Partially Controlled Multi-Agent Systems", 
   Volume 4, pages 477-507.
   PostScript: volume4/brafman96a.ps (356K)
	       compressed, volume4/brafman96a.ps.Z (146K)
   PDF: volume4/brafman96a.pdf (349K)

   Abstract: Motivated by the control theoretic distinction between
   controllable and uncontrollable events, we distinguish between two
   types of agents within a multi-agent system: controllable agents,
   which are directly controlled by the system's designer, and
   uncontrollable agents, which are not under the designer's direct
   control. We refer to such systems as partially controlled multi-agent
   systems, and we investigate how one might influence the behavior of
   the uncontrolled agents through appropriate design of the controlled
   agents. In particular, we wish to understand which problems are
   naturally described in these terms, what methods can be applied to
   influence the uncontrollable agents, the effectiveness of such
   methods, and whether similar methods work across different
   domains. Using a game-theoretic framework, this paper studies the
   design of partially controlled multi-agent systems in two contexts: in
   one context, the uncontrollable agents are expected utility
   maximizers, while in the other they are reinforcement learners. We
   suggest different techniques for controlling agents' behavior in each
   domain, assess their success, and examine their relationship.



	  		          Volume5


Yip, K. and Zhao, F. (1996)
  "Spatial Aggregation: Theory and Applications", 
   Volume 5, pages 1-26.
   PostScript: volume5/yip96a.ps (828K)
	       compressed, volume5/yip96a.ps.Z (248K)
   PDF: volume5/yip96a.pdf (391K)

   Abstract: Visual thinking plays an important role in scientific
   reasoning.  Based on the research in automating diverse reasoning
   tasks about dynamical systems, nonlinear controllers, kinematic
   mechanisms, and fluid motion, we have identified a style of visual
   thinking, imagistic reasoning.  Imagistic reasoning organizes
   computations around image-like, analogue representations so that
   perceptual and symbolic operations can be brought to bear to infer
   structure and behavior.  Programs incorporating imagistic reasoning
   have been shown to perform at an expert level in domains that defy
   current analytic or numerical methods.
   
   We have developed a computational paradigm, spatial aggregation, to
   unify the description of a class of imagistic problem solvers.  A
   program written in this paradigm has the following properties.  It
   takes a continuous field and optional objective functions as input,
   and produces high-level descriptions of structure, behavior, or
   control actions. It computes a multi-layer of intermediate
   representations, called spatial aggregates, by forming equivalence
   classes and adjacency relations.  It employs a small set of generic
   operators such as aggregation, classification, and localization to
   perform bidirectional mapping between the information-rich field and
   successively more abstract spatial aggregates. It uses a data
   structure, the neighborhood graph, as a common interface to modularize
   computations.  To illustrate our theory, we describe the computational
   structure of three implemented problem solvers -- KAM, MAPS, and
   HIPAIR --- in terms of the spatial aggregation generic operators by
   mixing and matching a library of commonly used routines.


Ben-Eliyahu, R. (1996)
  "A Hierarchy of Tractable Subsets for Computing Stable Models", 
   Volume 5, pages 27-52.
   PostScript: volume5/ben-eliyahu96a.ps (317K)
	       compressed, volume5/ben-eliyahu96a.ps.Z (126K)

   Abstract: Finding the stable models of a knowledge base is a
   significant computational problem in artificial intelligence. This
   task is at the computational heart of truth maintenance systems,
   autoepistemic logic, and default logic.  Unfortunately, it is NP-hard.
   In this paper we present a hierarchy of classes of knowledge bases,
   Omega_1,Omega_2,..., with the following properties: first, Omega_1 is
   the class of all stratified knowledge bases; second, if a knowledge
   base Pi is in Omega_k, then Pi has at most k stable models, and all of
   them may be found in time O(lnk), where l is the length of the
   knowledge base and n the number of atoms in Pi; third, for an
   arbitrary knowledge base Pi, we can find the minimum k such that Pi
   belongs to Omega_k in time polynomial in the size of Pi; and, last,
   where K is the class of all knowledge bases, it is the case that
   union{i=1 to infty} Omega_i = K, that is, every knowledge base
   belongs to some class in the hierarchy.


Litman, D.J. (1996)
  "Cue Phrase Classification Using Machine Learning", 
   Volume 5, pages 53-94.
   PostScript: volume5/litman96a.ps (347K)
	       compressed, volume5/litman96a.ps.Z (135K)
   PDF: volume5/litman96a.pdf (379K)

   Abstract: Cue phrases may be used in a discourse sense to explicitly
   signal discourse structure, but also in a sentential sense to convey
   semantic rather than structural information.  Correctly classifying
   cue phrases as discourse or sentential is critical in natural language
   processing systems that exploit discourse structure, e.g., for
   performing tasks such as anaphora resolution and plan recognition.
   This paper explores the use of machine learning for classifying cue
   phrases as discourse or sentential.  Two machine learning programs
   (Cgrendel and C4.5) are used to induce classification models from sets
   of pre-classified cue phrases and their features in text and speech.
   Machine learning is shown to be an effective technique for not only
   automating the generation of classification models, but also for
   improving upon previous results.  When compared to manually derived
   classification models already in the literature, the learned models
   often perform with higher accuracy and contain new linguistic insights
   into the data.  In addition, the ability to automatically construct
   classification models makes it easier to comparatively analyze the
   utility of alternative feature representations of the data.  Finally,
   the ease of retraining makes the learning approach more scalable and
   flexible than manual methods.


Gerevini, A. and Schubert, L. (1996)
  "Accelerating Partial-Order Planners: Some Techniques for Effective 
   Search Control and Pruning", Volume 5, pages 95-137.
   PostScript: volume5/gerevini96a.ps (401K)
	       compressed, volume5/gerevini96a.ps.Z (164K)
   Online Appendices: volume5/gerevini96a-appendix1 (68K), source code
                      volume5/gerevini96a-appendix2 (47K), domain description
   PDF: volume5/gerevini96a.pdf (432K)

  Abstract: We propose some domain-independent techniques for bringing
  well-founded partial-order planners closer to practicality. The first
  two techniques are aimed at improving search control while keeping
  overhead costs low.  One is based on a simple adjustment to the
  default A* heuristic used by UCPOP to select plans for refinement. The
  other is based on preferring ``zero commitment'' (forced) plan
  refinements whenever possible, and using LIFO prioritization
  otherwise. A more radical technique is the use of operator parameter
  domains to prune search. These domains are initially computed from the
  definitions of the operators and the initial and goal conditions,
  using a polynomial-time algorithm that propagates sets of constants
  through the operator graph, starting in the initial conditions.
  During planning, parameter domains can be used to prune nonviable
  operator instances and to remove spurious clobbering threats.  In
  experiments based on modifications of UCPOP, our improved plan and
  goal selection strategies gave speedups by factors ranging from 5 to
  more than 1000 for a variety of problems that are nontrivial for the
  unmodified version. Crucially, the hardest problems gave the greatest
  improvements. The pruning technique based on parameter domains often
  gave speedups by an order of magnitude or more for difficult problems,
  both with the default UCPOP search strategy and with our improved
  strategy. The Lisp code for our techniques and for the test problems
  is provided in on-line appendices.


Quinlan, J.R. (1996)
  "Learning First-Order Definitions of Functions", 
   Volume 5, pages 139-161.
   PostScript: volume5/quinlan96b.ps (528K)
	       compressed, volume5/quinlan96b.ps.Z (156K)
   PDF: volume5/quinlan96b.pdf (337K)

   Abstract: First-order learning involves finding a clause-form
   definition of a relation from examples of the relation and relevant
   background information.  In this paper, a particular first-order
   learning system is modified to customize it for finding definitions of
   functional relations.  This restriction leads to faster learning times
   and, in some cases, to definitions that have higher predictive
   accuracy.  Other first-order learning systems might benefit from
   similar specialization.


Zlotkin, G. and Rosenschein, J.S. (1996)
  "Mechanisms for Automated Negotiation in State Oriented Domains", 
   Volume 5, pages 163-238.
   PostScript: volume5/zlotkin96a.ps (946K)
	       compressed, volume5/zlotkin96a.ps.Z (374K)
   PDF: volume5/zlotkin96a.pdf (691K)

   Abstract: This paper lays part of the groundwork for a domain theory of
   negotiation, that is, a way of classifying interactions so that it is
   clear, given a domain, which negotiation mechanisms and strategies are
   appropriate.  We define State Oriented Domains, a general category of
   interaction.  Necessary and sufficient conditions for cooperation are
   outlined.  We use the notion of worth in an altered definition of
   utility, thus enabling agreements in a wider class of joint-goal
   reachable situations. An approach is offered for conflict resolution,
   and it is shown that even in a conflict situation, partial cooperative
   steps can be taken by interacting agents (that is, agents in
   fundamental conflict might still agree to cooperate up to a certain
   point).

   A Unified Negotiation Protocol (UNP) is developed that can be used in
   all types of encounters. It is shown that in certain borderline
   cooperative situations, a partial cooperative agreement (i.e., one
   that does not achieve all agents' goals) might be preferred by all
   agents, even though there exists a rational agreement that would
   achieve all their goals.

   Finally, we analyze cases where agents have incomplete information on
   the goals and worth of other agents. First we consider the case where
   agents' goals are private information, and we analyze what goal
   declaration strategies the agents might adopt to increase their
   utility.  Then, we consider the situation where the agents' goals (and
   therefore stand-alone costs) are common knowledge, but the worth they
   attach to their goals is private information.  We introduce two
   mechanisms, one 'strict', the other 'tolerant', and analyze their
   affects on the stability and efficiency of negotiation outcomes.


Helzerman, R.A and Harper, M.P. (1996)
  "MUSE CSP: An Extension to the Constraint Satisfaction Problem", 
   Volume 5, pages 239-288.
   PostScript: volume5/helzerman96a.ps (2.1M)
	       compressed, volume5/helzerman96a.ps.Z (439K)
   HTML:  http://www.cs.washington.edu/research/jair/volume5/helzerman96a-html/muse-csp.html
   PDF: volume5/helzerman96a.pdf (555K)

   Abstract: This paper describes an extension to the constraint
   satisfaction problem (CSP) called MUSE CSP (MUltiply SEgmented
   Constraint Satisfaction Problem).  This extension is especially useful
   for those problems which segment into multiple sets of partially
   shared variables.  Such problems arise naturally in signal processing
   applications including computer vision, speech processing, and
   handwriting recognition.  For these applications, it is often
   difficult to segment the data in only one way given the low-level
   information utilized by the segmentation algorithms.  MUSE CSP can be
   used to compactly represent several similar instances of the
   constraint satisfaction problem.  If multiple instances of a CSP have
   some common variables which have the same domains and constraints,
   then they can be combined into a single instance of a MUSE CSP,
   reducing the work required to apply the constraints.  We introduce the
   concepts of MUSE node consistency, MUSE arc consistency, and MUSE path
   consistency. We then demonstrate how MUSE CSP can be used to compactly
   represent lexically ambiguous sentences and the multiple sentence
   hypotheses that are often generated by speech recognition algorithms
   so that grammar constraints can be used to provide parses for all
   syntactically correct sentences.  Algorithms for MUSE arc and path
   consistency are provided.  Finally, we discuss how to create a MUSE
   CSP from a set of CSPs which are labeled to indicate when the same
   variable is shared by more than a single CSP.


de Campos, L.M. (1996)
  "Characterizations of Decomposable Dependency Models" (research note),
   Volume 5, pages 289-300.
   PostScript: volume5/campos96a.ps (172K)
	       compressed, volume5/campos96a.ps.Z (67K)
   PDF: volume5/campos96a.pdf (197K)

   Abstract: Decomposable dependency models possess a number of
   interesting and useful properties. This paper presents new
   characterizations of decomposable models in terms of independence
   relationships, which are obtained by adding a single axiom to the
   well-known set characterizing dependency models that are isomorphic to
   undirected graphs. We also briefly discuss a potential application of
   our results to the problem of learning graphical models from data.


Zhang, N.L. and Poole, D. (1996)
  "Exploiting Causal Independence in Bayesian Network Inference", 
   Volume 5, pages 301-328.
   PostScript: volume5/zhang96a.ps (276K)
	       compressed, volume5/zhang96a.ps.Z (113K)
   HTML: http://www.cs.ubc.ca/spider/poole/papers/ZhangPoole96/ZhangPoole96.html
   PDF: volume5/zhang96a.pdf (260K)

   Abstract: A new method is proposed for exploiting causal
   independencies in exact Bayesian network inference.  A Bayesian
   network can be viewed as representing a factorization of a joint
   probability into the multiplication of a set of conditional
   probabilities.  We present a notion of causal independence that
   enables one to further factorize the conditional probabilities into a
   combination of even smaller factors and consequently obtain a
   finer-grain factorization of the joint probability.  The new
   formulation of causal independence lets us specify the conditional
   probability of a variable given its parents in terms of an associative
   and commutative operator, such as ``or'', ``sum'' or ``max'', on the
   contribution of each parent.  We start with a simple algorithm VE for
   Bayesian network inference that, given evidence and a query variable,
   uses the factorization to find the posterior distribution of the
   query. We show how this algorithm can be extended to exploit causal
   independence. Empirical studies, based on the CPCS networks for
   medical diagnosis, show that this method is more efficient than
   previous methods and allows for inference in larger networks than
   previous algorithms.


Schlimmer, J.C. and Wells, P.C. (1996)
  "Quantitative Results Comparing Three Intelligent Interfaces for
Information Capture: A Case Study Adding Name Information into an
Electronic Personal Organizer", 
   Volume 5, pages 329-349.
   PostScript: volume5/schlimmer96a.ps (2.6M)
	       compressed, volume5/schlimmer96a.ps.Z (236K)
   Online Appendix: volume5/schlimmer96a-appendix.hqx (45K) Source code, bin hexed
   HTML:  http://www.cs.washington.edu/research/jair/volume5/schlimmer96a-html/schlimmer96-0.html
   PDF: volume5/schlimmer96a.pdf (177K)

   Abstract: Efficiently entering information into a computer is key to
   enjoying the benefits of computing. This paper describes three
   intelligent user interfaces: handwriting recognition, adaptive menus,
   and predictive fillin. In the context of adding a personUs name and
   address to an electronic organizer, tests show handwriting recognition
   is slower than typing on an on-screen, soft keyboard, while adaptive
   menus and predictive fillin can be twice as fast. This paper also
   presents strategies for applying these three interfaces to other
   information collection domains.


	  		          Volume6


Wilson, D.R. and Martinez, T.R. (1997)
  "Improved Heterogeneous Distance Functions", Volume 6, pages 1-34.
   PostScript: volume6/wilson97a.ps (536K)
	       compressed, volume6/wilson97a.ps.Z (192K)
   HTML:  http://axon.cs.byu.edu/~randy/jair/wilson1.html
   PDF: volume6/wilson97a.pdf (219K)

   Abstract: Instance-based learning techniques typically handle
   continuous and linear input values well, but often do not handle
   nominal input attributes appropriately.  The Value Difference Metric
   (VDM) was designed to find reasonable distance values between nominal
   attribute values, but it largely ignores continuous attributes,
   requiring discretization to map continuous values into nominal values.
   This paper proposes three new heterogeneous distance functions, called
   the Heterogeneous Value Difference Metric (HVDM), the Interpolated
   Value Difference Metric (IVDM), and the Windowed Value Difference
   Metric (WVDM).  These new distance functions are designed to handle
   applications with nominal attributes, continuous attributes, or both.
   In experiments on 48 applications the new distance metrics achieve
   higher classification accuracy on average than three previous distance
   functions on those datasets that have both nominal and continuous
   attributes.



Wermter, S. and Weber, V. (1997)
  "SCREEN: Learning a Flat Syntactic and Semantic Spoken Language Analysis Using Artificial Neural Networks", 
   Volume 6, pages 35-85.
   PostScript: volume6/wermter97a.ps (1.1M)
	       compressed, volume6/wermter97a.ps.Z (290K)
   HTML:  http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume6/wermter97a-html/abstract.html
   PDF: volume6/wermter97a.pdf (533K)

   Abstract: Previous approaches of analyzing spontaneously spoken
   language often have been based on encoding syntactic and semantic
   knowledge manually and symbolically. While there has been some
   progress using statistical or connectionist language models, many
   current spoken- language systems still use a relatively brittle,
   hand-coded symbolic grammar or symbolic semantic component.
   
   In contrast, we describe a so-called screening approach for learning
   robust processing of spontaneously spoken language.  A screening
   approach is a flat analysis which uses shallow sequences of category
   representations for analyzing an utterance at various syntactic,
   semantic and dialog levels.  Rather than using a deeply structured
   symbolic analysis, we use a flat connectionist analysis.  This
   screening approach aims at supporting speech and language processing
   by using (1) data-driven learning and (2) robustness of connectionist
   networks.  In order to test this approach, we have developed the
   SCREEN system which is based on this new robust, learned and flat
   analysis.
   
   In this paper, we focus on a detailed description of SCREEN's
   architecture, the flat syntactic and semantic analysis, the
   interaction with a speech recognizer, and a detailed evaluation
   analysis of the robustness under the influence of noisy or incomplete
   input.  The main result of this paper is that flat representations
   allow more robust processing of spontaneous spoken language than
   deeply structured representations.  In particular, we show how the
   fault-tolerance and learning capability of connectionist networks can
   support a flat analysis for providing more robust spoken-language
   processing within an overall hybrid symbolic/connectionist framework.


De Giacomo, G. and Lenzerini, M. (1997)
  "A Uniform Framework for Concept Definitions in Description Logics", 
   Volume 6, pages 87-110.
   PostScript: volume6/degiacomo97a.ps (603K)
	       compressed, volume6/degiacomo97a.ps.Z (174K)
   PDF: volume6/degiacomo97a.pdf (386K)

   Abstract: Most modern formalisms used in Databases and Artificial
   Intelligence for describing an application domain are based on the
   notions of class (or concept) and relationship among classes.  One
   interesting feature of such formalisms is the possibility of defining
   a class, i.e., providing a set of properties that precisely
   characterize the instances of the class.  Many recent articles point
   out that there are several ways of assigning a meaning to a class
   definition containing some sort of recursion.  In this paper, we argue
   that, instead of choosing a single style of semantics, we achieve
   better results by adopting a formalism that allows for different
   semantics to coexist. We demonstrate the feasibility of our argument,
   by presenting a knowledge representation formalism, the description
   logic muALCQ, with the above characteristics.  In addition to the
   constructs for conjunction, disjunction, negation, quantifiers, and
   qualified number restrictions, muALCQ includes special fixpoint
   constructs to express (suitably interpreted) recursive definitions.
   These constructs enable the usual frame-based descriptions to be
   combined with definitions of recursive data structures such as
   directed acyclic graphs, lists, streams, etc.  We establish several
   properties of muALCQ, including the decidability and the computational
   complexity of reasoning, by formulating a correspondence with a
   particular modal logic of programs called the modal mu-calculus.


Agre, P. and Horswill, I. (1997)
  "Lifeworld Analysis", 
   Volume 6, pages 111-145.
   PostScript: volume6/agre97a.ps (548K)
	       compressed, volume6/agre97a.ps.Z (243K)
   HTML:  http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume6/agre97a-html/lifeworlds.html
   PDF: volume6/agre97a.pdf (447K)

   Abstract: We argue that the analysis of agent/environment interactions
   should be extended to include the conventions and invariants
   maintained by agents throughout their activity.  We refer to this
   hicker notion of environment as a lifeworld and present a partial set
   of formal tools for describing structures of lifeworlds and the ways
   in which they computationally simplify activity.  As one specific
   example, we apply the tools to the analysis of the Toast system and
   show how versions of the system with very different control structures
   in fact implement a common control structure together with different
   conventions for encoding task state in the positions or states of
   objects in the environment.




Darwiche, A. and Provan, G. (1997)
  "Query DAGs: A Practical Paradigm for Implementing Belief-Network Inference", 
   Volume 6, pages 147-176.
   PostScript: volume6/darwiche97a.ps (412K)
	       compressed, volume6/darwiche97a.ps.Z (162K)
   HTML:  http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume6/darwiche97a-html/jair-f.html
   PDF: volume6/darwiche97a.pdf (337K)

   Abstract: We describe a new paradigm for implementing inference in
   belief networks, which consists of two steps: (1) compiling a belief
   network into an arithmetic expression called a Query DAG (Q-DAG); and
   (2) answering queries using a simple evaluation algorithm. Each node
   of a Q-DAG represents a numeric operation, a number, or a symbol for
   evidence.  Each leaf node of a Q-DAG represents the answer to a
   network query, that is, the probability of some event of interest. It
   appears that Q-DAGs can be generated using any of the standard
   algorithms for exact inference in belief networks (we show how they
   can be generated using clustering and conditioning algorithms). The
   time and space complexity of a Q-DAG generation algorithm is no worse
   than the time complexity of the inference algorithm on which it is
   based. The complexity of a Q-DAG evaluation algorithm is linear in the
   size of the Q-DAG, and such inference amounts to a standard evaluation
   of the arithmetic expression it represents. The intended value of
   Q-DAGs is in reducing the software and hardware resources required to
   utilize belief networks in on-line, real-world applications. The
   proposed framework also facilitates the development of on-line
   inference on different software and hardware platforms due to the
   simplicity of the Q-DAG evaluation algorithm. Interestingly enough,
   Q-DAGs were found to serve other purposes: simple techniques for
   reducing Q-DAGs tend to subsume relatively complex optimization
   techniques for belief-network inference, such as network-pruning and
   computation-caching.


Opitz, D.W. and Shavlik, J.W. (1997)
  "Connectionist Theory Refinement: Genetically Searching the Space of Network Topologies", 
   Volume 6, pages 177-209.
   PostScript: volume6/opitz97a.ps (578K)
	       compressed, volume6/opitz97a.ps.Z (267K)
   HTML:  http://www.cs.umt.edu/CS/FAC/OPITZ/JAIR97/main.html
   PDF: volume6/opitz97a.pdf (436K)

   Abstract: An algorithm that learns from a set of examples should
   ideally be able to exploit the available resources of (a) abundant
   computing power and (b) domain-specific knowledge to improve its
   ability to generalize.  Connectionist theory-refinement systems, which
   use background knowledge to select a neural network's topology and
   initial weights, have proven to be effective at exploiting
   domain-specific knowledge; however, most do not exploit available
   computing power. This weakness occurs because they lack the ability to
   refine the topology of the neural networks they produce, thereby
   limiting generalization, especially when given impoverished domain
   theories. We present the REGENT algorithm which uses (a) domain-specific 
   knowledge to help create an initial population of knowledge-based
   neural networks and (b) genetic operators of crossover and mutation
   (specifically designed for knowledge-based networks) to continually
   search for better network topologies. Experiments on three real-world
   domains indicate that our new algorithm is able to significantly
   increase generalization compared to a standard connectionist
   theory-refinement system, as well as our previous algorithm for
   growing knowledge-based networks.


Jonsson, P. and Drakengren, T. (1997)
  "A Complete Classification of Tractability in RCC-5", Volume 6, pages 211-221.
   PostScript: volume6/jonsson97a.ps (168K)
	       compressed, volume6/jonsson97a.ps.Z (69K)
   PDF: volume6/jonsson97a.pdf (205K)
   Online Appendix: volume6/jonsson97a-appendix.tar (39K) Source code

   Abstract: We investigate the computational properties of the spatial
   algebra RCC-5 which is a restricted version of the RCC framework for
   spatial reasoning.  The satisfiability problem for RCC-5 is known to
   be NP-complete but not much is known about its approximately four
   billion subclasses. We provide a complete classification of
   satisfiability for all these subclasses into polynomial and
   NP-complete respectively. In the process, we identify all maximal
   tractable subalgebras which are four in total.


Pollack, M.E., Joslin, D. and Paolucci, M.. (1997)
  "Flaw Selection Strategies for Partial-Order Planning", 
   Volume 6, pages 223-262.
   PostScript: volume6/pollack97a.ps (1.1M)
	       compressed, volume6/pollack97a.ps.Z (387K)
   Online Appendix: volume6/pollack97a-appendix.sit.hqx (80K) Excel Spreadsheet, Experimental Data
   HTML:  http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume6/pollack97a-html/base.html
   PDF: volume6/pollack97a.pdf (592K)

   Abstract: Several recent studies have compared the relative efficiency
   of alternative flaw selection strategies for partial-order causal link
   (POCL) planning.  We review this literature, and present new
   experimental results that generalize the earlier work and explain some
   of the discrepancies in it.  In particular, we describe the Least-Cost
   Flaw Repair (LCFR) strategy developed and analyzed by Joslin and
   Pollack (1994), and compare it with other strategies, including
   Gerevini and Schubert's (1996) ZLIFO strategy.  LCFR and ZLIFO make
   very different, and apparently conflicting claims about the most
   effective way to reduce search-space size in POCL planning.  We
   resolve this conflict, arguing that much of the benefit that Gerevini
   and Schubert ascribe to the LIFO component of their ZLIFO strategy is
   better attributed to other causes.  We show that for many problems, a
   strategy that combines least-cost flaw selection with the delay of
   separable threats will be effective in reducing search-space size, and
   will do so without excessive computational overhead.  Although such a
   strategy thus provides a good default, we also show that certain
   domain characteristics may reduce its effectiveness.


   			       Volume7


Halpern, J.Y. (1997)
  "Defining Relative Likelihood in Partially-Ordered Preferential Structures", 
   Volume 7, pages 1-24.
   PostScript: volume7/halpern97a.ps (573K)
	       compressed, volume7/halpern97a.ps.Z (173K)
   PDF: volume7/halpern97a.pdf (395K)

   Abstract: Starting with a likelihood or preference order on worlds, we
   extend it to a likelihood ordering on sets of worlds in a natural way,
   and examine the resulting logic.  Lewis earlier considered such a
   notion of relative likelihood in the context of studying
   counterfactuals, but he assumed a total preference order on worlds.
   Complications arise when examining partial orders that are not present
   for total orders.  There are subtleties involving the exact approach
   to lifting the order on worlds to an order on sets of worlds.  In
   addition, the axiomatization of the logic of relative likelihood in
   the case of partial orders gives insight into the connection between
   relative likelihood and default reasoning.


Drakengren, T. and Jonsson, P. (1997)
  "Eight Maximal Tractable Subclasses of Allen's Algebra with Metric Time", 
   Volume 7, pages 25-45.
   PostScript: volume7/drakengren97a.ps (245K)
	       compressed, volume7/drakengren97a.ps.Z (97K)
   PDF: volume7/drakengren97a.pdf (958K)
   Online Appendix: volume7/drakengren97a-appendix.tar (359K) tar file containing algebras

   Abstract: This paper combines two important directions of research in
   temporal resoning: that of finding maximal tractable subclasses of
   Allen's interval algebra, and that of reasoning with metric temporal
   information. Eight new maximal tractable subclasses of Allen's
   interval algebra are presented, some of them subsuming previously
   reported tractable algebras.  The algebras allow for metric temporal
   constraints on interval starting or ending points, using the recent
   framework of Horn DLRs.  Two of the algebras can express the notion of
   sequentiality between intervals, being the first such algebras
   admitting both qualitative and metric time.


Mammen, D.L. and Hogg, T. (1997)
  "A New Look at the Easy-Hard-Easy Pattern of Combinatorial Search Difficulty", 
   Volume 7, pages 47-66.
   PostScript: volume7/mammen97a.ps (563K)
	       compressed, volume7/mammen97a.ps.Z (175K)
   HTML:  http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume7/mammen97a-html/ehe3.html
   PDF: volume7/mammen97a.pdf (277K)

   Abstract: The easy-hard-easy pattern in the difficulty of
   combinatorial search problems as constraints are added has been
   explained as due to a competition between the decrease in number of
   solutions and increased pruning. We test the generality of this
   explanation by examining one of its predictions: if the number of
   solutions is held fixed by the choice of problems, then increased
   pruning should lead to a monotonic decrease in search cost. Instead,
   we find the easy-hard-easy pattern in median search cost even when the
   number of solutions is held constant, for some search methods. This
   generalizes previous observations of this pattern and shows that the
   existing theory does not explain the full range of the peak in search
   cost.  In these cases the pattern appears to be due to changes in the
   size of the minimal unsolvable subproblems, rather than changing
   numbers of solutions.


Nevill-Manning, C.G. and Witten, I.H. (1997)
  "Identifying Hierarchical Structure in Sequences: A linear-time algorithm", 
   Volume 7, pages 67-82.
   PostScript: volume7/nevill97a.ps (287K)
	       compressed, volume7/nevill97a.ps.Z (118K)
   PDF: volume7/nevill97a.pdf (106K)
   Online Appendix: volume7/nevill97a-appendix.html, WWW Interface to SEQUITUR
   HTML: http://www.cs.waikato.ac.nz/sequitur/jair
   PDF: volume7/nevill97a.pdf (106K)

   Abstract: SEQUITUR is an algorithm that infers a hierarchical
   structure from a sequence of discrete symbols by replacing repeated
   phrases with a grammatical rule that generates the phrase, and
   continuing this process recursively. The result is a hierarchical
   representation of the original sequence, which offers insights into
   its lexical structure. The algorithm is driven by two constraints that
   reduce the size of the grammar, and produce structure as a by-product. 
   SEQUITUR breaks new ground by operating incrementally. Moreover, the
   method's simple structure permits a proof that it operates in space
   and time that is linear in the size of the input. Our implementation
   can process 50,000 symbols per second and has been applied to an
   extensive range of real world sequences.


Tambe, M. (1997)
  "Towards Flexible Teamwork", 
   Volume 7, pages 83-124.
   PostScript: volume7/tambe97a.ps (940K)
	       compressed, volume7/tambe97a.ps.Z (223K)
   PDF: volume7/tambe97a.pdf (1.7M)
   Online Appendix: http://www.isi.edu/soar/tambe/steam/steam.html, STEAM 1.0

   Abstract: Many AI researchers are today striving to build agent teams
   for complex, dynamic multi-agent domains, with intended applications
   in arenas such as education, training, entertainment, information
   integration, and collective robotics.  Unfortunately, uncertainties in
   these complex, dynamic domains obstruct coherent teamwork.  In
   particular, team members often encounter differing, incomplete, and
   possibly inconsistent views of their environment.  Furthermore, team
   members can unexpectedly fail in fulfilling responsibilities or
   discover unexpected opportunities.  Highly flexible coordination and
   communication is key in addressing such uncertainties.  Simply fitting
   individual agents with precomputed coordination plans will not do, for
   their inflexibility can cause severe failures in teamwork, and their
   domain-specificity hinders reusability.

   Our central hypothesis is that the key to such flexibility and
   reusability is providing agents with general models of teamwork.
   Agents exploit such models to autonomously reason about coordination
   and communication, providing requisite flexibility.  Furthermore, the
   models enable reuse across domains, both saving implementation effort
   and enforcing consistency.  This article presents one general,
   implemented model of teamwork, called STEAM.  The basic building block
   of teamwork in STEAM is joint intentions (Cohen & Levesque, 1991b);
   teamwork in STEAM is based on agents' building up a (partial)
   hierarchy of joint intentions (this hierarchy is seen to parallel
   Grosz & Kraus's partial SharedPlans, 1996).  Furthermore, in STEAM,
   team members monitor the team's and individual members' performance,
   reorganizing the team as necessary.  Finally, decision-theoretic
   communication selectivity in STEAM ensures reduction in communication
   overheads of teamwork, with appropriate sensitivity to the
   environmental conditions.  This article describes STEAM's application
   in three different complex domains, and presents detailed empirical
   results.


Leherte, L., Glasgow, J., Baxter, K., Steeg, E. and Fortier, S. (1997)
  "Analysis of Three-Dimensional Protein Images", 
   Volume 7, pages 125-159.
   PostScript: volume7/leherte97a.ps (3.1M)
	       compressed, volume7/leherte97a.ps.Z (525K)
   PDF: volume7/leherte97a.pdf (471K)

   Abstract: A fundamental goal of research in molecular biology is to
   understand protein structure. Protein crystallography is currently the
   most successful method for determining the three-dimensional (3D)
   conformation of a protein, yet it remains labor intensive and relies
   on an expert's ability to derive and evaluate a protein scene model.
   In this paper, the problem of protein structure determination is
   formulated as an exercise in scene analysis.  A computational
   methodology is presented in which a 3D image of a protein is segmented
   into a graph of critical points.  Bayesian and certainty factor
   approaches are described and used to analyze critical point graphs and
   identify meaningful substructures, such as alpha-helices and
   beta-sheets.  Results of applying the methodologies to protein images
   at low and medium resolution are reported.  The research is related to
   approaches to representation, segmentation and classification in
   vision, as well as to top-down approaches to protein structure
   prediction.


Ihrig, L.H. and Kambhampati, S. (1997)
  "Storing and Indexing Plan Derivations through Explanation-based Analysis 
   of Retrieval Failures", Volume 7, pages 161-198.
   PostScript: volume7/ihrig97a.ps (1.0M)
	       compressed, volume7/ihrig97a.ps.Z (350K)
   HTML:  http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume7/ihrig97a-html/ihrig-kambh97.html
   PDF: volume7/ihrig97a.pdf (496K)

   Abstract: Case-Based Planning (CBP) provides a way of scaling up
   domain-independent planning to solve large problems in complex
   domains.  It replaces the detailed and lengthy search for a solution
   with the retrieval and adaptation of previous planning experiences.
   In general, CBP has been demonstrated to improve performance over
   generative (from-scratch) planning.  However, the performance
   improvements it provides are dependent on adequate judgements as to
   problem similarity.  In particular, although CBP may substantially
   reduce planning effort overall, it is subject to a mis-retrieval
   problem. The success of CBP depends on these retrieval errors being
   relatively rare. This paper describes the design and implementation of
   a replay framework for the case-based planner DERSNLP+EBL. DERSNLP+EBL
   extends current CBP methodology by incorporating explanation-based
   learning techniques that allow it to explain and learn from the
   retrieval failures it encounters.  These techniques are used to refine
   judgements about case similarity in response to feedback when a wrong
   decision has been made.  The same failure analysis is used in building
   the case library, through the addition of repairing cases. Large
   problems are split and stored as single goal subproblems.  Multi-goal
   problems are stored only when these smaller cases fail to be merged
   into a full solution.  An empirical evaluation of this approach
   demonstrates the advantage of learning from experienced retrieval
   failure.


Zhang, N.L. and Liu, W. (1997)
  "A Model Approximation Scheme for Planning in Partially Observable 
   Stochastic Domains", Volume 7, pages 199-230.
   PostScript: volume7/zhang97a.ps (399K)
	       compressed, volume7/zhang97a.ps.Z (184K)
   PDF: volume7/zhang97a.pdf (405K)

   Abstract: Partially observable Markov decision processes (POMDPs) are
   a natural model for planning problems where effects of actions are
   nondeterministic and the state of the world is not completely
   observable.  It is difficult to solve POMDPs exactly.  This paper
   proposes a new approximation scheme.  The basic idea is to transform a
   POMDP into another one where additional information is provided by an
   oracle. The oracle informs the planning agent that the current state
   of the world is in a certain region.  The transformed POMDP is
   consequently said to be region observable. It is easier to solve than
   the original POMDP.  We propose to solve the transformed POMDP and use
   its optimal policy to construct an approximate policy for the original
   POMDP.  By controlling the amount of additional information that the
   oracle provides, it is possible to find a proper tradeoff between
   computational time and approximation quality.  In terms of algorithmic
   contributions, we study in details how to exploit region observability
   in solving the transformed POMDP. To facilitate the study, we also
   propose a new exact algorithm for general POMDPs.  The algorithm is
   conceptually simple and yet is significantly more efficient than all
   previous exact algorithms.


Monderer, D. and Tennenholtz, M. (1997)
  "Dynamic Non-Bayesian Decision Making", 
   Volume 7, pages 231-248.
   PostScript: volume7/monderer97a.ps (238K)
	       compressed, volume7/monderer97a.ps.Z (95K)
   PDF: volume7/monderer97a.pdf (269K)

   Abstract: The model of a non-Bayesian agent who faces a repeated game
   with incomplete information against Nature is an appropriate tool for
   modeling general agent-environment interactions.  In such a model the
   environment state (controlled by Nature) may change arbitrarily, and
   the feedback/reward function is initially unknown. The agent is not
   Bayesian, that is he does not form a prior probability neither on the
   state selection strategy of Nature, nor on his reward function.  A
   policy for the agent is a function which assigns an action to every
   history of observations and actions.  Two basic feedback structures
   are considered. In one of them -- the perfect monitoring case -- the
   agent is able to observe the previous environment state as part of his
   feedback, while in the other -- the imperfect monitoring case -- all
   that is available to the agent is the reward obtained. Both of these
   settings refer to partially observable processes, where the current
   environment state is unknown.  Our main result refers to the
   competitive ratio criterion in the perfect monitoring case. We prove
   the existence of an efficient stochastic policy that ensures that the
   competitive ratio is obtained at almost all stages with an arbitrarily
   high probability, where efficiency is measured in terms of rate of
   convergence.  It is further shown that such an optimal policy does not
   exist in the imperfect monitoring case. Moreover, it is proved that in
   the perfect monitoring case there does not exist a deterministic
   policy that satisfies our long run optimality criterion.  In addition,
   we discuss the maxmin criterion and prove that a deterministic
   efficient optimal strategy does exist in the imperfect monitoring case
   under this criterion. Finally we show that our approach to long-run
   optimality can be viewed as qualitative, which distinguishes it from
   previous work in this area.


Frank, J., Cheeseman, P. and Stutz, J. (1997)
  "When Gravity Fails: Local Search Topology", 
   Volume 7, pages 249-281.
   PostScript: volume7/frank97a.ps (612K)
	       compressed, volume7/frank97a.ps.Z (186K)
   PDF: volume7/frank97a.pdf (409K)

   Abstract: Local search algorithms for combinatorial search problems
   frequently encounter a sequence of states in which it is impossible to
   improve the value of the objective function; moves through these
   regions, called plateau moves, dominate the time spent in local
   search.  We analyze and characterize plateaus for three different
   classes of randomly generated Boolean Satisfiability problems.  We
   identify several interesting features of plateaus that impact the
   performance of local search algorithms.  We show that local minima
   tend to be small but occasionally may be very large.  We also show
   that local minima can be escaped without unsatisfying a large number
   of clauses, but that systematically searching for an escape route may
   be computationally expensive if the local minimum is large.  We show
   that plateaus with exits, called benches, tend to be much larger than
   minima, and that some benches have very few exit states which local
   search can use to escape.  We show that the solutions (i.e., global
   minima) of randomly generated problem instances form clusters, which
   behave similarly to local minima.  We revisit several enhancements of
   local search algorithms and explain their performance in light of our
   results.  Finally we discuss strategies for creating the next
   generation of local search algorithms.  


Kaindl, H. and  Kainz, G. (1997)
  "Bidirectional Heuristic Search Reconsidered", 
   Volume 7, pages 283-317.
   PostScript: volume7/kaindl97a.ps (858K)
	       compressed, volume7/kaindl97a.ps.Z (338K)
   PDF: volume7/kaindl97a.pdf (386K)

   Abstract: The assessment of bidirectional heuristic search has been
   incorrect since it was first published more than a quarter of a
   century ago.  For quite a long time, this search strategy did not
   achieve the expected results, and there was a major misunderstanding
   about the reasons behind it.  Although there is still wide-spread
   belief that bidirectional heuristic search is afflicted by the problem
   of search frontiers passing each other, we demonstrate that this
   conjecture is wrong.  Based on this finding, we present both a new
   generic approach to bidirectional heuristic search and a new approach
   to dynamically improving heuristic values that is feasible in
   bidirectional search only.  These approaches are put into perspective
   with both the traditional and more recently proposed approaches in
   order to facilitate a better overall understanding.  Empirical results
   of experiments with our new approaches show that bidirectional
   heuristic search can be performed very efficiently and also with
   limited memory.  These results suggest that bidirectional heuristic
   search appears to be better for solving certain difficult problems
   than corresponding unidirectional search.  This provides some evidence
   for the usefulness of a search strategy that was long neglected.  In
   summary, we show that bidirectional heuristic search is viable and
   consequently propose that it be reconsidered.

   			       Volume8


Engelfriet, J. (1998)
  "Monotonicity and Persistence in Preferential Logics", 
   Volume 8, pages 1-21.
   PostScript: volume8/engelfriet98a.ps (266K)
	       compressed, volume8/engelfriet98a.ps.Z (121K)
   PDF: volume8/engelfriet98a.pdf (310K)

   Abstract: An important characteristic of many logics for Artificial
   Intelligence is their nonmonotonicity. This means that adding a
   formula to the premises can invalidate some of the consequences. There
   may, however, exist formulae that can always be safely added to the
   premises without destroying any of the consequences: we say they
   respect monotonicity. Also, there may be formulae that, when they are
   a consequence, can not be invalidated when adding any formula to the
   premises: we call them conservative. We study these two classes of
   formulae for preferential logics, and show that they are closely
   linked to the formulae whose truth-value is preserved along the
   (preferential) ordering. We will consider some preferential logics for
   illustration, and prove syntactic characterization results for them.
   The results in this paper may improve the efficiency of theorem
   provers for preferential logics.


Gogic, G., Papadimitriou, C.H., and Sideri, M. (1998)
  "Incremental Recompilation of Knowledge", 
   Volume 8, pages 23-37.
   PostScript: volume8/gogic98a.ps (189K)
	       compressed, volume8/gogic98a.ps.Z (77K)
   PDF: volume8/gogic98a.pdf (659K)

   Abstract: Approximating a general formula from above and below by Horn
   formulas (its Horn envelope and Horn core, respectively) was proposed
   by Selman and Kautz (1991, 1996) as a form of ``knowledge
   compilation,'' supporting rapid approximate reasoning; on the negative
   side, this scheme is static in that it supports no updates, and has
   certain complexity drawbacks pointed out by Kavvadias, Papadimitriou
   and Sideri (1993).  On the other hand, the many frameworks and schemes
   proposed in the literature for theory update and revision are plagued
   by serious complexity-theoretic impediments, even in the Horn case, as
   was pointed out by Eiter and Gottlob (1992), and is further
   demonstrated in the present paper.  More fundamentally, these schemes
   are not inductive, in that they may lose in a single update any
   positive properties of the represented sets of formulas (small size,
   Horn structure, etc.).  In this paper we propose a new scheme,
   incremental recompilation, which combines Horn approximation and
   model-based updates; this scheme is inductive and very efficient, free
   of the problems facing its constituents.  A set of formulas is
   represented by an upper and lower Horn approximation.  To update, we
   replace the upper Horn formula by the Horn envelope of its
   minimum-change update, and similarly the lower one by the Horn core of
   its update; the key fact which enables this scheme is that Horn
   envelopes and cores are easy to compute when the underlying formula is
   the result of a minimum-change update of a Horn formula by a clause.
   We conjecture that efficient algorithms are possible for more complex
   updates.


Argamon-Engelson, S. and Koppel, M. (1998)
  "Tractability of Theory Patching", 
   Volume 8, pages 39-65.
   PostScript: volume8/argamon98a.ps (282K)
	       compressed, volume8/argamon98a.ps.Z (128K)
   PDF: volume8/argamon98a.pdf (1.1M)

   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 theory satisfies two conditions: that revisions
   to each theory component have monotonic effects on the classification
   of examples, and that theory components act independently in the
   classification of examples in the theory.  We also show how the
   concepts introduced can be used to determine the soundness and
   completeness of particular theory patching algorithms.


Moore, A. and Lee, M.S. (1998)
  "Cached Sufficient Statistics for Efficient Machine Learning with Large Datasets", 
   Volume 8, pages 67-91.
   PostScript: volume8/moore98a.ps (303K)
	       compressed, volume8/moore98a.ps.Z (122K)
   PDF: volume8/moore98a.pdf (300K)

   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.


Srivastava, B. and Kambhampati, S. (1998)
  "Synthesizing Customized Planners from Specifications", 
   Volume 8, pages 93-128.
   PostScript: volume8/srivastava98a.ps (750K)
	       compressed, volume8/srivastava98a.ps.Z (221K)
   PDF: volume8/srivastava98a.pdf (478K)

   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.


Fuernkranz, J. (1998)
  "Integrative Windowing", 
   Volume 8, pages 129-164.
   PostScript: volume8/fuernkranz98a.ps (455K)
	       compressed, volume8/fuernkranz98a.ps.Z (166K)
   HTML:  http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume8/fuernkranz98a-html/fuernkranz98a.html
   PDF: volume8/fuernkranz98a.pdf (383K)

   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 behavior 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
   achieve run-time gains in a set of experiments in a simple domain with
   artificial noise.


Darwiche, A. (1998)
  "Model-Based Diagnosis using Structured System Descriptions", 
   Volume 8, pages 165-222.
   PostScript: volume8/darwiche98a.ps (1.1M)
	       compressed, volume8/darwiche98a.ps.Z (327K)
   PDF: volume8/darwiche98a.pdf (2.6M)

   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.


Finkelstein, L. and Markovitch, S. (1998)
  "A Selective Macro-learning Algorithm and its Application to 
the NxN Sliding-Tile Puzzle", 
   Volume 8, pages 223-263.
   PostScript: volume8/finkelstein98a.ps (516K)
	       compressed, volume8/finkelstein98a.ps.Z (209K)
   Online Appendix: volume8/finkelstein98a-appendix.html (10K) Source code
   HTML:  http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume8/finkelstein98a-html/hillary.html
   PDF: volume8/finkelstein98a.pdf (1.6M)

   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 NxN sliding-tile puzzles. After
   learning on small puzzles, the system is able to efficiently solve
   puzzles of any size.


   			       Volume9


Littman, M.L., Goldsmith, J. and Mundhenk M. (1998)
  "The Computational Complexity of Probabilistic Planning", 
   Volume 9, pages 1-36.
   PostScript: volume9/littman98a.ps (975K)
	       compressed, volume9/littman98a.ps.Z (324K)
   PDF: volume9/littman98a.pdf (488K)

   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, NP^PP, co-NP^PP, and PSPACE.  In the process of
   proving that certain planning problems are complete for NP^PP, we
   introduce a new basic NP^PP-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.


Ledeniov, O. and Markovitch, S. (1998)
  "The Divide-and-Conquer Subgoal-Ordering Algorithm for Speeding up Logic Inference", 
   Volume 9, pages 37-97.
   PostScript: volume9/ledeniov98a.ps (644K)
	       compressed, volume9/ledeniov98a.ps.Z (253K)
   PDF: volume9/ledeniov98a.pdf (600K)

   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.


Backstrom, C. (1998)
  "Computational Aspects of Reordering Plans", 
   Volume 9, pages 99-137.
   PostScript: volume9/backstrom98a.ps (815K)
	       compressed, volume9/backstrom98a.ps.Z (241K)
   PDF: volume9/backstrom98a.pdf (653K)

   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.


Cook, D.J. and Varnell, R.C. (1998)
  "Adaptive Parallel Iterative Deepening Search", 
   Volume 9, pages 139-165.
   PostScript: volume9/cook98a.ps (628K)
	       compressed, volume9/cook98a.ps.Z (196K)
   Online Appendix: volume9/cook98a-appendix.tar (225K) Eureka 2.0 Source code
   HTML:  http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume9/cook98a-html/eureka.html
   PDF: volume9/cook98a.pdf (276K)

   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.  


Ruiz, A., Lopez-de-Teruel, P.E. and Garrido, M.C. (1998)
  "Probabilistic Inference from Arbitrary Uncertainty using Mixtures of Factorized Generalized Gaussians", 
   Volume 9, pages 167-217.
   PostScript: volume9/ruiz98a.ps (3.5M)
	       compressed, volume9/ruiz98a.ps.Z (1.1M)
   PDF: volume9/ruiz98a.pdf (753K)

   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.


Vandegriend, B. and Culberson, J. (1998)
  "The Gn,m Phase Transition is Not Hard for the Hamiltonian Cycle Problem", 
   Volume 9, pages 219-245.
   PostScript: volume9/vandegriend98a.ps (574K)
	       compressed, volume9/vandegriend98a.ps.Z (180K)
   Online Appendix1: volume9/vandegriend98a-appendix1.tar (368K) source code for HC program
   Online Appendix2: volume9/vandegriend98a-appendix2/append.html (3K) HTML illustration of artifact
   PDF: volume9/vandegriend98a.pdf (394K)

   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.


Wiebe, J.M., O'Hara, T.P., Ohrstrom-Sandgren, T. and McKeever, K.J. (1998)
  "An Empirical Approach to Temporal Reference Resolution", 
   Volume 9, pages 247-293.
   PostScript: volume9/wiebe98a.ps (726K)
	       compressed, volume9/wiebe98a.ps.Z (226K)
   Online Appendix1: volume9/wiebe98a-appendix.ps (353K) Temporal reference resolution algorithm 
   HTML:  http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume9/wiebe98a-html/journal98.html
   PDF: volume9/wiebe98a.pdf (483K)

   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.


Mazer, E., Ahuactzin, J.M., and Bessiere, P. (1998)
  "The Ariadne's Clew Algorithm", 
   Volume 9, pages 295-316.
   PostScript: volume9/mazer98a.ps (1.29M)
	       compressed, volume9/mazer98a.ps.Z (288K)
   Online Appendix1: volume9/mazer98a-appendix1.tar (421K) Source code
   Online Appendix2: volume9/mazer98a-appendix2.tar (12.9M) Quicktime movies
   HTML:  http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume9/mazer98a-html/ariane.html
   PDF: volume9/mazer98a.pdf (825K)

   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.


Di Caro, G. and Dorigo, M. (1998)
  "AntNet: Distributed Stigmergetic Control for Communications Networks", 
   Volume 9, pages 317-365.
   PostScript: volume9/dicaro98a.ps (1.22M)
	       compressed, volume9/dicaro98a.ps.Z (390K)
   PDF: volume9/dicaro98a.pdf (704K)

   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.


Fox, M. and Long, D. (1998)
  "The Automatic Inference of State Invariants in TIM", 
   Volume 9, pages 367-421.
   PostScript: volume9/fox98a.ps (423K)
	       compressed, volume9/fox98a.ps.Z (173K)
   Online Appendix1: volume9/fox98a-appendix.tar (266K) TIM code and examples
   PDF: volume9/fox98a.pdf (433K)

   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.


Rintanen, J. (1998)
  "Complexity of Prioritized Default Logics", 
   Volume 9, pages 423-461.
   PostScript: volume9/rintanen98a.ps (474K)
	       compressed, volume9/rintanen98a.ps.Z (211K)
   PDF: volume9/rintanen98a.pdf (1.7M)

   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.


Artale, A. and Franconi, E. (1998)
  "A Temporal Description Logic for Reasoning about Actions and Plans", 
   Volume 9, pages 463-506.
   PostScript: volume9/artale98a.ps (1.0M)
	       compressed, volume9/artale98a.ps.Z (292K)
   PDF: volume9/artale98a.pdf (699K)

   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.


	  		          Volume10


Davis, E. (1999)
  "Order of Magnitude Comparisons of Distance", 
   Volume 10, pages 1-38.
   PostScript: volume10/davis99a.ps (416K)
	       compressed, volume10/davis99a.ps.Z (188K)
   HTML:  http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume10/davis99a-html/om-dist.jair.html
   PDF: volume10/davis99a.pdf (461K)

   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.


Hogg, T. (1999)
  "Solving Highly Constrained Search Problems with Quantum Computers", 
   Volume 10, pages 39-66.
   PostScript: volume10/hogg99a.ps (252K)
	       compressed, volume10/hogg99a.ps.Z (116K)
   HTML:  http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume10/hogg99a-html/paper.html
   PDF: volume10/hogg99a.pdf (1076K)

   Abstract: A previously developed quantum search algorithm for solving
   1-SAT problems in a single step is generalized to apply to a range
   of highly constrained k-SAT problems. We identify a bound on the
   number of clauses in satisfiability problems for which the
   generalized algorithm can find a solution in a constant number of
   steps as the number of variables increases. This performance
   contrasts with the linear growth in the number of steps required by
   the best classical algorithms, and the exponential number required
   by classical and quantum methods that ignore the problem
   structure. In some cases, the algorithm can also guarantee that
   insoluble problems in fact have no solutions, unlike previously
   proposed quantum search algorithms. 


Halpern, J.Y. (1999)
  "A Counterexample to Theorems of Cox and Fine", 
   Volume 10, pages 67-85.
   PostScript: volume10/halpern99a.ps (501K)
	       compressed, volume10/halpern99a.ps.Z (148K)
   PDF: volume10/halpern99a.pdf (257K)

   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.


Long, D. and Fox, M. (1999)
  "Efficient Implementation of the Plan Graph in STAN", 
   Volume 10, pages 87-115.
   PostScript: volume10/long99a.ps (453K)
	       compressed, volume10/long99a.ps.Z (179K)
   Online Appendix1: volume10/long99a-appendix.tar (931K) Code and data
   PDF: volume10/long99a.pdf (422K)

   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.


Friedman, N. and Halpern, J.Y. (1999)
  "Modeling  Belief  in  Dynamic  Systems, Part  II:  Revision  and  Update", 
   Volume 10, pages 117-167.
   PostScript: volume10/friedman99a.ps (552K)
	       compressed, volume10/friedman99a.ps.Z (214K)
   PDF: volume10/friedman99a.pdf (541K)

   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.


Fuchs, D. and Fuchs, M. (1999)
  "Cooperation between Top-Down and Bottom-Up Theorem Provers", 
   Volume 10, pages 169-198.
   PostScript: volume10/fuchs99a.ps (308K)
	       compressed, volume10/fuchs99a.ps.Z (134K)
   PDF: volume10/fuchs99a.pdf (333K)

   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.


Lukasiewicz, T. (1999)
  "Probabilistic Deduction with Conditional Constraints over Basic Events", 
   Volume 10, pages 199-241.
   PostScript: volume10/lukasiewicz99a.ps (768K)
	       compressed, volume10/lukasiewicz99a.ps.Z (290K)
   PDF: volume10/lukasiewicz99a.pdf (674K)

   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.


Cohen, W.W., Schapire, R.E., and Singer, Y. (1999)
  "Learning to Order Things", 
   Volume 10, pages 243-270.
   PostScript: volume10/cohen99a.ps (512K)
	       compressed, volume10/cohen99a.ps.Z (229K)
   PDF: volume10/cohen99a.pdf (445K)

   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.


Ting, K.M. and Witten, I.H. (1999)
  "Issues in Stacked Generalization", 
   Volume 10, pages 271-289.
   PostScript: volume10/ting99a.ps (469K)
	       compressed, volume10/ting99a.ps.Z (140K)
   PDF: volume10/ting99a.pdf (245K)

   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.


Jaakkola, T.S. and Jordan, M.I. (1999)
  "Variational Probabilistic Inference and the QMR-DT Network", 
   Volume 10, pages 291-322.
   PostScript: volume10/jaakkola99a.ps (894K)
	       compressed, volume10/jaakkola99a.ps.Z (249K)
   HTML:  http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume10/jaakkola99a-html/paper.html
   PDF: volume10/jaakkola99a.pdf (695K)

   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.


Rintanen, J. (1999)
  "Constructing Conditional Plans by a Theorem-Prover", 
   Volume 10, pages 323-352.
   PostScript: volume10/rintanen99a.ps (354K)
	       compressed, volume10/rintanen99a.ps.Z (161K)
   PDF: volume10/rintanen99a.pdf (1.1M)

   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.


Joslin, D.E. and Clements, D.P. (1999)
  "Squeaky Wheel Optimization", 
   Volume 10, pages 353-373.
   PostScript: volume10/joslin99a.ps (474K)
	       compressed, volume10/joslin99a.ps.Z (148K)
   HTML:  http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume10/joslin99a-html/swo.html
   PDF: volume10/joslin99a.pdf (254K)

   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.


Chien, S., Stechert, A. and Mutz, D. (1999)
  "Efficient Heuristic Hypothesis Ranking", 
   Volume 10, pages 375-397.
   PostScript: volume10/chien99a.ps (709K)
	       compressed, volume10/chien99a.ps.Z (263K)
   PDF: volume10/chien99a.pdf (460K)

   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.


Borgida, A. (1999)
  "Extensible Knowledge Representation: the Case of Description Reasoners", 
   Volume 10, pages 399-434.
   PostScript: volume10/borgida99a.ps (1099K)
	       compressed, volume10/borgida99a.ps.Z (609K)
   PDF: volume10/borgida99a.pdf (534K)

   Abstract: This paper offers an approach to extensible knowledge
   representation and reasoning for a family of formalisms known as
   Description Logics. 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.


Barber, D. and van de Laar, P. (1999)
  "Variational Cumulant Expansions for Intractable Distributions", 
   Volume 10, pages 435-455.
   PostScript: volume10/barber99a.ps (430K)
	       compressed, volume10/barber99a.ps.Z (186K)
   PDF: volume10/barber99a.pdf (3378K)

   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 standard 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.


Birnbaum, E. and Lozinskii, E.L. (1999)
  "The Good Old Davis-Putnam Procedure Helps Counting Models", 
   Volume 10, pages 457-477.
   PostScript: volume10/birnbaum99a.ps (738K)
	       compressed, volume10/birnbaum99a.ps.Z (308K)
   PDF: volume10/birnbaum99a.pdf (253K)

   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(nm^d), where d=-1/log(1-p).  The practical
   performance of CDP has been estimated in a series of experiments on a
   wide variety of CNF formulas.


	  		          Volume11


Boutilier, C., Dean, T. and Hanks, S. (1999)
  "Decision-Theoretic Planning: Structural Assumptions and Computational Leverage", 
   Volume 11, pages 1-94.
   PostScript: volume11/boutilier99a.ps (1.3M)
	       compressed, volume11/boutilier99a.ps.Z (527K)
   PDF: volume11/boutilier99a.pdf (942K)

   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.


Resnik, P. (1999)
  "Semantic Similarity in a Taxonomy: An Information-Based Measure and its Application to Problems of Ambiguity in Natural Language", 
   Volume 11, pages 95-130.
   PostScript: volume11/resnik99a.ps (351K)
	       compressed, volume11/resnik99a.ps.Z (148K)
   PDF: volume11/resnik99a.pdf (396K)

   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.


Brodley, C.E. and Friedl, M.A. (1999)
  "Identifying Mislabeled Training Data", 
   Volume 11, pages 131-167.
   PostScript: volume11/brodley99a.ps (3.4M)
	       compressed, volume11/brodley99a.ps.Z (742K)
   PDF: volume11/brodley99a.pdf (455K)

   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 percent.  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.


Opitz, D. and Maclin, R. (1999)
  "Popular Ensemble Methods: An Empirical Study", 
   Volume 11, pages 169-198.
   PostScript: volume11/opitz99a.ps (1.1M)
	       compressed, volume11/opitz99a.ps.Z (559K)
   HTML:  http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume11/opitz99a-html/paper.html
   PDF: volume11/opitz99a.pdf (281K)

   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 & Shapire, 1996; Shapire, 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.


Calvanese, D., Lenzerini, M. and Nardi, D. (1999)
  "Unifying Class-Based Representation Formalisms", 
   Volume 11, pages 199-240.
   PostScript: volume11/calvanese99a.ps (490K)
	       compressed, volume11/calvanese99a.ps.Z (221K)
   HTML:  http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume11/calvanese99a-html/calvanese99a-html.html
   PDF: volume11/calvanese99a.pdf (558K)

   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.


Moriarty, D.E., Schultz, A.C., and Grefenstette, J.J. (1999)
  "Evolutionary Algorithms for Reinforcement Learning", 
   Volume 11, pages 241-276.
   PostScript: volume11/moriarty99a.ps (406K)
	       compressed, volume11/moriarty99a.ps.Z (168K)
   PDF: volume11/moriarty99a.pdf (299K)

   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.


Rosati, R. (1999)
  "Reasoning about Minimal Belief and Negation as Failure", 
   Volume 11, pages 277-300.
   PostScript: volume11/rosati99a.ps (530K)
	       compressed, volume11/rosati99a.ps.Z (157K)
   HTML:  http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume11/rosati99a-html/rosati99a-html.html
   PDF: volume11/rosati99a.pdf (353K)

   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 entailment in propositional MBNF lies at the third level of
   the polynomial hierarchy, 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.



Ygge, F. and Akkermans, H. (1999)
  "Decentralized Markets versus Central Control: A Comparative Study", 
   Volume 11, pages 301-333.
   PostScript: volume11/ygge99a.ps (1.0M)
	       compressed, volume11/ygge99a.ps.Z (459K)
   PDF: volume11/ygge99a.pdf (455K)

   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''.


Argamon-Engelson, S. and Dagan, I. (1999)
  "Committee-Based Sample Selection for Probabilistic Classifiers", 
   Volume 11, pages 335-360.
   PostScript: volume11/argamon99a.ps (375K)
	       compressed, volume11/argamon99a.ps.Z (459K)
   PDF: volume11/argamon99a.pdf (135K)

   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, extending
   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.


Cristani, M. (1999)
  "The Complexity of Reasoning about Spatial Congruence", 
   Volume 11, pages 361-390.
   PostScript: volume11/cristani99a.ps (709K)
	       compressed, volume11/cristani99a.ps.Z (218K)
   Online Appendix1: volume11/cristani99a-appendix.ps (102K) Lisp code
   PDF: volume11/cristani99a.pdf (553K)

   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.


Fox, D., Burgard, W. and Thrun, S. (1999)
  "Markov Localization for Mobile Robots in Dynamic Environments", 
   Volume 11, pages 391-427.
   PostScript: volume11/fox99a.ps (13.5M)
	       compressed, volume11/fox99a.ps.Z (3.2M)
   Online Appendix1: http://www.cs.cmu.edu/~dfox/museum-projects.html 
   HTML:  http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume11/fox99a-html/jair-localize.html
   PDF: volume11/fox99a.pdf (5.3M)

   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.


Halpern, J.Y. (1999)
  "Cox's Theorem Revisited", 
   Volume 11, pages 429-435.
   PostScript: volume11/halpern99b.ps (128K)
	       compressed, volume11/halpern99b.ps.Z (52K)
   PDF: volume11/halpern99b.pdf (154K)

   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.

	  		          Volume12


Kambhampati, S. (2000)
  "Planning Graph as a (Dynamic) CSP: Exploiting EBL, DDB and other CSP Search Techniques in Graphplan", 
   Volume 12, pages 1-34.
   PostScript: volume12/kambhampati00a.ps (859K)
	       compressed, volume12/kambhampati00a.ps.Z (302K)
   PDF: volume12/kambhampati00a.pdf (248K)

   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.


Barber, F. (2000)
  "Reasoning on Interval and Point-based Disjunctive Metric Constraints in Temporal Contexts", 
   Volume 12, pages 35-86.
   PostScript: volume12/barber00a.ps (2.8M)
	       compressed, volume12/barber00a.ps.Z (500K)
   HTML:  http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume12/barber00a-html/Barber.html
   PDF: volume12/barber00a.pdf (241K)

   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.


Neal, R.M. (2000)
  "On Deducing Conditional Independence from d-Separation in Causal Graphs with Feedback (Research Note)", 
   Volume 12, pages 87-91.
   PostScript: volume12/neal00a.ps (287K)
	       compressed, volume12/neal00a.ps.Z (81K)
   PDF: volume12/neal00a.pdf (132K)

   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.


Xu, K. and Li, W. (2000)
  "Exact Phase Transitions in Random Constraint Satisfaction Problems", 
   Volume 12, pages 93-103.
   PostScript: volume12/xu00a.ps (208K)
	       compressed, volume12/xu00a.ps.Z (101K)
   PDF: volume12/xu00a.pdf (268K)

   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.


Kaminka, G.A. and Tambe, M. (2000)
  "Robust Agent Teams via Socially-Attentive Monitoring", 
   Volume 12, pages 105-147.
   PostScript: volume12/kaminka00a.ps (553K)
	       compressed, volume12/kaminka00a.ps.Z (243K)
   PDF: volume12/kaminka00a.pdf (537K)

   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.


Baxter, J. (2000)
  "A Model of Inductive Bias Learning", 
   Volume 12, pages 149-198.
   PostScript: volume12/baxter00a.ps (476K)
	       compressed, volume12/baxter00a.ps.Z (216K)
   PDF: volume12/baxter00a.pdf (398K)

   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.


Tobies, S. (2000)
  "The Complexity of Reasoning with Cardinality Restrictions and Nominals in Expressive Description Logics", 
   Volume 12, pages 199-217.
   PostScript: volume12/tobies00a.ps (306K)
	       compressed, volume12/tobies00a.ps.Z (144K)
   Online Appendix1: volume12/tobies00a-appendix1.html (2K) online bibliography
   HTML:  http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume12/tobies00a-html/tobies00a.html
   PDF: volume12/tobies00a.pdf (369K)

   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 C^2, 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 C^2 (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.


Becker, A., Bar-Yehuda, R. and Geiger, D. (2000)
  "Randomized Algorithms for the Loop Cutset Problem", 
   Volume 12, pages 219-234.
   PostScript: volume12/becker00a.ps (215K)
	       compressed, volume12/becker00a.ps.Z (86K)
   PDF: volume12/becker00a.pdf (247K)

   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 6^k kn) steps with probability at least 
   1 - (1 - 1/(6^k))^c6^k, 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.


Singer, J., Gent, I.P. and Smaill, A. (2000)
  "Backbone Fragility and the Local Search Cost Peak", 
   Volume 12, pages 235-270.
   PostScript: volume12/singer00a.ps (1.2M)
	       compressed, volume12/singer00a.ps.Z (326K)
   PDF: volume12/singer00a.pdf (811K)

   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.


Nebel, B. (2000)
  "On the Compilability and Expressive Power of Propositional Planning Formalisms", 
   Volume 12, pages 271-315.
   PostScript: volume12/nebel00a.ps (419K)
	       compressed, volume12/nebel00a.ps.Z (186K)
   PDF: volume12/nebel00a.pdf (293K)

   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.


Halpern, J.Y. (2000)
  "Axiomatizing Causal Reasoning", 
   Volume 12, pages 317-337.
   PostScript: volume12/halpern00a.ps (565K)
	       compressed, volume12/halpern00a.ps.Z (170K)
   PDF: volume12/halpern00a.pdf (275K)

   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. In addition, the complexity of the
   decision procedures is characterized for all the languages and classes
   of models considered.


Koehler, J. and Hoffmann, J. (2000)
  "On Reasonable and Forced Goal Orderings and their Use in an Agenda-Driven Planning Algorithm", 
   Volume 12, pages 338-386.
   PostScript: volume12/koehler00a.ps (541K)
	       compressed, volume12/koehler00a.ps.Z (244K)
   Online Appendix1: volume12/koehler00a.html (1k) Source code and domains
   PDF: volume12/koehler00a.pdf (598K)

   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.


Walker, M.A. (2000)
  "An Application of Reinforcement Learning to Dialogue Strategy Selection in a Spoken Dialogue System for Email", 
   Volume 12, pages 387-416.
   PostScript: volume12/walker00a.ps (346K)
	       compressed, volume12/walker00a.ps.Z (165K)
   PDF: volume12/walker00a.pdf (419K)

   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.


	  		          Volume13

Cadoli, M., Donini, F.M., Liberatore, P., and Schaerf, M. (2000)
  "Space Efficiency of Propositional Knowledge Representation Formalisms", 
   Volume 13, pages 1-31.
   PostScript: volume13/cadoli00a.ps (511K)
	       compressed, volume13/cadoli00a.ps.Z (256K)
   HTML:  http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume13/cadoli00a-html/cadoli00a.html
   PDF: volume13/cadoli00a.pdf (305K)

   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 A, is the size of the shortest formula of F that
   represents A. 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.


Hauskrecht, M. (2000)
  "Value-Function Approximations for Partially Observable Markov Decision Processes", 
   Volume 13, pages 33-94.
   PostScript: volume13/hauskrecht00a.ps (1534K)
	       compressed, volume13/hauskrecht00a.ps.Z (532K)
   PDF: volume13/hauskrecht00a.pdf (654K)

   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.


Gordon, D.F. (2000)
  "Asimovian Adaptive Agents", 
   Volume 13, pages 95-153.
   PostScript: volume13/gordon00a.ps (943K)
	       compressed, volume13/gordon00a.ps.Z (284K)
   PDF: volume13/gordon00a.pdf (584K)

   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.


Cheng, J. and Druzdzel, M.J. (2000)
  "AIS-BN: An Adaptive Importance Sampling Algorithm for Evidential Reasoning in Large Bayesian Networks", 
   Volume 13, pages 155-188.
   PostScript: volume13/cheng00a.ps (593K)
	       compressed, volume13/cheng00a.ps.Z (260K)
   HTML:  http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume13/cheng00a-html/cheng00a-hmtl.html
   PDF: volume13/cheng00a.pdf (314K)

   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.


Jensen, R.M. and Veloso, M.M. (2000)
  "OBDD-based Universal Planning for Synchronized Agents in Non-Deterministic Domains", 
   Volume 13, pages 189-226.
   PostScript: volume13/jensen00a.ps (405K)
	       compressed, volume13/jensen00a.ps.Z (178K)
   PDF: volume13/jensen00a.pdf (470K)
   Online Appendix1: volume13/jensen00a-appendix1.tar.gz, UMOP Planner (994K)

   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.


Dietterich, T.G. (2000)
  "Hierarchical Reinforcement Learning with the MAXQ Value Function Decomposition", 
   Volume 13, pages 227-303.
   PostScript: volume13/dietterich00a.ps (1682K)
	       compressed, volume13/dietterich00a.ps.Z (464K)
   PDF: volume13/dietterich00a.pdf (967K)

   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 non-hierarchical execution experimentally.
   Finally, the paper concludes with a comparison to related work and a
   discussion of the design tradeoffs in hierarchical reinforcement learning.


Cimatti, A. and Roveri, M. (2000)
  "Conformant Planning via Symbolic Model Checking", 
   Volume 13, pages 305-338.
   PostScript: volume13/cimatti00a.ps (600K)
	       compressed, volume13/cimatti00a.ps.Z (251K)
   Online Appendix1: volume13/cimatti00a-appendix1.tar.gz (199K) CMBP Planner
   PDF: volume13/cimatti00a.pdf (529K)

   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.


   			       Volume 14


Brafman, R.I. (2001)
  "On Reachability, Relevance, and Resolution in the Planning as Satisfiability Approach", 
   Volume 14, pages 1-28.
   PostScript: volume14/brafman01a.ps (352K)
	       compressed, volume14/brafman01a.ps.Z (162K)
   PDF: volume14/brafman01a.pdf (354K)

   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.


Zhang, N.L. and Zhang, W. (2001)
  "Speeding Up the Convergence of Value Iteration in Partially Observable Markov Decision Processes", 
   Volume 14, pages 29-51.
   PostScript: volume14/zhang01a.ps (291K)
	       compressed, volume14/zhang01a.ps.Z (138K)
   HTML:  http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume14/zhang01a-html/zhang01a.html
   PDF: volume14/zhang01a.pdf (299K)

   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.


Chen, X. and van Beek, P. (2001)
  "Conflict-Directed Backjumping Revisited", 
   Volume 14, pages 53-81.
   PostScript: volume14/chen01a.ps (391K)
	       compressed, volume14/chen01a.ps.Z (156K)
   Online Appendix1: volume14/chen01a-appendix1.tar (552K) Source code
   PDF: volume14/chen01a.pdf (298K)

   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 Bessiere and
   Regin's conclusion (1996) that CBJ is useless to an algorithm
   that maintains arc consistency.


Lusena, C., Goldsmith, J. and Mundhenk, M. (2001)
  "Nonapproximability Results for Partially Observable Markov Decision Processes", 
   Volume 14, pages 83-103.
   PostScript: volume14/lusena01a.ps (800K)
	       compressed, volume14/lusena01a.ps.Z (247K)
   PDF: volume14/lusena01a.pdf (401K)

   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.


Boutilier, C. and Brafman, R.I. (2001)
  "Partial-Order Planning with Concurrent Interacting Actions", 
   Volume 14, pages 105-136.
   PostScript: volume14/boutilier01a.ps (405K)
	       compressed, volume14/boutilier01a.ps.Z (164K)
   PDF: volume14/boutilier01a.pdf (337K)

   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.


Straccia, U. (2001)
  "Reasoning within Fuzzy Description Logics", 
   Volume 14, pages 137-166.
   PostScript: volume14/straccia01a.ps (1564K)
	       compressed, volume14/straccia01a.ps.Z (804K)
   PDF: volume14/straccia01a.pdf (272K)

   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.


Kusters, R. and Borgida, A. (2001)
  "What's in an Attribute? Consequences for the Least Common Subsumer", 
   Volume 14, pages 167-203.
   PostScript: volume14/kuesters01a.ps (484K)
	       compressed, volume14/kuesters01a.ps.Z (217K)
   PDF: volume14/kuesters01a.pdf (449K)

   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.


Debruyne, R. and Bessiere, C. (2001)
  "Domain Filtering Consistencies", 
   Volume 14, pages 205-230.
   PostScript: volume14/debruyne01a.ps (489K)
	       compressed, volume14/debruyne01a.ps.Z (203K)
   PDF: volume14/debruyne01a.pdf (338K)

   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.


Basu, C., Hirsh, H., Cohen, W.W., Nevill-Manning, C. (2001)
  "Technical Paper Recommendation: A Study in Combining Multiple Information Sources", 
   Volume 14, pages 231-252.
   PostScript: volume14/basu01a.ps (301K)
	       compressed, volume14/basu01a.ps.Z (110K)
   PDF: volume14/basu01a.pdf (267K)

   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.


Hoffmann, J. and Nebel, B. (2001)
  "The FF Planning System: Fast Plan Generation Through Heuristic Search", 
   Volume 14, pages 253-302.
   PostScript: volume14/hoffmann01a.ps (532K)
	       compressed, volume14/hoffmann01a.ps.Z (234K)
   Online Appendix1: volume14/hoffmann01a-appendix1.tar (379K) C code for FF-v2.2 as used in AIPS-2000 competition
   Online Appendix3: volume14/hoffmann01a-appendix3.tar (901) PDDL files, raw data and experimental results (gzipped)
   PDF: volume14/hoffmann01a.pdf (531K)

   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.


Ginsberg, M.L. (2001)
  "GIB: Imperfect Information in a Computationally Challenging Game", 
   Volume 14, pages 303-358.
   PostScript: volume14/ginsberg01a.ps (561K)
	       compressed, volume14/ginsberg01a.ps.Z (252K)
   PDF: volume14/ginsberg01a.pdf (414K)

   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.


Halpern, J.Y. (2001)
  "Conditional Plausibility Measures and Bayesian Networks", 
   Volume 14, pages 359-389.
   PostScript: volume14/halpern01a.ps (699K)
	       compressed, volume14/halpern01a.ps.Z (207K)
   PDF: volume14/halpern01a.pdf (386K)

   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.

	  		          Volume 15


Hong, J. (2001)
  "Goal Recognition through Goal Graph Analysis", 
   Volume 15, pages 1-30.
   PostScript: volume15/hong01a.ps (439K)
	       compressed, volume15/hong01a.ps.Z (218K)
   PDF: volume15/hong01a.pdf (252K)

   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.</p>
   
   <p>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.


Siskind, J.M. (2001)
  "Grounding the Lexical Semantics of Verbs in Visual Perception using Force Dynamics and Event Logic", 
   Volume 15, pages 31-90.
   PostScript: volume15/siskind01a.ps.gz (18M)
	       or compressed, volume15/siskind01a.ps.Z (35M)
   Online Appendix1: volume15/siskind01a-appendix1.tar.gz (25M) Software and video sequences
   HTML:  http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume15/siskind01a-html/siskind2001a-html.html
   PDF: volume15/siskind01a.pdf (16M)

   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.


Bhattacharyya, C. and Keerthi, S.S. (2001)
  "Mean Field Methods for a Special Class of Belief Networks", 
   Volume 15, pages 91-114.
   PostScript: volume15/bhattacharyya01a.ps (421K)
	       compressed, volume15/bhattacharyya01a.ps.Z (159K)
   PDF: volume15/bhattacharyya01a.pdf (298K)

   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.


Refanidis, I. and Vlahavas, I. (2001)
  "The GRT Planning System: Backward Heuristic Construction in Forward State-Space Planning", 
   Volume 15, pages 115-161.
   PostScript: volume15/refanidis01a.ps (2.9M)
	       compressed, volume15/refanidis01a.ps.Z (626K)
   Online Appendix1: volume15/refanidis01a-appendix1.tar.gz (4.6M) Source code and experimental data
   HTML:  http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume15/refanidis01a-html/refanidis01a.html
   PDF: volume15/refanidis01a.pdf (591K)

   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.


Elomaa, T. and Kaariainen, M. (2001)
  "An Analysis of Reduced Error Pruning", 
   Volume 15, pages 163-187.
   PostScript: volume15/elomaa01a.ps (356K)
	       compressed, volume15/elomaa01a.ps.Z (166K)
   PDF: volume15/elomaa01a.pdf (387K)

   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.  


Stone, P., Littman, M.L., Singh, S. and Kearns, M. (2001)
  "ATTac-2000: An Adaptive Autonomous Bidding Agent", 
   Volume 15, pages 189-206.
   PostScript: volume15/stone01a.ps (256K)
	       compressed, volume15/stone01a.ps.Z (106K)
   HTML:  http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume15/stone01a-html/stone01a.html
   PDF: volume15/stone01a.pdf (266K)

   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.


Ambite, J.L. and Knoblock, C.A. (2001)
  "Planning by Rewriting", 
   Volume 15, pages 207-261.
   PostScript: volume15/ambite01a.ps (849K)
	       compressed, volume15/ambite01a.ps.Z (354K)
   HTML:  http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume15/ambite01a-html/ambite01a.html
   PDF: volume15/ambite01a.pdf (321K)

   Abstract: Domain-independent planning is a hard combinatorial
   problem. Taking into account plan quality makes the task even more
   difficult. 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.


Palomar, M. and Martinez-Barco, P. (2001)
  "Computational Approach to Anaphora Resolution in Spanish Dialogues", 
   Volume 15, pages 263-287.
   PostScript: volume15/palomar01a.ps (747K)
	       compressed, volume15/palomar01a.ps.Z (249K)
   HTML:  http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume15/palomar01a-html/palomar01a.html
   PDF: volume15/palomar01a.pdf (344K)

   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.


Renz, J. and Nebel, B. (2001)
  "Efficient Methods for Qualitative Spatial Reasoning", 
   Volume 15, pages 289-318.
   PostScript: volume15/renz01a.ps (1.1M)
	       compressed, volume15/renz01a.ps.Z (350K)
   Online Appendix1: volume15/renz01a-appendix.tar ( 204K) Source code
   PDF: volume15/renz01a.pdf (1.0M)

   Abstract: The theoretical properties of qualitative spatial reasoning
   in the RCC8 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 RCC8 instances, even if they are in the phase
   transition region -- provided that one uses the maximal tractable
   subsets of RCC8 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.


Baxter, J. and Bartlett, P.L. (2001)
  "Infinite-Horizon Policy-Gradient Estimation", 
   Volume 15, pages 319-350.
   PostScript: volume15/baxter01a.ps (333K)
	       compressed, volume15/baxter01a.ps.Z (159K)
   PDF: volume15/baxter01a.pdf (266K)

   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 et al. 1995). The algorithm's chief advantages are that it
   requires storage of only twice the number of policy parameters, uses
   one free beta (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 beta 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 et al., this volume) 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.


Baxter, J., Bartlett, P.L. and Weaver, L. (2001)
  "Experiments with Infinite-Horizon, Policy-Gradient Estimation", 
   Volume 15, pages 351-381.
   PostScript: volume15/baxter01b.ps (1.4M)
	       compressed, volume15/baxter01b.ps.Z (301K)
   PDF: volume15/baxter01b.pdf (288K)

   Abstract: 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, this volume),
   which computes biased estimates of the performance gradient in POMDPs.
   The algorithm's chief advantages are that it uses only one free
   parameter beta, 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 & Bartlett, this
   volume) on a toy problem, and practical aspects of the algorithms on a
   number of more realistic problems.


Meek, C. (2001)
  "Finding a Path is Harder than Finding a Tree", 
   Volume 15, pages 383-389.
   PostScript: volume15/meek01a.ps (139K)
	       compressed, volume15/meek01a.ps.Z (70K)
   PDF: volume15/meek01a.pdf (175K)

   Abstract: I consider the problem of learning an optimal path graphical
   model from data and show the problem to be NP-hard for the maximum
   likelihood and minimum description length approaches and a Bayesian
   approach. This hardness result holds despite the fact that the problem
   is a restriction of the polynomially solvable problem of finding the
   optimal tree graphical model.


Sato, T. and Kameya, Y. (2001)
  "Parameter Learning of Logic Programs for Symbolic-Statistical Modeling", 
   Volume 15, pages 391-454.
   PostScript: volume15/sato01a.ps (1.1M)
	       compressed, volume15/sato01a.ps.Z (323K)
   PDF: volume15/sato01a.pdf (697K)

   Abstract: We propose a logical/mathematical framework for statistical
   parameter learning of parameterized logic programs, i.e.  definite
   clause programs containing probabilistic facts with a parameterized
   distribution.  It extends the traditional least Herbrand model
   semantics in logic programming to distribution semantics, possible
   world semantics with a probability distribution which is
   unconditionally applicable to arbitrary logic programs including ones
   for HMMs, PCFGs and Bayesian networks.

   We also propose a new EM algorithm, the graphical EM algorithm, that
   runs for a class of parameterized logic programs representing
   sequential decision processes where each decision is exclusive and
   independent.  It runs on a new data structure called support graphs
   describing the logical relationship between observations and their
   explanations, and learns parameters by computing inside and outside
   probability generalized for logic programs.

   The complexity analysis shows that when combined with OLDT search for
   all explanations for observations, the graphical EM algorithm, despite
   its generality, has the same time complexity as existing EM
   algorithms, i.e. the Baum-Welch algorithm for HMMs, the Inside-Outside
   algorithm for PCFGs, and the one for singly connected Bayesian
   networks that have been developed independently in each research
   field.  Learning experiments with PCFGs using two corpora of moderate
   size indicate that the graphical EM algorithm can significantly
   outperform the Inside-Outside algorithm.  


	  		          Volume 16



Baader, F., Lutz, C., Sturm, H., Wolter, F. (2002)
  "Fusions of Description Logics and Abstract Description Systems", 
   Volume 16, pages 1-58.
   PostScript: volume16/baader02a.ps (684K)
	       compressed, volume16/baader02a.ps.Z (294K)
   PDF: volume16/baader02a.pdf (473K)

   Abstract: Fusions are a simple way of combining logics. For normal
   modal logics, fusions have been investigated in detail. In particular,
   it is known that, under certain conditions, decidability transfers
   from the component logics to their fusion.  Though description logics
   are closely related to modal logics, they are not necessarily
   normal. In addition, ABox reasoning in description logics is not
   covered by the results from modal logics.
<p>      
   In this paper, we extend the decidability transfer results from normal
   modal logics to a large class of description logics. To cover
   different description logics in a uniform way, we introduce abstract
   description systems, which can be seen as a common generalization of
   description and modal logics, and show the transfer results in this
   general setting.


Drummond, C. (2002)
  "Accelerating Reinforcement Learning by Composing Solutions of Automatically Identified Subtasks", 
   Volume 16, pages 59-104.
   PostScript: volume16/drummond02a.ps (1.3M)
	       compressed, volume16/drummond02a.ps.Z (475K)
   HTML:  http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume16/drummond02a-html/drummond02a-html.html
   PDF: volume16/drummond02a.pdf (714K)

   Abstract: This paper discusses a system that accelerates reinforcement
   learning by using transfer from related tasks.  Without such
   transfer, even if two tasks are very similar at some abstract level,
   an extensive re-learning effort is required.  The system achieves
   much of its power by transferring parts of previously learned
   solutions rather than a single complete solution. The system
   exploits strong features in the multi-dimensional function produced
   by reinforcement learning in solving a particular task. These
   features are stable and easy to recognize early in the learning
   process. They generate a partitioning of the state space and thus
   the function.  The partition is represented as a graph.  This is
   used to index and compose functions stored in a case base to form a
   close approximation to the solution of the new task.  Experiments
   demonstrate that function composition often produces more than an
   order of magnitude increase in learning rate compared to a basic
   reinforcement learning algorithm.


Singh, S., Litman, D., Kearns, M., Walker, M. (2002)
  "Optimizing Dialogue Management with Reinforcement Learning: Experiments with the NJFun System", 
   Volume 16, pages 105-133.
   PostScript: volume16/singh02a.ps (1.1M)
	       compressed, volume16/singh02a.ps.Z (238K)
   PDF: volume16/singh02a.pdf (345K)

   Abstract: Designing the dialogue policy of a spoken dialogue system
   involves many nontrivial choices.  This paper presents a reinforcement
   learning approach for automatically optimizing a dialogue policy,
   which addresses the technical challenges in applying reinforcement
   learning to a working dialogue system with human users.  We report on
   the design, construction and empirical evaluation of NJFun, an
   experimental spoken dialogue system that provides users with access to
   information about fun things to do in New Jersey.  Our results show
   that by optimizing its performance via reinforcement learning, NJFun
   measurably improves system performance.


Blockeel, H., Dehaspe, L., Demoen, B., Janssens, G., Ramon, J., and Vandecasteele, H. (2002)
  "Improving the Efficiency of Inductive Logic Programming Through the
Use of Query Packs", 
   Volume 16, pages 135-166.
   PostScript: volume16/blockeel02a.ps (416K)
	       compressed, volume16/blockeel02a.ps.Z (193K)
   HTML:  http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume16/blockeel02a-html/packs-html.html
   PDF: volume16/blockeel02a.pdf (470K)

   Abstract: Inductive logic programming, or relational learning, is a
   powerful paradigm for machine learning or data mining.  However, in
   order for ILP to become practically useful, the efficiency of ILP
   systems must improve substantially. To this end, the notion of a query
   pack is introduced: it structures sets of similar
   queries. Furthermore, a mechanism is described for executing such
   query packs.  A complexity analysis shows that considerable efficiency
   improvements can be achieved through the use of this query pack
   execution mechanism. This claim is supported by empirical results
   obtained by incorporating support for query pack execution in two
   existing learning systems.


Shatkay, H. and Kaelbling, L.P. (2002)
  "Learning Geometrically-Constrained Hidden Markov Models for Robot Navigation: Bridging the Topological-Geometrical Gap", 
   Volume 16, pages 167-207.
   PostScript: volume16/shatkay02a.ps (1.3M)
	       compressed, volume16/shatkay02a.ps.Z (472K)
   PDF: volume16/shatkay02a.pdf (852K)

   Abstract: Hidden Markov models (HMMs) and partially observable Markov
   decision processes (POMDPs) provide useful tools for modeling
   dynamical systems.  They are particularly useful for representing the
   topology of environments such as road networks and office buildings,
   which are typical for robot navigation and planning.  The work
   presented here describes a formal framework for incorporating readily
   available odometric information and geometrical constraints into both
   the models and the algorithm that learns them.  By taking advantage of
   such information, learning HMMs/POMDPs can be made to generate better
   solutions and require fewer iterations, while being robust in the face
   of data reduction.  Experimental results, obtained from both simulated
   and real robot data, demonstrate the effectiveness of the approach.


Di Sciascio, E., Donini, F.M. and Mongiello, M. (2002)
  "Structured Knowledge Representation for Image Retrieval", 
   Volume 16, pages 209-257.
   PostScript: volume16/disciascio02a.ps (43M)
	       compressed, volume16/disciascio02a.ps.Z (2M)
   HTML:  http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume16/disciascio02a-html/disciascio02a.html
   PDF: volume16/disciascio02a.pdf (1M)

   Abstract: We propose a structured approach to the problem of retrieval
   of images by content and present a description logic that has been
   devised for the semantic indexing and retrieval of images containing
   complex objects.
   <p>
   As other approaches do, we start from low-level features extracted
   with image analysis to detect and characterize regions in an
   image. However, in contrast with feature-based approaches, we provide
   a syntax to describe segmented regions as basic objects and complex
   objects as compositions of basic ones. Then we introduce a companion
   extensional semantics for defining reasoning services, such as
   retrieval, classification, and subsumption.  These services can be
   used for both exact and approximate matching, using similarity
   measures.  
   <p> 
   Using our logical approach as a formal specification, we implemented a
   complete client-server image retrieval system, which allows a user to
   pose both queries by sketch and queries by example. A set of
   experiments has been carried out on a testbed of images to assess the
   retrieval capabilities of the system in comparison with expert users
   ranking. Results are presented adopting a well-established measure of
   quality borrowed from textual information retrieval.


Xu, X., He, H. and Hu, D. (2002)
  "Efficient Reinforcement Learning Using Recursive Least-Squares Methods", 
   Volume 16, pages 259-292.
   PostScript: volume16/xu02a.ps (1.7M)
	       compressed, volume16/xu02a.ps.Z (700K)
   PDF: volume16/xu02a.pdf (219K)

   Abstract: The recursive least-squares (RLS) algorithm is one of the
   most well-known algorithms used in adaptive filtering, system
   identification and adaptive control. Its popularity is mainly due to
   its fast convergence speed, which is considered to be optimal in
   practice. In this paper, RLS methods are used to solve reinforcement
   learning problems, where two new reinforcement learning algorithms
   using linear value function approximators are proposed and
   analyzed. The two algorithms are called RLS-TD(lambda) and Fast-AHC
   (Fast Adaptive Heuristic Critic), respectively. RLS-TD(lambda) can be
   viewed as the extension of RLS-TD(0) from lambda=0 to general lambda
   within interval [0,1], so it is a multi-step temporal-difference (TD)
   learning algorithm using RLS methods. The convergence with probability
   one and the limit of convergence of RLS-TD(lambda) are proved for
   ergodic Markov chains. Compared to the existing LS-TD(lambda)
   algorithm, RLS-TD(lambda) has advantages in computation and is more
   suitable for online learning. The effectiveness of RLS-TD(lambda) is
   analyzed and verified by learning prediction experiments of Markov
   chains with a wide range of parameter settings.
   <p>
   The Fast-AHC algorithm is derived by applying the proposed
   RLS-TD(lambda) algorithm in the critic network of the adaptive
   heuristic critic method. Unlike conventional AHC algorithm, Fast-AHC
   makes use of RLS methods to improve the learning-prediction efficiency
   in the critic. Learning control experiments of the cart-pole balancing
   and the acrobot swing-up problems are conducted to compare the data
   efficiency of Fast-AHC with conventional AHC. From the experimental
   results, it is shown that the data efficiency of learning control can
   also be improved by using RLS methods in the learning-prediction
   process of the critic. The performance of Fast-AHC is also compared
   with that of the AHC method using LS-TD(lambda). Furthermore, it is
   demonstrated in the experiments that different initial values of the
   variance matrix in RLS-TD(lambda) are required to get better
   performance not only in learning prediction but also in learning
   control. The experimental results are analyzed based on the existing
   theoretical work on the transient phase of forgetting factor RLS
   methods.


Walker, M.A., Langkilde-Geary, I., Wright Hastie, H., Wright, J., Gorin, A. (2002)
  "Automatically Training a Problematic Dialogue Predictor for a Spoken Dialogue System", 
   Volume 16, pages 293-319.
   PostScript: volume16/walker02a.ps (304K)
	       compressed, volume16/walker02a.ps.Z (144K)
   HTML:  http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume16/walker02a-html/index.html
   PDF: volume16/walker02a.pdf (341K)

   Abstract: Spoken dialogue systems promise efficient and natural access
   to a large variety of information sources and services from any phone.
   However, current spoken dialogue systems are deficient in their
   strategies for preventing, identifying and repairing problems that
   arise in the conversation. This paper reports results on automatically
   training a Problematic Dialogue Predictor to predict problematic
   human-computer dialogues using a corpus of 4692 dialogues collected
   with the 'How May I Help You' (SM) spoken dialogue system.  The
   Problematic Dialogue Predictor can be immediately applied to the
   system's decision of whether to transfer the call to a human customer
   care agent, or be used as a cue to the system's dialogue manager to
   modify its behavior to repair problems, and even perhaps, to prevent
   them. We show that a Problematic Dialogue Predictor using
   automatically-obtainable features from the first two exchanges in the
   dialogue can predict problematic dialogues 13.2% more accurately than
   the baseline.


Chawla, N.V., Bowyer, K.W., Hall, L.O., Kegelmeyer, W.P. (2002)
  "SMOTE: Synthetic Minority Over-sampling Technique", 
   Volume 16, pages 321-357.
   PostScript: volume16/chawla02a.ps (812K)
	       compressed, volume16/chawla02a.ps.Z (330K)
   HTML:  http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume16/chawla02a-html/chawla2002.html
   PDF: volume16/chawla02a.pdf (490K)

   Abstract: An approach to the construction of classifiers from
   imbalanced datasets is described. A dataset is imbalanced if the
   classification categories are not approximately equally
   represented. Often real-world data sets are predominately composed of
   ``normal'' examples with only a small percentage of ``abnormal'' or
   ``interesting'' examples. It is also the case that the cost of
   misclassifying an abnormal (interesting) example as a normal example
   is often much higher than the cost of the reverse
   error. Under-sampling of the majority (normal) class has been proposed
   as a good means of increasing the sensitivity of a classifier to the
   minority class. This paper shows that a combination of our method of
   over-sampling the minority (abnormal) class and under-sampling the
   majority (normal) class can achieve better classifier performance (in
   ROC space) than only under-sampling the majority class.  This paper
   also shows that a combination of our method of over-sampling the
   minority class and under-sampling the majority class can achieve
   better classifier performance (in ROC space) than varying the loss
   ratios in Ripper or class priors in Naive Bayes. Our method of
   over-sampling the minority class involves creating synthetic minority
   class examples.  Experiments are performed using C4.5, Ripper and a
   Naive Bayes classifier. The method is evaluated using the area under
   the Receiver Operating Characteristic curve (AUC) and the ROC convex
   hull strategy.


Wolpert, D.H. and Tumer, K. (2002)
  "Collective Intelligence, Data Routing and Braess' Paradox", 
   Volume 16, pages 359-387.
   PostScript: volume16/wolpert02a.ps (368K)
	       compressed, volume16/wolpert02a.ps.Z (173K)
   PDF: volume16/wolpert02a.pdf (418K)

   Abstract: We consider the problem of designing the the utility
   functions of the utility-maximizing agents in a multi-agent system so
   that they work synergistically to maximize a global utility. The
   particular problem domain we explore is the control of network routing
   by placing agents on all the routers in the network.  Conventional
   approaches to this task have the agents all use the Ideal Shortest
   Path routing Algorithm (ISPA).  We demonstrate that in many cases, due
   to the side-effects of one agent's actions on another agent's
   performance, having agents use ISPA's is suboptimal as far as global
   aggregate cost is concerned, even when they are only used to route
   infinitesimally small amounts of traffic.  The utility functions of
   the individual agents are not ``aligned'' with the global utility,
   intuitively speaking.  As a particular example of this we present an
   instance of Braess' paradox in which adding new links to a network
   whose agents all use the ISPA results in a decrease in overall
   throughput. We also demonstrate that load-balancing, in which the
   agents' decisions are collectively made to optimize the global cost
   incurred by all traffic currently being routed, is suboptimal as far
   as global cost averaged across time is concerned. This is also due to
   `side-effects', in this case of current routing decision on future
   traffic. The mathematics of Collective Intelligence (COIN) is
   concerned precisely with the issue of avoiding such deleterious
   side-effects in multi-agent systems, both over time and space. We
   present key concepts from that mathematics and use them to derive an
   algorithm whose ideal version should have better performance than that
   of having all agents use the ISPA, even in the infinitesimal limit. We
   present experiments verifying this, and also showing that a
   machine-learning-based version of this COIN algorithm in which costs
   are only imprecisely estimated via empirical means (a version
   potentially applicable in the real world) also outperforms the ISPA,
   despite having access to less information than does the ISPA. In
   particular, this COIN algorithm almost always avoids Braess' paradox.


Pynadath, D.V. and Tambe, M. (2002)
  "The Communicative Multiagent Team Decision Problem: Analyzing Teamwork Theories and Models", 
   Volume 16, pages 389-423.
   PostScript: volume16/pynadath02a.ps (15M)
	       compressed, volume16/pynadath02a.ps.Z (455K)
   Online Appendix1: volume16/pynadath02a-appendix1.tar (336K) Algorithms and data
   HTML:  http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume16/pynadath02a-html/index.html
   PDF: volume16/pynadath02a.pdf (519K)

   Abstract: Despite the significant progress in multiagent teamwork,
   existing research does not address the optimality of its prescriptions
   nor the complexity of the teamwork problem.  Without a
   characterization of the optimality-complexity tradeoffs, it is
   impossible to determine whether the assumptions and approximations
   made by a particular theory gain enough efficiency to justify the
   losses in overall performance.  To provide a tool for use by
   multiagent researchers in evaluating this tradeoff, we present a
   unified framework, the COMmunicative Multiagent Team Decision Problem
   (COM-MTDP).  The COM-MTDP model combines and extends existing
   multiagent theories, such as decentralized partially observable Markov
   decision processes and economic team theory.  In addition to their
   generality of representation, COM-MTDPs also support the analysis of
   both the optimality of team performance and the computational
   complexity of the agents' decision problem.  In analyzing complexity,
   we present a breakdown of the computational complexity of constructing
   optimal teams under various classes of problem domains, along the
   dimensions of observability and communication cost.  In analyzing
   optimality, we exploit the COM-MTDP's ability to encode existing
   teamwork theories and models to encode two instantiations of joint
   intentions theory taken from the literature.  Furthermore, the
   COM-MTDP model provides a basis for the development of novel team
   coordination algorithms.  We derive a domain-independent criterion for
   optimal communication and provide a comparative analysis of the two
   joint intentions instantiations with respect to this optimal policy.
   We have implemented a reusable, domain-independent software package
   based on COM-MTDPs to analyze teamwork coordination strategies, and we
   demonstrate its use by encoding and evaluating the two joint
   intentions strategies within an example domain.


Baget, J.F. and Mugnier, M.L. (2002)
  "Extensions of Simple Conceptual Graphs: the Complexity of Rules and Constraints", 
   Volume 16, pages 425-465.
   PostScript: volume16/baget02a.ps (751K)
	       compressed, volume16/baget02a.ps.Z (294K)
   PDF: volume16/baget02a.pdf (567K)

   Abstract: Simple conceptual graphs are considered as the kernel of
   most knowledge representation formalisms built upon Sowa's
   model. Reasoning in this model can be expressed by a graph
   homomorphism called projection, whose semantics is usually given in
   terms of positive, conjunctive, existential FOL.  We present here a
   family of extensions of this model, based on rules and constraints,
   keeping graph homomorphism as the basic operation. We focus on the
   formal definitions of the different models obtained, including their
   operational semantics and relationships with FOL, and we analyze the
   decidability and complexity of the associated problems (consistency
   and deduction). As soon as rules are involved in reasonings, these
   problems are not decidable, but we exhibit a condition under which
   they fall in the polynomial hierarchy.  These results extend and
   complete the ones already published by the authors.  Moreover we
   systematically study the complexity of some particular cases obtained
   by restricting the form of constraints and/or rules.


	  		          Volume 17

Howe, A.E. and Dahlman, E. (2002)
  "A Critical Assessment of Benchmark Comparison in Planning", 
   Volume 17, pages 1-33.
   PostScript: volume17/howe02a.ps (2M)
	       compressed, volume17/howe02a.ps.Z (251K)
   HTML:  http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume17/howe02a-html/jair-plan-html.html
   PDF: volume17/howe02a.pdf (327K)

   Abstract: Recent trends in planning research have led to empirical 
   comparison becoming commonplace. The field has started to settle into
   a methodology for such comparisons, which for obvious practical
   reasons requires running a subset of planners on a subset of
   problems.  In this paper, we characterize the methodology and
   examine eight implicit assumptions about the problems, planners and
   metrics used in many of these comparisons. The problem assumptions
   are: PR1) the performance of a general purpose planner should not be
   penalized/biased if executed on a sampling of problems and domains,
   PR2) minor syntactic differences in representation do not affect
   performance, and PR3) problems should be solvable by STRIPS capable
   planners unless they require ADL. The planner assumptions are: PL1)
   the latest version of a planner is the best one to use, PL2) default
   parameter settings approximate good performance, and PL3) time
   cut-offs do not unduly bias outcome. The metrics assumptions are:
   M1) performance degrades similarly for each planner when run on
   degraded runtime environments (e.g., machine platform) and M2) the
   number of plan steps distinguishes performance. We find that most of
   these assumptions are not supported empirically; in particular, that
   planners are affected differently by these assumptions. We conclude
   with a call to the community to devote research resources to
   improving the state of the practice and especially to enhancing the
   available benchmark problems.


Barzilay, R., Elhadad, N., and McKeown K.R. (2002)
  "Inferring Strategies for Sentence Ordering in Multidocument News Summarization", 
   Volume 17, pages 35-55.
   PostScript: volume17/barzilay02a.ps (383K)
	       compressed, volume17/barzilay02a.ps.Z (251K)
   PDF: volume17/barzilay02a.pdf (215K)

   Abstract: The problem of organizing information for multidocument
   summarization so that the generated summary is coherent has received
   relatively little attention.  While sentence ordering for single
   document summarization can be determined from the ordering of
   sentences in the input article, this is not the case for multidocument
   summarization where summary sentences may be drawn from different
   input articles. In this paper, we propose a methodology for studying
   the properties of ordering information in the news genre and describe
   experiments done on a corpus of multiple acceptable orderings we
   developed for the task. Based on these experiments, we implemented a
   strategy for ordering information that combines constraints from
   chronological order of events and topical relatedness.  Evaluation of
   our augmented algorithm shows a significant improvement of the
   ordering over two baseline strategies.


Halpern, J.Y. and Pucella, R. (2002)
  "A Logic for Reasoning about Upper Probabilities", 
   Volume 17, pages 57-81.
   PostScript: volume17/halpern02a.ps (371K)
	       compressed, volume17/halpern02a.ps.Z (173K)
   PDF: volume17/halpern02a.pdf (295K)

   Abstract: We present a propositional logic to reason about the
   uncertainty of events, where the uncertainty is modeled by a set of
   probability measures assigning an interval of probability to each
   event. We give a sound and complete axiomatization for the logic, and
   show that the satisfiability problem is NP-complete, no harder than
   satisfiability for propositional logic.


Kaminka, G.A., Pynadath, D.V. and Tambe, M. (2002)
  "Monitoring Teams by Overhearing: A Multi-Agent Plan-Recognition Approach", 
   Volume 17, pages 83-135.
   PostScript: volume17/kaminka02a.ps (874K)
	       compressed, volume17/kaminka02a.ps.Z (369K)
   Online Appendix1: volume17/kaminka02a-appendix1.tar (99K) sample data
   PDF: volume17/kaminka02a.pdf (688K)

   Abstract: Recent years are seeing an increasing need for on-line
   monitoring of teams of cooperating agents, e.g., for visualization, or
   performance tracking. However, in monitoring deployed teams, we often
   cannot rely on the agents to always communicate their state to the
   monitoring system. This paper presents a non-intrusive approach to
   monitoring by 'overhearing', where the monitored team's state is
   inferred (via plan-recognition) from team-members' *routine*
   communications, exchanged as part of their coordinated task execution,
   and observed (overheard) by the monitoring system. Key challenges in
   this approach include the demanding run-time requirements of
   monitoring, the scarceness of observations (increasing monitoring
   uncertainty), and the need to scale-up monitoring to address
   potentially large teams. To address these, we present a set of
   complementary novel techniques, exploiting knowledge of the social
   structures and procedures in the monitored team: (i) an efficient
   probabilistic plan-recognition algorithm, well-suited for processing
   communications as observations; (ii) an approach to exploiting
   knowledge of the team's social behavior to predict future observations
   during execution (reducing monitoring uncertainty); and (iii)
   monitoring algorithms that trade expressivity for scalability,
   representing only certain useful monitoring hypotheses, but allowing
   for any number of agents and their different activities to be
   represented in a single coherent entity. We present an empirical
   evaluation of these techniques, in combination and apart, in
   monitoring a deployed team of agents, running on machines physically
   distributed across the country, and engaged in complex, dynamic task
   execution. We also compare the performance of these techniques to
   human expert and novice monitors, and show that the techniques
   presented are capable of monitoring at human-expert levels, despite
   the difficulty of the task.


Nock, R. (2002)
  "Inducing Interpretable Voting Classifiers without Trading Accuracy for Simplicity: Theoretical Results, Approximation Algorithms, and Experiments", 
   Volume 17, pages 137-170.
   PostScript: volume17/nock02a.ps (532K)
	       compressed, volume17/nock02a.ps.Z (228K)
   HTML:  http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume17/nock02a-html/nock02a-html.html
   PDF: volume17/nock02a.pdf (403K)

   Abstract: Recent advances in the study of voting classification
   algorithms have brought empirical and theoretical results clearly
   showing the discrimination power of ensemble classifiers. It has been
   previously argued that the search of this classification power in the
   design of the algorithms has marginalized the need to obtain
   interpretable classifiers. Therefore, the question of whether one
   might have to dispense with interpretability in order to keep
   classification strength is being raised in a growing number of machine
   learning or data mining papers. The purpose of this paper is to study
   both theoretically and empirically the problem. First, we provide
   numerous results giving insight into the hardness of the
   simplicity-accuracy tradeoff for voting classifiers. Then we provide
   an efficient ``top-down and prune'' induction heuristic, WIDC, mainly
   derived from recent results on the weak learning and boosting
   frameworks.  It is to our knowledge the first attempt to build a
   voting classifier as a base formula using the weak learning framework
   (the one which was previously highly successful for decision tree
   induction), and not the strong learning framework (as usual for such
   classifiers with boosting-like approaches). While it uses a well-known
   induction scheme previously successful in other classes of concept
   representations, thus making it easy to implement and compare, WIDC
   also relies on recent or new results we give about particular cases of
   boosting known as partition boosting and ranking loss
   boosting. Experimental results on thirty-one domains, most of which
   readily available, tend to display the ability of WIDC to produce
   small, accurate, and interpretable decision committees.


Scerri, P., Pynadath, D.V., Tampe, M. (2002)
  "Towards Adjustable Autonomy for the Real World", 
   Volume 17, pages 171-228.
   PostScript: volume17/scerri02a.ps (16M)
	       compressed, volume17/scerri02a.ps.Z (1.2M)
   PDF: volume17/scerri02a.pdf (774K)

   Abstract: Adjustable autonomy refers to entities dynamically varying
   their own autonomy, transferring decision-making control to other
   entities (typically agents transferring control to human users) in key
   situations.  Determining whether and when such transfers-of-control
   should occur is arguably the fundamental research problem in
   adjustable autonomy. Previous work has investigated various approaches
   to addressing this problem but has often focused on individual
   agent-human interactions.  Unfortunately, domains requiring
   collaboration between teams of agents and humans reveal two key
   shortcomings of these previous approaches. First, these approaches use
   rigid one-shot transfers of control that can result in unacceptable
   coordination failures in multiagent settings.  Second, they ignore
   costs (e.g., in terms of time delays or effects on actions) to an
   agent's team due to such transfers-of-control.
   
   To remedy these problems, this article presents a novel approach to
   adjustable autonomy, based on the notion of a transfer-of-control
   strategy.  A transfer-of-control strategy consists of a conditional
   sequence of two types of actions: (i) actions to transfer
   decision-making control (e.g., from an agent to a user or vice versa)
   and (ii) actions to change an agent's pre-specified coordination
   constraints with team members, aimed at minimizing miscoordination
   costs. The goal is for high-quality individual decisions to be made
   with minimal disruption to the coordination of the team.  We present a
   mathematical model of transfer-of-control strategies. The model guides
   and informs the operationalization of the strategies using Markov
   Decision Processes, which select an optimal strategy, given an
   uncertain environment and costs to the individuals and teams. The
   approach has been carefully evaluated, including via its use in a
   real-world, deployed multi-agent system that assists a research group
   in its daily activities.


Darwiche, A. and Marquis, P. (2002)
  "A Knowledge Compilation Map", 
   Volume 17, pages 229-264.
   PostScript: volume17/darwiche02a.ps (1.1M)
	       compressed, volume17/darwiche02a.ps.Z (514K)
   PDF: volume17/darwiche02a.pdf (444K)

   Abstract: We propose a perspective on knowledge compilation which
   calls for analyzing different compilation approaches according to two
   key dimensions: the succinctness of the target compilation language,
   and the class of queries and transformations that the language
   supports in polytime. We then provide a knowledge compilation map,
   which analyzes a large number of existing target compilation languages
   according to their succinctness and their polytime transformations and
   queries. We argue that such analysis is necessary for placing new
   compilation approaches within the context of existing ones. We also go
   beyond classical, flat target compilation languages based on CNF and
   DNF, and consider a richer, nested class based on directed acyclic
   graphs (such as OBDDs), which we show to include a relatively large
   number of target compilation languages.


Chan, H. and Darwiche, A. (2002)
  "When do Numbers Really Matter?", 
   Volume 17, pages 265-287.
   PostScript: volume17/chan02a.ps (2.4M)
	       compressed, volume17/chan02a.ps.Z (519K)
   PDF: volume17/chan02a.pdf (311K)

   Abstract: Common wisdom has it that small distinctions in the
   probabilities (parameters) quantifying a belief network do not matter
   much for the results of probabilistic queries. Yet, one can develop
   realistic scenarios under which small variations in network parameters
   can lead to significant changes in computed queries. A pending
   theoretical question is then to analytically characterize parameter
   changes that do or do not matter. In this paper, we study the
   sensitivity of probabilistic queries to changes in network parameters
   and prove some tight bounds on the impact that such parameters can
   have on queries. Our analytic results pinpoint some interesting
   situations under which parameter changes do or do not matter. These
   results are important for knowledge engineers as they help them
   identify influential network parameters. They also help explain some
   of the previous experimental results and observations with regards to
   network robustness against parameter changes.


Bod, R. (2002)
  "A Unified Model of Structural Organization in Language and Music", 
   Volume 17, pages 289-308.
   PostScript: volume17/bod02a.ps (1M)
	       compressed, volume17/bod02a.ps.Z (534K)
   PDF: volume17/bod02a.pdf (84K)

   Abstract: Is there a general model that can predict the perceived
   phrase structure in language and music? While it is usually assumed
   that humans have separate faculties for language and music, this work
   focuses on the commonalities rather than on the differences between
   these modalities, aiming at finding a deeper 'faculty'. Our key idea
   is that the perceptual system strives for the simplest structure (the
   'simplicity principle'), but in doing so it is biased by the
   likelihood of previous structures (the 'likelihood principle'). We
   present a series of data-oriented parsing (DOP) models that combine
   these two principles and that are tested on the Penn Treebank and the
   Essen Folksong Collection. Our experiments show that (1) a combination
   of the two principles outperforms the use of either of them, and (2)
   exactly the same model with the same parameter setting achieves
   maximum accuracy for both language and music. We argue that our
   results suggest an interesting parallel between linguistic and musical
   structuring.


Gao, Y. and Culberson, J. (2002)
  "An Analysis of Phase Transition in NK Landscapes", 
   Volume 17, pages 309-332.
   PostScript: volume17/gao02a.ps (359K)
	       compressed, volume17/gao02a.ps.Z (166K)
   PDF: volume17/gao02a.pdf (527K)

   Abstract: In this paper, we analyze the decision version of the NK
   landscape model from the perspective of threshold phenomena and phase
   transitions under two random distributions, the uniform probability
   model and the fixed ratio model. For the uniform probability model, we
   prove that the phase transition is easy in the sense that there is a
   polynomial algorithm that can solve a random instance of the problem
   with the probability asymptotic to 1 as the problem size tends to
   infinity. For the fixed ratio model, we establish several upper bounds
   for the solubility threshold, and prove that random instances with
   parameters above these upper bounds can be solved polynomially. This,
   together with our empirical study for random instances generated below
   and in the phase transition region, suggests that the phase transition
   of the fixed ratio model is also easy.  


Al-Ani, A. and Deriche, M. (2002)
  "A New Technique for Combining Multiple Classifiers using The Dempster-Shafer Theory of Evidence", 
   Volume 17, pages 333-361.
   PostScript: volume17/alani02a.ps (426K)
	       compressed, volume17/alani02a.ps.Z (193K)
   PDF: volume17/alani02a.pdf (243K)

   Abstract: This paper presents a new classifier combination
   technique based on the Dempster-Shafer theory of evidence. The
   Dempster-Shafer theory of evidence is a powerful method for
   combining measures of evidence from different classifiers. However,
   since each of the available methods that estimates the evidence of
   classifiers has its own limitations, we propose here a new
   implementation which adapts to training data so that the overall
   mean square error is minimized. The proposed technique is shown to
   outperform most available classifier combination methods when
   tested on three different classification problems.


Tennenholtz, M. (2002)
  "Competitive Safety Analysis: Robust Decision-Making
in Multi-Agent Systems", 
   Volume 17, pages 363-378.
   PostScript: volume17/tennenholtz02a.ps (409K)
	       compressed, volume17/tennenholtz02a.ps.Z (218K)
   PDF: volume17/tennenholtz02a.pdf (250K)

   Abstract: Much work in AI deals with the selection of proper actions
   in a given (known or unknown) environment. However, the way to select
   a proper action when facing other agents is quite unclear. Most work
   in AI adopts classical game-theoretic equilibrium analysis to predict
   agent behavior in such settings. This approach however does not
   provide us with any guarantee for the agent. In this paper we
   introduce competitive safety analysis. This approach bridges the gap
   between the desired normative AI approach, where a strategy should be
   selected in order to guarantee a desired payoff, and equilibrium
   analysis.  We show that a safety level strategy is able to guarantee
   the value obtained in a Nash equilibrium, in several classical
   computer science settings.  Then, we discuss the concept of
   competitive safety strategies, and illustrate its use in a
   decentralized load balancing setting, typical to network problems. In
   particular, we show that when we have many agents, it is possible to
   guarantee an expected payoff which is a factor of 8/9 of the payoff
   obtained in a Nash equilibrium.  Our discussion of competitive safety
   analysis for decentralized load balancing is further developed to deal
   with many communication links and arbitrary speeds.  Finally, we
   discuss the extension of the above concepts to Bayesian games, and
   illustrate their use in a basic auctions setup.


Fern, A., Givan, R., and Siskind, J.M. (2002)
  "Specific-to-General Learning for Temporal Events with Application to Learning Event Definitions from Video", 
   Volume 17, pages 379-449.
   PostScript: volume17/fern02a.ps (20M)
	       compressed, volume17/fern02a.ps.Z (6M)
   Online Appendix1: volume17/fern02a-appendix1.tar.Z (3M) Source code and data
   PDF: volume17/fern02a.pdf (1M)

   Abstract: We develop, analyze, and evaluate a novel, supervised,
   specific-to-general learner for a simple temporal logic and use the
   resulting algorithm to learn visual event definitions from video
   sequences.  First, we introduce a simple, propositional, temporal,
   event-description language called AMA that is sufficiently expressive
   to represent many events yet sufficiently restrictive to support
   learning.  We then give algorithms, along with lower and upper
   complexity bounds, for the subsumption and generalization problems for
   AMA formulas. We present a positive-examples--only specific-to-general
   learning method based on these algorithms. We also present a
   polynomial-time--computable ``syntactic'' subsumption test that
   implies semantic subsumption without being equivalent to it. A
   generalization algorithm based on syntactic subsumption can be used in
   place of semantic generalization to improve the asymptotic complexity
   of the resulting learning algorithm. Finally, we apply this algorithm
   to the task of learning relational event definitions from video and
   show that it yields definitions that are competitive with hand-coded
   ones.


Bui, H.H., Venkatesh, S., and West, G. (2002)
  "Policy Recognition in the Abstract Hidden Markov Model", 
   Volume 17, pages 451-499.
   PostScript: volume17/bui02a.ps (1.8M)
	       compressed, volume17/bui02a.ps.Z (563K)
   PDF: volume17/bui02a.pdf (614K)

   Abstract: In this paper, we present a method for recognising an
   agent's behaviour in dynamic, noisy, uncertain domains, and across
   multiple levels of abstraction.  We term this problem on-line plan
   recognition under uncertainty and view it generally as probabilistic
   inference on the stochastic process representing the execution of the
   agent's plan. Our contributions in this paper are twofold.  In terms
   of probabilistic inference, we introduce the Abstract Hidden Markov
   Model (AHMM), a novel type of stochastic processes, provide its
   dynamic Bayesian network (DBN) structure and analyse the properties of
   this network.  We then describe an application of the
   Rao-Blackwellised Particle Filter to the AHMM which allows us to
   construct an efficient, hybrid inference method for this model.  In
   terms of plan recognition, we propose a novel plan recognition
   framework based on the AHMM as the plan execution model.  The
   Rao-Blackwellised hybrid inference for AHMM can take advantage of the
   independence properties inherent in a model of plan execution, leading
   to an algorithm for online probabilistic plan recognition that scales
   well with the number of levels in the plan hierarchy.  This
   illustrates that while stochastic models for plan execution can be
   complex, they exhibit special structures which, if exploited, can lead
   to efficient plan recognition algorithms.  We demonstrate the
   usefulness of the AHMM framework via a behaviour recognition system in
   a complex spatial environment using distributed video surveillance
   data.


Gamberger, D. and Lavrac, N. (2002)
  "Expert-Guided Subgroup Discovery: Methodology and Application", 
   Volume 17, pages 501-527.
   PostScript: volume17/gamberger02a.ps (441K)
	       compressed, volume17/gamberger02a.ps.Z (221K)
   HTML:  http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume17/gamberger02a-html/gamberger2002a.html
   PDF: volume17/gamberger02a.pdf (356K)

   Abstract: This paper presents an approach to expert-guided subgroup
   discovery.  The main step of the subgroup discovery process, the
   induction of subgroup descriptions, is performed by a heuristic beam
   search algorithm, using a novel parametrized definition of rule
   quality which is analyzed in detail.  The other important steps of the
   proposed subgroup discovery process are the detection of statistically
   significant properties of selected subgroups and subgroup
   visualization: statistically significant properties are used to enrich
   the descriptions of induced subgroups, while the visualization shows
   subgroup properties in the form of distributions of the numbers of
   examples in the subgroups. The approach is illustrated by the results
   obtained for a medical problem of early detection of patient risk
   groups.

	  		          Volume 18


Thompson, C.A and Mooney, R.J. (2003)
  "Acquiring Word-Meaning Mappings for Natural Language Interfaces", 
   Volume 18, pages 1-44.
   PostScript: volume18/thompson03a.ps (601K)
	       compressed, volume18/thompson03a.ps.Z (278K)
   HTML:  http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume18/thompson03a-html/thompson03a-html.html
   PDF: volume18/thompson03a.pdf (454K)

   Abstract: This paper focuses on a system, WOLFIE (WOrd Learning From
   Interpreted Examples), that acquires a semantic lexicon from a corpus
   of sentences paired with semantic representations.  The lexicon
   learned consists of phrases paired with meaning representations.
   WOLFIE is part of an integrated system that learns to transform
   sentences into representations such as logical database queries.
   
   Experimental results are presented demonstrating WOLFIE's ability to
   learn useful lexicons for a database interface in four different
   natural languages.  The usefulness of the lexicons learned by WOLFIE
   are compared to those acquired by a similar system, with results
   favorable to WOLFIE.  A second set of experiments demonstrates
   WOLFIE's ability to scale to larger and more difficult, albeit
   artificially generated, corpora.
   
   In natural language acquisition, it is difficult to gather the
   annotated data needed for supervised learning; however, unannotated
   data is fairly plentiful.  Active learning methods attempt to select
   for annotation and training only the most informative examples, and
   therefore are potentially very useful in natural language
   applications.  However, most results to date for active learning have
   only considered standard classification tasks.  To reduce annotation
   effort while maintaining accuracy, we apply active learning to
   semantic lexicons.  We show that active learning can significantly
   reduce the number of annotated examples required to achieve a given
   level of performance.


Cemgil, A.T. and Kappen, B. (2003)
  "Monte Carlo Methods for Tempo Tracking and Rhythm Quantization", 
   Volume 18, pages 45-81.
   PostScript: volume18/cemgil03a.ps (1M)
	       compressed, volume18/cemgil03a.ps.Z (278K)
   PDF: volume18/cemgil03a.pdf (801K)

   Abstract: We present a probabilistic generative model for timing
   deviations in expressive music performance. The structure of the
   proposed model is equivalent to a switching state space model. The
   switch variables correspond to discrete note locations as in a musical
   score. The continuous hidden variables denote the tempo.  We formulate
   two well known music recognition problems, namely tempo tracking and
   automatic transcription (rhythm quantization) as filtering and maximum
   a posteriori (MAP) state estimation tasks. Exact computation of
   posterior features such as the MAP state is intractable in this model
   class, so we introduce Monte Carlo methods for integration and
   optimization. We compare Markov Chain Monte Carlo (MCMC) methods (such
   as Gibbs sampling, simulated annealing and iterative improvement) and
   sequential Monte Carlo methods (particle filters). Our simulation
   results suggest better results with sequential methods.  The methods
   can be applied in both online and batch scenarios such as tempo
   tracking and transcription and are thus potentially useful in a number
   of music applications such as adaptive automatic accompaniment, score
   typesetting and music information retrieval.


Grumberg, O., Livne, S. and Markovitch, S. (2003)
  "Learning to Order BDD Variables in Verification", 
   Volume 18, pages 83-116.
   PostScript: volume18/grumberg03a.ps (581K)
	       compressed, volume18/grumberg03a.ps.Z (262K)
   PDF: volume18/grumberg03a.pdf (279K)

   Abstract: The size and complexity of software and hardware systems
   have significantly increased in the past years.  As a result, it is
   harder to guarantee their correct behavior. One of the most successful
   methods for automated verification of finite-state systems is model
   checking. Most of the current model-checking systems use binary
   decision diagrams (BDDs) for the representation of the tested model
   and in the verification process of its properties. Generally, BDDs
   allow a canonical compact representation of a boolean function (given
   an order of its variables). The more compact the BDD is, the better
   performance one gets from the verifier. However, finding an optimal
   order for a BDD is an NP-complete problem. Therefore, several
   heuristic methods based on expert knowledge have been developed for
   variable ordering.
      We propose an alternative approach in which the variable ordering 
   algorithm gains 'ordering experience' from training models and 
   uses the learned knowledge for finding good orders. Our 
   methodology is based on offline learning of pair precedence 
   classifiers from training models, that is, learning which variable 
   pair permutation is more likely to lead to a good order. For each 
   training model, a number of training sequences are evaluated. Every 
   training model variable pair permutation is then tagged based on 
   its performance on the evaluated orders. The tagged permutations 
   are then passed through a feature extractor and are given as 
   examples to a classifier creation algorithm. Given a model for 
   which an order is requested, the ordering algorithm consults each 
   precedence classifier and constructs a pair precedence table 
   which is used to create the order. 
      Our algorithm was integrated with SMV, which is one of the most 
   widely used verification systems. Preliminary empirical evaluation of our 
   methodology, using real benchmark models, shows performance that 
   is better than random ordering and is competitive with existing 
   algorithms that use expert knowledge. We believe that in 
   sub-domains of models (alu, caches, etc.) our system will prove 
   even more valuable. This is because it features the ability to 
   learn sub-domain knowledge, something that no other ordering 
   algorithm does.


Peral, J. and Ferrandez, A. (2003)
  "Translation of Pronominal Anaphora between English and Spanish: Discrepancies and Evaluation", 
   Volume 18, pages 117-147.
   PostScript: volume18/peral03a.ps (471K)
	       compressed, volume18/peral03a.ps.Z (235K)
   HTML:  http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume18/peral03a-html/peral03a.html
   PDF: volume18/peral03a.pdf (232K)

   Abstract: This paper evaluates the different tasks carried out in the
   translation of pronominal anaphora in a machine translation (MT)
   system. The MT interlingua approach named AGIR (Anaphora Generation
   with an Interlingua Representation) improves upon other proposals
   presented to date because it is able to translate intersentential
   anaphors, detect co-reference chains, and translate Spanish zero
   pronouns into English---issues hardly considered by other systems. The
   paper presents the resolution and evaluation of these anaphora
   problems in AGIR with the use of different kinds of knowledge
   (lexical, morphological, syntactic, and semantic). The translation of
   English and Spanish anaphoric third-person personal pronouns
   (including Spanish zero pronouns) into the target language has been
   evaluated on unrestricted corpora. We have obtained a precision of
   80.4% and 84.8% in the translation of Spanish and English pronouns,
   respectively. Although we have only studied the Spanish and English
   languages, our approach can be easily extended to other languages such
   as Portuguese, Italian, or Japanese.


Lerman, K., Minton, S.N. and Knoblock, C.A. (2003)
  "Wrapper Maintenance: A Machine Learning Approach", 
   Volume 18, pages 149-181.
   PostScript: volume18/lerman03a.ps (1.1M)
	       compressed, volume18/lerman03a.ps.Z (615K)
   PDF: volume18/lerman03a.pdf (377K)

   Abstract: The proliferation of online information sources has led to an
   increased use of wrappers for extracting data from Web sources. While
   most of the previous research has focused on quick and efficient
   generation of wrappers, the development of tools for wrapper
   maintenance has received less attention. This is an important research
   problem because Web sources often change in ways that prevent the
   wrappers from extracting data correctly.  We present an efficient
   algorithm that learns structural information about data from positive
   examples alone. We describe how this information can be used for two
   wrapper maintenance applications: wrapper verification and
   reinduction. The wrapper verification system detects when a wrapper is
   not extracting correct data, usually because the Web source has
   changed its format.  The reinduction algorithm automatically recovers
   from changes in the Web source by identifying data on Web pages so
   that a new wrapper may be generated for this source.  To validate our
   approach, we monitored 27 wrappers over a period of a year. The
   verification algorithm correctly discovered 35 of the 37 wrapper
   changes, and made 16 mistakes, resulting in precision of 0.73 and
   recall of 0.95. We validated the reinduction algorithm on ten Web
   sources. We were able to successfully reinduce the wrappers, obtaining
   precision and recall values of 0.90 and 0.80 on the data
   extraction task.  


Tan, K.C., Khor, E.F., Lee, T.H. and Sathikannan, R. (2003)
  "An Evolutionary Algorithm with Advanced Goal and Priority Specification for Multi-objective Optimization", 
   Volume 18, pages 183-215.
   PostScript: volume18/tan03a.ps (1.9M)
	       compressed, volume18/tan03a.ps.Z (803K)
   PDF: volume18/tan03a.pdf (498K)

   Abstract: This paper presents an evolutionary algorithm with a new
   goal-sequence domination scheme for better decision support in
   multi-objective optimization. The approach allows the inclusion of
   advanced hard/soft priority and constraint information on each
   objective component, and is capable of incorporating multiple
   specifications with overlapping or non-overlapping objective functions
   via logical 'OR' and 'AND' connectives to drive the search
   towards multiple regions of trade-off. In addition, we propose a
   dynamic sharing scheme that is simple and adaptively estimated
   according to the on-line population distribution without needing any a
   priori parameter setting. Each feature in the proposed algorithm is
   examined to show its respective contribution, and the performance of
   the algorithm is compared with other evolutionary optimization
   methods. It is shown that the proposed algorithm has performed well in
   the diversity of evolutionary search and uniform distribution of
   non-dominated individuals along the final trade-offs, without
   significant computational effort. The algorithm is also applied to the
   design optimization of a practical servo control system for hard disk
   drives with a single voice-coil-motor actuator. Results of the
   evolutionary designed servo control system show a superior closed-loop
   performance compared to classical PID or RPT approaches.


Wilkins, D.E., Lee, T.J. and Berry, P. (2003)
  "Interactive Execution Monitoring of Agent Teams", 
   Volume 18, pages 217-261.
   PostScript: volume18/wilkins03a.ps (3.2M)
	       compressed, volume18/wilkins03a.ps.Z (2.3M)
   HTML:  http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume18/wilkins03a-html/ex-mon-jair-l2h.html
   PDF: volume18/wilkins03a.pdf (210K)

   Abstract: There is an increasing need for automated support for humans
   monitoring the activity of distributed teams of cooperating agents,
   both human and machine. We characterize the domain-independent
   challenges posed by this problem, and describe how properties of
   domains influence the challenges and their solutions. We will
   concentrate on dynamic, data-rich domains where humans are ultimately
   responsible for team behavior. Thus, the automated aid should
   interactively support effective and timely decision making by the
   human. We present a domain-independent categorization of the types of
   alerts a plan-based monitoring system might issue to a user, where
   each type generally requires different monitoring techniques. We
   describe a monitoring framework for integrating many domain-specific
   and task-specific monitoring techniques and then using the concept of
   value of an alert to avoid operator overload.
      We use this framework to describe an execution monitoring approach we
   have used to implement Execution Assistants (EAs) in two different
   dynamic, data-rich, real-world domains to assist a human in
   monitoring team behavior. One domain (Army small unit operations) has
   hundreds of mobile, geographically distributed agents, a combination
   of humans, robots, and vehicles. The other domain (teams of unmanned
   ground and air vehicles) has a handful of cooperating robots. Both
   domains involve unpredictable adversaries in the vicinity. Our
   approach customizes monitoring behavior for each specific task, plan,
   and situation, as well as for user preferences. Our EAs alert the
   human controller when reported events threaten plan execution or
   physically threaten team members. Alerts were generated in a timely
   manner without inundating the user with too many alerts (less than
   10 percent of alerts are unwanted, as judged by domain experts).  


Poole, D. and Zhang, N.L. (2003)
  "Exploiting Contextual Independence In Probabilistic Inference", 
   Volume 18, pages 263-313.
   PostScript: volume18/poole03a.ps (1.6M)
	       compressed, volume18/poole03a.ps.Z (454K)
   HTML:  http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume18/poole03a-html/poole03a.html
   PDF: volume18/poole03a.pdf (236K)

   Abstract: Bayesian belief networks have grown to prominence because
   they provide compact representations for many problems for which
   probabilistic inference is appropriate, and there are algorithms to
   exploit this compactness. The next step is to allow compact
   representations of the conditional probabilities of a variable given
   its parents. In this paper we present such a representation that
   exploits contextual independence in terms of parent contexts; which
   variables act as parents may depend on the value of other
   variables. The internal representation is in terms of contextual
   factors (confactors) that is simply a pair of a context and a table.
   The algorithm, contextual variable elimination, is based on the
   standard variable elimination algorithm that eliminates the non-query
   variables in turn, but when eliminating a variable, the tables that
   need to be multiplied can depend on the context. This algorithm
   reduces to standard variable elimination when there is no contextual
   independence structure to exploit. We show how this can be much more
   efficient than variable elimination when there is structure to
   exploit. We explain why this new method can exploit more structure
   than previous methods for structured belief network inference and an
   analogous algorithm that uses trees.  


Brafman, R.I. and Domshlak, C. (2003)
  "Structure and Complexity in Planning with Unary Operators", 
   Volume 18, pages 315-349.
   PostScript: volume18/brafman03a.ps (636K)
	       compressed, volume18/brafman03a.ps.Z (324K)
   PDF: volume18/brafman03a.pdf (351K)

   Abstract: Unary operator domains -- i.e., domains in which operators
   have a single effect -- arise naturally in many control problems.  In
   its most general form, the problem of STRIPS planning in unary
   operator domains is known to be as hard as the general STRIPS planning
   problem -- both are PSPACE-complete. However, unary operator domains
   induce a natural structure, called the domain's causal graph. This
   graph relates between the preconditions and effect of each domain
   operator. Causal graphs were exploited by Williams and Nayak in order
   to analyze plan generation for one of the controllers in NASA's
   Deep-Space One spacecraft. There, they utilized the fact that when
   this graph is acyclic, a serialization ordering over any subgoal can
   be obtained quickly. In this paper we conduct a comprehensive study of
   the relationship between the structure of a domain's causal graph and
   the complexity of planning in this domain.  On the positive side, we
   show that a non-trivial polynomial time plan generation algorithm
   exists for domains whose causal graph induces a polytree with a
   constant bound on its node indegree. On the negative side, we show
   that even plan existence is hard when the graph is a directed-path
   singly connected DAG.  More generally, we show that the number of
   paths in the causal graph is closely related to the complexity of
   planning in the associated domain.  Finally we relate our results to
   the question of complexity of planning with serializable subgoals.


Patel-Schneider, P.F. and Sebastiani, R. (2003)
  "A New General Method to Generate Random Modal Formulae for Testing Decision Procedures", 
   Volume 18, pages 351-389.
   PostScript: volume18/patelschneider03a.ps (1.9M)
	       compressed, volume18/patelschneider03a.ps.Z (422K)
   PDF: volume18/patelschneider03a.pdf (691K)

   Abstract: The recent emergence of heavily-optimized modal decision
   procedures has highlighted the key role of empirical testing in this
   domain.  Unfortunately, the introduction of extensive empirical tests
   for modal logics is recent, and so far none of the proposed test
   generators is very satisfactory.  To cope with this fact, we present a
   new random generation method that provides benefits over previous
   methods for generating empirical tests.  It fixes and much generalizes
   one of the best-known methods, the random CNF_[]m test, allowing for
   generating a much wider variety of problems, covering in principle the
   whole input space.  Our new method produces much more suitable test
   sets for the current generation of modal decision procedures.  We
   analyze the features of the new method by means of an extensive
   collection of empirical tests.


Lang, J., Liberatore, P. and Marquis, P. (2003)
  "Propositional Independence - Formula-Variable Independence and
Forgetting", 
   Volume 18, pages 391-443.
   PostScript: volume18/lang03a.ps (503K)
	       compressed, volume18/lang03a.ps.Z (216K)
   PDF: volume18/lang03a.pdf (486K)

   Abstract: Independence -- the study of what is relevant to a given
   problem of reasoning -- has received an increasing attention from the
   AI community. In this paper, we consider two basic forms of
   independence, namely, a syntactic one and a semantic one. We show
   features and drawbacks of them.  In particular, while the syntactic
   form of independence is computationally easy to check, there are cases
   in which things that intuitively are not relevant are not recognized
   as such.  We also consider the problem of forgetting, i.e., distilling
   from a knowledge base only the part that is relevant to the set of
   queries constructed from a subset of the alphabet. While such process
   is computationally hard, it allows for a simplification of subsequent
   reasoning, and can thus be viewed as a form of compilation: once the
   relevant part of a knowledge base has been extracted, all reasoning
   tasks to be performed can be simplified.


Acid, S. and de Campos. L.M. (2003)
  "Searching for Bayesian Network Structures in the Space of Restricted Acyclic Partially Directed Graphs", 
   Volume 18, pages 445-490.
   PostScript: volume18/acid03a.ps (894K)
	       compressed, volume18/acid03a.ps.Z (306K)
   HTML:  http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume18/acid03a-html/index.html
   PDF: volume18/acid03a.pdf (544K)

   Abstract: Although many algorithms have been designed to construct
   Bayesian network structures using different approaches and principles,
   they all employ only two methods: those based on independence
   criteria, and those based on a scoring function and a search procedure
   (although some methods combine the two). Within the score+search
   paradigm, the dominant approach uses local search methods in the space
   of directed acyclic graphs (DAGs), where the usual choices for
   defining the elementary modifications (local changes) that can be
   applied are arc addition, arc deletion, and arc reversal. In this
   paper, we propose a new local search method that uses a different
   search space, and which takes account of the concept of equivalence
   between network structures: restricted acyclic partially directed
   graphs (RPDAGs). In this way, the number of different configurations
   of the search space is reduced, thus improving efficiency. Moreover,
   although the final result must necessarily be a local optimum given
   the nature of the search method, the topology of the new search space,
   which avoids making early decisions about the directions of the arcs,
   may help to find better local optima than those obtained by searching
   in the DAG space. Detailed results of the evaluation of the proposed
   search method on several test problems, including the well-known Alarm
   Monitoring System, are also presented.


Reiter, E., Sripada, S.G., and Robertson, R. (2003)
  "Acquiring Correct Knowledge for Natural Language Generation", 
   Volume 18, pages 491-516.
   PostScript: volume18/reiter03a.ps (793K)
	       compressed, volume18/reiter03a.ps.Z (236K)
   PDF: volume18/reiter03a.pdf (203K)

   Abstract: Natural language generation (NLG) systems are computer software
   systems that produce texts in English and other human languages, often
   from non-linguistic input data. NLG systems, like most AI systems, need
   substantial amounts of knowledge.  However, our experience in two 
   NLG projects suggests that it is difficult to acquire correct knowledge 
   for NLG systems; indeed, every knowledge acquisition (KA) technique 
   we tried had significant problems. In general terms, these problems were 
   due to the complexity, novelty, and poorly understood nature of the 
   tasks our systems attempted, and were worsened by the fact that people
   write so differently. This meant in particular that corpus-based KA 
   approaches suffered because it was impossible to assemble a sizable 
   corpus of high-quality consistent manually written texts in our domains;
   and structured expert-oriented KA techniques suffered because experts 
   disagreed and because we could not get enough information about special 
   and unusual cases to build robust systems. We believe that such problems 
   are likely to affect many other NLG systems as well.  In the long term, 
   we hope that new KA techniques may emerge to help NLG system builders.  
   In the shorter term, we believe that understanding how individual KA 
   techniques can fail, and using a mixture of different KA techniques 
   with different strengths and weaknesses, can help developers acquire 
   NLG knowledge that is mostly correct.

	  		          Volume 19


Zanuttini, B. (2003)
  "New Polynomial Classes for Logic-Based Abduction", 
   Volume 19, pages 1-10.
   PostScript: volume19/zanuttini03a.ps (174K)
	       compressed, volume19/zanuttini03a.ps.Z (85K)
   Online Appendix1: volume19/zanuttini03a-appendix1.pdf (200K) Technical report with proofs and examples
   HTML:  http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume19/zanuttini03a-html/zanuttini03a-html.html
   PDF: volume19/zanuttini03a.pdf (155K)

   Abstract: We address the problem of propositional logic-based
   abduction, i.e., the problem of searching for a best explanation for a
   given propositional observation according to a given propositional
   knowledge base. We give a general algorithm, based on the notion of
   projection; then we study restrictions over the representations of the
   knowledge base and of the query, and find new polynomial classes of
   abduction problems.