Mike Barley

AAAI Conference 2020 Conference Paper

A Unifying View on Individual Bounds and Heuristic Inaccuracies in Bidirectional Search

• Vidal Alcázar
• Pat Riddle
• Mike Barley

In the past few years, new very successful bidirectional heuristic search algorithms have been proposed. Their key novelty is a lower bound on the cost of a solution that includes information from the g values in both directions. Kaindl and Kainz (1997) proposed measuring how inaccurate a heuristic is while expanding nodes in the opposite direction, and using this information to raise the f value of the evaluated nodes. However, this comes with a set of disadvantages and remains yet to be exploited to its full potential. Additionally, Sadhukhan (2013) presented BAE∗, a bidirectional best-first search algorithm based on the accumulated heuristic inaccuracy along a path. However, no complete comparison in regards to other bidirectional algorithms has yet been done, neither theoretical nor empirical. In this paper we define individual bounds within the lower-bound framework and show how both Kaindl and Kainz’s and Sadhukhan’s methods can be generalized thus creating new bounds. This overcomes previous shortcomings and allows newer algorithms to benefit from these techniques as well. Experimental results show a substantial improvement, up to an order of magnitude in the number of necessarily-expanded nodes compared to state-ofthe-art near-optimal algorithms in common benchmarks.

SoCS Conference 2019 Conference Paper

A Theoretical Comparison of the Bounds of MM, NBS, and GBFHS

• Vidal Alcázar
• Mike Barley
• Patricia J. Riddle

Recent work in bidirectional front-to-end heuristic search has led to the development of novel algorithms that have advanced the state of the art after many years without major developments. In particular, three different algorithms with very different behavior have been proposed: MM, NBS and GBFHS. In this paper we perform a theoretical comparison of these algorithms, defining lower and upper bounds for each of them and analyzing why a given algorithm displays beneficial characteristics that the others lack. With this information, we propose a simple and intuitive near-optimal algorithm to be used as a baseline for comparison in bidirectional front-to-end heuristic search.

SoCS Conference 2018 Conference Paper

GBFHS: A Generalized Breadth-First Heuristic Search Algorithm

• Mike Barley
• Patricia J. Riddle
• Carlos Linares López
• Sean Dobson
• Ira Pohl

Recently there has been renewed interest in bidirectional heuristic search. New algorithms, e. g. , MM, MMe, and NBS, have been introduced which seem much closer to refuting the accepted wisdom that "any front-to-end bidirectional heuristic search algorithm will likely be dominated by unidirectional heuristic search or bidirectional brute-force search". However, MM and MMe can still be dominated by their bidirectional brute-force versions, i. e. , they can show a "hump-in-the-middle". We introduce a novel general breadth-first heuristic search algorithm, GBFHS, that unifies both unidirectional and bidirectional search into a single algorithm. It uses knowledge of the edge cost in unit cost domains to stop on first-collision in unidirectional search and in bidirectional search, unlike MM, MMe, and NBS. With no heuristic it expands fewer nodes bidirectionally than Nicholson

IJCAI Conference 2017 Conference Paper

On Creating Complementary Pattern Databases

• Santiago Franco
• Álvaro Torralba
• Levi H. S. Lelis
• Mike Barley

A pattern database (PDB) for a planning task is a heuristic function in the form of a lookup table that contains optimal solution costs of a simplified version of the task. In this paper we introduce a method that sequentially creates multiple PDBs which are later combined into a single heuristic function. At a given iteration, our method uses estimates of the A* running time to create a PDB that complements the strengths of the PDBs created in previous iterations. We evaluate our algorithm using explicit and symbolic PDBs. Our results show that the heuristics produced by our approach are able to outperform existing schemes, and that our method is able to create PDBs that complement the strengths of other existing heuristics such as a symbolic perimeter heuristic.

IJCAI Conference 2016 Conference Paper

Heuristic Subset Selection in Classical Planning

• Levi H. S. Lelis
• Santiago Franco
• Marvin Abisrror
• Mike Barley
• Sandra Zilles
• Robert C. Holte

In this paper we present greedy methods for selecting a subset of heuristic functions for guiding A* search. Our methods are able to optimize various objective functions while selecting a subset from a pool of up to thousands of heuristics. Specifically, our methods minimize approximations of A*'s search tree size, and approximations of A*'s running time. We show empirically that our methods can outperform state-of-the-art planners for deterministic optimal planning.

SoCS Conference 2015 Conference Paper

Automated Transformation of PDDL Representations

• Patricia J. Riddle
• Mike Barley
• Santiago Franco
• Jordan Douglas

This paper describes a system that automatically transforms a PDDL encoding, calls a planner to solve the transformed representation, and translates the solution back into the original representation. The approach involves counting objects that are indistinguishable, rather than treating them as individuals, which eliminates some unnecessary combinatorial explosion.

ICAPS Conference 2014 Conference Paper

Overcoming the Utility Problem in Heuristic Generation: Why Time Matters

• Mike Barley
• Santiago Franco
• Patricia J. Riddle

Progress has been made recently in developing tech- niques to automatically generate effective heuristics. These techniques typically aim to reduce the size of the search tree, usually by combining more primitive heuristics. However, simply reducing search tree size is not enough to guarantee that problems will be solved more quickly. We describe a new approach to auto- matic heuristic generation that combines more primi- tive heuristics in a way that can produce better heuris- tics than current methods. We report on experiments us- ing 14 planning domains that show our system leads to a much greater reduction in search time than previous methods. In closing, we discuss avenues for extending this promising approach to combining heuristics.

AAAI Conference 2014 Conference Paper

Social Planning: Achieving Goals by Altering Others’ Mental States

• Chris Pearce
• Ben Meadows
• Pat Langley
• Mike Barley

In this paper, we discuss a computational approach to the cognitive task of social planning. First, we specify a class of planning problems that involve an agent who attempts to achieve its goals by altering other agents’ mental states. Next, we describe SFPS, a flexible problem solver that generates social plans of this sort, including ones that include deception and reasoning about other agents’ beliefs. We report the results for experiments on social scenarios that involve different levels of sophistication and that demonstrate both SFPS’s capabilities and the sources of its power. Finally, we discuss how our approach to social planning has been informed by earlier work in the area and propose directions for additional research on the topic.

ICML Conference 2002 Conference Paper

A Unified Decomposition of Ensemble Loss for Predicting Ensemble Performance

• Michael Goebel
• Patricia J. Riddle
• Mike Barley