Nothing Special   »   [go: up one dir, main page]

CN114174766A - 中间路径点生成器 - Google Patents

中间路径点生成器 Download PDF

Info

Publication number
CN114174766A
CN114174766A CN201980098897.7A CN201980098897A CN114174766A CN 114174766 A CN114174766 A CN 114174766A CN 201980098897 A CN201980098897 A CN 201980098897A CN 114174766 A CN114174766 A CN 114174766A
Authority
CN
China
Prior art keywords
yaw
map
robot
generating
node
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Pending
Application number
CN201980098897.7A
Other languages
English (en)
Inventor
G.C.费
A.里齐
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Boston Dynamics Inc
Original Assignee
Boston Dynamics Inc
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Boston Dynamics Inc filed Critical Boston Dynamics Inc
Publication of CN114174766A publication Critical patent/CN114174766A/zh
Pending legal-status Critical Current

Links

Images

Classifications

    • G—PHYSICS
    • G01—MEASURING; TESTING
    • G01C—MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY
    • G01C21/00—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00
    • G01C21/20—Instruments for performing navigational calculations
    • B—PERFORMING OPERATIONS; TRANSPORTING
    • B25—HAND TOOLS; PORTABLE POWER-DRIVEN TOOLS; MANIPULATORS
    • B25J—MANIPULATORS; CHAMBERS PROVIDED WITH MANIPULATION DEVICES
    • B25J9/00—Programme-controlled manipulators
    • B25J9/16—Programme controls
    • B25J9/1656—Programme controls characterised by programming, planning systems for manipulators
    • B25J9/1664—Programme controls characterised by programming, planning systems for manipulators characterised by motion, path, trajectory planning
    • B—PERFORMING OPERATIONS; TRANSPORTING
    • B25—HAND TOOLS; PORTABLE POWER-DRIVEN TOOLS; MANIPULATORS
    • B25J—MANIPULATORS; CHAMBERS PROVIDED WITH MANIPULATION DEVICES
    • B25J9/00—Programme-controlled manipulators
    • B25J9/16—Programme controls
    • B25J9/1694—Programme controls characterised by use of sensors other than normal servo-feedback from position, speed or acceleration sensors, perception control, multi-sensor controlled systems, sensor fusion
    • B25J9/1697—Vision controlled systems
    • B—PERFORMING OPERATIONS; TRANSPORTING
    • B62—LAND VEHICLES FOR TRAVELLING OTHERWISE THAN ON RAILS
    • B62D—MOTOR VEHICLES; TRAILERS
    • B62D57/00—Vehicles characterised by having other propulsion or other ground- engaging means than wheels or endless track, alone or in addition to wheels or endless track
    • B62D57/02—Vehicles characterised by having other propulsion or other ground- engaging means than wheels or endless track, alone or in addition to wheels or endless track with ground-engaging propulsion means, e.g. walking members
    • B62D57/032—Vehicles characterised by having other propulsion or other ground- engaging means than wheels or endless track, alone or in addition to wheels or endless track with ground-engaging propulsion means, e.g. walking members with alternately or sequentially lifted supporting base and legs; with alternately or sequentially lifted feet or skid
    • G—PHYSICS
    • G05—CONTROLLING; REGULATING
    • G05D—SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
    • G05D1/00—Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots
    • G05D1/02—Control of position or course in two dimensions
    • G05D1/021—Control of position or course in two dimensions specially adapted to land vehicles
    • G05D1/0231—Control of position or course in two dimensions specially adapted to land vehicles using optical position detecting means
    • G05D1/0246—Control of position or course in two dimensions specially adapted to land vehicles using optical position detecting means using a video camera in combination with image processing means
    • G05D1/0248—Control of position or course in two dimensions specially adapted to land vehicles using optical position detecting means using a video camera in combination with image processing means in combination with a laser
    • G—PHYSICS
    • G05—CONTROLLING; REGULATING
    • G05D—SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
    • G05D1/00—Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots
    • G05D1/02—Control of position or course in two dimensions
    • G05D1/021—Control of position or course in two dimensions specially adapted to land vehicles
    • G05D1/0268—Control of position or course in two dimensions specially adapted to land vehicles using internal positioning means
    • G05D1/0274—Control of position or course in two dimensions specially adapted to land vehicles using internal positioning means using mapping information stored in a memory device
    • G—PHYSICS
    • G05—CONTROLLING; REGULATING
    • G05B—CONTROL OR REGULATING SYSTEMS IN GENERAL; FUNCTIONAL ELEMENTS OF SUCH SYSTEMS; MONITORING OR TESTING ARRANGEMENTS FOR SUCH SYSTEMS OR ELEMENTS
    • G05B2219/00—Program-control systems
    • G05B2219/30—Nc systems
    • G05B2219/40—Robotics, robotics mapping to robotics vision
    • G05B2219/40519—Motion, trajectory planning
    • G—PHYSICS
    • G05—CONTROLLING; REGULATING
    • G05D—SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
    • G05D1/00—Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots
    • G05D1/0088—Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots characterized by the autonomous decision making process, e.g. artificial intelligence, predefined behaviours
    • G—PHYSICS
    • G05—CONTROLLING; REGULATING
    • G05D—SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
    • G05D1/00—Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots
    • G05D1/02—Control of position or course in two dimensions
    • G05D1/021—Control of position or course in two dimensions specially adapted to land vehicles
    • G05D1/0212—Control of position or course in two dimensions specially adapted to land vehicles with means for defining a desired trajectory
    • G05D1/0214—Control of position or course in two dimensions specially adapted to land vehicles with means for defining a desired trajectory in accordance with safety or protection criteria, e.g. avoiding hazardous areas

Landscapes

  • Engineering & Computer Science (AREA)
  • Radar, Positioning & Navigation (AREA)
  • Remote Sensing (AREA)
  • Physics & Mathematics (AREA)
  • Mechanical Engineering (AREA)
  • Automation & Control Theory (AREA)
  • General Physics & Mathematics (AREA)
  • Robotics (AREA)
  • Aviation & Aerospace Engineering (AREA)
  • Chemical & Material Sciences (AREA)
  • Combustion & Propulsion (AREA)
  • Transportation (AREA)
  • Computer Vision & Pattern Recognition (AREA)
  • Multimedia (AREA)
  • Electromagnetism (AREA)
  • Optics & Photonics (AREA)
  • Control Of Position, Course, Altitude, Or Attitude Of Moving Bodies (AREA)
  • Business, Economics & Management (AREA)
  • Health & Medical Sciences (AREA)
  • Artificial Intelligence (AREA)
  • Evolutionary Computation (AREA)
  • Game Theory and Decision Science (AREA)
  • Medical Informatics (AREA)
  • Manipulator (AREA)
  • Navigation (AREA)

Abstract

一种用于为机器人(10)的导航系统(100)生成中间路径点(310)的方法，该方法包含接收导航路线(112)。该导航路线包含开始于起始位置(113)处并结束于目的地位置(114)处的一系列高级路径点(210)，并且基于表示机器人要导航的区域中的静态障碍物的位置的高级导航数据(50)。该方法还包含从图像传感器(31)接收机器人周围的环境(8)的图像数据(17)，并基于该图像数据生成至少一个中间路径点。该方法还包括将至少一个中间路径点添加到该导航路线的该一系列高级路径点，并且将机器人从起始位置沿着该一系列高级路径点和该至少一个中间路径点朝向目的地位置导航。

Description

