Next: SINGLE-MATERIAL WORLDS WITH SINGLE-STATE Up: SINGLE-MATERIAL WORLDS Previous: SINGLE-MATERIAL WORLDS

### SINGLE-MATERIAL WORLDS WITH NO TOOLS

Since materials have linear chains as their state spaces, action in them is restricted, to say the least. In the case of an egg, we might have the chain:

(We will assume that the identity, or ``nop,'' action is always available in every state. This is not a trivial assumption.) In any given state, only one non-trivial action can be executed, so action selection for an agent is trivial. When solving a DCP involving a single-material world one of the following must always hold:

• The current state is a goal state, so we need only execute the identity action.
• The current state is a pregoal state: some goal state is later in the chain than the current state, so we can reach it by executing the unique action that brings us to the next state in the chain.
• The current state is a postgoal state: all goal states are earlier in the chain, so the problem is unsolvable.

All that really matters in single-material worlds, therefore, is how many states there are and in which direction the goal lies relative to the current state. In a sense, there is only really one single-material world, or rather one class of them, namely the chains of given length:

(Note this is just the same as the environment , but without the actions that move backward along the chain.)

Proof: Let E=(S,A) be the single-material environment. Define by letting be s's position in E's state chain, i.e. the first state maps to 1, the second to 2, etc. Let action(s) denote the unique action that can be performed in state s. Then

is a -implementation of and so E is reduced.

Just as there is only one real class of single-material worlds, there is only one real class of policies for single-material DCPs:

which clearly solves the DCP for any n and valid G.

Next: SINGLE-MATERIAL WORLDS WITH SINGLE-STATE Up: SINGLE-MATERIAL WORLDS Previous: SINGLE-MATERIAL WORLDS

Ian Horswill
Wed Apr 2 15:17:20 CST 1997