Author name cluster

Alex Fukunaga

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

18 papers

1 author row

AAAI Conference 2025 Conference Paper

Parallel Greedy Best-First Search with a Bound on Expansions Relative to Sequential Search

Takumi Shimoda
Alex Fukunaga

Parallelization of non-admissible search algorithms such as GBFS poses a challenge because straightforward parallelization can result in search behavior which significantly deviates from sequential search. Previous work proposed PUHF, a parallel search algorithm which is constrained to only expand states that can be expanded by some tie-breaking strategy for GBFS. We show that despite this constraint, the number of states expanded by PUHF is not bounded by a constant multiple of the number of states expanded by sequential GBFS with the worst-case tie-breaking strategy. We propose and experimentally evaluate One Bench At a Time (OBAT), a parallel greedy search which guarantees that the number of states expanded is within a constant factor of the number of states expanded by sequential GBFS with some tie-breaking policy.

PDF Details DOI

AAMAS Conference 2024 Conference Paper

On the Transit Obfuscation Problem

Hideaki Takahashi
Alex Fukunaga

Concealing an intermediate point on a route or visible from a route is an important goal in some transportation and surveillance scenarios. This paper studies the Transit Obfuscation Problem, the problem of traveling from some start location to an end location while "covering" a specific transit point that needs to be concealed from adversaries. We propose the notion of transit anonymity, a quantitative guarantee of the anonymity of a specific transit point, even with a powerful adversary with full knowledge of the path planning algorithm. We propose and evaluate planning/search algorithms that satisfy this anonymity criterion.

PDF

JAIR Journal 2022 Journal Article

Classical Planning in Deep Latent Space

Masataro Asai
Hiroshi Kajino
Alex Fukunaga
Christian Muise

PDF Details DOI

IJCAI Conference 2020 Conference Paper

Front-to-Front Heuristic Search for Satisficing Classical Planning

Ryo Kuroiwa
Alex Fukunaga

Although symbolic bidirectional search is successful in optimal classical planning, state-of-the-art satisficing planners do not use bidirectional search. Previous bidirectional search planners for satisficing planning behaved similarly to a trivial portfolio, which independently executes forward and backward search without the desired ``meet-in-the-middle'' behavior of bidirectional search where the forward and backward search frontiers intersect at some point relatively far from the forward and backward start states. In this paper, we propose Top-to-Top Bidirectional Search (TTBS), a new bidirectional search strategy with front-to-front heuristic evaluation. We show that TTBS strongly exhibits ``meet-in-the-middle'' behavior and can solve instances solved by neither forward nor backward search on a number of domains.

PDF Details DOI

AAAI Conference 2018 Conference Paper

Classical Planning in Deep Latent Space: Bridging the Subsymbolic-Symbolic Boundary

Masataro Asai
Alex Fukunaga

Current domain-independent, classical planners require symbolic models of the problem domain and instance as input, resulting in a knowledge acquisition bottleneck. Meanwhile, although deep learning has achieved signiﬁcant success in many ﬁelds, the knowledge is encoded in a subsymbolic representation which is incompatible with symbolic systems such as planners. We propose LatPlan, an unsupervised architecture combining deep learning and classical planning. Given only an unlabeled set of image pairs showing a subset of transitions allowed in the environment (training inputs), and a pair of images representing the initial and the goal states (planning inputs), LatPlan ﬁnds a plan to the goal state in a symbolic latent space and returns a visualized plan execution. The contribution of this paper is twofold: (1) State Autoencoder, which ﬁnds a propositional state representation of the environment using a Variational Autoencoder. It generates a discrete latent vector from the images, based on which a PDDL model can be constructed and then solved by an offthe-shelf planner. (2) Action Autoencoder / Discriminator, a neural architecture which jointly ﬁnds the action symbols and the implicit action models (preconditions/effects), and provides a successor function for the implicit graph search. We evaluate LatPlan using image-based versions of 3 planning domains: 8-puzzle, Towers of Hanoi and LightsOut. Note: The extended manuscript on Arxiv contains all details of Latplan, but please cite this AAAI version. Latplan code is available on Github.

PDF Details

AAAI Conference 2018 Conference Paper

Revisiting Immediate Duplicate Detection in External Memory Search

Shunji Lin
Alex Fukunaga

