Nathan R. Sturtevant

AAAI Conference 2026 Conference Paper

A Parallel CPU-GPU Framework for Batching Heuristic Operations in Depth-First Heuristic Search

• Ehsan Futuhi
• Nathan R. Sturtevant

The rapid advancement of GPU technology has unlocked powerful parallel processing capabilities, creating new opportunities to enhance classic search algorithms. This hardware has been exploited in best-first search algorithms with neural network-based heuristics by creating batched versions of A* and Weighted A* that delay heuristic evaluation until sufficiently many states can be evaluated in parallel on the GPU. But, research has not addressed how depth-first algorithms like IDA* or Budgeted Tree Search (BTS) can have their heuristic computations batched. This is more complicated in a tree search, because progress in the search tree is blocked until heuristic evaluations are complete. In this paper we show that GPU parallelization of heuristics can be effectively performed when the tree search is parallelized on the CPU while heuristic evaluations are parallelized on the GPU. We develop a parallelized cost-bounded depth-first search (CB-DFS) framework that can be applied to both IDA* and BTS, significantly improving their performance. We demonstrate the strength of the approach on the 3x3 Rubik's Cube and the 4x4 sliding tile puzzle (STP) with both classifier-based and regression-based heuristics.

AAMAS Conference 2026 Conference Paper

Approximating Nash Equilibria in General-Sum Games via Meta-Learning

• David Sychrovský
• Christopher Solinas
• Revan MacQueen
• Kevin Wang
• James R. Wright
• Nathan R. Sturtevant
• Michael Bowling

Nash equilibrium is perhaps the best-known solution concept in game theory. Such a solution assigns a strategy to each player which offers no incentive to unilaterally deviate. While a Nash equilibrium is guaranteed to always exist, the problem of finding one in general-sum games is PPAD-complete, generally considered intractable. Regret minimization is an efficient framework for approximatingNashequilibriaintwo-playerzero-sumgames. However, in general-sum games, such algorithms are only guaranteed to converge to a coarse-correlated equilibrium (CCE), a solution concept where players can correlate their strategies. In this work, we use meta-learning to minimize the correlations in strategies produced by a regret minimizer. This encourages the regret minimizer to find strategies that are closer to a Nash equilibrium. The meta-learned regret minimizer is still guaranteed to converge to a CCE, but we give a bound on the distance to Nash equilibrium in terms of our meta-loss. We evaluate our approach in general-sum imperfect information games. Our algorithms provide significantly betterapproximationsofNashequilibriathanstate-of-the-artregret minimization techniques.

AIJ Journal 2026 Journal Article

Is DIBBS a DXBB algorithm?

• Nathan R. Sturtevant
• Shahaf Shperberg
• Ariel Felner

The recently-introduced Dynamically Improved Bounds Bidirectional Search (DIBBS) algorithm attributes its success to the fact that it is not a deterministic expansion-based black box algorithm (DXBB). After communication with the authors, there is agreement that this characterization is incorrect. The goal of this research note is to provide correction in the literature regarding the claims around DIBBS, to make it clearer why DIBBS is a DXBB algorithm, and to explain why its performance is bounded by bidirectional search theory.

AAAI Conference 2025 Conference Paper

Anchor Search: A Unified Framework for Suboptimal Bidirectional Search

• Sepehr Lavasani
• Lior Siag
• Shahaf S. Shperberg
• Ariel Felner
• Nathan R. Sturtevant

In recent years the understanding of optimal bidirectional heuristic search (BiHS) has progressed significantly. Yet, Bi-HS is relatively unexplored in unbounded suboptimal search. Front-to-end (F2E) and front-to-front (F2F) bidirectional search have been used in optimal algorithms, but adapting them for unbounded suboptimal search remains an open challenge. We introduce a framework for suboptimal BiHS, called anchor search, and use it to derive a parameterized family of algorithms. Because our new algorithms need F2F heuristic evaluations, we propose using pattern databases (PDBs) as differential heuristics (DHs) to construct F2F heuristics. Our experiments evaluate three anchor search instances across diverse domains, outperforming existing methods, particularly as the search scales.

IJCAI Conference 2025 Conference Paper

Set-Based Retrograde Analysis: Precomputing the Solution to 28-card Bridge Double Dummy Deals

• Isaac Stone
• Nathan R. Sturtevant
• Jonathan Schaeffer

Among the most popular games played worldwide, Bridge stands out for having had little AI progress for over 25 years. Ginsberg's Partition Search algorithm (1996) was a breakthrough for double-dummy Bridge play, allowing a program to reason about sets of states rather than individual states. Partition Search supports the current state of the art for both bidding and cardplay. In the time since, virtually no progress has been made in Bridge bidding. Inspired by Ginsberg's idea, this paper presents Setrograde Analysis, a new set-based algorithm for perfectly solving Bridge hands. Using this approach, we have solved all 7-trick (28-card) hands — 10^30 states, which can be reduced to 10^17 unique states using preexisting techniques. This was done by considering five orders of magnitude fewer sets than the traditional state-based Retrograde Analysis algorithm. This work suggests that the entire 13-trick (52-card) state space can be solved with modern technology using this new approach. The 7-trick computation represents the largest endgame database to date in any game.

AAAI Conference 2025 Conference Paper

Suboptimal Search with Dynamic Distribution of Suboptimality

• Mohammadreza Hami
• Nathan R. Sturtevant

In bounded-suboptimal heuristic search, the aim is to find a solution path within a given bound as quickly as possible, which is crucial when computational resources are limited. Recent research has demonstrated Weighted A* variants such as XDP that find bounded suboptimal solutions without needing to perform state re-expansions; they work by shifting where the suboptimality in the search is allowed. However, the suboptimality distribution is fixed before the search begins. This paper introduces Dynamic Suboptimality Weighted A* (DSWA*), a search framework that allows suboptimality to be dynamically distributed at runtime, based on the properties of the search. Experiments show that dynamic policies can consistently outperform existing algorithms across a diverse set of domains, particularly those with dynamic costs.

AAMAS Conference 2024 Conference Paper

Clique Analysis and Bypassing in Continuous-Time Conflict-Based Search

• Thayne T. Walker
• Nathan R. Sturtevant
• Ariel Felner

We study symmetry-breaking enhancements for Continuous-Time Conflict-Based Search (CCBS), a solver for continuous-time MAPF. Resolving conflict symmetries in MAPF can require an exponential amount of work. We adapt known symmetry-breaking enhancements from unit-cost domains for CCBS. We then improve upon these to produce a new state of the art algorithm: CCBS with disjoint k-partite cliques (CCBS+DK). Finally, we show empirically that CCBS+DK solves for up to 20% more agents in the same amount of time when compared to previous state of the art.

SoCS Conference 2024 Conference Paper

Clique Analysis and Bypassing in Continuous-Time Conflict-Based Search

• Thayne T. Walker
• Nathan R. Sturtevant
• Ariel Felner

While the study of unit-cost Multi-Agent Pathfinding (MAPF) problems has been popular, many real-world problems require continuous time and costs. In this context, this paper studies symmetry-breaking enhancements for Continuous-Time Conflict-Based Search (CCBS), a solver for continuous-time MAPF. Resolving conflict symmetries in MAPF can require an exponential amount of work. We adapt known symmetry-breaking enhancements from unit-cost domains for CCBS: bypassing and biclique constraints. We then improve upon these to produce a new state-of-the-art algorithm: CCBS with disjoint k-partite cliques (CCBS+DK). Finally, we show empirically that CCBS+DK solves for up to 20% more agents in the same amount of time when compared to previous state-of-the-art.

SoCS Conference 2024 Conference Paper

Curriculum Generation for Learning Guiding Functions in State-Space Search Algorithms

• Sumedh Pendurkar
• Levi H. S. Lelis
• Nathan R. Sturtevant
• Guni Sharon

This paper investigates methods for training parameterized functions for guiding state-space search algorithms. Existing work commonly generates data for training such guiding functions by solving problem instances while leveraging the current version of the guiding function. As a result, as training progresses, the guided search algorithm can solve more difficult instances that are, in turn, used to further train the guiding function. These methods assume that a set of problem instances of varied difficulty is provided. Since previous work was not designed to distinguish the instances that the search algorithm can solve from those that cannot be solved with the current guiding function, the algorithm commonly wastes time attempting and failing to solve many of these instances. In this paper, we improve upon these training methods by generating a curriculum for learning the guiding function that directly addresses this issue. Namely, we propose and evaluate a Teacher-Student Curriculum (TSC) approach where the teacher is an evolutionary strategy that attempts to generate problem instances of ``correct difficulty

ICAPS Conference 2024 Conference Paper

Exact Multi-objective Path Finding with Negative Weights

