Generally AI Episode 6: You Are Here

Introduction

Roland Meertens: Let me start with the fun fact to start off. So in 1592, the Dutch cartographer, Cornelis Claesz made a map of France. So this was basically an amazing map which showed all Western Europe. However, after they made this map, after 1592, they invented so many new techniques to measure distances like triangulation, some localization methods we are going to talk about today, which allowed them to create a way more accurate map.

So in 1684, they made a whole new map of France using these new techniques. These are more accurate, but the king was shocked because his kingdom had suddenly shrunk and he complained that this new map cost him more territory than an invading army. And the other fun fact about this map is that it also showed the outline of the previous map, so basically showing the previous map was so wrong and look at how much better or smaller the land is on this new map.

Anthony Alford: The world is shrinking, right?

Roland Meertens:  Yes, I don't know. It just feels like product managers being angry at the engineers for telling them that something is impossible.

Anthony Alford: If you think product managers get angry, wait till you tell a king.

Roland Meertens:  Indeed. Welcome to Generally AI, an InfoQ podcast. This is episode six and the last episode of this season. And I, Roland Meertens, will be diving deep with Anthony Alford into the world of mapping and localization.

Anthony Alford: We are.

Roland Meertens:  Yes, we are going to discuss how to know where you are as a human. And then you, Anthony, are going to talk about where you are as a robot. And then I have a grand finale where we are going to talk about where satellites are and how they localize will be confirmed by someone who actually works on localization of spacecraft at NASA.

Anthony Alford: Oh, really?

Roland Meertens: Yes. I don't want to spoil a surprise, but that will be the surprise at the end of the episodes. So please stay here and listen.

Anthony Alford: I'm excited.

Human Navigation [02:21]

Roland Meertens: Yes, I'm excited as well. This is really good. Anyways, as I said, we're going to start by localizing on earth with old-fashioned methods. Then we can talk about how robots do it. And then we are going to talk about satellites.

And the reason I wanted to do it in this order is that last October I started thinking about localization using stars because NASA published an article Guide Star Found as Euclid's Navigation is Fine-tuned, where Euclid is a satellite making a deep map of the universe. And the issue was that the Euclid satellite had lost its guide stars.

And I was thinking, "If we don't have GPS in space, how do we localize ourselves?" How do we as humans know where we are? How do you normally determine where you are, Anthony?

Anthony Alford: Oh, man, I look at my phone.

Roland Meertens: Yes.

Anthony Alford: My phone knows where I am.

Roland Meertens: Yes, indeed. Everything is based on GPS. How would you do it in the past?

Anthony Alford: Well, usually I'm at wherever... So when I wake up in the morning, I'm wherever I went to bed. So somehow we just know where we are. We're at home or we're at work.

Roland Meertens: Yes, I think the easy answer is we generally don't really realize where we are on the whole sphere of the earth or we kind of do or we did using the stars. And I was always someone who was like, "Oh Yes, you just use the stars." But I never really figured out how. So I figured that you and I and multiple software engineers would enjoy hearing more about old-fashioned methods.

Anthony Alford: Sounds good.

Roland Meertens: Can you name a tool you would probably use?

Anthony Alford: Well, as someone who's read a lot of nautical fiction and some other things, you can use something called a sextant to do. It basically measures angles.

Roland Meertens: Yes, indeed. It measures the angle between two objects, but I never really realized what do you measure this on? So you could take an astronomical object like the sun and the horizon, and let's split it into two things. One is knowing your latitude and the other is knowing your longitude.

Because latitude, basically how high you are up on the earth, you can determine this for example, by knowing the angle between the sun at noon and the horizon, and then you can use a lookup table to figure out on which degree of the earth you are. The one thing I found a bit frustrating about this approach is that you only know that it is noon when the sun is at its highest point. So basically I guess you're staring at the sun for a full hour to see if it's really reaching the top.

Anthony Alford: So again, I mentioned that I read nautical fiction. So these are things like Horatio Hornblower or something like that. But they tried to keep a fairly good track of time with an hourglass. They had a guy whose job was to flip that hourglass every hour right on the spot. So they usually were pretty close to when the sun was going to be at noon, but you're right, you might have to wait around a while.

Roland Meertens: Yes, indeed. Actually, something I found interesting is that last week I was at a bridge pub which had a sundial-

Anthony Alford: Nice.

Roland Meertens: And I was told, "Okay, but a sundial is off by default." But this pub had both a sundial and a table showing how off it is at what time, so you can actually determine your offset between the actual hour and the sundial.

Anthony Alford: Very interesting. So how much would it be off? What was the peak discrepancy?

Roland Meertens: So this is where I say once you know how much off you are, then you can also know where you are because depending on where you are on the earth, it is off by a different amount.

Anthony Alford: Got it.

Roland Meertens: Yes, it's super confusing. But once you know how off you are, then you also know where you are. The other thing you can do is determine the angle to certain guide stars. You're also in the Northern Hemisphere, right?

Anthony Alford: Right.

Roland Meertens: Yes. Okay. So I think it's actually like a miracle that the north star is so perfectly above the North Pole because you can simply measure the angle between the horizon and the north star, where if it's directly on top of you zero degrees, you're at zero degrees. Longitude and you can just measure the angle and probably on the equator it's exactly at the horizon.

