2
$\begingroup$

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$).

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.