Robocars driving when the map is wrong

Topic: 

Yesterday's note on Here's maps brought up the question of the wisdom of map-based driving. While I addressed this a bit earlier let me add a bit more detail.

A common first intuition is that because people are able to drive just fine on a road they have never seen before that this is how robots will do it. They are bothered that present robocar designs instead create a super-detailed map of the road by having human driven cars (or eventually robots) scan the road with sensors in advance. After all, the geometry of the road can change due to construction; what happens then?

They hope for a car that, like a human, can build its model of the road in real time while driving the road for the first time. That would be nice, of course, and gives you a car that can drive most roads right away, without needing to map them. It is possible on many roads. But it's a much harder problem to solve, and unlikely to ever be solved perfectly. Car companies are building very simple systems which can follow the lines on a freeway under human supervision without need for a map. But real city streets are a different story.

The first thing to realize is that any system which could build the correct model as you drive is a system that could build a sufficiently useful map with no human oversight, so the situations are related. But building a map in advance from prior drives is always going to have several very large advantages:

  1. You build the map from not just one scan of the road, but several, and done in different lanes and directions. As a result, you get 3-D scans of everything from different angles, and can build a much superior model of the world.
  2. Using multiple scans lets you learn about things that are stationary but move one day to the next, like parked cars.
  3. You can process the data using a cloud supercomputer in as much time, memory and data storage as you want. Your computer is effectively thousands of times more capable. Any AI you can do in the car you can do much better in your supercomputer.
  4. Humans can review the map built by the software if there's anything it is uncertain about (or even if there is nothing) at their leisure.
  5. Humans can also test the result of the automatic and guided mapping to assure accuracy with one extra drive down the road.

In turn there are disadvantages:

  1. At times, such as construction, the road will have changed from when it was mapped
  2. This process costs effort, and so the vehicle either does not drive off the map, or only handles a more limited set of simpler roads off the map, or drives in a less capable way off the map.

The advantages are so great that even if you did have a system which could handle itself without a map, it is still always going to be able to do better with a map. Even with a great independent system you would want to make an effort to map the most popular roads and the most complex roads, up to the limit of your budget. The cost is an issue, but the cost of mapping roads is nothing compared to the cost of building or maintaining them. It's a few times driving down the road, and some medium-skilled labour.

The road has changed

Let's get to the big issue -- the map is wrong, usually because construction has changed it.

First of all, we must understand that the sensors always disagree with the map, because the sensors are showing all the other cars and pedestrians etc. Any car has to be able to perceive these and drive so as not to hit them. If a traffic cone, "road closed" sign or flagman appears in the road, a car is not going to just plow into them because they are not on the map! The car already knows where not to go, the question is where it should go when the lanes have changed.

Even vehicles not rated to drive any road without a map can probably still do basic navigation and stay within their lane markers without a map. For the 10,000 miles of driving you do in a year, you need a car that does that 99.99999% of the time (for which you want a map) but it may be acceptable to have a car that's only 99.9% able to do that for the occasional mile of restriped road. Indeed, when there are other, human-driven cars on the road, a very good strategy is just to follow them -- follow one in front, and watch cars to the side. If the car has a clear path following new lane markers or other cars, it can do so.

Google, for example, has shown videos of their vehicle detecting traffic cones and changing lanes to obey the cones. That's today -- it is only going to get better at this.

But not all the time. There will be times when the lanes are unclear (sometimes the old lanes are still visible or the new ones are not well marked.) If there are no other cars to follow, there are also no other cars to hit, and no other traffic to block.

Still, there will be times when the car is not sure of where to go, and will need help. Of course, if there is a passenger in the car, as there would be most of the time, that passenger can help. They don't need to be a licenced driver, they just need to be somebody who can point on the screen and tell the car which of the possible paths it is considering is the right one. Or guide it with something like a joystick -- not physically driving but just guiding the car as to where to go, where to turn.

If the car is empty, and has a network connection, it can send a picture, 3-D scan and low-res video to a remote help station, where a person can draw a path for the car to go for its next 100 meters, and keep doing that. Not steering the car but helping it solve the problem of "where is my lane?" The car will be cautious and stop or pull over for any situation where it is not sure of where to go, and the human just helps it get over that, and confirms where it is safe to go.

