My fellow coders, we have implemented two out of the four stages that are required to create the main
solver, but the first the robot location in localization.
And then we presented our MES in the form of a graph in mapping.
Now, with these information, our time, we need to look into methods of finding around from this maze
entry to the maze exit.
This is part planning for this.
We create a new file that we name as bought by Planet Dot.
By inside it we perform the necessary inputs.
This includes importing the CV to the library.
And after this we define the very first path planning algorithm, which will be the DFS of the DFS,
or the difference is a blind search algorithm.
And the reason it is called that, because it has no other information other than recognizing the goal
node when it's trying to find a path to the goal node.
And this is also the precise reason that instead of finding a single path from the start node to the
goal node, it finds all possible path on the start node to the goal.
And this is also the reason we defined the function as get path instead of get path.
And the arguments that it takes is the first argument is the graph that we extracted from the mapping
module.
Then we have the start and the goal node and then we have the path that leads up to that goes on.
And this is initialized to empty list at the start of this function.
And then because this is a complex problem, one method of solving this particular problem is through
recursion, and we are going to choose that method.
Now, recurrences, as mentioned in the theory is, can be solved in three separate steps.
The very first step is to break down the complex problem that you have.
The complex.
Into simpler
stuff problems.
So so our complex problem right now is that we want to find all possible path from the start node to
the gold node so we can simply break this down to instead trying to find a path from the neighbor node
to the start node, pick a gold node.
So this is a smaller part or smaller part that we need to find.
Then the original problem that we had that we were discussing earlier.
So let's break this down to a simpler problem so we can access the neighbor nodes, the start node,
by simply saying for node in graph file thing in the start key and then accessing all its keys, which
are basically all the neighbor nodes to the stock note.
So we trade over all the neighbor nodes and now instead of trying to find a path from the start node
to the goal node, we recursively call the get pass function.
Good boss function and boss in a graph as the first argument, and instead of the start node we now
pass in the node that is the neighbor node, the start node and and node, and then we passing the buck.
So basically what we are doing right here is that instead of trying to find a path for all possible
path from the start to the goal node, we are now trying to find a path from the neighbor node to start
node and the goal node.
So this is how recursion for steps works.
But this is recursively calling a simple case of the original problem.
So once we call this dysfunction, what would happen when this function gets called?
So what we want to do is to simply save the information of the path that we have just listed in all
those recursive calls, because we are leading up to that go node.
So basically, we are leading up to the path that leads up to that goal node.
So we want to save this information in the path.
And that can be done by writing path plus path, but is equal to Path Plus Star.
So basically all the norms that we have visited up until the final node is compose composes us that
the final part that leads up to the good note.
So this fills up the path that leads up to the goal node.
And now we need to address the second condition or the second step of the recursive.
Because in algorithm and the second step is that we to define the simplest case or the base condition.
So let's right here.
Define the simplest skills for this particular algorithm.
So the algorithm is to get past what would be the simplest case for this particular function.
The simplest case would be that we were trying to find a path from any node to itself.
So trying to find a path from a node.
So we simply return empty if we are trying to find a path from node to set.
But because this function can get called recursively, we need to return the information of the path
that we have been through previously and that can be done by simply writing if Port Authority, if part
is start equal, equal to.
And so basically we are trying to find a path from any node to it.
So then we simply return.
This is the basic condition.
We return the list that includes the path, so we return the path that we have just found.
So basically if we, if we call this function with any node with itself as the path is initialized empty,
so this will return an empty list.
But if it was already turning and calling the recursive call, this will basically return the port that
was leading up to that particular note.
Now we need to address the base or the boundary condition.
Now the boundary condition is what would happen if the start node that we are not writing on does not
exist in the graph case.
So if it does not exist, we simply don't need empty list because there's no path up until that node.
So now that we have addressed both this condition or all the steps of recursion, the final step is
to simply return the information from the simplest case and try to go back and solve this the previous
problems leading up to the original problem.
So basically we return this information when we use the simplest case of the recursive call, and then
we return the information right here where we have to perform the original call.
And this will be saved as new bots.
So this new path gets returned to the user.
And once this gets returned, we have now the path that leads up to our start node, to the goal node.
But as I mentioned, it's a blind search algorithm.
This will go on until it finds all possible path to the goal.
So that can be done by simply writing here.
So first means right.
We say here that this was the third step when we returned the new parts.
This was third step.
So go back.
Once we get the output of our function calls that we have called recursively, we go back and solve
previous legal sub problems.
So we tried to part solve the previously called sub problems because we now have the output, all those
sub problems.
So once we have this, we can now store all this information and start inside a complete list to store
all possible parts from start to end.
So now we create an empty list that will store all the possible paths to the start, nor to the gold
node.
So this is just a part we need to store all the possible bots that can be done by simply saying for
p in new parts that we have found, append these new parts to our total bot and that can be done by
writing auto foster apparent the p.
And finally once we have iterated over all the neighbor nodes to have a start node and find all the
possible parts, we finally done all the parts, all the possible path to our goal node.
So this completes the get pass function of our DFS algorithm for the case of our blind search algorithm.
Now we need to test it to see whether it is doing its job or not.
Until then.
Thank you.
And.
But.