Planning Questions and Answers

Answer: C

Summing the individual estimates assumes the subgoals are independent, which overestimates when actions achieve several at once, so it is informative but inadmissible. The maximum is admissible but weak, and the relaxed plan length lies between. Counting unsatisfied goals is a much cruder estimate. Choosing between an admissible weak estimate and an inadmissible strong one is a decision about whether optimality or speed is required. Framing the question as which quantity the change acts upon makes the answer follow without calculation.

Answer: D

If one action makes three goal atoms true, counting each separately triples the cost of that action and the total may exceed the true optimum. Ignoring positive interactions is exactly the assumption of independence. The relaxation is genuine and the individual estimates are themselves admissible. Recognising that combining admissible estimates by addition destroys admissibility, unless the subproblems are disjoint, is the same condition that governs additive pattern databases.

Answer: A

Extracting an actual plan for the relaxed problem, and counting its actions, accounts for the positive interactions that the additive heuristic double counts. It is inadmissible, since the extracted plan need not be optimal, but is highly informative and cheap. The other options describe different quantities. A heuristic obtained by solving a relaxation rather than estimating it is more expensive per node and usually repays the cost many times over.

Answer: B

The graph builds alternating fact and action layers, recording which pairs cannot hold or occur together, and is constructed in polynomial time. It supports both a strong heuristic and the GraphPlan extraction algorithm. State graphs, constraint graphs and task hierarchies are different structures. A polynomial structure that bounds the solution and guides the search, without solving the problem, is an unusually productive device. Reading the definition literally, rather than recalling a formula, is the reliable route through questions of this shape.

Answer: C

Two actions are mutually exclusive if one deletes the other's precondition or effect, or if their preconditions are mutex, and the relation propagates through the layers. It records the interactions the relaxation ignores. Ordering constraints, deletion and variable constraints are different notions. Capturing pairwise incompatibility, without attempting full consistency, is the compromise that keeps the construction polynomial.

Answer: D

Considering triples and larger subsets would raise the cost sharply, so the construction settles for pairs and accepts that some conflicts are detected only during extraction. Larger conflicts certainly exist and the algorithm could in principle use them. Choosing the level of consistency at which the cost is still polynomial is the same decision as choosing arc rather than path consistency in a constraint problem.

Answer: A

A partial order planner adds actions and causal links, committing to an ordering between two actions only when a conflict requires it. The result is a plan any linearisation of which works, which suits parallel execution. Partial goals, post hoc ordering and multiple plans are different notions. Deferring a commitment until it is forced is the principle of least commitment, and it is the organising idea of the whole approach.

Answer: B

By leaving orderings and variable bindings open until a conflict compels a decision, the planner avoids backtracking over choices that never mattered. The same principle produces the most general unifier in resolution. Early commitment, minimal repair and precondition counting are different notions. A principle that appears independently in planning, unification and constraint solving is worth recognising in its general form.

Answer: C

The link records that a particular action supplies a particular condition needed by another, so any action threatening that condition must be ordered outside the interval. It is what makes threats detectable. Bare orderings carry no such information, and the other options describe different relations. Recording why an ordering exists, rather than only that it does, is what allows the planner to detect when it has been violated.

Answer: D

A threatening action deletes the protected condition and could fall between the producer and the consumer, so it must be ordered before the producer or after the consumer. Those two resolutions are called demotion and promotion. Unachievable preconditions, conflicting goals and cycles are different failures. A conflict detected structurally, with exactly two possible repairs, gives a clean branching point for the search.