Recent enhancements to greedy best-first search (GBFS) such as DBFS, -GBFS, Type-GBFS improve performance by occasionally introducing exploratory behavior which occasionally expands non-greedy nodes. However, most of these exploratory mechanisms do not address exploration within the space sharing the same heuristic estimate (plateau). In this paper, we show these two modes of exploration, which work across (inter-) and within (intra-) plateau, are complementary, and can be combined to yield superior performance. We then introduces a new fractal-inspired scheme called Invasion-Percolation diversification, which addresses “breadth”-bias instead of the “depth”-bias addressed by the existing diversification methods. We evaluate IP-diversification for both intra- and inter-plateau exploration, and show that it significantly improves performance in several domains. Finally, we show that combining diversification methods results in a planner which is competitive to the state-of-the-art for satisficing planning.

Axioms can be used to model derived predicates in domain-independent planning models. Formulating models which use axioms can sometimes result in problems with much smaller search spaces than the original model. We propose a method for automatically extracting a particular class of axioms from standard STRIPS PDDL models. More specifically, we identify operators whose effects become irrelevant given some other operator, and generate axioms that capture this relationship. We show that this algorithm can be used to successfully extract axioms from standard IPC benchmark instances, and show that the extracted axioms can be used to significantly improve the performance of satisficing planners.

Recent enhancements to greedy best-first search (GBFS) improve performance by occasionally adopting a non-greedy node expansion policy, resulting in more exploratory behavior. However, previous exploratory mechanisms do not address exploration within the space sharing the same heuristic estimate (plateau) and the search bias in a breadth direction. In this abstract, we briefly describe two modes of exploration (diversification), which work inter-(across) and intra-(within) plateau, and also introduce IP-diversification, a method combining Minimum Spanning Tree and randomization, which addresses “breadth”-bias instead of the “depth”-bias addressed by the existing methods.

Axioms can be used to model derived predicates in domain-independent planning models. Formulating models which use axioms can sometimes result in problems with much smaller search spaces than the original model. We propose a method for automatically extracting a particular class of axioms from standard STRIPS PDDL models. More specifically, we identify operators whose effects become irrelevant given some other operator, and generate axioms that capture this relationship. We show that this algorithm can be used to successfully extract axioms from standard IPC benchmark instances, and show that the extracted axioms can be used to significantly improve the performance of an IP-based planner.

Black-box domains where the successor states generated by applying an action are generated by a completely opaque simulator pose a challenge for domain-independent planning. The main computational bottleneck in search-based planning for such domains is the number of calls to the black-box simulation. We propose a method for significantly reducing the number of calls to the simulator by the search algorithm by detecting and pruning sequences of actions which are dominated by others. We apply our pruning method to Iterated Width and breadth-first search in domain-independent black-box planning for Atari 2600 games in the Arcade Learning Environment (ALE), adding our pruning method significantly improves upon the baseline algorithms.

Black-box domains where the successor states generated by applying an action are generated by a completely opaque simulator pose a challenge for domain-independent planning. The main computational bottleneck in search-based planning for such domains is the number of calls to the black-box simulation. We propose a method for significantly reducing the number of calls to the simulator by the search algorithm by detecting and pruning sequences of actions which are dominated by others. We apply our pruning method to Iterated Width and breadth-first search in domain-independent black-box planning for Atari 2600 games, adding our pruning method significantly improves upon the baseline algorithms.

Best-first search algorithms such as A* need to apply tie-breaking strategies in order to decide which node to expand when multiple search nodes have the same evaluation score. We investigate and improve tie-breaking strategies for cost-optimal search using A*. We first experimentally analyze the performance of common tie-breaking strategies that break ties according to the heuristic value of the nodes. We find that the tie-breaking strategy has a significant impact on search algorithm performance when there are 0-cost operators that induce large plateau regions in the search space. Based on this, we develop two new classes of tie-breaking strategies. We first propose a depth diversification strategy which breaks ties according to the distance from the entrance to the plateau, and then show that this new strategy significantly outperforms standard strategies on domains with 0-cost actions. Next, we propose a new framework for interpreting A* search as a series of satisficing searches within plateaus consisting of nodes with the same f-cost. Based on this framework, we investigate a second, new class of tie-breaking strategy, a multi-heuristic tie-breaking strategy which embeds inadmissible, distance-to-go variations of various heuristics within an admissible search. This is shown to further improve the performance in combination with the depth metric.

Hash Distributed A* (HDA*) is an efficient parallel best first algorithm that asynchronously distributes work among the processes using a global hash function. Although Zobrist hashing, the standard hash function used by HDA*, achieves good load balance for many domains, it incurs significant communication overhead since it requires many node transfers among threads. We propose Abstract Zobrist hashing, a new work distribution method for parallel search which reduces node transfers and mitigates communication overhead by using feature projection functions. We evaluate Abstract Zobrist hashing for multicore HDA*, and show that it significantly outperforms previous work distribution methods.

Despite recent improvements in search techniques for cost-optimal classical planning, the exponential growth of the size of the search frontier in A* is unavoidable. We investigate tiebreaking strategies for A*, experimentally analyzing the performance of standard tiebreaking strategies that break ties according to the heuristic value of the nodes. We find that tiebreaking has a significant impact on search algorithm performance when there are zero-cost operators that induce large plateau regions in the search space. We develop a new framework for tiebreaking based on a depth metric which measures distance from the entrance to the plateau, and propose a new, randomized strategy which significantly outperforms standard strategies on domains with zero-cost actions.

In order for robots to interact with humans in the world around them, it is important that they are not just aware of the presence of people, but also able to understand what those people are doing. In particular, interaction involves multiple agents which requires some form of coordination, and this cannot be achieved by acting blindly. The field of plan recognition (PR) studies methods for identifying an observed agent’s task or goal given her action sequence. This is often regarded as the inverse of planning which, given a set of goal conditions, aims to derive a sequence of actions that will achieve the goals when performed from a given initial state. Ram´ırez and Geffner (2009; 2010) proposed a simple transformation of PR problems into classical planning problems for which off-the-shelf software is available for quick and efficient implementations. However, there is a reliance on the observed agent’s optimality which makes this PR technique most useful as a post-processing step when some of the final actions are observed. In human-robot interaction (HRI), it is usually too late to interact once the humans are finished performing their tasks. In this paper, we describe ongoing work two extensions to make classical planning-based PR more applicable to the field of HRI. First, we introduce a modification to their algorithm that reduces the optimality bias’s effect so that long-term goals may be recognized at earlier observations. This is then followed by methods for extracting information from these predictions so that the observing agent may run a second pass of the planner to determine its own actions to perform for a fully interactive system.