中间路径点生成器
技术领域
本公开涉及在存在约束的情况下生成中间路径点，尤其是那些由地形施加的约束的情况。
背景技术
机器人设备越来越多地用于在受约束的环境中导航以执行各种任务或功能。这些机器人设备经常需要在不与障碍物接触或不被卡住或被困的情况下导航穿过这些受约束的环境。随着这些机器人设备变得更盛行，需要避免与障碍物接触同时成功导航到目的地的实时导航和路线规划。
发明内容
本公开的一个方面提供了用于生成针对机器人的导航系统的中间路径点的方法。该方法包含在机器人的数据处理硬件处接收导航路线。该导航路线包含一系列高级路径点，该一系列高级路径点开始于起始位置处并结束于目的地位置处，并且基于高级导航数据。该高级导航数据表示在机器人要导航的区域中的静态障碍物的位置。该方法还包含在数据处理硬件处，从图像传感器接收机器人周围的环境的图像数据。该方法还包含由数据处理硬件基于该图像数据生成至少一个中间路径点。该方法还包含由数据处理硬件将该至少一个中间路径点添加到该导航路线的该一系列高级路径点，以及由数据处理硬件将机器人从起始位置沿着该一系列高级路径点和该至少一个中间路径点朝向目的地位置导航。
本公开的实施方式可以包含以下可选特征中的一个或多个特征。在一些实施方式中，每个高级路径点和每个中间路径点包含指示平面上的位置的两个坐标、偏航值和时间值。该时间值指示对于机器人导航到相应路径点的估计的时间量。在一些示例中，该方法还包含由数据处理硬件维护该导航路线上的该一系列高级路径点中的每个高级路径点。该方法还可以包含在数据处理硬件处接收身体障碍物地图。该身体障碍物地图包含机器人的身体不能穿越的障碍物的地图。附加地，生成至少一个中间路径点可以包含基于该身体障碍物地图生成稀疏图。该稀疏图包含一系列节点和边。该节点和边表示该机器人可以在环境中行进的路径。该方法还可以包含规划从来自一系列节点的第一节点至来自该一系列节点的第二节点的粗略路径。第一节点和第二节点各表示环境中的空间。该方法还可以包含确定沿着该粗略路径的图像传感器的视线丢失的点，并且在视线丢失的点处生成至少一个中间路径点之一。
在一些实施方式中，生成该稀疏图包含基于身体障碍物地图生成完全配置空间地图。该完全配置空间地图包含元素的二维网格，其中该网格的每个元素表示环境的空间并且该完全配置空间地图的每个元素包含相应的偏航配置集。每个偏航配置可以被归类为有效或无效，其中有效偏航配置表示在与相应元素相关联的空间处免于受到接触障碍物的危险的机器人的偏航配置，而无效偏航配置表示在与相应元素相关联的空间处不能免于受到接触障碍物的危险的机器人的偏航配置。该方法还可以包含从完全配置空间地图生成经压缩配置空间地图。该经压缩配置空间地图包含元素的第二二维网格，并且该第二网格的每个元素表示环境的空间。第二网格的每个元素还被分类为以下之一：(i)偏航碰撞区、(ii)偏航自由区或(iii)偏航约束区。在一些示例中，该方法包含从经压缩配置空间地图生成稀疏图。
可选地，规划从第一节点至第二节点的粗略路径包含从经压缩配置空间地图生成密集图。该密集图包含被分类为偏航自由区的元素。该方法还可以包含将来自稀疏图的边与来自密集图的元素相链接。在一些实施方式中，将边与来自密集图的元素相链接包含将稀疏图和密集图组合以生成最终图。在一些示例中，该方法还包含在最终涂上执行A*搜索算法。
在一些示例中，生成稀疏图还包含将多个沃罗诺伊(Voronoi)单元重叠在经压缩配置空间地图上，其中每个Voronoi单元在稀疏图上被分类为偏航约束区。每个Voronoi单元与被分类为偏航碰撞区的至少两个元素等距。可选地，生成稀疏图还包含将每个Voronoi单元归类为边或节点任一者。分类每个Voronoi单元可以包含执行洪水填充算法。
在一些实施方式中，规划从第一节点至第二节点的粗略路径包含修剪边，并且每个经修剪的边包含在阈值长度以下并且被分类为偏航碰撞区或偏航约束区任一者的元素。确定沿着粗略路径的图像传感器的视线丢失的点可以包含确定沿着规划的粗略路径的每个元素处的最小允许偏航和最大允许偏航，以及基于最小允许偏航和最大允许偏航确定最小包络。该方法还可以包含确定在粗略路径上的点处所需的偏航在最小包络之外。
在一些示例中，该方法还包含由数据处理硬件将具有高级路径点和至少一个中间路径点的导航路线发送到低级路径生成器。该方法还可以包含由数据处理硬件确定是否将至少一个中间路径点添加到导航路线，并且响应于确定不将该至少一个中间路径点添加到导航路线，由数据处理硬件将不变的导航路线传递到低级路径生成器。
本公开的另一方面提供了一种机器人，该机器人包含身体和耦接到身体并被配置为在环境中操纵该机器人的腿。该机器人还包含与腿相通信的数据处理硬件和与数据处理硬件相通信的存储器硬件。该存储器硬件存储指令，当在数据处理硬件上执行时，该些指令使得数据处理硬件执行操作。该些操作包含接收导航路线。该导航路线包含一系列高级路径点，该一系列高级路径点开始于起始位置处并结束于目的地位置处，并且基于高级导航数据。该高级导航数据表示在机器人要导航的区域中的静态障碍物的位置。该操作还包含从图像传感器接收机器人周围的环境的图像数据。该操作还包含基于该图像数据生成至少一个中间路径点。该操作还包含将该至少一个中间路径点添加到该导航路线的该一系列高级路径点，以及将机器人从起始位置沿着该一系列高级路径点和该至少一个中间路径点朝向目的地位置导航。
该方面可以包含以下可选特征中的一个或多个特征。在一些实施方式中，每个高级路径点和每个中间路径点包含两个坐标，该两个坐标指示平面上的位置、偏航值和时间值。该时间值指示对于机器人导航到相应路径点的估计的时间量。在一些示例中，该操作还包含维护该导航路线上的该一系列高级路径点中的每个高级路径点。该操作还可以包含接收身体障碍物地图。该身体障碍物地图包含机器人的身体不能穿越的障碍物的地图。附加地，生成至少一个中间路径点可以包含基于该身体障碍物地图生成稀疏图。该稀疏图包含一系列节点和边。该节点和边表示该机器人可以在环境中行进的路径。该操作还可以包含规划从来自一系列节点的第一节点至来自该一系列节点的第二节点的粗略路径。第一节点和第二节点各表示环境中的空间。该操作还可以包含确定沿着该粗略路径的图像传感器的视线丢失的点，并且在视线丢失的点处生成至少一个中间路径点之一。
在一些实施方式中，生成该稀疏图包含基于身体障碍物地图生成完全配置空间地图。该完全配置空间地图包含元素的二维网格，其中该网格的每个元素表示环境的空间并且该完全配置空间地图的每个元素包含相应的偏航配置集。每个偏航配置可以被归类为有效或无效，其中有效偏航配置表示在与相应元素相关联的空间处免受接触障碍物的危险的机器人的偏航配置，并且无效偏航配置表示在与相应元素相关联的空间处不能免受接触障碍物的危险的机器人的偏航配置。该操作还可以包含从完全配置空间地图生成经压缩配置空间地图。该经压缩配置空间地图包含元素的第二二维网格，并且该第二网格的每个元素表示环境的空间。第二网格的每个元素还被分类为以下之一：(i)偏航碰撞区、(ii)偏航自由区或(iii)偏航约束区。在一些示例中，该操作包含从经压缩配置空间地图生成稀疏图。
可选地，规划从第一节点至第二节点的粗略路径包含从经压缩配置空间地图生成密集图。该密集图包含被分类为偏航自由区的元素。该操作还可以包含将来自稀疏图的边与来自密集图的元素相链接。在一些实施方式中，将边与来自密集图的元素相链接包含将稀疏图和密集图组合以生成最终图。在一些示例中，该方法还包含在最终涂上执行A*搜索算法。
在一些示例中，生成稀疏图还包含将多个沃罗诺伊(Voronoi)单元重叠在经压缩配置空间地图上，其中每个Voronoi单元在稀疏图上被分类为偏航约束区。每个Voronoi单元与被分类为偏航碰撞区的至少两个元素等距。可选地，生成稀疏图还包含将每个Voronoi单元归类为边或节点任一者。分类每个Voronoi单元可以包含执行洪水填充算法。
在一些实施方式中，规划从第一节点至第二节点的粗略路径包含修剪边，并且每个经修剪的边包含在阈值长度以下并且被分类为偏航碰撞区或偏航约束区任一者的元素。确定沿着粗略路径的图像传感器的视线丢失的点可以包含确定沿着规划的粗略路径的每个元素处的最小允许偏航和最大允许偏航，以及基于最小允许偏航和最大允许偏航确定最小包络。该操作还可以包含确定在粗略路径上的点处所需的偏航在最小包络之外。
在一些示例中，该操作还包含将具有高级路径点和至少一个中间路径点的导航路线发送到低级路径生成器。该操作还可以包含确定是否将至少一个中间路径点添加到导航路线，并且响应于确定不将该至少一个中间路径点添加到导航路线，将不变的导航路线传递到低级路径生成器。
在附图和以下描述中阐述了本公开的一个或多个实施方式的细节。从说明书和附图以及权利要求中，其他方面、特征和优点将是显而易见的。
附图说明
图1是对于机器人生成中间路径点的导航系统的示例系统的示意图。
图2A和图2B是机器人使用高级路径点对导航路线进行导航的示意图。
图3是机器人使用高级路径点和中间路径点导航图2A和图2B的导航路线的示意图。
图4是图1的导航系统的示例中间路径点生成器的示意图。
图5是经压缩配置空间地图的示意图。
图6是图5的配置空间地图与Voronoi单元重叠的示意图。
图7是图6的Voronoi单元的示意图，示出了元素之间的距离和Voronoi单元的最近障碍物。
图8A-图8E是填充图6的Voronoi单元的洪水填充算法的示意图。
图9是从图6的Voronoi单元导出的边和节点的示意图。
图10是从图6的Voronoi单元导出的经修剪的边和节点的示意图。
图11A和图11B是二维稀疏图(图11A)和SE2稀疏图(图11B)的示意图。
图12A和图12B是对于目标目的地的添加的节点的示意图。
图13是穿过偏航自由区和偏航约束区的路径的示意图。
图14是穿过偏航约束区的路径的示意图。
图15A和图15B是机器人的导航路线的示意图，该导航路线包含放置在视线丢失位置的中间路径点。
图16是用于生成机器人的导航系统的中间路径点的示例方法的流程图。
图17是可以用于实施本文所描述的系统和方法的示例计算设备的示意图。
不同附图中相同的参考符号表示相同的元素。
具体实施方式
随着有腿机器人设备(也称为“机器人”)变得更加盛行，越来越需要机器人自主地在许多方面受限的环境中导航。通常，机器人依赖于存储与大型和/或静态物体(例如，墙壁、门等)相关的信息的高级地图数据。当给定目的地目标时，机器人将通常首先从这个高级地图中绘制路径或道路来导航静态障碍物，然后依赖于收集低级导航数据的感知系统以绕过行进中遇到的小型且动态物体进行导航。通常，在这类环境导航时，机器人会遇到高级地图中没有说明，但对于低级系统来说太大无法导航绕过的障碍物。在这些情况下，机器人变得被卡住或被困并不少见。本文的实施方式针对用于中间路径点生成器的系统和方法，该中间路径点生成器用于实时生成到高级路线的中间路径点，从而允许有腿机器人设备有效地绕过更大的动态物体导航。
参考图1，机器人或机器人设备10包含具有两条或更多条腿12的身体11，并执行导航系统100，用于使机器人10能够在受约束的环境8中导航。每条腿12耦接到主体11，并且可以具有由腿关节18分离的上部分14和下部分16。每条腿12的下部分16终止于脚19。每条腿的脚19是可选的，并且一条或多条腿12的下部分的终端(terminal end)可以耦接到轮子上，或者每条腿12的末端(distal end)可以直接接触地面9。机器人10具有沿着重力方向垂直的重力轴Vg和质心CM，质心CM是机器人10的分布质量的加权相对位置在其处总和为零的点。机器人10还具有基于相对于垂直重力轴Vg的CM(即，相对于重力的固定参考系)的姿势P，以限定由机器人10作出的特定姿态(attitude)或站姿(stance)。机器人10的姿态可以由机器人10在空间中的方位或角位置来限定。腿12相对于身体11的运动改变了机器人10的姿势P(即，机器人的CM的位置和机器人10的姿态或方位的组合)。
在一些实施方式中，机器人10还包含一个或多个附件，例如设置在身体11上并被配置为相对于身体11移动的铰接臂20。铰接臂20可以具有五个或更多的自由度。此外，铰接臂20可以互换地被称为操纵器臂或简单地称为附件。在所示的示例中，铰接臂20包含两个部分22、24，这两个部分可以相对于彼此以及身体11旋转；然而，铰接臂20可以在不脱离本公开的范围的情况下包含更多或更少的部分。第一部分22可以通过铰接臂关节26与第二部分24分开。可以互换地称为操纵器头28的端效应器28可以耦接到铰接臂20的第二部分24的末端，并且可以包含用于抓握/抓取物体的一个或多个致动器29。
机器人10还包含具有至少一个成像传感器或相机31的视觉系统30，每个传感器或相机31以视角32并在视场34内捕获机器人10周围环境8的图像数据或传感器数据17。视觉系统30可以被配置为通过调整视角32或者通过(独立地或经由机器人10任一者)平移和/或倾斜相机31来移动视场34，以在任何方向上移动视场34。替代地，视觉系统30可以包含多个传感器或相机31，从而视觉系统30环绕捕获机器人10的大致360度的视场。
在一些实施方式中，视觉系统30的一个或多个相机31包含一个或多个立体相机(例如，一个或多个RGBD立体相机)。在其他示例中，视觉系统30包含一个或多个雷达传感器，例如扫描光检测和测距(LIDAR)传感器、或扫描激光检测和测距(LADAR)传感器、光扫描仪、飞行时间传感器、或任何其他三维(3D)体积图像传感器(或任何这样的传感器组合)。在一些实施方式中，导航系统100包含感知系统102，其接收并处理传感器数据17，并将处理后的传感器数据17传递到中间路径点生成器120和低级路径生成器130。
视觉系统30向机器人10的数据处理硬件36提供图像数据或传感器数据17，该图像数据或传感器数据17从由相机或传感器31捕获的图像数据中导出。数据处理硬件36与存储器硬件38进行数字通信，并且在一些实施方式中，数据处理硬件36可以是远程系统。该远程系统可以是单个计算机、多个计算机或具有可扩展/弹性计算资源和/或存储资源的分布式系统(例如，云环境)。机器人10的导航系统100在数据处理硬件36上执行。
在所示的示例中，导航系统100包含高级路径点生成器110，其接收地图数据50(即，表示机器人10要导航的区域中的静态障碍物的位置的高级导航数据)并为导航路线112生成一个或多个高级路径点210(图2A和2B)，导航路线112绘制了从机器人10的当前位置到目标目的地的绕过大型的和/或静态障碍物的粗略路径。例如，高级路径点生成器110可以在大于10米的尺度上(例如，距离机器人10大于10米的距离)产生粗略路径。导航系统100还包含中间路径点生成器120，其从视觉系统30接收导航路线112和图像或传感器数据17，并且包含中间路径点生成器120。基于传感器数据17，中间路径点生成器120可以将一个或多个中间路径点310(图3)添加到导航路线112的高级路径点210(图2A、图2B和图3)，其形成机器人10行进的粗略路径或轨迹。导航路线112的高级路径点210和任何添加的中间路径点310被传递到低级路径生成器130，低级路径生成器130与传感器数据17相结合地生成绘制机器人10的每个单独步骤的步骤规划142，以从机器人10的当前位置导航到下一路径点210、310。使用步骤规划142，机器人10通过将脚19或腿12的末端放置在由步骤规划142指示的位置处的地面9上来遵循步骤规划142，从而操纵穿过环境8。在一些实施方式中，低级路径生成器130通过使用势场方法来提供更低级障碍物避免，以避免大约四米尺度的障碍物。该势场方法可以通过对朝向目标的速度和障碍物避免速度的总和进行集成来“推动”机器人10远离障碍物。
在一些实施方式中，导航系统100的至少一部分在与机器人10通信的远程设备上执行。例如，高级路径点生成器110可以在远程设备上执行以生成一个或多个高级路径点210，并且在机器人10上执行的中间路径点生成器120可以从远程设备接收高级路径点210。可选地，整个导航系统100可以在远程设备上执行，并且远程设备可以基于步骤规划142控制/指示机器人10操纵环境8。
现在参考图2A和图2B，低级路径生成器130(使用，例如，势场方法)在导航特定形状和/或凸起的障碍物时可能会遇到问题。例如，低级路径生成器130在试图导航到对应的导航路线112的高级路径点210时，可能滑下障碍物或表面220并卡在局部最小值230中(图2A)。在另一示例中，低级路径生成器130可能缺乏关于使机器人10转向的必要上下文(context)或决策制定能力。也就是说，低级路径生成器130可能难以区分何时“转向然后行驶”与“行驶然后转向”(图2B)。
现在参考图3，将附加路径点(即，中间路径点310)添加到导航路线112有助于低级路径生成器130作出恰当的拓扑决策，因为附加的一个或多个路径点310可以使轨迹对低级路径生成器130呈现凸形，并且允许低级路径生成器成功地绕过障碍物220导航。中间路径点生成器120可以确保添加到导航路线112的任何添加的中间路径点310离机器人10有足够的距离，以最小化地图抖动的影响。此外，中间路径点生成器120可以避免移除或删除任何高级路径点210，因为高级路径点生成器110可以知道对于中间路径点生成器120不可用的附加地图上下文，以及移除高级路径点210可能产生不可预测的结果。
现在参考图4，在一些实施方式中，中间路径点生成器120包含稀疏图生成器410、粗略路径规划器420和路径点放置器430。稀疏图生成器410从例如感知系统102接收身体障碍物地图412。身体障碍物地图412是机器人10的紧邻处(例如，四米内)的障碍物(例如，机器人10的身体11不能穿越的障碍物)的地图。稀疏图生成器410从身体障碍物地图412生成稀疏图416S。如下文更详细讨论的，稀疏图416S提供了节点812(图8A-图8E)之间的一系列有效互连和边810(图8A-图8E)。节点812和边810表示穿过机器人10附近的偏航约束区(即，困难或严格操纵的区域)的有效潜在路径，并且因此稀疏图416S提供了确定机器人10穿过偏航约束区的潜在路径所需的信息。
稀疏图生成器410将稀疏图416S传递到粗略路径规划器420。粗略路径规划器420使用稀疏图416S绘制从起始位置到目标目的地的粗略路径1310(图13)。在一些示例中，粗略路径规划器420通过使用搜索算法(例如，A*)来绘制粗略路径1310，以确定由稀疏图416S指示的有效潜在路径(即，一系列节点812之间的互连和边810)的最佳路线。粗略路径规划器420可以将路径1310传递到路径点放置器430。路径点放置器430根据机器人10的当前位置确定当沿着路径1310行进时视线丢失的位置，并将中间路径点放置在该位置。也就是说，如果机器人10从当前位置沿着粗略路径1310看，路径点放置器确定其中机器人10将丢失路径的视线(例如，因为障碍物)的位置，并将中间路径点310放置在路径1310上视线丢失的位置。中间路径点310将引导机器人10到低级路径生成器130能够成功地导航障碍物的位置。中间路径点310包含在导航路线112中，并被传递到低级路径生成器130。
在一些实施方式中，稀疏图生成器410最初基于接收到的身体障碍物地图412来生成完全配置空间地图414。在一些示例中，完全配置空间地图414包含元素510、510a–n的二维(2D)网格或阵列，其中每个元素510表示环境8的区域(例如，3厘米乘3厘米的平方)，其指示障碍物是否阻止机器人10进入特定元素510。可选地，完全配置空间地图414是128个元素乘128个元素的阵列。在一些示例中，每个元素510可以与多个相应的偏航配置512、512a–n(相应的偏航配置集512、512a–n)相关联，并且完全配置空间地图414可以指示每个元素510的每个相应的偏航配置512的状态。例如，每个元素510可以与64个相应偏航配置相关联。在该示例中，每个偏航配置将从先前配置旋转5.625度，因为360度(即，整圆)除以64(即，偏航配置的数量)等于5.625度。对于与相应元素510相关联的每个相应偏航配置512，完全配置空间地图414可以指示如果机器人10的选择点占据由元素510表示的空间，相应偏航配置512是否将导致与身体障碍物的碰撞。也就是说，完全配置空间地图414可以指示每个偏航配置512是有效的(即，机器人10在该偏航配置512中不会与障碍物碰撞)还是无效的(即，机器人10在该偏航配置512中会与障碍物碰撞)。选择点可以例如包含机器人10的身体11的中心点(例如，与每条腿12的顶部等距)。
在一些实施方式中，稀疏图生成器410从完全配置空间地图414生成经压缩配置空间地图500。经压缩配置空间地图500可以对配置空间地图500的每个元素510进行分类，而不是将每个元素与多个偏航配置512相关联。例如，每个元素510可以被分类为身体障碍物元素510A(图5)、偏航碰撞元素510B(图5)、偏航自由元素510C(图5)或偏航约束元素510D(图5)。也就是说，来自完全配置空间地图414的偏航配置512可以用于对经压缩配置空间地图500的每个元素510进行分类。
现在参考图5，示出了示例性经压缩配置空间地图500。在该示例中，经压缩配置空间地图500包含128乘128个元素510的网格，每个元素被分类为身体障碍物元素510、偏航碰撞元素510B、偏航自由元素510C或偏航约束元素510D。身体障碍物元素510A表示机器人10不能穿越的障碍物(即，从身体障碍地图412接收的障碍物)占据的元素。例如，机器人10必须避免的椅子、箱子或墙壁可以被分类为身体障碍物元素510A。偏航碰撞元素510B是其中当机器人10的选择点(例如，身体11的中心)占据由元素510B表示的空间时，机器人10的所有偏航配置512(例如，所有64个偏航配置)导致与身体障碍物(即，身体障碍物元素510A)碰撞的元素。例如，紧邻墙壁的空间，尽管实际上不含有墙壁，但对于机器人10可以太靠近墙壁以至于无法站立而不与墙壁碰撞。
偏航自由元素510C与偏航碰撞元素510B相反，因为没有偏航配置512将导致与身体障碍物的碰撞。换句话说，偏航自由元素510C表示环境8中机器人10可以旋转穿过所有偏航配置512(即，以在选择点处的轴心旋转360度)而不与身体障碍物碰撞的区域。偏航约束元素510D是其中一些偏航配置512是安全的或有效的(即，机器人10不会与障碍物碰撞)，而一些偏航配置512是不安全的(即，无效的偏航配置512，其中机器人10在那些偏航配置512中将与障碍物碰撞)的元素。例如，机器人10可以能够靠近并平行于墙壁行进，但是转向90度可能导致与墙壁碰撞。在该示例中，一些偏航配置512(即，机器人10平行于墙壁的偏航配置512)是安全的，而其他(即，机器人10垂直于墙壁的偏航配置512)是不安全的。
在一些示例中，稀疏图生成器410确定穿过经压缩配置空间地图500的偏航约束区510DZ(即，偏航约束元素510D的区域)的有效路径。现在参考图6，在一些实施方式中，稀疏图生成器410用多个Voronoi单元610重叠到经压缩配置空间地图500。Voronoi单元610包含偏航约束区510DZ和/或偏航自由区510CZ中的所有元素510，这些元素与被分类为偏航碰撞元素510B的至少两个元素510等距。换句话说，Voronoi单元610是离偏航碰撞区510BZ最远(因此离身体障碍物最远)的元素510。替代地，Voronoi单元610包含偏航约束区510DZ和/或偏航自由区510CZ中的所有元素510，这些元素与至少两个身体障碍物元素510A等距。在图6的示例中，单元610位于偏航碰撞区510BZ之间的偏航自由区510CZ和偏航约束区510DZ的中心。Voronoi单元610易于根据机器人10可以已经访问的数据(例如，有符号的距离场)来计算。
为了确定被标记为Voronoi单元610的元素510，稀疏图生成器410确定(配置空间地图500的)与配置空间地图500上的障碍物(即，身体障碍物元素510A)等距的元素510。也就是说，每个元素510固有地具有到最近障碍物边界的距离和方向。图7描绘了配置空间地图500的一部分，包含由偏航约束区510DZ分开的两个偏航碰撞区510BZ。一些Voronoi单元610穿过偏航约束区510DZ并在偏航碰撞区510BZ之间。在一些示例中，稀疏图生成器分析配置空间地图500的每个元素510，以确定元素510是否应该被标记为Voronoi单元610。当分析每个元素510以确定元素510是否是Voronoi单元610时，在一些实施方式中，稀疏图生成器410确定元素510(即，当前正在被分析的元素510)和相邻元素510是否指向基本不同的位置作为最近障碍物边界。也就是说，对于配置空间地图500中的每个元素510，稀疏图生成器410可以定位到相应元素的最近障碍物边界、相应元素的底部相邻的最近障碍物边界以及相应元素的右侧相邻的最近障碍物边界。每当三个最近障碍物边界中的任何两个之间的距离满足阈值距离时，元素510可以被标记为Voronoi单元610。阈值距离可以被表示为任意数量的元素(例如，一个元素、两个元素、五个元素等)。
在所示的示例中，当稀疏图生成器410分析被标为“A”的元素510时，稀疏图生成器410确定与元素“A”最近偏航碰撞元素510B(或身体障碍物元素510A)是元素510a。稀疏图生成器410然后确定与元素(标为“B”)的右侧相邻最近偏航碰撞元素510B，其在这种情况下是元素510b。稀疏图生成器410然后可以确定从元素的底部相邻(标为“C”)到最近偏航碰撞元素510B(在这种情况下，也是元素510a)的距离。在一些示例中，稀疏图生成器410可以确定三个最近障碍物边界中的两个(即，“A”和“B”之间、“A”和“C”之间以及“B”和“C”之间的三个距离中的两个)是否在相距阈值距离内。当元素具有相距相同距离的两个障碍物边界时，稀疏图生成器410可以确定两个元素之间的距离。
在该示例中，“A”和“B”的最近障碍物边界之间的距离是十个元素，“A”和“C”的最近障碍物边界之间的距离是零个元素(即它们共享相同的最近障碍物边界)，并且“B”和“C”的最近障碍物边界之间的距离也是十个元素。当阈值距离小于十个元素时，元素“A”将被标记为Voronoi单元610。
如前所讨论的，稀疏图生成器410可以为配置空间地图500的每个元素进行类似的分析。继续参考图7，稀疏图生成器410可以不将元素“D”标记为Voronoi单元610，因为与其右侧相邻(“E”)和底部相邻(“F”)的三个最近障碍物距离不满足阈值(例如，三个元素)。这是因为最近障碍物边界(即，元素510c、510d)之间的距离仅仅是一个元素，这可能不满足阈值。
现在参考图8A-图8E，在一些实施方式中，稀疏图生成器410确定从Voronoi单元610导出的边810和节点812。图8A示出了在偏航约束区510DZ中的示例性Voronoi单元610。在一些实施方式中，稀疏图生成器选择被标记为Voronoi单元610的任意(即，随机或接近随机)元素510ff。从任意元素510ff起始，稀疏图生成器执行洪水填充，并记录从被标记为Voronoi单元610的每个元素510到任意选择的元素510ff的距离。在所示的示例中，每个元素都用距任意元素510ff的距离(以元素为单位)来标记。洪水填充是一种确定连接到阵列中给定节点的区域的算法。在该情况下，洪水填充继续流过被标记为Voronoi单元610的所有元素510，直到所有元素都被分配了距离。虽然可以完全随机地选择任意选择的元素510ff，但是限制对在机器人10附近的元素510的选择可以是有利的，以便最小化来自任何误差的影响。
在被标记为Voronoi单元610的每个元素被分配了距离之后，在一些示例中，稀疏图生成器410确定Voronoi单元610的每个分支的端或端节点812。每个分支的端节点812将与任意选择的元素510ff具有局部最大的距离。在一些示例中，稀疏图生成器410从分支的端节点812开始标记每个元素510，同时朝向选择的元素510ff往回行进。每当稀疏图生成器410遇到先前已经被标记的元素510时，该生成器可以将唯一的标签附加到元素的组合。例如，在图8B中，稀疏图生成器410起始于端节点812a处，并朝着选择的元素510ff往回行进，沿途标记每个元素以形成边810a。也就是说，从端节点812a到选择的元素510ff的Voronoi单元610可以形成边810a。稀疏图生成器410可以继续该过程，直到所有元素都已被标记。例如，在图8C中，稀疏图生成器410从端节点812b向元素510ff行进，并标记每个元素以形成另一个边810b，直到在812c遇到先前标记的元素(图8B)。稀疏图生成器410可以在812c处为连接点(junction)元素(即，遇到的先前已经标记的第一个元素)分配唯一的标签。稀疏图生成器410可以继续往回行进，直到到达选择的元素510ff处，注意先前被标记为分开的边810c的每个元素。
现在参考图8D，稀疏图生成器410可以从端节点812d起始，并往回行进到元素510ff，再次标记沿途的每个元素以形成另一个边810d。在所有元素510都已被标记(并被分配给边810)之后，在一些实施方式中，稀疏图生成器410确定选择的元素510ff是否仅接触两个边810(即，不是三个或更多个边之间的连接点)。在这种情形下，稀疏图生成器410可以将两个边组合成单个边。例如，如图8D所示，选择的元素510ff仅接触两个其他边(即，边810c和边810d)，并且在图8E中，边810c和边810d被组合成单个边810。洪水填充和元素标记的最终结果向稀疏图生成器410提供了沿着边810的元素510的有序集和一系列节点元素812。一系列节点和边形成稀疏图416S，并表示机器人10可以行进穿过附近环境的约束空间(即，经压缩配置空间地图500的偏航约束区510DZ)的有效路径。
图9示出了配置空间地图500，其重叠有分类为多个边810和节点812的Voronoi单元610，每个边810连接到另一个边810(通过节点812)或者到偏航自由区510CZ(也通过节点812)任一者。在一些实施方式中，当生成稀疏图416S时，稀疏图生成器410仅考虑被标记为位于偏航约束区510DZ中的Voronoi单元610的元素510，因为穿过偏航自由区510DZ的路径可以在稍后确定。如参考图8A-图8E所讨论的，稀疏图生成器410可以将被标记为Voronoi单元610的元素分割成单独的边810和节点812。在一些示例中，稀疏图生成器410标记或识别在其处边810连接到偏航自由区510CZ的节点812。也就是说，稀疏图生成器410识别沿着连接偏航自由区510CZ和偏航约束区510DZ的Voronoi单元610的节点812(即，端或边810或边810之间的连接点)。稀疏图生成器410还可以识别是多个边810的连接点的节点812。在一些示例中，稀疏图生成器410假设连接到同一偏航自由区510CZ的所有节点812彼此连接。也就是说，只要节点812之间存在路径(即，连接到同一偏航自由区510CZ)，稀疏图生成器就可以(至少暂时)忽略穿过偏航自由区510CZ的运动。拥有边810和节点812，稀疏图生成器410可以首先基于与Voronoi单元610重叠的经压缩配置空间地图500中先前确定的边810和节点812，通过修剪掉不具有导航显著性的边810，生成最终2D配置地图1000(图10)。例如，图10示出了经压缩配置空间地图500，其覆盖有多个Voronoi单元610，并且具有被修剪以生成最终2D配置地图1000的多个不显著的边1010。也就是说，在一些实施方式中，稀疏图生成器410修剪比阈值长度更短并且终止或结束于偏航约束区域510DZ内的不显著的边1010，因为这些路径极不可能值得机器人10穿越。可选地，阈值长度可以大约是机器人10的半径。在一些示例中，当在修剪之后，连接点节点812连接到少于三个边810时，稀疏图生成器410将边810组合在一起。
现在参考图11A和图11B，在一些实施方式中，稀疏图生成器410将最终2D配置地图1000(图11A)转换成该图的SE2表示1100(图11B)。SE2是坐标系，其包含具有标准笛卡尔坐标的偏航(即x坐标、y坐标和偏航)。也就是说，SE2图1100采用最终2D配置地图1000，并且包含偏航。图11B示出了SE2图1100，其中偏航是高度。虽然机器人10可以具有任意数量的偏航配置512(例如，如前所讨论的64)，但是可以通过仅考虑两个偏航配置——向前和向后来简化SE2图1100。也就是说，通常，机器人10将在与其行进路径对齐的偏航配置512中行进，因此，通过仅考虑这两种偏航配置就可以极大地简化SE2图1100。2D地图1000的每个边810可以由两个具有相反切向(即，“向前”和“向后”偏航配置)1110a、1110b的SE2边表示。每个2D节点812(图11A)由连接到2D地图1000表示中的节点812的数量的两倍数量的边1110(图11B)表示。例如，图11A示出了在单个节点812处连接的三个边810，这转化为SE2图1100中的六个节点1112。这意味着机器人10将在节点1112处原地旋转，并且稀疏图生成器410可以基于来自完全配置空间地图414的有效偏航配置512来确定节点1112之间的互连。
为了最终确定SE2地图1100，在一些实施方式中，稀疏图生成器410从地图1100中为机器人10确定入口点和出口点。现在参考图12A和图12B，稀疏图生成器410可以沿着直线将地图外目标1210(即，目标目的地)投影到地图1100边界。当目标1210被设置在偏航自由区510CZ中时，稀疏图生成器410可以使用与目标1210相关联的相应元素。然而，当在偏航约束区510DZ中时，稀疏图生成器410可以沿着被标记为Voronoi单元610(来自2D地图1000)或偏航自由区510CZ边界的最近元素510进行搜索。如果最近元素在偏航自由区510CZ边界上，稀疏图生成器410可以将该元素设置为目标。当最近元素在边缘810上被标记为Voronoi单元610时，稀疏图生成器410可以通过在相应最近元素处放置新的节点1220来将边810一分为二。在图12A所示的示例中，目标1210被设置在偏航约束区510DZ中。稀疏图生成器确定最近期望元素是Voronoi单元610。稀疏图生成器410在最接近目标1210的元素处创建新的节点1220，并将先前的边810分成两个独立的边810。在一些实施方式中，稀疏图生成器410创建两个新的节点1220，其中一个节点1220表示向前偏航配置512，一个节点1220表示向后偏航配置512。
一旦已放置了新的节点1220，稀疏图生成器410确定机器人10的起始位置(例如，机器人的当前位置)是否连接向前偏航配置节点1220、向后偏航配置节点1220或两者。也就是说，稀疏图生成器410确定机器人10是否能够连接到具有相应的偏航配置的节点1220。在一些示例中，稀疏图生成器410确定原始或真实目标1210和沿着新的节点1220的边810的两个偏航配置(即，向前和向后)之间的角度1222。在图12B所示的示例中，当角度满足阈值时(例如，当角度在区域1230内时)，面向前方的节点1220连接到机器人的位置。当角度满足第二阈值时(例如，当角度在区域1240内时)，面向后方的节点1220连接到机器人的位置。当角度满足第三阈值时(例如，当角度在区域1250内时)，面向前方的节点1220和面向后方的节点1220都连接到机器人的起始位置。也就是说，机器人10可以向前或向后任一者行进到节点1220的位置。
在一些示例中，稀疏图生成器410连接指示机器人10将与障碍物碰撞的节点812。例如，稀疏图生成器410可以总是假设机器人通过从中心点旋转而转向，这可能使得一些转向是不可能的。然而，在一些情况下，低级路径生成器130仍然能够通过打开不在机器人10中心处的枢轴点来导航路径，并且在这些情况下，稀疏图生成器410可以在节点812之间创建边810，否则生成器120可以确定机器人不能穿越这些边。
返回参考图4，中间路径点生成器120还包含粗略路径规划器420，其被配置为从稀疏图生成器410接收稀疏图416S，并确定机器人10行进以到达目标1210(即，对应于目标目的地的节点1220(图12A))的拓扑正确路径(即，粗略路径1310)。在一些实施方式中，粗略路径规划器420还接收完全配置空间地图414和/或经压缩配置空间地图500。现在参考图4和图13，地图1100包含粗略路径1310，该粗略路径1310从偏航自由区510CZ中的起始点1320导航，穿过偏航约束区510DZ到达另一个偏航区自由510CZ。
为了生成路径1310，粗略路径规划器420可以实施搜索算法(例如，A*搜索算法)。粗略路径规划器420可以使用搜索算法来搜索2D偏航自由区510CZ的密集网格或图416D，以绘制路径1310。稀疏图生成器410还可以生成密集图416D，并将其与稀疏图416S组合，并将组合图发送给粗略路径规划器420。或者，粗略路径规划器可以生成该密集图416D。密集图是根据经压缩配置空间地图500确定的偏航自由区510CZ的互连节点的列表。也就是说，像稀疏图416S包含偏航约束区510DZ内的元素510的互连节点812的列表一样，密集图416D包含偏航自由区510DZ内的元素510的互连节点的列表。因为偏航自由区不需要方位(即，偏航)信息(因为机器人10可以在偏航自由区域510CZ中自由旋转)，所以粗略路径规划器420可以搜索密集图416D(相对于稀疏图416S密集)。粗略路径规划器420可以组合稀疏图416S和密集图416D以形成最终图416F。最终图416F包含偏航自由区510CZ和偏航约束区510DZ两者内的所有互连节点。粗略路径规划器420还可以使用搜索算法来搜索最终图416F，以寻找具有包含的方位信息的偏航约束区510DZ和偏航自由区510CZ中的Voronoi单元610。粗略路径规划器420可以将偏航自由区510CZ与偏航约束区510DZ链接起来，并且用粗略路径1310横穿偏航约束区510DZ。
因为密集图416D缺少方位信息(并且因此最终图416F缺少偏航自由区510CZ中的方位信息)，所以在一些实施方式中，粗略路径规划器420确定任何边810的任何方位(即，向前或向后)是否应该反转。可选地，粗略路径规划器420被偏置以沿着边810面向前方行走。粗略路径规划器420可以识别路径1310的能够使偏航方向反转的段(即，向前和向后方向两者都有效)。粗略路径规划器420然后可以计算穿越路径1310的成本(即，所需的旋转量)。
例如，现在参考图14的地图1100，粗略路径规划器420已经规划了从起始位置1410(具有与相应箭头对齐的方位)到目标位置1420(具有与相应箭头对齐的方向)的路径1430。由于向前偏置，搜索算法可以选择穿过偏航约束区510DZ的面向前方的方位(路径A-C)。粗略路径规划器420可选地计算路径A-C(面向前方)和路径B-D(面向后方)的成本。在给定的示例中，因为给定的起始和目标方位面向后方，所以B-D的向后的路径比面向前方的路径A-C更便宜(即，需要更少的旋转)，并且粗略路径规划器420可以相应地更新路径1430。
返回参考图4，在一些实施方式中，中间路径点生成器120还包含路径点放置器430。路径点放置器430从粗略路径规划器420接收完全配置空间地图414和具有路径1310的稀疏图416S。路径点放置器430处理路径1310以寻找合适的位置来放置中间路径点310。在一些示例中，路径点放置器430沿着路径1310搜索，直到视线首次丢失(例如，因为障碍物)，并将路径点310放置在该位置。可选地，路径点放置器430在搜索之前对路径1310进行下采样，以减少处理时间。
现在参考图15A，机器人10沿着路径1310导航穿过位于两个身体障碍物区510AZ之间的偏航约束区510DZ。路径点放置器430将射线1510从机器人10的当前位置吸引到沿着路径1310的各个点。当射线1510之一与身体障碍物区510的一部分相交时(或者，替代地，在身体障碍物区510的阈值距离内，以考虑机器人10的宽度)，路径点放置器430将中间路径点310放置在路径1310上射线1510与路径1310相交或就在视线丢失之前的点1530处。因此，在笛卡尔坐标(即x和y坐标)中确定视线丢失的位置相对简单。然而，确定SE2空间中的视线(即包含偏航)更为复杂。
参考图15B，为了解决所包含的偏航，路径点放置器430可以在沿着下采样路径1310的每个点处确定最小允许偏航和最大允许偏航，以生成包络1550、1550a–n。在一些示例中，路径点放置器430在每个下采样点处跟踪最小(即，最里面)的包络1560、1560a–n，并且当包络宽度下降到包络阈值以下或者在路径1310上的点1530处所需偏航配置在包络1550之外任一者时，放置中间路径点310。在所示的示例中，包络1550c的偏航在内包络1560c之外，并且是中间路径点310的候选。
在一些示例中，如果方位改变超过阈值量(例如，60度)，则当从偏航自由区510CZ移动到偏航约束区510DZ时，路径点放置器430还添加中间路径点310。可选地，当目标处的方位(即，目标姿势)偏离当前地图(即，离机器人的当前位置太远)并且到目标的视线丢失时，路径点放置器430可以在路径1310的端处添加中间路径点310。附加地，路径点放置器430可以远离狭窄空间中的连接点移动路径点。例如，中间路径点310可以向下投影到路径1310直到环绕连接点的阈值半径之外。
高级路径点210可以包括指示平面上的位置的两个坐标(即，x和y坐标)、偏航值和时间值。时间值可以指示机器人导航到相应路径点310的估计的时间量。除了x、y和偏航值，路径点放置器430可以类似地将估计的时间值添加到中间路径点310。可以通过考虑从起始位置到x、y中的路径点的最大时间量和使用接收到的任何速度限制的偏航来确定估计的时间值。路径点放置器430可以在中间路径点310之后的规划的轨迹上将对于每个高级路径点210的时间偏移。
返回参考图4，路径点放置器430将任何中间路径点310添加到导航路线112的高级路径点210。中间路径点生成器将导航路线112传递到低级路径生成器130，以生成导航到每个路径点210、310的步骤规划142。在中间路径点生成器120确定中间路径点310不是必要的(或者未能找到适当的位置)的情况下，中间路径点生成器120可以将接收到的导航路线112原封不动地传递到低级路径生成器130。
图16是用于为机器人10生成中间路径点310的方法1600的示例性操作安排的流程图。在操作1602，方法1600包含在机器人10的数据处理硬件36处接收导航路线112。导航路线112包含一系列高级路径点210，该一系列高级路径点210开始于起始位置113处并结束于目的地位置114处。导航路线112基于高级导航数据50，高级导航数据50表示机器人10要导航的区域中的静态障碍物的位置。
方法1600包含在操作1604，在数据处理硬件36处从图像传感器31接收机器人10周围的环境8的图像数据17。在操作1606，方法1600包括由数据处理硬件36基于图像数据17生成至少一个中间路径点310，并且在操作1608，由数据处理硬件36将至少一个中间路径点310添加到该导航路线112的该一系列高级路径点210。在操作1610，方法1600包括由数据处理硬件36将机器人10从起始位置113沿着该一系列高级路径点210和该至少一个中间路径点310朝向目的地位置114导航。
图17是可以用于实施本文档中所描述的系统和方法的示例计算设备1700(例如，数据处理硬件36和存储器硬件20)的示意图。这里所示的组件、它们的连接和关系以及它们的功能仅仅意味着是示例性的，并不意味着限制本文档中所描述和/或要求保护的发明的实施方式。
计算设备1700包含处理器1710(例如，数据处理硬件36)、存储器1720(例如，存储器硬件38)、存储设备1730、连接到存储器1720和高速扩展端口1750的高速接口/控制器1740、以及连接到低速总线1770和存储设备1730的低速接口/控制器1760。组件1710、1720、1730、1740、1750和1760中的每一个使用各种总线互连，并且可以安装在公共主板上或者以其他适当的方式安装。处理器1710(例如，数据处理硬件)可以处理用于在计算设备1700内执行的指令，包括存储在存储器1720中或存储设备1730上的指令，以在外部输入/输出设备上显示图形用户界面(GUI)的图形信息，例如耦接到高速接口1740的显示器1780。在其他实施方式中，可以酌情使用多个处理器和/或多条总线，以及多个存储器和多种类型的存储器。此外，可以连接多个计算设备1700，每个设备提供必要操作的部分(例如，作为服务器组、一组刀片式服务器或多处理器系统)。处理器1710可以执行图1和4的中间路径点生成器120。
存储器1720在计算设备1700内非暂时地存储信息。存储器1720可以是计算机可读介质、易失性存储单元或非易失性存储单元。非暂时性存储器1720可以是用于临时或永久存储程序(例如，指令序列)或数据(例如，程序状态信息)以供计算设备1700使用的物理设备。非易失性存储器的示例包含但不限于闪存和只读存储器(ROM)/可编程只读存储器(PROM)/可擦除可编程只读存储器(EPROM)/电可擦除可编程只读存储器(EEPROM)(例如，通常用于固件，例如引导程序)。易失性存储器的示例包含但不限于随机存取存储器(RAM)、动态随机存取存储器(DRAM)、静态随机存取存储器(SRAM)、相变存储器(PCM)以及磁盘或磁带。
存储设备1730能够为计算设备1700提供大量存储。在一些实施方式中，存储设备1730是计算机可读介质。在各种不同的实施方式中，存储设备1730可以是软盘设备、硬盘设备、光盘设备或磁带设备、闪存或其他类似的固态存储器设备，或者设备阵列，包含存储区域网络或其他配置中的设备。在附加的实施方式中，计算机程序产品有形地体现在信息载体中。该计算机程序产品含有指令，当被执行时，该些指令执行一个或多个方法，例如以上所描述的那些方法。该信息载体是计算机可读或机器可读介质，例如存储器1720、存储设备1730或处理器1710上的存储器。
高速控制器1740管理计算设备1700的带宽密集型操作，而低速控制器1760管理较低带宽密集型操作。这样的职责分配只是示范性的。在一些实施方式中，高速控制器1740耦接到存储器1720和高速扩展端口1750，高速扩展端口1750可以接受各种扩展卡(未示出)。在一些实施方式中，低速控制器1760耦接到存储设备1730和低速扩展端口1790。可以包含各种通信端口(例如，通用串行总线、蓝牙、以太网、无线以太网)的低速扩展端口1790可以例如通过网络适配器耦接到一个或多个输入/输出设备，例如键盘、定点设备、扫描仪或网络设备，例如交换机或路由器。
本文所描述的系统和技术的各种实施方式可以在数字电子和/或光学电路、集成电路、专门设计的专用集成电路(ASIC)、计算机硬件、固件、软件和/或其组合中实现。这些各种实施方式可以包含在可编程系统上可执行和/或可解释的一个或多个计算机程序中的实施方式，该可编程系统包含至少一个可编程处理器，该可编程处理器可以是专用或通用的，被耦接以从存储系统、至少一个输入设备和至少一个输出设备接收数据和指令，并将数据和指令发送到该存储系统、该至少一个输入设备和该至少一个输出设备。
这些计算机程序(也称为程序、软件、软件应用或代码)包含用于可编程处理器的机器指令，并且可以以高级过程和/或面向对象的编程语言和/或汇编/机器语言来实施。如本文所使用的，术语“机器可读介质”和“计算机可读介质”指的是用于向可编程处理器提供机器指令和/或数据的任何计算机程序产品、非暂时性计算机可读介质、装置和/或设备(例如，磁盘、光盘、存储器、可编程逻辑器件(PLD))，包含接收机器指令作为机器可读信号的机器可读介质。术语“机器可读信号”是指用于向可编程处理器提供机器指令和/或数据的任何信号。
本说明书中所描述的过程和逻辑流程可以由一个或多个可编程处理器(也称为数据处理硬件)来执行，该处理器执行一个或多个计算机程序以通过对输入数据进行操作并生成输出来执行功能。这些过程和逻辑流程也可以由专用逻辑电路例如现场可编程门阵列(FPGA)或专用集成电路(ASIC)来执行。举例来说，适合于执行计算机程序的处理器包含通用和专用微处理器两者，以及任何类型的数字计算机的任何一个或多个处理器。通常，处理器将从只读存储器或随机存取存储器或两者接收指令和数据。计算机的基本元件是用于执行指令的处理器和用于存储指令和数据的一个或多个存储设备。通常，计算机还将包含或可操作地耦接以从用于存储数据的一个或多个大容量存储设备(例如磁盘、磁光盘或光盘)接收数据或向其传送数据，或两者兼有。然而，计算机不需要有这样的设备。适于存储计算机程序指令和数据的计算机可读介质包含所有形式的非易失性存储器、介质和存储设备，包含，举例来说，半导体存储器设备，例如EPROM、EEPROM和闪存设备；磁盘，例如内部硬盘或可移动磁盘；磁光盘；以及CD ROM和DVD-ROM。处理器和存储器可以由专用逻辑电路来补充或结合在其中。
已经描述了多个实施方式。然而，应当理解，在不脱离本公开的精神和范围的情况下，可以进行各种修改。因此，其他实施方式在以下权利要求的范围内。

