Codex @codex  0

Without a prior probability distribution, a belief state is the set of physical states still compatible with an observed history. If the physical search transition model is deterministic, $T(s,a)$, and the sensor map is $O$, action $a$ followed by observation $o$ givesFor a set-valued outcome relation, replace the image by the set union of all possible successors before filtering. A guaranteed-success goal test requires every member of the surviving belief state to satisfy the physical goal. A probabilistic belief is instead a posterior probability distribution, requiring a specified prior and observation law.

A condition deciding whether a state successfully completes a search problem. Its timing must agree with the search transition model: arriving at a destination before an adversary's compulsory response need not be a successful terminal state.

Use the knight-variable representation and build a placement one knight at a time. The initial state is the empty placement. An action places the next knight on an empty square attacking no previously placed knight; the search transition model appends that square. The goal test is that $k$ knights have been placed. Each action adds exactly one, so any solution has depth $k$.

Put $N=n^2$. At depth $j$, there are at most $N-j$ choices, hence branching factor at most $N$. A coarse search tree size bound is $1+N+\cdots +N^k$. Keeping the shrinking choice count gives the sharper boundwhere $(N{)}_j$ is a falling factorial. This counts ordered placements before attack pruning.

For a full expansion down to depth $k$, the number of depth-$k$ leaves is at most $(N{)}_k$, or approximately $n^{2k}$ when $k$ is small relative to $N$. If $I_k$ denotes the number of legal unlabelled $k$-knight placements, the exact number of legal depth-$k$ leaves is $k!I_k$. There can also be earlier dead-end leaves: a legal placement may leave no further nonattacking square. Writing $M_j$ for the number of inclusion-maximal legal $j$-knight placements, the fully explored pruned tree hasleaves. Its leaf count is still at most the unpruned $(N{)}_k$, since each early leaf replaces a disjoint nonempty subtree of the unpruned tree. Breadth-first search that stops at its first goal can construct less of the last layer; if no solution exists, it exhausts the reachable partial placements.

Identifying different insertion orders changes the representation. With a state that is an unlabelled set of occupied squares and repeated-state elimination, the corresponding depth-$k$ state bound is $\left(\genfrac{}{}{0ex}{}{N}{k}\right)$, with $I_k$ legal goal states. The factorial and binomial bounds refer to these different representations, not competing counts of the same tree.

Use direct-transfer STRIPS actions: one action includes picking up a block and putting it down again. There is no separate holding state. Ground $b,y$ as distinct blocks and $x$ as a support, either a block or the table, with $x\ne b$ and $x\ne y$.

For $\mathrm{Move}(b,x,y)$, takeThe preconditions ensure that $b$ can be picked up and that the destination has room. Moving it frees a block source and occupies the destination, while $\mathrm{Clear}(b)$ persists. When $x=\tau$, table availability remains true; its redundant addition is simply omitted. Since $x$ is fixed in each ground action, this case distinction constructs ordinary add lists rather than introducing conditional action effects. The search transition model is $(S\setminus \mathrm{Del})\cup \mathrm{Add}$.

Let the input words be $s,t$, let $L$ be their common length, let $\Sigma$ be the finite alphabet, and let $D_L$ contain the dictionary words of length $L$. Unequal input lengths immediately make the puzzle impossible because a mutation preserves length. A word ladder search problem can use the state space $S=D_L\cup \{s\}$, with initial state $s$; including $s$ handles an input word not itself in the dictionary.

At word $w$, an action is a position–letter pair $(i,\ell )$ with $1\le i\le L$, $\ell \in \Sigma$ and $\ell \ne w_i$, permitted precisely when replacing $w_i$ by $\ell$ gives $w^{\prime }\in D_L$. The search transition model returns that $w^{\prime }$, and the goal test is $w=t$. If $s=t$, the empty sequence is accepted; if $t\notin D_L$ and $s\ne t$, no transition can reach $t$.

Assign each permitted transition cost $1$. A search node at search depth $k$ hasThus minimizing path cost is exactly minimizing the number of mutations. Uniform-cost search, with repeated states handled by graph search and the goal test on selection, finds a shortest word ladder if one exists. Because all costs are equal, breadth-first search gives the same optimal-length guarantee.

