Meet the devs that coded their way out of the coronavirus chip shortage

Necessity is the mother of invention. Never has that been truer. With global chip shortages ravaging automotive supply chains, carmakers are facing factory closures, production is slowing and costs are rising. Engineers at TomTom, though, are finding ways to innovate around the problem to prevent production delays.

Recap on the shortage

There are a whole host of factors that came together to create the chip shortage, but the two that had the biggest impact were: factory closures in Asia due to coronavirus lockdowns and the fact that semiconductors aren’t easy to make.

According to figures from Bloomberg, 12 weeks was the average lead time for semiconductor chips in March 2019. By January 2021, leads times were touching 15 weeks.

That might not sound like a significant increase, but for an industry like car production, which relies on just-in-time supply, a delay of just hours can cause production lines to come to a halt. When delays amount to days, or even weeks, significant problems are met.

On top of this, semiconductors are complex to make. The chips are produced on highly specialized production lines which must be kept incredibly clean, within very specific temperatures and free from static electricity. These days, most of the work is carried out by robots, which are also in limited supply, very expensive and not readily available. New production lines can take many months to come online.

Semiconductor chips are manufactured in sterile environments. Production lines are complex and expensive to run. Setting up new ones to fill in shortages in supply is not easily done.

Servicing demand when supply is strangled isn’t a simple task. However, a group of TomTom engineers are taking on the challenge of the semiconductor shortage and are finding ways to circumvent the need for some chips entirely.

Microprocessors and the automotive industry

Due to the technical complexity of modern cars, the automotive industry is one of the hardest hit by the shortage. Depending on who you talk to, and the complexity of the car you’re talking about, automobiles are said to contain anywhere between 500 and 1,500 microchips.

Not all those chips are created equal, though. Some are more vital to the car’s overall functioning than others. When it comes to navigation and positioning systems, there are microchips that absolutely must be present if the system is to function as intended; the gyroscope-on-a-chip is one.

Thanks to global navigation satellite system (GNSS) receivers, map data, wheel ticks, speed and gyroscopes, sat nav systems can calculate where a car is, how far it travels and, crucially, in which direction. It does this by continually repeating a two-step process which involves integrating data from these sources with a measure of time and correcting to the GNSS. In a basic sense, by then pairing this information to a map is what allows the vehicle to be placed correctly on a map, TomTom Senior Architect, Dr. Eugeniusz Bednarz explains.

GNSS and gyroscope data are crucial for navigation. They inform the system of the location and direction of travel.

However, remove the gyroscope from the system and the navigation system will have to rely on GNSS. The GNSS system will still be able to position the car in terms of longitude and latitude, but that won’t tell the car’s navigation system which direction the car is heading until it starts moving. When the car stops, the heading direction will remain based on how the vehicle was just traveling. However, if you then drive backwards, the heading will flip even though the car is still facing the same way. In this case, it’s possible to compute the heading of the vehicle but not the orientation.

In the worst case, if the gyroscope isn’t present the sat nav either won’t function or the system will fall back on GNSS data and the system’s performance will be limited.

“Pure GNSS receivers can only provide suitable fixes for navigation where at least four satellites are visible, trackable and used,” Dr Bednarz adds. GNSS performance decreases in urban canyons due to reduced satellite visibility, signal reflections and multipath interference caused by tall buildings and electromagnetic interference from adverse weather like lightning. As such, GNSS systems alone are not able to support continuous navigation, which is an absolute requirement for automotive navigation systems.

“Without the gyroscope chip, our algorithm is lost because it doesn’t get any direction,” Stephane Leclere, project manager at TomTom tells me. “It detects there is a problem, and it enters a recovery mode. If the chip is missing, our algorithm falls back to GNSS with limited performance.”

The gyroscope, along with a measure of how far the wheels travel, is a crucial component in a satellite navigation system as it safeguards against a loss of GNSS signal – this redundancy measure is called dead reckoning. Dead reckoning is the process of calculating position based on the last known position and measured sensor data that’s been logged since the location was last known. It’s the ability to understand a vehicle’s location and direction when GNSS signals are lost.

Suppose you enter a tunnel as you’re driving; you’ll lose the GNSS signal quite quickly. However, the gyroscope can effectively fill in the blanks by continuing to inform the navigation system of the direction of travel, and using wheel-tick sensors, how far the vehicle has traveled.

“Dead reckoning is using two things, it’s using a gyroscope to figure out if the car is turning left or right, and the wheel ticks from the ABS (anti-lock brake system) to know how many meters the car has traveled,” Leclare tells me.