• Saman Ahmadi
• Nathan R. Sturtevant
• Daniel Harabor
• Mahdi Jalili

The point-to-point Multi-objective Shortest Path (MOSP) problem is a classic yet challenging task that involves finding all Pareto-optimal paths between two points in a graph with multiple edge costs. Recent studies have shown that employing A* search can lead to state-of-the-art performance in solving MOSP instances with non-negative costs. This paper proposes a novel A*-based multi-objective search framework that not only handles graphs with negative costs and even negative cycles but also incorporates multiple speed-up techniques to enhance the efficiency of exhaustive search with A*. Through extensive experiments, our algorithm demonstrates remarkable success in solving difficult MOSP instances, outperforming leading solutions by several factors.

ECAI Conference 2024 Conference Paper

On Parallel External-Memory Bidirectional Search

• Lior Siag
• Shahaf S. Shperberg
• Ariel Felner
• Nathan R. Sturtevant

Parallelization and External Memory (PEM) techniques have significantly enhanced the capabilities of search algorithms when solving large-scale problems. Previous research on PEM has primarily centered on unidirectional algorithms, with only one publication on bidirectional PEM that focuses on the meet-in-the-middle (MM) algorithm. Building upon this foundation, this paper presents a framework that integrates both uni- and bi-directional best-first search algorithms into this framework. We then develop a PEM variant of the state-of-the-art bidirectional heuristic search (BiHS) algorithm BAE* (PEM-BAE*). As previous work on BiHS did not focus on scaling problem sizes, this work enables us to evaluate bidirectional algorithms on hard problems. Empirical evaluation shows that PEM-BAE* outperforms the PEM variants of A* and the MM algorithm, as well as a parallel variant of IDA*. These findings mark a significant milestone, revealing that bidirectional search algorithms clearly outperform unidirectional search algorithms across several domains, even when equipped with state-of-the-art heuristics.

SoCS Conference 2024 Conference Paper

On Parallel External-Memory Bidirectional Search (Extended Abstract)

• Lior Siag
• Shahaf S. Shperberg
• Ariel Felner
• Nathan R. Sturtevant

Parallelization and External Memory (PEM) techniques significantly enhance the capabilities of search algorithms for solving large-scale problems. While previous research on PEM has primarily centered on unidirectional algorithms, this work presents a versatile PEM framework that integrates both uni- and bi-directional best-first search algorithms.

SoCS Conference 2024 Conference Paper

On the Properties of All-Pair Heuristics

• Shahaf S. Shperberg
• Ariel Felner
• Lior Siag
• Nathan R. Sturtevant

While most work in heuristic search concentrates on goal-specific heuristics, which estimate the shortest path cost from any state to the goal, we explore all-pair heuristics that estimate distances between all pairs of states. We examine the relationship between these heuristic functions and the shortest distance function they estimate, revealing that all-pair consistent heuristics may violate the triangle inequality. Thus, we introduce a new property for heuristics called Δ-consistency, requiring adherence to the triangle inequality. Additionally, we present a method for transforming standard consistent heuristics to be Δ-consistent, showcasing its benefits through a synthetic example. We then show that common heuristic families inherently exhibit Δ-consistency. This positive finding encourages the use of all-pair consistent heuristics, and prompts further investigation into the optimality of A*, when given an all-pair heuristic instead of a goal-specific heuristic.

AAAI Conference 2023 Conference Paper

Analyzing and Improving the Use of the FastMap Embedding in Pathfinding Tasks

• Reza Mashayekhi
• Dor Atzmon
• Nathan R. Sturtevant

The FastMap algorithm has been proposed as an inexpensive metric embedding which provides admissible distance estimates between all vertices in an embedding. As an embedding, it also supports additional operations such as taking the median location of two vertices, which is important in some problems. This paper studies several aspects of FastMap embeddings, showing the relationship of FastMap to general additive heuristics. As an admissible heuristic, FastMap is not as strong as previous suggested. However, by combining FastMap with the ideas of differential heuristics, we can significantly improve the performance of FastMap heuristics. We show the impact of these ideas in both single-agent pathfinding and the Multi-Agent Meeting problem, where the performance of algorithms using our improved FastMap embedding is improved by up to a factor of two.

SoCS Conference 2023 Conference Paper

Comparing Front-to-Front and Front-to-End Heuristics in Bidirectional Search

• Lior Siag
• Shahaf S. Shperberg
• Ariel Felner
• Nathan R. Sturtevant

Most recent theoretical and algorithmic work in bidirectional heuristic search (BiHS) used front-to-end (F2E) heuristics that estimate the distance to the start and goal states. In this paper, we start exploring front-to-front (F2F) heuristics, which estimate the distance between any pair of states. Devising efficient algorithms that use F2F heuristics is a challenging task. Thus, it is important to first understand the benefits of using F2F heuristics compared to F2E heuristics. To this end, we theoretically and experimentally demonstrate that there is a great potential in using F2F heuristics implying that F2F BiHS is a promising area of future research.

ICAPS Conference 2023 Conference Paper

W-restrained Bidirectional Bounded-Suboptimal Heuristic Search

• Dor Atzmon
• Shahaf S. Shperberg
• Netanel Sabah
• Ariel Felner
• Nathan R. Sturtevant

In this paper, we develop theoretical foundations for bidirectional bounded-suboptimal search (BiBSS) based on recent advancements in optimal bidirectional search. In addition, we introduce a BiBSS variant of the prominent meet-in-the-middle (MM) algorithm, called Weighted MM (WMM). We show that WMM has an interesting property of being W-restrained, and study it empirically.

IJCAI Conference 2022 Conference Paper

Efficient Budgeted Graph Search

• Jasmeet Kaur
• Nathan R. Sturtevant

Iterative Budgeted Exponential Search (IBEX) is a general search algorithm that can limit the number of re-expansions performed in common problems like iterative-deepening tree search and search with inconsistent heuristics. IBEX has been adapted into a specific tree algorithm, Budgeted Tree Search (BTS), which behaves like IDA* when the problem instance is well-behaved but keeps the worst-case guarantees when problems are not well-behaved. The analogous algorithms on graphs, Budgeted Graph Search (BGS), do not have these same properties. This paper reformulates BGS into Efficient Budgeted Graph Search (BGSe), showing how to implement the algorithm so that it behaves identically to A* when problems are well-behaved, and retains the best-case performance otherwise. Experimental results validate the performance of BGSe on a range of theoretical and practical problem instances.

IJCAI Conference 2022 Conference Paper

Learning Curricula for Humans: An Empirical Study with Puzzles from The Witness

• Levi H. S. Lelis
• João G. G. V. Nova
• Eugene Chen
• Nathan R. Sturtevant
• Carrie Demmans Epp
• Michael Bowling

The combination of tree search and neural networks has achieved super-human performance in challenging domains. We are interested in transferring to humans the knowledge these learning systems generate. We hypothesize the process in which neural-guided tree search algorithms learn how to solve a set of problems can be used to generate curricula for helping human learners. In this paper we show how the Bootstrap learning system can be modified to learn curricula for humans in a puzzle domain. We evaluate our system in two curriculum learning settings. First, given a small set of problem instances, our system orders the instances to ease the learning process of human learners. Second, given a large set of problem instances, our system returns a small ordered subset of the initial set that can be presented to human learners. We evaluate our curricula with a user study where participants learn how to solve a class of puzzles from the game `The Witness. ' The user-study results suggest one of the curricula our system generates compares favorably with simple baselines and is competitive with the curriculum from the original `The Witness' game in terms of user retention and effort.

ICAPS Conference 2022 Conference Paper

Multi-Agent Path Finding with Temporal Jump Point Search

• Shuli Hu
• Daniel Harabor
• Graeme Gange
• Peter J. Stuckey
• Nathan R. Sturtevant

Temporal Jump Point Search (JPST) is a recently introduced algorithm for grid-optimal pathfinding among dynamic temporal obstacles. In this work we consider JPST as a low-level planner in Multi-Agent Path Finding (MAPF). We investigate how the canonical ordering of JPST can negatively impact MAPF performance and we consider several strategies which allow us to overcome these limitations. Experiments show our new CBS/JPST approach can substantially improve on CBS/SIPP, a contemporary and leading method from the area.

SoCS Conference 2022 Conference Paper

Optimal Search with Neural Networks: Challenges and Approaches

• Tianhua Li
• Ruimin Chen
• Borislav Mavrin
• Nathan R. Sturtevant
• Doron Nadav
• Ariel Felner

