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).
