未知环境下基于深度序列蒙特卡罗树搜索的信源导航方法

doi:10.12263/DZXB.20211252

电子学报 ›› 2022, Vol. 50 ›› Issue (7): 1744-1752.DOI: 10.12263/DZXB.20211252

未知环境下基于深度序列蒙特卡罗树搜索的信源导航方法

段世红¹^,², 何昊¹^,², 徐诚¹^,², 殷楠¹, 王然¹^,²

^1.北京科技大学计算机与通信工程学院，北京 100083
^2.北京科技大学顺德研究生院，广东佛山 528399

收稿日期:2021-09-13 修回日期:2021-12-28 出版日期:2022-07-25
- 作者简介:
- 段世红女，1973年生，山西太原人.北京科技大学副教授.研究方向为多智能体系统、嵌入式计算与无线定位、数值优化与分布式计算.
  段世红女，1973年生，山西太原人. 北京科技大学副教授. 研究方向为多智能体系统、嵌入式计算与无线定位、数值优化与分布式计算.
  何昊男，1997年生，湖南永州人. 研究方向为多智能体系统、无线定位.
  徐诚男，1988年生，辽宁开原人. 北京科技大学副教授. 研究方向为群体智能与协同计算、多智能体系统与分布式安全.E-mail: xucheng@ustb.edu.cn
  殷楠女，1996年生，山西忻州人.研究方向为多智能体系统、无线定位.
  殷楠女，1996年生，山西忻州人. 研究方向为多智能体系统、无线定位.
  王然女，1991年生，北京人.主要研究方向为群体智能与协同计算、多智能体系统与分布式安全.
  王然女，1991年生，北京人. 主要研究方向为群体智能与协同计算、多智能体系统与分布式安全.
- 基金资助:
- 国家自然科学基金 (62101029); 博士后创新人才支持计划 (BX20190033); 广东省基础与应用基础研究基金联合基金 (2019A1515110325); 中国博士后基金面上项目 (2020M670135); 北京科技大学顺德研究生院博士后科研经费 (2020BH001); 中央高校基本科研业务费 (06500127)

DS-MCTS: A Deep Sequential Monte-Carlo Tree Search Method for Source Navigation in Unknown Environments

DUAN Shi-hong¹^,², HE Hao¹^,², XU Cheng¹^,², YIN Nan¹, WANG Ran¹^,²

^1.School of Computer and Communication Engineering, University of Science and Technology Beijing, Beijing 100083, China
^2.Shunde Graduate School, University of Science and Technology Beijing, Foshan, Guangdong 528399, China

Received:2021-09-13 Revised:2021-12-28 Online:2022-07-25 Published:2022-07-30
- Supported by:
- National Natural Science Foundation of China (62101029); Post doctoral Innovative Talents Support Program (BX20190033); Joint Fund of Basic and Applied Basic Research Foundation of Guangdong Province (2019A1515110325); Post-doctoral Foundation of China (2020M670135); Postdoctoral Research Fund of Shunde Innovation School, University of Science and Technology Beijing (2020BH001); Fundamental Research Funds for the Central Universities (06500127)

摘要/Abstract

摘要：

信源导航在应急救援、工业巡检及其他危险作业中具有重要应用意义.在实际应用中，环境的状态信息往往是难以完全观测的，即部分可观测环境.如何利用观测到的部分环境信息做出实时决策，并基于历史序列信息对系统未来状态进行有效的预测，成为信源导航相关研究所面临的挑战性问题.本文提出一种基于深度序列蒙特卡洛树搜索（Deep Sequential Monte-Carlo Tree Search，DS-MCTS）的信源导航算法和系统框架，基于序列动作预测（Sequential Action Prediction，SAP）网络为MCTS决策提供先验知识，构建奖励分配预测（Reward Allocation Prediction，RAP）网络提高奖励分配精度，最终实现系统的最优化决策.仿真实验表明，DS-MCTS方法提供了一种端到端的信源导航解决方案，可以实现智能体动作的有效预测，实现高效、鲁棒的路径规划.

关键词: 信源导航, 蒙特卡洛树搜索, 序贯决策, 路径规划, 深度强化学习

Abstract:

