A conservative estimate of the latter number is the number of distinct board Using efficient methods that reduce the search states in which the board is at most half full. This estimate space, we design an algorithm strong enough to includes some invalid states: those in which one player already solve all 8 8 Hex openings.

In Bayesian networks, a most probable explanation (MPE) is a most likely instantiation of all network variables given a piece of evidence. Solving (the decision version of) an MPE query is NP-hard. Recent work proposed a branch-and-bound search algorithm that finds exact solutions to MPE queries, where bounds are computed on a relaxed network obtained by a technique known as node splitting. In this work we study the impact of variable and value ordering on such a search algorithm. We study several heuristics based on the entropies of variables and on the notion of  nogoods, and propose a new meta-heuristic that combines their strengths. Experiments indicate that search efficiency is significantly improved, allowing many hard problems to be solved for the first time.

This paper considers the problem of composing or scheduling several (non-deterministic) behaviors so as to conform to a specified target behavior as well as satisfying constraints imposed by the environment in which the behaviors are to be performed. This problem has already been considered by several works in the literature and applied to areas such as web service composition, the composition of robot behaviors and co-ordination of distributed devices. We develop a sound and complete algorithm for determining such a composition which has a number of significant advantages over previous proposals: a) our algorithm is different from previous proposals which resort to dynamic logic or simulation relations, b) we realized an implementation in Java as opposed to other approaches for which there are no known implementations, c) our algorithm determines all possible schedulers at once, and d) we can use our framework to define a notion of approximation when the target behavior cannot be realized.

Commonsense reasoning, in particular qualitative spatial and temporal reasoning (QSTR), provides flexible and intuitive methods for reasoning about vague and uncertain information including spatial orientation, topology and proximity.  Despite a number of theoretical advances in QSTR, there are relatively few applications that employ these methods.  The central problem is a significant lack of application level standards and validation methods for supporting developers in adapting and integrating QSTR with their domain specific qualitative spatial and temporal models.  To address this we present a significantly novel methodology for QSTR application validation, inspired by research in software engineering.  In this paper we focus on unit testing, and adapt the software engineering strategy of defining boundary cases.  We present two critical boundary concepts, a methodology for isolating the units under testing from other parts of the model, and methods to assist the designer in integrating our critical boundary unit testing approach with a broader validation plan.

Ontology mapping plays an important role in interoperability over ontologies. Many researchers have proposed algorithms and tools for (semi-)automatically mapping one concept to another concept. Among them, WordNet is widely used as the domain knowledge support in the mapping process. To our knowledge, however, most of them only use synonym, hypernym and hyponym relations in WordNet and the actual meanings provided in natural English(as gloss) are often ignored. In this paper, we treat the concepts(c) as English words (w) and propose an ontology mapping technique where we use the meanings of the words as given in Wordnet (in English) for semantic mapping by constructing their parse trees first and simplifying them for computing similarity measures. Our experimental results show that our method performs better in Recall and F1-Measure than many techniques reported in the literature.

This paper presents a tree-to-tree transduction method for sentence compression. Our model is based on synchronous tree substitution grammar, a formalism that allows local distortion of the tree topology and can thus naturally capture structural mismatches. We describe an algorithm for decoding in this framework and show how the model can be trained discriminatively within a large margin framework. Experimental results on sentence compression bring significant improvements over a state-of-the-art model.

Adequate representation of natural language semantics requires access to vast amounts of common sense and domain-specific world knowledge. Prior work in the field was based on purely statistical techniques that did not make use of background knowledge, on limited lexicographic knowledge bases such as WordNet, or on huge manual efforts such as the CYC project. Here we propose a novel method, called Explicit Semantic Analysis (ESA), for fine-grained semantic interpretation of unrestricted natural language texts. Our method represents meaning in a high-dimensional space of concepts derived from Wikipedia, the largest encyclopedia in existence. We explicitly represent the meaning of any text in terms of Wikipedia-based concepts. We evaluate the effectiveness of our method on text categorization and on computing the degree of semantic relatedness between fragments of natural language text. Using ESA results in significant improvements over the previous state of the art in both tasks. Importantly, due to the use of natural concepts, the ESA model is easy to explain to human users.

SPARK'08 was the first edition of a workshop series designed to provide a stable, longterm forum where researchers could discuss Workshop (SPARK) was established to help address this issue. Building on precursory events, SPARK'08 was the first workshop designed Scheduling (ICAPS-08) held in Sydney, Australia, in September 2008. Like its immediate predecessor (the ICAPS'07 Workshop on Moving Planning and Scheduling Systems), the 2008 SPARK workshop was collocated with the International Conference on Automated Planning and Scheduling (ICAPS), a premier forum for research in AI planning and scheduling, and the International Conference on Principles and Practice of Constraint Programming (CP). A handful of outstanding application-oriented papers are presented each year at the ICAPS conference. Time and again, in invited talks and in open microphone discussion sessions such as ICAPS's Festivus (where conference participants air their grievances in an open and entertaining way), researchers have lamented the small number of applications papers accepted at conferences such as ICAPS, CP, and the AAAI Conference on Artificial Intelligence.

In this work, we first show that feature selection methods other than boosting can also be used for training an efficient object detector. In particular, we introduce Greedy Sparse Linear Discriminant Analysis (GSLDA) \cite{Moghaddam2007Fast} for its conceptual simplicity and computational efficiency; and slightly better detection performance is achieved compared with \cite{Viola2004Robust}. Moreover, we propose a new technique, termed Boosted Greedy Sparse Linear Discriminant Analysis (BGSLDA), to efficiently train a detection cascade. BGSLDA exploits the sample re-weighting property of boosting and the class-separability criterion of GSLDA.

One common type of symmetry is when values are symmetric. For example, if we are assigning colours (values) to nodes (variables) in a graph colouring problem then we can uniformly interchange the colours throughout a colouring. For a problem with value symmetries, all symmetric solutions can be eliminated in polynomial time. However, as we show here, both static and dynamic methods to deal with symmetry have computational limitations. With static methods, pruning all symmetric values is NP-hard in general. With dynamic methods, we can take exponential time on problems which static methods solve without search.