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

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

Abstract

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

CLC Number:

TP242.3

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.

Figures/Tables 12

Fig.1

Fig.2

Fig.3

Fig.4

Table 1

Fig.5

Fig.6

Table 2

Fig.7

Fig.8

Fig.9

Table 3

References 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]	Zhi REN, Dong ZHANG, Shuo TANG. Improved three-dimensional A^* algorithm of real-time path planning based on reinforcement learning [J]. Systems Engineering and Electronics, 2023, 45(1): 193-201.
[2]	Haobo FENG, Qiao HU, Zhenyi ZHAO. AUV swarm path planning based on elite family genetic algorithm [J]. Systems Engineering and Electronics, 2022, 44(7): 2251-2262.
[3]	Dou CHEN, Xiuyun MENG. UAV offline path planning based on self-adaptive coyote optimization algorithm [J]. Systems Engineering and Electronics, 2022, 44(2): 603-611.
[4]	Yang YIN, Quanshun YANG, Zheng WANG, Yang LIU. USV cluster coverage search method with communication distance constraint [J]. Systems Engineering and Electronics, 2022, 44(12): 3821-3828.
[5]	Qingqing YANG, Yingying GAO, Yu GUO, Boyuan XIA, Kewei YANG. Target search path planning for naval battle field based on deep reinforcement learning [J]. Systems Engineering and Electronics, 2022, 44(11): 3486-3495.
[6]	Tong HAN, Andi TANG, Huan ZHOU, Dengwu XU, Lei XIE. Multiple UAV cooperative path planning based on LASSA method [J]. Systems Engineering and Electronics, 2022, 44(1): 233-241.
[7]	Weiqiang MA, Yongqi GAO, Miao ZHAO. Global-best difference-mutation brain storm optimization algorithm [J]. Systems Engineering and Electronics, 2022, 44(1): 270-278.
[8]	Lei LAI, Kun ZOU, Dewei WU, Baozhong LI. Multi-UAV cooperative path planning based on improved MOFA evolution of interactive strategy [J]. Systems Engineering and Electronics, 2021, 43(8): 2282-2289.
[9]	Zhiqiang JIAO, Jieyong ZHANG, Peiyang YAO, Xun WANG, Yichao HE. Distributed evolution method of C4ISR service deployment based on hierarchical structure [J]. Systems Engineering and Electronics, 2021, 43(6): 1572-1585.
[10]	Wenming WANG, Jialu DU. Agent path planning based on regular hexagon grid JPS algorithm [J]. Systems Engineering and Electronics, 2021, 43(12): 3635-3642.
[11]	Yanan LI, Haibin HUANG, Liangming CHEN, Yufei ZHUANG, Xiaoli WANG. Energy-optimal three-dimensional path planning for AUV under changing ocean current environment [J]. Systems Engineering and Electronics, 2021, 43(12): 3667-3674.
[12]	Wengang LI, Liujiang WANG, Dexiang FANG, Yuwei LI, Jun Huang. Path planning algorithm combining A^* with DWA [J]. Systems Engineering and Electronics, 2021, 43(12): 3694-3702.
[13]	Yao HAN, Shaohua LI. UAV path planning based on improved artificial potential field [J]. Systems Engineering and Electronics, 2021, 43(11): 3305-3311.
[14]	Daidai CHEN, Wanyou LI. Local path planning algorithm for USV with towed cable [J]. Systems Engineering and Electronics, 2020, 42(9): 1988-1994.
[15]	Quanxian ZHANG, Bin ZENG, Houpu LI. Underway replenishment path planning method for distributed naval warfare under the influence of sea conditions [J]. Systems Engineering and Electronics, 2020, 42(10): 2312-2319.

Energy-efficient path planning method for robots based on improved A^* algorithm

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 12

References 35

Related Articles 15

Recommended Articles

Metrics

Comments

Energy-efficient path planning method for robots based on improved A* algorithm

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 12

References 35

Related Articles 15

Recommended Articles

Metrics

Comments

Energy-efficient path planning method for robots based on improved A^* algorithm