Anthony Alford: Yes. In fact, I believe there's something called precession of the equinoxes where the pole star is not always right over north, it's kind of wobbles. It takes a very long time, you wouldn't notice it. It's thousands and thousands of years.

Roland Meertens: When we start talking about North Poles, I always find it very difficult because there is the actual axis, the earth spins around and the magnetic North Pole and then this Pole Star and there's so many references you can take. Yes, it's difficult.

Also, there's no good equivalent for the... There's no south star, there's a southern cross which kind of works, which you have to interpolate yourself where the actual south is. There is a star there, but it's not that bright, not as bright as the north star. So that also makes it harder to navigate.

Anthony Alford: Interesting.

The Longitude Problem [07:42]

Roland Meertens: So now that we basically determined our latitude, the question is how can you find your longitudes, because the earth is spinning. Do you have any proposals?

Anthony Alford: Well, I already know the answer. Well, we mentioned the sun being at its highest point at noon. I mean that's the definition of noon is the sun is at its highest point. So if you know what time it is somewhere else, then you can figure out how far away you are there in terms of longitude.

Roland Meertens: Yes. So we already actually talked about it last week because I visited Greenwich, the observatory there in London. So this was called the longitude problem. And this was a problem for which in 1714, basically super high rewards were promised and I found four approaches online. And the first one you will probably know from robotics and that's just doing dead reckoning.

Anthony Alford: Correct.

Roland Meertens: So you can just keep track of your speed and your environment so you can try to figure out where you are based on that. And I found that this seems to be accurate to about 10 degrees longitude, which on the equator would be about a thousand kilometers.

Anthony Alford: As they say, close enough for horseshoes and hand grenades. I don't know if it's close enough for either one of those.

Roland Meertens: Yes, I figured that if you land at the isle of Cuba, you have no clue where on Cuba you are. And I also always thought, "Oh, why is it so important to know exactly where you are? Because just knowing that the island is Cuba is probably good enough."

And I realized how important it's by thinking back about robotics. If my robot is not accurate on my map, my obstacle locations are not precise. And this is even more important for ships because if you don't know exactly where you are around Cuba all your obstacle maps are basically worthless. So you are going to run into cliffs. Which are probably even more dangerous than the wall if you're a robot.

Anthony Alford: Well, that's why you have someone standing out there in the front looking for obstacles.

Roland Meertens: So apparently there used to be a lot of shipwrecks simply because people just didn't realize exactly where they are. So it turns out that your precision needs to be smaller than one degree, so smaller than 111 kilometers basically. Otherwise, you start mistaking one group of islands for another one.

And when I was researching this, there's basically, if you have the UK, the Southwest is basically the first thing you see when you sail to the UK from Spain. You know, Anthony, whenever you do your sailing from Spain to the UK.

Anthony Alford: As one does.

Roland Meertens: As one does.

Anthony Alford: I usually bring an Armada with me.

Roland Meertens: Yes. I take out my sextant and I try to figure out where I am, but there are basically two tips you can see. And if you mistake one tip from the other, if you think you're at one place rather than the other, you will run into cliffs.

And it turns out that sometimes some of these experiments they did... I think one inventor took one of his inventions for the longitude problem onto a ship, and then warned the captain that they were not where they thought they were based on his calculations and that saved the ship. So then they were like, "Whoa, this technology is really important." The best customer demo ever.

Anthony Alford: Here in North Carolina we have lighthouses, or there's at least one still left, and this may be one of those urban legends that we have now, but basically the lighthouses have patterns painted on them, black and white. So my guess was that was to help you try to figure out which lighthouse that was.

Roland Meertens: Yes. Actually it's funny because I didn't even consider the lighthouses when doing this research, but also do you know that lighthouses flash specific patterns at night?

Anthony Alford: Yes, I was going to say that too. I've never actually verified that by going out and seeing them.

Roland Meertens: Yes. I frequently see lighthouses, but I never really considered learning the patterns to localize myself. It is quite smart. It's like active sensing applies to the real world.

Anthony Alford: It's a transponder in a way. Transponders.... We're kind of going off on a tangent, but aircraft transponders they used to do Morse code or I guess airport transponders actually send Morse code. So if you've ever heard of the band called Rush, they have a song called YYZ. The beginning of that song has a rhythm pattern, that's actually the Morse code for YYZ, which is the airport code for Toronto.

Roland Meertens: Oh, interesting. Which from a naming perspective doesn't make sense.

Anthony Alford: Well, I think all the Canadian ones start with YY-

Roland Meertens: Yes, good point.

Anthony Alford: ... for some reason, I don't know why.

Roland Meertens: CGP Grey has a really good video on why this is. Now we start recommending...

Anthony Alford: I was going to say now we're really on a tangent.

Roland Meertens: Also, in terms of robotics and talking about lighthouses, this virtual reality headset you can buy has lighthouses, but I also know that some people use them to power their robotics laboratory because then their robots on-device chip can basically register the patterns from the lighthouses and then knows where they are.

Anthony Alford: All right, nice.

Roland Meertens: Because you get all the timing information from the actively emitted signals from the lighthouse.

Anthony Alford: Very cool.

Roland Meertens: So Yes, everything is robotics at the end of the day for us.

Anthony Alford: Certainly not.

Roland Meertens: Okay. Anyway, so now we know why maps and localization is important for ships and humans. Now we know how precise you can get using that reckoning. The other option is you can determine the angle between certain stars and the moon, and then use a lookup table to determine at what longitude you see what angle at what time.

