菜单总览
新闻

我院五篇论文被人工智能顶级会议AAAI接收

  • 2020.12.23
  • 新闻
近日,我院机器学习与应用研究中心查宏远教授、付樟华博士,和计算机视觉研究中心黄锐教授团队共五篇论文被人工智能领域权威性顶级会议 AAAI 接收。

        近日,我院机器学习与应用研究中心查宏远教授、付樟华博士,和计算机视觉研究中心黄锐教授团队共五篇论文被人工智能领域权威性顶级会议 AAAI 接收。付樟华博士共参与了其中三篇论文,以下介绍的是付樟华博士作为第一作者,查宏远教授作为通讯作者发表的 Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances 一文。

        AAAI会议由人工智能促进协会AAAI(Association for the Advancement of Artificial Intelligence)主办,始于1980年,会议也以AAAI为简称。该会议注重理论与应用,也讨论对人工智能发展有着重要影响的社会、哲学、经济等话题,是人工智能顶级会议之一。

        今年,AIRS 学术科研工作捷报连连,前有 Nature 和 Nature Communications 发文,后有 IROS2020 最佳论文获奖与提名以及 JPC Letters 论文发表,充分展示了 AIRS 的科研实力。

研究意义

        旅行商问题(TSP)是一个经典 NP-hard 问题。针对该问题,已有许多传统方法,包括精确算法(以 Concorde 为代表)和启发式算法(以 LKH3 为代表)。不过,这些传统方法虽然性能强大,却过于依赖于专家知识。为减轻对专家知识的依赖,近年来不少学者尝试采用机器学习方法求解 TSP 问题,其中包括许多基于监督学习的模型。然而,现有的监督学习模型普遍面临难以泛化至大规模算例的问题。本文重点研究如何采用图分割、图转换和热力图融合等技术,将预训练好的小规模模型应用于任意大规模 TSP 算例,从而提高模型的泛化能力。在此基础上,本文进一步地采用强化学习方法(蒙特卡洛树搜索)搜索优质解。

研究背景

        TSP 问题在机器人路径规划、交通物流、生物信息、芯片设计等领域有着非常广泛的应用背景,比如电力系统巡检机器人的路径规划问题即可以建模成 TSP 问题,滴滴、顺丰、美团等公司经常面临的车辆调度问题也可以看成是在 TSP 的基础上叠加多种业务要求(多车辆、取送货等)及约束(容量约束、时间约束、续航里程约束等)。

图1:TSP实例(从左上角起点出发,依次访问所有结点,到达终点后返回起点)

研究概要

        本文提出了一种处理不同规模 TSP 问题的算法 Att-GCRN&MCTS,该算法先在小规模TSP算例集上训练一个小规模(n=20)的注意力图卷积神经网络(Att-GCRN)。训练好模型之后,输入一个 n=20 的 TSP 问题,即可输出一个热力图(每条边属于最优解的概率)。为提高模型的泛化能力,本文采用一系列图分割、图转换和热力图融合等技术,可基于小规模的预训练网络,融合得到任意大规模 TSP 问题的热力图。之后,将融合得到的热力图输入一个基于强化学习(蒙特卡洛树搜索,即MCTS)的迭代搜索算法,得到 TSP 问题的解。Att-GCRN&MCTS 融合监督学习与强化学习方法,通过监督学习获取热力图,然后基于热力图使用强化学习获得 TSP 问题的解。大量的实验测试表明,Att-GCRN&MCTS 算法在不同规模的 TSP 算例上均明显优于目前所有学习型方法。在点数达到10000时(此时精确算法Concorde难以在限定时间内停止),Att-GCRN&MCTS 与目前最好的启发式算法 LKH3 在优度方面的差距约4.39%,而此前最佳的学习型算法与 LKH3 的差距超过80%。

作者介绍

        论文第一作者付樟华博士分别于2005年、2007年、2011年获得华中科技大学学士、硕士、博士学位,2012年至2015年在法国LERIA实验室从事博士后研究。2018年5月加入香港中文大学(深圳)机器人与智能制造研究院,现任研究员,同时兼任深圳市人工智能与机器人研究院研究员。付博士长期从事人工智能和运筹优化领域研究,针对任务调度、路径规划、网络优化、多机器人协同调度等NP-hard问题,设计出一系列高性能算法,在大量国际标准算例上打破世界最佳纪录,以第一作者或通讯作者发表CCF A或JCR一区论文近二十篇。此外,付博士还于2014年12月参加运筹优化领域著名的国际算法设计大赛:第11届DIMACS Implementation Challenge,最终夺得冠军。 

        论文第二作者邱凯彬是香港中文大学(深圳)一年级硕士研究生,他的研究方向包括深度学习在组合优化问题上的应用和多智能体调度。

        论文通讯作者查宏远教授为香港中文大学(深圳)校长讲座教授、深圳市人工智能与机器人研究院副院长兼机器学习与应用研究中心主任。查宏远教授于1984年毕业于上海复旦大学数学系, 并于1993年获得斯坦福大学科学计算专业博士学位。查教授于1992年至2006年任职于宾州州立大学计算机科学与工程学院,他也曾于1999年至2001年任职于 Inktomi 公司。他目前的研究兴趣主要集中于机器学习。

代码:https://github.com/Spider-scnu/TSP

论文地址:https://github.com/Spider-scnu/TSP/blob/master/Full%20version%20of%20AAA...