Work in machine learning has grown tremendously in the past years, but has had little to no impact on optimal search approaches. This paper looks at challenges in using deep learning as a part of optimal search, including what is feasible using current public frameworks, and what barriers exist for further adoption. The primary contribution of the paper is to show how to learn admissible heuristics through supervised learning from an existing heuristic. Several approaches are described, with the most successful approach being based on learning a heuristic as a classifier and then adjusting the quantile used with the classifier to ensure heuristic admissibility, which is required for optimal solutions. A secondary contribution is a description of the Batch A* algorithm, which can batch evaluations for more efficient use by the GPU. While ANNs can effectively learn heuristics that produce smaller search trees than alternate compression approaches, there still exists a time overhead when compared to efficient C++ implementations. This point of evaluation points out a challenge for future work.

SoCS Conference 2021 Conference Paper

Avoiding Re-expansions in Suboptimal Best-First Search

• Jingwei Chen
• Nathan R. Sturtevant

This paper gives a summary of published conditions needed for a priority function to return bounded-optimal solutions when not performing re-expansions of previously expanded states in best-first search.

ICAPS Conference 2021 Conference Paper

Conflict-Based Increasing Cost Search

• Thayne T. Walker
• Nathan R. Sturtevant
• Ariel Felner
• Han Zhang 0018
• Jiaoyang Li 0001
• T. K. Satish Kumar

Two popular optimal search-based solvers for the multi-agent pathfinding (MAPF) problem, Conflict-Based Search (CBS) and Increasing Cost Tree Search (ICTS), have been extended separately for continuous time domains and symmetry breaking. However, an approach to symmetry breaking in continuous time domains remained elusive. In this work, we introduce a new algorithm, Conflict-Based Increasing Cost Search (CBICS), which is capable of symmetry breaking in continuous time domains by combining the strengths of CBS and ICTS. Our experiments show that CBICS often finds solutions faster than CBS and ICTS in both unit time and continuous time domains.

SoCS Conference 2021 Conference Paper

Iterative-Deepening Bidirectional Heuristic Search with Restricted Memory

• Shahaf S. Shperberg
• Steven Danishevski
• Ariel Felner
• Nathan R. Sturtevant

This extended abstract presents a bidirectional heuristic search algorithm called IDBiHS that operates under restricted memory. Several variants of this algorithm are introduced for different types of memory restrictions, and are compared against existing algorithms with similar restrictions.

ICAPS Conference 2021 Conference Paper

Iterative-deepening Bidirectional Heuristic Search with Restricted Memory

• Shahaf S. Shperberg
• Steven Danishevski
• Ariel Felner
• Nathan R. Sturtevant

The field of bidirectional heuristic search has recently seen great advances. However, the subject of memory-restricted bidirectional search has not received recent attention. In this paper we introduce a general iterative deepening bidirectional heuristic search algorithm (IDBiHS) that searches simultaneously in both directions while controlling the meeting point of the search frontiers. First, we present the basic variant of IDBiHS, whose memory is linear in the search depth. We then add improvements that exploit consistency and front-to-front heuristics. Next, we move to the case where a fixed amount of memory is available to store nodes during the search and develop two variants of IDBiHS: (1) A*+IDBiHS, that starts with A* and moves to IDBiHS as soon as memory is exhausted. (2) A variant that stores partial forward frontiers until memory is exhausted and then tries to match each of them from the backward side. Finally, we experimentally compare the new algorithms to existing unidirectional and bidirectional ones. In many cases our new algorithms outperform previous ones in both node expansions and time.

ICAPS Conference 2021 Conference Paper

Jump Point Search with Temporal Obstacles

• Shuli Hu
• Daniel Harabor
• Graeme Gange
• Peter J. Stuckey
• Nathan R. Sturtevant

In 4-connected grid-based path planning one often needs to account for temporal and moving obstacles: ones that appear, disappear and which can prevent the agent from reaching its target. Such problems are common in a variety of settings (games, robotics etc.) and they can be surprisingly challenging to solve. First, because the temporal aspect increases the size of the search space; second because the search space contains many symmetric paths, indistinguishable from one another except by the order in which grid moves appear. To tackle such problems we consider a new optimal algorithm – in the style of Jump Point Search – which can identify and break these symmetries and thus improves performance; from several factor to more than one order of magnitude vs. SIPP, arguably the gold standard baseline in the area.

AAAI Conference 2021 Conference Paper

Necessary and Sufficient Conditions for Avoiding Reopenings in Best First Suboptimal Search with General Bounding Functions

• Jingwei Chen
• Nathan R. Sturtevant

Recent work introduced XDP and XUP priority functions for best-first bounded-suboptimal search that do not need to perform state re-expansions as long as the search heuristic is consistent. However, that work had several limitations that are rectified here. This paper analyzes the sufficiency and necessity of the conditions used to formulate XDP and XUP. The analysis presents a simpler proof and generalizes the result in three aspects: (1) the priority function no longer has to be differentiable everywhere, (2) the quality of the solution does not have to be bounded by a constant factor, and (3) directed graphs are handled correctly. These results allow the introduction of more priority functions, such as piecewise linear functions, and more variants of bounded-suboptimal search, such as constant suboptimality. Several new priority functions are presented in this paper that, according to empirical results, can significantly outperform existing approaches including XDP.

SoCS Conference 2020 Conference Paper

A Guide to Budgeted Tree Search

• Nathan R. Sturtevant
• Malte Helmert

Budgeted Tree Search (BTS), a variant of Iterative Budgeted Exponential Search, is a new algorithm that has the same performance as IDA* on problems where the state space grows exponentially, but has far better performance than IDA* in other cases where IDA* fails. The goal of this paper is to provide a detailed guide to BTS with worked examples to make the algorithm more accessible to practitioners in heuristic search.

AAAI Conference 2020 Conference Paper

Abstraction and Refinement in Games with Dynamic Weighted Terrain

• Nathan R. Sturtevant
• Devon Sigurdson
• Bjorn Taylor
• Tim Gibson

This abstract looks at one version of the pathfinding problem in games and discusses how it motived our recent work at the AIIDE 2019 conference.

AAAI Conference 2020 Conference Paper

Generalized and Sub-Optimal Bipartite Constraints for Conflict-Based Search

• Thayne T. Walker
• Nathan R. Sturtevant
• Ariel Felner

The main idea of conflict-based search (CBS), a popular, state-of-the-art algorithm for multi-agent pathfinding is to resolve conflicts between agents by systematically adding constraints to agents. Recently, CBS has been adapted for new domains and variants, including non-unit costs and continuous time settings. These adaptations require new types of constraints. This paper introduces a new automatic constraint generation technique called bipartite reduction (BR). BR converts the constraint generation step of CBS to a surrogate bipartite graph problem. The properties of BR guarantee completeness and optimality for CBS. Also, BR’s properties may be relaxed to obtain suboptimal solutions. Empirical results show that BR yields significant speedups in 2k connected grids over the previous state-of-the-art for both optimal and suboptimal search.

SoCS Conference 2020 Conference Paper

Multi-Directional Search

• Dor Atzmon
• Jiaoyang Li 0001
• Ariel Felner
• Eliran Nachmani
• Shahaf S. Shperberg
• Nathan R. Sturtevant
• Sven Koenig

In the Multi-Agent Meeting (MAM) problem, the task is to find a meeting location for multiple agents, as well as a path for each agent to that location. In this paper, we introduce MM*, a Multi-Directional Search algorithm that finds the optimal meeting location under different cost functions. MM* generalizes the Meet in the Middle (MM) bidirectional search algorithm to the case of finding optimal meeting locations for multiple agents. A number of admissible heuristics are proposed and experiments demonstrate the benefits of MM*.

ICAPS Conference 2020 Conference Paper

Predicting the Effectiveness of Bidirectional Heuristic Search

• Nathan R. Sturtevant
• Shahaf S. Shperberg
• Ariel Felner
• Jingwei Chen

The question of when bidirectional heuristic search outperforms unidirectional heuristic search has been revisited numerous times in the field of Artificial Intelligence. This paper re-addresses the question of when bidirectional search outperforms unidirectional search using an updated theoretical understanding of the problem. We show that a core set of critical states in the state space are the primary factor determining whether a bidirectional search can outperform a unidirectional search and provide simple measures to determine whether a state space and heuristic contains these critical states. We similarly discuss and show the impact that asymmetry in the underlying problem graph has on the performance of bidirectional algorithms. Experimental results show the impact of these factors on whether a problem should be solved using unidirectional or bidirectional search.

ICAPS Conference 2020 Conference Paper

Probabilistic Robust Multi-Agent Path Finding

• Dor Atzmon
• Roni Stern
• Ariel Felner
• Nathan R. Sturtevant
• Sven Koenig

