Train scenario from the NeurIPS Flatland Challenge (GIF/Zhe Chen)
Beginning on Sept. 7, 2020, 700 participants from 51 countries around the world competed in the 2020 Neural Information Processing Systems (NeurIPS) Flatland Challenge. Participants had three months to tackle a key problem in the transportation world: how to efficiently manage dense traffic on complex railway networks.
On Dec. 1, 2020, a team of four Ph.D. computer science students—Jiaoyang Li, Yi Zheng, and Shao-Hung Chan of the USC Viterbi School of Engineering and Zhe Chen of Monash University in Australia, known collectively as Team Old Driver—were crowned world champions of this prestigious competition.
The Railway Problem
The premise of the challenge is simple: given train scenarios ranging from simple (one train on a track) to complex (multiple trains on multiple intersecting paths travelling at different times,) devise an algorithmic solution that allows all trains to arrive at their destination as quickly as possible.
“The competition was incredibly fierce; and we won round one by the slimmest of margins,” said Li, the team’s presenter. “I’ve never been so ecstatic about a victory.”
They realized soon after passing round one that to finish on top, their solution would not only be efficient, it would be optimal in algorithmic runtime. With their approach, a combination of leading planning algorithms and graph search heuristics, as well as new technologies they developed, Team Old Driver managed to generate schedules for thousands of trains within a few minutes, trumping over 2000 other submissions.
Success In The Making
Before becoming Flatland champions, Team Old Driver was a destined success story in the making. For several years, Sven Koenig, USC Viterbi professor of computer science, has led a research group of award-winning students devoted to solving some of the most challenging multi-agent path finding (MAPF) problems.
MAPF, according to a 2019 scholarly article co-authored by Koenig, is the fundamental problem of planning paths for multiple agents to ensure that they can follow these paths concurrently without colliding with each other. Applications of MAPF are seen widely in artificial intelligence endeavors, such as autonomous vehicles and gaming.
Another application is one more relevant to Koenig’s research: automated warehouses, such as Amazon fulfillment centers, where hundreds of robots work alongside humans to fulfill speedy deliveries.
Koenig’s students have received lavish praise for their work, including best paper, best dissertation, best research assistant, and best teaching assistant awards. A proud Koenig couldn’t imagine anything better — until it got even better.
Programming Throughout The Pandemic
Li was a third year Ph.D. student in Koenig’s group in February 2020 when she travelled to Australia to do research with Peter Stuckey, a professor of information technology at Monash University. Koenig and Stuckey’s research groups collaborated on MAPF problems frequently, and Li was excited to expand her research with new colleagues for the semester.
Then, the COVID-19 pandemic hit and Li got stuck in Australia indefinitely.
It was at Monash where she met Chen, one of Stuckey’s Ph.D. students. That fall, when they read about the Flatland Challenge, they decided to join forces.
“No one on our team had ever worked on optimizing transportation networks,” Chen said. “But when we realized that our MAPF research could be applied to the railway problem, we were determined to solve it.”
Li and Chen scouted Zheng and Chan, two of Li’s USC Viterbi lab mates in Koenig’s group, to join them. Team Old Driver was born.
With Li and Chen in Australia, Zheng in Los Angeles, Chan in Taiwan, Team Old Driver mastered the art of remote collaboration, trading video conferences for consistent group chat updates, and meeting “face-to-face” only when absolutely imperative.
“The students were extremely motivated. I was so proud to see all of their hard work and commitment pay off with the highest honor,” Koenig said.
NeurIPS Flatland 2020 was sponsored by three transportation and logistics companies highly interested in optimizing dense traffic networks: Swiss Federal Railways, Deutsche Bahn, and Société nationale des chemins de fer français, France’s national state-owned railway company.
As victors of the challenge, Team Old Driver was invited to speak at the 2020 NeurIPS conference in December.
“MAPF is a topic our teams have been passionate about for years,” Li said. “It’s awesome to know our contribution may shape the way modern traffic systems are implemented.”
Published on March 10th, 2021
Last updated on March 10th, 2021
