
## A Criterion Of Θ**-Admissibility**

It is fairly easy to come up with an example of a policy that does not satisfy the "max of min" condition and, consequently, does not preserve the θ-admissibility of the heuristic. Remarkably, heuristic updates more aggressive than those dictated by the "max of min" rule that do preserve θ-admissibility are also possible.

An example of each phenomenon is found in Figure A.1.

![0_image_0.png](0_image_0.png)

$$(\mathbf{A.1})$$

Figure A.1: **Left:** a three-state search problem with the current state s and the search neighborhood including the middle state. The heuristic values are shown in the states as ht/h∗. Each edge has the cost of 1.

Increasing the heuristic in state s above the value of 2 dictated by the "max of min" rule will break 1admissibility of the heuristic. **Right:** The same three-state search problem where the value of state s can be increased to 2, thus exceeding the 1 dictated by the "max of min" rule. Yet the 1-admissibility will be preserved.

It turns out that the "max of min" rule is a sufficient but not necessary condition for preserving θadmissibility. However, the "max of min" rule can be strengthened into a necessary condition as follows.

Specifically, with a slight modification to the "max of min" condition based on Definition 17, the criterion in Theorem A.1 is proved.

Definition 17 For any Γ ⊂ S, let us define the function h

$$\iota\,h_{t}^{\Gamma}\,\,\mathrm{as}.$$
$$\subset{\mathcal{S}},$$
$$h_{t}^{\Gamma}(s)=\operatorname*{max}_{s^{\prime}\in\Gamma}\left\{h_{t}(s),h_{t}(s^{\prime})-\theta\operatorname{dist}(s,s^{\prime})\right\}$$
$\mathbf{a}=\mathbf{a}$. 
0) − θ dist(*s, s*0)	(A.1)
where ht(s) is the heuristic value of state s at time t. The idea underlying h Γ
t
(s) is that if the heuristic ht(s)
is θ-admissible in all states at time t, then for any state s it can actually be increased at least to the value of its arbitrary neighbor s 0 minus the shortest distance from s to s 0.

Definition 18 We say that a search obeys a strengthened "max of min" condition if at any time t:

$$\forall s\in\Gamma^{*}(\sigma_{t})\left[h_{t+1}(s)\leq\max_{J\in\mathfrak{D}^{*}(s,\Gamma^{*}(\sigma_{t}))}\left(\min_{s^{\prime}\in J}\left[\theta\operatorname{dist}(s,s^{\prime})+h_{t}^{\Gamma^{*}(\sigma_{t})}(s^{\prime})\right]\right)\right],$$ (A.2)
where Γ
∗(σt) is the union of all neighborhoods considered by the policy up to the time t. Formally, Γ
∗(σt) =
∪t 0≤tΓ(σt). Additionally, D∗(s, Γ) = D(s, Γ) *∪ {{*s}}. The "raised" heuristic h Γ
∗(σt)
t(s 0) comes from Definition 17.

Theorem A.1 (maximum heuristic increase criterion). Suppose we start with θ-admissible heuristic h such that h(s) = 0 ⇐⇒ s ∈ Sg. Then as long as Γ
∗(σt) ∩ Sg = Ø, the condition of θ-admissibility
(Equation (4.5)) and the strengthened "max of mins" condition are interchangeable in the definition of θadmissible policy π.