This allows navigations systems to position the car correctly on the map. “You have how many meters you did, plus the direction, so you can extrapolate where the car went,” Leclare adds. If you compare this with the map, then you can also know if the car took a right or left turn and overlay a track showing the car’s path of travel.

Or as Dr Bednarz explains it: “We get a measurement from the gyroscope, a measurement from the wheel ticks, the engaged gear to indicate driving direction, we integrate both measurements into position, propagate against time, and correct to GNSS.” This process happens over and over, to constantly update the vehicle’s navigation system of where the vehicle is, which direction it's heading and how fast.

By the time you’re out of the tunnel, and the sky is clear and conditions for GNSS are perfect, the GNSS will reconnect, reconfirm the exact position of the travel, and complete accuracy will be restored. The driver will have no idea that any of this happened. Without the gyroscope, this wouldn’t be possible – that is until now at least.

Understanding location without a gyroscope

As Leclare mentioned, when there is no gyroscope, and the GNSS doesn’t have a good enough signal, the system won’t work correctly as there is no other redundancy system to take over. Faced with a possible shortage of gyroscope chips, Dr Bednarz and his colleagues began to think of ways to achieve this same level of accuracy without having to rely on the specialized chips.

Gyroscope chips look a little something like this. They’re an entire device on a chip. Small and unassuming, but vital to navigation systems.

One of the first things to take care of was the fact that sat nav systems check the gyroscope to ensure its presence and correct operation. In normal operation, the system recognizes it’s there and works correctly. However, when it isn’t present, the system may have trouble initializing.

Thankfully, in this case, the positioning algorithm can already take the lack of a gyroscope into consideration and continue to work even when it isn’t present. The next and most challenging step was to develop a new dead reckoning system that can operate when neither a gyroscope nor GNSS signal are present.

The algorithm Dr. Bednarz and his colleagues created is far from simple, but we’re going to look at it in as simple terms as possible. Dealing with gyroscope data, satellite positioning data and vehicle data is complicated, there’s no easy way around it.

So, in the most basic terms possible, what the group of TomTom engineers have created is a way of tracking a vehicle’s location and direction of travel, when there is no GNSS or gyroscope data available. They do this by using data from other sources on the vehicle: the wheel tick sensors.

Using these sensors, it’s possible to understand how far a vehicle has traveled and in what direction. These two crucial measures are foundational to building a dead reckoning system that doesn’t rely exclusively on GNSS and gyroscope data.

One way of doing this is to independently measure how far each wheel travels. By taking readings from the rear left and rear right wheels, it’s possible to calculate the direction the vehicle is travelling.

Think of the rear axle, it joins both wheels together and there is a differential in the middle that allows the wheels to turn at differing speeds when the vehicle changes direction. When taking a corner, the outside wheel must travel ever so slightly further than the inside wheel.

By actively measuring the distance each wheel travels, it’s possible to keep track of the turns a vehicle has made. Using this alongside wheel tick sensors to measure overall distance, it’s possible to match the vehicle’s path of travel to a map. Assuming we have at some point had a correct GNSS position to serve as a starting location.

Image for illustrative purposes and is vastly simplified. When a vehicle changes direction, the wheel on the outside of the turn travels further (see the blue lines) than the wheels on the inside of the turn, see the red lines. Measuring these distances helps understand directional changes in a vehicle when a gyroscope isn’t present.

“I replaced the module which was modeling the gyroscope. So, we could calculate the heading usually provided from the gyroscope measurements with the differential,” Dr Bednarz tells me. When this is achieved, data from wheel ticks and the differential could theoretically replace the gyroscope indefinitely and can fill in for the GNSS for periods of time when the signal is lost.

Overcoming unexpected challenges

Explaining this system in such a way makes it sound simple, but it’s far from it in practice. As Bednarz, Leclare and their colleagues found out, there are many considerations that need to be made to ensure this system works in all cars and in all scenarios – innovation is rarely easy.

As Dr Bednarz explains, “A loop of driving and testing is required. We collect the data, we build the model, we validate the model, and then undertake detailed testing to discover limitations and then we try to overcome the limitations of the model.”

One of the first identified limitations to overcome was understanding the dynamics of the vehicle. For example, “The first limitation didn’t include a dynamic estimation of the width of the vehicle, the distance between the left and right wheel,” Dr Bednarz says.

That’s simple to account for, the width between the wheels is fixed, it only needs coding once. Indeed, every car is different, but the distance between wheels on a car is known and doesn’t change, so this can be injected into the algorithm for each vehicle. By factoring in the width of the wheels, it’s possible to track the direction of the car more accurately by simulating its turn radius.

The differential of the vehicle allows left and right wheels to turn at different speeds.

