1
00:00:03,950 --> 00:00:06,350
Here we are at the business end of the schools.

2
00:00:06,650 --> 00:00:10,280
We are planning now what is part planning?

3
00:00:10,640 --> 00:00:17,690
Part planning in simpler terms is estimating apart from a start to a goal go in robot navigation.

4
00:00:17,720 --> 00:00:22,520
This amounts to the set of states that a robot needs to achieve to reach its goal.

5
00:00:23,060 --> 00:00:28,550
These states can be the position and orientation in the respective animation space.

6
00:00:29,270 --> 00:00:35,240
For example, in our case, there are several roles that the robot would take, but path planning algorithm

7
00:00:35,240 --> 00:00:39,110
will explicitly only find the path that leads to the maze exit.

8
00:00:39,870 --> 00:00:43,330
Now let us talk about the different types of path planning algorithms.

9
00:00:45,530 --> 00:00:47,960
So there are two types of path planning algorithms.

10
00:00:47,970 --> 00:00:53,870
Starting with the first type, there is the grid based path, then it's the grid based partners finds

11
00:00:53,870 --> 00:00:57,380
a path based on the minimum travel goals of a grid map.

12
00:00:58,350 --> 00:01:01,740
Now because a proper grade is maintained for any case.

13
00:01:02,220 --> 00:01:06,240
So this makes it impractical for higher dimensional cases.

14
00:01:07,840 --> 00:01:10,030
Also because a grid is maintained.

15
00:01:10,600 --> 00:01:14,200
This means that we are most more than likely to find a solution.

16
00:01:15,270 --> 00:01:23,110
About the example, algorithms that are grid based path planners are DFS and DFS and shortest path finding

17
00:01:23,110 --> 00:01:25,840
algorithms like Dijkstra and stuff.

18
00:01:26,980 --> 00:01:33,610
The second type of planning algorithms are sampling based venues, unlike the grid based path that is,

19
00:01:33,850 --> 00:01:37,030
these two cells by randomly sampling points.

20
00:01:38,070 --> 00:01:45,600
So no grade is maintained and the traversal is not based on coordinates but rather on the basis of randomly

21
00:01:45,600 --> 00:01:48,720
sampled point that satisfy a given criteria.

22
00:01:49,320 --> 00:01:54,540
That criteria is that this shouldn't be on the obstacle and are within the reasonable distance.

23
00:01:55,470 --> 00:02:01,470
So because nobody's maintained this makes it suitable for both low and high dimensional cases.

24
00:02:02,430 --> 00:02:07,740
That's providing us an impression, or should I say, a rather more practical solution?

25
00:02:08,550 --> 00:02:12,780
Here I mentioned that we've got an efficient solution, but this came at a cost.

26
00:02:13,140 --> 00:02:19,500
That is, that we may fail to find a solution if it only ran for a finite amount of time.

27
00:02:20,340 --> 00:02:27,120
The example algorithms that are sampling based partners are already and are already starting now.

28
00:02:27,120 --> 00:02:29,290
Which type of algorithms are we going?

29
00:02:29,310 --> 00:02:31,050
All depends on our case.

30
00:02:33,410 --> 00:02:39,860
So the case that we have is that we have performed to degrade mapping of Mars in the previous step for

31
00:02:39,860 --> 00:02:44,150
the occupancy grid, as that was a low dimensional case.

32
00:02:45,160 --> 00:02:48,250
So the great miss mapping is the go to choice here.

33
00:02:49,720 --> 00:02:51,370
For the goals that you want to achieve.

34
00:02:51,580 --> 00:02:56,680
There are two goals that you want to achieve in this particular module, starting with the first goal.

35
00:02:56,740 --> 00:03:01,990
That is, we want to find the first available path from the start to the main exit.

36
00:03:02,650 --> 00:03:08,770
This is suitable for the case when we are only looking to find a path and not the most optimal one.

37
00:03:09,770 --> 00:03:14,510
Also we have an unweighted graph meaning traversal from any node.

38
00:03:14,900 --> 00:03:19,790
All different nodes carry equal weight in the example algorithms.

39
00:03:20,840 --> 00:03:29,510
For the fourth finding algorithms are DFS and BFS and will be implementing the DFS algorithm and BFS

40
00:03:29,510 --> 00:03:32,450
algorithm will be left for the students to implement.

41
00:03:33,580 --> 00:03:38,710
The second and the last thing that you want to achieve are the shortest path that both planners.

42
00:03:39,660 --> 00:03:45,420
These, as the name suggests, are used to retrieve the shortest part from the given start to the means

43
00:03:45,450 --> 00:03:45,810
exit.

44
00:03:47,020 --> 00:03:48,070
These are suitable.

45
00:03:48,460 --> 00:03:51,220
Finding the shortest path is a requirement.

46
00:03:51,610 --> 00:03:58,330
Also we have the vertical graph available, meaning traversing from any node towards distant nodes carry

47
00:03:58,340 --> 00:04:04,450
different British, so we would know which reversal is the most optimal choice.

48
00:04:05,200 --> 00:04:10,090
The example algorithm for shortest path path planners are distraught.

49
00:04:11,120 --> 00:04:12,140
And a star.

50
00:04:14,490 --> 00:04:15,900
So let's implement them.