So far, we've looked at the theory for constructing a goat based plan, but now we have to program
one.
In the end, what we're after is an algorithm that sorts through the actions and matches their effects
with other preconditions to construct a plan.
So we start by getting all the available actions and agent can perform.
These are given to the planner, which checks through all of them to see if in principle they are achievable.
Remember, that little is achievable method we wrote for the actions that always returns true.
Well, this is the test for that.
Now, if you needed to put some other logic into that method, that would have an action rejected by
the planner before planning even takes place.
Then this is where you would put it.
But we are just working on the principle that all actions are going to be achievable.
Then we start building a graph beginning with an initial node.
Now this initial node is going to have the world states as its effects.
We then look through all the achievable actions for ones that can be performed given the states in the
first node.
Each matching action creates a new node and a new branch in the graph that we're constructing.
We then explore each branch for another action that can be attached using the preconditions and effects.
This process continues down each branch until a path is satisfied that matches the initial goal or the
planner runs out of actions.
If a path is found, that path becomes the agents queue of actions and then the agent starts to perform
them.
So let's start creating this planning class.
Right click down in your assets and add another C-sharp.
We're going to call this a G planner.
Then open that up.
And first thing we're going to do is at the top add using system link again for sorting things like
our dictionary and we will also create a helper class at the top.
So a public class for our nodes.
So remember we're constructing a graph and we're doing that with the planner which will link all of
our actions together in a plan, but rather than link the actions to other actions, we're actually
just going to create a set of nodes that are linked to one another and then they will just hold on or
point back to a particular action.
Okay.
So first of all, we're going to have a public node which is the parent of this node, then a public.
Float, which will be a cost for the action which will be used in determining which plan is actually
the cheapest.
Should there be multiple plans?
Then we want a public.
Dictionary and you can probably imagine what's going to go in here.
Yes.
String int for the state that we're going to store initially that will be the world states in the first
node and then the public g action, the action that this node is talking about or pointing to.
Okay.
So that's the properties of that node.
Now let's construct it.
So public node node.
Parent float cost.
Dictionary.
String int.
All states.
And finally, the action g action.
Action.
And then inside of here, we'll just make sure that we set each of our property values to the desired
ones.
So parent.
We should say this parent.
Equals parent.
This dot cost equals cost.
This dot state equals all states, but but not all states because it'll point back to that dictionary.
We actually want it to be a copy of that dictionary.
So in order to do that, we create a new dictionary of String iNts and we give it our all states to
make sure that we've definitely made a copy.
And then this dot action will equal the action, okay, to our planner.
So down the plan, we can actually get rid of our update.
Now start.
It's just going to be doing processing on our graph and constructing the graph.
So it doesn't need to be a mona behavior either.
Okay.
So first of all, we're going to create our method.
So it's public, it's returning a Q and it's going to return a Q of G actions.
So g action.
And we'll call it plan.
It's going to require a list of all of the actions.
So action which we have, the agent has a hold of that because it constructs one itself.
So actions the dictionary of the desired goal so dictionary and string int goal and the world states
as well.
So let's put well states and call that.
States.
Okay.
So in here, first of all, we will find out which of the actions that we've got is actually usable
and hold onto those.
So we'll create a list of action.
Here's a bull actions equals new list of actions.
And then for each g action a in actions.
If a dot is achievable, then we will add that one to our usable actions.
So usable actions do not add.
Hey, so that's going to siphon out any actions that can't be run right now.
After that, what we're going to do is set up our first leaf for our graph.
Okay?
So we want a list of nodes, let's call them leaves equals new list of node.
And the starting node node start.
It's going to equal a new node and it's going to have a null parent because it's the first one.
It's going to have zero cost again because it's the first one, it's going to have a list of the states.
So that's going to be inside of our worlds.
Singleton So that's G world dot instance, dot get world dot get states and then null for the action
that it's pointing to.
Because again, it's just that very first node, it's not actually pointing to a particular action right
now.
Once we've done that, we want to build the graph.
So we're going to return true or false based on whether we've actually found a path.
So it'll be bool success and that's going to equal what we return from build graph that we're yet to
write.
We'll pass it the starting node, the list of leaves which at this point is empty, the list of usable
actions and the goal.
So that's our bill graph.
Now, when we come back from build graph, we will test if we have a success.
If we're not successful, then what we can do in here is say that we haven't found a plan.
Now I'm going to put a debug log in here to make sure that we do get some kind of feedback, because
there's a lot going on once you start planning and running your agents as to trying to figure out what
is actually going on within the system.
And you might end up with an awful lot of bugs throughout the whole thing, which is, okay, that's
pretty natural until you get your head around the way that these nodes and the actions all sort of fit
together.
So at this point we will return null.
So we're actually returning no plan whatsoever if there is no plan, which makes sense.
Okay.
What we're going to do then is if we've got this far, then we do have a particular plan that we can
follow to achieve our goal.
So now we're going to find the cheapest, so node cheapest equals null initially and then we'll do a
for each node leaf in leaves.
Okay.
And we're going to loop around all of these.
Now, at this point, we're going to check if the cheapest leaf or node.
So if cheapest equals null, then the cheapest node that we have is just going to be set to the leaf.
It means we've not found anything that is actually cheaper, so we'll just use the one that we've got
and then else we're going to put.
If leaf cost is less than cheapest dot cost, then we're going to say cheapest.
Equals life.
So now at this point, we have found our cheapest leaf node.
Once we've got our cheapest node, Rashi now going to work backwards through it and back up the chain
to get the sequence of actions.
Because we've gone down through the graph, we found our cheapest leaf, which is right at the end of
the plan, and now we need to make our way back up it.
Okay, so we're going to create a list of G actions which will be our resulting plan.
And that's going to equal a new list.
Of G action.
And then node n equals the cheapest.
And then while an does not equal null.
Going to say if an action does not equal null and it should only be null if we've hit the starting node
anyway as we work out backwards along the path.
Results dot insert at the beginning and dot action.
And then in equals in dot parent.
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
its parent and loop around until we've got all those.
So essentially you've created a linked list out of these nodes which represent your graph right now
that we've got that we can actually create our queue, which will have our actions that our agent can
go ahead and perform.
So queue action, let's call it queue with lowercase equals new queue.
Of G action.
And then for each g action i in result.
We're going to go Q.
Dot in q which puts an item on the end of our Q a.
And that's it.
So we're just transitioning them from our list into our queue.
Now, at this point, if we've made it all the way down to here, well, we obviously have a plan because
we've put that plan together.
So let's just go debug dot log.
The plan is.
And of course, if you start getting just way too many of these debug lines as you're running the simulation,
then you can of course comment them out.
So for each g action A in Q.
And this is purely looping through it just to print them out so that you can see that you've got a plan.
So debug backlog of queue.
And plus a dot action name or use.
And then finally return our.
Q And that goes back to our agent with the plan.
So that is the bulk of the Q method.
Now we have to write the build graph and because there's still so much more code to type in, we'll
do that in the next video.