Claims (28)

1.一种方法(1600)，包括：
在机器人(10)的数据处理硬件(36)处接收导航路线(112)，所述导航路线(112)包括一系列高级路径点(210)，所述一系列高级路径点(210)开始于起始位置(113)处并结束于目的地位置(114)处，并且所述导航路线(112)基于表示所述机器人(10)要导航的区域中的静态障碍物的位置的高级导航数据(50)；
在所述数据处理硬件(36)处，从图像传感器(31)接收所述机器人(10)周围的环境(8)的图像数据(17)；
由所述数据处理硬件(36)基于所述图像数据(17)生成至少一个中间路径点(310)；
由所述数据处理硬件(36)将所述至少一个中间路径点(310)添加到所述导航路线(112)的所述一系列高级路径点(210)；以及
由所述数据处理硬件(36)将所述机器人(10)从所述起始位置(113)沿着所述一系列高级路径点(210)和所述至少一个中间路径点(310)朝向所述目的地位置(114)导航。
2.根据权利要求1所述的方法(1600)，其中，每个高级路径点(210)和每个中间路径点(310)包括指示平面上的位置的两个坐标、偏航值和时间值，所述时间值指示所述机器人(10)导航到相应路径点(210，310)的估计时间量。
3.根据权利要求1-3中任一项所述的方法(1600)，还包括由所述数据处理硬件(36)维护所述导航路线(112)上的所述一系列高级路径点(210)中的每一个。
4.根据权利要求1-4中任一项所述的方法(1600)，还包括在所述数据处理硬件(36)处接收身体障碍物地图(412)，所述身体障碍物地图(412)包括所述机器人(12)的身体(11)不能穿越的障碍物的地图，以及
其中，生成所述至少一个中间路径点(210)包括：
基于所述身体障碍物地图(412)生成稀疏图(416S)，所述稀疏图(416S)包括一系列节点(812)和边(810)，所述节点(812)和边(810)表示所述机器人(10)可以在所述环境(8)中行进的路径；
规划从来自所述一系列节点(812)中的第一节点(812)到来自所述一系列节点(812)中的第二节点(812)的粗略路径(1310)，所述第一节点(812)和所述第二节点(812)各自表示所述环境(8)中的空间；
确定沿着所述粗略路径(1310)的图像传感器(31)的视线丢失的点(1530)；以及
在所述视线丢失的点(1530)处生成所述至少一个中间路径点(310)之一。
5.根据权利要求4所述的方法(1600)，其中，生成所述稀疏图(416S)包括：
基于所述身体障碍物地图(412)生成完全配置空间地图(414)，所述完全配置空间地图(414)包括元素(510)的二维网格，所述网格的每个元素(510)表示所述环境(8)的空间，并且所述完全配置空间地图(414)的每个元素(510)包括相应的偏航配置(512)集，每个偏航配置(512)被分类为有效或无效，其中，有效偏航配置(512)表示在与相应元素(510)相关联的空间处免于受到接触障碍物的危险的所述机器人(10)的偏航配置(512)，而无效偏航配置(512)表示在与相应元素(510)相关联的空间处不能免于受到接触障碍物的危险的所述机器人(10)的偏航配置(512)；
从所述完全配置空间地图(414)生成经压缩配置空间地图(500)，所述经压缩配置空间地图(500)包括元素(510)的第二二维网格，并且第二网格的每个元素(510)表示所述环境(8)的空间，并且所述第二网格的每个元素(510)被分类为以下之一：(i)偏航碰撞区(510BZ)、(ii)偏航自由区(510CZ)或(iii)偏航约束区(510DZ)；以及
从所述经压缩配置空间地图(500)生成所述稀疏图(416)。
6.根据权利要求5所述的方法(1600)，其中，规划从所述第一节点(812)到所述第二节点(812)的粗略路径(1310)包括：
从所述经压缩配置空间地图(500)生成密集图(416D)，所述密集图(416D)包括被分类为偏航自由区(510CZ)的元素(510)；以及
将来自所述稀疏图(416S)的边(810)与来自所述密集图(416D)的元素(510)相链接。
7.根据权利要求6所述的方法(1600)，其中，将所述边(810)与来自所述密集图(416D)的元素(510)相链接包括：
组合所述稀疏图(416S)和所述密集图(416D)以生成最终图(416F)；以及
在所述最终图(416F)上执行A*搜索算法。
8.根据权利要求5所述的方法(1600)，其中，生成所述稀疏图(416)还包括将多个沃罗诺伊(Voronoi)单元(610)重叠到所述经压缩配置空间地图(500)上，每个Voronoi单元(610)在所述稀疏图(416)上被分类为偏航约束区(510DZ)，并且每个Voronoi单元(610)与被分类为偏航碰撞区(510BZ)的至少两个元素(510)等距。
9.根据权利要求8所述的方法(1600)，其中，生成所述稀疏图(416S)还包括将每个Voronoi单元(610)分类为边(810)或节点(812)任一者。
10.根据权利要求9所述的方法，其中，分类每个Voronoi单元(610)包括执行洪水填充算法。
11.根据权利要求5所述的方法(1600)，其中，规划从所述第一节点(812)到所述第二节点(812)的所述粗略路径(1310)包括修剪边(810)，每个经修剪的边(1010)包括阈值长度以下并且被分类为偏航碰撞区(510BZ)或偏航约束区(510DZ)任一者的元素(510)。
12.根据权利要求4所述的方法(1600)，其中，确定沿着所述粗略路径(1310)的图像传感器(31)的视线丢失的点(1530)包括：
确定沿着规划的粗略路径(1310)的每个元素(510)处的最小允许偏航和最大允许偏航(1550)；
基于所述最小允许偏航和所述最大容许偏航确定最小包络(1560)；以及
确定所述粗略路径(1310)上的点(1530)处的所需偏航在所述最小包络(1560)之外。
13.根据权利要求1-12中任一项所述的方法(1600)，还包括由所述数据处理硬件(36)将具有所述高级路径点(210)和所述至少一个中间路径点(310)的所述导航路线(112)发送到低级路径生成器(130)。
14.根据权利要求13所述的方法(1600)，还包括：
由所述数据处理硬件(36)确定是否将所述至少一个中间路径点(310)添加到所述导航路线(112)；以及
响应于确定不将所述至少一个中间路径点(310)添加到所述导航路线(112)，由所述数据处理硬件(36)将导航路线(112)不变地传递到所述低级路径生成器(130)。
15.一种机器人(10)，包括：
身体(11)；
腿(12)，所述腿(12)耦接到所述身体(11)并被配置为在环境(8)周围操纵所述机器人(10)；
数据处理硬件(36)，所述处理硬件(36)与所述腿(12)通信；以及
存储器硬件(38)，所述存储器硬件(38)与所述数据处理硬件(36)通信，所述存储器硬件(38)存储指令，当在所述数据处理硬件(36)上执行时，所述指令使得数据处理硬件(36)执行包括以下操作的操作：
接收导航路线(112)，所述导航路线(112)包括开始于起始位置(113)处并结束于目的地位置(114)处的一系列高级路径点(210)，并且所述导航路线(112)基于表示所述机器人(10)要导航的区域中的静态障碍物的位置的高级导航数据(50)；
从图像传感器(31)接收所述机器人(10)周围的环境(8)的图像数据(17)；
基于所述图像数据(17)生成至少一个中间路径点(310)；
将所述至少一个中间路径点(310)添加到所述导航路线(112)的所述一系列高级路径点(210)；以及
将所述机器人(10)从所述起始位置(113)沿着所述一系列高级路径点(210)和所述至少一个中间路径点(310)朝向所述目的地位置(114)导航。
16.根据权利要求15所述的机器人(10)，其中，每个高级路径点(210)和每个中间路径点(310)包括指示平面上的位置的两个坐标、偏航值和时间值，所述时间值指示所述机器人(10)导航到相应路径点(210，310)的估计的时间量。
17.根据权利要求15或16所述的机器人(10)，还包括维护所述导航路线(112)上的所述一系列高级路径点(210)中的每一个。
18.根据权利要求15-17中任一项所述的机器人(10)，还包括接收身体障碍物地图(412)，所述身体障碍物地图(412)包括所述机器人(12)的身体(11)不能穿越的障碍物的地图，以及
其中，生成所述至少一个中间路径点(210)包括：
基于所述身体障碍物地图(412)生成稀疏图(416S)，所述稀疏图(416S)包括一系列节点(812)和边(810)，所述节点(812)和边(810)表示所述机器人(10)可以在所述环境(8)中行进的路径；
规划从来自所述一系列节点(812)中的第一节点(812)到来自所述一系列节点(812)中的第二节点(812)的粗略路径(1310)，所述第一节点(812)和所述第二节点(812)各自表示所述环境(8)中的空间；
确定沿着所述粗略路径(1310)的图像传感器(31)的视线丢失的点(1530)；以及
在所述视线丢失的点(1530)处生成所述至少一个中间路径点(310)之一。
19.根据权利要求18所述的机器人(10)，其中，生成所述稀疏图(416S)包括：
基于所述身体障碍物地图(412)生成完全配置空间地图(414)，所述完全配置空间地图(414)包括元素(510)的二维网格，所述网格的每个元素(510)表示所述环境(8)的空间，并且所述完全配置空间地图(414)的每个元素(510)包括相应的偏航配置(512)集，每个偏航配置(512)被分类为有效或无效，其中，有效偏航配置(512)表示在与相应元素(510)相关联的空间处免于受到接触障碍物的危险的所述机器人(10)的偏航配置(512)，而无效偏航配置(512)表示在与相应元素(510)相关联的空间处不能免于受到接触障碍物的危险的所述机器人(10)的偏航配置(512)；
从所述完全配置空间地图(414)生成经压缩配置空间地图(500)，所述经压缩配置空间地图(500)包括元素(510)的第二二维网格，并且第二网格的每个元素(510)表示所述环境(8)的空间，并且所述第二网格的每个元素(510)被分类为以下之一：(i)偏航碰撞区(510BZ)、(ii)偏航自由区(510CZ)或(iii)偏航约束区(510DZ)；以及
从所述经压缩配置空间地图(500)生成所述稀疏图(416)。
20.根据权利要求19所述的机器人(10)，其中，规划从所述第一节点(812)到所述第二节点(812)的粗略路径(1310)包括：
从所述经压缩配置空间地图(500)生成密集图(416D)，所述密集图(416D)包括被分类为偏航自由区(510CZ)的元素(510)；以及
将来自所述稀疏图(416S)的边(810)与来自所述密集图(416D)的元素(510)相链接。
21.根据权利要求20所述的机器人(10)，其中，将所述边(810)与来自所述密集图(416D)的元素(510)相链接包括：
组合所述稀疏图(416S)和所述密集图(416D)以生成最终图(416F)；以及
在所述最终图(416F)上执行A*搜索算法。
22.根据权利要求19所述的机器人(10)，其中，生成所述稀疏图(416)还包括将多个沃罗诺伊(Voronoi)单元(610)重叠到所述经压缩配置空间地图(500)上，每个Voronoi单元(610)在所述稀疏图(416)上被分类为偏航约束区(510DZ)，并且每个Voronoi单元(610)与被分类为偏航碰撞区(510BZ)的至少两个元素(510)等距。
23.根据权利要求22所述的机器人(10)，其中生成所述稀疏图(416S)还包括将每个Voronoi单元(610)分类为边(810)或节点(812)任一者。
24.根据权利要求23所述的机器人(10)，其中，分类每个Voronoi单元(610)包括执行洪水填充算法。
25.根据权利要求19所述的机器人(10)，其中，规划从所述第一节点(812)到所述第二节点(812)的所述粗略路径(1310)包括修剪边(810)，每个经修剪的边(1010)包括阈值长度以下并且被分类为偏航碰撞区(510BZ)或偏航约束区(510DZ)任一者的元素(510)。
26.根据权利要求18所述的机器人(10)，其中，确定沿着所述粗略路径(1310)的图像传感器(31)的视线丢失的点(1530)包括：
确定沿着规划的粗略路径(1310)的每个元素(510)处的最小允许偏航和最大允许偏航(1550)；
基于所述最小允许偏航和所述最大容许偏航确定最小包络(1560)；以及
确定所述粗略路径(1310)上的点(1530)处的所需偏航在所述最小包络(1560)之外。
27.根据权利要求15-26中任一项所述的机器人(10)，还包括将具有所述高级路径点(210)和所述至少一个中间路径点(310)的所述导航路线(112)发送到低级路径生成器(130)。
28.根据权利要求27所述的机器人(10)，还包括：
确定是否将所述至少一个中间路径点(310)添加到所述导航路线(112)；以及
响应于确定不将所述至少一个中间路径点(310)添加到所述导航路线(112)，将所述导航路线(112)不变地传递到所述低级路径生成器(130)。
CN201980098897.7A 2019-08-06 2019-09-13 中间路径点生成器 Pending CN114174766A (zh)

