-
Notifications
You must be signed in to change notification settings - Fork 577
/
Copy pathagents-exercises.tex
238 lines (192 loc) · 9.09 KB
/
agents-exercises.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
%%%% 2.2: Good Behavior: The Concept of Rationality (4 exercises, 2 labelled)
%%%% ========================================================================
\begin{uexercise}
Suppose that the performance measure is concerned with just the first \(T\) time steps of the environment and ignores everything thereafter.
Show that a rational agent's action may depend not just on the state of the environment but also on the time step it has reached.
\end{uexercise}
% id=2.1 section=2.2
\begin{exercise}[vacuum-rationality-exercise]%
Let us examine the rationality of various vacuum-cleaner agent functions.
\begin{enumerate}
\item Show that the simple vacuum-cleaner agent function described in
\tabref{vacuum-agent-function-table} is indeed rational
under the assumptions listed on \pgref{vacuum-rationality-page}.
\item Describe a rational agent function for the case in which
each movement costs one point. Does the corresponding agent program require internal state?
\item Discuss possible agent designs for
the cases in which clean squares can become dirty and the geography
of the environment is unknown. Does it make sense for the agent to
learn from its experience in these cases? If so, what should it learn?
If not, why not?
\end{enumerate}
\end{exercise}
% id=2.5 section=2.2
\begin{iexercise}\libex
Write an essay on the relationship between evolution and one or more of autonomy, intelligence, and learning.
\end{iexercise}
% id=2.8 section=2.2
%%%% 2.3: The Nature of Environments (2 exercises, 1 labelled)
%%%% =========================================================
\begin{exercise}
For each of the following assertions, say whether it is true or false and support your answer with examples or counterexamples where appropriate.
\begin{enumerate}
\item An agent that senses only partial information about the state cannot be perfectly rational.
\item There exist task environments in which no pure reflex agent can behave rationally.
\item There exists a task environment in which every agent is rational.
\item The input to an agent program is the same as the input to the agent function.
\item Every agent function is implementable by some program/machine combination.
\item Suppose an agent selects its action uniformly at random from the set of possible actions. There exists a deterministic task environment in which this agent is rational.
\item It is possible for a given agent to be perfectly rational in two distinct task environments.
\item Every agent is rational in an unobservable environment.
\item A perfectly rational poker-playing agent never loses.
\end{enumerate}
\end{exercise}
% id=2.2 section=2.3
\begin{uexercise}[PEAS-exercise]
For each of the following activities, give a PEAS description of the task environment and characterize it in terms of the properties
listed in \secref{env-properties-subsection}.
\begin{itemize}
\item Playing soccer.
\item Exploring the subsurface oceans of Titan.
\item Shopping for used AI books on the Internet.
\item Playing a tennis match.
\item Practicing tennis against a wall.
\item Performing a high jump.
\item Knitting a sweater.
\item Bidding on an item at an auction.
\end{itemize}
\end{uexercise}
% id=2.6 section=2.3
\begin{iexercise}[PEAS-exercise]
For each of the following activities, give a PEAS description of the task environment and characterize it in terms of the properties
listed in \secref{env-properties-subsection}.
\begin{itemize}
\item Performing a gymnastics floor routine.
\item Exploring the subsurface oceans of Titan.
\item Playing soccer.
\item Shopping for used AI books on the Internet.
\item Practicing tennis against a wall.
\item Performing a high jump.
\item Bidding on an item at an auction.
\end{itemize}
\end{iexercise}
% id=2.6 section=2.3
%%%% 2.4: The Structure of Agents (9 exercises, 5 labelled)
%%%% ======================================================
\begin{exercise}
Define in your own words the following terms: agent, agent function,
agent program, rationality, autonomy, reflex agent, model-based agent,
goal-based agent, utility-based agent, learning agent.
\end{exercise}
% id=2.0 section=2.4
\begin{exercise}[agent-fn-prog-exercise]%
This exercise explores the differences between agent functions
and agent programs.
\begin{enumerate}
\item Can there be more than one
agent program that implements a given agent function?
Give an example, or show why one is not possible.
\item Are there agent functions that cannot be implemented by any agent
program?
\item Given a fixed machine architecture, does each agent program
implement exactly one agent function?
\item Given an architecture with \(n\) bits of storage, how many
different possible agent programs are there?
\item Suppose we keep the agent program fixed but speed up the machine by a factor of two. Does that change the agent function?
\end{enumerate}
\end{exercise}
% id=2.3 section=2.4
\begin{exercise}
Write pseudocode agent programs for the goal-based and utility-based agents.
\end{exercise}
% id=2.4 section=2.4
\begin{iexercise}
Consider a simple thermostat that turns on a furnace when the temperature
is at least 3 degrees below the setting, and turns off a furnace when
the temperature is at least 3 degrees above the setting.
Is a thermostat an instance of a simple reflex agent, a model-based reflex
agent, or a goal-based agent?
\end{iexercise}
% id=2.7 section=2.4
\medskip
\noindent
\prgex The following exercises all concern the implementation of environments and agents for the vacuum\index{agent!vacuum|(}\index{vacuum world}-cleaner world.
\begin{exercise}[vacuum-start-exercise]%%
Implement a performance-measuring environment simulator for the
vacuum-cleaner world depicted in \figref{vacuum-world-figure} and
specified on \pgref{vacuum-rationality-page}. Your implementation
should be modular so that the sensors, actuators, and environment
characteristics (size, shape, dirt placement, etc.) can be changed
easily. ({\em Note:} for some choices of programming language and operating
system there are already implementations in the online code
repository.)
\end{exercise}
% id=2.9 section=2.4
\begin{uexercise}
Implement a simple reflex agent for the vacuum environment in
\exref{vacuum-start-exercise}. Run the environment with this
agent for all possible initial dirt configurations and agent locations.
Record the performance score for each configuration and the overall average
score.
\end{uexercise}
% id=2.10 section=2.4
\begin{exercise}[vacuum-motion-penalty-exercise]%
Consider a modified version of the vacuum environment in
\exref{vacuum-start-exercise}, in which the agent is penalized
one point for each movement.
\begin{enumerate}
\item Can a simple reflex agent be perfectly rational
for this environment? Explain.
\item What about a reflex agent with state? Design such an agent.
\item How do your answers to {\bf a} and {\bf b} change if the agent's
percepts give it the clean/dirty status of every square in the environment?
\end{enumerate}
\end{exercise}
% id=2.11 section=2.4
\begin{exercise}[vacuum-unknown-geog-exercise]%
Consider a modified version of the vacuum environment in
\exref{vacuum-start-exercise}, in which the geography of the
environment---its extent, boundaries, and obstacles---is unknown, as
is the initial dirt configuration. (The agent can go \(\J{Up}\) and
\(\J{Down}\) as well as \(\J{Left}\) and \(\J{Right}\).)
\begin{enumerate}
\item Can a simple reflex agent be perfectly rational
for this environment? Explain.
\item Can a simple reflex agent with a {\em randomized} agent function
outperform a simple reflex agent? Design such an agent
and measure its performance on several environments.
\item Can you design an environment in which your randomized agent will perform
poorly? Show your results.
\item Can a reflex agent with state outperform a simple
reflex agent? Design such an agent
and measure its performance on several environments.
Can you design a rational agent of this type?
\end{enumerate}
\end{exercise}
% id=2.12 section=2.4
\begin{exercise}[vacuum-bump-exercise]
Repeat \exref{vacuum-unknown-geog-exercise} for the case
in which the location sensor is replaced with a ``bump'' sensor
that detects the agent's attempts to move into an obstacle or to cross
the boundaries of the environment. Suppose the bump sensor stops
working; how should the agent behave?
\end{exercise}
% id=2.13 section=2.4
\begin{exercise}[vacuum-finish-exercise]%
The vacuum environments in the preceding exercises have all been
deterministic. Discuss possible agent programs for each of the
following stochastic versions:
\begin{enumerate}
\item Murphy's law: twenty-five percent of the time, the \(\J{Suck}\) action
fails to clean the floor if it is dirty and deposits
dirt onto the floor if the floor is clean. How is your agent program
affected if the dirt sensor gives the wrong answer 10\% of the time?
\item Small children: At each time step,
each clean square has a 10\% chance of becoming dirty.
Can you come up with a rational agent design for this case?
\end{enumerate}
\end{exercise}
% id=2.14 section=2.4
\index{agent!vacuum|)}
%%\setlength{\medskipamount}{1.5\medskipamount}%%%%% Mona's suggestion
%%\setlength{\medskipamount}{0.666667\medskipamount}%%%%% Mona's suggestion