Domain-Dependent and Domain-Independent Problem Solving Techniques

1 Introduction

Heuristic search is one of the fundamental problem-solving techniques used in Artificial Intelligence (AI), dating back to Newell and Simon's General Problem Solving program [Newell et al., 1959]. Heuristic search algorithms, such as A∗ , are still the cornerstone of performing higher-level AI tasks such as automated planning [Bonet and Geffner, 2001] and Model-Based Diagnosis (MBD) [Reiter, 1987; De Kleer and Williams, 1987].

When solving a problem using a search algorithm, the world is abstracted as a set of states. Every state s is associated with a set of state-transition operators O(s), where each o ∈ O(s) is a function that maps s to a possibly different state s′ . A path from state s to s′ is a sequence of state-transition operators such that applying this sequence to s results in s′ . It is common for operators to have a cost, and to define the cost of a path as the sum of costs of its constituent operators. Path finding is a common type of search problem where the objective is to find a path from a given initial state to a goal state. A goal state is defined explicitly or implicitly via a goal-test function. Classical STRIPS-based planning is a prime example of a path finding problem [Bonet and Geffner, 2001; Fikes and Nilsson, 1971]. A common requirement in path finding problems is that the path has a low cost. An optimal solution in such cases is a lowest-cost path from the initial state to a goal state.

A search algorithm is called a heuristic search algorithm if it considers some imperfect source of information about the problem it is used to solve. In some heuristic search algorithms, this imperfect information is encapsulated in a blackbox heuristic function h that accepts a state s and outputs a number that estimates the cost of a lowest-cost path from s to a goal. We refer to such algorithms as domain-independent heuristic search algorithms. We use this term to emphasize that all the problem solver knows about the domain beyond the initial state, operators, and goal-test function, is a blackbox heuristic function.

Prominent examples are A∗ [Hart et al., 1968] and wA∗ [Pohl, 1970]. Other heuristic search algorithms are domain-dependent, in the sense that their behavior is customized to solve a specific type of problems. For example, Conflict-Directed A∗ [Williams and Ragno, 2007] is a heuristic search algorithm that is specifically designed to solve MBD problems. Similarly, Increasing Cost Tree Search [Sharon et al., 2013] is specifically designed to solve Multi-Agent Pathfinding (MAPF) problems.

In this paper, we review our contributions in developing algorithms and theory for domain-independent and domain-dependent heuristic search. In particular, we describe several recent algorithms aimed at satisfying various requirements about solution quality, and review a range of domain-dependent heuristic search algorithms we developed. Throughout, we highlight open challenges and topics that are left for future research.

2 Background

Best-first search is a general framework for solving search problems. A best-first search maintains a list of states called OPEN. Initially, OPEN contains the initial state. Then, in every iteration, a single state s is removed from OPEN and expanded. To expand a state s means that for every operator o ∈ O(s) we generate a new state o(s) and insert it into OPEN. Later iterations can choose to expand these new states, generating newer states. The search can halt when a goal state is generated.

There are many design choices when implementing a bestfirst search, e.g., whether to insert to OPEN a state that was already generated by another state. A particularly important design choice is how to choose which state to remove from OPEN in every iteration. Heuristic search algorithm use the heuristic function h to make this choice. For example, the famous A∗ algorithm chooses from OPEN the state s with the smallest f(s) = g(s) + h(s), where g(s) is the cost of the lowest-cost path known so far from the initial state to s. A heuristic h is admissible if for every state s it outputs a value that is smaller than or equal to the cost of a lowest-cost path from s to a goal. Given an admissible heuristic, A∗ is guaranteed to have found an optimal solution once a goal node is expanded [Hart et al., 1968]. Most heuristic search algorithms that return optimal solutions also rely on an admissible heuristic, e.g., IDA∗ [Korf, 1985] and RBFS [Korf, 1992].

3 Domain-Independent Search

Many search problems are just too hard to solve optimally, even with A∗ and a very accurate heuristic [Helmert et al., 2008]. To this end, a range of suboptimal search algorithms has been developed. One way to classify suboptimal search algorithms is by the theoretical guarantee they provide over the solution they return.

3.1 Incomplete and Not-Optimal Search

Some search algorithms are incomplete, i.e., they may not find a solution even if such exists. Hill Climbing and Genetic Algorithms [Holland, 1992] are examples of incomplete algorithms. Such algorithms are used for extremely difficult search problems.

