Almost all robocars use maps to drive. Not the basic maps you find in your phone navigation app, but more detailed maps that help them understand where they are on the road, and where they should go. These maps will include full details of all lane geometries, positions and meaning of all road signs and traffic signals, and also details like the texture of the road or the 3-D shape of objects around it. They may also include potholes, parking spaces and more.

The maps perform two functions. By holding a representation of the road texture or surrounding 3D objects, they let the car figure out exactly where it is on the map without much use of GPS. A car scans the world around it, and looks in the maps to find a location that matches that scan. GPS and other tools help it not have to search the whole world, making this quick and easy.

Google, for example, uses a 2D map of the texture of the road as seen by LIDAR. (The use of LIDAR means the image is the same night and day.) In this map you see the location of things like curbs and lane markers but also all the defects in those lane markers and the road surface itself. Every crack and repair is visible. Just as you, a human being, will know where you are by recognizing things around you, a robocar does the same thing.

Some providers measure things about the 3D world around them. By noting where poles, signs, trees, curbs, buildings and more are, you can also figure out where you are. Road texture is very accurate but fails if the road is covered with fresh snow. (3D objects also change shape in heavy snow.)

Once you find out where you are (the problem called "localization") you want a map to tell you where the lanes are so you can drive them. That's a more traditional computer map, though much more detailed than the typical navigation app map.

Some teams hope to get a car to drive without a map. That is possible for simpler tasks like following a road edge or a lane. There you just look for a generic idea of what lane markings or road edges should look like, find them and figure out what the lanes look like and how to stay in the one you want to drive in. This is a way to get a car up and running fast. It is what humans do, most of the time.

Driving without a map means making a map

Most teams try to do more than driving without a map because software good enough to do that is also software good enough to make a map. To drive without a map you must understand the geometry of the road and where you are on it. You must understand even more, like what to do at intersections or off-ramps.

Creating maps is effectively the act of saying, "I will remember what previous cars to drive on this road learned about it, and make use of that the next time a car drives it."

Put this way it seems crazy not to build and use maps, even with the challenges listed below. Perhaps some day the technology will be so good that it can't be helped by remembering, but that is not this day.

The big advantages of the map

There are many strong advantages of having the map:

