6 citations · 15 across the 16 of their papers we have counts for
21 papers
Belief Embedding Tree Search
Christopher Solinas, Radovan Haluška, Martin Schmid +3
Beliefs in a Partially Observable Markov Decision Process (POMDP) are posterior distributions over the hidden state given the agent's history of actions and observations. They summ…
Neural Bayesian Filtering
Christopher Solinas, Radovan Haluska, David Sychrovsky +6
Sequential estimation under partial observability requires tracking beliefs that may be high-dimensional, multimodal, and non-Gaussian. Classical Bayesian filters generalize zero-s…
Online Submission and Evaluation System Design for Competition Operations
Zhe Chen, Daniel Harabor, Ryan Hechnenberger +1
Research communities have developed benchmark datasets across domains to compare the performance of algorithms and techniques However, tracking the progress in these research areas…
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 b…
Approximating Nash Equilibria in General-Sum Games via Meta-Learning
David Sychrovský, Christopher Solinas, Revan MacQueen +4
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. Whi…
Parallelizing Multi-objective A* Search
Saman Ahmadi, Nathan R. Sturtevant, Andrea Raith +2
The Multi-objective Shortest Path (MOSP) problem is a classic network optimization problem that aims to find all Pareto-optimal paths between two points in a graph with multiple ed…
On Parallel External-Memory Bidirectional Search
Lior Siag, Shahaf S. Shperberg, Ariel Felner +1
Parallelization and External Memory (PEM) techniques have significantly enhanced the capabilities of search algorithms when solving large-scale problems. Previous research on PEM h…
Set-Based Retrograde Analysis: Precomputing the Solution to 24-card Bridge Double Dummy Deals
Isaac Stone, Nathan R. Sturtevant, Jonathan Schaeffer
Retrograde analysis is used in game-playing programs to solve states at the end of a game, working backwards toward the start of the game. The algorithm iterates through and comput…
On the Completeness of Conflict-Based Search: Temporally-Relative Duplicate Pruning
Thayne T Walker, Nathan R Sturtevant
Conflict-Based Search (CBS) algorithm for the multi-agent pathfinding (MAPF) problem is that it is incomplete for problems which have no solution; if no mitigating procedure is run…
Transformer Based Planning in the Observation Space with Applications to Trick Taking Card Games
Douglas Rebstock, Christopher Solinas, Nathan R. Sturtevant +1
Traditional search algorithms have issues when applied to games of imperfect information where the number of possible underlying states and trajectories are very large. This challe…
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 due to various movement models. In…
History Filtering in Imperfect Information Games: Algorithms and Complexity
Christopher Solinas, Douglas Rebstock, Nathan R. Sturtevant +1
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…
The Definition-Context-Purpose Paradigm and Other Insights from Industry Professionals About the Definition of a Quest
Kristen K. Yu, Matthew Guzdial, Nathan R. Sturtevant
Among academic communities there is no single agreed upon definition of a quest. The industry perspective on this topic is also largely unknown. Thus, thee purpose of this paper is…
The Impact of Visualizing Design Gradients for Human Designers
Matthew Guzdial, Nathan Sturtevant, Carolyn Yang
Mixed-initiative Procedural Content Generation (PCG) refers to tools or systems in which a human designer works with an algorithm to produce game content. This area of research rem…
Collision Detection for Agents in Multi-Agent Pathfinding
Thayne T. Walker, Nathan R. Sturtevant
Recent work on the multi-agent pathfinding problem (MAPF) has begun to study agents with motion that is more complex, for example, with non-unit action durations and kinematic cons…
Iterative Budgeted Exponential Search
Malte Helmert, Tor Lattimore, Levi H. S. Lelis +2
We tackle two long-standing problems related to re-expansions in heuristic search algorithms. For graph search, A* can require expansions, where is the number of sta…
Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks
Roni Stern, Nathan Sturtevant, Ariel Felner +9
The MAPF problem 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 witho…
Exponential-Binary State-Space Search
Nathan Sturtevant, Malte Helmert
Iterative deepening search is used in applications where the best cost bound for state-space search is unknown. The iterative deepening process is used to avoid overshooting the ap…
Policy Based Inference in Trick-Taking Card Games
Douglas Rebstock, Christopher Solinas, Michael Buro +1
Trick-taking card games feature a large amount of private information that slowly gets revealed through a long sequence of actions. This makes the number of histories exponentially…
Front-to-End Bidirectional Heuristic Search with Near-Optimal Node Expansions
Jingwei Chen, Robert C. Holte, Sandra Zilles +1
It is well-known that any admissible unidirectional heuristic search algorithm must expand all states whose -value is smaller than the optimal solution cost when using a consist…
Monte Carlo Tree Search with Heuristic Evaluations using Implicit Minimax Backups
Marc Lanctot, Mark H. M. Winands, Tom Pepels +1
Monte Carlo Tree Search (MCTS) has improved the performance of game engines in domains such as Go, Hex, and general game playing. MCTS has been shown to outperform classic alpha-be…