Other search algorithms are guaranteed to find a solution if such exists, but provide no guarantee regarding the quality of that solution. Greedy Best-First Search (GBFS) [Doran and Michie, 1966], also known as Pure heuristic search, is a popular example. GBFS is a best-first search that expands in every iteration the state in OPEN with the smallest heuristic value. Beam search is another popular algorithm from this class [Zhou and Hansen, 2005; Sabuncuoglu and Bayiz, 1999; Furcy and Koenig, 2005]. There is a limited understanding of the behavior of these algorithms, although recent research has been trying to identify the relation between their performance and the heuristic landscape [Wilt and Ruml, 2016; Heusner et al., 2018].

In many cases, it is not sufficient to find any solution, and there are some restrictions on the cost of the desired solution. We have explored several such cost-related restrictions.

3.2 Bounded-Cost Search

In a bounded-cost search problem, the user defines a cost bound C and aims to find a solution whose cost is at most C. This type of search problem arises, for example, in scenarios where there is a limited budget. Bounded-cost search problem has rarely been studied in a domain-independent manner.

We closed this gap by proposing a search algorithm called Potential Search (PS) [Stern et al., 2014] that is specifically designed to solve bounded-cost search problems. PS is a best-first search based on a unique evaluation function u(s) = C-g(s) h(s) . In every iteration, PS expands the state with the highest u(s). The u(·) evaluation function was discovered independently by two research groups [Stern et al., 2011; Van Den Berg et al., 2011] in the context of anytime search (see later) and through different mathematical derivations.

The derivation relevant to bounded-cost search relates u(s) to the potential of s. The potential of a state with respect to C is the probability that it part of a solution of cost lower than C. Under certain probabilistic relation between the available heuristic function and the cost it estimates, it can be shown that the state with the highest u(·) in OPEN is also the one with the highest potential. Empirically, we observed PS to be useful over a range of search domains. However, we also observed that PS may perform poorly on domains in which the length of a path, i.e., the number of its constituent operators, is not correlative with its cost.

For such domains, we proposed Bounded-cost Explicit Estimation Search (BEES) [Thayer et al., 2012]. BEES is based on Explicit Estimation Search (EES) [Thayer and Ruml, 2011], and considers additional heuristics including a heuristic that estimates the length of an optimal path to a goal. Empirical evaluations showed that BEES is particularly useful in these non-uniform domains. An open research challenge is to provide a more rigorous theory for the behavior of PS and BEES, and in general to bounded-cost search problems.

3.3 Bounded-Suboptimal Search

A common way to quantify the suboptimality a solution is by measuring the ratio between between its cost and the cost of an optimal solution. This is often called the suboptimality of a solution. 1 The suboptimality of an optimal solution is one, and higher suboptimality means a worse solution (i.e., higher cost). A bounded-suboptimal search algorithm is an algorithm that accepts a parameter B ≥ 1 and is guaranteed to return a solution whose suboptimality is at most B. An ideal bounded-suboptimal search algorithm trades off solution cost for runtime, i.e., increasing B results in worse (higher) solution cost and better (lower) search runtime.

wA∗ is a well-known bounded-suboptimal search algorithm [Pohl, 1970] that is still widely used. It expands in every iteration the state n in OPEN with the smallest g(n) + B · h(n).

A∗ϵ [Pearl and Kim, 1982] is another well-known boundedsuboptimal search algorithm. In A∗ϵ , the minimal f value in OPEN, referred to as fmin, is maintained. fmin is used to define FOCAL, which is the set containing every state s in OPEN for which f(s) ≤ B · fmin. A∗ϵ chooses in every iteration to expand a state from FOCAL. To choose which state in FOCAL to expand, A∗ϵ uses a different, possibly inadmissible heuristic. Since A∗ϵ does not define this secondary heuristic, it is, in fact, a search framework, which is known today as Focal search [Thayer and Ruml, 2011; Ebendt and Drechsler, 2009].