And I first thought, "Oh, this feels very similar to the satellite approach, but it's a bit different because you don't really need to determine angles on your satellites." And the other realization I actually had this morning is that the moon is actually a clock. So it repeats with a very specific pattern, but only I think every 18 years. So the moon is a very nice clock with very nice consistent repetitions, but only if you have mapped out exactly 18 years of motion.

Anthony Alford: Interesting.

Roland Meertens: Yes, and this is exactly why the observatory at Greenwich, which I keep talking about and which I like to go to, is built and the observatory in Greenwich is known for the zero longitude line and Greenwich Mean Time. So if you're saying that you are at, I don't know, I am guessing minus six hours, Greenwich Mean Time.

Anthony Alford: Five.

Roland Meertens: Minus five hours Greenwich Mean Time, then I know exactly at what longitude you are. So the zero is at this observatory. And the other thing which I found out is that later a third approach got added to these two or to these three I already mentioned. And that is you can use the moons of Jupiter as a clock.

Anthony Alford: Really?

Roland Meertens: Yes, because they are way more consistent in their pattern. And also coming back to the fun story I told at start, there's also a comparison map of France, which uses where people determine the locations they were at using the moons of Jupiter. And that again takes a lot of area away from France. So by this point the king must be so absolutely pissed at scientists who keep telling him that his country is smaller than he thought it was.

Anthony Alford: Where did the other land go?

Roland Meertens: It was just never there.

Anthony Alford: It was never there. It was all imaginary. Wow.

Roland Meertens: Yes, I can only imagine that some people try to bank on it by coming up with a new technique which makes this land seem bigger again.

Anthony Alford: Don't you feel bad for the people who had the title to that land?

Roland Meertens: I mean, it's still the same thing. They should just map out their lands with triangles.

Anthony Alford: So if we want to go on one more tangent, I heard a story here a while back, the border between North Carolina and South Carolina, it was determined that it was wrong. Apparently the people who surveyed it back in the colonial times didn't actually do the survey. They said they did but didn't do it because it was too hard to travel. So recently they adjusted the map and that meant there were some businesses and houses that were moved to a different state.

Roland Meertens: Oh, interesting. Also, to clarify about the map of France, what was not wrong was the border with whatever country was to the east of France at that time, what was really wrong was the coastline. So the coastline got adjusted, so they didn't actually take land away, they simply never had this land to start from.

Anthony Alford: The sea levels rose and swallowed the land.

Roland Meertens: Global warming. Something I also found interesting is because I am always now talking about all these angles between the moon, the stars, all these patterns, sometimes scientists would come out with a function which would basically describe these patterns, but that could take a long time to compute. And this is why they created tables by computers, where computers are of course humans doing all their calculations in their heads.

It's also interesting because I saw that they had a story on their website about Mary Edwards, who was one of the female contributors. She was one of the female computers and she apparently was really good at this and also taught her children, including daughters on how to be an efficient computer.

And also just to come back to previous episodes, I think the third one we recorded, I think also this is where someone like Charles Babbage must have come in by creating tables like this way faster and way more precise with a mechanical computer rather than relying on a human computer. And Charles Babbage was also part of the Royal Astronomical Society, just to wrap up of our entire season of Generally AI.

Anthony Alford: Nice.

Roland Meertens: Anyways, if you have a very precise clock and you know what star is above you at what time, that basically solves the entire issue. So someone called John Harrison worked on this. He was an inventor completely focusing on clocks someone can bring on the ship because back in the days they had this swinging mechanism and that gets disturbed if the ship also moves.

So he worked a lot with things like springs or mechanical springs, all the kind of springs you can think of to create consistent moving patterns. So Yes, he basically joined the observatory in Greenwich to work on clocks. His grave is close to my house because I always like to go to someone's grave to research them. That's basically how humans can localize themselves and then we can come back to the satellites later.

Anthony Alford: Sounds good. Actually, you didn't talk about the Mercator projection map: that's the map that everybody loves to hate because it shows Greenland is bigger than Brazil, which of course is not true. What's interesting about that map is it preserves angles.

So if you set a course due east, you could draw a straight line on the Mercator map and it's at the same bearing or heading---compass direction---as it would be on the real world. When you want to plot a course on the map, you can draw straight lines from checkpoint to checkpoint and the angles of those lines are the same as your compass heading would be.

Roland Meertens: Oh, that's pretty interesting. I never realized that this is the reason that they have it like this.

Anthony Alford: So it's very well suited for marine navigation.

Roland Meertens: But can you imagine how pissed the king of Greenland is after he sees his non Mercator projected map?

Anthony Alford: Maybe that's why Donald Trump wanted us to buy Greenland. It looks huge on the map.

Roland Meertens: Also, one thing I like to do at parties is I like to ask people, "What is bigger: Greenland or Australia?"

Anthony Alford: Oh, Australia, right?

Roland Meertens: Yes. And then after they give an answer, I show them the Google Maps map and I ask them if they want to change their answer. And it's very interesting to see how people respond to this.

Anthony Alford: So the reason of course that those get expanded at the north is because the longitude lines come together very close at the North Pole, but on the map they're the same distance apart, up and down.

QCon London 2024 [21:19]

Roland Meertens: Hey, it's Roland Meertens here. I wanted to tell you about QCon London 2024. It is QCon's flagship international software development conference that takes place in the heart of London next April 8 - 10. I will be there learning about senior practitioners' experiences and exploring their points of view on emerging trends and best practices across topics like software architecture, alternative AI, platform engineering, observability and secure software supply chains.

Discover what your peers have learned, explore the techniques they're using and learn about all the pitfalls to avoid. Learn more at qconlondon.com, and we really hope to see you there. Please say hi to me when you are.

Robot Navigation [22:13]

Anthony Alford: So let's move to mobile-

Roland Meertens: Mobile robots. Yes.

Anthony Alford: Well we're going to see, as you've alluded, this all kind of ties together in a lot of ways. As a matter of fact, a lot of people these days are ride around in a mobile robot, which we sometimes call the self-driving car, which that's amazing to think about that we're living in an age where we have robots to drive us around. So we've already kind of given one history lesson, let's do another one. How does the mobile robot know where to go? It's very similar or it can be similar to how the sailors did it.

So when the sailors were doing it, you need to know your 2D coordinates, latitude and longitude on the map. You need to know your location on a map and you actually need to know which way your ship is pointing. So you know the coordinates of where you are, the coordinates of your destination, you put those on that Mercator projection map, you draw a straight line between them and you just point your ship in that direction and go.

And you just keep up with where you are as you go until you get to that point. You mentioned obstacles, you also need to know the coordinates of the obstacles. Seems like shoals or reefs. So maybe if there's an island in the way you might head to a point near that island and then head to your destination after that.

Roland Meertens: And do you go to the islands just because you get more information from seeing it?

Anthony Alford: Well, that's a good question. Probably we go to the island for a lot of reasons, including you need more food and water, but you certainly could. It's certainly a good way to check your course. Maybe you look for a lighthouse that blinks twice or something.

So we need a map and we need to know our location and we need to know our destination, we need to have the obstacles on the map. We'll gloss over the fact that the map has to come from somewhere and we hope that people get it right. If we're the king of France, we don't want our ships running into Spain or something.

Roland Meertens: It's all pre-mapped out.

Anthony Alford: Yes, assuming it's pre-mapped out. So let's get back to the robot. Assuming the robot has a map that's mapped out, we have a problem, a big problem in figuring out what is the robot's current coordinates and that's the problem we'll call localization. So you mentioned dead reckoning or sometimes we call that inertial navigation.

And just to recap that is you know your starting coordinates, you know which way you're heading and you head in that direction for a certain amount of time at a certain speed, you know the distance you've traveled. So you can just do vector math and get a new set of coordinates for where you are. Just like if say you're on the highway, you're headed east, you drive east at 55 miles an hour for one hour you've gone 55 miles east.

Roland Meertens: Approximately, approximately.

Anthony Alford: Approximately. So that's the problem. So it depends on a couple of things that you can measure accurately how fast you're going and how long you've gone there, that there's no bumps in the road that make your speed calculation skip some or things like that. So anyway, this scheme has errors. The errors tend to accumulate, so the longer you rely on it, the less certain you are of where you are, and like you said with Cuba, you might be on one end of Cuba where you thought you were on the other end of Cuba.

Roland Meertens: Yes. And I think that's pretty bad for a self-driving car.

Anthony Alford: It is. It's really bad for a self-driving car. Now, we mentioned that on the ocean you can sometimes see things like lighthouses or islands to help you figure out where you actually are. It turns out though, for a robot it's not that easy.

So let me just give you an example of this from the 1970s. In the 1970s, the Stanford AI Lab had a mobile robot called the Stanford Cart. So the idea there was they would use vision as the main sensor for navigating just like sailors use or people driving a car. Let me do what you do to me. How would you do that?

Roland Meertens: Well, first of all, is this before or after Shakey?

Anthony Alford: This is after Shakey, actually-

Roland Meertens: After Shakey. Okay. Is this a robot inside the lab or outside?

Anthony Alford: I think they did both, but let's say you're inside.

Roland Meertens: And this is the 80s?

Anthony Alford: Late 70s, early 80s. Yes.

Roland Meertens: Okay, because I read this book from Marc Raibert who has his Boston Dynamics lab nowadays and I think he used an external sensor to track what's happening or is this internal.

Anthony Alford: So what they actually had was they had a camera on the robot and the camera could move laterally. So they could take a picture, move the camera laterally and take another picture. So then you have a stereo view.

Roland Meertens: Oh, it's an active stereo camera-

Anthony Alford: Yes. So the idea was, which seems like a natural idea, we'll build a 3D model of the world. Basically we'll build a map of the world and we'll localize where the robot is on the map by using vision. So they basically had a 3D drawing program of the environment, like the room. And then they could generate images that the robot should see from that 3D model.

And then when they got images, they could compare it with that. So this is what is called image registration. Basically you have live sensor data, you have stored sensor data, you basically have a bunch of stored sensor data images that you would see from a bunch of different positions and orientations. You try to match your actual sensor data with the stored ones to figure out what position and orientation you are relative to the scene-

Roland Meertens: They stored the entire images or did they store features?

Anthony Alford: So that's the thing. So this is the 1970s. So you got to store features and as you can imagine with 1970s tech, here's how well it worked. The cart could move one meter every 10 or 15 minutes. So it would take some pictures, do some calculations, figure out a path to go and go for one meter and stop.

