Explore How AI Agents Navigate Driving Directions

0:07<v ->Hello and welcome.</v>

0:09In this first skill

0:11we're gonna talk about AI and machine learning,

0:13which is part of a group of skills on AI

0:15and machine learning.

0:16But in this first one, we're gonna talk about

0:19how AI agents navigate driving directions, right?

0:22In some sort of a map or a terrain or an environment.

0:27But before we talk about that,

0:29let's take a look at everything

0:30that we're gonna learn in this skill.

0:33So first we're gonna talk about machine learning,

0:36and more importantly, what is machine learning?

0:38And that's because machine learning

0:40can be all kinds of things.

0:41Well, it's definitely part of AI.

0:44And it's part of other sort of domains

0:48such as deep learning, right?

0:49So these are just abbreviations for now,

0:52but that's what we're gonna talk about in this first video.

0:55What is machine learning?

0:56And also how does it apply to data science?

0:59Because data science and machine learning are very related.

1:02And so I'm gonna talk a little bit

1:04about how all of that works together.

1:07And then we're gonna jump into a game

1:10that's called Grand Search Auto.

1:14And this game is just,

1:16imagine that we're just designing a game

1:19and we're tasked with the logic

1:21on how agent can navigate this, right?

1:23So that's where the AI agent comes into play.

1:26And we'll talk more about this.

1:27And so this is just an opportunity for us

1:30to talk about this AI agent

1:32in the context of this game, right?

1:35And this game is just a fictitious game

1:37that we're just sort of designing.

1:39And then we'll dive a little bit deeper

1:40into this Grand Search Auto

1:42and start to explore different AI concepts.

1:46So first, we'll explore the frontier.

1:51And this frontier, it's just a concept.

1:53A data structure that we'll talk about.

1:55And it's a way of organizing all the options and states

2:00or basically choices that an agent has to make.

2:03For example, am I gonna make a right?

2:05Am I gonna go forward? Am I gonna make a left?

2:07Things like that.

2:08So that's what the frontier is about.

2:12And then we'll jump into some algorithms.

2:15So first we'll jump into Depth First Search,

2:21and that's just an algorithm that we're gonna use

2:23to navigate this environment.

2:26And then we're gonna do this other algorithm

2:28called Breadth First Search.

2:32And so they're very similar.

2:33These are the first two algorithms

2:34that we're gonna talk about.

2:36And then we're gonna finish things off.

2:37I'm running outta space here, but we'll go to number six.

2:40And this is gonna be about greedy algorithms

2:43and something called the A Star search, right?

2:47And that's how we're gonna finish these algorithms

2:49talking about them.

2:50And so this, this, this and this,

2:53these are all the algorithms that we're gonna dive into

2:56that really are gonna help our AI agent

2:58navigate this game environment, right?

3:02So a lot of cool stuff

3:03that we're gonna take a look at in this skill today.

3:06All right, so I hope you're excited.

3:08I know that I am.

3:09I've been waiting a long time to really make the bridge

3:12between data analysis, data science,

3:14and now machine learning.

3:15But the best way to start all of this

3:17is to really dive into AI,

3:19and that's what we're gonna do in the first video coming up.

3:23And until then, I hope this has been informative,

3:25and I'd like to thank you for viewing.

0:07<v ->Welcome back.</v>

0:08In this first video, we're just gonna talk about what is AI,

0:12and also how does it fit

0:14into data science and data analysis?

0:17For example, it's a very common path

0:18to go from data analysis to data science

0:21and then into machine learning.

0:23It's a very natural progression,

0:25and we'll talk more about that in this first video.

0:28Okay, so here it is.

0:30What is artificial intelligence?

0:32And more importantly, how does that fit

0:34into data analysis, data science, and now machine learning?

0:38And we'll talk more about deep learning,

0:40which is a subset of machine learning.

0:43Okay, so here we can clearly see what's going on.

0:46And here we have basically AI,

0:49and this is the larger domain, right?

0:52So, it's basically contains other things,

0:55and we're just gonna really talk about

0:57machine learning and deep learning,

0:58even though there are other subsets or sub-domains,

1:02right, to AI.

1:03But for the scope of this course,

1:05since we're talking about machine learning,

1:07we're just gonna talk about AI,

1:09machine learning, and deep learning,

1:11and how they fit into each other, right?

1:14But first, let's talk about data analysis.

1:16So, here we have data analysis,

1:18which is a very common place to start.

1:20And I would say

1:21this is where people would just historically work

1:24with numbers, and spreadsheets, and things like that.

1:27And this has changed dramatically

1:30as the advance of computers.

1:31So, as the power increases,

1:33so does the roles and the ability.

1:35So, this actually turned into data science,

1:38but there was no data science.

1:40So, the way it goes

1:42is that data science was actually a term invented

1:46to woo a data analyst who was really thinking of themselves

1:51as more of a scientist.

1:52And why is that?

1:53Well, here we're working a lot more with statistics

1:57and we'll work a lot more, there's a lot more math, right?

2:00So, you can get away with data analysis

2:03without really getting too far into statistics or math.

2:07And then, later on, as you take those two,

2:09well, basically statistics and math is,

2:12you can think of it as machine learning to a certain degree.

2:16Some people call it statistical learning,

2:18and that's a subset of machine learning

2:20or it's a little bit different.

2:22But if you may have heard those terms,

2:24so they're sort of related.

2:26And so, that's why we have machine learning,

2:27and then we'll talk about deep learning last.

2:30So, what is the difference?

2:31With data analysis, we're basically taking data,

2:34cleaning it, manipulating it,

2:36and then making some sort of an analysis

2:38and then presenting that information.

2:40Data science is similar

2:41except that we're again, more math, more stats,

2:45and there's more programming involved.

2:47This is generally speaking, of course.

2:49And then, where does machine learning turn into that?

2:51Well, to really dive into that, let's talk about AI.

2:56So, what are some examples of AI?

2:58So, we say maybe you've heard of ChatGPT,

3:02and that is something called a large language model.

3:07Right, and that's,

3:08you could say that's part of AI, right?

3:10They can summarize, translate text,

3:12predict future words in a sentence.

3:15We're just looking at AI

3:17as equivalent to human intelligence, right?

3:21That's what it's called, artificial intelligence.

3:22So, the takeaway here

3:23is that anything that a computer can do

3:27that are like human tasks

3:29that would normally require a human to perform,

3:32then that's what AI is, right?

3:33That's like the most common explanation for AI.

3:36And one of the examples is this ChatGPT,

3:39which is very human-like,

3:40you can actually have a conversation with it, right?

3:43So, what else?

3:44How about when you talk to your phone

3:45and it sort of gets it?

3:46Well, that would be Siri, right?

3:47Which now Siri seems not very intelligent

3:50compared to ChatGPT, it's kind of,

3:54but I'm sure that's gonna change very quickly.

3:56And driving directions have AI in the backend also, right,

4:00giving us optimal routes.

4:01So, let's,

4:02you know, we want to go to this destination,

4:05we start here,

