From jair-ed@isi.edu Wed Jan 22 01:07:48 2003 From: jair-ed@isi.edu (JAIRMAIL) Date: Tue, 21 Jan 2003 17:07:48 -0800 (PST) Subject: [Jairsubscribers] Welcome JAIR Subscribers Message-ID: <200301220107.h0M17mF22876@nitro.isi.edu> Dear JAIR Subscribers: Thank you for resubscribing to the JAIR mailing list. We plan to send out notices every two months or so listing new JAIR papers. If you have any comments or questions, please send mail to jair-ed@isi.edu. Note that this mailing list is read only... we do not accept any posts here. To unsubscribe, visit http://mailman.isi.edu/mailman/listinfo/jairsubscribers Since notices were not sent out over the last few months due to the problems with our previous mailing system, below you'll find a list of recent papers for your convenience: Wolpert, D.H. and Tumer, K. (2002) "Collective Intelligence, Data Routing and Braess' Paradox" Pynadath, D.V. and Tambe, M. (2002) "The Communicative Multiagent Team Decision Problem: Analyzing Teamwork Theories and Models" Baget, J.F. and Mugnier, M.L. (2002) "Extensions of Simple Conceptual Graphs: the Complexity of Rules and Constraints" Howe, A.E. and Dahlman, E. (2002) "A Critical Assessment of Benchmark Comparison in Planning" Barzilay, R., Elhadad, N., and McKeown K.R. (2002) "Inferring Strategies for Sentence Ordering in Multidocument News Summarization" Halpern, J.Y. and Pucella, R. (2002) "A Logic for Reasoning about Upper Probabilities" Kaminka, G.A., Pynadath, D.V. and Tambe, M. (2002) "Monitoring Teams by Overhearing: A Multi-Agent Plan-Recognition Approach" Nock, R. (2002) "Inducing Interpretable Voting Classifiers without Trading Accuracy for Simplicity: Theoretical Results, Approximation Algorithms, and Experiments" Scerri, P., Pynadath, D.V., Tampe, M. (2002) "Towards Adjustable Autonomy for the Real World" Volume 17, pages 171-228. Darwiche, A. and Marquis, P. (2002) "A Knowledge Compilation Map" Chan, H. and Darwiche, A. (2002) "When do Numbers Really Matter?" Bod, R. (2002) "A Unified Model of Structural Organization in Language and Music" Gao, Y. and Culberson, J. (2002) "An Analysis of Phase Transition in NK Landscapes" Al-Ani, A. and Deriche, M. (2002) "A New Technique for Combining Multiple Classifiers using The Dempster-Shafer Theory of Evidence" Tennenholtz, M. (2002) "Competitive Safety Analysis: Robust Decision-Making in Multi-Agent Systems" Fern, A., Givan, R., and Siskind, J.M. (2002) "Specific-to-General Learning for Temporal Events with Application to Learning Event Definitions from Video" Bui, H.H., Venkatesh, S., and West, G. (2002) "Policy Recognition in the Abstract Hidden Markov Model" Gamberger, D. and Lavrac, N. (2002) "Expert-Guided Subgroup Discovery: Methodology and Application" From jair-ed@isi.edu Sat Mar 1 01:36:26 2003 From: jair-ed@isi.edu (JAIRMAIL) Date: Fri, 28 Feb 2003 17:36:26 -0800 (PST) Subject: [Jairsubscribers] Recent JAIR articles Message-ID: <200303010136.h211aQE18356@nitro.isi.edu> CONTENTS: I. New JAIR Articles II. Instructions for Obtaining Articles Dear JAIR subscriber: This message lists papers that have been recently published in JAIR and describes how to access them. (If you wish to remove yourself from this mailing list, see section II.) - Halpern, J.Y. (1999) "Cox's Theorem Revisited" - Kambhampati, S. (2000) "Planning Graph as a (Dynamic) CSP: Exploiting EBL, DDB and other CSP Search Techniques in Graphplan" - Barber, F. (2000) "Reasoning on Interval and Point-based Disjunctive Metric Constraints in Temporal Contexts" ---------------------------------------------------------------- I. NEW ARTICLES: Halpern, J.Y. (1999) "Cox's Theorem Revisited", Volume 11, pages 429-435. Available in PDF, PostScript and compressed PostScript. For quick access go to 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. Kambhampati, S. (2000) "Planning Graph as a (Dynamic) CSP: Exploiting EBL, DDB and other CSP Search Techniques in Graphplan", Volume 12, pages 1-34. Available in PDF, PostScript and compressed PostScript. For quick access go to 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. Available in HTML, PDF, PostScript and compressed PostScript. For quick access go to 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. ---------------------------------------------------------------- II. INSTRUCTIONS FOR OBTAINING ARTICLES When an article is published in JAIR, it is immediately available from our distribution sites. The article is also immediately announced and posted on the USENET newsgroups comp.ai.jair.announce and comp.ai.jair.papers. Periodically, we send out announcements like this to our mailing list announcing recent papers, for those of you who do not read the JAIR newsgroups. (Note that if you read the JAIR newsgroups, you have the advantage of immediately being notified about new papers.) Each complete volume of JAIR is also published by Morgan Kaufmann Publishers. To obtain an article, there are a variety of access methods: -- WWW: You can access our server through the web. The URL is: http://www.jair.org/ -- Anonymous FTP from either of the two sites below: CMU Machine: ftp.cs.cmu.edu directory: project/jair Genoa Machine: ftp.mrg.dist.unige.it directory: pub/jair/pub -- Newsgroups: read comp.ai.jair.announce and comp.ai.jair.papers To Remove Yourself from this Mailing List To remove yourself from the JAIR subscribers mailing list, visit our Web site (http://www.jair.org/) and follow the link "notify me of new articles". In the event that you've already deleted yourself from the list and we keep sending you messages like this one, send mail to jair-ed@isi.edu. From jair-ed@isi.edu Sat Mar 1 02:06:42 2003 From: jair-ed@isi.edu (JAIRMAIL) Date: Fri, 28 Feb 2003 18:06:42 -0800 (PST) Subject: [Jairsubscribers] Correction! New articles... Message-ID: <200303010206.h2126gj06603@nitro.isi.edu> My apologies! As you can see from the last message, we are still experiencing a few glitches with our new mailing last. I inadvertently sent out a 3-year-old message. The correct message below lists JAIR articles recently published in Volume 18. - Steven Minton JAIR Managing Editor CONTENTS: I. New JAIR Articles II. Instructions for Obtaining Articles Dear JAIR subscriber: This message lists papers that have been recently published in JAIR and describes how to access them. (If you wish to remove yourself from this mailing list, see section II.) Thompson, C.A and Mooney, R.J. (2003) "Acquiring Word-Meaning Mappings for Natural Language Interfaces", For quick access go to Cemgil, A.T. and Kappen, B. (2003) "Monte Carlo Methods for Tempo Tracking and Rhythm Quantization", For quick access go to Brumberg, O., Livne, S. and Markovitch, S. (2003) "Learning to Order BDD Variables in Verification", For quick access go to Peral, J. and Ferrandez, A. (2003) "Translation of Pronominal Anaphora between English and Spanish: Discrepancies and Evaluation", For quick access go to Lerman, K., Minton, S.N. and Knoblock, C.A. (2003) "Wrapper Maintenance: A Machine Learning Approach", Volume 18, pages 149-181. For quick access go to 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. For quick access go to ---------------------------------------------------------------- II. INSTRUCTIONS FOR OBTAINING ARTICLES When an article is published in JAIR, it is immediately available from our distribution sites. The article is also immediately announced and posted on the USENET newsgroups comp.ai.jair.announce and comp.ai.jair.papers. Periodically, we send out announcements like this to our mailing list announcing recent papers, for those of you who do not read the JAIR newsgroups. (Note that if you read the JAIR newsgroups, you have the advantage of immediately being notified about new papers.) To obtain an article, there are a variety of access methods: -- WWW: You can access our server through the web. The URL is: http://www.jair.org/ -- Anonymous FTP from the site below: CMU Machine: ftp.cs.cmu.edu directory: project/jair -- Newsgroups: read comp.ai.jair.announce and comp.ai.jair.papers To Remove Yourself from this Mailing List To remove yourself from the JAIR subscribers mailing list, visit our Web site (http://www.jair.org/), follow the link "notify me of new articles", enter your email address in the form at the bottom of the page, and follow the directions. In the event that you've already deleted yourself from the list and we keep sending you messages like this one, send mail to jair-ed@isi.edu. From jair-ed@isi.edu Tue Apr 1 17:23:30 2003 From: jair-ed@isi.edu (JAIRMAIL) Date: Tue, 1 Apr 2003 09:23:30 -0800 (PST) Subject: [Jairsubscribers] Announcement: JMLG Message-ID: <200304011723.h31HNU311650@nitro.isi.edu> JAIR Readers: The announcement below was passed to us by Michael Littman (mlittman@cs.rutgers.edu). JAIR is not responsible for any of the content. Thanks! -Ed. .................................................. To the AI and ML community: We are pleased to announce the first volume of a new online journal, the Journal of Machine Learning Gossip. The volume includes the following award-winning papers: Markov Indecision Processes: A Formal Model of Decision-Making Under Extreme Confusion by Harry Q. Bovik, Judy Q. Goldsmith, Andrew Q. Klapper, and Michael Q. Littman Data Set Selection by Doudou LaLoudouana and Mambobo Bonouliqui Tarare On the Origin and Destiny of Inductive Machine Learning by Terran Lane Visit our web site http://www.jmlg.org/papers.htm for access to these papers and for more information about the journal and its goals. We look forward to serving you in the coming years. Sincerely, Cycle L. Bittmap, PhD on behalf of the editors of the JMLG From jair-ed@isi.edu Thu May 1 01:46:02 2003 From: jair-ed@isi.edu (JAIRMAIL) Date: Wed, 30 Apr 2003 17:46:02 -0700 (PDT) Subject: [Jairsubscribers] JAIR News Message-ID: <200305010046.h410k2u07498@nitro.isi.edu> CONTENTS: I. New JAIR Articles II. Instructions for Obtaining Articles Dear JAIR subscriber: This message lists papers that have been recently published in JAIR and describes how to access them. (If you wish to remove yourself from this mailing list, see section II.) Wilkins, D.E., Lee, T.J. and Berry, P. (2003) "Interactive Execution Monitoring of Agent Teams" Poole, D. and Zhang, N.L. (2003) "Exploiting Contextual Independence In Probabilistic Inference" Brafman, R.I. and Domshlak, C. (2003) "Structure and Complexity in Planning with Unary Operators" ---------------------------------------------------------------- I. New JAIR Articles Wilkins, D.E., Lee, T.J. and Berry, P. (2003) "Interactive Execution Monitoring of Agent Teams", Volume 18, pages 217-261. For quick access go to 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. For quick access go to 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. For quick access go to 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. ---------------------------------------------------------------- II. INSTRUCTIONS FOR OBTAINING ARTICLES When an article is published in JAIR, it is immediately available from our distribution sites. The article is also immediately announced and posted on the USENET newsgroups comp.ai.jair.announce and comp.ai.jair.papers. Periodically, we send out announcements like this to our mailing list announcing recent papers, for those of you who do not read the JAIR newsgroups. (Note that if you read the JAIR newsgroups, you have the advantage of immediately being notified about new papers.) To obtain an article, there are a variety of access methods: -- WWW: You can access our server through the web. The URL is: http://www.jair.org/ -- Anonymous FTP from the site below: CMU Machine: ftp.cs.cmu.edu directory: project/jair -- Newsgroups: read comp.ai.jair.announce and comp.ai.jair.papers To Remove Yourself from this Mailing List To remove yourself from the JAIR subscribers mailing list, visit our Web site (http://www.jair.org/), follow the link "notify me of new articles", enter your email address in the form at the bottom of the page, and follow the directions. In the event that you've already deleted yourself from the list and we keep sending you messages like this one, send mail to jair-ed@isi.edu. From jair-ed@isi.edu Wed Jul 2 00:53:36 2003 From: jair-ed@isi.edu (JAIRMAIL) Date: Tue, 1 Jul 2003 16:53:36 -0700 (PDT) Subject: [Jairsubscribers] JAIR update Message-ID: <200307012353.h61NraF26381@nitro.isi.edu> CONTENTS: I. New JAIR Articles II. Instructions for Obtaining Articles Dear JAIR subscriber: This message lists papers that have been recently published in JAIR and describes how to access them. (If you wish to remove yourself from this mailing list, see section II.) Patel-Schneider, P.F. and Sebastiani, R. (2003) "A New General Method to Generate Random Modal Formulae for Testing Decision Procedures" Lang, J., Liberatore, P. and Marquis, P. (2003) "Propositional Independence - Formula-Variable Independence and Forgetting" Acid, S. and de Campos. L.M. (2003) "Searching for Bayesian Network Structures in the Space of Restricted Acyclic Partially Directed Graphs" Reiter, E., Sripada, S.G., and Robertson, R. (2003) "Acquiring Correct Knowledge for Natural Language Generation" ---------------------------------------------------------------- I. New JAIR Articles 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. Available in PDF, PostScript and compressed PostScript. For quick access go to 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. Available in PDF, PostScript and compressed PostScript. For quick access go to 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. Available in HTML, PDF, PostScript and compressed PostScript. For quick access go to 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. Available in HTML, PDF, PostScript and compressed PostScript. For quick access go to 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. ---------------------------------------------------------------- II. INSTRUCTIONS FOR OBTAINING ARTICLES When an article is published in JAIR, it is immediately available from our distribution sites. The article is also immediately announced and posted on the USENET newsgroups comp.ai.jair.announce and comp.ai.jair.papers. Periodically, we send out announcements like this to our mailing list announcing recent papers, for those of you who do not read the JAIR newsgroups. (Note that if you read the JAIR newsgroups, you have the advantage of immediately being notified about new papers.) To obtain an article, there are a variety of access methods: -- WWW: You can access our server through the web. The URL is: http://www.jair.org/ -- Anonymous FTP from the site below: CMU Machine: ftp.cs.cmu.edu directory: project/jair -- Newsgroups: read comp.ai.jair.announce and comp.ai.jair.papers To Remove Yourself from this Mailing List To remove yourself from the JAIR subscribers mailing list, visit our Web site (http://www.jair.org/), follow the link "notify me of new articles", enter your email address in the form at the bottom of the page, and follow the directions. In the event that you've already deleted yourself from the list and we keep sending you messages like this one, send mail to jair-ed@isi.edu. From jair-ed@isi.edu Tue Oct 7 23:02:18 2003 From: jair-ed@isi.edu (JAIRMAIL) Date: Tue, 7 Oct 2003 15:02:18 -0700 (PDT) Subject: [Jairsubscribers] JAIR update Message-ID: <200310072202.h97M2I218182@nitro.isi.edu> CONTENTS: I. New JAIR Articles II. Instructions for Obtaining Articles Dear JAIR subscriber: This message lists papers that have been recently published in JAIR and describes how to access them. (If you wish to remove yourself from this mailing list, see section II.) Zanuttini, B. (2003) "New Polynomial Classes for Logic-Based Abduction" Brafman, R.I. and Tennenholtz, M. (2003) "Learning to Coordinate Efficiently: A Model-based Approach" Eiter, T., Faber, W., Leone, N., Pfeifer, G. and Polleres, A. (2003) "Answer Set Planning Under Action Costs" Finkelstein, L., Markovitch, S. and Rivlin, E. (2003) "Optimal Schedules for Parallelizing Anytime Algorithms: The Case of Shared Resources" Leisink, M. and Kappen, B. (2003) "Bound Propagation" Maynard-Zhang, P. and Lehmann, D. (2003) "Representing and Aggregating Conflicting Beliefs" Wiewiora, E. (2003) "Potential-Based Shaping and Q-Value Initialization are Equivalent" Stone, P., Schapire, R.E., Littman, M.L., Csirik, J.A. and McAllester, D.(2003) "Decision-Theoretic Bidding Based on Learned Density Models in Simultaneous, Interacting Auctions" ---------------------------------------------------------------- I. New JAIR Articles Zanuttini, B. (2003) "New Polynomial Classes for Logic-Based Abduction", Volume 19, pages 1-10. Available in HTML, PDF, PostScript and compressed PostScript. An online appendix (Technical report with proofs and examples) is also a available. For quick access go to 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. Brafman, R.I. and Tennenholtz, M. (2003) "Learning to Coordinate Efficiently: A Model-based Approach", Volume 19, pages 11-23. For quick access go to Abstract: In common-interest stochastic games all players receive an identical payoff. Players participating in such games must learn to coordinate with each other in order to receive the highest-possible value. A number of reinforcement learning algorithms have been proposed for this problem, and some have been shown to converge to good solutions in the limit. In this paper we show that using very simple model-based algorithms, much better (i.e., polynomial) convergence rates can be attained. Moreover, our model-based algorithms are guaranteed to converge to the optimal value, unlike many of the existing algorithms. Eiter, T., Faber, W., Leone, N., Pfeifer, G. and Polleres, A. (2003) "Answer Set Planning Under Action Costs", Volume 19, pages 25-71. For quick access go to Abstract: Recently, planning based on answer set programming has been proposed as an approach towards realizing declarative planning systems. In this paper, we present the language Kc, which extends the declarative planning language K by action costs. Kc provides the notion of admissible and optimal plans, which are plans whose overall action costs are within a given limit resp. minimum over all plans (i.e., cheapest plans). As we demonstrate, this novel language allows for expressing some nontrivial planning tasks in a declarative way. Furthermore, it can be utilized for representing planning problems under other optimality criteria, such as computing ``shortest'' plans (with the least number of steps), and refinement combinations of cheapest and fastest plans. We study complexity aspects of the language Kc and provide a transformation to logic programs, such that planning problems are solved via answer set programming. Furthermore, we report experimental results on selected problems. Our experience is encouraging that answer set planning may be a valuable approach to expressive planning systems in which intricate planning problems can be naturally specified and solved. Finkelstein, L., Markovitch, S. and Rivlin, E. (2003) "Optimal Schedules for Parallelizing Anytime Algorithms: The Case of Shared Resources", Volume 19, pages 73-138. For quick access go to Abstract: The performance of anytime algorithms can be improved by simultaneously solving several instances of algorithm-problem pairs. These pairs may include different instances of a problem (such as starting from a different initial state), different algorithms (if several alternatives exist), or several runs of the same algorithm (for non-deterministic algorithms). In this paper we present a methodology for designing an optimal scheduling policy based on the statistical characteristics of the algorithms involved. We formally analyze the case where the processes share resources (a single-processor model), and provide an algorithm for optimal scheduling. We analyze, theoretically and empirically, the behavior of our scheduling algorithm for various distribution types. Finally, we present empirical results of applying our scheduling algorithm to the Latin Square problem. Leisink, M. and Kappen, B. (2003) "Bound Propagation", Volume 19, pages 139-154. For quick access go to Abstract: In this article we present an algorithm to compute bounds on the marginals of a graphical model. For several small clusters of nodes upper and lower bounds on the marginal values are computed independently of the rest of the network. The range of allowed probability distributions over the surrounding nodes is restricted using earlier computed bounds. As we will show, this can be considered as a set of constraints in a linear programming problem of which the objective function is the marginal probability of the center nodes. In this way knowledge about the maginals of neighbouring clusters is passed to other clusters thereby tightening the bounds on their marginals. We show that sharp bounds can be obtained for undirected and directed graphs that are used for practical applications, but for which exact computations are infeasible. Maynard-Zhang, P. and Lehmann, D. (2003) "Representing and Aggregating Conflicting Beliefs", Volume 19, pages 155-203. For quick access go to Abstract: We consider the two-fold problem of representing collective beliefs and aggregating these beliefs. We propose a novel representation for collective beliefs that uses modular, transitive relations over possible worlds. They allow us to represent conflicting opinions and they have a clear semantics, thus improving upon the quasi-transitive relations often used in social choice. We then describe a way to construct the belief state of an agent informed by a set of sources of varying degrees of reliability. This construction circumvents Arrow's Impossibility Theorem in a satisfactory manner by accounting for the explicitly encoded conflicts. We give a simple set-theory-based operator for combining the information of multiple agents. We show that this operator satisfies the desirable invariants of idempotence, commutativity, and associativity, and, thus, is well-behaved when iterated, and we describe a computationally effective way of computing the resulting belief state. Finally, we extend our framework to incorporate voting. Wiewiora, E. (2003) "Potential-Based Shaping and Q-Value Initialization are Equivalent", Volume 19, pages 205-208. For quick access go to Abstract: Shaping has proven to be a powerful but precarious means of improving reinforcement learning performance. Ng, Harada, and Russell (1999) proposed the potential-based shaping algorithm for adding shaping rewards in a way that guarantees the learner will learn optimal behavior. In this note, we prove certain similarities between this shaping algorithm and the initialization step required for several reinforcement learning algorithms. More specifically, we prove that a reinforcement learner with initial Q-values based on the shaping algorithm's potential function make the same updates throughout learning as a learner receiving potential-based shaping rewards. We further prove that under a broad category of policies, the behavior of these two learners are indistinguishable. The comparison provides intuition on the theoretical properties of the shaping algorithm as well as a suggestion for a simpler method for capturing the algorithm's benefit. In addition, the equivalence raises previously unaddressed issues concerning the efficiency of learning with potential-based shaping. Stone, P., Schapire, R.E., Littman, M.L., Csirik, J.A. and McAllester, D.(2003) "Decision-Theoretic Bidding Based on Learned Density Models in Simultaneous, Interacting Auctions", Volume 19, pages 209-242. For quick access go to Abstract: Auctions are becoming an increasingly popular method for transacting business, especially over the Internet. This article presents a general approach to building autonomous bidding agents to bid in multiple simultaneous auctions for interacting goods. A core component of our approach learns a model of the empirical price dynamics based on past data and uses the model to analytically calculate, to the greatest extent possible, optimal bids. We introduce a new and general boosting-based algorithm for conditional density estimation problems of this kind, i.e., supervised learning problems in which the goal is to estimate the entire conditional distribution of the real-valued label. This approach is fully implemented as ATTac-2001, a top-scoring agent in the second Trading Agent Competition (TAC-01). We present experiments demonstrating the effectiveness of our boosting-based price predictor relative to several reasonable alternatives. ---------------------------------------------------------------- II. INSTRUCTIONS FOR OBTAINING ARTICLES When an article is published in JAIR, it is immediately available from our distribution sites. The article is also immediately announced and posted on the USENET newsgroups comp.ai.jair.announce and comp.ai.jair.papers. Periodically, we send out announcements like this to our mailing list announcing recent papers, for those of you who do not read the JAIR newsgroups. (Note that if you read the JAIR newsgroups, you have the advantage of immediately being notified about new papers.) To obtain an article, there are a variety of access methods: -- WWW: You can access our server through the web. The URL is: http://www.jair.org/ -- Anonymous FTP from the site below: CMU Machine: ftp.cs.cmu.edu directory: project/jair -- Newsgroups: read comp.ai.jair.announce and comp.ai.jair.papers To Remove Yourself from this Mailing List To remove yourself from the JAIR subscribers mailing list, visit our Web site (http://www.jair.org/), follow the link "notify me of new articles", enter your email address in the form at the bottom of the page, and follow the directions. In the event that you've already deleted yourself from the list and we keep sending you messages like this one, send mail to jair-ed@isi.edu. From jair-ed@isi.edu Wed Dec 31 09:00:27 2003 From: jair-ed@isi.edu (JAIRMAIL) Date: Wed, 31 Dec 2003 01:00:27 -0800 (PST) Subject: [Jairsubscribers] JAIR Update Message-ID: <200312310900.hBV90RT08306@nitro.isi.edu> CONTENTS: I. New JAIR Articles II. Instructions for Obtaining Articles Dear JAIR subscriber: This message lists papers that have been recently published in JAIR and describes how to access them. (If you wish to remove yourself from this mailing list, see section II.) Grunwald, P.D. and Halpern, J.Y. "Updating Probabilities" Lin, F. "Compiling Causal Theories to Successor State Axioms and STRIPS-Like Systems" Weiss, G.M. and Provost, F. "Learning When Training Data are Costly: The Effect of Class Distribution on Tree Induction" Wray, R.E. and Laird, J.E. "An Architectural Approach to Ensuring Consistency in Hierarchical Execution" Guestrin, C., Koller, D., Parr, R. and Venkataraman, S. "Efficient Solution Algorithms for Factored MDPs" Console, L., Picardi, C. and Theseider Dupre, D. "Temporal Decision Trees: Model-based Diagnosis of Dynamic Systems On-Board" Walsh, W.E. and Wellman, M.P. "Decentralized Supply Chain Formation: A Market Protocol and Competitive Equilibrium Analysis" Price, B. and Boutilier, C. "Accelerating Reinforcement Learning through Implicit Imitation" Sanchez, R. and Kambhampati, S. "AltAltp: Online Parallelization of Plans with Heuristic State Search" ---------------------------------------------------------------- I. New JAIR Articles Grunwald, P.D. and Halpern, J.Y. (2003) "Updating Probabilities", Volume 19, pages 243-278. For quick access go to Abstract: As examples such as the Monty Hall puzzle show, applying conditioning to update a probability distribution on a ``naive space'', which does not take into account the protocol used, can often lead to counterintuitive results. Here we examine why. A criterion known as CAR (``coarsening at random'') in the statistical literature characterizes when ``naive'' conditioning in a naive space works. We show that the CAR condition holds rather infrequently, and we provide a procedural characterization of it, by giving a randomized algorithm that generates all and only distributions for which CAR holds. This substantially extends previous characterizations of CAR. We also consider more generalized notions of update such as Jeffrey conditioning and minimizing relative entropy (MRE). We give a generalization of the CAR condition that characterizes when Jeffrey conditioning leads to appropriate answers, and show that there exist some very simple settings in which MRE essentially never gives the right results. This generalizes and interconnects previous results obtained in the literature on CAR and MRE. Lin, F. (2003) "Compiling Causal Theories to Successor State Axioms and STRIPS-Like Systems", Volume 19, pages 279-314. An online appendix (Benchmark action domain descriptions) is also a available. For quick access go to Abstract: We describe a system for specifying the effects of actions. Unlike those commonly used in AI planning, our system uses an action description language that allows one to specify the effects of actions using domain rules, which are state constraints that can entail new action effects from old ones. Declaratively, an action domain in our language corresponds to a nonmonotonic causal theory in the situation calculus. Procedurally, such an action domain is compiled into a set of logical theories, one for each action in the domain, from which fully instantiated successor state-like axioms and STRIPS-like systems are then generated. We expect the system to be a useful tool for knowledge engineers writing action specifications for classical AI planning systems, GOLOG systems, and other systems where formal specifications of actions are needed. Weiss, G.M. and Provost, F. (2003) "Learning When Training Data are Costly: The Effect of Class Distribution on Tree Induction", Volume 19, pages 315-354. For quick access go to Abstract: For large, real-world inductive learning problems, the number of training examples often must be limited due to the costs associated with procuring, preparing, and storing the training examples and/or the computational costs associated with learning from them. In such circumstances, one question of practical importance is: if only n training examples can be selected, in what proportion should the classes be represented? In this article we help to answer this question by analyzing, for a fixed training-set size, the relationship between the class distribution of the training data and the performance of classification trees induced from these data. We study twenty-six data sets and, for each, determine the best class distribution for learning. The naturally occurring class distribution is shown to generally perform well when classifier performance is evaluated using undifferentiated error rate (0/1 loss). However, when the area under the ROC curve is used to evaluate classifier performance, a balanced distribution is shown to perform well. Since neither of these choices for class distribution always generates the best-performing classifier, we introduce a budget-sensitive progressive sampling algorithm for selecting training examples based on the class associated with each example. An empirical analysis of this algorithm shows that the class distribution of the resulting training set yields classifiers with good (nearly-optimal) classification performance. Wray, R.E. and Laird, J.E. (2003) "An Architectural Approach to Ensuring Consistency in Hierarchical Execution", Volume 19, pages 355-398. For quick access go to Abstract: Hierarchical task decomposition is a method used in many agent systems to organize agent knowledge. This work shows how the combination of a hierarchy and persistent assertions of knowledge can lead to difficulty in maintaining logical consistency in asserted knowledge. We explore the problematic consequences of persistent assumptions in the reasoning process and introduce novel potential solutions. Having implemented one of the possible solutions, Dynamic Hierarchical Justification, its effectiveness is demonstrated with an empirical analysis. Guestrin, C., Koller, D., Parr, R. and Venkataraman, S. (2003) "Efficient Solution Algorithms for Factored MDPs", Volume 19, pages 399-468. For quick access go to Abstract: This paper addresses the problem of planning under uncertainty in large Markov Decision Processes (MDPs). Factored MDPs represent a complex state space using state variables and the transition model using a dynamic Bayesian network. This representation often allows an exponential reduction in the representation size of structured MDPs, but the complexity of exact solution algorithms for such MDPs can grow exponentially in the representation size. In this paper, we present two approximate solution algorithms that exploit structure in factored MDPs. Both use an approximate value function represented as a linear combination of basis functions, where each basis function involves only a small subset of the domain variables. A key contribution of this paper is that it shows how the basic operations of both algorithms can be performed efficiently in closed form, by exploiting both additive and context-specific structure in a factored MDP. A central element of our algorithms is a novel linear program decomposition technique, analogous to variable elimination in Bayesian networks, which reduces an exponentially large LP to a provably equivalent, polynomial-sized one. One algorithm uses approximate linear programming, and the second approximate dynamic programming. Our dynamic programming algorithm is novel in that it uses an approximation based on max-norm, a technique that more directly minimizes the terms that appear in error bounds for approximate MDP algorithms. We provide experimental results on problems with over 10^40 states, demonstrating a promising indication of the scalability of our approach, and compare our algorithm to an existing state-of-the-art approach, showing, in some problems, exponential gains in computation time. Console, L., Picardi, C. and Theseider Dupré, D. (2003) "Temporal Decision Trees: Model-based Diagnosis of Dynamic Systems On-Board", Volume 19, pages 469-512. For quick access go to Abstract: The automatic generation of decision trees based on off-line reasoning on models of a domain is a reasonable compromise between the advantages of using a model-based approach in technical domains and the constraints imposed by embedded applications. In this paper we extend the approach to deal with temporal information. We introduce a notion of temporal decision tree, which is designed to make use of relevant information as long as it is acquired, and we present an algorithm for compiling such trees from a model-based reasoning system. Walsh, W.E. and Wellman, M.P. (2003) "Decentralized Supply Chain Formation: A Market Protocol and Competitive Equilibrium Analysis", Volume 19, pages 513-567. For quick access go to Abstract: Supply chain formation is the process of determining the structure and terms of exchange relationships to enable a multilevel, multiagent production activity. We present a simple model of supply chains, highlighting two characteristic features: hierarchical subtask decomposition, and resource contention. To decentralize the formation process, we introduce a market price system over the resources produced along the chain. In a competitive equilibrium for this system, agents choose locally optimal allocations with respect to prices, and outcomes are optimal overall. To determine prices, we define a market protocol based on distributed, progressive auctions, and myopic, non-strategic agent bidding policies. In the presence of resource contention, this protocol produces better solutions than the greedy protocols common in the artificial intelligence and multiagent systems literature. The protocol often converges to high-value supply chains, and when competitive equilibria exist, typically to approximate competitive equilibria. However, complementarities in agent production technologies can cause the protocol to wastefully allocate inputs to agents that do not produce their outputs. A subsequent decommitment phase recovers a significant fraction of the lost surplus. Price, B. and Boutilier, C. (2003) "Accelerating Reinforcement Learning through Implicit Imitation", Volume 19, pages 569-629. For quick access go to Abstract: Imitation can be viewed as a means of enhancing learning in multiagent environments. It augments an agent's ability to learn useful behaviors by making intelligent use of the knowledge implicit in behaviors demonstrated by cooperative teachers or other more experienced agents. We propose and study a formal model of implicit imitation that can accelerate reinforcement learning dramatically in certain cases. Roughly, by observing a mentor, a reinforcement-learning agent can extract information about its own capabilities in, and the relative value of, unvisited parts of the state space. We study two specific instantiations of this model, one in which the learning agent and the mentor have identical abilities, and one designed to deal with agents and mentors with different action sets. We illustrate the benefits of implicit imitation by integrating it with prioritized sweeping, and demonstrating improved performance and convergence through observation of single and multiple mentors. Though we make some stringent assumptions regarding observability and possible interactions, we briefly comment on extensions of the model that relax these restricitions. Sanchez, R. and Kambhampati, S. (2003) "AltAltp: Online Parallelization of Plans with Heuristic State Search", Volume 19, pages 631-657. For quick access go to Abstract: Despite their near dominance, heuristic state search planners still lag behind disjunctive planners in the generation of parallel plans in classical planning. The reason is that directly searching for parallel solutions in state space planners would require the planners to branch on all possible subsets of parallel actions, thus increasing the branching factor exponentially. We present a variant of our heuristic state search planner AltAlt, called AltAltp which generates parallel plans by using greedy online parallelization of partial plans. The greedy approach is significantly informed by the use of novel distance heuristics that AltAltp derives from a graphplan-style planning graph for the problem. While this approach is not guaranteed to provide optimal parallel plans, empirical results show that AltAltp is capable of generating good quality parallel plans at a fraction of the cost incurred by the disjunctive planners. ---------------------------------------------------------------- II. INSTRUCTIONS FOR OBTAINING ARTICLES When an article is published in JAIR, it is immediately available from our distribution sites. The article is also immediately announced and posted on the USENET newsgroups comp.ai.jair.announce and comp.ai.jair.papers. Periodically, we send out announcements like this to our mailing list announcing recent papers, for those of you who do not read the JAIR newsgroups. (Note that if you read the JAIR newsgroups, you have the advantage of immediately being notified about new papers.) To obtain an article, there are a variety of access methods: -- WWW: You can access our server through the web. The URL is: http://www.jair.org/ -- Anonymous FTP from the site below: CMU Machine: ftp.cs.cmu.edu directory: project/jair -- Newsgroups: read comp.ai.jair.announce and comp.ai.jair.papers To Remove Yourself from this Mailing List To remove yourself from the JAIR subscribers mailing list, visit our Web site (http://www.jair.org/), follow the link "notify me of new articles", enter your email address in the form at the bottom of the page, and follow the directions. In the event that you've already deleted yourself from the list and we keep sending you messages like this one, send mail to jair-ed@isi.edu.