WEBVTT

00:02.930 --> 00:08.810
So far, we've looked at the theory for constructing a goat based plan, but now we have to program

00:08.810 --> 00:09.260
one.

00:09.290 --> 00:15.440
In the end, what we're after is an algorithm that sorts through the actions and matches their effects

00:15.440 --> 00:18.890
with other preconditions to construct a plan.

00:19.490 --> 00:23.870
So we start by getting all the available actions and agent can perform.

00:23.990 --> 00:30.980
These are given to the planner, which checks through all of them to see if in principle they are achievable.

00:31.010 --> 00:36.960
Remember, that little is achievable method we wrote for the actions that always returns true.

00:36.980 --> 00:38.870
Well, this is the test for that.

00:38.900 --> 00:44.210
Now, if you needed to put some other logic into that method, that would have an action rejected by

00:44.210 --> 00:47.440
the planner before planning even takes place.

00:47.450 --> 00:49.400
Then this is where you would put it.

00:49.400 --> 00:54.590
But we are just working on the principle that all actions are going to be achievable.

00:55.070 --> 00:59.000
Then we start building a graph beginning with an initial node.

00:59.330 --> 01:04.170
Now this initial node is going to have the world states as its effects.

01:04.190 --> 01:10.220
We then look through all the achievable actions for ones that can be performed given the states in the

01:10.220 --> 01:11.510
first node.

01:11.660 --> 01:17.750
Each matching action creates a new node and a new branch in the graph that we're constructing.

01:18.200 --> 01:25.700
We then explore each branch for another action that can be attached using the preconditions and effects.

01:26.390 --> 01:34.670
This process continues down each branch until a path is satisfied that matches the initial goal or the

01:34.670 --> 01:36.500
planner runs out of actions.

01:37.300 --> 01:43.930
If a path is found, that path becomes the agents queue of actions and then the agent starts to perform

01:43.930 --> 01:44.380
them.

01:45.070 --> 01:48.310
So let's start creating this planning class.

01:48.430 --> 01:52.660
Right click down in your assets and add another C-sharp.

01:52.660 --> 01:55.510
We're going to call this a G planner.

01:55.900 --> 01:57.760
Then open that up.

01:57.760 --> 02:07.090
And first thing we're going to do is at the top add using system link again for sorting things like

02:07.090 --> 02:12.910
our dictionary and we will also create a helper class at the top.

02:12.910 --> 02:16.120
So a public class for our nodes.

02:16.120 --> 02:23.200
So remember we're constructing a graph and we're doing that with the planner which will link all of

02:23.200 --> 02:28.690
our actions together in a plan, but rather than link the actions to other actions, we're actually

02:28.690 --> 02:35.770
just going to create a set of nodes that are linked to one another and then they will just hold on or

02:35.770 --> 02:38.680
point back to a particular action.

02:38.860 --> 02:39.160
Okay.

02:39.220 --> 02:47.530
So first of all, we're going to have a public node which is the parent of this node, then a public.

02:48.750 --> 02:55.170
Float, which will be a cost for the action which will be used in determining which plan is actually

02:55.170 --> 02:56.240
the cheapest.

02:56.250 --> 02:58.200
Should there be multiple plans?

02:58.320 --> 03:00.420
Then we want a public.

03:02.320 --> 03:06.400
Dictionary and you can probably imagine what's going to go in here.

03:06.400 --> 03:06.820
Yes.

03:06.820 --> 03:14.260
String int for the state that we're going to store initially that will be the world states in the first

03:14.260 --> 03:23.530
node and then the public g action, the action that this node is talking about or pointing to.

03:24.980 --> 03:25.290
Okay.

03:25.360 --> 03:29.320
So that's the properties of that node.

03:29.320 --> 03:30.940
Now let's construct it.

03:31.120 --> 03:34.330
So public node node.

03:35.530 --> 03:39.490
Parent float cost.

03:41.130 --> 03:42.540
Dictionary.

03:43.450 --> 03:45.910
String int.

03:48.530 --> 03:49.880
All states.

03:51.660 --> 03:54.450
And finally, the action g action.

03:55.900 --> 03:56.620
Action.

03:57.640 --> 04:06.190
And then inside of here, we'll just make sure that we set each of our property values to the desired

04:06.190 --> 04:06.460
ones.

04:06.460 --> 04:07.780
So parent.

04:09.570 --> 04:11.580
We should say this parent.

04:12.600 --> 04:14.040
Equals parent.

04:15.780 --> 04:18.960
This dot cost equals cost.

