Vadim Bulitko

SoCS Conference 2023 Conference Paper

Core Expansion in Optimization Crosswords

• Adi Botea
• Vadim Bulitko

In constraint optimization many problem instances remain challenging to current technology. We focus on the Romanian Crosswords Competition Problem. It is a challenging, NP-hard constraint optimization problem where state-of-the-art AI has been lagging significantly behind top human performance. We present an approach that first builds a core, a portion of the problem that will have a high contribution to the objective function. A core is grown into a seed, a partial solution with a subset of variables defined and instantiated. Seeds are further extended into full solutions. Our approach takes as input the size of a rectangular core to consider, and the locations of zero or more black cells inside the core. The results advance state-of-the-art substantially. We report a boost in the scores obtained, bringing our top solutions in the vicinity of top human entries.

SoCS Conference 2022 Conference Paper

Portability and Explainability of Synthesized Formula-based Heuristics

• Vadim Bulitko
• Shuwei Wang
• Justin Stevens 0001
• Levi H. S. Lelis

Heuristic search is a key component of automated planning and pathfinding. It is guided by a heuristic function which estimates remaining solution cost. Traditionally heuristic functions for pathfinding have been human-designed or pre-computed for a specific search graph. The former tend to be compact, human-readable but generic. The latter offer better guidance but require per-graph pre-computation and have a substantial memory cost. We aim to retain compactness and readability of human-designed heuristics and increase their performance. We adopt the recently published approach of representing heuristic functions as algebraic formulae and automatically synthesizing them for video-game maps. Whereas published work merely randomly sampled the space of formula-based heuristic functions, we implement and evaluate a parameterized synthesis algorithm that unifies and generalizes the stochastic sampling, simulated annealing and a basic genetic algorithm. We tune the parameters for better synthesis performance and then, using maps from multiple video games, show that heuristics synthesized for maps from one game still outperform the baseline search (A* with weighted Manhattan distance) on maps from a different game. We analyze a frequently synthesized formula and explain how, despite having a higher error than the Manhattan distance, it takes advantage of the structure in video-game pathfinding problems and speeds up A*.

SoCS Conference 2021 Conference Paper

Scaling Up Search with Partial Initial States in Optimization Crosswords

• Adi Botea
• Vadim Bulitko

Heuristic search remains a leading approach to difficult combinatorial optimization problems. Search algorithms can utilize pruning based on comparing a target score with an admissible (optimistic) estimate of the best score that can be achieved from a given state. If the former is larger they prune the state. However, when the target score is too high the search can fail by exhausting the space without finding a solution. In this paper we show that such failed searches can still be valuable. Specifically, best partial solutions encountered in such failed searches can often bear a high similarity to the corresponding part of a full high-quality or even optimal solution. Thus, a new search for a full solution, with a lower target score, can start with a best known partial solution, rather than starting from scratch. We demonstrate our ideas in a constraint optimization problem modelled on the Romanian Crosswords Competition, a challenging problem where humans perform much better than computers. Utilizing partial solutions produced by a failed search cuts down the running time of an existing state-of-the-art solver by orders of magnitude on competition-level crossword puzzle instances and allows to solve more instances.

SoCS Conference 2021 Conference Paper

Speeding Up Heuristic Function Synthesis via Extending the Formula Grammar

• Sergio Poo Hernandez
• Vadim Bulitko

Heuristic search algorithms have long been used in video-game AI for unit navigation and planning. The quality of the solution they produce depends substantially on the quality of the heuristic function they use. Recent work automatically synthesized human-readable heuristic functions for a given pathfinding map. This enables tailoring a heuristic to the map but is expensive since each map requires an independent synthesis run. In this paper we propose and evaluate re-using elements of heuristics synthesized for one map in synthesizing heuristics for another map. We do so by adding parts of a synthesized heuristic back to the grammar that defines the space of heuristic functions for the synthesis.

SoCS Conference 2019 Conference Paper

A Learning-Based Framework for Memory-Bounded Heuristic Search: First Results

• Carlos Hernández Ulloa
• Jorge A. Baier
• William Yeoh 0001
• Vadim Bulitko
• Sven Koenig

Many existing boundedly-suboptimal heuristic search algorithms are variants of best-first search. Due to memory limitations, these algorithms are unable to solve problems with extremely large search spaces. In this paper, we present a framework that allows best-first search algorithms to solve problems with such large search spaces given a (reasonable) memory bound while also preserving optimality guarantees in tree-structured search spaces. In our framework, a given algorithm is run several times. In each search episode, the algorithm expands up to a user-defined number of states. After each episode, unless the goal has been found, the heuristic values of the generated states are updated using a linear-time algorithm that preserves consistency in tree-structured search spaces. In subsequent search episodes, only the heuristic values of the states generated in the previous episode need to be kept in memory. We present experimental results where we plug A*, GBFS, and wA* into our framework to solve traveling salesman problems and compare them against benchmark linear-memory algorithms like DFBnB and wDFBnB.

