Page 188 - 《软件学报》2025年第7期

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
2025,36(7):3109−3133 [doi: 10.13328/j.cnki.jos.007340] [CSTR: 32375.14.jos.007340] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563

*
面向智能体路径规划算法的动态随机测试方法

张逍怡 1 , 李 幸 1 , 刘 洋 2 , 郑 征 3 , 孙昌爱 1

1
(北京科技大学 计算机科学与通信工程学院, 北京 100083)
2
(北京交通大学 机械与电子控制工程学院, 北京 100044)
3
(北京航空航天大学 自动化与电气工程学院, 北京 100191)
通信作者: 刘洋, E-mail: yangliu2@bjtu.edu.cn

摘 要: 智能体路径规划算法旨在规划某个智能体的行为轨迹, 使其在不碰到障碍物的情况下安全且高效地从起
始点到达目标点. 目前智能体路径规划算法已经被广泛应用到各种重要的物理信息系统中, 因此在实际投入使用
前对算法进行测试, 以评估其性能是否满足需求就非常重要. 然而, 作为路径规划算法的输入, 任务空间中威胁障
碍物的分布形式复杂且多样. 此外, 路径规划算法在为每个测试用例规划路径时, 通常需要较高的运行代价. 为了
提升路径规划算法的测试效率, 将动态随机测试思想引入到路径规划算法中, 提出了面向智能体路径规划算法的
动态随机测试方法 (dynamic random testing approach for intelligent agent path planning algorithms, DRT-PP). 具体来
说, DRT-PP 对路径规划任务空间进行离散划分, 并在每个子区域内引入威胁生成概率, 进而构建测试剖面, 该测试
剖面可以作为测试策略在测试用例生成过程中使用. 此外, DRT-PP 在测试过程中通过动态调整测试剖面, 使其逐
渐优化, 从而提升测试效率. 实验结果显示, 与随机测试及自适应随机测试相比, DRT-PP 方法能够在保证测试用例
多样性的同时, 生成更多能够暴露被测算法性能缺陷的测试用例.
关键词: 软件测试; 路径规划算法; 动态随机测试; 快速扩展随机树生成算法; 测试剖面生成
中图法分类号: TP311

中文引用格式: 张逍怡, 李幸, 刘洋, 郑征, 孙昌爱. 面向智能体路径规划算法的动态随机测试方法. 软件学报, 2025, 36(7):
3109–3133. http://www.jos.org.cn/1000-9825/7340.htm
英文引用格式: Zhang XY, Li X, Liu Y, Zheng Z, Sun CA. Dynamic Random Testing Approach for Intelligent Agent Path Planning
Algorithms. Ruan Jian Xue Bao/Journal of Software, 2025, 36(7): 3109–3133 (in Chinese). http://www.jos.org.cn/1000-9825/7340.htm

Dynamic Random Testing Approach for Intelligent Agent Path Planning Algorithms
3
2
1
1
ZHANG Xiao-Yi , LI Xing , LIU Yang , ZHENG Zheng , SUN Chang-Ai 1
1
(School of Computer and Communication Engineering, University of Science and Technology Beijing, Beijing 100083, China)
2
(School of Mechanical, Electronic and Control Engineering, Beijing Jiaotong University, Beijing 100044, China)
3
(School of Automation Science and Electronic Engineering, Beihang University, Beijing 100191, China)
Abstract: Path planning algorithms for intelligent agents are designed to plan the behavior trajectory of an agent so that it can safely and
efficiently reach the target point from the starting point without colliding with obstacles. Currently, path planning algorithms have been
widely applied in various critical cyber-physical systems. Therefore, it is essential that the path planning algorithms be tested before being
put into use to evaluate whether their performance can meet the requirements. However, the distribution patterns of threat obstacles in the
task space, which are the inputs of the path planning algorithm, are complex and diverse. Moreover, a relatively high operational cost is
usually required when the path planning algorithm plans a path for each test case. To improve the testing efficiency of the path planning

* 基金项目: 国家自然科学基金 (62302035, 62403044, 62372021); 中央高校基本科研业务费专项资金 (2023JBMC017, FRF-IDRY-23-016)
本文由“新兴软件与系统的可信赖性与安全”专题特约编辑向剑文教授、陈厅教授、杨珉教授、周俊伟教授推荐.
收稿时间: 2024-08-26; 修改时间: 2024-10-15; 采用时间: 2024-11-25; jos 在线出版时间: 2024-12-10
CNKI 网络首发时间: 2025-04-17