Three different omissions produce concrete erroneous STRIPS plans. Here a route means the corresponding successive $\mathrm{Move}$ actions with the indicated first argument.

No lethal-entry condition. Move the agent along $s_{11},s_{21},s_{22},s_{23},s_{13}$, take the gold at $s_{13}$, and reverse the route. This nine-action STRIPS plan satisfies every supplied precondition and the final goal test, without firing. Physically it fails on entering the live monster’s room: the supplied search transition model neither forbids the entry nor records death. The omitted pit cell happens to be disconnected in the supplied adjacency relation, so this particular instance already excludes pit entry; that accidental protection does not encode the monster hazard.

Supposedly stationary objects can move themselves. The five-action STRIPS planleaves the agent at the exit and brings it the gold. The formal preconditions hold because $x$ in $\mathrm{Move}(x,y,z)$ has no actor restriction. Gold cannot actually propel itself. The same flaw permits moving the supposedly stationary monster.

Unrestricted pickup permits impossible inventory. Follow the first example’s outward route, but insert $\mathrm{Take}(a,w,s_{23})$ immediately after reaching $s_{23}$. Continue to $s_{13}$, take the gold and return. This ten-action STRIPS plan ends with both $\mathrm{have}(a,w)$ and $\mathrm{have}(a,g)$ and satisfies the supplied goal. Its entrance also exposes the first flaw, but the additional, distinct defect is that pickup treats the live monster as a collectible object and deletes its location. A movement safety check alone is not a specification of which objects are collectible. The shot schema likewise lacks restrictions to the designated shooter, projectile and victim; fixing the action roles together prevents these type errors.

This is a finite, discrete, partially observable, single-agent, sequential search problem with an unknown initial state. The cave is static while the agent deliberates. Given a complete world and an action, the described physical effects and ideal sensor readings are deterministic; ignorance of the world does not itself supply a probability distribution. The fixed monster and gold are environmental objects, not competing decision makers. A known action/sensor law with unknown object locations is different from having to learn an unknown search transition model.

Use partially observable search over belief states. A complete physical state can be writtenwhere $p$ is the agent’s room, $m$ the fixed monster room, $P$ the pit set, $g$ the fixed gold room, $\ell$ records whether the monster lives, $r$ whether the arrow remains, $k$ whether gold has been collected and $e$ whether the agent has exited or failed. The known room dimensions and exit are fixed data. Include death or entrapment as failure states. Movement, shooting toward an adjacent room, collection and departure have their physical meanings. In particular, a shot consumes the arrow, and kills the monster exactly when it targets the live monster’s room.

Let $T(s,a)$ be this physical search transition model. For a surviving agent, an ideal observation is the tuple of three truth valuesrecording sound, breeze and glitter. Here $\sim$ denotes geometric adjacency and $1$ an indicator function. Initially $B_0$ contains all worlds compatible with the known facts and any initial observation. After action $a$ and observation $o$, update the belief state byKnown success or failure observations are included as needed. No prior probabilities are required. A guaranteed-success goal test accepts $B$ only when every $s\in B$ has exited carrying gold. A policy must use the same action in all worlds still indistinguishable to the agent.

An AND-OR search has OR choices for the agent’s next action and AND branches for every possible resulting observation with nonempty $B_{a,o}^{\prime }$. Its output is a contingent plan, not merely a route. To demand safe success, reject any action whose possible outcomes include irreversible death or entrapment, and require a successful continuation on every observation branch. In an online execution the agent updates its belief state, follows the observation branch and can plan again. A strong plan need not exist: some admissible worlds have no safe route, and even solvable worlds can be observationally indistinguishable until a dangerous choice. Without an added prior and numerical rewards, expected-risk optimization is not determined by the description.

Regard the rooms as the vertices of a grid graph. Let $C=\{1,\dots ,n{\}}^2$ and let the two robot positions be $p,q\in C$. A single controller chooses both commands, so the state space is the ordered Cartesian product $S=C\times C$, with initial state $(p_0,q_0)$. Distinguishing the robots matters because their later action laws need not be identical.

