Bidirectional APF-RRT Algorithm for Agent Path Planning Based on Heuristic Search and Probabilistic Sampling

SONG Wei; ZHANG Wen; ZHANG Ming; LIU Xiangchun

doi:10.12382/bgxb.2025.0539

您当前的位置：

首页 >

文章列表页 >

Bidirectional APF-RRT Algorithm for Agent Path Planning Based on Heuristic Search and Probabilistic Sampling

更新时间：2026-05-06

- Bidirectional APF-RRT Algorithm for Agent Path Planning Based on Heuristic Search and Probabilistic Sampling
- Acta Armamentarii Vol. 47, Issue 4, Pages: 250539(2026)
- 作者机构：
  
  中央民族大学国家安全研究院，北京 100081
  中央民族大学民族语言智能分析与安全治理教育部重点实验室，北京 100081
- 作者简介：
- 基金信息：
- DOI：10.12382/bgxb.2025.0539
  CLC： TP242.6
- Received：24 June 2025，
  
  Online First：27 January 2026，
  
  Published：2026-04
- 稿件说明：
移动端阅览
SONG Wei, ZHANG Wen, ZHANG Ming, et al. Bidirectional APF-RRT Algorithm for Agent Path Planning Based on Heuristic Search and Probabilistic Sampling[J]. Acta Armamentarii, 2026, 47(4): 250539.
DOI：

SONG Wei, ZHANG Wen, ZHANG Ming, et al. Bidirectional APF-RRT Algorithm for Agent Path Planning Based on Heuristic Search and Probabilistic Sampling[J]. Acta Armamentarii, 2026, 47(4): 250539. DOI： 10.12382/bgxb.2025.0539.

摘要

针对传统的快速探索随机树星（Rapidly-exploring Random Tree Star，RRT

）算法随机性强、收敛缓慢、路径冗长、转折点多等问题，为进一步提升无人智能装备的路径自主规划能力，提出一种基于启发式搜索和概率采样的双向人工势场引导的RRT

无人飞行智能体路径规划算法。设计融合目标切换、目标偏置与区域概率采样策

略，指导生成质量更高的随机采样点，并结合双向扩展机制加快搜索进程；引入启发式搜索方法，综合考虑已遍历路径的实际代价和目标方向的启发式代价，引导搜索树优先扩展低代价节点，有效减少无效探索；进一步结合改进的人工势场法与动态步长扩展机制，优化新节点的生成方向与距离，提高路径的平滑性与避障能力；通过贪婪优化与三次B样条插值实现路径精简和平滑处理。仿真结果表明，与已有的RRT

多种主流改进算法相比，新算法在收敛速度、路径代价和节点数等指标上具有优势，能够有效实现复杂场景的三维路径规划。

Abstract

The traditional rapidly-exploring random tree star (RRT

) algorithm has problems such as excessive randomness

slow convergence

lengthy paths

and excessive turning points. Focusing on the problem above

a heuristic search and probabilistic sampling-based bidirectional artificial potential field (APF) RRT

algorithm for unmanned aerial intelligent agent path planning is proposed to further enhance the autonomous path planning capability of unmanned intelligent systems. A strategy considering target switching

goal biasing and regional probabilistic sampling is designed to guide the generation of higher-quality random sampling points

and accelerate the search process by using the bidirectional expansion mechanism. A heuristic search strategy is incorporated to guide the expansion of search trees toward lower-cost nodes by jointly considering the actual traversal cost and heuristic cost to the target

thereby reducing ineffective exploration. Furthermore

an improved artificial potential field method combined with a dynamic step-size extension mechanism

adapted to obstacle density

is introduced to optimize the direction and distance of new node generation

enhancing both path smoothness and obstacle avoidance capability. Ultimately

the greedy optimization and cubic spline interpolation are employed to perform path simplification and smoothing. Simulated results demonstrate that

compared with existing mainstream improved variants of the RRT

algorithm

the proposed algorithm achieves advantages in convergence speed

path cost

and the number of nodes

effectively accomplishing three-dimensional path planning in complex scenarios.

关键词

Keywords

references

FANG Z X, SAVKIN A V. Strategies for optimized UAV surveillance in various tasks and scenarios:a review [J]. Drones, 2024, 8 (5): 193.

陈慧岩，张玉.军用地面无人机动平台技术发展综述[J].兵工学报，2014，35（10）：1696-1706.

CHEN H Y, ZHANG Y.An overview of research on military unmanned ground vehicles [J]. Acta Armamentarii, 2014, 35 (10): 1696-1706. (in Chinese)

DEBNATH D, VANEGAS F, SANDINO J, et al. A review of UAV path-planning algorithms and obstacle avoidance methods for remote sensing applications [J]. Remote Sensing, 2024, 16 (21): 4019.

DENG L X, CHEN H Y, LIU H Y, et al. Overview of UAV path planning algorithms [C]∥ Proceedings of the 2021 IEEE International Conference on Electronic Technology, Communication and Information. Changchun, China:IEEE, 2021:520-523.

LIU L X, WANG X, YANG X, et al. Path planning techniques for mobile robots: review and prospect [J]. Expert Systems with Applications, 2023, 227:120254.

YANG L, QI J T, XIAO J Z, et al. A literature review of UAV 3D path planning[C]∥Proceedings of the 11st World Congress on Intelligent Control and Automation. Shenyang, China:IEEE, 2014:2376-2381.

李季，孙秀霞.基于改进A-Star算法的无人机航迹规划算法研究[J].兵工学报，2008，29（7）：788-792.

