Planning Questions and Answers

Answer: C

The classical setting assumes actions have known deterministic effects, the state is fully known, nothing changes except by the agent's actions, and time is a sequence of discrete steps. Each assumption relaxed produces a named extension. Recognising that the classical formalism is the point at every dimension of the environment taxonomy where the problem is easiest explains why so many extensions exist and what each of them costs. A single measurement chosen to respond to the one asymmetry beats several that respond to shared behaviour.

Answer: D

Uncertain effects call for a probabilistic model, typically a Markov decision process, whose solution is a policy rather than a sequence. Conformant planning addresses an unknown initial state with deterministic actions, and the other two relax quite different assumptions. Matching an extension to the assumption it relaxes is what makes the family of planning formalisms navigable rather than a list of unrelated techniques.

Answer: A

Conformant planning searches over sets of possible states and seeks a sequence succeeding from every one of them. Contingent planning is the version with sensing available, and the other two relax different assumptions altogether. Distinguishing the case where the agent cannot observe from the case where it can, and knowing that the first admits a fixed sequence while the second requires a tree, is the essential difference between them. Naming the cost of a choice alongside its benefit is what turns a fact into a design decision.

Answer: B

Since the agent cannot tell which state it occupies, it reasons about the whole set and an action maps one set to another. The goal is reached when every state in the belief satisfies it. Confidence, most likely states and observation histories are different notions. Lifting a problem from states to sets of states is the standard treatment of partial observability and it costs an exponential in the size of the space.

Answer: C

A domain with n states has two to the n subsets, so the search space is exponentially larger even before any actions are considered. Compact representations of belief states and heuristics computed over them are what make it tractable in practice. Ordering, goal testing and plan length are secondary. An exponential increase in the size of the space, arising purely from removing an assumption, is the price of every step towards realism in this family.

Answer: D

A sensing action does not change the world but partitions the belief state according to what is observed, which is what allows a contingent plan to branch. Ordinary actions that happen to be observable are different, and the other options describe conditions rather than definitions. An action whose effect is epistemic rather than physical is a genuinely different kind of thing and requires its own treatment in the formalism.

Answer: A

Observing a fluent divides the belief into the states where it holds and those where it does not, and the plan branches on which is actually seen. Complete certainty is achieved only if the observation distinguishes every possibility. Enlargement and no effect are both wrong. That an action which changes nothing physically nonetheless changes what the agent may do next is the essential feature of information gathering.

Answer: B

Sensing is worth performing only if what is learned would change what the agent does, and the value is the resulting improvement in expected outcome. An observation that cannot change the decision is worthless however informative it seems. Cost, probability and state counts are inputs to the calculation rather than the value. Asking whether an answer would change the decision, before paying to obtain it, is a principle that applies well beyond planning.

Answer: C

Given a deadline that may not be known, a planner that has a valid plan available throughout and improves it with further computation is far more useful than one that produces nothing until it finishes. Weighted heuristic search provides the usual mechanism. Invocation timing, fixed running times and changing goals are different notions. Making plan quality a function of the time available, rather than requiring completion, is what a real time agent needs.

Answer: D

In most applications a plan five per cent longer, available in a second rather than an hour, is plainly the better outcome, and weighted search provides a bound on the loss. Optimal plans are computable for small problems, quality is measurable by plan cost, and execution cost varies. Choosing the quality actually required, rather than the best obtainable, is a decision that should be made deliberately rather than by default.