If the car is unmanned and has no network connection of any kind, and can't figure out the road, then it will pull over, or worst case, stop and wait for a human to come and help. Is that acceptable? Turns out it probably is, due to one big factor:

This only applies to the first car to encounter an unplanned, unreported construction zone

We all drive construction zones every day. But it's much more rare that we are the first car to drive the construction zone as they are setting it up. And most of the rules I describe above are only for the first connected car to encounter a surprise change to the road. In other words, it's not going to happen very often. Once a car encounters a surprise change to the road, it will report the problem with the map. Immediately all other cars will know about the zone.

If that first car is able to navigate the new zone, it will be scanning it with sensors, and uploading that data, where a crew can quickly build a corrected map. Within a few minutes, the map and the road will no longer differ. And that first car will be able to navigate the new zone 99.999% of the time -- either because it has a human on board, remote human help or it's a simple enough change that the car is able to drive it with an incorrect map.

In addition, the construction zone has to be a surprise. That means that, in spite of regulations, the construction crews did not log plans for it in the appropriate databases. Today that happens fairly often, but over time it's going to happen less. In fact, there are plans to have transponders on construction equipment and even traffic cones that make it impossible to create a new construction zone without it showing up in the databases. Setting up a road change has a lot of strongly enforced safety rules, and I predict we'll see "Get out your smartphone and make sure the zone is in the database before you create it" as one of them, especially since that's so easy to do.

(You have probably also seen that tools like Waze, driven by ordinary human driver smartphones, are already mapping all the construction zones when they pop up.)

If a complex zone is present and unmapped, unmanned cars just won't route through there until the map is updated. The more important the zone, the more quickly it will get updated. If need be, a mapping worker will go out in a car before work even begins. If a plan was filed, we'll also know the plan for the zone, and whether cars can handle it with an old map or not.

Most of the time, though, a human passenger will be there to guide the car through the zone. Not to steer -- there may not be a steering wheel -- but to guide. The car will go slowly and stay safe.

Once a car is through, it will send the scans up to the mapping center, and all future cars will have a map to guide them until the crew changes the road again without logging it. I believe that doing so should be made against safety regulations, and be quite rare.

So look at those numbers. I will hope it's reasonable to expect that 99% of construction zones will be logged in road authority databases before they begin. Of the 1% that aren't, there will be a first robocar to encounter the zone. 90% of the time that car will have a passenger able to help. For the 10% unmanned cars, I predict a data network will be available 99% of the time. (Some would argue 100% of the time because unmanned cars will just not go where there is not a data connection, and we may also get new data services like Google's Loon, or Facebook's drone program to assure coverage everywhere.)

So now we are looking at one construction zone in 100,000 where there was no warning, there is no human, and there is no data. But we've rated are car as able to handle handle off-map driving 99.9% of the time. For the other .1%, it decides it can't see a clear path, and pulls over. When it doesn't report back in on the other side of the data dead zone, a service vehicle is dispatched and fixes the problem.

So now in one in 100,000,000 construction zones, we have a car deciding to pull over. Perhaps for half of those, it can't figure out how to pull over, and it stops in the lane. Not great -- but this is one in 200 million construction zones. In other words, it happens with much less frequency than accidents or stalled cars. And there is even a solution. If a construction worker flashes an ID card at the car's camera when it's in a confused state, the car can then follow that worker to a place to stop. In fact, since the confused state is so rare, there is probably not even a need for an ID card. Just walk up, make a "follow me" gesture and walk the car where it needs to go.

Tweak these numbers as you like. Perhaps you think there will be far more construction zones not logged in databases. Perhaps you think the car's ability to drive a changed zone will only be 50%. Perhaps you think there will still be lots of unmanned cars running in wireless dead zones in 2020. Even so the number of cars that stop and give up will still be far fewer than the number of cars that block roads today due to accidents and mechanical problems. In other words, no big whoop.

It's important to realize that unmanned cars are not in a hurry. They can avoid zones they are not comfortable with. If they can't get through at all, the taxi company sending the car can just send another from a different direction in almost all cases.

