Past exam of the computer science course of the University of Oxford / 2022 / Artificial intelligence / 1

Use $a,w,g,r$ for the agent, monster, gold and arrow, and abbreviate $s{q}_{ij}$ to $s_{ij}$. A physically safe STRIPS plan isEvery movement follows a listed adjacency predicate. The shot is taken from $s_{22}$ while the arrow is held, and kills the monster before entry into $s_{23}$. The pit at $s_{12}$ is never entered. The pickup establishes possession of the gold, and the last four movements restore the exit location while preserving that possession. Thus ten actions achieve the formal goal and the intended safe return; arriving at the exit is the source model’s representation of leaving.

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.

A corrected STRIPS model can fix object roles in the action names, leaving only room parameters to instantiate. Use the same $a,w,g,r$ and introduce static $\mathrm{pitfree}(z)$ and $\mathrm{exit}(z)$ facts, plus a planning fluent $\mathrm{clear}(z)$ meaning “no live monster occupies $z$”. Unlike the supplied adjacency relation, let $\mathrm{adj}$ describe all geometrically adjacent rooms; safety is then explicit rather than hidden by missing edges.

Initially the agent, monster and gold have their specified locations, $\mathrm{have}(a,r)$, $\mathrm{alive}(w)$ and $\mathrm{active}$ hold, $\mathrm{exit}(s_{11})$ holds, $\mathrm{pitfree}$ holds at every room except $s_{12}$, and $\mathrm{clear}$ holds at every room except $s_{23}$. All unlisted facts are false by the closed-world assumption. The following positive preconditions, add lists and delete lists are a complete action specification:Require $\mathrm{exited}$ as the goal. If reaching the exit suffices, omit $\mathrm{Leave}$ and use the original two goal facts. Instantiating these schemata over the finite room set gives ordinary ground STRIPS actions.

Only $a$ moves, only $g$ is collectible and only $r$ can be fired at $w$. No action changes the monster’s location; its corpse can stay there, while $\mathrm{clear}$ records that it is harmless. The gold stays at its original room until collection. The arrow is consumed by its only use. By mathematical induction on plan length, every applicable action preserves the planning state invariant that the active agent occupies one pit-free room without a live monster. Consequently every solution is a safe execution. The plan in part a, followed by $\mathrm{Leave}(s_{11})$, is one such execution.

Ordinary classical planning with STRIPS starts from one completely specified state. Here the missing locations express ignorance: not listing a pit or a monster at a room does not establish its absence. Applying the closed-world assumption to those omissions would manufacture knowledge of safety. Moreover, future sensor readings can determine which action is appropriate, so a fixed action sequence need not suffice.

The suitable object is a belief state and a contingent plan that branches on observations. A finite belief state model could in principle be compiled into a larger classical planning instance, but the ordinary physical-state STRIPS representation does not directly represent the required uncertainty and sensing.

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.