= Solution
This is a \b[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 written
$$
s=(p,m,P,g,\ell,r,k,e),
$$
where $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 values>
$$
O(s)=\bigl(\mathbf1_{\{\ell\ \text{and}\ m\sim p\}},\ \mathbf1_{\{\exists q\in P:q\sim p\}},\ \mathbf1_{\{p=g\ \text{and}\ k=0\}}\bigr),
$$
recording sound, breeze and glitter. Here $\sim$ denotes geometric adjacency and $\mathbf1$ 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> by
$$
\boxed{B'_{a,o}=\{T(s,a):s\in B,\ O(T(s,a))=o\}.}
$$
Known 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}$. 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.
Back to article page