LI J, SUN X X.A route planning's method for unmanned aerial vehicles based on improved A-Star algorithm [J]. Acta Armamentarii, 2008, 29 (7): 788-792. (in Chinese)

ALSHAMMREI S, BOUBAKER S, KOLSI L. Improved Dijkstra algorithm for mobile robot path planning and obstacle avoidance [J]. Computers, Materials and Continua, 2022, 72 (3): 5939-5954.

BROOKS R A, LOZANO-PÉREZ T. A subdivision algorithm in configuration space for findpath with rotation [J]. IEEE Transactions on Systems, Man, and Cybernetics, 1985, SMC-15 (2): 224-233.

AB WAHAB M N, NAZIR A, KHALIL A, et al. Improved genetic algorithm for mobile robot path planning in static environments [J]. Expert Systems with Applications, 2024, 249:123762.

KAYA E, GORKEMLI B, AKAY B, et al. A review on the studies employing artificial bee colony algorithm to solve combinatorial optimization problems [J]. Engineering Applications of Artificial Intelligence, 2022, 115:105311.

李宗刚，韩森，陈引娟，等.基于角度搜索和深度Q网络的移动机器人路径规划算法[J].兵工学报，2025，46（2）：240265.

LI Z G, HAN S, CHEN Y J, et al. A path planning algorithm for mobile robots based on angle searching and deep Q-network [J]. Acta Armamentarii, 2025, 46 (2): 240265. (in Chinese)

MNIH V, KAVUKCUOGLU K, SILVER D, et al. Human-level control through deep reinforcement learning [J]. Nature, 2015, 518 (7540): 529-533.

LAVALLE S M. Rapidly-exploring random trees:a new tool for path planning[R]. Ames, IA, US:Iowa State University, 1998.

夏炎，隋岩.PRM路径规划算法优化研究[J].应用科技，2010，37（10）：1-5.

XIA Y, SUI Y.Research on optimization of PRM path planning algorithm [J]. Applied Science and Technology, 2010, 37 (10): 1-5. (in Chinese)

KARAMAN S, FRAZZOLI E.Sampling-based algorithms for optimal motion planning:arXiv:1105.1186[R].Ithaca, NY, US:Cornell University, 2011:1105.1186.

MATTHEW J, ALEJANDRO P. Optimal bidirectional rapidlyexploring random trees[R]. Cambridge, MA, US:Massachusetts Institute of Technology, 2013.

QURESHI A H, AYAZ Y. Intelligent bidirectional rapidly exploring random trees for optimal motion planning in complex cluttered environments [J]. Robotics and Autonomous Systems, 2015, 68:1-11.

GAMMELL J D, SRINIVASA S S, BARFOOT T D. Informed RRT * :optimal sampling-based path planning foc used via direct sampling of an admissible ellipsoidal heuristic[C ] ∥Proceedings of the 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems. Chicago, IL, US:IEEE, 2014:2997-3004.

JEONG I B, LEE S J, KIM J H. RRT * -quick:a motion planning algorithm with faster convergence rate[C ] ∥Proceedings of the 3rd International Conference on Robot Intelligence Technology and Applications. Cham, Switzerland:Springer, 2015:67-76.

QURESHI A H, AYAZ Y. Potential functions based sampling heuristic for optimal path planning [J]. Autonomous Robots, 2016, 40:1079-1093.

FAN J M, CHEN X, LIANG X. UAV trajectory planning based on bi-directional APF-RRT * algorithm with goal-biased [J ] . Expert Systems with Applications, 2023, 213:119137.

孙海杰，伞红军，肖乐，等.一种改进的移动机器人路径规划算法[J].系统仿真学报，2024，36（9）：2193-2207.

SUN H J, SAN H J, XIAO L, et al. An improved path planning algorithm for mobile robots [J]. Journal of System Simulation, 2024, 36 (9): 2193-2207. (in Chinese)

WANG W J, LI J Y, BAI Z N, et al. Toward optimization of AGV path planning: an RRT * -ACO algorithm [J ] . IEEE Access, 2024, 12:18387-18399.

PROPPERT S, WOLTER S, HOLM T, et al. Cubic B-spline calibration for 3D super-resolution measurements using astigmatic imaging [J].Optics Express, 2014, 22 (9): 10304-10316.

Views

下载量

CNKI被引量

Alert me when the article has been cited

提交

Tools

Publicity Resources

Bi-directional Optimization of Multi-target Task Allocation and Path Planning for Autonomous Vehicles

RobotPath Planning Based on APF-IPPO Algorithm

A Rapid Global Path Planning Method for Unmanned Tracked Vehicles Considering Energy Consumption

ELPIO-based Collaboration Path Planning for UAV Swarm in Ultra-low Altitude Electromagnetic Threat Zone

Related Author

LIU Xiangchun

BAI Liting

LIU Xulei

ZHOU Guofeng

PENG Yiqiang

CHEN Siye

LI Feng

LIU Qingyun

Related Institution

School of Engineering, Shanghai Ocean University

School of Automobile and Transportation, Xihua University

Yibin Research Institute, Xihua University

Provincial Engineering Research Center for New Energy Vehicle Intelligent Control and Simulation Test Technology of Sichuan

School of Geospatial Information, Information Engineering University

Postal code：100089
Tel：010-68963060/68962718 Fax：010-68963025 Email：bgxb@cos.org.cn
Technical support is provided by Beijing Founder electronics co., LTD 京ICP备05059581号-4 京公网安备11010802024360号
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.
Total Visits：128316 Visits Today：432

⁰