Cartographic Trade-offs for Self-Driving Cars: Map or No Map


By Dr. Lance B. Eliot is the AI Trends Insider

I was driving in an area of Beverly Hills that has some of the priciest retail establishments in the world, and then went up to a mansion in nearby Beverly Glen for a special VIP party. The Beverly Glen area is one that I have rarely driven into. No problem, I figured, since I could use the GPS on my smartphone to guide me around. I entered the destination address into my smartphone and away I went. As I entered into the tony Beverly Glen neighborhoods, there were massive homes with equally massive iron gates surrounding their properties. It was also very lush, including quite a number of trees to help further hide and protect the homes from the prying eyes of others.

The hills there tend to rise and fall, and upon slowly making my way around the curved hilly sides I began to realize that I no longer was getting a signal on my smartphone. Apparently, this was presumably another desired protection by the well-to-do homeowners. Keep away strangers by not having any cell connection in the area. I found out later on that the homeowners all pretty much rely upon their cable and satellite providers for cell coverage in their homes and across their properties. The party I attended had about 15 wireless access points distributed all around the property.

Anyway, I found myself trying to find the party but my GPS wasn’t able to get updated. I was lost! In the olden days, I would have grabbed up my trusty Thomas Guide. Those of you that don’t know, it was the golden map provider for anywhere you might wanted to go. You’d keep various Thomas Guide maps in your car, such as maps of Los Angeles, Orange County, San Diego, Santa Barbara, San Francisco, all places in California you might be heading to. If you were driving out of town, you’d get yourself Thomas Guide maps for wherever you might be going. The backseat of my car had tons of those maps. Of course, now, we just rely upon our electronic GPS.

Question for you. Without my GPS, would I be unable to drive my car? I hope you would say that no, I wasn’t somehow prevented from driving my car. Obviously, you say, I was certainly able to drive my car. I was just though driving without necessarily knowing how to get to where I wanted to go. I could still drive. The car was still able to move along on the roads. I could look at street signs and see the names of streets. It might take a bit longer to find my way, but yes, I could drive and I could proceed.

Does this elicit a ho-hum from you? It might. You would likely think that I was stating the obvious. As a human driver, and having a working car, I could still drive around, even though I had no map. The lack of a map did not stop me from wandering around. The reason that this is an important point is because I am about to discuss self-driving cars. Ready?

Today, some are saying that any self-driving car that doesn’t have maps is unable to drive. In other words, no maps, no driving. This is because some of the self-driving car makers are tying the use of a map into whatever the self-driving car tries to do while driving. If you want the self-driving car to take you on a trip to Disneyland, it needs maps to know which streets to take. It needs to route via the maps and determine when to make a left turn, when to make a right turn, and so on. Without a map, the self-driving car is useless.

At the Cybernetic Self-Driving Car Institute, we don’t believe that a lack of having a map is a nonstarter for a self-driving car. We make the assumption that there might be times that the self-driving car does not have a map available. In which case, the self-driving should still be able to drive.

Yikes, you say, a blind self-driving car that is going on the roads and doesn’t know where it is going, this sounds like a recipe for disaster. Keep in mind that the self-driving car should still be able to drive on the roads and be able to do things like stopping at lighted intersections and making left turns and right turns. These should be based on whatever the self-driving car encounters when it encounters it.

Similar to my story above about driving around Beverly Glen, I was able to drive up and down the streets even without having a map. It would have been much easier to get to my destination if I had a map, but I wasn’t stuck and unable to move. Having a fundamental understanding of how to drive a car, and following the flow of the streets, making legal turns, and otherwise just driving on the roads, I could get around. In this case, I also had the street signs on the corners of the streets, which I then was able to read and determine what street I was on.

Believe it or not, I even made a quickly hand drawn diagram of my own, a map if you were. I became suddenly a cartographer.  As an amateur cartographer, I penciled out the neighborhood by making lines for the roads and created a small grid on a piece of paper. I labeled the streets based on the street signs. I noted some landmarks along the way, such as a house with a large letter P emblazoned on its roof (the ponderosa?), and I also saw a nifty koi pond at the front of one house (made a mental note to go back there one day and see the koi fish).

If I had been really doing a good job and used my skills as a former Scout Master for my son’s Boy Scout Troop, I would have added topographical markings to my budding map. I could have guessed at the elevations. I could have marked whether the road was tending up or tending downward. Other aspects of the terrain could have been noted. But, in this case, I just wanted to get to the party. That was more important than making a cool map.

In the news lately about self-driving cars, there are some complaining that China is not letting foreign companies go into China and make electronic maps of the roadways there. Some self-driving car makers outside of China are saying that without being able to make maps, their self-driving cars won’t be usable in China. This seems a bit overblown. The self-driving cars will be usable, but admittedly not as effective. No doubt about that.

Also, I can guess that Chinese companies that are allowed to create maps will then be able to charge exorbitant prices to the self-driving car makers that want to have their cars driving in China. Sure, that’s a problem. This also seems to be forcing non-Chinese map making firms to have to buddy up to Chinese mapping firms. It’s a socio-political issue, and it does then impact self-driving cars in terms of the added costs.

Some self-driving car makers insist that without maps, the self-driving car won’t be able to provide as smooth a ride. Their claim is that by examining a map beforehand, the AI can ascertain which roads are bad and which are good. If a road is bad, meaning all torn up and poorly maintained, the self-driving car will bounce around during that part of the trip. The occupants of the self-driving car will get a jostled ride. If the a road is good, meaning in quality shape and smooth, it will help the self-driving car to provide a non-jarring ride. That all makes sense and I appreciate that the self-driving car makers want to use whatever they can to ensure that the self-driving car operates well and that the occupants are treated to as smooth a ride as possible.

