AAAI Conferences


Rewriting Constraint Models with Metamodels

AAAI Conferences

An important challenge in constraint programming is to rewrite constraint models into executable programs calculating the solutions. This phase of constraint processing may require translations between constraint programming languages, transformations of constraint representations, model optimizations, and tuning of solving strategies. In this paper, we introduce a pivot metamodel describing the common features of constraint models including different kinds of constraints, statements like conditionals and loops, and other first-class elements like object classes and predicates. This metamodel is general enough to cope with the constructions of many languages, from object-oriented modeling languages to logic languages, but it is independent from them. The rewriting operations manipulate metamodel instances apart from languages. As a consequence, the rewriting operations apply whatever languages are selected and they are able to manage model semantic information. A bridge is created between the metamodel space and languages using parsing techniques. Tools from the software engineering world can be useful to implement this framework.


Simultaneously Searching with Multiple Settings: An Alternative to Parameter Tuning for Suboptimal Single-Agent Search Algorithms

AAAI Conferences

When constructing a suboptimal single-agent search system, there are a number of decisions to be made that can significantly affect search efficiency. Each of these design decisions -- including the selection of an algorithm, a heuristic function, parameter values, etc. -- can greatly impact search speed. Following the work of others (Hutter, Hoos, and Stützle 2007) we refer to the set of choices made for an algorithm as the algorithm's configuration. In practice, configurations are tested offline so as to find some single setting to be used in any future search. Unfortunately, tuning is an expensive process that is specific to each problem domain.


Humboldt-Universität zu Berlin Institut für Informatik 10099 Berlin, Germany moldenha@informatik.hu-berlin.de

AAAI Conferences

We introduce a new bidirectional search algorithm, Single-Frontier Bidirectional Search (SFBDS). Unlike traditional BDS which keeps two frontiers, SFBDS uses a single frontier. At a particular node we can decide to search from start to goal or from goal to start, choosing the direction with the highest potential for minimizing the total work done. We provide theoretical analysis that explains when SFBDS will work validated by experimental results.


The Logic of Benchmarking: A Case Against State-of-the-Art Performance

AAAI Conferences

First, it is better to test on small benchmark instances than to solve the largest possible ones. This eases replication and allows a more diverse set of instances to be tested. There are few conclusions that one can draw from running on large benchmarks that can't also be drawn from running on small benchmarks. Second, experimental evaluation should focus on understanding algorithm behavior and forming predictive models, rather than on achieving state-of-the-art performance on toy problems. Third, it is more important to develop search techniques that are robust across multiple domains than ones that only give state-of-the-art performance in a single domain. Robust techniques are more likely be useful to others.


William Cushing and J. Benton and Subbarao Kambhampati

AAAI Conferences

Planning research has returned to the issue of optimizing costs (rather than sizes) of plans. A prevalent perception, at least among non-experts in search, is that graph search for optimizing the size of paths generalizes more or less trivially to optimizing the cost of paths. While this kind of generalization is usually straightforward for graph theorems, graph algorithms are a different story. In particular, implementing a search evaluation function by substituting cost for size is a Bad Idea. Though experts have stated as much, cutting-edge practitioners are still learning of the consequences the hard way; here we mount a forceful indictment on the inherent dangers of cost-based search.


A Comparison of Greedy Search Algorithms

AAAI Conferences

We discuss the relationships between three approaches to greedy heuristic search: best-first, hill-climbing, and beam search. We consider the design decisions within each family and point out their oft-overlooked similarities.


Edge Partitioning in Parallel Structured Duplicate Detection

AAAI Conferences

Heuristic-search planners that use A* and related graph search algorithms must be parallelized to harness advances in computing power that are based on increasing use of multi-core processors. Although a graph can always be converted to an equivalent tree that can be easily searched in parallel, such a conversion increases the size of the search space exponentially, and the resulting overhead is hard to justify in the context of parallel search for which the speedup ratio is bounded by the number of parallel processes, a polynomial resource in most practical settings. A more direct approach to parallelizing graph search is needed. The challenge in parallelizing graph search is duplicate detection, which requires checking newly generated nodes against the set of already visited nodes. If performed naively, duplicate detection may require excessive synchronization among concurrent search processes (e.g., to maintain the open and closed lists of A*). Here we show how edge partitioning, a technique that was developed originally for reducing the number of time-consuming disk I/O operations in external-memory search, can be used in a parallel setting to reduce the frequency with which search processes need to synchronize with one another, effectively reducing the primary source of overhead in parallel graph search.


Potential Search: A New Greedy Anytime Heuristic Search

AAAI Conferences

In this paper we explore a novel approach for anytime heuristic search, in which the node that is most probable to improve the incumbent solution is expanded first. This is especially suited for the "anytime aspect" of anytime algorithms - the possibility that the algorithm will be be halted anytime throughout the search. The potential of a node to improve the incumbent solution is estimated by a custom cost function, resulting in Potential Search, an anytime best-first search. Experimental results on the 15-puzzle and on the key player problem in communication networks (KPP-COM) show that this approach is competitive with state-of-the-art anytime heuristic search algorithms, and is more robust.


Adding Diversity to Classical Heuristic Planning

AAAI Conferences

State spaces in classical planning domains are usually quite large and can easily be extended to larger unmanageable sizes that do often exceed the capacity of many solvers. In this context, heuristic planning provides a powerful mean for solving rather difficult instances. However, it has been empirically observed that the performance significantly drops in the most difficult domains where the heuristic function induces large plateaus or unrecognized dead-ends. Therefore, a large effort has been invested in improving heuristic functions while only a few contributions have been made to the selection of the search algorithm. Thus, we review the choice of the search algorithm and show that some improvements are still feasible for various kinds of domains, especially the harder ones. In order to do so, we add diversity to the heuristic search in the hope that severe plateaus and/or dead-ends will be avoided or that shorter plans will be found. Also, with the aim of making the reporting of results more clear, a technique based on cumulative distribution functions is advocated.


Peter Kissmann and Stefan Edelkamp

AAAI Conferences

In this paper we propose a new algorithm for solving general two-player turn-taking games that performs symbolic search utilizing binary decision diagrams (BDDs). It consists of two stages: First, it determines all breadth-first search (BFS) layers using forward search and omitting duplicate detection, next, the solving process operates in backward direction only within these BFS layers thereby partitioning all BDDs according to the layers the states reside in. We provide experimental results for selected games and compare to a previous approach. This comparison shows that in most cases the new algorithm outperforms the existing one in terms of runtime and used memory so that it can solve games that could not be solved before with a general approach.