Multi-objective search (MOS) has emerged as a unifying framework for planning and decision-making problems where multiple, often conflicting, criteria must be balanced. While the problem has been studied for decades, recent years have seen renewed interest in the topic across AI applications such as robotics, transportation, and operations research, eflecting the reality that real-world systems rarely optimize a single measure. This paper surveys developments in MOS while highlighting cross-disciplinary opportunities, and outlines open challenges that define the emerging frontier of MOS research.

In Bi-Objective Search (BOS), the task is to compute the Pareto-optimal frontier of paths in a graph with two cost values per edge. Recent work introduced a general BOS framework that classifies search nodes and studies how ordering functions affect expansion order. In this paper, we continue this line of research. We further refine the classes of nodes and show that many nodes that were added to the open list and are classified as never-expand nodes still need to be extracted and further examined. Additionally, we introduce a method that enables constant-time dominance checks for the MIN and MAX ordering functions. This allows a practical usage of these ordering functions, as we demonstrate in our experimental section.

In multi-objective search, given a directed graph where each edge is annotated with multiple cost metrics, a start state, and a goal state. We are interested in computing the Pareto frontier, i.e., the set of all undominated paths from the start state to the goal state. Almost all multi-objective search algorithms use dominance checks to determine if a search node can be pruned. Since dominance checks are performed in the inner loop of the multi-objective search, they are the most time-consuming part of it. In this paper, we propose (1) two novel techniques to reduce duplicate dominance checks and (2) a simple data structure that enables more efficient dominance checks. Our experimental results show that combining our proposed techniques and data structure speeds up LTMOA*, a state-of-the-art multi-objective search algorithm, by up to an order of magnitude on road network instances.

In the multi-objective search problem, a typical task is to compute the Pareto frontier, i.e., the set of all undominated solutions. However, computing the entire Pareto frontier can be very time-consuming, and in practice, we often have limited deliberation time. Therefore, this paper focuses on solving the multi-objective search problem with anytime algorithms, which compute an initial approximate frontier quickly and then work to find more solutions until eventually finding the entire Pareto frontier. Existing work has investigated such anytime algorithms for problem instances with only two objectives. In this paper, we propose Anytime A*pex (A-A*pex), which works with any number of objectives. In each iteration of A-A*pex, it runs A*pex, a state-of-the-art approximate multi-objective search algorithm, to compute more solutions. From one iteration to the next, A-A*pex can either reuse its previous search effort or restart from scratch. Our experimental results show that an A-A*pex variant that mixes reusing its search effort and restarting from scratch yields the best runtime performance. We also show that A-A*pex often computes solutions that collectively approximate the Pareto frontier much better than the solutions found by state-of-the-art multi-objective search algorithms for short deliberation times.

Bi-objective search requires computing a Pareto solution set which contains a set of paths. In real-world applications, Pareto solution sets may contain several tens or even hundreds of solutions. For a human user trying to commit to just one of these paths, navigating through a large solution set may become overwhelming, which motivates the problem of computing small, good-quality subsets of Pareto frontiers. This document presents two main contributions. First, we provide a simple formalization of good-quality subsets of a Pareto solution set. For this, we use measure of richness which has been employed in the study of Population Dynamics. Second, we propose Chebyshev BOA*, a variant of BOA* to compute good-quality subset approximations.

In the multi-objective shortest-path problem (MOSP) we are interested in finding paths between two vertices of a graph while considering multiple objectives. A key procedure, which dominates the running time of many state-of-the-art (SOTA) algorithms for MOSP is set dominance checks (SDC). In SDC, we are given a set X of N-dimensional tuples and a new N-dimensional tuple p and we need to determine whether there exists a tuple q in X such that q dominates p (i.e., if every element in q is lower or equal than the corresponding element in p). In this work, we offer a simple-yet-effective approach to perform SDC in a parallel manner, an approach that can be seamlessly integrated with most SOTA MOSP algorithms. Specifically, by storing states in memory dimension-wise and not state-wise, we can exploit vectorized operations offered by ``Single Instruction/Multiple Data'' (SIMD) instructions to efficiently perform SDC on ubiquitous consumer CPUs. Integrating our approach for SDC allows to dramatically improve the runtime of existing MOSP algorithms.

