State Space Search I
- Define a state space. (0.125%)
- What two types of information are held a state? (0.125%)
- What are the three types of information that can be used to guide the
search for a solution in a state space? (0.125%)
- In what two ways may one problem solution be considered better than
another? (0.125%)
- What does the control strategy do in state space search? (0.125%)
- What are the three requirements for a control strategy to succeed? (0.125%)
- Describe the criteria that determine the best direction for search in
a problem space. (0.125%)
- Describe three principles for avoiding loops in state space search.
Mention their relative costs. (0.125%)
- 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.
(1%)