4:07the fastest route is not gonna be the straightest route

4:10because there's some traffic, right?

4:12So, things like that,

4:13so human-like intelligence.

4:16So, now let's focus on the differences.

4:19All right, so what is AI, right?

4:20We really haven't dived into that just yet,

4:23but in short, it's about teaching computers to be smart.

4:26So, that might sound a little silly, but it's true.

4:29Computers are powerful but not necessarily smart,

4:33they don't know what the difference

4:34between making a left or right is.

4:37We have to tell them that and give them like rewards

4:40or some sort of information

4:42so that they can make these decisions,

4:44but they can't do that on their own, right?

4:46So, that's kind of the first part.

4:48But since they are powerful,

4:50then we can leverage that, right,

4:52and we can make them smarter.

4:54And that's the takeaway.

4:55So, they're not smart,

4:57but they're so powerful that we can make them smarter.

5:00So, AI is a broader field

5:03that focuses on creating machines or systems

5:06that can carry out tasks

5:08that normally a human would have to carry out.

5:11For example, in early AI,

5:13a lot of these were rule-based

5:14or expert systems that required human

5:17and expertise to enter these things.

5:20So, that took a long, long time.

5:22So, we had AI, but you would basically take expert knowledge

5:26and then encode that in a way

5:28that the computer could use to become smarter.

5:32So, it takes a long, long time.

5:34And one of the advantages of machine learning

5:37is that it can actually make that a lot quicker

5:39because the computer can do a lot of those repetitive tasks

5:43because it's powerful.

5:44And as a result, then it's smarter, right?

5:46So, that's kind of like the takeaway for now,

5:49and we're gonna keep building on this.

5:51Okay, so we know that these human expertise

5:55that got encoded as rules or heuristics,

5:59and this is exactly what we're gonna demo in this skill.

6:02All right, so instead of doing things

6:03programmatically or even manually,

6:06we're going to leverage machine learning, right?

6:09So, machine learning is all about learning from data

6:11and making predictions without being programmed.

6:15And that might seem pretty amazing, and it is.

6:18So, we're leveraging power

6:19to basically get better and better and better.

6:23For example, this is a famous story of machine learning.

6:27One of the pioneers wasn't great at checkers.

6:31We're gonna talk more about this person,

6:32and just to give you a story though,

6:34and basically they programmed a computer

6:38to play a game of checkers,

6:41and it played 10,000 times

6:43and got better and better and better and better.

6:45So, that's how it got smarter.

6:47You see, it had to play the game 10,000 times

6:49and it used different algorithms

6:51to become very, very accurate,

6:54and that's machine learning.

6:55So, through this power of iteration,

6:57we can actually get this sort of intelligence.

7:02So, what are some examples, right?

7:04So, we have spam filters,

7:06so word probability such as buy now, or like money,

7:09or I don't know, like prints,

7:12you know, those emails

7:14or like buy one, get one free, things that sound spammy.

7:17Well, it can filter that out for us, right?

7:19And then how about Siri?

7:22We talked about Siri

7:23is not as smart with ChatGPT in the mix,

7:25but there's also Alexa,

7:27which suffers from the same problem,

7:29and Google Assistant.

7:31And what's interesting is that all of these companies

7:33are really just running

7:35to try to catch up to ChatGPT, right?

7:38So, ChatGPT just really changed the game

7:41as far as AI in saying, "Hey, AI can do this."

7:44And now all of these services,

7:46which used to be really cool at one time,

7:48they're not incredible anymore.

7:51So, that's going to sort of change pretty quickly,

7:55right, because you need to keep the customers happy

7:58or it's gonna be a problem.

8:00So, what else?

8:01Well, medical diagnoses,

8:03that is a really powerful one, right?

8:05There's gonna be a lot of advances in medicine.

8:07So, how is medical diagnosis even a thing, right?

8:12Well, what it can do

8:13is look at many thousands,

8:16tens and hundreds of thousands of images

8:19and then say, "Well, these images we know have,

8:22are sort of something that we need to look at, right?

8:26This could be dangerous,"

8:27or some things that are, "Hey, this is totally fine."

8:30And that repetitive sort of iteration

8:33makes them very, very smart,

8:34and then get very accurate

8:36and make predictions or detect anomalies

8:39or even cancer or other diseases, right?

8:43And that's something very, very helpful.

8:45Even surgery.

8:47So, there's computers now using machine learning

8:49that perform surgeries much more accurately

8:52than a doctor, right?

8:54They make a lot mistakes.

8:56So, this is a pretty exciting time, there's a lot happening.

8:59All right, so that's all about machine learning,

9:02so what about deep learning?

9:04Well, deep learning is a subset of machine learning

9:07and it uses networks, all right?

9:09So, that's the main difference.

9:11And these networks, interestingly enough,

9:14were inspired by the brain.

9:16So, that's where this is coming from.

9:18There's an interesting white paper

9:20that really talks about the human eye

9:22and that sort of started to kick off

9:24these really, basically deep learning has to do with that.

9:27So, there's a lot more information,

9:29we're just scratching the surface.

9:31But basically, we're gonna talk about these networks

9:33and make a difference or a distinction

9:34between machine learning and deep learning.

9:38So, this is a neural network,

9:42or you can write it as NN, right?

9:45And this is great for image recognition, speech recognition,

9:48natural language processing, things like that.

9:51And then we have RNN,

9:54which is a recurrent neural network,

9:56and that's great for sequences or time series data,

9:59such as making predictions

10:01and even machine translation, right?

10:03Let's say you wanna translate from Python

10:05to some other language,

10:07you can do that with machine translation.

10:09And then, there's convolutional neural network,

10:13which is great for object detections and things like that.

10:15And there's also transformers,

10:17which is very popular with large learning models,

10:21large or large language models, LLM, right?

10:25So, basically ChatGPT.

10:27So, this is basically deep learning, right?

10:30You have these networks,

10:32these various networks like neural networks,

10:34recurrent neural networks, convolutional neural networks,

10:38transformers, and things like that.

10:40And again, if you've seen deep fake videos,

10:44that's deep learning,

10:45and it uses these sort of algorithms

10:47to achieve these amazing results.

10:50All right, that's about it for this video.

10:52We've talked about a lot of amazing stuff,

10:55but don't worry, we're gonna unpack this in this skill.

10:58So, by the end of this skill,

10:59you'll have a good understanding of how an AI agent

11:02can navigate driving directions, right?

11:05Because if you don't know how that works,

11:07wow, it's kind of like, well, it's hard to even imagine.

11:11I guess that's what I'm getting at.

11:13All right, I'll see you in the next video.

11:14And until then, I hope this has been informative.

11:17I'd like to thank you for viewing.

0:06<v ->Welcome back, in this video,</v>

0:09we're gonna really just unpack a lot of these concepts

0:12and we're gonna do so thinking about a video game

0:14and I think that's probably the easiest way.

0:16And so let's say that we've created a video game

0:19or we work for a company

0:20and they've created a video game

0:22called Grand Search Auto.

