用于在操作环境中优化路线规划的系统和方法

技术领域

本发明一般而言涉及路线规划，并且更具体地与优化路线规划以 处置在操作环境中面临的关键场景相关联，这些关键场景例如碰撞、 最小化拥堵、安全隐患、提高性能(例如，利用率、生产率、自主车 辆的效率、仓库管理工具)等。

背景技术

在狭小空间内为大量机器人规划路线(特别是在多个自主移动机 器人可以一次穿过空间的情况下)尚未得到工业界的认可。机器人解 决方案供应商试图通过设计机器人来迫使机器人遵循特定路线、可预 测地移动机器人(假设它们周围没有任何东西)来处置类似问题。对 于此类系统，不需要太多的路线规划。另外，此类系统无法扩展且无 法与现有仓库设计集成。此类系统面临的问题是重新规划路线变得繁 琐，重新配置在基础设施级别具有挑战性，并且没有障碍物可以干扰 它们。

每当新机器人被添加到此类或任何其它系统时，输入空间都呈指 数级增长；因此，现有系统并没有跟上机器人的增长规模。这种场景 导致组合问题，并且随着机器人规模的扩大，系统变得难以匹配。这 个问题可以与任何类型的自主车辆相关。

发明内容

以下是本文更详细描述的主题的概述。本概述不旨在限制权利要 求的范围。在考虑附图和对那些附图的以下详细描述以及本发明的当 前优选的和其它实施例后，将更容易理解本发明的这些和其它特征。

本文描述的是与优化路线规划有关的各种技术。该系统包括云平 台，其包括多机器人路线规划器。多机器人规划器包括节点解析器， 该节点解析器基于与操作环境(如仓库、建筑工地或医院)相关的输 入来解析一个或多个节点。节点可以被认为是操作环境中的空间的区 域。多机器人规划器包括多个模块，这些模块基于解析的节点规划一 条或多条用于导航的路线。模块可以为关键决策场景分析一个或多个 路线规划，例如避免碰撞或最小化拥堵。在模块分析路线规划之后， 系统利用多机器人路线规划器基于分析来优化路线规划。经优化的路 线规划被分发给一个或多个自主车辆。

本文描述的技术与优化路线规划的健壮云平台相关。在示例性实 施例中，平台利用多个数据结构来表示操作环境、生成路线规划并允 许车辆从一个节点到另一个节点的优化移动。平台提供各种技术来分 析针对关键场景(如碰撞)的一个或多个生成的路线规划。在分析一 个或多个生成的路线规划的同时，平台可以应用试探法、成本函数、 度量等来识别可以避免碰撞的新路线规划。在示例性实施例中，在分 析一个或多个生成的路线规划的同时，当确定节点之间的路线规划之 一会导致冲突时，平台可以动态地创建重复节点。所创建的重复节点 可以被平台用来生成替代路线规划以避免碰撞或使用成本函数来生成 更好的路线规划。

在示例性实施例中，系统或云平台可以利用多种技术或数据中的 一种或多种或其组合，包括速度缩放、上采样、被动路径、可停放节 点、非重叠节点、优先级度量、时间惩罚等，用于分析和优化针对一 次或多次碰撞的路线规划。然后，系统可以将经优化的路线规划分发 给一个或多个自主车辆。

以上概要呈现了简化的概要以提供对本文讨论的系统和/或方法 的一些方面的基本理解。本概述不是本文讨论的系统和/或方法的广 泛概述。它不旨在限制权利要求的范围或不旨在识别主要(key)/关 键(critical)要素或描述此类系统和/或方法的范围。它的唯一目的 是以简化的形式呈现一些概念，作为稍后呈现的更详细描述的前言。

附图说明

关于以下描述、所附权利要求和附图将更好地理解本文所述的具 体特征、方面和优点，其中：

图1是图示根据实施例的用于优化自主车辆的路线规划的计算机 实现的系统的框图；

图2是图示根据实施例的用于分发经优化的路线规划的组件和处 理步骤的框图；

图3(A)-3(E)，各自表示根据实施例的用于优化路线规划的示例 性非限制性表示；

图3(F)是图示根据实施例的在操作环境中的各个节点之间生成经 优化的路线规划的示例性非限制性表示；

图4(A)-4(D)，各自表示根据实施例的在时域和空间域中的轨迹 的示例性非限制性表示；

图5(A)-5(B)，各自表示根据实施例的用于优化路线规划的示例 性非限制性表示；

图6是根据实施例的用于优化路线规划的示例性非限制性表示；

图7是图示根据实施例的用于优化路线规划的处理步骤的示例性 流程图；

图8是图示根据实施例的用于优化路线规划的处理步骤的示例性 流程图；

图9是图示根据实施例的用于优化路线规划的处理步骤的示例性 流程图；以及

图10是图示根据实施例的用于优化路线规划的处理步骤的示例 性流程图。

虽然本发明的具体特征在一些附图中而没有在其它附图中示出， 但是这样做仅仅是为了方便，因为每个特征可以与根据本发明的任何 或所有其它特征组合。附图中的方框或组件的次序不是限制性的并且 可以根据本发明以任何次序互换。上面的附图呈现了对本文讨论的系 统和/或方法的一些方面的基本理解。附图不是本文讨论的系统和/或 方法的广泛概述。它并非旨在识别主要/关键要素或界定此类系统和/ 或方法的范围。它的唯一目的是以简化的形式呈现一些概念，作为稍 后呈现的更详细描述的前言。

具体实施方式

本文描述了提供用于优化自主车辆的路线规划的平台的技术的实 施例。贯穿整个说明书，对“一个实施例”、“这个实施例”和类似短语 的引用意味着结合该实施例描述的特定特征、结构或特点包括在一个 或多个实施例中的至少一个中。因此，贯穿整个说明书在不同地方出 现的这些短语不一定都是指同一个实施例。此外，特定特征、结构或 特点可以在一个或多个实施例中以任何合适的方式组合。

可以利用一种或多种计算机可读介质的任何组合。计算机可读介 质可以是计算机可读信号介质或计算机可读存储介质。计算机可读存 储介质可以是例如但不限于电子、磁、光、电磁或半导体系统、装置 或设备，或前述的任何合适组合。本文讨论的所有系统和处理都可以 在从一个或多个非暂态计算机可读介质读取的程序代码中实施。计算 机可读存储介质的更具体示例(非详尽列表)将包括以下：便携式计 算机软盘、硬盘、随机存取存储器(RAM)、只读存储器(ROM)、 可擦除可编程只读存储器(EPROM或闪存)、带有中继器的适当光 纤、便携式光盘只读存储器(CD-ROM)、光学存储设备、磁存储 设备，或前述的任何合适组合。在本文档的上下文中，计算机可读存 储介质可以是可包含或存储由指令执行系统、装置或设备使用或与其 结合使用的程序的任何有形介质。在一些实施例中，硬连线电路系统 可以代替用于实现根据一些实施例的处理的程序代码或与其结合使用。 因此，实施例不限于硬件和软件的任何特定组合。

计算机可读信号介质可以包括传播的数据信号，其中实施有计算 机可读程序代码，例如，在基带中或作为载波的一部分。这种传播的 信号可以采用多种形式中的任何一种，包括但不限于电磁、光或其任 何合适组合。计算机可读信号介质可以是可以传送、传播或运输由指 令执行系统、装置或设备使用或与其连接使用的程序的不是计算机可 读存储介质的任何计算机可读介质。实施在计算机可读信号介质上的 程序代码可以使用任何合适的介质(包括但不限于无线、有线、光纤 电缆、RF或前述的任何合适组合)来传输。

用于执行本公开的各方面的操作的计算机程序代码可以用一种或 多种编程语言的任何组合来编写。程序代码可以完全在用户计算机上、 部分在用户计算机上、作为独立软件包、部分在用户计算机上且部分 在远程计算机上或者完全在远程计算机或服务器上执行。在后一种场 景中，远程计算机可以通过任何类型的网络(包括局域网(LAN) 或广域网(WAN))连接到用户的计算机，或者可以连接到外部计 算机(例如，通过使用互联网服务提供商的互联网)或在云计算环境 中或作为服务提供，诸如软件即服务(SaaS)、平台即服务(PaaS) 或基础设施即服务(IaaS)或机器人即服务(RaaS)或仓库即服务 (WaaS)或协作机器人(cobot)即服务或其它服务模型。通信可以 扩展到有线和无线通信。

本文参考根据本公开的实施例的方法、装置(系统)和计算机程 序产品的流程图和/或框图来描述本公开的各方面。将理解的是，流 程图图示和/或框图的每个方框，以及流程图图示和/或框图中的方框 的组合，可以由计算机程序指令实现。这些计算机程序指令可以提供 给通用计算机、专用计算机或其它可编程数据处理装置的处理器以产 生机器，使得经由计算机或其它可编程指令执行装置的处理器执行的 指令创建用于实现在一个或多个流程图和/或框图方框中指定的功能/ 动作的机制。就这一点而言，流程图或框图中的每个方框可以表示代 码的模块、片段或一部分，其包括用于实现(一个或多个)指定的逻 辑功能的一个或多个可执行指令。还应当注意的是，在一些替代实施 方式中，方框中标注的功能可以不按照图中标注的次序出现。例如， 取决于所涉及的功能，相继示出的两个方框实际上可以基本同时执行， 或者有时可以以相反的次序执行这些方框。还将注意到的是，框图和/或流程图图示的每个方框，以及框图和/或流程图图示中的方框的组 合，可以由执行指定功能或动作的基于专用硬件的系统或专用硬件和 计算机指令的组合来实现。

这些计算机程序指令还可以存储在计算机可读介质中，当其被执 行时可以指示计算机、其它可编程数据处理装置或其它设备以特定方 式起作用，使得指令在存储在计算机可读介质中时产生包括指令的制 品，这些指令在被执行时使计算机实现一个或多个流程图和/或框图 方框中指定的功能/动作。计算机程序指令也可以被加载到计算机、 其它可编程指令执行装置或其它设备上，以使得在计算机、其它可编 程装置或其它设备上执行一系列操作步骤以产生计算机实现的过程， 使得在一个或多个计算机或其它可编程装置上执行的指令提供用于实 现一个或多个流程图和/或框图方框中指定的功能/动作的过程。

如本领域技术人员将认识到的，本公开的各方面可以在本文中以 多个可专利类别或上下文中的任何一个进行说明和描述，包括任何新 的和有用的过程、机器、制造或物质的组成，或其任何新的和有用的 改进。因而，本公开的各方面可以被实现为完全硬件、完全软件(包 括固件、常驻软件、微代码或其它合适类型的软件)或组合软件和硬 件实施方式，这些实施方式在本文中都可以被统称为“电路”、“模块”、 “组件”或“系统”或“平台”或“装置”。此外，本公开的各方面可以采用 在具有在其上实施的计算机可读程序代码的一种或多种计算机可读介 质(例如，有形、非暂态计算机可读介质)中实施的计算机程序产品的形式。本公开涉及如“用户”、“开发人员”、“设计者”、“第三方”、 “仓库所有者”、“机器人解决方案提供者”等术语，并在若干或特定实 施例中使用，但是，这些术语不限于那些特定实施例并且可以由(一 个或多个)其它术语代替，因为本发明不受这些术语的限定或限制。

设备是具有唯一标识符和通过互联网传输数据的能力的物体或物 理实体。在一个实施例中，设备是物联网(IoT)中的“事物”。在 IoT语境中，事物是指具有唯一标识符、嵌入式系统和通过网络传输 数据的能力的实体或物理物体。这些设备可以包括物理设备、家用电 器、车辆、边缘设备、雾化设备等。该设备还包括可以执行致动和感 测以及其它设备功能的机器人。

应该理解的是，本发明参考可互换并且可以互换地在一个或多个 实施例中使用的各种术语。例如，术语“节点”可以与“连接点”或“树 元素”或“图形元素”互换，而对本发明的范围或实施方式没有任何改 变。这种互换可以不被认为是限制性的并且这种互换被认为在本发明 的范围内。在一个实施例中，应该理解的是，自主车辆可以被称为运 行环境中的节点，使得自主车辆可以是停在节点处、在节点处等待、 经由节点行驶、停在节点处、在节点处完成导航等中的一种或多种。 还应该理解的是，术语“路线”、“路线规划”、“轨迹”、“行驶规划”、 “导航规划”等可以指示相同的术语并且根据用例场景在不同的地方使用。应该理解的是，一个或多个处理步骤的执行导致作为处理步骤的 执行结果的输出。例如，基于操作环境中解析的节点来规划一个或多 个路线规划的处理步骤可以导致输出至少一个或多个生成的路线规划 的输出。基于分析优化生成的路线规划的处理步骤可以导致输出，从 而至少导致经优化的路线规划的生成。类似地，基于第一自主车辆的 识别出的优先级值对来自生成的路线规划的路线规划进行优先化的处 理步骤可以导致至少一个或多个优先化的路线规划的输出。

图1是图示根据实施例的用于优化自主车辆的路线规划的计算机 实现的系统的框图。在一个实施例中，系统100的目标是应用尽力而 为方法来最小化冲突并尽可能采取措施以避免冲突。系统100可以包 括一个或多个处理设备和存储设备，该存储设备包括由处理设备执行 的用于优化路线规划的计算机可读指令。系统100包括云平台110， 其可以被视为具有/没有用户直接主动管理的计算机系统资源的按需 可用性。云平台包括一个或多个处理器和存储器，以生成并存储路线 规划或轨迹。在一个实施例中，云平台110包括用于存储路线规划或 轨迹以及用于生成路线规划的相关数据的数据库111，如在此讨论的。在一个实施例中，相关数据可以是自主车辆状态信息、统计数据，与 导航、遍历树或图、前提条件、路线表等相关的其它信息。云平台110包括多机器人路线规划器(mrrp)112，它包括一个或多个处理 器和存储器，以执行与优化路线规划以避免碰撞相关的主要任务。在 一个实施例中，mrrp 112可以充当用于执行与路线规划相关的各种 任务的服务器、系统、等效设备、软件或硬件组件。出于表示和简单 的目的，mrrp 112已被示为云平台110的模块。但是，mrrp 112可 以充当与路线规划相关的任务所涉及的任何其它系统或平台的组件。云平台110包括调度器113，其主要功能是任务指派并且决定哪个自 主车辆或自主设备应当在特定时间执行特定任务。调度器模块在通信 层160上将与任务相关的细节传达给知道目的地和在给定时间要执行 的任务的一个或多个自主设备。然后自主设备被编程为经由通信层 160与mrrp 112交互。系统100还包括仪表板120，其可以被用于接 收输入，如障碍物地图、图形、树结构、任何其它相关输入，并用于 显示地图、表示(如图形、树、模拟环境等)。仪表板120可以包括 UI 121、模拟器122和设计器123，用于与多机器人路线规划相关的 各种功能和与自主车辆功能相关的其它任务(如指示自主车辆从地图 或UI上的一个地点移动到另一个地点等)。UI 121可以被用于接收 障碍物地图或与路线规划相关的其它输入。模拟器122提供模拟环境， 该环境包括地图以表示操作环境中自主设备的导航路径。操作环境可 以包括仓库、医院、建筑工地、办公室、造船厂(dockyard)、船厂 (shipyard)、道路、铁路等。模拟器122还可以被用于指示自主设 备执行某些任务以优化路线规划以避免碰撞。指令之一可以包括提供 会比另一个车辆更多地影响一个车辆的导航优先级或参数等。设计器 123可以提供设计环境来编辑输入(如障碍物地图)，并提供定制的 状态信息(例如，输入，如在特定时间的动态碰撞的可能，例如，在 特定时间或日期基于该特定时间或日期的交通状况某些自主设备(如 无人驾驶汽车)到达交通路口)。输入或指令可以由仪表板120的任 何组件或系统100的其它组件(例如，仓库管理系统(WMS)/仓库 控制系统(WCS)130)提供。WMS或WCS 130可以由仓库管理员 /操作者处置并且系统100的其它组件可以或者可操作地耦合或者嵌 入在WMS/WCS 130中。在一个实施例中，WMS或WCS 130可以 被配置为与云平台100的组件接口以用于与自主车辆协调并生成多机 器人路线规划。各种外部或内部组件的耦合可以经由业务逻辑层140 或通信层160或通过任何其它非限制性的通信手段。该系统支持类似 或异构的自主驾驶车辆，如自动叉车171、乌龟机器人172、手臂173、 自动卡车174、拣选机器人175、无人驾驶汽车176、受让人的拣选辅 助自主移动机器人(AMR)177等。业务逻辑层140可以被定制以允 许客户或其它利益相关者对于定制的机器人解决方案集成他们的机器 人软件或硬件。系统100包括外部设备150，如移动机架、自动机、 区域传感器等。

