Multi-Agent Reinforcement Learning in Helicopter Airport Dispatching

doi:10.3778/j.issn.1002-8331.2205-0370

Abstract

Abstract: Fast and efficient helicopter airport dispatching is the main challenge faced by modern helicopter airport dispatching system. Helicopter airport dispatching can be regarded as a classical multi-agent path finding problem. A helicopter airport dispatching test platform is designed, which uses a two-dimensional grid environment for rapid test of various algorithms. The airport dispatching test platform edits the map according to the actual terrain of the airport, and provides the traditional centralized planning algorithm and the algorithm based on multi-agent reinforcement learning to carry out fast and efficient simulation dispatching experiments. In order to explore the potential of multi-agent reinforcement learning in airport scheduling, a large number of experiments are carried out, and the applicability and characteristics of different types of algorithms are compared and analyzed. The experimental results show that the reinforcement learning method based on multi-agent has good scalability and real-time planning effect. The test platform provides a good starting point for further research on airport scheduling, and will have a beneficial impact on the application of multi-agent path finding in practical scenarios in the future.

Key words: airport dispatching, test platform, multi-agent path finding, reinforcement learning

摘要： 快速高效的直升机机场调度是现代直升机机场调度系统面临的主要挑战。设计了一个直升机机场调度试验平台，使用二维网格环境，供多种算法进行快速试验。机场调度试验平台根据机场实际地形进行地图编辑，提供了传统的集中式规划算法和基于多智能体强化学习算法来进行快速高效的模拟调度实验。实验表明，基于多智能体强化学习方法的可扩展性和实时规划效果较好。试验平台为进一步研究机场调度提供了良好的起点，对未来多智能体路径规划问题应用于实际场景将会产生有益影响。

关键词: 机场调度, 试验平台, 多智能体路径规划, 强化学习

LIU Zhifei, DONG Qiang, LAI Jun, CHEN Xiliang. Multi-Agent Reinforcement Learning in Helicopter Airport Dispatching[J]. Computer Engineering and Applications, 2023, 59(16): 285-294.

刘志飞, 董强, 赖俊, 陈希亮. 多智能体强化学习在直升机机场调度中的应用[J]. 计算机工程与应用, 2023, 59(16): 285-294.

References