Applications Claiming Priority (3)

Application Number Priority Date Filing Date Title
US201962883438P 2019-08-06 2019-08-06
US62/883,438 2019-08-06
PCT/US2019/051092 WO2021025707A1 (en) 2019-08-06 2019-09-13 Intermediate waypoint generator

Publications (1)

Publication Number Publication Date
CN114174766A true CN114174766A (zh) 2022-03-11

Family

ID=74501887

Family Applications (1)

Application Number Title Priority Date Filing Date
CN201980098897.7A Pending CN114174766A (zh) 2019-08-06 2019-09-13 中间路径点生成器

Country Status (6)

Country Link
US (3) US11268816B2 (zh)
EP (1) EP4010659A1 (zh)
JP (1) JP7502409B2 (zh)
KR (1) KR20220078563A (zh)
CN (1) CN114174766A (zh)
WO (1) WO2021025707A1 (zh)

Families Citing this family (15)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US11747825B2 (en) 2018-10-12 2023-09-05 Boston Dynamics, Inc. Autonomous map traversal with waypoint matching
US11548151B2 (en) * 2019-04-12 2023-01-10 Boston Dynamics, Inc. Robotically negotiating stairs
JP7502409B2 (ja) 2019-08-06 2024-06-18 ボストン ダイナミクス，インコーポレイテッド 中間ウェイポイント生成器
US20230022637A1 (en) * 2019-11-28 2023-01-26 Sony Group Corporation Information processing apparatus, information processing method, and program
US11712802B2 (en) * 2020-04-20 2023-08-01 Boston Dynamics, Inc. Construction constrained motion primitives from robot maps
US11927961B2 (en) 2020-04-20 2024-03-12 Boston Dynamics, Inc. Constrained robot autonomy language
US11720108B2 (en) * 2020-12-22 2023-08-08 Baidu Usa Llc Natural language based indoor autonomous navigation
US20220388170A1 (en) * 2021-06-04 2022-12-08 Boston Dynamics, Inc. Alternate Route Finding for Waypoint-based Navigation Maps
US20220390950A1 (en) * 2021-06-04 2022-12-08 Boston Dynamics, Inc. Directed exploration for navigation in dynamic environments
WO2023140928A1 (en) 2022-01-21 2023-07-27 Boston Dynamics, Inc. Systems and methods for recording robot missions
CN114577217B (zh) * 2022-05-05 2022-07-29 季华实验室 基于冯洛诺伊图的路径规划方法、装置、设备及存储介质
CN117724467A (zh) * 2022-09-08 2024-03-19 华为云计算技术有限公司 一种路径规划方法、相关装置及系统
US20240176348A1 (en) * 2022-11-30 2024-05-30 Earthsense Inc. System and method for autonomous navigation of a field robot
KR102706517B1 (ko) * 2023-08-08 2024-09-12 네이버 주식회사 로봇의 내비게이션 목적지 보정 방법 및 시스템
CN117705115B (zh) * 2023-12-11 2024-06-25 中国南方航空股份有限公司 基于标签法的航路规划方法、装置、存储介质及终端设备

