An automotive navigation system is part of the automobile controls or a third party add-on used to find direction in an automobile. It typically uses a satellite navigation device to get its position data which is then correlated to a position on a road. When directions are needed routing can be calculated. On the fly traffic information (road closures, congestion) can be used to adjust the route. Dead reckoning using distance data from sensors attached to the drivetrain, an accelerometer, a gyroscope, and a magnetometer can be used for greater reliability, as GNSS signal loss and/or multipath can occur due to urban canyons or tunnels. Mathematically, automotive navigation is based on the shortest path problem, within graph theory, which examines how to identify the path that best meets some criteria (shortest, cheapest, fastest, etc.) between two points in a large network. Automotive navigation systems are crucial for the development of self-driving cars. History Automotive navigation systems represent a convergence of a number of diverse technologies, many of which have been available for many years, but were too costly or inaccessible. Limitations such as batteries, display, and processing power had to be overcome before the product became commercially viable. 1961: Hidetsugu Yagi designed a wireless-based navigation system. This design was still primitive and intended for military-use. 1966: General Motors Research (GMR) was working on a non-satellite-based navigation and assistance system called DAIR (Driver Aid, Information & Routing). After initial tests GM found that it was not a scalable or practical way to provide navigation assistance. Decades later, however, the concept would be reborn as OnStar (founded 1996). 1973: Japan's Ministry of International Trade and Industry (MITI) and Fuji Heavy Industries sponsored CATC (Comprehensive Automobile Traffic Control), a Japanese research project on automobile navigation systems. 1979: MITI established JSK (Association of Electronic Technology for Automobile Traffic and Driving) in Japan. 1980: Electronic Auto Compass with new mechanism on the Toyota Crown. 1981: The earlier research of CATC led to the first generation of automobile navigation systems from Japanese companies Honda, Nissan and Toyota. They used dead reckoning technology. 1981: Honda's Electro Gyrocator was the first commercially available car navigation system. It used inertial navigation systems, which tracked the distance traveled, the start point, and direction headed. It was also the first with a map display. 1981: Navigation computer on the Toyota Celica (NAVICOM). 1983: Etak was founded. It made an early system