In the multi-objective shortest-path problem we are interested in computing a path, or a set of paths that simultaneously balance multiple cost functions. This problem is important for a diverse range of applications such as transporting hazardous materials considering travel distance and risk. This family of problems is not new with results dating back to the 1970's. Nevertheless, the significant progress made in the field of heuristic search resulted in a new and growing interest in the sub-field of multi-objective search. Consequently, in this paper we review the fundamental problems and techniques common to most algorithms and provide a general overview of the field. We then continue to describe recent work with an emphasis on new challenges that emerged and the resulting research opportunities.

This extended abstract presents a theoretical analysis of node expansions in Multi-Objective Search. We define three categories of nodes, Must-Expand Nodes, Maybe-Expand Nodes, and Never-Expand Nodes. Our analysis establishes that regardless of the Ordering Function or Multi-Objective Search algorithm used, any Multi-Objective Search algorithm must expand all Must-Expand Nodes, some or none of Maybe-Expand Nodes, and none of Never-Expand Nodes. In addition, we conduct experimental evaluations of various Ordering Functions, revealing that they all expand the same number of nodes and compare their efficiency at finding solutions at various stages of the search.

In bi-objective graph search, each edge is annotated with a cost pair, where each cost corresponds to an objective to optimize. We are interested in finding all undominated paths from a given start state to a given goal state (called the Pareto front). Almost all existing works of bi-objective search use single-valued heuristics, which use one number for each objective, to estimate the cost between any given state and the goal state. However, single-valued heuristics cannot reflect the trade-offs between the two costs. On the other hand, multi-valued heuristics use a set of pairs to estimate the Pareto front between any given state and the goal state and are more informed than single-valued heuristics. However, they are rarely studied and have yet to be investigated in explicit state spaces by any existing work. In this paper, we are interested in using multi-valued heuristics to improve bi-objective search algorithms in explicit state spaces. More specifically, we generalize Differential Heuristics (DHs), a class of memory-based heuristics for single-objective search, to bi-objective search, resulting in Bi-objective Differential Heuristics (BO-DHs). We propose several techniques to reduce the memory usage and computational overhead of BO-DHs significantly. Our experimental results show that, with suggested improvement and tuned parameters, BO-DHs can reduce the node expansion and runtime of a bi-objective search algorithm by up to an order of magnitude, paving the way for more effective multi-valued heuristics.

In bi-objective search, we are given a graph in which each directed arc is associated with a pair of non-negative weights, and the objective is to find the Pareto-optimal solution set. Unfortunately, in many practical settings, this set is too large, and therefore its computation is very time-consuming. In addition, even though bi-objective search algorithms generate the Pareto set incrementally, they do so exhaustively. This means that early during search the solution set covers is not diverse, being concentrated in a small region of the solution set. To address this issue, we present a new approach to subset approximation of the solution set, that can be used as the basis for an anytime bi-objective search algorithm. Our approach transforms the given task into a target bi-objective search task using two real parameters. For each particular parameter setting, the solutions to the target task is a subset of the solution set of the original task. Depending on the parameters used, the solution set of the target task may be computed very quickly. This allows us to obtain, in challenging road map benchmarks, a rich variety of solutions in times that may be orders of magnitude smaller than the time needed to compute the solution set. We show that by running the algorithm with an appropriate sequence of parameters, we obtain a growing sequence of solutions that converges to the full solution set. We prove that our approach is correct and that Bi-Objective A* prunes at least as many nodes when run over the target task.