In a multi-agent path finding (MAPF) problem, the task is to move a set of agents to their goal locations without conflicts. In the real world, unexpected events may delay some of the agents. In this paper, we therefore study the problem of finding a p-robust solution to a given MAPF problem, which is a solution that succeeds with probability at least p, even though unexpected delays may occur. We propose two methods for verifying that given solutions are p-robust. We also introduce an optimal CBS-based algorithm, called pR-CBS, and a fast suboptimal algorithm, called pR-GCBS, for finding such solutions. Our experiments show that a p-robust solution reduces the number of conflicts compared to optimal, non-robust solutions.

IJCAI Conference 2019 Conference Paper

Conditions for Avoiding Node Re-expansions in Bounded Suboptimal Search

• Jingwei Chen
• Nathan R. Sturtevant

Many practical problems are too difficult to solve optimally, motivating the need to found suboptimal solutions, particularly those with bounds on the final solution quality. Algorithms like Weighted A*, A*-epsilon, Optimistic Search, EES, and DPS have been developed to find suboptimal solutions with solution quality that is within a constant bound of the optimal solution. However, with the exception of weighted A*, all of these algorithms require performing node re-expansions during search. This paper explores the properties of priority functions that can find bounded suboptimal solution without requiring node re-expansions. After general bounds are developed, two new convex priority functions are developed that can outperform weighted A*.

IJCAI Conference 2019 Conference Paper

Direction-Optimizing Breadth-First Search with External Memory Storage

• Shuli Hu
• Nathan R. Sturtevant

While computing resources have continued to grow, methods for building and using large heuristics have not seen significant advances in recent years. We have observed that direction-optimizing breadth-first search, developed for and used broadly in the Graph 500 competition, can also be applied for building heuristics. But, the algorithm cannot run efficiently using external memory -- when the heuristics being built are larger than RAM. This paper shows how to modify direction-optimizing breadth-first search to build external-memory heuristics. We show that the new approach is not effective in state spaces with low asymptotic branching factors, but in other domains we are able to achieve up to a 3x reducing in runtime when building an external-memory heuristic. The approach is then used to build a 2. 6TiB Rubik's Cube heuristic with 5. 8 trillion entries, the largest pattern database heuristic ever built.

AAAI Conference 2019 Conference Paper

Enriching Non-Parametric Bidirectional Search Algorithms

• Shahaf S. Shperberg
• Ariel Felner
• Nathan R. Sturtevant
• Solomon E. Shimony
• Avi Hayoun

NBS is a non-parametric bidirectional search algorithm proven to expand at most twice the number of node expansions required to verify the optimality of a solution. We introduce new variants of NBS that are aimed at finding all optimal solutions. We then introduce an algorithmic framework that includes NBS as a special case. Finally, we introduce DVCBS, a new algorithm in this framework that aims to further reduce the number of expansions. Unlike NBS, DVCBS does not have any worst-case bound guarantees, but in practice it outperforms NBS in verifying the optimality of solutions.

SoCS Conference 2019 Conference Paper

Enriching Non-Parametric Bidirectional Search Algorithms - Extended Abstract

• Shahaf S. Shperberg
• Ariel Felner
• Nathan R. Sturtevant
• Solomon Eyal Shimony
• Avi Hayoun

NBS is a non-parametric bidirectional search algorithm, proved to expand at most twice the number of node expansions required to verify the optimality of a solution. We introduce new variants of NBS that are aimed at finding all optimal solutions. We then introduce an algorithmic framework that includes NBS as a special case. Finally, we introduce DVCBS, a new algorithm in this framework that aims to further reduce the number of expansions. Unlike NBS, DVCBS does not have any worst-case bound guarantees, but in practice it outperforms NBS in verifying the optimality of solutions.

SoCS Conference 2019 Conference Paper

Improving Bidirectional Heuristic Search by Bounds Propagation

• Shahaf S. Shperberg
• Ariel Felner
• Solomon Eyal Shimony
• Nathan R. Sturtevant
• Avi Hayoun

Recent work in bidirectional heuristic search characterize pairs of nodes from which at least one node must be expanded in order to ensure optimality of solutions. We use these findings to propose a method for improving existing heuristics by propagating lower bounds between the forward and backward frontiers. We then define a number of desirable properties for bidirectional heuristic search algorithms, and show that applying the bound propagations adds these properties to many existing algorithms (e. g. to the MM family of algorithms). Finally, experimental results show that applying these propagations significantly reduce the running time of various algorithms.

IJCAI Conference 2019 Conference Paper

Iterative Budgeted Exponential Search

• Malte Helmert
• Tor Lattimore
• Levi H. S. Lelis
• Laurent Orseau
• Nathan R. Sturtevant

We tackle two long-standing problems related to re-expansions in heuristic search algorithms. For graph search, A* can require Ω(2ⁿ) expansions, where n is the number of states within the final f bound. Existing algorithms that address this problem like B and B’ improve this bound to Ω(n²). For tree search, IDA* can also require Ω(n²) expansions. We describe a new algorithmic framework that iteratively controls an expansion budget and solution cost limit, giving rise to new graph and tree search algorithms for which the number of expansions is O(n log C*), where C* is the optimal solution cost. Our experiments show that the new algorithms are robust in scenarios where existing algorithms fail. In the case of tree search, our new algorithms have no overhead over IDA* in scenarios to which IDA* is well suited and can therefore be recommended as a general replacement for IDA*.

SoCS Conference 2019 Conference Paper

Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks

• Roni Stern
• Nathan R. Sturtevant
• Ariel Felner
• Sven Koenig
• Hang Ma 0001
• Thayne T. Walker
• Jiaoyang Li 0001
• Dor Atzmon

The multi-agent pathfinding problem (MAPF) is the fundamental problem of planning paths for multiple agents, where the key constraint is that the agents will be able to follow these paths concurrently without colliding with each other. Applications of MAPF include automated warehouses, autonomous vehicles, and robotics. Research on MAPF has been flourishing in the past couple of years. Different MAPF research papers assume different sets of assumptions, e. g. , whether agents can traverse the same road at the same time, and have different objective functions, e. g. , minimize makespan or sum of agents

IJCAI Conference 2019 Conference Paper

Optimally Efficient Bidirectional Search

• Eshed Shaham
• Ariel Felner
• Nathan R. Sturtevant
• Jeffrey S. Rosenschein

A* is optimally efficient with regard to node expansions among unidirectional admissible algorithms — those that only assume that the heuristic used is admissible. This paper studies algorithms that are optimally efficient for bidirectional search algorithms. We present the Fractional MM algorithm and its sibling, the MT algorithm, which is simpler to analyze. We then develop variants of these algorithms that are optimally efficient, each under different assumptions on the information available to the algorithm.

SoCS Conference 2019 Conference Paper

Revisiting Suboptimal Search

• Jingwei Chen
• Nathan R. Sturtevant
• William J. Doyle
• Wheeler Ruml

Suboptimal search algorithms can often solve much larger problems than optimal search algorithms, and thus have broad practical use. This paper returns to early algorithms like WA*, A*_e and Optimistic search. It studies the commonalities between these approaches in order to build a new bounded-suboptimal algorithm. Combined with recent research on avoiding node re-expansions in bounded-optimal search, a new solution quality bound is developed, which often provides proof of the solution bound much earlier during the search. Put together, these ideas provide a new state-of-the-art in bounded-optimal search.

SoCS Conference 2019 Conference Paper

Unbounded Sub-Optimal Conflict-Based Search in Complex Domains

• Thayne T. Walker
• Nathan R. Sturtevant
• Ariel Felner

Conflict-Based Search (CBS) is a state of the art algorithm for multi-agent pathfinding (MAPF). CBS has been studied in many domains, however, most research has focused on classic domains with point agents that move with unit time steps and unit costs. In this work, we are interested in MAPF solutions for classic domains and complex domains, that is, domains which include shaped agents, actions with non-unit costs, non-uniform action durations and/or non-holonomic or kinodynamic movement constraints. Prior work on sub-optimal formulations of CBS has focused on heuristics. Instead, our work introduces new types of constraints. We show that certain constraint formulations have properties that can cause CBS to run orders of magnitude faster, but may cause the algorithm to be incomplete and yield sub-optimal results. We introduce new conditional constraints which allow CBS to exploit constraint properties which cause it to run faster and still retain algorithmic completeness. We additionally formulate a new constraint accumulation technique called constraint overloading which utilizes conditional constraints in order to achieve further performance gains.

SoCS Conference 2018 Conference Paper

Benchmarks for Pathfinding in 3D Voxel Space

• Daniel Brewer
• Nathan R. Sturtevant

