Newer
Older
" <span class=\"k\">def</span> <span class=\"nf\">act</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">action</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""</span>\n",
"<span class=\"sd\"> Performs the HLA given as argument.</span>\n",
"<span class=\"sd\"> Note that this is different from the superclass action - where the parameter was an</span>\n",
"<span class=\"sd\"> Expression. For real world problems, an Expr object isn't enough to capture all the</span>\n",
"<span class=\"sd\"> detail required for executing the action - resources, preconditions, etc need to be</span>\n",
"<span class=\"sd\"> checked for too.</span>\n",
"<span class=\"sd\"> """</span>\n",
" <span class=\"n\">args</span> <span class=\"o\">=</span> <span class=\"n\">action</span><span class=\"o\">.</span><span class=\"n\">args</span>\n",
" <span class=\"n\">list_action</span> <span class=\"o\">=</span> <span class=\"n\">first</span><span class=\"p\">(</span><span class=\"n\">a</span> <span class=\"k\">for</span> <span class=\"n\">a</span> <span class=\"ow\">in</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">actions</span> <span class=\"k\">if</span> <span class=\"n\">a</span><span class=\"o\">.</span><span class=\"n\">name</span> <span class=\"o\">==</span> <span class=\"n\">action</span><span class=\"o\">.</span><span class=\"n\">name</span><span class=\"p\">)</span>\n",
" <span class=\"k\">if</span> <span class=\"n\">list_action</span> <span class=\"ow\">is</span> <span class=\"bp\">None</span><span class=\"p\">:</span>\n",
" <span class=\"k\">raise</span> <span class=\"ne\">Exception</span><span class=\"p\">(</span><span class=\"s2\">"Action '{}' not found"</span><span class=\"o\">.</span><span class=\"n\">format</span><span class=\"p\">(</span><span class=\"n\">action</span><span class=\"o\">.</span><span class=\"n\">name</span><span class=\"p\">))</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">init</span> <span class=\"o\">=</span> <span class=\"n\">list_action</span><span class=\"o\">.</span><span class=\"n\">do_action</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">jobs</span><span class=\"p\">,</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">resources</span><span class=\"p\">,</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">init</span><span class=\"p\">,</span> <span class=\"n\">args</span><span class=\"p\">)</span><span class=\"o\">.</span><span class=\"n\">clauses</span>\n",
5016
5017
5018
5019
5020
5021
5022
5023
5024
5025
5026
5027
5028
5029
5030
5031
5032
5033
5034
5035
5036
5037
5038
5039
5040
5041
5042
5043
5044
5045
5046
" <span class=\"k\">def</span> <span class=\"nf\">refinements</span><span class=\"p\">(</span><span class=\"n\">hla</span><span class=\"p\">,</span> <span class=\"n\">state</span><span class=\"p\">,</span> <span class=\"n\">library</span><span class=\"p\">):</span> <span class=\"c1\"># TODO - refinements may be (multiple) HLA themselves ...</span>\n",
" <span class=\"sd\">"""</span>\n",
"<span class=\"sd\"> state is a Problem, containing the current state kb</span>\n",
"<span class=\"sd\"> library is a dictionary containing details for every possible refinement. eg:</span>\n",
"<span class=\"sd\"> {</span>\n",
"<span class=\"sd\"> 'HLA': ['Go(Home,SFO)', 'Go(Home,SFO)', 'Drive(Home, SFOLongTermParking)', 'Shuttle(SFOLongTermParking, SFO)', 'Taxi(Home, SFO)'],</span>\n",
"<span class=\"sd\"> 'steps': [['Drive(Home, SFOLongTermParking)', 'Shuttle(SFOLongTermParking, SFO)'], ['Taxi(Home, SFO)'], [], [], []],</span>\n",
"<span class=\"sd\"> # empty refinements ie primitive action</span>\n",
"<span class=\"sd\"> 'precond': [['At(Home), Have(Car)'], ['At(Home)'], ['At(Home)', 'Have(Car)'], ['At(SFOLongTermParking)'], ['At(Home)']],</span>\n",
"<span class=\"sd\"> 'effect': [['At(SFO)'], ['At(SFO)'], ['At(SFOLongTermParking)'], ['At(SFO)'], ['At(SFO)'], ['~At(Home)'], ['~At(Home)'], ['~At(Home)'], ['~At(SFOLongTermParking)'], ['~At(Home)']]</span>\n",
"<span class=\"sd\"> }</span>\n",
"<span class=\"sd\"> """</span>\n",
" <span class=\"n\">e</span> <span class=\"o\">=</span> <span class=\"n\">Expr</span><span class=\"p\">(</span><span class=\"n\">hla</span><span class=\"o\">.</span><span class=\"n\">name</span><span class=\"p\">,</span> <span class=\"n\">hla</span><span class=\"o\">.</span><span class=\"n\">args</span><span class=\"p\">)</span>\n",
" <span class=\"n\">indices</span> <span class=\"o\">=</span> <span class=\"p\">[</span><span class=\"n\">i</span> <span class=\"k\">for</span> <span class=\"n\">i</span><span class=\"p\">,</span> <span class=\"n\">x</span> <span class=\"ow\">in</span> <span class=\"nb\">enumerate</span><span class=\"p\">(</span><span class=\"n\">library</span><span class=\"p\">[</span><span class=\"s1\">'HLA'</span><span class=\"p\">])</span> <span class=\"k\">if</span> <span class=\"n\">expr</span><span class=\"p\">(</span><span class=\"n\">x</span><span class=\"p\">)</span><span class=\"o\">.</span><span class=\"n\">op</span> <span class=\"o\">==</span> <span class=\"n\">hla</span><span class=\"o\">.</span><span class=\"n\">name</span><span class=\"p\">]</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">i</span> <span class=\"ow\">in</span> <span class=\"n\">indices</span><span class=\"p\">:</span>\n",
" <span class=\"c1\"># TODO multiple refinements</span>\n",
" <span class=\"n\">precond</span> <span class=\"o\">=</span> <span class=\"p\">[]</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">p</span> <span class=\"ow\">in</span> <span class=\"n\">library</span><span class=\"p\">[</span><span class=\"s1\">'precond'</span><span class=\"p\">][</span><span class=\"n\">i</span><span class=\"p\">]:</span>\n",
" <span class=\"k\">if</span> <span class=\"n\">p</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">]</span> <span class=\"o\">==</span> <span class=\"s1\">'~'</span><span class=\"p\">:</span>\n",
" <span class=\"n\">precond</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">expr</span><span class=\"p\">(</span><span class=\"s1\">'Not'</span> <span class=\"o\">+</span> <span class=\"n\">p</span><span class=\"p\">[</span><span class=\"mi\">1</span><span class=\"p\">:]))</span>\n",
" <span class=\"k\">else</span><span class=\"p\">:</span>\n",
" <span class=\"n\">precond</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">expr</span><span class=\"p\">(</span><span class=\"n\">p</span><span class=\"p\">))</span>\n",
" <span class=\"n\">effect</span> <span class=\"o\">=</span> <span class=\"p\">[]</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">e</span> <span class=\"ow\">in</span> <span class=\"n\">library</span><span class=\"p\">[</span><span class=\"s1\">'effect'</span><span class=\"p\">][</span><span class=\"n\">i</span><span class=\"p\">]:</span>\n",
" <span class=\"k\">if</span> <span class=\"n\">e</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">]</span> <span class=\"o\">==</span> <span class=\"s1\">'~'</span><span class=\"p\">:</span>\n",
" <span class=\"n\">effect</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">expr</span><span class=\"p\">(</span><span class=\"s1\">'Not'</span> <span class=\"o\">+</span> <span class=\"n\">e</span><span class=\"p\">[</span><span class=\"mi\">1</span><span class=\"p\">:]))</span>\n",
" <span class=\"k\">else</span><span class=\"p\">:</span>\n",
" <span class=\"n\">effect</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">expr</span><span class=\"p\">(</span><span class=\"n\">e</span><span class=\"p\">))</span>\n",
" <span class=\"n\">action</span> <span class=\"o\">=</span> <span class=\"n\">HLA</span><span class=\"p\">(</span><span class=\"n\">library</span><span class=\"p\">[</span><span class=\"s1\">'steps'</span><span class=\"p\">][</span><span class=\"n\">i</span><span class=\"p\">][</span><span class=\"mi\">0</span><span class=\"p\">],</span> <span class=\"n\">precond</span><span class=\"p\">,</span> <span class=\"n\">effect</span><span class=\"p\">)</span>\n",
" <span class=\"k\">if</span> <span class=\"n\">action</span><span class=\"o\">.</span><span class=\"n\">check_precond</span><span class=\"p\">(</span><span class=\"n\">state</span><span class=\"o\">.</span><span class=\"n\">init</span><span class=\"p\">,</span> <span class=\"n\">action</span><span class=\"o\">.</span><span class=\"n\">args</span><span class=\"p\">):</span>\n",
" <span class=\"k\">yield</span> <span class=\"n\">action</span>\n",
5048
5049
5050
5051
5052
5053
5054
5055
5056
5057
5058
5059
5060
5061
5062
5063
5064
5065
5066
5067
5068
5069
5070
" <span class=\"k\">def</span> <span class=\"nf\">hierarchical_search</span><span class=\"p\">(</span><span class=\"n\">problem</span><span class=\"p\">,</span> <span class=\"n\">hierarchy</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""</span>\n",
"<span class=\"sd\"> [Figure 11.5] 'Hierarchical Search, a Breadth First Search implementation of Hierarchical</span>\n",
"<span class=\"sd\"> Forward Planning Search'</span>\n",
"<span class=\"sd\"> The problem is a real-world problem defined by the problem class, and the hierarchy is</span>\n",
"<span class=\"sd\"> a dictionary of HLA - refinements (see refinements generator for details)</span>\n",
"<span class=\"sd\"> """</span>\n",
" <span class=\"n\">act</span> <span class=\"o\">=</span> <span class=\"n\">Node</span><span class=\"p\">(</span><span class=\"n\">problem</span><span class=\"o\">.</span><span class=\"n\">actions</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">])</span>\n",
" <span class=\"n\">frontier</span> <span class=\"o\">=</span> <span class=\"n\">deque</span><span class=\"p\">()</span>\n",
" <span class=\"n\">frontier</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">act</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>\n",
" <span class=\"k\">print</span><span class=\"p\">(</span><span class=\"n\">plan</span><span class=\"o\">.</span><span class=\"n\">state</span><span class=\"o\">.</span><span class=\"n\">name</span><span class=\"p\">)</span>\n",
" <span class=\"n\">hla</span> <span class=\"o\">=</span> <span class=\"n\">plan</span><span class=\"o\">.</span><span class=\"n\">state</span> <span class=\"c1\"># first_or_null(plan)</span>\n",
" <span class=\"n\">prefix</span> <span class=\"o\">=</span> <span class=\"bp\">None</span>\n",
" <span class=\"k\">if</span> <span class=\"n\">plan</span><span class=\"o\">.</span><span class=\"n\">parent</span><span class=\"p\">:</span>\n",
" <span class=\"n\">prefix</span> <span class=\"o\">=</span> <span class=\"n\">plan</span><span class=\"o\">.</span><span class=\"n\">parent</span><span class=\"o\">.</span><span class=\"n\">state</span><span class=\"o\">.</span><span class=\"n\">action</span> <span class=\"c1\"># prefix, suffix = subseq(plan.state, hla)</span>\n",
" <span class=\"n\">outcome</span> <span class=\"o\">=</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=\"p\">,</span> <span class=\"n\">prefix</span><span class=\"p\">)</span>\n",
" <span class=\"k\">if</span> <span class=\"n\">hla</span> <span class=\"ow\">is</span> <span class=\"bp\">None</span><span class=\"p\">:</span>\n",
" <span class=\"k\">if</span> <span class=\"n\">outcome</span><span class=\"o\">.</span><span class=\"n\">goal_test</span><span class=\"p\">():</span>\n",
" <span class=\"k\">return</span> <span class=\"n\">plan</span><span class=\"o\">.</span><span class=\"n\">path</span><span class=\"p\">()</span>\n",
" <span class=\"k\">else</span><span class=\"p\">:</span>\n",
" <span class=\"k\">print</span><span class=\"p\">(</span><span class=\"s2\">"else"</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>\n",
" <span class=\"k\">print</span><span class=\"p\">(</span><span class=\"s2\">"..."</span><span class=\"p\">)</span>\n",
" <span class=\"n\">frontier</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">Node</span><span class=\"p\">(</span><span class=\"n\">plan</span><span class=\"o\">.</span><span class=\"n\">state</span><span class=\"p\">,</span> <span class=\"n\">plan</span><span class=\"o\">.</span><span class=\"n\">parent</span><span class=\"p\">,</span> <span class=\"n\">sequence</span><span class=\"p\">))</span>\n",
" <span class=\"k\">def</span> <span class=\"nf\">result</span><span class=\"p\">(</span><span class=\"n\">problem</span><span class=\"p\">,</span> <span class=\"n\">action</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""The outcome of applying an action to the current problem"""</span>\n",
" <span class=\"k\">if</span> <span class=\"n\">action</span> <span class=\"ow\">is</span> <span class=\"ow\">not</span> <span class=\"bp\">None</span><span class=\"p\">:</span>\n",
" <span class=\"n\">problem</span><span class=\"o\">.</span><span class=\"n\">act</span><span class=\"p\">(</span><span class=\"n\">action</span><span class=\"p\">)</span>\n",
" <span class=\"k\">return</span> <span class=\"n\">problem</span>\n",
" <span class=\"k\">else</span><span class=\"p\">:</span>\n",
" <span class=\"k\">return</span> <span class=\"n\">problem</span>\n",
"</pre></div>\n",
"</body>\n",
"</html>\n"
],
"text/plain": [
"<IPython.core.display.HTML object>"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## HLA\n",
"To be able to model a real-world planning problem properly, it is essential to be able to represent a _high-level action (HLA)_ that can be hierarchically reduced to primitive actions."
]
},
{
"cell_type": "code",
"metadata": {},
"outputs": [
{
5114
5115
5116
5117
5118
5119
5120
5121
5122
5123
5124
5125
5126
5127
5128
5129
5130
5131
5132
5133
5134
5135
5136
5137
5138
5139
5140
5141
5142
5143
5144
5145
5146
5147
5148
5149
5150
5151
5152
5153
5154
5155
5156
5157
5158
5159
5160
5161
5162
5163
5164
5165
5166
5167
5168
5169
5170
5171
5172
5173
5174
5175
5176
5177
5178
5179
5180
5181
5182
5183
5184
5185
5186
5187
5188
5189
5190
5191
5192
5193
5194
5195
5196
5197
5198
5199
5200
5201
"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\">class</span> <span class=\"nc\">HLA</span><span class=\"p\">(</span><span class=\"n\">Action</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""</span>\n",
"<span class=\"sd\"> Define Actions for the real-world (that may be refined further), and satisfy resource</span>\n",
"<span class=\"sd\"> constraints.</span>\n",
"<span class=\"sd\"> """</span>\n",
" <span class=\"n\">unique_group</span> <span class=\"o\">=</span> <span class=\"mi\">1</span>\n",
" <span class=\"k\">def</span> <span class=\"fm\">__init__</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">action</span><span class=\"p\">,</span> <span class=\"n\">precond</span><span class=\"o\">=</span><span class=\"bp\">None</span><span class=\"p\">,</span> <span class=\"n\">effect</span><span class=\"o\">=</span><span class=\"bp\">None</span><span class=\"p\">,</span> <span class=\"n\">duration</span><span class=\"o\">=</span><span class=\"mi\">0</span><span class=\"p\">,</span>\n",
" <span class=\"n\">consume</span><span class=\"o\">=</span><span class=\"bp\">None</span><span class=\"p\">,</span> <span class=\"n\">use</span><span class=\"o\">=</span><span class=\"bp\">None</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""</span>\n",
"<span class=\"sd\"> As opposed to actions, to define HLA, we have added constraints.</span>\n",
"<span class=\"sd\"> duration holds the amount of time required to execute the task</span>\n",
"<span class=\"sd\"> consumes holds a dictionary representing the resources the task consumes</span>\n",
"<span class=\"sd\"> uses holds a dictionary representing the resources the task uses</span>\n",
"<span class=\"sd\"> """</span>\n",
" <span class=\"n\">precond</span> <span class=\"o\">=</span> <span class=\"n\">precond</span> <span class=\"ow\">or</span> <span class=\"p\">[</span><span class=\"bp\">None</span><span class=\"p\">]</span>\n",
" <span class=\"n\">effect</span> <span class=\"o\">=</span> <span class=\"n\">effect</span> <span class=\"ow\">or</span> <span class=\"p\">[</span><span class=\"bp\">None</span><span class=\"p\">]</span>\n",
" <span class=\"nb\">super</span><span class=\"p\">()</span><span class=\"o\">.</span><span class=\"fm\">__init__</span><span class=\"p\">(</span><span class=\"n\">action</span><span class=\"p\">,</span> <span class=\"n\">precond</span><span class=\"p\">,</span> <span class=\"n\">effect</span><span class=\"p\">)</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">duration</span> <span class=\"o\">=</span> <span class=\"n\">duration</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">consumes</span> <span class=\"o\">=</span> <span class=\"n\">consume</span> <span class=\"ow\">or</span> <span class=\"p\">{}</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">uses</span> <span class=\"o\">=</span> <span class=\"n\">use</span> <span class=\"ow\">or</span> <span class=\"p\">{}</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">completed</span> <span class=\"o\">=</span> <span class=\"bp\">False</span>\n",
" <span class=\"c1\"># self.priority = -1 # must be assigned in relation to other HLAs</span>\n",
" <span class=\"c1\"># self.job_group = -1 # must be assigned in relation to other HLAs</span>\n",
" <span class=\"k\">def</span> <span class=\"nf\">do_action</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">job_order</span><span class=\"p\">,</span> <span class=\"n\">available_resources</span><span class=\"p\">,</span> <span class=\"n\">kb</span><span class=\"p\">,</span> <span class=\"n\">args</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""</span>\n",
"<span class=\"sd\"> An HLA based version of act - along with knowledge base updation, it handles</span>\n",
"<span class=\"sd\"> resource checks, and ensures the actions are executed in the correct order.</span>\n",
"<span class=\"sd\"> """</span>\n",
" <span class=\"c1\"># print(self.name)</span>\n",
" <span class=\"k\">if</span> <span class=\"ow\">not</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">has_usable_resource</span><span class=\"p\">(</span><span class=\"n\">available_resources</span><span class=\"p\">):</span>\n",
" <span class=\"k\">raise</span> <span class=\"ne\">Exception</span><span class=\"p\">(</span><span class=\"s1\">'Not enough usable resources to execute {}'</span><span class=\"o\">.</span><span class=\"n\">format</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">name</span><span class=\"p\">))</span>\n",
" <span class=\"k\">if</span> <span class=\"ow\">not</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">has_consumable_resource</span><span class=\"p\">(</span><span class=\"n\">available_resources</span><span class=\"p\">):</span>\n",
" <span class=\"k\">raise</span> <span class=\"ne\">Exception</span><span class=\"p\">(</span><span class=\"s1\">'Not enough consumable resources to execute {}'</span><span class=\"o\">.</span><span class=\"n\">format</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">name</span><span class=\"p\">))</span>\n",
" <span class=\"k\">if</span> <span class=\"ow\">not</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">inorder</span><span class=\"p\">(</span><span class=\"n\">job_order</span><span class=\"p\">):</span>\n",
" <span class=\"k\">raise</span> <span class=\"ne\">Exception</span><span class=\"p\">(</span><span class=\"s2\">"Can't execute {} - execute prerequisite actions first"</span><span class=\"o\">.</span>\n",
" <span class=\"n\">format</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">name</span><span class=\"p\">))</span>\n",
" <span class=\"n\">kb</span> <span class=\"o\">=</span> <span class=\"nb\">super</span><span class=\"p\">()</span><span class=\"o\">.</span><span class=\"n\">act</span><span class=\"p\">(</span><span class=\"n\">kb</span><span class=\"p\">,</span> <span class=\"n\">args</span><span class=\"p\">)</span> <span class=\"c1\"># update knowledge base</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">resource</span> <span class=\"ow\">in</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">consumes</span><span class=\"p\">:</span> <span class=\"c1\"># remove consumed resources</span>\n",
" <span class=\"n\">available_resources</span><span class=\"p\">[</span><span class=\"n\">resource</span><span class=\"p\">]</span> <span class=\"o\">-=</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">consumes</span><span class=\"p\">[</span><span class=\"n\">resource</span><span class=\"p\">]</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">completed</span> <span class=\"o\">=</span> <span class=\"bp\">True</span> <span class=\"c1\"># set the task status to complete</span>\n",
" <span class=\"k\">return</span> <span class=\"n\">kb</span>\n",
" <span class=\"k\">def</span> <span class=\"nf\">has_consumable_resource</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">available_resources</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""</span>\n",
"<span class=\"sd\"> Ensure there are enough consumable resources for this action to execute.</span>\n",
"<span class=\"sd\"> """</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">resource</span> <span class=\"ow\">in</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">consumes</span><span class=\"p\">:</span>\n",
" <span class=\"k\">if</span> <span class=\"n\">available_resources</span><span class=\"o\">.</span><span class=\"n\">get</span><span class=\"p\">(</span><span class=\"n\">resource</span><span class=\"p\">)</span> <span class=\"ow\">is</span> <span class=\"bp\">None</span><span class=\"p\">:</span>\n",
" <span class=\"k\">return</span> <span class=\"bp\">False</span>\n",
" <span class=\"k\">if</span> <span class=\"n\">available_resources</span><span class=\"p\">[</span><span class=\"n\">resource</span><span class=\"p\">]</span> <span class=\"o\"><</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">consumes</span><span class=\"p\">[</span><span class=\"n\">resource</span><span class=\"p\">]:</span>\n",
" <span class=\"k\">return</span> <span class=\"bp\">False</span>\n",
" <span class=\"k\">return</span> <span class=\"bp\">True</span>\n",
" <span class=\"k\">def</span> <span class=\"nf\">has_usable_resource</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">available_resources</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""</span>\n",
"<span class=\"sd\"> Ensure there are enough usable resources for this action to execute.</span>\n",
"<span class=\"sd\"> """</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">resource</span> <span class=\"ow\">in</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">uses</span><span class=\"p\">:</span>\n",
" <span class=\"k\">if</span> <span class=\"n\">available_resources</span><span class=\"o\">.</span><span class=\"n\">get</span><span class=\"p\">(</span><span class=\"n\">resource</span><span class=\"p\">)</span> <span class=\"ow\">is</span> <span class=\"bp\">None</span><span class=\"p\">:</span>\n",
" <span class=\"k\">return</span> <span class=\"bp\">False</span>\n",
" <span class=\"k\">if</span> <span class=\"n\">available_resources</span><span class=\"p\">[</span><span class=\"n\">resource</span><span class=\"p\">]</span> <span class=\"o\"><</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">uses</span><span class=\"p\">[</span><span class=\"n\">resource</span><span class=\"p\">]:</span>\n",
" <span class=\"k\">return</span> <span class=\"bp\">False</span>\n",
" <span class=\"k\">return</span> <span class=\"bp\">True</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"nf\">inorder</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">job_order</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""</span>\n",
"<span class=\"sd\"> Ensure that all the jobs that had to be executed before the current one have been</span>\n",
"<span class=\"sd\"> successfully executed.</span>\n",
"<span class=\"sd\"> """</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">jobs</span> <span class=\"ow\">in</span> <span class=\"n\">job_order</span><span class=\"p\">:</span>\n",
" <span class=\"k\">if</span> <span class=\"bp\">self</span> <span class=\"ow\">in</span> <span class=\"n\">jobs</span><span class=\"p\">:</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">job</span> <span class=\"ow\">in</span> <span class=\"n\">jobs</span><span class=\"p\">:</span>\n",
" <span class=\"k\">if</span> <span class=\"n\">job</span> <span class=\"ow\">is</span> <span class=\"bp\">self</span><span class=\"p\">:</span>\n",
" <span class=\"k\">return</span> <span class=\"bp\">True</span>\n",
" <span class=\"k\">if</span> <span class=\"ow\">not</span> <span class=\"n\">job</span><span class=\"o\">.</span><span class=\"n\">completed</span><span class=\"p\">:</span>\n",
" <span class=\"k\">return</span> <span class=\"bp\">False</span>\n",
" <span class=\"k\">return</span> <span class=\"bp\">True</span>\n",
"</pre></div>\n",
"</body>\n",
"</html>\n"
],
"text/plain": [
"<IPython.core.display.HTML object>"
]
},
"metadata": {},
"output_type": "display_data"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
5301
5302
5303
5304
5305
5306
5307
5308
5309
5310
5311
5312
5313
5314
5315
5316
5317
5318
5319
5320
5321
5322
"In addition to preconditions and effects, an object of the `HLA` class also stores:\n",
"- the `duration` of the HLA\n",
"- the quantity of consumption of _consumable_ resources\n",
"- the quantity of _reusable_ resources used\n",
"- a bool `completed` denoting if the `HLA` has been completed\n",
"\n",
"The class also has some useful helper methods:\n",
"- `do_action`: checks if required consumable and reusable resources are available and if so, executes the action.\n",
"- `has_consumable_resource`: checks if there exists sufficient quantity of the required consumable resource.\n",
"- `has_usable_resource`: checks if reusable resources are available and not already engaged.\n",
"- `inorder`: ensures that all the jobs that had to be executed before the current one have been successfully executed."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## PLANNING PROBLEMS\n",
"---\n",
"## Job-shop Problem\n",
"This is a simple problem involving the assembly of two cars simultaneously.\n",
"The problem consists of two jobs, each of the form [`AddEngine`, `AddWheels`, `Inspect`] to be performed on two cars with different requirements and availability of resources.\n",
"Let's look at how the `job_shop_problem` has been defined on the module."
]
},
{
"cell_type": "code",
5330
5331
5332
5333
5334
5335
5336
5337
5338
5339
5340
5341
5342
5343
5344
5345
5346
5347
5348
5349
5350
5351
5352
5353
5354
5355
5356
5357
5358
5359
5360
5361
5362
5363
5364
5365
5366
5367
5368
5369
5370
5371
5372
5373
5374
5375
5376
5377
5378
5379
5380
5381
5382
5383
5384
5385
5386
5387
5388
5389
5390
5391
5392
5393
5394
5395
5396
5397
5398
5399
5400
5401
5402
5403
5404
5405
5406
5407
5408
5409
5410
5411
5412
5413
5414
5415
"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",
"<div class=\"highlight\"><pre><span></span><span class=\"k\">def</span> <span class=\"nf\">job_shop_problem</span><span class=\"p\">():</span>\n",
" <span class=\"sd\">"""</span>\n",
"<span class=\"sd\"> [Figure 11.1] JOB-SHOP-PROBLEM</span>\n",
"<span class=\"sd\"> A job-shop scheduling problem for assembling two cars,</span>\n",
"<span class=\"sd\"> with resource and ordering constraints.</span>\n",
"<span class=\"sd\"> Example:</span>\n",
"<span class=\"sd\"> >>> from planning import *</span>\n",
"<span class=\"sd\"> >>> p = job_shop_problem()</span>\n",
"<span class=\"sd\"> >>> p.goal_test()</span>\n",
"<span class=\"sd\"> False</span>\n",
"<span class=\"sd\"> >>> p.act(p.jobs[1][0])</span>\n",
"<span class=\"sd\"> >>> p.act(p.jobs[1][1])</span>\n",
"<span class=\"sd\"> >>> p.act(p.jobs[1][2])</span>\n",
"<span class=\"sd\"> >>> p.act(p.jobs[0][0])</span>\n",
"<span class=\"sd\"> >>> p.act(p.jobs[0][1])</span>\n",
"<span class=\"sd\"> >>> p.goal_test()</span>\n",
"<span class=\"sd\"> False</span>\n",
"<span class=\"sd\"> >>> p.act(p.jobs[0][2])</span>\n",
"<span class=\"sd\"> >>> p.goal_test()</span>\n",
"<span class=\"sd\"> True</span>\n",
"<span class=\"sd\"> >>></span>\n",
"<span class=\"sd\"> """</span>\n",
" <span class=\"n\">resources</span> <span class=\"o\">=</span> <span class=\"p\">{</span><span class=\"s1\">'EngineHoists'</span><span class=\"p\">:</span> <span class=\"mi\">1</span><span class=\"p\">,</span> <span class=\"s1\">'WheelStations'</span><span class=\"p\">:</span> <span class=\"mi\">2</span><span class=\"p\">,</span> <span class=\"s1\">'Inspectors'</span><span class=\"p\">:</span> <span class=\"mi\">2</span><span class=\"p\">,</span> <span class=\"s1\">'LugNuts'</span><span class=\"p\">:</span> <span class=\"mi\">500</span><span class=\"p\">}</span>\n",
" <span class=\"n\">add_engine1</span> <span class=\"o\">=</span> <span class=\"n\">HLA</span><span class=\"p\">(</span><span class=\"s1\">'AddEngine1'</span><span class=\"p\">,</span> <span class=\"n\">precond</span><span class=\"o\">=</span><span class=\"s1\">'~Has(C1, E1)'</span><span class=\"p\">,</span> <span class=\"n\">effect</span><span class=\"o\">=</span><span class=\"s1\">'Has(C1, E1)'</span><span class=\"p\">,</span> <span class=\"n\">duration</span><span class=\"o\">=</span><span class=\"mi\">30</span><span class=\"p\">,</span> <span class=\"n\">use</span><span class=\"o\">=</span><span class=\"p\">{</span><span class=\"s1\">'EngineHoists'</span><span class=\"p\">:</span> <span class=\"mi\">1</span><span class=\"p\">})</span>\n",
" <span class=\"n\">add_engine2</span> <span class=\"o\">=</span> <span class=\"n\">HLA</span><span class=\"p\">(</span><span class=\"s1\">'AddEngine2'</span><span class=\"p\">,</span> <span class=\"n\">precond</span><span class=\"o\">=</span><span class=\"s1\">'~Has(C2, E2)'</span><span class=\"p\">,</span> <span class=\"n\">effect</span><span class=\"o\">=</span><span class=\"s1\">'Has(C2, E2)'</span><span class=\"p\">,</span> <span class=\"n\">duration</span><span class=\"o\">=</span><span class=\"mi\">60</span><span class=\"p\">,</span> <span class=\"n\">use</span><span class=\"o\">=</span><span class=\"p\">{</span><span class=\"s1\">'EngineHoists'</span><span class=\"p\">:</span> <span class=\"mi\">1</span><span class=\"p\">})</span>\n",
" <span class=\"n\">add_wheels1</span> <span class=\"o\">=</span> <span class=\"n\">HLA</span><span class=\"p\">(</span><span class=\"s1\">'AddWheels1'</span><span class=\"p\">,</span> <span class=\"n\">precond</span><span class=\"o\">=</span><span class=\"s1\">'~Has(C1, W1)'</span><span class=\"p\">,</span> <span class=\"n\">effect</span><span class=\"o\">=</span><span class=\"s1\">'Has(C1, W1)'</span><span class=\"p\">,</span> <span class=\"n\">duration</span><span class=\"o\">=</span><span class=\"mi\">30</span><span class=\"p\">,</span> <span class=\"n\">use</span><span class=\"o\">=</span><span class=\"p\">{</span><span class=\"s1\">'WheelStations'</span><span class=\"p\">:</span> <span class=\"mi\">1</span><span class=\"p\">},</span> <span class=\"n\">consume</span><span class=\"o\">=</span><span class=\"p\">{</span><span class=\"s1\">'LugNuts'</span><span class=\"p\">:</span> <span class=\"mi\">20</span><span class=\"p\">})</span>\n",
" <span class=\"n\">add_wheels2</span> <span class=\"o\">=</span> <span class=\"n\">HLA</span><span class=\"p\">(</span><span class=\"s1\">'AddWheels2'</span><span class=\"p\">,</span> <span class=\"n\">precond</span><span class=\"o\">=</span><span class=\"s1\">'~Has(C2, W2)'</span><span class=\"p\">,</span> <span class=\"n\">effect</span><span class=\"o\">=</span><span class=\"s1\">'Has(C2, W2)'</span><span class=\"p\">,</span> <span class=\"n\">duration</span><span class=\"o\">=</span><span class=\"mi\">15</span><span class=\"p\">,</span> <span class=\"n\">use</span><span class=\"o\">=</span><span class=\"p\">{</span><span class=\"s1\">'WheelStations'</span><span class=\"p\">:</span> <span class=\"mi\">1</span><span class=\"p\">},</span> <span class=\"n\">consume</span><span class=\"o\">=</span><span class=\"p\">{</span><span class=\"s1\">'LugNuts'</span><span class=\"p\">:</span> <span class=\"mi\">20</span><span class=\"p\">})</span>\n",
" <span class=\"n\">inspect1</span> <span class=\"o\">=</span> <span class=\"n\">HLA</span><span class=\"p\">(</span><span class=\"s1\">'Inspect1'</span><span class=\"p\">,</span> <span class=\"n\">precond</span><span class=\"o\">=</span><span class=\"s1\">'~Inspected(C1)'</span><span class=\"p\">,</span> <span class=\"n\">effect</span><span class=\"o\">=</span><span class=\"s1\">'Inspected(C1)'</span><span class=\"p\">,</span> <span class=\"n\">duration</span><span class=\"o\">=</span><span class=\"mi\">10</span><span class=\"p\">,</span> <span class=\"n\">use</span><span class=\"o\">=</span><span class=\"p\">{</span><span class=\"s1\">'Inspectors'</span><span class=\"p\">:</span> <span class=\"mi\">1</span><span class=\"p\">})</span>\n",
" <span class=\"n\">inspect2</span> <span class=\"o\">=</span> <span class=\"n\">HLA</span><span class=\"p\">(</span><span class=\"s1\">'Inspect2'</span><span class=\"p\">,</span> <span class=\"n\">precond</span><span class=\"o\">=</span><span class=\"s1\">'~Inspected(C2)'</span><span class=\"p\">,</span> <span class=\"n\">effect</span><span class=\"o\">=</span><span class=\"s1\">'Inspected(C2)'</span><span class=\"p\">,</span> <span class=\"n\">duration</span><span class=\"o\">=</span><span class=\"mi\">10</span><span class=\"p\">,</span> <span class=\"n\">use</span><span class=\"o\">=</span><span class=\"p\">{</span><span class=\"s1\">'Inspectors'</span><span class=\"p\">:</span> <span class=\"mi\">1</span><span class=\"p\">})</span>\n",
" <span class=\"n\">actions</span> <span class=\"o\">=</span> <span class=\"p\">[</span><span class=\"n\">add_engine1</span><span class=\"p\">,</span> <span class=\"n\">add_engine2</span><span class=\"p\">,</span> <span class=\"n\">add_wheels1</span><span class=\"p\">,</span> <span class=\"n\">add_wheels2</span><span class=\"p\">,</span> <span class=\"n\">inspect1</span><span class=\"p\">,</span> <span class=\"n\">inspect2</span><span class=\"p\">]</span>\n",
" <span class=\"n\">job_group1</span> <span class=\"o\">=</span> <span class=\"p\">[</span><span class=\"n\">add_engine1</span><span class=\"p\">,</span> <span class=\"n\">add_wheels1</span><span class=\"p\">,</span> <span class=\"n\">inspect1</span><span class=\"p\">]</span>\n",
" <span class=\"n\">job_group2</span> <span class=\"o\">=</span> <span class=\"p\">[</span><span class=\"n\">add_engine2</span><span class=\"p\">,</span> <span class=\"n\">add_wheels2</span><span class=\"p\">,</span> <span class=\"n\">inspect2</span><span class=\"p\">]</span>\n",
" <span class=\"k\">return</span> <span class=\"n\">Problem</span><span class=\"p\">(</span><span class=\"n\">init</span><span class=\"o\">=</span><span class=\"s1\">'Car(C1) & Car(C2) & Wheels(W1) & Wheels(W2) & Engine(E2) & Engine(E2) & ~Has(C1, E1) & ~Has(C2, E2) & ~Has(C1, W1) & ~Has(C2, W2) & ~Inspected(C1) & ~Inspected(C2)'</span><span class=\"p\">,</span>\n",
" <span class=\"n\">goals</span><span class=\"o\">=</span><span class=\"s1\">'Has(C1, W1) & Has(C1, E1) & Inspected(C1) & Has(C2, W2) & Has(C2, E2) & Inspected(C2)'</span><span class=\"p\">,</span>\n",
" <span class=\"n\">actions</span><span class=\"o\">=</span><span class=\"n\">actions</span><span class=\"p\">,</span>\n",
" <span class=\"n\">jobs</span><span class=\"o\">=</span><span class=\"p\">[</span><span class=\"n\">job_group1</span><span class=\"p\">,</span> <span class=\"n\">job_group2</span><span class=\"p\">],</span>\n",
" <span class=\"n\">resources</span><span class=\"o\">=</span><span class=\"n\">resources</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": [
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Has(x, y)**: Car **'x'** _has_ **'y'** where **'y'** can be an Engine or a Wheel.\n",
"\n",
"**~Has(x, y)**: Car **'x'** does _not have_ **'y'** where **'y'** can be an Engine or a Wheel.\n",
"\n",
"**Inspected(c)**: Car **'c'** has been _inspected_.\n",
"\n",
"**~Inspected(c)**: Car **'c'** has _not_ been inspected.\n",
"\n",
"In the initial state, `C1` and `C2` are cars and neither have an engine or wheels and haven't been inspected.\n",
"`E1` and `E2` are engines.\n",
"`W1` and `W2` are wheels.\n",
"Our goal is to have engines and wheels on both cars and to get them inspected. We will discuss how to achieve this.\n",
"Let's define an object of the `job_shop_problem`."
]
},
{
"cell_type": "code",
"execution_count": 77,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"jobShopProblem = job_shop_problem()"
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
5519
5520
5521
5522
5523
5524
5525
5526
5527
5528
5529
5530
5531
5532
5533
5534
5535
5536
5537
5538
5539
5540
5541
5542
5543
5544
5545
5546
5547
5548
5549
5550
5551
5552
5553
5554
5555
5556
5557
5558
5559
5560
5561
5562
5563
5564
5565
5566
5567
5568
5569
5570
5571
5572
5573
5574
5575
5576
5577
5578
5579
5580
5581
5582
5583
5584
5585
5586
5587
5588
5589
5590
5591
5592
5593
5594
5595
5596
5597
5598
5599
5600
5601
5602
5603
5604
5605
5606
"Before taking any actions, we will check if `jobShopProblem` has reached its goal."
]
},
{
"cell_type": "code",
"execution_count": 78,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"False\n"
]
}
],
"source": [
"print(jobShopProblem.goal_test())"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We now define a possible solution that can help us reach the goal. \n",
"The actions are then carried out on the `jobShopProblem` object."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The following actions are available to us:\n",
"\n",
"**AddEngine1**: Adds an engine to the car C1. Takes 30 minutes to complete and uses an engine hoist.\n",
" \n",
"**AddEngine2**: Adds an engine to the car C2. Takes 60 minutes to complete and uses an engine hoist.\n",
"\n",
"**AddWheels1**: Adds wheels to car C1. Takes 30 minutes to complete. Uses a wheel station and consumes 20 lug nuts.\n",
"\n",
"**AddWheels2**: Adds wheels to car C2. Takes 15 minutes to complete. Uses a wheel station and consumes 20 lug nuts as well.\n",
"\n",
"**Inspect1**: Gets car C1 inspected. Requires 10 minutes of inspection by one inspector.\n",
"\n",
"**Inspect2**: Gets car C2 inspected. Requires 10 minutes of inspection by one inspector."
]
},
{
"cell_type": "code",
"execution_count": 79,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"solution = [jobShopProblem.jobs[1][0],\n",
" jobShopProblem.jobs[1][1],\n",
" jobShopProblem.jobs[1][2],\n",
" jobShopProblem.jobs[0][0],\n",
" jobShopProblem.jobs[0][1],\n",
" jobShopProblem.jobs[0][2]]\n",
"\n",
"for action in solution:\n",
" jobShopProblem.act(action)"
]
},
{
"cell_type": "code",
"execution_count": 80,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"True\n"
]
}
],
"source": [
"print(jobShopProblem.goal_test())"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This is a valid solution and one of many correct ways to solve this problem."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Double tennis problem\n",
"This problem is a simple case of a multiactor planning problem, where two agents act at once and can simultaneously change the current state of the problem. \n",
"A correct plan is one that, if executed by the actors, achieves the goal.\n",
"In the true multiagent setting, of course, the agents may not agree to execute any particular plan, but atleast they will know what plans _would_ work if they _did_ agree to execute them.\n",
"In the double tennis problem, two actors A and B are playing together and can be in one of four locations: `LeftBaseLine`, `RightBaseLine`, `LeftNet` and `RightNet`.\n",
"The ball can be returned only if a player is in the right place.\n",
"Each action must include the actor as an argument.\n",
"<br>\n",
"Let's first look at the definition of the `double_tennis_problem` in the module."
]
},
{
"cell_type": "code",
5628
5629
5630
5631
5632
5633
5634
5635
5636
5637
5638
5639
5640
5641
5642
5643
5644
5645
5646
5647
5648
5649
5650
5651
5652
5653
5654
5655
5656
5657
5658
5659
5660
5661
5662
5663
5664
5665
5666
5667
5668
5669
5670
5671
5672
5673
5674
5675
5676
5677
5678
5679
5680
5681
5682
5683
5684
5685
5686
5687
5688
5689
5690
5691
5692
5693
5694
5695
5696
5697
5698
5699
5700
5701
5702
5703
5704
5705
5706
5707
5708
5709
5710
5711
5712
5713
5714
5715
5716
5717
5718
"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\">double_tennis_problem</span><span class=\"p\">():</span>\n",
" <span class=\"sd\">"""</span>\n",
"<span class=\"sd\"> [Figure 11.10] DOUBLE-TENNIS-PROBLEM</span>\n",
"<span class=\"sd\"> A multiagent planning problem involving two partner tennis players</span>\n",
"<span class=\"sd\"> trying to return an approaching ball and repositioning around in the court.</span>\n",
"<span class=\"sd\"> Example:</span>\n",
"<span class=\"sd\"> >>> from planning import *</span>\n",
"<span class=\"sd\"> >>> dtp = double_tennis_problem()</span>\n",
"<span class=\"sd\"> >>> goal_test(dtp.goals, dtp.init)</span>\n",
"<span class=\"sd\"> False</span>\n",
"<span class=\"sd\"> >>> dtp.act(expr('Go(A, RightBaseLine, LeftBaseLine)'))</span>\n",
"<span class=\"sd\"> >>> dtp.act(expr('Hit(A, Ball, RightBaseLine)'))</span>\n",
"<span class=\"sd\"> >>> goal_test(dtp.goals, dtp.init)</span>\n",
"<span class=\"sd\"> False</span>\n",
"<span class=\"sd\"> >>> dtp.act(expr('Go(A, LeftNet, RightBaseLine)'))</span>\n",
"<span class=\"sd\"> >>> goal_test(dtp.goals, dtp.init)</span>\n",
"<span class=\"sd\"> True</span>\n",
"<span class=\"sd\"> >>></span>\n",
"<span class=\"sd\"> """</span>\n",
" <span class=\"k\">return</span> <span class=\"n\">PlanningProblem</span><span class=\"p\">(</span><span class=\"n\">init</span><span class=\"o\">=</span><span class=\"s1\">'At(A, LeftBaseLine) & At(B, RightNet) & Approaching(Ball, RightBaseLine) & Partner(A, B) & Partner(B, A)'</span><span class=\"p\">,</span>\n",
" <span class=\"n\">goals</span><span class=\"o\">=</span><span class=\"s1\">'Returned(Ball) & At(x, LeftNet) & At(y, RightNet)'</span><span class=\"p\">,</span>\n",
" <span class=\"n\">actions</span><span class=\"o\">=</span><span class=\"p\">[</span><span class=\"n\">Action</span><span class=\"p\">(</span><span class=\"s1\">'Hit(actor, Ball, loc)'</span><span class=\"p\">,</span>\n",
" <span class=\"n\">precond</span><span class=\"o\">=</span><span class=\"s1\">'Approaching(Ball, loc) & At(actor, loc)'</span><span class=\"p\">,</span>\n",
" <span class=\"n\">effect</span><span class=\"o\">=</span><span class=\"s1\">'Returned(Ball)'</span><span class=\"p\">),</span>\n",
" <span class=\"n\">Action</span><span class=\"p\">(</span><span class=\"s1\">'Go(actor, to, loc)'</span><span class=\"p\">,</span> \n",
" <span class=\"n\">precond</span><span class=\"o\">=</span><span class=\"s1\">'At(actor, loc)'</span><span class=\"p\">,</span>\n",
" <span class=\"n\">effect</span><span class=\"o\">=</span><span class=\"s1\">'At(actor, to) & ~At(actor, loc)'</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": [
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The states of this problem are:\n",
"\n",
"**Approaching(Ball, loc)**: The `Ball` is approaching the location `loc`.\n",
"\n",
"**Returned(Ball)**: One of the actors successfully hit the approaching ball from the correct location which caused it to return to the other side.\n",
"\n",
"**At(actor, loc)**: `actor` is at location `loc`.\n",
"\n",
"**~At(actor, loc)**: `actor` is _not_ at location `loc`.\n",
"\n",
"Let's now define an object of `double_tennis_problem`.\n"
]
},
{
"cell_type": "code",
"execution_count": 82,
"metadata": {
"collapsed": true
},
"outputs": [],
"doubleTennisProblem = double_tennis_problem()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Before taking any actions, we will check if `doubleTennisProblem` has reached the goal."
]
},
{
"cell_type": "code",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"False\n"
]
"print(goal_test(doubleTennisProblem.goals, doubleTennisProblem.init))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"As we can see, the goal hasn't been reached. \n",
"We now define a possible solution that can help us reach the goal of having the ball returned.\n",
"The actions will then be carried out on the `doubleTennisProblem` object."
"The actions available to us are the following:\n",
"\n",
"**Hit(actor, ball, loc)**: returns an approaching ball if `actor` is present at the `loc` that the ball is approaching.\n",
"\n",
"**Go(actor, to, loc)**: moves an `actor` from location `loc` to location `to`.\n",
"\n",
"We notice something different in this problem though, \n",
"which is quite unlike any other problem we have seen so far. \n",
"The goal state of the problem contains a variable `a`.\n",
"This happens sometimes in multiagent planning problems \n",
"and it means that it doesn't matter _which_ actor is at the `LeftNet` or the `RightNet`, as long as there is atleast one actor at either `LeftNet` or `RightNet`."
"cell_type": "code",
"execution_count": 84,
"metadata": {
"collapsed": true
},
"outputs": [],
"solution = [expr('Go(A, RightBaseLine, LeftBaseLine)'),\n",
" expr('Hit(A, Ball, RightBaseLine)'),\n",
" expr('Go(A, LeftNet, RightBaseLine)')]\n",
"\n",
"for action in solution:\n",
" doubleTennisProblem.act(action)"
]
},
{
"cell_type": "code",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "execute_result"
"goal_test(doubleTennisProblem.goals, doubleTennisProblem.init)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"It has now successfully reached its goal, ie, to return the approaching ball."
}
],
"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",
}
},
"nbformat": 4,