-
Notifications
You must be signed in to change notification settings - Fork 225
Expand file tree
/
Copy pathindex.html
More file actions
339 lines (304 loc) · 15.6 KB
/
index.html
File metadata and controls
339 lines (304 loc) · 15.6 KB
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
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
<!DOCTYPE html>
<html lang="en">
<head>
<title>4 Beyond Classical Search</title>
<link rel="stylesheet" href="../styles.css">
<link rel="stylesheet" href="main.css" charset="utf-8">
<script src="http://code.jquery.com/jquery-1.12.4.js"></script>
<script type="text/javascript" src="../main.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/two.js/0.6.0/two.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/4.9.1/d3.min.js"></script>
<script type="text/javascript" src="./geneticAlgorithm.js"></script>
<script type="text/javascript" src="./simulatedAnnealing.js"></script>
<script type="text/javascript" src="./hillClimbing.js"></script>
<script type="text/javascript" src="./andOrGraphSearch.js"></script>
<script type="text/javascript" src="./lrtaAgent.js"></script>
<script type="text/javascript" src="./onlineDfsAgent.js"></script>
<script type="text/javascript" src="./erraticVacuum.js"></script>
<script type="text/javascript" src="./localization.js"></script>
<script type="text/javascript" src="./c_geneticAlgorithm.js"></script>
<script type="text/javascript" src="./c_simulatedAnnealing.js"></script>
<script type="text/javascript" src="./c_hillClimbing.js"></script>
<script type="text/javascript" src="./c_andOrGraphSearch.js"></script>
<script type="text/javascript" src="./c_lrtaAgent.js"></script>
<script type="text/javascript" src="./c_onlineDfsAgent.js"></script>
<script type="text/javascript" src="./c_erraticVacuum.js"></script>
<script type="text/javascript" src="./c_noObservation.js"></script>
<script type="text/javascript" src="./c_localization.js"></script>
</head>
<body>
<div class="row">
<div class="col-sm-6 col-md-10 col-md-offset-1" id="content">
<h1>Beyond classical search</h1>
<h3>Table of contents</h3>
<ul class="content-table">
<li><a href="#optimization-problem">Optimization Problem</a></li>
<li><a href="#hill-climbing">Hill Climbing Search</a></li>
<li><a href="#simulated-annealing">Simulated Annealing</a></li>
<li><a href="#genetic-algorith">Genetic Algorithm</a></li>
<li><a href="#searching-with-non-deterministic-actions">Searching with non-deterministic actions</a></li>
<li><a href="#erratic-vacuum-world">The erratic vacuum world</a></li>
<li><a href="#searching-with-partial-observations">Searching with Partial Observations</a></li>
<li><a href="#vacuum-world-with-no-observation">Vacuum World with no observation</a></li>
<li><a href="#and-or-graph-search">And-Or-Graph-Search</a></li>
<li><a href="#online-dfs-agent">Online DFS Agent</a></li>
<li><a href="#lrta-agent">LRTA*-Agent</a></li>
</ul>
<h2 id="optimization-problem">Optimization Problem</h2>
<p>In many optimization problems, the path to the solution is irrelevant. In pure optimization problems, the best state is defined by the objective function. To represent such problems, a <b>state-space</b> landscape is used. It has a location (state)
represented by x-axis and elevation(objective function value) represented by y-axis. The best state is hence the state with the highest objective value</p>
<p>The given diagram is a state-space representation of an objective function. You can click anywhere inside the box to reveal the elevation there. You are allowed <i>25 moves</i> to <b>find the highest peak</b> before the hill is revealed.</p>
<p><span class='inline-legend maxima'></span> represents found global maximas and <span class='inline-legend unvisitedmaxima'></span> represents unfound global maximas</p>
<p>Try to come up with a strategy that can be used for all kinds of hills.</p>
<div class='row'>
<div class="col-md-2">
<div class='btn btn-primary restart-button' id='hillClimbRestart'>Restart</div>
</div>
<div class="col-md-4">
<h2 id='hillMoves'></h2>
</div>
</div>
<div id="hillCanvas">
</div>
<h2 id="hill-climbing">Hill Climbing Search</h2>
<p>In hill climbing search, the current node is replaced by the best neighbor. In this case, the objective function is represented by elevation, neighbors of a state are the states to the left and right of it and the best neigbor is the neigbor state
with the highest elevation.</p>
<p>The <span class='inline-legend maxima'></span> represents global maximas and <span class='inline-legend gmra'></span> represents the states from where the hill climbing search can reach a global maxima.</p>
<p>Click on different states to start Hill Climbing Search from there and see which direction it prefers and when does it stop.</p>
<p>Use the restart button to try it on different kinds of hills.</p>
<div class='row'>
<div class="col-md-2">
<div class='btn btn-primary restart-button' id='hillSearchRestart'>Restart</div>
</div>
</div>
<div id="hillSearchCanvas">
</div>
<h2 id="simulated-annealing">Simulated Annealing</h2>
<p>Simulated Annealing is a combination of Hill Climbing and Random Walk to gain more efficiency and completeness. In this procedure, instead of always moving to the best neighbor, a random neighbor is chosen. If the new state has better objective
value than the current state, it is always chosen. If not, the algorithm accept the new state with a probability less than one. The probability of choosing a <b>bad state</b> depends on :
<ol>
<li>The difference in objective value of the new state and the current state</li>
<li>The temperature</li>
</ol>
The temperature T denotes how likely it is for a bad state to be accepted. The procedure starts with a high temperature and decreases it with time. The probability of accepting a bad move decreases exponentially with temperature.</p>
<p>The <span class='inline-legend maxima'></span> represents global maximas and <span class='inline-legend anneal-region'></span> represents current state.</p>
<p>Notice how the algorithm shakes violently between states when the temperature is high and then stabilizes to higher states as the temperature decreases.</p>
<p>Try to set the temperature from the slider to different values and notice how the algorithm behaves.</p>
<div class='row'>
<div class="col-md-2">
<div class='btn btn-primary restart-button' id='annealingRestart'>Restart</div>
</div>
<div class="col-md-8">
<b>Temperature</b>
<input style="margin-top:1.5%" type="range" id="tempSelector" name="tempInput" step="0.1" min="0" max="100" value="100">
</div>
</div>
<div id="annealingCanvas"></div>
<h2 id="genetic-algorith">Genetic Algorithm</h2>
<p>Little critters change the color of their fur to match the background to camouflage themselves from predators.</p>
<p>Click on the canvas to generate next generation. Keep clicking to generate another progeny.</p>
<p>Note: Single point crossover might not be suitable for all applications</p>
<div class="canvas" id="geneticCanvas" height="300px" style="background: #87BC5E">
</div>
<h1 id="searching-with-non-deterministic-actions">Searching with non-deterministic actions</h1>
<p>In a world with non-deterministic actions, the result of an action is not known with complete certainty. </p>
<h2 id="erratic-vacuum-world">The erratic vacuum world</h2>
<p>The erratic vacuum world is an extension of vacuum world from Chapter 2. In this world, the behavior of the cleaner is non-deterministic.</p>
<p>To define this behavior more formally, in this world, the <b>Suck</b> action works as follows</p>
<ul>
<li>If the tile is dirty, the suck action cleans up the tile and sometimes also clean up dirt in adjacent tiles </li>
<li>If the tile is clean, the suck action sometimes deposits dirt on the carpet.</li>
</ul>
<p>Given below is a 5 tile erratic vacuum world. You can record a sequence of actions which you believe will clean up all the dirt. Use the play the button to execute that sequence. Play the sequence multiple times to see how they can result in different
end state sometimes. Use restart button to generate a new initial state. Use clear button to clear the recorded sequence and record a new one.</p>
<div class='row' id='erraticVacuum'>
<div class="col-md-8">
<div class="row">
<div class="col-md-4">
<div class='btn btn-primary restart-button'>Restart</div>
</div>
<div class="col-md-6">
<div class="row">
<div class="col-md-4">
<div class='btn btn-default control-button left-button'>Left</div>
</div>
<div class="col-md-4">
<div class='btn btn-default control-button suck-button'>Vacuum</div>
</div>
<div class="col-md-4">
<div class='btn btn-default control-button right-button'>Right</div>
</div>
</div>
</div>
</div>
<div class="row">
<div class="col-md-10">
<div class='canvas'></div>
</div>
</div>
</div>
<div class="col-md-4">
<div class="row">
<div class="col-md-6">
<div class='btn btn-success control-button play-button'>Play</div>
</div>
<div class="col-md-6">
<div class='btn btn-default control-button clear-button'>Clear</div>
</div>
</div>
<h5>Moves</h5>
<div class='list-group movesWrapper'>
<ol class='movesList'>
</ol>
</div>
</div>
</div>
<h1 id="searching-with-partial-observations">Searching with Partial Observations</h1>
<p>Now we come back to a world where the actions of the robot are deterministic again (no erratic behavior like before) but, the robot no longer has complete sense of its current state or its environment.</p>
<h2 id="vacuum-world-with-no-observation">Vacuum World with no observation</h2>
<p>In this world, the vacuum cleaner has no idea initially about its own location and the location of dirt in the world. Since the robot has no percept, it should be able to figure out a sequence of actions that will work despite its current state.</p>
<p>Given below are 8 random initial states. You can record a sequence of actions and see it in action just like before. Assume that illegal moves (like moving right in the right-most tile) have no effect on the world.</p>
<p>Try to find a sequence of actions that will lead to a final state (Clean all the dirt), no matter what the initial state of the world.</p>
<div class='row' id='noObservation'>
<div class="col-md-9">
<div class="row">
<div class="col-md-4">
<div class='btn btn-primary restart-button'>Restart</div>
</div>
<div class="col-md-6">
<div class="row">
<div class="col-md-4">
<div class='btn btn-default control-button left-button'>Left</div>
</div>
<div class="col-md-4">
<div class='btn btn-default control-button suck-button'>Vacuum</div>
</div>
<div class="col-md-4">
<div class='btn btn-default control-button right-button'>Right</div>
</div>
</div>
</div>
</div>
<div class="row" id='canvasWrapper'>
</div>
</div>
<div class="col-md-3">
<div class="row">
<div class="col-md-6">
<div class='btn btn-success control-button play-button'>Play</div>
</div>
<div class="col-md-6">
<div class='btn btn-default control-button clear-button'>Clear</div>
</div>
</div>
<h5>Moves</h5>
<div class='list-group movesWrapper'>
<ol class='movesList'>
</ol>
</div>
</div>
</div>
<h2>Localization in a partially observable environment</h2>
<p>
Localization refers to the process of finding its own position in the world by a robot.
</p>
<h3>
Find initial states.
</h3>
<p>
In the given diagram, A robot is assigned a random position in the maze.
Only the current percept of the robot is visible to you.
Try to find all the positions in the maze where the robot can be.
</p>
<div class='row localization' id='localization1'>
<div class="col-md-8">
<div class="row">
<div class="col-md-4">
<div class='btn btn-primary restart-button'>Restart</div>
</div>
</div>
<div class="row canvas">
</div>
</div>
<div class="col-md-4">
<div class="row">
<div class='sidePanel1'>
</div>
</div>
<div class="row">
<div class='sidePanel2'>
</div>
</div>
</div>
</div>
<h3>
Get to know percept.
</h3>
<p>
Hover over the cells of the maze to see the percept the robot would give if it was there.
Also, notice all the other cells which can have the same percept.
</p>
<div class='row localization' id='localization2'>
<div class="col-md-8">
<div class="row canvas">
</div>
</div>
<div class="col-md-4">
<div class="row">
<div class='sidePanel1'>
</div>
</div>
<div class="row">
<div class='sidePanel2'>
</div>
</div>
</div>
</div>
<div class='row localization' id='localization3'>
<div class="col-md-8">
<div class="row">
<div class="col-md-4">
<div class='btn btn-primary restart-button'>Restart</div>
</div>
</div>
<div class="row canvas">
</div>
</div>
<div class="col-md-4">
<div class="row">
<div class='sidePanel1'>
</div>
</div>
<div class="row">
<div class='sidePanel2'>
<button type="button" name="button" class='up'>UP</button>
<button type="button" name="button" class='down'>DOWN</button>
<button type="button" name="button" class='left'>LEFT</button>
<button type="button" name="button" class='right'>RIGHT</button>
</div>
</div>
</div>
</div>
<h2>And-Or-Graph-Search</h2>
<div class="canvas" id="andOrGraphCanvas" height="300px">
</div>
<h2 id="online-dfs-agent">Online DFS Agent</h2>
<p>Click to reset. Green tile is destination.</p>
<div class="canvas" id="onlineDfsCanvas" height="300px">
</div>
<h2 id="lrta-agent">LRTA*-Agent</h2>
<p></p>
<div class="canvas" id="lrtaCanvas" height="300px">
<p></p>
</div>
<div class='license'>
<h4>Third Party License Information</h4>
<ul>
<li><a href="https://thenounproject.com/term/robot/1248/">Robot by Simon Child, The Noun Project</a>, <a href="https://creativecommons.org/licenses/by/3.0/">Creative Commons BY-3.0</a></li>
<li><a href="http://game-icons.net/delapouite/originals/vacuum-cleaner.html">Vacuum Cleaner from Delapouite under CC BY 3.0</a></li>
</ul>
</div>
</div>
</div>
</body>
</html>