Source navigation has important application significance in emergency rescue, industrial patrol, and other dangerous operations. In practical applications, it is often difficult to fully observe the state information of the environment, that is, a partially observable environment. Making real-time decisions using part of the observed environmental information and effectively predicting the system's future state based on the historical sequence information have become a challenge faced by research institutes related to source navigation. This paper proposes a source navigation algorithm and system framework based on deep sequential Monte-Carlo tree search(DS-MCTS). Prior knowledge is provided to MCTS decision-making based on a sequential action prediction(SAP) network. A reward allocation prediction(RAP) network is built to improve the accuracy of reward distribution and finally realize the system's optimal decision-making. The simulation results show that the DS-MCTS method provides an end-to-end source navigation solution, which can effectively predict agents' actions and achieve efficient and robust path planning.

Key words: source navigation, Monte-Carlo tree search, sequential decision-making, path planning, deep reinforcement learning

中图分类号:

TP391

段世红, 何昊, 徐诚, 殷楠, 王然. 未知环境下基于深度序列蒙特卡罗树搜索的信源导航方法[J]. 电子学报, 2022, 50(7): 1744-1752.

DUAN Shi-hong, HE Hao, XU Cheng, YIN Nan, WANG Ran. DS-MCTS: A Deep Sequential Monte-Carlo Tree Search Method for Source Navigation in Unknown Environments[J]. Acta Electronica Sinica, 2022, 50(7): 1744-1752.

图/表 12

图1 集成信源导航框架图

图2 蒙特卡洛树搜索示意图

图3 SAP网络结构图

图4 RAP网络结构图

表1 SAP网络结构

网络层数	神经元个数	激活函数
LSTM	72	—
LSTM	100	—
Full connected	8	SoftMax

表2 RAP网络结构

网络层数	神经元个数	激活函数
Full connected	18	tanh
Full connected	10	tanh
Full connected	1	—

图5 仿真实验信源导航路径图(a) 初始位置[3,15] (b) 初始位置[18,14]

图6 RAP网络训练损失图

图7 SAP网络训练损失图

图8 迭代步数图

图9 不同方法对比实验步数

表3 不同方法信源导航结果比较

方法	寻源成功率/%	平均步数	时间/s
GD^[32]	48	115	1.2
MCTS-GP^[33]	99	29	9.5
DS-MCTS	100	18	0.9

参考文献 34

1	路永鑫, 魏云冰, 赵启承, 等. 基于层次分析法和改进A*算法的电力应急机器人路径规划[J]. 电力系统保护与控制, 2021, 49(9): 82-89.
	LUY X, WEIY B, ZHAOQ C, et al. Path planning of a power emergency robot based on an analytic hierarchy process and improved A* algorithm[J]. Power System Protection and Control, 2021, 49(9): 82-89. (in Chinese)
2	MANDALS, SAHAD, MAHANTIA. A heuristic search for generalized cellular network planning[C]//2002 IEEE International Conference on Personal Wireless Communications. New Delhi, India: IEEE, 2002: 105-109.
3	LINQ Z, LIUS B, ZHUQ L, et al. Particle swarm optimization with a balanceable fitness estimation for many-objective optimization problems[J]. IEEE Transactions on Evolutionary Computation, 2018, 22(1): 32-46.
4	ROJAS SANTIAGOM, MUTHUSWAMYS, HULETTM. An ACO algorithm for scheduling a flow shop with setup times[J]. International Journal of Industrial and Systems Engineering, 2020, 36(1): 98-109.
5	LIJ, SHUZ. Research on path planning based on improved D* lite genetic algorithm[J]. Machine Tool & Hydraulics, 2019, 47(11): 39-42.
6	YANX S, LIP P, TANGK, et al. Clonal selection based intelligent parameter inversion algorithm for prestack seismic data[J]. Information Sciences, 2020, 517: 86-99.
7	WANGH Q, HUY Y, LIAOW D, et al. Path planning algorithm based on improved artificial bee colony algorithm[J]. Control Engineering, 2016, 23(95): 1407-1411.
8	VITERBIA J. CDMA: Principles of Spread Spectrum Communication[M]. Wokingham: Addison-Wesley, 1995.
9	SKOLNIKM I. Radar Handbook[M]. 3rd ed. New York: McGraw-Hill, 2008.
10	XIEG, SHANGGUANA Q, FEIR, et al. Motion trajectory prediction based on a CNN-LSTM sequential model[J].Science China Information Sciences, 2020, 63(11): 1-21.
11	许凯波, 鲁海燕, 黄洋, 等. 基于双层蚁群算法和动态环境的机器人路径规划方法[J]. 电子学报, 2019, 47(10): 2166-2176.
	XUK B, LUH Y, HUANGY, et al. Robot path planning based on double-layer ant colony optimization algorithm and dynamic environment[J]. Acta Electronica Sinica, 2019, 47(10): 2166-2176. (in Chinese)