External memory search algorithms store the open and closed lists in secondary memory (e. g. , hard disks) to augment limited internal memory. To minimize expensive random access in hard disks, these algorithms typically employ delayed duplicate detection (DDD), at the expense of processing more nodes than algorithms using immediate duplicate detection (IDD). Given the recent ubiquity of solid state drives (SSDs), we revisit the use of IDD in external memory search. We propose segmented compression, an improved IDD method that signiﬁcantly reduces the number of false positive access into secondary memory. We show that A*-IDD, an external search variant of A* that uses segmented compression-based IDD, signiﬁcantly improves upon previous open-addressing based IDD. We also show that A*-IDD can outperform DDD-based A* on some domains in domain-independent planning.

PDF Details

AAAI Conference 2017 Short Paper

Automatically Extracting Axioms in Classical Planning

Shuwa Miura
Alex Fukunaga

Axioms can be used to model derived predicates in domainindependent 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 speciﬁcally, 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 signiﬁcantly improve the performance of an IP-based planner.

PDF Details

AAAI Conference 2017 Short Paper

Improving Greedy Best-First Search by Removing Unintended Search Bias (Extended Abstract)

Masataro Asai
Alex Fukunaga

Recent enhancements to greedy best-ﬁrst 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 brieﬂy describe two modes of exploration (diversiﬁcation), which work inter-(across) and intra-(within) plateau, and also introduce IP-diversiﬁcation, a method combining Minimum Spanning Tree and randomization, which addresses “breadth”-bias instead of the “depth”-bias addressed by the existing methods.

PDF Details

AAAI Conference 2017 Short Paper

Learning to Avoid Dominated Action Sequences in Planning for Black-Box Domains

Yuu Jinnai
Alex Fukunaga

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 signiﬁcantly 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-ﬁrst search in domain-independent black-box planning for Atari 2600 games, adding our pruning method signiﬁcantly improves upon the baseline algorithms.

PDF Details

AAAI Conference 2017 Conference Paper

Learning to Prune Dominated Action Sequences in Online Black-Box Planning

Yuu Jinnai
Alex Fukunaga

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 signiﬁcantly 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-ﬁrst search in domain-independent blackbox planning for Atari 2600 games in the Arcade Learning Environment (ALE), adding our pruning method signiﬁcantly improves upon the baseline algorithms.

PDF Details

JAIR Journal 2017 Journal Article

On Hash-Based Work Distribution Methods for Parallel Best-First Search

Yuu Jinnai
Alex Fukunaga

Parallel best-first search algorithms such as Hash Distributed A* (HDA*) distribute work among the processes using a global hash function. We analyze the search and communication overheads of state-of-the-art hash-based parallel best-first search algorithms, and show that although Zobrist hashing, the standard hash function used by HDA*, achieves good load balance for many domains, it incurs significant communication overhead since almost all generated nodes are transferred to a different processor than their parents. We propose Abstract Zobrist hashing, a new work distribution method for parallel search which, instead of computing a hash value based on the raw features of a state, uses a feature projection function to generate a set of abstract features which results in a higher locality, resulting in reduced communications overhead. We show that Abstract Zobrist hashing outperforms previous methods on search domains using hand-coded, domain specific feature projection functions. We then propose GRAZHDA*, a graph-partitioning based approach to automatically generating feature projection functions. GRAZHDA* seeks to approximate the partitioning of the actual search space graph by partitioning the domain transition graph, an abstraction of the state space graph. We show that GRAZHDA* outperforms previous methods on domain-independent planning.

PDF Details DOI

JAIR Journal 2017 Journal Article

Tie-Breaking Strategies for Cost-Optimal Best First Search

Masataro Asai
Alex Fukunaga

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.

PDF Details DOI

AAAI Conference 2016 Conference Paper

Abstract Zobrist Hashing: An Efficient Work Distribution Method for Parallel Best-First Search

Yuu Jinnai
Alex Fukunaga

Hash Distributed A* (HDA*) is an efﬁcient parallel best ﬁrst 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 signiﬁcant 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.

PDF Details

AAAI Conference 2016 Conference Paper

Tiebreaking Strategies for A* Search: How to Explore the Final Frontier

Masataro Asai
Alex Fukunaga

