root labeled by T, (b) leaves labeled by φ (in order), and (c) each internal vertex is decomposed into its children (in order) by some m ∈ M. For such internal vertices, say v, let T(v), m(v), and θ(v) be the associated task, reducing method, and prior probability of that reduction. The prior probability of an entire parse tree is the product of θ(v) over every internal vertex v. Given a fixed root, the prior probability of a primitive sequence is the sum of prior probabilities of every parse of that sequence with the fixed root:

$$P(\phi\mid{\mathcal{H}},T)=\sum_{\mathrm{\scriptsize~parse}\;{\mathcal{X}}}P({\mathcal{X}}\mid T,{\mathcal{H}})$$ $$=\sum_{\mathrm{\scriptsize~parse}\;{\mathcal{X}}}\prod_{v}\theta(v);$$
(1)  $\binom{2}{1}$  . 
note that the prior probability of a primitive sequence has nothing to do with whether or not the sequence is goal-achieving or even executable. Enumerating all parses could, however, become expensive, so in the remainder we approximate by considering only the most probable parse of φ - define:

$$\mathcal{X}^{*}(\phi)=\operatorname*{argmax}_{\text{parse}\mathcal{X}\text{of}\phi}\prod_{\text{internal}v}\theta(v).\tag{3}$$

Learning pHTNs. We can now state the pHTN learning problem formally. Fix the total number of task symbols, k, and fix the first task symbol as the top level task T. Given a set Φ of observed training plans (so each is executable and (presumably) goal-achieving), find the most likely pHTN domain, H∗. We assume a uniform prior distribution on domains with k task symbols, so it is equivalent to maximizing the likelihood of the observation:

$$\mathcal{H}^{*}=\operatorname{argmax}_{\mathcal{H}}P(\mathcal{H}\mid\Phi,T)$$ $$=\operatorname{argmax}_{\mathcal{H}}P(\Phi\mid\mathcal{H},T)\cdot\frac{P(\mathcal{H}\mid T)}{P(\Phi\mid T)}$$ $$=\operatorname{argmax}_{\mathcal{H}}P(\Phi\mid\mathcal{H},T)\qquad\qquad\left(\frac{P(\mathcal{H}\mid T)}{P(\Phi\mid T)}=\frac{\text{uniform prior}}{\text{constant}}\right)$$ $$=\operatorname{argmax}_{\mathcal{H}}\prod_{\phi\in\Phi}P(\phi\mid\mathcal{H},T).\tag{1}$$  $\mathcal{H}^{*}=\operatorname{argmax}_{\mathcal{H}}P(\Phi\mid\mathcal{H},T)$.  
Remark. The preceding incorporates several simplifying assumptions, most importantly we are making the connection to context-free grammars as strong as

$$(4)$$
$$\begin{array}{c}{{|}}\\ {{}}\\ {{(5)}}\end{array}$$
