1
00:00:01,310 --> 00:00:06,680
My fellow coders, we have implemented two out of the four stages that are required to create the main

2
00:00:06,680 --> 00:00:10,490
solver, but the first the robot location in localization.

3
00:00:10,580 --> 00:00:13,790
And then we presented our MES in the form of a graph in mapping.

4
00:00:14,240 --> 00:00:19,820
Now, with these information, our time, we need to look into methods of finding around from this maze

5
00:00:19,820 --> 00:00:21,410
entry to the maze exit.

6
00:00:21,740 --> 00:00:24,500
This is part planning for this.

7
00:00:24,710 --> 00:00:31,400
We create a new file that we name as bought by Planet Dot.

8
00:00:31,400 --> 00:00:34,520
By inside it we perform the necessary inputs.

9
00:00:34,790 --> 00:00:37,910
This includes importing the CV to the library.

10
00:00:38,450 --> 00:00:46,340
And after this we define the very first path planning algorithm, which will be the DFS of the DFS,

11
00:00:46,340 --> 00:00:49,070
or the difference is a blind search algorithm.

12
00:00:49,250 --> 00:00:54,230
And the reason it is called that, because it has no other information other than recognizing the goal

13
00:00:54,230 --> 00:00:57,230
node when it's trying to find a path to the goal node.

14
00:00:57,650 --> 00:01:03,470
And this is also the precise reason that instead of finding a single path from the start node to the

15
00:01:03,470 --> 00:01:07,170
goal node, it finds all possible path on the start node to the goal.

16
00:01:08,360 --> 00:01:13,010
And this is also the reason we defined the function as get path instead of get path.

17
00:01:13,610 --> 00:01:18,260
And the arguments that it takes is the first argument is the graph that we extracted from the mapping

18
00:01:18,260 --> 00:01:18,750
module.

19
00:01:19,010 --> 00:01:24,230
Then we have the start and the goal node and then we have the path that leads up to that goes on.

20
00:01:24,950 --> 00:01:27,920
And this is initialized to empty list at the start of this function.

21
00:01:28,280 --> 00:01:33,620
And then because this is a complex problem, one method of solving this particular problem is through

22
00:01:33,620 --> 00:01:36,290
recursion, and we are going to choose that method.

23
00:01:36,830 --> 00:01:41,450
Now, recurrences, as mentioned in the theory is, can be solved in three separate steps.

24
00:01:41,840 --> 00:01:47,510
The very first step is to break down the complex problem that you have.

25
00:01:48,080 --> 00:01:48,860
The complex.

26
00:01:50,930 --> 00:01:52,730
Into simpler

27
00:01:55,310 --> 00:01:56,240
stuff problems.

28
00:01:57,680 --> 00:02:03,950
So so our complex problem right now is that we want to find all possible path from the start node to

29
00:02:03,950 --> 00:02:09,890
the gold node so we can simply break this down to instead trying to find a path from the neighbor node

30
00:02:09,890 --> 00:02:11,360
to the start node, pick a gold node.

31
00:02:11,570 --> 00:02:14,840
So this is a smaller part or smaller part that we need to find.

32
00:02:14,960 --> 00:02:18,470
Then the original problem that we had that we were discussing earlier.

33
00:02:18,890 --> 00:02:23,990
So let's break this down to a simpler problem so we can access the neighbor nodes, the start node,

34
00:02:24,230 --> 00:02:33,710
by simply saying for node in graph file thing in the start key and then accessing all its keys, which

35
00:02:33,710 --> 00:02:36,260
are basically all the neighbor nodes to the stock note.

36
00:02:36,620 --> 00:02:42,260
So we trade over all the neighbor nodes and now instead of trying to find a path from the start node

37
00:02:42,260 --> 00:02:45,650
to the goal node, we recursively call the get pass function.

38
00:02:48,040 --> 00:02:53,980
Good boss function and boss in a graph as the first argument, and instead of the start node we now

39
00:02:53,980 --> 00:03:00,430
pass in the node that is the neighbor node, the start node and and node, and then we passing the buck.

40
00:03:00,880 --> 00:03:05,440
So basically what we are doing right here is that instead of trying to find a path for all possible

41
00:03:05,440 --> 00:03:10,510
path from the start to the goal node, we are now trying to find a path from the neighbor node to start

42
00:03:10,510 --> 00:03:11,740
node and the goal node.

43
00:03:11,920 --> 00:03:14,290
So this is how recursion for steps works.

44
00:03:14,530 --> 00:03:18,340
But this is recursively calling a simple case of the original problem.

45
00:03:18,850 --> 00:03:23,350
So once we call this dysfunction, what would happen when this function gets called?

46
00:03:23,710 --> 00:03:28,810
So what we want to do is to simply save the information of the path that we have just listed in all

47
00:03:28,810 --> 00:03:32,740
those recursive calls, because we are leading up to that go node.

48
00:03:32,980 --> 00:03:36,460
So basically, we are leading up to the path that leads up to that goal node.

49
00:03:36,670 --> 00:03:39,250
So we want to save this information in the path.

50
00:03:39,520 --> 00:03:44,460
And that can be done by writing path plus path, but is equal to Path Plus Star.

51
00:03:44,620 --> 00:03:50,770
So basically all the norms that we have visited up until the final node is compose composes us that

52
00:03:50,770 --> 00:03:53,040
the final part that leads up to the good note.

53
00:03:53,530 --> 00:03:56,500
So this fills up the path that leads up to the goal node.