In bi-objective search, we are given a graph in which each directed arc is associated with a pair of non-negative weights, and the objective is to find the Pareto-optimal solution set. Unfortunately, in many practical settings, this set is too large, and therefore its computation is very time-consuming. In addition, even though bi-objective search algorithms generate the Pareto set incrementally, they do so exhaustively. This means that early during search the solution set covered is not diverse, being concentrated in a small region. To address this issue, we present a new approach to subset approximation of the solution set, that can be used as the basis for an anytime bi-objective search algorithm. Our approach transforms the given task into a target bi-objective search task using two real parameters. For each particular parameter setting, the solutions to the target task is a subset of the solution set of the original task. Depending on the parameters used, the solution set of the target task may be computed very quickly. This allows us to obtain, in challenging road map benchmarks, a rich variety of solutions in times that may be orders of magnitude smaller than the time needed to compute the solution set. We show that by running the algorithm with an appropriate sequence of parameters, we obtain a growing sequence of solutions that converges to the full solution set. We prove that our approach is correct and that Bi-Objective A* prunes at least as many nodes when run over the target task.

Learned heuristics, though inadmissible, can provide very good guidance for bounded-suboptimal search. Given a single search state s and a learned heuristic h, evaluating h(s) is typically very slow relative to expansion time, since state-of-the-art learned heuristics are implemented as neural networks. However, by using a Graphics Processing Unit (GPU), it is possible to compute heuristics using batched computation. Existing approaches to batched heuristic computation are specific to satisficing search and have not studied the problem in the context of bounded-suboptimal search. In this paper, we present K-Focal Search, a bounded suboptimal search algorithm that in each iteration expands K nodes from the FOCAL list and computes the learned heuristic values of the successors using a GPU. We experiment over the Rubik's Cube domain using DeepCubeA, a very effective inadmissible learned heuristic. Our results show that K-Focal Search benefits both from batched computation and from the diversity in the search introduced by its expansion strategy. Over standard FS, it improves runtime by a factor of 6, expansions by up to three orders of magnitude, and finds better solutions, keeping the theoretical guarantees of Focal Search.

There are many settings that extend the basic shortest path search problem. In Bounded-Cost Search, we are given a constant bound and the task is to find a solution within the bound. In Bi-Objective Search, each edge is associated with two costs (objectives) and the task is to minimize both objectives. In this paper, we combine both these settings into a new setting of Bounded-Cost Bi-Objective Search. We are given two bounds, one for each objective and the task is to find a solution within these bounds. We provide a scheme for normalizing the two objectives. We then introduce several algorithms for this new setting and compare them experimentally.

The Pareto-optimal frontier for a bi-objective search problem instance consists of all solutions that are not worse than any other solution in both objectives. The size of the Pareto-optimal frontier can be exponential in the size of the input graph, and hence finding it can be hard. Some existing works leverage a user-specified approximation factor epsilon to compute an approximate Pareto-optimal frontier that can be significantly smaller than the Pareto-optimal frontier. In this paper, we propose an anytime approximate bi-objective search algorithm, called Anytime Bi-Objective A*-epsilon (A-BOA*). A-BOA* is useful when deliberation time is limited. It first finds an approximate Pareto-optimal frontier quickly, iteratively improves it while time allows, and eventually finds the Pareto-optimal frontier. It efficiently reuses the search effort from previous iterations and makes use of a novel pruning technique. Our experimental results show that A-BOA* substantially outperforms baseline algorithms that do not reuse previous search effort, both in terms of runtime and number of node expansions. In fact, the most advanced variant of A-BOA* even slightly outperforms BOA*, a state-of-the-art bi-objective search algorithm, for finding the Pareto-optimal frontier. Moreover, given only a limited amount of deliberation time, A-BOA* finds solutions that collectively approximate the Pareto-optimal frontier much better than the solutions found by BOA*.

