Multi-Directional Heuristic Search

1 Introduction

MM [Holte et al., 2016] is a bidirectional heuristic search algorithm with a unique priority function; nodes are ordered in OPEN according to max(2g, g+h). MM is guaranteed to meet in the middle but the practical meaning of this property is that the two search frontiers never venture further than C ∗ /2 from their start locations (where C ∗ is the cost of the shortest path). Nevertheless, it is important to note that a meeting location is not returned by MM; a shortest path from a start location to a goal location is returned. In fact, a meeting location is not even defined in MM.

In this paper, we deal with the "real" problem of meeting in the middle, where a meeting location is returned. Furthermore, while MM is designed for a problem that is defined on start and goal locations, our problem is defined on k ≥ 2 start locations where we search for an optimal meeting location with respect to the shortest path from each of these k start locations to that meeting location. We call this problem the Multi-Agent Meeting problem (MAM). We focus on minimizing the following two common cost functions defined on possible solutions. (1) Sum-Of-Costs (SOC): the sum of the costs of the paths to the meeting location. (2) Makespan (MKSP): the cost of the longest path to the meeting location. SOC may corresponds to the energy (fuel) consumed until the agents meet, and MKSP corresponds to the time elapsed until the agents meet. MAM has many real-life applications, such as choosing a gathering point for multiple traveling agents (humans, cars, or robots), or suggesting a location that needs to be close to important surrounding locations.

To find the optimal meeting location, we introduce the Multi-Directional Meet in the Middle (MM*) algorithm. MM* is a best-first search algorithm that progresses in k directions until a meeting location is found. We provide a unique priority function for each of the SOC and MKSP cost functions and prove the optimality of MM* for these cases. MM* is strongly related to MM - its priority function for MKSP is a generalization of that of MM, although their halting conditions are different (so as to return the actual meeting location). MM* relies on an admissible heuristic function and we propose a number of such heuristic functions for SOC and MKSP. We then provide experimental results that demonstrate the benefits of MM* with these heuristic functions.

MAM is also known as Optimal Meeting Point [Yan et al., 2015], Smallest Enclosing Discs [Welzl, 1991], and 1-Center problem [Megiddo, 1983] in other areas of computer science. In the field of computational geometry, MAM is known as the Weber problem [Cooper, 1968]. Many efficient algorithms exist for MAM in continuous Euclidean spaces [Ostresh Jr, 1977; Chen, 1984; Rad´o, 1988; Rosing, 1992] that calculate a geometric point that satisfies the relevant constraints. The problem has also been investigated on general graphs by applying variants of Dijkstra's algorithm [Dijkstra, 1959] in parallel, one for each agent. Once a path from all start locations to all locations in the graph is known, the best meeting location can be chosen by iterating over all relevant meeting locations, exhaustively. Many improvements have been suggested, such as pruning areas of the state space [Lanthier et al., 2005; Xu and Jacobsen, 2010; Yan et al., 2015; Li et al., 2019; Geisberger et al., 2008]. We continue this direction and, to the best of our knowledge, are the first ones to add admissible heuristics and study MAM in the context of heuristic search.

2 ProblemDefinition

The Multi-Agent Meeting problem (MAM) receives as input a weighted, undirected graph G = (V,E) and a set of k start locations S = {s1, . . . , sk} ⊆ V for k agents A = {a1, . . . , ak}. The cost of edge (v, v′ ) ∈ E is denoted by c(v, v′ ) > 0. A solution is a target location t ∈ V , indicating a meeting location for the agents, plus a set of shortest paths from each si to t. Let d(v, u) be the cost of a shortest path from v to u. The cost functions for SOC and MKSP for a meeting location t are calculated as follows. For SOC:

This corresponds to the sum of the costs of the paths to the meeting location. For MKSP:

This is the cost of the longest path to the meeting location. An optimal solution has the lowest cost among all possible solutions. Its cost is denoted by C ∗ and its meeting location by t∗ . In this paper, we focus on optimal solutions.