54
00:03:57,040 --> 00:04:01,540
And now we need to address the second condition or the second step of the recursive.

55
00:04:01,810 --> 00:04:07,990
Because in algorithm and the second step is that we to define the simplest case or the base condition.

56
00:04:08,650 --> 00:04:09,490
So let's right here.

57
00:04:10,570 --> 00:04:15,580
Define the simplest skills for this particular algorithm.

58
00:04:15,880 --> 00:04:20,020
So the algorithm is to get past what would be the simplest case for this particular function.

59
00:04:20,320 --> 00:04:25,030
The simplest case would be that we were trying to find a path from any node to itself.

60
00:04:25,510 --> 00:04:27,520
So trying to find a path from a node.

61
00:04:27,790 --> 00:04:32,710
So we simply return empty if we are trying to find a path from node to set.

62
00:04:33,070 --> 00:04:37,840
But because this function can get called recursively, we need to return the information of the path

63
00:04:37,840 --> 00:04:45,790
that we have been through previously and that can be done by simply writing if Port Authority, if part

64
00:04:45,820 --> 00:04:47,530
is start equal, equal to.

65
00:04:47,530 --> 00:04:51,370
And so basically we are trying to find a path from any node to it.

66
00:04:51,370 --> 00:04:53,080
So then we simply return.

67
00:04:53,470 --> 00:04:54,550
This is the basic condition.

68
00:04:54,970 --> 00:05:00,910
We return the list that includes the path, so we return the path that we have just found.

69
00:05:01,300 --> 00:05:08,440
So basically if we, if we call this function with any node with itself as the path is initialized empty,

70
00:05:08,440 --> 00:05:09,910
so this will return an empty list.

71
00:05:10,210 --> 00:05:16,030
But if it was already turning and calling the recursive call, this will basically return the port that

72
00:05:16,030 --> 00:05:17,920
was leading up to that particular note.

73
00:05:18,820 --> 00:05:21,940
Now we need to address the base or the boundary condition.

74
00:05:22,180 --> 00:05:27,910
Now the boundary condition is what would happen if the start node that we are not writing on does not

75
00:05:27,910 --> 00:05:29,160
exist in the graph case.

76
00:05:29,500 --> 00:05:34,690
So if it does not exist, we simply don't need empty list because there's no path up until that node.

77
00:05:35,350 --> 00:05:41,290
So now that we have addressed both this condition or all the steps of recursion, the final step is

78
00:05:41,500 --> 00:05:47,990
to simply return the information from the simplest case and try to go back and solve this the previous

79
00:05:48,130 --> 00:05:50,650
problems leading up to the original problem.

80
00:05:51,040 --> 00:05:56,920
So basically we return this information when we use the simplest case of the recursive call, and then

81
00:05:56,920 --> 00:06:01,450
we return the information right here where we have to perform the original call.

82
00:06:01,690 --> 00:06:03,760
And this will be saved as new bots.

83
00:06:04,330 --> 00:06:06,910
So this new path gets returned to the user.

84
00:06:07,150 --> 00:06:12,250
And once this gets returned, we have now the path that leads up to our start node, to the goal node.

85
00:06:12,670 --> 00:06:15,250
But as I mentioned, it's a blind search algorithm.

86
00:06:15,580 --> 00:06:19,180
This will go on until it finds all possible path to the goal.

87
00:06:19,840 --> 00:06:22,750
So that can be done by simply writing here.

88
00:06:22,990 --> 00:06:23,920
So first means right.

89
00:06:24,250 --> 00:06:28,000
We say here that this was the third step when we returned the new parts.

90
00:06:28,600 --> 00:06:29,530
This was third step.

91
00:06:29,860 --> 00:06:31,150
So go back.

92
00:06:32,800 --> 00:06:38,950
Once we get the output of our function calls that we have called recursively, we go back and solve

93
00:06:39,730 --> 00:06:43,420
previous legal sub problems.

94
00:06:43,960 --> 00:06:49,480
So we tried to part solve the previously called sub problems because we now have the output, all those

95
00:06:49,480 --> 00:06:50,200
sub problems.

96
00:06:50,650 --> 00:06:57,460
So once we have this, we can now store all this information and start inside a complete list to store

97
00:06:57,460 --> 00:06:59,470
all possible parts from start to end.

98
00:06:59,800 --> 00:07:05,020
So now we create an empty list that will store all the possible paths to the start, nor to the gold

99
00:07:05,020 --> 00:07:05,290
node.

100
00:07:05,500 --> 00:07:11,170
So this is just a part we need to store all the possible bots that can be done by simply saying for

101
00:07:11,170 --> 00:07:18,700
p in new parts that we have found, append these new parts to our total bot and that can be done by

102
00:07:18,700 --> 00:07:21,370
writing auto foster apparent the p.

103
00:07:21,820 --> 00:07:27,850
And finally once we have iterated over all the neighbor nodes to have a start node and find all the

104
00:07:27,850 --> 00:07:35,140
possible parts, we finally done all the parts, all the possible path to our goal node.

105
00:07:35,590 --> 00:07:41,890
So this completes the get pass function of our DFS algorithm for the case of our blind search algorithm.

106
00:07:42,460 --> 00:07:45,970
Now we need to test it to see whether it is doing its job or not.

107
00:07:46,970 --> 00:07:47,510
Until then.

108
00:07:47,870 --> 00:07:48,380
Thank you.

109
00:07:48,650 --> 00:07:48,890
And.

110
00:07:48,890 --> 00:07:49,190
But.