Why Use Maps for Navigation?

Why choose maps as the basis for representing, sharing, and managing navigation for Autonomous Vehicles?

Vision dominates most of our lives and we have evolved acute abilities to find patterns and notice differences – these often mean the different between life and death (e.g., avoiding cars), or in earlier times, eating or going hungry or being eaten.

We are very aware of our location and our surroundings, so maps, which represent those features, have evolved as powerful tools for presenting all sorts of information related to geography.

Every child learns to use maps, either in school or on their smartphone, so there is an expectation that people will be able to understand and use maps. Their prevalence has now led to maps being used even for non-geographic information.

Maps have been used throughout history by people, “as essential tools to help them define, explain, and navigate their way through the world. … the earliest known maps are of the heavens, not the earth. Dots dating to 16,500 BC found on the walls of the Lascaux caves map out part of the night sky, including the three bright stars Vega, Deneb, and Altair (the Summer Triangle asterism), as well as the Pleiades star cluster… A map-like representation of a mountain, river, valleys and routes around Pavlov in the Czech Republic has been dated to 25,000 BP”.

Here is one interpretation of the dots as constellations. (Search on “Lascaux cave constellations” for more information.)

Maps are also the focus of many existing technologies:

1. Map data are already widely available for many different types of information

Maps for roads, geography, weather, and many other features are increasingly available online. More detailed maps have more limited availability, but many are already digitized, such as: building floor plans, utility infrastructure maps, manufacturer data (you’ll see why this is so important shortly).

For example, Science on a Sphere contains hundreds of maps as live datasets, showing everything from Animal Migrations to Volcanic Eruptions causing Tsunamis, and even other Planets. To really appreciate these visually, you need to see them stunningly projected in motion on a 5-foot sphere, such as Planet Adirondack.

2. Technology for efficiently transmitting and manipulating maps is widely available and provides many useful features

Hundreds of millions of people use these everyday on their smartphones, GPS devices, computers, etc. to:

• Find their location using GPS and other methods
• Zoom in and out with correspondingly more or less detail
• Find features such as restaurants, banks, and hospitals
• Make online reservations for planes or ships to select your seat or accommodations using a map of the vehicle.

3. Technology to collect data from myriad sources is in wide use

Many fields integrate data from myriad, widely distributed sensors for weather prediction, traffic analysis, earthquake monitoring, ocean conditions, and a host of other applications.

4. Maps are used in storing historical data, predicting the future, and displaying the results

TV and smart devices have made weather maps showing history and predictions ubiquitous. Increasingly we are seeing vehicle traffic levels and predictions displayed on our route maps. Diverse fields such as tsunami predictions are displayed as maps as well.

5. Maps are widely used in planning and optimization for many different disciplines

Your GPS device and your smartphone can calculate distances, ascent & descent for hikers, and estimated travel times. They even calculate minimum distance routes and adjust for your preferences for highways vs. scenery to help you find your optimal routes.

Several of my years at Bell Labs were spent building optimal network expansion algorithms, and later studying digital network evolution, and we used maps for everything from data collection and storage to analysis and presentation of the results of analyses.

6. Technology is widely used for Distributed Dynamic Maps with simultaneous updates from and displays to thousands of participants

Massively Multiplayer Online Games, or MMOGs, such as World of Warcraft, with about 9M subscribers, can have thousands of players navigating using maps in the same virtual space. So the system must provide not only the static information about environment but accept the acceleration control information from each player while also showing the motions of all the other players within view on that player’s screen/map.

These players can be distributed all around the world, with only the Internet connecting them. Thus we have thousands of processors collaborating to navigate, and perform other functions, in a shared virtual space.

Compared with this, having a few dozen nearby vehicles navigating sounds like a relatively easy problem. Of course, we have to deal with life-and-death in the real world, so the system must provide 100% safety and reliability. And we need to account for people and systems trying to hack, jam, and spoof the navigation system. So this isn’t such an easy task after all. But at least we have a feasibility demonstration of a large-scale distributed processing arrangement handling real-time, albeit artificial, navigation.

7. Technology for Modeling Motion