Figure 1(a) illustrates a MAM problem instance with three agents a1, a2, and a3 with start locations s1, s2, and s3, respectively. Edges are labeled with their costs. Consider location t as a meeting location. Since d(s1, t) = 5, d(s2, t) = 5, and d(s3, t) = 5, CSOC(t) = 15 while CMKSP(t) = 5. Now, consider v. Since d(s1, v) = 8, d(s2, v) = 2, and d(s3, v) = 2, CSOC(v) = 12 and CMKSP(v) = 8. v is optimal for minimizing SOC and t for MKSP. Next, we present the MM* algorithm that solves MAM for both cost functions.

3 Multi-Directional MM (MM*)

MM* is a multi-directional best-first search algorithm that guarantees to return an optimal MAM solution for both SOC and MKSP. As will be shown below, the only difference in MM* between SOC and MKSP is the priority function used.

A node in MM* is a pair (ai, v) representing an agent and its location. MM* organizes nodes in a single open-list (denoted OPEN) and a single closed-list (denoted CLOSED). 1 OPEN is initialized with k root nodes: (ai, si) representing each of the k agents and its start location. Each node is associated with a g-value. Naturally, g(ai, si) = 0. Let N(v) represent the successors of v. Expanding a node (ai, v) has two parts: (1) Generating a node (ai, v′ ) for each v′ ∈ N(v), setting g(ai, v′ ) = g(ai, v) + c(v, v′ ), and inserting it into OPEN. (2) Moving (ai, v) to CLOSED.

Recall that, in heuristic search, given a node n in the search tree, f ∗ (n) is defined to be the cost of the optimal solution that passes through n, and f(n) is defined to be a lower bound on f ∗ (n). This terminology is migrated to MM*. Let f ∗ (ai, v) be the cost of the optimal MAM solution (for either SOC or MKSP) such that ai passes through v on its way to the meeting location. f(ai, v) is a lower bound on f ∗ (ai, v), i.e., f(ai, v) ≤ f ∗ (ai, v). In Section 4, we define f(ai, v) for either SOC or MKSP by exploiting admissible heuristic functions that estimate the remaining cost of all agents (including that of ai) that can be added to g(ai, v) (the cost of the path from si to v along the search tree). Each of these f-values can be plugged into MM*.

1 Bidirectional searches usually maintain two open-lists, one for each search direction, but the priority function can choose a node from either one of them. This is logically equivalent to a single openlist which contains nodes from both directions. MM* uses a single open-list, which is equivalent to k open-lists, one for each agent, that use the same priority function.

There is no notion of a goal node in MM* but instead we have a goal condition on each location v. We say that v is a possible goal iff it has been generated from all directions, i.e., ∀ai ∈ A: (ai, v) ∈ OPEN ∪ CLOSED. To manage this in practice, for each location v, we keep a k bit-vector, where bit i is set when node (ai, v) is generated. If v is a possible goal, its cost C(v) depends on the cost function and is:

Let U be the cost of the incumbent solution, i.e., U is the minimum C(v) among all possible goals (initially U = ∞). U is an upper bound on C ∗ . The halting condition for MM* is to halt if fmin ≥ U, where fmin is the minimum f-value in OPEN. This guarantees that U cannot be further improved.

