Newer
Older
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Angelic Search \n",
"\n",
"Search using angelic semantics (is a hierarchical search), where the agent chooses the implementation of the HLA's. <br>\n",
"The algorithms input is: problem, hierarchy and initialPlan\n",
"- problem is of type Problem \n",
"- hierarchy is a dictionary consisting of all the actions. \n",
"- initialPlan is an approximate description(optimistic and pessimistic) of the agents choices for the implementation. <br>\n",
" It is a nested list, containing sequence a of actions with their optimistic and pessimistic\n",
" description "
]
},
{
"cell_type": "code",
"from planning import * \n",
"from notebook import psource"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The Angelic search algorithm consists of three parts. \n",
"- Search using angelic semantics\n",
"- Decompose\n",
"- a search in the space of refinements, in a similar way with hierarchical search\n",
"\n",
"### Searching using angelic semantics\n",
"- Find the reachable set (optimistic and pessimistic) of the sequence of angelic HLA in initialPlan\n",
" - If the optimistic reachable set doesn't intersect the goal, then there is no solution\n",
" - If the pessimistic reachable set intersects the goal, then we call decompose, in order to find the sequence of actions that lead us to the goal. \n",
" - If the optimistic reachable set intersects the goal, but the pessimistic doesn't we do some further refinements, in order to see if there is a sequence of actions that achieves the goal. \n",
" \n",
"### Search in space of refinements\n",
"- Create a search tree, that has root the action and children it's refinements\n",
"- Extend frontier by adding each refinement, so that we keep looping till we find all primitive actions\n",
"- If we achieve that we return the path of the solution (search tree), else there is no solution and we return None.\n",
"\n",
" \n"
]
},
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
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"<!DOCTYPE html PUBLIC \"-//W3C//DTD HTML 4.01//EN\"\n",
" \"http://www.w3.org/TR/html4/strict.dtd\">\n",
"\n",
"<html>\n",
"<head>\n",
" <title></title>\n",
" <meta http-equiv=\"content-type\" content=\"text/html; charset=None\">\n",
" <style type=\"text/css\">\n",
"td.linenos { background-color: #f0f0f0; padding-right: 10px; }\n",
"span.lineno { background-color: #f0f0f0; padding: 0 5px 0 5px; }\n",
"pre { line-height: 125%; }\n",
"body .hll { background-color: #ffffcc }\n",
"body { background: #f8f8f8; }\n",
"body .c { color: #408080; font-style: italic } /* Comment */\n",
"body .err { border: 1px solid #FF0000 } /* Error */\n",
"body .k { color: #008000; font-weight: bold } /* Keyword */\n",
"body .o { color: #666666 } /* Operator */\n",
"body .ch { color: #408080; font-style: italic } /* Comment.Hashbang */\n",
"body .cm { color: #408080; font-style: italic } /* Comment.Multiline */\n",
"body .cp { color: #BC7A00 } /* Comment.Preproc */\n",
"body .cpf { color: #408080; font-style: italic } /* Comment.PreprocFile */\n",
"body .c1 { color: #408080; font-style: italic } /* Comment.Single */\n",
"body .cs { color: #408080; font-style: italic } /* Comment.Special */\n",
"body .gd { color: #A00000 } /* Generic.Deleted */\n",
"body .ge { font-style: italic } /* Generic.Emph */\n",
"body .gr { color: #FF0000 } /* Generic.Error */\n",
"body .gh { color: #000080; font-weight: bold } /* Generic.Heading */\n",
"body .gi { color: #00A000 } /* Generic.Inserted */\n",
"body .go { color: #888888 } /* Generic.Output */\n",
"body .gp { color: #000080; font-weight: bold } /* Generic.Prompt */\n",
"body .gs { font-weight: bold } /* Generic.Strong */\n",
"body .gu { color: #800080; font-weight: bold } /* Generic.Subheading */\n",
"body .gt { color: #0044DD } /* Generic.Traceback */\n",
"body .kc { color: #008000; font-weight: bold } /* Keyword.Constant */\n",
"body .kd { color: #008000; font-weight: bold } /* Keyword.Declaration */\n",
"body .kn { color: #008000; font-weight: bold } /* Keyword.Namespace */\n",
"body .kp { color: #008000 } /* Keyword.Pseudo */\n",
"body .kr { color: #008000; font-weight: bold } /* Keyword.Reserved */\n",
"body .kt { color: #B00040 } /* Keyword.Type */\n",
"body .m { color: #666666 } /* Literal.Number */\n",
"body .s { color: #BA2121 } /* Literal.String */\n",
"body .na { color: #7D9029 } /* Name.Attribute */\n",
"body .nb { color: #008000 } /* Name.Builtin */\n",
"body .nc { color: #0000FF; font-weight: bold } /* Name.Class */\n",
"body .no { color: #880000 } /* Name.Constant */\n",
"body .nd { color: #AA22FF } /* Name.Decorator */\n",
"body .ni { color: #999999; font-weight: bold } /* Name.Entity */\n",
"body .ne { color: #D2413A; font-weight: bold } /* Name.Exception */\n",
"body .nf { color: #0000FF } /* Name.Function */\n",
"body .nl { color: #A0A000 } /* Name.Label */\n",
"body .nn { color: #0000FF; font-weight: bold } /* Name.Namespace */\n",
"body .nt { color: #008000; font-weight: bold } /* Name.Tag */\n",
"body .nv { color: #19177C } /* Name.Variable */\n",
"body .ow { color: #AA22FF; font-weight: bold } /* Operator.Word */\n",
"body .w { color: #bbbbbb } /* Text.Whitespace */\n",
"body .mb { color: #666666 } /* Literal.Number.Bin */\n",
"body .mf { color: #666666 } /* Literal.Number.Float */\n",
"body .mh { color: #666666 } /* Literal.Number.Hex */\n",
"body .mi { color: #666666 } /* Literal.Number.Integer */\n",
"body .mo { color: #666666 } /* Literal.Number.Oct */\n",
"body .sa { color: #BA2121 } /* Literal.String.Affix */\n",
"body .sb { color: #BA2121 } /* Literal.String.Backtick */\n",
"body .sc { color: #BA2121 } /* Literal.String.Char */\n",
"body .dl { color: #BA2121 } /* Literal.String.Delimiter */\n",
"body .sd { color: #BA2121; font-style: italic } /* Literal.String.Doc */\n",
"body .s2 { color: #BA2121 } /* Literal.String.Double */\n",
"body .se { color: #BB6622; font-weight: bold } /* Literal.String.Escape */\n",
"body .sh { color: #BA2121 } /* Literal.String.Heredoc */\n",
"body .si { color: #BB6688; font-weight: bold } /* Literal.String.Interpol */\n",
"body .sx { color: #008000 } /* Literal.String.Other */\n",
"body .sr { color: #BB6688 } /* Literal.String.Regex */\n",
"body .s1 { color: #BA2121 } /* Literal.String.Single */\n",
"body .ss { color: #19177C } /* Literal.String.Symbol */\n",
"body .bp { color: #008000 } /* Name.Builtin.Pseudo */\n",
"body .fm { color: #0000FF } /* Name.Function.Magic */\n",
"body .vc { color: #19177C } /* Name.Variable.Class */\n",
"body .vg { color: #19177C } /* Name.Variable.Global */\n",
"body .vi { color: #19177C } /* Name.Variable.Instance */\n",
"body .vm { color: #19177C } /* Name.Variable.Magic */\n",
"body .il { color: #666666 } /* Literal.Number.Integer.Long */\n",
"\n",
" </style>\n",
"</head>\n",
"<body>\n",
"<h2></h2>\n",
"\n",
"<div class=\"highlight\"><pre><span></span> <span class=\"k\">def</span> <span class=\"nf\">angelic_search</span><span class=\"p\">(</span><span class=\"n\">problem</span><span class=\"p\">,</span> <span class=\"n\">hierarchy</span><span class=\"p\">,</span> <span class=\"n\">initialPlan</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""</span>\n",
"<span class=\"sd\">\t[Figure 11.8] A hierarchical planning algorithm that uses angelic semantics to identify and</span>\n",
"<span class=\"sd\">\tcommit to high-level plans that work while avoiding high-level plans that don’t. </span>\n",
"<span class=\"sd\">\tThe predicate MAKING-PROGRESS checks to make sure that we aren’t stuck in an infinite regression</span>\n",
"<span class=\"sd\">\tof refinements. </span>\n",
"<span class=\"sd\">\tAt top level, call ANGELIC -SEARCH with [Act ] as the initialPlan .</span>\n",
"\n",
"<span class=\"sd\"> initialPlan contains a sequence of HLA's with angelic semantics </span>\n",
"\n",
"<span class=\"sd\"> The possible effects of an angelic HLA in initialPlan are : </span>\n",
"<span class=\"sd\"> ~ : effect remove</span>\n",
"<span class=\"sd\"> $+: effect possibly add</span>\n",
"<span class=\"sd\"> $-: effect possibly remove</span>\n",
"<span class=\"sd\"> $$: possibly add or remove</span>\n",
"<span class=\"sd\">\t"""</span>\n",
" <span class=\"n\">frontier</span> <span class=\"o\">=</span> <span class=\"n\">deque</span><span class=\"p\">(</span><span class=\"n\">initialPlan</span><span class=\"p\">)</span>\n",
" <span class=\"k\">while</span> <span class=\"bp\">True</span><span class=\"p\">:</span> \n",
" <span class=\"k\">if</span> <span class=\"ow\">not</span> <span class=\"n\">frontier</span><span class=\"p\">:</span>\n",
" <span class=\"k\">return</span> <span class=\"bp\">None</span>\n",
" <span class=\"n\">plan</span> <span class=\"o\">=</span> <span class=\"n\">frontier</span><span class=\"o\">.</span><span class=\"n\">popleft</span><span class=\"p\">()</span> <span class=\"c1\"># sequence of HLA/Angelic HLA's </span>\n",
" <span class=\"n\">opt_reachable_set</span> <span class=\"o\">=</span> <span class=\"n\">Problem</span><span class=\"o\">.</span><span class=\"n\">reach_opt</span><span class=\"p\">(</span><span class=\"n\">problem</span><span class=\"o\">.</span><span class=\"n\">init</span><span class=\"p\">,</span> <span class=\"n\">plan</span><span class=\"p\">)</span>\n",
" <span class=\"n\">pes_reachable_set</span> <span class=\"o\">=</span> <span class=\"n\">Problem</span><span class=\"o\">.</span><span class=\"n\">reach_pes</span><span class=\"p\">(</span><span class=\"n\">problem</span><span class=\"o\">.</span><span class=\"n\">init</span><span class=\"p\">,</span> <span class=\"n\">plan</span><span class=\"p\">)</span>\n",
" <span class=\"k\">if</span> <span class=\"n\">problem</span><span class=\"o\">.</span><span class=\"n\">intersects_goal</span><span class=\"p\">(</span><span class=\"n\">opt_reachable_set</span><span class=\"p\">):</span> \n",
" <span class=\"k\">if</span> <span class=\"n\">Problem</span><span class=\"o\">.</span><span class=\"n\">is_primitive</span><span class=\"p\">(</span> <span class=\"n\">plan</span><span class=\"p\">,</span> <span class=\"n\">hierarchy</span> <span class=\"p\">):</span> \n",
" <span class=\"k\">return</span> <span class=\"p\">([</span><span class=\"n\">x</span> <span class=\"k\">for</span> <span class=\"n\">x</span> <span class=\"ow\">in</span> <span class=\"n\">plan</span><span class=\"o\">.</span><span class=\"n\">action</span><span class=\"p\">])</span>\n",
" <span class=\"n\">guaranteed</span> <span class=\"o\">=</span> <span class=\"n\">problem</span><span class=\"o\">.</span><span class=\"n\">intersects_goal</span><span class=\"p\">(</span><span class=\"n\">pes_reachable_set</span><span class=\"p\">)</span> \n",
" <span class=\"k\">if</span> <span class=\"n\">guaranteed</span> <span class=\"ow\">and</span> <span class=\"n\">Problem</span><span class=\"o\">.</span><span class=\"n\">making_progress</span><span class=\"p\">(</span><span class=\"n\">plan</span><span class=\"p\">,</span> <span class=\"n\">initialPlan</span><span class=\"p\">):</span>\n",
" <span class=\"n\">final_state</span> <span class=\"o\">=</span> <span class=\"n\">guaranteed</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">]</span> <span class=\"c1\"># any element of guaranteed </span>\n",
" <span class=\"c1\">#print('decompose')</span>\n",
" <span class=\"k\">return</span> <span class=\"n\">Problem</span><span class=\"o\">.</span><span class=\"n\">decompose</span><span class=\"p\">(</span><span class=\"n\">hierarchy</span><span class=\"p\">,</span> <span class=\"n\">problem</span><span class=\"p\">,</span> <span class=\"n\">plan</span><span class=\"p\">,</span> <span class=\"n\">final_state</span><span class=\"p\">,</span> <span class=\"n\">pes_reachable_set</span><span class=\"p\">)</span>\n",
" <span class=\"p\">(</span><span class=\"n\">hla</span><span class=\"p\">,</span> <span class=\"n\">index</span><span class=\"p\">)</span> <span class=\"o\">=</span> <span class=\"n\">Problem</span><span class=\"o\">.</span><span class=\"n\">find_hla</span><span class=\"p\">(</span><span class=\"n\">plan</span><span class=\"p\">,</span> <span class=\"n\">hierarchy</span><span class=\"p\">)</span> <span class=\"c1\"># there should be at least one HLA/Angelic_HLA, otherwise plan would be primitive.</span>\n",
" <span class=\"n\">prefix</span> <span class=\"o\">=</span> <span class=\"n\">plan</span><span class=\"o\">.</span><span class=\"n\">action</span><span class=\"p\">[:</span><span class=\"n\">index</span><span class=\"p\">]</span>\n",
" <span class=\"n\">suffix</span> <span class=\"o\">=</span> <span class=\"n\">plan</span><span class=\"o\">.</span><span class=\"n\">action</span><span class=\"p\">[</span><span class=\"n\">index</span><span class=\"o\">+</span><span class=\"mi\">1</span><span class=\"p\">:]</span>\n",
" <span class=\"n\">outcome</span> <span class=\"o\">=</span> <span class=\"n\">Problem</span><span class=\"p\">(</span><span class=\"n\">Problem</span><span class=\"o\">.</span><span class=\"n\">result</span><span class=\"p\">(</span><span class=\"n\">problem</span><span class=\"o\">.</span><span class=\"n\">init</span><span class=\"p\">,</span> <span class=\"n\">prefix</span><span class=\"p\">),</span> <span class=\"n\">problem</span><span class=\"o\">.</span><span class=\"n\">goals</span> <span class=\"p\">,</span> <span class=\"n\">problem</span><span class=\"o\">.</span><span class=\"n\">actions</span> <span class=\"p\">)</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">sequence</span> <span class=\"ow\">in</span> <span class=\"n\">Problem</span><span class=\"o\">.</span><span class=\"n\">refinements</span><span class=\"p\">(</span><span class=\"n\">hla</span><span class=\"p\">,</span> <span class=\"n\">outcome</span><span class=\"p\">,</span> <span class=\"n\">hierarchy</span><span class=\"p\">):</span> <span class=\"c1\"># find refinements</span>\n",
" <span class=\"n\">frontier</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">Angelic_Node</span><span class=\"p\">(</span><span class=\"n\">outcome</span><span class=\"o\">.</span><span class=\"n\">init</span><span class=\"p\">,</span> <span class=\"n\">plan</span><span class=\"p\">,</span> <span class=\"n\">prefix</span> <span class=\"o\">+</span> <span class=\"n\">sequence</span><span class=\"o\">+</span> <span class=\"n\">suffix</span><span class=\"p\">,</span> <span class=\"n\">prefix</span><span class=\"o\">+</span><span class=\"n\">sequence</span><span class=\"o\">+</span><span class=\"n\">suffix</span><span class=\"p\">))</span>\n",
"</pre></div>\n",
"</body>\n",
"</html>\n"
],
"text/plain": [
"<IPython.core.display.HTML object>"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"psource(Problem.angelic_search)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"### Decompose \n",
"- Finds recursively the sequence of states and actions that lead us from initial state to goal.\n",
"- For each of the above actions we find their refinements,if they are not primitive, by calling the angelic_search function. \n",
" If there are not refinements return None\n",
" \n"
]
},
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
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"<!DOCTYPE html PUBLIC \"-//W3C//DTD HTML 4.01//EN\"\n",
" \"http://www.w3.org/TR/html4/strict.dtd\">\n",
"\n",
"<html>\n",
"<head>\n",
" <title></title>\n",
" <meta http-equiv=\"content-type\" content=\"text/html; charset=None\">\n",
" <style type=\"text/css\">\n",
"td.linenos { background-color: #f0f0f0; padding-right: 10px; }\n",
"span.lineno { background-color: #f0f0f0; padding: 0 5px 0 5px; }\n",
"pre { line-height: 125%; }\n",
"body .hll { background-color: #ffffcc }\n",
"body { background: #f8f8f8; }\n",
"body .c { color: #408080; font-style: italic } /* Comment */\n",
"body .err { border: 1px solid #FF0000 } /* Error */\n",
"body .k { color: #008000; font-weight: bold } /* Keyword */\n",
"body .o { color: #666666 } /* Operator */\n",
"body .ch { color: #408080; font-style: italic } /* Comment.Hashbang */\n",
"body .cm { color: #408080; font-style: italic } /* Comment.Multiline */\n",
"body .cp { color: #BC7A00 } /* Comment.Preproc */\n",
"body .cpf { color: #408080; font-style: italic } /* Comment.PreprocFile */\n",
"body .c1 { color: #408080; font-style: italic } /* Comment.Single */\n",
"body .cs { color: #408080; font-style: italic } /* Comment.Special */\n",
"body .gd { color: #A00000 } /* Generic.Deleted */\n",
"body .ge { font-style: italic } /* Generic.Emph */\n",
"body .gr { color: #FF0000 } /* Generic.Error */\n",
"body .gh { color: #000080; font-weight: bold } /* Generic.Heading */\n",
"body .gi { color: #00A000 } /* Generic.Inserted */\n",
"body .go { color: #888888 } /* Generic.Output */\n",
"body .gp { color: #000080; font-weight: bold } /* Generic.Prompt */\n",
"body .gs { font-weight: bold } /* Generic.Strong */\n",
"body .gu { color: #800080; font-weight: bold } /* Generic.Subheading */\n",
"body .gt { color: #0044DD } /* Generic.Traceback */\n",
"body .kc { color: #008000; font-weight: bold } /* Keyword.Constant */\n",
"body .kd { color: #008000; font-weight: bold } /* Keyword.Declaration */\n",
"body .kn { color: #008000; font-weight: bold } /* Keyword.Namespace */\n",
"body .kp { color: #008000 } /* Keyword.Pseudo */\n",
"body .kr { color: #008000; font-weight: bold } /* Keyword.Reserved */\n",
"body .kt { color: #B00040 } /* Keyword.Type */\n",
"body .m { color: #666666 } /* Literal.Number */\n",
"body .s { color: #BA2121 } /* Literal.String */\n",
"body .na { color: #7D9029 } /* Name.Attribute */\n",
"body .nb { color: #008000 } /* Name.Builtin */\n",
"body .nc { color: #0000FF; font-weight: bold } /* Name.Class */\n",
"body .no { color: #880000 } /* Name.Constant */\n",
"body .nd { color: #AA22FF } /* Name.Decorator */\n",
"body .ni { color: #999999; font-weight: bold } /* Name.Entity */\n",
"body .ne { color: #D2413A; font-weight: bold } /* Name.Exception */\n",
"body .nf { color: #0000FF } /* Name.Function */\n",
"body .nl { color: #A0A000 } /* Name.Label */\n",
"body .nn { color: #0000FF; font-weight: bold } /* Name.Namespace */\n",
"body .nt { color: #008000; font-weight: bold } /* Name.Tag */\n",
"body .nv { color: #19177C } /* Name.Variable */\n",
"body .ow { color: #AA22FF; font-weight: bold } /* Operator.Word */\n",
"body .w { color: #bbbbbb } /* Text.Whitespace */\n",
"body .mb { color: #666666 } /* Literal.Number.Bin */\n",
"body .mf { color: #666666 } /* Literal.Number.Float */\n",
"body .mh { color: #666666 } /* Literal.Number.Hex */\n",
"body .mi { color: #666666 } /* Literal.Number.Integer */\n",
"body .mo { color: #666666 } /* Literal.Number.Oct */\n",
"body .sa { color: #BA2121 } /* Literal.String.Affix */\n",
"body .sb { color: #BA2121 } /* Literal.String.Backtick */\n",
"body .sc { color: #BA2121 } /* Literal.String.Char */\n",
"body .dl { color: #BA2121 } /* Literal.String.Delimiter */\n",
"body .sd { color: #BA2121; font-style: italic } /* Literal.String.Doc */\n",
"body .s2 { color: #BA2121 } /* Literal.String.Double */\n",
"body .se { color: #BB6622; font-weight: bold } /* Literal.String.Escape */\n",
"body .sh { color: #BA2121 } /* Literal.String.Heredoc */\n",
"body .si { color: #BB6688; font-weight: bold } /* Literal.String.Interpol */\n",
"body .sx { color: #008000 } /* Literal.String.Other */\n",
"body .sr { color: #BB6688 } /* Literal.String.Regex */\n",
"body .s1 { color: #BA2121 } /* Literal.String.Single */\n",
"body .ss { color: #19177C } /* Literal.String.Symbol */\n",
"body .bp { color: #008000 } /* Name.Builtin.Pseudo */\n",
"body .fm { color: #0000FF } /* Name.Function.Magic */\n",
"body .vc { color: #19177C } /* Name.Variable.Class */\n",
"body .vg { color: #19177C } /* Name.Variable.Global */\n",
"body .vi { color: #19177C } /* Name.Variable.Instance */\n",
"body .vm { color: #19177C } /* Name.Variable.Magic */\n",
"body .il { color: #666666 } /* Literal.Number.Integer.Long */\n",
"\n",
" </style>\n",
"</head>\n",
"<body>\n",
"<h2></h2>\n",
"\n",
"<div class=\"highlight\"><pre><span></span> <span class=\"k\">def</span> <span class=\"nf\">decompose</span><span class=\"p\">(</span><span class=\"n\">hierarchy</span><span class=\"p\">,</span> <span class=\"n\">s_0</span><span class=\"p\">,</span> <span class=\"n\">plan</span><span class=\"p\">,</span> <span class=\"n\">s_f</span><span class=\"p\">,</span> <span class=\"n\">reachable_set</span><span class=\"p\">):</span>\n",
" <span class=\"n\">solution</span> <span class=\"o\">=</span> <span class=\"p\">[]</span> \n",
" <span class=\"n\">i</span> <span class=\"o\">=</span> <span class=\"nb\">max</span><span class=\"p\">(</span><span class=\"n\">reachable_set</span><span class=\"o\">.</span><span class=\"n\">keys</span><span class=\"p\">())</span>\n",
" <span class=\"k\">while</span> <span class=\"n\">plan</span><span class=\"o\">.</span><span class=\"n\">action_pes</span><span class=\"p\">:</span> \n",
" <span class=\"n\">action</span> <span class=\"o\">=</span> <span class=\"n\">plan</span><span class=\"o\">.</span><span class=\"n\">action_pes</span><span class=\"o\">.</span><span class=\"n\">pop</span><span class=\"p\">()</span>\n",
" <span class=\"k\">if</span> <span class=\"p\">(</span><span class=\"n\">i</span><span class=\"o\">==</span><span class=\"mi\">0</span><span class=\"p\">):</span> \n",
" <span class=\"k\">return</span> <span class=\"n\">solution</span>\n",
" <span class=\"n\">s_i</span> <span class=\"o\">=</span> <span class=\"n\">Problem</span><span class=\"o\">.</span><span class=\"n\">find_previous_state</span><span class=\"p\">(</span><span class=\"n\">s_f</span><span class=\"p\">,</span> <span class=\"n\">reachable_set</span><span class=\"p\">,</span><span class=\"n\">i</span><span class=\"p\">,</span> <span class=\"n\">action</span><span class=\"p\">)</span> \n",
" <span class=\"n\">problem</span> <span class=\"o\">=</span> <span class=\"n\">Problem</span><span class=\"p\">(</span><span class=\"n\">s_i</span><span class=\"p\">,</span> <span class=\"n\">s_f</span> <span class=\"p\">,</span> <span class=\"n\">plan</span><span class=\"o\">.</span><span class=\"n\">action</span><span class=\"p\">)</span>\n",
" <span class=\"n\">angelic_call</span> <span class=\"o\">=</span> <span class=\"n\">Problem</span><span class=\"o\">.</span><span class=\"n\">angelic_search</span><span class=\"p\">(</span><span class=\"n\">problem</span><span class=\"p\">,</span> <span class=\"n\">hierarchy</span><span class=\"p\">,</span> <span class=\"p\">[</span><span class=\"n\">Angelic_Node</span><span class=\"p\">(</span><span class=\"n\">s_i</span><span class=\"p\">,</span> <span class=\"n\">Node</span><span class=\"p\">(</span><span class=\"bp\">None</span><span class=\"p\">),</span> <span class=\"p\">[</span><span class=\"n\">action</span><span class=\"p\">],[</span><span class=\"n\">action</span><span class=\"p\">])])</span>\n",
" <span class=\"k\">if</span> <span class=\"n\">angelic_call</span><span class=\"p\">:</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">x</span> <span class=\"ow\">in</span> <span class=\"n\">angelic_call</span><span class=\"p\">:</span> \n",
" <span class=\"n\">solution</span><span class=\"o\">.</span><span class=\"n\">insert</span><span class=\"p\">(</span><span class=\"mi\">0</span><span class=\"p\">,</span><span class=\"n\">x</span><span class=\"p\">)</span>\n",
" <span class=\"k\">else</span><span class=\"p\">:</span> \n",
" <span class=\"k\">return</span> <span class=\"bp\">None</span>\n",
" <span class=\"n\">s_f</span> <span class=\"o\">=</span> <span class=\"n\">s_i</span>\n",
" <span class=\"n\">i</span><span class=\"o\">-=</span><span class=\"mi\">1</span>\n",
" <span class=\"k\">return</span> <span class=\"n\">solution</span>\n",
"</pre></div>\n",
"</body>\n",
"</html>\n"
],
"text/plain": [
"<IPython.core.display.HTML object>"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"psource(Problem.decompose)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Example\n",
"\n",
"Suppose that somebody wants to get to the airport. \n",
"The possible ways to do so is either get a taxi, or drive to the airport. <br>\n",
"Those two actions have some preconditions and some effects. \n",
"If you get the taxi, you need to have cash, whereas if you drive you need to have a car. <br>\n",
"Thus we define the following hierarchy of possible actions.\n",
"\n",
"##### hierarchy"
]
},
{
"cell_type": "code",
"metadata": {},
"outputs": [],
"source": [
"library = {\n",
" 'HLA': ['Go(Home,SFO)', 'Go(Home,SFO)', 'Drive(Home, SFOLongTermParking)', 'Shuttle(SFOLongTermParking, SFO)', 'Taxi(Home, SFO)'],\n",
" 'steps': [['Drive(Home, SFOLongTermParking)', 'Shuttle(SFOLongTermParking, SFO)'], ['Taxi(Home, SFO)'], [], [], []],\n",
" 'precond': [['At(Home) & Have(Car)'], ['At(Home)'], ['At(Home) & Have(Car)'], ['At(SFOLongTermParking)'], ['At(Home)']],\n",
" 'effect': [['At(SFO) & ~At(Home)'], ['At(SFO) & ~At(Home) & ~Have(Cash)'], ['At(SFOLongTermParking) & ~At(Home)'], ['At(SFO) & ~At(LongTermParking)'], ['At(SFO) & ~At(Home) & ~Have(Cash)']] }\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"the possible actions are the following:"
]
},
{
"cell_type": "code",
"metadata": {},
"outputs": [],
"source": [
"go_SFO = HLA('Go(Home,SFO)', precond='At(Home)', effect='At(SFO) & ~At(Home)')\n",
"taxi_SFO = HLA('Taxi(Home,SFO)', precond='At(Home)', effect='At(SFO) & ~At(Home) & ~Have(Cash)')\n",
"drive_SFOLongTermParking = HLA('Drive(Home, SFOLongTermParking)', 'At(Home) & Have(Car)','At(SFOLongTermParking) & ~At(Home)' )\n",
"shuttle_SFO = HLA('Shuttle(SFOLongTermParking, SFO)', 'At(SFOLongTermParking)', 'At(SFO) & ~At(LongTermParking)')"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Suppose that (our preconditionds are that) we are Home and we have cash and car and our goal is to get to SFO and maintain our cash, and our possible actions are the above. <br>\n",
"##### Then our problem is: "
]
},
{
"cell_type": "code",
"metadata": {},
"outputs": [],
"source": [
"prob = Problem('At(Home) & Have(Cash) & Have(Car)', 'At(SFO) & Have(Cash)', [go_SFO, taxi_SFO, drive_SFOLongTermParking,shuttle_SFO])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"An agent gives us some approximate information about the plan we will follow: <br>\n",
"(initialPlan is an Angelic Node, where: \n",
"- state is the initial state of the problem, \n",
"- parent is None \n",
"- action: is a list of actions (Angelic HLA's) with the optimistic estimators of effects and \n",
"- action_pes: is a list of actions (Angelic HLA's) with the pessimistic approximations of the effects\n",
"##### InitialPlan"
]
},
{
"cell_type": "code",
"metadata": {},
"outputs": [],
"source": [
"angelic_opt_description = Angelic_HLA('Go(Home, SFO)', precond = 'At(Home)', effect ='$+At(SFO) & $-At(Home)' ) \n",
"angelic_pes_description = Angelic_HLA('Go(Home, SFO)', precond = 'At(Home)', effect ='$+At(SFO) & ~At(Home)' )\n",
"\n",
"initialPlan = [Angelic_Node(prob.init, None, [angelic_opt_description], [angelic_pes_description])] \n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We want to find the optimistic and pessimistic reachable set of initialPlan when applied to the problem:\n",
"##### Optimistic/Pessimistic reachable set"
]
},
{
"cell_type": "code",
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[[At(Home), Have(Cash), Have(Car)], [Have(Cash), Have(Car), At(SFO), NotAt(Home)], [Have(Cash), Have(Car), NotAt(Home)], [At(Home), Have(Cash), Have(Car), At(SFO)], [At(Home), Have(Cash), Have(Car)]] \n",
"\n",
"[[At(Home), Have(Cash), Have(Car)], [Have(Cash), Have(Car), At(SFO), NotAt(Home)], [Have(Cash), Have(Car), NotAt(Home)]]\n"
]
}
],
"source": [
"opt_reachable_set = Problem.reach_opt(prob.init, initialPlan[0])\n",
"pes_reachable_set = Problem.reach_pes(prob.init, initialPlan[0])\n",
"print([x for y in opt_reachable_set.keys() for x in opt_reachable_set[y]], '\\n')\n",
"print([x for y in pes_reachable_set.keys() for x in pes_reachable_set[y]])\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"##### Refinements"
]
},
{
"cell_type": "code",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[HLA(Drive(Home, SFOLongTermParking)), HLA(Shuttle(SFOLongTermParking, SFO))]\n",
"[{'duration': 0, 'effect': [At(SFOLongTermParking), NotAt(Home)], 'args': (Home, SFOLongTermParking), 'uses': {}, 'consumes': {}, 'name': 'Drive', 'completed': False, 'precond': [At(Home), Have(Car)]}, {'duration': 0, 'effect': [At(SFO), NotAt(LongTermParking)], 'args': (SFOLongTermParking, SFO), 'uses': {}, 'consumes': {}, 'name': 'Shuttle', 'completed': False, 'precond': [At(SFOLongTermParking)]}] \n",
"[{'duration': 0, 'effect': [At(SFO), NotAt(Home), NotHave(Cash)], 'args': (Home, SFO), 'uses': {}, 'consumes': {}, 'name': 'Taxi', 'completed': False, 'precond': [At(Home)]}] \n",
"\n"
]
}
],
"source": [
"for sequence in Problem.refinements(go_SFO, prob, library):\n",
" print (sequence)\n",
" print([x.__dict__ for x in sequence ], '\\n')"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Run the angelic search\n",
"##### Top level call"
]
},
{
"cell_type": "code",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[HLA(Drive(Home, SFOLongTermParking)), HLA(Shuttle(SFOLongTermParking, SFO))] \n",
"\n",
"[{'duration': 0, 'effect': [At(SFOLongTermParking), NotAt(Home)], 'args': (Home, SFOLongTermParking), 'uses': {}, 'consumes': {}, 'name': 'Drive', 'completed': False, 'precond': [At(Home), Have(Car)]}, {'duration': 0, 'effect': [At(SFO), NotAt(LongTermParking)], 'args': (SFOLongTermParking, SFO), 'uses': {}, 'consumes': {}, 'name': 'Shuttle', 'completed': False, 'precond': [At(SFOLongTermParking)]}]\n"
]
}
],
"source": [
"plan= Problem.angelic_search(prob, library, initialPlan)\n",
"print (plan, '\\n')\n",
"print ([x.__dict__ for x in plan])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Example 2"
]
},
{
"cell_type": "code",
"metadata": {},
"outputs": [],
"source": [
"library_2 = {\n",
" 'HLA': ['Go(Home,SFO)', 'Go(Home,SFO)', 'Bus(Home, MetroStop)', 'Metro(MetroStop, SFO)' , 'Metro(MetroStop, SFO)', 'Metro1(MetroStop, SFO)', 'Metro2(MetroStop, SFO)' ,'Taxi(Home, SFO)'],\n",
" 'steps': [['Bus(Home, MetroStop)', 'Metro(MetroStop, SFO)'], ['Taxi(Home, SFO)'], [], ['Metro1(MetroStop, SFO)'], ['Metro2(MetroStop, SFO)'],[],[],[]],\n",
" 'precond': [['At(Home)'], ['At(Home)'], ['At(Home)'], ['At(MetroStop)'], ['At(MetroStop)'],['At(MetroStop)'], ['At(MetroStop)'] ,['At(Home) & Have(Cash)']],\n",
" 'effect': [['At(SFO) & ~At(Home)'], ['At(SFO) & ~At(Home) & ~Have(Cash)'], ['At(MetroStop) & ~At(Home)'], ['At(SFO) & ~At(MetroStop)'], ['At(SFO) & ~At(MetroStop)'], ['At(SFO) & ~At(MetroStop)'] , ['At(SFO) & ~At(MetroStop)'] ,['At(SFO) & ~At(Home) & ~Have(Cash)']] \n",
" }"
]
},
{
"cell_type": "code",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[HLA(Bus(Home, MetroStop)), HLA(Metro1(MetroStop, SFO))] \n",
"\n",
"[{'duration': 0, 'effect': [At(MetroStop), NotAt(Home)], 'args': (Home, MetroStop), 'uses': {}, 'consumes': {}, 'name': 'Bus', 'completed': False, 'precond': [At(Home)]}, {'duration': 0, 'effect': [At(SFO), NotAt(MetroStop)], 'args': (MetroStop, SFO), 'uses': {}, 'consumes': {}, 'name': 'Metro1', 'completed': False, 'precond': [At(MetroStop)]}]\n"
]
}
],
"source": [
"plan_2 = Problem.angelic_search(prob, library_2, initialPlan)\n",
"print(plan_2, '\\n')\n",
"print([x.__dict__ for x in plan_2])"
]
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Example 3 \n",
"\n",
"Sometimes there is no plan that achieves the goal!"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [],
"source": [
"library_3 = {\n",
" 'HLA': ['Shuttle(SFOLongTermParking, SFO)', 'Go(Home, SFOLongTermParking)', 'Taxi(Home, SFOLongTermParking)', 'Drive(Home, SFOLongTermParking)', 'Drive(SFOLongTermParking, Home)', 'Get(Cash)', 'Go(Home, ATM)'],\n",
" 'steps': [['Get(Cash)', 'Go(Home, SFOLongTermParking)'], ['Taxi(Home, SFOLongTermParking)'], [], [], [], ['Drive(SFOLongTermParking, Home)', 'Go(Home, ATM)'], []],\n",
" 'precond': [['At(SFOLongTermParking)'], ['At(Home)'], ['At(Home) & Have(Cash)'], ['At(Home)'], ['At(SFOLongTermParking)'], ['At(SFOLongTermParking)'], ['At(Home)']],\n",
" 'effect': [['At(SFO)'], ['At(SFO)'], ['At(SFOLongTermParking) & ~Have(Cash)'], ['At(SFOLongTermParking)'] ,['At(Home) & ~At(SFOLongTermParking)'], ['At(Home) & Have(Cash)'], ['Have(Cash)'] ]\n",
" }\n"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [],
"source": [
"shuttle_SFO = HLA('Shuttle(SFOLongTermParking, SFO)', 'Have(Cash) & At(SFOLongTermParking)', 'At(SFO)')\n",
"prob_3 = Problem('At(SFOLongTermParking) & Have(Cash)', 'At(SFO) & Have(Cash)', [shuttle_SFO])\n",
"# optimistic/pessimistic descriptions\n",
"angelic_opt_description = Angelic_HLA('Shuttle(SFOLongTermParking, SFO)', precond = 'At(SFOLongTermParking)', effect ='$+At(SFO) & $-At(SFOLongTermParking)' ) \n",
"angelic_pes_description = Angelic_HLA('Shuttle(SFOLongTermParking, SFO)', precond = 'At(SFOLongTermParking)', effect ='$+At(SFO) & ~At(SFOLongTermParking)' ) \n",
"# initial Plan\n",
"initialPlan_3 = [Angelic_Node(prob.init, None, [angelic_opt_description], [angelic_pes_description])] "
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"None\n"
]
}
],
"source": [
"plan_3 = prob_3.angelic_search(library_3, initialPlan_3)\n",
"print(plan_3)"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.5.3"
}
},
"nbformat": 4,
"nbformat_minor": 1
}