Newton’s laws of motion, F = Ma, are at the heart of vehicle navigation (unless you are traveling at an appreciable fraction of the speed of light J). The throttle, brakes, and steering all control forces, which convert to accelerations, and then integrate over time into velocity and again into position.

My graduate work was in Control Systems and Optimization Theory, so I have spent a lot of time with the techniques of modeling and analyzing motion and navigation.

We use position, velocity, and acceleration in 3-Dimensions, and time as the 4^th dimension to analyze and control vehicle motion (if you want to be more technical, this is a 9-dimension space with time-varying elements; however, we also have “plans”, such as the route you intend to take to get to the restaurant in time for your reservation, so time plays a more complex role with additional constraints; plus you need to consider interactions with other vehicles, moving objects such as people and animals, and traffic signals, so being even more technical it’s a very large dimension, complex “space” – but I don’t think that’s very helpful at the level we are discussing, so we’ll stick with 4 dimensions).

You might think we could get by with only 2 space dimensions, assuming we are ignoring air travel. However, height plays an important role. For example, we were taking a load of our belongings to the storage facility for our move, but our route was blocked only 300 yards from our destination because a truck tried to go through a railroad underpass which wasn’t tall enough, so the underpass was blocked for over an hour while they pulled the truck out – we had to go 5 miles out of our way to go through the next underpass for the railroad. More frequently encountered issues include needing additional power to go up a hill, or braking to go down the hill, and whether the arms of my father’s Personal Mobility Vehicle will fit under the restaurant table he is approaching.

So using a 3-Dimension position space plus time as the 4^th dimension is natural for managing navigation of Autonomous Vehicles, with the derivatives understood to be included.

8. Alternatives for Managing Navigation Information

Many systems exist for managing navigation information, and they have made a variety of choices for what design to use. Key factors include:

• The Amount of Information, which needs to be transmitted – this is often intentionally limited based on other factors in the design
• Number of Cases, for example a railroad switch is either straight or turned, while telegraph messages have an unlimited number of different messages to be transmitted
• Data Rate Available, this limits design choices
• Information Importance, for some systems, the information is life-or-death, for others it varies with content, such as Telegraph messages, or with usage, such as GPS
• Number of Participants, some systems are between 2 parties, such as Telegraph, others range from a few participants, such as nearby vehicles, to an unlimited number for GPS
• Two-Way, systems can be either one-direction only, such as GPS, or two-way
• Ease of Updates, some systems are fixed in hardware, such as Railroad Signaling, others are dependent on changing human knowledge and practice, such as Telegraph, while others are remotely software upgradeable
• Strategy, messages can be fixed, systems can be updated incrementally, have a flexible structure, or use voice for flexibility (note these typically use codes for abbreviating common messages – which require updating all the users’ knowledge, and language for unspecified messages)
• Design Chosen, there are many different approaches

To compare several systems, I have coded them from red, most limited, to Green, most flexible, (the numerical values -2 to +2 are merely to get the colors to work J).

Comparison of parameters and choices for other Navigation Systems:

Navigation Type	Amount of Information	Number of Cases	Data Rate Available	Information Importance	Number of Participants	Two-Way	Ease of Updates	Strategy	Design Chosen
Railroad Signaling	-2	-2	-2	-2	Few	-2	-2	Hardware + Message	Fixed signals and Limited Messages
Telegraph	1	2	-1	0	2	2	-2	Fixed	Morse Code
GPS	-2	-2	-1	0	Open	-2	-2	Fixed	Parameters
Airplane to Tower	0	0	0	-2	2	2	-1	Voice	Codes + Alphabet + Language
Proposed Car Warnings	-1	-1	0	-1	Few	-2	-1	Incremental	Message-Oriented
Proposed AV Navigation	2	2	2	-1	Many	2	1	Flexible structure	Dynamic 4-D Maps

The main point of this comparison is that different situations call for different solutions. Of course, the evolution of technology plays a huge role due to the time differences in design for these cases, in particular, high data rates and the ability to remotely download software updates greatly increases the flexibility available to the designer.

Thus the feasibility of using maps for Autonomous Vehicle navigation hinges on high-speed networks and significant local computing power.