This is just one of the first and most basic examples of the challenges the TomTom engineers faced. Besides wrestling with code iterations and troubleshooting edge cases, the engineers had to develop an understanding of how the driving dynamics affect how a vehicle changes direction in the most detailed way.

How fast a vehicle is traveling, the type of turn it’s making, the scenario in which it’s driving and the speed it steers all affect the geometry of the turn it will make. The issue is that all these different turns are represented by different shapes and geometries. What’s more, vehicles tend to have more than one axle, which also affects how it changes direction. If the model the TomTom engineers were developing only accounted for one axle, mapped turns wouldn’t always be accurately reflected.

Think about when you change lanes on a highway or take the exit ramp. These types of maneuvers are quite different from turning a corner in a city. Generally speaking, in city driving, when making turns around corners, the turns can be mapped by parts of a circle. However, on multi-lane highways and slip roads, turns display a different geometry.

“This effect is more pronounced in some situations”, Dr Bednarz adds. “On multi lane roads, slip roads and highway entries and exits, roads designed to maintain a high flow of vehicles, the turns vehicles tend to make are represented by parts of clothoids [complex curve shapes] rather than parts of circles.”

If these aren’t accounted for, the system would incorrectly adjust the trajectory of the vehicle and its calculated position could be incorrect.

“If you drive and steer in a two-axle vehicle, but the turn being mapped is based on the geometric model for a single-axle system, the mapped turn will be greater than the actual turn made, unless the turn represents part of a circle.”

If you were wondering what a clothoid, also known as a Euler spiral, is, it’s a type of curve, the curvature of which changes along its length. They’re used a lot in railway design to transition between two parallel linear tracks. You’ll almost certainly have seen them before, even if you didn’t know the name.

Uncovering these dynamics can only happen during testing. Rather than having to go out and drive in the real world to test the effectiveness of the model, the team can simulate an entire day’s worth of driving within a few seconds. They can then compare the model’s performance against a known truth by overlaying the simulated vehicle’s trajectory on a real map. This allows them to spot any errors where the track doesn’t follow the road. After this, the process of iterative improvement can begin again.

With every code revision, the model’s accuracy has improved, but it’s still in constant development. The team has thousands of kilometers worth of historical drive data which it can test new iterations of the model against.

Dr Bednarz believes the model has potential for further development and will be on par with the performance of the gyroscope on a chip. Speaking with him, I get the sense he’s being humble and that developing this solution is a pursuit of perfection, and for Bednarz and his colleagues, the work will never be completely finished. They will always be looking for ways to improve their model.

With good reason, too, because it could have a dramatic impact on the automotive industry.

Cost savings and cheaper navigation

While the chip shortage gave the motivation necessary for Bednarz, Leclare et al. to develop their system and help carmakers navigate their way around supply chain issues, it will also open new opportunities for carmakers to forgo the use of the gyroscope chip in markets where it’s not really needed.

The algorithm-based model isn’t just a band-aid solution, it could very easily replace gyroscope chips entirely.

In some countries, particularly in South America, there isn’t as much need for gyroscope chips as there is in places like Europe and the US. There aren’t many road tunnels or highly built-up areas which can negatively affect GNSS signals.

In countries where there aren’t many tunnels or dense, tall buildings, and GNSS locks are strong and consistent, there isn’t much need of a gyroscope chip with this new algorithm.

With strong and consistent GNSS signals, the algorithm the TomTom engineers have created will be highly reliable, even without a gyroscope. The GNSS signal provides an accurate longitude and latitude, the algorithm keeps the vehicle’s navigation system updated in terms of direction and trajectory and pairing it with a map ensures the vehicle appears in the correct location on the nav screen.

This opens a new opportunity for the low-end, budget-oriented car market.

Typically, gyroscope chips cost less than $10, which isn’t much. But for carmakers that produce and sell millions of vehicles a year globally, not needing to equip cars with a gyro chip could save them tens of millions of dollars a year in hardware costs alone.

On top of that, there are significant integration and development costs that are accrued to make that chip part of the vehicle’s navigation systems. With an algorithm-based solution these costs are circumvented too.

What’s more, and perhaps the most valuable part of this, is that the algorithmic-based system that the TomTom engineers have created could be added to low end cars that previously didn’t have navigation systems as they were too costly and complex to produce on budget focused vehicles.

It has the potential to bring accurate navigation to even more people, to those that previously couldn’t afford it.

While the algorithm that’s been created here was born of necessity, it looks like it’ll be with us for years to come and further democratize navigation. Even though it was born of difficult circumstances, it’s a clear positive to come out of the pandemic and chip shortage.