Highlights

In brief

The GP3 navigational algorithm could improve travel times by accounting for dynamic, real-world fluctuations in rush hour traffic, road conditions and weather changes.

© Unsplash

How to get around in a jiffy

19 Jan 2023

Researchers have built a navigation algorithm that leverages multidimensional real-world data to map faster and more efficient traffic routes.

When you’re rushing to the airport to catch a flight, the last thing you want is to get stuck in a traffic jam. Thankfully, navigation apps like Waze or Google Maps can suggest the fastest routes by analysing traffic patterns in real-time throughout your journey.

While we’ve become somewhat reliant on these apps, we can’t always fully trust their recommendations. This is because current navigation algorithms don’t take into account other factors such as rush hour traffic fluctuations, unanticipated road conditions or abrupt weather changes — a complication that Hongliang Guo, a Research Scientist at A*STAR’s Institute for Infocomm Research (I2R), seeks to resolve.

Collaborating with researchers from A*STAR's Singapore Institute of Manufacturing Technology (SIMTech); the University of Electronic Science and Technology of China; and Nanyang Technological University, Singapore, Guo set out to build better algorithms that help travellers get to their destinations on time, every time.

The team proposed a Gaussian process path planning (GP3) algorithm as a more reliable solution to the reliable shortest path (RSP) problem, an exercise that aims to find a path from one location to another using the least resources. Unlike today’s navigational algorithms, GP3 uses a three-step pathway to take more dynamic, real-world factors into account for more dependable wayfinding.

“In the first step, GP3 transforms the initial difficult-to-solve RSP problem into a much simpler one called quadratic integer programming (QIP),” said Guo. “Next, our system modifies the QIP problem to introduce more efficient algorithms that could help find an optimal solution.”

Finally, the modified QIP problem is solved using an elementary path enumeration algorithm, which calculates the distance of each possible path to map the shortest and most efficient route.

When applied to various real-world transportation networks such as those in Anaheim, Chicago, Barcelona and Chengdu, the team’s GP3-powered platform was found to be both more accurate and faster than existing state-of-the-art algorithms.

“Compared to standard algorithms for RSP problems, our formulation can guide users to their destinations via the shortest route possible without straying too far from the estimated arrival time,” said Guo. “To the best of our knowledge, this is the first study that demonstrates a path-planning solution that is both accurate and efficient—crucial hallmarks of a reliable and intelligent navigation system.”

Guo is optimistic that navigation apps will soon get more efficient as GP3 can theoretically be integrated into some of the most popular ones, such as Google Maps.

To that end, the research team is currently working towards commercialising their GP3 model by adapting it for compatibility with popular navigation systems. “We will explore how GP3 could work hand-in-hand with other existing models in Google Maps and investigate what conditions favour which models best,” concluded Guo.

The A*STAR researchers contributing to this research are from the Institute for Infocomm Research (I2R) and the Singapore Institute of Manufacturing Technology (SIMTech).

Want to stay up to date with breakthroughs from A*STAR? Follow us on Twitter and LinkedIn!

References

Guo, H., Hou, X., Cao, Z. and Zhang, J. GP3: Gaussian Process Path Planning for Reliable Shortest Path in Transportation Networks. IEEE Transactions on Intelligent Transportation Systems 23, 1-16 (2021).│article

About the Researcher

Hongliang Guo received his Bachelor of Engineering in Dynamic Engineering and a Master of Engineering in Dynamic Control at the Beijing Institute of Technology, China, in 2005 and 2007 respectively. He holds a PhD degree in Electrical and Computer Engineering from the Stevens Institute of Technology, USA. His research interests include planning and learning under uncertainties. He served as an Associate professor at the University of Electronics Science and Technology of China, from 2016 to 2020. In 2021, he joined the Institute of Infocomm Research (I2R) in A*STAR.

This article was made for A*STAR Research by Wildtype Media Group