摘要

许多导航系统，包括无处不在的ROS导航堆栈，在单个成本图上执行路径规划，其中大部分信息存储在单个网格中。这种方法在生成最小长度的无碰撞路径方面非常成功，但是当成本图中的值超出已占用或空闲空间时，它在动态的、充满人员的环境中可能会遇到困难。
我们已经创建并实现了一种称为分层成本图的新方法，它通过将成本图数据的处理分离到语义上分离的层来工作。每一层跟踪一种类型的障碍或约束，然后修改用于路径规划的主成本图。我们展示了该算法如何与开源ROS导航堆栈集成，以及我们的方法如何比现有的单一方法更容易微调到特定的环境上下文。我们的设计还在实际使用中实现了更快的路径规划，并展示了比原始架构更清晰的关注点分离。新算法还可以表示复杂的代价值，以便为广泛的上下文创建导航行为。

1.Introduction

导航算法在过去的几十年里变得越来越复杂。它们可以处理大量传感器数据，以非常精确地跟踪障碍物和自由空间的位置。与正确的路径规划器相结合，他们可以非常熟练地引导机器人绕过环境。然而，许多这些导航算法都面临着同样的问题:算法优化基于寻找有效无碰撞路径的单一约束。
这种算法适用于许多用例，或者抽象的导航，如果所有重要的是从A点到b点，它对其他用例来说是不够的。]=
对于在人多的动态环境中运动的机器人，需要将更复杂的约束条件集成到优化中。从一个点移动到另一个点只是一个更大背景的一部分。机器人仅仅为了避免碰撞而绕过障碍物是不够的;机器人必须以不同的方式对待障碍，因为它是语义上的。例如，在大多数情况下，远离桌子几厘米是完全没问题的。然而，开车离一个人那么近在社会上是不受欢迎的。然而，如果导航算法平等地对待所有感知到的障碍，路径规划器就无法选择其中一条路径。

除了尊重人们的个人空间之外，还有许多其他情况，在这些情况下，选择最短的无碰撞路径可能不是最佳选择。考虑到人们经常在哪里的信息，避开可能的障碍的较长的路径可能是可取的。机器人还必须考虑进入潜在危险区域的效用，比如厨房，这是有效的路径，但需要付出代价。即使是像在走廊的右侧行驶这样简单的因素也需要考虑。机器人选择哪条路径将取决于对更大环境的额外信息。
关于路径规划器使用的环境的信息存储在成本映射中。在传统的成本图中，所有的数据都存储在单一的网格值中，我们称之为整体成本图。单片成本映射一直是流行的技术，因为它很简单，因为只有一个地方可以读取值和写入值。这样做的一个结果是丢失了关于成本映射中值的大量语义信息，这使得在周期之间正确维护成本映射变得更加困难