Logo

CS 188's Personal Meeting Room - Shared screen with speaker view
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?