12	WENT, YANGD C, LIUW F, et al. A novel integrated path planning algorithm for warehouse AGVs[J]. Chinese Journal of Electronics, 2021, 30(2): 331-338.
13	陈劲峰, 黄卫华, 章政, 等. 动态环境下基于改进人工势场法的路径规划算法[J]. 组合机床与自动化加工技术, 2020(12): 6-9, 14.
	CHENJ F, HUANGW H, ZHANGZ, et al. Path planning algorithm based on improved artificial potential field method in dynamic environment[J]. Modular Machine Tool & Automatic Manufacturing Technique, 2020(12): 6-9, 14. (in Chinese)
14	TRAUTMANP, KRAUSEA. Unfreezing the robot: Navigation in dense, interacting crowds[C]//2010 IEEE/RSJ International Conference on Intelligent Robots and Systems. Taipei, China: IEEE, 2010: 797-803.
15	HELBINGD, MOLNÁRP. Social force model for pedestrian dynamics[J]. Physical Review. E, Statistical Physics, Plasmas, Fluids, and Related Interdisciplinary Topics, 1995, 51(5): 4282-4286.
16	SUTTONR S, BartoA G. Reinforcement learning: An introduction[M]. MIT press, 2018.
17	PUTERMANM L. Markov Decision Processes: Discrete Stochastic Dynamic Programming[M]. Hoboken: John Wiley & Sons, 1994.
18	PENGP, ZHUF, LIUQ, et al. Achieving safe deep reinforcement learning via environment comprehension mechanism[J]. Chinese Journal of Electronics, 2021, 30(6): 1049-1058.
19	VODOPIVECT, SAMOTHRAKISS, STERB. On Monte Carlo tree search and reinforcement learning[J]. Journal of Artificial Intelligence Research, 2017, 60: 881-936.
20	SILVERD, HUANGA, MADDISONC J, et al. Mastering the game of Go with deep neural networks and tree search[J]. Nature, 2016, 529(7587): 484-489.
21	KEARNSM, MANSOURY, NGA Y. A sparse sampling algorithm for near-optimal planning in large Markov decision processes[J].Machine Learning, 2002, 49(2/3): 193-208.
22	SILVERD, SCHRITTWIESERJ, SIMONYANK, et al. Mastering the game of Go without human knowledge[J]. Nature, 2017, 550(7676): 354-359.
23	LILLICRAPT P, HUNTJ J, PRITZELA, et al. Continuous control with deep reinforcement learning[J]. arXiv preprint, arXiv:, 2015.
24	黄志清, 曲志伟, 张吉, 等. 基于深度强化学习的端到端无人驾驶决策[J]. 电子学报, 2020, 48(9): 1711-1719.
	HUANGZ Q, QUZ W, ZHANGJ, et al. End-to-end autonomous driving decision based on deep reinforcement learning[J]. Acta Electronica Sinica, 2020, 48(9): 1711-1719. (in Chinese)
25	CHENX, LIZ, WANGK, et al. MDP-based network selection with reward optimization in HetNets[J]. Chinese Journal of Electronics, 2018, 27(1): 183-190.
26	COULOMR. Efficient selectivity and backup operators in Monte-Carlo tree search[C]//International Conference on Computers and Games. Turin, Italy: Springer, 2007: 72-83.
27	CHASLOTG, BAKKESS, SZITAI, et al. Monte-Carlo tree search: A new framework for game AI[C]//Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment. Palo Alto, California, USA: The AAAI Press. 2008, 4(1): 216-217.
28	BROWNEC B, POWLEYE, WHITEHOUSED, et al. A survey of monte carlo tree search methods[J]. IEEE Transactions on Computational Intelligence and AI in games, 2012, 4(1): 1-43.
29	KRONBERGERG, BRAUNER. Bandit-based Monte-Carlo planning for the single-machine total weighted tardiness scheduling problem[C]//International Conference on Computer Aided Systems Theory. Las Palmas de Gran Canaria, Spain: Springer, 2007: 837-844.
30	ZHANGJ J, LIUH Y, CHANGQ, et al. Recurrent neural network for motion trajectory prediction in human-robot collaborative assembly[J]. CIRP Annals, 2020, 69(1): 9-12.
31	徐诚, 何昊, 段世红, 等. 一种基于深度蒙特卡洛树搜索的信源导航方法及装置: 202110316103.9[P].2021.
32	DENKERA, İŞERIM C. Design and implementation of a semi-autonomous mobile search and rescue robot: SALVOR[C]//2017 International Artificial Intelligence and Data Processing Symposium (IDAP). Malatya, Turkey: IEEE, 2017: 1-6.
33	方朋朋, 杨家富, 施杨洋, 等. 基于梯度下降法和改进人工势场法的无人车避障方法[J]. 制造业自动化, 2018, 40(11):81-84.
	FANGP P, YANGJ F, SHIY Y, et al. Gradient descent method and improved artificial potential field method for obstacle avoidance of unmanned vehicle[J]. Manufacturing Automation, 2018, 40(11): 81-84. (in Chinese)