0:24And it has some sort of player,

0:27or I guess like an AI agent in this case

0:30that's gonna have to navigate that environment

0:33and find the shortest directions

0:34to get to the goal

0:37which is gonna be an X, right?

0:38So a starting place and then an X of destination.

0:41And this AI agent is gonna have to figure out

0:43how to navigate that.

0:45So why are we doing this?

0:46Well, think about it.

0:47How would you program an AI agent

0:49to do this, right?

0:50If you think about, if you have

0:52a Python programming background, well,

0:55you could start trying to create functions

0:57and like logic.

0:59So if you get to a point

1:01and you can make a left, right, straight, right?

1:03We're thinking about it programmatically.

1:05So how would we do that when we're working with AI?

1:08And what are the algorithms

1:09that are available to us

1:11when we're working with these kinds of problems?

1:14That's what we're gonna check out.

1:17All right, so here is our AI game.

1:20So we're gonna imagine that we've created

1:22or we're working with a company

1:24that has an AI-powered game

1:25where this AI agent has to navigate a city in a car

1:29and find a particular spot, like an X, right?

1:32Like our goal.

1:34And that can represent a destination or like a goal

1:37or even a prize of some kind, right?

1:39So it's a game, it is gonna be fun,

1:41but I think the cool part is like, wow,

1:44try to imagine it right now

1:46before we go further, pause it.

1:48How would an AI agent even do this

1:50and think about functions and doing it programmatically.

1:53But let's go ahead and unpack that.

1:55Okay, so here's one part of the game,

1:57and in this case, we want to find this red X, right?

2:00Right here and that's our goal.

2:02And this could be a destination or a prize,

2:04but for us, this is gonna be just the goal, right?

2:07Just to remind you,

2:08the game part is being developed

2:10in the game department

2:11and we're just figuring out the logic part.

2:13So like how did the AI agent will navigate

2:17the driving directions to find this X?

2:20And I guess we could start somewhere like here, right?

2:22And then, you would have to basically go up

2:24and at every decision point, especially here, right?

2:28Because there's nowhere you could go,

2:30you just have to go straight.

2:31But here, you could either go this way

2:33or you can go this way.

2:34But first, what kind of problem are we dealing with?

2:37And to answer that question,

2:39that is going to be a search problem.

2:43So even without knowing

2:44what the game will look like when it's done,

2:47we can clearly see that this is a search problem, right?

2:50Because we start here

2:51and we want to find this,

2:53so we're searching for that red X.

2:56So the agent has to search and find that red X

2:59and keep in mind that the AI can solve

3:01many kinds of problems, right?

3:04But in this case, we're just thinking about a search problem

3:07and how to find that red X, right?

3:10Especially when we're having decision points

3:12like this, right?

3:14For example, you can clearly see

3:15that this is gonna be the fastest route

3:17and this is gonna be unnecessarily

3:19add this whole section to it, right?

3:22So this is going to really also talk about optimization

3:26because you want the best route,

3:28you don't want just any route, right?

3:30There are some routes where, for example,

3:33let's say you keep on going in circles

3:36and that could happen like this.

3:39You can go down here, you decide to go this way.

3:42You go over here, you decide to go this way.

3:45You go over here,

3:45and then it just ends up going

3:47in this forever loop.

3:49So we really have to keep an eye on the AI

3:51and write logic and use algorithms

3:53to allow us to search in a way

3:55that avoids these kinds of things.

3:58And the goal is so that we can play the game.

4:00So let's dive into this a little bit further.

4:02So first, let's talk about the AI agent.

4:04So this is just a picture that I drew.

4:06It's not an agent like that,

4:08but you know, I thought how am I gonna draw it?

4:11So this is a representation of our agent,

4:13which starts right here.

4:14And as we talked about,

4:15we have a goal and that's the goal.

4:17So we were gonna keep things simple

4:19so we can focus on the steps, right?

4:22Because it can get very complicated.

4:24So how is the AI gonna solve this search problem?

4:29But before we dive into that,

4:30let's define what an agent is in the first place.

4:34Again, this is the concept that we're using, right for AI.

4:37So in our case, an agent is driving a car

4:41and searching for the X, right?

4:43But an AI agent could also be playing a game

4:46of chess or tic-tac-toe.

4:48So it doesn't have to be just a search problem,

4:51it could be tic-tac-toe, right?

4:54Or it could be a game of chess,

4:58checkers or whatever.

5:00It can be image recognition and so on and so forth.

5:03In this case, we have a game

5:05and the contact is how do we start

5:07and then find that goal, right?

5:09And we want this agent to be able to navigate that goal.

5:12And here we're gonna talk about state.

5:15So you might already have some understanding of state,

5:17but if you don't, it's not like the state of Florida,

5:20we're just talking about a configuration file.

5:23So let's jump into this.

5:25So the state here,

5:27and generally speaking is a way to communicate

5:29what the environment is for the agent.

5:32Otherwise, how could it know what's happening, right?

5:35So you need something like that, some state.

5:38So we can communicate this

5:39using a configuration of the agent

5:41in the environment, right?

5:42So ultimately, that's what we're talking about.

5:45State is a configuration

5:46of both the agent and the environment.

5:50And so this could be one representation of the state

5:52because you can see they have that agent here

5:55and there's the goal

5:57and here's some sort of a path,

5:58and this is exactly where they are right now.

6:01And that gives you basically configuration

6:03of the agent and the environment.

6:05All right, so pretty straightforward there.

6:08And here, we need some additional information.

6:11And this is pretty obvious

6:13because you're going to be

6:15in a sort of initial state, right?

6:17So this is your starting state,

6:19plus you have some sort of actions,

6:22and this is where our game begins

6:24and the actions that are needed

6:26to get to this X, right?

6:28So we can express all of this as a function, right?

6:31But first, let's talk about these actions.

6:33So we have an initial state plus actions,

6:36which are options that the agent can make in a state.

6:40So here, this is the first one,

6:43it can go down to this point.

6:44And then, then we have two choices.

6:47So these are the actions right here.

6:49Those are the two actions plus the initial state, right?

6:52So since we're talking about initial state,

6:55then we can need to back all this up and say,

6:59okay, this is the initial state and the actions available,

7:03we can go straight.

7:04So that's really the initial state.

7:06If you keep adding that

7:08and then you get to that decision point,

7:10that's gonna be something else.

7:12So just we wanted to make that distinction.

7:15So let's check out what this something else is.

7:20But first, let's check out the function.

7:23So I said that we can represent these as functions, right?

7:26So actions are functions.

7:28So let's say that this is our function,

7:30which is an action or actions,

7:33and it takes in some sort of a state, right?

7:36And it returns the actions available.

7:39So return the set of actions

7:41that are available in state s, right?

7:45So that's how we think of this or express this

7:47as a function.

7:48So the actions here available to the agent

7:50depend on the environment state,

7:53but how can the agent keep track of these changes?

7:56So how do we keep track of that?

7:57And that would be the transitional model

7:59that I was talking about earlier.