The problem of finding optimal paths in 3D space is computationally more complex than in a 2D plane. While a range of different approaches have been developed across different fields, there has been relatively little work studying the complexities and tradeoffs of implementations for path planning in 3D space. This paper describes the 3D path planning problem faced in the game Warframe. The solution used by industry was tuned for their own constraints, but little is known about the applicability of other approaches to solving this problem. Thus, the makers of this game have made their underlying planning data available for researchers to use. This paper describes this new data set which is publicly available for study and dissemination.

IJCAI Conference 2018 Conference Paper

Extended Increasing Cost Tree Search for Non-Unit Cost Domains

• Thayne T. Walker
• Nathan R. Sturtevant
• Ariel Felner

Multi-agent pathfinding (MAPF) has applications in navigation, robotics, games and planning. Most work on search-based optimal algorithms for MAPF has focused on simple domains with unit cost actions and unit time steps. Although these constraints keep many aspects of the algorithms simple, they also severely limit the domains that can be used. In this paper we introduce a new definition of the MAPF problem for non-unit cost and non-unit time step domains along with new multiagent state successor generation schemes for these domains. Finally, we define an extended version of the increasing cost tree search algorithm (ICTS) for non-unit costs, with two new sub-optimal variants of ICTS: epsilon-ICTS and w-ICTS. Our experiments show that higher quality sub-optimal solutions are achievable in domains with finely discretized movement models in no more time than lower-quality, optimal solutions in domains with coarsely discretized movement models.

SoCS Conference 2018 Conference Paper

Minimizing Node Expansions in Bidirectional Search with Consistent Heuristics

• Eshed Shaham
• Ariel Felner
• Nathan R. Sturtevant
• Jeffrey S. Rosenschein

A* is optimally effective with regard to node expansions among unidirectional admissible algorithms—those that only assume that the heuristic used is admissible. Among bidirectional algorithms the Fractional MM algorithm is optimally effective (given the correct parameters) among admissible algorithms. This paper generalizes the bidirectional result to more complex settings where more information on the problem domain can be exploited: (1) When the cost of the minimal edge is known. (2) When the algorithm knows that the heuristics are consistent. This characterization uses a novel algorithm called MT. MT is similar to Fractional MM and is also optimally effective, but simpler to analyze.

SoCS Conference 2018 Conference Paper

Rapid Randomized Restarts for Multi-Agent Path Finding Solvers

• Liron Cohen 0002
• Glenn Wagner
• David M. Chan
• Howie Choset
• Nathan R. Sturtevant
• Sven Koenig
• T. K. Satish Kumar

Multi-Agent Path Finding (MAPF) is an NP-hard problem that has been well studied in artificial intelligence and robotics. Recently, randomized MAPF solvers have been shown to exhibit heavy-tailed distributions of runtimes, which can be exploited to boost their success rate for a given runtime limit. In this paper, we discuss different ways of randomizing MAPF solvers and evaluate simple rapid randomized restart strategies for state-of-the-art MAPF solvers such as iECBS, M* with highways and CBS-CL.

IJCAI Conference 2017 Conference Paper

Front-to-End Bidirectional Heuristic Search with Near-Optimal Node Expansions

• Jingwei Chen
• Robert C. Holte
• Sandra Zilles
• Nathan R. Sturtevant

It is well-known that any admissible unidirectional heuristic search algorithm must expand all states whose f-value is smaller than the optimal solution cost when using a consistent heuristic. Such states are called “surely expanded” (s. e. ). A recent study characterized s. e. pairs of states for bidirectional search with consistent heuristics: if a pair of states is s. e. then at least one of the two states must be expanded. This paper derives a lower bound, VC, on the minimum number of expansions required to cover all s. e. pairs, and present a new admissible front-to-end bidirectional heuristic search algorithm, Near-Optimal Bidirectional Search (NBS), that is guaranteed to do no more than 2VC expansions. We further prove that no admissible front-to-end algorithm has a worst case better than 2VC. Experimental results show that NBS competes with or outperforms existing bidirectional search algorithms, and often outperforms A* as well.

AIJ Journal 2017 Journal Article

MM: A bidirectional search algorithm that is guaranteed to meet in the middle

• Robert C. Holte
• Ariel Felner
• Guni Sharon
• Nathan R. Sturtevant
• Jingwei Chen

Bidirectional search algorithms interleave two separate searches, a normal search forward from the start state, and a search backward from the goal. It is well known that adding a heuristic to unidirectional search dramatically reduces the search effort. By contrast, despite decades of research, bidirectional heuristic search has not yet had a major impact. Additionally, no comprehensive theory was ever devised to understand the nature of bidirectional heuristic search. In this paper we aim to close this gap. We first present MM, a novel bidirectional heuristic search algorithm. Unlike previous bidirectional heuristic search algorithms, MM's forward and backward searches are guaranteed to “meet in the middle”, i. e. never expand a node beyond the solution midpoint. Based on this unique attribute we present a novel framework for comparing MM, A*, and their brute-force variants. We do this by dividing the entire state space into disjoint regions based on their distance from the start and goal. This allows us to perform a comparison of these algorithms on a per region basis and identify conditions favoring each algorithm. Finally, we present experimental results that support our theoretical analysis.

SoCS Conference 2017 Conference Paper

On Variable Dependencies and Compressed Pattern Databases

• Malte Helmert
• Nathan R. Sturtevant
• Ariel Felner

Pattern databases are among the strongest known heuristics for many classical search benchmarks such as sliding-tile puzzles, the 4-peg Towers of Hanoi puzzles, Rubik

SoCS Conference 2017 Conference Paper

Search-Based Optimal Solvers for the Multi-Agent Pathfinding Problem: Summary and Challenges

• Ariel Felner
• Roni Stern
• Solomon Eyal Shimony
• Eli Boyarski
• Meir Goldenberg
• Guni Sharon
• Nathan R. Sturtevant
• Glenn Wagner

Multi-agent pathfinding (MAPF) is an area of expanding research interest. At the core of this research area, numerous diverse search-based techniques were developed in the past 6 years for optimally solving MAPF under the sum-of-costs objective function. In this paper we survey these techniques, while placing them into the wider context of the MAPF field of research. Finally, we provide analytical and experimental comparisons that show that no algorithm dominates all others in all circumstances. We conclude by listing important future research directions.

ICAPS Conference 2017 Conference Paper

Sufficient Conditions for Node Expansion in Bidirectional Heuristic Search

• Jürgen Eckerle
• Jingwei Chen
• Nathan R. Sturtevant
• Sandra Zilles
• Robert C. Holte

In this paper we study bidirectional state space search with consistent heuristics, with a focus on obtaining sufficient conditions for node expansion, that is, conditions characterizing nodes that must be expanded by any admissible bidirectional search algorithm. We provide such conditions for front-to-front and front-to-end bidirectional search. The sufficient conditions are used to prove that the front-to-front bidirectional search algorithm BDS1 is optimally efficient, in terms of node expansion, among a broad class of bidirectional search algorithms, for a specific class of problem instances. Dechter and Pearl's well-known result on sufficient conditions for node expansion by unidirectional algorithms such as A* is shown to be a special case of our results.

SoCS Conference 2017 Conference Paper

The Minimal Set of States that Must Be Expanded in a Front-to-End Bidirectional Search

• Eshed Shaham
• Ariel Felner
• Jingwei Chen
• Nathan R. Sturtevant

A* is optimal among admissible unidirectional algorithms when searching with a consistent heuristic. Recently, similar optimality bounds have been established for bidirectional search, but no practical algorithm is guaranteed to always achieve this bound. In this paper we study the nature of the number of nodes that must be expanded in any front-to-end bidirectional search. We present an efficient algorithm for computing that number and show that a theoretical parameterized generalization of MM, with the correct parameter, is the optimal front-to-end bidirectional search. We then experimentally compare various algorithms and show how far they are from optimal.

ICAPS Conference 2017 Conference Paper

Using Hierarchical Constraints to Avoid Conflicts in Multi-Agent Pathfinding

• Thayne T. Walker
• David M. Chan
• Nathan R. Sturtevant

Recent work in multi-agent path planning has provided a number of optimal and suboptimal solvers that can efficiently find solutions to problems of growing complexity. Solvers based on Conflict-Based Search (CBS) combine single-agent solvers with shared constraints between agents to find feasible solutions. Suboptimal variants of CBS introduce alternate heuristics to avoid conflicts. In this paper we study the multi-agent planning problem in the context of non-holonomic vehicles planning on a lattice. We propose that in addition to using heuristics to avoid conflicts, we can plan using a hierarchy of movement constraints to efficiently avoid conflicts. We develop a new extension to the CBS algorithm, CBS with constraint layering (CBS+CL), which iteratively applies different movement constraint models during the CBS planning process. Our results show that this approach allows us to solve for about 2. 4 times more agents in the same amount of time when compared to regular CBS without using a constraint hierarchy.