All Focal search algorithms are bounded-suboptimal because throughout the search fmin is always a lower bound on the cost of an optimal solution, given that f is computed with an admissible heuristic. This understanding allowed us to develop a novel bounded-suboptimal search algorithm called Dynamic Potential Search (DPS). DPS considers both fmin and the u(·) function used by PS [Gilon et al., 2016]. DPS is a best-first search that expands in every iteration the state with the highest u(·). Since a cost bound C is not given in a bounded-suboptimal search problem, DPS sets C to be B · fmin. This guarantees that any solution found will indeed be bounded suboptimal. If fmin changes, DPS will re-sort OPEN to update the u values. In a sense, DPS is running a sequence of bounded-cost searches, where the cost bound is B · fmin. A major advantage of DPS over Focal search algorithms is that it does not need to maintain FOCAL. Empirically, DPS performs well on a range of domains.

1 Other ways to define suboptimality of a solution exist, e.g., the difference from the optimal solution cost [Valenzano et al., 2013].

DPS, as well as EES, wA∗ , and A∗ϵ , are all in the bestfirst search framework. Thus, there are cases where memory will be a bottleneck to the search. To address this, there are several modern bounded-suboptimal search algorithms that run in linear space [Hatem and Ruml, 2014; Hatem et al., 2013] and outperform traditional boundedsuboptimal linear-space algorithms such as weighted IDA∗ and weighted RBFS [Korf, 1992].

Indeed, the past decade has seen an explosion of boundedsuboptimal search algorithms. However, the theoretical understanding of these algorithms is, to-date, limited. For example, in optimal search, under some conditions, any bestfirst search must expand at least the set of nodes expanded by A∗ [Dechter and Pearl, 1985; Goldenberg et al., 2014; Holte and Zilles, 2019]. An equivalent claim does not exist for bounded-suboptimal search. Also, there is no clear answer for which bounded-suboptimal algorithm to use in a given domain. There are important directions for future work.

3.4 Anytime Search

An anytime algorithm is an algorithm "whose quality of results improves gradually as computation time increases" [Zilberstein, 1996]. An anytime search algorithm finds an initial solution quickly, and then, given more running time, finds better solutions. Several anytime search algorithms have been proposed over the years. Prominent examples are Anytime Repairing A∗ (ARA*) [Likhachev et al., 2004], Anytime Weighted A∗ (AWA*) [Hansen and Zhou, 2007], Anytime Windowed A∗ [Aine et al., 2007], and Restarting Weighted A∗ [Richter et al., 2010]. A major limitation of all these algorithms is that they accept a parameter and there is no clear theory on how to set it. To address this, we developed a nonparametric anytime search algorithm, that works as follows. First, it finds an initial solution with GBFS. Then, we run PS and set the cost-bound to be the cost of the incumbent solution. This will return a new, better, solution. Then, we run PS again with the cost of the new solution. This process continues until time has run out or the optimal solution has been found. The resulting anytime search algorithm is, to-date, one of the best anytime search algorithms. 2

This anytime algorithm and the bounded-suboptimal algorithm DPS are both built on top of PS. However, they demonstrate a more general approach in which one can use a bounded-cost search algorithm to construct an anytime search algorithm as well as a bounded-suboptimal search algorithm. Thus, future work on developing better bounded-cost search algorithms can have a wide impact beyond solving boundedcost search problems.

2 Due to its dual origin, this algorithm has two names: Anytime PS or Anytime Non-Parametric A∗ (ANA∗ ).

3.5 Probably Bounded-Suboptimal Search

Recently, we explored the notion of probabilistic solution quality guarantees, where the suboptimality of a solution must be bounded in most cases, but not always [Stern et al., 2019]. More formally, a Probably Bounded-Suboptimal (PBS) search algorithm is an algorithm that accepts, in addition to a suboptimality bound B, a confidence parameter δ. The guarantee provided by a PBS is that the suboptimality of the solution it returns is at most B with probability at least 1-δ. We proposed several PBS algorithms based on running an anytime search algorithm and analyzing the domain and previously solved problems in it. Experimentally, we showed that allowing a non-zero δ, i.e., a non-zero probability of returning a solution without the desired suboptimality, can lead to significant search speedup.

The PBS algorithms we proposed can be viewed as a middle-ground between domain-independent and domainspecific search. Indeed, we envision such forms of analysis of the domain can provide a bridge to introducing data-driven methods into heuristic search algorithms that provide some form of solution quality guarantees.

4 Domain-Dependent Search

Domain-independent heuristic search algorithms, such as those listed in the previous section, are widely used in a range of domains. However, an in-depth understanding of the problem domain is needed in some domains in order to guide the search effectively. In this section, we describe a partial list of domain-specific search problems that we have worked on.

