Newer
Older
4001
4002
4003
4004
4005
4006
4007
4008
4009
4010
4011
4012
4013
4014
4015
4016
4017
4018
4019
4020
4021
4022
4023
4024
4025
4026
4027
4028
4029
4030
4031
4032
4033
4034
4035
4036
4037
4038
4039
4040
4041
4042
4043
4044
4045
4046
4047
4048
4049
4050
4051
4052
4053
4054
4055
4056
4057
4058
4059
4060
4061
4062
4063
4064
4065
4066
4067
4068
4069
4070
4071
4072
4073
4074
4075
4076
4077
4078
4079
4080
4081
4082
4083
4084
4085
4086
4087
4088
4089
4090
4091
4092
4093
4094
4095
4096
4097
4098
4099
4100
4101
4102
4103
4104
4105
4106
4107
4108
4109
4110
4111
4112
4113
4114
4115
4116
4117
4118
4119
4120
4121
4122
4123
4124
4125
4126
4127
4128
4129
4130
4131
4132
4133
4134
4135
4136
4137
4138
4139
4140
4141
4142
4143
4144
4145
4146
4147
4148
4149
4150
4151
4152
4153
4154
4155
4156
4157
4158
4159
4160
4161
4162
4163
4164
4165
4166
4167
4168
4169
4170
4171
4172
4173
4174
4175
4176
4177
4178
4179
4180
4181
4182
4183
4184
4185
4186
4187
4188
4189
4190
4191
4192
4193
4194
4195
4196
4197
4198
4199
4200
4201
4202
4203
4204
4205
4206
4207
4208
4209
4210
4211
4212
4213
4214
4215
4216
4217
4218
4219
4220
4221
4222
4223
4224
4225
4226
4227
4228
4229
4230
4231
4232
4233
4234
4235
4236
4237
4238
4239
4240
4241
4242
4243
4244
4245
4246
4247
4248
4249
4250
4251
4252
4253
4254
4255
4256
4257
4258
4259
4260
4261
4262
4263
4264
4265
4266
4267
4268
4269
4270
4271
4272
4273
4274
4275
4276
4277
4278
4279
4280
4281
4282
4283
4284
4285
4286
4287
4288
4289
4290
4291
4292
4293
4294
4295
4296
4297
4298
4299
4300
4301
4302
4303
4304
4305
4306
4307
4308
4309
4310
4311
4312
4313
4314
4315
4316
4317
4318
4319
4320
4321
4322
4323
4324
4325
4326
4327
4328
4329
4330
4331
4332
4333
4334
4335
4336
4337
4338
4339
4340
4341
4342
4343
4344
4345
4346
4347
4348
4349
4350
4351
4352
4353
4354
4355
4356
4357
4358
4359
4360
4361
4362
4363
4364
4365
4366
4367
4368
4369
4370
4371
4372
4373
4374
4375
4376
4377
4378
4379
4380
4381
4382
4383
4384
4385
4386
4387
4388
4389
4390
4391
4392
4393
4394
4395
4396
4397
4398
4399
4400
4401
4402
4403
4404
4405
4406
4407
4408
4409
4410
4411
4412
4413
4414
4415
4416
4417
4418
4419
4420
4421
4422
4423
4424
4425
4426
4427
4428
4429
4430
4431
4432
4433
4434
4435
4436
4437
4438
4439
4440
4441
4442
4443
4444
4445
4446
4447
4448
4449
4450
4451
4452
4453
4454
4455
4456
4457
4458
4459
4460
4461
4462
4463
4464
4465
4466
4467
4468
4469
4470
4471
4472
4473
4474
4475
4476
4477
4478
4479
4480
4481
4482
4483
4484
4485
4486
4487
4488
4489
4490
4491
4492
4493
4494
4495
4496
4497
4498
4499
4500
4501
4502
4503
4504
4505
4506
4507
4508
4509
4510
4511
4512
4513
4514
4515
4516
4517
4518
4519
4520
4521
4522
4523
4524
4525
4526
4527
4528
4529
4530
4531
4532
4533
4534
4535
4536
4537
4538
4539
4540
4541
4542
4543
4544
4545
4546
4547
4548
4549
4550
4551
4552
4553
4554
4555
4556
4557
4558
4559
4560
"data": {
"text/plain": [
"[MoveToTable(C, A), Move(B, Table, C), Move(A, Table, B)]"
]
},
"execution_count": 63,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# total-order solution for three_block_tower problem\n",
"Linearize(three_block_tower()).execute()"
]
},
{
"cell_type": "code",
"execution_count": 64,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[ToTable(A, B), FromTable(B, A), FromTable(C, B)]"
]
},
"execution_count": 64,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# total-order solution for simple_blocks_world problem\n",
"Linearize(simple_blocks_world()).execute()"
]
},
{
"cell_type": "code",
"execution_count": 65,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[LeftSock, RightSock, LeftShoe, RightShoe]"
]
},
"execution_count": 65,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# total-order solution for socks_and_shoes problem\n",
"Linearize(socks_and_shoes()).execute()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### PARTIAL ORDER PLANNER\n",
"A partial-order planning algorithm is significantly different from a total-order planner.\n",
"The way a partial-order plan works enables it to take advantage of _problem decomposition_ and work on each subproblem separately.\n",
"It works on several subgoals independently, solves them with several subplans, and then combines the plan.\n",
"<br>\n",
"A partial-order planner also follows the **least commitment** strategy, where it delays making choices for as long as possible.\n",
"Variables are not bound unless it is absolutely necessary and new actions are chosen only if the existing actions cannot fulfil the required precondition.\n",
"<br>\n",
"Any planning algorithm that can place two actions into a plan without specifying which comes first is called a **partial-order planner**.\n",
"A partial-order planner searches through the space of plans rather than the space of states, which makes it perform better for certain problems.\n",
"<br>\n",
"<br>\n",
"Let's have a look at the `PartialOrderPlanner` class."
]
},
{
"cell_type": "code",
"execution_count": 66,
"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\">PartialOrderPlanner</span><span class=\"p\">:</span>\n",
"\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\">pddl</span><span class=\"p\">):</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">pddl</span> <span class=\"o\">=</span> <span class=\"n\">pddl</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">initialize</span><span class=\"p\">()</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"nf\">initialize</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""Initialize all variables"""</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">causal_links</span> <span class=\"o\">=</span> <span class=\"p\">[]</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">start</span> <span class=\"o\">=</span> <span class=\"n\">Action</span><span class=\"p\">(</span><span class=\"s1\">'Start'</span><span class=\"p\">,</span> <span class=\"p\">[],</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">pddl</span><span class=\"o\">.</span><span class=\"n\">init</span><span class=\"p\">)</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">finish</span> <span class=\"o\">=</span> <span class=\"n\">Action</span><span class=\"p\">(</span><span class=\"s1\">'Finish'</span><span class=\"p\">,</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">pddl</span><span class=\"o\">.</span><span class=\"n\">goals</span><span class=\"p\">,</span> <span class=\"p\">[])</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">actions</span> <span class=\"o\">=</span> <span class=\"nb\">set</span><span class=\"p\">()</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">actions</span><span class=\"o\">.</span><span class=\"n\">add</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">start</span><span class=\"p\">)</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">actions</span><span class=\"o\">.</span><span class=\"n\">add</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">finish</span><span class=\"p\">)</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">constraints</span> <span class=\"o\">=</span> <span class=\"nb\">set</span><span class=\"p\">()</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">constraints</span><span class=\"o\">.</span><span class=\"n\">add</span><span class=\"p\">((</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">start</span><span class=\"p\">,</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">finish</span><span class=\"p\">))</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">agenda</span> <span class=\"o\">=</span> <span class=\"nb\">set</span><span class=\"p\">()</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">precond</span> <span class=\"ow\">in</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">finish</span><span class=\"o\">.</span><span class=\"n\">precond</span><span class=\"p\">:</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">agenda</span><span class=\"o\">.</span><span class=\"n\">add</span><span class=\"p\">((</span><span class=\"n\">precond</span><span class=\"p\">,</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">finish</span><span class=\"p\">))</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">expanded_actions</span> <span class=\"o\">=</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">expand_actions</span><span class=\"p\">()</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"nf\">expand_actions</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">name</span><span class=\"o\">=</span><span class=\"bp\">None</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""Generate all possible actions with variable bindings for precondition selection heuristic"""</span>\n",
"\n",
" <span class=\"n\">objects</span> <span class=\"o\">=</span> <span class=\"nb\">set</span><span class=\"p\">(</span><span class=\"n\">arg</span> <span class=\"k\">for</span> <span class=\"n\">clause</span> <span class=\"ow\">in</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">pddl</span><span class=\"o\">.</span><span class=\"n\">init</span> <span class=\"k\">for</span> <span class=\"n\">arg</span> <span class=\"ow\">in</span> <span class=\"n\">clause</span><span class=\"o\">.</span><span class=\"n\">args</span><span class=\"p\">)</span>\n",
" <span class=\"n\">expansions</span> <span class=\"o\">=</span> <span class=\"p\">[]</span>\n",
" <span class=\"n\">action_list</span> <span class=\"o\">=</span> <span class=\"p\">[]</span>\n",
" <span class=\"k\">if</span> <span class=\"n\">name</span> <span class=\"ow\">is</span> <span class=\"ow\">not</span> <span class=\"bp\">None</span><span class=\"p\">:</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">action</span> <span class=\"ow\">in</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">pddl</span><span class=\"o\">.</span><span class=\"n\">actions</span><span class=\"p\">:</span>\n",
" <span class=\"k\">if</span> <span class=\"nb\">str</span><span class=\"p\">(</span><span class=\"n\">action</span><span class=\"o\">.</span><span class=\"n\">name</span><span class=\"p\">)</span> <span class=\"o\">==</span> <span class=\"n\">name</span><span class=\"p\">:</span>\n",
" <span class=\"n\">action_list</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">action</span><span class=\"p\">)</span>\n",
" <span class=\"k\">else</span><span class=\"p\">:</span>\n",
" <span class=\"n\">action_list</span> <span class=\"o\">=</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">pddl</span><span class=\"o\">.</span><span class=\"n\">actions</span>\n",
"\n",
" <span class=\"k\">for</span> <span class=\"n\">action</span> <span class=\"ow\">in</span> <span class=\"n\">action_list</span><span class=\"p\">:</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">permutation</span> <span class=\"ow\">in</span> <span class=\"n\">itertools</span><span class=\"o\">.</span><span class=\"n\">permutations</span><span class=\"p\">(</span><span class=\"n\">objects</span><span class=\"p\">,</span> <span class=\"nb\">len</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=\"n\">bindings</span> <span class=\"o\">=</span> <span class=\"n\">unify</span><span class=\"p\">(</span><span class=\"n\">Expr</span><span class=\"p\">(</span><span class=\"n\">action</span><span class=\"o\">.</span><span class=\"n\">name</span><span class=\"p\">,</span> <span class=\"o\">*</span><span class=\"n\">action</span><span class=\"o\">.</span><span class=\"n\">args</span><span class=\"p\">),</span> <span class=\"n\">Expr</span><span class=\"p\">(</span><span class=\"n\">action</span><span class=\"o\">.</span><span class=\"n\">name</span><span class=\"p\">,</span> <span class=\"o\">*</span><span class=\"n\">permutation</span><span class=\"p\">))</span>\n",
" <span class=\"k\">if</span> <span class=\"n\">bindings</span> <span class=\"ow\">is</span> <span class=\"ow\">not</span> <span class=\"bp\">None</span><span class=\"p\">:</span>\n",
" <span class=\"n\">new_args</span> <span class=\"o\">=</span> <span class=\"p\">[]</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">arg</span> <span class=\"ow\">in</span> <span class=\"n\">action</span><span class=\"o\">.</span><span class=\"n\">args</span><span class=\"p\">:</span>\n",
" <span class=\"k\">if</span> <span class=\"n\">arg</span> <span class=\"ow\">in</span> <span class=\"n\">bindings</span><span class=\"p\">:</span>\n",
" <span class=\"n\">new_args</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">bindings</span><span class=\"p\">[</span><span class=\"n\">arg</span><span class=\"p\">])</span>\n",
" <span class=\"k\">else</span><span class=\"p\">:</span>\n",
" <span class=\"n\">new_args</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">arg</span><span class=\"p\">)</span>\n",
" <span class=\"n\">new_expr</span> <span class=\"o\">=</span> <span class=\"n\">Expr</span><span class=\"p\">(</span><span class=\"nb\">str</span><span class=\"p\">(</span><span class=\"n\">action</span><span class=\"o\">.</span><span class=\"n\">name</span><span class=\"p\">),</span> <span class=\"o\">*</span><span class=\"n\">new_args</span><span class=\"p\">)</span>\n",
" <span class=\"n\">new_preconds</span> <span class=\"o\">=</span> <span class=\"p\">[]</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">precond</span> <span class=\"ow\">in</span> <span class=\"n\">action</span><span class=\"o\">.</span><span class=\"n\">precond</span><span class=\"p\">:</span>\n",
" <span class=\"n\">new_precond_args</span> <span class=\"o\">=</span> <span class=\"p\">[]</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">arg</span> <span class=\"ow\">in</span> <span class=\"n\">precond</span><span class=\"o\">.</span><span class=\"n\">args</span><span class=\"p\">:</span>\n",
" <span class=\"k\">if</span> <span class=\"n\">arg</span> <span class=\"ow\">in</span> <span class=\"n\">bindings</span><span class=\"p\">:</span>\n",
" <span class=\"n\">new_precond_args</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">bindings</span><span class=\"p\">[</span><span class=\"n\">arg</span><span class=\"p\">])</span>\n",
" <span class=\"k\">else</span><span class=\"p\">:</span>\n",
" <span class=\"n\">new_precond_args</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">arg</span><span class=\"p\">)</span>\n",
" <span class=\"n\">new_precond</span> <span class=\"o\">=</span> <span class=\"n\">Expr</span><span class=\"p\">(</span><span class=\"nb\">str</span><span class=\"p\">(</span><span class=\"n\">precond</span><span class=\"o\">.</span><span class=\"n\">op</span><span class=\"p\">),</span> <span class=\"o\">*</span><span class=\"n\">new_precond_args</span><span class=\"p\">)</span>\n",
" <span class=\"n\">new_preconds</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">new_precond</span><span class=\"p\">)</span>\n",
" <span class=\"n\">new_effects</span> <span class=\"o\">=</span> <span class=\"p\">[]</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">effect</span> <span class=\"ow\">in</span> <span class=\"n\">action</span><span class=\"o\">.</span><span class=\"n\">effect</span><span class=\"p\">:</span>\n",
" <span class=\"n\">new_effect_args</span> <span class=\"o\">=</span> <span class=\"p\">[]</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">arg</span> <span class=\"ow\">in</span> <span class=\"n\">effect</span><span class=\"o\">.</span><span class=\"n\">args</span><span class=\"p\">:</span>\n",
" <span class=\"k\">if</span> <span class=\"n\">arg</span> <span class=\"ow\">in</span> <span class=\"n\">bindings</span><span class=\"p\">:</span>\n",
" <span class=\"n\">new_effect_args</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">bindings</span><span class=\"p\">[</span><span class=\"n\">arg</span><span class=\"p\">])</span>\n",
" <span class=\"k\">else</span><span class=\"p\">:</span>\n",
" <span class=\"n\">new_effect_args</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">arg</span><span class=\"p\">)</span>\n",
" <span class=\"n\">new_effect</span> <span class=\"o\">=</span> <span class=\"n\">Expr</span><span class=\"p\">(</span><span class=\"nb\">str</span><span class=\"p\">(</span><span class=\"n\">effect</span><span class=\"o\">.</span><span class=\"n\">op</span><span class=\"p\">),</span> <span class=\"o\">*</span><span class=\"n\">new_effect_args</span><span class=\"p\">)</span>\n",
" <span class=\"n\">new_effects</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">new_effect</span><span class=\"p\">)</span>\n",
" <span class=\"n\">expansions</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">Action</span><span class=\"p\">(</span><span class=\"n\">new_expr</span><span class=\"p\">,</span> <span class=\"n\">new_preconds</span><span class=\"p\">,</span> <span class=\"n\">new_effects</span><span class=\"p\">))</span>\n",
"\n",
" <span class=\"k\">return</span> <span class=\"n\">expansions</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"nf\">find_open_precondition</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""Find open precondition with the least number of possible actions"""</span>\n",
"\n",
" <span class=\"n\">number_of_ways</span> <span class=\"o\">=</span> <span class=\"nb\">dict</span><span class=\"p\">()</span>\n",
" <span class=\"n\">actions_for_precondition</span> <span class=\"o\">=</span> <span class=\"nb\">dict</span><span class=\"p\">()</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">element</span> <span class=\"ow\">in</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">agenda</span><span class=\"p\">:</span>\n",
" <span class=\"n\">open_precondition</span> <span class=\"o\">=</span> <span class=\"n\">element</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">]</span>\n",
" <span class=\"n\">possible_actions</span> <span class=\"o\">=</span> <span class=\"nb\">list</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">actions</span><span class=\"p\">)</span> <span class=\"o\">+</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">expanded_actions</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">action</span> <span class=\"ow\">in</span> <span class=\"n\">possible_actions</span><span class=\"p\">:</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">effect</span> <span class=\"ow\">in</span> <span class=\"n\">action</span><span class=\"o\">.</span><span class=\"n\">effect</span><span class=\"p\">:</span>\n",
" <span class=\"k\">if</span> <span class=\"n\">effect</span> <span class=\"o\">==</span> <span class=\"n\">open_precondition</span><span class=\"p\">:</span>\n",
" <span class=\"k\">if</span> <span class=\"n\">open_precondition</span> <span class=\"ow\">in</span> <span class=\"n\">number_of_ways</span><span class=\"p\">:</span>\n",
" <span class=\"n\">number_of_ways</span><span class=\"p\">[</span><span class=\"n\">open_precondition</span><span class=\"p\">]</span> <span class=\"o\">+=</span> <span class=\"mi\">1</span>\n",
" <span class=\"n\">actions_for_precondition</span><span class=\"p\">[</span><span class=\"n\">open_precondition</span><span class=\"p\">]</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">action</span><span class=\"p\">)</span>\n",
" <span class=\"k\">else</span><span class=\"p\">:</span>\n",
" <span class=\"n\">number_of_ways</span><span class=\"p\">[</span><span class=\"n\">open_precondition</span><span class=\"p\">]</span> <span class=\"o\">=</span> <span class=\"mi\">1</span>\n",
" <span class=\"n\">actions_for_precondition</span><span class=\"p\">[</span><span class=\"n\">open_precondition</span><span class=\"p\">]</span> <span class=\"o\">=</span> <span class=\"p\">[</span><span class=\"n\">action</span><span class=\"p\">]</span>\n",
"\n",
" <span class=\"n\">number</span> <span class=\"o\">=</span> <span class=\"nb\">sorted</span><span class=\"p\">(</span><span class=\"n\">number_of_ways</span><span class=\"p\">,</span> <span class=\"n\">key</span><span class=\"o\">=</span><span class=\"n\">number_of_ways</span><span class=\"o\">.</span><span class=\"fm\">__getitem__</span><span class=\"p\">)</span>\n",
" \n",
" <span class=\"k\">for</span> <span class=\"n\">k</span><span class=\"p\">,</span> <span class=\"n\">v</span> <span class=\"ow\">in</span> <span class=\"n\">number_of_ways</span><span class=\"o\">.</span><span class=\"n\">items</span><span class=\"p\">():</span>\n",
" <span class=\"k\">if</span> <span class=\"n\">v</span> <span class=\"o\">==</span> <span class=\"mi\">0</span><span class=\"p\">:</span>\n",
" <span class=\"k\">return</span> <span class=\"bp\">None</span><span class=\"p\">,</span> <span class=\"bp\">None</span><span class=\"p\">,</span> <span class=\"bp\">None</span>\n",
"\n",
" <span class=\"n\">act1</span> <span class=\"o\">=</span> <span class=\"bp\">None</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">element</span> <span class=\"ow\">in</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">agenda</span><span class=\"p\">:</span>\n",
" <span class=\"k\">if</span> <span class=\"n\">element</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">]</span> <span class=\"o\">==</span> <span class=\"n\">number</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">]:</span>\n",
" <span class=\"n\">act1</span> <span class=\"o\">=</span> <span class=\"n\">element</span><span class=\"p\">[</span><span class=\"mi\">1</span><span class=\"p\">]</span>\n",
" <span class=\"k\">break</span>\n",
"\n",
" <span class=\"k\">if</span> <span class=\"n\">number</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">]</span> <span class=\"ow\">in</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">expanded_actions</span><span class=\"p\">:</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">expanded_actions</span><span class=\"o\">.</span><span class=\"n\">remove</span><span class=\"p\">(</span><span class=\"n\">number</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">])</span>\n",
"\n",
" <span class=\"k\">return</span> <span class=\"n\">number</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">],</span> <span class=\"n\">act1</span><span class=\"p\">,</span> <span class=\"n\">actions_for_precondition</span><span class=\"p\">[</span><span class=\"n\">number</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">]]</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"nf\">find_action_for_precondition</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">oprec</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""Find action for a given precondition"""</span>\n",
"\n",
" <span class=\"c1\"># either</span>\n",
" <span class=\"c1\"># choose act0 E Actions such that act0 achieves G</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">action</span> <span class=\"ow\">in</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">actions</span><span class=\"p\">:</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">effect</span> <span class=\"ow\">in</span> <span class=\"n\">action</span><span class=\"o\">.</span><span class=\"n\">effect</span><span class=\"p\">:</span>\n",
" <span class=\"k\">if</span> <span class=\"n\">effect</span> <span class=\"o\">==</span> <span class=\"n\">oprec</span><span class=\"p\">:</span>\n",
" <span class=\"k\">return</span> <span class=\"n\">action</span><span class=\"p\">,</span> <span class=\"mi\">0</span>\n",
"\n",
" <span class=\"c1\"># or</span>\n",
" <span class=\"c1\"># choose act0 E Actions such that act0 achieves G</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">action</span> <span class=\"ow\">in</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">pddl</span><span class=\"o\">.</span><span class=\"n\">actions</span><span class=\"p\">:</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">effect</span> <span class=\"ow\">in</span> <span class=\"n\">action</span><span class=\"o\">.</span><span class=\"n\">effect</span><span class=\"p\">:</span>\n",
" <span class=\"k\">if</span> <span class=\"n\">effect</span><span class=\"o\">.</span><span class=\"n\">op</span> <span class=\"o\">==</span> <span class=\"n\">oprec</span><span class=\"o\">.</span><span class=\"n\">op</span><span class=\"p\">:</span>\n",
" <span class=\"n\">bindings</span> <span class=\"o\">=</span> <span class=\"n\">unify</span><span class=\"p\">(</span><span class=\"n\">effect</span><span class=\"p\">,</span> <span class=\"n\">oprec</span><span class=\"p\">)</span>\n",
" <span class=\"k\">if</span> <span class=\"n\">bindings</span> <span class=\"ow\">is</span> <span class=\"bp\">None</span><span class=\"p\">:</span>\n",
" <span class=\"k\">break</span>\n",
" <span class=\"k\">return</span> <span class=\"n\">action</span><span class=\"p\">,</span> <span class=\"n\">bindings</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"nf\">generate_expr</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">clause</span><span class=\"p\">,</span> <span class=\"n\">bindings</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""Generate atomic expression from generic expression given variable bindings"""</span>\n",
"\n",
" <span class=\"n\">new_args</span> <span class=\"o\">=</span> <span class=\"p\">[]</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">arg</span> <span class=\"ow\">in</span> <span class=\"n\">clause</span><span class=\"o\">.</span><span class=\"n\">args</span><span class=\"p\">:</span>\n",
" <span class=\"k\">if</span> <span class=\"n\">arg</span> <span class=\"ow\">in</span> <span class=\"n\">bindings</span><span class=\"p\">:</span>\n",
" <span class=\"n\">new_args</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">bindings</span><span class=\"p\">[</span><span class=\"n\">arg</span><span class=\"p\">])</span>\n",
" <span class=\"k\">else</span><span class=\"p\">:</span>\n",
" <span class=\"n\">new_args</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">arg</span><span class=\"p\">)</span>\n",
"\n",
" <span class=\"k\">try</span><span class=\"p\">:</span>\n",
" <span class=\"k\">return</span> <span class=\"n\">Expr</span><span class=\"p\">(</span><span class=\"nb\">str</span><span class=\"p\">(</span><span class=\"n\">clause</span><span class=\"o\">.</span><span class=\"n\">name</span><span class=\"p\">),</span> <span class=\"o\">*</span><span class=\"n\">new_args</span><span class=\"p\">)</span>\n",
" <span class=\"k\">except</span><span class=\"p\">:</span>\n",
" <span class=\"k\">return</span> <span class=\"n\">Expr</span><span class=\"p\">(</span><span class=\"nb\">str</span><span class=\"p\">(</span><span class=\"n\">clause</span><span class=\"o\">.</span><span class=\"n\">op</span><span class=\"p\">),</span> <span class=\"o\">*</span><span class=\"n\">new_args</span><span class=\"p\">)</span>\n",
" \n",
" <span class=\"k\">def</span> <span class=\"nf\">generate_action_object</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\">bindings</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""Generate action object given a generic action andvariable bindings"""</span>\n",
"\n",
" <span class=\"c1\"># if bindings is 0, it means the action already exists in self.actions</span>\n",
" <span class=\"k\">if</span> <span class=\"n\">bindings</span> <span class=\"o\">==</span> <span class=\"mi\">0</span><span class=\"p\">:</span>\n",
" <span class=\"k\">return</span> <span class=\"n\">action</span>\n",
"\n",
" <span class=\"c1\"># bindings cannot be None</span>\n",
" <span class=\"k\">else</span><span class=\"p\">:</span>\n",
" <span class=\"n\">new_expr</span> <span class=\"o\">=</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">generate_expr</span><span class=\"p\">(</span><span class=\"n\">action</span><span class=\"p\">,</span> <span class=\"n\">bindings</span><span class=\"p\">)</span>\n",
" <span class=\"n\">new_preconds</span> <span class=\"o\">=</span> <span class=\"p\">[]</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">precond</span> <span class=\"ow\">in</span> <span class=\"n\">action</span><span class=\"o\">.</span><span class=\"n\">precond</span><span class=\"p\">:</span>\n",
" <span class=\"n\">new_precond</span> <span class=\"o\">=</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">generate_expr</span><span class=\"p\">(</span><span class=\"n\">precond</span><span class=\"p\">,</span> <span class=\"n\">bindings</span><span class=\"p\">)</span>\n",
" <span class=\"n\">new_preconds</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">new_precond</span><span class=\"p\">)</span>\n",
" <span class=\"n\">new_effects</span> <span class=\"o\">=</span> <span class=\"p\">[]</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">effect</span> <span class=\"ow\">in</span> <span class=\"n\">action</span><span class=\"o\">.</span><span class=\"n\">effect</span><span class=\"p\">:</span>\n",
" <span class=\"n\">new_effect</span> <span class=\"o\">=</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">generate_expr</span><span class=\"p\">(</span><span class=\"n\">effect</span><span class=\"p\">,</span> <span class=\"n\">bindings</span><span class=\"p\">)</span>\n",
" <span class=\"n\">new_effects</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">new_effect</span><span class=\"p\">)</span>\n",
" <span class=\"k\">return</span> <span class=\"n\">Action</span><span class=\"p\">(</span><span class=\"n\">new_expr</span><span class=\"p\">,</span> <span class=\"n\">new_preconds</span><span class=\"p\">,</span> <span class=\"n\">new_effects</span><span class=\"p\">)</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"nf\">cyclic</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">graph</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""Check cyclicity of a directed graph"""</span>\n",
"\n",
" <span class=\"n\">new_graph</span> <span class=\"o\">=</span> <span class=\"nb\">dict</span><span class=\"p\">()</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">element</span> <span class=\"ow\">in</span> <span class=\"n\">graph</span><span class=\"p\">:</span>\n",
" <span class=\"k\">if</span> <span class=\"n\">element</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">]</span> <span class=\"ow\">in</span> <span class=\"n\">new_graph</span><span class=\"p\">:</span>\n",
" <span class=\"n\">new_graph</span><span class=\"p\">[</span><span class=\"n\">element</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">]]</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">(</span><span class=\"n\">element</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\">new_graph</span><span class=\"p\">[</span><span class=\"n\">element</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">]]</span> <span class=\"o\">=</span> <span class=\"p\">[</span><span class=\"n\">element</span><span class=\"p\">[</span><span class=\"mi\">1</span><span class=\"p\">]]</span>\n",
"\n",
" <span class=\"n\">path</span> <span class=\"o\">=</span> <span class=\"nb\">set</span><span class=\"p\">()</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"nf\">visit</span><span class=\"p\">(</span><span class=\"n\">vertex</span><span class=\"p\">):</span>\n",
" <span class=\"n\">path</span><span class=\"o\">.</span><span class=\"n\">add</span><span class=\"p\">(</span><span class=\"n\">vertex</span><span class=\"p\">)</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">neighbor</span> <span class=\"ow\">in</span> <span class=\"n\">new_graph</span><span class=\"o\">.</span><span class=\"n\">get</span><span class=\"p\">(</span><span class=\"n\">vertex</span><span class=\"p\">,</span> <span class=\"p\">()):</span>\n",
" <span class=\"k\">if</span> <span class=\"n\">neighbor</span> <span class=\"ow\">in</span> <span class=\"n\">path</span> <span class=\"ow\">or</span> <span class=\"n\">visit</span><span class=\"p\">(</span><span class=\"n\">neighbor</span><span class=\"p\">):</span>\n",
" <span class=\"k\">return</span> <span class=\"bp\">True</span>\n",
" <span class=\"n\">path</span><span class=\"o\">.</span><span class=\"n\">remove</span><span class=\"p\">(</span><span class=\"n\">vertex</span><span class=\"p\">)</span>\n",
" <span class=\"k\">return</span> <span class=\"bp\">False</span>\n",
"\n",
" <span class=\"n\">value</span> <span class=\"o\">=</span> <span class=\"nb\">any</span><span class=\"p\">(</span><span class=\"n\">visit</span><span class=\"p\">(</span><span class=\"n\">v</span><span class=\"p\">)</span> <span class=\"k\">for</span> <span class=\"n\">v</span> <span class=\"ow\">in</span> <span class=\"n\">new_graph</span><span class=\"p\">)</span>\n",
" <span class=\"k\">return</span> <span class=\"n\">value</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"nf\">add_const</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">constraint</span><span class=\"p\">,</span> <span class=\"n\">constraints</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""Add the constraint to constraints if the resulting graph is acyclic"""</span>\n",
"\n",
" <span class=\"k\">if</span> <span class=\"n\">constraint</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">]</span> <span class=\"o\">==</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">finish</span> <span class=\"ow\">or</span> <span class=\"n\">constraint</span><span class=\"p\">[</span><span class=\"mi\">1</span><span class=\"p\">]</span> <span class=\"o\">==</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">start</span><span class=\"p\">:</span>\n",
" <span class=\"k\">return</span> <span class=\"n\">constraints</span>\n",
"\n",
" <span class=\"n\">new_constraints</span> <span class=\"o\">=</span> <span class=\"nb\">set</span><span class=\"p\">(</span><span class=\"n\">constraints</span><span class=\"p\">)</span>\n",
" <span class=\"n\">new_constraints</span><span class=\"o\">.</span><span class=\"n\">add</span><span class=\"p\">(</span><span class=\"n\">constraint</span><span class=\"p\">)</span>\n",
"\n",
" <span class=\"k\">if</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">cyclic</span><span class=\"p\">(</span><span class=\"n\">new_constraints</span><span class=\"p\">):</span>\n",
" <span class=\"k\">return</span> <span class=\"n\">constraints</span>\n",
" <span class=\"k\">return</span> <span class=\"n\">new_constraints</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"nf\">is_a_threat</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">precondition</span><span class=\"p\">,</span> <span class=\"n\">effect</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""Check if effect is a threat to precondition"""</span>\n",
"\n",
" <span class=\"k\">if</span> <span class=\"p\">(</span><span class=\"nb\">str</span><span class=\"p\">(</span><span class=\"n\">effect</span><span class=\"o\">.</span><span class=\"n\">op</span><span class=\"p\">)</span> <span class=\"o\">==</span> <span class=\"s1\">'Not'</span> <span class=\"o\">+</span> <span class=\"nb\">str</span><span class=\"p\">(</span><span class=\"n\">precondition</span><span class=\"o\">.</span><span class=\"n\">op</span><span class=\"p\">))</span> <span class=\"ow\">or</span> <span class=\"p\">(</span><span class=\"s1\">'Not'</span> <span class=\"o\">+</span> <span class=\"nb\">str</span><span class=\"p\">(</span><span class=\"n\">effect</span><span class=\"o\">.</span><span class=\"n\">op</span><span class=\"p\">)</span> <span class=\"o\">==</span> <span class=\"nb\">str</span><span class=\"p\">(</span><span class=\"n\">precondition</span><span class=\"o\">.</span><span class=\"n\">op</span><span class=\"p\">)):</span>\n",
" <span class=\"k\">if</span> <span class=\"n\">effect</span><span class=\"o\">.</span><span class=\"n\">args</span> <span class=\"o\">==</span> <span class=\"n\">precondition</span><span class=\"o\">.</span><span class=\"n\">args</span><span class=\"p\">:</span>\n",
" <span class=\"k\">return</span> <span class=\"bp\">True</span>\n",
" <span class=\"k\">return</span> <span class=\"bp\">False</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"nf\">protect</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">causal_link</span><span class=\"p\">,</span> <span class=\"n\">action</span><span class=\"p\">,</span> <span class=\"n\">constraints</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""Check and resolve threats by promotion or demotion"""</span>\n",
"\n",
" <span class=\"n\">threat</span> <span class=\"o\">=</span> <span class=\"bp\">False</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">effect</span> <span class=\"ow\">in</span> <span class=\"n\">action</span><span class=\"o\">.</span><span class=\"n\">effect</span><span class=\"p\">:</span>\n",
" <span class=\"k\">if</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">is_a_threat</span><span class=\"p\">(</span><span class=\"n\">causal_link</span><span class=\"p\">[</span><span class=\"mi\">1</span><span class=\"p\">],</span> <span class=\"n\">effect</span><span class=\"p\">):</span>\n",
" <span class=\"n\">threat</span> <span class=\"o\">=</span> <span class=\"bp\">True</span>\n",
" <span class=\"k\">break</span>\n",
"\n",
" <span class=\"k\">if</span> <span class=\"n\">action</span> <span class=\"o\">!=</span> <span class=\"n\">causal_link</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">]</span> <span class=\"ow\">and</span> <span class=\"n\">action</span> <span class=\"o\">!=</span> <span class=\"n\">causal_link</span><span class=\"p\">[</span><span class=\"mi\">2</span><span class=\"p\">]</span> <span class=\"ow\">and</span> <span class=\"n\">threat</span><span class=\"p\">:</span>\n",
" <span class=\"c1\"># try promotion</span>\n",
" <span class=\"n\">new_constraints</span> <span class=\"o\">=</span> <span class=\"nb\">set</span><span class=\"p\">(</span><span class=\"n\">constraints</span><span class=\"p\">)</span>\n",
" <span class=\"n\">new_constraints</span><span class=\"o\">.</span><span class=\"n\">add</span><span class=\"p\">((</span><span class=\"n\">action</span><span class=\"p\">,</span> <span class=\"n\">causal_link</span><span class=\"p\">[</span><span class=\"mi\">0</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\">cyclic</span><span class=\"p\">(</span><span class=\"n\">new_constraints</span><span class=\"p\">):</span>\n",
" <span class=\"n\">constraints</span> <span class=\"o\">=</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">add_const</span><span class=\"p\">((</span><span class=\"n\">action</span><span class=\"p\">,</span> <span class=\"n\">causal_link</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">]),</span> <span class=\"n\">constraints</span><span class=\"p\">)</span>\n",
" <span class=\"k\">else</span><span class=\"p\">:</span>\n",
" <span class=\"c1\"># try demotion</span>\n",
" <span class=\"n\">new_constraints</span> <span class=\"o\">=</span> <span class=\"nb\">set</span><span class=\"p\">(</span><span class=\"n\">constraints</span><span class=\"p\">)</span>\n",
" <span class=\"n\">new_constraints</span><span class=\"o\">.</span><span class=\"n\">add</span><span class=\"p\">((</span><span class=\"n\">causal_link</span><span class=\"p\">[</span><span class=\"mi\">2</span><span class=\"p\">],</span> <span class=\"n\">action</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\">cyclic</span><span class=\"p\">(</span><span class=\"n\">new_constraints</span><span class=\"p\">):</span>\n",
" <span class=\"n\">constraints</span> <span class=\"o\">=</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">add_const</span><span class=\"p\">((</span><span class=\"n\">causal_link</span><span class=\"p\">[</span><span class=\"mi\">2</span><span class=\"p\">],</span> <span class=\"n\">action</span><span class=\"p\">),</span> <span class=\"n\">constraints</span><span class=\"p\">)</span>\n",
" <span class=\"k\">else</span><span class=\"p\">:</span>\n",
" <span class=\"c1\"># both promotion and demotion fail</span>\n",
" <span class=\"k\">print</span><span class=\"p\">(</span><span class=\"s1\">'Unable to resolve a threat caused by'</span><span class=\"p\">,</span> <span class=\"n\">action</span><span class=\"p\">,</span> <span class=\"s1\">'onto'</span><span class=\"p\">,</span> <span class=\"n\">causal_link</span><span class=\"p\">)</span>\n",
" <span class=\"k\">return</span>\n",
" <span class=\"k\">return</span> <span class=\"n\">constraints</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"nf\">convert</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">constraints</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""Convert constraints into a dict of Action to set orderings"""</span>\n",
"\n",
" <span class=\"n\">graph</span> <span class=\"o\">=</span> <span class=\"nb\">dict</span><span class=\"p\">()</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">constraint</span> <span class=\"ow\">in</span> <span class=\"n\">constraints</span><span class=\"p\">:</span>\n",
" <span class=\"k\">if</span> <span class=\"n\">constraint</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">]</span> <span class=\"ow\">in</span> <span class=\"n\">graph</span><span class=\"p\">:</span>\n",
" <span class=\"n\">graph</span><span class=\"p\">[</span><span class=\"n\">constraint</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">]]</span><span class=\"o\">.</span><span class=\"n\">add</span><span class=\"p\">(</span><span class=\"n\">constraint</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\">graph</span><span class=\"p\">[</span><span class=\"n\">constraint</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">]]</span> <span class=\"o\">=</span> <span class=\"nb\">set</span><span class=\"p\">()</span>\n",
" <span class=\"n\">graph</span><span class=\"p\">[</span><span class=\"n\">constraint</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">]]</span><span class=\"o\">.</span><span class=\"n\">add</span><span class=\"p\">(</span><span class=\"n\">constraint</span><span class=\"p\">[</span><span class=\"mi\">1</span><span class=\"p\">])</span>\n",
" <span class=\"k\">return</span> <span class=\"n\">graph</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"nf\">toposort</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">graph</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""Generate topological ordering of constraints"""</span>\n",
"\n",
" <span class=\"k\">if</span> <span class=\"nb\">len</span><span class=\"p\">(</span><span class=\"n\">graph</span><span class=\"p\">)</span> <span class=\"o\">==</span> <span class=\"mi\">0</span><span class=\"p\">:</span>\n",
" <span class=\"k\">return</span>\n",
"\n",
" <span class=\"n\">graph</span> <span class=\"o\">=</span> <span class=\"n\">graph</span><span class=\"o\">.</span><span class=\"n\">copy</span><span class=\"p\">()</span>\n",
"\n",
" <span class=\"k\">for</span> <span class=\"n\">k</span><span class=\"p\">,</span> <span class=\"n\">v</span> <span class=\"ow\">in</span> <span class=\"n\">graph</span><span class=\"o\">.</span><span class=\"n\">items</span><span class=\"p\">():</span>\n",
" <span class=\"n\">v</span><span class=\"o\">.</span><span class=\"n\">discard</span><span class=\"p\">(</span><span class=\"n\">k</span><span class=\"p\">)</span>\n",
"\n",
" <span class=\"n\">extra_elements_in_dependencies</span> <span class=\"o\">=</span> <span class=\"n\">_reduce</span><span class=\"p\">(</span><span class=\"nb\">set</span><span class=\"o\">.</span><span class=\"n\">union</span><span class=\"p\">,</span> <span class=\"n\">graph</span><span class=\"o\">.</span><span class=\"n\">values</span><span class=\"p\">())</span> <span class=\"o\">-</span> <span class=\"nb\">set</span><span class=\"p\">(</span><span class=\"n\">graph</span><span class=\"o\">.</span><span class=\"n\">keys</span><span class=\"p\">())</span>\n",
"\n",
" <span class=\"n\">graph</span><span class=\"o\">.</span><span class=\"n\">update</span><span class=\"p\">({</span><span class=\"n\">element</span><span class=\"p\">:</span><span class=\"nb\">set</span><span class=\"p\">()</span> <span class=\"k\">for</span> <span class=\"n\">element</span> <span class=\"ow\">in</span> <span class=\"n\">extra_elements_in_dependencies</span><span class=\"p\">})</span>\n",
" <span class=\"k\">while</span> <span class=\"bp\">True</span><span class=\"p\">:</span>\n",
" <span class=\"n\">ordered</span> <span class=\"o\">=</span> <span class=\"nb\">set</span><span class=\"p\">(</span><span class=\"n\">element</span> <span class=\"k\">for</span> <span class=\"n\">element</span><span class=\"p\">,</span> <span class=\"n\">dependency</span> <span class=\"ow\">in</span> <span class=\"n\">graph</span><span class=\"o\">.</span><span class=\"n\">items</span><span class=\"p\">()</span> <span class=\"k\">if</span> <span class=\"nb\">len</span><span class=\"p\">(</span><span class=\"n\">dependency</span><span class=\"p\">)</span> <span class=\"o\">==</span> <span class=\"mi\">0</span><span class=\"p\">)</span>\n",
" <span class=\"k\">if</span> <span class=\"ow\">not</span> <span class=\"n\">ordered</span><span class=\"p\">:</span>\n",
" <span class=\"k\">break</span>\n",
" <span class=\"k\">yield</span> <span class=\"n\">ordered</span>\n",
" <span class=\"n\">graph</span> <span class=\"o\">=</span> <span class=\"p\">{</span><span class=\"n\">element</span><span class=\"p\">:</span> <span class=\"p\">(</span><span class=\"n\">dependency</span> <span class=\"o\">-</span> <span class=\"n\">ordered</span><span class=\"p\">)</span> <span class=\"k\">for</span> <span class=\"n\">element</span><span class=\"p\">,</span> <span class=\"n\">dependency</span> <span class=\"ow\">in</span> <span class=\"n\">graph</span><span class=\"o\">.</span><span class=\"n\">items</span><span class=\"p\">()</span> <span class=\"k\">if</span> <span class=\"n\">element</span> <span class=\"ow\">not</span> <span class=\"ow\">in</span> <span class=\"n\">ordered</span><span class=\"p\">}</span>\n",
" <span class=\"k\">if</span> <span class=\"nb\">len</span><span class=\"p\">(</span><span class=\"n\">graph</span><span class=\"p\">)</span> <span class=\"o\">!=</span> <span class=\"mi\">0</span><span class=\"p\">:</span>\n",
" <span class=\"k\">raise</span> <span class=\"ne\">ValueError</span><span class=\"p\">(</span><span class=\"s1\">'The graph is not acyclic and cannot be linearly ordered'</span><span class=\"p\">)</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"nf\">display_plan</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""Display causal links, constraints and the plan"""</span>\n",
"\n",
" <span class=\"k\">print</span><span class=\"p\">(</span><span class=\"s1\">'Causal Links'</span><span class=\"p\">)</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">causal_link</span> <span class=\"ow\">in</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">causal_links</span><span class=\"p\">:</span>\n",
" <span class=\"k\">print</span><span class=\"p\">(</span><span class=\"n\">causal_link</span><span class=\"p\">)</span>\n",
"\n",
" <span class=\"k\">print</span><span class=\"p\">(</span><span class=\"s1\">'</span><span class=\"se\">\\n</span><span class=\"s1\">Constraints'</span><span class=\"p\">)</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">constraint</span> <span class=\"ow\">in</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">constraints</span><span class=\"p\">:</span>\n",
" <span class=\"k\">print</span><span class=\"p\">(</span><span class=\"n\">constraint</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">],</span> <span class=\"s1\">'<'</span><span class=\"p\">,</span> <span class=\"n\">constraint</span><span class=\"p\">[</span><span class=\"mi\">1</span><span class=\"p\">])</span>\n",
"\n",
" <span class=\"k\">print</span><span class=\"p\">(</span><span class=\"s1\">'</span><span class=\"se\">\\n</span><span class=\"s1\">Partial Order Plan'</span><span class=\"p\">)</span>\n",
" <span class=\"k\">print</span><span class=\"p\">(</span><span class=\"nb\">list</span><span class=\"p\">(</span><span class=\"nb\">reversed</span><span class=\"p\">(</span><span class=\"nb\">list</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">toposort</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">convert</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">constraints</span><span class=\"p\">))))))</span>\n",
"\n",
" <span class=\"k\">def</span> <span class=\"nf\">execute</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"p\">,</span> <span class=\"n\">display</span><span class=\"o\">=</span><span class=\"bp\">True</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""Execute the algorithm"""</span>\n",
"\n",
" <span class=\"n\">step</span> <span class=\"o\">=</span> <span class=\"mi\">1</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">tries</span> <span class=\"o\">=</span> <span class=\"mi\">1</span>\n",
" <span class=\"k\">while</span> <span class=\"nb\">len</span><span class=\"p\">(</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">agenda</span><span class=\"p\">)</span> <span class=\"o\">></span> <span class=\"mi\">0</span><span class=\"p\">:</span>\n",
" <span class=\"n\">step</span> <span class=\"o\">+=</span> <span class=\"mi\">1</span>\n",
" <span class=\"c1\"># select <G, act1> from Agenda</span>\n",
" <span class=\"k\">try</span><span class=\"p\">:</span>\n",
" <span class=\"n\">G</span><span class=\"p\">,</span> <span class=\"n\">act1</span><span class=\"p\">,</span> <span class=\"n\">possible_actions</span> <span class=\"o\">=</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">find_open_precondition</span><span class=\"p\">()</span>\n",
" <span class=\"k\">except</span> <span class=\"ne\">IndexError</span><span class=\"p\">:</span>\n",
" <span class=\"k\">print</span><span class=\"p\">(</span><span class=\"s1\">'Probably Wrong'</span><span class=\"p\">)</span>\n",
" <span class=\"k\">break</span>\n",
"\n",
" <span class=\"n\">act0</span> <span class=\"o\">=</span> <span class=\"n\">possible_actions</span><span class=\"p\">[</span><span class=\"mi\">0</span><span class=\"p\">]</span>\n",
" <span class=\"c1\"># remove <G, act1> from Agenda</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">agenda</span><span class=\"o\">.</span><span class=\"n\">remove</span><span class=\"p\">((</span><span class=\"n\">G</span><span class=\"p\">,</span> <span class=\"n\">act1</span><span class=\"p\">))</span>\n",
"\n",
" <span class=\"c1\"># For actions with variable number of arguments, use least commitment principle</span>\n",
" <span class=\"c1\"># act0_temp, bindings = self.find_action_for_precondition(G)</span>\n",
" <span class=\"c1\"># act0 = self.generate_action_object(act0_temp, bindings)</span>\n",
"\n",
" <span class=\"c1\"># Actions = Actions U {act0}</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">actions</span><span class=\"o\">.</span><span class=\"n\">add</span><span class=\"p\">(</span><span class=\"n\">act0</span><span class=\"p\">)</span>\n",
"\n",
" <span class=\"c1\"># Constraints = add_const(start < act0, Constraints)</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">constraints</span> <span class=\"o\">=</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">add_const</span><span class=\"p\">((</span><span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">start</span><span class=\"p\">,</span> <span class=\"n\">act0</span><span class=\"p\">),</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">constraints</span><span class=\"p\">)</span>\n",
"\n",
" <span class=\"c1\"># for each CL E CausalLinks do</span>\n",
" <span class=\"c1\"># Constraints = protect(CL, act0, Constraints)</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">causal_link</span> <span class=\"ow\">in</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">causal_links</span><span class=\"p\">:</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">constraints</span> <span class=\"o\">=</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">protect</span><span class=\"p\">(</span><span class=\"n\">causal_link</span><span class=\"p\">,</span> <span class=\"n\">act0</span><span class=\"p\">,</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">constraints</span><span class=\"p\">)</span>\n",
"\n",
" <span class=\"c1\"># Agenda = Agenda U {<P, act0>: P is a precondition of act0}</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">precondition</span> <span class=\"ow\">in</span> <span class=\"n\">act0</span><span class=\"o\">.</span><span class=\"n\">precond</span><span class=\"p\">:</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">agenda</span><span class=\"o\">.</span><span class=\"n\">add</span><span class=\"p\">((</span><span class=\"n\">precondition</span><span class=\"p\">,</span> <span class=\"n\">act0</span><span class=\"p\">))</span>\n",
"\n",
" <span class=\"c1\"># Constraints = add_const(act0 < act1, Constraints)</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">constraints</span> <span class=\"o\">=</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">add_const</span><span class=\"p\">((</span><span class=\"n\">act0</span><span class=\"p\">,</span> <span class=\"n\">act1</span><span class=\"p\">),</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">constraints</span><span class=\"p\">)</span>\n",
"\n",
" <span class=\"c1\"># CausalLinks U {<act0, G, act1>}</span>\n",
" <span class=\"k\">if</span> <span class=\"p\">(</span><span class=\"n\">act0</span><span class=\"p\">,</span> <span class=\"n\">G</span><span class=\"p\">,</span> <span class=\"n\">act1</span><span class=\"p\">)</span> <span class=\"ow\">not</span> <span class=\"ow\">in</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">causal_links</span><span class=\"p\">:</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">causal_links</span><span class=\"o\">.</span><span class=\"n\">append</span><span class=\"p\">((</span><span class=\"n\">act0</span><span class=\"p\">,</span> <span class=\"n\">G</span><span class=\"p\">,</span> <span class=\"n\">act1</span><span class=\"p\">))</span>\n",
"\n",
" <span class=\"c1\"># for each A E Actions do</span>\n",
" <span class=\"c1\"># Constraints = protect(<act0, G, act1>, A, Constraints)</span>\n",
" <span class=\"k\">for</span> <span class=\"n\">action</span> <span class=\"ow\">in</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">actions</span><span class=\"p\">:</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">constraints</span> <span class=\"o\">=</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">protect</span><span class=\"p\">((</span><span class=\"n\">act0</span><span class=\"p\">,</span> <span class=\"n\">G</span><span class=\"p\">,</span> <span class=\"n\">act1</span><span class=\"p\">),</span> <span class=\"n\">action</span><span class=\"p\">,</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">constraints</span><span class=\"p\">)</span>\n",
"\n",
" <span class=\"k\">if</span> <span class=\"n\">step</span> <span class=\"o\">></span> <span class=\"mi\">200</span><span class=\"p\">:</span>\n",
" <span class=\"k\">print</span><span class=\"p\">(</span><span class=\"s1\">'Couldn</span><span class=\"se\">\\'</span><span class=\"s1\">t find a solution'</span><span class=\"p\">)</span>\n",
" <span class=\"k\">return</span> <span class=\"bp\">None</span><span class=\"p\">,</span> <span class=\"bp\">None</span>\n",
"\n",
" <span class=\"k\">if</span> <span class=\"n\">display</span><span class=\"p\">:</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">display_plan</span><span class=\"p\">()</span>\n",
" <span class=\"k\">else</span><span class=\"p\">:</span>\n",
" <span class=\"k\">return</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">constraints</span><span class=\"p\">,</span> <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">causal_links</span> \n",
"</pre></div>\n",
"</body>\n",
"</html>\n"
],
"text/plain": [
"<IPython.core.display.HTML object>"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"psource(PartialOrderPlanner)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We will first describe the data-structures and helper methods used, followed by the algorithm used to find a partial-order plan."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Each plan has the following four components:\n",
"\n",
"1. **`actions`**: a set of actions that make up the steps of the plan.\n",
"`actions` is always a subset of `pddl.actions` the set of possible actions for the given planning problem. \n",
"The `start` and `finish` actions are dummy actions defined to bring uniformity to the problem. The `start` action has no preconditions and its effects constitute the initial state of the planning problem. \n",
"The `finish` action has no effects and its preconditions constitute the goal state of the planning problem.\n",
"The empty plan consists of just these two dummy actions.\n",
"2. **`constraints`**: a set of temporal constraints that define the order of performing the actions relative to each other.\n",
"`constraints` does not define a linear ordering, rather it usually represents a directed graph which is also acyclic if the plan is consistent.\n",
"Each ordering is of the form A < B, which reads as \"A before B\" and means that action A _must_ be executed sometime before action B, but not necessarily immediately before.\n",
"`constraints` stores these as a set of tuples `(Action(A), Action(B))` which is interpreted as given above.\n",
"A constraint cannot be added to `constraints` if it breaks the acyclicity of the existing graph.\n",
"3. **`causal_links`**: a set of causal-links. \n",
"A causal link between two actions _A_ and _B_ in the plan is written as _A_ --_p_--> _B_ and is read as \"A achieves p for B\".\n",
"This imples that _p_ is an effect of _A_ and a precondition of _B_.\n",
"It also asserts that _p_ must remain true from the time of action _A_ to the time of action _B_.\n",
"Any violation of this rule is called a threat and must be resolved immediately by adding suitable ordering constraints.\n",
"`causal_links` stores this information as tuples `(Action(A), precondition(p), Action(B))` which is interpreted as given above.\n",
"Causal-links can also be called **protection-intervals**, because the link _A_ --_p_--> _B_ protects _p_ from being negated over the interval from _A_ to _B_.\n",
"4. **`agenda`**: a set of open-preconditions.\n",
"A precondition is open if it is not achieved by some action in the plan.\n",
"Planners will work to reduce the set of open preconditions to the empty set, without introducing a contradiction.\n",
"`agenda` stored this information as tuples `(precondition(p), Action(A))` where p is a precondition of the action A.\n",
"\n",
"A **consistent plan** is a plan in which there are no cycles in the ordering constraints and no conflicts with the causal-links.\n",
"A consistent plan with no open preconditions is a **solution**.\n",
"<br>\n",
"Let's briefly glance over the helper functions before going into the actual algorithm.\n",
4564
4565
4566
4567
4568
4569
4570
4571
4572
4573
4574
4575
4576
4577
4578
4579
4580
4581
4582
4583
4584
4585
4586
4587
4588
4589
4590
4591
4592
4593
4594
4595
4596
4597
4598
4599
4600
4601
4602
4603
4604
4605
4606
4607
4608
4609
4610
4611
4612
4613
4614
4615
4616
4617
4618
4619
4620
4621
4622
4623
4624
4625
4626
4627
4628
4629
4630
4631
4632
4633
4634
4635
4636
4637
4638
4639
4640
4641
4642
4643
4644
4645
4646
4647
4648
4649
4650
4651
4652
4653
4654
4655
4656
4657
4658
4659
4660
4661
4662
4663
4664
4665
4666
4667
4668
4669
4670
4671
4672
4673
4674
4675
4676
4677
4678
4679
4680
4681
4682
4683
4684
4685
4686
4687
4688
4689
4690
4691
4692
4693
4694
4695
4696
4697
4698
4699
4700
4701
4702
4703
4704
4705
4706
4707
4708
4709
4710
4711
4712
4713
4714
4715
4716
4717
4718
4719
4720
4721
4722
4723
4724
4725
4726
4727
4728
4729
4730
4731
4732
4733
4734
4735
4736
4737
4738
4739
4740
4741
4742
4743
4744
4745
4746
4747
4748
4749
4750
4751
4752
4753
4754
4755
4756
4757
4758
4759
4760
4761
4762
4763
4764
4765
4766
4767
4768
4769
4770
4771
4772
4773
4774
4775
4776
4777
4778
4779
4780
4781
4782
4783
4784
4785
4786
4787
4788
4789
4790
4791
4792
4793
4794
4795
4796
4797
4798
4799
4800
4801
4802
4803
4804
4805
4806
4807
4808
4809
4810
4811
4812
4813
4814
4815
4816
4817
4818
4819
4820
4821
4822
4823
4824
4825
4826
4827
4828
4829
4830
4831
4832
4833
4834
4835
4836
4837
4838
4839
4840
4841
4842
4843
4844
4845
4846
4847
4848
4849
4850
4851
4852
4853
4854
4855
4856
4857
4858
4859
4860
4861
4862
4863
4864
4865
4866
4867
4868
4869
4870
4871
4872
"**`expand_actions`**: generates all possible actions with variable bindings for use as a heuristic of selection of an open precondition.\n",
"<br>\n",
"**`find_open_precondition`**: finds a precondition from the agenda with the least number of actions that fulfil that precondition.\n",
"This heuristic helps form mandatory ordering constraints and causal-links to further simplify the problem and reduce the probability of encountering a threat.\n",
"<br>\n",
"**`find_action_for_precondition`**: finds an action that fulfils the given precondition along with the absolutely necessary variable bindings in accordance with the principle of _least commitment_.\n",
"In case of multiple possible actions, the action with the least number of effects is chosen to minimize the chances of encountering a threat.\n",
"<br>\n",
"**`cyclic`**: checks if a directed graph is cyclic.\n",
"<br>\n",
"**`add_const`**: adds `constraint` to `constraints` if the newly formed graph is acyclic and returns `constraints` otherwise.\n",
"<br>\n",
"**`is_a_threat`**: checks if the given `effect` negates the given `precondition`.\n",
"<br>\n",
"**`protect`**: checks if the given `action` poses a threat to the given `causal_link`.\n",
"If so, the threat is resolved by either promotion or demotion, whichever generates acyclic temporal constraints.\n",
"If neither promotion or demotion work, the chosen action is not the correct fit or the planning problem cannot be solved altogether.\n",
"<br>\n",
"**`convert`**: converts a graph from a list of edges to an `Action` : `set` mapping, for use in topological sorting.\n",
"<br>\n",
"**`toposort`**: a generator function that generates a topological ordering of a given graph as a list of sets.\n",
"Each set contains an action or several actions.\n",
"If a set has more that one action in it, it means that permutations between those actions also produce a valid plan.\n",
"<br>\n",
"**`display_plan`**: displays the `causal_links`, `constraints` and the partial order plan generated from `toposort`.\n",
"<br>"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The **`execute`** method executes the algorithm, which is summarized below:\n",
"<br>\n",
"1. An open precondition is selected (a sub-goal that we want to achieve).\n",
"2. An action that fulfils the open precondition is chosen.\n",
"3. Temporal constraints are updated.\n",
"4. Existing causal links are protected. Protection is a method that checks if the causal links conflict\n",
" and if they do, temporal constraints are added to fix the threats.\n",
"5. The set of open preconditions is updated.\n",
"6. Temporal constraints of the selected action and the next action are established.\n",
"7. A new causal link is added between the selected action and the owner of the open precondition.\n",
"8. The set of new causal links is checked for threats and if found, the threat is removed by either promotion or demotion.\n",
" If promotion or demotion is unable to solve the problem, the planning problem cannot be solved with the current sequence of actions\n",
" or it may not be solvable at all.\n",
"9. These steps are repeated until the set of open preconditions is empty."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"A partial-order plan can be used to generate different valid total-order plans.\n",
"This step is called **linearization** of the partial-order plan.\n",
"All possible linearizations of a partial-order plan for `socks_and_shoes` looks like this.\n",
"<br>\n",
"\n",
"<br>\n",
"Linearization can be carried out in many ways, but the most efficient way is to represent the set of temporal constraints as a directed graph.\n",
"We can easily realize that the graph should also be acyclic as cycles in constraints means that the constraints are inconsistent.\n",
"This acyclicity is enforced by the `add_const` method, which adds a new constraint only if the acyclicity of the existing graph is not violated.\n",
"The `protect` method also checks for acyclicity of the newly-added temporal constraints to make a decision between promotion and demotion in case of a threat.\n",
"This property of a graph created from the temporal constraints of a valid partial-order plan allows us to use topological sort to order the constraints linearly.\n",
"A topological sort may produce several different valid solutions for a given directed acyclic graph."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now that we know how `PartialOrderPlanner` works, let's solve a few problems using it."
]
},
{
"cell_type": "code",
"execution_count": 67,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Causal Links\n",
"(Action(PutOn(Spare, Axle)), At(Spare, Axle), Action(Finish))\n",
"(Action(Start), Tire(Spare), Action(PutOn(Spare, Axle)))\n",
"(Action(Remove(Flat, Axle)), NotAt(Flat, Axle), Action(PutOn(Spare, Axle)))\n",
"(Action(Start), At(Flat, Axle), Action(Remove(Flat, Axle)))\n",
"(Action(Remove(Spare, Trunk)), At(Spare, Ground), Action(PutOn(Spare, Axle)))\n",
"(Action(Start), At(Spare, Trunk), Action(Remove(Spare, Trunk)))\n",
"(Action(Remove(Flat, Axle)), At(Flat, Ground), Action(Finish))\n",
"\n",
"Constraints\n",
"Action(Start) < Action(Finish)\n",
"Action(Start) < Action(Remove(Spare, Trunk))\n",
"Action(Remove(Flat, Axle)) < Action(PutOn(Spare, Axle))\n",
"Action(Remove(Flat, Axle)) < Action(Finish)\n",
"Action(Remove(Spare, Trunk)) < Action(PutOn(Spare, Axle))\n",
"Action(Start) < Action(PutOn(Spare, Axle))\n",
"Action(Start) < Action(Remove(Flat, Axle))\n",
"Action(PutOn(Spare, Axle)) < Action(Finish)\n",
"\n",
"Partial Order Plan\n",
"[{Action(Start)}, {Action(Remove(Flat, Axle)), Action(Remove(Spare, Trunk))}, {Action(PutOn(Spare, Axle))}, {Action(Finish)}]\n"
]
}
],
"source": [
"st = spare_tire()\n",
"pop = PartialOrderPlanner(st)\n",
"pop.execute()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We observe that in the given partial order plan, Remove(Flat, Axle) and Remove(Spare, Trunk) are in the same set.\n",
"This means that the order of performing these actions does not affect the final outcome.\n",
"That aside, we also see that the PutOn(Spare, Axle) action has to be performed after both the Remove actions are complete, which seems logically consistent."
]
},
{
"cell_type": "code",
"execution_count": 68,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Causal Links\n",
"(Action(FromTable(B, A)), On(B, A), Action(Finish))\n",
"(Action(FromTable(C, B)), On(C, B), Action(Finish))\n",
"(Action(Start), Clear(C), Action(FromTable(C, B)))\n",
"(Action(Start), Clear(A), Action(FromTable(B, A)))\n",
"(Action(Start), OnTable(C), Action(FromTable(C, B)))\n",
"(Action(Start), OnTable(B), Action(FromTable(B, A)))\n",
"(Action(ToTable(A, B)), Clear(B), Action(FromTable(C, B)))\n",
"(Action(Start), On(A, B), Action(ToTable(A, B)))\n",
"(Action(ToTable(A, B)), Clear(B), Action(FromTable(B, A)))\n",
"(Action(Start), Clear(A), Action(ToTable(A, B)))\n",
"\n",
"Constraints\n",
"Action(Start) < Action(FromTable(B, A))\n",
"Action(Start) < Action(FromTable(C, B))\n",
"Action(Start) < Action(ToTable(A, B))\n",
"Action(ToTable(A, B)) < Action(FromTable(C, B))\n",
"Action(Start) < Action(Finish)\n",
"Action(ToTable(A, B)) < Action(FromTable(B, A))\n",
"Action(FromTable(C, B)) < Action(Finish)\n",
"Action(FromTable(B, A)) < Action(Finish)\n",
"Action(FromTable(B, A)) < Action(FromTable(C, B))\n",
"\n",
"Partial Order Plan\n",
"[{Action(Start)}, {Action(ToTable(A, B))}, {Action(FromTable(B, A))}, {Action(FromTable(C, B))}, {Action(Finish)}]\n"
]
}
],
"source": [
"sbw = simple_blocks_world()\n",
"pop = PartialOrderPlanner(sbw)\n",
"pop.execute()"
]
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": true
},
"source": [
"We see that this plan does not have flexibility in selecting actions, ie, actions should be performed in this order and this order only, to successfully reach the goal state."
]
},
{
"cell_type": "code",
"execution_count": 69,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Causal Links\n",
"(Action(RightShoe), RightShoeOn, Action(Finish))\n",
"(Action(LeftShoe), LeftShoeOn, Action(Finish))\n",
"(Action(LeftSock), LeftSockOn, Action(LeftShoe))\n",
"(Action(RightSock), RightSockOn, Action(RightShoe))\n",
"\n",
"Constraints\n",
"Action(Start) < Action(RightSock)\n",
"Action(Start) < Action(LeftSock)\n",
"Action(RightSock) < Action(RightShoe)\n",
"Action(RightShoe) < Action(Finish)\n",
"Action(Start) < Action(LeftShoe)\n",
"Action(LeftSock) < Action(LeftShoe)\n",
"Action(Start) < Action(RightShoe)\n",
"Action(Start) < Action(Finish)\n",
"Action(LeftShoe) < Action(Finish)\n",
"\n",
"Partial Order Plan\n",
"[{Action(Start)}, {Action(LeftSock), Action(RightSock)}, {Action(RightShoe), Action(LeftShoe)}, {Action(Finish)}]\n"
]
}
],
"source": [
"ss = socks_and_shoes()\n",
"pop = PartialOrderPlanner(ss)\n",
"pop.execute()"
]
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": true
},
"source": [
"This plan again doesn't have constraints in selecting socks or shoes.\n",
"As long as both socks are worn before both shoes, we are fine.\n",
"Notice however, there is one valid solution,\n",
"<br>\n",
"LeftSock -> LeftShoe -> RightSock -> RightShoe\n",
"<br>\n",
"that the algorithm could not find as it cannot be represented as a general partially-ordered plan but is a specific total-order solution."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Runtime differences\n",
"Let's briefly take a look at the running time of all the three algorithms on the `socks_and_shoes` problem."
]
},
{
"cell_type": "code",
"execution_count": 70,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"ss = socks_and_shoes()"
]
},
{
"cell_type": "code",
"execution_count": 71,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"333 µs ± 8.86 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n"
]
}
],
"source": [
"%%timeit\n",
"GraphPlan(ss).execute()"
]
},
{
"cell_type": "code",
"execution_count": 72,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"1.29 ms ± 43.6 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n"
]
}
],
"source": [
"%%timeit\n",
"Linearize(ss).execute()"
]
},
{
"cell_type": "code",
"execution_count": 73,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"425 µs ± 17 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n"
]
}
],
"source": [
"%%timeit\n",
"PartialOrderPlanner(ss).execute(display=False)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We observe that `GraphPlan` is about 4 times faster than `Linearize` because `Linearize` essentially runs a `GraphPlan` subroutine under the hood and then carries out some transformations on the solved planning-graph.\n",
"<br>\n",
"We also find that `GraphPlan` is slightly faster than `PartialOrderPlanner`, but this is mainly due to the `expand_actions` method in `PartialOrderPlanner` that slows it down as it generates all possible permutations of actions and variable bindings.\n",
"<br>\n",
"Without heuristic functions, `PartialOrderPlanner` will be atleast as fast as `GraphPlan`, if not faster, but will have a higher tendency to encounter threats and conflicts which might take additional time to resolve.\n",
"<br>\n",
"Different planning algorithms work differently for different problems."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## PLANNING IN THE REAL WORLD\n",
"---\n",
"## PROBLEM\n",
"The `Problem` class is a wrapper for `PlanningProblem` with some additional functionality and data-structures to handle real-world planning problems that involve time and resource constraints.\n",
"The `Problem` class includes everything that the `PlanningProblem` class includes.\n",
"Additionally, it also includes the following attributes essential to define a real-world planning problem:\n",
"- a list of `jobs` to be done\n",
"- a dictionary of `resources`\n",
"\n",
"It also overloads the `act` method to call the `do_action` method of the `HLA` class, \n",
"and also includes a new method `refinements` that finds refinements or primitive actions for high level actions.\n",
"<br>\n",
"`hierarchical_search` and `angelic_search` are also built into the `Problem` class to solve such planning problems."
{
"cell_type": "code",
4897
4898
4899
4900
4901
4902
4903
4904
4905
4906
4907
4908
4909
4910
4911
4912
4913
4914
4915
4916
4917
4918
4919
4920
4921
4922
4923
4924
4925
4926
4927
4928
4929
4930
4931
4932
4933
4934
4935
4936
4937
4938
4939
4940
4941
4942
4943
4944
4945
4946
4947
4948
4949
4950
4951
4952
4953
4954
4955
4956
4957
4958
4959
4960
4961
4962
4963
4964
4965
4966
4967
4968
4969
4970
4971
4972
4973
4974
4975
4976
4977
4978
4979
4980
4981
4982
4983
4984
4985
4986
4987
"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\">Problem</span><span class=\"p\">(</span><span class=\"n\">PlanningProblem</span><span class=\"p\">):</span>\n",
" <span class=\"sd\">"""</span>\n",
"<span class=\"sd\"> Define real-world problems by aggregating resources as numerical quantities instead of</span>\n",
"<span class=\"sd\"> named entities.</span>\n",
"<span class=\"sd\"> This class is identical to PDLL, except that it overloads the act function to handle</span>\n",
"<span class=\"sd\"> resource and ordering conditions imposed by HLA as opposed to Action.</span>\n",
"<span class=\"sd\"> """</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\">init</span><span class=\"p\">,</span> <span class=\"n\">goals</span><span class=\"p\">,</span> <span class=\"n\">actions</span><span class=\"p\">,</span> <span class=\"n\">jobs</span><span class=\"o\">=</span><span class=\"bp\">None</span><span class=\"p\">,</span> <span class=\"n\">resources</span><span class=\"o\">=</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\">init</span><span class=\"p\">,</span> <span class=\"n\">goals</span><span class=\"p\">,</span> <span class=\"n\">actions</span><span class=\"p\">)</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">jobs</span> <span class=\"o\">=</span> <span class=\"n\">jobs</span>\n",
" <span class=\"bp\">self</span><span class=\"o\">.</span><span class=\"n\">resources</span> <span class=\"o\">=</span> <span class=\"n\">resources</span> <span class=\"ow\">or</span> <span class=\"p\">{}</span>\n",