Nathan Sturtevant

AIJ Journal 2023 Journal Article

Conflict-tolerant and conflict-free multi-agent meeting

• Dor Atzmon
• Ariel Felner
• Jiaoyang Li
• Shahaf Shperberg
• Nathan Sturtevant
• Sven Koenig

IJCAI Conference 2023 Conference Paper

Front-to-End Bidirectional Heuristic Search with Consistent Heuristics: Enumerating and Evaluating Algorithms and Bounds

• Lior Siag
• Shahaf Shperberg
• Ariel Felner
• Nathan Sturtevant

Recent research on bidirectional heuristic search (BiHS) is based on the must-expand pairs theory (MEP theory), which describes which pairs of nodes must be expanded during the search to guarantee the optimality of solutions. A separate line of research in BiHS has proposed algorithms that use lower bounds that are derived from consistent heuristics during search. This paper links these two directions, providing a comprehensive unifying view and showing that both existing and novel algorithms can be derived from the MEP theory. An extended set of bounds is formulated, encompassing both previously discovered bounds and new ones. Finally, the bounds are empirically evaluated by their contribution to the efficiency of the search

NeurIPS Conference 2023 Conference Paper

History Filtering in Imperfect Information Games: Algorithms and Complexity

• Christopher Solinas
• Doug Rebstock
• Nathan Sturtevant
• Michael Buro

Historically applied exclusively to perfect information games, depth-limited search with value functions has been key to recent advances in AI for imperfect information games. Most prominent approaches with strong theoretical guarantees require subgame decomposition - a process in which a subgame is computed from public information and player beliefs. However, subgame decomposition can itself require non-trivial computations, and its tractability depends on the existence of efficient algorithms for either full enumeration or generation of the histories that form the root of the subgame. Despite this, no formal analysis of the tractability of such computations has been established in prior work, and application domains have often consisted of games, such as poker, for which enumeration is trivial on modern hardware. Applying these ideas to more complex domains requires understanding their cost. In this work, we introduce and analyze the computational aspects and tractability of filtering histories for subgame decomposition. We show that constructing a single history from the root of the subgame is generally intractable, and then provide a necessary and sufficient condition for efficient enumeration. We also introduce a novel Markov Chain Monte Carlo-based generation algorithm for trick-taking card games - a domain where enumeration is often prohibitively expensive. Our experiments demonstrate its improved scalability in the trick-taking card game Oh Hell. These contributions clarify when and how depth-limited search via subgame decomposition can be an effective tool for sequential decision-making in imperfect information settings.

IJCAI Conference 2020 Conference Paper

Bidirectional Heuristic Search: Expanding Nodes by a Lower Bound

• Shahaf Shperberg
• Ariel Felner
• Nathan Sturtevant
• Eyal Shimony
• Avi Hayoun

Recent work on bidirectional search defined a lower bound on costs of paths between pairs of nodes, and introduced a new algorithm, NBS, which is based on this bound. Building on these results, we introduce DVCBS, a new algorithm that aims to to further reduce the number of expansions. Generalizing beyond specific algorithms, we then propose a method for enhancing heuristics by propagating such lower bounds (lb-propagation) between frontiers. This lb-propagation can be used in existing algorithms, often improving their performance, as well as making them "well behaved".

IJCAI Conference 2020 Conference Paper

Multi-Directional Heuristic Search

• Dor Atzmon
• Jiaoyang Li
• Ariel Felner
• Eliran Nachmani
• Shahaf Shperberg
• Nathan Sturtevant
• Sven Koenig

In the Multi-Agent Meeting problem (MAM), 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 Heuristic 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 an optimal meeting location for multiple agents. Several admissible heuristics are proposed, and experiments demonstrate the benefits of MM*.

AAAI Conference 2018 Conference Paper

A Brief History and Recent Achievements in Bidirectional Search

• Nathan Sturtevant
• Ariel Felner

The state of the art in bidirectional search has changed significantly a very short time period; we now can answer questions about unidirectional and bidirectional search that until very recently we were unable to answer. This paper is designed to provide an accessible overview of the recent research in bidirectional search in the context of the broader efforts over the last 50 years. We give particular attention to new theoretical results and the algorithms they inspire for optimal and nearoptimal node expansions when finding a shortest path.