一般而言，当自主车辆X必须从源节点A行驶到目的地节点B 时，该解决方案可以要求另一个自主车辆Y让路给自主车辆X以到 达目的地B。这样的场景没有解耦。为了实现用于自主车辆X的解决 方案，自主车辆Y必须让路，因此，由于这种依赖性，问题没有解 耦。当这种依赖性对于在操作环境中导航的其它车辆进一步扩大时， 这种情况会进一步加剧。但是，该系统使用了一种方法，该方法使用 其它自主车辆让路给车辆X的效果来避免解耦问题。通过将问题定位 到车辆X或个别自主车辆来处置计算。

在一些场景中，仓库中的过道可能太窄或空间受限。本系统不是 指示自主移动设备由于空间受限而无法在过道中导航，而是使用了一 种新颖且不同的方法，其中输出始终是最大努力并提供解决方案。

在一个实施例中，路线规划问题的方法之一可以是碰撞最小化问 题而不是令人满意的解决方案。该系统最小化碰撞和行驶时间，并且 在设计解决方案的同时将碰撞视为参数而不是将碰撞视为约束。在这 样的场景中，输出路线规划可能发生冲突。系统将具有冲突的输出视 为有效输出。对于有限自主车辆，这个解决方案可能显得微不足道。 但是，随着系统随着自主车辆的增加以及每辆车的决定取决于另一辆 车的路线规划而扩展，整体输入空间和决策制定呈指数级增长。于是， 场景变成更高级别的问题，以最小化整体冲突。然后，系统会尽最大 努力为每个场景提供输出。

可以存在事物可能不按照仓库实体(例如，仓库经理)的规划进 行的场景。在一个实施例中，将机器人视为自主车辆。例如，可能不 按规划进行的事物可以是机器人的故障、动态障碍物、机器人减速、 机器人特性的不准确表征、机器人速度的不正确估计、一个或多个机 器人是否可以适应某些地方或空间对于机器人导航来说是否太小或受 限等。系统可以提供元策略来解决上面提到的场景。例如，假定存在 不可能的场景，如由于多个机器人在特定区组装而造成的阻塞。在那 种情况下，系统可以将其中一些机器人从那个区移动到其它仓库区。 被移动的机器人可能无法在特定时间完成任务。但是，系统的决策解 决了与该不可能场景相关的问题(由于多个机器人造成的阻塞)并生 成尽力而为的解决方案。

消息是包括类型化字段的数据结构。每个消息具有消息类型，例 如可以是整数、浮点数、布尔值等。系统和自主车辆可以使用任何通 信机制来接收或发送消息。例如，通信机制可以是用于从云平台向自 主车辆发送和接收消息的发布者-供应者通信机制或请求-应答通信机 制。ROS(机器人操作系统)提供可以被用于发送或接收消息的三种 通信机制：话题(发布者-订阅者通信机制)、服务(请求-应答通信 机制)和动作(目标、反馈、来自通信模块的结果)。每种通信机制 被用于发送消息。它与通过通信机制发送的消息的消息类型绑定，并 且接收者只能接收与那个消息类型对应的消息。例如，当发送者在 “机器人名称”话题上发布“字符串”类型的名称消息时，订阅“机器人 名称”话题的订阅者只能接收“字符串”类型的消息。

存在可以应用本发明的多种场景。本发明可适用的主要领域之一 可以是在任何种类的动态或静态环境中为任何异构自主车辆进行路线 规划，如受让人的名为“Sootballs”的自主移动机器人或者自动叉车或 者自主汽车或无人驾驶汽车等。可以应用本发明的其它领域可以包括 多个机器人在操作环境中导航。正在导航的机器人可以广播它们的路 线细节，该细节可以被系统用来规划路线。因此，该系统启用混合执 行模式，其中在执行阶段在操作环境(如仓库)中导航的机器人向系 统提供与路线相关的细节，而对于其它机器人中尚未开始导航过程的 一些而言可能处于规划阶段。然后可以与其它机器人共享新规划的路 线，以最优使用系统的各种模块并使用由导航机器人接收到的新路线相关细节来重新计算更好的路线。该系统还可以基于多种因素进行定 制，例如，操作环境的动态程度等。本发明不限制或局限于移动机器 人，例如，如连杆机械手之类的设备也可以在其它自主车辆的操作环 境中发挥作用。连杆机械手的两个臂在执行多个不同的任务的同时可 能需要确保臂在执行功能时不彼此碰撞。本发明本质上是非限制性和 通用的，并且可以不限于机器人，而是可以应用于需要在一个或多个 轨迹中避免碰撞的环境中。系统可以被定制，其中碰撞可以被重新定 义，例如，可以存在可以要求确切的计算和高度准确性以实现导航的 环境。

已经基于2D环境描述了系统，但是，这不是限制，并且系统可 以被扩展到3D环境。系统内可以要求的改变包括距离计算，它可以 具有附加维度Z轴。由于数据结构的重点是节点而不是几何维度，因 此本发明本质上是通用的和非限制性的，并且可以包括附加维度而除 了包括附加维度相关信息之外没有任何显著改变。

图2是图示根据实施例的用于分发经优化的路线规划的组件和处 理步骤的框图。异构自主车辆的车队可以包括机器人或真空吸尘器。 在一个实施例中，操作环境可以是仓库。障碍物地图201是从数据库 111或来自仪表板120的任何组件导入的仓库的地图。障碍物地图是 包括特定区域中各种障碍物和自由空间的细节的地图。例如，在仓库 中，障碍物地图可以包括仓库内的货架、通路、墙壁等的细节。障碍 物地图201可以被转换成图片或图像以对障碍物地图图像进行处理。 在一个实施例中，与图像一起生成障碍物地图元数据，包括障碍物地 图中包括的障碍物的细节。在图2中，圆圈表示数据，而框表示处理。 数据可以是输入、输出或在流中传递的数据，而框可以实现执行特定 任务所涉及的步骤。初始步骤是了解仓库的布局。这可以以至少两种 形式实现：a)CAD绘图-这类似于建筑物的设计，提供部署建筑 物的各种表示的蓝图，包括墙壁、板、柱等的位置。类似地，障碍物 地图是仓库的地图，包括仓库中的静态障碍物，并且是驱动机器人、 使用机器人的激光扫描仪扫描仓库的结果。输出可以是设计者123可 以拼凑在一起以获得位图图像的多次激光扫描。位图图像给出与障碍 物的地点、存在或不存在相关的信息。设计器123是用于从激光扫描 中去除寄生噪声的软件模块。这个清洁步骤有助于勾勒出仓库中的不 同区，并获取与仓库中静态障碍物的地点、尺寸等相关的细节。由于 这个阶段是初始规划处理，因此重点始终放在静态障碍物上。在初始 规划阶段，系统可能无法处置动态障碍物(例如，突然出现在机器人 的路径中的人)。但是，如果这种信息在初始规划阶段可用，那么在 开发障碍物地图的同时也可以考虑这种信息。然后障碍物地图201被 传递到地图生成器模块211上。地图生成器模块211接收障碍物地图 201作为输入并转换成离散形式，诸如图形。该图形包括表示自由空 间的区域的多个节点。连接节点的每条边表示机器人可以移动通过的 具有一定量空间的通路。功能空间的这种主要表示有助于更快的遍历 并简化整体方法。在该图形中，边也有空间约束，其指示路径的宽度 或窄度。假设是如果机器人太大而无法移动通过通路，那么规划处理 可以认为机器人无法通过它。可替代地，在规划阶段，如果路径大到 足以让多个机器人同时通过它，那么该信息使系统不会将该场景视为 碰撞。

在一个实施例中，所生成的图形202现在被递送到节点解析器模 块212。为了理解节点解析器模块，需要理解图包括节点并且节点是 空间中的离散点。但是，对机器人的请求不是离散的，而是连续的 (x，y坐标)。只有当机器人从一个节点开始并在一个节点上结束 时，路线规划器才起作用，但是如果机器人在节点之间开始并在节点 之间结束，那么将是困难的。因此，节点解析器的作用是在输入不一 致或无效的情况下弥合间隙。节点解析器模块执行连续到离散映射的 步骤，从而识别哪个机器人从哪个节点开始。系统为节点解析器模块 寻找多种方式来解析节点的定位场景。在大多数情况下起作用的最容 易和通用的解决方案是基于欧几里得或勾股定理种类的距离关联与机 器人当前位置最接近的节点。但是，在一些情况下，这种解决方案可 能不起作用，例如，考虑没有出口并且空间狭窄只能让一个机器人通 过的走廊的简单场景。走廊可以包括一排多个节点。现在，考虑有一个机器人位于节点左侧的位置，而另一个机器人位于节点右侧的位置。 因此，如果应用最近距离解决方案，那么两个机器人都可以被映射到 同一个节点，但是，实际上，机器人有点偏移，一个在节点的左侧， 另一个在节点的右侧。在这个假设下，如果机器人被指示去走廊的另 一端但去往相同的地点，那么这种输入查询会被认为是不可能的输入 查询。这个输入查询被认为是不可能的原因是两个机器人都必须从同 一个源开始，经由单车道走廊并到达同一个目的地。因此，假设如果 要执行这个查询，那么目的地节点将完全是同一个地方，并且通过最 近距离解决方案，两个机器人的起始节点将完全相同。因此，系统分 析路线规划并且发现有两个对称的机器人，都从同一个地点出发并到 达同一个目的地，可能会发生碰撞。因此，对于这些机器人，路线规 划器的功能就是找到满足这些条件且碰撞次数最少的路线。

在一个实施例中，基于分析，系统生成最优路线规划作为解决上 面提到的场景的解决方案，这可以是允许第一机器人首先离开源到达 目的地，然后允许第二机器人在第一个机器人从源地点移动后离开。 这将导致第一机器人到达目的地，第二机器人尾随其后。这可以被认 为是路线规划器或系统生成的最佳解决方案。但是，挑战在于起动请 求是对称的但输出是不对称的，一个机器人成为领先机器人而另一个 机器人落后。因此，在此类情况下，系统必须识别解决方案以解决不 对称场景。为了解决这种不对称场景，系统分析路线规划并随机挑选 一个机器人，并让那个机器人先走。在实时场景中，系统做出的这个决定很重要，因为物理上落后的机器人可能会被选中先走。如果是这 种情况，那么这在物理上是不可能发生的，因为物理上出现在前面的 另一个机器人不能只是翻转位置，因为走廊可能没有那么多空间并且 会导致死锁状况。因此，为了解决这种情况的发生，节点解析器模块 212具有关键任务。系统基于分析做出决定，并将机器人指派给起始 位置，主要是基于最近距离，但是在一些场景中，可以存在需要解决 的争用。如果多个机器人竞争最近节点，那么两个机器人无法物理上 到达同一个节点，因为这会导致碰撞。因此，系统通过指示一个机器 人去另一个离起始节点不近而是可能更远的节点来优化路线规划，并 且节点解析器必须以这样一种方式将节点指派给机器人，使得移动可 以在物理上完成，这意味着没有纵横交错否则可以要求机器人去其它 有足够空间的地方。节点解析器212对节点的这种指派必须是操作环 境内的有效配置。节点解析器的这个任务会变得复杂，因为节点可以用任意量的空间重新定义。因此，对于可行的解决方案，如果存在具 有足够空间(比如用于十个机器人)的节点，那么节点解析器可以指 派多个可能适合这些节点的机器人。但是，如果有二十个机器人，那 么节点解析器可能由于空间约束和死锁问题而不得不将那些附加的机 器人设置到不同的节点。在为机器人解析节点之后，输出与接收到的 路线请求203相同，但进行了离散化。因此，现在代替与开始和结束 位置的协调，节点解析器模块212的输出可以包括指派给机器人的节 点。

在一个实施例中，节点解析器模块212可以采用至少两个输入- 图形202和关于机器人想要在哪里导航的路线请求203。系统被设计 为使用多种方法进行优化-系统可以在一个请求实例中处理针对所 有机器人的请求，或者可以一次处理每个机器人的请求。默认情况下， 除非被覆盖，否则系统可以将输入作为路线的批量请求。机器人的路 线请求可以是起点A和目的地点D的2D坐标(x，y)的形式，并且 可以包括多个通过点，例如B和C。因此，机器人的路线请求可以指 示机器人可能想从点A出发，然后访问点B，然后访问点C，然后到达目的地D。这些路线请求可以由包括信息(如机器人的当前地点、 机器人的任务等)的web用户界面输入。用户(例如，仓库管理员、 操作者、开发人员、设计者等)可以在web用户界面上选择机器人， 并且可以指示机器人停止正在执行的所有任务并请求机器人前往特定 目的地。这可以是让机器人在仓库中导航或自主地在仓库中导航的一 种方式。在一个实施例中，可能没有人工干预并且机器人智能地决定 他们必须导航到哪里。

在一个实施例中，为了控制机器人的自主行为，可以提供分离的 用户界面，其中根据应用需求，例如，在仓库中的工作班次之前(例 如，上午9点时隙或晚上6点时隙)，仓库操作者可以提供任务列表， 其包括要从仓库的各个过道或区中挑选然后投放到目的地点的物体。 这也可以以任何文档格式(例如电子表格格式(input.xls文件))输 入到系统中。

在一个实施例中，在节点解析器模块212解析用于机器人车队的 节点之后，输出与多路径树搜索(MPTS)模块213共享。MPTS模 块213可以参与为机器人车队分析路线规划和优化路线规划。用于机 器人的路线规划包括从特定点出发并避开其它机器人向目的地点移动。 静态障碍物已经在预处理阶段由地图生成器模块211负责(take care)。路径搜索模块214与MPTS模块213并行工作以帮助生成路 线规划、分析路线规划、优化路线规划或路径轨迹205。例如，用于 第一机器人220的路线规划可以包括不考虑其它机器人的正常路径搜 索。作为路线规划的分析的一部分，在为相继机器人(机器人230和 机器人240)规划期间，路径搜索模块214比较在前机器人的轨迹或 路线规划(例如，在这种情况下，机器人220的路线规划)并规划避 开在前机器人的路线规划的一条或多条路线，同时优化到达目的地的 行驶时间。在图2中以及如此处所描述的，为了简化和理解目的，仅 考虑了3个机器人。但是，本发明对于自主车辆的数量和自主车辆的 类型没有限制。本发明支持异构自主车辆的车队，例如图1的不同类 型171-177的自主车辆。

