启发式最优航迹规划算法数据结构的改进研究

摘要

结合航迹规划多约束条件的实际,改进了启发式A*系列算法的流程及数据结构,将A*算法中的OPEN表映射到CLOSED表中,提出一种装箱式方法管理CLOSED表,提高了对重复节点的查找效率,解决了并行A*算法中维护CLOSED表时存在的数据访问冲突问题,使得算法更加适用于实现并行多核编程.采用最小二叉树的方式管理OPEN表,克服了采用传统链表排序耗时、二叉堆数组容量有上界的缺点.仿真结果表明,改进的算法无论在单线程还是多线程并行解算以及搜索效率上都远远高于传统的A*系列算法.%Through improving the process and data structure of A * series algorithm for path planning with multi-restriction actual application, the OPEN list of A* algorithm was mapping to CLOSED list, this paper proposed a box model to manage CLOSED list, which improved the efficiency of seek for repeated nodes, and solved the data visiting conflict when using parallel computing, which made it more suitable for multi-processor programming. Using minimum binary tree to manage OPEN list, which overcome low efficiency sequencing of using traditional chained list and the capacity upper bound of binary heap array. The simulation results show the improved algorithm whether apply to parallel computing of single-threading or multi-threading and the efficiency of search are far more higher than traditional A' series algorithm.