Roland Meertens: That's not the fastest self-driving car.

Anthony Alford: It's not the fastest. You could probably walk faster than that.

Roland Meertens: It is still impressive though.

Sweeping the Nation [29:11]

Anthony Alford: But the point was using vision to try to localize where the robot was and so it could plan where its next destination was. This was the late 70s, early 80s. A little later after that some robotics researchers started to question: why do we need to do this? They were thinking about, animals seem to walk around the world pretty well. A lot of them have homes that they go back and forth to.

Even insects can do this, they can navigate fairly well and they almost certainly have no idea of latitude and longitude or X-Y coordinates. Insects don't have a whole lot of neural circuitry, but they seem to find their way around just fine. They must be doing something else.

And you asked me how do I know where I'm at? Great question. Even when we're out driving our car or just walking around, we don't really think about our latitude and longitude. We just know how to do it. We're certainly not solving any kind of kinematics equations in our head. We do have a world model and a map of some sort almost certainly, but we don't have precise coordinates.

Roland Meertens: Sometimes when I'm driving on the highway, I think about how difficult it will be to solve kinematics equations in my head.

Anthony Alford: Exactly. But when you are driving your car, you do kind of have an idea of where you are, but it's usually relative to where you are along your route. What is the name of the road or street you're on and about how far until the next intersection or something where you need to make a turn. But again, it's not X-Y coordinates. It's not latitude and longitude.

And in fact, if you think about driving on a long trip, let's say you were on the Autobahn or here in the US, the interstate, you get on that interstate and you just drive. You don't think about where you are. You just basically follow some rules. You set the cruise control, you stay in your lane, you don't bump into anybody.

Roland Meertens: Indeed, you only care once you have to get your exit and you hope that you're not missing your exit.

Anthony Alford: Right. And basically there's this idea of two modes of thinking: slow and fast. Here you're doing the fast mode of thinking where you're reacting, you're basically, I'm staying in my lane, I'm staying behind this car. So what the researchers started calling this was behaviors and they started doing so-called behavior-based robotics.

The robot doesn't really have a world model, it just has some rules that it follows like, don't bump into things. And you can implement that very easily with sonar. And in a real simple fashion, if you have several sonars in front of the robot, you can make it turn until it finds the furthest distance away. So basically that's the direction it can go where there's the most open space. That's obstacle avoidance.

All you have to do is have a way to tell it to do two things at once: drive forward, but also turn until you see more open space and then it can navigate essentially a maze. Or if you have a way to measure…I was the TA for a class where the college kids did this. You basically put a strip of black tape along the floor, you give it two sensors for sensing black left and right and it just kind of zigzags along that line of tape. So think about that, that's lane keeping.

And in fact, most cars have... Even cars that are not self-driving have this now. It can keep the car between two white lines and the cars have adaptive cruise control where you can maintain a speed but stay a distance away from things in front of you. It's pretty much self-driving as long as you don't have to make a turn. So this actually this behavior-based robotics, I like to say it swept the nation because you know who was one of the inventors of this?

Roland Meertens: Let me think about who it could be. Yes, just tell me.

Anthony Alford: Rodney Brooks, who was the founder of iRobot, which makes the Roomba, so his robotic architecture swept the nation. So that's my dad joke for the day.

Roland Meertens: 

Nice. I really like it.

SLAM [33:55]

Anthony Alford: But the idea of localization never completely died because sometimes you want the robot to go to a specific place and in a more... We've implemented bug behavior, that's fine, but not everybody wants a robot that's as dumb as a bug. Sometimes you want a robot that's a little smarter than a bug, that you can say, "Go to Joe's office and bring him this document," say.

So localization never completely died and we kind of glossed over the idea of well, somebody's got to make that map. So where does that map come from? Well, by the late 90s and early 2000s, technology was a little better and people were starting to work on this problem again. And they used an algorithm or scheme called simultaneous localization and mapping or SLAM, so that solves two problems.

One is building the map and the way that works is the robot uses its sensors to identify landmarks or things such as walls in the environment and at the same time figuring out where it is on the map. And both of those things have a little bit of error in them, but if you can iterate over and over, they can converge to a fairly accurate map and localization.

Roland Meertens: The question is also whether you need the perfectly accurate map, as long as you can navigate to the right spots on the map-

Anthony Alford: Correct.

Roland Meertens: ... afterwards.

Anthony Alford: So the way it works is…we did talk about the dead reckoning and inertial navigation. So if you have an approximate idea of where you are and the direction you're going and how fast, so in a car that would be the angle of your steering wheel and the speed, you can take your current position and update it where you're going to be. So that's prediction. So you're going to say, the next time step, I'm going to be more or less in this XY coordinate.

And then you do an update by taking your sensors and measuring the relative location of landmarks, just like you mentioned you're near an island, how far away is that island? You assume these landmarks don't move. So changes in the landmark's location relative to the robot gives the robot information on its position. So you still kind of need to do that registration step we talked about, where you take your sensor data and try to match it up with what you know about landmarks.

But all of these things are updated iteratively. So interestingly, one of the pioneers of this SLAM process was a researcher named Sebastian Thrun. In 2003, he became the director of the Stanford AI lab that we mentioned earlier. 2011, he went to Google and started work on their driverless cars.

Roland Meertens: I have his business card.