It's also important to realize that cars in an uncertain situation are also not in a big hurry. They will slow until they can be sure they are safe and able to handle the road. Slow, it turns out, is easy. Slow and heavy traffic (ie. a traffic jam) is actually also very easy -- you don't even need to see the lines on the road to handle that one; you usually can't.

Once again this is only for the first car to encounter the surprise zone. Much more common will be a car that is the first to encounter a planned zone. This car will always have a competent passenger, because the service will not direct an unmanned car into an unknown construction zone where there is no data. This passenger will get plenty of warning, and their car may well pull over so there is no transition from full-auto to semi-auto while the car is moving. Then this person will guide the car through the zone at reduced speed. Probably just with a joystick, though possibly there will handlebars that can pop out or plug in if true semi-manual driving is needed.

New road signs

Road signs are a different problem. Already there are very decent systems for recognizing road signs captured by the camera -- systems that actually do better at it than human beings. But sometimes there are road signs with text, and the system may recognize them, but not understand them. Here again we may call upon human beings, either in the vehicle, or available via a data connection. Once again, this is only for the first unmanned car to encounter the new road sign.

I will propose something stronger, though. I believe there should be a government mandated database of all road signs. Further, I believe the law should say that no road sign has legal effect until it is entered in the database. Ie. if you put up a sign with a new speed limit, it is not a violation of the limit to ignore the sign until the sign is in the database. At least not for robots. Once again, all this needs is that the crews putting in the signs have smartphones so they can plonk the sign on the map and enter what it is.

We may never need this, though, because the ability of computers to read signs is getting very good. It may be faster to just make it even better than to wait for a law that mandates the database. With a 3-D map, you will never miss a brand new sign, but you might get confused by a changed sign -- you will know it changed but may need to ask for help to understand it if it is non-standard. There are already laws that standardize road signs, but only to a limited extent. Even so, the number of sign styles in any given country is still a very manageable number.

Random road events

Sometimes driving geometry changes not due to construction, but due to accidents and the environment. Trees get knocked down. Roads flood. Power lines may fall. The trees will be readily seen, and for the first car to come to a fallen tree, the procedure will be similar, though in a low traffic area the vehicles will be programmed to go around them, as they are for stalled cars and slow moving vehicles. Flooding and power lines are more challenging because they are harder to see. Flooding, of course, does not happen by surprise. That there is flooding in a region will be well known so cars will be on the lookout for it. Human guides will again be key.

A plane is not a bird

Aircraft do not fly by flapping their wings, and robocars will not see the world as people do nor drive as they do. When they have accurate maps, it gives us much more confidence in their safety, particularly the ability to pick the right path reliably at speed. But they have a number of tools open to them for driving a road that doesn't match the map precisely without needing to have the ability to drive unmapped roads 99.999999% of the time. That's a human level ability and they don't need it.

Comments

I'm re-reading Tom Vanderbilt's book "Traffic" and just finished the chapter on how "unsafe" roads might actually be safer. "Unsafe" in the sense that there is more ambiguity (e.g. no curbs, no marked crosswalks, fewer or no signs) in order to compel drivers to be more cautious and "social." I'm wondering what you think of this idea for human drivers, and does this run contrary to robocars' need for clearly defined maps? Can robocars be social? I imagine there will be a significant period of time where robocars and human drivers will share the roads. How would a robocar do something like signal it's intent to give way to a human driver? Or to a bicyclist or pedestrian?

I have thought about that. Generally, experiments like this do mean going more slowly. Knowing just what the rules are helps you go faster. It turns out that the overall traffic throughput can even be slightly better, even going more slowly, but that's not true for robocars -- they will get the best throughput in an understood world at decent speed.

It's actually a simple trick to follow other cars, which is one form of social driving. The bigger challenge is knowing where to go when there are no lines on the road. If this were a common thing, I think people could code up suitable approaches, just as humans can. They would still need to know some rules, what you do in conflict situations, and how to stay in the right as far as the law is concerned.

At a 4 way stop, Google found the cars had to assert. They could not be timid and let somebody else go when it was their turn because you never get to go.

