Roland Meertens and Anthony Alford discuss the historical cycles of AI "summers" and "winters": periods of optimism and decline in AI research. The conversation follows the story of neural networks, to the resurgence of AI with backpropagation and deep learning in the 2010s. They also explore the potential for a future "AI Winter", as technological advances face both hype and skepticism.
Key Takeaways
- Early AI efforts aimed high but faced technical and computational limitations, leading to periods of reduced funding and interest.
- Neural networks, while developed in the 1950s, only became practical after the introduction of backpropagation in the 1980s, sparking the modern deep learning revolution.
- Despite the current AI boom, some experts predict another "AI Winter" is possible, as expectations for AI continue to rise while the technology may hit new challenges.
- A* is a heuristic-based search algorithm that optimizes pathfinding by estimating the best next step, improving on Dijkstra’s method for specific point-to-point searches.
- Despite its age, A* remains one of the most versatile algorithms and is widely applied in robotics, gaming, and AI for solving complex routing and mapping problems.
Subscribe on:
Transcript
Roland Meertens: Let me start with a fun fact and that is that did you know, Anthony, that in 1966 Seymour Papert created the Summer Vision Project?
Anthony Alford: Oh, I did not know that.
Roland Meertens: And his idea was to create a significant part of a visual system, which can do pattern recognition.
Anthony Alford: Okay.
Roland Meertens: In 1966. And they did break this down into sub-problems, which can be solved independently. Because doing pattern recognition in one summer in 1966 is a hard task. So examples of a sub-task is dividing the image into regions such as likely objects, likely background area, and chaos. And I don't know what class chaos is, but I want more of this.
Anthony Alford: But do you?
Roland Meertens: Yes. As I said, I was just reading the technical review today, but what they wanted to do is view shape and surface properties, and extensions they thought of for the end of summer, like in August, would be handling objects with complex patterns and backgrounds such as a cigarette pack with writing and bands of different color, tools, cups, et cetera, which shows that in that time it was still normal to smoke and have your cigarettes packages in the workplace.
Anthony Alford: I think they probably came with your desk when you got hired.
Roland Meertens: Yes, it's such an interesting look at how life was in 1966. The other fun fact I have by the way, is that in 1980, this person, Seymour Papert, wrote a book Mindstorms: Children, Computers and Powerful Ideas, where his thesis was that children can learn faster and be more social when they're using computers for learning. And this book is what Lego named their robotics kits after.
Anthony Alford: Very cool. Those things were really fun to play with too.
Roland Meertens: The Lego Mindstorm robots are amazing. You get any project done quickly instead of having to play around with installing operating systems in Linux and whatever. It's amazing.
Anthony Alford: Very cool. I did not know that.
AI Winter [02:26]
Roland Meertens: Welcome to Generally AI, season two, episode three, where I, Roland Meertens, will be discussing the AI Winter with Anthony Alford.
Anthony Alford: That's right, Roland. I'm really looking forward to it.
Roland Meertens: Yes. So I found an AI algorithm which was invented before the first AI Winter, which is still relevant today. And you actually looked up all about AI Winter. So shall we start with what you did?
Anthony Alford: I shall. Hopefully I'm not going to steal any of your thunder because a lot of the technologies that have come and gone through the AI Winters are still here with us and I'm going to weave that into the story. And by the way, when we're recording this in July and I'm in the Northern Hemisphere, it's really not winter, it's summer. It's pretty hot. So I kind of would like a little winter at this point.
Roland Meertens: Even in London, the weather is warm today, which is very rare.
Anthony Alford: It's a high of like 25, 27 degrees centigrade. You know we laugh at that. But anyway, I digress. Those of our fans who are still following us after the first season may remember when we talked about Alan Turing and Claude Shannon and how they both made early contributions to AI. And you probably remember that they did this a very long time ago. The term artificial intelligence was coined in the 1950s.
Roland Meertens: Where they also wanted to invent AI over the summer. I see a pattern.
Anthony Alford: The Summer of AI followed by the AI Winter. Not to foreshadow, right?
Roland Meertens: Yes, indeed, indeed.
Anthony Alford: So when people talk about AI, these days of course, they mean neural networks. They mean deep learning. They mean ChatGPT. But the key technology is the neural network. That was not always the case. Actually throughout the years, AI researchers have explored a lot of technologies like symbolic logic, like trees and search, but neural networks have been around for just about as long as AI has been around. And hopefully, not to steal your thunder, but that it was there before the first AI Winter and is still around.
Roland Meertens: I will talk more about your search algorithms.
Rosenblatt’s Perceptron [04:33]
Anthony Alford: Ah, okay. Well, in 1957, a scientist named Frank Rosenblatt developed the perceptron. And I probably don't have to explain neural networks and perceptrons to our audience, but why not? We've got time. A perceptron is a mathematical model of what a single biological neuron does. It has several numeric inputs. It computes a weighted sum of those inputs, so each input has a different weight. And then it thresholds that weighted sum to decide whether to fire its output. The magic though is that you don't have to figure out yourself by hand or by thinking what the weight should be. You teach the perceptron what the weight should be using supervised learning.
Roland Meertens: Did he already look at backpropagation or it is only a single neuron, right?
Anthony Alford: That's right. He did not use backpropagation, but his learning algorithm was: you put the inputs in, you knew the expected output, you got the actual output and you could difference that. And then there's a simple update algorithm to update the weights.
And then you do this with a bunch of input-output examples. Do it iteratively, adjust the weights until it gets as correct as you can. And Rosenblatt actually wrote a software implementation of this perceptron. I think he had a bank of perceptrons. It could classify a 72-by-72 pixel image. They actually used patterns on a punch card for the images, the image inputs.
Roland Meertens: Yes.
Anthony Alford: He did a set of experiments and in one experiment he showed the perceptron could distinguish between the letter E and the letter X, even if they were rotated, and do it about 95% of the time, which is not bad for 1960.
Roland Meertens: Yes, even when it's rotated, quite big grids on punch cards?
Anthony Alford: I don't know how big an angle of rotation, but probably a few degrees, I think.
Roland Meertens: Yes.
Anthony Alford: But you would think in 1960 if they could do this kind of computer vision, why didn't we get ChatGPT in the seventies and AGI before Y2K?
Roland Meertens: Compute and not enough GPUs.
Anthony Alford: Well, yes, that was one reason. But also your guy, Seymour Papert, and Marvin Minsky, they published a paper in 1969. They had done research showing a severe limitation of perceptrons.
Roland Meertens: Oh, I think I know what it is.
Anthony Alford: You know what it is? It can only learn a line. Technically speaking, it can only discriminate between classes that are linearly separable by a hyperplane. So the classic example is: a perceptron cannot learn the XOR function, the exclusive-OR function.
Roland Meertens: Yes.
Anthony Alford: A lot of people gave up on perceptrons. Now, of course, perceptrons weren’t the only thing in AI: there were a lot of other rumblings in the AI field. Apparently, I didn't know this, there was that computer vision project in the '60s, but there was also a machine translation project in the '60s that was not meeting expectations.
So this has that classic story, which is too good to be true, but it's illustrative. You could put in the English text, "The spirit is willing, but the flesh is weak", translate that to Russian and then translate the Russian back to English and get, "The vodka is good, but the meat is rotten".
Roland Meertens: Yes, I heard of that example before. It's so funny.
Anthony Alford: Yes, probably it's not true. The good stories are never true.
Roland Meertens: Yes, it's good still. It could be true.
The First AI Winter [08:09]
Anthony Alford: It could be true. So in 1966, the US government pulled its funding from machine translation. In 1973, the British government published a report called the Lighthill Report that criticized the lack of progress in AI and they subsequently cut funding for AI research in their universities. In the US, DARPA was funding a lot of AI. In 1969, they changed their policies to no longer fund undirected research, but instead to focus on concrete projects with obvious military applications. And after the Lighthill Report, DARPA didn't fund a lot of AI research either. So the end of AI Summer had come, it was AI Winter.
Roland Meertens: Yes, the end of the free money.
Anthony Alford: Yes. Now, that doesn't mean there was no AI research going on at all. In fact, some people dispute the fact that there actually was an AI Winter based on things like: people enrolled in AI organizations like special interest groups and so forth. But the funding was definitely dried up.
Roland Meertens: So there were still people studying it or students starting or being interested in AI.
Anthony Alford: Right. There were of course labs like the Stanford AI Lab and Carnegie Mellon, but the scale and the funding globally had been reduced.
Roland Meertens: Yes.
Anthony Alford: And in fact, some people were actually still working with perceptrons, but now they were calling this a more general term of artificial neural networks. In their paper, Minsky and Papert did say that neural networks could learn exclusive-OR and other nonlinear functions if you had multiple layers of perceptrons.
Rosenblatt just had a single layer, but if you had multiple layers where the output of perceptrons are the input of the next layer of perceptrons, you could learn nonlinear functions. In fact, you only need a single hidden layer to learn exclusive-OR.
Roland Meertens: Yes.
Anthony Alford: But nobody knew how to do the training algorithm for them.
Roland Meertens: Oh, okay. So you can easily show that with the right weights, you can solve XOR, right?
Anthony Alford: Yes.
Roland Meertens: But nobody knew how to do backpropagation.
Backpropagation Brings Back AI [10:18]
Anthony Alford: Right. And that's in fact what happened. So around 1985, a group of researchers, including Geoff Hinton, which is a name you may know, they came up with an algorithm for training these multi-layer perceptron networks: gradient descent with backpropagation, AKA backprop. What's funny is Hinton's paper literally says that the mathematical derivation of it can be omitted by the reader who finds such derivations tedious.
Roland Meertens: Okay.
Anthony Alford: Which I think that's definitely me, so I'm going to skip over that. I think probably, again, most of our listeners are familiar with gradient descent and backprop. And in fact, those ideas were not new in 1985, it's just that nobody had applied them to neural networks until then.
Roland Meertens: Yes.
Anthony Alford: Neural networks were back. It was the Summer of AI again.
Roland Meertens: Yes. What are we going to do now?
Anthony Alford: Well, in 1989, a researcher named Yann LeCun, again, another name you may know, he was using multi-layered neural networks to recognize handwritten digits, 16 by 16 pixel images, and he was getting 95% accuracy. So AI was back.
Roland Meertens: Pretty good. I assume that he had applications for things like sorting letters in the post office.
Anthony Alford: Again, you're familiar with this. Yes, he was doing digit recognition for, I think, post office applications.
Roland Meertens: Yes, interesting.
Anthony Alford: I remember the early '80s, and it was a great time in so many ways, Men Without Hats and the "Safety Dance" and other things. And there was an AI boom. There were things like expert systems, which were very popular. And in Japan, the Japanese government had started to spend a lot of money on their Fifth Generation Computing project. And in the US, DARPA was doing something similar. But guess what happened?
Roland Meertens: I'm feeling that there will be a second AI Winter.
The Second AI Winter [12:12]
Anthony Alford: Second AI Winter, 1990s, rock and roll was over and it was grunge and flannel shirts because of the AI Winter being so cold. Yes, AI Winter. And for neural networks in particular, people were running up to limits there. The backprop training algorithm worked, but it didn't work great on very deep networks, networks with lots of layers. I'm sure you know what the problem was.
Roland Meertens: I'm assuming there will be vanishing gradients or exploding gradients.
Anthony Alford: That's exactly right. And you had mentioned hardware earlier: it was slow, it was the '80s.
Roland Meertens: Also, the amount of data. How many data sets can you fit on a floppy disk?
Anthony Alford: Exactly.
Roland Meertens: This is even before the small floppy disks.
Anthony Alford: Yes, we had the eight-inch floppy disks. But yes, you're exactly right. So the gradients were a problem. The hardware was a problem, and the data sets were a problem. So again, AI Winter in general and for neural networks in particular. So let's skip over the '90s and the early 2000s. And let's get to the part of the story that was----actually, feels like it wasn't that long ago, but if you think about it, it was 2012.
Roland Meertens: It's already been years.
Anthony Alford: 2012.
Roland Meertens: Yes, yes.
Anthony Alford: It's 12 years, Roland.
Roland Meertens: Yes, yes. Time flies.
The Endless Summer of Deep Learning [13:30]
Anthony Alford: Time flies. So Hinton and some of his colleagues at Toronto had published their results. They were using the MNIST dataset of handwritten digits, which is similar to what LeCun was using in '89. They were getting better than 99% accuracy. But the gold standard, of course, of recognizing objects and images by then was ImageNet. ImageNet had come. And there's the dataset problem solved, right?
Roland Meertens: Yes.
Anthony Alford: Millions of images, 256-by-256 pixels.
Roland Meertens: Yes. Of loads of different types of objects. Fei-Fei Li made this dataset.
Anthony Alford: Exactly. And certainly kicked off the modern era of deep learning, I think. And then using that, one of Hinton's students trained a neural network that got about 85% accuracy compared to the previous record of less than 75%. So that was AlexNet, right?
Roland Meertens: Yes.
Anthony Alford: And so those two nets, ImageNet and AlexNet, had really kicked off the age of deep learning.
Roland Meertens: Yes.
Anthony Alford: And it's been endless summer ever since.
Roland Meertens: Yes. It's crazy that we keep seeing that the more data you give these networks and the bigger you make these networks, the more they can learn.
Anthony Alford: And in fact, I think it was OpenAI that---pretty famously---their laws of scaling, that they've plotted that it's a power law. As you increase, as you increase model size, as you can increase training, compute, the training loss is predictable.
Roland Meertens: But would you then say that the second AI Winter lasted till 2012?
Anthony Alford: Well-
Roland Meertens: When would you say that the second AI winter started and ended?
Is Winter Coming? [15:09]
Anthony Alford: These things are always kind of like…it's not a bright line like the solstice or whatever, but it's certainly the 1990s and the early 2000s are considered to be one AI Winter. And so you might start thinking, well, when is the next AI Winter?
Roland Meertens: Yes. When are you predicting that we will all be fired and need to find a new job?
Anthony Alford: What if I told you that it already happened?
Roland Meertens: Oh. Tell me more.
Anthony Alford: Of course, as I said, since 2012, it's been nonstop AI and we're so used to hearing about it now all the time. But apparently, in late 2018, early 2019, people already were predicting another AI Winter. There were headlines and think pieces talking about deep learning has reached or would soon reach its limits.
Roland Meertens: Yes.
Anthony Alford: And this talk continued through 2019 and on into 2020. And in fact, if you look at things like the number of AI publications, according to Wikipedia, for the years 2021 and 2022, they actually did drop: the number of publications dropped like 30%.
Roland Meertens: Interesting.
Anthony Alford: But then of course, was that AI Winter or was it a global pandemic?
Roland Meertens: Yes. Although I do feel that in 2018, people were very excited about seeing the performances of networks go up a lot every year and every year.
Anthony Alford: Yes.
Roland Meertens: And we basically said at that time, perception is solved. It's a solved problem.
Anthony Alford: More or less. So what's interesting is, well of course you know that '21 and '22 was really a blip. December of 2022 was the release of ChatGPT. And since then we've had almost two years of constant AI Summer, we have had a Heat Wave of AI, but people are still predicting another AI Winter any day now.
Roland Meertens: Yes, it can't always go up.
Anthony Alford: Exactly.
Roland Meertens: Unless one day we all work in AI. Everybody is working at an AI company nowadays.
Anthony Alford: And in fact, people like LeCun are saying things like: these LLMs, while impressive, they will not give us AGI, they're not general intelligence.
Roland Meertens: Yes.
Anthony Alford: LeCun has been pretty vocal about that. Some people disagree, some people think LLMs can do it. But back to AI Winter, you've probably heard of Rodney Brooks.
Roland Meertens: Yes.
Anthony Alford: He's the guy that founded iRobot. He's been working in AI for my entire lifetime.
Roland Meertens: Yes.
Anthony Alford: He has a blog where in 2018 he made a bunch of predictions about future technological advances, things like autonomous vehicles and space flight and AI. And he updates these every year with how has he done.
What's interesting, in 2018, so around the time people were predicting the limits of deep learning, predicting a new AI Winter, he wrote on his blog, he predicted that the next big thing in AI would happen no earlier than 2023 and no later than 2027. And he said, "I don't know what this is, but whatever it turns out to be", this is a quote, "whatever it turns out to be, it will be something that someone is already working on and there are already published papers about it". He said that in 2017.
Roland Meertens: Yes. So what did he refer to as the next big thing?
Anthony Alford: In January of this year, he said it's ChatGPT.
Roland Meertens: Yes.
Anthony Alford: And as we know, we talked about last season, the T in GPT, the transformer, the paper was published in 2017.
Roland Meertens: '17, yes, indeed. Yes.
Anthony Alford: So he's taking a victory lap on that prediction.
Roland Meertens: Yes, but it's also an easy prediction to say-
Anthony Alford: Well, that's what he said.
Roland Meertens: "There will be the next big thing in the next five years and someone is already working on it".
Anthony Alford: He said that exactly. He said, "I've seen this so many times. I know that the next big thing is always going to be: somebody's working on it and five years later…" What's interesting, in that same blog post in January of this year, he predicted another AI Winter. He said AI Winter is just around the corner and it's going to be cold.
Roland Meertens: Yes. How cold is it going to be?
Anthony Alford: I don't know. Personally, I don't have a prediction. I just know that people like that, I obviously respect Brooks a lot and respect his prediction. On the other hand, this is sort of like that thing about: "So-and-so has predicted nine of the last five recessions". It's very easy to predict there's an AI Winter if you just say: it's going to happen next year, it's going to happen in a couple of years, you'll eventually be right.
Roland Meertens: Yes, it's true, true. And also there will always be one person correct and that's the person you talk about. Survivor bias.
Anthony Alford: Right. But again, he's been through this so many times.
Roland Meertens: Yes.
Anthony Alford: He's probably got good reasons for thinking it.
Roland Meertens: How was it for you, Anthony, to live through the AI Winter?
Anthony Alford: What's interesting is I was doing my own grad school research in, it wasn't AI, it was intelligent systems, intelligent robotics in the late 1990s, which was certainly during one of those winters.
Now, what's interesting is in our work, we were inspired a lot by Rod Brooks, and we were doing a lot of stuff like behavior-based robotics, which was very different from what we contrasted with traditional AI. Things like: tree search and perception and modeling, 3D world modeling and planning and stuff like that. It was fun. I enjoyed it. I was not doing things like neural networks. Although what's interesting, somebody else in our lab was doing neural networks.
Roland Meertens: Yes.
Anthony Alford: And I talked with him a few years ago and he said, "It's great. It's coming back and my stuff is still relevant".
Roland Meertens: Yes, I must say that I learned about neural networks in university in 2009, 2010. And then as students, we kind of acknowledged this is outdated technology, this is not state of the art, you shouldn't use this too much. And then in 2014, of course, you got AlexNet. So we were like, "Oh, okay, interesting. Good on the teacher for teaching us neural networks, but let's see where it goes". And it kept blowing up and kept blowing up. Interesting experience.
Anthony Alford: So that's my weather report on the AI Winter.
A Star Is Born [22:28]
Roland Meertens: All right. So what I wanted to do with you, Anthony, is take a look at an AI algorithm, which was invented before the first AI Winter and which is still relevant today. So you already talked about neural networks, which was very much up, down, up, down. But I was thinking about what are examples of what people consider to be AI, but which kind of pass the test of time where people can always use it, it's always relevant, it's always good, it's always interesting.
And I think that the thing I want to talk about is A* search, and I think most listeners are familiar with the A* search algorithm. People probably heard of it at least. And I think that alone shows that it is an everlasting algorithm. That even if you are not into AI, you are still familiar with A*.
Anthony Alford: I've heard of it.
Roland Meertens: Yes. You probably had to implement it for some coding tests. The one thing which I also find interesting about AI in general is that in the past, people would say, "Oh, search is AI and world modeling is AI". Nowadays, you wouldn't really say that search algorithms are pure AI. Would you? Or if you talk about chess algorithms or something, you wouldn't really say, "Oh, it's AI", it's more like computer science.
Anthony Alford: `Yes. I tried to find the quote, and I know I'm not imagining it, but I couldn't find it. But there's a quote that's something like: AI just means something that computers aren't supposed to be good at. And once computers become good at it, it's no longer AI.
Roland Meertens: Yes. I think I always summarized it as "once it works, it becomes computer science".
Anthony Alford: Oh, that's awesome. Okay.
Roland Meertens: Yes, this is one of these algorithms which became so good, it became computer science. So in terms of history, do you know when A* was invented?
Anthony Alford: I don't. I'm guessing probably the 1950s or '60s though.
Roland Meertens: Yes. So it's invented in 1968 by Peter Hart, Niels Nielsen, and Bertrand Raphael of the Stanford Research Institute. I will also put the paper in our show notes so you can read it yourself. And what's also interesting is that it was invented for Shakey the Robot for his path planning. I'll also put a PDF of that report in the show notes.
I read both the original paper and looked through the report for Shakey the Robot. And what disappointed me was that in the report for Shakey the Robot, they just mentioned using a breadth-first search.
Anthony Alford: No A*?
Roland Meertens: So that's what I find interesting is that everybody always says, "Oh, A*", Wikipedia says, "Oh, it's invented for Shakey the Robot". But if you look at the report, I think at some point they invented it and then they already thought that even A* was too slow to do a grid-based search.
Anthony Alford: Interesting.
Roland Meertens: So if you look through the paper, what I really like about papers which are this old, is that they have very smart inventive solutions for problems. So they're not doing a grid search you would do nowadays. You would divide the room into tiles of 10 by 10 centimeters and navigate between those tiles.
They have something where they define the obstacles and then they have the tangent towards these obstacles so that the robot goes in the most optimal path around these obstacles and only plans from object edge to object edge. So the amount of search space becomes super low. So they don't even need to think of A* anymore in the reports.
Anthony Alford: With compute and other constraints at the time, they probably had to do a lot of these kinds of optimizations.
Roland Meertens: Yes. And also what you mentioned before in terms of representing images on punch cards, I would love to do more episodes around that, it's such an interesting topic. Maybe next season we have more time for that.
The other thing to note about A* is that it is similar to Dijkstra's algorithm, which we discussed as a fun fact at the start of the last episode. But A*, the big difference is that A* is really point-to-point and not point-to-world like Dijkstra where you calculate the distance to the entire world.
Heuristic: the Key Ingredient [26:49]
Roland Meertens: And the thing I really like for listeners who don't really know, A* adds a heuristic. So you have a heuristic on how close are you to actually getting closer to a solution. So if you're going from point A to point B, if you're getting closer to point B, that's probably worth a point which you want to prioritize investigating first rather than going back to the point.
Imagine that you're navigating from Amsterdam to Paris, as a human, you just follow your finger towards Paris, you know where to go and that's what you explore first. And then if you find that some road is blocked, then you backtrack and you start searching around it. And here, what's cool is that the better your heuristic is, the more you can prune away from your solution space.
Anthony Alford: Right. Didn't this become really the core of a lot of chess-playing engines as well?
Roland Meertens: Yes. And that's what I really liked, the versatility of the algorithm is super big. I've seen it being applied in Super Mario where people had a heuristic on how to play Super Mario. They would expand the game states and then pick the state where Mario was the closest to the right boundary or something or had the most points, whatever. So I've seen it being used there.
For chess, I think they use these trees where you have some kind of probabilistic tree structure where you keep expanding, but you do keep estimating how many points you have, what your estimated win chance is. But yes, they are super versatile. You have loads of different applications and not just mapping.
And even when there is mapping, it's still, I think, one of the best algorithms. Whenever I have to program a search algorithm for anything, I try to think of: how can I add a heuristic to this so I know that I'm closer to getting to the actual solution.
Anthony Alford: That makes sense. What's interesting is we could probably do another episode on A* versus something like reinforcement learning and the parallels there. Because basically what it is, right, how do you pick the next best action?
Roland Meertens: Well, so it's a combination between how good are you or what is your state and where do you probably want to be and can you keep expanding everything until you get closer to it? The one thing which I also, as I said, it's really an everlasting algorithm.
So one thing which people probably noticed when they ever visualized or implemented A* is that A* can be slow if your heuristic isn't good or if you just have a lot of space to explore. And you can see this if you go to the Wikipedia article, I think they have a visualization of expanding a search horizon, not even a very big maze, but you do still keep expanding a lot of states. So I would say that if someone plans a route, I don't know, from one end of America to another end of America, you and I would just say, "Let's go on the highway".
Anthony Alford: Yes. Interstate 40.
Roland Meertens: Interstate 40. So that's, I guess, your heuristic. But for mapping companies or for graphs, there is an alternative, right? Contraction hierarchies is an example where you contract parts of the graph. So you can ignore the smaller streets when you have to travel a large distance. So you just navigate a graph on a higher level and then navigate back down onto the smaller streets. So there are alternatives.
Anthony Alford: So you may not have studied this part, but how does it prevent getting into a cycle?
Roland Meertens: Oh, you keep track of what you already expanded.
Anthony Alford: I see, okay.
Roland Meertens: Yes, you keep track of which nodes you already visited. That's what I generally do. So because you know that A* found the fastest path towards a certain spot, you also don't have to expand it anymore afterwards. It's either expanded or visited, one of two works.
Anthony Alford: Okay, nice.
An Evergreen AI Algorithm [30:36]
Roland Meertens: Yes. So just going back towards the everlasting aspects. As I said, there are for mapping nowadays, you would say that since 1968, there must have been better algorithms invented, right? It's a long time.
But what I like is that sometimes I talk to people working at map companies and whenever they have to plan very specific routes, for example, imagine that you are a truck who can't go over certain bridges, maybe you are a truck which has to ride on roads which are minimum this wide. Maybe you have customers who have a sports car and they want to drive over nice and windy roads with great views.
There's loads of different customers who have demands for which roads they can take. And that means that once you have a lot of these different things to factor in, these companies just switch back to A* because this algorithm can always deal with any kind of constraints about what nodes you can and cannot expand to.
Anthony Alford: That's really cool. I never thought of that. It's that heuristic that you have to have lets you essentially guide your result so that it meets your constraints or your desires.
Roland Meertens: Yes, the heuristic can be anything you want. So in the case of mapping, you would probably take a distance heuristic. That makes a lot of sense.
Anthony Alford: But you can also add the windiness or the width or something of the road?
Roland Meertens: Yes, I guess that could be something where you say, for example, I think the trucks is a better example where if you have a pre-computed graph, a contracted graph for the highway, if there is one edge in your graph, you have to take the minimum part of your graph.
If the maximum weight of one bridge is two tons, this entire edge becomes unusable for your truck. But with A*, you simply say, "Can I go over this edge with my truck? No? Okay. Well, then I won't expand this node". So you have one algorithm which can just handle everything.
Anthony Alford: I see. That's pretty awesome.
A* in Games [32:46]
Roland Meertens: It is pretty awesome. The last thing which I want to encourage listeners to take a look at is a problem which Factorio had. Do you know the game Factorio?
Anthony Alford: Is that one of the ones with the snakes? Which one is this?
Roland Meertens: No.
Anthony Alford: That's Slither.
Roland Meertens: Slither.io. Yes. No, Factorio is a factory building game.
Anthony Alford: Oh, okay.
Roland Meertens: Which is extremely addictive to people like me. If you enjoy automating things and solving problems, like most people who are programmers will, then Factorio is like crack. It is absolutely insane how addictive this game is.
Anthony Alford: Well, I'm going to stay away from it then.
Roland Meertens: Yes, smart. Yes. Sometimes I manage to convince friends to download the game or buy the game and then a week later you see them with black dots around our eyes being like, "I haven't slept in a week". It's insane how this game just grips people.
Anyway, the goal of the game is that you want to build a big factory and launch a rocket, but you have aliens on the planet which you at some point can start shooting. So once you shoot an alien at a big distance from your factory on the landscape, the alien tries to plan a path to your base to start attacking whatever attacked him.
And Factorio faced the problem that this pathfinding on these massive maps can be slow, especially if you have to plan around a big lake or something like that. So they already implemented A* and the heuristic was simply the distance heuristic with what is the path around the lake.
So A* was too slow, but you can modify the heuristic. And the heuristic is basically you want to get quickly back to the place where the fire originated from, where you want to go to. So what they did is they had a second search algorithm which would search from the place they want to attack back to the aliens over all the tiles they deemed walkable.
So they would divide the world up into bigger tiles and then they would just calculate: can I cross this tile or not, which is faster than having to do this for a massive map. So they have this very global idea. As I said, if you want to go from Amsterdam to Paris, you know roughly where Paris is, so you can really quickly expand in this direction. Or if you have to go around the lake, you have to go around the lake. It doesn't make sense to start searching away from the lake.
So they modified the heuristic, which again, most people set to the Euclidean distance, but instead, they calculate a rough distance for each tile back to the place they want to go. And that way they can nudge the search very quickly in the right direction. And then they just still use a normal A* algorithm with this new heuristic.
So I will put the link to the blog in the show notes so you can read it yourself and see the visualizations. It's extremely cool to see how you can modify A* and how much flexibility you have with it.
Anthony Alford: It's like the Swiss army knife of algorithms.
Roland Meertens: Yes. It genuinely is a Swiss army knife, which I love implementing. It's always fun. It's always good. It's easy and extremely efficient. And you can build in your own nudges and heuristics very fast. I love it.
Anthony Alford: You'd think they would've called it A++ or something.
Roland Meertens: Yes. I think the reason for calling it A* was that the star was meant to indicate that this was optimal.
I know there is something around where in the paper they mentioned that this is the optimal way to plan a path, that it always finds an optimal route. And then another researcher said, "No, but you haven't thought of this constraint".
So they published a paper about how that's not the case, that you should maybe modify something in the order you expand nodes. But then later, another researcher published a paper showing that, "Oh, but it actually works", like there was a mistake in the other paper. So there's a lot of drama around A*.
Anthony Alford: I'm going to have to read up on it. I love drama.
Roland Meertens: Yes, I mean drama in the most academic sense where someone finds a counter example.
Anthony Alford: Well, it's the old saying that in academia, the fights are so brutal because the stakes are so low.
Roland Meertens: Yes, that must be true. Any last questions about A*?
Anthony Alford: No. As you can guess, I had heard of it and was familiar with it, but I wasn't aware of how useful it was or how versatile and how long it had been around.
Roland Meertens: Yes, it's a true winner of the Land before AI Winters. Always sticking around, always there, always trustworthy, always fast.
Anthony Alford: Just like the mammals after the dinosaurs went extinct, huh?
Roland Meertens: Yes. I don't know how they came about because breadth-first search is also still around. It's just amazing that there's such a versatile or easy to implement algorithm for this case.
Anthony Alford: Sometimes a simple thing is great.
Words of Wisdom [37:54]
Roland Meertens: It's exactly what you need. So words of wisdom. Did you learn anything new this podcast? Or did you learn anything yourself recently?
Anthony Alford: In one of those strange coincidences, I'd finished [reading] my last book and picked up an old book, an old favorite, The Moon is a Harsh Mistress by Robert Heinlein, one of the great classics of sci-fi. And you may know that, spoiler alert, one of the main characters is a self-aware computer.
And this book was written in 1966. What's interesting is in the very beginning of the book, part of the description of the computer is that it has "associative neural networks" attached to it. So I thought that was kind of interesting and fun.
What also is interesting, in this book, the computer learns how to do essentially a CGI version of a person. They made up a fictitious person and the computer creates essentially a real time artificial video, photorealistic video of the person along with voice and so forth, which has never been done before in [the book’s] universe.
Roland Meertens: Yes and it's still not done.
Anthony Alford: Well, yes, we're getting there. What's funny, I don't know if you're an aficionado of classic sci-fi like Robert Heinlein. Robert Heinlein…in his books in the 1940s and 1950s, he had a lot of space technology, like nuclear-powered, faster than light rockets, but all the navigation is done with slide rules and things like that. So he missed out on computers early, but by the '60s, he basically just jumped to: "Okay, computers are now self-aware".
Roland Meertens: Interesting. Yes, I love the old sci-fi where if you read it now, you don't realize that these people didn't know what we have now.
Anthony Alford: There's a couple of old Heinlein stories from the '50s and '60s where characters essentially have cell phones and it's just like a casual thing.
Roland Meertens: Yes. If you read it now you just think, "Oh, of course they have a cell phone", but no, the guy has to invent cell phones in his head.
Anthony Alford: Exactly. Anyway, I don't know if that's words of wisdom, but it's something that I had not remembered.
Roland Meertens: It's a good fun fact. The one thing which I started looking at yesterday was the history of gliders and airplanes and parachutes. So the one thing which I discovered is number one, the first aerostatic flight was carried out by the Montgolfier brothers at Versailles in 1783.
Anthony Alford: Yes.
Roland Meertens: That's interesting fun fact number one. That's quite a long time ago, right?
Anthony Alford: Yes. I think, again, one of those stories that may not be true but is really good: supposedly Benjamin Franklin witnessed this and somebody remarked how useless it was and he said, "Well, what's the use of a newborn baby?"
Roland Meertens: Yes, that's one way to phrase it. Anyway, so then the other thing which I was wondering is then: when was the first parachute invented? And here, Wikipedia says that the modern parachute was invented in 1783. It's the same year, right?
Anthony Alford: They jumped out of the balloon with it, I think, right?
Roland Meertens: Yes. And there was someone who jumped off a building, I guess. Also, I think at some point someone invented a frameless parachute and I think they brought it with them on a balloon trip in 1797. And then at some point they ditched the balloon, so they had to use a parachute or at least that's what the person said, "Oh, the balloon had problems, so I had to use my parachute". Maybe it was like sales talk, you don't know.
Anthony Alford: Probably we should caveat that it was the first successful parachute incident.
Roland Meertens: Yes.
Anthony Alford: You know somebody tried it before and did not succeed.
Roland Meertens: Yes. The first time that someone tries a parachute is by jumping from a building, but then they invent these balloons so then they can jump from even higher. So in 1785, apparently someone demonstrated it as a means of safely disembarking from a hot air balloon. I have Blanchard's and I read it on Wikipedia, his first parachute demonstrations were conducted with a dog as a passenger. Yes, sad.
Anthony Alford: Just like the Russians, right?
Roland Meertens: Yes.
Anthony Alford: Sending a dog into space, let the dog test out the parachute.
Roland Meertens: Anyways, the reason that I was looking at this was that I was reading a mechanics magazine from Saturday, September 25th, 1852, where George Cayley is talking about governable parachutes. So George Cayley has basically invented a glider here: it's an airplane without any motor, so it is a glider, and he basically calls it a governable parachute. So I will also put this article in the show notes. It's quite interesting to read. Gliders or airplanes were called governable parachutes before they were called gliders or airplanes.
Anthony Alford: They needed to workshop that one a little better.
Roland Meertens: I like it. If you don't have an airplane, what would you call it? And you do have parachutes because they have been around for a long time. Parachutes are old news now.
So what if you can have a governable parachute? He also describes that to start this governable parachute, you can maybe hang it behind one of those air balloons. So his idea was to go up behind an air balloon and then release it and have his governable parachute be steered.
Anthony Alford: He didn't have a fast enough motorboat.
Roland Meertens: He didn't even have a motor. This is before the motor.
Anthony Alford: Had a steam train.
Roland Meertens: But as you say, motorboat: if you look at the illustration on the front page of this thing, he is sitting in what very much looks like a massive boat or a chariot. It looks more like a boat than a chariot.
Anthony Alford: Interesting.
Roland Meertens: Yes, it's fun. Thank you so much for recording this podcast, Anthony. Thank you so much to the listeners for listening to this podcast. Please like it if your podcast platform has an option for this and please tell your friends all about it and make sure that they listen to this.
Anthony Alford: Thank you, Roland. It's a pleasure as always.
Roland Meertens: Yes. Thank you very much for recording this with me, Anthony. I like it as always. The only last fun fact I still want to tell you is that I think in one episode last season, I was complaining about my Apple Watch and that it didn't show the correct time.
I'm done with it. It was still showing the wrong time last week. I bought a Garmin watch. I now have the correct time. And instead of the battery lasting for half a day, even though the watch is relatively new, I now have, I don't know, 17 days of battery life.
Anthony Alford: Wow.
Roland Meertens: I like it.
Anthony Alford: And it works with your iPhone?
Roland Meertens: It works with my iPhone, yes. It shows my messages whenever they come in.
Anthony Alford: I might look into that.
Roland Meertens: Yes, as I said, I was kind of fed up. Especially if I would cycle to work, then cycle somewhere else, cycle back to my home and then take a run. The watch would be dead. It can't keep up with an active lifestyle somehow.
Anthony Alford: Ridiculous.
Roland Meertens: Now, last weekend I went on a hike. I walked 25 kilometers, had the map on the watch the whole time and it has only used a quarter of its charge or something. It's crazy.
Mentioned:
