In this paper we describe the application of a novel learning and problem solving architecture to the domain of airspace management, where multiple requests for the use of airspace need to be reconciled and managed automatically. The key feature of our "Generalized Integrated Learning Architecture" (GILA) is a set of integrated learning and reasoning (ILR) systems coordinated by a central meta-reasoning executive (MRE). Each ILR learns independently from the same training example and contributes to problem-solving in concert with other ILRs as directed by the MRE. Formal evaluations show that our system performs as well as or better than humans after learning from the same training data. Further, GILA outperforms any individual ILR run in isolation, thus demonstrating the power of the ensemble architecture for learning and problem solving.

NASA and the United States Geological Survey (USGS) are collaborating to produce a global map of the Earth using Landsat 5 Thematic Mapper (TM) and Landsat 7 Enhanced Thematic Mapper Plus (ETM) remote sensor data from the period of 2004 through 2007. Constraints and preferences on map quality make it desirable to develop an automated solution to the map generation problem. This paper formulates a Global Map Generator problem as a Constraint Optimization Problem (GMG-COP) and describes an approach to solving it using local search. The paper also describes the integration of a GMG solver into a graphical user interface for visualizing and comparing solutions, thus allowing for solutions to be generated with human participation and guidance.

NASA and the United States Geological Survey (USGS) are collaborating to produce a global map of the Earth using Landsat 5 Thematic Mapper (TM) and Landsat 7 Enhanced Thematic Mapper Plus (ETM+) remote sensor data from the period of 2004 through 2007. The map is comprised of thousands of scene locations and, for each location, there are tens of different images of varying quality to chose from. Constraints and preferences on map quality make it desirable to develop an automated solution to the map generation problem. This paper formulates a Global Map Generator problem as a Constraint Optimization Problem (GMG-COP) and describes an approach to solving it using local search. The paper also describes the integration of a GMG solver into a graphical user interface for visualizing and comparing solutions, thus allowing for solutions to be generated with human participation and guidance.

But this premature paving is not very useful if the searchtree is explored depth-first (DFS) or breadth-first (BFS): DFS When applied to numerical CSPs, the branch and quickly converges to ɛ-boxes that are too close to one another prune algorithm (BPA) computes a sharp covering to be representative of the solution set (see the left part of of the solution set. The BPA is therefore impractical Figure 1); BFS computes a homogeneous paving but finds no when the solution set is large, typically when ɛ-box at all if stopped too early (see the center graphic of Figure it has a dimension larger than four or five which is 1; note that such a sharp paving cannot be computed for often met in underconstrained problems. The purpose larger solution sets, making BFS useless in such cases). of this paper is to present a new search tree The search strategy used in an anytime BPA should quickly exploration strategy for BPA that hybridizes depthfirst find ɛ-boxes that are representative of the solution set: ɛ- and breadth-first searches. This search strategy boxes should be discovered uniformly on a continuous connected allows the BPA discovering potential solutions component in the solution set, while every connected in different areas of the search space in early stages components should be reached by some ɛ-boxes in early of the exploration, hence allowing an anytime usage stages of the search. Two such strategies are introduced in of the BPA. The merits of the proposed search the present paper. The most distant-first strategy (MDFS) strategy are experimentally evaluated.

This can increase the size of the Treewidth is a fundamental property of a graph with significant search exponentially. We explore two techniques implications for several areas of artificial intelligence that prevent this: duplicate detection and duplicate research. A reason for focusing on treewidth is that a natural avoidance. We illustrate these techniques on search space for it uses a maximum edge cost function. As the treewidth problem, a combinatorial optimization we discuss in a later section, in an iterative-deepening search problem with applications to a variety of research on a problem with a maximum edge cost function, every duplicate areas. The bottleneck for previous treewidth node can be discarded. This makes these problems algorithms is a large memory requirement. We develop well-suited for studying duplicate elimination techniques.

In this paper we approach the problem of reasoning with quantified Boolean formulas (QBFs) by combining search and resolution, and by switching between them according to structural properties of QBFs. We provide empirical evidence that QBFs which cannot be solved by search or resolution alone, can be solved by combining them, and that our approach makes a proof-of-concept implementation competitive with current QBF solvers.

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.

The MAP (maximum a posteriori assignment) problem in Bayesian networks is the problem of finding the most probable instantiation of a set of variables given partial evidence for the remaining variables. The state-of-the-art exact solution method is depth-first branch-and-bound search using dynamic variable ordering and a jointree upper bound proposed by Park and Darwiche [2003]. Since almost all search time is spent computing the jointree bounds, we introduce an efficient method for computing these bounds incrementally. We point out that, using a static variable ordering, it is only necessary to compute relevant upper bounds at each search step, and it is also possible to cache potentials of the jointree for efficient backtracking. Since the jointree computation typically produces bounds for joint configurations of groups of variables, our method also instantiates multiple variables at each search step, instead of a single variable, in order to reduce the number of times that upper bounds need to be computed. Experiments show that this approach leads to orders of magnitude reduction in search time.

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 deals with Decision-Making in the context of multiattribute utility theory and, more precisely, with the problem of efficiently determining the best alternative w.r.t. an agent's preferences (choice problem). We assume that alternatives are elements of a product set of attributes and that the agent's preferences are represented by a generalized additive decomposable (GAI) utility on this set. Such a function allows an efficient representation of interactions between attributes while preserving some decomposability of the model. GAI utilities can be compiled into graphical structures called GAI networks that can be exploited to solve choice problems using collect/distribute schemes essentially similar to those used in Bayesian networks. In this paper, rather than directly using this scheme on the GAI network for determining the most preferred alternative, we propose to work with another GAI function, acting as an upper-bound on utility values and enhancing the model's decomposability. This method still provides the exact optimal solution but speeds up significantly the search. It proves to be particularly useful when dealing with choice and ranking under constraints and within collective Decision-Making, where GAI nets tend to have a large size. We present an efficient algorithm for determining this new GAI function and provide experimental results highlighting the practical efficiency of our procedure.