[1]邢慧杰,张晓滨,张宏伟.APF与A*融合的多目标点路径规划算法[J].计算机技术与发展,2024,34(08):116-121.[doi:10.20165/j.cnki.ISSN1673-629X.2024.0116]
　XING Hui-jie,ZHANG Xiao-bin,ZHANG Hong-wei.A Multi-objective Point Path Planning Algorithm Based on Fusion of APF and A*[J].,2024,34(08):116-121.[doi:10.20165/j.cnki.ISSN1673-629X.2024.0116]
点击复制

APF与A*融合的多目标点路径规划算法

《计算机技术与发展》[ISSN:1006-6977/CN:61-1281/TN]

卷:
34
期数:
2024年08期
页码:
116-121
栏目:
人工智能
出版日期:
2024-08-10

文章信息/Info

Title:
A Multi-objective Point Path Planning Algorithm Based on Fusion of APF and A*
文章编号:
1673-629X(2024)08-0116-06
作者:
邢慧杰1; 张晓滨1; 张宏伟2
1. 西安工程大学 计算机科学学院,陕西 西安 710048; 2. 西安翔腾微电子科技有限公司,陕西 西安 710068
Author(s):
XING Hui-jie1; ZHANG Xiao-bin1; ZHANG Hong-wei2
1. School of Computer Science,Xi'an Polytechnic University,Xi'an 710048,China; 2. Xi'an Xiangteng Microelectronics Technology Co. ,Ltd. ,Xi'an 710068,China
关键词:
移动机器人; A*算法; 人工势场法; 多目标点路径规划; 融合算法
Keywords:
mobile robot; A* algorithm; artificial potential field method; multi-target point path planning; fusion algorithm
分类号:
TP242
DOI:
10.20165/j.cnki.ISSN1673-629X.2024.0116
摘要:
在智能餐厅环境下,针对移动机器人在多目标点路径规划时存在规划效率不高的问题,提出了一种基于 A*算法 与 APF 算法相结合的多目标点路径规划的方法。 将多目标点路径规划问题转化成类旅行商问题,采用 A*算法和人工势场法规划出多目标点的最优遍历顺序。 首先,将若干个目标点用一个集合表示并应用在 A*算法上面,实现 A*算法多个目标点的路径规划;其次,引入人工势场法对多个目标点进行优先级判定,借助人工势场法计算各个目标点的势能值,之后利用人工势场法得到的势能值对目标点集进行排序,完成各个目标点之间的最优顺序;最后,对规划好的目标点集使用A*算法进行全局路径规划。 为了验证该方法的有效性和先进性,将该算法进行消融实验,同时也与两种典型的多目标点规划算法进行对比。 结果表明,该算法是有效的,能够在缩短路径规划时间和降低路径代价的同时规划出一条有效路径。
Abstract:
In the smart restaurant environment,in order to solve the problem of low planning efficiency in multi-target point path planning of mobile robots,we propose a multi-target point path planning method based on the combination of A* algorithm and APF algorithm.The multi-target point path planning problem is transformed into a traveling salesman-like problem,and the A* algorithm and artificial potential field method are used to plan the optimal traversal sequence of multiple target points. Firstly, several target points are represented as a set and applied to the A* algorithm to realize the path planning of multiple target points of the A* algorithm.Secondly, the artificial potential field method is introduced to determine the priority of multiple target points. With the help of the artificial potential field method,the potential energy value of each target point is calculated and applied to sort the target point set for com-pleting of the optimal order among the target points. Finally,the A* algorithm is used for global path planning on the planned target point set. In order to verify the effectiveness and advancement of the proposed method,the proposed algorithm is subjected to ablation ex-periments and also compared with two typical multi-target point planning algorithms. The results show that the proposed algorithm is effective and can plan an effective path while shortening the path planning time and reducing the path cost.

相似文献/References:

[1]郑延斌 李新源 段德全.一种保持Agent团队队形的路径规划方法[J].计算机技术与发展,2009,(07):159.
　ZHENG Yan-bin,LI Xin-yuan,DUAN De-quan.A Path Planning Algorithm with Agent Team Formation Maintained[J].,2009,(08):159.
[2]冯晓辉 马光思.数码谜题求解的算法设计及其扩展研究[J].计算机技术与发展,2009,(08):110.
　FENG Xiao-hui,MA Guang-si.Algorithm Design and Extension Research of N - Puzzle Problem[J].,2009,(08):110.
[3]王娜 马昕.基于细化算法的移动机器人拓扑地图创建[J].计算机技术与发展,2009,(10):11.
　WANG Na,MA Xin.Mobile Robot Topological Map Building Based on Thinning Algorithm[J].,2009,(08):11.
[4]李培 何中市.基于ArcGIS和GPS的水电气管理系统设计与实现[J].计算机技术与发展,2009,(01):172.
　LI Pei,HE Zhong-shi.Design and Implementation Water, Electricity and Gas Management System Based on ArcGIS and GPS[J].,2009,(08):172.
[5]范莉丽 王奇志.改进的生物激励神经网络的机器人路径规划[J].计算机技术与发展,2006,(04):19.
　FAN Li-li,WANG Qi-zhi.Robot Path Planning of Modified Biologically Inspired Neural Networks[J].,2006,(08):19.
[6]王肖青 王奇志.传统人工势场的改进[J].计算机技术与发展,2006,(04):96.
　WANG Xiao-qing,WANG Qi-zhi.An Evolutionary Method of Traditional Artificial Potential Field[J].,2006,(08):96.
[7]朱永红 张燕平.用VC＋＋实现基于A＊算法的八数码问题[J].计算机技术与发展,2006,(09):32.
　ZHU Yong-hong,ZHANG Yan-ping.Programming for Eight - Figure Puzzle Problem Based on Algorithm A ＊ with Visual C ＋ ＋[J].,2006,(08):32.
[8]陈益富 卢潇 丁豪杰.对Dijkstra算法的优化策略研究[J].计算机技术与发展,2006,(09):73.
　CHEN Yi-fu,LU Xiao,DING Hao-jie.Optimized Strategy Research over Algorithm of Dijkstra[J].,2006,(08):73.
[9]吕凌 曾碧.基于评估和分工合作并行蚁群机器人路径规划[J].计算机技术与发展,2011,(09):10.
　Lü Ling,ZENG Bi.Path Planning for Robot Introduction Parallel Ant Colony Algorithm Based on Division of Labor and Assessment[J].,2011,(08):10.
[10]方伟华.基于A＊算法和图遍历的烟草物流VRP的研究[J].计算机技术与发展,2011,(12):63.
　FANG Wei-hua.Research on Tobacco Logistics VRP Based on A ＊ Algorithm and Graph Traversal[J].,2011,(08):63.

更新日期/Last Update: 2024-08-10