基于多层双向A~*的未知环境路径规划算法研究  

PATH PLANNING IN UNKNOWN ENVIRONMENT BASED ON MULTI-LAYER BI-A~* ALGORITHM

作　　者：杜婉茹 王潇茵[1] 贾福凯 郑重[1] 李慧妍 Du Wanru;Wang Xiaoyin;Jia Fukai;Zheng Zhong;Li Huiyan(China Aerospace Academy of Systems Science and Engineering,Beijing 100048,China)

机构地区：[1]中国航天系统科学与工程研究院

出　　处：《计算机应用与软件》2019年第12期261-267,共7页Computer Applications and Software

基　　金：广东省科技厅应用型研发基金专项(2016B010127005)

摘　　要：面向未知战场环境的路径规划问题,提出一种多层双向A^*算法。该算法引入分层策略,使智能体在行进过程中实时响应突发障碍,进行有效避障路径重规划。采用同步双向搜索,并改进启发式代价函数,使得路径搜索算法快速收敛,提高算法在大规模环境中的路径规划效率。为保证智能体在拐角的行进安全,使用Her mite差值对路径进行平滑处理。实验表明,该算法与现有改进算法相比,处理冗余节点数减少12.9%,总用时缩短17.4%,在复杂未知环境中路径规划准确度和效率均有较大提高。For the path planning problem for unknown battlefield environment,this paper proposes a multi-layer bidirectional A^* algorithm.The algorithm introduced a layered strategy,which enabled the agent to respond to sudden obstacles in real time in the moving process,and to effectively re-plan the obstacle avoidance path.We adopted synchronous bidirectional search and improved the heuristic cost function,which made the path search algorithm converge quickly and improved the efficiency of the algorithm in large-scale environment.In order to ensure the safety of the agent in the corner,Hermite method was used to smooth the path.Experiments show that compared with the existing improved algorithm,the algorithm reduces the number of redundant nodes by 12.9%and the total time is shortened by 17.4%.The accuracy and efficiency of path planning are greatly improved in complex and unknown environments.

关 键 词：未知环境 路径规划 智能体 多层双向 A^*算法 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]