Solving a Multi-Agent Pathfinding (MAPF) problem involves finding non-conflicting paths that lead a number of agents to their goal location. In the sum-of-costs variant of MAPF, one is also required to minimize the total number of moves performed by agents before stopping at the goal. Not surprisingly, since MAPF is combinatorial, a number of compilations to Satisfiability solving (SAT) and Answer Set Programming (ASP) exist. In this paper, we propose the first family of compilations to ASP that solve sum-of-costs MAPF over 4-connected grids. Unlike existing compilations to ASP that we are aware of, our encoding is the first that, after grounding, produces a number of clauses that is linear on the number of agents. In addition, the representation of the optimization objective is also carefully written, such that its size after grounding does not depend on the size of the grid. In our experimental evaluation, we show that our approach outperforms search- and SAT-based sum-of-costs MAPF solvers when grids are congested with agents.

Many interesting search problems can be formulated as bi-objective search problems; for example, transportation problems where both travel distance and time need to be minimized. Multi-objective best-first search algorithms need to maintain the set of undominated paths from the start state to each state to compute a set of paths from a given start state to a given goal state (the Pareto-optimal solutions) such that no path in the set is dominated by another path in the set. Each time they find a new path to a state n, they perform a dominance check to determine whether such a path dominates any of the previously found paths to n. Existing algorithms do not perform these checks efficiently, requiring at least a full iteration over the Open list per check. In this paper, we present the first multi-objective algorithm that performs these checks efficiently. Indeed, Bi-Objective A* (BOA*)—our algorithm—requires constant time to check for dominance. Our experimental evaluation shows that BOA*is orders-of-magnitude faster than state-of-the-art search algorithms, such as NAMOA*, Bi-Objective Dijkstra, and Bidirectional Bi-Objective Dijkstra.

Grid path planning is an important problem in AI. Its understanding has been key for the development of autonomous navigation systems. An interesting and rather surprising fact about the vast literature on this problem is that only a few neighborhoods have been used when evaluating these algorithms. Indeed, only the 4- and 8-neighborhoods are usually considered, and rarely the 16-neighborhood. This paper describes three contributions that enable the construction of effective grid path planners for extended 2k-neighborhoods; that is, neighborhoods that admit 2k neighbors per state, where k is a parameter. First, we provide a simple recursive definition of the 2k-neighborhood in terms of the 2k-1-neighborhood. Second, we derive distance functions, for any k ≥ 2, which allow us to propose admissible heuristics that are perfect for obstacle-free grids, which generalize the well-known Manhattan and Octile distances. Third, we define the notion of canonical path for the 2k-neighborhood; this allows us to incorporate our neighborhoods into two versions of A*, namely Canonical A* and Jump Point Search (JPS), whose performance, we show, scales well when increasing k. Our empirical evaluation shows that, when increasing k, the cost of the solution found improves substantially. Used with the 2k-neighborhood, Canonical A* and JPS, in many configurations, are also superior to the any-angle path planner Theta* both in terms of solution quality and runtime. Our planner is competitive with one implementation of the any-angle path planner, ANYA in some configurations. Our main practical conclusion is that standard, well-understood grid path planning technology may provide an effective approach to any-angle grid path planning.

Multi-Agent Pathfinding (MAPF) over grids is the problem of finding n non-conflicting paths that lead n agents from a given initial cell to a given goal cell. Cost-optimal MAPF in addition minimizes the total number of actions performed by each agent before stopping at the goal. Being a combinatorial problem in nature, a number of compilations from MAPF to Answer Set Programming (ASP) exist. In this paper we propose a new one, which unlike existing ASP approaches (1) produces cost-optimal solutions, (2) exploits information that can be pre-computed quickly using Dijkstra's algorithm, and (3) when grounded, produces a number of clauses that grows linearly with the number of agents. In our empirical evaluation, in which we use the clasp solver, we show that our approach is superior to heuristic-search-based algorithms in various settings.

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.