8:00So we have that initial state

8:02and this transitional model

8:04contains state results

8:06from performing an action in a state.

8:09So here's the result and it takes in state

8:14and here, action.

8:16And then, it returns the new state.

8:19So we have that initial state, right?

8:21And then, we have a transitional model, right?

8:24And then, it takes in a state in an action.

8:26And then, you get this new state, right?

8:29These are just abbreviations.

8:30So you can see how we're just going down

8:32sort of like this sequence, right?

8:34Initial state, transitional model,

8:37and then you get another transitional model,

8:39and another transitional model

8:40until you get to the goal.

8:42So visually, we can represent this like this,

8:45but of course, normally it would be numbers, right?

8:47It would be encoded.

8:49So here's a result

8:50and this is what the state would look like

8:52and this is what the action is available at that time

8:54because we're starting here

8:56and the only action really is just to go forward.

8:58And so here we have this representation

9:02and here the result is a new state

9:05and many new states equals a state space.

9:08So let's talk about that.

9:09So here's a result and here's the state

9:11and that action that we took.

9:13And when you do that,

9:14you'll get this new state

9:17and that new state really has that action taken.

9:19And then, we're gonna have new actions that we can take.

9:23So in this case, we can go this way.

9:25Or in this case, we're gonna make a left or right.

9:27So the state space is a set of states

9:31from the initial state, right?

9:32So you have the initial state,

9:33and then you can have the bunch of these states,

9:36and that collection is called a state space, right?

9:40And when you're thinking about this state space,

9:42instead of trying to show each one as this image,

9:45which I just did for convenience and educational purposes,

9:49we can represent them as individual state

9:52with arrows, right?

9:53And that would look more like a graph, right?

9:57If you have these options,

9:58you would have these arrows,

10:00and that starts to look like a graph.

10:02And that starts to make more sense

10:03because having just pictures, well,

10:05you'd have to create a program to read the pictures too.

10:08So why not use something

10:09that the computer can understand?

10:11So that's what encoding is, right?

10:13You're taking something and turning it into a data type

10:16that the computer can understand.

10:20And so here it is,

10:21a visual representation of a graph of nodes

10:25which reveals the steps needed to find the goal

10:28and all of the relationships for other nodes,

10:31which don't lead to the goal, right?

10:33For example, we can say,

10:35all right, let's go here and go down.

10:37And then now, we can go down.

10:39So that's it.

10:40There's only choices that we have.

10:42Now we can only go this way,

10:44and then it's a dead end.

10:45So we went the wrong way.

10:47All right, let's try this one instead.

10:49And then, we go from here to here

10:51and same thing, dead end, right?

10:53So at each stage, right?

10:55We can ask,

10:56is this the state the goal? No.

10:59Is this the goal? No.

11:00Is this the goal? No.

11:01So on and so forth.

11:03And here, we can represent

11:05this sequence of actions, right?

11:08That actually leads to the goal.

11:10And then you can say, I found the goal,

11:12because you're checking

11:13each sort of instance.

11:16So let's break down what we're looking at here.

11:20So these, all of these purple dots are nodes,

11:23which equals one state, okay?

11:26And then these edges,

11:28which the arrows that connect these nodes,

11:31would be the action, right?

11:33And then, so this is like a state,

11:34and then you can see actions,

11:36and that's what is stored

11:38inside of each one of these, right?

11:41And those transitional models

11:43to a certain point.

11:45So we have a starting s, starting node,

11:48and each node represents one state

11:50and the arrow is depicting

11:52the relationships or connections,

11:54which are in this case an action.

11:56And this is formally referred to as an edge, right?

11:58We talked about that.

12:00So here, each node state can store

12:03each state in actions available.

12:05Finally, when we have a goal state,

12:08we could say, we found it,

12:09this is the destination

12:11and now you can take all of those directions.

12:14And then, that's how many turns it took

12:16to get to that goal state.

12:18All right, so what is a goal state?

12:20And how will the AI agent know

12:23when it reaches that goal state?

12:24'Cause we are just saying it's just checking it, right?

12:27So it's gonna identify the goal state

12:30by comparing each state to the goal state.

12:33So it's basically just a double equals

12:35if you're doing like comparisons, right?

12:39Is this equal that?

12:40If so, then we're done because we found the goal.

12:42So basically, it's a gold test, right?

12:45A way to determine if a state is a goal.

12:47So basically like equality,

12:49but that's not it, there's more.

12:51So what else do we need?

12:53So instead of just any solution,

12:55how about asking the agent

12:57for the best solution?

12:59And that's what we're talking about here, right?

13:01So imagine you need to get to the airport to get, you know,

13:04to your flight on time.

13:05Well, if you go the red path,

13:07it's gonna be super expensive

13:09and you're going to miss your flight.

13:11But if you go with the green arrow,

13:12it's gonna be basically super direct

13:15and that's gonna be the most cost effective, right?

13:18So some cost based on the steps taken.

13:21So we need some way to calculate that.

13:25And so how do we even calculate the cost

13:27of certain routes, right?

13:29So this is a cost function.

13:30How do we even approach creating a cost function?

13:35So here you can see all the steps taken,

13:37but what are the steps?

13:38What's the value for each one of these steps?

13:41And here we can see

13:42that the cost for the distance

13:44might be higher, right?

13:46And I think that would make sense

13:48in the context of directions

13:50because let's say you make a right

13:52and that right until the next right

13:54is a mile or two miles.

13:56So another turn is gonna be a 10th of a mile.

14:00So one is gonna be longer

14:01and the other is gonna be shorter.

14:03So this might be a good reason

14:04to have variable costs, right?

14:06So one route or one turn or one action

14:10is gonna be greater than another action

14:12because it's gonna be much longer,

14:14but this is not always the case.

14:15But I wanted to give you an example of this, right?

14:17Visually, and this sometimes happens,

14:20but what is more common

14:22is a constant cost, right?

14:25Where we're only counting turn

14:27and not distance per turn.

14:29So in this game, we're just counting turns

14:32because it's gonna be a lot simpler.

14:33We just wanna say it took 10 turns

14:37to get to the goal, right?

14:39We're not calculating distance at this time.

14:41If we wanted to calculate distance,

14:42it wouldn't be very difficult to do that

14:44after we've figured out the logic for the game.

14:47And then finally, we have the search problem

14:51where you'll have a path cost function

14:55that tells us how good the solution is.

14:58Okay, so here's our starting state,

14:59we've already seen that

15:01and you see that we have actions that we can take.

15:03So we take some actions

15:05and we keep track of that

15:06with a transitional model

15:08and we're always checking for that goal, right?

15:11Is it the goal? Is it the goal?

15:13Are we there yet? Are we there yet?

15:15And then, we have this cost function

15:17which calculates the path cost, right?

15:19And tells us if this was like very efficient

15:21or very inefficient

15:23and it gives us that optimal route, right?

15:26And that's super important

15:28because the cost function tells us

15:30how good the solution is, right?

15:33So how can the agent keep track of everything?