04:19.890 --> 04:27.360
This dot state equals all states, but but not all states because it'll point back to that dictionary.

04:27.360 --> 04:30.270
We actually want it to be a copy of that dictionary.

04:30.270 --> 04:41.490
So in order to do that, we create a new dictionary of String iNts and we give it our all states to

04:41.490 --> 04:45.120
make sure that we've definitely made a copy.

04:45.120 --> 04:51.600
And then this dot action will equal the action, okay, to our planner.

04:51.600 --> 04:54.230
So down the plan, we can actually get rid of our update.

04:54.240 --> 04:54.990
Now start.

04:54.990 --> 05:00.630
It's just going to be doing processing on our graph and constructing the graph.

05:00.630 --> 05:03.000
So it doesn't need to be a mona behavior either.

05:03.240 --> 05:03.690
Okay.

05:03.690 --> 05:06.810
So first of all, we're going to create our method.

05:06.810 --> 05:13.560
So it's public, it's returning a Q and it's going to return a Q of G actions.

05:13.560 --> 05:16.320
So g action.

05:17.360 --> 05:19.460
And we'll call it plan.

05:20.180 --> 05:24.350
It's going to require a list of all of the actions.

05:24.350 --> 05:30.020
So action which we have, the agent has a hold of that because it constructs one itself.

05:30.020 --> 05:43.360
So actions the dictionary of the desired goal so dictionary and string int goal and the world states

05:43.370 --> 05:44.270
as well.

05:44.270 --> 05:49.070
So let's put well states and call that.

05:49.950 --> 05:51.020
States.

05:51.480 --> 05:51.670
Okay.

05:51.720 --> 05:58.800
So in here, first of all, we will find out which of the actions that we've got is actually usable

05:58.800 --> 06:00.130
and hold onto those.

06:00.150 --> 06:05.610
So we'll create a list of action.

06:06.590 --> 06:13.670
Here's a bull actions equals new list of actions.

06:14.330 --> 06:21.860
And then for each g action a in actions.

06:25.110 --> 06:32.640
If a dot is achievable, then we will add that one to our usable actions.

06:32.640 --> 06:36.270
So usable actions do not add.

06:37.360 --> 06:44.770
Hey, so that's going to siphon out any actions that can't be run right now.

06:44.770 --> 06:50.500
After that, what we're going to do is set up our first leaf for our graph.

06:50.530 --> 06:50.890
Okay?

06:50.920 --> 07:03.820
So we want a list of nodes, let's call them leaves equals new list of node.

07:04.300 --> 07:08.140
And the starting node node start.

07:08.320 --> 07:14.920
It's going to equal a new node and it's going to have a null parent because it's the first one.

07:14.920 --> 07:24.340
It's going to have zero cost again because it's the first one, it's going to have a list of the states.

07:24.340 --> 07:28.270
So that's going to be inside of our worlds.

07:28.270 --> 07:41.620
Singleton So that's G world dot instance, dot get world dot get states and then null for the action

07:41.620 --> 07:42.490
that it's pointing to.

07:42.490 --> 07:50.500
Because again, it's just that very first node, it's not actually pointing to a particular action right

07:50.500 --> 07:50.710
now.

07:50.710 --> 07:53.170
Once we've done that, we want to build the graph.

07:53.170 --> 07:58.600
So we're going to return true or false based on whether we've actually found a path.

07:58.600 --> 08:07.360
So it'll be bool success and that's going to equal what we return from build graph that we're yet to

08:07.360 --> 08:07.990
write.

08:08.020 --> 08:15.430
We'll pass it the starting node, the list of leaves which at this point is empty, the list of usable

08:15.430 --> 08:18.970
actions and the goal.

08:21.190 --> 08:22.450
So that's our bill graph.

08:22.510 --> 08:27.790
Now, when we come back from build graph, we will test if we have a success.

08:28.240 --> 08:36.370
If we're not successful, then what we can do in here is say that we haven't found a plan.

08:36.400 --> 08:44.020
Now I'm going to put a debug log in here to make sure that we do get some kind of feedback, because

08:44.020 --> 08:50.710
there's a lot going on once you start planning and running your agents as to trying to figure out what

08:50.710 --> 08:53.320
is actually going on within the system.

08:53.320 --> 08:58.210
And you might end up with an awful lot of bugs throughout the whole thing, which is, okay, that's

08:58.210 --> 09:04.300
pretty natural until you get your head around the way that these nodes and the actions all sort of fit

09:04.300 --> 09:04.960
together.