在一个实施例中，一旦生成路线规划，则用路径协调器204登记 路线规划。路径协调器204包括中央数据库或路线规划的日志并且被 用于跟踪先前规划的路线。路径协调器204还可以包括用于冲突检查 和解决与规划的路线相关的查询的计算逻辑。路径搜索模块214一次 扩展一个节点。因此，当路径搜索模块214遍历从一个节点到另一个 节点的路径时，涉及进行测试以检查路径遍历期间冲突的可能性。因 此，对于这些测试，对于每个相继的机器人向路径协调器204发出查 询以检查在前机器人的规划。其它模块也可以查询路径协调器204以 快速查找路线规划。这有助于系统优化不会与先前的路线规划冲突或 可以建立在现有路线规划之上的路线规划。当路径搜索模块214的另 一次迭代发生时，系统利用路径协调器204来分析已经规划好的先前 路径，然后除了现有的登记的规划之外还规划新的路线。因此，路径 协调器204包括记录正在规划的相继路径的历史和跨度并且还负责与 先前规划的路径的碰撞检查的数据结构。路径协调器204可以包括路 径和路径的统计数据的树状分层数据库。可以理解的是，也可以使用 像堆栈这样的其它表示。为了避免碰撞，系统可以找到为在前机器人 规划的潜在碰撞轨迹并避开它们。因此，路径协调器204的主要任务 是响应或回答查询，例如，如果机器人穿过从源点到目的点的路径， 那么对于在前机器人，在沿着源点和目标点之间的通路已经规划的所 有轨迹上是否存在碰撞的可能性。

在一个实施例中，MPTS模块213主要确定机器人车队的路径或 路线规划的排序。如果存在其它机器人的已知轨迹，那么MPTS模块 213执行优化步骤，在基本级别确定哪个机器人可以让步于(一个或 多个)其它机器人以及哪个机器人可以具有更高的优先级值。MPTS 模块213可以通过识别可以首先被移动的机器人来解决这个问题，并 且维护关于总行驶时间、遇到的碰撞总数等的统计数据。MPTS模块 213利用路径协调器204作为存储结构，用于存储上面提到的信息。 此外，路径搜索模块214的输出被附加回路径协调器204的树状分层 数据库。系统通过从根节点到叶节点遍历树来核实规划的排序是否最 优，并且单次遍历可以包括给出碰撞计数、路径时间、成本函数等的 估计的路径的集合。多路径搜索模块213和路径搜索模块214的并行 处理的输出是路径轨迹205的集合。输出就像针对每个单个请求的地 点和时间序列，在此详细表示。作为轨迹的集合的输出可以包括附加 信息，例如，如果碰撞一定会发生，那么碰撞中可以涉及的特定机器 人、哪个机器人正在与另一个机器人发生碰撞，以及碰撞可能发生的 时间、碰撞可能发生的路线、预期的行驶时间、其它统计数据等。对 于每个机器人，都有与节点和时间序列相关的信息。系统还可以包括一些可以被被动转换的任务，这也是输出信息的一部分，例如，一些 机器人可能无法导航到其路线规划指示的特定节点，但是，为了避免 碰撞，系统可以迫使机器人去其它地方。大部分计算发生在MPTS模 块213和路径搜索模块214的组合树搜索中，并且问题空间随着机器 人的数量呈指数级增长。

在一个实施例中，路径轨迹205的集合被传递到前提条件生成模 块215上。前提条件生成模块215的主要目的是将轨迹作为输入，从 中去除时间元素，并提取路径规划的次序。对于空间的每个区域，机 器人的预期访问都按时间排序。例如，第一个要稍后访问特定地点的 机器人需要等到之前访问该地点的第二个机器人移动，然后第一个机 器人才能进入。这是链依赖的示例，其中第一个较晚到达的机器人必 须等待较早到达的机器人离开，然后第一个机器人才能进入。在此， 代替时间戳，前提条件生成模块215利用路径排序来解决碰撞避免场 景。

在现实生活中，机器人不一定像预期的那样快。在一个实施例中， 前提条件生成模块215通过在前提条件生成阶段转换时间戳来吸收时 间变化。前提条件生成模块215确保系统对时移中的干扰具有相对稳 健性，但前提条件生成模块215无法解决一些极端问题，如当机器人 发生故障和该机器人后面的其它机器人停顿时。系统一般面临一些问 题，例如，如果一个机器人无限期停顿，并且如果其它机器人正在等 待该停顿的机器人，那么所有其它机器人也会无限期地停顿。机器人 可以出于各种原因停止移动，如系统错误，于是系统识别一种或多种 解决方案，包括重新规划路线，其中停顿的机器人可以将该地点识别 为被阻塞，以便其它机器人可以被重新路由远离被阻塞的地点。前提 条件生成模块215的流程也可以用示例来解释：-考虑必须导航到节 点1、节点2和节点3的机器人220，并且节点2上可以存在直到另 一个机器人230已经通过其第五个检查点时机器人220才能去该节点 2的前提条件，其中机器人230的第五个检查点可以是节点2。基于 这个分析，前提条件生成模块215然后生成前提条件输出，更新、重 新规划或优化除非机器人230通过节点2机器人220不能前往节点2 或可能必须等待的路线规划。

在一个实施例中，在前提条件生成模块215生成前提条件之后， 将前提条件包括在路线表206中。路线表206与机器人车队(例如， 机器人220、230和240)接口。路线表206包括连续坐标形式的信 息，而不是现实生活中的离散节点。系统将离散化的节点转换成连续坐标，从而导致开始和结束节点被覆写。但是，机器人的起点和目的 地已经在路线请求中指定。一旦执行离散化过程，进入搜索，系统就 分析机器人的状态并在节点解析器模块212的帮助下改变节点的位置。 在分析先前路线时，系统用原始请求中指示的位置替换节点，例如原 始开始和结束位置现实生活坐标。所有中间点可以正好在节点的位置 上。只要识别出开始和结束位置用于分析，中间点是什么都没有关系。

在一个实施例中，一旦生成了路线表206，就将各个路线分发到 所有机器人；例如，在图2中，单个路由可能会指派给3个机器人— —220、230和240。每个机器人都会收到自己的路线，可能不需要知 道其它机器人的路线。路线表被拆分并发送到各个机器人。可能有任 何形式的通信过程可以用于向单个机器人发送路线。示例之一可能是 以消息的形式向机器人发送路由。每个机器人有两个模块，路由同步 模块和本地导航模块；例如，机器人220具有路线同步模块221和本 地导航模块222。路线表206被发送到机器人220内的组件路线同步 221、路线规划器或系统的本地扩展。路线同步模块221在机器人220 本身上运行并且作为分布式系统的一部分运行。每个机器人在自己的 车辆上运行一个版本的路线同步模块。在一个实施例中，来自协调机 器人的中央服务器的输入可能有限，并且本地模块可以处置协调和导 航。机器人之间相互协调，同步对分发给它们的路线的遵循。路线同 步模块监听其它机器人的路线进展，以根据前提条件的约束来确定机 器人下一步应当去哪里以及允许机器人在自己的路线上走多远。一旦 做出决定，路线同步模块就将机器人应当前往下一个路线点的这个信 息中继到本地导航模块。然后机器人开始移动，同时，本地导航模块 可以提供关于机器人认为机器人在导航空间中的位置的反馈。共享的 位置是现实生活中的坐标，并且随着路线的进行，坐标被转换回来。 因此，在较低级别，本地导航模块保持跟踪地图上的当前位置。相比 之下，在更高级别，系统保持跟踪机器人在路线上的位置，例如机器 人是否通过了第一个检查点或第二个检查点等。基于机器人在地图上 的位置确定路线进展的处理在路线同步模块中完成。路线同步模块的 功能是–监听其它机器人的路线进展，确定机器人应当去哪里，并 将那个信息中继到本地导航模块以前往该位置。同时，基于来自本地 导航模块的反馈，从生成的最优路线规划中计算其自己的路线进展并将其发送给其它机器人。其它机器人有自己的路线同步模块和本地导 航模块，并且它们执行与第一个机器人相似的任务。

在一个实施例中，系统可以是灵活的并且从机器人获取反馈以改 进路线规划。从系统到机器人的双向指令可以是消息通信的形式。在 实时场景中，仓库的环境条件会不断改变。如果地图是几天前基于环 境的激光扫描准备的，那么有可能一些静态物体可能已经移动，或者 机器人可能会在今天遇到新的障碍物。在某些情形下，系统可以允许 每个机器人的路线同步模块和本地导航模块做出决定，如在新的障碍 物进入它们的通路时在特定地点等待。决定可以被分为多个类别：例 如，如果障碍物是人，那么机器人可能等待；但是，如果障碍物是如 桌子或盒子之类的物体，那么机器人知道那些物体是静态障碍物，因 此可以绕着障碍物移动。如果障碍物是新信息，那么障碍物相关信息 被中继回mrrp模块。路线同步模块和本地导航模块不断将这个信息 作为反馈回路发送回mrrp模块或系统，以进一步改进路线规划的生 成。而且，路线规划是更保守的处理，因此，在规划阶段期间，有时可以指示机器人避免由于过道狭窄而移动。但是，路线同步模块和/ 或本地导航模块可以提供反馈；例如，过道的宽度可能足够宽以供行 驶。因此，在一些情况下，机器人可以沿着路径行驶，而这条路径可 能早先被排除在外。系统将这种信息视为如已在本地获得的信息那样 准确并指示机器人的当前状态、环境等。系统在此类场景中做出决定， 考虑所有因素，并可以允许机器人行驶。

在更高级别，系统必须决定何时必须进行重新规划；例如，地图 的描述有时与现实生活中的描述不一致。由于这种与仓库现实环境的 不一致，在规划时，有可能可以考虑到机器人有足够的空间行驶；但 是，在现实生活中，空间可能对机器人不足。在此类情况下，系统动 态地分析某些通路被阻塞的位置，然后优化规划以避免这种情况。因 此，系统重新规划路线并将那些被阻塞的通路视为不可行驶。随着条 件的改进，这些约束可以在以后被移除。此类因素可以迫使系统优化 或重新规划，并使机器人能够采取替代路径到达目的地或避免碰撞。 在一个实施例中，系统可以优化路线并且分发给机器人的规划的路线是前瞻性的。已经考虑所有可能的潜在碰撞规划了路线。因此，如果 机器人遵循交给他们的路线图走，那么就不会发生任何碰撞。

在一个实施例中，树的每个单个节点都包含关于遍历树中该节点 的统计数据的信息。树的每个节点存储为该节点规划的整个轨迹。此 外，与路径一起，存储在节点上的其它信息是与轨迹相关的统计数据。 这些保持在节点中的轨迹稍后被识别为任何新轨迹的先前规划的轨迹。 存储在树的每个节点中的数据包括路径、路径的统计数据(如错误代码、总行驶时间、碰撞次数等)。数据还包括可以手动指定或由系统 基于包括碰撞次数、被动计数、优先级偏置等的成本函数计算的值函 数的结果。数据还可以包括访问计数(访问计数被用于平衡探索访 问。)在发生碰撞的情况下，数据可以包括碰撞的细节，如谁与谁相撞，在什么时间，在路线中的什么点，等等。

在一个实施例中，图形202(例如有向图)以具有带有多个特性 的节点。图形202的特性之一是不可停放节点。可以理解的是，不可 停放节点可以是仓库中系统或路线规划者可能不希望被交通阻塞或堵 塞的关键连接点。此类连接点经常被使用，并且会减慢机器人的速度。 此类连接点可以被指示为禁止停车，这表明机器人不能在那里等待或 停在那里或去那里作为目的地。此类节点可以被称为不可停放节点。 这个特性对于处置多个机器人可能在关键连接点堵塞的情况是有用的。 然后这个特性被系统用于强制指示机器人不应当在此类目的地停车、 等待或停止。系统可以要求机器人移动到可能没有任何系统或仓库相 关问题(如关键连接点)并且可以被机器人停放的不同节点。可以理 解的是，系统在应用图形的此类特性之后更新、重新规划或优化路线 规划，或者用于处置在仓库中导航时遇到的复杂场景。

在一个实施例中，系统启用图形202的与为没有任何目的地的机 器人规划路径相关的另一个特性。此类路径被称为被动路径，即，没 有任何目的地的路径。例如，在此类路径中，最终目标的定义不仅仅 是单个地方，而是任何地点都是可能的。图形202的这种被动路径特 性使系统能够允许机器人采取最短转移或移动以避免碰撞。系统可以 分析，如果第一机器人试图通过第二个机器人的通路，那么可以优化 路线规划以包括指示第二机器人从该路径移开以避开第一机器人并允 许第一机器人通过。但是，假定分析指示没有其它机器人正在通过第 二机器人的通路。在那种情况下，可以优化路线规划以包括第二机器人坚持原始路径，因此，可能不需要第二机器人从通路移开。

在一个实施例中，如果路径是被动的并且存在不可停放节点，那 么在一些场景中，系统可以优化路线规划以不允许在被动路线上行驶 的机器人以不可停放节点作为目的地的目标。考虑与防火门相关的安 全场景。当火警响起时，系统自动关闭防火门，并指示所有系统组件 停止所有任务并移至空闲状态。但是，在此类关键场景中的担忧之一 可以是，由于系统发出停止指令，机器人可能刚好停在那些防火门下。 这会导致防火门被堵塞，并且门可能无法关闭，这会导致火灾隐患， 这被认为是关键风险。这种场景也会对机器人造成损坏。系统分析仓 库关键场景的路线规划，并且当机器人到达非停车节点时，将与防火 门重合的节点标记为禁止停车。然后基于分析优化路线，并且机器人 请求被动路线而不是停止。如果机器人位于可停放节点，那么机器人 中止并停留在它们所在的位置。但是，如果机器人不在可停放节点， 那么机器人将移动到最近的可停放节点。系统启用路线规划的优化生 成以处置关键场景。关键场景可以包括碰撞、火灾隐患、交通堵塞、 损坏、安全隐患、可以影响仓库或机器人的生产力、利用率、效率的 性能等。在一个实施例中，考虑一个场景，如一小时销售、黄金日 (Prime day)销售或折扣日销售，仓库中机器人的性能影响业务。 因此，机器人在此类时间段期间的性能可以被视为关键场景。

在另一个实施例中，系统基于图特性(如被动路径和不可停放节 点)来分析路线规划。系统可以使用与避免拥塞问题相关的技术之一。 系统应用试探法来解决拥塞。试探法是在地图中识别交通可能繁忙的 节点并将该节点指定为不可停放。基于试探法分析，系统可以优化路 线规划以不包括在那些不可停放节点处停止或等待。随着自主车辆在 不可停放节点处汇聚，系统更新、重新规划或优化具有被动路径的路 线规划以绕道而行，而不是在那些节点停止或等待。系统避开阻塞通 路并采取预防措施，以免车辆造成拥堵。