Focal search (FS) is a bounded-suboptimal search (BSS) variant of A*. Like A*, it uses an open list whose states are sorted in increasing order of their f-values. Unlike A*, it also uses a focal list containing all states from the open list whose f-values are no larger than a suboptimality factor times the smallest f-value in the open list. In this paper, we develop an anytime version of FS, called anytime FS (AFS), that is useful when deliberation time is limited. AFS finds a "good" solution quickly and refines it to better and better solutions if time allows. It does this refinement efficiently by reusing previous search efforts. On the theoretical side, we show that AFS is bounded suboptimal and that anytime potential search (ATPS/ANA*), a state-of-the-art anytime bounded-cost search (BCS) variant of A*, is a special case of AFS. In doing so, we bridge the gap between anytime search algorithms based on BSS and BCS. We also identify different properties of priority functions, used to sort the focal list, that may allow for efficient reuse of previous search efforts. On the experimental side, we demonstrate the usefulness of AFS for solving hard combinatorial problems, such as the generalized covering traveling salesman problem and the multi-agent pathfinding problem.

The 2k neighborhood has been recently proposed as an alternative to optimal any-angle path planning over grids. Even though it has been observed empirically that the quality of solutions approaches the cost of an optimal any-angle path as k is increased, no theoretical bounds were known. In this paper we study the ratio between the solutions obtained by an any-angle path and the optimal path in the 2kk, that generalizes previously known bounds for the 4- and 8-connected grids. We analyze two cases: when vertices of the search graph are placed (1) at the corners of grid cells, and (2) when they are located at their centers. For case (1) we obtain a suboptimality bound of 1 + 1/8k2 + O(1/k3), which is tight; for (2), however, worst-case suboptimality is a fixed value, for every k ≤ 3. Our results strongly suggests that vertices need to be placed in corners in order to obtain near-optimal solutions. In an empirical analysis, we compare theoretical and experimental suboptimality.

Most real-time heuristic search algorithms solve search problems by executing a series of episodes. During each episode the algorithm decides an action for execution. Such a decision is usually made using information gathered by running a bounded, heuristic-search algorithm. In this paper we report on a real-time search algorithm that does not use a search algorithm to choose the next action to be applied. Rather, it uses a neural network whose input is local information about the search graph, comparable to the information that would be used by a bounded search algorithm. We describe a supervised learning approach to training such a network. Our three types of maps from the Moving AI benchmarks, shows that our algorithm is, in some cases, substantially superior to algorithms that have access to the same information about the graph. One of our most important conclusions is that our extended set of features important: indeed, using features beyond the heuristic seems key to achieving good performance.

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.

Any-angle path finding on grids is an important problem with applications in autonomous robot navigation. In this paper, we show that a well-known pre-processing technique, namely subgoal graphs, originally proposed for (non any-angle) 8-connected grids, can be straightforwardly adapted to the 2k neighborhoods, a family of neighborhoods that allow an increasing number of movements (and angles) as k is increased. This observation yields a pathfinder that computes 2k-optimal paths very quickly. Compared to ANYA, an optimal true any-angle planner, over a variety of benchmarks, our planner is one order of magnitude faster while being less than 0.0005% suboptimal. Important to our planner's performance was the development of an iterative 2k heuristic, linear in k, which is also a contribution of this paper.

