A key challenge in non-cooperative multi-agent systems is that of developing efficient planning algorithms for intelligent agents to interact and perform effectively among boundedly rational, self-interested agents (e.g., humans). The practicality of existing works addressing this challenge is being undermined due to either the restrictive assumptions of the other agents' behavior, the failure in accounting for their rationality, or the prohibitively expensive cost of modeling and predicting their intentions. To boost the practicality of research in this field, we investigate how intention prediction can be efficiently exploited and made practical in planning, thereby leading to efficient intention-aware planning frameworks capable of predicting the intentions of other agents and acting optimally with respect to their predicted intentions. We show that the performance losses incurred by the resulting planning policies are linearly bounded by the error of intention prediction. Empirical evaluations through a series of stochastic games demonstrate that our policies can achieve better and more robust performance than the state-of-the-art algorithms.

The recent proliferation of smart-phones and other wearable devices has lead to a surge of new mobile applications. Partially observable Markov decision processes provide a natural framework to design applications that continuously make decisions based on noisy sensor measurements. However, given the limited battery life, there is a need to minimize the amount of online computation. This can be achieved by compiling a policy into a finite state controller since there is no need for belief monitoring or online search. In this paper, we propose a new branch and bound technique to search for a good controller. In contrast to many existing algorithms for controllers, our search technique is not subject to local optima. We also show how to reduce the amount of search by avoiding the enumeration of isomorphic controllers and by taking advantage of suitable upper and lower bounds. The approach is demonstrated on several benchmark problems as well as a smart-phone application to assist persons with Alzheimer's to wayfind.

Domain-independent optimal planning has seen important breakthroughs in recent years with the development of tractable and informative admissible heuristics, suitable for planners based on forward state-space search. These heuristics allow planners to optimally solve an important number of benchmark problems, including problems that are quite involved and difficult for the layman. In this paper we present a new admissible heuristic that is obtained from the state equation associated to the Petri-net representation of the planning problem. The new heuristic, that does not fall into one of the four standard classes, can be computed in polynomial time and is competitive with the current state of the art for optimal planning, as empirically demonstrated over a large number of problems, mainly because it often shows an improved quality-to-cost ratio. The new heuristic applies to SAS+ planning tasks with arbitrary non-negative action costs.

There are two major uses of abstraction in planning and search: refinement (where abstract solutions are extended into concrete solutions) and heuristics (where abstract solutions are used to compute heuristics for the original search space). These two approaches are usually viewed as unrelated in the literature. It is reasonable to believe, though, that they are related, since they are both intrinsically based on the structure of abstract search spaces. We take the first steps towards formally investigating their relationships, employing our recently introduced framework for analysing and comparing abstraction methods. By adding some mechanisms for expressing metric properties, we can capture concepts like admissibility and consistency of heuristics. We present an extensive study of how such metric properties relate to the properties in the original framework, revealing a number of connections between the refinement and heuristic approaches. This also provides new insights into, for example, Valtorta's theorem and spurious states.

Community question answering (cQA), which providesa platform for people with diverse backgroundto share information and knowledge, hasbecome an increasingly popular research topic. Inthis paper, we focus on the task of question retrieval.The key problem of question retrieval is tomeasure the similarity between the queried questionsand the historical questions which have beensolved by other users. The traditional methodsmeasure the similarity based on the bag-of-words(BOWs) representation. This representation neithercaptures dependencies between related words, norhandles synonyms or polysemous words. In thiswork, we first propose a way to build a conceptthesaurus based on the semantic relations extractedfrom the world knowledge of Wikipedia. Then, wedevelop a unified framework to leverage these semanticrelations in order to enhance the questionsimilarity in the concept space. Experiments conductedon a real cQA data set show that with thehelp of Wikipedia thesaurus, the performance ofquestion retrieval is improved as compared to thetraditional methods.

Discriminative structured prediction models have been widely used in many natural language processing tasks, but it is challenging to apply the methods to semantic parsing. In this paper, by introducing hybrid tree as a latent structure variable to close the gap between the input sentences and output representations, we formulate semantic parsing as a structured prediction problem, based on the latent variable perceptron model incorporated with a tree edit-distance loss as optimization criterion. The proposed approach maintains the advantage of a discriminative model in accommodating flexible combination of features and naturally incorporates an efficient decoding algorithm in learning and inference. Furthermore, in order to enhance the efficiency and accuracy of inference, we design an effective approach based on vector space model to extract a smaller subset of relevant MR productions for test examples. Experimental results on publicly available corpus show that our approach significantly outperforms previous systems.

Heuristic search with reachability-based heuristics is arguably the most successful paradigm in Automated Planning to date. In its earlier stages of development, heuristic search was proposed as both forward and backward search. Due to the disadvantages of backward search, in the last decade researchers focused mainly on forward search, and backward search was abandoned for the most part as a valid alternative. In the last years, important advancements regarding both the theoretical understanding and the performance of heuristic search have been achieved, applied mainly to forward search planners. In this work we revisit regression in planning with reachability-based heuristics, trying to extrapolate to backward search current lines of research that were not as well understood as they are now.

We present partial-tree linearization, a generalized word ordering (i.e. ordering a set of input words into a grammatical and fluent sentence) task for text-to-text applications. Recent studies of word ordering can be categorized into either abstract word ordering (no input syntax except for POS) or tree linearization (input words are associated with a full unordered syntax tree). Partial-tree linearization covers the whole spectrum of input between these two extremes. By allowing POS and dependency relations to be associated with any subset of input words, partial-tree linearization is more practical for a dependency-based NLG pipeline, such as transfer-based MT and abstractive text summarization. In addition, a partial-tree linearizer can also perform abstract word ordering and full-tree linearization. Our system achieves the best published results on standard PTB evaluations of these tasks.

Keyword extraction attracts much attention for its significant role in various natural language processing tasks. While some existing methods for keyword extraction have considered using single type of semantic relatedness between words or inherent attributes of words, almost all of them ignore two important issues: 1) how to fuse multiple types of semantic relations between words into a uniform semantic measurement and automatically learn the weights of the edges between the words in the word graph of each document, and 2) how to integrate the relations between words and words' intrinsic features into a unified model. In this work, we tackle the two issues based on the supervised random walk model. We propose a supervised ranking based method for keyword extraction, which is called SEAFARER. It can not only automatically learn the weights of the edges in the unified graph of each document which includes multiple semantic relations but also combine the merits of semantic relations of edges and intrinsic attributes of nodes together. We conducted extensive experimental study on an established benchmark and the experimental results demonstrate that SEAFARER outperforms the state-of-the-art supervised and unsupervised methods.

Cross lingual entity linking means linking an entity mention in a background source document in one language with the corresponding real world entity in a knowledge base written in the other language. The key problem is to measure the similarity score between the context of the entity mention and the document of the candidate entity. This paper presents a general framework for doing cross lingual entity linking by leveraging a large scale and bilingual knowledge base, Wikipedia. We introduce a bilingual topic model that mining bilingual topic from this knowledge base with the assumption that the same Wikipedia concept documents of two different languages share the same semantic topic distribution. The extracted topics have two types of representation, with each type corresponding to one language. Thus both the context of the entity mention and the document of the candidate entity can be represented in a space using the same semantic topics. We use these topics to do cross lingual entity linking. Experimental results show that the proposed approach can obtain the competitive results compared with the state-of-art approach.