Despite recent improvements in search techniques for costoptimal 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 ﬁnd that tiebreaking has a signiﬁcant 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 signiﬁcantly outperforms standard strategies on domains with zero-cost actions.

PDF Details

JAIR Journal 2015 Journal Article

On a Practical, Integer-Linear Programming Model for Delete-Free Tasks and its Use as a Heuristic for Cost-Optimal Planning

Tatsuya Imai
Alex Fukunaga

We propose a new integer-linear programming model for the delete relaxation in cost-optimal planning. While a straightforward IP for the delete relaxation is impractical, our enhanced model incorporates variable reduction techniques based on landmarks, relevance-based constraints, dominated action elimination, immediate action application, and inverse action constraints, resulting in an IP that can be used to directly solve delete-free planning problems. We show that our IP model is competitive with previous state-of-the-art solvers for delete-free problems. The LP-relaxation of the IP model is often a very good approximation to the IP, providing an approach to approximating the optimal value of the delete-free task that is complementary to the well-known LM-cut heuristic. We also show that constraints that partially consider delete effects can be added to our IP/LP models. We embed the new IP/LP models into a forward-search based planner, and show that the performance of the resulting planner on standard IPC benchmarks is comparable with the state-of-the-art for cost-optimal planning.

PDF Details DOI

AIJ Journal 2013 Journal Article

Evaluation of a simple, scalable, parallel best-first search strategy

Akihiro Kishimoto
Alex Fukunaga
Adi Botea

Large-scale, parallel clusters composed of commodity processors are increasingly available, enabling the use of vast processing capabilities and distributed RAM to solve hard search problems. We investigate Hash-Distributed A⁎ (HDA⁎), a simple approach to parallel best-first search that asynchronously distributes and schedules work among processors based on a hash function of the search state. We use this approach to parallelize the A⁎ algorithm in an optimal sequential version of the Fast Downward planner, as well as a 24-puzzle solver. The scaling behavior of HDA⁎ is evaluated experimentally on a shared memory, multicore machine with 8 cores, a cluster of commodity machines using up to 64 cores, and large-scale high-performance clusters, using up to 2400 processors. We show that this approach scales well, allowing the effective utilization of large amounts of distributed memory to optimally solve problems which require terabytes of RAM. We also compare HDA⁎ to Transposition-table Driven Scheduling (TDS), a hash-based parallelization of IDA⁎, and show that, in planning, HDA⁎ significantly outperforms TDS. A simple hybrid which combines HDA⁎ and TDS to exploit strengths of both algorithms is proposed and evaluated.

Details DOI

AAAI Conference 2012 Conference Paper

Iterative Resource Allocation for Memory Intensive Parallel Search Algorithms on Clouds, Grids, and Shared Clusters

Alex Fukunaga
Akihiro Kishimoto
Adi Botea

The increasing availability of “utility computing” resources such as clouds, grids, and massively parallel shared clusters can provide practically unlimited processing and memory capacity on demand, at some cost per unit of resource usage. This requires a new perspective in the design and evaluation of parallel search algorithms. Previous work in parallel search implicitly assumed ownership of a cluster with a static amount of CPU cores and RAM, and emphasized wallclock runtime. With utility computing resources, trade-offs between performance and monetary costs must be considered. This paper considers dynamically increasing the usage of utility computing resources until a problem is solved. Efficient resource allocation policies are analyzed in comparison with an optimal allocation strategy. We evaluate our iterative allocation strategy by applying it to the HDA* parallel search algorithm. The experimental results validate our theoretical predictions. They show that, in practice, the costs incurred by iterative allocation are reasonably close to an optimal (but a priori unknown) policy, and are significantly better than the worst-case analytical bounds.

PDF Details

AAAI Conference 2002 Conference Paper

Automated Discovery of Composite SAT Variable-Selection Heuristics

Alex Fukunaga

Variants of GSAT and Walksat are among the most successful SAT local search algorithms. We show that several well-known SAT local search algorithms are the result of novel combininations of a set of variable selection primitives. We describe CLASS, an automated heuristic discovery system which generates new, effective variable selection heuristic functions using a simple composition operator. New heuristics discovered by CLASS are shown to be competitive with the best Walksat variants, including Novelty+ and R-Novelty+. We also analyze the local search behavior of the learned heuristics using the depth, mobility, and coverage metrics recently proposed by Schuurmans and Southey.

PDF Details