15:35Well, we talked about that node as a data structure

15:38that keeps track of the state

15:40and the parent or previous state,

15:43and then the actions taken

15:44or the available actions,

15:46and then the path costs

15:47like step by step, right?

15:50How many turns that we take.

15:51And so that's how we are sort of keeping track

15:53of all of this information.

15:55And to sum it all up,

15:57we have this initial starting state,

15:59and then we find this path to get to that goal.

16:02And then, the cost is gonna be all parent nodes, right?

16:06That equals the steps.

16:07So every step that you took, whatever that is,

16:11that's gonna be your cost.

16:15All right, so we're just breaking it down

16:17from a very high level, right?

16:19We're talking about, hey, we have this game

16:21and our job is to figure out the logic.

16:23And then, we're just figuring it out

16:24and that's what we've done

16:26and we're gonna continue this.

16:27And as we get deeper into this,

16:29we're gonna jump into algorithms

16:31such as depth-first search

16:34and breadth-first search.

16:36All right, until then, I hope this has been informative

16:38and I'd like to thank you for viewing.

0:06<v ->Alright, so now that we have a good idea of this game,</v>

0:10let's dive into the logic,

0:11because we've talked about starting points,

0:14goal states, and initial states,

0:17transitional models, and things like that,

0:19but we haven't really talked about

0:21making a left and making a right and things like that.

0:23So more about the logic and step by step,

0:25so let's take a look.

0:27Alright, so we talked about the frontier,

0:30and the frontier is a set of nodes

0:31adjacent to at least one node.

0:33So if you have here a node, and then here's another node,

0:37that adjacent node, so that's the frontier, right?

0:40So the initial state equals the starting frontier, right?

0:43All the agent nodes at the moment.

0:45So this is our starting point,

0:48and we're using this frontier data type

0:50to accomplish this, right?

0:52Alright, so what do we do now?

0:56At this point, we see this sequence.

0:58So this is kind of the logic.

0:59So the first step is this initial state, right?

1:02Which is the starting frontier.

1:04That's all that the agent knows,

1:06and then we go to number two.

1:07If the frontier's empty, then there's, well,

1:10you could finish,

1:11because there's no possible solution, right?

1:13Like there's nowhere to go.

1:15Another way to say that

1:15is like maybe there's a problem, right?

1:17Maybe you can't go for some reason.

1:19So in that case then we'd be done.

1:22Number three, else, right?

1:25Remove the node from the frontier.

1:27So we're gonna go through this one by one,

1:29and then the next step

1:30is if that node state equals the goal state,

1:33then return the directions,

1:34because hey, we found the goal, right?

1:36Remember, we're checking for that goal state.

1:40So that's number four.

1:41And then finally, else expand the node

1:44with the next adjacent nodes, right?

1:46So we're actually traversing these nodes,

1:48and this is part of getting those directions,

1:53and then it repeats, as you can imagine, right?

1:54Not the first one,

1:55because you only have one starting frontier,

1:58but here, once you're on a roll,

2:00you just check over and over.

2:02If the frontier's empty, then there's no solution,

2:05else remove the node from the frontier.

2:07So we're gonna do this together.

2:09And then four, if the node equals the goal state,

2:13then you're done.

2:13You won, right?

2:14You found the goal, so you win the game,

2:16or go to the next level or something like that.

2:19And if four is not the goal,

2:21then five says else expand node

2:23with the next adjacent nodes.

2:26And so we keep doing this over and over, right?

2:28Until we find the goal or there's no solution,

2:31something like that, until something happens,

2:34and that something is gonna be optimal directions.

2:37But we need to figure out,

2:38how do we find these optimal directions?

2:41Well, here we have the frontier.

2:44So this is our graph, right?

2:46So check it out.

2:48And we're starting here, so our frontier is A,

2:51so start with frontier plus initial state,

2:54so that's what it is.

2:55And the directions here

2:56is we're just trying to go from A to E, right?

3:00Which is our goal state.

3:02So number one, start with frontier and initial state.

3:06So that is check.

3:08We've done that.

3:09Number two, it says here,

3:12and just remember that if the frontier is empty,

3:14there's no possible solution, right?

3:17So that's why we went to number three.

3:18Else remove the node from the frontier,

3:21and that's exactly what we've done.

3:23We've taken this A and put it back.

3:25Let's go to number four.

3:28Here we're gonna say,

3:29if the node is a goal state, then you won, right?

3:32But it is not the goal state, so we continue.

3:37Now we're back at the top.

3:38So now we're gonna say

3:40else expand the node with the next adjacent nodes,

3:43and then you repeat.

3:44So I kind of jumped the gun,

3:45so number five, and then you repeat.

3:48So number five is just saying

3:49expand the node with the next one.

3:51So we put A back.

3:53We said A is not the goal, and then we take the next one,

3:56and then we're basically start to cycle again.

4:01So we're at number two.

4:02If there's no possible solutions, then you're done.

4:05Well, there is a possible solution,

4:07'cause either C and D are options, right?

4:09That's what's that's connected to B, so what do we do now?

4:15Now we say else remove the node from the frontier, right?

4:18Because there are possible nodes.

4:21Then we say is it the goal, right?

4:24So if the node state equals goal state,

4:26then you return the directions and you win, but we don't.

4:30That's false, right?

4:32This is false, so we are gonna continue the cycle.

4:36Then here we are at number five,

4:38else expand the node with the next adjacent nodes,

4:41which are these two, right?

4:42So now we have these two nodes in the frontier,

4:46and what's the next step?

4:48Remove a node, so we're gonna remove C,

4:51and at this point, we're just doing this arbitrarily.

4:54Once we have an algorithm,

4:56then we're gonna have some sort of logic behind the choices.

5:01Right now we're just choosing one sort of arbitrarily.

5:05Right, so we remove a node.

5:06We decided to remove C,

5:08'cause we're just doing it arbitrarily at this time,

5:10and then here we wanna check is C the goal?

5:13And the answer is no, so then we would continue.

5:16And then is E the goal?

5:18And the answer is yes,

5:19because this whole time we knew that E was the goal.

5:21That's what we're trying to get.

5:22That's the directions that we're looking for.

5:24And once you get to E and you check for that,

5:27then you're done, right?

5:28You don't have to keep on exploring D or E.

5:30You just saved yourself that time, right?

5:34So this is like how we can do this step by step.

5:38Alright, so we found our goal

5:39and we kind of understand

5:41the very minimal logic that we have in place.

5:44We have this frontier and that we have a sequence, right?

5:48Like a loop that we sort of loop through

5:50after that initial state,

5:52and that's our logic.

5:54So far, we decided to choose C over D arbitrarily,

5:58but as we start to get into the algorithms,

6:00we can actually have some control over that

6:03so that we can set ourselves up for success, right?

6:06So that we can find that shorter distance,

6:09that more optimal route.

6:11Alright, until the next video,

6:12I hope this has been informative.

6:14I'd like to thank you for viewing.

0:07<v ->Now that we've checked out some of the logic</v>