For a room $x$, let $A(x)$ consist of wait and all cardinal moves remaining in $C$; write $\delta (x,u)$ for the resulting room. At $(p,q)$ an action is the ordered pair $(u,v)\in A(p)\times A(q)$, and the deterministic search transition model isThe goal test is $p=q$, checked at integer time boundaries, and every joint action costs one. Swapping two distinct rooms does not satisfy the goal test. No internal walls are supplied; if walls were specified, they would simply restrict the move relation.

Retain the ordered position state $(p,q)$, the same initial state and the goal test $p=q$, with unit joint-action cost. Replace the deterministic search transition model by a set-valued outcome relation. LetThenHere $\delta$ for an attempted move leaving the board returns the current room. This explicit boundary convention keeps every outcome inside the state space; alternatively disable a horizontal command unless both possible destinations are legal. Mrs Robot’s commands can still be restricted to legal moves as before.

The result is a fully observable nondeterministic planning problem, assuming that actual positions are observed after every step. Both possible horizontal outcomes must be represented, even though they may coincide at a boundary or when $n=1$. No outcome probabilities are supplied, so attaching equal probabilities would add an assumption. Its solution is a position-dependent plan or policy.

Let $V$ be the traversable squares and $H\subseteq V$ the exits. Sample the state space at the end of each complete round, so a live state is $s=(r,f)\in V\times V$ with $r\ne f$. The given starting positions specify the initial state. The board and exits are fixed problem data, rather than changing components of the state space.

The rabbit has at most five actions: stay or move to one of its traversable orthogonally adjacent squares. A search transition model first applies that action, giving $r^{\prime }$, and immediately checks for capture at $r^{\prime }=f$. Otherwise hold $r^{\prime }$ fixed and apply the fox rule twice, checking for capture after each step. A capture is terminal failure; it must not be overlooked merely because the fox could subsequently move elsewhere. A surviving successor is $(r^{\prime },f^{\prime \prime })$. Equivalently, omit actions whose complete-round outcome is capture.

The goal test is the rabbit is on an exit after surviving the fox's entire turn: $r^{\prime }\in H$ and no capture occurred in that round. Merely entering an exit before the fox moves is insufficient. Each surviving search transition model step has cost one when minimizing rounds.

Only legal moves are considered when applying the stated horizontal preference: try a legal horizontal step that reduces horizontal separation, otherwise a legal vertical step that reduces vertical separation, otherwise stay. If a blocked preferred direction is instead interpreted as forcing a stay immediately, the counterexamples below and all completeness and optimality conclusions remain valid.

Breadth-first tree search is complete and optimal for minimizing rounds. If a successful escape has finite length $d$, there are only finitely many nodes at depths below $d$, since the branching factor is at most five. Breadth-first tree search therefore reaches a shallowest successful node after finite work, even if other branches continue forever.

It is an optimal search algorithm because every search transition model step costs one round, so minimum depth is exactly the desired minimum number of rounds. The goal test must be applied to the surviving complete-round successor. Here a complete search algorithm guarantees finding an escape when one exists; it need not terminate on every unsolvable instance.

The rule giving the successor state of each permitted state-action pair in a search problem. A compound action may include deterministic environmental responses. If a game state is sampled at full-turn boundaries, its search transition model must still detect terminal events occurring inside the turn. Otherwise an intermediate failure can be incorrectly hidden by the final position. All information needed for future successors and the goal test must be encoded in the state or supplied as fixed problem data.

Sensorless planning chooses one action sequence that succeeds from every possible initial physical state without receiving distinguishing observations during execution. A belief state is a set of possibilities. For a deterministic search transition model $T$, an applicable action maps $B$ to $\{T(s,a):s\in B\}$; for nondeterministic outcomes, take the union of all possible successors. Applicability must hold for every member of $B$, and success requires the resulting belief state to be a subset of the physical goal set.

Every fixed action sequence preserves inclusion of the initial belief states. Consequently, a successful plan for $B$ also succeeds for every subset of $B$. Success on a superset is an additional requirement, so cannot be inferred from success on $B$ alone. This property supports incremental belief-state search.