# Is the minimum and maximum of a set of admissible and consistent heuristics also consistent and admissible?

Let's suppose I have a set of heuristics $$H$$ = {$$h_1, h_2, ..., h_N$$}.

1. If all heuristics in $$H$$ are admissible, does that mean that a heuristic that takes the $$\min(H)$$ (or $$\max(H)$$ for that matter) is also admissible?

2. If all heuristics in $$H$$ are consistent, does that mean that a heuristic that takes the $$\min(H)$$ (or $$max(H)$$ for that matter) is also consistent?

I'm thinking about a search problem in a bi-dimensional grid that every iteration of an algorithm, the agent will have to find a different goal. Therefore, depending on the goal node, a certain heuristic can possibly better guide the agent than the others (hence the use of $$\min$$ and $$\max$$).

Yes, in both cases. Below I give two very simple proofs that directly follow from the definitions of admissible and consistent heuristics. However, in a nutshell, the idea of the proofs is that $$h_{\max}(n)$$ and $$h_{\min}(n)$$ are, by definition (of $$h_{\max}$$ and $$h_{\min}$$), equal to one of the given admissible (or consistent) heuristics, for all nodes $$n$$, so $$h_{\max}(n)$$ and $$h_{\min}(n)$$ are consequently admissible (or consistent).

## Definitions

Consider the graph $$G=(V, E, \mathcal{G})$$ representing the search space, where $$V$$, $$E$$ and $$\mathcal{G} \subseteq V$$ are respectively the set of nodes, edges and goal nodes, and the function $$w\colon E \times E \rightarrow \mathbb{R}$$, which gives you the cost of each edge $$e = (u, v) \in E$$, where $$u, v \in V$$, that is, $$w(e) = w(u, v) \in \mathbb{R}$$ is the cost of the edge $$e$$.

A heuristic $$h$$ is admissible if $$h(n) \leq h^*(n), \forall n \in V,$$ where $$h^*(n)$$ is the optimal cost to reach a goal from node $$n$$ (that is, it is the optimal heuristic).

On the other hand, a heuristic $$h$$ is consistent if

\begin{align} h(n) &\leq w(n, s) + h(s), \forall n \in V \setminus \mathcal{G}, \text{ and} \\ h(n) &= 0, \forall n \in \mathcal{G}, \end{align} where $$s$$ is a successor of $$n$$.

## Theorem 1

Given a set of admissible heuristics $$H = \{ h_1, \dots, h_N \}$$, then, for every $$n \in V$$, the heuristics $$h_{\max}(n) = \max(h_1(n), \dots, h_N(n))$$ and $$h_{\min}(n) = \min(h_1(n), \dots, h_N(n))$$ are also admissible.

### Proof

Given that, $$h_i(n) \leq h^*(n), \forall n \in V$$ and $$\forall i \in \{ 1, \dots N \}$$, then $$h_{\max}(n) = h_j(n) \leq h^*(n)$$ (for some $$j \in \{ 1, \dots N \}$$) and $$h_{\min}(n) = h_k(n) \leq h^*(n)$$ (for some $$k \in \{ 1, \dots N \}$$), so $$h_{\max}$$ and $$h_{\min}$$ are also admissible.

$$\tag*{\blacksquare}$$

## Theorem 2

Given a set of consistent heuristics $$H = \{ h_1, \dots, h_N \}$$, then, for every $$n \in V$$, the heuristics $$h_{\max}(n) = \max(h_1(n), \dots, h_N(n))$$ and $$h_{\min}(n) = \min(h_1(n), \dots, h_N(n))$$ are also consistent.

### Proof

Given that, for every $$i \in \{ 1, \dots, N \}$$,

\begin{align} \begin{cases} h_i(n) \leq w(n, s) + h_i(s), & \text{ if } n \in V \setminus \mathcal{G}\\ h_i(n) = 0, & \text{ if } n \in \mathcal{G} \end{cases} \end{align}

then, if $$n \in V \setminus \mathcal{G}$$, $$h_{\max}(n) = h_j(n) \leq w(n, s) + h_j(s)$$, for some $$j \in \{1, \dots, N \}$$, and, similarly, $$h_{\min}(n) = h_k(n) \leq w(n, s) + h_{k}(s)$$, for some $$k \in \{1, \dots, N \}$$. Similarly, if $$n \in \mathcal{G}$$, $$h_{\max}(n) = h_{\min}(n) = h_i(n) = 0, \forall i \in \{1, \dots, N \}$$. Thus, $$h_{\max}$$ and $$h_{\min}$$ are also consistent.

$$\tag*{\blacksquare}$$

## Notes

$$h_{\max}$$ and $$h_{\min}$$ have been defined in the only possible reasonable way, because, given two (admissible or consistent) heuristics, one may not always dominate the other (or vice-versa), even if both are admissible and consistent.

• When you say "hmax(n)=hj(n)≤w(n,s)+hj(s), for some j∈{1,…,N}", aren't you implicity assuming nodes n and s both using ith heuristic, but this may not be the case. What you need to show is "hmax(n) = hi(n) ≤ w(n, s) + hj(s), for some i,j ∈{1,…,N}" or am I mistaken? Oct 21, 2021 at 1:10