We introduce a stochastic graph-based method for computing relative importance of textual units for Natural Language Processing. We test the technique on the problem of Text Summarization (TS). Extractive TS relies on the concept of sentence salience to identify the most important sentences in a document or set of documents. Salience is typically defined in terms of the presence of particular important words or in terms of similarity to a centroid pseudo-sentence. We consider a new approach, LexRank, for computing sentence importance based on the concept of eigenvector centrality in a graph representation of sentences. In this model, a connectivity matrix based on intra-sentence cosine similarity is used as the adjacency matrix of the graph representation of sentences. Our system, based on LexRank ranked in first place in more than one task in the recent DUC 2004 evaluation. In this paper we present a detailed analysis of our approach and apply it to a larger data set including data from earlier DUC evaluations. We discuss several methods to compute centrality using the similarity graph. The results show that degree-based methods (including LexRank) outperform both centroid-based methods and other systems participating in DUC in most of the cases. Furthermore, the LexRank with threshold method outperforms the other degree-based techniques including continuous LexRank. We also show that our approach is quite insensitive to the noise in the data that may result from an imperfect topical clustering of documents.

Multiagent learning is a necessary yet challenging problem as multiagent systems become more prevalent and environments become more dynamic. Much of the groundbreaking work in this area draws on notable results from game theory, in particular, the concept of Nash equilibria. Learners that directly learn an equilibrium obviously rely on their existence. Learners that instead seek to play optimally with respect to the other players also depend upon equilibria since equilibria are fixed points for learning. From another perspective, agents with limitations are real and common. These may be undesired physical limitations as well as self-imposed rational limitations, such as abstraction and approximation techniques, used to make learning tractable. This article explores the interactions of these two important concepts: equilibria and limitations in learning. We introduce the question of whether equilibria continue to exist when agents have limitations. We look at the general effects limitations can have on agent behavior, and define a natural extension of equilibria that accounts for these limitations. Using this formalization, we make three major contributions: (i) a counterexample for the general existence of equilibria with limitations, (ii) sufficient conditions on limitations that preserve their existence, (iii) three general classes of games and limitations that satisfy these conditions. We then present empirical results from a specific multiagent learning algorithm applied to a specific instance of limited agents. These results demonstrate that learning with limitations is feasible, when the conditions outlined by our theoretical analysis hold.

The difficulty in solving optimally such problems arises when the agents lack full observability of the global state of the system when they operate. The general problem has been shown to be NEXP-complete. In this paper, we identify classes of decentralized control problems whose complexity ranges between NEXP and P. In particular, we study problems characterized by independent transitions, independent observations, and goal-oriented objective functions. Two algorithms are shown to solve optimally useful classes of goal-oriented decentralized processes in polynomial time. This paper also studies information sharing among the decision-makers, which can improve their performance. We distinguish between three ways in which agents can exchange information: indirect communication, direct communication and sharing state features that are not controlled by the agents. Our analysis shows that for every class of problems we consider, introducing direct or indirect communication does not change the worst-case complexity. The results provide a better understanding of the complexity of decentralized control problems that arise in practice and facilitate the development of planning algorithms for these problems.

Trends in Intelligent Information Knowledge Based Computer Systems. The 18th International FLAIRS Conference seeks high quality, original, Larry Holder, University of Texas at Arlington unpublished submissions in all areas of AI, including, but not limited to, holder@cse.uta.edu The FLAIRS conference offers a set of special tracks, and authors are encouraged to submit papers to a relevant track.

This eclectic keepsake provides a sampling was initially inspired by science fiction, "[iRobot Chairman Helen] Greiner believes'One of what can be found (with links to the full the movie may influence a new generation She said the R2D2 robot's humanlike She went on to the articles were initially available inventions were predicted by those sort of MIT where she earned undergraduate and online and without charge, few things that writers. In terms of the capabilities that graduate degrees in mechanical engineering, good last forever; and (4) the AI in the News we get in modern computers, they could electrical engineering and computer collection--updated, hyperlinked, and see some of that. What I find so interesting science. 'It takes all three (disciplines) and archived--can be found by going to is that we start with these ideas which they must all come together in robotics,' www.aaai.org/aitopics/html/current.html. June 10, "In the war on terror, University about robots programmed to think on Breazeal of the Massachusetts Institute of professor Robin Murphy finds herself a New Jersey.

Committee is listed in the sidebar.

Sketch maps are an important spatial representation used in many geospatial-reasoning tasks. This article describes techniques we have developed that enable software to perform humanlike reasoning about sketch maps. We illustrate the utility of these techniques in the context of nuSketch Battlespace, a research system that has been successfully used in a variety of experiments. After an overview of the nuSketch approach and nuSketch Battlespace, we outline the representations of glyphs and sketches and the nuSketch spatial reasoning architecture. We describe the use of qualitative topology and Voronoi diagrams to construct spatial representations, and explain how these facilities are combined with analogical reasoning to provide a simple form of enemy intent hypothesis generation.

We are pleased to publish this special selection of papers from the 2003 Innovative Applications of Artificial Intelligence Conference (IAAI-03). IAAI seeks out applications of artificial intelligence that either demonstrate new technology or use previously known technology in innovative ways. IAAI particularly seeks out examples of deployments of AI technology that tackle the problems of demonstrating value and planning for long-term deployment. The five articles we have selected for this special issue are extended versions of papers that appeared in the conference. Two of the articles are deployed applications that have already demonstrated practical value. The remaining three articles are particularly innovative emerging applications. We will briefly outline each of them.

The 2003International Conference on Automated Planning and Scheduling (ICAPS-03) was held 9 to 13 June 2003 in Trento, Italy. It was chaired by Enrico Giunchiglia (University of Genova), Nicola Muscettola (NASA Ames), and Dana Nau (University of Maryland). Piergiorgio Bertoli and Marco Benedetti (both from ITC-IRST) were the local chair and the workshop-tutorial coordination chair, respectively.