22 August 2017
Last summer Michael Cui, then a first-year student in Monash University’s Bachelor of Computer Science Advanced, took on a summer project with Daniel Harabor, Research Fellow, Monash School of Information Technology and Alban Grastien, a Senior Research Scientist, from Data61.
Michael’s task was to investigate how to efficiently compute a shortest path in a flat two-dimensional space. It's the kind of problem you might encounter in a computer game, where virtual characters need to navigate from one part of the game world to another. Since navigation is a fundamental topic, similar versions of the same problem are studied in many parts of the academic literature, for example Robotics, Computational Geometry and of course Artificial Intelligence. It’s a very competitive research area.
Daniel Harabor said, “The thing about navigation problems is that it's often easy to come up with a solution, but surprisingly tricky to find the best solution. So while many approaches exist, all of them, until now, involve compromises”.
One very common type of compromise is to trade optimality for speed. Algorithms of this type can be very fast but the paths they find might not be very good.
“For example, your virtual character might end up taking an unnecessary detour or they could make strange-looking turns for no apparent reason. Another type of compromise involves trading flexibility for speed. Such an algorithm might assume, for example, that the virtual world is static and nothing ever changes. That assumption can often simplify navigation but it's not very realistic”, said Daniel.
So it's a constant trade-off, especially for game developers who very much want to create rich dynamic worlds with artificial opponents that players will think are "smart".
During his project Michael developed a new state-of-the-art algorithm called Polyanya which has the remarkable property of being compromise-free: that means the method is guaranteed optimal, it does not make any unrealistic assumptions about the virtual world and it runs very fast.
Michael said, “Polyanya can find shortest paths tens and sometimes hundreds of times faster than its nearest direct rival. It's remarkable because no other method in the literature has the same advantages.”
Michael will present Polyanya at the 26th International Joint Conference on Artificial Intelligence from 19-25 August. This is the most prestigious conference in the field of Artificial Intelligence, which this year is taking place in Melbourne.
“This would be a great result if Michael were a PhD student -- but he's still a junior undergraduate!” said an equally amazed and proud Daniel.