在一个实施例中，系统基于图特性(如非重叠节点)来分析路线 规划。当设计图时，机器人必须在节点中等待。因此，假设图中的节 点不能重叠。每个单个节点都具有定义由该节点占用的空间量的特性。 例如，将节点的表示视为几何形状，圆形。可以理解的是，如果在第 一节点中的某处有机器人，而另一个机器人在第二节点中的不同位置， 那么被那些区域占据的空间不重叠。因此，节点不重叠。系统假设， 如果机器人到达节点，那么机器人在节点内并且不干扰其它节点中的 其它机器人/人。这是个避免碰撞的假设，使系统的任务更简单。这 有助于系统更高效并避免扫描其它节点。系统认为在节点内等待的机器人不会干扰在它周围移动的其它机器人。因此，这要求节点不能与 操作空间中的其它节点重叠。

在一个实施例中，地图生成器模块211的输出可以是表示的形式， 例如，其中节点在空间上不重叠的图形202。系统仍然可以尝试最大 化节点的放置，使得最大程度地利用空闲空间。为了绘制精细的轨迹， 图形有必要在空间上进行详细说明并将节点更靠近地放置在一起。这 会违反节点间距假设，但是，图形的重叠节点特性有助于增大这个问 题。因此，每个节点具有指定与所述节点重叠的其它节点的细节的特 性。因此，在碰撞检测中，如果多个机器人同时处于同一片段或节点 中，并且如果它们的尺寸之和超过那个节点中的空间，那么可以认为 是碰撞。在重叠节点特性中，机器人可能不仅占据特定节点，而且还占据可以与该特定节点重叠的其它节点。系统针对各种特性分析路线 规划并优化路线以避开相邻节点和机器人可能定位在其中的其它节点 中的碰撞。

在一个实施例中，本发明支持异构自主车辆，如机器人。考虑下 面的路线请求表和轨迹的示例输出，例如，要遍历哪些节点、什么时 间等。这就像空间和时间对，并且可以发生在前提条件生成步骤之前。 轨迹是路线规划器的原始输出。考虑有两个机器人A和B，具有以下 输入细节：可以理解，节点信息仅为了理解和表示目的而提供；但是， 直到节点解析器模块没有被激活，节点信息才对系统可用。

表1：路线请求

在表1中，输入请求包括：机器人A在时间0在与仓库中的节点9对 齐的(x,y)＝(90,0)坐标处开始，并且在与节点19对齐的(x,y) ＝(90,10)标处结束，该坐标从起始位置更朝着y方向。类似地，对 于机器人B，表数据指示机器人B不想从其位置移动，因此，对于起始和结束位置两者，(x,y)坐标(40,0)与节点4的对齐。

表2：示例输出轨迹如下所示：

表2表示在输出与前提条件生成器模块共享之前路线轨迹的原始输出。 在时间0，机器人A在节点9处，而在时间10，机器人A在节点8 处，在时间20处，机器人移动到与节点7对齐的坐标(70,0)。为 了表示和简化目的，用于B的路径在A之后示出。与A相似，用于 B的路径在时间0在节点4处开始，即(40,0)，在时间10，机器人 B在节点3处，即(30,0)。在表2中，考虑机器人A在时间40的 路径。在时间40，机器人A在节点5处，并且在时间50，机器人将在节点4处。但是，机器人B在节点4处开始。因此，在时间50， 机器人B必须移到节点3，以避免与机器人A发生碰撞，机器人A在 时间50将位于节点4处。因此，当机器人A从节点5朝着节点4移 动时，在那个时间点(对于机器人A是50)，机器人B开始朝着节 点3移动，然后朝着节点2、1和0移动。系统分析路径并识别出潜 在的碰撞场景。系统采取措施并生成路线规划，使机器人A不与机器 人B发生碰撞。虽然机器人B必须在同一节点开始和结束，但由于机 器人A可能在节点4处与机器人B发生碰撞，因此系统指示机器人B 从节点4移开并绕道而行，并在稍后的时间点返回到节点4。类似地， 机器人B在时间60位于节点20处坐标(0,20)，而机器人A在时 间60位于坐标(30,0)。系统观察到此时没有碰撞，但是，基于对 路径的分析，系统确定，如果机器人B移动到节点10，那么机器人B 可能会与机器人A发生碰撞，因为机器人A将在时间100到达节点 A。因此，系统生成包括机器人B在节点20处等待直到机器人A在时间110通过节点10的路线规划。当机器人A在时间110通过节点 10时，机器人B然后从等待状态移至移动状态，并在时间111移动 到节点10。在以上两个示例中，系统都生成涉及让自主车辆等待或 移动以避免碰撞的路线规划。

在一个实施例中，片段可以被表示为具有由x和y坐标指示的对 角相对的点的矩形区域或框格式。片段在图4(B)-图4(D)中图解地表 示。片段可以被表示为图中的边。例如，如表2中所示，在时间0和 10，机器人A可以用空间中的矩形表示，坐标为(90,0)和(80,0)。系 统计算被矩形占据的体积以识别机器人A在时间0和10所在的空间。 空间的体积由矩形或框表示。在路径的分析期间，为了检查碰撞，系 统可以检查机器人A和机器人B的两个矩形或框是否相交。如果框 相交，那么该路径可能不是最优路径，因为存在潜在碰撞。每当机器 人必须从一个节点移动到另一个节点时，就会触发查询以核实轨迹是 否与先前的轨迹发生碰撞或相交。如果对查询的响应是肯定的，那么 机器人移动到下一个节点，否则，系统决定为可能潜在地与另一条轨 迹发生碰撞的机器人生成最优路线规划。出于表示目的，碰撞发生在 两个机器人位于同一节点时，但是，在现实生活场景中，当两个机器 人位于同一节点处时，碰撞发生，但是，在实际生活场景中，当两个 机器人位于由几何形状之一(框或矩形或任何等效形状)表示的空间 的同一片段中时，碰撞会发生。可以理解的是，操作环境中的实时场 景比上表中所示的要复杂得多，但是，为了理解的目的，该表示保持 比较简单。所选择的示例还包括确保两个机器人在特定时间点不在同 一节点处的简单情况。但是，对于系统可以采取措施以优化路线规划， 还有各种其它原因。在优化路线的同时，系统旨在尽最大努力将碰撞 降至最低。

可以理解，当自主车辆从一个节点移动到另一个节点或者存在来 自系统的让车辆或者等待、停车、绕道、移动或停止的指令或消息时， 系统生成路线规划或轨迹以捕获这些步骤。出于表示或简化的目的， 参考可能仅针对车辆移动或改变状态，但是，为了实现，系统必须生 成一个或多个路线规划，这些路线规划被分析是否有碰撞，然后最优 路线规划被确定以便稍后分发给车辆。

在一个实施例中，在实施级别，图形可以由文件表示，该文件包 括样本输出轨迹中所示的数字的列表和上面提到的表中所表示的路线 请求。图形可以以多种方式在系统中表示，例如作为锯齿状数组。锯 齿状数组是其元素为数组的数组。锯齿状数组的元素可以具有不同的 维度和尺寸。2D锯齿状数组被用于表示图形。考虑到CSV文件，这 可以以简化的方式进行解释。文件就像数字的表，第一列是节点的 ID(标识符)，第二列是节点的x坐标，第三列是节点的y坐标，第 四列是节点的尺寸(就半径而言)。其余的列是存在的边的列表。每 条边由该行表示的特定节点可以连接到的节点的ID表示。而且，在 每一行中，还包括边的宽度。

在一个实施例中，图形生成器模块211提供节点的优化的布置， 使得空闲空间的量被最大程度地使用并且没有节点彼此重叠。然后生 成图，它基本上是整个操作的起点。这个由图形生成器模块自动生成 的图没有任何特殊特性，例如，它没有重叠节点，也没有任何可停放 节点，等等。它可以具有空间特性，因此，最初的假设是机器人大到 足以容纳其中一个走廊，否则机器人可能无法移动到任何地方。在一 个实施例中，对于两个机器人，考虑到机器人小到足以穿过走廊，并 且最初不需要考虑任何碰撞避免步骤。最初，可以假设机器人刚好可 以从彼此身边走过以发起该处理。

在图形或地图生成器模块生成图形302之后，可以由系统接收一 个或多个路线请求。如前面所讨论的，表1提供了路线请求的示例。 因此，机器人A可以在(90,0)处开始，并且可以在(90,10)处结 束。类似地，机器人B可以在(40,0)处开始并在同一点(40,0)处 结束。对于其它机器人，可以提供具有等效节点细节的类似起点和终 点作为路线请求的一部分。如表1中所示，路线请求在坐标中。在节 点解析器模块处接收这些节点请求以离散化并指派正确的起始节点。 例如，机器人A可以在节点9处开始并在节点19处结束，而机器人 B可以在节点4处开始并在节点4处结束。在一个实施例中，路线请 求可以不包括与节点相关的信息，并且正确的起始节点指派由节点解 析器模块完成。这个节点指派任务由节点解析器模块以多种方式处置。 方法之一是使用自组织映射。自组织映射是一种使用无监督学习来训 练的神经网络，以产生训练样本的输入空间的2D离散化表示。在一 个实施例中，训练样本输入空间可以被称为映射。

在一个实施例中，代替使用自组织映射技术，节点解析器模块可 以使用将机器人映射到最靠近的节点的更简单方法。即使多个机器人 不能容纳到同一个节点中，多个机器人也与最靠近的节点对齐。在与 碰撞相关场景中，系统可以将碰撞解决推迟到较晚的阶段，而不是在 输入阶段本身进行处置。系统不会将此视为错误或无效的输入，而是 接受这个输入并移至路线规划的下一步。

在一个实施例中，类似于图像上采样技术的概念，用于执行节点 解析步骤的附加技术是通过对图进行上采样。在图像上采样中，该技 术涉及通过在从低分辨率图像到高分辨率图像的像素之间应用插值技 术来获得近似平滑曲线以解释从一个像素到另一个像素的改变。类似 地，在图中，我们有包括边和节点的图，而不是像素。上采样处理涉 及分析每条边，划分成两半，然后在边的中间放置节点。这种上采样 处理导致自动加倍边和增加节点。上采样处理的优点是系统获得图的 高分辨率细粒度拓扑细节。这个过程有助于系统更准确地确定最靠近 的节点。这个最靠近的节点可以相对更靠近最初可用的实际位置信息。其次，由于存在更多节点，两个机器人之间发生争用的可能性由于存 在越多节点就越小，因此节点指派变得更加容易。这种对图形进行上 采样的过程需要考虑一些因素。例如，如果图形中没有节点的重叠， 那么该图形的上采样会导致节点的重叠，因为现在多个节点被放置在 相同量的区域中。

应该理解的是，对于表示，术语树的“节点”不同于上面提到的仓 库的“节点”。在一个实施例中，仓库的节点是机器人可以访问、等待、 绕行或停止的空间的区域，而树结构中的节点可以表示路线规划的不 同阶段。在其它场景中，术语“节点”也可以表示可以在那些节点处访 问、等待、停止、绕道等的自动驾驶车辆。术语“节点”的含义可以基 于所讨论的上下文、示例和场景来决定。

根据实施例，图3(A)-图3(E)中的每个图表示用于优化路线规划 的示例性非限制性表示。在图3(A)中，将每个圆圈视为轨迹。出于表 示目的，在一个实施例中使用数据结构，诸如树。由于使用的数据结 构是树，因此树中的各个实体可以被称为节点。在图3(A)中，圆圈 301可以被认为是根节点，它是初始状态并且最初没有信息可用。每 个节点的状态信息存储在路径协调器204中。路径协调器204的结构 最初是空的，因为系统还没有开始规划，并且没有路线。首先，系统 规划路线A，其由从根301到节点A的线或边在视觉上表示。当系统 为路线A规划路线时，系统调用路径搜索模块214。如前所述，系统 的目标是与已经规划好的路线相比规划最优路线。系统分析树并且在 这个阶段确定没有现有的规划好的路线，因此最优路线是从根节点到 节点A的直线。对于下一个节点B的路线规划步骤，在路径协调器 中存在用于A的先前规划的路线的现有知识。在分析期间，系统遇到 用于A的现有的规划好的路线。因此，对于为B规划路线，系统通 过避开在A中已经规划的路线来优化路线。规划的路线的这个树结构 存储在路径协调器204中并由系统查询以获取关于已经规划好的路线 的信息，作为分析处理的一部分。在规划好路线B之后，路径协调器 204内的树结构如图3(A)所示，直至节点B的构建。在每个节点内部， 从根节点到节点B，路径协调器204中存储的信息不限于只有路径。 在路径协调器204中，系统还存储如规划的统计数据之类的信息，例 如，路线花费多少时间和多长，如与不可避免的碰撞(例如，与A) 相关的细节等其它信息。统计数据也可以被用于理解路线的最优程度。 在一个实施例中，不可避免的碰撞信息可以从用于特定路线的规划步 骤的输出接收，例如，通过单个机器人路径搜索处理214。在高级别 处，系统可以基于统计数据、早期规划的路线或轨迹、节点信息、机 器人想去的目的地、表示为节点等来规划路线。这个整体信息在路径 协调器204中被重复地更新。因此，系统在每个阶段分析现有的路线 规划，例如，将路线与先前生成的路线进行比较。在一个实施例中， 系统的目标是基于关键任务(如避免碰撞、最小化拥堵、提高机器人和/或仓库的利用率、性能、效率等)进行分析，然后将生成的最优 路线规划分发给机器人的车队。

在图3(A)中，考虑另一个节点C；然后，对于路线规划，可以重 复以上步骤。在分析阶段期间，系统进行碰撞检查。在针对节点C的 路线规划期间，系统在反向方向上进行遍历，由箭头310和320描绘， 直到遍历较早规划的路线，直到根节点为止。对于每条较早规划的路 线(从根节点A以及B开始)，系统在称为访问表的数据结构中创 建条目。路径协调器204执行建立访问表的任务。访问表是由节点索 引的快速查找表，其允许系统识别特定地点处的碰撞。访问表就像操 作环境中每个位置的日志。每次机器人通过连接点或节点或操作环境 中的任何其它地点时，用机器人信息、时间、地点、碰撞信息相关细 节等对访问表进行更新。访问表由正在导航的所有机器人进行更新。 假定机器人在操作空间的某个地方。在那种情况下，系统允许机器人 查询访问表，这进而允许快速查找机器人当前所在位置的本地碰撞信 息，而无需对树结构执行任何广泛的遍历。因此，在路线规划之前， 每次对树中的祖先节点的遍历完成时都更新访问表。在完成针对C的 路径规划之后，获得将路线B连接到路线C的分支或边。对于以后 的路线规划，重复上面讨论的相同处理，并相应地更新访问表。随着 分支对于树中的新路线规划增长，系统不断更新路径协调器204中的 访问表。由于路径协调器本身是树结构，因此可以通过重用访问表的 部分来进一步优化系统，这些部分可以在遍历祖先节点的同时被分析 和更新。优化涉及追踪路线规划次序的沿袭以查看哪个是最近的共同 祖先节点并使用来自最近共同祖先节点的访问表信息而不是遍历整个 树结构。例如，在图3(D)和图3(E)中，节点A和节点D的共同祖先 节点是节点C。在遍历节点A之后并且在为节点D进行规划的同时， 访问表中可用的路线规划信息不能对所有节点被再次重新访问，并且 代替地，最近的共同祖先节点(节点C)只能通过重用访问表的部分 (即，节点C而不是所有其它节点)来遍历以进行优化。