Where do maps come from?

We are used to the satellite maps that you can get online. For those, the self-driving cars can use them to plan out overall aspects of a trip, but it is often not detailed enough to get down to the specific street aspects (we’re getting there). A self-driving car could either store the satellite generated maps in the memory of the car, or it could use a communication connection to access such maps. The downside of the communication connection approach involves circumstance like I experienced whereby there was not a communication connection available.

The problem with storing maps in the memory of the self-driving car is that the maps might be outdated in comparison to what might be online. From a design perspective for a self-driving car, it is best to use both methods in conjunction with each other. Store maps on-board the self-driving car, and augment those maps with the communication connection when available.

The maps are often provided by the car maker. The car maker usually though didn’t create the maps, they bought them or licensed them from someone else that made the maps. A major map provider might have detailed maps generally, but often might not have localized maps. Third parties that make localized maps often then provide that last mile of detailed indications.

Another approach involves crowdsourcing for a map. There are companies that actually will pay people to help make local maps. You might have heard that Apple is desperate to get its maps used over say Google Maps, and has indicated that freelancers that want to earn some extra cash can do so for a small payment to them for each map addition or confirmation they make. Yes, you could earn a fortune helping to make maps, get going today!

Should a self-driving car believe a map? We say a self-driving car should use a mode of trust but verify. Just because a map says one thing, it does not mean that the actual road will be what the maps says. I was in San Diego last month, and after doing some work there, I wanted to get back to the major freeway and make my way home. I mapped using my in-car GPS. I dutifully followed its instructions. The voice told me to make a turn here, go straight a quarter mile, make another turn, and so on. I eventually could see that I was almost to the freeway. Upon one of the last instructions before I would get to the freeway onramp, I took the turn that the GPS said to do, and suddenly found myself at a dead-end. The road came to a dead-end. The GPS map showed that the road continued to the freeway entrance. I could see the freeway entrance, and I am betting that at some point the road did go through, but not anymore.

The point is that the self-driving car should be using its sensors to verify that what the maps says is true and accurate. The map provides overall guidance, but it should not be used to blindly drive the car into whatever trap awaits. The AI has to assume that for whatever reason there is a chance that the map being used will be faulty. It might be outdated. It might be inaccurate.

A map could even be intentionally falsified. Here’s an example of what some critics of self-driving cars are concerned about. You are a wealthy person, or maybe a known celebrity or political figure. You get into your true self-driving car, assume that it is a Level 5 (see my column about the Richter scale for self-driving cars). You settle into the self-driving car, have a few drinks, relax, and don’t pay attention to the driving journey. There isn’t any reason to pay attention since you aren’t the driver. You are merely a passenger along for the ride to your desired destination. Leave the driving to the AI.

Suppose someone has hacked the maps that you are using. You have indicated to the self-driving car where you want to go, doing via in-car commands (see my column on in-car commands for self-driving cars). The hacked maps fool the AI system into taking a particular route that appears to go to the desired destination. In fact, what has happened is that kidnappers are waiting at a point of the trip that they know the self-driving car will come to. Once the self-driving car arrives there, they will take the occupants and kidnap them, and maybe even take the car too (see my column on robojacking of self-driving cars).

This is a valid concern.

There are some ways to try and prevent or at least reduce the chances of this. For example, if the AI has multiple maps, it could compare the routes to see whether one is suspicious in comparison to the others. There also could be special encryption coding in the maps so that if they are hacked it would reveal that something amiss has happened to the map. Most self-driving car makers are assuming that the map they are using is perfectly fine and clean. They aren’t resorting to encryption or other protective measures, and they aren’t dealing with any redundancy and double-checking. This might seem like an overkill measure now, but once we have lots of self-driving cars on the roadway, and a few instances of map tampering, I am betting there will be a scramble by the self-driving car makers to do something about it.

Let’s assume that at some point while in your self-driving car, it cannot access maps or otherwise there just aren’t any maps for where you are. What should the self-driving car do?

It could use commonly known maze traversal techniques to make its way.

We have made use of the simple random mouse algorithm for a self-driving car that otherwise does not have a map available. This approach involves making random choices at junctions and is based on a constrained maze. It can work to some degree when in a neighborhood like the Beverly Glen example I mentioned before.  This is augmented by the self-driving car vision system that is looking for the street signs that say the name of the street (see my column about self-driving cars and street signs).

Another maze traversal technique is Tremaux’s algorithm. This is akin to how I made my own map while driving around Beverly Glen. The AI essentially creates a map as it goes along. The paths taken are then marked. There are other recursive algorithms that can also be used. All of these need to be considered in light of where the self-driving car is trying to drive. A classic maze shape might not be a proper fit to the locale of the driving journey.

In recap, a self-driving car should be doing this:

  •        Use a map if available
  •        Store the map on-board
  •        Augment with external maps via communication
  •        Trust but verify the map as the driving journey proceeds
  •        Be on alert for maps that are outdated, inaccurate, etc.
  •        Protect and detect for falsified maps
  •        Use multiple maps to do double-checks
  •        Be able to drive on a journey even when maps aren’t available
  •        Use various maze traversal techniques and create a map as warranted
  •        Potentially interact with the occupants as needed

No map does not mean no trip. Self-driving cars don’t need to be grounded simply because of a lack of an available map. Eventually, with V2V (vehicle-to-vehicle communication), a self-driving car that lacks a map might be able to bum a map off another vehicle (if it makes sense and is safe to do so). Crowdsourcing of maps is predicted to occur by self-driving cars that learn from each other. That’s a ways off in the future, and so meanwhile it still makes sense to have a self-driving car that can drive without a map and make its own map.  Adapt and overcome.

This content is originally posted to AI Trends.