一种路径规划方法和装置
技术领域
本发明涉及计算机技术领域，尤其涉及一种路径规划方法和装置。
背景技术
现有对可行驶装置的路径规划方法中，通常是把可行驶装置当做一个质点来考虑，基于起始点、目的地点的规划中，只考虑路径的可到达性，使得可行驶装置在按照规划的路径行驶时，在一些狭窄和转弯道路导致行驶困难，并且遇到障碍物时，需要依赖可行驶装置自身的感知决策控制系统来做额外避障，增加了可行驶装置行驶中的避障次数。
在实现本发明过程中，发明人发现现有技术中至少存在如下问题：
现有方法使得可行驶装置在一些狭窄和转弯道路行驶困难，且遇到障碍物时，需依赖自身的感知决策控制系统来做额外避障，增加了可行驶装置的避障次数，行驶的安全性差，路径实用性能差。
发明内容
有鉴于此，本发明实施例提供一种路径规划方法和装置，能够避免可行驶装置遇到狭窄和转弯道路而出现行驶困难的情况，减少可行驶装置行驶中的避障次数，提高行驶的安全性，路径实用性能高。
为实现上述目的，根据本发明实施例的一个方面，提供了一种路径规划方法。
一种路径规划方法，包括：接收可行驶装置发送的路径规划请求，所述路径规划请求包括所述可行驶装置的起始点位置和目的地位置；以所述起始点位置作为起始的途经节点，利用路径规划算法逐一确定其他各途经节点，直到最终确定出的途经节点为所述目的地位置时不再继续确定途经节点，其中，在逐一确定各途经节点的过程中，将当前途经节点的寻路范围内的各节点中总移动代价最小的节点确定为所述当前途经节点的下一途经节点，所述各节点的总移动代价利用所述可行驶装置的物理运动特性参数计算得到；根据所有所述途经节点得到所述可行驶装置的规划路径。
可选地，所述物理运动特性参数包括所述可行驶装置的物理尺寸和最小转向半径，将当前途经节点的寻路范围内的各节点中总移动代价最小的节点确定为所述当前途经节点的下一途经节点的步骤之前，包括：确定所述当前途经节点的相邻可行驶节点集合，对于所述相邻可行驶节点集合中的每个节点：根据所述可行驶装置的物理尺寸和最小转向半径，计算该节点的总移动代价；判断该节点是否在所述当前途经节点的上一途经节点的寻路范围内，若在，则将计算出的该节点的总移动代价与该节点的已存总移动代价比较，并在所述计算出的该节点的总移动代价小于所述已存总移动代价的情况下，将所述已存总移动代价更新为所述计算出的该节点的总移动代价；若该节点不在所述当前途经节点的上一途经节点的寻路范围内，则将该节点添加到所述当前途经节点的上一途经节点的寻路范围对应的节点列表，以根据所述节点列表确定所述当前途经节点的寻路范围，并保存该节点的总移动代价；其中，所述当前途经节点为所述起始点位置时，所述当前途经节点的上一途经节点的寻路范围为空。
可选地，根据所述可行驶装置的物理尺寸和最小转向半径，计算该节点的总移动代价的步骤，包括：根据所述可行驶装置的物理尺寸和最小转向半径，计算所述当前途经节点到该节点的通过权重代价和转向代价；利用所述当前途经节点到该节点的通过权重代价和转向代价，计算所述当前途经节点到该节点的移动代价；根据所述当前途经节点到该节点的移动代价以及所述当前途经节点的已存移动代价，计算该节点的移动代价；计算该节点到所述目的地位置的估计代价；将该节点的移动代价和所述估计代价加和，得到该节点的总移动代价。
可选地，根据所述可行驶装置的物理尺寸和最小转向半径，计算所述当前途经节点到该节点的通过权重代价和转向代价的步骤，包括：根据所述可行驶装置的物理尺寸，判断所述当前途经节点到所述该节点之间的路段是否具备所述可行驶装置的通行条件；如果所述路段不具备所述通行条件，则将所述通过权重代价和所述转向代价均设置为大于第一阈值的任意数值；如果所述路段具备所述通行条件，其中：在所述路段不包括转向道路的情况下，根据所述可行驶装置的物理尺寸和所述路段的宽度，计算所述通过权重代价，并设置所述转向代价为设定值；在所述路段包括转向道路的情况下，根据所述可行驶装置的最小转向半径判断所述路段是否具备所述可行驶装置的转向条件，若是，则根据所述可行驶装置的物理尺寸和所述路段的宽度，计算所述通过权重代价，以及根据所述转向道路的转向角与转向代价之间的第一预设对应关系，计算所述转向代价；否则，将所述通过权重代价和所述转向代价均设置为大于所述第一阈值的任意数值。
可选地，所述通行条件为：所述路段的宽度大于或等于所述可行驶装置的物理尺寸与预设安全冗余值之和；所述转向条件为：所述转向道路的转向半径大于或等于所述可行驶装置的最小转向半径；根据所述可行驶装置的物理尺寸和所述路段的宽度，计算所述通过权重代价的步骤，包括：通过将所述可行驶装置的物理尺寸与预设安全冗余值加和，得到所述可行驶装置的最小安全通过宽度；计算所述路段的宽度与所述最小安全通过宽度的比值，利用所述比值与所述通过权重代价之间的第二预设对应关系，得到所述通过权重代价。
可选地，所述通行条件为：所述路段的宽度大于或等于所述可行驶装置的物理尺寸与预设安全冗余值之和；所述转向条件为：所述转向道路的转向半径大于或等于所述可行驶装置的最小转向半径；根据所述可行驶装置的物理尺寸和所述路段的宽度，计算所述通过权重代价的步骤，包括：通过将所述可行驶装置的物理尺寸与预设安全冗余值加和，得到所述可行驶装置的最小安全通过宽度；计算所述路段的宽度与所述最小安全通过宽度的比值，利用所述比值与所述通过权重代价之间的第二预设对应关系，得到第一通过权重代价；将与所述路段的至少一种道路属性对应的预设的代价值与所述第一通过权重加和，得到所述通过权重代价。
可选地，所述路径规划请求还包括所述可行驶装置的姿态信息，根据所有所述途经节点得到所述可行驶装置的规划路径的步骤，包括：根据所有所述途经节点得到第一规划路径，并对所述第一规划路径进行平滑处理，得到第二规划路径，所述第二规划路径为所述可行驶装置的规划路径；其中，所述平滑处理包括以下一种或多种：若一途经节点与障碍物位置的距离小于或等于第二阈值，则利用切线圆平滑的方法，对所述第一规划路径中该途经节点处进行平滑处理；根据所述姿态信息，在所述起始点位置，沿着所述姿态信息所指示的所述可行驶装置的朝向对所述第一规划路径做平滑处理；在所述目的地位置，沿着所述可行驶装置的停放方位对所述第一规划路径做平滑处理。
根据本发明实施例的另一方面，提供了一种路径规划装置。
一种路径规划装置，包括：路径规划请求接收模块，用于接收可行驶装置发送的路径规划请求，所述路径规划请求包括所述可行驶装置的起始点位置和目的地位置；途经节点确定模块，用于以所述起始点位置作为起始的途经节点，利用路径规划算法逐一确定其他各途经节点，直到最终确定出的途经节点为所述目的地位置时不再继续确定途经节点，其中，在逐一确定各途经节点的过程中，将当前途经节点的寻路范围内的各节点中总移动代价最小的节点确定为所述当前途经节点的下一途经节点，所述各节点的总移动代价利用所述可行驶装置的物理运动特性参数计算得到；路径规划模块，用于根据所有所述途经节点得到所述可行驶装置的规划路径。
可选地，所述物理运动特性参数包括所述可行驶装置的物理尺寸和最小转向半径，所述途经节点确定模块包括寻路范围确定子模块，用于：确定所述当前途经节点的相邻可行驶节点集合，对于所述相邻可行驶节点集合中的每个节点：根据所述可行驶装置的物理尺寸和最小转向半径，计算该节点的总移动代价；判断该节点是否在所述当前途经节点的上一途经节点的寻路范围内，若在，则将计算出的该节点的总移动代价与该节点的已存总移动代价比较，并在所述计算出的该节点的总移动代价小于所述已存总移动代价的情况下，将所述已存总移动代价更新为所述计算出的该节点的总移动代价；若该节点不在所述当前途经节点的上一途经节点的寻路范围内，则将该节点添加到所述当前途经节点的上一途经节点的寻路范围对应的节点列表，以根据所述节点列表确定所述当前途经节点的寻路范围，并保存该节点的总移动代价；其中，所述当前途经节点为所述起始点位置时，所述当前途经节点的上一途经节点的寻路范围为空。
可选地，所述寻路范围确定子模块包括总移动代价计算单元，用于：根据所述可行驶装置的物理尺寸和最小转向半径，计算所述当前途经节点到该节点的通过权重代价和转向代价；利用所述当前途经节点到该节点的通过权重代价和转向代价，计算所述当前途经节点到该节点的移动代价；根据所述当前途经节点到该节点的移动代价以及所述当前途经节点的已存移动代价，计算该节点的移动代价；计算该节点到所述目的地位置的估计代价；将该节点的移动代价和所述估计代价加和，得到该节点的总移动代价。
可选地，所述总移动代价计算单元包括计算子单元，用于：根据所述可行驶装置的物理尺寸，判断所述当前途经节点到所述该节点之间的路段是否具备所述可行驶装置的通行条件；如果所述路段不具备所述通行条件，则将所述通过权重代价和所述转向代价均设置为大于第一阈值的任意数值；如果所述路段具备所述通行条件，其中：在所述路段不包括转向道路的情况下，根据所述可行驶装置的物理尺寸和所述路段的宽度，计算所述通过权重代价，并设置所述转向代价为设定值；在所述路段包括转向道路的情况下，根据所述可行驶装置的最小转向半径判断所述路段是否具备所述可行驶装置的转向条件，若是，则根据所述可行驶装置的物理尺寸和所述路段的宽度，计算所述通过权重代价，以及根据所述转向道路的转向角与转向代价之间的第一预设对应关系，计算所述转向代价；否则，将所述通过权重代价和所述转向代价均设置为大于所述第一阈值的任意数值。
可选地，所述通行条件为：所述路段的宽度大于或等于所述可行驶装置的物理尺寸与预设安全冗余值之和；所述转向条件为：所述转向道路的转向半径大于或等于所述可行驶装置的最小转向半径；所述计算子单元在根据所述可行驶装置的物理尺寸和所述路段的宽度，计算所述通过权重代价时：通过将所述可行驶装置的物理尺寸与预设安全冗余值加和，得到所述可行驶装置的最小安全通过宽度；计算所述路段的宽度与所述最小安全通过宽度的比值，利用所述比值与所述通过权重代价之间的第二预设对应关系，得到所述通过权重代价。
可选地，所述通行条件为：所述路段的宽度大于或等于所述可行驶装置的物理尺寸与预设安全冗余值之和；所述转向条件为：所述转向道路的转向半径大于或等于所述可行驶装置的最小转向半径；所述计算子单元在根据所述可行驶装置的物理尺寸和所述路段的宽度，计算所述通过权重代价时：通过将所述可行驶装置的物理尺寸与预设安全冗余值加和，得到所述可行驶装置的最小安全通过宽度；计算所述路段的宽度与所述最小安全通过宽度的比值，利用所述比值与所述通过权重代价之间的第二预设对应关系，得到第一通过权重代价；将与所述路段的至少一种道路属性对应的预设的代价值与所述第一通过权重加和，得到所述通过权重代价。
可选地，所述路径规划请求还包括所述可行驶装置的姿态信息，所述路径规划模块还用于：根据所有所述途经节点得到第一规划路径，并对所述第一规划路径进行平滑处理，得到第二规划路径，所述第二规划路径为所述可行驶装置的规划路径；其中，所述平滑处理包括以下一种或多种：若一途经节点与障碍物位置的距离小于或等于第二阈值，则利用切线圆平滑的方法，对所述第一规划路径中该途经节点处进行平滑处理；根据所述姿态信息，在所述起始点位置，沿着所述姿态信息所指示的所述可行驶装置的朝向对所述第一规划路径做平滑处理；在所述目的地位置，沿着所述可行驶装置的停放方位对所述第一规划路径做平滑处理。
根据本发明实施例的又一方面，提供了一种电子设备。
一种电子设备，包括：一个或多个处理器；存储器，用于存储一个或多个程序，当所述一个或多个程序被所述一个或多个处理器执行时，使得所述一个或多个处理器实现本发明提供的路径规划方法。
根据本发明实施例的又一方面，提供了一种计算机可读介质。
一种计算机可读介质，其上存储有计算机程序，所述程序被处理器执行时实现如本发明提供的路径规划方法。
上述发明中的一个实施例具有如下优点或有益效果：以可行驶装置的起始点位置作为起始的途经节点，利用路径规划算法逐一确定其他各途经节点，直到最终确定出的途经节点为可行驶装置的目的地位置时不再继续确定途经节点，其中，在逐一确定各途经节点的过程中，将当前途经节点的寻路范围内的各节点中总移动代价最小的节点确定为当前途经节点的下一途经节点，且各节点的总移动代价利用可行驶装置的物理运动特性参数计算得到；根据所有途经节点得到可行驶装置的规划路径。在路径规划时充分考虑可行驶装置的物理运动特性参数，避免可行驶装置遇到狭窄和转弯道路而出现行驶困难的情况，减少可行驶装置行驶中的避障次数，提高行驶的安全性，路径实用性能高。并且可以先根据所有途经节点得到第一规划路径，再对第一规划路径进行平滑处理，得到最终的规划路径，使得可行驶装置运动更加符合实际情况，减少了急转、急停现象。
上述的非惯用的可选方式所具有的进一步效果将在下文中结合具体实施方式加以说明。
附图说明
附图用于更好地理解本发明，不构成对本发明的不当限定。其中：
图1是根据本发明实施例的路径规划方法的主要步骤示意图；
图2是根据本发明实施例的路径规划流程示意图；
图3是根据实施例规划出的平滑绕过固定障碍物的路径示意图；
图4是根据本发明实施例的在狭窄道路的路径规划示意图；
图5是根据本发明实施例的路径规划装置的主要模块示意图；
图6是本发明实施例可以应用于其中的示例性系统架构图；
图7是适于用来实现本发明实施例的终端设备或服务器的计算机系统的结构示意图。
具体实施方式
以下结合附图对本发明的示范性实施例做出说明，其中包括本发明实施例的各种细节以助于理解，应当将它们认为仅仅是示范性的。因此，本领域普通技术人员应当认识到，可以对这里描述的实施例做出各种改变和修改，而不会背离本发明的范围和精神。同样，为了清楚和简明，以下的描述中省略了对公知功能和结构的描述。
本领域技术技术人员知道，本发明的实施方式可以实现为一种系统、装置、设备、方法或计算机程序产品。因此，本公开可以具体实现为以下形式，即：完全的硬件、完全的软件(包括固件、驻留软件、微代码等)，或者硬件和软件结合的形式。
图1是根据本发明实施例的路径规划方法的主要步骤示意图。
如图1所示，本发明实施例的路径规划方法主要包括如下的步骤S101至步骤S103。
步骤S101：接收可行驶装置发送的路径规划请求，路径规划请求包括可行驶装置的起始点位置和目的地位置。
其中，该起始点位置是指可行驶装置请求规划的路径上的行驶起点，可以是发送路径规划请求时可行驶装置的当前位置。
路径规划请求还包括可行驶装置的姿态信息和可行驶装置的标识信息，姿态信息可以包括可行驶装置的初始朝向等信息，标识信息例如可行驶装置的型号，用于查找预存的该可行驶装置的物理运动特性参数，可行驶装置的型号与其物理运动特性参数关联存储。
可行驶装置可以是机器人、AGV(自动导引运输车)等。
步骤S102：以起始点位置作为起始的途经节点，利用路径规划算法逐一确定其他各途经节点，直到最终确定出的途经节点为目的地位置时不再继续确定途经节点，其中，在逐一确定各途经节点的过程中，将当前途经节点的寻路范围内的各节点中总移动代价最小的节点确定为当前途经节点的下一途经节点，各节点的总移动代价利用可行驶装置的物理运动特性参数计算得到。
当前途经节点的寻路范围内每个节点都有已存的各自的总移动代价，从这些已存总移动代价中选取总移动代价最小的节点确定为当前途经节点的下一个途经节点。
本发明实施例的路径规划算法可以基于通用路径规划算法的思路实现，通用路径规划算法例如A星算法等。
途经节点是可行驶装置的规划路径所经过的节点，起始点位置为规划路径上的第一个节点，称之为起始的途经节点。每个途经节点对应一个寻路范围，该寻路范围包括多个节点，对于当前的每一个途经节点(即当前途经节点)，其寻路范围用于从中找到一个节点作为该当前途经节点的下一途经节点。以基于A星算法的路径规划算法为例，当前途经节点的寻路范围是确定在当前途经节点的下一途经节点时所遍历的Open列表(开放列表)。A星算法中Open列表是路径规划时被考虑的节点的列表，相对于Open列表，还有Close列表(封闭列表)，Close列表是路径规划时不被考虑的节点的列表。
可行驶装置的物理运动特性参数可以包括可行驶装置的物理尺寸和最小转向半径。物理尺寸例如宽度等。
将当前途经节点的寻路范围内的各节点中总移动代价最小的节点确定为所述当前途经节点的下一途经节点的步骤之前，确定当前途经节点的相邻可行驶节点集合，对于相邻可行驶节点集合中的每个节点：
根据可行驶装置的物理尺寸和最小转向半径，计算该节点的总移动代价；
判断该节点是否在当前途经节点的上一途经节点的寻路范围内，若在，则将计算出的该节点的总移动代价与该节点的已存总移动代价比较，并在计算出的该节点的总移动代价小于已存总移动代价的情况下，将已存总移动代价更新为计算出的该节点的总移动代价；
若该节点不在当前途经节点的上一途经节点的寻路范围内，则将该节点添加到当前途经节点的上一途经节点的寻路范围对应的节点列表，以根据该节点列表确定当前途经节点的寻路范围，并保存该节点的总移动代价；
其中，当前途经节点为起始点位置时，当前途经节点的上一途经节点的寻路范围为空。
当前途经节点的相邻可行驶节点是该当前途经节点的相邻节点之中可行驶的节点，其中，相邻节点在地图上可以与当前途经节点的上、下、左、右及对角方向上相邻。可行驶的节点是指该节点不是被墙或类似导致不可通行的事物占用、且不是无法通行地形等类似情况的节点。以基于A星算法的路径规划算法为例，一个节点的相邻节点可以称为该节点的后继节点，一个节点的相邻可行驶节点是该节点的不在Close列表(封闭列表)中的后继节点。
根据可行驶装置的物理尺寸和最小转向半径，计算该节点的总移动代价的步骤，具体可以包括：根据可行驶装置的物理尺寸和最小转向半径，计算当前途经节点到该节点的通过权重代价和转向代价；利用当前途经节点到该节点的通过权重代价和转向代价，计算当前途经节点到该节点的移动代价；根据当前途经节点到该节点的移动代价以及当前途经节点的已存移动代价，计算该节点的移动代价；计算该节点到目的地位置的估计代价；将该节点的移动代价和估计代价加和，得到该节点的总移动代价。
其中，计算该节点到目的地位置的估计代价的方法与现有的路径规划算法中计算估计代价的方法相同，例如采用欧拉代价估计、曼哈顿代价估计、几何代价估计等估计方法实现。
根据可行驶装置的物理尺寸和最小转向半径，计算当前途经节点到该节点的通过权重代价和转向代价的步骤，具体可以包括：
根据可行驶装置的物理尺寸，判断当前途经节点到该节点之间的路段是否具备可行驶装置的通行条件；通行条件具体可以为：路段的宽度大于或等于可行驶装置的物理尺寸与预设安全冗余值之和。可行驶装置的物理尺寸可为可行驶装置宽度，预设安全冗余值可以根据需要设置，例如设为40cm(厘米)，即在可行驶装置两侧各增加20cm，得到可行驶装置行驶时可以安全通过的最小宽度，如果路段道路的宽度小于该最小宽度，则可行驶装置无法安全通行，路段不具备通行条件，反之，路段具备通行条件。
如果该路段不具备通行条件，则将该通过权重代价和该转向代价均设置为大于第一阈值的任意数值；第一阈值为一个比较大的数值，例如1000000，以使得在路段不具备通行条件的情况下，通过权重代价和转向代价可以视为无穷大。
如果该路段具备所述通行条件，其中：
在该路段不包括转向道路的情况下，根据可行驶装置的物理尺寸和该路段的宽度，计算该通过权重代价，并设置该转向代价为设定值，该设定值为直行的转向代价，通常设置为1；转向道路可以是弯道、折线道路等非直线的道路。
在该路段包括转向道路的情况下，根据可行驶装置的最小转向半径判断该路段是否具备可行驶装置的转向条件，转向条件可以为转向道路的转向半径大于或等于可行驶装置的最小转向半径。若具备转向条件，则根据可行驶装置的物理尺寸和该路段的宽度，计算该通过权重代价，以及根据转向道路的转向角与转向代价之间的第一预设对应关系，计算该转向代价；不具备转向条件，将通过权重代价和转向代价均设置为大于第一阈值的任意数值。
根据转向道路的转向角与转向代价之间的第一预设对应关系，计算转向代价，具体地，设可行驶装置直行的转向代价为1，向左或者向右转向时，转向角每增加15度，则增加0.3倍的转向代价，即：转向15度对应的转向代价为1.3，转向30度时对应的转向代价为1.6，转向45度时对应的转向代价为1.9，以此类推，从而计算出可行驶装置在转向道路的转向代价。
作为一种实施方式，根据可行驶装置的物理尺寸和该路段的宽度，计算该通过权重代价的步骤，具体可以包括：通过将可行驶装置的物理尺寸与预设安全冗余值加和，得到可行驶装置的最小安全通过宽度，即上文所述的可行驶装置行驶时可以安全通过的最小宽度；计算路段的宽度与最小安全通过宽度的比值，利用该比值与通过权重代价之间的第二预设对应关系，得到该通过权重代价。第二预设对应关系例如：比值<1.5时，通过权重代价＝3；1.5≤比值<2时，通过权重代价＝2；比值≥2时，通过权重代价＝1。
作为另一种实施方式，在计算通过权重代价时，在基于上文计算出的通过权重代价的基础上，还可以考虑路段的道路长度、道路限速、减速带(如是否有减速带、减速带的数量等)、道路材质等道路属性中的一种或多种道路属性，例如对于每一道路属性的各种情况赋予不同的代价值。以道路材质为例，可以在道路材质为某一材质的情况下赋予某一代价值，在道路材质为另一材质的情况下赋予另外的代价值等等。最终将上文的根据可行驶装置的物理尺寸和最小转向半径计算出的通过权重代价，与利用道路属性计算出的代价值相加，得到当前途经节点到该节点的通过权重代价。
步骤S103：根据所有途经节点得到可行驶装置的规划路径。
具体地，根据所有途经节点得到第一规划路径，并对第一规划路径进行平滑处理，得到第二规划路径，第二规划路径为可行驶装置的规划路径；其中，平滑处理包括以下一种或多种：若一途经节点与障碍物位置的距离小于或等于第二阈值，则利用切线圆平滑的方法，对第一规划路径中该途经节点处进行平滑处理，其中，该第二阈值可以为上述可行驶装置的最小安全通过宽度的一半；根据可行驶装置的姿态信息，在起始点位置，沿着该姿态信息所指示的可行驶装置的朝向对第一规划路径做平滑处理；在目的地位置，沿着可行驶装置的停放方位对第一规划路径做平滑处理。
下面以可行驶装置为机器人为例，详细介绍本发明实施例的路径规划方法，本实施例的路径规划算法以基于A星算法的路径规划算法为例。
机器人在请求路径规划时，将其当前位置(为路径规划的起点，可称为机器人的起始点位置)、机器人姿态(即机器人的姿态信息)、目的地位置等信息上传到路径规划服务器。路径规划服务器根据机器人上传的信息，执行基于A星算法的路径规划算法，以进行路径规划，从而确定出一条合适的规划路径。
路径规划服务器执行的路径规划流程如图2所示，主要包括如下的步骤S201至步骤S214。
步骤S201：将起始节点放入Open列表。
起始节点即机器人的起始点位置，是路径起始的途经节点。此时Open列表中只有起始节点，在后续流程中Open列表将不断更新。
步骤S202：遍历当前Open列表，并从当前Open列表中取出总移动代价最小的节点作为当前节点。
从当前Open列表中取出总移动代价最小的节点作为当前节点，包括将该当前节点从Open列表中删除，并放入Close列表。
其中，在Open列表中只有起始节点的情况下，即将起始节点从Open列表中取出。
Open列表中的节点都有各自的保存的总移动代价、移动代价和估计代价，可分别对应称为该节点的已存总移动代价、已存移动代价、已存估计代价。
节点的已存总移动代价等于该节点的已存移动代价与已存估计代价之和。
节点的已存移动代价＝该节点的父节点的已存移动代价+该父节点到该节点的移动代价。其中，该父节点到该节点的移动代价为该父节点到该节点的通过权重代价、转向代价的加和，计算通过权重代价、转向代价后文将详细介绍。
与起始节点相邻的节点最初以起始节点为父节点，在路径规划过程中，节点的父节点可以更新。起始节点的已存移动代价为0。随着节点的父节点信息的更新，节点的已存总移动代价、已存移动代价相应改变。
节点的已存估计代价指该节点到目的地位置的估计代价，可以采用欧拉代价估计、曼哈顿代价估计、几何代价估计等估计方法计算。
步骤S203：判断当前节点是否为目的节点，若是，则执行步骤S213，否则，执行步骤S204。
目的节点是路径最后一个途径节点，即机器人的目的地位置。
步骤S204：计算当前节点的后继节点。
当前节点的后继节点是指当前节点的相邻节点，即在地图上与当前节点位置在上、下、左、右及对角方向相邻的各节点。
步骤S205：遍历当前节点的后继节点。
步骤S206：判断当前被遍历到的后继节点是否在Close列表中，若是，则抛弃该后继节点以执行S205遍历下一后继节点，否则，执行步骤S207。
步骤S207：计算当前节点到被遍历到的后继节点的移动代价，以及该后继节点的估计代价和总移动代价，其中根据机器人的物理运动特性参数计算当前节点到该后继节点的通过权重代价和转向代价，并根据该通过权重代价和转向代价计算该节点的移动代价。
该后继节点的估计代价h是该后继节点到目的地位置的估计代价；
当前节点到该后继节点的移动代价g1＝当前节点到该后继节点的通过权重代价+当前节点到该后继节点的转向代价；其中，根据机器人的物理运动特性参数(包括机器人的物理尺寸和最小转向半径)计算该通过权重代价和该转向代价。具体地：
可以根据机器人的物理尺寸，例如机器人宽度，在机器人两侧各增加20cm宽度，得到机器人可以安全通过的最小宽度，如果当前节点到该后继节点的路段道路宽度小于该机器人可以安全通过的最小宽度，则该路段不可通行，即不具备机器人的通行条件，那么应赋予一个较大的通过权重代价以提示该路段的通过性相对较差，将该通过权重代价和该转向代价都设置为无穷大(实际实施时可将1000000视为无穷大)。
在路段满足上述通行条件的情况下，可以判断路段是否包括转向道路，其中：在路段不包括转向道路的情况下，设置该转向权重为1(即直行条件下的转向权重)，并计算该通过权重代价。
在路段包括转向道路的情况下，可以根据机器人的物理运动属性，判断路段道路的转向半径是否小于机器人的最小转向半径，若是，则说明该路段不具备机器人的转向条件，否则该路段具备机器人的转向条件。
若路段不具备机器人的转向条件，则该通过权重代价和该转向代价都设置为无穷大(实际实施时可将1000000视为无穷大)。若路段具备该转向条件，则分别计算该通过权重代价和该转向代价。
在路段满足上述通行条件、且不包括转向道路的情况下，或者，在路段包括转向道路、且满足上述通行条件和转向条件的情况下，计算该通过权重代价的方法为：将路段的道路宽度与该机器人可以安全通过的最小宽度相比，得到一个比值，该比值与通过权重代价存在预设的对应关系，例如：比值<1.5时，通过权重代价＝3；1.5≤比值<2时，通过权重代价＝2；比值≥2时，通过权重代价＝1。
在路段包括转向道路、且满足上述通行条件和转向条件的情况下，计算该转向代价的方法为：以机器人直行条件下转向代价设置为1，道路向左或者向右转向，每增加15度则增加0.3倍的代价。例如转向15度，则转向代价为1.3，以此类推。路段道路转弯越急，该转向代价越大，代表转向通行性越差。
计算该后继节点的移动代价g＝当前节点的已存移动代价g2+当前节点到该后继节点的移动代价g1；
根据该后继节点的移动代价g、该后继节点的估计代价h，计算该后继节点的总移动代价f，f＝g+h。
步骤S208：判断该被遍历到的后继节点是否在Open列表中，若是，则执行步骤S210，否则，执行步骤S209。
步骤S209：将该被遍历到的后继节点加入Open列表，并将该后继节点的父节点设置为当前节点。
然后执行步骤S212。该被遍历到的后继节点加入Open列表之后，保存上述S207计算出的该后继节点的移动代价g、估计代价h、总移动代价f，保存的g、h、f的值相应地为该后继节点的已存移动代价、已存估计代价、已存总移动代价的值。
步骤S210：判断S207计算出的后继节点的总移动代价是否小于Open列表中该后继节点的已存总移动代价，若是，则执行步骤S211，否则执行步骤S212。
若该后继节点在Open列表中，则该后继节点有已经保存的总移动代价(即该节点的已存总移动代价)，以及已存移动代价、已存估计代价；则将S207计算出的后继节点的总移动代价f与该已存总移动代价比较，若该总移动代价f小于该已存总移动代价，则执行步骤S211。
步骤S211：将该后继节点的已存总移动代价、已存移动代价更新为S207计算出的相应代价，并更新该后继节点的父节点信息。
即将该后继节点的已存总移动代价、已存移动代价更新为S207计算出的该后继节点的总移动代价、移动代价，并将该后继节点的父节点更新为当前节点。该后继节点的已存估计代价与S207计算出的估计代价均为该后继节点到目的地位置的估计代价，二者相同。
步骤S212：判断当前节点的所有后继节点是否已经遍历完成，若否，则继续执行步骤S205，若是，则继续执行步骤S202。
步骤S213：从目的节点开始，向对应的父节点移动，最终达到起始节点，所得到的路径为第一规划路径。
通过上述过程，当最终选出的当前节点为目的节点，从该目的节点开始向其父节点移动，其父节点再向其自身的父节点移动，以此类推，直到从某一个节点移动到起始节点，由这些节点得到的路径即第一规划路径。
步骤S214：对第一规划路径进行平滑处理，得到第二规划路径。
第二规划路径即规划出的机器人最终的规划路径。
可以从机器人信息保存服务器中读取该型号机器人的物理运动特性参数，例如物理尺寸、最小转向半径等参数，根据机器人运动特性，进一步来优化平滑第一规划路径。其中，机器人型号的信息可以携带在机器人发送的路径规划请求中。
平滑处理可以包括：在经过障碍物时，先采取碰撞检测，如果路径和障碍物距离过近(例如路径中的节点与障碍物的最小距离小于机器人可以安全通过的最小宽度的一半，则视为距离过近)，可以采用切线圆平滑的方法，对该节点处的路径进行平滑，以降低路径的曲折程度，减少路径曲率不断变化的情况；针对机器人出发姿态，在路径规划起始处(即机器人的起始点位置)，沿着机器人朝向的切线方向开始规划；针对机器人将要到达的目的地，在路径规划停止处(即目的地位置)，是沿着预设的机器人停放方位做平滑处理；在机器人行驶过程中的路径进行平滑，以使机器人的运动方向和路径切线方向保持重合。
本实施例的路径规划流程综合考虑机器人的物理运动特性和运动规律，并把机器人的物理尺寸、转向半径等性能参数纳入到路径规划的约束因子中，从而在全局路径规划时，充分考虑到机器人的实际运动特性，针对机器人的运动特点，规划出一条实用性较强的路径，减少了折线路径和曲率不断变化的路径，提高了机器人自动行驶过程中的安全性和经济性。并且，本实施例针对固定障碍物，根据机器人的物理尺寸，提前做了膨胀处理，以防机器人行驶时发生与障碍物紧挨现象，减少机器人对固定障碍物的避障次数。并且，在路径规划经过固定障碍物时，根据机器人的最小转向半径等运动特性，针对性地进行路径调整和平滑处理，使得机器人运动更加符合实际情况，减少了机器人急转、急停现象。本实施例规划出的平滑绕过固定障碍物的路径示意图如图3所示。
另外，本实施例在路径规划时，考虑到机器人的物理尺寸、最小转向半径等因素，在狭窄范围处理上，减少了路径经过的几率，对于必须经过的路段，对路径的规划符合机器人运动规律，尽可能地减少机器人在狭窄路段的行驶困难程度，提高机器人通过狭小空间的便利性。本发明实施例在狭窄道路的路径规划示意图如图4所示，图4中机器人用带阴影的形状表示。
图5是根据本发明实施例的路径规划装置的主要模块示意图。
如图5所示，本发明实施例的路径规划装置500主要包括：路径规划请求接收模块501、途经节点确定模块502、路径规划模块503。
路径规划请求接收模块501，用于接收可行驶装置发送的路径规划请求，路径规划请求包括可行驶装置的起始点位置和目的地位置，路径规划请求还可以包括可行驶装置的姿态信息；
途经节点确定模块502，用于以起始点位置作为起始的途经节点，利用路径规划算法逐一确定其他各途经节点，直到最终确定出的途经节点为所述目的地位置时不再继续确定途经节点，其中，在逐一确定各途经节点的过程中，将当前途经节点的寻路范围内的各节点中总移动代价最小的节点确定为当前途经节点的下一途经节点，各节点的总移动代价利用可行驶装置的物理运动特性参数计算得到；
路径规划模块503，用于根据所有途经节点得到可行驶装置的规划路径。
其中，物理运动特性参数包括所述可行驶装置的物理尺寸和最小转向半径。
途经节点确定模块502可以包括寻路范围确定子模块，用于：确定当前途经节点的相邻可行驶节点集合，对于该相邻可行驶节点集合中的每个节点：根据可行驶装置的物理尺寸和最小转向半径，计算该节点的总移动代价；判断该节点是否在当前途经节点的上一途经节点的寻路范围内，若在，则将计算出的该节点的总移动代价与该节点的已存总移动代价比较，并在计算出的该节点的总移动代价小于已存总移动代价的情况下，将已存总移动代价更新为计算出的该节点的总移动代价；若该节点不在当前途经节点的上一途经节点的寻路范围内，则将该节点添加到当前途经节点的上一途经节点的寻路范围对应的节点列表，以根据节点列表确定当前途经节点的寻路范围，并保存该节点的总移动代价；其中，当前途经节点为起始点位置时，当前途经节点的上一途经节点的寻路范围为空。
寻路范围确定子模块可以包括总移动代价计算单元，用于：根据可行驶装置的物理尺寸和最小转向半径，计算当前途经节点到该节点的通过权重代价和转向代价；利用当前途经节点到该节点的通过权重代价和转向代价，计算当前途经节点到该节点的移动代价；根据当前途经节点到该节点的移动代价以及当前途经节点的已存移动代价，计算该节点的移动代价；计算该节点到目的地位置的估计代价；将该节点的移动代价和估计代价加和，得到该节点的总移动代价。
总移动代价计算单元可以包括计算子单元，用于：根据可行驶装置的物理尺寸，判断当前途经节点到该节点之间的路段是否具备可行驶装置的通行条件；如果该路段不具备所述通行条件，则将通过权重代价和转向代价均设置为大于第一阈值的任意数值；如果该路段具备通行条件，其中：在该路段不包括转向道路的情况下，根据可行驶装置的物理尺寸和该路段的宽度，计算该通过权重代价，并设置该转向代价为设定值；在该路段包括转向道路的情况下，根据可行驶装置的最小转向半径判断该路段是否具备可行驶装置的转向条件，若是，则根据可行驶装置的物理尺寸和该路段的宽度，计算该通过权重代价，以及根据转向道路的转向角与转向代价之间的第一预设对应关系，计算该转向代价；否则，将通过权重代价和转向代价均设置为大于第一阈值的任意数值。
通行条件为：该路段的宽度大于或等于可行驶装置的物理尺寸与预设安全冗余值之和；转向条件为：转向道路的转向半径大于或等于可行驶装置的最小转向半径；
作为一种实施方式，计算子单元在根据可行驶装置的物理尺寸和该路段的宽度，计算上述通过权重代价时：通过将可行驶装置的物理尺寸与预设安全冗余值加和，得到可行驶装置的最小安全通过宽度；计算该路段的宽度与最小安全通过宽度的比值，利用该比值与该通过权重代价之间的第二预设对应关系，得到该通过权重代价。
作为另一种实施方式，计算子单元在根据可行驶装置的物理尺寸和所述路段的宽度，计算通过权重代价时：通过将可行驶装置的物理尺寸与预设安全冗余值加和，得到可行驶装置的最小安全通过宽度；计算该路段的宽度与最小安全通过宽度的比值，利用比值与通过权重代价之间的第二预设对应关系，得到第一通过权重代价；将与所述路段的至少一种道路属性对应的预设的代价值与第一通过权重加和，得到通过权重代价。
路径规划模块503具体可以用于：根据所有途经节点得到第一规划路径，并对第一规划路径进行平滑处理，得到第二规划路径，第二规划路径为可行驶装置的规划路径；其中，平滑处理包括以下一种或多种：若一途经节点与障碍物位置的距离小于或等于第二阈值，则利用切线圆平滑的方法，对第一规划路径中该途经节点处进行平滑处理；根据可行驶装置的姿态信息，在起始点位置，沿着该姿态信息所指示的可行驶装置的朝向对第一规划路径做平滑处理；在目的地位置，沿着可行驶装置的停放方位对第一规划路径做平滑处理。
另外，在本发明实施例中所述路径规划装置的具体实施内容，在上面所述路径规划方法中已经详细说明了，故在此重复内容不再说明。
图6示出了可以应用本发明实施例的路径规划方法或路径规划装置的示例性系统架构600。
如图6所示，系统架构600可以包括终端设备601、602、603，网络604和服务器605。网络604用以在终端设备601、602、603和服务器605之间提供通信链路的介质。网络604可以包括各种连接类型，例如有线、无线通信链路或者光纤电缆等等。
用户可以使用终端设备601、602、603通过网络604与服务器605交互，以接收或发送消息等。终端设备601、602、603上可以安装有各种通讯客户端应用，例如搜索类应用、即时通信工具、邮箱客户端、社交平台软件等(仅为示例)。
终端设备601、602、603可以是具有显示屏并且支持网页浏览的各种电子设备，包括但不限于智能手机、平板电脑、膝上型便携计算机和台式计算机等等。
服务器605可以是提供各种服务的服务器，例如对用户利用终端设备601、602、603所浏览的网站提供支持的后台管理服务器(仅为示例)。后台管理服务器可以对接收到的产品信息查询请求等数据进行分析等处理，并将处理结果(例如推送信息--仅为示例)反馈给终端设备。
需要说明的是，本发明实施例所提供的路径规划方法一般由服务器605执行，相应地，路径规划装置一般设置于服务器605中。
应该理解，图6中的终端设备、网络和服务器的数目仅仅是示意性的。根据实现需要，可以具有任意数目的终端设备、网络和服务器。
下面参考图7，其示出了适于用来实现本申请实施例的终端设备或服务器的计算机系统700的结构示意图。图7示出的终端设备或服务器仅仅是一个示例，不应对本申请实施例的功能和使用范围带来任何限制。
如图7所示，计算机系统700包括中央处理单元(CPU)701，其可以根据存储在只读存储器(ROM)702中的程序或者从存储部分708加载到随机访问存储器(RAM)703中的程序而执行各种适当的动作和处理。在RAM 703中，还存储有系统700操作所需的各种程序和数据。CPU 701、ROM 702以及RAM 703通过总线704彼此相连。输入/输出(I/O)接口705也连接至总线704。
以下部件连接至I/O接口705：包括键盘、鼠标等的输入部分706；包括诸如阴极射线管(CRT)、液晶显示器(LCD)等以及扬声器等的输出部分707；包括硬盘等的存储部分708；以及包括诸如LAN卡、调制解调器等的网络接口卡的通信部分709。通信部分709经由诸如因特网的网络执行通信处理。驱动器710也根据需要连接至I/O接口705。可拆卸介质711，诸如磁盘、光盘、磁光盘、半导体存储器等等，根据需要安装在驱动器710上，以便于从其上读出的计算机程序根据需要被安装入存储部分708。
特别地，根据本发明公开的实施例，上文参考流程图描述的过程可以被实现为计算机软件程序。例如，本发明公开的实施例包括一种计算机程序产品，其包括承载在计算机可读介质上的计算机程序，该计算机程序包含用于执行流程图所示的方法的程序代码。在这样的实施例中，该计算机程序可以通过通信部分709从网络上被下载和安装，和/或从可拆卸介质711被安装。在该计算机程序被中央处理单元(CPU)701执行时，执行本申请的系统中限定的上述功能。
需要说明的是，本发明所示的计算机可读介质可以是计算机可读信号介质或者计算机可读存储介质或者是上述两者的任意组合。计算机可读存储介质例如可以是——但不限于——电、磁、光、电磁、红外线、或半导体的系统、装置或器件，或者任意以上的组合。计算机可读存储介质的更具体的例子可以包括但不限于：具有一个或多个导线的电连接、便携式计算机磁盘、硬盘、随机访问存储器(RAM)、只读存储器(ROM)、可擦式可编程只读存储器(EPROM或闪存)、光纤、便携式紧凑磁盘只读存储器(CD-ROM)、光存储器件、磁存储器件、或者上述的任意合适的组合。在本申请中，计算机可读存储介质可以是任何包含或存储程序的有形介质，该程序可以被指令执行系统、装置或者器件使用或者与其结合使用。而在本申请中，计算机可读的信号介质可以包括在基带中或者作为载波一部分传播的数据信号，其中承载了计算机可读的程序代码。这种传播的数据信号可以采用多种形式，包括但不限于电磁信号、光信号或上述的任意合适的组合。计算机可读的信号介质还可以是计算机可读存储介质以外的任何计算机可读介质，该计算机可读介质可以发送、传播或者传输用于由指令执行系统、装置或者器件使用或者与其结合使用的程序。计算机可读介质上包含的程序代码可以用任何适当的介质传输，包括但不限于：无线、电线、光缆、RF等等，或者上述的任意合适的组合。
附图中的流程图和框图，图示了按照本申请各种实施例的系统、方法和计算机程序产品的可能实现的体系架构、功能和操作。在这点上，流程图或框图中的每个方框可以代表一个模块、程序段、或代码的一部分，上述模块、程序段、或代码的一部分包含一个或多个用于实现规定的逻辑功能的可执行指令。也应当注意，在有些作为替换的实现中，方框中所标注的功能也可以以不同于附图中所标注的顺序发生。例如，两个接连地表示的方框实际上可以基本并行地执行，它们有时也可以按相反的顺序执行，这依所涉及的功能而定。也要注意的是，框图或流程图中的每个方框、以及框图或流程图中的方框的组合，可以用执行规定的功能或操作的专用的基于硬件的系统来实现，或者可以用专用硬件与计算机指令的组合来实现。
描述于本发明实施例中所涉及到的模块可以通过软件的方式实现，也可以通过硬件的方式来实现。所描述的模块也可以设置在处理器中，例如，可以描述为：一种处理器包括路径规划请求接收模块、途经节点确定模块、路径规划模块。其中，这些模块的名称在某种情况下并不构成对该模块本身的限定，例如，路径规划请求接收模块还可以被描述为“用于接收可行驶装置发送的路径规划请求的模块”。
作为另一方面，本发明还提供了一种计算机可读介质，该计算机可读介质可以是上述实施例中描述的设备中所包含的；也可以是单独存在，而未装配入该设备中。上述计算机可读介质承载有一个或者多个程序，当上述一个或者多个程序被一个该设备执行时，使得该设备包括：接收可行驶装置发送的路径规划请求，所述路径规划请求包括所述可行驶装置的起始点位置和目的地位置；以所述起始点位置作为起始的途经节点，利用路径规划算法逐一确定其他各途经节点，直到最终确定出的途经节点为所述目的地位置时不再继续确定途经节点，其中，在逐一确定各途经节点的过程中，将当前途经节点的寻路范围内的各节点中总移动代价最小的节点确定为所述当前途经节点的下一途经节点，所述各节点的总移动代价利用所述可行驶装置的物理运动特性参数计算得到；根据所有所述途经节点得到所述可行驶装置的规划路径。
根据本发明实施例的技术方案，以可行驶装置的起始点位置作为起始的途经节点，利用路径规划算法逐一确定其他各途经节点，直到最终确定出的途经节点为可行驶装置的目的地位置时不再继续确定途经节点，其中，在逐一确定各途经节点的过程中，将当前途经节点的寻路范围内的各节点中总移动代价最小的节点确定为当前途经节点的下一途经节点，且各节点的总移动代价利用可行驶装置的物理运动特性参数计算得到；根据所有途经节点得到可行驶装置的规划路径。在路径规划时充分考虑可行驶装置的物理运动特性参数，避免可行驶装置遇到狭窄和转弯道路而出现行驶困难的情况，减少可行驶装置行驶中的避障次数，提高行驶的安全性，路径实用性能高。并且可以先根据所有途经节点得到第一规划路径，再对第一规划路径进行平滑处理，得到最终的规划路径，使得可行驶装置运动更加符合实际情况，减少了急转、急停现象。
上述具体实施方式，并不构成对本发明保护范围的限制。本领域技术人员应该明白的是，取决于设计要求和其他因素，可以发生各种各样的修改、组合、子组合和替代。任何在本发明的精神和原则之内所作的修改、等同替换和改进等，均应包含在本发明保护范围之内。
