基于MA-PPA的露天煤矿智能巡视机器人路径规划研究

doi:10.19678/j.issn.1000-3428.0069500

摘要/Abstract

摘要：

移动机器人在复杂环境下多使用智能算法进行路径规划, 但由于传统计算机存在"储存墙"问题, 算法运行需要耗费大量的时间。针对上述问题, 提出基于忆阻器阵列与多头绒泡菌算法(MA-PPA)的露天煤矿智能巡视机器人路径规划算法。忆阻器具有"存算一体"等特性, 能够降低算法的运行时间, 多头绒泡菌算法可以自组织且高效地找到最短路径。结合两者的优点, 根据忆阻器阻值随电流变化的正反馈性, 用忆阻器阵列实现了多头绒泡菌算法在二维全局环境下的路径规划, 并在忆阻器阵列中进行多头绒泡菌算法的并行计算, 大幅降低算法的运行时间。实验结果表明, 与其他传统的生物启发算法相比, 提出的算法降低了算法的时间复杂度, 寻找到的最短路径转弯次数更少。

关键词: 忆阻器阵列, 生物启发, 存算一体, 多头绒泡菌算法, 并行计算, 路径规划, 栅格法

Abstract:

Autonomous mobile robots employ intelligent algorithms for path planning in complex environments. However, the ″memory wall″ problem in traditional computers increases the running time of the algorithms substantially. To address this problem, this study proposes path planning for intelligent inspection robots in open-pit coal mines based on a Memristor Array and Physarum Polycephalum Algorithm (MA-PPA). A memristor device can reduce the running time of an algorithm because of its ″memory and computation integration″. The Physarum polycephalum algorithm can self-organize and efficiently locate the shortest path. By leveraging the advantages of both and based on the positive feedback property of the memristor resistance varying with current, the Physarum polycephalum algorithm is implemented for path planning in a two-dimensional global environment using a memristor array. Parallel computing is applied to the Physarum polycephalum algorithm on a memristor array, which significantly reduces the running time of the algorithm. Experimental results show that compared with traditional bio-inspired algorithms, the proposed algorithm reduces time complexity and finds the shortest path with fewer turns.

Key words: Memristor Array (MA), biological inspired, memory and computation integration, Physarum Polycephalum Algorithm (PPA), parallel computing, path planning, grid method

祁永强, 胡杞澍. 基于MA-PPA的露天煤矿智能巡视机器人路径规划研究[J]. 计算机工程, 2025, 51(11): 366-376.

QI Yongqiang, HU Qishu. Research on Path Planning of Intelligent Inspection Robot in Open-pit Coal Mine Based on Memristor Array and Physarum Polycephalum Algorithm[J]. Computer Engineering, 2025, 51(11): 366-376.

https://www.ecice06.com/CN/Y2025/V51/I11/366

图/表 16

图1 忆阻器的物理模型

Fig.1 Physical model of memristor

图2 忆阻器阵列表示的单个栅格图

Fig.2 Single grid graph represented by an memristors array

图3 忆阻器阵列表示的2×2栅格图

Fig.3 2×2 grid graph represented by an memristors array

图4 忆阻器列阵结构

Fig.4 Memristor array structure

图5 忆阻器更新路径信息示意图

Fig.5 Schematic diagram of the memristor update path information

图6 MA-PPA算法流程

Fig.6 The procedure of the MA-PPA algorithm

图7 单个忆阻器模型的伏安特性曲线

Fig.7 Voltammetric characteristic curves of single memristor model

图8 阻值收敛情况对比

Fig.8 Comparison of resistance convergence

图9 电流收敛情况对比

Fig.9 Comparison of current convergence

图10 10×10地图中的最短路径

Fig.10 10 Shortest path in 10×10 map

图11 20×20地图中的最短路径

Fig.11 Shortest path in 20×20 map

图12 算法收敛速度

Fig.12 Convergence rate of algorithm

图13 几种静态地图中分别使用蚁群算法和MA-PPA算法找到的路径

Fig.13 Paths found in several static maps using ant colony algorithm and MA-PPA algorithm respectively

图14 20×20动态地图中使用MA-PPA算法找到的最短路径

Fig.14 Shortest path found in 20×20 dynamic map using MA-PPA algorithm

参考文献 25

1	杨孝新, 刘婷婷, 刘福明, 等. 露天煤矿带式输送机智能巡检机器人. 露天采矿技术, 2022, 37 (4): 48- 51.
	YANG X X , LIU T T , LIU F M , et al. Intelligent inspection robots for belt conveyors in open-pit coal mines. Opencast Mining Technology, 2022, 37 (4): 48- 51.