34	VISERASA, SHUTIND, MERINOL. Robotic active information gathering for spatial field reconstruction with rapidly-exploring random trees and online learning of Gaussian processes[J]. Sensors(Basel, Switzerland), 2019, 19(5): 1016.

[1]	宣志玮, 毛剑琳, 张凯翔. CBS框架下面向复杂地图的低拓展度A*算法[J]. 电子学报, 2022, 50(8): 1943-1950.
[2]	饶宁, 许华, 蒋磊, 宋佰霖, 史蕴豪. 基于多智能体深度强化学习的分布式协同干扰功率分配算法[J]. 电子学报, 2022, 50(6): 1319-1330.
[3]	宋佰霖, 许华, 齐子森, 饶宁, 彭翔. 一种基于深度强化学习的协同通信干扰决策算法[J]. 电子学报, 2022, 50(6): 1301-1309.
[4]	易令, 李泽平. 基于深度强化学习的码率自适应算法研究[J]. 电子学报, 2022, 50(5): 1192-1200.
[5]	张涛, 张文涛, 代凌, 陈婧怡, 王丽, 魏倩茹. 基于序贯博弈多智能体强化学习的综合模块化航空电子系统重构方法[J]. 电子学报, 2022, 50(4): 954-966.
[6]	蒋林, 方东君, 周和文, 黄惠保. 基于射线模型的改进全局路径规划算法[J]. 电子学报, 2022, 50(3): 548-556.
[7]	肖硕, 黄珍珍, 张国鹏, 杨树松, 江海峰, 李天旭. 基于SAC的多智能体深度强化学习算法[J]. 电子学报, 2021, 49(9): 1675-1681.
[8]	韩冲, 王俊丽, 吴雨茜, 张超波. 基于神经进化的深度学习模型研究综述[J]. 电子学报, 2021, 49(2): 372-379.
[9]	刘润滋, 吴伟华, 张文柱, 周笛, 张琰. 基于图学习的密集空间网络传输资源调度方法[J]. 电子学报, 2021, 49(11): 2133-2137.
[10]	马慧, 汤庸, 何怀文. 主存高效的公交网络路径规划索引[J]. 电子学报, 2021, 49(11): 2273-2278.
[11]	陈思光, 陈佳民, 赵传信. 基于深度强化学习的云边协同计算迁移研究[J]. 电子学报, 2021, 49(1): 157-166.
[12]	黄志清, 曲志伟, 张吉, 张严心, 田锐. 基于深度强化学习的端到端无人驾驶决策[J]. 电子学报, 2020, 48(9): 1711-1719.
[13]	王乐乐, 眭泽智, 蒲志强, 刘振, 易建强. 一种改进RRT的多机器人编队路径规划算法[J]. 电子学报, 2020, 48(11): 2138-2145.
[14]	王秋萍, 王彦军, 戴芳. 多策略集成的樽海鞘群算法的机器人路径规划[J]. 电子学报, 2020, 48(11): 2101-2113.
[15]	许凯波, 鲁海燕, 黄洋, 胡士娟. 基于双层蚁群算法和动态环境的机器人路径规划方法[J]. 电子学报, 2019, 47(10): 2166-2176.

未知环境下基于深度序列蒙特卡罗树搜索的信源导航方法

DS-MCTS: A Deep Sequential Monte-Carlo Tree Search Method for Source Navigation in Unknown Environments

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 12

参考文献 34

相关文章 15

编辑推荐

Metrics