Paths generated by A* and other graph-search-based planners are widely used in the robotic field. Due to the restricted node-expansion directions, the resulting paths are usually not the shortest. Besides, unnecessary heading changes, or zig-zag patterns, exist even when no obstacle is nearby, which is inconsistent with the human intuition that the path segments should be straight in wide-open space due to the absence of obstacles. This article puts forward a general and systematic post-processing algorithm for A* and other graph-search-based planners. The A* post-processing algorithm, called APP, is developed based on the costmap, which is widely used in commercial service robots. First, a bidirectional vertices reduction algorithm is proposed to tackle the asymm- etry of the path and the environments. During the forward and backward vertices reduction, a thorough shortcut strategy is put forward to improve the path-shortening performance and avoid unnecessary heading changes. Second, an iterative path perturbation algorithm is adopted to locally reduce the number of unnecessary heading changes and improve the path smooth- ness. Comparative experiments are then carried out to validate the superiority of the proposed method. Quantitative performance indexes show that APP outperforms the existing methods in planning time, path length as well as the number of unnecessary heading changes. Finally, field navigation experiments are carried out to verify the practicability of APP.

翻译：由A*及其他基于图搜索的规划器生成的路径在机器人领域被广泛应用。由于节点扩展方向的限制，所得路径通常并非最短。此外，即使附近无障碍物，路径中仍存在不必要的航向变化或锯齿状模式，这与人类直觉相悖——在开阔无障碍空间内路径段应为直线。本文提出了一种适用于A*及其他基于图搜索规划器的通用系统化后处理算法。该算法命名为APP（A*后处理算法），基于商用服务机器人广泛使用的代价地图开发。首先，针对路径与环境的不对称性，提出一种双向顶点缩减算法。在前后向顶点缩减过程中，引入全面捷径策略以提升路径缩短性能并避免不必要的航向变化。其次，采用迭代式路径扰动算法局部减少不必要的航向变化数量并提升路径平滑度。随后通过对比实验验证所提方法的优越性。定量性能指标表明，APP在规划时间、路径长度及不必要航向变化数量方面均优于现有方法。最后，通过实地导航实验验证了APP的实用性。