Robert S. (Bob) Engelmore, who retired in 1998 He When the HPP's goal shifted to studying information Allan Terry's of Technology (later Carnegie Mellon University) Ph.D. dissertation and several publications and became a physics major. He had close grew out of this work. Working with crystallographers friendships with (later-to-be AI scientists) Professor Joseph Kraut and Dr. Steve Robert Lindsay and Ed Feigenbaum and Freer from the University of California at San roomed with Feigenbaum for six years of undergraduate Diego, Bob and Allan designed and implemented and graduate school. It graduate work, he met his future wife, Ellie, in was an ambitious project, involving sophisticated Pittsburgh. They were married in 1958.

I'm delighted to bring our readers the news of an exciting resource for AAAI members. AAAI has now completed a major initiative, begun five years ago, to develop a digital library of AAAI publications. The collection now comprises approximately 13,000 papers, including the full set of papers from the AAAI proceedings, papers from other major conferences, AAAI workshop and symposium technical reports, selected AAAI Press books, and the full contents of AI Magazine. This already-extensive collection is a growing resource, with new publications and access methods to be added over time. I encourage readers to visit it at the members' library section of the AAAI web site, www.aaai.org.

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.

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.

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.

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.

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.

We hope by sending a message to majordomo@aaai.org AAAI regular members in the body of the message: subscribe can view and browse tables of aaai-members. Acapulco is the largest and most AAAI events and deadlines. They may also view, print, at www.aaai.org/AITopics/aitopics. stunning beaches, exuberant natural and/or download excerpts of reasonable html. Participation in this Registration information for the America, since its functional, modern experimental program is included in Eighteenth International Joint Conference infrastructure has had very little impact your normal AAAI membership dues.

In the span of a few months, the AI community lost four important figures. The fall of 2002 marked the passing of Ray Reiter, for whom a memorial article by Jack Minker appears in this issue. As the issue was going to press, AI lost Saul Amarel, Norm Nielsen, and Charles Rosen. This section of AI Magazine commemorates these friends, leaders, and AI pioneers. We thank Tom Mitchell and Casimir Kulikowski for their memorial to Saul Amarel, Ray Perrault for his remembrance of Norm Nielsen, and Peter Hart and Nils Nilsson for their tribute to Charles Rosen. The AI community mourns our lost colleagues and gratefully remembers their contributions, which meant so much to so many and to the advancement of artificial intelligence as a whole.

This eclectic keepsake provides a sampling of what can be found (with links to the full articles) on the AI Topics web site. Please keep in mind that (1) the mere mention of anything here does not imply any endorsement whatsoever; (2) the excerpt might not reflect the overall tenor of the article; (3) although the articles were initially available online and without charge, few things that good last forever; and (4) the AI in the News collection -- updated, hyperlinked, and archived -- can be found by going to www.aaai.org/aitopics/ html/current.php.