IJCAI Conference 2017 Conference Paper

Online Bridged Pruning for Real-Time Search with Arbitrary Lookaheads

• Carlos Hernandez
• Adi Botea
• Jorge A. Baier
• Vadim Bulitko

Real-time search algorithms are relevant to time-sensitive decision-making domains such as video games and robotics. In such settings, the agent is required to decide on each action under a constant time bound, regardless of the search space size. Despite recent progress, poor-quality solutions can be produced mainly due to state re-visitation. Different techniques have been developed to reduce such a re-visitation with state pruning showing promise. In this paper, we propose a novel pruning approach applicable to the wide class of real-time search algorithms. Given a local search space of arbitrary size, our technique aggressively prunes away all states in its interior, possibly adding new edges to maintain the connectivity of the search space frontier. An experimental evaluation shows that our pruning often improves the performance of a base real-time search algorithm by over an order of magnitude. This allows our implemented system to outperform state-of-the-art real-time search algorithms used in the evaluation.

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.

SoCS Conference 2016 Conference Paper

Searching for Real-Time Heuristic Search Algorithms

• Vadim Bulitko

Heuristic search is a core area of Artificial Intelligence with applications to planning, scheduling and game playing. Real-time heuristic search applies to search problems where plan execution needs to start before a complete solution can be computed. Since the inception of real-time heuristic search in the early 1990s a great number of algorithms have been proposed and evaluated. In this paper we break them down into building blocks and conduct a search in the space of such building blocks. Even simple tabulated and iterative searches find new real-time heuristic search algorithms outperforming manually crafted contemporary algorithms.

SoCS Conference 2016 Conference Paper

Weighted Lateral Learning in Real-Time Heuristic Search

• Vadim Bulitko
• Alexander Sampley

Real-time heuristic search models an autonomous agent solving a search task. The agent operates in a real-time setting by interleaving local planning, learning and move execution. In this paper we propose a simple parametric algorithm that combines weighting with learning from multiple neighbors. Doing so breaks heuristic admissibility but allows the agent to escape heuristic depressions more quickly. We prove completeness of the algorithm and empirically compare it to several competitors more than twenty years apart. In a large-scale evaluation the new algorithm found better solutions than the recent algorithms, despite not learning additional information that they do. Finally, we study robustness of the algorithms to noise in the heuristic function — a desirable property in a physical implementation of real-time heuristic search. The new algorithm outperforms its contemporaries.

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.

AAAI Conference 2012 Conference Paper

Interactive Narrative: A Novel Application of Artificial Intelligence for Computer Games

• Mark Riedl
• Vadim Bulitko

AAAI Conference 2011 Conference Paper

Extending the Applications of Recent Real-Time Heuristic Search

• Daniel Huntley
• Vadim Bulitko

Real-time heuristic search algorithms that precompute search space-specific databases have demonstrated exceptional performance in video-game pathfinding. We discuss the first steps towards extending these algorithms to other search spaces that also benefit from the real-time property. We present our initial progress in characterizing the performance of current algorithms based on the features of a search space, and discuss future directions of this research.

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.

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.

UAI Conference 2008 Conference Paper

Speeding Up Planning in Markov Decision Processes via Automatically Constructed Abstraction

• Alejandro Isaza
• Csaba Szepesvári
• Vadim Bulitko
• Russell Greiner

In this paper, we consider planning in stochastic shortest path (SSP) problems, a subclass of Markov Decision Problems (MDP). We focus on medium-size problems whose state space can be fully enumerated. This problem has numerous important applications, such as navigation and planning under uncertainty. We propose a new approach for constructing a multi-level hierarchy of progressively simpler abstractions of the original problem. Once computed, the hierarchy can be used to speed up planning by first finding a policy for the most abstract level and then recursively refining it into a solution to the original problem. This approach is fully automated and delivers a speed-up of two orders of magnitude over a state-of-the-art MDP solver on sample problems while returning near-optimal solutions. We also prove theoretical bounds on the loss of solution optimality resulting from the use of abstractions.

ECAI Conference 2008 Conference Paper

Thinking Too Much: Pathology in Pathfinding

• Mitja Lustrek
• Vadim Bulitko

IJCAI Conference 2007 Conference Paper

• Brian Tanner
• Vadim Bulitko
• Anna Koop
• Cosmin Paduraru

This paper proposes a systematic approach of representing abstract features in terms of low-level, subjective state representations. We demonstrate that a mapping between the agent's predictive state representation and an abstract feature representation can be derived automatically from high-level training data supplied by the designer. Our empirical evaluation demonstrates that an experience-oriented state representation built around a single-bit sensor can represent useful abstract features such as "back against a wall, " "in a corner, " or "in a room". As a result, the agent gains virtual sensors that could be used by its control policy.

IJCAI Conference 2007 Conference Paper