Algorithm 1 gives the pseudo-code of MM*. First, MM* initializes OPEN and CLOSED, and sets U = ∞ (line 2). Then, the initial nodes (ai, si) are inserted into OPEN (lines 3-4). MM* performs a best-first search as follows. While OPEN is not empty (line 5), it extracts (ai, v), the best node (with the lowest f-value) from OPEN (line 6). Then, it checks the halting condition on location v, i.e., whether fmin = f(ai, v) ≥ U (lines 7-8). Otherwise, it performs the expansion cycle on (ai, v) (lines 9-18). MM* performs duplicate detection and pruning on CLOSED (lines 10-13) and OPEN (lines 14-16). As a result, MM* always keeps the lowest seen g-value for each generated node (ai, v′ ). In general, MM* allows nodes in CLOSED to be re-opened (line 13). But, this will never happen for consistent heuristics (such as all heuristics that we suggest and experiment with below). If (ai, v′ ) is not a duplicate node, then (ai, v′ ) is inserted into OPEN (line

2 In Equations 1 and 2, we used d(si, v). Here, we use g(ai, v) because the path is the path from si to v along the search tree.

17). Then, U is updated in case v′ is a possible goal with a smaller cost (line 18). After its expansion, (ai, v) is inserted into CLOSED (line 19). When U is returned (lines 8 and 20), it also includes the meeting location t as well as the paths to it, that can be constructed by parent-pointers (not included in the pseudo-code).

4 MM* Priority Functions

We next define the priority function f for MM* for both SOC and MKSP. In A*, given a node n, a perfect heuristic h∗ (n) equals d(n, goal) and a perfect priority function f ∗ (n) equals g(n) + h∗ (n). If h(n) is a lower bound on h∗ (n) = d(n, goal), then f(n) = g(n) + h(n) is a lower bound on f ∗ (n). Next, we generalize this to MM* and define all these functions for both SOC and MKSP.

4.1 SOC

Consider node (ai, v) in OPEN. f ∗ SOC (ai, v) is the cost of the optimal solution such that: (1) ai passes through v (via the path of cost g(ai, v) along the search tree). (2) ai continues from v to meet the other agents at some location t. (3) Each of the other agents aj travels from sj to t. Now, f ∗ SOC (ai, v) = g(ai, v) + h∗SOC (ai, v), where h∗SOC (ai, v) is the sum of the cost of ai to get from v to t along a shortest path (item 2), plus the cost of the other agents to get from their start locations to t along shortest paths (item 3):

We denote the best meeting location t w.r.t. to node (ai, v) by t∗ (ai, v). hSOC(ai, v) is an admissible estimate (lower bound) of h∗SOC (ai, v), i.e., hSOC (ai, v) ≤ h∗SOC (ai, v). We propose a number of admissible h-functions for SOC in Section 7. For SOC, naturally,

4.2 MKSP

The MKSP case is more complicated. Since, in MKSP, we take the maximum among agents (not the sum), we do not know which agent has the path with the highest cost. We begin by defining f ∗MKSP (ai, v), which is the optimal solution given that ai passes through v, via a path of cost g(ai, v):

For a given possible meeting location t, we want the path of one of the agents with the highest cost. If this is our current agent ai, then this is given by g(ai, v) + d(v, t) (top line of the max term). If it is some other agent aj, then it is given by d(sj , t) (bottom line).

Next, we need to define fMKSP as a lower bound on f ∗MKSP . Here, we do not define h∗MKSP and hMKSP but define fMKSP(ai, v) in terms of hSOC (ai, v) as follows:

where k is the number of agents. g(ai, v) is a lower bound on f ∗MKSP (ai, v) because ai has already traveled along a path of cost g(ai, v). Thus, f ∗MKSP (ai, v) ≥ g(ai, v). Now, observe that f ∗ SOC (ai ,v) k ≤ f ∗MKSP (ai, v) because one of the agents must travel at least f ∗ SOC (ai ,v) k . Since fSOC(ai, v) is a lower bound on f ∗ SOC (ai, v), dividing it by k will yield a lower bound on f ∗MKSP (ai, v).

Costs of Subsets