Time-Bounded A* is a real-time, single-agent, deterministic search algorithm that expands states of a graph in the same order as A* does, but that unlike A* interleaves search and action execution. Known to outperform state-of-the-art real-time search algorithms based on Korf's Learning Real-Time A* (LRTA*) in some benchmarks, it has not been studied in detail and is sometimes not considered as a ``true'' real-time search algorithm since it fails in non-reversible problems even it the goal is still reachable from the current state. In this paper we propose and study Time-Bounded Best-First Search (TB(BFS)) a straightforward generalization of the time-bounded approach to any best-first search algorithm. Furthermore, we propose Restarting Time-Bounded Weighted A* (TB_R(WA*)), an algorithm that deals more adequately with non-reversible search graphs, eliminating ``backtracking moves'' and incorporating search restarts and heuristic learning. In non-reversible problems we prove that TB(BFS) terminates and we deduce cost bounds for the solutions returned by Time-Bounded Weighted A* (TB(WA*)), an instance of TB(BFS). Furthermore, we prove TB_R(WA*), under reasonable conditions, terminates. We evaluate TB(WA) in both grid pathfinding and the 15-puzzle. In addition, we evaluate TB_R(WA*) on the racetrack problem. We compare our algorithms to LSS-LRTWA*, a variant of LRTA* that can exploit lookahead search and a weighted heuristic. A general observation is that the performance of both TB(WA*) and TB_R(WA*) improves as the weight parameter is increased. In addition, our time-bounded algorithms almost always outperform LSS-LRTWA* by a significant margin.

Generalized Adaptive A* (GAA*) is an incremental algorithm that replans using A* when solving goal-directed navigation problems in dynamic terrain. Immediately after each A* search, it runs an efficient procedure that updates the heuristic values of states that were just expanded by A*, making them more informed. Those updates allow GAA* to speed up subsequent A* searches. Being based on A*, it is simple to describe and communicate; however, it is outperformed by other incremental algorithms like the state-of-the-art D*Lite algorithm at goal-directed navigation. In this paper we show how GAA* can be modified to exploit more information from a previous search in addition to the updated heuristic function. Specifically, we show how GAA* can be modified to utilize the paths found by a previous A* search. Our algorithm — Multipath Generalized Adaptive A* (MPGAA*) — has the same theoretical properties of GAA* and differs from it by only a few lines of pseudocode. Arguably, MPGAA* is simpler to understand than D*Lite. We evaluate MPGAA* over various realistic dynamic terrain settings, and observed that it generally outperforms the state-of-the-art algorithm D*Lite in scenarios resembling outdoor and indoor navigation.

In moving target search, the objective is to guide a hunter agent to catch a moving prey. Even though in game applications maps are always available at developing time, current approaches to moving target search do not exploit preprocessing to improve search performance. In this paper, we propose MtsCopa, an algorithm that exploits precomputed information in the form of compressed path databases (CPDs), and that is able to guide a hunter agent in both known and partially known terrain. CPDs have previously been used in standard, fixed-target pathfinding but had not been used in the context of moving target search. We evaluated MtsCopa over standard game maps. Our speed results are orders of magnitude better than current state of the art. The time per individual move is improved, which is important in real-time search scenarios, where the time available to make a move is limited. Compared to state of the art, the number of hunter moves is often better and otherwise comparable, since CPDs provide optimal moves along shortest paths. Compared to previous successful methods, such as I-ARA*, our method is simple to understand and implement. In addition, we prove MtsCopa always guides the agent to catch the prey when possible.

Time-Bounded A* (TBA*) is a single-agent deterministic search algorithm that expands states of a graph in the same order as A* does, but that unlike A* interleaves search and action execution. Although the idea underlying TBA* can be generalized to other single-agent deterministic search algorithms, little is known about the impact on performance that would result from using algorithms other than A*. In this paper we propose Time-Bounded Best-First Search (TB-BFS) a generalization of the time-bounded approach to any best-first search algorithm. Furthermore, we propose restarting strategies that allow TB-BFS to solve search problems in dynamic environments. In static environments, we prove that the resulting framework allows agents to always find a solution if such a solution exists, and prove cost bounds for the solutions returned by Time-Bounded Weighted A* (TB-WA*). We evaluate the performance of TB-WA* and Time-Bounded Greedy Best-First Search (TB-GBFS). We show that in pathfinding applications in static domains, TB-WA* and TB-GBFS are not only faster than TBA* but also find significantly better solutions in terms of cost. In the context of videogame pathfinding, TB-WA* and TB-GBFS perform fewer undesired movements than TBA*. Restarting TB-WA* was also evaluated in dynamic pathfinding random maps, where we also observed improved performance compared to restarting TBA*. Our experimental results seem consistent with theoretical bounds.

