|
Main /
News
MAPF Team wins the NeurIPS-20 Flatland Competition Team An_Old_Driver, consisting of three Ph.D. students from the University of Southern California and one Ph.D. student from Monash University, used multi-agent path finding (MAPF) technology to reach the highest score in both rounds of the NeurIPS-20 Flatland Challenge, a railway scheduling competition which was held in partnership with German, Swiss, and French railway companies. They outperformed all other entries in both tracks, including all reinforcement learning entries, to win overall first place in both rounds. According to the organizers, there were more than 700 participants from 51 countries making more than 2,000 submissions. NeurIPS is a top machine learning conference. The organizers characterized the research challenge, that lasted several months with continuous software submissions, as follows: "This challenge tackles a key problem in the transportation world: How to efficiently manage dense traffic on complex railway networks? This is a real-world problem faced by many transportation and logistics companies around the world such as the Swiss Federal Railways and Deutsche Bahn. Your contribution may shape the way modern traffic management systems are implemented, not only in railway but also in other areas of transportation and logistics." One of the main applications of MAPF is autonomous warehouses, such as Amazon fulfillment centers, where on the order of one thousand robots already navigate autonomously to move inventory pods all the way from their storage locations to the picking stations that need the products they store (and vice versa). Human workers no longer need to move around in such automated warehouses, collecting the right items under time pressure - a physically demanding job whose automation makes it possible to store 40 percent more inventory and at least double the picking productivity of the human workers. Optimal and even some approximately optimal path planning for these robots is NP-hard, yet one must find high-quality collision-free paths for them in real-time since shorter paths result in higher throughput or lower operating costs (since fewer robots are required). Algorithms for such multi-agent path-finding problems have been studied in robotics and theoretical computer science for a longer time but are insufficient since they are either fast but of insufficient solution quality or of good solution quality but too slow (especially for highly congested environments). MAPF technology applies to goal-directed collision-free navigation for multiple agents (such as ground robots, drones, trains, or characters in video games) in general, even though the team had not worked on train scheduling before. However, train scheduling raised several new issues, for example, because entries in the competition were rewarded not only for solution quality but also for how fast a solution could be found. The team built on its MAPF expertise but also developed new MAPF solvers and eventually managed to generate schedules for thousands of trains within a few minutes. Publications on the technical innovations are in the works. The team members of this collaboration between the University of Southern California and Monash University:
The advisors:
Hang Ma is an ex-Ph.D. student from Sven Koenig's group. Han Zhang, another Ph.D. student from Sven Koenig's group initially tried some ideas for the competition as well. While not having been directly involved in the competition, a lot of credit also goes to Satish Kumar (Research Assistant Professor in Computer Science, Physics, and Industrial Engineering), who has been part of Sven Koenig's group for a long time and provided many ideas over the years. The team is also working with other researchers at USC (Nora Ayanian and Bistra Dilkina) but also researchers in Canada, Chile, the Czech Republic, Israel, and (previously) Japan. The organizers of the competition had initially invited Sven Koenig to participate as expert but, given the great outcome for the team, now he is glad that he stepped down and was not involved in the organization of the competition other than its initial proposal to NeurIPS. The research at the University of Southern California and the US-Australian collaboration was supported by the National Science Foundation (NSF) under grant numbers 1724392, 1409987, 1817189, 1837779, and 1935712. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the sponsoring organizations, agencies, or the U.S. government. Links for further reading: |