f ∗MKSP for k agents is determined by the path of one of the agents with the highest cost. Therefore, f ∗MKSP and fMKSP for any subset of these k agents are also lower bounds on f ∗MKSP for all k agents. Thus, for any subset of k′ < k agents, we can compute fMKSP and use it as a lower bound on f ∗MKSP for the entire set of k agents. Therefore, while the right-hand side of the max function in fMKSP(ai, v) (Equation 6) contains all k agents, it can also contain any subset of agents. This can be done by calculating hSOC(ai, v) for the selected subset of k′ < k agents and dividing it by k′ instead of k. Figure 1(a,b) shows examples of MAM problem instances for MKSP. In both cases, the optimal MKSP is 5 at location t. Assume a perfect heuristic for SOC. For Figure 1(a), the optimal SOC is 12 at location v. Thus, for each agent ai, fSOC(ai, si) = 12, and, by computing MKSP for all agents, we get fMKSP(ai, si) = 12/3 = 4. Now, consider the subset of agents {a1, a2}. Their SOC is 10, and hence fMKSP(ai, si) = 10/2 = 5. For Figure 1(b), the optimal SOC is 15 at location t, and thus fSOC (ai, si) = 15. By computing MKSP for all agents, we get fMKSP (ai, si) = 15/3 = 5 but the SOC of the subset of agents {a1, a2} is 8, and hence fMKSP(ai, si) = 8/2 = 4. This shows that there is no best subset for all cases. In our experiments, we used all combinations of pairs of agents, in addition to the set of all agents. It is future work to investigate additional subset selection policies.

5 MM&MM* - Similarities and Differences

It is very interesting that fMKSP is a generalization of the priority function of the MM algorithm: pr(n) = max(2g(n), g(n) + h(n)) [Holte et al., 2016].

If we divide this expression by two, we get pr(n) = max(g(n), g(n)+h(n) 2 ). This is a special case of the proposed fMKSP for k = 2 (h(n) is equivalent to an estimate of the cost from the start location of the backward agent, the goal in MM, to the current location of the forward agent). MM prioritizes nodes based on MKSP to keep MM restrained [Shaham et al., 2017], i.e., to never expand nodes with g(n) > C∗ 2 .

In Figure 1(c), we illustrate the difference between MM and MM* (for MKSP with 2 agents) with regard to halting. Both algorithms start by inserting s1 and s2 into OPEN. Next, both algorithms expand s1 and generate x and s2. MM sets pr(x) = 12 and pr(s2) = 10 (from the forward side; hF (x) = 6 and hF (s2) = 0), and U = 10 because a path of cost 10 has been found. At this point, MM halts, as U ≤ fmin = 10, so a path of smaller cost cannot be found. By contrast, MM* sets fMKSP(a1, x) = g(a1, x) = 6 and fMKSP(a1, s2) = g(a1, s2) = 10, and U = 10 because a meeting location with cost 10 has been found. Unlike MM, MM* continues to search because a better meeting location might be found as fmin = fMKSP(a1, x) = 6. While U is similar for both algorithms, the priorities of MM* are half of the ones of MM. So, MM* continues and returns either x or y as meeting location. For SOC, it returns s2 as meeting location with cost 10, as it is on a path of minimal cost.

6 Theoretical Analysis

Lemma 1 (Completeness). MM* is guarantees to return a solution if one exists, and U = ∞ otherwise.

Proof outline. For each agent ai, MM* performs a best-first search from si. In the worst case, MM* explores every reachable location for each agent. If a solution exists, a location reachable for all agents will be generated from all directions and U will be updated. At some point, either fmin will reach U or the entire graph will have been explored for all agents (OPEN will be empty), and a solution will be returned. If no solution exists, there is no location that is reachable for all agents and U will not be updated and thus remains ∞. □

Lemma 2 (Optimality). Given an admissible f (i.e., f(n) ≤ f ∗ (n) for all nodes n), MM* is guaranteed to return the optimal location t∗ with cost C ∗ .

Proof outline. Assume, by contradiction, that MM* returned a sub-optimal location t ̸= t∗ with cost C > C ∗ . Since MM* has terminated and returned a solution, fmin ≥ C > C ∗ . Since MM* terminated without returning an optimal solution, there exists a node n′ = (ai, vi) in OPEN s.t. vi is a location on the optimal path of ai to t∗ , and every node before n′ on the path has already been expanded. Since n′ is the first node on the optimal path that was not expanded, it was generated by a node on the optimal path, and thus g(n′ ) = d(si, vi). By definition, f ∗ (n′ ) is the cost of the optimal solution that passes through n′ . Therefore, since g(n′ ) = d(si, vi), f ∗ (n′ ) = C ∗ . f is admissible. Thus, f(n′ ) ≤ f ∗ (n′ ) = C ∗ . As n′ ∈ OPEN, fmin ≤ f(n′ ) ≤ f ∗ (n′ ) = C ∗ , which contradicts the fact that fmin ≥ C > C ∗ . □