Depth-First Branch and Bound (DFBnB) is an anytime algorithm for solving combinatorial optimization problems. In this paper we present a weighted version of DFBnB, wDFBnB, which incorporates standard techniques for using weights in heuristic search and offers suboptimality guarantees. Our main contribution drawn from a preliminary evaluation is the observation that wDFBnB, used along with automated or hand-crafted weight schedules, can significantly outperform DFBnB both in terms of anytime behavior and convergence to the optimal. We think this small study calls for more research on the design of automated weight schedules that could provide superior anytime performance across a wider range of domains.

Many applications, ranging from video games to dynamic robotics, require solving single-agent, deterministic search problems in partially known environments under very tight time constraints. Real-Time Heuristic Search (RTHS) algorithms are specifically designed for those applications. As a subroutine, most of them invoke a standard, but bounded, search algorithm that searches for the goal. In this paper we present FRIT, a simple approach for single-agent deterministic search problems under tight constraints and partially known environments that unlike traditional RTHS does not search for the goal but rather searches for a path that connects the current state with a so-called ideal tree T . When the agent observes that an arc in the tree cannot be traversed in the actual environment, it removes such an arc from T and then carries out a reconnection search whose objective is to find a path between the current state and any node in T . The reconnection search is done using an algorithm that is passed as a parameter to FRIT. If such a parameter is an RTHS algorithm, then the resulting algorithm can be an RTHS algorithm. We show, in addition, that FRIT may be fed with a (bounded) complete blind-search algorithm. We evaluate our approach over grid pathfinding benchmarks including game maps and mazes. Our results show that FRIT, used with RTAA*, a standard RTHS algorithm, outperforms RTAA* significantly; by one order of magnitude under tight time constraints. In addition, FRIT(daRTAA*) substantially outperforms daRTAA*, a state-of-the-art RTHS algorithm, usually obtaining solutions 50% cheaper on average when performing the same search effort. Finally, FRIT(BFS), i.e., FRIT using breadth-first-search, obtains best-quality solutions when time is limited compared to Adaptive A* and Repeated A*. Finally we show that Bug2, a pathfinding-specific navigation algorithm, outperforms FRIT(BFS) when planning time is extremely limited, but when given more time, the situation reverses.

In this paper, we present a conceptually simple, easy-to-implement real-time search algorithm suitable for a priori partially known environments. Instead of performing a series of searches towards the goal, like most Real-Time Heuristic Search Algorithms do, our algorithm follows the arcs of a tree T rooted in the goal state that is built initially using the heuristic h. When the agent observes that an arc in the tree cannot be traversed in the actual environment, it removes such an arc from T and our algorithm carries out a reconnection search whose objective is to find a path between the current state and any node in T. The reconnection search need not be guided by $h$, since the search objective is not to encounter the goal. Furthermore, h need not be updated. We implemented versions of our algorithm that utilize various blind search algorithms for reconnection. We show experimentally that these implementations significantly outperform state-of-the-art real-time heuristic search algorithms for the task of pathfinding in grids. In grids, our algorithms, which do not incorporate any geometrical knowledge, naturally behaves similarly to a bug algorithm, moving around obstacles, and never returning to areas that have been visited in the past. In addition, we prove theoretical properties of the algorithm.

Incremental search algorithms, such as D* Lite, reuse information from previous searches to speed up the current search and can thus solve sequences of similar search problems faster than Repeated A*, which performs repeated A* searches. In this position paper, we study goal-directed navigation in initially unknown terrain and point out that it is currently not well understood when D* Lite runs faster than Repeated A*. In general, it appears that Repeated A* runs faster than D* Lite for easy navigation problems (where the agent reaches the goal with only a small number of searches), which means that it runs faster than D* Lite quite often in practice. We draw two conclusions, namely that incremental search algorithms need to be evaluated in more diverse testbeds to improve our understanding of their properties and that they can be improved to be more competitive for easy navigation problems.