IJCAI Conference 2016 Conference Paper

Canonical Orderings on Grids

• Nathan R. Sturtevant
• Steve Rabin

Jump Point Search, an algorithm developed for fast search on uniform cost grids, has successfully improved the performance of grid-based search. But, the approach itself is actually a set of diverse ideas applied together. This paper decomposes the algorithm and gradually reconstructs it, showing the component pieces from which the algorithm is constructed. In this process, we are able to define a spectrum of new algorithms that borrow and repurpose ideas from Jump Point Search. This decomposition opens the door for applying the ideas from Jump Point Search in other grid domains with significantly different characteristics from two dimensional grids.

SoCS Conference 2016 Conference Paper

Extended Abstract: An Improved Priority Function for Bidirectional Heuristic Search

• Guni Sharon
• Robert C. Holte
• Ariel Felner
• Nathan R. Sturtevant

Bidirectional search algorithms interleave a search forward from the start state (start ) and a search backward (i. e. using reverse operators) from the goal state (goal). We say that the two searches “meet in the middle” if neither search expands a node whose g-value (in the given direction) exceeds C*/2, where C* is the cost of an optimal solution. The only bidirectional heuristic search algorithm that is guaranteed to meet in the middle under all circumstances is the recently introduced MM algorithm (Holte et al. 2016). The feature of MM that provides this guarantee is its unique priority functions for nodes on its open lists. In this short note we present MMe, which enhances MM’s priority function and is expected to expand fewer nodes than MM under most circumstances. We sketch a proof of MMe’s correctness, describe conditions under which MMe will expand fewer nodes than MM and vice versa, and experimentally compare MMe and MM on the 10-Pancake problem.

IJCAI Conference 2016 Conference Paper

External Memory Bidirectional Search

• Nathan R. Sturtevant
• Jingwei Chen

This paper studies external memory bidirectional search. That is, how bidirectional search algorithms can run using external memory such as hard drives or solid state drives. While external memory algorithms have been broadly studied in unidirectional search, they have not been studied in the context of bidirectional search. We show that the primary bottleneck in bidirectional search is the question of solution detection - knowing when the two search frontiers have met. We propose a method of delayed solution detection that makes external bidirectional search more efficient. Experimental results show the effectiveness of the approach.

SoCS Conference 2016 Conference Paper

Generalizing JPS Symmetry Detection: Canonical Orderings on Graphs

• Nathan R. Sturtevant

The Jump Point Search (JPS) algorithm is designed explicitly for search on grids; it uses grid-specific properties to reduce symmetry and provide faster optimal search without pre-computation. Recent work has broken the algorithm down into three components: a best-first search, a canonical ordering of states, and a jumping policy. This paper shows how a canonical ordering can be built on general graphs and used in a similar manner to the canonical ordering of JPS. This approach is able to significantly reduce the number of states generated by an A* search, but more work is needed to optimize and fully characterize the correctness of the approach.

JAIR Journal 2016 Journal Article

Scrubbing During Learning In Real-time Heuristic Search

• Nathan R. Sturtevant
• Vadim Bulitko

Real-time agent-centered heuristic search is a well-studied problem where an agent that can only reason locally about the world must travel to a goal location using bounded computation and memory at each step. Many algorithms have been proposed for this problem and theoretical results have also been derived for the worst-case performance with simple examples demonstrating worst-case performance in practice. Lower bounds, however, have not been widely studied. In this paper we study best-case performance more generally and derive theoretical lower bounds for reaching the goal using LRTA*, a canonical example of a real-time agent-centered heuristic search algorithm. The results show that, given some reasonable restrictions on the state space and the heuristic function, the number of steps an LRTA*-like algorithm requires to reach the goal will grow asymptotically faster than the state space, resulting in ``scrubbing'' where the agent repeatedly visits the same state. We then show that while the asymptotic analysis does not hold for more complex real-time search algorithms, experimental results suggest that it is still descriptive of practical performance.

AIJ Journal 2015 Journal Article

Conflict-based search for optimal multi-agent pathfinding

• Guni Sharon
• Roni Stern
• Ariel Felner
• Nathan R. Sturtevant

In the multi-agent pathfinding problem (MAPF) we are given a set of agents each with respective start and goal positions. The task is to find paths for all agents while avoiding collisions. Most previous work on solving this problem optimally has treated the individual agents as a single ‘joint agent’ and then applied single-agent search variants of the A* algorithm. In this paper we present the Conflict Based Search (CBS) a new optimal multi-agent pathfinding algorithm. CBS is a two-level algorithm that does not convert the problem into the single ‘joint agent’ model. At the high level, a search is performed on a Conflict Tree (CT) which is a tree based on conflicts between individual agents. Each node in the CT represents a set of constraints on the motion of the agents. At the low level, fast single-agent searches are performed to satisfy the constraints imposed by the high level CT node. In many cases this two-level formulation enables CBS to examine fewer states than A* while still maintaining optimality. We analyze CBS and show its benefits and drawbacks. Additionally we present the Meta-Agent CBS (MA-CBS) algorithm. MA-CBS is a generalization of CBS. Unlike basic CBS, MA-CBS is not restricted to single-agent searches at the low level. Instead, MA-CBS allows agents to be merged into small groups of joint agents. This mitigates some of the drawbacks of basic CBS and further improves performance. In fact, MA-CBS is a framework that can be built on top of any optimal and complete MAPF solver in order to enhance its performance. Experimental results on various problems show a speedup of up to an order of magnitude over previous approaches.

SoCS Conference 2015 Invited Paper

The Grid-Based Path Planning Competition: 2014 Entries and Results

• Nathan R. Sturtevant
• Jason M. Traish
• James R. Tulip
• Tansel Uras
• Sven Koenig
• Ben Strasser
• Adi Botea
• Daniel Harabor

The Grid-Based Path Planning Competition has just completed its third iteration. The entriesused in the competition have improved significantly during this time, changing the view ofthe state of the art of grid-based pathfinding. Furthermore, the entries from the competition have beenmade publicly available, improving the ability of researchers to compare their work. Thispaper summarizes the entries to the 2014 competition, presents the 2014 competition results, and talks about what has been learned and where there is room for improvement.

ICAPS Conference 2014 Conference Paper

A Comparison of Knowledge-Based GBFS Enhancements and Knowledge-Free Exploration

• Richard Valenzano
• Nathan R. Sturtevant
• Jonathan Schaeffer 0001
• Fan Xie 0001

GBFS-based satisficing planners often augment their search with knowledge-based enhancements such as preferred operators and multiple heuristics. These techniques seek to improve planner performance by making the search more informed. In our work, we will focus on how these enhancements impact coverage and we will use a simple technique called epsilon-greedy node selection to demonstrate that planner coverage can also be improved by introducing knowledge-free random exploration into the search. We then revisit the existing knowledge-based enhancements so as to determine if the knowledge these enhancements employ is offering necessary guidance, or if the impact of this knowledge is to add exploration which can be achieved more simply using randomness. This investigation provides further evidence of the importance of preferred operators and shows that the knowledge added when using an additional heuristic is crucial in certain domains, while not being as effective as random exploration in others. Finally, we demonstrate that random exploration can also improve the coverage of LAMA, a planner which already employs multiple enhancements. This suggests that knowledge-based enhancements need to be compared to appropriate knowledge-free random baselines so as to ensure the importance of the knowledge being used.

SoCS Conference 2014 Conference Paper

Estimating Search Tree Size with Duplicate Detection

• Levi H. S. Lelis
• Roni Stern
• Nathan R. Sturtevant

In this paper we introduce Stratified Sampling with Duplicate Detection (SSDD), an algorithm for estimating the number of state expansions performed by heuristic search algorithms seeking solutions in state spaces represented by undirected graphs. SSDD is general and can be applied to estimate other state-space properties. We test SSDD on two tasks: (i) prediction of the number of A* expansions in a given f-layer when using a consistent heuristic function, and (ii) prediction of the state-space radius. SSDD has the asymptotic guarantee of producing perfect estimates in both tasks. Our empirical results show that in task (i) SSDD produces good estimates in all four domains tested, being in most cases orders of magnitude more accurate than a competing scheme, and in task (ii) SSDD quickly produces accurate estimates of the radii of the 4x4 Sliding-Tile Puzzle and the 3x3x3 Rubik

SoCS Conference 2014 Conference Paper

Exploiting the Rubik's Cube 12-Edge PDB by Combining Partial Pattern Databases and Bloom Filters

• Nathan R. Sturtevant
• Ariel Felner
• Malte Helmert