7 Heuristics for MM*

We now introduce a number of heuristics for SOC and prove their admissibility. They are plugged directly into fSOC(ai, v) = g(ai, v) + hSOC(ai, v) and used indirectly for fMKSP as shown in Equation 6. Let t∗ (ai, v) be the optimal meeting location where ai passes through v. For simplicity, we use ˆ t∗ to denote t∗ (ai, v) and h(ai, v) to denote hSOC(ai, v). Recall that S is the set of all start locations. Let Si(v) be the set of all start locations in S, except for si, which is replaced with v (the current location of ai). Formally, Si(v) = S \ {si} ∪ {v}. Then, h∗SOC (ai, v) = ∑v′∈Si(v) d(v′ , ˆ t∗ ) (from Equation 3), and we want to find a lower bound on it. 3

7.1 h1 : Clique Heuristic

We assume that, for every pair of locations (v1, v2), there exists a classic admissible heuristic h (e.g., straight-line distance or Manhattan distance), such that h(v1, v2) ≤ d(v1, v2).

Based on the triangle inequality, for every pair of locations v1, v2 ∈ Si(v) (with v1 ̸= v2), we have that:

By summing over all such pairs, we get:

As each v′ ∈ Si(v) is paired with k - 1 other locations in Si(v), we can rewrite the right-hand side of Equation 8 as (k -1) · ∑v′∈Si(v) d(v′ , ˆ t∗ ). Therefore:

Now, since h(v1, v2) ≤ d(v1, v2), we get that:

This heuristic h1 is called the Clique heuristic, as it combines the heuristic values of every (unordered) pair of locations in Si(v). Figure 1(d) presents an example of the clique heuristic for three agents. For node (a1, s1), S1(s1) = {s1, s2, s3}. Therefore, h(a1, s1) = h(s1,s2)+h(s1,s3)+h(s2,s3) 2 = 3+3+6 2 = 6.

For each start location si ∈ S, Si(si) = S and hence h1 can be calculated once for all start locations. For each location v that is not a start location, all locations in Si(v) except for v remain the same. So, h1 can be calculated incrementally in time that is linear in the number of agents. If h(v1, v2) is consistent, then h1 is also consistent.

3 This is a form of a front-to-end heuristic. A front-to-front heuristic needs to estimate the remaining costs when all other agents are in their current locations, but these locations thus need to be specified for a given node (ai, v). This is left for future work.

7.2 h2 : Median Heuristic

For a set of numbers B ⊂ R, the median of B provably minimizes the sum of the absolute deviations, i.e., argminr∈R ∑b∈B |b - r| = median(B). Inspired by this property, we design the Median heuristic (h2) for 4-neighbor 2D grids. On such a grid, each location has two coordinates - x and y. For a set of locations, we can find the median over the x-coordinates (dimension 1) of all locations and the median over the y-coordinates (dimension 2) of all locations. Let tmd be the median of dimension d. This creates a potential meeting location tm = (tm1, tm2), that minimizes the sum of the absolute deviations over both dimensions. Namely, if there are no obstacles on the grid, tm will be the optimal meeting location for minimizing SOC. This is due to the fact that the distance between any two locations is their L1-distance (also known as Manhattan distance on 2D grids).

Assume that the input graph G = (V,E) is a 4-neighbor 2D grid where every location v ∈ V is represented by its coordinates ⃗v = (v1, v2). The L1-distance for any two locations u, v ∈ V is defined as ||⃗u - ⃗v||1 = |u1 - v1| + |u2 - v2|. Due to the existence of obstacles, for any pair of locations u, v ∈ V , ||⃗u -⃗v||1 ≤ d(u, v). So, for a given node (ai, v),