2	杨春雨, 张鑫. 煤矿机器人环境感知与路径规划关键技术. 煤炭学报, 2022, 47 (7): 2844- 2872.
	YANG C Y , ZHANG X . Key technologies of coal mine robots for environment perception and path planning. Journal of China Coal Society, 2022, 47 (7): 2844- 2872.
3	唐昀超, 祁少军, 朱立学, 等. 移动机器人避障运动研究. 系统仿真学报, 2024, 36 (1): 1- 26.
	TANG Y C , QI S J , ZHU L X , et al. Obstacle avoidance motion in mobile robotics. Journal of System Simulation, 2024, 36 (1): 1- 26.
4	WANG Z L , GAO F , ZHAO Y , et al. Improved A * algorithm and model predictive control-based path planning and tracking framework for hexapod robots. Industrial Robot: the International Journal of Robotics Research and Application, 2023, 50 (1): 135- 144. doi: 10.1108/IR-01-2022-0028
5	王志特, 罗丽平, 廖义奎. 改进A * 算法融合改进动态窗口法的移动机器人路径规划. 计算机工程, 2024, 50 (8): 86- 101. doi: 10.19678/j.issn.1000-3428.0068483
	WANG Z T , LUO L P , LIAO Y K . Mobile robot path planning by improved A * algorithm fused with improved dynamic window approach. Computer Engineering, 2024, 50 (8): 86- 101. doi: 10.19678/j.issn.1000-3428.0068483
6	巩慧, 倪翠, 王朋, 等. 基于Dijkstra算法的平滑路径规划方法. 北京航空航天大学学报, 2024, 50 (2): 535- 541.
	GONG H , NI C , WANG P , et al. A smooth path planning method based on Dijkstra algorithm. Journal of Beijing University of Aeronautics and Astronsutics, 2024, 50 (2): 535- 541.
7	高飞翔, 郝万君, 吴宇, 等. 改进人工势场法机器人避障路径规划研究. 计算机仿真, 2023, 40 (9): 431-436, 442.
	GAO F X , HAO W J , WU Y , et al. Research on robot obstacle avoidance path planning based on improved artificial potential field method. Computer Simulation, 2023, 40 (9): 431-436, 442.
8	ZHANG R , GUO H , ANDRIUKAITIS D , et al. Intelligent path planning by an improved RRT algorithm with dual grid map. Alexandria Engineering Journal, 2024, 88, 91- 104. doi: 10.1016/j.aej.2023.12.044
9	王宏民, 李江源, 蒋孟, 等. 基于改进哈里斯鹰优化算法的多机器人协作焊接路径规划. 机电工程技术, 2024, 53 (1): 35- 39.
	WANG H M , LI J Y , JIANG M , et al. Multi-robot cooperative welding path planning based on improved Harris eagle optimization algorithm. Mechanical & Electrical Engineering Technology, 2024, 53 (1): 35- 39.
10	TERO A , TAKAGI S , SAIGUSA T , et al. Rules for biologically inspired adaptive network design. Science, 2010, 327 (5964): 439- 442. doi: 10.1126/science.1177894
11	汪丹. 多头绒泡菌仿生算法优化及其应用[D]. 重庆: 西南大学, 2021.
	WANG D. Optimization of physarum polycephalum bionic algorithm and its application[D]. Chongqing: Southwest University, 2021. (in Chinese)
12	ZHANG Y , YANG Z Q . Application of an improved physarum polycephalum algorithm on QoS routing problem. International Journal of Wireless and Mobile Computing, 2021, 21 (4): 323. doi: 10.1504/IJWMC.2021.121613
13	ZHANG Y , YANG Z Q , QI X . An improved physarum polycephalum algorithm for the Steiner tree problem. International Journal of Bio-Inspired Computation, 2022, 19 (1): 40. doi: 10.1504/IJBIC.2022.120753
14	LUO Y D , GUO J W , LAO Z P , et al. Swarm robot exploration strategy for path formation tasks inspired by physarum polycephalum. Complexity, 2021, 2021 (1): 6698421. doi: 10.1155/2021/6698421
15	CHUA L . Memristor the missing circuit element. IEEE Transactions on Circuit Theory, 1971, 18 (5): 507- 519. doi: 10.1109/TCT.1971.1083337
16	STRUKOV D B , SNIDER G S , STEWART D R , et al. The missing memristor found. Nature, 2008, 453 (7191): 80- 83. doi: 10.1038/nature06932
17	YU H , NI L , HUANG H . Distributed in-memory computing on binary memristor-crossbar for machine learning. Berlin, Germany: Springer, 2017.
18	PERSHIN Y V , DI VENTRA M . Solving mazes with memristors: a massively parallel approach. Physical Review E, 2011, 84 (4): 046703. doi: 10.1103/PhysRevE.84.046703
19	AWAD A , PANG W , LUSSEAU D , et al. A survey on physarum polycephalum intelligent foraging behaviour and bio-inspired applications. Artificial Intelligence Review, 2023, 56 (1): 1- 26. doi: 10.1007/s10462-021-10112-1
20	YONEOKA E , TAKAMATSU A . Relation between learning process and morphology of transport tube network in plasmodium of physarum polycephalum. Front Cell Dev Biol, 2023, 11, 1249165. doi: 10.3389/fcell.2023.1249165
21	WILKINSON R , KOZIOL M , ALIM K , et al. Flow modes provide a quantification of physarum network peristalsis. Fungal Ecology, 2023, 65, 101283. doi: 10.1016/j.funeco.2023.101283
22	邓权芯. 基于忆阻网络的典型群体智能算法研究[D]. 成都: 电子科技大学, 2021.
	DENG Q X. Research on typical swarm intelligence algorithm based on memristor network[D]. Chengdu: University of Electronic Science and Technology of China, 2021. (in Chinese)
23	吴雨横. 多头绒泡菌智能行为模型研究及其应用[D]. 重庆: 西南大学, 2013.
	WU Y H. Research and application of physarum polycephalum's intelligent behavior model[D]. Chongqing: Southwest University, 2013. (in Chinese)
24	LI K , TORRES C E , THOMAS K , et al. Slime mold inspired routing protocols for wireless sensor networks. Swarm Intelligence, 2011, 5 (3): 183- 223.
25	XIONG L , ZHANG X G , CHEN Y . Experimental verification of volt-ampere characteristic curve for a memristor-based chaotic circuit. Circuit World, 2019, 46 (1): 13- 24. doi: 10.1108/CW-04-2019-0035

[1]	潘顺杰, 于俊洋, 王龙葛, 李涵, 翟锐. 基于RDD重用度的Spark自适应缓存优化策略[J]. 计算机工程, 2025, 51(7): 190-198.
[2]	张文帅, 李会民, 李京, 潘必才. 一种集成于超算作业调度系统应用的并行参数优化方法[J]. 计算机工程, 2025, 51(7): 59-67.
[3]	张博强, 陈新明, 冯天培, 吴兰, 刘宁宁, 孙朋. 基于混合A^*和修正RS曲线融合的路径规划[J]. 计算机工程, 2025, 51(4): 373-382.
[4]	周青, 潘凡安, 陈文冲, 江波. 面向工业互联网平台的物流服务选择性众包与路径规划研究[J]. 计算机工程, 2025, 51(4): 360-372.
[5]	李淑怡, 阳波, 陈灵, 沈玲, 唐文胜. 自适应奖励函数的PPO曲面覆盖方法[J]. 计算机工程, 2025, 51(3): 86-94.
[6]	张国胜, 李彩虹, 张耀玉, 周瑞红, 梁振英. 基于改进人工势场法的机器人局部路径规划[J]. 计算机工程, 2025, 51(1): 88-97.
[7]	陈浩, 陈珺, 刘飞. 基于自主探索的移动机器人路径规划研究[J]. 计算机工程, 2025, 51(1): 60-70.
[8]	杨太龙, 赵红朋, 张磊. 基于国产异构平台的奇异值分解法[J]. 计算机工程, 2024, 50(9): 216-225.
[9]	张磊, 赵光岳, 肖超恩, 王建新. Falcon后量子算法的密钥树生成部件GPU并行优化设计与实现[J]. 计算机工程, 2024, 50(9): 208-215.
[10]	王志特, 罗丽平, 廖义奎. 改进A^*算法融合改进动态窗口法的移动机器人路径规划[J]. 计算机工程, 2024, 50(8): 86-101.
[11]	雷斗威, 何德彪, 罗敏, 彭聪. 基于AVX512的格密码高速并行实现[J]. 计算机工程, 2024, 50(2): 15-24.
[12]	王其涵, 庞建民, 岳峰, 祝迪, 沈莉, 肖谦. 面向申威架构的KNN并行算法实现与优化[J]. 计算机工程, 2023, 49(5): 286-294.
[13]	夏立斌, 刘晓宇, 姜晓巍, 孙功星. 基于分布式数据集的并行计算框架内存优化方法[J]. 计算机工程, 2023, 49(4): 43-51.
[14]	刘国名, 李彩虹, 李永迪, 张国胜, 张耀玉, 高腾腾. 基于改进PPO算法的机器人局部路径规划[J]. 计算机工程, 2023, 49(2): 119-126,135.
[15]	李奇儒, 耿霞. 基于改进DQN算法的机器人路径规划[J]. 计算机工程, 2023, 49(12): 111-120.

选择文件类型/文献管理软件名称

选择包含的内容