0:09by working with the frontier,

0:11let's ask the question, "What could go wrong?" right?

0:14It was working pretty smoothly,

0:15but in the beginning of this skill,

0:17we talked a little bit

0:18about how the AI agent could make a left, a right,

0:23and a left and kind of get into a circle, right?

0:26Into a loop, and so that's a problem.

0:29So let's take a look at what could go wrong

0:31with the logic or the series of steps

0:35that could get us into a loop.

0:37All right, so what could go wrong? This is gonna be fun.

0:41So first, let's take a look at our graph.

0:43And so how do we keep track?

0:44So we're going A to B,

0:47but if you follow those steps,

0:48you could go back to A and back to B.

0:52Let me show you what I mean.

0:53This could cause just an infinite loop.

0:56Okay, so let's say that we're here

0:58and that's our starting point,

1:00and then we decide to go to B,

1:02but we know that we can go to C and to D,

1:06but how about if we could go back to A?

1:09How about if there was an arrow that said that?

1:11Well, then we could decide to go to A again, right?

1:16From B, you can go to A, C, or D.

1:19How about if we just chose bad luck and chose A,

1:22and then from A, we chose B 'cause that's the only choice.

1:25And then here we have three choices,

1:27and again, it goes to A and then back.

1:29And that's exactly what's happening here.

1:31So this is an infinite loop,

1:33and, well, we don't want to do that.

1:36So how do we keep track of which nodes that we've visited?

1:39I think that's probably the most important part.

1:43In here, we can see that we have the initial state.

1:46This is our sequence.

1:47And then we have an explored set.

1:50So that's how we're gonna keep track, right?

1:53And this way, we know what we've explored.

1:55And then you repeat all of this, right?

1:59So you're always checking that explored set

2:00to make sure that you don't do A again.

2:02So for example, we are here at A, we go to B,

2:06and then from B, we don't go back to A, even though you can,

2:10because we have now visited A.

2:12So that's gonna be part of the explored set.

2:15So as long as we keep track of this,

2:16and this can be right somehow, then you can say,

2:19"Well, I don't want to go back to A

2:21because I've already been there."

2:23And that's how you avoid that.

2:24So let's go through the steps.

2:26So we have that explored step, and then you're gonna repeat.

2:28If empty, we're done.

2:30So it's not empty, so remove node.

2:32Then you remove that node, and then is it a goal state? No.

2:35Then you add that node B, right?

2:39So we've already done all these.

2:40And then, so you want to check the frontier explored set,

2:43and that's when you would check this,

2:45and you would no longer end up

2:47in this sort of recursive infinity loop, right?

2:51And so that's one way to do that.

2:55So keep in mind that the frontier is a data structure,

2:58and then the order in which we add and remove nodes

3:01is super important.

3:03So far, it's been kind of arbitrary.

3:05However, if you want the last thing you add to the frontier

3:09to be the first thing out,

3:11then you'd want to use a data type

3:13that allows that action, right?

3:15So why would you wanna do that?

3:17We're gonna illustrate what happens

3:19when you apply a stack to a search problem, right?

3:21We can apply a stack to the frontier,

3:24and this is gonna be pretty cool.

3:25And you're gonna see why you would want

3:27that last-in, first-out structure, right?

3:31Okay, so here we are. We have the first step.

3:33So we have our frontier,

3:35and now we've added that also to our explored set.

3:38So we won't be making

3:40that sort of cyclical mistake again, right?

3:43So that's first. And then let's go through this together.

3:47So that's the first part. Then we take it out, right?

3:50And we keep that explored set.

3:52We've returned this, and now what are we gonna do?

3:54So we're gonna put the B in there.

3:56So we've removed the A node. It's not the goal state.

4:00And then we check B.

4:01And then say we have these two nodes here, C and D,

4:05and we've already explored A, so we can't go back there.

4:08Okay, so is B the goal? No, it's not the goal.

4:11It's connected to C and D, however. So we can do that.

4:15All right, so we take that out, and then we put C and D in.

4:19However, now that we're using the stack data structure,

4:23whatever goes in last, right?

4:26Let me show you that again.

4:29Last-in, first-out.

4:31So if this one is last in,

4:36then it's gonna be first out.

4:38So just keep that in mind. So what does that look like?

4:40We take that D and then remove it 'cause it's first out,

4:45and then you have F.

4:47And then so you add, "Hey, I've explored A, B, and D,

4:50so now I'm at F, right?"

4:53So we went A, B, D, and now we're here at F.

4:58F is not the goal state, so we go back to C, right?

5:02And what does that look like?

5:03Well, we took F out, put it down here,

5:06and then when we're at C and we go to E, that's the goal.

5:10So we stop right there.

5:12So that's the part of the logic

5:13where you basically stop right there,

5:16and you might be asking yourself,

5:17"What is this algorithm called?"

5:19And it's called Depth-First Search.

5:21And what does that do?

5:22Well, it explores the deepest nodes first.

5:25And we need to take a look at this in a visual

5:28because it's much harder to understand the logic,

5:31but it's really important to go over it first.

5:33And then when we go over the logic visually,

5:35it should totally make sense

5:37when we're looking at directions, right?

5:39And before we close things down,

5:40I want to show you some Python code

5:43that shows you this Depth-First Search.

5:47Okay, so this is a Colab notebook with some Python,

5:50and here is the graph.

5:51So here we have A, B, C, D, E, F, G.

5:55So that's our graph.

5:56And we're gonna demonstrate DFS or Depth-First Search

6:00using a simple graph.

6:02But let's visualize that. (chuckles)

6:04Much easier to do that here.

6:06So let's go ahead and visualize that,

6:07and then we'll look at it.

6:08Okay, so it goes A to B, right?

6:12And then it goes to D,

6:14and you can see that it goes all the way to the end.

6:17Is this the goal? No.

6:19Then I'm gonna go here.

6:20Is that the goal? No.

6:21And so let's look at the rest of this.

6:25So it goes A, B, D, E, C, F, G.

6:29A, B, D. Then it goes to E, C, F.

6:34So it's going to the bottom of each one of these, right?

6:39So that's Depth-First Search.

6:41And there's another algorithm that's more conservative

6:44that we'll look at next,

6:45but I wanted to show you how this works.

6:47So here, we can visualize the traversals

6:51by using different colors, right?

6:54And so here's that function.

6:55I'm just gonna run the traversal.

6:57And here you have that showing you the the order.

7:00So one, two, three, four,

7:04five, six, seven.

7:07The reason that A is like this

7:09is that you visit A once

7:10'cause you have a visited node.

7:12So for example, you go from A to B to D,

7:15you wouldn't go back to A, B, E, right?

7:18'Cause you visited them.

7:19So you would go A, B, D, then E,

7:23then C because you haven't visited them.

7:26And then F, and then G.

7:27So that should explain a little bit

7:29about this algorithm Depth-First Search.

7:34And definitely don't worry

7:35if any of these algorithms are fuzzy

7:36because first of all, you have the Python code,

7:40and then we're visually navigating this.

