公开的实施例总体上涉及路由自主车辆。
背景技术：
：在未来几年中，自主车辆(av)技术将克服运动规划和控制中的当前挑战。例如，自主车辆将能够留在车道上、跟随汽车、避开行人并且像出租车司机那样在街道上巡逻驾驶。将仅需要告知自主车辆去往何处以及如何到达那里，从而路线规划在av驾驶世界中变得至关重要。因此，随着开发人员建立核心自主技术并开始扩展其自动驾驶车辆的车队，无论是出售给个人消费者还是启动其自己的乘车共享网络，他们都将需要有效的路由技术。在这场比赛中的赢家和输家将由运营最高效的网络、且具有最高的车辆利用率的公司来确定。技术实现要素：(a1)提供了一种路由自主车辆的方法。在包括一个或多个处理器和存储器的计算机系统上执行方法。方法包括生成用于路由自主车辆的成本模型。成本模型包括除行程时间以外的一个或多个成本，除行程时间以外的一个或多个成本选自由以下组成的组：遍历禁止自主驾驶的区域的成本、驾驶操纵的成本、自主车辆的特性的成本、天气状况的成本、一天中的时间的成本、日照角度的成本、行人交通模式的成本、非机动车辆交通模式的成本、路面状况的成本、道路使用年限的成本、在路由请求时发生的事件的成本、缺少车道线的道路的成本、充电约束的成本以及加速的成本。方法还包括接收将自主车辆从第一位置路由到第二位置的请求。方法包括：响应于路由自主车辆的请求，根据成本模型选择从第一位置到第二位置的路线，以及沿着选择的路线路由自主车辆。(a2)在(a1)的一些实施例中，响应于路由自主车辆的请求来生成成本模型。(a3)在(a1)-(a2)中的任一个的一些实施例中，成本模型是用于自主车辆的第一成本模型。方法包括接收将非自主车辆从第三位置路由到第四位置的请求。方法还包括生成用于路由非自主车辆的第二成本模型。第二成本模型不同于第一成本模型，并且不包括第一成本模型所包括的除行程时间以外的成本中的一个或多个。方法还包括，响应于路由非自主车辆的请求：根据第二成本模型选择从第三位置到第四位置的路线，以及沿着为非自主车辆选择的路线路由非自主车辆。(a4)在(a1)-(a3)中的任一个的一些实施例中，自主车辆是具有第一自主驾驶能力的第一自主车辆。成本模型是用于第一自主车辆的第一成本模型。用于第一成本模型的除行程时间以外的一个或多个成本包括对应于第一自主驾驶能力的成本。方法包括接收将第二自主车辆从第五位置路由到第六位置的请求。第二自主车辆具有不同于第一自主驾驶能力的第二自主驾驶能力。方法还包括生成用于路由第二自主车辆的第三成本模型。第三成本模型不同于第一成本模型，并且包括对应于第二自主驾驶能力的成本。方法还包括，响应于路由第二自主车辆的请求：根据第二成本模型选择从第五位置到第六位置的路线，以及沿着为第二自主车辆选择的路线路由第二自主车辆。(a5)在(a1)-(a4)中的任一个的一些实施例中，成本模型还包括行程时间成本，并且根据行程时间成本和除行程时间以外的一个或多个成本来选择路线。(a6)在(a1)-(a5)中的任一个的一些实施例中，除行程时间以外的一个或多个成本包括在路由请求时发生的事件的成本，以及在路由请求时发生的事件是施工项目或交通事故。(a7)在(a1)-(a6)中的任一个的一些实施例中，除行程时间以外的一个或多个成本包括在路由请求时发生的事件的成本，在路由请求时发生的事件是定期安排的事件，以及根据在路由请求时正发生定期安排的事件的确定，至少部分地基于定期安排的事件的成本进行选择路线。(a8)在(a1)-(a6)中的任一个的一些实施例中，除行程时间以外的一个或多个成本包括在路由请求时发生的事件的成本，在路由请求时发生的事件是定期安排的事件，以及根据定期安排的事件将在自主车辆预期到达定期安排的事件的时刻发生的确定，至少部分地基于定期安排的事件的成本进行选择路线。(a9)在(a1)-(a8)中的任一个的一些实施例中，驾驶操纵选自由车道改变、右转弯、左转弯、没有保护的左转弯、u形转弯和高速公路合并组成的组。(a10)在(a1)-(a9)中的任一个的一些实施例中，除行程时间以外的一个或多个成本包括自主车辆的特性的成本，以及自主车辆的特性是车辆类型。(a11)在(a1)-(a10)中的任一个的一些实施例中，除行程时间以外的一个或多个成本包括自主车辆的特性的成本，并且自主车辆的特性是自主车辆的自主驾驶能力。(a12)在(a1)-(a11)中的任一个的一些实施例中，除行程时间以外的一个或多个成本中的至少一个是用于特定地理区域、道路、道路内的车道或操纵的成本。(a13)在(a1)-(a12)中的任一个的一些实施例中，除行程时间以外的一个或多个成本包括：对于多条不同道路，在不同道路上对于共享天气状况的多个不同的特定道路成本。(a14)在(a1)-(a13)中的任一个的一些实施例中，除行程时间以外的一个或多个成本包括：对于多条不同道路，在不同道路上对于不同天气状况的多个不同的特定道路成本。(a15)在(a1)-(a14)中的任一个的一些实施例中，除行程时间以外的一个或多个成本包括：对于不同道路的一天中的时间的多个不同的特定道路成本。(a16)在(a1)-(a15)中的任一个的一些实施例中，除行程时间以外的一个或多个成本包括：对于不同道路的日照角度的多个不同的特定道路成本。(b1)提供了一种路由自主车辆的方法。在包括一个或多个处理器和存储器的计算机系统上执行方法。方法包括：接收将自主车辆从第一位置路由到第二位置的请求；识别自主车辆的一个或多个自主驾驶能力的集合；根据自主车辆的一个或多个自主驾驶能力的集合，选择从第一位置到第二位置的路线，以及根据选择的路线路由自主车辆。(b2)在(b1)的一些实施例中，自主车辆是第一自主车辆。方法包括接收将第二自主车辆从第三位置路由到第四位置的请求。方法还包括识别第二自主车辆的一个或多个自主驾驶能力的集合，其中第二自主车辆的一个或多个自主驾驶能力的集合包括不同于第一自主车辆的一个或多个自主驾驶能力的集合的至少一个自主驾驶能力。方法还包括：根据第二自主车辆的一个或多个自主驾驶能力的集合，选择从第三位置到第四位置的路线，以及根据为第二自主车辆选择的路线路由第二自主车辆。(b3)在(b1)-(b2)中的任一个的一些实施例中，识别自主车辆的一个或多个自主驾驶能力的集合包括：与请求一起接收自主驾驶能力。(b4)在(b1)-(b3)中的任一个的一些实施例中，方法还包括，在计算机系统上，与路由自主车辆的请求一起接收用于自主车辆的标识符。识别包括：基于标识符查找自主车辆的一个或多个自主驾驶能力。(b5)在(b1)-(b4)中的任一个的一些实施例中，方法还包括，在计算机系统上，生成用于路由自主车辆的成本模型，成本模型包括用于自主车辆的一个或多个自主驾驶能力的集合的一个或多个成本。选择包括：至少部分地基于成本模型，选择从第一位置到第二位置的路线。(b6)在(b1)-(b5)中的任一个的一些实施例中，自主车辆的一个或多个自主驾驶能力的集合包括自主车辆的传感器的能力。(b7)在(b1)-(b6)中的任一个的一些实施例中，自主车辆的一个或多个自主驾驶能力的集合包括自主车辆的可操纵性。(b8)在(b1)-(b7)中的任一个的一些实施例中，自主车辆的一个或多个自主驾驶能力的集合包括对自主车辆的限制，从用于自主车辆和/或与自主车辆相同类型的车辆中的至少一个的历史性能数据来确定对自主车辆的限制。(b9)在(b1)-(b8)中的任一个的一些实施例中，自主车辆的一个或多个自主驾驶能力的集合包括用于自主车辆的安全等级，以及至少部分地基于自主车辆的安全等级进行选择。(b10)在(b1)-(b9)中的任一个的一些实施例中，自主车辆的一个或多个自主驾驶能力的集合包括自主车辆的多个自主驾驶能力，以及至少部分地基于自主车辆的多个自主驾驶能力进行选择。(c1)提供了一种路由自主车辆的方法。在包括一个或多个处理器和存储器的计算机系统上执行方法。方法包括生成用于路由自主车辆的成本模型。成本模型包括对于交叉路口，用于遍历通过交叉路口的不同路径的多个成本。方法包括接收将自主车辆从第一位置路由到第二位置的请求。方法包括，响应于路由自主车辆的请求：根据成本模型选择从第一位置到第二位置的路线。选择至少部分地基于用于遍历通过交叉路口的不同路径的多个成本中的一个。方法包括根据选择的路线路由自主车辆。(c2)在(c1)的一些实施例中，成本模型被表示为节点和边的图，各条边具有表示成本的各自边权重。在一些实施例中，方法还包括，在计算机系统上，将交叉路口表示为多个节点和具有边权重的多条边。交叉路口的表示的每条边表示通过交叉路口的不同路径。(c3)在(c2)的一些实施例中，方法还包括，在计算机系统上，放弃通过交叉路口的禁止路径的表示。(c4)在(c1)-(c3)中任一项的一些实施例中，交叉路口是多条道路的交点，多条道路中的每条道路具有一个或多个成本，一个或多个成本不同于用于遍历通过交叉路口的不同路径的多个成本。(c5)在(c1)-(c4)中任一个的一些实施例中，用于遍历通过交叉路口的不同路径的多个成本包括：用于遍历通过交叉路口的不同路径中的一条的驾驶操纵的一个或多个成本。(c6)在(c5)的一些实施例中，驾驶操纵选自由车道改变、右转弯、左转弯、没有保护的左转弯、u形转弯和高速公路合并组成的组。(d1)提供了一种路由自主车辆的方法。在包括一个或多个处理器和存储器的计算机系统上执行方法。方法包括：接收从不同于自主车辆的第二车辆上的相机获得的信息；通过使用从第二车辆上的相机接收到的信息的图像分析，自动地识别道路状况；以及接收将自主车辆从第一位置路由到第二位置的请求。方法还包括，响应于请求，生成用于路由自主车辆的成本模型。成本模型包括从接收自第二车辆上的相机的信息自动地识别出的道路状况的成本。方法包括根据成本模型选择从第一位置到第二位置的路线以及根据选择的路线路由自主车辆。(d2)在(d1)的一些实施例中，生成成本模型包括：响应于请求更新先前的成本模型。(d3)在(d1)-(d2)中的任一个的一些实施例中，方法包括，在计算机系统上，确定在请求时是否存在道路状况。在一些实施例中，根据在请求时存在道路状况的确定，将道路状况的成本包括在成本模型中。(d4)在(d1)-(d3)中的任一个的一些实施例中，从接收自第二车辆上的相机的信息自动地识别出的道路状况是选自由天气状况、由于天气引起的道路状况、由于施工引起的道路状况以及由于交通事故引起的道路状况组成的组的状况。(d5)在(d1)-(d3)中的任一个的一些实施例中，从接收自第二车辆上的相机的信息自动地识别出的道路状况是选自由日照角度、行人交通、非机动车辆交通、路面状况和缺少车道线组成的组的状况。(d6)在(d1)-(d5)中的任一个的一些实施例中，相机是行车记录仪。(e1)提供了一种用于乘车共享的交通网络的路由方法。方法包括存储多个第一乘客的表示。多个第一乘客的表示中的每个包括多个第一乘客中的相应第一乘客的请求上车位置和请求下车位置。方法还包括存储多个车队车辆的表示。方法还包括生成地理地图的图表示，图表示包括多个第一乘客的请求上车位置和请求下车位置。方法还包括生成多个第一乘客和车队车辆的状态图表示。状态图表示包括通过边连接的多个节点。状态图表示的多个节点中的每个节点表示多个第一乘客和车队车辆的候选状态。状态图表示的相应边表示相应车辆使乘客上车或下车的动作。相应边具有至少部分基于地理地图的图表示的遍历的成本。方法还包括生成用于车队车辆的路线集合，包括将待上车和待下车的多个第一乘客中的每个乘客分配给车队车辆的相应车辆。通过评估包括各条边的成本的成本模型，对状态图表示进行图搜索而生成用于车队车辆的路线。方法还包括根据生成的路线集合路由车队车辆。(e2)在(e1)的一些实施例中，车队车辆包括多个自主车辆。(e3)在(e1)-(e2)中的任一个的一些实施例中，多个车队车辆由单个运营商运营。(e4)在(e1)-(e3)中的任一个的一些实施例中，方法包括从不同于多个第一乘客的第二乘客接收乘坐请求，其中，请求包括第二乘客的请求上车位置和请求下车位置。方法还包括根据一个或多个最便宜插入标准更新车队车辆的相应车辆的路线，包括将待上车和待下车的第二乘客分配给相应车辆。(e5)在(e4)的一些实施例中，更新车队车辆的相应车辆的路线包括：将第二乘客的上车位置和下车位置插入到相应车辆的现有路线中，而无需修改已分配给相应车辆的乘客的上车和下车位置。(e6)在(e4)的一些实施例中，更新车队车辆的相应车辆的路线包括：将第二乘客的上车位置和下车位置插入到相应车辆的现有路线中，以及将已分配给相应车辆的乘客重新分配给车队车辆的不同车辆。(e7)在(e1)-(e6)中的任一个的一些实施例中，生成用于车队车辆的路线集合包括：基于第一乘客的请求上车位置，将第一多个乘客中的每个乘客分配到一个或多个候选上车位置；基于第一乘客的请求下车位置，将第一多个乘客中的每个乘客分配到一个或多个候选下车位置；根据他们被分配的候选上车位置和下车位置对第一多个乘客进行聚类；将车队车辆中的各个车辆分配到多个集群；以及根据为车队车辆的各个车辆分配的多个集群，并行化车队车辆的路由。(e8)在(e7)的一些实施例中，方法还包括：从不同于多个第一乘客的第二乘客接收乘坐请求。请求包括第二乘客的请求上车位置和请求下车位置。方法还包括：通过将第二乘客分配到现有集群以及更新分配到现有集群的车辆的路线，更新车队车辆的相应车辆的路线，包括将待上车和待下车的第二乘客分配给相应车辆。(e9)在(e1)-(e8)中的任一个的一些实施例中，进行图搜索包括：通过放弃来自状态图表示中的对于其成本函数的最低界限超出车队车辆的已确定路线集合的成本的任何节点的后续探索，使用最低界限启发法来限制在状态图表示中探索的状态数量。(e10)在(e1)-(e9)中的任一个的一些实施例中，成本模型包括第一乘客的上车等待时间。(e11)在(e1)-(e10)中的任一个的一些实施例中，图搜索是双向搜索。本公开的一些实施例提供一种计算机系统(例如，服务器系统)，计算机系统包括一个或多个处理器以及存储一个或多个程序的存储器。一个或多个程序存储指令，指令当被一个或多个处理器执行时，使计算机系统执行本文描述的任何方法。本公开的一些实施例提供了一种自主车辆。自主车辆包括计算机系统，计算机系统包括一个或多个处理器和存储一个或多个程序的存储器。一个或多个程序存储指令，指令当被一个或多个处理器执行时，使一个或多个处理器执行本文描述的任何方法。本公开的一些实施例提供了一种存储指令的非暂时性计算机可读存储介质，指令当被具有一个或多个处理器的计算机系统执行时，使计算机系统执行本文描述的任何方法。附图说明在附图的图中以示例而非限制的方式示出本文公开的实施例。在整个附图中，相似的附图标记指代对应部分。图1是示出常规(非自主车辆)路线的示例的二维地图。图2是示出根据一些实施例的自主车辆路线的示例的二维地图。图3a-3b是示出根据一些实施例的自主车辆路由引擎的架构的框图。图4a是示出根据一些实施例的交叉路口的示例的二维鸟瞰图，交叉路口被表示为单个节点。图4b是示出根据一些实施例的交叉路口的示例的二维鸟瞰图，交叉路口被表示为多个节点(而不是单个节点)和多条边，其中一些边表示通过交叉路口的路径。图5是示出根据一些实施例的路线特征的示例的二维鸟瞰图，其中车道级细节和约束可用于为自主车辆提供可驾驶路线。图6是示出根据一些实施例的另一示例的二维鸟瞰图，其中通过交叉路口的路径在图中用其自身的边表示。图7是示出根据一些实施例的严重惩罚人为干预区域过渡的路线的示例的二维鸟瞰图。图8是示出路由图的常规示例的二维地图，其中道路是边、且交叉路口是节点。图9是在晴天和大雪情况下道路(以照片示出，也包括在图9中)的饱和度直方图。根据一些实施例，饱和度直方图是分析的示例，可以用于自动地确定道路状况并为道路分配成本或属性，然后在自主车辆路由中使用成本或属性。图10是根据一些实施例的增强的级联haar分类器的可视化。图11是根据一些实施例的级联lbp分类器的框图屏幕截图。图12是根据一些实施例的用于实时对象检测的“您只能看一次(youonlylookonce，yolo)”架构的框图。图13是示出根据一些实施例的使用卷积神经网络模型检测各种交通标志的一系列照片。图14是示出根据一些实施例的客户端-服务器环境的框图。图15a-图15b是根据一些实施例的用于使用具有除行程时间以外的成本的成本模型的车辆路由方法的流程图。图16是根据一些实施例的使用具有车辆约束的成本模型的自主车辆路由的方法的流程图。图17是根据一些实施例的使用具有交叉路口成本的成本模型的自主车辆路由的方法的流程图。图18是根据一些实施例的将实时数据叠加到自主车辆路由成本模型上的方法的流程图。图19是示出根据一些实施例的用于路由车辆车队的示例架构的框图。图20示出根据一些实施例的分配到请求上车位置和下车位置的停靠站。图21示出根据一些实施例的用于未分组和分组的乘车请求的乘车请求图。图22是示出根据一些实施例的车辆集群对的创建的二维空间表示。图23是根据一些实施例的用于多个车辆的组合(例如，联合的)路线的二维地图。图24是根据一些实施例的多个乘客和车辆的状态图表示。图25a-图25b是示出根据一些实施例的将插入点添加到现有路线的二维空间表示。图26a-图26c是根据一些实施例的用于乘车共享交通网络的路由方法的流程图。具体实现方式自主车辆不能稳健地处理它们在道路上可能遇到的每种情况。为了解决这个问题，本公开提供考虑了专注于av的需求和约束(例如，对于自主车辆来说特别重要、尽管可能不是唯一重要的需求和约束)的路由设备和方法。这些方法和设备通过避免自主车辆无法处理或可能难以处理的情况来改进它们。通过允许自主车辆避免这种情况，本文描述的路由设备和方法使自主车辆对乘客和行人更安全，甚至可以挽救生命，并且还可以使在自主车辆中的乘坐也更舒适。本公开提供在车辆路由(例如，自主车辆路由)中使用成本模型的方法和设备。如本文所使用的，在车辆路由的上下文中，术语“成本模型”是指与行程(即，正在路由的行程)的各个方面相关联的“成本”的分配或安排。成本模型中的成本不必也通常不是财务成本。例如，根据一些实施例，本文提供的成本模型使用行程时间成本、等待上车的乘客的成本、安全成本(例如，自主车辆进行没有保护的左转弯的成本)以及许多其他成本。在某些实施例中，路线的总成本是该路线的所有单独成本的和(例如，已分配成本的路线各个方面的所有成本的和)。一般而言，优先选择具有较低成本的路线而不是较高成本的路线。因此，例如，将较高成本分配给没有保护的左转弯意味着，本文提供的系统和方法将生成具有更少的没有保护的左转弯的路线。作为另一个示例，将较高成本分配给等待上车的乘客将导致待上车乘客的等待时间缩短，即使这意味着花费在车辆上的时间更长或使车辆进行更多的没有保护的左转弯。换句话说，本文描述的成本模型使用数值成本来加权潜在路线的各个方面的相对偏好。为此，一些实施例提供了专注于自主车辆(av)的方法和设备，这些方法和设备考虑(例如，优化)除时间和距离以外的成本，考虑例如用于人为干预区域过渡的不同权重、天气和行人区域。此外，自主车辆的操作得益于高清(hd)和车道级地图。但是，此类高清地图的覆盖范围将逐渐增加。本公开通过提供提供混合路线的路由方法和设备来弥合差距，其中安全驾驶员可以在常规道路网络中接管，并且当hd地图数据可用时允许自主车辆自行驾驶。例如，常规(非av)路由方法可能会创建图1示出的路由。从自主车辆的角度来看，此路线存在许多问题。路线没有考虑哪些操纵对于自主车辆是安全的，或考虑av安全的上车和下车点。例如，路线100(例如，粗虚线)包括下车点102，其不被视为av安全的下车点。路线100还包括交叉路口104。交叉路口104创建非法的av操纵点(例如，进行左转弯)。因此，没有基于特定自主车辆的约束来定制路线。路线无助于优选自主车辆区域(例如，避开仅人类区域)、减少必要的人为干预次数或使车辆自主操作的时间最大化。例如，路线100还包括人为干预区域106。另外，通常不以自主车辆可以使用的格式(例如，路线几何形状通常沿着道路的中心)来表示从常规路由引擎生成的路线。例如，在双向道路中，中心线沿着划分对向交通的车道线。由于自主车辆在车道上行驶，因此它们可能需要关于这些车道定义的其路线。试图将以道路为中心的路线“地图匹配”为以车道为中心的地图的技术容易发生匹配错误，尤其是在道路几何形状通常不对应于车道几何形状的交叉路口处。此外，取决于自主车辆的自主水平，av路线可能需要或可能不需要特定于运动规划者的更多细节。最终，上面示出的路线不支持av级数据集(例如，具有车道数据)和道路级数据集。本文描述的路由方法和设备在路由自主车辆时可以考虑这些问题。例如，图2中所示的路线200(例如，由粗虚线表示)可以根据本文描述的实施例生成。图2中所示的路线200考虑了哪些操纵对自主车辆是安全的(例如，避免交叉路口104)，考虑了av安全的上车和下车点(例如，避免不安全的下车点102)并考虑了人为干预区域(例如，避免人为干预区域106)。可以基于特定自主车辆的约束来定制诸如图2所示的路线200的路线。本文描述的路由方法和设备可以处理人类和自主车辆需求。例如，这些方法和设备包括以下特征中的一些或全部：·车道级地图和道路级地图二者；·考虑可用的道路级交通和车道级交通二者；·考虑自主车辆约束(例如，在成本模型中用于自主车辆约束的成本的分配)，包括特定于单个车辆或请求的约束(例如，由于特定品牌或型号仅可以自主行进在诸如无分隔物的双向高速公路的某些类型的道路上的事实而产生的成本)，以及通常用于自主车辆的约束(例如，方法和设备选择专注于av的路线，其避免列入黑名单区域并减少/最小化人为干预)；·针对不同目标的改进/优化，例如最快的时间、最大的自主时间；·实时改变成本的灵活性；·考虑用于自主车辆的最佳上车/下车位置；·考虑收费约束；·用于离线路由(例如，在车辆中或车载上)和在线路由(例如，在云端)的统一sdk；·除效率以外还关注安全性；·具有灵活架构的可扩展性；以及·在线和离线模式，后者用于在自主车辆失去连接时。表1突出显示根据某些实施例的av-路由和常规路由之间的一些差异。表1从根本上说，路由依赖于3个组成部分：节点和边的图、边权重以及遍历该图的算法。该图表示自主车辆可行进的车道和/或道路的可遍历空间。边权重是遍历每条道路/车道的成本。诸如dijkstra，a*和bidirectionaldijkstra的算法会探索加权的图，以找到使起点和终点之间的成本函数最小化的路径。在一些实施例中，路由方法和设备利用从常规道路地图以及车道级地图建立的混合地图。例如，可以从开放街道地图(osm)中获取基层道路地图。车道级地图可以从oem的提供商和其他第三方提供商获得，也可以从传感器数据(例如，自主车辆传感器数据或来自人类驾驶车辆的行车记录仪数据)创建。根据基本道路地图，构造默认边权重的静态道路图(例如，考虑到人为干预区域、速度限制、自主车辆转弯限制等)。在运行时，实时数据层保留在存储器中，以侦听来自各种实时数据管道的更新。对于每个请求，可以创建新的成本函数(例如，成本模型)并将其用于遍历图。图3a是根据一些实施例的自主车辆路由引擎的架构的示例。例如，客户端330是待路由的自主车辆或与自主车辆相关联的电子设备。实时数据更新340包括服务器系统，服务器系统接收和/或跟踪实时交通342、历史交通344和av事件346，并且将交通和事件处理/转发给av路由引擎338，使得av路由引擎338可以为客户端330创建/更新路线。av路由引擎338还使用从混合地图336接收到的信息(例如，基于道路级地图332和车道级地图334)来创建/更新用于客户端330的路线。图3b示出用于车辆车队的另一个示例性架构(例如，所谓的“堆栈”)。图3b中所示的示例性架构的特征可以可选地补充、替换关于图3a描述的架构的特征或与关于图3a描述的架构的特征相结合。在一些实施例中，车辆车队是包括自主车辆(例如，自主车辆308)和非自主车辆(例如，非自主车辆306)的混合车辆车队。在一些情况下，车队包括不同类型的车辆(例如，汽车、自行车、踏板车和/或送货机器人)的混合。在一些情况下，车队通过将乘坐者从第一位置运送到第二位置来为乘坐者(例如，乘坐者/消费者304)提供服务。在某些情况下，例如通过将物品交付给消费者(例如交付来自餐馆的餐点、交付来自零售商店的包裹)，车队为其他消费者提供服务。为了促进使用混合车辆车队提供这些服务，堆栈包括提供车队管理服务和路由信息的第一服务器系统300。第一服务器系统300包括一个或多个处理器(例如cpu)和存储用于参考第一服务器系统描述的模块(例如，地图匹配/定位模块316、路由引擎310、地理空间竖井型数据库312和归一化数据模式314)的指令的存储器。第一服务器系统300与第二服务器系统302上的车队管理器303连接。在图中所示的示例性架构中，第二服务器系统302充当第一服务器系统300的客户端，而乘坐者、消费者(例如，乘坐者/消费者304)和车辆(例如，非自主车辆306和/或自主车辆308)充当第二服务器系统302的客户端。在一些实施例中，第二服务器系统302是与第一服务器系统300分离且不同的服务器系统。第二服务器系统302包括一个或多个处理器(例如，cpu)以及存储用于参考第二服务器系统302描述的模块(例如，车队管理器303)的指令的存储器。指令由一个或多个处理器执行。在一些情况下，车队管理器303是由第一服务器系统300服务的多个车队管理器中的一个。例如，车队管理器303可以是用于特定公司车队的车队管理器，并且第一服务器系统300可以为多个公司车队提供服务。第一服务器系统300包括路由引擎310，路由引擎310根据本文描述的各种路由方法(例如，如参考图17描述的及其他)为自主车辆308和非自主车辆306提供路线和估计的到达时间。在一些实施例中，为每个车队实例化路由引擎的不同实例。第一服务器系统包括存储地理空间数据(例如，存储有对应地理位置，诸如纬度和经度的数据)的一个或多个地理空间竖井型数据库312。地理空间竖井型数据库312包括从sd地图数据提供者接收到的“标准清晰度”(sd)地图数据(例如，诸如街道位置/几何形状、街道名称的数据)。sd地图数据提供者的一个示例是开放街道地图(openstreetmap)。在一些实施例中，地理空间数据还包括从hd地图数据提供者接收到的“高清晰度”数据，诸如车道级数据(例如，车道位置/几何形状、关于允许从哪些车道进行哪些操纵的信息)。地理空间数据还包括来自其他数据提供者的数据，诸如从市政当局接收到的有关施工和道路封闭的信息、实时数据(如上参考图18描述获取的)、交通数据和其他数据。另外，地理空间竖井型数据库312存储各个车队中的车辆的位置(例如，地图匹配的位置)。在一些实施例中，地理空间竖井型数据库312存储覆盖同一地理区域的数据的多个不同实例。例如，地理空间竖井型数据库312存储覆盖同一区域的多个地图(例如，具有地理空间数据覆盖在那些地图上)。在某些情况下，不同的地图将包括适合特定车队车辆的数据(例如，车队将包括自主车辆和送货机器人，而地理空间竖井型数据库将存储具有适合该车队车辆类型的信息的一个或多个地图)。地图的一些实例可能对任何客户端(例如，任何车队管理器)都是公共的，而地图的其他版本可能对某些客户端(例如，某些车队管理器)是私有的。例如，相应车队可以许可来自相应hd地图数据提供者的数据。因此，由相应hd地图数据提供者提供的数据是竖井型的并且对相应车队的车队管理器(例如，车队管理器303)是私有的。在一些实施例中，从各个数据源(例如，sd地图数据提供者318、hd地图数据提供者320、其他数据提供者322)摄取的数据通过归一化数据模式314被归一化。归一化数据模式314将数据从多个第一格式转换为独立于第一格式(例如，独立于数据源)的归一化第二格式。第一服务器系统300还包括地图匹配/定位模块316，其将从车辆接收到的位置数据与地图位置(例如，存储在地理空间竖井型数据库312中的地图的位置)进行匹配。例如，一些车辆生成位置数据(例如gps数据或来自另一个定位系统(诸如glonass、galileo或beidou)的数据)。在某些情况下，此数据是有噪声的，并且可能会使车辆远离其实际位置，例如在人行道上或建筑物中。地图匹配/定位模块316从相应车辆接收位置数据(例如，通过与第一服务器系统300连接的车队管理器303)，将有噪声的位置数据与可能的道路位置和/或车道位置进行匹配，并且更新车辆在地理空间竖井型数据库312中的“地图匹配的”位置(例如，更新匹配的位置)。另外，出于各种目的(例如，监视车队)，将地图匹配的位置提供给车队管理器303。如上所述，堆栈包括第二服务器系统302，第二服务器系统302可选地与第一服务器系统300不同且分离。第二服务器系统302包括车队管理器303，其充当第一服务器系统300的客户端(例如路由引擎的客户端)。车队管理器303调度车辆(例如，非自主车辆306和/或自主车辆308)，为车辆分配路线，以及将集结位置(staginglocation)分配给在其对应车队内的车辆(例如，使用由路由引擎提供的信息和路线)。另外，车队管理器303与乘坐者/消费者304连接(例如，经由乘坐者的智能手机或其他设备上的移动应用)。车队管理器303经由乘坐者/消费者304的移动设备为乘坐者/消费者304提供诸如估计的到达时间(eta)和行程成本的信息。在一些实施例中，车队管理器303还从单个车辆接收数据，诸如车辆位置(例如可选地包括指定车道位置的位置和方向(例如，车辆指向的方向))。在一些实施例中，自主车辆包括av平台，其用作用于自主车辆的自主功能的操作系统和框架。自主车辆包括一个或多个处理器(例如，cpu)和存储用于参考自主车辆描述的模块(例如接口模块、av平台、用于传感器/控件的驱动器)的指令的存储器。指令由一个或多个处理器执行。av平台的示例是开源的机器人操作系统。车队管理器(例如，车队管理器303)通过接口模块与自主车辆(例如，自主车辆308)交互，接口模块是在av平台上运行以提供路线到av平台并从自主车辆的传感器接收数据的模块。例如在一些情况下，接口模块由路由引擎的开发人员提供，以充当第一服务器系统与自主车辆的机器人之间的联络。av平台从自主车辆的传感器接收传感器数据，并且在一些情况下，使传感器数据可用于车队管理器，其可以使传感器数据可用于堆栈中的更下方，例如可用于地图匹配/位置模块。在一些实施例中，av平台通过线控驱动系统将命令(例如，加速命令、中断命令、转弯命令等)发送到自主车辆的控件。构造路由图为了支持上面的灵活成本场景，构造了可以处理转弯成本和车道过渡成本的路由图的表示。在一些实施例中，成本模型包括，对于交叉路口，用于遍历通过交叉路口的不同路径(例如，直行通过交叉路口的路径、交叉路口处的左转弯、交叉路口处的右转弯或交叉口处的u形转弯)的成本。为此，可将交叉路口表示为多个节点(而不是如图4a所示的单个节点400)和多条边，其中一些边表示通过交叉路口的各个路径。例如，左转弯被表示为由具有第一权重的第一边连接的节点402和404。直行通过交叉路口的路径被表示为由第二边连接的节点402和406，第二边具有第二权重(例如，不同于第一权重的权重)。通过交叉路口的非法路径(例如，向右转弯沿着单向街道走错路)未表示在图中，因此不能通过路由过程被探索到。例如，在节点402和408之间没有示出边(例如，右转弯)。类似地，在必要时在车道之间添加车道过渡边，这可以捕获自主车辆改变车道的成本。例如，只要道路地图中的车道数量发生变化，便会添加车道过渡边。图5示出车道过渡的示例。图5的道路地图中的第一道路500是单车道。第二道路502包括两个车道(例如，双车道)。存在现实世界情况，车道级的详细信息和约束可用于为自主车辆提供可驾驶(例如，最佳)路线，如图5中的示例所示。在一些实施例中，图边不是与权重直接相关联，而是与标签或属性相关联(例如，将边标记为人为干预区域)。成本函数(例如，实时)评估每条边的实际成本。这允许图的某些方面保持静态(例如，通过交叉路口的可能路径)，同时允许与图的那些方面相关联的成本是动态的(例如，自主车辆针对人为干预区域可以请求具有特别强烈偏好的路线)。通常，将道路图中的边表示为单向或双向。这在行业中很普遍，大多数路由引擎都使用复杂的表示来基于其方向性处理边。但是，为了更简单地表示图，一些实施例消除图中的双向边。因此，所有边都是单向的，并与其几何形状对齐。边可分为两类之一：“原始边”或“过渡边”。在扩展原始表示时会创建过渡边，并且可以捕获特定原始边之间的转弯/过渡成本。这种扩展有助于正确捕获转弯成本，并提供低成本(例如最佳)路径。图6示出一个说明性示例。如果在原始图600(在图6的左侧)上生成从起点602到终点604的路线，一旦已经探索到给定节点(即，一旦节点已在dijkstra的最短路径算法中标记为解析)则可以添加转弯成本。在这种情况下，甚至在查看来自d是否更便宜之前，就完全有可能将c和e之间的节点标记为解析。在此示例中，路径a→c→e具有总成本：c(a→c→e)＝c(a) t(a→c) c(c) t(c→e) c(e)第二条路径具有以下成本：c(a→b→d→e)＝c(a) t(a→b) c(b) t(b→d) c(d) t(d→e) c(e)请注意，在以下情况下，第二条路径的成本可能较小：c(a→b→d→e)<c(a→c→e)c(a) t(a→b) c(b) t(b→d) c(d) t(d→e) c(e)<c(a) t(a→c) c(c) ......t(c→e) c(e)c(b) c(d) t(a→b) t(b→d) t(d→e)<c(c) t(a→c) t(c→e)t(c→e)>c(b) c(d)-c(c) t(a→b) t(b→d) t(d→e)-t(a→c)这表明可以任意提高从c→e的转弯成本，并在原始表示中找到次优路径。但是在扩展图606中，因为已经添加了额外的节点以处理额外的状态，所以在考虑两条边之间的过渡成本时可以找到最佳路径。在过渡被表征为极难进行(例如，自主车辆的没有保护的左转弯)的情形下，就会发生这种情况。为了完全表征扩展图606，显著增加节点和边的总数。在图6提供的示例中，节点从3个节点(在图600中)增加到8个节点(在扩展图606中)，总边从5条边(在图600中)增加到10条边(在图606中)。这些增加可以通过在强调灵活性和正确性的小型道路网络中操作来弥补(offset)。原始边和过渡边在属性方面具有差异。表2示出根据某些实施例的原始边和过渡边之间的一些属性差异：表2特征/属性原始边过渡边几何形状是否街道名称是否转弯成本否是高速公路类是否时间成本是是(可选的)距离成本是否av-人过渡否是也可以容易地处理转弯图表示中的硬编码转弯限制。如果两条边之间的转弯受到限制，则将两条边之间的过渡边完全被排除。遍历图(选择路线)在遍历期间，成本模型可用于评估被探索的边的成本(例如，基于与边相关联的标签或属性将权重分配为边的成本)。这通过使用成本函数来完成(例如，在运行时由客户请求确定)。可以返回使该成本函数最小化的最佳路径。成本函数考虑的成本的示例包括但不限于：·时间：遍历边的时间量·距离：边的距离(例如，以米为单位)·转弯：与转弯相关联的成本(对于所有非过渡边，此成本返回0)·人为干预：与从非人为干预到人为干预区域相关联的成本(对于所有非过渡边均返回0)。类似地，如果需要，路由可以完全限制某些边或过渡。客户端可以定制自己的成本线性组合(或对应成本函数)，以为边创建混合权重，像这样：其表示边e的以下权重：权重(e)＝时间(e) 0.25*距离(e) 转弯(e) 10*人(e)不存在尺寸转换包括在此。每个成本函数都单独没有单位，因此可以轻松地与其他成本进行比较。图7示出极重地惩罚人为干预区域过渡的最佳路线的示例。例如，从起点702到终点704的第一路线(涉及起点702和704之间的直线(例如，最短路径))包括人为干预区域700。当人为干预区域的惩罚较大时，为了避免人为干预区域700，起点702和704之间的最佳路线反而采用更长的路径。随着收集更多数据，可以为自主车辆操作的不同模式(例如“安全”模式或“避免人为干预”模式)捕获最佳权重。因此，不同的路由模式可以使用不同的成本模型和函数，从而导致不同的路线。因此，根据一些实施例，可以在选择模式之前进行路由。在一些实施例中，在静态数据上，实时数据层周期性地更新图上的边属性并且可以影响路径计算。例如，实时交通数据管道可以为边的子集提供实时速度，或者自主车辆传感器数据可以提供实时道路或车道封闭信息。如果期望，客户端可以使用历史成本函数覆写实时信息。最短路径问题是找到从起点到终点的路径的问题，其根据成本函数优化(例如最小化)路径边的权重和。为了计算此最佳路径，路由取决于3个组成部分：图、其权重和遍历图的算法。图是表示可遍历空间的平面拓扑。对于人类路由，此图直接与道路网络相关，其中边和节点分别表示路段和交叉路口。例如，图8示出路由图的常规示例，其中道路是边并且交叉路口是节点。在本节中，讨论仅限于边权重为非负数的图。其他图表示也是可能的。例如，基于边的图通过采用图的对偶来表示，其中节点映射到路段，而边映射到后续路段之间的过渡。该表示可能是有用的，因为它允许引入或移除过渡边，以便分别捕获转弯成本和限制。图边表示整条道路(忽略车道)。即使仅使用道路表示，该图也非常大。例如，全球osm构建当前包含大约40亿个唯一节点。为了改善数据爆炸，其他图表示构建多个级别的详细信息，划分为子图或计算额外元数据(诸如到地标的距离)。找到更严格的下限使得a*更具选择性，因此更快。alt算法(a*，地标、三角形不等式)预先计算了从图中每个节点到称为地标的节点集合的最短路径成本，并利用三角形不等式为a*预先计算了甚至更严格的下限。具体而言，对于终点节点t、地标节点l和节点x：这意味着相减的距离d(x,l)-d(t,l)可以用作实际距离d(x,t)的下限。实际上，选择了许多地标，并且可以采用最大的相减距离以便获得最严格的下限启发法。为了找到最短路径，每条图边必须具有关联的权重，其表示遍历的成本。在简单的路由算法中，路由边的成本是车辆在其上行进所需的时间。通常成本是标量值，但它也可以具有多个成本(例如时间和距离)和/或置信概率。前者使用帕累托/多值优化，后者使用随机路由。对于时间相依路由问题，成本自身会随着时间而变化，并且需要采用不同方法来进行最优地求解。被创建来在非负数的加权图上找到最短路径的第一算法是dijkstra算法和bellman-ford算法。不幸的是，即使是城市规模的道路图，这些方法也无法很好地扩展。最近的进展集中在以巧妙的方式应用这些基本图探索算法以缩放到真实世界图尺寸。一种改进是从起点和终点节点都应用dijkstra，并将巧妙的终止条件应用于两个搜索的边界以减小搜索空间的大小。a*搜索算法是另一种流行的技术，其使用启发式成本指导dijkstra的搜索，启发式成本充当最优成本的下限。常规地，a*使用优先级队列供节点访问，其中节点x的优先级是其当前成本d(s,x)和其启发式成本h(x)的和。反过来，这有助于以过高的成本使节点去优先级。最短时间成本的典型下限是从节点到终点的半正矢距离除以最大车速。可以将a*看作是dijkstra的朴素路由算法利用零成本启发法(即，对于所有x，h(x)＝0)的一般化。鉴于权重为非负数，a*还可以用于最优地求解在运行时确定的加权成本函数。具体来说，对于成本函数fi的集合：f(x)＝∑wifi(x)f(x)上的最小值是fi(x)的最小值的加权和的上限。通过将值f*、fi*分别定义为f(x)、fi(x)的最小值，以及将x*、xi*分别定义为这些函数的最小化参数：fi*≤fi(x)fi*≤fi(x*)wifi*≤wifi(x*)∑wifi*≤wifi(x*)＝f(x*)因此，最小值的加权和可以用于每个函数，作为运行时所需的任何混合成本函数的有效下限。这也使alt成为一种灵活成本核算的引人注目的算法。用于为自主车辆的车队提供动力的实时数据随着自主车辆(av)的开始运行，它们在很大程度上依赖于先前收集和处理的高清(hd)地图数据(例如，包含车道和方向信息的数据)来实现如定位的功能，定位允许自主车辆能够跟踪其在现实世界中的位置。然而，为了更安全、更有效地运行，自主车辆得益于单独的实时数据层。例如，实时从自主车辆和非自主车辆收集的位置数据(例如gps数据或来自其他定位系统的数据，诸如glonass、galileo或beidou)指示实时交通，这有助于产生更准确的估计的到达时间和更有效的路线。在一些实施例中，相机系统被使用在自主车辆(例如，自主车辆相机传感器)上和人类驾驶车辆(例如，行车记录仪)上，以收集关于道路状况(例如，道路封闭、障碍物、交通等)的实时数据。该信息在被用于路由自主车辆时，允许自主车辆避开某些道路或在其周围安全行驶。表3是这种道路状况(cv＝计算机视觉)的部分列表：表3如本文所提及，“许可”是指可从另一来源获得的数据。例如，可以从政府(例如，市政府、地方政府、州政府、联邦政府)获得的有关施工区域的数据可得到政府的许可。许可数据可能是完整的或不完整的。当不完整时，可以使用其他获取数据的方法(例如，使用gps或其他定位技术的计算机视觉(cv))来补充数据。如表3示出的，计算机视觉检测相机数据中影响自主车辆安全性和效率的许多特征。在一些实施例中，利用标记和未标记的相机数据、卷积神经网络(cnn)和/或云计算和边缘计算两者来解决计算机视觉检测问题。表4列举了进一步示例(rt是实时的)：表4以下列表以及表5提供可以使用计算机视觉检测并在成本模型中考虑的道路状况的更多示例：·天气或由于天气(例如，晴、雨、风、雪、雾)引起的道路状况；·日照角度(例如，小于、或小于或等于相对地平线的指定度数(例如20度)的角度可能会损害视觉传感器，从而影响基于视觉的系统)；·复杂的环境(例如，密集行人或自行车交通)；·路面状况或类型(例如，新的、现代的、古代的、开裂的、铺好的、坑洼的、泥土、沥青、鹅卵石)；以及·事件(例如，施工区域、警察、道路封闭、事故、诸如游行的事件、临时监管标志)。一些实施例仅检测影响自主车辆安全性和效率的特征(例如，放弃不影响自主车辆安全性和效率的特征的检测)。这种受约束的检测空间使得许多特定图像的捕获能够解决特定的检测问题。例如，在一些实施例中，计算机视觉不识别与检测问题无关的对象。另外，有监督的学习技术(如上述的cnn)比无监督的学习更为优选，即使后者的数据量更大，并且有可能为更强大的人为智能铺平道路。在这些检测和分类问题中的另一个数据优势是对历史图像以及实时图像的访问。例如，历史图像的位置(例如，gps位置)被捕捉到道路网络，以便多次关联同一道路的图像。特定于域的数据有助于我们更可靠地检测实时数据中的异常值(例如天气和道路施工)，并允许我们对未标记的数据使用一些无监督的学习方法(例如，下面的对天气分类进行聚类)。一些实施例利用云计算和边缘计算两者。在传统的云计算中，所有数据(例如，来自物联网设备的数据)都被传输到云端以进行批处理(例如，用于计算机视觉的分布式机器学习)。不幸的是，这不仅需要大型且复杂的集群来满足计算需求，而且成为实时使用数据的瓶颈。数据的价值会随着时间的推移而迅速降低。借助边缘计算，移动设备上的计算能力被用来执行类似但精度较低的检测，以在检测管道中尽早过滤掉噪声。在云端，可以通过由更多数据训练并在功能更强大的计算机上运行的更复杂模型来完善潜在的阳性检测。诸如哈里斯(harris)角点的简单兴趣点也可能会被捕获，并随后用于运动检测和跟踪。边缘与云的方法在很大程度上可以相同，除了边缘模型的复杂性及其相对较低的精度，但潜在地具有较高的召回率。表5天气识别在一些实施例中，检测到损害自主车辆的视觉系统的天气状况(例如，雨、雾或日照眩光)。直觉是天气状况在整个图像中是全局的。一种通用方法是在整个图像上提取全局描述符，将它们编译为特征向量，并通过训练数据学习有差别的描述符，以进行多类分类。在一些实施例中，局部天气馈送(“今天多雨”、“晴天”、“旧金山早晨有雾”)被用作图像特征向量中的另一个描述符(例如，被附到图像特征向量上)。对于全局图像描述符，可以使用梯度直方图(hog)和颜色直方图，如图9所示。给定训练集合中的这些特征向量，可以训练线性多分类器(多类svm)。存在可以使用的更丰富的机器学习模型，诸如执行更智能特征选择的模型(例如，m.varma和brbabu，“moregeneralityinefficientmultiplekernellearning”，acminternationalconferenceonmachinelearning，2009年)。可以使用cnn(例如，参见elhoseiny等，“weatherclassificationwithdeepconvolutionalneuralnetworks”，internationalconferenceonimageprocessing，2015年)。在一些实施例中，通过使用在同一小时但在不同日期的同一条道路的历史图像，使用dbscan将直方图聚类在直方图特征空间中，以检测异常值(ester等，“adensity-basedalgorithmfordiscoveringclustersinlargespatialdatabaseswithnoise”，proceedingsofthesecondinternationalconferenceonknowledgediscoveryanddatamining，1996年)。转向更加空间上的粒度分类，可以检测到标示的速度限制标志。交通标志的更一般类别的这种特定分类类别可以利用另一个信号：位置(例如gps位置)。例如，基于视觉的分类器和用于速度的扩展卡尔曼滤波器(ekf)结合使用，可以实现对速度标志及其标示的速度限制的可靠检测和识别。基于视觉的分类器一些实施例使用两种方法进行分类：(1)增强的级联类haar特征分类(图10)和(2)cnn。由于待求解的参数量少于cnn，因此增强的级联类haar特征分类最初可以用于引导图像采集。该方法在过去已成功用于面部检测(viola，jones，“robustreal-timefacedetection”，internationaljournalofcomputervision，2004年)。基本思想是将只需要稍好于随机的弱分类器(haar特征)的集合(例如经由adaboost)一起增强，以提供更高的预测质量。级联方面意味着特征在分类中链接在一起，并且早期坏分类器可以用于拒绝后续特征。级联弱分类器在滑动窗口(在图像的高斯金字塔的不同级别)上运行，并且保留具有最高检测率的窗口。最后，经由非最大的抑制来选择一个窗口。分类和检测(例如，图像中类的定位)在两个单独的步骤中完成。图11示出了增强的级联局部二进制模式(lbp)分类器。用于估计位置和速度以改进检测的扩展卡尔曼滤波器在描述一般的cnn视觉方法之前，简要解释使用传感器融合帮助检测速度限制标志。标准的扩展卡尔曼滤波器(ekf)用于将惯性测量单元(imu)(加速度计、陀螺仪和磁力计)与位置(例如gps位置)融合在一起，以预测位置和速度。对于传感器协方差，地图域知识用于提供比标准校准更好的估计(例如，在城市峡谷中，噪声有所增加，但在某些实施例中，仍假定为正态分布的噪声)。凭直觉，驾驶员在标示的速度限制更改时会改变他们的速度。可以将相邻路段(多个行程)上更好的位置和速度估计馈送作为cnn的附加参数，以在速度改变时专门检测标示的速度限制标志。通用交通标志和对象使用增强的级联分类器，参数的数量小于cnn，但是它需要使用haar过滤器以及它们带来的限制。使用cnn，大量的标记数据用于训练，以使网络优化以执行最佳卷积。cnn是专门用于计算机视觉分类的一种特殊类型的深度神经网络。与它们的一般对应物类似，cnn由多层节点组成，其中每个节点都通过简单的权重和偏差(其值被学习)来描述。cnn还采用relu来捕获非线性，并采用相同的正则化和随机优化技术(例如sgd)最小化损失。cnn与一般神经网络的不同之处在于，某些节点实际上描述前一层上的图像卷积或滤波器响应。另外，研究人员采用了特定于图像域的见解，例如最大池化，以提高cnn识别的准确性。这和其他见解使机器学习工程师可以直观地了解cnn如何从简单特征到复杂的聚合图案逐步搜索图像特征。最近的工作表明交通标志检测具有很高的准确性(91％)(zhu等，cvpr，2016年)。因此，例如，使用如图12所示的“您只能看一次(yolo)”架构(例如，使用tensorflow用keras实现)，对cnn进行训练以检测一般交通标志和任何其他对象(但不是场景)。图13示出根据一些实施例的各种交通标志的检测。平台本公开的一些实施例是使用java来实现的，更具体地说是使用graphhopper来实现的。对于离线实现方式，可以在自主车辆上运行车载java虚拟机(jvm)。为了减少车载设备上所需的存储器量，一些实施例将路由图分片以仅将必要的图组成部分加载到存储器中。可替代地，一些实施例在单独的移动设备上运行自主车辆路由，移动设备经由本地通信(蓝牙、lan、usb等)与汽车连接。在这种情况下，以离线模式运行自主车辆路由等同于在移动设备上运行它。操作环境图14是根据一些实施例的客户端-服务器环境1400的框图。客户端-服务器环境1400包括车辆1410(例如，1410-1、1410-2，...，1410-n)，其通过一个或多个网络1414连接到车辆路由服务器1420。在一些实施例中，车辆1410是车辆306/308或类似于车辆306/308(图3b)。在某些情况下，车辆1410操作为车辆路由服务器1420的客户端。一个或多个网络1414可以是任何网络(或网络的组合)，诸如因特网、其他广域网、局域网、城域网、vpn、点对点、ad-hoc连接等。非自主车辆1410-1是代表性的人类驾驶车辆(例如汽车、卡车或摩托车)。在一些实施例中，非自主车辆1410-1是非自主车辆306或类似于非自主车辆306(图3b)。在一些实施例中，非自主车辆1410包括获取相机图像并将其发送到车辆路由服务器1420的行车记录仪1412，车辆路由服务器1420可以从行车记录仪图像(以及来自自主车辆的自主车辆相机传感器数据，诸如来自自主车辆1410-2中的传感器1402)自动地识别道路状况。自主车辆1410-2(例如，汽车、卡车或摩托车)包括存储用于一个或多个客户端路由应用1406的指令的非暂时性存储器1404(例如，非易失性存储器)。在一些实施例中，自主车辆1410-2是自主车辆308或类似于自主车辆308(图3b)。客户端路由应用1406由自主车辆1410-2上的一个或多个处理器(例如，cpu)1408执行。在一些实施例中，客户端路由应用1406向车辆路由服务器1420发送对路线的请求，并从车辆路由服务器1420接收选择的路线。在一些实施例中，客户端路由应用1406沿着选择的路线引导自主车辆1410-2。客户端路由应用1406可以体现为程序、固件、操作系统或自主车辆1410-2的其他逻辑或物理方面的任何适当组合。自主车辆1410-2还可选地包括一个或多个网络接口以及用于互连这些组件的一个或多个通信总线。自主车辆1410-2还包括车辆组件，诸如引擎/马达、转向机构、灯、发信号机构等，其中的一些或全部可以在程序(例如，客户端路由应用1406)的控制下存储在存储器1404中。在某些情况下，例如直到车辆1410-n的车辆车队与车辆路由服务器1420通信。车队可以是自主车辆和人类驾驶车辆的混合，或者可以是完全是自主的。车辆路由服务器1420包括存储用于一个或多个服务器路由应用1418(有时称为“路由引擎”)的指令的非暂时性存储器1416(例如，非易失性存储器)。车辆路由服务器1420还包括用于执行服务器路由应用1418的一个或多个处理器(例如，cpu)1422。存储在非暂时性存储器中的服务器路由应用，包括用于执行本文描述的任何方法(例如，方法1500、1600、1700和/或1800，图15a-15b、16-18)的指令。服务器路由应用1418可以体现为程序、固件、操作系统或自主车辆1410-2的其他逻辑或物理方面的任何适当组合。车辆路由服务器1420还可选地包括一个或多个网络接口以及用于互连这些组件的一个或多个通信总线。以上标识的应用对应于用于执行本文描述的功能的指令集合。不需要将应用实现为单独的软件程序、过程或模块，因此，在各种实施例中，可以组合或以其他方式重新布置这些指令的各个子集合。用于使用具有除行程时间以外的成本的成本模型来路由车辆的方法图15a-图15b是示出根据一些实施例的用于使用具有除行程时间以外的成本的成本模型来车辆路由的方法1500的流程图。在电子设备(例如，图14的车辆路由服务器1420)处执行方法1500。尽管以下讨论描述车辆路由服务器1420执行方法1500的步骤的实现方式，但是在其他实施例中，一个或多个(例如，全部)步骤是由另一个电子设备，诸如自主车辆1410-2(例如，车辆1410-2上的具有存储用于执行该方法的指令的非暂时性存储器和用于执行指令的一个或多个处理器的计算机系统)执行的。此外，方法1500中的一些操作被可选地组合和/或一些操作的顺序被可选地改变。在一些实施例中，方法1500的一些或全部操作是自动执行的，而无需人为干预。如下面描述的，方法1500提供对路由自主车辆时发生的问题的技术解决方案。具体地，方法1500通过发送减轻不足的路线给自主车辆来解决自主车辆能力的这些不足(例如，降低自主车辆将遇到装备不良的情况的可能性)。以适合其能力的方式对自主车辆进行路由，增加乘客的舒适度和安全性、节省资源(例如，减少自主车辆的碳排放量和/或电池使用量)、减少交通量。车辆路由服务器1420生成(1502)用于路由自主车辆的成本模型。成本模型包括除行程时间以外(或除行程时间和距离以外)的一个或多个成本。在一些实施例中，成本模型包括节点和边的图的表示。各条边具有表示成本的各自边权重。在一些实施例中，在没有边权重的情况下存储图，并且边与标签或属性(例如，道路状况)相关联。在一些在实施例中，生成成本模型包括在运行时(例如，当接收到路由请求时)分配边权重(例如，基于其标签或属性)。在一些实施例中，成本对应于特定的地理区域、道路、道路内的车道、操纵和/或通过交叉路口的路径。在一些实施例中，除行程时间以外的一个或多个成本中的至少一个是(1504)特定地理区域、道路、道路内的车道或操纵的成本。例如，上面描述的图的各条边对应于道路、道路内的线或操纵。作为与特定区域相关联的成本的示例，在某些实施例中，成本模型包括(1506)遍历(例如，进入)禁止自主驾驶的区域的成本。在某些情况下，自主车辆从特定区域被列入黑名单。如果在无人驾驶车辆中发生这种情况，则必须完全避开该区域，并且分配的成本是过高的。当车辆具有人类后备驾驶员时，可以根据偏好设置成本，用于避免人类后备驾驶员必须控制的情况(例如，该偏好可以由人类后备驾驶员或另一个人，例如汽车的所有者设置)。在一些实施例中，禁止自主驾驶的区域是有地理围栏的(例如，具有例如通过gps定义的虚拟地理边界，当自主车辆进入或离开特定区域时，使得软件能够触发响应，诸如在自主车辆已经进入地理围栏区域时指示人类接管驾驶，并在自主车辆离开地理围栏区域时指示恢复控制)。在一些实施例中，特定地理区域的成本被添加到与区域内的特定道路相关联的任何成本(例如，在地理围栏区域内的道路可能具有与行人交通相关联的成本，其由于道路在禁区内的事实而被添加到成本中)。在一些实施例中，成本模型包括(1508)驾驶操纵(例如，车道改变、右转弯、左转弯、没有保护的左转弯、u形转弯和高速公路合并)的成本。在一些实施例中，对于自主车辆不安全的操纵被分配了过高的成本。在一些实施例中，右转弯的成本小于或等于受保护的左转弯的成本，受保护的左转弯的成本小于没有保护的左转弯的成本。较高成本的效果是车辆路由服务器1420不太可能选择具有较高成本特征的路线。因此，通过使没有保护的左转弯比右转弯具有更高的成本操纵，自主车辆不太可能被路由为沿着具有没有保护的左转弯的路线，从而导致更少的没有保护的左转弯。在一些在实施例中，将没有保护的左转弯的成本设置得过高，以完全避免没有保护的左转弯。在一些实施例中，成本模型包括(1510)自主车辆的特性的成本(或与自主车辆的特性相关联)。在一些实施例中，自主车辆的特性是(1512)车辆类型，例如，车辆的品牌或型号，无论该车辆是轿车、运动型多用途车、厢式货车还是大型车辆)。例如，在一些实施例中，与较高的车辆相比，较小的道路对于较小的车辆具有相关联的较低成本。在一些实施例中，自主车辆的特性是(1514)自主车辆的自主驾驶能力(或等效地，自主驾驶限制)(例如，传感器能力或操纵能力)。例如，在某些实施例中，对于无法自行确定车道的自主车辆，没有车道线的道路具有较高成本。参考方法1600(图16)更详细地描述根据自主车辆的特性的成本进行的路由。在一些实施例中，成本模型包括(1516)天气状况的成本，诸如当前天气(例如，正在下雪)的成本。在一些实施例中，天气状况的成本是由于天气引起的道路状况(例如，道路上有雪)的成本。在一些实施例中，除行程时间以外的一个或多个成本包括(1518)：在不同道路上对于共享天气状况的不同的特定道路成本。例如，在暴风雪中，可以给小型道路分配比高速公路更高的成本(特别是如果小型道路是不经常耕作的道路，例如，如从相机数据确定，如参考图18的方法1800描述)。在一些实施例中，除行程时间以外的一个或多个成本包括(1520)：在不同道路上对于不同天气状况的不同的特定道路成本。例如，对于长途旅行或在有小气候的地区中的旅行，可能完全避免诸如雪和雾的情况。具有天气状况的道路被分配了一个成本，而没有天气状况的道路(例如，具有较好天气的道路)被分配了较低的成本。在一些实施例中，除行程时间以外的一个或多个成本包括：一天中的时间的成本(例如，对于不同道路的一天中的时间的不同的特定道路成本)。例如，小乡村道路在夜间可能比大高速公路更不安全。因此在夜间，为小乡村道路分配了额外的成本，与白天的偏好相比，这甚至更多地降低了小乡村道路相对于高速公路的偏好。在一些实施例中，除行程时间以外的一个或多个成本包括：日照角度的成本(例如，对于不同的道路，日照角度的不同的特定道路成本)。例如，在日落时几乎直接指向太阳的道路要比相对于太阳的位置更成角度的道路接收较高成本。在一些实施例中，根据一年中的时间分配日照角度的成本(例如，道路仅在冬季日落期间直接指向太阳，且因此分配给日落角度的成本仅在冬季日落期间被分配)。在一些实施例中，除行程时间以外的一个或多个成本包括：行人交通模式(例如，行人交通的预测或测量的密度)的成本。在一些实施例中，除行程时间以外的一个或多个成本包括非机动车辆(例如，自行车)交通模式的成本。在一些实施例中，行人/非机动车辆交通模式是时间模式。在某些实施例中，行人/非机动车交通模式是一种空间模式(例如，自主车辆路由试图避开行人交通量大的区域，例如时代广场)。在一些实施例中，行人/非机动车辆交通模式是基于历史数据的(例如，行人/非机动车辆交通模式不是由自主车辆在沿着路线行驶时确定的，而是在确定路由之前确定的，使得行人/非机动车辆交通模式可以在路由中使用)。在一些实施例中，除行程时间以外的一个或多个成本包括：路面状况的成本。在一些实施例中，除行程时间以外的一个或多个成本包括：道路使用年限的成本(例如，较老的道路被分配为比较新的道路高的成本)。在一些实施例中，除行程时间以外的一个或多个成本包括：缺少车道线的道路的成本(例如，具有车道线的道路被分配为比没有车道线的道路低的成本)。在一些实施例中，除行程时间以外的一个或多个成本包括：充电约束的成本(例如，没有绵延的充电设施的道路被分配为比具有频繁的充电设施的道路高的成本)。该约束可以对应于电动车辆的范围。在一些实施例中，除行程时间以外的一个或多个成本包括加速成本。晕车在自主车辆中很常见。这至少部分是因为自主车辆尚未学会模仿人类驾驶，因此自主车辆倾向于以乘客感觉不自然的方式加速(例如改变速度和/或方向)。为了减轻自主车辆中的晕车，方法1500的一些实施例为加速分配成本(例如，在成本模型中包括加速成本)以不利于具有不自然的加速曲线的路线。在一些实施例中，成本模型还包括行程时间成本(和/或距离成本)，并且根据行程时间成本(和/或距离成本)和一个或多个其他成本来选择路线。因此，除行程时间(和/或距离)以外的成本可以与行程时间和/或距离成本(例如，另外地)一起操作，从而防止车辆路由服务器1420沿着不合理的长路线对自主车辆进行路由，例如以避免人为干预区域。车辆路由服务器1420接收(1522)将自主车辆从第一位置路由到第二位置的请求。在一些实施例中，在生成成本模型之前，接收路由自主车辆的请求。例如，第一位置和第二位置是各自对应于街道地址、交叉路口、地标(例如，“市政厅”)等的物理位置。在一些实施例中，请求识别第一位置和第二位置。在一些实施例中，第一位置是行程的起点。在一些实施例中，第二位置是行程的终点。可替代地，自主车辆路由可以零碎地进行，其中第一位置和第二位置是沿着较长路线的中间点。在一些实施例中，从车辆(例如，车辆1410-2或1410-n)或车辆内的乘客(例如，使用乘客的智能电话)接收路由自主车辆的请求。响应于路由自主车辆的请求，车辆路由服务器1420根据成本模型选择(1524)从第一位置到第二位置的路线。在一些实施例中，如上文在标题“遍历图(选择路线)”下描述的那样进行路线的选择。在一些实施例中，除行程时间以外的一个或多个成本包括：在路由请求时发生的事件(例如，施工项目、交通事故或体育赛事)的成本。在一些实施例中，除行程时间以外的一个或多个成本包括在路由请求时开始和/或结束的事件(例如，开始和/或结束的体育比赛)的成本。至少部分地基于事件的成本来进行路线的选择。例如，除行程时间以外的一个或多个成本包括(1526)定期安排的事件的成本。根据在路由请求时发生定期安排的事件的确定，至少部分地基于定期安排的事件的成本进行选择路线。例如，当在接收到请求时发生体育赛事时，会向场地(例如体育场)周围的街道分配附加的成本，以不利于场地附近的路线。在一些实施例中，根据定期安排的事件将在自主车辆预期到达定期安排的事件的时刻发生的确定，至少部分地基于定期安排的事件的成本进行选择路线。例如，不利于在对应于事件的开始时间的指定时间段内到达场地周围区域的路线。路由车辆远离在路由时发生的事件，增加乘客的舒适度和安全性、节约资源(例如，减少自主车辆的碳排放量和/或电池使用量)、减少交通量。进一步响应于请求，车辆路由服务器1420沿着选择的路线路由(1528)自主车辆。在一些实施例中，对自主车辆进行路由包括控制车辆的机械操作，包括控制自主车辆的转向、加速、中断和发信号。在一些实施例中，对自主车辆进行路由包括引导自主车辆遵循选择的路线。在一些实施例中，引导自主车辆遵循选择的路线包括：引导单独的计算机实现的模块(例如，车辆1410-2或1410-n上的路由应用1406)遵循选择的路线(例如，为车载模块提供选择的路线)。车载模块处理车辆的机械控制(例如，处理车辆的中断、加速、转向和发信号、避开行人等)。在一些实施例中，车辆在没有人为干预(例如，乘客干预)的情况下自动地遵循路线。在一些实施例中，响应于路由自主车辆的请求来生成成本模型，并且成本模型是用于自主车辆的第一成本模型。在一些实施例中，车辆路由服务器1420接收将非自主车辆(例如，没有自主能力的人类驾驶车辆)从第三位置路由到第四位置的请求。车辆路由服务器1420生成用于路由非自主车辆的第二成本模型。第二成本模型不同于第一成本模型，并且不包括第一成本模型中所包括的除行程时间以外的一个或多个成本(例如，不包括遍历禁止自主驾驶的区域的成本、不包括加速的成本)。在某些实施例中，第二成本模型包括针对对于第一个成本模型所考虑的因素的不同成本。例如，第一成本模型包括相应驾驶操纵的第一成本，而第二成本模型包括相同的相应驾驶操纵的第二成本，其中第二成本不同于第一成本。响应于路由非自主车辆的请求，车辆路由服务器1420根据第二成本模型选择从第三位置到第四位置的路线，并且沿着为非自主车辆选择的路线路由非自主车辆(例如，为自主车辆选择的路线是第一选择路线，以及为非自主车辆选择的路线是第二选择路线)。例如通过分别对自主车辆和非自主车辆使用不同的成本模型，对自主车辆和非自主车辆进行不同的路由，以使路线适合自主车辆和非自主车辆的各自能力。以适合其能力的方式对车辆进行路由，增加乘客的舒适度和安全性、节省资源(例如，减少自主车辆的碳排放量和/或电池使用量)、减少交通量。在一些实施例中，自主车辆是具有第一自主驾驶能力的第一自主车辆，并且成本模型是用于第一自主车辆的第一成本模型。用于第一成本模型的除行程时间以外的一个或多个成本包括对应于第一自主驾驶能力的成本。在一些实施例中，车辆路由服务器1420接收将第二自主车辆从第五位置路由到第六位置的请求。第二自主车辆具有不同于第一自主驾驶能力的第二自主驾驶能力。车辆路由服务器1420生成用于路由第二自主车辆的第三成本模型。第三成本模型不同于第一成本模型，并且第三成本模型包括对应于第二自主驾驶能力的成本(例如，这是不同于对应于第一自主车辆的第一成本模型的第一自主驾驶能力的成本)。响应路由第二自主车辆的请求，车辆路由服务器1420根据第二成本模型选择从第五位置到第六位置的路线；以及沿着为第二自主车辆选择的路线路由第二自主车辆。例如，通过针对具有不同能力的不同自主车辆分别使用不同的成本模型，取决于其能力来不同地路由自主车辆，以使路线适合自主车辆的各自能力。以适合其能力的方式对车辆进行路由，增加乘客的舒适度和安全性、节省资源(例如，减少自主车辆的碳排放量和/或电池使用量)、减少交通量。应当理解的是，已经在图15a-15b中描述的操作的特定顺序仅是示例性的，并且不意图指示描述的顺序是可以执行操作的唯一顺序。本领域普通技术人员将认识到重新排序本文描述的操作的各种方式。为简便起见，此处不再赘述。另外，图15a-15b中的操作可以与其他地方(例如，参考图16-图18)描述的其他操作组合，或者具有参考其他地方描述的类似操作描述的特性(例如，方法1500的路由操作可以(可选地)共享本文其他地方描述的其他路由操作的任何特性)。使用具有车辆约束的成本模型的自主车辆路由的方法图16是示出根据一些实施例的使用具有车辆约束的成本模型的自主车辆路由的方法1600的流程图。在电子设备(例如，图14的车辆路由服务器1420)处执行方法1600。尽管以下讨论描述车辆路由服务器1420执行方法1600的步骤的实现方式，但是在其他实施例中，一个或多个(例如，全部)步骤是由另一个电子设备，诸如车辆1410-2(例如，车辆1410-2上的计算机系统，计算机系统具有存储用于执行方法的指令的非暂时性存储器和用于执行指令的一个或多个处理器)执行的。此外，方法1600中的一些操作被可选地组合和/或一些操作的顺序被可选地改变。在一些实施例中，方法1600的一些或全部操作是自动地执行的，而无需人为干预。如下面描述的，方法1600提供对路由自主车辆时发生的问题的技术解决方案。具体地，方法1600认识到不同的自主车辆具有不同的驾驶能力的事实。为此，在一些实施例中，方法1600根据自主车辆的特定能力来路由自主车辆。以适合其特定能力的方式对自主车辆进行路由，增加乘客的舒适度和安全性、节省资源(例如，减少自主车辆的碳排放量和/或电池使用量)、减少交通量。车辆路由服务器1420接收(1602)将自主车辆从第一位置路由到第二位置的请求(例如，提供行程路线的请求)。在一些实施例中，车辆路由服务器1420接收自主车辆的当前位置。例如，将自主车辆从第一位置路由到第二位置的请求包括自主车辆的当前位置(例如，第一位置)。请求可以具有关于(图15a-15b)方法1500的操作1522描述的请求的任何特性。在一些实施例中，车辆路由服务器1420接收车队车辆的当前位置。在一些实施例中，车辆路由服务器1420确定车辆车队的集结位置(例如，路线将从其开始的位置)。另外，在一些实施例中，车辆路由服务器1420与路由自主车辆的请求一起接收(1604)用于自主车辆的标识符。例如，自主车辆的标识符可以是车辆识别号(vin号)；自主车辆的品牌、型号和年份；或用于自主车辆的账号。在一些实施例中，车辆路由服务器1420接收自主车辆的当前位置。例如，将自主车辆从第一位置路由到第二位置的请求包括自主车辆的当前位置(例如，第一位置)。车辆路由服务器1420识别(1606)自主车辆的一个或多个自主驾驶能力的集合。在一些实施例中，车辆路由服务器基于标识符(例如，在车辆能力数据库中)查找(1608)自主车辆的一个或多个自主驾驶能力。在一些实施例中，自主车辆的一个或多个自主驾驶能力的集合包括自主车辆的传感器(例如，传感器1402，图14)的能力。车辆路由服务器1420使用与路由请求一起接收的标识符来在数据库中查找车辆。数据库返回指示车辆具有哪些类型的传感器和/或传感器的能力是什么的信息。在一些实施例中，识别自主车辆的一个或多个自主驾驶能力的集合包括(1610)与请求一起接收自主驾驶能力。例如，请求包括识别车辆具有哪些类型的传感器的信息。在一些实施例中，请求中包括一个或多个自主驾驶能力，该请求还识别车辆，并且通过在数据库中查找车辆来确定一个或多个附加驾驶能力。在一些实施例中，一个或多个自主驾驶能力的集合包括多个自主驾驶能力。在一些实施例中，自主车辆的一个或多个自主驾驶能力的集合包括自主车辆的可操纵性。例如，自主驾驶能力的集合可以包括对特定车辆或车辆类型、对进行没有保护的左转弯、改变车道或合并到高速公路上的能力的评级、分数或成本。在一些实施例中，自主车辆的一个或多个自主驾驶能力的集合包括从自主车辆和与自主车辆相同类型的车辆中的至少一个的历史性能数据确定的对自主车辆的限制。例如，来自发生事故或事故附近的自主车辆的传感器数据可以用于识别车辆或车辆类型表现不佳的情况。作为更具体的示例，可以基于历史性能数据来确定特定品牌、型号和年份的自主车辆在密集的行人交通中或在低日照角度下表现不佳。在一些实施例中，自主车辆的一个或多个自主驾驶能力的集合包括用于自主车辆的安全等级(例如，基于nhtsa安全等级的复合安全分数)。在一些实施例中，车辆路由服务器1420生成(1612)用于路由自主车辆的成本模型，成本模型包括用于自主车辆的一个或多个自主驾驶能力的集合的一个或多个成本(例如，用于集合中各个能力的各自成本)。在一些实施例中，生成成本模型包括根据一个或多个自主驾驶能力的集合来分配成本。例如，成本模型可以包括表示地图的图(例如，在生成成本模型之前存储的图)。图中的特定边可以对应于高速公路合并，并且被标记为“高速公路合并”作为属性。作为生成操作的一部分，车辆路由服务器1420基于请求车辆关于合并到高速公路的能力为边分配成本。车辆路由服务器1420根据自主车辆的一个或多个自主驾驶能力的集合来选择(1614)从第一位置到第二位置的路线(例如，车辆路由服务器1420至少部分地基于成本模型选择(1616)从第一位置到第二位置的路线)。例如，当自主车辆在高速公路合并中表现不佳时，为高速公路合并边分配的成本会更高。结果，车辆路由服务器1420不太可能选择包括高速公路合并的路线。作为另一个示例，在一些实施例中，至少部分地基于自主车辆的安全等级进行选择。在一些实施例中，具有较低安全等级的车辆比具有较高安全等级的车辆被路由为沿着更安全的路线(例如，选择更安全的路线)。在一些实施例中，一个或多个自主驾驶能力的集合包括针对特定情况(例如，特定操纵、特定天气、特定位置等)的安全等级(例如，前排乘客侧安全等级用于增加或减少具有没有保护的左转弯的偏好路线)。车辆路由服务器1420根据选择的路线路由(1618)自主车辆。路由操作1618类似于上面参考方法1500(图15a-15b)描述的路由操作1528。在一些实施例中，自主车辆是第一自主车辆。在一些实施例中，车辆路由服务器1420接收将第二自主车辆从第三位置路由到第四位置的请求。车辆路由服务器1420识别第二自主车辆的一个或多个自主驾驶能力的集合(例如，不同的传感器、关于检测对象/车道的能力的不同规格等)。第二自主车辆的一个或多个自主驾驶能力的集合包括不同于第一自主车辆的一个或多个自主驾驶能力的集合的至少一个自主驾驶能力。车辆路由服务器1420根据第二自主车辆的一个或多个自主驾驶能力的集合，选择从第三位置到第四位置的路线，以及根据为第二自主车辆选择的路线路由第二自主车辆。例如，通过针对具有不同能力的不同自主车辆分别使用不同的成本模型，取决于其能力来不同地路由自主车辆，以使路线适合自主车辆的各自能力。以适合其能力的方式对车辆进行路由，增加乘客的舒适度和安全性、节省资源(例如，减少自主车辆的碳排放量和/或电池使用量)、减少交通量。应当理解的是，已经在图16操作中描述的操作的特定顺序仅是示例性的，并且不意图指示描述的顺序是可以执行操作的唯一顺序。本领域普通技术人员将认识到重新排序本文描述的操作的各种方式。为简便起见，此处不再赘述。另外，图16中的操作可以与在其他地方(例如，参考图15a-图15b和图17-图18)描述的其他操作组合，或者具有参考其他地方描述的类似操作描述的特性(例如，方法1600的路由操作可以可选地共享本文其他地方描述的其他路由操作的任何特性)。使用具有交叉路口成本的成本模型的自主车辆路由的方法图17是示出根据一些实施例的使用具有交叉路口成本的成本模型的自主车辆路由的方法1700的流程图。在电子设备(例如，图14的车辆路由服务器1420)处执行方法1700。尽管以下讨论描述车辆路由服务器1420执行方法1700的步骤的实现方式，但在其他实施例中，一个或多个步骤是由另一个电子设备，诸如车辆1410-2(例如，车辆1410-2上的计算机系统，计算机系统具有存储用于执行方法的指令的非暂时性存储器和用于执行指令的一个或多个处理器)执行的。此外，方法1700中的一些操作被可选地组合和/或一些操作的顺序被可选地改变。在某些实施例中，方法1700的一些或全部操作是自动地执行的，而无需人为干预。如下面描述的，方法1700提供对在路由自主车辆时发生的问题的技术解决方案。具体地，方法1700通过发送减少自主车辆必须进行某种操纵的可能性的路线给自主车辆来解决自主车辆在交叉路口处执行此种操纵的能力的不足。例如，通常右转弯要比没有保护的左转弯容易。在一些情况下，方法1700将使没有保护的左转弯(就成本模型中的成本而言)比右转弯“更昂贵”，从而减少自主车辆进行没有保护的左转弯的次数。以适合其能力的方式对自主车辆进行路由，增加乘客的舒适度和安全性、节省资源(例如，减少自主车辆的碳排放量和/或电池使用量)、减少交通量。车辆路由服务器1420生成(1702)用于将自主车辆从第一位置路由到第二位置的成本模型。成本模型包括，对于交叉路口，用于遍历通过交叉路口的不同路径的多个成本。各个成本对应于通过交叉路口的各个路径。在一些在实施例中，成本模型包括交叉路口的表示，如参考上文在标题“构造路由图”下的部分描述的。在一些实施例中，成本模型被表示为节点和边的图。各条边具有表示成本的各自边权重。车辆路由服务器1420将交叉路口表示为图中的多个节点和多条边。交叉路口的表示的每条边表示通过交叉路口的不同路径。例如，图4示出通过被表示为边的交叉路口的多个路径(例如，从南北道路的南侧(s)到东西道路的东侧(e)的路径；从南北道路的南侧(s)到南北道路的北侧(n)的路径)。此外，生成操作1702可以具有本文其他地方描述的生成操作的任何特征(例如，响应于请求分配边权重，并且边权重可选地包括与特定车辆的约束相关联的成本)。在一些实施例中，车辆路由服务器1420放弃通过交叉路口的禁止路径的表示。例如，在图4中，南北道路的南侧(s)和东西道路的西侧(w)之间不存在边，因为东西道路是向东的单向道路)。在一些实施例中，交叉路口是多条道路的交点。多条道路中的每条道路具有一个或多个成本，一个或多个成本不同于用于遍历通过交叉路口的不同路径的多个成本(例如，在交叉路口处相交的道路具有其自己的成本，其不同于与通过交叉路口的路径的成本)。在一些实施例中，表示通过交叉路口的路径的边具有与表示道路的边不同的特性(例如，如上表1所示)。在一些实施例中，用于遍历通过交叉路口的不同路径的多个成本包括：用于遍历通过交叉路口的不同路径中的一个的驾驶操纵(例如，车道改变、右转弯、左转弯、没有保护的左转弯、u形转弯和高速公路合并)的一个或多个成本。参考方法1500更详细地描述驾驶操纵的成本及其技术优势。车辆路由服务器1420接收(1704)将自主车辆从第一位置路由到第二位置的请求。在一些实施例中，成本模型是在接收到请求之后(例如，响应于接收到请求)生成的。在一些实施例中，车辆路由服务器1420接收自主车辆的当前位置。例如，将自主车辆从第一位置路由到第二位置的请求包括自主车辆的当前位置(例如，第一位置)。请求可以具有关于方法1500和1600(图15a-15b、图16)中的请求接收操作描述的请求的任何特性。响应于请求，车辆路由服务器1420至少部分地基于用于遍历通过交叉路口的不同路径的多个成本中的一个，根据成本模型选择(1706)从第一位置到第二位置的路线(例如，如上面关于方法1500和1600中的选择操作描述的那样)。进一步响应于请求，车辆路由服务器1420根据选择的路线路由(1708)自主车辆(例如，如上面关于方法1500和1600中的路由操作描述的那样)。应当理解的是，已经在图17中描述的操作的特定顺序仅是示例性的，并且不旨在指示描述的顺序是可以执行操作的唯一顺序。本领域普通技术人员将认识到重新排序本文描述的操作的各种方式。为简便起见，此处不再赘述。另外，图17中的操作可以与其他地方(例如，参考图15a-15b、图16和图18)描述的其他操作组合，或者具有参考其他地方描述的类似操作描述的特性(例如，方法1700的路由操作可以可选地共享本文其他地方描述的其他路由操作的任何特性)。将实时数据叠加到自主车辆路由成本模型上的方法图18是示出根据一些实施例的将实时数据叠加到自主车辆路由成本模型上的方法1800的流程图。在电子设备(例如，如图14所示的车辆路由服务器1420)处执行方法1800。尽管以下讨论描述车辆路由服务器1420执行方法1800的步骤的实现方式，但是在其他实施例中，一个或多个步骤是由另一个电子设备，例如车辆1410-2(例如，车辆1410-2上的计算机系统，计算机系统具有存储用于执行方法的指令的非暂时性存储器以及用于执行指令的一个或多个处理器)执行的。此外，方法1800中的一些操作被可选地组合和/或一些操作的顺序被可选地改变。在一些实施例中，方法1800的一些或全部操作是自动地执行的，而无需人为干预。如下面描述的，方法1800通过认识到车辆在物联网(iot)中的重要性，提供对在路由自主车辆时发生的问题的技术解决方案。特别地，方法1800认识到，车辆(特别是自主车辆)，不仅是运输方式，而且代表大量运动传感器阵列，能够检测与路由自主车辆的技术问题相关联的状况。因此，在一些实施例中，方法1800通过使用利用来自其他车辆上的传感器的信息自动地确定的道路状况来对自主车辆进行路由，从而允许更有效地路由自主车辆。对自主车辆进行更有效的路由节省资源(例如，减少自主车辆的碳排放量和/或电池使用量)、增加乘客的舒适度和安全性、减少交通量。车辆路由服务器1420接收(1802)从不同于待路由的自主车辆的第二车辆(例如，附加车辆)上的相机(例如，行车记录仪或自主车辆相机传感器)获得的信息。在一些实施例中，信息是从相机队、一些人为驱动的(例如，利用行车记录仪)和/或一些自主的(例如，利用行车记录仪和/或自主车辆相机传感器)中的相机获得的。在一些实施例中，信息是在由相机采集时实时获得的(例如，在没有故意引入的延迟的情况下被接收，使得信息在被相机采集后的几秒钟内可用于车辆路由服务器1420)。在一些实施例中，车辆路由服务器1420持续接收从相机获得的信息(例如，车辆路由服务器1420持续监视新的相机信息)。在一些实施例中，从相机获得的信息包括由车辆路由服务器1420分析的一个或多个图像(例如，如下面关于操作1804描述的)。在一些实施例中，图像包括静止图片。在一些实施例中，图像包括视频馈送。在一些在实施例中，图像由车辆1410上的计算机分析，并且从相机获得的信息包括自动识别的道路状况(例如，如下面参考操作1804描述的那样)。车辆路由服务器1420使用对从第二车辆上的相机接收到的信息的图像分析来自动地识别(1804)道路状况。参考上面在“用于为自主车辆的车队提供动力的实时数据”、“天气识别”、“基于视觉的分类器”和“用于估计位置和速度以改进检测的扩展卡尔曼滤波器”标题下的部分描述道路状况的识别。车辆路由服务器1420接收(1806)将自主车辆从第一位置路由到第二位置的请求。在一些实施例中，车辆路由服务器1420接收自主车辆的当前位置。例如，将自主车辆从第一位置路由到第二位置的请求包括自主车辆的当前位置(例如，第一位置)。路线请求接收操作1806具有上面路线请求接收操作的任何特性(例如，参考图15a-图15b、图16-图17的方法1500、1600和1700)。车辆路由服务器1420生成(1808)用于路由自主车辆的成本模型(例如通过基于属性将权重分配给图的边，如上面描述地生成成本模型)。成本模型包括从第二车辆上的相机接收到的信息自动识别的道路状况的成本。在一些实施例中，响应于请求生成成本模型。在一些实施例中，生成成本模型包括响应于请求更新先前的成本模型。在一些实施例中，当从其他车辆上的相机中识别出道路状况时，实时更新成本模型。在一些实施例中，生成成本模型包括：基于使用相机信息自动地为道路、车道、驾驶操纵、或地理区域识别出的道路状况，将属性分配给该道路、道路中的车道、驾驶操纵或地理区域。在一些实施例中，车辆路由服务器1420确定在请求时道路状况是否存在。根据在请求时存在道路状况的确定，将道路状况的成本包括在成本模型中。例如，车辆路由服务器1420可以基于来自在山区道路上行驶的车辆的行车记录仪数据，确定山区道路上正在下雪。然后，车辆路由服务器1420将属性“下雪”分配给山区道路，直到可以确定山区道路上不再下雪。当山区道路具有“下雪”属性的同时接收到路线请求时，车辆路由服务器1420向山区道路分配下雪属性的成本(例如，固定成本或基于请求自主车辆在雪中行驶能力的成本)。在一些实施例中，车辆路由服务器1420从第二相机信息(例如，来自不同于第二车辆的第三车辆(例如，附加车辆)和自主车辆)确定不再存在道路状况。例如，车辆路由服务器1420从另一个车辆确定山区道路上现在“晴天”并且山区道路上没有积雪，以及移除“下雪”的属性。在一些实施例中，从接收自第二车辆(例如，附加的)上的相机的信息自动地识别出的道路状况是选自由天气状况、由于天气引起的道路状况、由于施工引起的道路状况以及由于交通事故引起的道路状况组成的组的状况。在一些实施例中，从接收自第二车辆(例如，附加的)上的相机的信息自动地识别出的道路状况是选自由日照角度、行人交通、非机动车辆交通、路面状况和缺少车道线组成的组的状况。进一步响应于请求，车辆路由服务器1420根据成本模型选择(1810)从第一位置到第二位置的路线(例如，如上面关于选择操作描述的)。仍进一步响应于请求，车辆路由服务器1420根据选择的路线路由(1812)自主车辆(例如，如上面的路由操作描述的)。应当理解的是，已经在图18中描述的操作的特定顺序仅是示例性的，并且不意图指示描述的顺序是可以执行操作的唯一顺序。本领域普通技术人员将认识到重新排序本文描述的操作的各种方式。为简便起见，此处不再赘述。另外，图18中的操作可以与其他地方(例如，参考图15a-15b和图16-17)描述的其他操作组合，或者具有参考其他地方描述的类似操作描述的特性(例如，方法的路由操作1800可以可选地共享本文其他地方描述的其他路由操作的任何特性)。多对多车辆路由和管理过去一直在努力解决诸如车辆路由问题(vrp)及其一些变型(例如，拨召公车(dial-a-ride)、限制的vrp等)的问题。下文描述的一些实现方式大规模解决了许多问题。广义上讲，一些实现方式涉及使用时空聚类将较大的问题分解为较小的子问题，然后将这些子问题在专用求解器实例之间并行化以快速找到解决方案。车队路由问题(frp)可以如下定义车队路由问题(frp)：给定具有非均匀容量(例如，车队大小不恒定)、具有处于不同位置的车辆的车辆集合以及可以是时间窗口受限制(例如，没有人应该等待超过10分钟才能上车)的多个上车/下车请求，将让每个人上车和下车的任务分配给车辆的子集合，同时最小化目标函数。目标函数可以采用各种形式，包括所谓的规范形式：c＝σv(w1rv w2d(rv))在上面的等式中，c是整个车队的总成本函数，v是车辆集合，rv是车辆v采取的路线的成本，并且d是根据路线的乘客的不舒适成本函数。例如，成本函数d使用权重系数w1和w2平衡乘客的等待时间和总行程时间。因为vrp是np-hard优化问题，所以通用vrp求解器(例如milp或cp)花费了不可接受的长时间来进行求解，即使在应用于大小适中(例如10辆汽车用于100个请求)的问题时。对于涉及实时请求模式和更新的情况，需要实时解决更大的问题。架构在图19中示出用于解决车队路由问题的近似版本的示例架构。路由器1902如本文其他地方描述的那样确定路线、计算多对多请求的估计的到达时间和成本(例如，提出请求的多个乘客，每个乘客都可以由多个车辆中的任一个服务)。求解器1910为来自规划器1908的frp问题的实例提供服务，如下面描述的。在一些实施例中，规划器1908并行求解多个车辆中的每个车辆(例如，车队中的每个车辆)。分组器1906经由时空聚类将较大的frp问题分解为多个较小的frp问题实例。在一些实施例中，分组器1906将乘客分配给潜在停靠点集合，并执行凝聚聚类，以通过规划器1908将停靠点划分为可独立求解的组，从而实现可并行的分而治之。在一些实施例中，将乘客上车/下车分配给按步行距离排序的n个潜在停靠点的集合。图20示出基于请求上车/下车位置之间的距离而被分配给(例如，由连接停靠点和请求位置的线表示)潜在停靠点的请求上车和下车。图21示出，在一些实施例中，使用实时驾驶eta(例如，由路由器提供)作为距离/成本函数，经由具有完整/最大链接的凝聚聚类在空间上对请求进行分组。该聚类对应于最小化集群中任何两个停靠点之间的最大距离。使用目标k个集群，使得规划器可求解集群中的最大元素数，以达到目标延迟(例如5秒)。聚类之后，多个车辆被分配给集群对。在一些实施例中，车辆满负荷，同时最小化它们的行程距离。在一些实施例中，集群对被表示为质心，其中边对应于在集群之间遍历的负载/需求，如图22所示。现在，多个车辆中的每个车辆(被分配一组集群对)成为由规划器1908并行求解的子规划。分配给车辆的集群对的数量是车辆容量和集群对上的负载的函数。然后，将每个车辆子规划联合以形成全局车队规划，如图23所示。例如，图23示出多个不同车辆的组合(例如，全局车队)规划。多个不同车辆中的每个车辆的每个子规划对应于组合规划的一部分。在一些实施例中，车辆的子规划彼此至少部分重叠。在一些实施例中，每个车辆的每个子规划不同于其他车辆的子规划。规划器1908是与路由器1902和求解器1910连接的服务，以为规划请求和更新提供服务(例如，如下面描述的，向现有路线添加上车/下车请求)。在一些实施例中，规划器1908为由分组器1906生成的多个frp问题实例中的每个创建成本矩阵。在一些实施例中，成本矩阵是从实时eta(以及可选地，历史/预测eta)生成的。规划器1908将多个frp问题实例及其成本矩阵传送到求解器1910中以进行求解。求解器1910求解frp问题实例(例如，从规划器传递到求解器的多个frp问题实例)。在一些实施例中，求解器1910将frp问题实例求解为“拨召公车问题”(darp)的实例，其是车队路由问题的表述。为此，在一些实施例中，将问题从广义动态编程实现方式分解为图搜索问题，并使用具有可允许的启发法或双向dijkstra(对于非时间窗变型)的a*进行求解。在一些实施例中，状态被分解为以下表示：s＝(l1,…,lm,k1,…,kn)li∈{0,1,…,n,n 1,…,2n,2n 1}ki∈{w,vj,d}m＝|v|其中，n是车辆下车对的数量。l状态表示车辆位置：l＝0指示车辆处于无界状态，0<l≤n指示上车位置(例如，当0<i<n时，l＝i是第i辆车的上车状态)，以及n 1≤l≤2n指示下车。k个状态代表各乘客状态，它们是集合“等待”、“在第j辆车中”或“下车”中的一部分。因此，s表示乘客和车辆的总状态(例如，系统的状态)。在一些实施例中，终止状态是其中所有k个状态都处于下车状态的状态。系统的总状态数量f可以根据请求数量和车辆数量的函数(o是状态的总数的“阶(order)”)进行精确计算：f(m,n)＝(2n 1)m×(2 m)no(m,n)＝nm×mn由于指数增长率是车辆数量和乘客数量的函数，所以一些实施例使用精确的最优性算法并保持对求解器的请求受限。但是在一些实施例中，使用容量、基于时间的最大位置偏移(mps)和一致性约束来帮助保持对小问题的图搜索受限和有效(例如，具有5个上车-下车对的2个车辆)。多个乘客和车辆的状态的图空间表示可以将frp问题实例作为以下形式的优化问题进行求解：minσv(w1σti w2(αwtj (1-α)×rtj))其中，ti表示遍历路线分支的时间，wtj表示第j个客户的总等待时间，以及rtj表示第j个客户的总乘坐时间。通过将我们的状态空间映射到具有过渡边的图，可以最小化此函数并求解最佳路线，图包含在此函数中的各个元素。alpha(α)是一个常数，其表示乘客的偏好在车内而不是等待。在一些实施例中，图搜索从s0＝(0,0,...,0,w,w,...,w)初始化，并且在到达终止节点时终止：st＝(2n 1,2n 1,…,2n 1,d,d,…,d)。作为示例，考虑一个车辆具有两个上车/下车位置。从上面的优化函数中，我们可以计算出状态总数为45，但是其中许多状态将不一致，例如(1，w，w)。在图24中示出(例如，其示出多个乘客和车辆的状态图表示)该示例的图。这里，第一节点2400“(0，w，w)”指示初始状态(车辆处于无乘客的无界位置)，节点2402指示规划期间的各种状态，节点2404-1和2404-2是终止节点。从最短路径的角度来看，问题是从第一节点2400路由到终止节点2404-1或2404-2中的任一个(一对任意路由问题)，其中给出从状态si到sj的边的边权重：w(si,sj)＝w1×t(si,sj) w2×(α×xw (1-α)×xv)这里，t函数指示从到sj的行程时间，xw指示在状态si中有多少乘客正在等待，以及xv指示在si中有多少乘坐者在车辆中。注意，路径的边权重的和正好等于最小化函数，因此通过该图找到最短路径等同于求解优化问题。还注意，有效搜索空间大小(13个节点)明显小于状态总数(45)。大量状态是不一致的，并且可能实际上是不可达到的，这允许图在图的狭窄子空间中被遍历。在某些情况下，该图的子空间大小渐近地接近总空间大小的1/3。添加如容量或mps的约束甚至会进一步使子空间变狭窄，而不是如在常规milp或cp求解器中那样增大搜索空间。搜索算法因为一些实施例对图空间中的darp进行求解，所以一些实施例应用图搜索技术和算法来加快搜索。例如，代替应用广度优先搜索，一些实施例的dijkstra算法用以加快搜索。对于非时间窗口搜索，一些实施例在相反方向上搜索并实现双向dijkstra算法以更快地解决搜索。但是，即使在具有时间窗的情况下，一些实施例也以可允许的下限启发法在向前方向上应用单向搜索，并使用a*搜索算法。此外，可以经由max函数组合任何启发法，以在搜索过程中找到最佳启发法。下面，讨论示例性启发法。简单的最低界限启发法从状态si到终止状态st的成本可以写成如下：c(si,st)＝σv(w1σpti w2σp(α×wtj (1-α)×rtj))当内部求和是在从状态si到终止状态st的最短路径p上。因为w1和w2以及内部求和都是非负数的，并且结合路由距离的三角不等式，所以可以建立成本的下限：σv(w1σpti w2σp(α×wtj (1-α)×rtj))≥w1×t(si,st)＝h(si,st)然后可以将a*启发式函数hs定义为所有终止节点上的最小值：上车-下车界限启发法可以考虑关于当前状态的等待、上车和下车的乘客数量的信息来构造启发法。为此，在一些实施例中，定义了以下值：tp＝mint(sd,sp)td＝mint(sp,sd)其中sd是下车状态，sp是上车状态。如果车辆当前处于下车并且需要在完成之前进行另一个上车，则可以建立成本的下限：hd(sd)＝w1×td类似地，如果需要上车，并且需要让至少一个人下车，可以建立成本的下限：hp(sp)＝w1×tp动态请求对于较大的问题(例如，10个或更多个的上车请求和车辆车队)，当请求越过可接受性阈值(例如，非实时延迟阈值)时，图空间探索将很快变得不可行。对于这些情况，在某些实施例中，求解器支持增量规划更新，其中它采用现有解决方案并将新请求插入状态空间中的现有路径，而不是运行整个图探索。贪婪(greedy)增量更新一些实现方式通过最小化在插入新点时的时间的变化来将新的上车或下车插入到现有路径中。一些实施例通过求解以下来找到最佳插入点p：p＝argminc(si,p) c(p,s 1)-c(si,s 1)其中，si是指求解方案中的第i个状态，而c(si,sj)是从si到sj的成本。例如，图25a和25b示出将插入点(三角形2500)添加到现有路径。假设存在具有上车/下车点的现有路线，并且需要为三角形2500服务(例如，在三角形的当前位置进行拾取并将其下放到其他地方)。一些实施例通过最小化通过中断分支而获得的时间差来计算在何处插入三角形2500(例如，要中断路径的哪条分支)。注意，由于三角形不等式，时间变化应始终为正。用于乘坐共享交通网络的路由方法图26a-26c是示出根据一些实施例的用于乘坐共享交通网络的路由方法2600的流程图。在电子设备(例如，图14的车辆路由服务器1420，其可以使用图19所示的架构)处执行方法2600。尽管以下讨论描述车辆路由服务器1420执行方法2600的步骤的实现方式，但是在其他实施例中，一个或多个步骤是由另一个电子设备，诸如自主车辆1410-2(例如，车辆1410-2上的计算机系统，计算机系统具有存储用于执行方法的指令的非暂时性存储器和一个或多个用于执行指令的处理器)执行的。此外，方法2600中的一些操作被可选地组合和/或一些操作的顺序被可选地改变。在一些实施例中，方法2600的一些或全部操作是自动地执行的，而无需人为干预。如下面描述的，方法2600提供对上面讨论的车队路由问题的技术解决方案。具体地，方法2600解决如何路由车辆车队以满足可以预先安排、实时请求或两者结合的乘坐请求的问题。用以满足乘坐请求的更有效地路由车辆车队(例如，多个车辆)，节省资源(例如，减少自主车辆的碳排放量和/或电池使用量)，减少交通量并增加乘客的舒适度和安全性。车辆路由服务器1420存储(2602)多个第一乘客的表示。多个第一乘客的表示的每个包括多个第一乘客中的相应第一乘客的请求上车位置和请求下车位置。在一些实施例中，在存储多个第一乘客的表示之前，车辆路由服务器1420从多个第一乘客中的每个接收乘坐请求。请求包括用于相应第一乘客的请求上车位置和请求下车位置。在一些实施例中，来自多个第一乘客中的每个的乘坐请求是安排乘坐的请求，并且包括请求上车时间和/或请求下车时间。例如，在一些实施例中，在请求上车时间和/或请求下车时间之前至少一个小时接收来自多个第一乘客中的每个的乘坐请求(例如，在某些情况下，在需要乘坐的前一晚上接收到来自至少一些第一乘客的乘坐请求)。例如，在一些实施例中，如下面描述的，来自多个第一乘客的乘坐请求被聚类。为此，在一些实施例中，车辆路由服务器1420分别地将落在预定的上车时间或下车时间窗口内的安排请求的批次进行聚类(例如，车辆路由服务器1420分别地分批处理在每个半小时窗口内安排的上车乘坐请求)。在一些实施例中，来自多个第一乘客中的每个的乘坐请求是实时请求(有时称为动态请求)(例如，待尽可能快地进行上车和/或下车的请求)。在一些实施例中，来自多个第一乘客的乘坐请求是在时间上彼此接近地被接收的动态请求。例如，在一些实施例中，如下面描述的，来自多个第一乘客的乘坐请求被聚类。为此，在一些实施例中，车辆路由服务器1420分别将预定义数量的动态请求(例如20个请求、50个请求、100个请求)的批次聚类。在一些实施例中，车辆路由服务器1420分别地对在预定时间窗口(例如1秒、5秒、30秒、1分钟)内接收到的动态请求的批次进行聚类。车辆路由服务器1420存储(2604)多个车队车辆的表示。在一些实施例中，车队车辆包括(2606)多个自主车辆(例如，自主车辆1410-2)。路由自主车辆车队解决了技术问题，因为不像人类驾驶车辆，自主车辆无法自行路由，因此必须(至少在某些情况下)由计算机路由。在一些实施例中，多个车队车辆由单个运营商(例如，或)运营(2608)。路由由单个运营商运营的车辆车队解决了在车队而不是单个车辆上分配成本的技术问题，从而节省资源(例如，减少自主车辆的碳排放量和/或电池使用量)、减少交通量并增加乘客的舒适度和安全性。在此，术语“成本”是指成本模型成本，其在整个本文中进行了描述(例如，参考图15a-图5c的方法1500)。在一些实施例中，车辆路由服务器1420接收关于车队车辆的信息(例如，从车辆本身或从车辆的运营商)。在一些实施例中，关于车队车辆的信息包括车队中每个车辆的位置。在一些实施例中，关于车队车辆的信息包括车队中的车辆的数量(例如，计数)。在一些实施例中，关于车队车辆的信息包括多个车队车辆中的每个车辆(或至少车辆的子集合)的能力，其可以用于根据它们的能力对车队车辆进行路由(如参考图16的方法1600描述的)。车辆路由服务器1420生成(2610)地理地图的图表示，图表示包括多个第一乘客的请求上车位置和请求下车位置。如本文所使用的，术语“图表示”是指节点和边的集合。在一些实施例中，边具有成本(也称为权重)。在一些实施例中，地理地图的图表示包括表示道路的边。在一些实施例中，如参考图17的方法1700描述的，地理地图的图表示包括表示通过交叉路口的路径的边。车辆路由服务器1420生成(2612)多个第一乘客和车队车辆的状态图表示(例如，如参考图24所示出和描述的)。多个第一乘客和车队车辆的状态图表示与地理地图的图表示不同并且分开。状态图表示包括通过边连接的多个节点。状态图表示的多个节点中的每个节点表示多个第一乘客和车队车辆的候选状态。候选状态是如果通过该候选状态选择路线、则多个第一乘客和车辆车队将获得的状态(例如，候选状态是潜在状态，如果路线通过该潜在状态被选择，则它将成为选择的状态)。例如，候选状态可以包括指示乘客pj正在乘坐车辆vi的信息。状态图表示的相应边(例如，每个相应边)表示相应车辆使乘客上车或下车的动作。例如，边可以表示行驶去接乘客pj上车的车辆vi。因此，连接到该边的下游节点将包括指示乘客pj正在乘坐车辆vi的信息。相应边具有至少部分地基于地理地图的图表示的遍历的成本。例如，相应边具有与相应车辆使乘客上车或下车的动作相关联的成本，其包括行程时间成本或本文描述的任何其他成本(例如，参考图15a-图15b的方法1500描述的成本)。因此，在一些实施例中，多个第一乘客和车队车辆的状态图表示的一些或全部边表示与使乘客上车或下车的动作相关联的单个车辆路由问题的解决方案(例如，使用地图的图表示)。车辆路由服务器1420生成(2614)车队车辆的路线集合，包括将待上车和待下车的多个第一乘客中的每个乘客分配给车队车辆的相应车辆(例如，将相应车辆分配给每个乘客，使得相应车辆接乘客上车和使乘客下车)。通过评估包括各条边的成本的成本模型，对状态图表示进行图搜索而生成用于车队车辆的路线。在一些实施例中，生成用于相应车辆的路线包括：为相应车辆生成到乘客被分配的上车位置的路线(例如，请求上车位置或请求上车位置附近的不同上车位置)。在一些实施例中，生成路线集合包括：为相应车队车辆生成从乘客被分配的上车位置到被分配的下车位置(例如，请求下车位置或请求下车位置附近的不同下车位置)的路线。在一些实施例中，图搜索是(2616)双向搜索(例如，如本文其他地方描述的)。通过使用双向搜索允许图搜索被更快地完成，而解决技术问题。在某些情况下，使用双向搜索使状态图表示的使用变得切实可行(例如，足够快以通过实时请求执行)，因此更普遍地产生方法2600的技术优势(例如，节约资源、减少交通量并增加乘客的舒适度和安全性)。在一些实施例中，在执行状态图表示的图搜索的同时生成状态图表示。例如，车辆路由服务器1420生成状态图表示的节点和边的初始集合。如下面更详细地描述的，在一些实施例中，车辆路由服务器1420使用下限启发法来消除的状态图表示的部分。因此，在一些实施例中，通过下限启发法，对于已经呈现出无实际意义的状态图表示的部分，车辆路由服务器1420放弃一些或全部节点和边(例如，通过下限启发法放弃生成呈现出无实际意义的所有边和节点，除了需要首先计算下限启发法的那些)。在一些实施例中，如参考图19-图23描述的，生成用于车队车辆的路线集合包括(2618)：基于第一乘客的请求上车位置，将第一多个乘客中的每个乘客分配到一个或多个候选上车位置；基于第一乘客的请求下车位置，将第一多个乘客中的每个乘客分配到一个或多个候选下车位置；根据他们被分配的候选上车位置和下车位置对第一多个乘客进行聚类；将车队车辆中的各个车辆分配给多个集群；以及根据分配给车队车辆的各个车辆的多个集群，并行化车队车辆的路由。在某些实施例中，候选上车(下车)位置是第一乘客请求的上车位置附近的可允许上车(下车)位置。在一些实施例中，候选上车(下车)位置是自主车辆可以进入的位置(即，用于自主车辆的可进入位置)。在一些实施例中，车辆路由服务器1420向各个乘客提供信息，以将各个乘客引导到其被分配的上车位置(例如，将其被分配的上车位置通知各个乘客，或路由各个乘客步行到其被分配的上车位置)。在某些情况下，上面描述的聚类过程允许车队路由问题以有效方式并行化。在某些情况下，上面描述的聚类过程允许方法2600更快地完成。在某些情况下，上面描述的聚类过程使状态图表示的使用变得切实可行(例如，足够快以通过实时请求执行)，从而更普遍地产生方法2600的技术优势(例如，节约资源、减少交通量并增加乘客的舒适度和安全性)。在一些实施例中，如参考“简单的最低界限启发法”和“上车-下车界限启发法”部分描述的，进行图搜索包括(2620)：通过放弃来自状态图表示中的对其而言成本函数的最低界限超出车队车辆的已确定路线集合的成本的任何节点的后续探索，使用最低界限启发法来限制在状态图表示中探索的状态数量。如本文所使用的，下限启发法是基于成本函数下限的确定来限制搜索空间(例如，通过放弃来自相应节点的后续探索来限制状态图表示的探索)的条件。相应节点的成本函数的下限意味着来自相应节点的任何实际路线将具有大于或等于成本函数的下限的成本(例如，成本函数的下限是来自相应节点的路线的成本的底限)。因此，在一些实施例中，车辆路由服务器1420确定状态图表示中的相应节点(例如，多个节点)的下限，并且基于下限启发法(例如，如果成本的下限超出路由问题的已存在的解决方案的成本)，放弃状态图表示中的来自相应节点(例如，多个节点)的后续探索。例如，如果图探索前往表示进入相应车辆的乘客的相应节点，车辆至少必须使该乘客下车。如果使该乘客下车的成本导致成本超出路由问题的已存在的解决方案的成本，则车辆路由系统1420放弃探索相应节点下游的任何内容(例如，放弃生成相应节点下游的所有或一些图)。在某些情况下，从探索中消除状态图表示的部分允许更快地完成方法2600。在某些情况下，消除状态图表示的部分使状态图表示的使用变得切实可行(例如，足够快以通过实时请求执行)，因此，更普遍地产生方法2600的技术优势(例如，节约资源、减少交通量并增加乘客的舒适度和安全性)。在一些实施例中，成本模型包括(2622)第一乘客的上车等待时间。在一些实施例中，成本模型包括等待车辆的乘客的成本和/或(例如，在乘坐期间)在车辆中等待的乘客的成本。在一些实施例中，乘客不必是人类(例如，可以是包裹)，因此成本模型不包括乘客等待车辆的成本和/或乘客在车辆中等待的成本。相反，例如，当乘客是包裹时，成本模型对按时交付进行大量加权。在某些实施例中，乘客包括人类乘坐者和包裹的组合，请求将乘客识别为人类还是包裹。当乘客是人类时，成本模型包括乘客等待车辆的成本和/或乘客在车辆中等待的成本。当乘客不是人类时，成本模型不包括乘客等待车辆的成本和/或乘客在车辆中等待的成本。车辆路由服务器1420根据生成的路线集合路由(2624)车队车辆。在一些实施例中，根据生成的路线集合来路由车队车辆包括：将每个车辆的路线发送给车辆。在一些实施例中，根据生成的路线集合来路由车队车辆包括：将生成的路线集合发送给车队车辆的运营商。在一些实施例中，根据生成的路线来路由车队车辆包括：将被分配为接乘客上车的相应车辆路由到该乘客被分配的上车位置(例如，请求上车位置或请求上车位置附近的不同上车位置)。在某些实施例中，路由车队车辆包括将相应车辆从乘客被分配的上车位置路由到被分配的下车位置(例如，请求下车位置或请求下车位置附近的不同下车位置)。操作2626-2632描述一种将附加乘客插入到生成的路线集合中的方法。将附加乘客插入到生成的路线集合中允许车队路由问题在已生成路线集合之后得以继续有效地被解决，这节省资源(例如，减少自主车辆的碳排放量和/或电池使用量)、减少交通量并增加乘客的舒适度和安全性。在一些实施例中，车辆路由服务器1420接收(2626)来自不同于多个第一乘客的第二乘客的乘车请求。请求包括第二乘客的请求上车位置和请求下车位置。在一些实施例中，来自第二乘客的请求是动态请求(例如，待尽可能快地进行上车和/或下车的实时请求)。在一些实施例中，在接收到来自多个第一乘客的请求之后，接收到来自第二乘客的请求。在一些实施例中，在生成路线集合之后，接收到来自第二乘客的请求。在某些实施例中，接收到来自第二乘客的请求，同时一些或所有的车辆正在进行生成的路线集合中的它们各自的路线(在它们各自路线上)。在一些实施例中，车辆路由服务器1420将第二乘客的请求插入到现有生成的路线集合中。为此，在某些实施例中，车辆路由服务器1420根据一个或多个最便宜插入标准，更新(2628)车队车辆中的相应车辆的路线，包括将待上车和待下车的第二乘客分配给相应车辆。例如，不是使用车队车辆、第一多个乘客和第二乘客的新成本模型来从头进行状态图搜索，车辆路由服务器1420根据车队车辆、第一多个乘客和第二乘客的新成本模型，确定哪条现有路线是最便宜的路线来插入第二乘客的请求。在一些实施例中，如下面描述的，允许有限数量(例如，预定义数量)的“交易”乘客(例如，交易一位乘客)。在一些实施例中，更新车队车辆的相应车辆的路线包括(2630)：将第二乘客的上车位置和下车位置插入到相应车辆的现有路线中，而无需修改已分配给相应车辆(例如但尚未上车)的乘客的上车和下车位置。在一些实施例中，更新车队车辆的相应车辆的路线包括(2632)：将第二乘客的上车位置和下车位置插入到相应车辆的现有路线中；以及将已分配给相应车辆(例如但尚未上车)的乘客重新分配给车队车辆中的不同车辆(例如，交易乘客)。在一些实施例中，通过以下更新车队车辆的相应车辆的路线，包括将待上车和待下车的第二乘客分配给相应车辆：将第二乘客分配到现有集群(例如，在操作2618处生成的)；以及更新分配到现有集群的车辆的路线。在一些实施例中，因为状态图表示的复杂性随着更多请求的到来而增加，更新车队车辆的相应车辆的路线包括更新状态图表示(例如，使得状态图表示是多个第一乘客和第二乘客以及车辆车队的表示)，并使用更新后的状态图表示的至少部分来进行图搜索。还应当理解的是，尽管在某些情况下，术语“第一”、“第二”等在本文中用于描述各种元件，但是这些元件不应受到这些术语的限制。这些术语仅用于区分一个元件和另一个元件。例如，第一辆车可以被称为第二车辆，类似地，第二车辆可以被称为第一车辆，只要所有出现的“第一车辆”均被一致地重命名并且所有出现的第二车辆均被一致地重命名，改变描述的含义。第一车辆和第二车辆都是车辆，但是它们不是同一车辆(例如，第二车辆是附加车辆)。本文所使用的术语仅是出于描述具体实施例的目的，并不旨在限制权利要求。如在实施例和所附权利要求的描述中所使用的，单数形式“一”、“一个”和“该”也旨在包括复数形式，除非上下文另外明确指出。还应当理解的是，本文所使用的术语“和/或”是指并且涵盖一个或多个相关联所列项目的任何和所有可能的组合。还将理解的是，当在本说明书中使用时，术语“包括”和/或“包含”指定了所陈述的特征、整数、步骤、操作、元件和/或组件的存在，但不排除存在或附加一个或多个其他特征、整数、步骤、操作、元件、组件和/或它们的组。如本文所使用，术语“如果”可选地应解释为表示所陈述条件先例为真的“当”或“在…时”或“响应于确定”或“根据确定”或“响应于检测”，这取决于上下文。类似地，短语“如果确定(陈述条件先例为真)”或“如果(陈述条件先例为真)”或“当(陈述条件先例为真)”，可选地应解释为表示所陈述条件先例为真的“在确定时”或“响应于确定”或“根据确定”或“在检测时”或“响应于检测”，这取决于上下文。前述描述包括体现说明性实施例的示例系统、方法、技术、指令序列和计算机器程序产品。出于解释说明的目的，阐述许多具体细节以便提供对发明主题的各种实施例的理解。但是，对于本领域技术人员将显而易见的是，在没有这些具体细节的情况下可选地实践主题的实施例。通常，没有详细示出公知的指令实例、协议、结构和技术。出于解释说明的目的，已经参考具体实施例描述了前述描述。但是，以上说明性讨论并不旨在穷举或将实施例限制为所公开的精确形式。鉴于以上教导，许多修改和变化是可能的。选择和描述实施例是为了最好地解释原理及其实际应用，从而使本领域的其他技术人员能够最好地使用实施例以及具有适于预期的特定用途的各种修改的各种实施例。当前第1页1 2 3
技术特征：1.一种车辆路由方法，包括：
在包括一个或多个处理器和存储器的计算机系统上：
接收将自主车辆从第一位置路由到第二位置的请求；以及
生成用于路由自主车辆的成本模型，其中成本模型包括除行程时间以外的一个或多个成本，除行程时间以外的一个或多个成本选自由以下组成的组：
遍历禁止自主驾驶的区域的成本；
驾驶操纵的成本；
自主车辆的特性的成本；
天气状况的成本；
一天中的时间的成本；
日照角度的成本；
行人交通模式的成本；
非机动车辆交通模式的成本；
路面状况的成本；
道路使用年限的成本；
在路由请求时发生的事件的成本；
缺少车道线的道路的成本；
充电约束的成本；以及
加速的成本；
响应于路由自主车辆的请求：
根据成本模型选择从第一位置到第二位置的路线；以及
沿着选择的路线路由自主车辆。
2.根据权利要求1所述的方法，其中，响应于路由自主车辆的请求来生成成本模型。
3.根据权利要求1-2中任一项所述的方法，其中：
成本模型是用于自主车辆的第一成本模型；以及
方法包括：
接收将非自主车辆从第三位置路由到第四位置的请求；以及
生成用于路由非自主车辆的第二成本模型，其中第二成本模型不同于第一成本模型，并且不包括第一成本模型所包括的除行程时间以外的成本中的一个或多个；
响应于路由非自主车辆的请求：
根据第二成本模型选择从第三位置到第四位置的路线；以及
沿着为非自主车辆选择的路线路由非自主车辆。
4.根据权利要求1-3中任一项所述的方法，其中：
自主车辆是具有第一自主驾驶能力的第一自主车辆；
成本模型是用于第一自主车辆的第一成本模型；以及
用于第一成本模型的除行程时间以外的一个或多个成本包括对应于第一自主驾驶能力的成本；
方法包括：
接收将第二自主车辆从第五位置路由到第六位置的请求，其中，第二自主车辆具有不同于第一自主驾驶能力的第二自主驾驶能力；以及
生成用于路由第二自主车辆的第三成本模型，其中，第三成本模型不同于第一成本模型，并且包括对应于第二自主驾驶能力的成本；
响应于路由第二自主车辆的请求：
根据第二成本模型选择从第五位置到第六位置的路线；以及
沿着为第二自主车辆选择的路线路由第二自主车辆。
5.根据权利要求1-4中任一项所述的方法，其中，成本模型还包括行程时间成本，并且根据行程时间成本和除行程时间以外的一个或多个成本来选择路线。
6.根据权利要求1-5中任一项所述的方法，其中：
除行程时间以外的一个或多个成本包括在路由请求时发生的事件的成本；以及
在路由请求时发生的事件是施工项目或交通事故。
7.根据权利要求1-6中任一项所述的方法，其中：
除行程时间以外的一个或多个成本包括在路由请求时发生的事件的成本；
在路由请求时发生的事件是定期安排的事件；以及
根据在路由请求时正发生定期安排的事件的确定，至少部分地基于定期安排的事件的成本进行选择路线。
8.根据权利要求1-6中任一项所述的方法，其中：
除行程时间以外的一个或多个成本包括在路由请求时发生的事件的成本；
在路由请求时发生的事件是定期安排的事件；以及
根据定期安排的事件将在自主车辆预期到达定期安排的事件的时刻发生的确定，至少部分地基于定期安排的事件的成本进行选择路线。
9.根据权利要求1-8中任一项所述的方法，其中，驾驶操纵选自由车道改变、右转弯、左转弯、没有保护的左转弯、u形转弯和高速公路合并组成的组。
10.根据权利要求1-9中任一项所述的方法，其中：
除行程时间以外的一个或多个成本包括自主车辆的特性的成本；以及
自主车辆的特性是车辆类型。
11.根据权利要求1-10中任一项所述的方法，其中：
除行程时间以外的一个或多个成本包括自主车辆的特性的成本；以及
自主车辆的特性是自主车辆的自主驾驶能力。
12.根据权利要求1-11中任一项所述的方法，其中，除行程时间以外的一个或多个成本中的至少一个是用于特定地理区域、道路、道路内的车道或操纵的成本。
13.根据权利要求1-12中任一项所述的方法，其中，除行程时间以外的一个或多个成本包括：对于多条不同道路，在不同道路上对于共享天气状况的多个不同的特定道路成本。
14.根据权利要求1-13中任一项所述的方法，其中，除行程时间以外的一个或多个成本包括：对于多条不同道路，在不同道路上对于不同天气状况的多个不同的特定道路成本。
15.根据权利要求1-14中任一项所述的方法，其中，除行程时间以外的一个或多个成本包括：对于不同道路的一天中的时间的多个不同的特定道路成本。
16.根据权利要求1-15中任一项所述的方法，其中，除行程时间以外的一个或多个成本包括：对于不同道路的日照角度的多个不同的特定道路成本。
17.一种计算机系统，包括：
一个或多个处理器；以及
存储一个或多个程序的存储器，一个或多个程序存储指令，指令当被一个或多个处理器执行时，使计算机系统执行权利要求1-16中任一项所述的方法。
18.一种自主车辆，包括：
计算机系统，包括：
一个或多个处理器；以及
存储一个或多个程序的存储器，一个或多个程序存储指令，指令当被一个或多个处理器执行时，使一个或多个处理器执行权利要求1-16中任一项所述的方法。
19.一种非暂时性计算机可读存储介质，存储有指令，指令当被具有一个或多个处理器的计算机系统执行时，使计算机系统执行根据权利要求1-16中任一项所述的方法。
20.一种路由自主车辆的方法，包括：
在包括一个或多个处理器和存储器的计算机系统上：
接收将自主车辆从第一位置路由到第二位置的请求；
识别自主车辆的一个或多个自主驾驶能力的集合；
根据自主车辆的一个或多个自主驾驶能力的集合，选择从第一位置到第二位置的路线；以及
根据选择的路线路由自主车辆。
21.根据权利要求20所述的方法，其中：
自主车辆是第一自主车辆；
方法包括：
接收将第二自主车辆从第三位置路由到第四位置的请求；
识别第二自主车辆的一个或多个自主驾驶能力的集合，其中第二自主车辆的一个或多个自主驾驶能力的集合包括不同于第一自主车辆的一个或多个自主驾驶能力的集合的至少一个自主驾驶能力；
根据第二自主车辆的一个或多个自主驾驶能力的集合，选择从第三位置到第四位置的路线；以及
根据为第二自主车辆选择的路线路由第二自主车辆。
22.根据权利要求20-21中任一项所述的方法，其中，识别自主车辆的一个或多个自主驾驶能力的集合包括：与请求一起接收自主驾驶能力。
23.根据权利要求20-22中任一项所述的方法，还包括，在计算机系统上：
与路由自主车辆的请求一起接收用于自主车辆的标识符；
其中识别包括：基于标识符查找自主车辆的一个或多个自主驾驶能力。
24.根据权利要求20-23中任一项所述的方法，还包括，在计算机系统上：
生成用于路由自主车辆的成本模型，成本模型包括用于自主车辆的一个或多个自主驾驶能力的集合的一个或多个成本；
其中选择包括：至少部分地基于成本模型，选择从第一位置到第二位置的路线。
25.根据权利要求20-24中任一项所述的方法，其中，自主车辆的一个或多个自主驾驶能力的集合包括自主车辆的传感器的能力。
26.根据权利要求20-25中任一项所述的方法，其中，自主车辆的一个或多个自主驾驶能力的集合包括自主车辆的可操纵性。
27.根据权利要求20-26中任一项所述的方法，其中，自主车辆的一个或多个自主驾驶能力的集合包括从自主车辆和与自主车辆相同类型的车辆中的至少一个的历史性能数据确定的对自主车辆的限制。
28.根据权利要求20-27中任一项所述的方法，其中：
自主车辆的一个或多个自主驾驶能力的集合包括用于自主车辆的安全等级；以及
至少部分地基于自主车辆的安全等级进行选择。
29.根据权利要求20-28中任一项所述的方法，其中：
自主车辆的一个或多个自主驾驶能力的集合包括自主车辆的多个自主驾驶能力；以及
至少部分地基于自主车辆的多个自主驾驶能力进行选择。
30.一种计算机系统，包括：
一个或多个处理器；以及
存储一个或多个程序的存储器，一个或多个程序存储指令，指令当被一个或多个处理器执行时，使计算机系统执行权利要求20-29中任一项所述的方法。
31.一种自主车辆，包括：
计算机系统，包括：
一个或多个处理器；以及
存储一个或多个程序的存储器，一个或多个程序存储指令，指令当被一个或多个处理器执行时，使计算机系统执行权利要求20-29中任一项所述的方法。
32.一种非暂时性计算机可读存储介质，存储有指令，指令当被具有一个或多个处理器的计算机系统执行时，使一个或多个处理器执行根据权利要求20-29中任一项所述的方法。
33.一种路由自主车辆的方法，包括：
在包括一个或多个处理器和存储器的计算机系统上：
生成用于路由自主车辆的成本模型，其中成本模型包括，对于交叉路口，用于遍历通过交叉路口的不同路径的多个成本；
接收将自主车辆从第一位置路由到第二位置的请求；以及
响应于路由自主车辆的请求：
根据成本模型选择从第一位置到第二位置的路线，其中选择至少部分地基于用于遍历通过交叉路口的不同路径的多个成本中的一个；以及
根据选择的路线路由自主车辆。
34.根据权利要求33所述的方法，其中：
成本模型被表示为节点和边的图，各条边具有表示成本的各自边权重；以及
方法还包括，在计算机系统上，将交叉路口表示为多个节点和具有边权重的多条边，其中，交叉路口的表示的每条边表示通过交叉路口的不同路径。
35.如权利要求34所述的方法，还包括，在计算机系统上，放弃通过交叉路口的禁止路径的表示。
36.根据权利要求33-35中任一项所述的方法，其中，交叉路口是多条道路的交点，多条道路中的每条道路具有一个或多个成本，所述一个或多个成本不同于用于遍历通过交叉路口的不同路径的多个成本。
37.根据权利要求33-36中任一项所述的方法，其中，用于遍历通过交叉路口的不同路径的多个成本包括：用于遍历通过交叉路口的不同路径中的一条的驾驶操纵的一个或多个成本。
38.根据权利要求37所述的方法，其中，驾驶操纵选自由车道改变、右转弯、左转弯、没有保护的左转弯、u形转弯和高速公路合并组成的组。
39.一种计算机系统，包括：
一个或多个处理器；以及
存储一个或多个程序的存储器，一个或多个程序存储指令，指令当被一个或多个处理器执行时，使计算机系统执行权利要求33-38中任一项所述的方法。
40.一种自主车辆，包括：
计算机系统，包括：
一个或多个处理器；以及
存储一个或多个程序的存储器，一个或多个程序存储指令，指令当被一个或多个处理器执行时，使一个或多个处理器执行权利要求33-38中任一项的方法。
41.一种非暂时性计算机可读存储介质，存储有指令，指令当被具有一个或多个处理器的计算机系统执行时，使计算机系统执行根据权利要求33-38中任一项所述的方法。
42.一种路由自主车辆的方法，包括：
在包括一个或多个处理器和存储器的计算机系统上：
接收从不同于自主车辆的第二车辆上的相机获得的信息；
通过使用从第二车辆上的相机接收到的信息的图像分析，自动地识别道路状况；
接收将自主车辆从第一位置路由到第二位置的请求；以及
响应于请求：
生成用于路由自主车辆的成本模型，其中成本模型包括从接收自第二车辆上的相机的信息自动识别出的道路状况的成本；
根据成本模型选择从第一位置到第二位置的路线；以及
根据选择的路线路由自主车辆。
43.根据权利要求42所述的方法，其中，生成成本模型包括：响应于请求更新先前的成本模型。
44.根据权利要求42-43中任一项所述的方法，还包括，在计算机系统上：
确定在请求时是否存在道路状况；以及
其中，根据在请求时存在道路状况的确定，将道路状况的成本包括在成本模型中。
45.根据权利要求42-44中任一项所述的方法，其中，从接收自第二车辆上的相机的信息自动识别出的道路状况是选自由天气状况、由于天气引起的道路状况、由于施工引起的道路状况以及由于交通事故引起的道路状况组成的组的状况。
46.根据权利要求42-44中任一项所述的方法，其中，从接收自第二车辆上的相机的信息自动识别出的道路状况是选自由日照角度、行人交通、非机动车辆交通、路面状况和缺少车道线组成的组的状况。
47.根据权利要求42-46中任一项所述的方法，其中，相机是行车记录仪。
48.一种计算机系统，包括：
一个或多个处理器；以及
存储一个或多个程序的存储器，一个或多个程序存储指令，指令当被一个或多个处理器执行时，使计算机系统执行权利要求42-47中任一项所述的方法。
49.一种自主车辆，包括：
计算机系统，包括：
一个或多个处理器；以及
存储一个或多个程序的存储器，一个或多个程序存储指令，指令当被一个或多个处理器执行时，使一个或多个处理器执行权利要求42-47中任一项所述的方法。
50.一种非暂时性计算机可读存储介质，存储有指令，指令当被具有一个或多个处理器的计算机系统执行时，使计算机系统执行根据权利要求42-47中任一项所述的方法。
51.一种用于乘车共享的交通网络的路由方法，包括：
存储多个第一乘客的表示，其中多个第一乘客的表示中的每个包括多个第一乘客的相应第一乘客的请求上车位置和请求下车位置；
存储多个车队车辆的表示；
生成地理地图的图表示，图表示包括多个第一乘客的请求上车位置和请求下车位置；
生成多个第一乘客和车队车辆的状态图表示，其中：
状态图表示包括通过边连接的多个节点；
状态图表示的多个节点中的每个节点表示多个第一乘客和车队车辆的候选状态；
状态图表示的相应边表示相应车辆使乘客上车或下车的动作，以及
相应边具有至少部分地基于地理地图的图表示的遍历的成本；
生成用于车队车辆的路线集合，包括将待上车和待下车的多个第一乘客中的每个乘客分配给车队车辆的相应车辆，其中，通过评估包括各条边的成本的成本模型，对状态图表示进行图搜索而生成用于车队车辆的路线；以及
根据生成的路线集合路由车队车辆。
52.根据权利要求51所述的方法，其中，车队车辆包括多个自主车辆。
53.根据权利要求51-52中任一项所述的方法，其中，多个车队车辆由单个运营商运营。
54.根据权利要求51-53中任一项所述的方法，包括：
从不同于多个第一乘客的第二乘客接收乘坐请求，其中，请求包括第二乘客的请求上车位置和请求下车位置；以及
根据一个或多个最便宜插入标准更新车队车辆的相应车辆的路线，包括将待上车和待下车的第二乘客分配给相应车辆。
55.根据权利要求54所述的方法，其中，更新车队车辆的相应车辆的路线包括：将第二乘客的上车位置和下车位置插入到相应车辆的现有路线中，而无需修改已分配给相应车辆的乘客的上车位置和下车位置。
56.根据权利要求54所述的方法，其中，更新车队车辆的相应车辆的路线包括：
将第二乘客的上车位置和下车位置插入到相应车辆的现有路线中；以及
将已分配给相应车辆的乘客重新分配给车队车辆的不同车辆。
57.根据权利要求51-56中任一项所述的方法，其中，生成用于车队车辆的路线集合包括：
基于第一乘客的请求上车位置，将第一多个乘客中的每个乘客分配到一个或多个候选上车位置；
基于第一乘客的请求下车位置，将第一多个乘客中的每个乘客分配到一个或多个候选下车位置；
根据他们被分配的候选上车位置和候选下车位置对第一多个乘客进行聚类；
将车队车辆的各个车辆分配到多个集群；以及
根据为车队车辆的各个车辆分配的多个集群，并行化车队车辆的路由。
58.根据权利要求57所述的方法，包括：
从不同于多个第一乘客的第二乘客接收乘坐请求，其中，请求包括第二乘客的请求上车位置和请求下车位置；以及
通过以下步骤更新车队车辆的相应车辆的路线，包括将待上车和待下车的第二乘客分配给相应车辆：
将第二乘客分配到现有集群；以及
更新分配到现有集群的车辆的路线。
59.根据权利要求51-58中的任一项所述的方法，其中，进行图搜索包括：通过放弃来自状态图表示中的对于其成本函数的最低界限超出车队车辆的已确定路线集合的成本的任何节点的后续探索，使用最低界限启发法，限制在状态图表示中探索的状态数量。
60.根据权利要求51-59中任一项所述的方法，其中，成本模型包括第一乘客的上车等待时间。
61.根据权利要求51-60中任一项所述的方法，其中，图搜索是双向搜索。
62.一种计算机系统，包括：
一个或多个处理器；以及
存储一个或多个程序的存储器，一个或多个程序存储指令，指令当被一个或多个处理器执行时，使计算机系统执行权利要求51-61中的任一项所述的方法。
63.一种非暂时性计算机可读存储介质，存储有指令，指令当被具有一个或多个处理器的计算机系统执行时，使计算机系统执行根据权利要求51-61中任一项所述的方法。
技术总结提供了用于路由自主车辆的系统和方法。在一个方面，提供了一种方法，方法包括生成用于路由自主车辆的成本模型。成本模型包括除行程时间以外的一个或多个成本。除行程时间以外的一个或多个成本可以包括：例如遍历禁止自主驾驶的区域的成本、自主车辆的特性的成本或缺少车道线的道路的成本。方法还包括接收将自主车辆从第一位置路由到第二位置的请求。方法还包括：响应于路由自主车辆的请求，根据成本模型选择从第一位置到第二位置的路线，以及沿着选择的路线路由自主车辆。
技术研发人员：贾斯汀·候;克里斯托弗·布鲁门伯格;比利·陈;罗汉·帕拉尼佩;托马斯·基尔布斯;克里斯托弗·摩尔;敏·姬·李;埃里克·里德;米歇尔·特里科特
受保护的技术使用者：瑞迪欧斯公司
技术研发日：2018.10.19
技术公布日：2020.06.05