[1] YAKOVLEV K，ANDEYCHUK A.Any-angle pathfinding for multiple agents based on SIPP algorithm[C]//Proceedings of the 27th International Conference on Automated Planning and Scheduling，2017.
[2] LI J，TINKA A，KIESEL S，et al.Lifelong multi-agent path finding in large-scale warehouses[C]//Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems，2020：1898-1900.
[3] MA H，YANG J，COHEN L，et al.Feasibility study：moving non-homogeneous teams in congested video game environments[C]//Proceedings of the 13th AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment，2017：270-272.
[4] LI J，CHEN Z，ZHENG Y，et al.Scalable rail planning and replanning：winning the 2020 flatland challenge[C]//Proceedings of the 31st International Conference on Automated Planning and Scheduling，2021：477-485.
[5] CARTUCHO J，VENTURA R，VELOSO M.Robust object recognition through symbiotic deep learning in mobile robots[C]//2018 IEEE/RSJ International Conference on Intelligent Robots and Systems，2018：2336-2341.
[6] FELNER A，STERN R，SHIMONY S E，et al.Search-based optimal solvers for the multi-agent pathfinding problem：summary and challenges[C]//10th Annual Symposium on Combinatorial Search，2017.
[7] SURYNEK P，FELNER A，STERN R，et al.An empirical comparison of the hardness of multi-agent path finding under the makespan and the sum of costs objectives[C]//9th Annual Symposium on Combinatorial Search，2016.
[8] BARTáK R，?VANCARA J，?KOPKOVá V，et al.Multi-agent path finding on real robots：first experience with ozobots[C]//16th Ibero-American Conference on Artificial Intelligence.Cham：Springer，2018：290-301.
[9] ELLIS J.Multi-agent path finding with reinforcement learning[D].Stellenbosch：Stellenbosch University，2021.
[10] MA H，HARABOR D，STUCKEY P J，et al.Searching with consistent prioritization for multi-agent path finding[C]//Proceedings of the 33rd AAAI Conference on Artificial Intelligence，2019：7643-7650.
[11] LAURENT F，SCHNEIDER M，SCHELLER C，et al.Flatland competition 2020：MAPF and MARL for efficient train coordination on a grid world[J].arXiv：2103.16511，2021.
[12] CHEVAILIER-BOISVERT M，WILLEMS L，PAL S.Minimalistic gridworld environment for OpenAI Gym （2018）[EB/OL].（2016）[2022-04-26].https：//github.com/maximecb/gym-minigrid.
[13] STERN R，STURTEVANT N R，FELNER A，et al.Multi-agent pathfinding：definitions，variants，and benchmarks[C]//12th Annual Symposium on Combinatorial Search，2019.
[14] FERGUSON D，LIKHACHEV M，STENTZ A.A guide to heuristic-based path planning[C]//Proceedings of the International Workshop on Planning Under Uncertainty for Autonomous Systems，International Conference on Automated Planning and Scheduling，2005：9-18.
[15] FILAR J，VRIEZE K.Competitive Markov decision processes[M].Berlin：Springer Science & Business Media，2012.
[16] OLIEHOEK F A，SPAAN M T J，VLASSIS N.Optimal and approximate Q-value functions for decentralized POMDPs[J].Journal of Artificial Intelligence Research，2008，32：289-353.
[17] 刘志飞，曹雷，赖俊，等.多智能体路径规划综述[J].计算机工程与应用，2022，58（20）：43-62.
LIU Z F，CAO L，LAI J，et al.Overview of multi-agent path finding[J].Computer Engineering and Applications，2022，58（20）：43-62.
[18] MOHANTY S，NYGREN E，LAURENT F，et al.Flatland-RL：multi-agent reinforcement learning on trains[J].arXiv：2012.05893，2020.
[19] PANOV A I，YAKOVLEV K S，SUVOROV R.Grid path planning with deep reinforcement learning：preliminary results[J].Procedia Computer Science，2018，123：347-353.
[20] MNIH V，KAVUKCUOGLU K，SILVER D，et al.Human-level control through deep reinforcement learning[J].Nature，2015，518（7540）：529-533.
[21] SARTORETTI G，KERR J，SHI Y，et al.PRIMAL：pathfinding via reinforcement and imitation multi-agent learning[J].IEEE Robotics and Automation Letters，2019，4（3）：2378-2385.
[22] MA Z，LUO Y，PAN J.Learning selective communication for multi-agent path finding[J].arXiv：2109.05413，2021.
[23] MA Z，LUO Y，MA H.Distributed heuristic multi-agent path finding with communication[C]//2021 IEEE International Conference on Robotics and Automation，2021：8699-8705.
[24] 王毅然，经小川，田涛，等.基于强化学习的多Agent路径规划方法研究[J].计算机应用与软件，2019，36（8）：165-171.
WANG Y R，JING X C，TIAN T，et al.Research on multi-agent path panning method based on reinforcement learning[J].Computer Application and Software，2019，36（8）：165-171.
[25] SKRYNNIK A，YAKOVLEVA A，DAVYDOV V，et al.Hybrid policy learning for multi-agent pathfinding[J].IEEE Access，2021，9：126034-126047.
[26] WANG B，LIU Z，LI Q，et al.Mobile robot path planning in dynamic environments through globally guided reinforcement learning[J].IEEE Robotics and Automation Letters，2020，5（4）：6932-6939.
[27] LING J，CHANDAK K，KUMAR A.Integrating knowledge compilation with reinforcement learning for routes[C]//Proceedings of the International Conference on Automated Planning and Scheduling，2021，31：542-550.
[28] ZHANG Y，QIAN Y，YAO Y，et al.Learning to cooperate：application of deep reinforcement learning for online AGV path finding[C]//Proceedings of the 19th International Conference on Autonomous Agents and Multi-
agent Systems，2020：2077-2079.
[29] 郑延斌，李波，安德宇，等.基于分层强化学习及人工势场的多Agent路径规划方法[J].计算机应用，2015，35（12）：3491-3496.
ZHENG Y B，LI B，AN D Y，et al.Multi-agent path planning method based on hierarchical reinforcement learning and artificial potential field[J].Journal of Computer Applications，2015，35（12）：3491-3496.
[30] 张靖南.基于多智能体的群体路径规划研究[D].哈尔滨：哈尔滨工程大学，2019.
ZHANG J N.Research on group path planning based on multi-agent[D].Harbin：Harbin Engineering University，2019.
[31] LUO Z Y，SARTORETTI G.Deep reinforcement learning based multi-agent pathfinding[R].2020.
[32] WAGNER G，CHOSET H.Subdimensional expansion for multirobot path planning[J].Artificial Intelligence，2015，219（2）：1-24.
[33] DE WITT C S，GUPTA T，MAKOVIICHUK D，et al.Is independent learning all you need in the StarCraft multi-agent challenge[J].arXiv：2011.09533，2020.
[34] IQBAL S，SHA F.Actor-attention-critic for multi-agent reinforcement learning[C]//Proceedings of the 36th International Conference on Machine Learning，2019：2961-2970.
[35] SCHULMAN J，WOLSKI F，DHARIWAL P，et al.Proximal policy optimization algorithms[J].arXiv：1707.06347，2017.