4.1 Multi-Agent Pathfinding

A MAPF problem consists of a graph and n agents. Each agent has a unique start node and a unique goal node. Time is discretized into time steps. In each time step, each agent can either move to an adjacent node or wait in its current node. A plan for a single agent is a sequence of (more or wait) actions that moves the agent from its start to its goal. Two agents cannot occupy the same node at the same time, as that would cause a collision. A valid solution to a MAPF problem is a joint plan, which is a set of plans, one for each agent, such that no collisions will occur. MAPF has topical applications in warehouse management [Wurman et al., 2008], airport towing [Morris et al., 2016], autonomous vehicles, robotics [Veloso et al., 2015], and digital entertainment [Ma et al., 2017].

In many cases, there is also a requirement to minimize some cumulative cost function, such as the time spent or costs incurred until all agents have reached their goals. Solving MAPF optimally is NP-Hard [Yu and LaValle, 2013; Surynek, 2010]. MAPF is particularly challenging for domain-independent search algorithms because the number of operators in a given state is exponential in the number of agents, since agents can move concurrently.

To address this, we developed the Enhanced Partial Expansion A∗ (EPEA*) algorithm [Goldenberg et al., 2014], that uses a domain-specific operator selection function to choose to use only a subset of the applicable operators when a state is expanded. EPEA* is, in fact, applicable to any problem with a large branching factor. We also developed more sophisticated, domain-specific MAPF, that solve MAPF by solving two different search problems that interact with each other. For more details, see Felner et al. [2017].

4.2 Longest Simple Path

The Longest Simple Path (LSP) problem is the problem of finding the longest simple path in a graph from one node to another. A path is simple iff no node appears twice in the path. LSP is a classical graph theory problem with various applications. A key challenge in LSP is that it is non-monotonic, i.e., longer paths are better. This makes it harder to identify when an optimal solution has been found [Stern et al., 2014]. We describe how to adapt A∗ to such problems, and propose several heuristics for LSP, and for a particular type of LSP called snake in the box, which has application in coding [Palombo et al., 2015].

A second challenge in LSP is the simple-path requirement. This requirement prohibits pruning multiple paths that reach the same node, thereby making the search much harder. A similar challenge exists in other search problems, such as the target-value search [L´opez et al., 2013]. Creating a general, domain-independent algorithm for problems with this requirement, is an open challenge.

4.3 Model-Based Diagnosis

An MBD problem occurs when an observation of a system is inconsistent with an available model of that system and the assumption that all the system components are not faulty. The task of a consistency-based MBD algorithm is to infer diagnoses, which are assumptions about which system components are faulty that explain the observation.

MBD is a classical problem in the Artificial Intelligence literature with numerous applications [Reiter, 1987; De Kleer and Williams, 1987]. MBD can be modeled as a search problem. A state is an assumption about which component is faulty. The initial state assumes all components are not faulty. A state transition operator adds an assumption that one component is faulty. A goal-test function checks if the assumption represented by a state is consistent with the observation and the available system model.

MBD is a challenging problem because the number of operators applicable in a state is the number of system components. A common way to address this is to limit the search using conflicts. A conflict is a set of components that contain at least one faulty component. Conflict-directed A∗ [Williams and Ragno, 2007] and other algorithms [Reiter, 1987; De Kleer and Williams, 1987] work by identifying conflicts, and then limiting the search to only consider hitting sets of identified conflicts.

Identifying conflicts, however, is a hard problem in its own right. To address this, we proposed an MBD-specific search algorithm that runs two searches in parallels: one searching for conflicts and the other searching for diagnoses [Stern et al., 2012]. Due to the duality between conflicts and diagnoses, these searches effectively interact, where finding diagnoses helps finding conflicts and vice versa.

5 Conclusion

Recent years have shown tremendous progress in both domain-independent and domain-dependent heuristic search algorithms. We believe that cross-fertilization between domain-independent and domain-dependent search algorithms can lead to impactful advancement in the field. This calls for automating the process of learning domain properties and extracting useful information from them that can be used in search.

Acknowledgments

The contributions in this paper are a result of collaborations with many other researchers. Special thanks go to Ariel Felner, my long-time mentor and friend, as well as to Meir Kalech, Rami Puzis, and Robert Holte, for their key role in this research and my academic education. This research is supported by ISF grants no. 210/17 to Roni Stern.