在一个实施例中，路径协调器204也可以使用其它技术进行扩展。 每次规划路线时，路径协调器204中的数据集并且在粒度级别，访问 表本身被不断更新。例如，如图3(B)中所示，与图3(A)不同，考虑系 统已接收到优先级输入，即，首先针对路线B为机器人生成路线规划， 然后再针对路线A为另一个机器人生成路线规划。针对B的规划将 是理想路线，因为没有可能需要避开的物体，如图3(B)中所表示的。 应该理解的是，物体可以包括可以与在操作环境中导航的机器人碰撞 的非人类和/或人类障碍物。在规划B之后，如图3(B)中所示，系统 可以为A规划，然后可以为C规划。图3(B)表示另一种排序形式， 其可以提供另一个统计数据集合。例如，虽然在图3(A)和图3(B)中最 后规划C，但A和B的排序交换了。与图3(A)中描绘的排序相比， 图3(B)中描绘的排序会导致碰撞计数和行驶时间减少。应该理解的是， 系统基于多个参数(包括碰撞信息、减少行驶时间等)分析各种路线 规划，并且随后优化路线规划以进行导航。

在一个实施例中，路线规划的分析可以识别对树进行排序以生成 更好路线规划的不同方式。例如，树的分支可能不一定需要从根开始。 如图3(C)中所描绘的，分支可以从中间节点发起。可以先规划B，然 后接下来可以规划C，然后规划A。可以规划另一个排序，并且图 3(C)中描绘的这种排序可以比图3(A)和图3(B)中表示的排序更好。这 些排序的优点是也可以使用共享信息，与为重用访问表的部分所做的 优化相似。例如，在图3(B)和图3(C)中，在优化针对节点B的路线 规划的同时，所有收集的统计数据都可以用于排序，因为节点B对于 两个排序是共用的。这种形式的共享信息对于开发两种排序都是有用 的。共享信息的示例可以包括可以重用于建立访问表的共同祖先的数 据(例如，图3(B)和图3(C)中的节点B)。图3(A)、3(B)和3(C)中的 非限制性示例表示建立树状数据结构的路径协调器204的功能，其中 每次规划路径时，路径或轨迹附加到树结构。树结构扩展并且随后， 这个树结构可以被用于快速查找规划的次序的不同排列的统计数据和 快速查找碰撞检查。

在一个实施例中，统计数据可以存储在树的每个节点中。树中的 每个节点都存储统计数据，指示解决方案是否适合特定节点。对于这 个确定存在各种度量，例如，在从父节点到该节点遍历的同时遇到的 碰撞计数、被动路径的数量(其指示转换成到达特定节点是无目的地 的路线数量)、总行驶时间、系统遍历包括用于决策的节点的路径的 次数等。这个信息对系统是关键的，因为在路线规划的分析期间，必 须就子节点是否要被遍历做出决定。系统更喜欢以最小或零碰撞遍历 节点。但是，如果统计数据指示要遍历的节点有更多碰撞，那么这个 信息允许系统跳过该节点并寻找替代节点。最初，当系统开始遍历树 时，系统处于未知领域。因此，系统在第一级遍历；但是，在那之后， 系统不断地做出决定并遍历包括一个又一个节点的路径，直到到达树 的子节点。现在，系统具有关于解决方案有多好的一个数据点。类似 地，系统遍历其它路径以收集更多数据点，从而对优化路线规划做出 准确决定。统计数据是允许系统做出正确决定的信息集合。

在一个实施例中，系统在多路径树搜索期间使用多线程以同时生 成不同的路线规划。搜索线程是相互耦合的，因此如果任何线程在遍 历期间接收到任何信息，那么数据被反馈到全局数据库111，其它线 程可以访问该数据库以进行决策。这个全局数据库111与本文讨论的 其它数据结构和存储装置(例如，路径协调器204)同步。系统允许 多个线程不断读取数据，只要没有人改变数据即可。数据可以保持恒 定以避免任何改变；但是，在整个路线规划处理期间，一些数据必须 跨所有线程被共享。但是，当一个线程可能想要将数据写入全局数据 库，而另一个线程可能尝试读取数据时，问题就开始了。因此，系统 为解决这个问题而采取的步骤之一是使用树表示。祖先节点中的解是 之前遍历过的路径。由于系统是确定性的，因此这些解不会改变。因 此，可以保持恒定的数据可以是祖先节点中的解。解是计算出的轨迹， 并且在计算之后不需要改变它们。这些解不断添加到全局数据库111。但是，可能需要被修改的数据是树统计数据。用于特定节点的统计数 据可以在一个阶段指示好的解；但是，另一个线程可以指出，在遍历 与该节点相关的路径之后，由于如碰撞、行驶时间等原因，用于该节 点的统计数据可能不好。因此，可能需要修改统计数据并且不能保持 恒定。基于由不同线程在不同时间点接收到的信息修改统计数据的值。 因此，通过这种技术，系统确保，如果由某个线程基于其遍历为特定 节点给出更好的反馈，那么必须更新与该节点相关的统计数据。这启 用更准确的路线规划并确保系统可以不断优化路线规划。系统通过允 许树的一些部分(祖先节点)受到保护而与统计数据相关的树的其它 部分可以被更新来处置竞争条件问题。

在一个实施例中，路径协调器204的实施方式与路径规划处理协 同工作。路径规划的输入是整个数据结构，即，路径协调器204，如 由图3(A)、3(B)和/或3(C)所表示的。注意的是，为了理解的目的， 表示被简化；但是，在现实生活中，该结构是复杂的，并且取决于要 规划的路径、基于操作环境的广阔搜索空间以及为了导航多个异构自 主车辆而具有各种分支。系统可以接收输入以在节点C的顶部添加节 点，比如图3(D)中所示的D。在分析阶段期间，系统然后使用整个数 据结构来调用路径搜索模块214以确定单个机器人可以通过哪些方式 避开共同祖先中所有先前规划的路径。多路径树搜索模块213是用于 决策如何建立树的树搜索处理。路径协调器204本身就是树。对于多 路径树搜索模块213，系统应用更智能的技术来探索并获得好的结果 而不浪费太多计算资源。可以应用的技术有很多种，例如从根节点到 叶节点进行遍历，并且收集树中的每个节点的统计数据，并且对于特 定遍历路径中从根节点到叶节点的路径中的所有节点汇总统计数据。 例如，在图3(D)中，可以为从D、C到B的所有节点(由点线330表 示)和从A、C到B的路径(由点线340表示)收集汇总的统计数 据。下一次，在遍历根节点和节点C之后，多路径树搜索模块213然 后可以取决于先前收集的包括碰撞信息、行驶时间、障碍物信息等的 统计数据来分析是遍历跨越图3(D)的节点A还是节点D的路径。系 统还可以向统计数据添加一些试探法以引导决定以确定要遍历的路径， 例如，历史上遍历特定路径的预期奖励是多少或者系统多想探索未知 参数。

在一个实施例中，本发明改进现有的树搜索技术。系统使用元试 探法过程自动确定可以规划的排序。在一个实施例中，系统的输入之 一可以是特定机器人具有更高的优先级值，因此可能需要首先进行规 划。在图3(E)中，将新的根节点视为R，并且在进入树搜索模块之前， 系统可以规划机器人X和另一个高优先级机器人，比如Y。节点Y的 分支被附加到节点X并且稍后被附加到新的根节点。这迫使首先探索 X，然后探索Y。这个优先级输入可以由用户手动完成或者由系统在 做出与碰撞处置相关的决定时进行处置。此后，节点Y可以连接到图 3(E)中描绘的节点。这种技术确保X始终具有最高优先级值，然后Y 具有次要优先级，然后是用于探索的其余节点。优先级值还可以基于 系统所做的涉及偏置探索的分析(例如，基于在特定路径而不是任何 其它路径中遍历的奖励来选择节点)通过更软或更少限制的方式来确 定。例如，在图3(E)中，优先考虑左节点A或右节点D的决定可以 取决于该节点已被探索的次数。例如，如果节点A被探索的次数比节 点D多，那么优先化可以基于探索较少的节点，因此，在这种情况 下，节点D可以被优先化。可以用于这个决定过程的其它参数可以是 偏好参数，其中由于诸如以最小碰撞遍历的路径之类的原因，节点A 可能优于节点D。每个参数可以具有加权点，并且可以考虑加权点的 总和来对特定节点或路径进行优先排序。这个搜索试探法项提升了节 点B，这有助于将探索决策偏向节点B。各种类似的机制可以应用于 这个决定过程。

在为相似的输入重新规划路线时，可以获得不同的解决方案。系 统可以基于确定性实施方式。在确定性实施方式中，对于相似的输入， 在一个实施例中获得相似的解决方案。但是，获得不同解决方案的原 因可以是由于在执行树搜索时的多线程实施方式。由于操作系统不是 实时的，因此不同的线程可以在不同的时间完成执行。在此类场景中， 树结构中各个节点的统计数据可以取决于系统和处理器上的负载而以 不同的速率被更新。由于决策是基于各个节点的统计数据，因此当系 统分析路线规划时，结果所得的解决方案可以基于系统和处理器的负 载和计算而改变。在一些场景中，通过允许树搜索处理是单线程的， 可以使系统更具确定性。在其它场景中，为了利用系统的全部资源， 系统可以多线程运行。通过多线程系统，树结构的每个单个节点可以 同时扩展到完整的图形搜索，这进而要求大量的计算资源并且可以由 多个线程执行以给出最优结果。

在一个实施例中，由于系统的一般非确定性性质，系统具有灵活 性的优点，并且通过使用之前讨论的方法，例如，通过排序偏置，其 可以包括优选图3(E)的路线规划D而不是路线规划A。因此，下一 次，即使考虑路线规划D，系统也仍然可以保留相同的偏置，并且解 决方案在排序方面可以或多或少相同，因为输出是路线结构的次序。 但是，如果事件与避免碰撞相关，那么事件可以被视为关键过程。由 于偏置，如果发生轻微改变，那么系统可以生成有偏置的路线规划， 就像在碰撞前所做的那样。但是，在分析期间，虽然存在偏置，但系 统别无选择，只能改变顺序以避免碰撞。系统还使得关键任务能够优 先于其它任务。如果必须遵循树结构的特定排序，但是，如果这会导 致碰撞，那么系统可以认为这是糟糕的或消极的方法，并采取措施来 抵消试探法或其它偏置。系统然后尝试遵循可以避免或最小化碰撞场 景的另一个排序。

在一个实施例中，系统提供各种技术来避免碰撞，例如速度缩放。 为了防止碰撞，系统可以采取措施以使机器人逃脱迎面而来的障碍物。 在此，对于这个示例，障碍物可以是机器人、人类或任何其它移动物 体。考虑障碍物是第二机器人。如果针对第二机器人的路线规划包括 直接穿过第一机器人的路径，那么，即使系统意识到该路径，第一机 器人也会需要足够快以确保不会与第二机器人发生碰撞。在此类场景 中，避免碰撞的技术之一是让移动缓慢的机器人首先被规划并具有更 高的优先级值，而另一个行驶快的机器人可以稍后被规划。稍后规划 另一个机器人的另一个原因可以是该机器人与较慢的机器人相比具有 由于更高速度而避免碰撞的能力。在一些复杂的场景中，可以应用其 它技术来防止碰撞。一般而言有试探法，就像如果系统扩展节点并且 如果存在不期望的结果(诸如解决方案包括碰撞)，那么系统可以基 于分析修改路线规划(例如，遍历树的另一个节点)，以获得更好的 解决方案。这意味着系统可以首先生成可能导致碰撞的路线。之后， 基于对路线的分析，系统可以通过以更高速度移动机器人来更新路线 规划，这具有更高的避免碰撞的机会。机器人的减慢由路径搜索模块 中的等待条件单独负责。当系统分析路径以避免碰撞时，系统通过使 得机器人能够在某个其它地方等待以避免与其它机器人碰撞来更新路 线规划。这个让机器人在某个其它地方等待的过程可以被认为等同于 使机器人减慢。在一个实施例中，通过分析系统试图避免的碰撞，然 后计算可以向前预测的速度以确认如果机器人按照准确计算的速度移 动则可以避免碰撞，可以进一步改进速度提升技术。可以使得系统能 够防止碰撞的确切速度也可以通过树搜索处理来计算，其中可以确定 可以领先并继续前进的第一机器人。相比之下，另一个机器人可以在 后面并减慢，从而允许第一机器人向前移动。

在一个实施例中，系统提供另一种技术以避免依赖于被动转换过 程的碰撞。从概念上讲，它可以看起来与速度提升技术相似；但是， 在被动转换过程中，系统更新路线规划以将目的地改为与机器人预期 的地点不同的地点而不是提升速度。一般而言，路线规划生成的输出 可以包括统计数据；例如，估计的行驶时间可以基于结果轨迹的长度、 可以从过去的搜索中搜集的存在的碰撞计数、最初要前往的路线中被 拒绝的路线的数量等。作为优化和处置关键过程(如避免碰撞)的一 部分，系统可以基于优先级将统计数据划分为多个级别，其中优先级 最高的用于避免碰撞，其次是减少被动转换(这是最初要前往的路线 中被拒绝的路线的数量)，第三是减少总行驶时间。虽然仅讨论了三 种统计数据，但是，本发明可以不受这三种统计数据的限制，并且可 以考虑在操作环境中机器人的导航期间出现的其它潜在可能性。优先 级值可以根据一个或多个外部实体(如仓库管理员)或内部系统实体 (如路线规划师等)定义的要求进行定制。在该树搜索期间，每当存 在不期望数量的碰撞时，系统可以决定查询被动路线技术。这是系统 为减少不期望数量的碰撞而采取的稳健决策。

在路线规划处理的生命周期期间，系统不断扩展树形结构。它保 持跟踪每个事件中遇到的最佳解决方案和/或碰撞，包括先前的路线 规划。应该理解的是，如树遍历、在树中扩展节点、停止树的搜索、 在树中添加节点或分支之类的数据结构相关处理步骤是底层实施方式， 在更高级别处，系统遵循分析路线规划并优化路线规划。在一个实施 例中，系统保持最佳解决方案的统计数据，例如，到叶节点的哪条通 路历史上给出最佳统计数据等。每当搜索停止时，系统存储遇到的最 佳通路，这可以基于多种因素，如更少的行驶时间、更少的碰撞、更 少的路径转换、非重叠或可停放节点的计数、优先级值、偏好偏置、 速度等。这种方法的优点是系统可以基于上面提到的参数决定搜索的 终止。搜索终止条件之一也可以是定义计算时间限制的阈值。如果机 器人在导航期间没有卡住，那么阈值可以是可接受的。系统还可以接 受可以被定义的阈值。系统可以允许没有碰撞、3-4个被拒绝的目的 地或3-4个被动路径转换并返回满足阈值的相关路径。在分析针对关 键任务的路线规划的同时，系统允许将不同的度量、试探法和数据定 义为阈值参数。而且，在一个实施例中，可以有1-2个机器人和小的 搜索空间，因此准则之一可以是在返回潜在路径作为解决方案之前探 索整个树结构。系统还可以允许用户在某些情形下无视决策并取消搜 索。