• Human beings can review the maps built by software, and correct errors. You don't need software that understands everything. You can drive a tricky road that software can't figure out. (You want to keep this to a minimum to control costs and delays, but you don't want to give it up entirely.)
• Even if software does all the map building, you can do it using arbitrary amounts of data and computer power in cloud servers. To drive without a map you can must process the data in real time with low computing resources.
• You can take advantage of multiple scans of the road from different lanes and vantage points. You can spot things that moved.
• You can make use of data from other sources such as the cities and road authorities themselves.
• You can cooperate with other players -- even competitors -- to make everybody's understanding of the road better.

One intermediate goal might be to have cars that can drive with only a navigation map, but use more detailed maps in "problem" areas. This is pretty similar, except in database size, with automatic map generation with human input only on the problem areas. If your non-map driving is trustworthy, such that it knows not to try problem areas, you could follow the lower cost approach of "don't map it until somebody's car pulled over because it could not handle an area."

Levels of maps

There are two or three components of the maps people are building, in order to perform the functions above. At the most basic level is something not too far above the navigation maps found in phones. That's a vector map, except with lane level detail. Such maps know how many lanes there are, and usually what lanes connect to what lanes. For example, they will indicate that to turn right, you can use either of the right two lanes at some intersections. Usually on top of that will be physical dimensions for these lanes, with their shape and width. The position information may be absolute (ie. GPS coordinates) but in most cases cars are more interested in the position of things relative to one another. It doesn't matter that you drive exactly the path on the Earth that the lane is in, what matters is that you're in the right lane relative to the edge of the road. That's particularly true when you have to deal with re-striping.

Maps will have databases of interesting objects. The most interesting will be traffic signals. It is much easier to decode them if you know exactly where they are in advance. Cars also want to know the geometry of sidewalks and crosswalks to spot where pedestrians will be and what it means if they are there.

Somewhat independent of this are the databases of texture, objects or edges which the car uses to figure out exactly where it is on the map. A car's main job is "stay in your lane" which means knowing the trajectory of the lane and where you are relative to the lane.

Even those who hope to "drive without a map" still want the basic navigation map, because driving involves not just staying in lanes, but deciding what to do at intersections. You still need to pick a route, just as humans use maps in tools like Waze. The human using Waze still often has the job of figuring out where the lanes are and which one to be in for turns, and how to make the turn, but a map still governs where you will be making turns.

The cost of maps

The main reason people seek to drive without a map is the cost of making maps. Because there is a cost, it means your map only covers the roads you paid to map. If you can only drive at full safety where you have a map, you have limited your driving area. You might say, "Sorry, I can't go down that road, I don't have a map."

This is particularly true if mapping requires human labour. Companies like Google started by sending human driven cars out to drive roads multiple times to gather data for the map. Software builds the first version of the map, and humans review it. This has to be repeated if the roads change.

Maps also are fairly large, so a lot of data must be moved, but storage is cheap, and almost all of it can be moved when cars are parked next to wifi.

To bring down this cost, many companies hope to have ordinary "civilian" drivers go out and gather the sensor data, and to reduce the amount of human labour needed to verify and test the maps.

When the road changes

The second big challenge with maps is the fact that roads get modified. The map no longer matches the road. Fortunately, if the map is detailed enough, that's quite obvious to the car's software. The bigger challenge is what to do.

This means that even cars that drive on maps must have some ability to drive when the map is wrong, and even absent. The question is, how much ability?

A surprise change in the road should actually be rare. They happen every day of course as construction crews go out on jobs, but it's only a surprise to the first car to encounter the change. That very first car will immediately log in the databases that there is a change. If it still drives the road, it will also upload sensor data about the new state of the road. We all see construction zones every day, but how often are the first car even to see that zone?

Most construction zones are scheduled and should not be a surprise even to the first car. Construction crews are far from perfect, so there will still be surprises. In the future, as crews all carry smartphones and have strict instructions to log construction activity with that phone before starting, surprises should become even more rare. In addition, in the interests of safety, the presence of such zones is likely to be shared, even among competitors.

Once a problem zone is spotted, all other cars will know about it. Unmanned cars will probably take a very simple strategy and avoid that section of road if they can, until the map is updated. Why take any risk you don't need to? Cars with a capable human driver in them may decide they can continue through such zones with the guidance of the passenger. (This does not necessarily mean the passenger taking the controls, but instead just helping the car if it gets confused about things like two sets of lane markings, or unusual cones, or a construction flag crew.)

Nissan has also built a system where the car can ask a remote operations center for such advice, if there is data service at the construction zone. Unmanned cars will probably avoid routes where there could be surprise construction in a place with no data service.

As noted above, several teams are trying to make cars that drive without maps, even in construction zones. Even the cars with maps can still make use of such ability. Even if the car is not quite as safe as it is with a correct map, this will be so rare that the overall safety level can still be acceptable. (Real driving today consists of driving a mix of safer and more dangerous roads after all.) The worst case, which should be very rare, would be a car pulling over, deciding it can't figure out the road and can't get help from anybody. A crew in another car would come out to fetch it quickly.

The many players in mapping

This long introduction is there to help understand all the different types of efforts that are going on in mapping and localization. There is lots of variation.

Google/Waymo

The biggest and first player, Google's car team was founded by people who had worked on Google Streetview. For them the idea of getting cars to scan every road in a region was not daunting -- they had done it several times before. Their approach uses detailed texture maps of all roads and surrounding areas. Google is really the world's #1 map company, so this was a perfect match for them.

Waymo's maps are not based on Google Maps information, they are much more detailed. Unlike Google Maps, which they give out free to everybody to build on top of, the Waymo maps are proprietary, at least for now.

Navteq/Here

The company with the silly name of "Here" was originally a mapping company named Navteq. It was purchased by Nokia, renamed to "Here" and then sold to a consortium of German automakers. They will thus share their mapping efforts, and also sell the data to other automakers. In addition, the company gets to gather data from a giant fleet of cars from its owners and customers.

Here's product is called "HD Maps" and it has some similarity to Google's efforts in scope, but they took a lower cost approach to building them. They build a 3D map of the world using LIDAR. You can find an article about their approach at Here

TomTom

The Dutch navigation company was already feeling the hurt from the move to phone-based navigation, and with my encouragement, entered the space of self-driving car maps. They have decided to take a "smaller data" approach. Their maps measure the width, not just of the road, but of the space around the road. The width is the distance from what you see looking left and looking right. Sensors will measure the presence of trees, poles, buildings and more to build a profile of the width. That's enough to figure out where you are on the map, and also where you are on the road.

Later they approved on the RoadDNA product with an HD Maps project which has a more complete 3D map of the road and things around it. This is wise -- it is rarely a good bet to assume that bandwidth or storage will be expensive, and the winner is the one who creates the smallest map.

MobilEye

MobilEye (now a unit of Intel) has cameras in a lot of cars. They provide the ADAS functions (like adaptive cruise control, and emergency braking) for a lot of OEMs, and they are trying to take a lead in self-driving cars. That's what pushed their value up to $16B when Intel bought them.

MobilEye wants to leverage all those cars by having them scan the world as they drive, and looks for differences from ME's compact maps. The maps are very small -- just 3D locations of man-made objects around the highway. The location of these objects can be determined by a camera using motion parallax -- how things like signs and poles move against the background.

ME believes they can get this data compact enough so that every car with their gear can be uploading updates to maps over the cell network. That way any changes to the road will be reflected in their database quickly, and before they get dramatic, and before a self-driving car gets there.

This is a good plan and the company that does this with the most cars sending data will have an advantage. Like TomTom this makes the bad bet that taking low bandwidth will be an important edge. A more interesting question is how strong the value is in live updates. A fleet that is 10x bigger will discover a change to the road sooner, but is there a big advantage to discovering it in 1 minute vs. 10 minutes?

Tesla

Tesla is one of the few companies hoping to drive without a map, or with a very limited map. A very limited map is more like a phone navigation map -- it is not used to localize or plan, but does provide information on specific locations, such as details about off-ramps, or locations of potholes.

Tesla also has an interesting edge because they have many cars out there in production with their autopilot system. That gives them huge volumes of new data every day, though it is the limited data of their cameras. By having customers gather data about the roads, that's given them a jump up.

Civil Maps

Civil Maps is a VC funded mapping startup. Their plan is to use neural network AI techniques to do a better job at turning image and sensor data into maps. That's a good, but fairly obvious idea. The real challenge will be just how well they can do it. When it comes to the question of turning the map into a map of lane paths that guide where the vehicle drives, errors can't be tolerated. If the AI software can't figure out where the lane is, the software in the car isn't going to do it either. If successful, the key will be to reduce the amount of human QA done on the maps, not to eliminate it.

Civil Maps publishes technical articles on their web site about their approaches -- kudos to them.

DeepMap

DeepMap is another VC funded startup trying to generate a whole map ecosystem. They have not said a lot about their approach, other than they want to use data from production cars rather than having survey fleets do the mapping and re-mapping. That's hardly a big leap -- everybody will use that data if they can get it, and the battle there will partly depend on who has access to the data streams from cars that are out driving with good sensors. We'll see in the future what other special sauce they want to provide.

Others

Almost every team has some mapping effort. Most teams do not roam a large enough set of roads to have encountered the cost and scaling problems of mapping yet. Only those attempting production cars (like Tesla and Audi) that allow driving without constant supervision had truly needed to deal with a very wide road network. In fact, those planning taxi fleets will not have to cover a wide road network for a number of years.

Most players expect to buy from a provider if they can. While all teams seek competitive edges, this is one sector where the edge is less and the value of cooperation is high. Indeed, the big question in mapping as an industry, is will it become cooperative -- as in the case of 3 German automakers co-owning "Here Inc." or will it become a competitive advantage, with one player making a better product because they have better or cheaper maps?

Infrastructure providers

It seems like a natural for the folks who build and maintain infrastructure to map it. A few things stand in the way of that. Because teams will be trusting the safety of their vehicles to their maps, they need to be very sure about the QA. That means either doing it themselves, or working with a provider whose QA process they can certify.

Working with the thousands of agencies who maintain and build roads is another story. Making all their data consistent and safety critical is a big challenge. Providers will certainly make use of data that infrastructure providers offer, but they will need to do expensive work on it in some cases.

Infrastructure providers can and should work to make sure that "surprises" are very rare. They will never be totally eliminated, but things can be improved. One simple step would be the creation of standardized databases for data on roads and road work. Authorities can pass laws saying that changes to the road can't be done until they are logged in a smartphone app. This is not a big burden -- everybody has smartphones, and those phones know where they are. In fact, smartphones used by contractors can even get smarts to notice that the contractor might be doing work without logging it. Old cheap phones could be stuck in every piece of road maintenance equipment. Those phones would say, "Hmm, I seem to suddenly be parked on a road but there is no construction logged for this area" and alert the workers or a control center.

All new road signs could be also logged by a smartphone app. A law could be made to say, "A road sign is not actually legally in effect until it is logged." In addition, contractors can face financial penalties for changing roads without logging them. "Fire up the app when you start and end work or you don't get paid" -- that will make it standard pretty quickly.