Citations (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2006239844A (ja) * 2005-03-04 2006-09-14 Sony Corp 障害物回避装置、障害物回避方法及び障害物回避プログラム並びに移動型ロボット装置
CN104536445A (zh) * 2014-12-19 2015-04-22 深圳先进技术研究院 移动导航方法和系统
US9586316B1 (en) * 2015-09-15 2017-03-07 Google Inc. Determination of robotic step path
US20180051991A1 (en) * 2016-08-17 2018-02-22 Sharp Laboratories Of America, Inc. Lazier graph-based path planning for autonomous navigation
CN108801269A (zh) * 2018-08-29 2018-11-13 山东大学 一种室内云机器人导航系统及方法
CN109029417A (zh) * 2018-05-21 2018-12-18 南京航空航天大学 基于混合视觉里程计和多尺度地图的无人机slam方法
CN109540142A (zh) * 2018-11-27 2019-03-29 达闼科技（北京）有限公司 一种机器人定位导航的方法、装置、计算设备
US20190187703A1 (en) * 2017-12-19 2019-06-20 X Development Llc Semantic Obstacle Recognition For Path Planning

Family Cites Families (56)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5111401A (en) * 1990-05-19 1992-05-05 The United States Of America As Represented By The Secretary Of The Navy Navigational control system for an autonomous vehicle
JP3467136B2 (ja) 1995-11-07 2003-11-17 富士重工業株式会社 自律走行車の走行制御装置
JP3994950B2 (ja) 2003-09-19 2007-10-24 ソニー株式会社 環境認識装置及び方法、経路計画装置及び方法、並びにロボット装置
US20050216182A1 (en) 2004-03-24 2005-09-29 Hussain Talib S Vehicle routing and path planning
JP4479372B2 (ja) 2004-06-25 2010-06-09 ソニー株式会社 環境地図作成方法、環境地図作成装置、及び移動型ロボット装置
US7444237B2 (en) 2005-01-26 2008-10-28 Fujitsu Limited Planning a journey that includes waypoints
WO2007051972A1 (en) 2005-10-31 2007-05-10 Qinetiq Limited Navigation system
US20070282564A1 (en) * 2005-12-06 2007-12-06 Microvision, Inc. Spatially aware mobile projection
US8326469B2 (en) * 2006-07-14 2012-12-04 Irobot Corporation Autonomous behaviors for a remote vehicle
US8843244B2 (en) * 2006-10-06 2014-09-23 Irobot Corporation Autonomous behaviors for a remove vehicle
US20100066587A1 (en) 2006-07-14 2010-03-18 Brian Masao Yamauchi Method and System for Controlling a Remote Vehicle
CA2602879A1 (en) 2006-09-14 2008-03-14 University Of South Florida System and method for real-time travel path prediction and automatic incident alerts
JP2008072963A (ja) 2006-09-21 2008-04-03 Yanmar Co Ltd 農用作業車
US8346391B1 (en) * 2006-12-28 2013-01-01 Science Applications International Corporation Methods and systems for an autonomous robotic platform
US8930058B1 (en) 2008-10-20 2015-01-06 The United States Of America As Represented By The Secretary Of The Navy System and method for controlling a vehicle traveling along a path
KR101581197B1 (ko) 2009-01-06 2015-12-30 삼성전자주식회사 로봇 및 그 제어방법
IL200921A (en) * 2009-09-14 2016-05-31 Israel Aerospace Ind Ltd A robotic carry system for infantry and useful methods for the above purpose
US9014848B2 (en) 2010-05-20 2015-04-21 Irobot Corporation Mobile robot system
US9400503B2 (en) * 2010-05-20 2016-07-26 Irobot Corporation Mobile human interface robot
US9330567B2 (en) * 2011-11-16 2016-05-03 Autoconnect Holdings Llc Etiquette suggestion
KR101772977B1 (ko) 2010-10-07 2017-08-31 삼성전자주식회사 이동 로봇 및 그 지도 작성 방법
US9146558B2 (en) 2010-11-30 2015-09-29 Irobot Corporation Mobile robot and method of operating thereof
US9323250B2 (en) 2011-01-28 2016-04-26 Intouch Technologies, Inc. Time-dependent navigation of telepresence robots
US9463574B2 (en) 2012-03-01 2016-10-11 Irobot Corporation Mobile inspection robot
JP2013250795A (ja) 2012-05-31 2013-12-12 Aisin Seiki Co Ltd 移動体誘導装置及び移動体誘導方法
JP5886502B2 (ja) 2012-12-20 2016-03-16 トヨタ自動車株式会社 移動体制御装置、移動体制御方法及び制御プログラム
US9483055B2 (en) 2012-12-28 2016-11-01 Irobot Corporation Autonomous coverage robot
US8849494B1 (en) * 2013-03-15 2014-09-30 Google Inc. Data selection by an autonomous vehicle for trajectory modification
CN203371557U (zh) 2013-07-19 2014-01-01 上海化学工业区公共管廊有限公司 机器人视频系统
EP2933604B1 (en) 2014-04-14 2016-11-30 Softbank Robotics Europe A method for localizing a robot in a localization plane
JP2016081404A (ja) * 2014-10-21 2016-05-16 株式会社日立製作所 自律移動装置
US9352470B1 (en) 2014-11-11 2016-05-31 Google Inc. Yaw slip handling in a robotic device
JP6481347B2 (ja) 2014-11-28 2019-03-13 村田機械株式会社 移動量推定装置、自律移動体、及び移動量の推定方法
US9717387B1 (en) 2015-02-26 2017-08-01 Brain Corporation Apparatus and methods for programming and training of robotic household appliances
WO2017090108A1 (ja) 2015-11-25 2017-06-01 株式会社日立製作所 棚配置システム、搬送ロボット及び棚配置方法
US20170165835A1 (en) * 2015-12-09 2017-06-15 Qualcomm Incorporated Rapidly-exploring randomizing feedback-based motion planning
US9868210B1 (en) 2015-12-30 2018-01-16 Google Inc. Methods and systems for planning a body position of a robotic device
CN108885436B (zh) 2016-01-15 2021-12-14 美国iRobot公司 自主监视机器人系统
JP6492024B2 (ja) * 2016-03-30 2019-03-27 株式会社豊田中央研究所 移動体
US9933781B1 (en) * 2016-11-23 2018-04-03 Denso International America, Inc. Data-driven planning for automated driving
US10296012B2 (en) 2016-12-21 2019-05-21 X Development Llc Pre-computation of kinematically feasible roadmaps
JP6982999B2 (ja) * 2017-07-20 2021-12-17 株式会社Ｉｈｉエアロスペース 経路決定装置と経路決定方法
DE102017214746A1 (de) 2017-08-23 2019-02-28 Neusoft Technology Solutions Gmbh Verfahren zur Erzeugung alternativer Routenvorschläge
US10754339B2 (en) 2017-09-11 2020-08-25 Baidu Usa Llc Dynamic programming and quadratic programming based decision and planning for autonomous driving vehicles
CN108052103B (zh) 2017-12-13 2020-12-04 中国矿业大学 基于深度惯性里程计的巡检机器人地下空间同时定位和地图构建方法
WO2019126332A1 (en) 2017-12-19 2019-06-27 Carnegie Mellon University Intelligent cleaning robot
CA3096857A1 (en) * 2018-04-12 2019-10-17 Uber Technologies, Inc. Autonomous vehicle control using service pools across different service entities
US11747825B2 (en) 2018-10-12 2023-09-05 Boston Dynamics, Inc. Autonomous map traversal with waypoint matching
JP7502409B2 (ja) 2019-08-06 2024-06-18 ボストン ダイナミクス，インコーポレイテッド 中間ウェイポイント生成器
CN211956515U (zh) 2020-04-30 2020-11-17 上海允登信息科技有限公司 一种数据中心it设备智能资产盘点系统
CN111604916B (zh) 2020-04-30 2024-04-02 杭州优云科技有限公司 一种机房it设备故障机柜u位定位系统及方法
CN112034861A (zh) 2020-09-15 2020-12-04 航天科工智能机器人有限责任公司 一种仿生自主机器人自主避障系统及其避障方法
US20220390954A1 (en) 2021-06-04 2022-12-08 Boston Dynamics, Inc. Topology Processing for Waypoint-based Navigation Maps
US20220390950A1 (en) 2021-06-04 2022-12-08 Boston Dynamics, Inc. Directed exploration for navigation in dynamic environments
US20220388170A1 (en) 2021-06-04 2022-12-08 Boston Dynamics, Inc. Alternate Route Finding for Waypoint-based Navigation Maps
CN113633219B (zh) 2021-07-23 2022-12-20 美智纵横科技有限责任公司 回充路径确定方法、装置、设备及计算机可读存储介质

Patent Citations (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2006239844A (ja) * 2005-03-04 2006-09-14 Sony Corp 障害物回避装置、障害物回避方法及び障害物回避プログラム並びに移動型ロボット装置
CN104536445A (zh) * 2014-12-19 2015-04-22 深圳先进技术研究院 移动导航方法和系统
US9586316B1 (en) * 2015-09-15 2017-03-07 Google Inc. Determination of robotic step path
US20180051991A1 (en) * 2016-08-17 2018-02-22 Sharp Laboratories Of America, Inc. Lazier graph-based path planning for autonomous navigation
US20190187703A1 (en) * 2017-12-19 2019-06-20 X Development Llc Semantic Obstacle Recognition For Path Planning
CN109029417A (zh) * 2018-05-21 2018-12-18 南京航空航天大学 基于混合视觉里程计和多尺度地图的无人机slam方法
CN108801269A (zh) * 2018-08-29 2018-11-13 山东大学 一种室内云机器人导航系统及方法
CN109540142A (zh) * 2018-11-27 2019-03-29 达闼科技（北京）有限公司 一种机器人定位导航的方法、装置、计算设备

Non-Patent Citations (4)

* Cited by examiner, † Cited by third party
Title
刘达才;刘治;: "未知环境下基于行为的移动机器人导航系统研究", 工业控制计算机, no. 12, 25 December 2017 (2017-12-25) *
孟伟, 黄庆成, 韩学东, 洪炳: "一种动态未知环境中自主机器人的导航方法", 计算机研究与发展, no. 09, 30 September 2005 (2005-09-30) *
宋彩云;王明磊;刘肖琳;: "基于环境模型的移动机器人路径规划", 电光与控制, no. 03, 30 June 2006 (2006-06-30) *
赵颖;孙群;陈兵旗;王书茂;: "基于机器视觉的非结构化道路导航路径检测方法", 农业机械学报, no. 06, 25 June 2007 (2007-06-25) *

Also Published As

Publication number Publication date
JP2022542807A (ja) 2022-10-07
KR20220078563A (ko) 2022-06-10
US20210041243A1 (en) 2021-02-11
WO2021025707A1 (en) 2021-02-11
EP4010659A1 (en) 2022-06-15
US11268816B2 (en) 2022-03-08
JP7502409B2 (ja) 2024-06-18
US20220155078A1 (en) 2022-05-19
US11774247B2 (en) 2023-10-03
US20230400307A1 (en) 2023-12-14

Similar Documents

Publication Publication Date Title
US11774247B2 (en) Intermediate waypoint generator
CN110262518B (zh) 基于轨迹拓扑地图和避障的车辆导航方法、系统及介质
US11747825B2 (en) Autonomous map traversal with waypoint matching
Sadat et al. Feature-rich path planning for robust navigation of MAVs with mono-SLAM
US20220388170A1 (en) Alternate Route Finding for Waypoint-based Navigation Maps
Jaspers et al. Multi-modal local terrain maps from vision and lidar
US11712802B2 (en) Construction constrained motion primitives from robot maps
WO2022256815A1 (en) Topology processing for waypoint-based navigation maps
US11598878B2 (en) Vision-cued random-access lidar system and method for localization and navigation
Fassbender et al. Landmark-based navigation in large-scale outdoor environments
US20220196410A1 (en) Vehicle navigation
US11865724B2 (en) Movement control method, mobile machine and non-transitory computer readable storage medium
Canh et al. Multisensor data fusion for reliable obstacle avoidance
Kushnir UGV Backtracking Recovery with Active Visual Landmarks-Based Navigation
US11927961B2 (en) Constrained robot autonomy language
Ferrin Autonomous Goal-Based Mapping and Navigation Using a Ground Robot
Lian et al. Traversable map construction and robust localization for unstructured road environments 1
Chaudhuri et al. A Novel Zone Segmentation (ZS) Method for Dynamic Obstacle Detection and Flawless Trajectory Navigation of Mobile Robot
Wu et al. Developing a dynamic obstacle avoidance system for autonomous mobile robots using Bayesian optimization and object tracking: Implementation and testing
Gujarathi et al. Aman Jain, Navid Panchi under the guidance of Dr. Ashwin Dhabale and
Lee et al. Consecutive Scanning Scheme: Application to Localization and Dynamic Obstacle Detection for a Mobile Robot
Matta et al. Development of an efficient perception system and a path planning algorithm for autonomous mobile robots

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination