改进A*算法的机器人能耗最优路径规划方法

doi:10.12305/j.issn.1001-506X.2023.02.23

摘要/Abstract

摘要：

为了降低移动机器人在运动过程中的能耗, 提高在能源补给有限时的任务执行率, 提出了一种改进A^*算法的机器人能耗最优路径规划方法。首先, 根据四轮差速驱动移动机器人的运动学约束, 建立了其运动的能耗模型。然后, 根据起始状态和目标状态约束求解生成运动基元, 采用能耗模型计算运动基元的能耗值, 构建了能耗运动基元集。其次, 基于传统A^*算法, 改进提出了一种能耗最优路径规划方法, 该方法在规划进程中以能耗运动基元集中定义的节点之间的连接关系进行节点扩展, 而以能耗值作为节点之间的通行成本, 从而保证获得一条全局能耗最优路径。最后, 离线地图仿真测试和机器人实验结果表明所生成的路径总能耗可降低约28.24%, 从而验证了算法的有效性。

关键词: 路径规划, 改进A^*算法, 能耗模型, 能耗运动基元

Abstract:

In order to reduce the energy consumption during the robot movements and increase the task execution rate with limit energy supply, an energy-efficient path planning method is proposed based on improved A^* algorithm for mobile robots. Firstly, the energy consumption model of four-wheel differential drive robot is established according to its kinematic constraints. Secondly, the motion primitive of the robot is solved by given the start and goal states. The energy consumption motion primitive set is constructed after using the energy consumption model to calculate the cost of each motion primitive. Thirdly, the energy efficient path planning method is proposed based on the traditional A^* algorithm. In the planning process, the nodes are expanded using the defined connection relationship in energy consumption motion primitive set and the energy consumption is treated as the cost between them, which guarantees to find a global energy efficient path. Finally, the offline map simulation test and robotic experiment results show that the energy cost of the generated path is reduced by about 28.24%. Therefore, the effectiveness of the algorithm is verified.

Key words: path planning, improved A^* algorithm, energy consumption model, energy consumption motion primitive

中图分类号:

TP242.3

张浩杰, 张玉东, 梁荣敏, 杨甜甜. 改进A^*算法的机器人能耗最优路径规划方法[J]. 系统工程与电子技术, 2023, 45(2): 513-520.

Haojie ZHANG, Yudong ZHANG, Rongmin LIANG, Tiantian YANG. Energy-efficient path planning method for robots based on improved A^* algorithm[J]. Systems Engineering and Electronics, 2023, 45(2): 513-520.

图/表 12

图1

图2

图3

图4

表1

图5

图6

表2

图7

图8

图9

表3

参考文献 35

1	SALONI W. The role of autonomous unmanned ground vehicle technologies in defense application[R]. New York: Aerospace & Defense Technology Magazine, 2020.
2	LEONARDB,TOMA,HENNINGS.State of the art-automated micro-vehicles for urban logistics[J].International Federation of Automatic Control,2019,52(13):2455-2462.
3	SANTOS L C, SANTOS F N, PIRES E J S, et al. Path planning for ground robots in agriculture: a short review[C]//Proc. of the IEEE International Conference on Autonomous Robot Systems and Competitions, 2020: 61-66.
4	ALGIRDASV V,OLEGASC,VADIMV.Motion and energy efficiency parameters of the unmanned ground vehicle[J].Solid State Phenomena,2015,220,934-939.
5	DIK C,LIUZ Q,WANW H,et al.Geospatial technologies for Chang'e-3 and Chang'e-4 lunar rover missions[J].Geo-spatial Information Science,2020,23(1):87-97. doi: 10.1080/10095020.2020.1718002
6	ZHANGZ W,WUL H,ZHANGW Q,et al.Energy-efficient path planning for a single-load automated guided vehicle in a manufacturing workshop[J].Computers & Industrial Engineering,2021,158,107397.
7	RAPPAPORT M. Energy-aware mobile robot exploration with adaptive decision thresholds[C]//Proc. of the 47th International Symposium on Robotics, 2016: 236-243.
8	VALIAOTSE,SELLR.Energy efficiency profiles for unmanned ground vehicles[J].Proceedings of the Estonian Academy of Sciences,2019,68(1):55-65. doi: 10.3176/proc.2019.1.04
9	SHARIF A, LAHIRU H M, HERATH S, et al. Energy efficient path planning of hybrid fly-drive robot using A^* algorithm[C]//Proc. of the 15th International Conference on Informatics in Control, Automation and Robotics, 2018: 201-210.
10	HILL R B. Design of high-speed robots with drastically reduced energy consumption[D]. France: Centrale Nontes, 2019.
11	ROWEN C,ROSSR S.Optimal grid-free path planning across arbitrarily contoured terrain with anisotropic friction and gravity effects[J].IEEE Trans.on Robotics and Automation,1990,6(5):540-553. doi: 10.1109/70.62043
12	ZHANGH J,ZHANGY D,YANGT T.A survey of energy-efficient motion planning for wheeled mobile robots[J].Industrial Robot: the International Journal of Robotics Research and Application,2020,4(47):607-621.
13	SUNZ,REIFJ H.On finding energy-minimizing paths on terrains[J].IEEE Trans.on Robotics,2005,21(1):102-114. doi: 10.1109/TRO.2004.837232
14	SAAD M, SALAMEH A I, ABDALLAH S. Energy-efficient shortest path planning on uneven terrains: a composite routing metric approach[C]//Proc. of the 19th International Symposium on Signal Processing and Information Technology, 2019.
15	SAADM,SALAMEHA I,ABDALLAHS,et al.A compo-site metric routing approach for energy-efficient shortest path planning on natural terrains[J].Applied Sciences,2021,11(15):6939. doi: 10.3390/app11156939
16	殷建军,董文龙,梁利华,等.复杂环境下农业机器人路径规划优化方法[J].农业机械学报,2019,50(5):17-22.
	YINJ J,DONGW L,LIANGL H,et al.Optimization method of agricultural robot path planning in complex environment[J].Transactions of the Chinese Society for Agricultural Machinery,2019,50(5):17-22.
17	ZAKHAROV K, SAVELIEV A, SIVCHENKO O. Energy-efficient path planning algorithm on three-dimensional large-scale terrain maps for mobile robots[C]//Proc. of the 5th International Conference on Interactive Collaborative Robotics, 2020: 319-330.
18	ZHANGZ W,WUL H,ZHANGW Q,et al.Energy-efficient path planning for a single-load automated guided vehicle in a manufacturing workshop[J].Computers & Industrial Engineering,2021,158,107397.
19	ZHANGX L,HUANGY,RONGY M,et al.Optimal trajectory planning for wheeled mobile robots under localization uncertainty and energy efficiency constraints[J].Sensors,2021,21(2):335. doi: 10.3390/s21020335
20	SANGEETHAV,KRISHANKUMARR,RAVICHANDRANK S,et al.Energy-efficient green ant colony optimization for path planning in dynamic 3D environments[J].Soft Computing,2021,25,4749-4769. doi: 10.1007/s00500-020-05483-6
21	SINGH V, BARAI R K, MANDAL P. Real-time heuristic search based minimum energy path planning of wheeled mobile robot[C]//Proc. of the Conference on Advances in Robotics, 2015: 171-177.
22	HAUSLERA J,SACCONA,AGUIARA P,et al.Energy-optimal motion planning for multiple robotic vehicles with collision avoidance[J].IEEE Trans.on Control Systems Technology,2016,24(3):867-883. doi: 10.1109/TCST.2015.2475399
23	孙鹏耀,黄炎焱,潘尧.基于改进势场法的移动机器人路径规划[J].兵工学报,2020,41(10):2106-2121. doi: 10.3969/j.issn.1000-1093.2020.10.021
	SUNP Y,HUANGY Y,PANY.Path planning of mobile robots based on improved potential field algorithm[J].Acta Armamentarii,2020,41(10):2106-2121. doi: 10.3969/j.issn.1000-1093.2020.10.021
24	SHINJ,KWAKD,KWAKK.Model predictive path planning for an autonomous ground vehicle in rough terrain[J].International Journal of Control, Automation and Systems,2021,19,2224-2237. doi: 10.1007/s12555-020-0267-2
25	GUPTAN,ORDONEZC,COLLINSE G.Dynamically feasible, energy efficient motion planning for skid-steered vehicles[J].Autonomous Robots,2017,41(2):453-471. doi: 10.1007/s10514-016-9550-8
26	JARAMILLO-MORALESM F,DOGRUS,GOMEZ-MENDOZAJ B,et al.Energy estimation for differential drive mobile robots on straight and rotational trajectories[J].International Journal of Advanced Robotic Systems,2020,17(2):1729881420909654.
27	XIEL,HENKELC,STOLK,et al.Power-minimization and energy-reduction autonomous navigation of an omnidirectional mecanum robot via the dynamic window approach local trajectory planning[J].International Journal of Advanced Robotic Systems,2018,15(1):1729881418754563.
28	VISCAM,POWELLR,GAOY,et al.Deep meta-learning energy-aware path planner for unmanned ground vehicles in unknown terrains[J].IEEE Access,2022,10,30055-30068. doi: 10.1109/ACCESS.2022.3155161
29	AJANOVICZ,STOLZM,HORNM.Energy-efficient driving in dynamic environment: global optimal MPC-like motion planning framework[M].Berlin:Springer,2018.
30	张浩杰,苏治宝,HERNANDEZD E,等.移动机器人低能耗最优路径规划方法[J].农业机械学报,2018,49(9):19-26.
	ZHANGH J,SUZ B,HERNANDEZD E,et al.Energy optimal path planning for mobile robots based on improved AD^* algorithm[J].Transactions of the Chinese Society for Agricultural Machinery,2018,49(9):19-26.
31	CSERVENAKA.Simulation and modeling of a DC motor used in a mobile robot[J].Academic Journal of Manufacturing Engineering,2020,18(4):183-190.
32	高德欣,程捷,白剑飞.最小二乘法在电机测试分析中的应用[J].微电机,2017,50(3):9-13.
	GAOD X,CHENGJ,BAIJ F.Application of least square in test and analysis of motor[J].Micromotors,2017,50(3):9-13.
33	PIVTORAIKO M, KELLY A. Kinodynamic motion planning with state lattice motion primitives[C]//Proc. of the IEEE/RSJ International Conference on Intelligent Robots and Systems, 2011: 2172-2179.
34	GANGANATHN,CHENGC T,ChiK T.A constraint-aware heuristic path planner for finding energy-efficient paths on uneven terrains[J].IEEE Trans.on Industrial Informatics,2015,11(3):601-611. doi: 10.1109/TII.2015.2413355
35	ZHANG H J, BUTZKE J, LIKHACHEV M. Combining global and local planning with guarantees on completeness[C]//Proc. of the IEEE International Conference on Robotics and Automation, 2012: 4500-4506.

参数名称	数值
车轮半径r/m	0.16
轮距L/m	0.8
电机反电动势系数K_b/(V/(r·min^-1))	0.023
电机电枢电阻R_a/Ω	0.71
电机减速比g	38.3
电池电压U_s/V	24
单个运动基元运行总时间T/s	1
栅格分辨率R_e/m	0.1
权重因子e/J	1 000

地图大小	算法种类	规划时间/s	路径长度/m	路径能耗/J
1 000×1 000	本文方法	1.69	146.22	138 626
	A^*算法	2.69	145.23	194 510
	ECA^*算法	2.15	148.27	164 842
1 500×1 500	本文方法	3.44	221.06	208 184
	A^*算法	4.68	219.69	289 588
	ECA^*算法	3.97	225.79	239 741
2 000×2 000	本文方法	4.22	293.64	275 714
	A^*算法	7.29	292.08	382 259
	ECA^*算法	5.64	296.15	317 325

算法种类	路径长度/m	路径能耗/J
本文方法	51.8	48 831
A^*算法	41.2	54 452

[1]	任智, 张栋, 唐硕. 基于强化学习的改进三维A^*算法在线航迹规划[J]. 系统工程与电子技术, 2023, 45(1): 193-201.
[2]	冯豪博, 胡桥, 赵振轶. 基于精英族系遗传算法的AUV集群路径规划[J]. 系统工程与电子技术, 2022, 44(7): 2251-2262.
[3]	尹洋, 杨全顺, 王征, 刘洋. 通信距离约束下的无人船集群覆盖搜索方法[J]. 系统工程与电子技术, 2022, 44(12): 3821-3828.
[4]	杨清清, 高盈盈, 郭玙, 夏博远, 杨克巍. 基于深度强化学习的海战场目标搜寻路径规划[J]. 系统工程与电子技术, 2022, 44(11): 3486-3495.
[5]	马威强, 高永琪, 赵苗. 基于全局最优和差分变异的头脑风暴优化算法[J]. 系统工程与电子技术, 2022, 44(1): 270-278.
[6]	焦志强, 张杰勇, 姚佩阳, 王勋, 何宜超. 基于分层结构的C4ISR服务部署分布式演化方法[J]. 系统工程与电子技术, 2021, 43(6): 1572-1585.
[7]	王文明, 杜佳璐. 基于正六边形栅格JPS算法的智能体路径规划[J]. 系统工程与电子技术, 2021, 43(12): 3635-3642.
[8]	李亚南, 黄海滨, 陈亮名, 庄宇飞, 王晓丽. 变化海流环境下AUV能量最优三维路径规划[J]. 系统工程与电子技术, 2021, 43(12): 3667-3674.
[9]	李文刚, 汪流江, 方德翔, 李玉玮, 黄郡. 联合A^*与动态窗口法的路径规划算法[J]. 系统工程与电子技术, 2021, 43(12): 3694-3702.
[10]	陈岱岱, 李玩幽. 带拖线阵的水面无人艇局部路径规划算法[J]. 系统工程与电子技术, 2020, 42(9): 1988-1994.
[11]	张泉先, 曾斌, 李厚朴. 海况影响下的分布式海战补给路径规划方法[J]. 系统工程与电子技术, 2020, 42(10): 2312-2319.
[12]	杨秀霞, 曹唯一, 张毅. 时间和角度约束下的双圆弧路径规划[J]. 系统工程与电子技术, 2019, 41(8): 1835-1843.
[13]	胡腾, 刘占军, 刘洋, 夏帅帅, 陈前斌. 多无人机3D侦察路径规划[J]. 系统工程与电子技术, 2019, 41(7): 1551-1559.
[14]	高春庆, 寇英信, 李战武, 徐安, 李游, 常一哲. 小型无人机协同覆盖侦察路径规划[J]. 系统工程与电子技术, 2019, 41(6): 1294-1299.
[15]	王瑛, 郑煜坤, 姚頔, 李正欣, 李超. 危险天气下改航路径网络规划[J]. 系统工程与电子技术, 2019, 41(6): 1309-1315.