3 · What the planner says for every goal
Every candidate goal gets a score for “how well does it explain what R_ed did so far?”, then the scores are turned into beliefs that add up to 1. Three steps:
What do the symbols mean? (click to open)
- G
- A candidate goal: one of the 12 words R_ed might be building.
- O, t
- O is the list of R_ed's moves seen so far, in order; t is how many (the “step”).
- c(G+O)
- Number of moves of the cheapest plan that reaches G and performs all of O in order.
- c(G+Ō)
- Number of moves of the cheapest plan that reaches G but does not perform all of O in order (missing even one observed move is enough). ∞ means no such plan exists.
- β
- How strictly R_ed is assumed to avoid wasted moves. With β = 0 the cost gap is ignored; the larger β, the more one extra move counts.
- P(O|G), likelihood
- How expected the observed moves are if G were the goal. Near 1: supports G. 0.5: neutral. Near 0: speaks against G.
- c*(G)
- The cheapest possible plan for G from the very start: the earliest moment a plan for G could be finished.
- ε
- Foresight: how many steps ahead the prior looks. ε = 0 means no foresight.
- t′
- t′ = t + ε, the moment at which the prior is evaluated.
- λ
- How many extra (wasted) moves R_ed is expected to make beyond the optimal plan; it shapes the prior.
- P(t′|G), prior
- The probability that a plan for G has not finished yet at time t′ (“survival”). It is 1 while t′ ≤ c*(G) and shrinks afterwards.
- Z
- Normalising constant: the sum over all goals of likelihood × prior (the bottom row of the table).
- P(G|O,t), posterior
- The belief in G after seeing O at time t. This is the number the helper uses.
1 · Likelihood P(O|G) = e−β·c(G+O) / ( e−β·c(G+O) + e−β·c(G+Ō) )
“If her goal were G, how natural are the moves I have seen?” It compares two plan costs: the cheapest plan that does what was observed (G+O) and the cheapest that does not (G+Ō). If following the observed moves is cheaper, the likelihood is above 0.5; if equal, exactly 0.5.
2 · Dynamic prior P(t′|G), t′ = t + ε
“Before weighing the moves: how plausible is it that a plan for G is still running after t′ steps?” A goal whose cheapest plan is short should already be finished by now, so it loses weight; long goals stay plausible. ε looks a few steps ahead.
3 · Posterior (the belief) P(G|O,t) = P(O|G) · P(t′|G) / Z
Bayes' rule: belief ∝ likelihood × prior. Z is the sum of (likelihood × prior) over all 12 goals; dividing by it makes the 12 beliefs add up to 1.
What does each table column show? (click to open)
- goal
- The candidate word. ★ marks R_ed's real, hidden goal; the observer does not know it, it is shown so that you can see whether the recognition is right.
- c*(G)
- The length of the shortest possible plan for this word from the start (HER 6 moves, MASTER 16, BOTHER 22). It never changes. It is the earliest time at which a plan for this goal could be finished, and the prior uses it.
- c(G+O)
- The planner's cheapest plan that reaches G and also performs everything observed so far, in order. If the observed moves fit a shortest plan for G, this equals c*(G); each observed move that is a detour for G makes it larger.
- c(G+Ō)
- The cheapest plan that reaches G but does not perform the whole observed sequence in order. It shows how cheaply G can be reached while ignoring what was seen. ∞ means that no such plan exists: the observed moves cannot be avoided for this goal.
- gap
- gap = c(G+Ō) − c(G+O). Negative: following the observed moves costs extra, so a rational agent aiming at G would have avoided them: evidence against G (HER at step 6: 6 − 10 = −4). 0: following or avoiding them costs the same: no evidence (MASTER: 16 − 16). ∞: the moves cannot be avoided at all: strongest support.
- P(O|G)
- Likelihood: how expected the observed moves are if G were R_ed's goal. It is computed from the gap: P(O|G) = e−β·c(G+O) / ( e−β·c(G+O) + e−β·c(G+Ō) ), which is the same as 1 / (1 + e−β·gap). Every move of gap multiplies the odds by eβ (about 2.7 for β = 1). Worked values for β = 1: gap 0 → 0.5; gap −1 → 0.269; gap −2 → 0.119; gap −4 → 0.018; gap ∞ → 1. So it reads like a probability that is neutral at 0.5, drops quickly as the observed moves become costly for G, and is exactly 1 when they are unavoidable. It is not yet the belief in G: it ignores how long the plan is expected to run.
- t′
- The time at which the prior is evaluated: t′ = t + ε, the number of observed moves plus the foresight ε. Shown as “–” when the belief is “likelihood only”.
- P(t′|G)
- Dynamic prior (survival): the probability that a plan for G is still running at time t′. It is 1 while t′ ≤ c*(G), because the plan cannot have finished yet, and it falls after that, since real plans usually end soon after their optimal length. A short goal such as HER has almost certainly ended by t′ = 9 (0.165); a long one such as BOTHER has not (1).
- P(O|G)·P(t′|G)
- The score of the goal: the likelihood (do the moves fit?) times the prior (is the plan still running?). A goal needs both to score high. Scores are not probabilities yet; their sum is Z, in the bottom row.
- P(G|O,t)
- Posterior: the belief in G. The score divided by Z, so that the 12 beliefs add up to 1 (bottom row). This is the final answer of the recognition, and it is what panel 5 uses to decide which conditions are needed.
4 · One goal in detail
5 · Necessity and the helper's estimated goal
Beliefs about goals are turned into facts about what must be built, so that the helper has something concrete to work toward.
Necessity N(p | O) = ΣG P(G|O,t) · 𝟙(p ∈ G)
p is a goal condition such as “S on T”. 𝟙(p ∈ G) is 1 if the goal word G contains p and 0 if not. So N(p) is the total belief of all the goals that need p: 1 means every likely goal needs it; 0 means none does.
Estimated goal ĜRed = { p : N(p|O) ≥ τ }
The conditions that are needed with enough confidence (at least the threshold τ). ĜRed is what R_ing tries to help with. If two of its conditions cannot both be true at once (a conflict), no plan exists and R_ing waits.