AAMAS Conference 2018 Conference Paper

Rapid Randomized Restarts for Multi-Agent Path Finding: Preliminary Results

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

Multi-Agent Path Finding (MAPF) is an NP-hard problem with many real-world applications. However, existing MAPF solvers are deterministic and perform poorly on MAPF instances where many agents interfere with each other in a small region of space. In this paper, we enhance MAPF solvers with randomization and observe that their runtimes can exhibit heavy-tailed distributions. This insight leads us to develop simple Rapid Randomized Restart (RRR) strategies with the intuition that multiple short runs will have a better chance of solving such MAPF instances than one long run with the same runtime limit. Our contribution is to show experimentally that the same RRR strategy indeed boosts the performance of two state-of-the-art MAPF solvers, namely M* and ECBS.

AAAI Conference 2017 Conference Paper

The State of the AIIDE Conference in 2017

• Nathan Sturtevant
• Brian Magerko

This abstract looks at the state of the Artificial Intelligence and Interactive Digital Entertainment Conference (AIIDE), describing some of the changes in the field and areas of focus for current work.

AAAI Conference 2017 Conference Paper

Value Compression of Pattern Databases

• Nathan Sturtevant
• Ariel Felner
• Malte Helmert

One common pattern database compression technique is to merge adjacent database entries and store the minimum of merged entries to maintain heuristic admissibility. In this paper we propose a compression technique that preserves every entry, but reduces the number of bits used to store each entry, therefore limiting the values that can be represented. Even when this technique throws away low values in the heuristic, it can still have better performance than the traditional approach. We develop a theoretical basis for selecting which values to keep and show improved performance in both unidirectional and bidirectional search.

AAAI Conference 2016 Conference Paper

Bidirectional Search That Is Guaranteed to Meet in the Middle

• Robert Holte
• Ariel Felner
• Guni Sharon
• Nathan Sturtevant

We present MM, the first bidirectional heuristic search algorithm whose forward and backward searches are guaranteed to “meet in the middle”, i. e. never expand a node beyond the solution midpoint. We also present a novel framework for comparing MM, A*, and brute-force search, and identify conditions favoring each algorithm. Finally, we present experimental results that support our theoretical analysis.

AAAI Conference 2016 Conference Paper

Combining Bounding Boxes and JPS to Prune Grid Pathfinding

• Steve Rabin
• Nathan Sturtevant

Pathfinding is a common task across many domains and platforms, whether in games, robotics, or road maps. Given the breadth of domains, there are also a wide variety of representations used for pathfinding, and there are many techniques which have been shown to improve performance. In the last few years, the state-of-the-art in grid-based pathfinding has been significantly improved with domain-specific techniques such as Jump Point Search (JPS), Subgoal Graphs, and Compressed Path Databases. In this paper we look at a specific implementation of the general idea of Geometric Containers, showing that, while it is effective on grid maps, when combined with JPS+ it provides state-of-the-art performance.

AAAI Conference 2014 Conference Paper

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

• Guni Sharon
• Ariel Felner
• Nathan Sturtevant

In the Real-Time Agent-Centered Search (RTACS) problem, an agent has to arrive at a goal location while acting and reasoning in the physical world. Traditionally, RTACS problems are solved by propagating and updating heuristic values of states visited by the agent. In existing RTACS algorithms the agent may revisit each state many times causing the entire procedure to be quadratic in the state space. We study the Iterative Deepening (ID) approach for solving RTACS and introduce Exponential Deepening A* (EDA*), an RTACS algorithm where the threshold between successive Depth-First calls is increased exponentially. EDA* is proven to hold a worst case bound that is linear in the state space. Experimental results supporting this bound are presented and demonstrate up to 10x reduction over existing RTACS solvers wrt distance traveled, states expanded and CPU runtime.

AAAI Conference 2014 Conference Paper

Worst-Case Solution Quality Analysis When Not Re-Expanding Nodes in Best-First Search

• Richard Valenzano
• Nathan Sturtevant
• Jonathan Schaeffer