Pattern Databases (PDBs) are a common form of abstraction-based heuristic whichare often compressed so that a large PDB can fit inmemory. Partial Pattern Databases (PPDBs) achieve this by storing only layersof the PDB which are close to the goal. This paper studies the problem of howto best compress and use the 457 GB 12-edge Rubik

SoCS Conference 2014 Conference Paper

Exponential Deepening A* for Real-Time Agent-Centered Search

• Guni Sharon
• Ariel Felner
• Nathan R. Sturtevant

This paper introduces Exponential Deepening A* (EDA*), an Iterative Deepening (ID) algorithm where the threshold between successive Depth-First calls is increased exponentially. EDA* can be viewed as a Real-Time Agent-Centered (RTACS) algorithm. Unlike most existing RTACS algorithms, EDA* is proven to hold a worst case bound that is linear in the state space. Experimental results demonstrate up to 5x reduction over existing RTACS solvers wrt distance traveled, states expanded and CPU runtime. A full version of this paper appears in AAAI-14.

SoCS Conference 2014 Conference Paper

Reaching the Goal in Real-Time Heuristic Search: Scrubbing Behavior is Unavoidable

• Nathan R. Sturtevant
• Vadim Bulitko

Real-time agent-centered heuristic search is a well-studied problem where an agent that can only reason locally about the world must travel to a goal location using bounded computation and memory at each step. Many algorithms have been proposed for this problem, and theoretical results have also been derived for the worst-case performance. Assuming sufficiently poor tie-breaking, among other conditions, we derive theoretical best-case bounds for reaching the goal using LRTA*, a canonical example of a real-time agent-centered heuristic search algorithm. We show that the number of steps required to reach the goal can grow asymptotically faster than the state space, resulting in a "scrubbing" when the agent repeatedly visits the same state. This theoretical result, supported by experimental data, encourages recent work in the field that uses novel tie-breaking schemas and/or perform different types of learning.

SoCS Conference 2013 Conference Paper

Finding Bounded Suboptimal Multi-Agent Path Planning Solutions Using Increasing Cost Tree Search (Extended Abstract)

• Faten Aljalaud
• Nathan R. Sturtevant

The Increasing Cost Tree Search (ICTS) algorithm is used to produce optimal solutions to the multi-agent path finding problem (MAPF). In this problem, multiple agents are trying to reach their goals without conflicting with each other, while minimizing the total cost of the paths. ICTS has been shown to be very effective in finding optimal solutions. In this paper we consider the problem of finding solutions with bounded suboptimality by changing the order in which ICTS searches its increasing cost tree. With a variety of strategies, we are unable to consistently and significantly reduce the cost of ICTS. Further experimentation suggests why significantly more work is needed to modify ICTS to find suboptimal solutions.

IJCAI Conference 2013 Conference Paper

Minimizing Writes in Parallel External Memory Search

• Nathan R. Sturtevant
• Matthew J. Rutherford

Recent research on external-memory search has shown that disks can be effectively used as secondary storage when performing large breadthfirst searches. We introduce the Write-Minimizing Breadth-First Search (WMBFS) algorithm which is designed to minimize the number of writes performed in an external-memory BFS. WMBFS is also designed to store the results of the BFS for later use. We present the results of a BFS on a single-agent version of Chinese Checkers and the Rubik’s Cube edge cubes, state spaces with about 1 trillion states each. In evaluating against a comparable approach, WMBFS reduces the I/O for the Chinese Checkers domain by over an order of magnitude. In Rubik’s cube, in addition to reducing I/O, the search is also 3. 5 times faster. Analysis of the results suggests the machine and state-space properties necessary for WMBFS to perform well.

SoCS Conference 2013 Conference Paper

Online Detection of Dead States in Real-Time Agent-Centered Search

• Guni Sharon
• Nathan R. Sturtevant
• Ariel Felner

In this paper we introduce techniques for state pruning atruntime in a priori unknown domains. We describe how toidentify states that can be deleted from the state-space whenlooking for both optimal and suboptimal solutions. We discussgeneral graphs and special cases like 8-connected grids. Experimental results show a speed up of up to an order ofmagnitude when applying our techniques on real-time agentcenteredsearch problems.

SoCS Conference 2013 Conference Paper

Optimal-Generation Variants of EPEA

• Meir Goldenberg
• Ariel Felner
• Nathan R. Sturtevant
• Robert C. Holte
• Jonathan Schaeffer 0001

It is known that A* is optimal with respect to the expanded nodes (Dechter and Pearl 1985) (D&P). The exact meaning of this optimality varies depending on the class of algorithms and instances over which A* is claimed to be optimal. A* does not provide any optimality guarantees with respect to the generated nodes. However, such guarantees may be critical for optimally solving instances of domains with a large branching factor. In this paper, we introduce two new variants of the recently introduced Enhanced Partial Expansion A* algorithm (EPEA*) (Felner et al. 2012). We leverage the results of D&P to show that these variants possess optimality with respect to the generated nodes in much the same sense as A* possesses optimality with respect to the expanded nodes. The results in this paper are theoretical. A study of the practical performance of the new variants is beyond the scope of this paper.

ICAPS Conference 2013 Conference Paper

Using Alternative Suboptimality Bounds in Heuristic Search

• Richard Valenzano
• Shahab Jabbari Arfaee
• Jordan Tyler Thayer
• Roni Stern
• Nathan R. Sturtevant

Most bounded suboptimal algorithms in the search literature have been developed so as to be epsilon-admissible. This means that the solutions found by these algorithms are guaranteed to be no more than a factor of (1 + ε) greater than optimal. However, this is not the only possible form of suboptimality bounding. For example, another possible suboptimality guarantee is that of additive bounding, which requires that the cost of the solution found is no more than the cost of the optimal solution plus a constant gamma. In this work, we consider the problem of developing algorithms so as to satisfy a given, and arbitrary, suboptimality requirement. To do so, we develop a theoretical framework which can be used to construct algorithms for a large class of possible suboptimality paradigms. We then use the framework to develop additively bounded algorithms, and show that in practice these new algorithms effectively trade-off additive solution suboptimality for runtime.

ECAI Conference 2012 Conference Paper

ArvandHerd: Parallel Planning with a Portfolio

• Richard Valenzano
• Hootan Nakhost
• Martin Müller 0003
• Jonathan Schaeffer 0001
• Nathan R. Sturtevant

ArvandHerd is a parallel planner that won the multicore sequential satisficing track of the 2011 International Planning Competition (IPC 2011). It assigns processors to run different members of an algorithm portfolio which contains several configurations of each of two different planners: LAMA-2008 and Arvand. In this paper, we demonstrate that simple techniques for using different planner configurations can significantly improve the coverage of both of these planners. We then show that these two planners, when using multiple configurations, can be combined to construct a high performance parallel planner. In particular, we will show that ArvandHerd can solve more IPC benchmark problems than even a perfect parallelization of LAMA-2011, which won the satisficing track at IPC 2011. We will also show that the coverage of ArvandHerd can be further improved if LAMA-2008 is replaced by LAMA-2011 in the portfolio.

SoCS Conference 2012 Conference Paper

Conflict-Based Search for Optimal Multi-Agent Path Finding

• Guni Sharon
• Roni Stern
• Ariel Felner
• Nathan R. Sturtevant

We present a new two-level search algorithm for optimal multi-agent path finding called Conflict Based Search (CBS). At the high level, a search is performed on a tree based on conflicts between agents. At the low level, a search is performed only for a single agent at a time. Experimental results on various problems shows a speedup of up to a full order of magnitude over previous approaches.

SoCS Conference 2012 Conference Paper

Meta-Agent Conflict-Based Search For Optimal Multi-Agent Path Finding

• Guni Sharon
• Roni Stern
• Ariel Felner
• Nathan R. Sturtevant

The task in the multi-agent path finding problem (MAPF) isto find paths for multiple agents, each with a different startand goal position, such that agents do not collide. It is possibleto solve this problem optimally with algorithms that arebased on the A* algorithm. Recently, we proposed an alternativealgorithm called Conflict-Based Search (CBS) (Sharonet al. 2012), which was shown to outperform the A*-basedalgorithms in some cases. CBS is a two-level algorithm. Atthe high level, a search is performed on a tree based on conflictsbetween agents. At the low level, a search is performedonly for a single agent at a time. While in some cases CBSis very efficient, in other cases it is worse than A*-based algorithms. This paper focuses on the latter case by generalizingCBS to Meta-Agent CBS (MA-CBS). The main idea isto couple groups of agents into meta-agents if the number ofinternal conflicts between them exceeds a given bound. MACBSacts as a framework that can run on top of any completeMAPF solver. We analyze our new approach and provideexperimental results demonstrating that it outperforms basicCBS and other A*-based optimal solvers in many cases.

SoCS Conference 2012 Conference Paper