• D. Chris Rayner
• Katherine Davison
• Vadim Bulitko
• Kenneth Anderson
• Jieshan Lu

Learning real-time search, which interleaves planning and acting, allows agents to learn from multiple trials and respond quickly. Such algorithms require no prior knowledge of the environment and can be deployed without pre-processing. We introduce Prioritized-LRTA* (P-LRTA*), a learning real-time search algorithm based on Prioritized Sweeping. P-LRTA* focuses learning on important areas of the search space, where the importance of a state is determined by the magnitude of the updates made to neighboring states. Empirical tests on path-planning in commercial game maps show a substantial learning speed-up over state-of-the-art real-time search algorithms.

ICAPS Conference 2007 Conference Paper

Dynamic Control in Path-Planning with Real-Time Heuristic Search

• Vadim Bulitko
• Yngvi Björnsson
• Mitja Lustrek
• Jonathan Schaeffer 0001
• Sverrir Sigmundarson

Real-time heuristic search methods, such as LRTA*, are used by situated agents in applications that require the amount of planning per action to be constant-bounded regardless of the problem size. LRTA* interleaves planning and execution, with a fixed search depth being used to achieve progress towards a fixed goal. Here we generalize the algorithm to allow for a dynamically changing search depth and a dynamically changing (sub-)goal. Evaluation in path-planning on video-game maps shows that the new algorithm significantly outperforms fixed-depth, fixed-goal LRTA*. The new algorithm can achieve the same quality solutions as LRTA*, but with nine times less computation, or use the same amount of computation, but produce four times better quality solutions. These extensions make real-time heuristic search a practical choice for path-planning in computer video-games.

AAAI Conference 2006 Conference Paper

Lookahead Pathology in Real-Time Path-Finding

• Vadim Bulitko

Path-finding tasks commonly require real-time response, which on large problems precludes the use of complete search methods such as A*. Incomplete single-agent search methods work similarly to minimax-based algorithms used in two-player games. They conduct a limited-depth lookahead search, i.e., expand a part of the space centered on the agent, and heuristically evaluate the distances from the frontier of the expanded space to the goal. Actions selected based on heuristic lookahead search are not necessarily optimal, but both in minimax search and in single-agent search it is generally believed that deeper lookahead increases the quality of decisions. Theoretical analyses of minimax have shown that the opposite is sometimes the case. This phenomenon has been termed the minimax pathology. Recently pathological behavior was observed in single-agent search as well. In this poster we investigate lookahead pathology in real-time path-finding on maps from commercial computer games. Pathology was experimentally observed in more than half of the 1,000 problems considered. This indicates that in single-agent search, pathological behavior is a practical issue - unlike in minimax search, where it seems to be mostly an artifact of the theoretical analyses.

AAAI Conference 2005 Conference Paper

Speeding Up Learning in Real-time Search via Automatic State Abstraction

• Vadim Bulitko

Situated agents which use learning real-time search are well poised to address challenges of real-time path-finding in robotic and computer game applications. They interleave a local lookahead search with movement execution, explore an initially unknown map, and converge to better paths over repeated experiences. In this paper, we first investigate how three known extensions of the most popular learning realtime search algorithm (LRTA*) influence its performance in a path-finding domain. Then, we combine automatic state abstraction with learning real-time search. Our scheme of dynamically building a state abstraction allows us to generalize updates to the heuristic function, thereby speeding up learning. The novel algorithm converges up to 80 times faster than LRTA* with only one fifth of the response time of A*.

IJCAI Conference 2003 Conference Paper

Lookahead Pathologies for Single Agent Search

• Vadim Bulitko
• Lihong Li
• Russ Greiner
• Ilya Levner

AIJ Journal 2003 Journal Article

Qualitative simulation of temporal concurrent processes using Time Interval Petri Nets

• Vadim Bulitko
• David C. Wilkins

This paper presents a formalism called Time Interval Petri Nets (TIPNs), which are designed to support a qualitative simulation of temporal concurrent processes. One of the key features of TIPNs is a uniform use of time intervals throughout the model. This enables a natural and efficient representation of temporal uncertainty in inputs, outputs, and intermediate states of the qualitative simulation. This is required because the exact time of key events, such as the start time of a fire crisis, is typically not known with certainty. Likewise, output conclusions of the qualitative simulation include earliest time and guaranteed time of key events that can be used by a decision maker to select the most appropriate action. Results are described of a TIPN-based qualitative simulator constructed in the domain of ship damage control. The simulator was created to replace an existing quantitative simulator which was too slow to support envisionment-based real-time decision making in this domain. The experimental results showed a speedup of four to five orders of magnitude which enables hyper-real time qualitative prediction of consequences of multiple competing actions. An automated shipboard damage control decision-making system incorporating a TIPN-based qualitative simulator achieved a 318% improvement over human subject matter experts in a large-scale simulated exercise of over 500 scenarios.