Therefore, by modeling the problem in an empty 2D L1-space (i.e., without obstacles), we introduce a new admissible (and consistent) heuristic, called Median heuristic:

It is admissible because the right-hand side of Equation 12 is no larger than the left-hand side of Equation 11.

We use the Quick-select algorithm for finding medians [Hoare, 1961], which runs in Θ(k) time, to compute h2(ai, si) for all root nodes. Then, for every non-root node (ai, v) (i.e., v ̸= si), k - 1 locations have not changed, and we only need to update the median based on the single location that has changed. This can be done in O(1) time.

Figure 1(e) shows an example of a MAM problem instance with three agents (s1, s2, and s3) that are located in (1, 1), (3, 1), and (1, 2). The x-coordinates are {1,3,1} and the y-coordinates are {1,1,2}. Thus, the median location is (1, 1). By computing the Manhattan distances from (1, 1) to each start location, we get h2(ai, si) = 3 for each agent ai.

h2 can be generalized easily for 6-neighbor 3D grids and similar graphs of higher dimensions.

7.3 h3 : FastMap Heuristic

The Median heuristic (h2) only works for graphs that have coordinates. In addition, h2 ignores obstacles, which may introduce inaccuracies to the heuristic. The FastMap heuristic

(h3) handles this. FastMap [Cohen et al., 2018; Li et al., 2019] is a near-linear preprocessing algorithm that embeds the locations of a given edge-weighted undirected connected graph G = (V, E) into a D-dimensional L1-space RD . The dimension D of the L1-space is user-specified. Each location vi ∈ V is mapped to a D-dimensional point ⃗ pi ∈ RD . The length of a shortest path d(vi, vj) between any two locations vi, vj ∈ V is approximated by the L1-distance ||⃗ pi - ⃗ pj ||1 between the corresponding two points ⃗ pi, ⃗ pj ∈ RD in this space. FastMap ensures that the L1-distance in RD can be used as an admissible and consistent heuristic for the shortest path computation in G. See [Cohen et al., 2018] for more details on FastMap. To compute h-values for MAM, h3 applies the Median heuristic on the generated embedding RD . For any node (ai, v), its FastMap heuristic is defined as:

where ⃗ p′ ∈ RD is the point of the embedding of location v′ generated by FastMap. By the same analysis as for h2, we can show that the FastMap heuristic (h3) is admissible (and consistent), and we can compute it for every root node in Θ(kD) time and for any non-root node in O(D) time.

There are many other approaches for embedding a graph in a continuous space, such as [Ng and Zhang, 2002; Shavitt and Tankel, 2004; Rayner et al., 2011]. However, most of them use L2-distances, which are not applicable here because the L2-distance version of Equation 15 is NP-hard to solve optimally [Hoare, 1961].

8 Experimental Results

We experimented with MM* on an Intel R© Xeon E5-2660 v4 @2.00GHz processor with 16GB of RAM. We compared all new heuristics to the Dijkstra version of MM*, i.e. where h = 0 (denoted by h0), on different grids while minimizing both SOC and MKSP. For h1, we used the Manhattan Distance (MD) as a classic admissible heuristic between any two locations. The number of dimensions D for h3 was always set to 10, as suggested by Li et al. [2019].

8.1 SOC

We experimented on a 500 × 500 grid with 0% - 30% obstacles. Table 1(left) shows the average over 50 instances of: the solution cost, the initial h-value, the number of expansions, and the CPU time for 5 randomly placed agents. h2 had the best initial h-value, had the lowest number of expansions, and was the fastest. The initial h-values of h1 (MD) and h2 remain constant as more obstacles are added since they both ignore obstacles. By contrast, h3 increases as more obstacles are added. So, h2 degrades while h3 improves, in terms of number of expansions and CPU time. h3 incurred a preprocessing time of ≈ 30s, which is incurred only once per grid and thus amortized over multiple problem instances.