Anthony Alford: So you know all about it. So again, going back to driverless cars, basically the map is there now. Nowadays, we have really good maps, detailed maps for highways.

Roland Meertens: Also, for the cities like San Francisco, the maps are incredibly detailed. Every millimeters mapped out.

Anthony Alford: Right, with lidar. So I didn't really get into that, but you can use, instead of just vision, you can use lidar to give you a very detailed and very precise map of where everything is. GPS is pretty good. Now we know GPS still has some error of up to a few meters. So the car knows what highway it's on and kind of where it is, but you still need to figure out how to stay in your lane and when to make turns and not run over curbs.

Now we're back to a situation where really the mapping and localization is pretty close with just GPS and commercially available maps. You still need to do those things where your obstacle avoidance and turns and a little more precise navigation don't run over a curb or a pedestrian kind of thing.

Roland Meertens: Also, the GPS is very inaccurate in a city-

Anthony Alford: Exactly.

Roland Meertens: ... because of this multi-path problem. So the satellite signals bounce off of all the buildings, which creates massive issues because it adds a tiny, tiny fraction to the time they sense and then they're off.

Anthony Alford: Yes. And so then you do…probably….the lidar helps you out a lot with recognizing where you are.

Roland Meertens: Yes, lidar is insanely cool.

Anthony Alford: And there're also still inertial navigation sensors, which helps somewhat as well. So all these things, again, the inertial navigation and GPS can kind of give you an approximate location that helps you reduce the search space for that sensor registration problem. You know you're in San Francisco, you know you're probably in this neighborhood. You don't have to search your map for as many possible locations as you might be if you didn't know those things.

Roland Meertens: And then also coming back to Sebastian Thrun, one of the books he is a co-author of about the probabilistic robotics, just if you can combine all your probability distributions over where you think you could be on the map based on every sensor, then you can get to a super accurate location. And I'm always wondering how much of these Bayesian probabilistic technologies they had in the time and era of the ships and voyages and how much it would've helped them.

Anthony Alford: That's interesting because Reverend Bayes, he was born in 1701, so he was around that same time of the invention of the chronometer. However, I don't know if the idea... His name is applied to it, but I don't know how much he actually did what we call Bayesian inference.

Roland Meertens: Yes, sounds like an episode we can record next season.

Anthony Alford: That's a great idea. So that was the material that I had prepared for robotics navigation. And I think maybe that's enough of me talking for, and now you can, let's tell us how the satellites do it. And I do have a related fun fact when you get to that.

Lost in Space [40:29]

Roland Meertens: Now that we know how to navigate based on stars and how robots navigate. The person when I was working on self-driving cars as Audi's autonomous intelligent driving company was someone named Ashley Clark. So she worked both on localization for self-driving cars, but she also worked on localization for satellites. So I basically went to her and said, "Hey, what's up with this Euclid satellite? Why has it lost tracking with the stars and how does localization actually work?"

So apparently the satellites have a so-called fine guidance sensor on board, which images the sky from the sites of the field of view of Euclid's visible instruments. And then they use guide stars to navigate them and they maintain precise pointing because it needs to point consistently to one location for a very long time.

And in this case, the problem with the Euclid satellite was that sun rays were basically causing artifacts and false signals which created super loopy star trails. And this is extra important because it stitches together images to get a good feeling for where it is and where it has to point. But basically for the quiz I have for you today, I kind of had the following things for you to ponder about before we hear Ashley Clark give us the actual answer. So how do you think a satellite knows its exact position in space?

Anthony Alford: Well, I don't know that there's such a thing as exact position in space. From what I understand, everything's an orbit and perhaps you would give a location relative to something like the sun or the earth and you might do... For example, here on the earth when we're talking about the position of the star, we talk about azimuth, right ascension and things like that. So basically it's like a polar coordinate and then you have a distance. But I actually don't know Roland.

Roland Meertens: Yes. Okay. So the one question we have is how does the satellite know its exact position in space where we basically say, "Oh, we don't know." You also mentioned predicting it, basing on geometry. How would that work? What do you think?

Anthony Alford: Well, so again, let's talk, if you think about how astronomers studied the planets, basically they track its position in the sky over time. From that they can figure out an orbit somehow. I don't know how they know the distance.

Roland Meertens: Indeed. So it's the same with satellites, but what influences this orbit? Because you would say once you know the orbit of something, then you're done. And how often do you want to update its estimates, if at all?

Anthony Alford: I don't know. So obviously again with planets you assume that they're orbiting around the sun, so the sun's gravity is what counts. But we do know that Jupiter, that's actually how they found some of the non-visible planets like Neptune and Pluto, because the orbits of the planets that they saw didn't quite add up, I think.

So that all the planets have an effect on the others, it's just to what degree and how much you can measure it. So I don't know if I answered your question other than trying to show off how much I know about this.

Roland Meertens: No, you absolutely answered the question. Get ready for the answers given by Ashley Clark.

Anthony Alford: I'm ready.

Ashley Clark: Spacecraft position is usually tracked and estimated on earth and then uploaded to the spacecraft. This is typically done by using large radio antennas on earth to measure the position and velocity of the spacecraft.

One of the coolest things about spacecraft navigation to me is that once you measure a spacecraft's position and velocity you know the geometry of its orbit and can therefore predict its future location for a very, very long time, just based on the simple geometry.