This paper summarizes our AAMAS 2012 paper on "Time-Bounded Adaptive A*," which introduces the game time model to evaluate search algorithms in real-time settings, such as video games. It then extends the existing real-time search algorithm TBA* to path planning with the freespace assumption in initially partially or completely unknown terrain, resulting in Time-Bounded Adaptive A* (TBAA*). TBAA* needs fewer time intervals in the game time model than several state-of-the-art complete and real-time search algorithms and about the same number of time intervals as the best compared complete search algorithm, even though it has the advantage over complete search algorithms that the agent starts to move right away.

We propose a method for preprocessing an eight-neighbor gridworld to generate a subgoal graph and a method for using this subgoal graph to find shortest paths faster than A*, by first finding high-level paths through subgoals and then shortest low-level paths between consecutive subgoals on the high-level path.

Heuristics used for solving hard real-time search problems have regions with depressions. Such regions are bounded areas of the search space in which the heuristic function is inaccurate compared to the actual cost to reach a solution. Early real-time search algorithms, like LRTA*, easily become trapped in those regions since the heuristic values of their states may need to be updated multiple times, which results in costly solutions. State-of-the-art real-time search algorithms, like LSS-LRTA* or LRTA*(k), improve LRTA*'s mechanism to update the heuristic, resulting in improved performance. Those algorithms, however, do not guide search towards avoiding depressed regions. This paper presents depression avoidance, a simple real-time search principle to guide search towards avoiding states that have been marked as part of a heuristic depression. We propose two ways in which depression avoidance can be implemented: mark-and-avoid and move-to-border. We implement these strategies on top of LSS-LRTA* and RTAA*, producing 4 new real-time heuristic search algorithms: aLSS-LRTA*, daLSS-LRTA*, aRTAA*, and daRTAA*. When the objective is to find a single solution by running the real-time search algorithm once, we show that daLSS-LRTA* and daRTAA* outperform their predecessors sometimes by one order of magnitude. Of the four new algorithms, daRTAA* produces the best solutions given a fixed deadline on the average time allowed per planning episode. We prove all our algorithms have good theoretical properties: in finite search spaces, they find a solution if one exists, and converge to an optimal after a number of trials.

Heuristics used for solving hard real-time search problems have regions with depressions. Such regions are bounded areas of the search space in which the heuristic function is exceedingly low compared to the actual cost to reach a solution. Real-time search algorithms easily become trapped in those regions since the heuristic values of states in them may need to be updated multiple times, which results in costly solutions. State-of-theart real-time search algorithms like LSS-LRTA∗, LRTA∗ (k), etc., improve LRTA∗’s mechanism to update the heuristic, resulting in improved performance. Those algorithms, however, do not guide search towards avoiding or escaping depressed regions. This paper presents depression avoidance, a simple real-time search principle to guide search towards avoiding states that have been marked as part of a heuristic depression. We apply the principle to LSS-LRTA ∗ producing aLSS-LRTA∗, a new real-time search algorithm whose search is guided towards exiting regions with heuristic depressions. We show our algorithm outperforms LSS-LRTA∗ in standard real-time benchmarks. In addition we prove aLSS-LRTA∗ has most of the good theoretical properties of LSS-LRTA∗.

Real-time search is a well known approach to solving search problems under tight time constraints. Recently, it has been shown that LSS-LRTA∗ , a well-known real-time search algorithm, can be improved when search is actively guided away of depressions. In this paper we investigate whether or not RTAA∗ can be improved in the same manner. We propose aRTAA∗ and daRTAA∗ , two algorithms based on RTAA∗ that avoid heuristic depressions. Both algorithms outperform RTAA∗ on standard path-finding tasks, obtaining better-quality solutions when the same time deadline is imposed on the duration of the planning episode. We prove, in addition, that both algorithms have good theoretical properties.