7:42And as we go through this algorithm

7:44and the next algorithm, Breadth-First Search,

7:47it should start to click, right?

7:49I've made this as simple as possible

7:51so that we can visually see this

7:53because these algorithms

7:54are the foundation for understanding AI machine learning,

7:58and deep learning.

8:00All right, until the next video,

8:02I hope this has been informative,

8:03and I'd like to thank you for viewing.

0:07<v ->All right, so we've talked about a stack,</v>

0:09and that's a data structure that we've talked about before.

0:12However, what we're doing here is comparing,

0:15basically showing you the data structure,

0:17and then the algorithm

0:18that basically gives you that behavior.

0:22So, what we're gonna do now, so we've checked out the stack

0:25and the depth-first search algorithm.

0:28So, you can use that data structure

0:30to give you that algorithm behavior.

0:32And then, we can do the same thing with a queue.

0:35It's a different order. And we'll look at that.

0:38And then, what this will allow us

0:39to do is the breadth-first search.

0:42And I'll definitely show this to you in the nodes,

0:43so you can see what the advantage is

0:45from one algorithm to the other,

0:47so that you can make a choice

0:49when you need one behavior over the other.

0:52So, we're starting to illuminate the logic here

0:54and why you would want to use one algorithm over another.

0:58However, at the end of the scale,

1:00we're gonna talk about two much better algorithms

1:03and you'll see why.

1:04All right, let's get started.

1:07So, we also have breadth-first search.

1:10So, it explores the shallowest nodes.

1:14So, before we're exploring the deepest nodes,

1:17and that's when we were talking about a stack.

1:18Last in, first-out.

1:20So, here, we have a different behavior,

1:22because we're working with a queue, and not a stack.

1:28Queue data structure,

1:29it gives you that breadth-first search pattern.

1:32Let me show you what I mean by that.

1:33So, here we have the queue, which is a first-in, first-out.

1:37So, we can treat the frontier as a queue

1:40and we'll get a result

1:41that searches for the shallowest nodes first.

1:44It's pretty awesome. Alright, so let's try this out.

1:47So, here's the frontier, and we're just getting started.

1:50So, what are we gonna do?

1:51Let you think about it. Yep.

1:53We're going to get A, put it into the frontier.

1:56Now that we have A in the frontier,

1:58we can also see that we've explored that.

2:00And then, we can just remove it,

2:03because it's not the goal state and it's not empty.

2:06Next, we're gonna go to B.

2:08And we're not gonna do

2:09that sort of infinite loop here anymore,

2:12because, well, we have the visited nodes.

2:15And we visited A and B, we're at B,

2:18and it's not empty and it's not the goal.

2:21So, we can just move on, put that back,

2:23and grab the next two nodes, C and D.

2:26Now, here we have a choice.

2:28So, what are we going to do?

2:30So, try to figure this out as we go step by step.

2:33So, we're at C, and then D.

2:35Which one you think is gonna be next?

2:37First-in, first-out.

2:40Okay, so the first one in is C,

2:44and that's gonna be the first-out.

2:45So, now, we take C out,

2:48because it's not empty and it's not the goal.

2:50Okay, now, we have D and E. So, what happened here?

2:53So, we were at C, and then we added this to the frontier,

2:57but we haven't examined it.

2:59We moved on to this one. So, it's going to the shallowest.

3:02You see what I'm saying?

3:03It's going here, then here, then here, then here.

3:07And this will make more sense. So, let's continue this.

3:10Okay, so we say that D is not empty and it's not the goal.

3:14So, now, we go back to E, and then F.

3:17So, we have both of them in the frontier.

3:19Now, we go to E, and then it's the goal. Okay.

3:22So, that should make a lot more sense

3:24now that we've actually seen this visually.

3:27So, what is a takeaway here?

3:29Well, we have two very important algorithms.

3:32Depth-first search, which we explored first,

3:34which uses the stack data type, which is last-in, first-out.

3:40So, LIFO explores the deepest nodes first.

3:44And then, we have breadth-first search,

3:47which uses the queue data type

3:49and it has first-in, first-out, FIFO.

3:52LIFO and FIFO. So, explores the shallowest nodes.

3:56All right, so here's a quick look

3:57at the breadth-first search algorithm.

4:02And here's the graph.

4:04Just like before, let's go ahead and run this node.

4:06This node is just basically a starting point,

4:08just like before.

4:09And it's taking a little longer,

4:10'cause of the first time I'm running this notebook.

4:12All right, so it's run.

4:14And I'm not gonna go through this,

4:15it's basically the same thing,

4:16but different algorithm,

4:19definitely check out this code if you understand more.

4:21And here, it's giving us the order of visited nodes.

4:24And you can see

4:25that it's ['A', 'B', 'C', 'D', 'E', 'F', 'G'],

4:28very different than the other one.

4:29Let's try to figure out why this is the case.

4:32Let me run this one here.

4:34And once this runs, we're gonna get this graph.

4:36So, showing us this graph.

4:37So, it's going A, B, C, D, E, F, G, hmm.

4:43And then, this one is gonna show us the colors.

4:46So, let's go ahead and and run these too,

4:48and it'll show us the order,

4:49so we can see a little bit clearer.

4:51All right, so we're going from A to B to C.

4:56So, this is the shallowest first.

4:58Then, it goes to D, E, F, and G.

5:01So, it's really exploring the shallowest first,

5:04and I think it's pretty straightforward.

5:06I just wanted to give you this algorithm.

5:08I just wanted to give you this Python code,

5:10because we had the Python code for the depth-first search.

5:15And here's breadth-first search.

5:17And I think this is just really helpful

5:18if you wanted to see a working example of that,

5:21and also to see the different steps taken,

5:23just to reinforce what we've learned so far.

5:26And best of all, we've applied this to Grand Search Auto.

5:29So, thinking about it as game.

5:31We have this AI agent who's trying to figure out

5:33how to navigate this environment.

5:36We've given it some logic,

5:37because before, I was just guessing.

5:38It's like, I'll make a left

5:39and see if that's a good way to go.

5:41Well, now, we're using these algorithms,

5:43but as you see, these algorithms are not super flexible.

5:47They're actually pretty rigid.

5:48However, if you're dealing with large,

5:51vast amounts of information for searching,

5:55mentioned searching in a different context,

5:57these algorithms can actually give you better results

6:00if you choose the right one.

6:02But it could also give you worse results

6:04if you choose the wrong one.

6:05So, knowing about data structures

6:07and about these algorithms,

6:10especially when it applies to AI, it's paramount.

6:12Because without that understanding of that logic,

6:15you're just really gonna be running Python.

6:18It's not gonna be AI.

6:20It's gonna be what it used to be before we had AI. (laughs)

6:24So, now that we have AI, we want to leverage these tools

6:26and create human intelligence,

6:30something that can perform tasks

6:33that require human intelligence.

6:35All right.

6:36So, until the next video, I hope this has been informative.

6:38I'd like to thank you for viewing.

0:06<v ->Congratulations on making it</v>