Partial-Expansion A* with Selective Node Generation

• Ariel Felner
• Meir Goldenberg
• Guni Sharon
• Roni Stern
• Tal Beja
• Nathan R. Sturtevant
• Robert C. Holte
• Jonathan Schaeffer 0001

A* is often described as being 'optimal, ' in that it expands the minimum number of unique nodes. But, A* may generate many extra nodes which are never expanded. This is a performance loss, especially when the branching factor is large. Partial Expansion A* (PEA*) addresses this problem when expanding a node, n, by generating all the children of n but only storing children with the same f-cost as n. We introduce an enhanced version of PEA* (EPEA*). Given a priori domain knowledge, EPEA* only generates the children with the same f-cost as the parent. State-of-the-art results were obtained for a number of domains. Drawbacks of EPEA* are also discussed. A full version of this paper appears in the proceedings of AAAI-2012

SoCS Conference 2011 Conference Paper

A Polynomial-Time Algorithm for Non-Optimal Multi-Agent Pathfinding

• Mokhtar M. Khorshid
• Robert C. Holte
• Nathan R. Sturtevant

Multi-agent pathfinding, where multiple agents must travel to their goal locations without getting stuck, has been studied in both theoretical and practical contexts, with a variety of both optimal and sub-optimal algorithms proposed for solving problems. Recent work has shown that there is a linear-time check for whether a multi-agent pathfinding problem can be solved in a tree, however this was not used to actually produce solutions. In this paper we provide a constructive proof of how to solve multi-agent pathfinding problems in a tree that culminates in a novel approach that we call the tree-based agent swapping strategy (TASS). Experimental results showed that TASS can find solutions to the multi-agent pathfinding problem on a highly crowded tree with 1000 nodes and 996 agents in less than 8 seconds. These results are far more efficient and general than existing work, suggesting that TASS is a productive line of study for multi-agent pathfinding.

SoCS Conference 2011 Conference Paper

Distance Learning in Agent-Centered Heuristic Search

• Nathan R. Sturtevant

Real-time agent-centric algorithms have been used for learning and solving problems since the introduction of the LRTA* algorithm in 1990. In this time period, numerous variants have been produced, however, they have generally followed the same approach in varying parameters to learn a heuristic which estimates the remaining cost to arrive at a goal state. This short paper discusses the history and implications of learning g-costs, both alone and in conjunction with learning h-costs as an introduction to the new f-LRTA* algorithm which learns both.

SoCS Conference 2011 Conference Paper

The Compressed Differential Heuristic

• Meir Goldenberg
• Nathan R. Sturtevant
• Ariel Felner
• Jonathan Schaeffer 0001

The differential heuristic (DH) is an effective memory-based heuristic for explicit state spaces. In this paper, we aim to improve its performance and memory usage. We introduce a compression method for DHs which stores only a portion of the original uncompressed DH, while preserving enough information to enable efficient search. Compressed DHs (CDH) can be tuned to fit any size of memory, even smaller than the size of the state space. Experimental results across different domains show that, for a given amount of memory, a CDH significantly outperforms an uncompress

SoCS Conference 2010 Conference Paper

Portal-Based True-Distance Heuristics for Path Finding

• Meir Goldenberg
• Ariel Felner
• Nathan R. Sturtevant
• Jonathan Schaeffer 0001

True distance memory-based heuristics (TDHs) were recently introduced as a way to obtain admissible heuristics for explicit state spaces. In this paper, we introduce a new TDH, the portal-based heuristic. The domain is partitioned into regions and portals between regions are identified. True distances between all pairs of portals are stored and used to obtain admissible heuristics throughout the search. We introduce an A*-based algorithm that takes advantage of the special properties of the new heuristic. We study the advantages and limitations of the new heuristic. Our experimental results show large performance improvements over previously-reported TDHs for commonly used classes of maps.

SoCS Conference 2010 Conference Paper

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

• Richard Valenzano
• Nathan R. Sturtevant
• Jonathan Schaeffer 0001
• Karen Buro
• Akihiro Kishimoto

Many search algorithms have parameters that need to be tuned to get the best performance. Typically, the parameters are tuned offline, resulting in a generic setting that is supposed to be effective on all problem instances. For suboptimal single-agent search, problem-instance-specific parameter settings can result in substantially reduced search effort. We consider the use of dovetailing as a way to take advantage of this fact. Dovetailing is a procedure that performs search with multiple parameter settings simultaneously. Dovetailing is shown to improve the search speed of weighted IDA* by several orders of magnitude and to generally enhance the performance of weighted RBFS. This procedure is trivially parallelizable and is shown to be an effective form of parallelization for WA* and BULB. In particular, using WA* with parallel dovetailing yields good speedups in the sliding-tile puzzle domain, and increases the number of problems solved when used in an automated planning system.

ICAPS Conference 2010 Conference Paper

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

• Richard Valenzano
• Nathan R. Sturtevant
• Jonathan Schaeffer 0001
• Karen Buro
• Akihiro Kishimoto

Many search algorithms have parameters that need to be tuned to get the best performance. Typically, the parameters are tuned offline, resulting in a generic setting that is supposed to be effective on all problem instances. For suboptimal single-agent search, problem-instance-specific parameter settings can result in substantially reduced search effort. We consider the use of dovetailing as a way to take advantage of this fact. Dovetailing is a procedure that performs search with multiple parameter settings simultaneously. Dovetailing is shown to improve the search speed of weighted IDA* by several orders of magnitude and to generally enhance the performance of weighted RBFS. This procedure is trivially parallelizable and is shown to be an effective form of parallelization for WA* and BULB. In particular, using WA* with parallel dovetailing yields good speedups in the sliding-tile puzzle domain, and increases the number of problems solved when used in an automated planning system.

SoCS Conference 2010 Conference Paper

Single-Frontier Bidirectional Search

• Carsten Moldenhauer
• Ariel Felner
• Nathan R. Sturtevant
• Jonathan Schaeffer 0001

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.

IJCAI Conference 2009 Conference Paper

• Zhifu Zhang
• Nathan R. Sturtevant
• Robert Holte
• Jonathan Schaeffer
• Ariel Felner

Early research in heuristic search discovered that using inconsistent heuristics with A* could result in an exponential increase in the number of node expansions. As a result, the use of inconsistent heuristics has largely disappeared from practice. Recently, inconsistent heuristics have been shown to be effective in IDA*, especially when applying the bidirectional pathmax (BPMX) enhancement. This paper presents new worst-case complexity analysis of A*’s behavior with inconsistent heuristics, discusses how BPMX can be used with A*, and gives experimental results justifying the use of inconsistent heuristics in A* searches.

IJCAI Conference 2009 Conference Paper

• Carsten Moldenhauer
• Nathan R. Sturtevant

Moving target search (MTS) or the game of cops and robbers has a broad field of application reaching from law enforcement to computer games. Within the recent years research has focused on computing move policies for one or multiple pursuers (cops). The present work motivates to extend this perspective to both sides, thus developing algorithms for the target (robber). We investigate the game with perfect information for both players and propose two new methods, named TrailMax and Dynamic Abstract Trailmax, to compute move policies for the target. Experiments are conducted by simulating games on 20 maps of the commercial computer game Baldur’s Gate and measuring survival time and computational complexity. We test seven algorithms: Cover, Dynamic Abstract Minimax, minimax, hill climbing with distance heuristic, a random beacon algorithm, TrailMax and DA- TrailMax. Analysis shows that our methods outperform all the other algorithms in quality, achieving up to 98% optimality, while meeting modern computer game computation time constraints.

IJCAI Conference 2009 Conference Paper

• Nathan R. Sturtevant
• Ariel Felner
• Max Barrer
• Jonathan Schaeffer
• Neil Burch

ICML Conference 2009 Conference Paper

Learning when to stop thinking and do something!

• Barnabás Póczos
• Yasin Abbasi-Yadkori
• Csaba Szepesvári
• Russell Greiner
• Nathan R. Sturtevant

AAAI Conference 2006 Conference Paper

Prob-Maxn: Playing N-Player Games with Opponent Models

• Nathan R. Sturtevant

Much of the work on opponent modeling for game tree search has been unsuccessful. In two-player, zero-sum games, the gains from opponent modeling are often outweighed by the cost of modeling. Opponent modeling solutions simply cannot search as deep as the highly optimized minimax search with alpha-beta pruning. Recent work has begun to look at the need for opponent modeling in n-player or generalsum games. We introduce a probabilistic approach to opponent modeling in n-player games called prob-maxn, which can robustly adapt to unknown opponents. We implement prob-maxn in the game of Spades, showing that prob-maxn is highly effective in practice, beating out the maxn and softmaxn algorithms when faced with unknown opponents.