09:04.960 --> 09:07.240
So at this point we will return null.

09:07.240 --> 09:13.840
So we're actually returning no plan whatsoever if there is no plan, which makes sense.

09:14.020 --> 09:14.260
Okay.

09:14.290 --> 09:22.390
What we're going to do then is if we've got this far, then we do have a particular plan that we can

09:22.390 --> 09:24.400
follow to achieve our goal.

09:24.400 --> 09:34.330
So now we're going to find the cheapest, so node cheapest equals null initially and then we'll do a

09:34.330 --> 09:40.990
for each node leaf in leaves.

09:42.970 --> 09:43.530
Okay.

09:43.540 --> 09:46.630
And we're going to loop around all of these.

09:47.050 --> 09:52.810
Now, at this point, we're going to check if the cheapest leaf or node.

09:52.810 --> 10:06.700
So if cheapest equals null, then the cheapest node that we have is just going to be set to the leaf.

10:06.730 --> 10:12.430
It means we've not found anything that is actually cheaper, so we'll just use the one that we've got

10:12.700 --> 10:15.010
and then else we're going to put.

10:15.010 --> 10:25.450
If leaf cost is less than cheapest dot cost, then we're going to say cheapest.

10:27.270 --> 10:28.980
Equals life.

10:31.560 --> 10:38.550
So now at this point, we have found our cheapest leaf node.

10:38.760 --> 10:45.690
Once we've got our cheapest node, Rashi now going to work backwards through it and back up the chain

10:45.690 --> 10:47.910
to get the sequence of actions.

10:47.910 --> 10:54.390
Because we've gone down through the graph, we found our cheapest leaf, which is right at the end of

10:54.390 --> 10:57.290
the plan, and now we need to make our way back up it.

10:57.440 --> 11:03.990
Okay, so we're going to create a list of G actions which will be our resulting plan.

11:04.920 --> 11:07.410
And that's going to equal a new list.

11:08.230 --> 11:10.000
Of G action.

11:12.380 --> 11:16.070
And then node n equals the cheapest.

11:18.210 --> 11:22.890
And then while an does not equal null.

11:26.110 --> 11:34.270
Going to say if an action does not equal null and it should only be null if we've hit the starting node

11:34.270 --> 11:38.410
anyway as we work out backwards along the path.

11:38.680 --> 11:47.320
Results dot insert at the beginning and dot action.

11:48.880 --> 11:54.220
And then in equals in dot parent.

11:55.690 --> 12:01.840
So that we're now got the parent in an and we're going to get it's action and then we're going to get

12:01.840 --> 12:04.900
its parent and loop around until we've got all those.

12:04.900 --> 12:10.750
So essentially you've created a linked list out of these nodes which represent your graph right now

12:10.750 --> 12:16.810
that we've got that we can actually create our queue, which will have our actions that our agent can

12:16.810 --> 12:18.370
go ahead and perform.

12:18.470 --> 12:25.900
So queue action, let's call it queue with lowercase equals new queue.

12:27.150 --> 12:30.060
Of G action.

12:32.470 --> 12:39.730
And then for each g action i in result.

12:41.890 --> 12:44.590
We're going to go Q.

12:45.980 --> 12:53.600
Dot in q which puts an item on the end of our Q a.

12:55.030 --> 12:55.960
And that's it.

12:55.960 --> 13:01.030
So we're just transitioning them from our list into our queue.

13:01.060 --> 13:06.790
Now, at this point, if we've made it all the way down to here, well, we obviously have a plan because

13:06.790 --> 13:08.740
we've put that plan together.

13:08.740 --> 13:12.460
So let's just go debug dot log.

13:14.330 --> 13:16.460
The plan is.

13:16.460 --> 13:22.640
And of course, if you start getting just way too many of these debug lines as you're running the simulation,

13:22.640 --> 13:24.440
then you can of course comment them out.

13:24.950 --> 13:30.110
So for each g action A in Q.

13:31.770 --> 13:37.800
And this is purely looping through it just to print them out so that you can see that you've got a plan.

13:38.070 --> 13:42.450
So debug backlog of queue.

13:44.200 --> 13:50.440
And plus a dot action name or use.

13:52.990 --> 13:55.900
And then finally return our.

13:55.900 --> 14:00.430
Q And that goes back to our agent with the plan.

14:01.880 --> 14:07.880
So that is the bulk of the Q method.

14:07.910 --> 14:15.740
Now we have to write the build graph and because there's still so much more code to type in, we'll

14:15.740 --> 14:18.170
do that in the next video.
