WEBVTT 00:00:00.000 --> 00:00:02.580 So if you think about playing a video game or 00:00:02.580 --> 00:00:05.780 using a travel app or even just parsing natural 00:00:05.780 --> 00:00:08.900 language, you're relying on this invisible math. 00:00:09.080 --> 00:00:11.019 doing a ton of heavy lifting in the background. 00:00:11.400 --> 00:00:13.240 Right, yeah. We treat it like magic, like the 00:00:13.240 --> 00:00:15.779 optimal path just, you know, materializes out 00:00:15.779 --> 00:00:19.320 of nowhere. Totally. But back in 1968, getting 00:00:19.320 --> 00:00:21.899 a piece of hardware to physically just roll across 00:00:21.899 --> 00:00:24.440 a living room without hitting a sofa, that was 00:00:24.440 --> 00:00:26.399 considered one of the most punishing mathematical 00:00:26.399 --> 00:00:28.300 challenges on earth. Oh, absolutely. It was a 00:00:28.300 --> 00:00:31.030 massive problem. And today... That exact same 00:00:31.030 --> 00:00:33.049 mathematical architecture, the algorithm built 00:00:33.049 --> 00:00:36.429 for a clunky, rolling robot, is quietly working 00:00:36.429 --> 00:00:39.450 behind the scenes in almost every digital routing 00:00:39.450 --> 00:00:42.310 system you use. Yeah. That invisible engine is 00:00:42.310 --> 00:00:46.170 the Aster search algorithm, or A as it's written 00:00:46.170 --> 00:00:48.549 out. Right. We just sort of assume optimal routing 00:00:48.549 --> 00:00:50.829 is a given, you know? Whether it's packet switching 00:00:50.829 --> 00:00:53.909 on a network or programming an NPC to hunt a 00:00:53.909 --> 00:00:56.390 player through a game, we rarely stop to look 00:00:56.390 --> 00:00:58.950 at the massive high speed geometric negotiation 00:00:58.950 --> 00:01:01.850 happening beneath the surface. Okay, let's unpack 00:01:01.850 --> 00:01:05.069 this. Our mission for today's deep dive is to 00:01:05.069 --> 00:01:08.629 dissect exactly what makes A -Star the absolute 00:01:08.629 --> 00:01:11.030 gold standard for getting from point A to point 00:01:11.030 --> 00:01:13.569 B. Yeah, it's the ultimate blueprint for efficient 00:01:13.569 --> 00:01:15.950 problem solving. It's a whole world of weighted 00:01:15.950 --> 00:01:19.129 graphs and complex decision trees. Exactly. So 00:01:19.129 --> 00:01:22.209 we're going to explore the crazy 1960s hardware 00:01:22.209 --> 00:01:26.049 history behind it and the mathematical compromises 00:01:26.049 --> 00:01:28.329 it has to make so it doesn't just completely 00:01:28.329 --> 00:01:30.829 break modern computers. Right, because before 00:01:30.829 --> 00:01:32.849 we get into the complex math of how it works, 00:01:32.849 --> 00:01:35.030 we really have to look at why it was invented. 00:01:35.469 --> 00:01:39.189 And that brings us back to some very shaky 1960s 00:01:39.189 --> 00:01:41.250 hardware. Yeah, literally shaky, right? Yeah. 00:01:41.349 --> 00:01:43.430 Because they built a robot named Shakey. Exactly, 00:01:43.530 --> 00:01:45.310 yeah. ASTAR wasn't just cooked up on a chalkboard 00:01:45.310 --> 00:01:47.650 for fun. It was born at the Stanford Research 00:01:47.650 --> 00:01:51.290 Institute which is now SRI International in 1968. 00:01:51.549 --> 00:01:54.269 Purely out of necessity. Total necessity. Researchers 00:01:54.269 --> 00:01:57.650 Peter Hart, Nielsen, and Bertram Raphael were 00:01:57.650 --> 00:02:00.689 trying to build this mobile robot, shaky, and 00:02:00.689 --> 00:02:02.609 it had to be autonomous. Meaning it had to plan 00:02:02.609 --> 00:02:04.930 its own waypoints and navigate a room full of 00:02:04.930 --> 00:02:07.409 obstacles all by itself. Right. Which, you know, 00:02:07.530 --> 00:02:10.530 with the computing power of 1968... I mean, that's 00:02:10.530 --> 00:02:12.590 like trying to navigate a jungle in the dark 00:02:12.590 --> 00:02:15.310 with a dying flashlight. The processing power 00:02:15.310 --> 00:02:18.569 required just to look a few steps ahead was like... 00:02:18.430 --> 00:02:22.250 It really was. So initially, Nielsen proposed 00:02:22.250 --> 00:02:24.789 using something called the graph traverser algorithm. 00:02:25.169 --> 00:02:27.830 OK, and how does that work? Well, it operated 00:02:27.830 --> 00:02:30.610 entirely on what we call a heuristic function. 00:02:30.870 --> 00:02:33.389 In computer science, we call that h of n. It 00:02:33.389 --> 00:02:35.870 basically only looked at the estimated distance 00:02:35.870 --> 00:02:38.370 to the goal. Oh, so it completely ignored how 00:02:38.370 --> 00:02:40.490 far the robot had already traveled. Exactly. 00:02:40.750 --> 00:02:43.129 It possessed zero memory of the energy it just 00:02:43.129 --> 00:02:45.289 spent. Let me give an analogy here. It's like 00:02:45.289 --> 00:02:47.810 a toddler. navigating a living room full of furniture. 00:02:48.129 --> 00:02:51.110 Right, okay, I like that. If the robot or the 00:02:51.110 --> 00:02:53.949 toddler only looks at the toy it wants on the 00:02:53.949 --> 00:02:56.729 other side of the room, but ignores the giant 00:02:56.729 --> 00:02:58.849 maze of couches it just crawled through, won't 00:02:58.849 --> 00:03:02.199 it just get stuck in a loop? Yes. That is exactly 00:03:02.199 --> 00:03:05.159 what happens. It's a greedy search. If shaky 00:03:05.159 --> 00:03:07.819 hits a U -shaped wall, it just drives straight 00:03:07.819 --> 00:03:09.680 into the deepest part of the U, because moving 00:03:09.680 --> 00:03:12.639 away from the goal to go around the wall mathematically 00:03:12.639 --> 00:03:15.759 increases that H of N estimate. So the algorithm 00:03:15.759 --> 00:03:17.900 just refuses to do it. It gets permanently trapped. 00:03:17.939 --> 00:03:21.229 Trapped in a local minimum, yeah. And Bertram 00:03:21.229 --> 00:03:24.789 Raphael realized this was a fatal flaw. He suggested 00:03:24.789 --> 00:03:27.430 combining the distance traveled with the estimated 00:03:27.430 --> 00:03:29.990 distance remaining. Basically introducing consequence 00:03:29.990 --> 00:03:32.449 into the machine's memory. Precisely. And then 00:03:32.449 --> 00:03:35.110 Peter Hart took that idea and formalized the 00:03:35.110 --> 00:03:38.409 math. He invented the core concepts of admissibility 00:03:38.409 --> 00:03:41.189 and consistency. And that's what guaranteed the 00:03:41.189 --> 00:03:43.090 robot would actually escape the dead ends. Right. 00:03:43.150 --> 00:03:45.310 It guaranteed the single most optimal path every 00:03:45.310 --> 00:03:48.610 single time. But the academic drama around this 00:03:48.610 --> 00:03:51.050 is wild. Oh, yeah. The source text gets into 00:03:51.050 --> 00:03:54.129 this decades -long academic warfare. Because 00:03:54.129 --> 00:03:56.870 they published in 1968, but the scientific community 00:03:56.870 --> 00:03:59.469 didn't just accept it. No, they didn't. The original 00:03:59.469 --> 00:04:01.930 paper had a theorem about A star's efficiency. 00:04:02.430 --> 00:04:05.819 But then in 1972, a correction was published 00:04:05.819 --> 00:04:08.379 claiming that consistency wasn't even required. 00:04:08.800 --> 00:04:11.780 Which, I mean, in the 70s, every kilobyte of 00:04:11.780 --> 00:04:13.939 memory was precious. If someone says you can 00:04:13.939 --> 00:04:16.360 draw a complex math rule and save computational 00:04:16.360 --> 00:04:18.439 overhead, you're going to take that deal. Oh, 00:04:18.439 --> 00:04:22.139 totally. And that correction sat basically unchallenged 00:04:22.139 --> 00:04:25.319 for over 10 years. Wow. Over a decade of people 00:04:25.319 --> 00:04:29.170 using bad math. Yeah. It wasn't until 1985 that 00:04:29.170 --> 00:04:32.149 researchers Rina Dechter and Judea Pearl proved 00:04:32.149 --> 00:04:35.089 the 1972 correction was totally false. They proved 00:04:35.089 --> 00:04:37.029 that dropping consistency was a catastrophic 00:04:37.029 --> 00:04:39.410 mistake, right? Exactly. They mathematically 00:04:39.410 --> 00:04:43.610 cemented the original 1968 rules, proving A star's 00:04:43.610 --> 00:04:45.930 optimal efficiency. Okay, so this collaboration 00:04:45.930 --> 00:04:49.029 gave us this incredibly powerful formula. But 00:04:49.029 --> 00:04:51.350 how exactly does it balance the past and the 00:04:51.350 --> 00:04:53.910 future to find that perfect path? Well, it all 00:04:53.910 --> 00:04:56.779 comes down to the magic formula. F of n equals 00:04:56.779 --> 00:04:59.779 g of n plus h of n. OK, break that down for us. 00:04:59.899 --> 00:05:02.160 Sure. So g of n is the cost of the path from 00:05:02.160 --> 00:05:04.620 the start node to your current position. And 00:05:04.620 --> 00:05:06.899 h of n is the heuristic function, the estimated 00:05:06.899 --> 00:05:09.019 cheapest path to the goal. So it's like a road 00:05:09.019 --> 00:05:11.459 trip. The g of n is your car's odometer. It's 00:05:11.459 --> 00:05:13.540 the gas you've already burned. And the h of n 00:05:13.540 --> 00:05:17.720 is the road sign saying Los Angeles, 500 miles. 00:05:18.220 --> 00:05:20.800 Yes. Perfect analogy. It's a guess of what's 00:05:20.800 --> 00:05:23.379 left. And the algorithm just adds them together 00:05:23.379 --> 00:05:25.759 to decide if this specific highway is the best 00:05:25.759 --> 00:05:28.980 choice. Exactly. It scores the options and picks 00:05:28.980 --> 00:05:31.040 the lowest one. But here's where it gets really 00:05:31.040 --> 00:05:35.439 interesting. What if that road sign is just wrong? 00:05:35.959 --> 00:05:38.259 Like what if the H of N is a terrible guess? 00:05:38.720 --> 00:05:41.480 Ah, and that brings us back to Peter Hart's concept 00:05:41.480 --> 00:05:45.100 of admissibility. A star only guarantees a perfect 00:05:45.100 --> 00:05:47.839 optimal solution if the heuristic never ever 00:05:48.480 --> 00:05:50.980 overestimates the true costs. Never overestimates 00:05:50.980 --> 00:05:53.300 it, right? Right. It can be wildly optimistic 00:05:53.300 --> 00:05:55.740 and underestimate the cost. But the second it 00:05:55.740 --> 00:05:58.620 becomes pessimistic, the second it thinks a path 00:05:58.620 --> 00:06:01.120 is more expensive than it really is, the whole 00:06:01.120 --> 00:06:03.339 optimal guarantee just collapses. Because it'll 00:06:03.339 --> 00:06:05.519 look at a perfectly good path, think it's too 00:06:05.519 --> 00:06:07.819 expensive, and just abandon it for a physically 00:06:07.819 --> 00:06:10.769 longer route. Exactly. Which is why computer 00:06:10.769 --> 00:06:12.889 scientists have to be incredibly careful about 00:06:12.889 --> 00:06:14.810 choosing heuristics. Like if you're searching 00:06:14.810 --> 00:06:16.829 a standard map, a good heuristic is the straight 00:06:16.829 --> 00:06:19.230 line distance or Euclidean distance. Because 00:06:19.230 --> 00:06:21.689 you literally cannot travel between two points 00:06:21.689 --> 00:06:24.329 faster than a straight line. The laws of physics 00:06:24.329 --> 00:06:26.970 say it's a guaranteed underestimate. Right. But 00:06:26.970 --> 00:06:30.250 what if you're in a video game grid where diagonal 00:06:30.250 --> 00:06:32.670 movement is physically impossible? Like you can 00:06:32.670 --> 00:06:35.589 only go up, down, left, or right. Yeah. In that 00:06:35.589 --> 00:06:38.069 case, a straight line breaks the math. You have 00:06:38.069 --> 00:06:41.129 to use the taxi cab or Manhattan distance measuring 00:06:41.129 --> 00:06:43.790 in blocky perpendicular steps. And if the game 00:06:43.790 --> 00:06:46.490 does allow diagonals? Then you shift to Chebyshev 00:06:46.490 --> 00:06:49.569 distance or if you're routing railroads or flights 00:06:49.569 --> 00:06:52.790 globally, say between Washington DC and Los Angeles, 00:06:53.149 --> 00:06:55.110 you have to use the Great Circle distance because 00:06:55.110 --> 00:06:58.220 the Earth is a sphere. Wow, so the math literally 00:06:58.220 --> 00:07:00.399 shapeshifts based on the geometry of the world 00:07:00.399 --> 00:07:02.480 it's in. It does, and what's fascinating here 00:07:02.480 --> 00:07:05.240 is, what happens if you drop the h of n entirely? 00:07:05.600 --> 00:07:07.660 Like you just make the heuristic zero. Wait, 00:07:07.740 --> 00:07:10.779 if it's zero? Then it has no intuition at all, 00:07:10.800 --> 00:07:13.100 it doesn't know where the goal is. Exactly. If 00:07:13.100 --> 00:07:16.680 h of n is zero, A star simply becomes Dijkstra's 00:07:16.680 --> 00:07:19.939 algorithm. Oh, because zero never overestimates, 00:07:19.959 --> 00:07:22.660 so it's technically perfectly admissible. Right. 00:07:22.829 --> 00:07:25.329 But it's totally uninformed. Instead of cutting 00:07:25.329 --> 00:07:27.949 toward a target like a laser beam, Dijkstra just 00:07:27.949 --> 00:07:30.649 searches outward in every single direction uniformly, 00:07:30.970 --> 00:07:33.490 like a ripple in a pond. Which takes forever. 00:07:34.170 --> 00:07:36.990 So A -Star uses the heuristic to warp that ripple 00:07:36.990 --> 00:07:39.470 into an ellipse that aggressively pulls toward 00:07:39.470 --> 00:07:41.709 the target. That pull is what guarantees the 00:07:41.709 --> 00:07:44.370 perfect route. But perfection comes at a massive 00:07:44.370 --> 00:07:46.949 cost. Yeah, let's talk about the fatal flaw here. 00:07:47.370 --> 00:07:49.310 Because this algorithm actually breaks computers 00:07:49.310 --> 00:07:51.290 if they aren't careful, right? Oh, absolutely. 00:07:51.870 --> 00:07:54.449 The worst case space complexity of A star is 00:07:54.449 --> 00:07:57.470 big O of B to the power of D. OK, let's translate 00:07:57.470 --> 00:07:59.790 that for the listeners. Right, sorry. So B is 00:07:59.790 --> 00:08:02.269 the branching factor, the number of choices at 00:08:02.269 --> 00:08:05.290 any intersection. And D is the depth of the solution, 00:08:05.430 --> 00:08:07.860 how many steps to the goal. So B to the power 00:08:07.860 --> 00:08:10.779 of D means exponential growth. Yes. In simple 00:08:10.779 --> 00:08:13.560 terms, A star keeps every single generated node 00:08:13.560 --> 00:08:16.240 in its memory. It stores the entire search tree. 00:08:16.379 --> 00:08:18.639 To guarantee it didn't miss a better route. It's 00:08:18.639 --> 00:08:20.839 like someone trying to plan a road trip, but 00:08:20.839 --> 00:08:23.079 they're hoarding every single physical map of 00:08:23.079 --> 00:08:25.360 every single county in their car until the windows 00:08:25.360 --> 00:08:28.360 shatter. That is exactly what happens to a computer's 00:08:28.360 --> 00:08:31.290 RAM. In practical travel routing, it can get 00:08:31.290 --> 00:08:34.190 entirely bogged down. A server will just saturate 00:08:34.190 --> 00:08:36.629 its memory and crash long before it finds the 00:08:36.629 --> 00:08:39.090 perfect path. Which is pretty useless for real 00:08:39.090 --> 00:08:41.429 -world apps. If I open my map app, I want an 00:08:41.429 --> 00:08:43.950 answer now, not when the server catches fire. 00:08:44.049 --> 00:08:47.210 Right. So how do they fix this? They compromise 00:08:47.210 --> 00:08:50.090 through something called bounded relaxation. 00:08:50.269 --> 00:08:52.690 Bounded relaxation. Oh yeah, or epsilon admissible 00:08:52.690 --> 00:08:56.120 algorithms. Basically, instead of finding the 00:08:56.120 --> 00:08:58.440 absolute perfect path, they instruct the engine 00:08:58.440 --> 00:09:01.759 to find a path that is no worse than 1 plus epsilon 00:09:01.759 --> 00:09:04.620 times the optimal solution. So they settle for 00:09:04.620 --> 00:09:07.179 good enough. Exactly. A really common version 00:09:07.179 --> 00:09:09.740 of this is weighted A star. They take the standard 00:09:09.740 --> 00:09:12.000 formula, but they multiply the heuristic by a 00:09:12.000 --> 00:09:14.620 number greater than 1. Wait. But you said earlier 00:09:14.620 --> 00:09:17.480 it can never overestimate. I did. And by multiplying 00:09:17.480 --> 00:09:19.840 it, they are intentionally breaking the rule 00:09:19.840 --> 00:09:22.279 of admissibility. They are forcing it to overestimate. 00:09:22.519 --> 00:09:24.360 Oh, wow. So it becomes super greedy. It stops 00:09:24.360 --> 00:09:26.580 exploring side paths and just charges straight 00:09:26.580 --> 00:09:28.820 toward the goal. Right. It forces the algorithm 00:09:28.820 --> 00:09:31.720 to search exponentially faster, expanding way 00:09:31.720 --> 00:09:33.980 fewer nodes. Which saves the computer's memory. 00:09:34.279 --> 00:09:36.860 Completely. And there are some fascinating variants 00:09:36.860 --> 00:09:39.960 mentioned in the sources, like dynamic weighting. 00:09:40.179 --> 00:09:42.820 How does that one work? It changes based on the 00:09:42.820 --> 00:09:45.559 search depth. It starts out highly weighted and 00:09:45.559 --> 00:09:48.059 greedy to cover ground quickly. But as it gets 00:09:48.059 --> 00:09:50.779 closer to the goal, the weight drops, so it becomes 00:09:50.779 --> 00:09:53.519 more precise for the final approach. Oh, that's 00:09:53.519 --> 00:09:55.980 clever. And the sources also mentioned XUP and 00:09:55.980 --> 00:09:59.139 XDP, right? Yeah. Those are bi -directional variants 00:09:59.139 --> 00:10:01.940 that push the optimality toward the start or 00:10:01.940 --> 00:10:04.940 the goal using parabolic curves. So it basically 00:10:04.940 --> 00:10:07.320 inflates the search area to quickly escape a 00:10:07.320 --> 00:10:10.259 complex starting maze and then just blitzes across 00:10:10.259 --> 00:10:12.480 the open space. Exactly. It's brilliant engineering. 00:10:13.120 --> 00:10:16.379 So synthesizing this for you listening, in the 00:10:16.379 --> 00:10:18.340 real world, whether you're designing a game or 00:10:18.340 --> 00:10:21.159 a mapping app, sometimes a fast, good enough 00:10:21.159 --> 00:10:24.299 answer is objectively better than a perfect answer 00:10:24.299 --> 00:10:26.710 that takes a supercomputer to store. A hundred 00:10:26.710 --> 00:10:28.750 percent. It's a pragmatic trade -off. So what 00:10:28.750 --> 00:10:31.269 does this all mean for you? Next time you open 00:10:31.269 --> 00:10:33.649 a map app to find a coffee shop, where you watch 00:10:33.649 --> 00:10:36.789 an NPC navigate a maze in a video game to attack 00:10:36.789 --> 00:10:40.129 you, remember, shaky the robot. Yeah, pay your 00:10:40.129 --> 00:10:42.750 respects to shaky. Seriously. Remember that moving 00:10:42.750 --> 00:10:45.289 from point A to point B is just a really delicate 00:10:45.289 --> 00:10:47.929 mathematical balance between what you've already 00:10:47.929 --> 00:10:50.909 spent the G and what you're guessing lies ahead, 00:10:51.149 --> 00:10:53.950 the H. And if we connect this to the bigger picture, 00:10:54.279 --> 00:10:57.639 There is one final mind -bending detail from 00:10:57.639 --> 00:10:59.320 the source text that we have to talk about. Oh, 00:10:59.399 --> 00:11:03.000 yeah. Lay it on us. We naturally associate ASTAR 00:11:03.000 --> 00:11:06.200 with physical geography, right? Game maps, road 00:11:06.200 --> 00:11:08.240 networks. Because it was built for a robot in 00:11:08.240 --> 00:11:10.320 a physical room. Right. But the source notes 00:11:10.320 --> 00:11:13.039 that ASTAR is also heavily used in natural language 00:11:13.039 --> 00:11:15.200 processing. Wait, what? Like parsing language? 00:11:15.299 --> 00:11:18.460 Yes. Specifically for parsing stochastic grammars. 00:11:18.740 --> 00:11:21.080 That is wild. How does the structure of a sentence 00:11:21.080 --> 00:11:23.299 become a pathfinding problem? Well, a sentence 00:11:23.299 --> 00:11:25.919 is a sequence of discrete observations. A system 00:11:25.919 --> 00:11:28.539 has to find the most probable grammatical structure 00:11:28.539 --> 00:11:30.840 among thousands of possibilities. So it maps 00:11:30.840 --> 00:11:33.639 the words as nodes and the grammatical rules 00:11:33.639 --> 00:11:37.049 as edges. And the cost is... What, the probability 00:11:37.049 --> 00:11:39.870 of the grammar? Exactly. A common grammatical 00:11:39.870 --> 00:11:43.190 transition has a low cost. An awkward one has 00:11:43.190 --> 00:11:47.190 a high cost. It uses the exact same A star equation 00:11:47.190 --> 00:11:50.009 to find the shortest path to the correct meaning. 00:11:50.230 --> 00:11:53.549 So a math formula designed in 1968 to get a clunky 00:11:53.549 --> 00:11:56.330 robot across a living room is the exact same 00:11:56.330 --> 00:11:58.330 formula used to navigate the structure of human 00:11:58.330 --> 00:12:01.350 sentences. It is. Which raises such a crazy question 00:12:01.350 --> 00:12:03.389 for you listening. What does that say about language? 00:12:03.870 --> 00:12:05.769 Like, is human language just another geographic 00:12:05.769 --> 00:12:08.009 maze waiting to be optimally solved? It really 00:12:08.009 --> 00:12:09.710 makes you wonder. It totally does. Something 00:12:09.710 --> 00:12:11.490 for you to chew on until our next deep dive.