12 September 2022 — NUS Computing professors David Hsu and Lee Wee Sun, along with their research collaborators, have won the 2022 IJCAI-JAIR Best Paper Award for their paper on planning for uncertainty in artificial intelligence.
The prestigious annual award is given by the International Joint Conference on Artificial Intelligence (IJCAI) and the Journal of Artificial Intelligence Research (JAIR). Each year, the prize is awarded to an outstanding paper published in the JAIR in the preceding five calendar years.
The group’s paper, titled DESPOT: Online POMDP Planning with Regularisation, was co-authored by NUS Computing PhD graduate Dr Nan Ye, currently a lecturer with the University of Queensland, and Computer Science graduate Adhiraj Somani (Class of 2013). It was published in 2017.
The paper focuses on the Partially Observable Markov Decision Process (POMDP), a principled mathematical framework that lays the foundation for decision making under uncertainty.
For decades, the POMDP had been considered theoretically interesting, but impractical for real-world applications, because of its intractably high computational cost.
One way of deciding the best action to take when solving a POMDP is to imagine all possible future observation sequences for all possible future action sequences, and take the action that has the best expected outcome in the future, assuming that optimal actions are always taken. Unfortunately, finding the best action is computationally intractable, explained Prof Lee, who is head of the Department of Computer Science at NUS Computing.
Enter the DESPOT, which is a more efficient POMDP algorithm.
“Since 2006, we spent more than 10 years in developing efficient POMDP algorithms. DESPOT, which stands for Deterministic Sparse Partially Observable Tree, is the culmination of this effort. It is based on a very simple idea: despite the myriad of possibilities, we just need to sample a relatively small representative subset to identify good decisions,” explained Prof Hsu, who is also director of the Smart Systems Institute.
Added Prof Lee: “Instead of computing all possible states, observations, and actions, it uses sampling and only computes for the sampled states and observations.”
“DESPOT provides rigorous mathematical guarantee about its performance. Most importantly, it has many applications. It has been implemented for autonomous driving and runs in real time for autonomous control of our robot vehicle,” said Prof Hsu.
He also added that the algorithms they developed has also been used in other robot tasks, such as in human-AI interaction and in disaster response systems. “DESPOT is one of the very few POMDP algorithms providing efficient, robust decision making under uncertainty in complex real-world situations.”
These situations may involve an autonomous car driving through a crowd of pedestrians, or even autonomous racing on a track crammed full of obstacles, explained Prof Lee. “As a result of the computational savings, it becomes more practical to use POMDPs to improve decision making in many practical problems, such as or autonomous driving through a crowd,” he said.
With the Best Paper win, the researchers walked away with prize winnings of USD$500 which they donated to NUS Computing’s Centre for Computing for Social Good & Philanthropy (CCSGP).