All good points Brad, you make a convincing argument there are no problems that cannot be solved.
A couple of points, the first human occupant that has to choose the correct route for a vehicle may be a child or blind person. Again solvable by calling in for remote help if in a service area however perhaps a very basic rider licensing system may be needed so people know their level of authority. Also the actual time of setting up and activating a lane closure needs to be thought out. A transponder or signal that slowed approaching traffic would be easy, it just may need a bit of co-ordination when to interrupt the traffic and start any diversions. Often workmen set up much of the work on the side before actually closing a lane.

Actually, kids above a certain age are more than capable of guiding a car along the correct route. They are not necessarily steering, just guiding. More like playing a video game in a car that can't hit anything. So I would rate that 10 and above could do this easily, perhaps even younger.

But not the blind, or those with dementia, or those who are very young. Those cars would be treated like unmanned cars in that situation. Which means they would not be sent as the first through a construction zone, they would take an alternate route if possible.

Zones will indeed change during setup. But it will also be clear that the zone is in the middle of setup. Remember, the car has a map that was created a month ago or an hour ago, but either way it quickly sees if the map differs from reality, and acts accordingly. When the lanes have changed it's actually very obvious to the software.

Thanks for the articles you're posting on this subject. One exceptional condition I thought of while reading this one, is the situation where police are directing traffic at an intersection, due to an accident or perhaps due to temporary high traffic volume like a concert or school getting out. I can envision how the police on the scene could disable whatever traffic control is there (4-way flashing red or similar) and also put this fact into the database -- the car won't easily be able to follow the police officer's whistle and hand gestures, but perhaps the officer could use some kind of wand that could relay the same signal electronically. And perhaps if the car is recognizable as autonomous, the police wouldn't be upset if it "tailgates" behind the previous car when it was commanded to stop.

But this scenario is complicated by the fact that keeping traffic moving is a priority goal, and the car (if unmanned or e.g. carrying a blind passenger) isn't going to have much time to coordinate with a remote helper, before the police and travellers around it become impatient. Stopping the car due to a network outage or failsafe could create a real problem in this case... there may not be an available shoulder space to pull into. etc.

Of course the vehicle will see the officer standing in the middle of the road and not proceed. The question is how does it figure out where it's supposed to go.

Again, this is the first vehicle to come upon this. Once one vehicle has done it, the word will get out quickly to all others to keep unmanned vehicles away from this intersection -- within a few seconds if they are on a data network.

As before, if the first vehicle has a competent passenger -- problem solved.

If a remote operator can see some video over the data network -- problem also solved.

Don't have any of this? Well, it may not be as hard as you think to write software to understand the police gestures. The car is seeing the cop in 3D, remember, not just 2D. And police could get some training on gestures the car is sure to understand.

You could also give the cops an app on their smartphone which sends signals -- by bluetooth, wifi or flashing the LED in the phone in pulses -- that the car is sure to understand. I don't see much reason for the police to resist that, it makes their job easier. Of course the app could also tell the network that they are doing traffic controls at their GPS location, but we're presuming there is no network at this location, or rather none capable of sending low-res video.

A few other tricks are possible -- the cops having a special coloured card in their pocket the car recognizes etc. But if none work, the car would give up and pull over. Not perfect, but rare enough to be lower frequency than other problems of that sort that we tolerate. It is important to understand that humans are not perfect in these situations either, and perfection is not the goal -- superior performance to humans is the goal.

If the ideal situation means all roads, signs, constructions zones etc. are mapped, logged and put into a database, why would we need signs at all? The cars will know all the rules and regulations for that area, no extra visual clutter needed.

The signs would be for the people, who will still be on the roads, both driving and as pedestrians and cyclists.

There's a network effect with these maps that will lead to a monopoly. There will be more cars following Google's map database and therefore more maps submitted to Google's database and so it repeats.

There are economies of scale here, but it varies. Some companies will dominate in some areas, and in fact if they're smart, they will share mapping data.

An interesting question is whether companies would compete on safety-critical things like a map update because the road has been restriped. While all must build a car that is "safe enough" in that situation, you can always do better, and an updated map helps you do better.

There are reasons to share -- everybody wins if everybody is safer -- but also reasons to compete. But you can have both, in that the company that re-maps an area (to the quality standard necessary) can charge money for that data, just a bit less money than it would cost to re-map directly.

Add new comment