0:08to the last video in this skill.

0:10And to close things off,

0:12I thought maybe just take a look at some maps

0:15and test out BFS and DFS,

0:18and look at their behaviors,

0:19and just finish things off with two much better algorithms

0:23that have information

0:25that allows them to be more efficient, right?

0:27So far, we're using algorithms without information,

0:31so this an uninformed search.

0:33But we can also do informed search

0:35and that's what we're gonna talk about at the very end

0:37with two different algorithms,

0:38two new algorithms.

0:41All right, so we already talked

0:42about Depth-First Search, right?

0:44It'll go from one...

0:46It'll go all the way down

0:49and then it'll go to the next one, right,

0:52and then the next one.

0:54So this would be Depth-First Search.

0:56Breadth-First Search would go from the starting node

1:00and then to the next node, right,

1:01and then to this node,

1:03and then to this node,

1:05then this one, and then this one.

1:07So it just kind of does it like this, right?

1:09Like floor by floor, right?

1:10This one goes all the way down and then all the way down.

1:13So now we know, and we have two different data types,

1:16data structures, a stack and a queue.

1:19So a stack is last in, first out

1:21and a queue is first in, first out.

1:26Okay, so let's take a look at Depth-First Search.

1:29So let's say that you're here.

1:31What is the next direction that you would take?

1:35Let's see, try to guess.

1:38All right, so it's basically going all the way

1:41as deep as possible,

1:42then the next deepest possible route,

1:45and then the next one, and then the next one.

1:47So in this case, it didn't perform so well.

1:50It took much longer, right,

1:52'cause it had to go through

1:53basically at the end of every street and be like,

1:56"Okay, no, no, no, it's not the best."

2:01Okay, so how about Breadth-First Search?

2:03So we go up here, there's no choices yet,

2:06but now we're here.

2:07So what do you think will happen here?

2:09Let's find out.

2:11So it makes that one choice, makes that other choice.

2:14So it's kind of doing it little by little,

2:16and it's more conservative

2:17because maybe it finds the goal first, right?

2:21Well, in this case, it doesn't.

2:23So both algorithms didn't really work out

2:27that very, very well for us, right?

2:29So we have been using uninformed search.

2:33That's partly why,

2:35because we're not using any useful in knowledge, right?

2:39So we're just searching kind of like blindly,

2:41but we are using algorithms that can give us better results,

2:45depending on what the problem is that we're trying to solve.

2:48However, we can also do informed search, right?

2:52So we're searching with some kind

2:54of useful knowledge, right?

2:56So what is that useful knowledge?

2:59So here, we can talk about

3:01the Greedy Best-First Search algorithm

3:03that tries to explore the node that is closest to the goal.

3:07So that's pretty cool, that's new.

3:09This algorithm evaluates nodes

3:11by using a heuristic function, right?

3:14So that heuristic function is a evaluation function

3:18that is equal to the heuristic function.

3:20So what we're talking about there is that our function

3:24is equal to this heuristic function, right?

3:27Because now, it has this information that,

3:30"Hey, this is gonna be closer to the goal."

3:37So let's check out the estimate of the goal

3:39using a heuristic function.

3:41And in this case,

3:42we're using something called Manhattan distance,

3:44which is basically like go up, down, left, or right,

3:49thinking about like city blocks,

3:51maybe like Manhattan, right?

3:52So that kind of thing.

3:54Nothing diagonal, for example.

3:56So what do you think would happen here?

3:59Okay, so let's take a look.

4:01So here, it's gonna calculate the distance for this one

4:06and calculate the distance for this one.

4:09Clearly, Q is the winner, right?

4:12And that's great because now,

4:14we are actually measuring this to the actual distance,

4:17which is pretty cool.

4:18So now, that is actually some sort of knowledge.

4:22However, sometimes, the heuristically longer route

4:25is the shorter distance.

4:27So let's just say that there was traffic right here, right?

4:30So this would block you off for about an hour

4:34'cause we're in Manhattan, let's say, right?

4:36So that shorter distance is not the best one

4:39because there's no traffic here.

4:41So that one's gonna be faster.

4:43So in this case, if there's traffic,

4:46P is the best option, right?

4:48So once we start talking about information,

4:52so sort of like knowledge, they'll get informed search,

4:55then things totally change, right?

4:56Because you can use a heuristic function

4:58that's gonna give you some sort of a number

5:00to calculate which one could be made better.

5:03But it also doesn't guarantee that it's gonna work

5:06because there are real conditions like traffic.

5:10And so we can calculate that too, right?

5:13That's something we're gonna talk about in another scale,

5:15but I just wanted to give you

5:16sort of an bird's-eye view, right?

5:18The concepts behind these algorithms.

5:21Okay, so we know that the Greedy Best search

5:23uses a heuristic function to calculate the distance

5:26between the start and goal points

5:29because it knows where that goal is.

5:31The Greedy Best algorithm is not always the best

5:34(Jonathan laughs)

5:35because it can get stuck like we just talked about.

5:37However, when we're talking about the A-Star Search,

5:40on the other hand,

5:41it's an extension of Greedy Best

5:43that combines a heuristic function

5:45with a cost to reach the goal.

5:48All right, so let's talk about that.

5:49Okay, so this function

5:51equals the cost function to reach the goal

5:57plus the distance away from that goal.

6:01So we're exploring the lowest cost to reach a node

6:05and the cost to reach the goal, right?

6:08So the cost to reach the node

6:09and the cost to reach the goal.

6:12So that's what the A-Star Search is.

6:13So let's take a look at the behavior.

6:16All right, so here we are,

6:17we start off, and then we just go to this first corner.

6:21And that's because we haven't made a choice

6:22'cause we're here and now we have a decision point.

6:25What do you think the A-Star Search will select?

6:29Let's take a look.

6:30All right, so let's say this is our starting goal.

6:33We come up here

6:34and this is our first decision point as we discovered.

6:36And then let's say we go this way

6:38because it's closer to the goal, right?

6:40Because going left,

6:41it would be further away from the goal, right?

6:44So it's doing good so far,

6:45but then it's starting to say,

6:46"Hey, this is starting to become more expensive."

6:49So it's not just calculating the heuristic function,

6:53but it's the cost of getting to that goal.

6:56So the cost of the getting to the goal is gonna say,

6:58"Hey, I don't know about this one.

6:59Let's go to the other way."

7:01And then it goes over here,

7:03and that is actually the faster one

7:04because you'd have to do all of this stuff

7:07and then get there.

7:08So this is a much better option

7:10because it is able to discover

7:12that the cost to reach the goal

7:14becomes higher than the blue option very soon.

7:17And then it switches to the blue goal, right?

7:19Super cool.

7:20All right, so this should give you a really solid idea

7:24of how all of these algorithms work

7:26to help an AI agent navigate in its environment.

7:30In the context of this game Grand Search Auto, all right?

7:33So I hope this has been fun.

7:35I had a great time, and I hope this has been informative,

7:38and I'd like to thank you for viewing.