Exercise 3.24 [vacuum-search-exercise]
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$?