The use of inconsistent heuristics with A∗ can result in increased runtime due to the need to re-expand nodes. Poor performance can also be seen with Weighted A∗ if nodes are reexpanded. While the negative impact of re-expansions can often be minimized by setting these algorithms to never expand nodes more than once, the result can be a lower solution quality. In this paper, we formally show that the loss in solution quality can be bounded based on the amount of inconsistency along optimal solution paths. This bound holds regardless of whether the heuristic is admissible or inadmissible, though if the heuristic is admissible the bound can be used to show that not re-expanding nodes can have at most a quadratic impact on the quality of solutions found when using A∗. We then show that the bound is tight by describing a process for the construction of graphs for which a best-first search that does not re-expand nodes will find solutions whose quality is arbitrarily close to that given by the bound. Finally, we will use the bound to extend a known result regarding the solution quality of WA∗ when weighting a consistent heuristic, so that it also applies to other types of heuristic weighting.

IJCAI Conference 2013 Conference Paper

Subset Selection of Search Heuristics

• Chris Rayner
• Nathan Sturtevant
• Michael Bowling

Constructing a strong heuristic function is a central problem in heuristic search. A common approach is to combine a number of heuristics by maximizing over the values from each. If a limit is placed on this number, then a subset selection problem arises. We treat this as an optimization problem, and proceed by translating a natural loss function into a submodular and monotonic utility function under which greedy selection is guaranteed to be nearoptimal. We then extend this approach with a sampling scheme that retains provable optimality. Our empirical results show large improvements over existing methods, and give new insight into building heuristics for directed domains.

AAAI Conference 2012 Conference Paper

Conflict-Based Search For Optimal Multi-Agent Path Finding

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

In the multi agent path finding problem (MAPF) paths should be found for several agents, each with a different start and goal position such that agents do not collide. Previous optimal solvers applied global A*-based searches. We present a new search algorithm called Conflict Based Search (CBS). CBS is a two-level algorithm. 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. In many cases this reformulation enables CBS to examine fewer states than A* while still maintaining optimality. We analyze CBS and show its benefits and drawbacks. Experimental results on various problems shows a speedup of up to a full order of magnitude over previous approaches.

AAAI Conference 2012 Conference Paper

Heuristic Search Comes of Age

• Nathan Sturtevant
• Ariel Felner
• Maxim Likhachev
• Wheeler Ruml

In looking back on the last five to ten years of work in heuristic search a few trends emerge. First, there has been a broadening of research topics studied. Second, there has been a deepened understanding of the theoretical foundations of search. Third, and finally, there have been increased connections with work in other fields. This paper, corresponding to a AAAI 2012 invited talk on recent work in heuristic search, highlights these trends in a number of areas of heuristic search. It is our opinion that the sum of these trends reflects the growth in the field and the fact that heuristic search has come of age.

AAAI Conference 2012 Conference Paper

Partial-Expansion A* with Selective Node Generation

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

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*) (Yoshizumi, Miura, and Ishida 2000) 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. n is re-inserted into the OPEN list, but with the f-cost of the next best child. This paper introduces an enhanced version of PEA* (EPEA*). Given a priori domain knowledge, EPEA* generates only the children with the same f-cost as the parent. EPEA* is generalized to its iterative-deepening variant, EPE-IDA*. For some domains, these algorithms yield substantial performance improvements. State-of-the-art results were obtained for the pancake puzzle and for some multi-agent pathfinding instances. Drawbacks of EPEA* are also discussed.

AAAI Conference 2011 Conference Paper

Euclidean Heuristic Optimization

• D. Chris Rayner
• Michael Bowling
• Nathan Sturtevant

We pose the problem of constructing good search heuristics as an optimization problem: minimizing the loss between the true distances and the heuristic estimates subject to admissibility and consistency constraints. For a well-motivated choice of loss function, we show performing this optimization is tractable. In fact, it corresponds to a recently proposed method for dimensionality reduction. We prove this optimization is guaranteed to produce admissible and consistent heuristics, generalizes and gives insight into differential heuristics, and show experimentally that it produces strong heuristics on problems from three distinct search domains.

AIJ Journal 2011 Journal Article

