智能规划是人工智能的一个重要方向,路径规划是智能规划研究的基本和热点问题。在过去的二十年里,机器人技术和视频游戏的不断进步导致了超凡的智能系统,取得这些进展的关键无疑是路径规划。但在各种环境条件下找到起点与目标点之间一条满足约束的有效路径的能力仍然是一项巨大挑战。路径规划在此基础上更高的目标是为用户提供高性能、真实的路径。Hart和Nilson在Dijkstra算法十年后于1969年发表了一篇伟大的论文,提出了著名的A*算法。A*算法作为最经典的人工智能算法之一,对路径规划问题的算法研究和具体应用都有着及其深远的影响。经典A*算法具有框架简洁和适用范围广的突出优越性,但其主要缺点是时间开销大。对此,在过去的几十年间,不计其数的研究人员对经典A*算法进行改进,提出了几十种改进A*的算法,如CPDs（Compressed Path Databases）、JPS（Joint Point Search）、Topping（Two-Oracle Path Planning）、HPA*（Hierarchical Path-Finding A*）等。本文工作主要集中在以下三个方面:（1）CPDs算法改进:CPDs算法属于基于预处理改进A*的方法之一,其在GPPC（Grid-based Path Planning Competition）2014有着优异表现。本文在Chiari等人于2019年提出的Proximity-wildcards策略及相应算法（CPDs＿PW）基础上进行改进,它是CPDs算法压缩效率方向最新优秀成果之一,主要思想是通过扩大Proximity-wildcards区域面积,从而利用更多启发式信息,减少CPDs算法的预处理内存。本文提出两种改进的Proximity-wildcards策略:RPW（Rectangular Proximity-wildcards）和CPW（Coordinates Proximity-wildcards）并提出CPDs＿RPW和CPDs＿CPW相应两种路径规划算法。RPW将Proximity-wildcards区域从以任意节点为中心的正方形扩大至矩形。CPW以任意节点为原点将CPD结构分为四象限,计算每个象限的最大矩形区域。（2）Topping算法改进:Topping算法即属于基于预处理改进又属于基于对称性消除（Symmetry Breaking）改进A*的方法,其是由Salvetti等人于2018年提出的一种结合JPS+（Joint Point Search+）和SRC（Single Row Compression）思想的算法。本文在Topping算法基础上结合启发式冗余符号、Proximity-wildcards和RPW三种策略提出Topping+H、Topping+H+PW和Topping+H+RPW三种算法,改进算法可在减小预处理内存同时加快搜索效率。（3）在GPPC竞赛基准数据集上的实验结果表明:基于RPW的CPDs＿RPW算法在预处理阶段和搜索阶段所有指标上均优于CPDs＿PW算法;基于CPW的CPDs＿CPW算法在CPD大小和搜索时间上的结果稍显逊色,但在其余第一移动表大小、游程编码（Run Length Encoding,RLE）次数和执行二分搜索次数指标上在所有对比算法中表现最优,展示出无穷潜力;Topping+H、Topping+H+PW和Topping+H+RPW三种算法在预处理阶段和搜索阶段所有指标均优于Topping算法。