以上树搜索技术基于使用统计方法、对不同技术进行采样、引导 进一步探索、对找到的最佳解决方案保持跟踪，以及当搜索终止时获 得并返回最佳解决方案。除此之外，还可以在搜索终止之后返回的其 它参数可以是将路线转换成被动路线、根据速度提升技术改变速度等。 系统可以使用所有可能的排列和技术组合(如本文所讨论的)来定义 分析度量，这些度量可以被用于在给定生成的路线规划集合的情况下 确定最优路线规划。

在一个实施例中，系统启用可定制的时间惩罚特征来做出优化路 线规划的决定。考虑机器人，它要花一定的时间才能从一个节点移动 到另一个节点。时间可以基于边有多长以及机器人从起始节点移动到 结束节点有多快来计算。但是，在一些场景中，这个简单的解决方案 会变得复杂。机器人的尺寸可以胖或大，因此要花更多的时间来遍历 角落，这会导致系统施加时间惩罚。这个惩罚可以是基于定制地图的 成本函数，该成本函数可以在一个或多个机器人的导航期间施加于它 们。系统可以允许在规划路线的同时允许这样的动态约束。基于定制 地图的成本函数的另一个示例可以是高度限制参数，例如，特定的边可以仅允许机器人在1m的高度以下，特定尺寸或高度的卡车可以仅 被允许通过图形的片段或节点，大于2m的机器人对于片段可以被要 求移动得更慢。应该理解的是，在本发明的范围内可以应用其它成本 函数。系统在规划阶段也可以使用此类约束来处置可以具有特定能力、 行为、尺寸等的异构车辆。

图3(F)是根据实施例的图示在操作环境中的各个节点之间生成优 化的路线规划的示例性非限制性表示。在一个实施例中，系统接收多 个输入，包括一个或多个机器人关于机器人在哪里开始、在哪里结束、 地图、先前找到的路线的祖先等的请求。基于输入，系统可能必须确 定同时避免碰撞的最优路线。考虑图形数据结构，图3(F)中所示，其 中图形数据结构中的每个节点都是地图中的物理节点。在图形数据结 构中，考虑带有中间节点的结束节点和起始节点。从起始节点到结束 节点有多条路径可以到达。例如，路径可以从起始节点->节点A->结 束节点或起始节点->节点B->节点C->结束节点或者起始节点->节点B->节点A->结束节点，以及从起始节点到达结束节点的其它可能组 合。箭头指示路线中从一个节点到另一个节点的遍历。让我们考虑从 起始节点到达结束节点的遍历技术。在这种技术中，考虑起始节点的 两个直接邻居节点A和节点B，并且它们的边权重可以指示机器人从 一个节点遍历到另一个节点可能要花的时间。例如，起始节点到节点 A的边权重可以是1，并且起始节点到节点B的边权重可以是2。因 此，边权重的值越大，这可以指示机器人从一个节点遍历到另一个节 点所花的时间越长。因此，机器人从起始节点到达节点B的时间可以 比到达节点A的时间长，如图3(F)中所描绘的。系统还可以对使机器 人旋转或偏离其路径征收(levy)行驶时间惩罚。例如，如果机器人 必须采用从起始节点->节点B->节点A的路径，那么机器人必须在节 点B处转弯才能到达节点A，从而导致行驶时间惩罚。在一些实施例 中，机器人的动力学可以约束机器人在转弯之前可能必须减慢，这导 致时间惩罚，考虑到如果机器人采用直线路径：起始节点->节点A-> 结束节点，则那么机器人就不会需要减慢并且因此不会征收时间惩罚 的话。

在一个实施例中，让我们考虑整个图结构的边权重是1。如果路 线是起始节点->节点A->结束节点，那么总边权重将是遍历从起始节 点到结束节点的路径所采用的边权重之和，将是2。类似地，对于路 线起始节点->节点B->节点A->结束节点，总边权重将是3。对于从 起始节点到达结束节点，最短路径可以是起始节点->节点A->结束节 点，边的总权重是2，这提供了这种场景下的最优路径。系统总是使 用本地信息集合来采用最短路径。但是，对于其它搜索技术，除了边 遍历长度以外，还可以考虑偏置试探法，其中在起始节点的邻居之间 做出决定，节点A可以获得偏好，因为它更靠近结束节点。因此，这 种技术使得系统能够将节点的扩展朝着具有最短路径的直线方向偏置， 最短路径从起始节点到结束节点所花的时间更少。这些技术指示典型 的路径搜索技术如何找到最短路径；但是，这些技术没有提供与避免 碰撞相关的任何细节。

根据实施例，图4(A)-图4(D)中的每个图是时域和空间域中的轨 迹的示例性非限制性表示。当节点被扩展时，系统检查碰撞。例如， 考虑连接起始节点到邻居节点A或节点B的边。系统检查机器人是 否可以从起始节点行驶到节点A或节点B，因为图形数据结构中表示 的两个节点之间存在物理连接。在一个实施例中，碰撞检查可以被认 为是边界测试。考虑图4(A)中所示的2D图，其中Y轴表示时间，X 轴表示空间。一般而言，空间是2维的；但是，出于可视化目的，在 图4中，考虑X轴上的1D空间。为了表示离散轨迹，图4(A)示出了 非限制性表示，点(t1，t2，t3)作为时间和空间中的气泡。在此， 点t1可以被认为是具有与表2相似的x和y坐标的点，如之前所示。 由气泡表示的多个点，图4(A)中所示，指示如何遍历通过时间和空间。 为了表示一个轨迹将占据的区域，图4(B)表示多个框。为了从点t1遍 历到点t2，机器人必须在空间和时间上行进一段距离。然后画框401 来表示遍历，并且覆盖点t1到点t2的框表示空间和时间上的体积。 可以对路径的所有连接的节点重复该处理，然后多个框(例如，401、 402、403)表示一条轨迹可以占据的区域，如图4(B)中所示。然后基 于路径协调器中存储的数据与系统的其它模块共享这个信息。现在， 将点t1到点t3的路径视为先前已规划的路径。在此类场景中，图4(B) 中的表示可以指示通过3个框401、402和403的相交可以是不可能 的。而且，考虑该表示指示与先前规划的轨迹没有相交或碰撞。

在一个实施例中，在完成图3(F)中描绘的图表示之后，考虑系统 专注于将机器人从起始节点移动到另一个节点的场景。这在图4(C)中 表示。在规划期间，考虑机器人从起始节点移动到节点A(图3(F))， 然后，在图4(C)中表示点线框。这个点线框404被认为是机器人在操 作环境的空间和时间中占据的体积。点线框404指示与先前规划的或 另一条轨迹的相交；因此，结果没有用，因为路线会导致碰撞。但是， 如果机器人移动到另一个节点B(参见图3(F))，由图4(C)的点线框 405表示，那么系统避免了碰撞，因为没有与先前规划的路径或轨迹 的相交。系统现在能够关于在某个时间从起始节点到节点A或起始节 点到节点B(图3(F))是否会导致碰撞(图4(C))做出决定。基于这 种方法，系统可以分析路线规划并确定从源节点到中间或目的地节点 A的遍历是否会导致碰撞(例如，图4(C)的点线框404)。因此，系 统可以尝试遍历到图3(F)的另一个节点B，该节点可以是无碰撞的 (与框405相似)。以上非限制性场景被认为有助于以简化的方式理 解系统为寻找无碰撞路径而做出的决定。而且，在一些情形下，如图 3(F)和图4(C)中所示，系统知道在特定时间，从起始节点到节点A的 路径可以与之前规划的路径或其它路径规划在空间和时间中有相交，这种场景可以并不总是恒定的并且可以在稍后的时间点改变。在稍后 的时间点，有可能新规划的路径不会与先前规划的路径相交。这在图 4(D)中由箭头410表示，指示框404(出于表示的目的用深色边界示 出)已及时滑到新位置。通过该技术，系统分析路线规划并指示一个 或多个自主车辆及时等待，并且可以规划不会与先前规划的路径相交 的路径。而且，框404到如箭头410所描绘的新位置的移动可能不必 太远。系统不需要将框404移动到任意地点；相反，系统只需要确保 框必须在不同方向上移动，例如，在时间上朝着Y轴在向上的方向 上，这样就不会与先前规划的或其它轨迹发生碰撞。系统准确地计算 位置，以便可以预见与先前规划的路径的碰撞，以便在预见的碰撞范 围结束之后将框定位在那个点处。新的路线规划包括自主车辆移动到 计算出的位置并避免碰撞。通过该技术，系统确保规划的路径没有任 何碰撞。在一个实施例中，系统还可以准确地计算位置并生成新的路 线规划，该路线规划不会与先前规划的路径或任何其它生成的路线规 划发生碰撞。系统在针对一个或多个碰撞分析一个或多个生成的路线 规划的同时采用本文讨论的一种或多种技术。基于分析，系统优化一 个或多个路线规划。这些优化的路线规划随后被分发给一个或多个自 主车辆。在一个实施例中，由系统执行的用于分析路线规划的步骤可 以被视为路线规划的优化的一部分，并且路线规划的优化期间执行的 步骤可以被视为针对关键场景进行路线规划的分析的一部分。

根据实施例，图5(A)-图5(B)中的每个图是用于优化路线规划的 示例性非限制性表示。将图5(A)视为图3(F)的延伸，具有这里讨论的 碰撞场景。在一个实施例中，当系统在规划从节点A到结束节点F的 路径的同时分析碰撞时，系统动态地修改图形，因为搜索处理也对图 执行。为了动态地修改图形，系统创建重复节点E，它是碰撞节点 (节点A和节点F)之一的在前节点(节点A)的副本。在这种情况 下，对于涉及节点A和结束节点F之间碰撞的场景，在前节点是节点 A，如图5(A)中所描绘的。由于存在从节点S到新节点E的路径，因 此系统可以允许机器人从节点S行驶到节点E。如果机器人从节点S 行驶到新的重复节点E，那么作为规则，系统可以强制机器人在新节 点E处等待，直到节点A和节点F之间的原始碰撞结束。新节点E 将具有与节点A(碰撞节点A和F的源节点)相似的新边，这是从节 点S到节点E的边和从节点E到节点F的另一条边。为了表示的目 的，新边以点线格式示出。新节点E现在可以作为替代被遍历，而不 是被阻塞的节点A。除了存在这个新节点E直到节点A和节点F之 间的原始碰撞结束才会被遍历(由X示出)的条件之外，新节点E在 图形中被动态更新。在一些场景中，系统可能会因为碰撞而不允许从 节点A遍历到节点F，但可以使用新节点E代替节点A进行遍历。 但是，系统可能不允许从起始节点S遍历到新节点E。即使新节点E 可以更早到达(例如，如果从节点S到新节点E的行驶时间短)，系 统仍然不允许从节点E到节点F的路径，因为在新节点E上存在关 于新节点E可以在多早之前被遍历的更低界限。下限可以基于以下原 则：在为从节点A到节点F的路径检测到的原始碰撞结束之前，不能 遍历新节点E。出于表示的目的，这里已经示出了起始节点S和结束 节点F，但是，这不是限制性的，并且该技术可以应用于图中的任何 节点。

图中的每个连接的节点给出访问或遍历其连接的相邻节点的可能 动作。在图5(A)中，将起始节点S连接到新节点E的边是特殊的， 因为它与节点A在空间上重叠，但存在时间约束。新节点E和原始 节点A与空间中的相同地点对应(在空间中重叠)。这种空间中的重 叠也可以基于图4(A)-图4(D)中所示的表示来理解。在图5(B)中，从 起始节点S行驶到被阻塞的节点A并不是真正意义上的不可能；但 是，由于与先前规划的轨迹的相交(潜在碰撞)，系统应用巨大的成 本惩罚。从起始节点S到阻塞节点A的路径被标记为高成本惩罚。但是，如果从起始节点到其它连接的节点的所有其它路径都具有相同的 高成本，那么从起始节点S到节点A的路径仍然可以被系统考虑进行 遍历。在另一种场景中，即使机器人已经规划从起始节点S遍历到节 点E并等待直到原始碰撞结束，也有可能在节点E处等待之后，从节 点E行驶到结束节点F会导致另一次碰撞(例如，由于操作环境情形 的潜在改变)。如果在这种情况下在节点E和结束节点F之间检测到 新碰撞，那么系统可以决定最好采取惩罚命中(penalty hit)。系统 然后可以决定从起始节点S到节点A然后再到结束节点F的路径可 以是更好的选择，虽然成本高。因此，系统有许多可能的被同时探索 的路径选项。在给定时间，随着系统离起点S越来越远，系统可以不 断地决定未来可能的最佳选项。系统迭代地应用这种技术以确保避免 碰撞。这些是系统在分析路线规划的同时使用的底层实施方式，然后 基于分析决定(如避免碰撞)优化路线规划。

在一个实施例中，系统可以实现用于最优路径规划的递归过程。 如图5(B)中所示，考虑节点A和结束节点F之间的路径被阻塞的场 景。系统可能不得不在前一个节点(在这种情况下，起始节点S)处 后退一步。从起始节点S开始，节点A可以是个死胡同，因为如果采 取那条路线，那么由于节点A和结束节点F之间检测到的现有碰撞而 征收高成本。现在，如果系统决定从起始节点S转到新节点E，那么 在新节点E处有等待时间，直到节点A和目的地节点F之间的原始 碰撞结束。现在，假定起始节点S和新节点E之间存在碰撞，那么发 生递归过程。递归过程包括复制过程，其包括创建复制节点G，该复 制节点是与节点E发生碰撞的在前节点(起始节点S)的副本。这个 新节点G将具有与起始节点相似的边S，这意味着新节点G将具有 从节点G到节点E的边(用点线边示出)和到节点B的另一条边(点 线边)，它们是起始节点S的相邻节点。这种技术递归地回溯并尝试 识别系统是否可以满足开始节点，然后系统可以为后面的节点规划路 由。但是，如果系统不能满足开始节点，那么系统可能不得不回到规 划较早的节点，这将同时增加要遍历的选项的数量。为了遍历其它节 点，系统有多个选项，如在树中移动上一级别并重新开始遍历，如本 文所讨论的，遍历替代分支以找到更好的选项等。

在一个实施例中，在图形搜索处理期间，可能无法改变先前规划 的路线。系统可用的选项是更快地移动机器人或更慢地移动机器人或 绕道以避开障碍物。例如，如果障碍物是人，那么他们已经有设定的 路线。有时，在图形搜索中探索所有可能的选项或场景之后，系统可 能会找到一个或多个可能无法避开的碰撞。在此类场景中，系统可以 强制改变早先规划的路线以采取避免碰撞措施。这是系统采取的一种 更高级别的优先级搜索决定，以覆盖用于避免碰撞的一般场景。例如， 系统可以指示一个或多个模块在树中向上移动并改变轨迹的排序。每 当模块即使在应用这里讨论的技术的所有排列和组合之后也未能找到 无碰撞路线时，系统向多路径树搜索模块给出指示以进行控制。进而， 多路径树搜索模块可以将遍历重定向到当前节点上方一级，并请求首 先从树中的那个节点开始规划轨迹以找到无碰撞路线。