Of course there are small perturbations that add up due to gravity of other planets and space-borne objects, atmospheric drag if it's orbiting around the earth and solar radiation pressure.

By the way, second cool fun fact, solar radiation pressure is the force generated by getting hit by photons from the sun and the resulting momentum transfer and is absolutely necessary to account for when operating a spacecraft. So cool.

Typically, a spacecraft gets an updated estimate of its orbital parameters at a low frequency and also right before important maneuvers. And then propagates the estimate forward in time on board the spacecraft until it's ready for the next scheduled update. The update schedule depends on the mission's localization accuracy requirements and the expected magnitude of any unrattled forces.

Anthony Alford: So interestingly, it sounds a bit like dead reckoning. You have an idea of where you are and you measure essentially where you're headed and you can track that out using... They probably do use kinematics---actually dynamics.

Roland Meertens: Yes, indeed. So they use a lot of kinematics, but the sun is a factor, which I don't think anyone ever took into account when going on a sailing trip.

Anthony Alford: Basically it's pushed by light, which is crazy. That's nuts, but that's kind of cool. I mean you're probably a sci-fi reader like me where you always have these ideas of a solar sail, right? You have an interstellar spacecraft that can be pushed by light or photons.

Roland Meertens: Yes. It's insane that it actually works. So to get to the other questions I had about the Euclid satellites, are these stars and constellations mapped out beforehand or are they using something like SLAM, where they are mapping out the stars while they are already in space? What do you think?

Anthony Alford: Well, my guess is... For most of our purposes here on earth, we kind of assume the stars are fixed. We know they're not, we actually know they move relative to everything. So I don't know, I assume they kind of treat that as more or less fixed with maybe with low-frequency updates like she mentioned.

Roland Meertens: Okay. And where do you think they get these constellations from? So you think the constellations are already programmed in?

Anthony Alford: That's a good question. I don't know. So again, if you look at sci-fi, when you navigate... By the way I could go on a tangent now. The Apollo astronauts were trained to use celestial navigation, basically taking sightings on stars to figure out where they were on their trip if they needed to. And they actually were trained how to do that here in North Carolina at the University of North Carolina Planetarium.

So in the sci-fi stories, you basically, you take sightings on two or three stars so that you can get a good orientation of which way your jet is pointing. So my guess is probably it's not pre-programmed, although if you were going to pre-program it, that would make sense as long as you could update it.

Roland Meertens: And also then the question I would have is how do you know ahead of time what constellation and stars you can see?

Anthony Alford: Well, that's the trick, right? So that you don't know, although I guess if you know the orbit pretty well, you could probably predict it, which ones you should be able to see.

Roland Meertens: And I was also wondering how many stars there are actually and how fast is to compute because I don't know how many stars there are at all in the universe, but do we all give them to a spacecraft? Is this just one massive file?

Anthony Alford: Well, you're going to want to give them big ones, I'm guessing, because how do you tell one star from another? I don't know how they do that. Is it based on the spectrum, based on the brightness? Something like that.

Roland Meertens: Okay, well get ready to hear the answers from Ashley Clark.

Anthony Alford: All right.

Ashley Clark: Star trackers are devices that estimate a spacecraft's orientation based on which constellation it can detect in a camera image. There are several different commonly used star catalogs available to provide these reference constellations. And the one that is used on a given spacecraft depends on how sensitive the star tracker camera is. If the camera can see very low intensity stars, for example, then one of the larger catalogs would be used.

However, the number of visible stars can become quite big and memory and compute capacity on satellites is limited, so typically the star catalog will be limited to the portion of the sky that the mission plans on looking at. Sometimes there can be a course-resolution star tracker that uses a star catalog of only really bright stars over all the night sky in order to orient the spacecraft initially.

And then it uses a more detailed catalog once it's close to the goal orientation. Whatever catalog the mission is going to be used will be uploaded to the spacecraft before launch or updated in flight before it goes into mission operations.

Anthony Alford: That makes sense because the communication channel I think has pretty low bandwidth a lot of times.

Roland Meertens: So you probably don't want to send it everything all at once, which in this case, they just needed to tweak what it could see on this particular satellite.

Anthony Alford: Nice.

Roland Meertens: And then we get to the last questions because we already talked about the accuracy of our location on the ship, which we wanted to have within a hundred kilometers basically on our ships. And for the Euclid satellite, how accurate does the location actually need to be and is position important here?

Anthony Alford: I'm not sure what the mission of this thing is. For some things the location is pretty important. Like for say a GPS satellite, it needs to be where it needs to be so that we know where we are. For something else I don't know if they're just taking pictures of the sun, for example.

Roland Meertens: So in this case it is making images of deep space. It's mapping out very deep space.

Anthony Alford: I have to assume that its position relative to deep space…it can probably tolerate quite a bit of error, but I don't actually know, so I would love to hear what she says.

Roland Meertens: All right, get ready for Ashley Clark.

Ashley Clark: Spacecraft positioning accuracy requirements highly depend on the mission. For a spacecraft like Euclid, it's imaging objects that are very, very far away. This means that the science doesn't directly depend on a very accurate location, but rather very accurate orientation.

Its position accuracy just needs to be enough to verify that it stays in its orbit near the Earth-Sun L2 Lagrange point. This is a very special orbit where the Sun, Earth, and Euclid remain perfectly in line throughout the entire orbit, but that the earth blocks out a large amount of light and radiation from the sun so that there's less noise in the scope images.

Anthony Alford: We didn't even talk about Lagrange points, but that's a whole episode in itself.

Roland Meertens: That is indeed a whole episode in itself.

Anthony Alford: In fact, we could do a whole series on Napoleonic-era French mathematicians, probably.

Roland Meertens: I think so far we are already well on the way to combining computer science from over the human lifespan.

Anthony Alford: Very cool. That's cool. I have to admit, I haven't been keeping up with a lot of space news, but that makes a lot of sense what she said. You need to know what part of the sky you're pointing it at, but you don't really need to know exactly where you are, XYZ.

Roland Meertens: Yes, massive thanks to Ashley Clark. Besides being one of my favorite ex co-workers and having worked on localization for self-driving cars, also ex NASA engineer. So incredibly, incredibly talented. Incredibly cool.

Anthony Alford: Definitely. Well, hopefully you two can come to a QCon and we can hang out. That would pretty fun. We can talk about... That's what we need to do. We need to have a podcast at QCon and quiz people.

Roland Meertens: I am still thinking of doing a QCon live. If people are interested in having a Generally AI live show, please send us a message on LinkedIn because we might actually do this.

Anthony Alford: Especially if we let hecklers heckle. That would be funny.

Roland Meertens: I didn't know that you could have hecklers heckle about technical things.

Anthony Alford: Hey, why not?

Conclusion [53:41]

Roland Meertens: Anyways, let's run it up. What did we learn today and did you learn anything this week?

Anthony Alford: I learned a lot about satellites. That was something that was new to me and it was incredibly interesting and I think that's amazing that you got Ashley to give us that information.

Roland Meertens: All right. I am very impressed that they already got a robot using cameras before, I am going to say webcams, but the web was only a thing in the 90s. Before webcams were a thing they used cameras to localize. I didn't know they first did that and then went for reactive robotics like Rodney Brooks did, that's a whole revelation.

Anthony Alford: You'd heard of Shakey. I think Shakey did that even before then.

Roland Meertens: Yes, I'm not entirely sure what Shakey used. I thought that Shakey just had an external localization system.

Anthony Alford: Oh, maybe that's it. You may be right, Yes.

Roland Meertens: As I said, I read this book about robots that walk and balance, something like that. It's very interesting to see what they use in the 80s on robotics projects and how inventive you can get if you don't have all the resources we have nowadays.

Anthony Alford: Yes.

Roland Meertens: Anything specific you learned this week, which you want to tell the listeners?

Anthony Alford: I feel like I have all these fun facts that I tossed out during the show. I do really like the Mercator projection. I had one of those on my wall.

Roland Meertens: I never realized that the Mercator projection was like that because then the angles are consistent and that's important for navigation. That's super interesting.

Anthony Alford: Yes. I had a roommate who was a pilot and he said, "Yes, they use those in aviation as well."

Roland Meertens: Yes, it makes so much sense. I think in the past, in the super old maps, you sometimes see those roses on the-

Anthony Alford: That's exactly right.

Roland Meertens: So you can keep following the rose lines of the wind rose of all the angles.

Anthony Alford: That's right.

Roland Meertens: I also saw a paper, which is pretty cool, that generative AI can now generate the next image in a sequence of images so you can show it, I don't know, a photo of one dog, then two dogs. It generates something with three dogs. It tries to figure it out. It's pretty cool.

Anthony Alford: Speaking of generative AI and mobile robots, I wrote this up for InfoQ News, but I attended a conference not too long ago where someone from... Wow, I can't remember which self-driving car company, but they use generative AI to generate synthetic scenarios for testing their self-driving AI and collision avoidance and things like that.

Roland Meertens: Was it the company Wave?

Anthony Alford: Cruise.

Roland Meertens: Cruise. Oh, okay.

Anthony Alford: I think it was Cruise.

Roland Meertens: Oh, Cruise is a whole other topic. By the time this podcast comes out, we don't even know if the company is still there. Anyways, I think that's it for this episode of Generally AI, an InfoQ podcast, and that's also this for the first season. So I had a lot of fun making this with you, Anthony.

Anthony Alford: The most fun part is doing the podcast. You always come out with some fun and entertaining and informative stuff. I'll admit, it takes me a bit of effort to make sure that I'm coming out with facts and not hallucinating like an LLM when I give my talk, but it's definitely fun and worth it.

Roland Meertens: Yes. We are going to take a short break and then we are going to record... I'm assuming we're going to record the second season.

Anthony Alford: I'm all for it. Yes.

Roland Meertens: All right. I'm excited about this. I also hope that the listener enjoyed listening to us talking about fun facts and rambling about technology both old and very new. I hope this was useful to you. I hope this was entertaining to you. I say this every episode, but if you like this podcast, of course you can share, like, post it on X, formerly Twitter, which I still think is weird that we went from Twitter to X to X, formerly Twitter.

I think the domain name xformerlytwitter.com is still free if you're listening to this. But Yes, you can also tell your friends because that's how I learn about all my podcasts. So besides liking and giving us a rating, you can also just reach out to us on LinkedIn and I really hope you enjoyed it.

Anthony Alford: Same here.

Roland Meertens: All right, then, thank you, Anthony for the first season.

Anthony Alford: Thank you Roland for setting this up. It's been a pleasure.

Roland Meertens: And thank you listeners for listening to our shows.