Answers.Body: <p>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 <span class="math-container">$h_{\max}(n)$</span> and <span class="math-container">$h_{\min}(n)$</span> are, <strong>by definition</strong> (of <span class="math-container">$h_{\max}$</span> and <span class="math-container">$h_{\min}$</span>), equal to one of the given admissible (or consistent) heuristics, for all nodes <span class="math-container">$n$</span>, so <span class="math-container">$h_{\max}(n)$</span> and <span class="math-container">$h_{\min}(n)$</span> are consequently admissible (or consistent).</p>
  
  <h2>Definitions</h2>
  
  <p>Consider the graph <span class="math-container">$G=(V, E, \mathcal{G})$</span> representing the search space, where <span class="math-container">$V$</span>, <span class="math-container">$E$</span> and <span class="math-container">$\mathcal{G} \subseteq V$</span> are respectively the set of nodes, edges and goal nodes, and the function <span class="math-container">$w\colon E \times E \rightarrow \mathbb{R}$</span>, which gives you the cost of each edge <span class="math-container">$e = (u, v) \in E$</span>, where <span class="math-container">$u, v \in V$</span>, that is, <span class="math-container">$w(e) = w(u, v) \in \mathbb{R}$</span> is the cost of the edge <span class="math-container">$e$</span>.</p>
  
  <p>A heuristic <span class="math-container">$h$</span> is admissible if <span class="math-container">$$h(n) \leq h^*(n), \forall n \in V,$$</span>
  where <span class="math-container">$h^*(n)$</span> is the optimal cost to reach a goal from node <span class="math-container">$n$</span> (that is, it is the optimal heuristic).</p>
  
  <p>On the other hand, a heuristic <span class="math-container">$h$</span> is consistent if</p>
  
  <p><span class="math-container">\begin{align}
  h(n) &amp;\leq w(n, s) + h(s), \forall n \in V \setminus \mathcal{G}, \text{ and} \\
  h(n) &amp;= 0, \forall n \in \mathcal{G},
  \end{align}</span>
  where <span class="math-container">$s$</span> is a successor of <span class="math-container">$n$</span>.</p>
  
  <h2>Theorem 1</h2>
  
  <p>Given a set of admissible heuristics <span class="math-container">$H = \{ h_1, \dots, h_N \}$</span>, then, for every <span class="math-container">$n \in V$</span>, the heuristics <span class="math-container">$h_{\max}(n) = \max(h_1(n), \dots, h_N(n))$</span> and <span class="math-container">$h_{\min}(n) = \min(h_1(n), \dots, h_N(n))$</span> are also admissible.</p>
  
  <h3>Proof</h3>
  
  <p>Given that, <span class="math-container">$h_i(n) \leq h^*(n), \forall n \in V$</span> and <span class="math-container">$\forall i \in \{ 1, \dots N \}$</span>, then <span class="math-container">$h_{\max}(n) = h_j(n) \leq h^*(n)$</span> (for some <span class="math-container">$j \in \{ 1, \dots N \}$</span>)  and <span class="math-container">$h_{\min}(n) = h_k(n) \leq h^*(n)$</span> (for some <span class="math-container">$k \in \{ 1, \dots N \}$</span>), so <span class="math-container">$h_{\max}$</span> and <span class="math-container">$h_{\min}$</span> are also admissible.</p>
  
  <p><span class="math-container">$\tag*{$\blacksquare$}$</span></p>
  
  <h2>Theorem 2</h2>
  
  <p>Given a set of consistent heuristics <span class="math-container">$H = \{ h_1, \dots, h_N \}$</span>, then, for every <span class="math-container">$n \in V$</span>, the heuristics <span class="math-container">$h_{\max}(n) = \max(h_1(n), \dots, h_N(n))$</span> and <span class="math-container">$h_{\min}(n) = \min(h_1(n), \dots, h_N(n))$</span> are also consistent.</p>
  
  <h3>Proof</h3>
  
  <p>Given that, for every <span class="math-container">$i \in \{ 1, \dots, N \}$</span>, </p>
  
  <p><span class="math-container">\begin{align}
  \begin{cases}
  h_i(n) \leq w(n, s) + h_i(s), &amp; \text{ if }  n \in V \setminus \mathcal{G}\\
  h_i(n) = 0, &amp; \text{ if }  n \in \mathcal{G}
  \end{cases}
  \end{align}</span></p>
  
  <p>then, if <span class="math-container">$n \in V \setminus \mathcal{G}$</span>, <span class="math-container">$h_{\max}(n) = h_j(n) \leq w(n, s) + h_j(s)$</span>, for some <span class="math-container">$j \in \{1, \dots, N \}$</span>, and, similarly, <span class="math-container">$h_{\min}(n) = h_k(n) \leq w(n, s) + h_{k}(s)$</span>, for some <span class="math-container">$k \in \{1, \dots, N \}$</span>. Similarly, if <span class="math-container">$n \in \mathcal{G}$</span>, <span class="math-container">$h_{\max}(n) = h_{\min}(n) = h_i(n) = 0, \forall i \in \{1, \dots, N \} $</span>. Thus, <span class="math-container">$h_{\max}$</span> and <span class="math-container">$h_{\min}$</span> are also consistent.</p>
  
  <p><span class="math-container">$\tag*{$\blacksquare$}$</span></p>
  
  <h2>Notes</h2>
  
  <p><span class="math-container">$h_{\max}$</span> and <span class="math-container">$h_{\min}$</span> have been defined in the only possible reasonable way, because, given two (admissible or consistent) heuristics, <a href="https://ai.stackexchange.com/q/15701/2444">one may not always dominate the other (or vice-versa)</a>, even if both are admissible and consistent.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-10-21T01:10:56.670Z
Answers.Text: 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?
Answers.UserDisplayName: unlut
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-11T15:07:38.460Z
Answers.LastActivityDate: 2019-11-11T17:03:57.083Z
Answers.LastEditDate: 2019-11-11T17:03:57.083Z
Answers.UserDisplayName: nbro
Body: <p>Let's suppose I have a set of heuristics <span class="math-container">$H$</span> = {<span class="math-container">$h_1, h_2, ..., h_N$</span>}.</p>
  
  <ol>
  <li><p>If all heuristics in <span class="math-container">$H$</span> are <strong>admissible</strong>, does that mean that a heuristic that takes the <span class="math-container">$\min(H)$</span> (or <span class="math-container">$\max(H)$</span> for that matter) is also admissible?</p></li>
  <li><p>If all heuristics in <span class="math-container">$H$</span> are <strong>consistent</strong>, does that mean that a heuristic that takes the <span class="math-container">$\min(H)$</span> (or <span class="math-container">$max(H)$</span> for that matter) is also consistent?</p></li>
  </ol>
  
  <p>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 <span class="math-container">$\min$</span> and <span class="math-container">$\max$</span>).</p>
  
Tags: <search><proofs><heuristics><admissible-heuristic><consistent-heuristic>
Title: Is the minimum and maximum of a set of admissible and consistent heuristics also consistent and admissible?
UserDisplayName: ihavenoidea
ThreadText: # Is the minimum and maximum of a set of admissible and consistent heuristics also consistent and admissible?
  
  (Asked by: username_0 on 2019-04-10)
  
  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$).
  
  **Tags:** search, proofs, heuristics, admissible-heuristic, consistent-heuristic
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-11-11. Score: 2 | Accepted answer
  
  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)](https://ai.stackexchange.com/q/15701/2444), even if both are admissible and consistent.
  
  > **Comments:**
  > **username_2**: 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?  
  
  ---
  
  