在一个实施例中，多路径树搜索模块分析并关于首先规划哪条路 线的排序做出决定。该模块还可以决定是否需要对路线规划是否必须 从一个节点改变为另一个节点进行任何重新排序。分析处理涉及基于 试探法的树搜索的选择过程，其包括总碰撞计数、总行驶时间、总被 动转换、已探索和未探索的分支、重叠节点、可停放节点等的汇总。 由多路径树搜索模块执行的分析处理导致路线规划处理的优化，也可 以自由改变路线规划的排序、改变其中一些路线的目的地、改变其中 一些机器人的速度。多路径树搜索模块的输出可以包括要规划的路线 的排序、规划的排序的汇总统计数据、可以已经将其目的地转换成被 动的路线的子集，以及机器人速度被改变的路线的子集。决策是分层 的，其中，在每个单个决定内，存在图形遍历决定，其基本上包括关 于是否可能从一个节点遍历到另一个节点以及相邻节点遍历到第三节 点等的查询，同时满足多个约束并最小化路线行驶时间。最底层的决 定是非常基本的：基于遍历是否会导致与先前规划的轨迹或其它轨迹 的碰撞，机器人是否可以从特定节点遍历到另一个节点。一旦做出基 本决定，下一个决定就是在图3(A)或图3(B)中表示的树搜索的一个圆 圈或一个节点内的潜在选项当中做出最优选择。

图6是根据实施例的用于优化路线规划的示例性非限制性表示。 在一个实施例中，考虑在同一地点开始和结束的机器人。这在图6中 用点线弧描绘。将图视为这种表示的数据结构。轨迹可以包括行驶到 多个节点和行驶回到相同的开始节点。一般而言，这种场景是其中图 形搜索可能由于返回起始节点的回路形成而无法工作。系统面临的挑 战是可以如何因回路形成而终止搜索。系统检查机器人的当前位置是 否与机器人的预期位置等同。如果是这种情况，那么系统停止搜索。 如果起始节点与结束节点相同，那么系统停止搜索，因为机器人已经 到达目的地。环回可能需要具有与系统同时避免碰撞的正常路径搜索相同的特点。这是通过以下技术实现的：一般而言，当机器人到达目 的地时，预计机器人应当留在那里直到时间结束或直到指示下一个路 线规划。对于碰撞检查，系统执行包括时-空碰撞框在内的附加任务。 时-空碰撞框由节点定义，其中机器人停留在该节点处直到时间结束。 如本文所讨论的，这是在空间和时间维度中表示的不同类型的体积。

在一个实施例中，系统以两种方式分析路线规划：一旦机器人在 结束节点处结束，系统就进行附加查询，这是环回碰撞检查，即机器 人可以停留在那里直到时间结束吗？有时，系统给出肯定响应，因为 可以没有任何其它机器人可能通过，于是处理终止，并且机器人可以 在那里等待。在其它场景中，由于另一个机器人可能通过等原因，系 统给出机器人可以在那里停留一段时间但不能直到时间结束的否定响 应。在这种否定响应场景中，回环轨迹(由点线弧表示)成为机器人 的碰撞。解决这个问题的机制之一是系统指示机器人遍历某个其它地 方然后返回，如图6中所描绘的。这基本上通过相同的机制工作，与 正常碰撞避免相似。系统动态地创建碰撞解决节点E并复制结束节点 的所有边，现在新节点E具有与结束节点相似的边。与这里讨论的碰 撞避免技术相似，系统回溯一个节点(例如，节点C)并分析是否有 可能从节点C遍历到新节点E。新节点E也充当结束节点，与原始结 束节点相似。新结束节点E具有时间约束，与每个动态生成的碰撞解 决节点相似。直到原始碰撞结束，系统才可以允许遍历新节点E。由 于时间约束，可能不存在从节点C到新节点E的路径。如果行驶是 不可能的，那么系统会递归回溯，直到可以避免碰撞。如果有可能从 节点C行驶到节点E，那么重复相同的处理。系统可以调用环回模块 来检查节点E是否成功避免了结束节点的先前碰撞。系统动态地创建 节点E，以避免结束节点的碰撞，因为节点E的环回在不同的时间。 如果机器人可以到达节点E，这意味着克服了时间约束条件，那么结 束节点处的碰撞肯定已经结束。可替代地，这种技术可能无法立即解 决碰撞，因为可能存在另一个碰撞(与我们早先关于图5(A)和图5(B) 的讨论相似)，在这种情况下，复制处理将递归地继续。递归过程继 续，直到系统可以通过到达机器人从其开始遍历的原始节点来解决对机器人的决策。

在一个实施例中，如果多个机器人可能必须行驶到同一个目的地， 那么以上技术可能不起作用，因为多个机器人在竞争同一个目的地。 这种场景会导致涉及多个机器人的空间在大量时间相交的两个或更多 个碰撞边界。在此类场景下，其中多个碰撞边界导致大量时间，系统 忽略碰撞避免措施并推动前提条件生成器模块寻求解决方案。路线轨 迹被传递到前提条件生成器模块，在那里此类碰撞被停止而不会发生。 该模块分析路线轨迹并创建死锁场景。死锁将出现在最终目的地处， 其中机器人可能不会朝着碰撞前进，而是被添加到整个等待队列中。 系统通过为多个机器人规划死锁队列来采取先发制人措施以避免碰撞。

在一个实施例中，系统可以不同地处置碰撞解决机制。如上面所 讨论的，碰撞解决机制被描述为系统在稍后时刻处置的动作；例如， 系统可以创建新节点并请求稍后在不同的时间戳返回以解决问题。考 虑两个机器人在同一地点开始，这基本上是不可避免的碰撞。如果系 统忽略这个条件，那么后续也会导致碰撞。因此，系统决定在开始时 及时将它们隔开。为了解决这个问题，系统缩减时间，例如以负时间 戳，并尝试抢先一步。如果获得先机，那么系统可以确保机器人快速 摆脱阻挡机器人。这有助于系统在多个机器人就位的情况下在起点解 决碰撞问题。这与早先讨论的机器人可以快速向前移动并避免碰撞的 速度提升机制的构思相似。但是，在速度提升机制中，如果将该技术 应用于起始位置，那么不可能有领先优势。

在一个实施例中，对于碰撞检查，系统的输入是轨迹，并且系统 检查轨迹是否与任何其它规划的轨迹发生碰撞。隐含的假设是在轨迹 开始之前，机器人在哪里？例如，机器人是在起点，还是在完成导航 之后在终点节点处等待。这个信息与碰撞检查相关，因为要求机器人 的位置，因为可以有其它机器人可能想要穿过所述机器人。有时，系 统分析并决定对路线的一部分(起始位置或结束位置，或其它部分) 而不是整个路线进行碰撞检查例程。

在一个实施例中，系统为被认为不可解的输入生成最优解；例如， 多个机器人从同一位置开始或注定在同一位置结束被认为是无解的， 因为起始和结束位置本身都会导致碰撞。系统旨在最小化碰撞，而不 是将输入视为错误或无效。系统具有绝对碰撞检查机制，该机制检查 是否发生碰撞，并且如果碰撞是不可避免的，那么系统在初始阶段通 过忽略它进行优化。稍后，如早先所讨论的，系统具有前提条件生成 器模块，该模块在它在路线中遇到碰撞时生成回路依赖。这种回路依 赖会导致死锁，如本文所讨论的，而不是实际碰撞。系统知道多个机 器人必须相互穿过，从而导致碰撞；但是，由于前提生成器模块的回路依赖生成，多个机器人彼此靠近并卡在死锁队列中，而不是相互碰 撞。然后系统启动并尝试识别原因并尝试解决死锁场景，诸如将其中 一个机器人移动到另一个地点并让另一个机器人通过。系统的这种动 作由被动转换模块处置，该模块将攻击或阻挡机器人之一移动到不同 的地点。这些是系统基于其分析使用的不同种类的机制。它有助于优 化分发给自主车辆的路线规划。

在一个实施例中，可以定制系统以确保完成任何绕行、环回等， 从而成本不会显著影响路线规划。如果在机器人的导航中可以预见到 任何潜在问题(例如，电池电量不足)，那么可以将目的地定义为充 电点。系统还可以引入中间点(诸如充电点)，而不是将这些点定义 为目的地点或下车点。然后机器人可以在通过点充电，然后在目的地 或下车点拾取或放下物体。可以根据系统分析更新规划的轨迹以适应 本文描述的各种场景。

在一个实施例中，终止可以有不同的准则，例如，物理空间中只 有一个节点作为目的地。对于被动路线，只要机器人可以到达节点， 设置为可停放的任何节点都可以被设置为用于终止。另一个示例可以 是可以被视为终止区的给定区域。如果任何机器人到达该区域，那么 它们可能被视为终止。因此，系统可以对任何节点应用不同的终止条 件。

在一个实施例中，系统允许使用模式来提供最优路线规划。在路 线可以固定且无法改变的情况下，模式可以是固定的，而其它模式可 以是基于优先级的。考虑一个场景，其中有一条预定义的且不受控制 的路线，例如外部手推车可以被预编程为遵循某条路线，它可以被外 部系统控制，而该系统可能不能控制手推车的运动。系统的手推车可 以被视为动态障碍物，并遵循本文讨论的某些步骤以确保机器人不会 在其预先编程的路线上阻碍手推车。例如，系统可以使得机器人不干 扰手推车或等到手推车在其路线上移开，或者如果手推车没有移开， 那么系统可以使机器人从手推车移开并继续沿着规划的路线行驶。在规划阶段，如果预编程的路线被输入到系统，那么系统可以围绕外部 手推车进行规划，因为系统可以处置已知轨迹，如本文所讨论的。因 此，系统决定由于预编程的轨迹不能被改变或干扰，因此系统可以使 规划的轨迹避开预编程的轨迹。

在一个实施例中，搜索统计数据可以被设计为对数的，这为决策 制定系统提供对称性。每当将节点添加到树(例如，优先级树)时， 系统就可以决定接下来可以规划的路线。系统可以查询统计数据并进 行比较。用于这个过程的试探法函数的设计方式是，无论观察哪个节 点，视角都是对称的。这是一种优化技术，其使系统具有可扩展性并 且使树对树的深度增加保持不变。

在一个实施例中，系统提供自定义功能，其使得能够向系统提供 各种输入源。有一些数据已经可供系统使用。例如，边的长度来自图 形，路径的几何形状也来自图形，边可以具有速度限制以避免设备快 速移动等。图形上的每个细节都与图形ID相关联。自定义函数可以 将图形ID作为参数来计算成本。系统可以使用图形ID查询数据库并 获取所有特性以导出成本。

在一个实施例中，系统基于机器人的能力、行为或朝向来优化路 线规划。在操作环境中，例如在仓库中，一些过道可以小或窄，并且 由于机器人的结构可能较长，因此机器人可能无法转动180度或更多。 因此，系统可能必须意识到机器人的特性(诸如机器人的朝向)，而 不仅仅是机器人的位置。这个附加信息会使树搜索处理变得复杂。一 般而言，图形中的节点指示针对系统的位置。但是，关于一个节点的 信息是不够的。机器人可以在一个朝向的一个位置的一个节点上。稍 后，机器人可以以不同的朝向到达同一位置。因此，到达那两个不同 状态要求两个不同的时间线积累。系统可以在执行时通过不改变路线 而是根据机器人的需要改变朝向来处置这种复杂场景，比如叉车。例 如，叉车可以具有如携带托盘之类的偏好，那么，叉车应当面向前方， 并且如果它没有携带任何物体，那么应当面向后方。这更多的是一种 安全措施，以防止叉车造成任何损坏。在优化路线规划的同时，系统可以更新路线规划，以便叉车必须在仓库中最少的地方转弯，理想情 况下只在拐角处转弯，在那里叉车无论如何都必须转弯。此外，如果 机器人进入过道并在过道中的节点处等待，然后从过道中出来，那么 系统也可以使叉车具有最小的朝向。系统在机器人导航期间提供附加 的朝向优化。在一个实施例中，系统在规划一些场景时也可以改变路 线；例如，机器人可能必须以相反的朝向到达节点。在一些场景中， 机器人可能无法在路径上做任何种类的转弯，剩下的唯一选项是机器 人在空间巨大的地方绕道而行。稍后，机器人可以改变朝向，然后返 回到目的地。系统分析机器人的特性并且可以在规划阶段期间更新路 线，以使机器人以相反的朝向到达目的地。

在一个实施例中，系统优化路线规划，如本文所讨论的。当系统 在路径搜索处理期间在图形中搜索时，图形也会被修改以留下轨迹供 系统稍后回溯或追溯。这个处理与暂存器相似，其中存储信息以备日 后重新收集，但是一旦任务完成，暂存器上的数据就会被擦除。类似 地，在搜索的同时，信息存储在每个节点上；但是，一旦搜索完成， 信息就会被移除。一般而言，这是在发起下一次搜索之前清除所有数 据的密集过程，即计算的规模和缓存的数据量随着图形的扩展呈指数 级增长。系统提供到期特征，其中系统不是擦除所有数据，而是基于 时间戳保留数据。缓存的数据有时间戳，并且在下次发起搜索时，系 统检查数据，并且如果它是旧数据，那么系统不会使用该数据。因此， 到期特征使系统能够优化空间和计算，以确保每当发起新搜索时仅基 于时间戳清除选择性数据。

在一个实施例中，如本文所讨论的，系统优化路线规划。在树路 径搜索期间，系统一次搜索一个机器人。每个机器人具有指定的半径， 并且根据这个信息，系统可以决定机器人可能行驶通过哪些边，因为 对于机器人来说一些边可能小得多以至于无法行驶。在规划阶段，作 为优化的一部分，系统可以只考虑那些相关的有限边，并跳过或拒绝 不符合机器人行驶条件的剩余边。这种技术使系统能够更高效地计算 并使用有限的参数执行搜索。允许或拒绝边和路线规划的决定可以基 于更高级别的自主车辆的状态。状态可以包括机器人的尺寸、其朝向、 能力、行为等。

在一个实施例中，系统可以使用到达半径特征来优化路线规划。 系统可以以最少的行驶时间调用被动路线特征，或者让机器人停留在 原地。到达半径特征可以被认为是中间特征。目的地具有既定的半径 或目的地集合，并且机器人可以或者到达目的地半径内或目的地集合 中任何一个作为路线规划的一部分。例如，系统可以允许多个目的地， 比如5个目的地，而不是一个目的地。系统现在有找到通往任何一个 目的地的路径而不是只关注一个目的地的灵活选项。

图7是图示根据实施例的用于优化路线规划的处理步骤的示例性 流程图。系统基于与操作环境(如仓库)相关的一个或多个输入来解 析一个或多个节点。节点可以被认为是操作环境中的空间的区域 (701)。基于一个或多个解析的节点，规划导致生成路线规划的路 线(702)。基于规划，系统针对一个或多个关键场景(如碰撞、拥 堵、安全隐患预防、机器人损坏等)分析生成的路线规划(703)。 系统的分析技术基于本文讨论的各种机制。系统基于对生成的路线规 划的分析来优化路线规划(704)。在一个实施例中，为分析路线规 划而讨论或实现的技术中的一些也可以被用于优化生成的路线规划， 并且为优化生成的路线规划而实现的一种或多种技术可以被系统用于 分析以处置关键场景。然后将一个或多个优化的路线规划分发给一个 或多个自主车辆(705)。自主车辆具有其自己的一个或多个处理器 和存储指令供处理器执行的一个或多个存储器。自主车辆包括路线同 步和本地导航模块，以利用优化的路线规划在操作环境中进行导航。 自主车辆内的模块可以被用于发消息通知路线规划、路线的进展、同 步路线信息和操作环境内的导航(706)。