Inconsistent heuristics in theory and practice

• Ariel Felner
• Uzi Zahavi
• Robert Holte
• Jonathan Schaeffer
• Nathan Sturtevant
• Zhifu Zhang

AAAI Conference 2011 Conference Paper

The Compressed Differential Heuristic

• Meir Goldenberg
• Nathan Sturtevant
• Ariel Felner
• Jonathan Schaeffer

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) are flexible and can be tuned to fit any size of memory, even smaller than the size of the state space. Furthermore, CDHs can be built without the need to create and store the entire uncompressed DH. Experimental results across different domains show that, for a given amount of memory, a CDH significantly outperforms an uncompressed DH.

AAMAS Conference 2010 Conference Paper

On Learning In Agent-Centered Search

• Nathan Sturtevant
• Vadim Bulitko
• Yngvi Bjornsson

Since the introduction of the LRTA* algorithm, real-time heuristic search algorithms have generally followed the same plan-act-learn cycle: an agent plans one or several actions based on locallyavailable information, executes them and then updates (i. e. , learns)its heuristic function. Algorithm evaluation has almost exclusivelybeen empirical with the results often being domain-specific andincomparable across papers. Even when unification and cross-algorithm comparisons have been carried out in a single paper, there was no understanding of how efficient the learning processwas with respect to a theoretical optimum. This paper addresses theproblem with two primary contributions. First, we formally definea lower bound on the amount of learning any heuristic-learning algorithm needs to do. This bound is based on the notion of heuristicdepressions and allows us to have a domain-independent measureof learning efficiency across different algorithms. Second, usingthis measure we propose to learn "costs-so-far" ($g$-costs) insteadof "costs-to-go" ($h$-costs). This allows us to quickly identify redundant paths and dead-end states, thereby leading to asymptoticperformance improvement as well as 1-2 orders of magnitude convergence speed-ups in practice.

AAAI Conference 2010 Conference Paper

Single-Frontier Bidirectional Search

• Ariel Felner
• Carsten Moldenhauer
• Nathan Sturtevant
• Jonathan Schaeffer

On the surface, bidirectional search (BDS) is an attractive idea with the potential for significant asymptotic reductions in search effort. However, the results in practice often fall far short of expectations. We introduce a new bidirectional search algorithm, Single-Frontier Bidirectional Search (SF- BDS). Unlike traditional BDS which keeps two frontiers, SF- BDS uses a single frontier. Each node in the tree can be seen as an independent task of finding the shortest path between the current start and current goal. 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. Theoretical results give insights as to when this approach will work and experimental data validates the algorithm for a broad range of domains.

AAAI Conference 2010 Conference Paper

Understanding the Success of Perfect Information Monte Carlo Sampling in Game Tree Search

• Jeffrey Long
• Nathan Sturtevant
• Michael Buro
• Timothy Furtak

Perfect Information Monte Carlo (PIMC) search is a practical technique for playing imperfect information games that are too large to be optimally solved. Although PIMC search has been criticized in the past for its theoretical deficiencies, in practice it has often produced strong results in a variety of domains. In this paper, we set out to resolve this discrepancy. The contributions of the paper are twofold. First, we use synthetic game trees to identify game properties that result in strong or weak performance for PIMC search as compared to an optimal player. Second, we show how these properties can be detected in real games, and demonstrate that they do indeed appear to be good predictors of the strength of PIMC search. Thus, using the tools established in this paper, it should be possible to decide a priori whether PIMC search will be an effective approach to new and unexplored games.

IJCAI Conference 2009 Conference Paper

• Yngvi Björnsson
• Vadim Bulitko
• Nathan Sturtevant

Real-time heuristic search algorithms are used for planning by agents in situations where a constantbounded amount of deliberation time is required for each action regardless of the problem size. Such algorithms interleave their planning and execution to ensure real-time response. Furthermore, to guarantee completeness, they typically store improved heuristic estimates for previously expanded states. Although subsequent planning steps can benefit from updated heuristic estimates, many of the same states are expanded over and over again. Here we propose a variant of the A* algorithm, Time- Bounded A* (TBA*), that guarantees real-time response. In the domain of path-finding on videogame maps TBA* expands an order of magnitude fewer states than traditional real-time search algorithms, while finding paths of comparable quality. It reaches the same level of performance as recent state-of-the-art real-time search algorithms but, unlike these, requires neither state-space abstractions nor pre-computed pattern databases.