We also fixed the number of obstacles at 10% while varying the number of agents from 3 to 9. Table 2(left) shows the CPU time for SOC. Here, too, h2 was the best heuristic with only 1.27s for 9 agents because h2 is suitable for grids with small numbers of obstacles.

/ SOC time / expansions / MKSP time / expansions

MKSP

#Obs. 0% 10% 20% 30% 0% 10% 20% 30%

995 1,008 1,033 1,103 292 293 295 305

0

0

0

0

828 828 828 828 166 166 166 166

995 995 995 995 199 199 199 199

643 680 736 778 127 137 140 148

#Expansions (thousands)

h0 1,244 1,120 994 856 542 485 420 341

330 322 320 318 180 159 133 121

83 143 179 158 132 119

634 561 465 402 308 299 239 197

h0 22.05 19.04 16.10 13.04 7.81 6.69 5.47 4.10

4.50 4.29 4.18 4.01 2.83 2.43 1.94 1.66

0.28 0.54 0.77 1.40 2.79 2.40 1.93 1.64

9.48 8.66 6.81 5.60 6.99 5.44 4.12 4.00

Finally, we experimented on the 768 × 768 Enigma grid (presented in Figure 2(a)) from the Starcraft video game, available in the movingai repository [Sturtevant, 2012]. Figures 2(b) and 2(c) show the average number of expansions and CPU time, respectively, for 3 to 9 agents for SOC. Here, h3 was the best heuristic in both expansions and time. Since this grid has many obstacles (about 57%), h1 and h2 were less effective than h3, which uses real distances (albeit in the embedded graph). Nevertheless, h3 required a preprocessing time of 39s for this grid (done once). h2 was the second best heuristic but h2 is only suited for grids while h1 can be used on any graph. For 9 agents, h1 expanded slightly fewer nodes than h0 but, since it consumes time for computing the heuristic, was a little slower than h0.

8.2 MKSP

As described in Section 4, there are different policies for choosing subsets for computing MKSP. We compared two of these policies: (1) selecting all agents and (2) selecting all agents plus all pairs of agents and taking the maximum over all of those. Figure 3 shows the number of expansions and CPU time averaged over 50 instances for h3 on the Enigma grid with 3 to 9 agents. As expected, adding all pairs of agents produces a better heuristic and fewer expansions. It was also better in terms of the CPU time despite the fact that its computation overhead is larger. Therefore, we used this subset selection policy for computing MKSP. It is future work to investigate different policies for choosing subsets.

We repeated the same experiments (reported for SOC) for MKSP. Table 1(right) presents the results. Here, too, h2 was the best heuristic but here (unlike SOC) h1 was very close to h2. This is so probably because the clique heuristic (h1) for MKSP also guides the agents to the median.

The same trends were observed for different numbers of agents with 10% obstacles and are presented in Table 2(right).

In the Enigma grid for MKSP (Figures 2(d,e)), h3 was again the best heuristic. h1 and h2 (curves cover each other) had fewer numbers of expansion but were slower than h0.

9 Conclusions

We introduced the multi-directional search algorithm MM* that optimally solves MAM. We proved that MM* is complete and optimal and suggested a few admissible heuristics. Experimentally, we showed that MM* performs better with heuristics. For grids with few obstacles, h2 is best. For grids with many obstacles, h3 is best but requires preprocessing. The advantage of h1 is that it is applicable to all domains without the need for preprocessing. Future work will: (1) develop a weighted version of MM* that can find boundedsuboptimal solutions, (2) extend MM* to a Euclidean space, and (3) further investigate subset selection for MKSP.

Acknowledgements

This research was supported by ISF grant 844/17 and BSF grant 2017692 to Ariel Felner, NSF grant 1815660 to Nathan R. Sturtevant and NSF grants 1409987, 1724392, 1817189, 1837779 and 1935712 to Sven Koenig.