图8-10中的每个图是图示根据实施例的用于优化路线规划的处 理步骤的示例性流程图。在一个实施例中，图8-10可以被表示为图7 的扩展；但是，图8-10中包括的处理步骤也可以被认为是单独的或 实施例的组合。基于与操作环境相关的一个或多个输入所解析的一个 或多个节点可以包括基于距离和速度中的至少一个或多个将一个或多 个自主车辆与一个或多个节点相关联。一个或多个输入可以包括一个 或多个地图、图形、树、自主车辆输入、路线请求和用户输入 (801)。基于一个或多个解析的节点生成一个或多个路线规划的处 理步骤包括分析一个或多个在前自主车辆的一个或多个路线规划 (802)。系统避开被分析的一个或多个在前自主车辆的路线规划 (803)。

通过基于使用上采样处理减少自主车辆之间的争用将一个或多个 自主车辆与一个或多个节点相关联，系统基于与操作环境相关的一个 或多个输入进一步解析一个或多个节点(914)。上采样处理还可以 包括动态地增加操作环境内的节点数。

系统可以通过查询访问表中的碰撞数据来分析和优化一个或多个 生成的用于碰撞的路线规划(804)。然后，系统可以针对被查询的 碰撞数据分析一个或多个先前的路线规划(805)。在分析了先前的 路线规划之后，如果被分析的先前路线规划没有导致碰撞，那么系统 更新访问表(806)。

系统可以基于包括接收与一个或多个路线规划相关的参数的分析 来优化一个或多个路线规划。参数包括至少一个或多个优先级值、偏 好偏置、用户输入和搜索试探法(807)。基于接收到的参数更新路 线规划的排序。如果更新后的排序没有导致碰撞，那么系统可以更新 访问表以反映改变(808)。

系统可以通过基于第一自主设备的速度、行为、朝向或能力中的 至少一个或多个识别第一自主车辆的优先级值来进一步分析和优化一 个或多个生成的碰撞路线规划(809)。然后基于识别出的第一自主 车辆的优先级优先化生成的路线规划中的路线规划以提供优先化的路 线规划(810)。可以基于优先化的路线规划来避免第一自主车辆和 第二自主车辆之间的碰撞(811)。

系统可以基于优先化的路线规划避免第一自主车辆和第二自主车 辆之间的碰撞，该优先化的路线规划可以包括计算第一自主车辆的速 度以避免碰撞(812)。第一自主设备可以按照计算出的速度被移动 以领先于第二自主设备(813)，其中第二自主车辆可以通过更慢移 动、在当前地点等待或绕道到另一个地点中的至少一个来允许第一自 主车辆领先(814)。

系统可以通过估计来自一个或多个先前路线规划的碰撞计数来进 一步针对一个或多个碰撞分析和优化一个或多个生成的路线规划 (815)。基于该估计，系统可以识别一个或多个最佳先前路线规划 (816)。系统然后基于一个或多个识别出的最佳先前路线规划来优 化一个或多个生成的路线规划(817)。

系统基于包括行驶时间、路径转换、非重叠节点、优先级值、偏 好偏置、速度和可停放节点等中的一个或多个的估计来识别一个或多 个最佳先前路线规划。系统基于分析优化路线规划，包括基于自主车 辆的尺寸、遍历角落所花的时间、高度限制、旋转或从路径转弯等中 的一个或多个将成本函数应用于一个或多个自主车辆(901)。系统 优化一个或多个生成的路线规划，包括基于应用的成本函数做出决定 (902)。

系统基于分析优化一个或多个生成的路线规划，该分析包括使用 至少一种几何形状(例如，框、矩形等)表示由一个或多个生成的路 线规划覆盖的一个或多个区域(903)。系统确定一个或多个表示的 区域之间是否存在相交。一个或多个表示的区域之间的相交指示一个 或多个生成的路线规划之间存在一个或多个碰撞(904)。可以基于 一个或多个表示的区域之间的相交的确定从一个或多个生成的路线规 划中识别最佳路线规划(905)。

系统基于分析优化一个或多个路线规划，该分析可以包括确定一 个或多个生成的路线规划在不同时间点无碰撞(906)。基于一个或 多个确定的无碰撞路线规划，从一个或多个生成的路线规划中识别一 个或多个最佳路线规划(907)。

系统针对一个或多个碰撞分析并优化一个或多个生成的路线规划， 这可以包括基于一个或多个生成的路线规划的所表示的区域来计算操 作环境中的无碰撞位置(908)。可以计算的无碰撞位置包括基于自 主车辆的当前位置预见碰撞(909)。可以基于该计算生成新的路线 规划，其中生成的新路线规划不与一个或多个生成的路线规划碰撞 (910)。

系统进一步针对一个或多个碰撞分析一个或多个生成的路线规划， 包括识别一个或多个生成的路线规划中的碰撞节点之间的碰撞 (911)。系统还动态生成新节点，其中一旦碰撞节点之间的识别出 的碰撞结束，就遍历该新节点(912)。可以更新一个或多个生成的 路线规划以包括动态生成的新节点(913)。

系统可以动态生成新节点，这可以包括在新节点处等待，直到碰 撞节点之间识别出的碰撞结束(1001)。系统然后回溯到连接到碰撞 节点之一的先前节点(1002)。系统还复制具有回溯节点的边的新节 点(1003)。

系统针对一个或多个碰撞分析一条或多条规划的路线(路线规 划)，包括确定第一节点和第二节点之间的路径是否可能导致碰撞 (1004)。在一个实施例中，第一节点连接到在前节点。基于该确定， 系统动态地创建重复节点，其中重复节点的边与第一节点的边相似 (1005)。系统然后生成路线规划，该路线规划包括遍历从在前节点 到复制节点的第一路径和从复制节点到结束节点的第二路径(1006)， 并且如果第一节点和第二节点之间的碰撞结束，那么允许从复制节点 到结束节点的遍历(1007)。

系统进一步针对一个或多个碰撞分析一个或多个路线规划，包括 确定路线规划可能与一个或多个生成的路线规划发生碰撞(1008)。 然后指示自主车辆之一在特定节点处等待一段时间(1009)。计算新 位置，其中自主车辆之一在一段时间之后可以移动到该位置以避免碰 撞(1010)。基于该计算，系统生成路线规划以将自主车辆之一移动 到新位置(1011)。

系统可以通过包括识别自主车辆的状态来针对一个或多个碰撞分 析一个或多个路线规划，其中状态包括自主车辆的尺寸、朝向、能力、 行为等中的一个或多个(1012)。可以识别满足自主车辆的识别出的 状态的一个或多个生成的路线规划(1013)。系统可以拒绝不满足自 主车辆的识别出的状态的一个或多个生成的路线规划(1014)。

系统通过包括发送一个或多个自主车辆以避免导航路径来针对一 个或多个碰撞分析一个或多个路线规划(1015)。从在一个或多个自 主车辆上运行的模块接收反馈(1016)。在分析接收到的反馈之后并 基于分析，系统可以改变决定以允许在路径上导航(1017)。

应该理解的是，上述实施例仅仅是对可以构成本发明原理的应用 的多种不同的其它实施例的说明。在不脱离本发明的精神或范围的情 况下，本领域技术人员可以容易地设计出这样的其它实施例，并且我 们的意图是它们被认为在我们的发明的范围内。

前述附图表示用于描述根据一些实施例的过程的逻辑体系架构， 并且实际的实施方式可以包括以其它方式布置的一个或多个组件。可 以结合其它实施例使用其它拓扑。而且，本文描述的每个组件或设备 可以由经由任何数量的其它公共和/或专用网络进行通信的任何数量 的设备来实现。两个或更多个这样的计算设备可以彼此远离并且可以 经由(一个或多个)网络和/或专用连接的任何已知方式彼此通信。 每个组件或设备可以包括适于提供本文描述的功能以及任何其它功能 的任何数量的硬件和/或软件元素。例如，在根据一些实施例的系统 的实施方式中使用的任何计算设备都可以包括执行程序代码的处理器， 使得计算设备如本文所述那样操作。

如在本申请中使用的，术语“组件”、“平台”、“模块”和“系统”旨 在指代与计算机相关的实体，或者硬件、软件和有形硬件的组合、软 件，或者正在执行的软件。例如，组件可以是但不限于有形组件，诸 如处理器、芯片存储器、大容量存储设备(例如，光驱、固态驱动器 和/或磁存储介质驱动器)和计算机，以及软件组件(诸如在处理器 上运行的进程、对象、可执行文件、数据结构(存储在易失性或非易 失性存储介质中)、模块、执行线程和/或程序)。举例来说，在服 务器上运行的应用和服务器都可以是组件。一个或多个组件可以驻留 在进程和/或执行线程内，并且组件可以位于一个计算机上和/或分布 在两个或更多个计算机之间。词语“示例性”在本文中可以被用于表示 用作示例、实例或说明。本文描述为“示例性”的任何方面或设计都不 一定被解释比其它方面或设计优选或有利。

本文使用的术语仅用于描述特定方面的目的，而不旨在限制本公 开。如本文所使用的，单数形式“一”、“一个”和“该”也旨在包括复数 形式，除非这种排除另有明确说明。将进一步理解的是，术语“包括” 和/或“包含”，当在本说明书中使用时，指定所述特征、整数、步骤、 操作、元素和/或组件的存在，但不排除存在或添加一个或多个其它 特征、整数、步骤、操作、元素、组件和/或其组。而且，除非明确 相反地说明，否则“包括”、“包含”或“具有”(或类似术语)具有特定 特性的元素或具有特定特性的多个元素的实施例可以包括没有特定特 性的附加的此类元素。此外，对当前描述的发明性主题的“实施例”的 引用并不旨在被解释为排除也结合所述特征的附加实施例的存在。

以下权利要求中的任何部件或步骤加功能元件的对应结构、材料、 动作和等效物旨在包括用于与如具体要求保护的其它要求保护的元件 组合执行功能的任何公开的结构、材料或动作。本公开的描述是出于 说明和描述的目的而呈现的，而并非旨在是详尽的或限制到所公开形 式的公开内容。在不脱离本公开的范围和精神的情况下，许多修改和变化对于本领域普通技术人员来说将是显而易见的。选择和描述本文 公开的方面是为了最好地解释本公开的原理和实际应用，并使本领域 其他普通技术人员能够理解具有适合预期的特定用途的各种修改的本 公开。

本文描述的各种实施例的各种技术优势可以包括优化针对自主车 辆的路线规划。本文描述的各种实施例的各种技术优势可以包括为复 杂操作环境生成路线规划的能力，而对在环境中导航的自主车辆的规 模没有限制。本文描述的各种实施例使用各种技术和数据结构来实现 避免碰撞或最小化拥塞(作为在操作环境中出现的问题的示例)的步骤。各种技术优势包括系统能够处置无解或不可能的输入、防止关键 连接点处的死锁场景、在优化路线规划的同时规划预防措施以避免操 作环境中的安全隐患等。本文描述的多个实施例的各种技术优势还可 以包括优化空间和计算、采取先发制人的措施来避免关键场景等。各 种技术优势可以包括利用多机器人路线规划器来实现稳健且灵活的云 平台，以处置不同类型、朝向、能力、尺寸或制造商的自主车辆的车 队，以在复杂操作环境中提供无碰撞的优化的路线规划。其它技术优 势包括在优化路线规划的同时，在多个数据结构中表示复杂的现实生 活场景、重用现有存储装置以及经由稳健的遍历技术高效利用最近搜集的知识。

如本文所使用的，术语“可以”和“可能”指示在一组情形内发生的 可能性；拥有特定的财产、特点或功能；和/或通过表达与限定动词 相关联的能力(ability)、功能(capability)或可能性中的一个或多 个来限定另一个动词。因而，“可以”和“可能”的用法指示经修改的术 语显然适合、能够或适于指示的能力、功能或用途，同时考虑到在一 些情形下经修改的术语有时可能不合适、不能够或不适于。例如，在 一些情形下，事件或能力是可以被预期，而在其它情形下，事件或能 力不会发生，即这种区别由术语“可以”和“可能”捕获。

如本文所使用的，诸如“系统”、“模块”、“平台”或“组件”之类的 术语可以包括操作以执行一个或多个功能的硬件和/或软件。例如， 系统、模块或控制器可以包括一个或多个计算机处理器或其它基于逻 辑的设备，这些设备基于存储在(一个或多个)有形和非暂态计算机 可读存储介质(诸如计算机存储器)上的指令执行操作。可替代地， 系统、模块或控制器可以包括基于设备的硬连线逻辑执行操作的硬连 线设备。图中所示的系统、模块、组件、平台和控制器可以表示基于 软件或硬连线指令操作的硬件、指导硬件执行操作的软件，或其组合。

应该理解的是，本文描述的主题在其应用方面不限于在本文的描 述中阐述或在其附图中示出的元件的构建和布置的细节。本文描述的 主题可以与一个或多个实施例组合或相互链接以利用各种技术或组件， 并形成此处可能未明确描述的多个场景或用例。本文描述的主题能够 有其它实施例并且能够以各种方式被实践或执行。

应该理解的是，以上描述旨在是说明性的，而不是限制性的。例 如，上述实施例(和/或其方面)可以彼此组合使用。此外，在不脱 离其范围的情况下，可以进行许多修改以使特定情况或材料适应当前 描述的主题的教导。因此，本发明性主题的范围应当参考所附权利要 求以及这些权利要求所享有的等效物的完整范围来确定。在所附权利 要求中，术语“包括(including)”和“其中(in which)”用作相应术 语“包含(comprising)”和“在其中(wherein)”的简单英语等同物。 而且，在以下权利要求中，术语“第一”、“第二”和“第三”等仅用作标 签，而不旨在对其对象强加数字要求。而且，除非另有特别说明，否 则“第一”、“第二”、“A”、“B”、“C”或“D”等术语的任何使用都不表 示任何次序或重要性，而是术语“第一”、“第二”或“A”、“B”、“C”、 “D”等可以用于区分一个元素与另一个元素。另外，以下权利要求的 限制不是以部件加功能的格式编写的，并且也不打算基于35U.S.C. §112第6段来解释，除非且直到此类权利要求限制明确使用短语“用 于…的部件(means for)”后面跟着没有进一步结构的功能声明。

本书面描述使用示例来公开本发明性主题的若干实施例，并且还 使本领域普通技术人员能够实践本发明性主题的实施例，包括制造和 使用任何设备或系统以及执行任何结合的方法。本发明的主题的可专 利范围由权利要求限定并且可以包括本领域普通技术人员想到的其它 示例。如果这些其它示例具有与权利要求的字面语言没有区别的结构要素，或者如果它们包括与权利要求的字面语言没有实质性差异的等 效结构要素，那么这些其它示例旨在在权利要求的范围内。

本文描述的实施例仅用于说明的目的。本领域技术人员将认识到 可以通过对上述那些实施例的修改和更改来实践的其它实施例。