IJCAI Conference 2009 Conference Paper

• Michael Buro
• Jeffrey R. Long
• Timothy Furtak
• Nathan Sturtevant

Skat is Germany’s national card game played by millions of players around the world. In this paper, we present the world’s first computer skat player that plays at the level of human experts. This performance is achieved by improving state evaluations using game data produced by human players and by using these state evaluations to perform inference on the unobserved hands of opposing players. Our results demonstrate the gains from adding inference to an imperfect information game player and show that training on data from average human players can result in expert-level playing strength.

AAMAS Conference 2008 Conference Paper

A new approach to cooperative pathfinding

• Renee Jansen
• Nathan Sturtevant

In the multi-agent pathfinding problem, groups of agents need to plan paths between their respective start and goal locations in a given environment, usually a two-dimensional map. Existing approaches to this problem include using static or dynamic information to help coordination. However, the resulting behaviour is not always desirable, in that too much information is hand-coded into the problem, agents take paths which look unintelligent, or because the agents collide and must re-plan frequently. We present a distributed approach in which agents share information about the direction in which they traveled when passing through each location. This information is then used to encourage agents passing through the same location to travel in the same direction as previous agents. In addition to this new approach, we present performance metrics for multi-agent path planning as well as experimental results for the new approach. These results indicate that the number of collisions between agents is reduced and that the visual fidelity is improved.

AAMAS Conference 2008 Conference Paper

Optimized Algorithms for Multi-Agent Routing

• Akihiro Kishimoto
• Nathan Sturtevant

Auction methods have been successfully used for coordinating teams of robots in the multi-robot routing problem, a representative domain for multi-agent coordination. Solutions to this problem typically use bids computed using the shortest distance between various locations on a map. But, the cost of this shortest-distance computation has not been considered in previous research. This paper presents a new auction-based algorithm, FastBid, that works to reduce the computational costs associated with bidding in the multirobot routing problem. We also analyze how a small modification in the bidding algorithm can reduce the computational load of the bidding process. Experiments demonstrate that FastBid not only scales much better than previous approaches, but does so with little or no loss in solution quality.

AAMAS Conference 2006 Conference Paper

Robust Game Play Against Unknown Opponents

• Nathan Sturtevant
• Michael Bowling

AAAI Conference 2005 Conference Paper

Partial Pathfinding Using Map Abstraction and Refinement

• Nathan Sturtevant

Classical search algorithms such as A* or IDA* are useful for computing optimal solutions in a single pass, which can then be executed. But in many domains agents either do not have the time to compute complete plans before acting, or should not spend the time to do so, due to the dynamic nature of the environment. Extensions to A* such as LRTA* address this problem by gradually learning an exact heuristic function, but the learning process is quite slow. In this paper we introduce Partial–Refinement A* (PRA*), which can fully interleave planning and acting through path abstraction and refinement. We demonstrate the effectiveness of PRA* in the domain of real–time strategy (RTS) games. In maps taken from popular RTS games, we show that PRA* is not only able to cleanly interleave planning and execution, but it is also able to do so with only minimal losses of optimality.

IJCAI Conference 2003 Conference Paper

Last-Branch and Speculative Pruning Algorithms for Max

• Nathan Sturtevant

Previous work in pruning algorithms for max" multi-player game trees has produced shallow pruning and alpha-beta branch-and-bound pruning. The effectiveness of these algorithms is dependant as much on the range of terminal values found in the game tree as on the ordering of nodes. We introduce last-branch and speculative pruning techniques which can prune any constantsum multi-player game tree. Their effectiveness depends only on node-ordering within the game tree. As b grows large, these algorithms will, in the best case, reduce the branching factor of a //player game from b to /; <n -,)/n. In Chinese Checkers these methods reduce average expansions at depth 6 from 1. 2 million to 100k nodes, and in Hearts and Spades they increase the average search depth by 1-3 ply.