本文为经典文献《Path Planning for Autonomous Vehicles in Unknown Semi-structured Environments》第二章节中“2.2. Analytic Expansions”内容的中文译文，并附有英文原文。所翻译内容结合了本人见解，欢迎指正。
2.2. 分步扩展
前文所述的前向搜索方法使用了控制变量（前轮转角）的离散空间。这意味着该搜索方法不能搜索到目标状态的具体连续坐标值（搜索精度取决于A*栅格的分辨率）。为了解决搜索精度问题并进一步提高搜索速度，我们使用基于Reeds–Shepp模型（Reeds and Shepp 1990 [1]）的分步扩展方法来加速搜索。在该方法中，通过使用车辆运动学模型（使用某一特定的控制变量）来扩展得到搜索树中的节点，每间隔一小段时间（取决于栅格精度）进行一次扩展。
The forward search described above uses a discretized space of control actions (steering). This means that the search will never reach the exact continuous-coordinate goal state (the accuracy depends on the resolution of the grid in A*). To address this precision issue, and to further improve search speed, we augment the search with Analytic expansions based on the Reed–Shepp model (Reeds and Shepp 1990). In the search described above, a node in the tree is expanded by simulating a kinematic model of the car (using a particular control action) for a small period of time (corresponding to the resolution of the grid).
除了通过前向搜索方法生成子节点外，对于某些节点的子节点，还可以通过计算从当前状态到目标状态的最优Reeds–Shepp路径来生成（假设环境中不存在障碍物）。然后在当前存在障碍物的地图中对Reeds–Shepp路径进行碰撞检测，只有当该路径不处于碰撞状态时，子节点才能被添加到搜索树。尽管Reeds–Shepp扩展是通过分步执行的（即按周期扩展），但是我们的研究表明该扩展方法比常规的前向节点扩展方法消耗稍微更多的时间。因此，不需要对每一个节点都执行Reeds–Shepp扩展（特别是距离目标节点较远的节点，大部分由扩展得到的Reeds–Shepp路径都处于碰撞状态）。在研究中我们使用了一个简单的筛选规则，即每相隔N个节点执行一次Reeds–Shepp扩展，N随着目标代价启发函数值的减小而减小（当越接近目标节点时，提高执行分步扩展的频率）。
In addition to children generated in such a way, for some nodes an additional child is generated by computing an optimal Reed–Shepp path from the current state to the goal (assuming an obstacle-free environment). The Reed–Shepp path is then checked for collisions against the current obstacle map, and the child node is only added to the tree if the path is collision-free. Despite the fact that Reed–Shepp expansions are done Analytically (i.e. in constant time), in our implementation they are slightly more expensive than the regular forward node expansions. Therefore, it might not be desirable to apply the Reed–Shepp expansion to every node (especially far from the goal, where most such paths are likely to go through obstacles). In our implementation we used a simple selection rule where the Reed–Shepp expansion is applied to one of every N nodes, where N decreases as a function of the cost-to-goal heuristic (leading to more frequent Analytic expansions as we get closer to the goal).
图4展示了使用Reeds–Shepp扩展的搜索树。图中黄色和绿色部分是由逐渐递增的前向节点扩展得到的搜索树，紫色线段是由Reeds–Shepp扩展得到的，该线段从搜索树延申到目标节点。我们发现这种搜索树分步扩展方法能够显著改善路径规划的准确性和实时性。
A search tree with the Reed–Shepp expansion is shown in Figure 4. The search tree generated by the short incremental expansion of nodes is shown in the yellow-green color range, and the Reed–Shepp expansions is shown as the single purple line leading to the goal. We found that this Analytic extension of the search tree leads to significant benefits in both accuracy and planning time.
Reeds–Shepp分步扩展的算力优势在很大程度上取决于环境中障碍物的密度。当环境中的一大片区域不存在障碍物时，Reeds–Shepp扩展方法只需计算一次就能找到路径，而前向扩展方法所需的计算次数与环境区域的面积大小呈正相关。当环境中存在大量障碍物时，大部分由Reeds–Shepp扩展生成的路径都处于碰撞状态，并且需要排除掉。尽管如此，我们认为在特定的驾驶场景中这种方法能够显著提高路径重规划的速度。我们将在第五章中探讨这种方法的实证结果。
The computational benefits of using the Reed–Shepp Analytic expansions highly depend on the density of obstacles in the environment. On one side of the spectrum are large obstacle-free environments, where Reed–Shepp expansions will find a solution in one step, whereas a forward search will scale with the size of the environment. On the other side of the spectrum are environments with high density of obstacles, where most Reed–Shepp expansions will result in collisions and will have to be pruned. However, we found that in typical driving scenarios this technique leads to noticeable gains in replanning speed. We discuss empirical results of the benefits in Section 5.
参考文献：
[1] Reeds, J. A. and Shepp, L. A. (1990). Optimal paths for a car that goes both forwards and backwards. Pacific Journal of Mathematics, 145(2): 367–393.