Newer
Older
3001
3002
3003
3004
3005
3006
3007
3008
3009
3010
3011
3012
3013
3014
3015
3016
3017
3018
3019
3020
3021
3022
3023
3024
3025
3026
3027
3028
3029
3030
3031
3032
3033
3034
3035
3036
3037
"<span class=\"sd\"> """</span>\n",
" <span class=\"n\">hla</span> <span class=\"o\">=</span> <span class=\"bp\">None</span>\n",
" <span class=\"n\">index</span> <span class=\"o\">=</span> <span class=\"nb\">len</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=\"k\">for</span> <span class=\"n\">i</span> <span class=\"ow\">in</span> <span class=\"nb\">range</span><span class=\"p\">(</span><span class=\"nb\">len</span><span class=\"p\">(</span><span class=\"n\">plan</span><span class=\"o\">.</span><span class=\"n\">action</span><span class=\"p\">)):</span> <span class=\"c1\"># find the first HLA in plan, that is not primitive</span>\n",
" <span class=\"k\">if</span> <span class=\"ow\">not</span> <span class=\"n\">Problem</span><span class=\"o\">.</span><span class=\"n\">is_primitive</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=\"p\">[</span><span class=\"n\">plan</span><span class=\"o\">.</span><span class=\"n\">action</span><span class=\"p\">[</span><span class=\"n\">i</span><span class=\"p\">]]),</span> <span class=\"n\">hierarchy</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\">action</span><span class=\"p\">[</span><span class=\"n\">i</span><span class=\"p\">]</span> \n",
" <span class=\"n\">index</span> <span class=\"o\">=</span> <span class=\"n\">i</span>\n",
" <span class=\"k\">break</span>\n",
" <span class=\"k\">return</span> <span class=\"p\">(</span><span class=\"n\">hla</span><span class=\"p\">,</span> <span class=\"n\">index</span><span class=\"p\">)</span>\n",
"\t\n",
" <span class=\"k\">def</span> <span class=\"nf\">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=\"sd\">""" </span>\n",
"<span class=\"sd\"> Not correct</span>\n",
"\n",
"<span class=\"sd\"> Normally should from infinite regression of refinements </span>\n",
"<span class=\"sd\"> </span>\n",
"<span class=\"sd\"> Only case covered: when plan contains one action (then there is no regression to be done) </span>\n",
"<span class=\"sd\"> """</span>\n",
" <span class=\"k\">if</span> <span class=\"p\">(</span><span class=\"nb\">len</span><span class=\"p\">(</span><span class=\"n\">plan</span><span class=\"o\">.</span><span class=\"n\">action</span><span class=\"p\">)</span><span class=\"o\">==</span><span class=\"mi\">1</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\">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=\"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=\"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\">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\">j</span><span class=\"o\">=</span><span class=\"mi\">0</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">x</span> <span class=\"ow\">in</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=\"n\">solution</span><span class=\"o\">.</span><span class=\"n\">insert</span><span class=\"p\">(</span><span class=\"n\">j</span><span class=\"p\">,</span><span class=\"n\">x</span><span class=\"p\">)</span>\n",
" <span class=\"n\">j</span><span class=\"o\">+=</span><span class=\"mi\">1</span>\n",
" <span class=\"n\">s_f</span> <span class=\"o\">=</span> <span class=\"n\">s_i</span>\n",
" <span class=\"k\">return</span> <span class=\"n\">solution</span>\n",
" <span class=\"k\">def</span> <span class=\"nf\">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=\"sd\">"""</span>\n",
"<span class=\"sd\"> Given a final state s_f and an action finds a state s_i in reachable_set </span>\n",
"<span class=\"sd\"> such that when action is applied to state s_i returns s_f. </span>\n",
"<span class=\"sd\"> """</span>\n",
" <span class=\"n\">s_i</span> <span class=\"o\">=</span> <span class=\"n\">reachable_set</span><span class=\"p\">[</span><span class=\"n\">i</span><span class=\"o\">-</span><span class=\"mi\">1</span><span class=\"p\">][</span><span class=\"mi\">0</span><span class=\"p\">]</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">state</span> <span class=\"ow\">in</span> <span class=\"n\">reachable_set</span><span class=\"p\">[</span><span class=\"n\">i</span><span class=\"o\">-</span><span class=\"mi\">1</span><span class=\"p\">]:</span>\n",
" <span class=\"k\">if</span> <span class=\"n\">s_f</span> <span class=\"ow\">in</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\">Problem</span><span class=\"o\">.</span><span class=\"n\">reach_pes</span><span class=\"p\">(</span><span class=\"n\">state</span><span class=\"p\">,</span> <span class=\"n\">Angelic_Node</span><span class=\"p\">(</span><span class=\"n\">state</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><span class=\"mi\">1</span><span class=\"p\">]]:</span>\n",
" <span class=\"n\">s_i</span> <span class=\"o\">=</span><span class=\"n\">state</span>\n",
" <span class=\"k\">break</span>\n",
" <span class=\"k\">return</span> <span class=\"n\">s_i</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",
3078
3079
3080
3081
3082
3083
3084
3085
3086
3087
3088
3089
3090
3091
3092
3093
3094
3095
3096
3097
3098
3099
3100
3101
3102
3103
3104
3105
3106
3107
3108
3109
3110
3111
3112
3113
3114
3115
3116
3117
3118
3119
3120
3121
3122
3123
3124
3125
3126
3127
3128
3129
3130
3131
3132
3133
3134
3135
3136
3137
3138
3139
3140
3141
3142
3143
3144
3145
3146
3147
3148
3149
3150
3151
3152
3153
3154
3155
3156
3157
3158
3159
3160
3161
3162
3163
3164
3165
3166
3167
3168
"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\">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": [
3268
3269
3270
3271
3272
3273
3274
3275
3276
3277
3278
3279
3280
3281
3282
3283
3284
3285
3286
3287
3288
3289
"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",
3297
3298
3299
3300
3301
3302
3303
3304
3305
3306
3307
3308
3309
3310
3311
3312
3313
3314
3315
3316
3317
3318
3319
3320
3321
3322
3323
3324
3325
3326
3327
3328
3329
3330
3331
3332
3333
3334
3335
3336
3337
3338
3339
3340
3341
3342
3343
3344
3345
3346
3347
3348
3349
3350
3351
3352
3353
3354
3355
3356
3357
3358
3359
3360
3361
3362
3363
3364
3365
3366
3367
3368
3369
3370
3371
3372
3373
3374
3375
3376
3377
3378
3379
3380
3381
3382
"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",
"outputs": [],
"source": [
"jobShopProblem = job_shop_problem()"
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Before taking any actions, we will check if `jobShopProblem` has reached its goal."
]
},
{
"cell_type": "code",
3490
3491
3492
3493
3494
3495
3496
3497
3498
3499
3500
3501
3502
3503
3504
3505
3506
3507
3508
3509
3510
3511
3512
3513
3514
3515
3516
3517
3518
3519
3520
3521
3522
3523
3524
3525
3526
3527
3528
3529
3530
3531
3532
"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",
"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",
"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",
3591
3592
3593
3594
3595
3596
3597
3598
3599
3600
3601
3602
3603
3604
3605
3606
3607
3608
3609
3610
3611
3612
3613
3614
3615
3616
3617
3618
3619
3620
3621
3622
3623
3624
3625
3626
3627
3628
3629
3630
3631
3632
3633
3634
3635
3636
3637
3638
3639
3640
3641
3642
3643
3644
3645
3646
3647
3648
3649
3650
3651
3652
3653
3654
3655
3656
3657
3658
3659
3660
3661
3662
3663
3664
3665
3666
3667
3668
3669
3670
3671
3672
3673
3674
3675
3676
3677
3678
3679
3680
3681
"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(a, LeftNet) & At(a, 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",
"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"
]
]
},
{
"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`."
"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"
]
},
{
"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,