Consider the vacuum-world problem defined in .
-
Which of the algorithms defined in this chapter would be appropriate for this problem? Should the algorithm use tree search or graph search?
-
Apply your chosen algorithm to compute an optimal sequence of actions for a
$3\times 3$ world whose initial state has dirt in the three top squares and the agent in the center. -
Construct a search agent for the vacuum world, and evaluate its performance in a set of
$3\times 3$ worlds with probability 0.2 of dirt in each square. Include the search cost as well as path cost in the performance measure, using a reasonable exchange rate. -
Compare your best search agent with a simple randomized reflex agent that sucks if there is dirt and otherwise moves randomly.
-
Consider what would happen if the world were enlarged to
$n \times n$ . How does the performance of the search agent and of the reflex agent vary with$n$ ?