Vishal Raman

01:53:09

Are we expected to go to one section per week?

Andy Fang

01:53:27

Around how long would the written assessments usually take to be graded?

Zackoric

01:53:53

Where's written assessment 1 on the website?

Carlos Calderon

01:59:05

the slides are online

Nikita Kitaev

01:59:07

https://drive.google.com/file/d/1hxaBVYKgjeSAZfbp6CtKdTxMmSyTO49Y/view?usp=sharing

Yewen Zhou

02:00:23

Hi Alex just a reminder this is a class of 90+ students

Carlos Calderon

02:02:39

what do you mean when you say “no info about goal location”?

Zackoric

02:03:02

You blindly expand from the origin without know where the goal is

Jae Min Im

02:03:08

if we have a location, we can tell if it is a goal, but we don't know as we are searching, if we are getting closer

Carlos Calderon

02:03:29

I see, thank you

Cindy Chen (She/Her/Hers)

02:05:49

how would you know where the goal is tho

Amit Palekar

02:05:51

I’m confused because say for example you the shortest path from A to B has a very heavy cost. But a longer path might have a shorter cost. Doesn’t the idea of a heuristic and cost conflict the

Zackoric

02:06:31

The heuristic may direct the search in the wrong path for a little bit, but the final path will be correct

Estea

02:06:32

Maybe heuristic is just another piece of info.

Julius Tereck

02:06:45

Well the heuristic isn't guaranteed to be correct

Oscar Xu

02:06:53

Heuristic is just an estimation

Amit Palekar

02:07:06

ah makes sensee

Andy Fang

02:07:12

So the heuristic just estimates the actual cost of the path?

Luke Cheng

02:07:26

Heuristic seems to be based on the goal. Cost is based on the next possible state.

Luke Cheng

02:07:31

So next state vs goal state.

Carlos Calderon

02:07:34

heuristic is an estimate of the distance between current state -> goal

Zackoric

02:07:37

The heuristic cannot over estimate as you'll learn later on

Yewen Zhou

02:09:03

how to come up with a good heuristic?

Amit Palekar

02:09:22

I think it’s like admissibility and consistent

Zackoric

02:09:39

he'll talk about in later

jimwang

02:10:39

@Alex Calitri it would greatly help if you could post questions in chat instead of interrupting and asking out loud

Soonhyuck Hong

02:10:46

^

Marco Gellecanao

02:10:51

^

Amit Palekar

02:10:52

+1

Yewen Zhou

02:10:56

+ 1

Luke Cheng

02:10:57

^

Lukas Finkbeiner

02:11:02

Okay, there is no need to pile on

Zhe Zhao

02:11:05

+1

allen

02:11:25

+1

Estea

02:11:42

@ Lukas - second that

Lukas Finkbeiner

02:12:22

Also, public service announcement:please use private messaging as often as possible

Carlos Calderon

02:12:23

we need to look at the cost of the current path we are on as well?

Estea

02:13:01

Heuristic and cost independent of each other?

Anand Madathil

02:14:31

Is best first the same thing as the greedy search

Yewen Zhou

02:14:43

which is why you will then have greedy + UCS = A* basically

Zackoric

02:15:31

I think most questions here are jumping the gun a bit

ryanhurst

02:16:50

Yeah my bad was just thought he was saying the heuristic is different for greedy because it goes node by node instead of estimating from root node to goal

Amit Palekar

02:16:50

What did he mean by best-case takes you to the “wrong goal"

Danny Sallurday

02:17:03

So Manhattan distance is just straight line distance regardless of walls/dead ends?

Zackoric

02:17:09

the final path was no optimistic

Jae Min Im

02:17:33

manhattan distance is distance only using vertical and horizontal path

Zackoric

02:17:44

@Danny yes, it passing through walls

Prabhman Dhaliwal

02:17:47

it would make more sense if the turtle was riding the bunny

Cindy Chen (She/Her/Hers)

02:20:13

no…the turtle is too heavy for a bunny

Zackoric

02:20:27

So greedy search is just UCS without edge costs?

Miran

02:20:56

doesn't this depend on the relative scaling of the costs and the heuristic?

Prabhman Dhaliwal

02:21:02

bunny needs to hit the gym

Matthew Cuevas

02:21:03

Will A* always find the optimal solution?

Brandon Lee

02:21:07

So if the summed g+h weight of node G was larger than the summed weight of b and e it would explore b and e first?

allen

02:21:14

do greedy search just consider heuristic as edge cost?

Zackoric

02:21:38

Heuristic applies to a point

Zackoric

02:22:08

cost to a point is sum of edge costs to that point (given the path)

Danny Sallurday

02:23:39

I don’t understand how h isn’t equal to edge cost (i.e B-G)

Yewen Zhou

02:23:41

how to understand this concept intuitively?

Chenyue Cai

02:23:56

In A* search do we basically search all the path combinations?

Amit Palekar

02:24:16

Isn’t this very expensive if you there’s only one path to goal. I.e wouldn’t you end up traversing the entire goal?

Vishal Raman

02:24:25

Doesn’t the scaling of g(n), h(n) play a big role? For example, if h(n) is much much greater than g(n), then f(n) is approximately h(n), so the search will be essentially greedy

Amit Palekar

02:24:25

*graph

Carlos Calderon

02:24:39

the heuristic overestimated?

Heming Wu

02:25:10

how do we define "optimal" in this case?

Amit Palekar

02:25:20

The path with the least cost

Heming Wu

02:25:38

got it, tks

Jae Min Im

02:26:55

so heuristic close to real value is great but under estimate is almost always better than over estimate?

Zackoric

02:27:07

no, never over estimate

Danny Sallurday

02:30:59

G is cost, f is heuristic ?

Amit Palekar

02:31:13

g is backward cost, h is heuristic

Amit Palekar

02:31:17

F = g + h

Danny Sallurday

02:31:23

ty

Chenyue Cai

02:33:57

why is f(n)<g(a)?

Estea

02:34:03

is backward cost related to how optimal a path is?

Alex Calitri

02:34:19

Manhatten distances are heuristics because they are always the shortest path to the goal

Amit Palekar

02:35:11

yes, party because you want to explore nodes that have a shorter backward path, but also in the direction of the goal

Amit Palekar

02:35:22

That’s why you also use the heuristic

Estea

02:35:56

I see, ty!

Zackoric

02:37:15

Why would the red dot not go directly to the goal if you use manhattan hueristics

Zackoric

02:37:35

yes

Zackoric

02:37:47

alright

Julius Tereck

02:38:18

So you can weight towards greedy or UCS depending on how you weight g and h?

Zackoric

02:39:08

wdyu

Andrew

02:39:24

yes but I think you always want to try to find a good heuristic to find the optimal solution fastest

Amit Palekar

02:42:05

i kinda get ur saying by weighting but idt the properties of A* are preserved when you do this I.e you are solving a completely different problem

Matthew Cuevas

02:42:43

Did anyone else just lose audio?

Frank Liu

02:42:45

same

Jae Min Im

02:42:46

is his mic muted?

Calvin Wong

02:42:46

Ye

Shrey Vasavada

02:42:46

Yes

Oscar Xu

02:42:47

same

Shrey Vasavada

02:42:48

Same

Lukas Finkbeiner

02:42:48

Yes

Zackoric

02:42:48

I can't ehar

Adyant Kamdar

02:42:48

same

Anand Madathil

02:42:48

+1

Vishal Raman

02:42:49

yep

Heming Wu

02:42:49

I can't hear

Jorgiana Lopez

02:42:49

No audio

Danny Sallurday

02:42:52

Lol

Estea

02:42:52

No audio

kendallkikkawa

02:42:54

same

Marcos Rico

02:43:01

No audio

Julius Tereck

02:43:22

No audio here either

Zackoric

02:43:28

wait what

Julius Tereck

02:43:31

Wait now it's back

Zackoric

02:43:32

yes we can

Jae Min Im

02:43:33

now we can

Calvin Wong

02:43:34

I think its back

Zackoric

02:43:50

I don't think the algo is on the list

Estea

02:43:52

can you play it again

Carlos Calderon

02:43:54

can you replay it please?

Jae Min Im

02:44:07

I'm guessing the 2nd one was UCS?

Zackoric

02:44:42

greedy is a subset of A* though

Tyler Nunez

02:44:43

greedy?

Carlos Calderon

02:44:43

greedy search?

Julius Tereck

02:44:53

It looked like greedy, but could possibly be DFS?

Jorgiana Lopez

02:44:54

can you clarify what the second one was? the audio cut off

Shengxian Chen

02:45:02

It could be DFS

Jorgiana Lopez

02:45:03

ty

joewy

02:45:14

dfs?

Calvin Wong

02:45:14

Greedy is based on heuristic tho which makes me think it's not greedy

Yewen Zhou

02:45:26

how do we know it's not A*?

Lukas Finkbeiner

02:45:29

Yeah, the heuristic is the Manhattan distance

Carlos Calderon

02:45:30

DFS

Calvin Wong

02:46:10

oh gotcha thanks lukas

Danny Sallurday

02:46:10

Why does it stop so quickly in the deep water?

Andrew

02:46:13

i think A* would consider other non-green options like the white dots

Heming Wu

02:46:45

how do we determine greedy search while we don't know about it's heuristic?

Zackoric

02:47:00

greedy search is heuristic only

Luke Cheng

02:47:00

Why does DFS turn towards the goal?

Zackoric

02:47:05

no movement cost

Luke Cheng

02:47:30

It could go to the corner instead though?

Monica Wang

02:47:37

How do u differentiate BFS and UCS in this case

Rafael Flores

02:48:05

water expands slower in dark blue

Zackoric

02:49:51

2

Julius Tereck

02:49:54

4

Zhe Zhao

02:49:55

4

Oscar Xu

02:49:57

4

Zackoric

02:49:57

4

Vishal Raman

02:49:57

4

Matthew Cuevas

02:49:57

4

Danny Sallurday

02:49:58

4

Chenyue Cai

02:50:03

4

Yewen Zhou

02:53:28

so relaxed means ignoring the constraints?

Danny Sallurday

02:53:44

Wouldn’t calculating Manhattan distance in that case be the same as finding the optimal path ?

Zackoric

02:54:13

not if there's walls

Andrew

02:54:16

manhattan distance assumes you can move tiles into other tiles but you cant

Danny Sallurday

02:54:41

I just meant for that case that he used it with

Zackoric

02:54:50

the 8-puzzle?

Danny Sallurday

02:55:23

Yeah the second one with each square on their own track. Why calculated a heuristic that’s literally the solution ?

Amit Palekar

02:55:51

Is there such a thing as an optimal heuristic?

Zackoric

02:56:05

It's, that would be consistant

Amit Palekar

02:56:05

or like a method to find it

Zackoric

02:56:38

@Amit depends on the problem

Anand Madathil

02:56:51

Why not the min?

Shrey Vasavada

02:57:05

because the greater the better

jimwang

02:57:09

Min approaches 0 so its inefficient

Zackoric

02:57:30

better inefficient than in consistant

Yewen Zhou

02:57:33

what exactly does "better" mean? Does it mean more efficient?

Zackoric

02:57:46

better in what I wrote means not wrong

Yewen Zhou

02:57:47

expand less nodes?

Yewen Zhou

02:58:07

but as long as heuristic is admissible it's optimal right?

Shrey Vasavada

02:58:14

better means closer to the actual cost because heuristics estimate it

Yewen Zhou

02:58:14

(and consistent)

jimwang

02:58:44

inconsistent can be optimal if you allow reexpansion of nodes

Zackoric

02:59:22

there are subtleties involved in optimalitiy with consistency and admissibility

Zackoric

03:00:07

it depends on the algorithm, if you A* is written correctly, it will be optimal if the h is just admissible

jimwang

03:00:32

Not if you never expand a state twice

Danny Sallurday

03:01:33

At what point in the previous slide would this catch a duplicate stat ?

Danny Sallurday

03:01:35

state

Danny Sallurday

03:03:53

Nvm ^ State just means node?

Andrew

03:06:47

i think we don't expand a duplicated state but we can save memory by never adding nodes we've already seen before? i.e. if you had graph S->A->G and there were a million edges between S->A we would still only add 1 edge

Vishal Raman

03:07:23

Is consistency a stronger condition than admissibility?

jimwang

03:07:39

@Andrew the hw provides a counterexample of that

jimwang

03:09:06

Could I see the proof again?

jimwang

03:09:15

of optimality for graph search

Eric Verduzco

03:09:20

will discussion take place here as well?

Ferdie Taruc

03:09:21

there's a discussion at 2 right?

Frank Liu

03:09:22

is the proof of optimality for A* graph search something in scope for exams and homeworks?

Calvin Wong

03:09:43

Thanks professor!

Carlos Calderon

03:09:50

is there a discussion worksheet?