State Space Search I

Define a state space.
A state space is the set of all configurations that a given problem and its environment could achieve.
What two types of information are held a state?
Static information and Dynamic information.
What are the three types of information that can be used to guide the search for a solution in a state space?
The static information. The dynamic information in achieved states, statically state per state. The structure of the space of achieved states.
In what two ways may one problem solution be considered better than another?
Best may be measured by cost of transformation, and quality of the goal state found.
What does the control strategy do in state space search?
A control strategy will decide which (finite number of) transformations should be made at any point in time, from which achieved state.
What are the three requirements for a control strategy to succeed?
The goal states are not randomly distributed. The pattern of distribution is detectable. The problem solver be able to react so as to search to according to the detected pattern.
Describe the criteria that determine the best direction for search in a problem space.
Working in the direction of a lower branching factor is superior, as the search tree is smaller. If the branching factor is the same both ways it is better to start from a few states and work towards many states.
Describe three principles for avoiding loops in state space search. Mention their relative costs.
Do not return to where you just came from. Do not create cycles. Do not create duplicate states.
An agent is at state I, and is considerng two non-deterministic transformations T1 and T2. The quality of the states is uncertain due to an inaccessible environment.
- The possible states that T1 will lead to are S1 (probability 0.5), S2 (probability 0.3), and S3 (probability 0.2). The possible qualities of S1 are 10 (probability 0.5), and 20 (probability 0.5). The possible qualities of S2 are 18 (probability 0.5), 12 (probability 0.3), and 6 (probability 0.2). The possible qualities of S3 are 20 (probability 0.8), and 0 (probability 0.2).
- The possible states that T2 will lead to are S4 (probability 0.8), and S5 (probability 0.2). The possible qualities of S4 are 12 (probability 0.6), and 18 (probability 0.4). The possible qualities of S5 are 10 (probability 0.7), 20 (probability 0.2), and 0 (probability 0.1).
Use utility to decide which transformation is preferred.
Answer
```
Q(S1) = 0.5 * 10 + 0.5 * 20 = 15
Q(S2) = 0.5 * 18 + 0.3 * 12 + 0.2 * 6 = 13.8
Q(S3) = 0.8 * 20 + 0.2 *  0 = 16
Utility(T1) = 0.5 * 15 + 0.3 * 13.8 + 0.2 * 16 = 14.84

Q(S4) = 0.6 * 12 + 0.4 * 18 = 14.4
Q(S5) = 0.7 * 10 + 0.2 * 20 + 0.1 *  0 = 11.0
Utility(T2) = 0.8 * 14.4 + 0.2 * 11.0 = 13.72

Prefer T1
```
(1%)