Login| Sign Up| Help| Contact|

Patent Searching and Data


Title:
PATH PLANNING FOR ROBOT
Document Type and Number:
WIPO Patent Application WO/2019/201188
Kind Code:
A1
Abstract:
A path planning method for a robot, wherein: when a robot performs a traversal operation in an area, the robot must first travel along the boundary of the area and return to a starting point or an approximate point of the starting point (action 1), and when the robot travels along the boundary or around an independent obstacle, if it is detected at a point that there is a relatively independent closed area between a route along which the robot is traveling and a route along which the robot has traveled, this point is temporally marked as a point P, and the original traveling direction is marked as a direction q, and the robot first traverses this relatively independent area, then to the point P, and continues to travel in the direction q, and in a following traversing process, will no longer travel through this relatively independent area, but take a shortcut route or an approximate route along the edge of the area close to the inner circle, and during a following traversal operation starting from a point O, when encountering a large independent obstacle for the first time, where this point is temporally marked as a point A and the original traveling direction is marked as a direction OA, the robot will must go around a circle along the boundary of the obstacle and return to the point A or an approximate point of A (action 2), and then bypass the obstacle and travel to a point Z on the other side of the independent obstacle from the point A along the direction OA or a point that is away from the point Z of the obstacle by a parking place (action 3).

Inventors:
ZHANG SHUYI (CN)
Application Number:
PCT/CN2019/082586
Publication Date:
October 24, 2019
Filing Date:
April 14, 2019
Export Citation:
Click for automatic bibliography generation   Help
Assignee:
ZHANG SHUYI (CN)
International Classes:
G05D1/02; A47L11/24
Foreign References:
CN102092048A2011-06-15
CN106292697A2017-01-04
US20110166737A12011-07-07
CN103120573A2013-05-29
CN106805856A2017-06-09
CN107491069A2017-12-19
Download PDF:
Claims:
权利要求书

[权利要求 1] 当机器人在一片区域内遍历运行时, 必先沿区域的边界绕行一周并返 回起始点或起始点的近似点 (动作 i) , 当机器人在沿边界运行过程 或绕独立障碍物运行时, 检测到正在行走的路线与已经走过的路线之 间存在一个相对独立的封闭区域时, 此处暂记为 P点, 原本的行进方 向记为 q向, 首先遍历该相对独立的区域, 然后走至 P点, 继续沿 q向 运行, 在以后的遍历过程中, 不再走该相对独立的区域, 而是沿该区 域靠近内圈的边沿走简捷路线或近似路线, 在以后的遍历运行时从 0 点出发首次遇到大的独立障碍物时, 此处暂记为 A点, 原本的行进方 向记为 OA向, 也必沿障碍物的边界绕行一周并返 A点或 A的近似点 ( 动作 2) ,然后绕过障碍物, 行走至从 A点沿 OA延伸至独立障碍物的另 一面的 Z点或 Z点背离障碍物一个车位的点 (动作 3) 。

2. 根据权利要求 1所述的吸尘机器人的路径规划方法, 其特征在于: 在绕行完区域边界以后的遍历运行时如果从 0点出发, 首次遇到大的 独立障碍物时, 此处暂记为 A点, 原本的行进方向记为 OA向, 也必 沿障碍物的边界绕行一周并返 A点或 A的近似点 (动作 2) ,然后绕过 障碍物, 在执行动作 2的过程中, 如果检测到正在行走的路线与已经 走过的路线之间存在一个相对独立的封闭区域时, 优先遍历该相对独 立的区域, 然后继续绕行并返 A点或 A的近似点, 然后行走至从 A点 沿 OA延伸至独立障碍物的另一面的 Z点或 Z点背离障碍物一个车位的 点 (动作 3) 。

3 . 根据权利要求 2所述的吸尘机器人的局部路径规划方法, 其特征在 于: 动作 3是沿刚才从 A点至 Z点绕行的路线, 在障碍物右侧以简捷线 路行走至 Z点。

4. 根据权利要求 2所述的机器人的路径规划方法, 其特征在于: 动作 3是沿刚才从 A点至 Z点绕行的路线的近似路线, 行走至 Z点背离障碍 物一个车位的点。

5 . 根据权利要求 2所述的机器人的路径规划方法, 其特征在于: 动作 3是沿刚才从 A点至 Z点绕行的路线部分简捷路线、 部分近似路线, 行 走至 Z点或 Z点背离障碍物一个车位的点。

6. 根据权利要求 2所述的机器人的路径规划方法, 其特征在于: 动作 3是沿 Z点至 A点的路线的反方向以简捷线路在障碍物左侧行走至 Z点

7 . 根据权利要求 2所述的机器人的路径规划方法, 其特征在于: 在以 后从 0的右侧 n (n>=l) 个车位处再开始遍历运行时, 在第 m (m>l) 次遇到或将遇到已经绕行过的障碍物时, 可照权利要求 3、 4、 5的近 似路线任意一项执行。

8 . 根据权利要求 1所述的机器人的路径规划方法, 其特征在于: 在绕 行完区域边界以后的遍历运行时如果从 0点出发, 首次遇到大的独立 障碍物时, 此处暂记为 A点, 在 A点出发沿障碍物的边界绕行过程中

, 在某一转角点检测到正在行走的路线右侧不超过 2个车位的距离有 已经走过的非本次绕行障碍物的平行路线, 说明剩余的障碍物绕行路 线与已走过的路线之间存在一个相对独立的封闭区域 S1时, 此处暂记 为 P点, 正在的行进方向记为 q向, 沿 q向运行继续执行动作 2走至 A点 的近似点, 然后遍历该相对独立的区域 S1, 返回 P点背离障碍物一个 车位的点, 将该点看作 Z点, 方向调整为 q向的反方向, 走相邻一侧 已走过路线的近似路线。

9. 根据权利要求 1所述的机器人的路径规划方法, 其特征在于: 在绕 行完区域边界以后的遍历运行时如果从 0点出发, 首次遇到大的独立 障碍物时, 此处暂记为 A点, 在 A点出发沿障碍物的边界绕行过程中

, 在某一转角点检测到将要行走的路线右侧不超过 2个车位的距离有 已经走过的非本次绕行障碍物的平行路线, 说明剩余的障碍物绕行路 线与已走过的路线之间存在一个相对独立的封闭区域 S1时, 此处暂记 为 P点, 将要的行进方向记为 q向, 沿 q向运行继续执行动作 2走至 A点 的近似点, 然后遍历该相对独立的区域 S1, 遍历完 S1后, 返回 P点, 将该 P点看作 Z点, 方向调整为 q向反方向, 走相邻一侧已走过路线的 近似路线。

10. 根据权利要求 1所述的吸尘机器人的局部路径规划方法, 其特征 在于在第 n (n >=1) 次非处理独立障碍物的行走过程中, 检测到正在 行走的通道与已经走过的线路之间存在一个相对独立的封闭区域 S1时 , 此处暂记为 P点, 原本的行进方向记为 q向, 首先遍历该相对独立的 区域 S1, 遍历完 S1后, 返回 P点, 继续沿 q向运行

Description:
机器人的路径规划

技术领域

[0001] 本发明涉及一种机器人的路径规划, 主要涉及清洁机器人等类需在一个相对封 闭的区域内, 全部走遍的机器人的路径规划方式, 特别是在走遍过程中遇到大 的独立的障碍物时的路径规划。

背景技术

[0002] 在现有技术中, 清洁机器人在房间内移动的路径规划已有多种 方案, 如公开号 为 W00038025或 CN1365647A或 CN1463658A、 CN1129053C、 CN1287722C、 CN 102138769的发明专利申请说明书中描述的, 但无论何种方案, 均不能 100%走 遍一个任意形状的封闭的区域, 对一些形状较复杂的障碍物, 上述路径规划方 案都不能有效处理, 故目前所有这类追求遍历的路径规划中的例图 (包括专利 或者论文) 无一例外均采用简单障碍物的布置方式, 虽然似乎满足大多数房间 的遍历, 但对于办公场所等相对复杂一些区域, 5见有已公开的路径规划就不能 有效处理了。 5见有的智能机器人吸尘器产品中, 较为成功商业化量产的路径规 划导航系统有 Neato公司的 RPS Laser Mapping

System (RPS激光绘图系统) , Samsung公司的 Visionary Mapping System (幻影 绘图系统) , 以及 Evolution公司 NorthStar室内天体导航系统等等, 也都是基于简 单障碍物的路径规划, 都有各自的缺陷, 也都无法精确的实现 100%清洁覆盖率 。 而其余大部分产品均采用类似 iRobot公司的 iAdapt随机碰撞寻路系统, 包括 Ro omba在内的产品均无法避免清扫遗漏的问题。 依据“墨菲”定律, 如果差错有可 能发生, 那它就一定会发生。

发明概述

技术问题

[0003] 本发明的目的在于提供一种能有效的处理形状 复杂的障碍物的路径规划方案, 进而能 100%走遍任意形状、 任意复杂障碍物的封闭、 相对平坦的区域一称之 为“遍历”。 问题的解决方案

技术解决方案

[0004] 本发明是这样规划的: 当机器人在一片区域内遍历运行时, 必先沿区域的边界 绕行一周并返回起始点或起始点的近似点 (动作 1) , 当机器人在沿边界运行过 程或绕独立障碍物运行时, 检测到正在行走的路线与已经走过的路线之间 存在 一个相对独立的封闭区域时, 此处暂记为 P点, 原本的行进方向记为 q向, 首先 遍历该相对独立的区域, 然后走至 P点, 继续沿 q向运行, 在以后的遍历过程中 , 不再走进该相对独立的区域内。

[0005] 在以后的遍历运行时从 0点出发首次遇到大的独立障碍物时, 此处暂记为 A点

, 原本的行进方向记为 OA向, 也必沿障碍物的边界绕行一周并返 A点或 A的近似 点 (动作 2) ,然后绕过障碍物, 行走至从 A点沿 OA延伸至独立障碍物的另一面的 Z点或 Z点背离障碍物一个车位的点 (动作 3) 。

[0006] 动作 3是沿刚才从 A点至 Z点绕行的路线, 在障碍物右侧以简捷线路行走至 Z点

[0007] 动作 3是沿刚才从 A点至 Z点绕行的路线的近似路线, 行走至 Z点背离障碍物一 个车位的点。

[0008] 动作 3是沿刚才从 A点至 Z点绕行的路线部分简捷路线、 部分近似路线, 行走至 Z点或 Z点背离障碍物一个车位的点。

[0009] 动作 3是沿 Z点至 A点的路线的反方向以简捷线路在障碍物左侧 走至 Z点。

[0010] 在以后从 0的右侧 n (n>=l) 个车位处再开始遍历运行时, 在第 m (m>l) 次遇 到或将遇到已经绕行过的障碍物时, 可照上述动作 3任意一项路线的类似路线执 行。

[0011] 在绕行完区域边界以后的遍历运行时如果从 0点出发, 首次遇到大的独立障碍 物时, 此处暂记为 A点, 在 A点出发沿障碍物的边界绕行过程中, 在某一转角点 检测到正在行走的路线右侧不超过 2个车位的距离有已经走过的非本次绕行障碍 物的平行路线, 说明剩余的障碍物绕行路线与已走过的路线之 间存在一个相对 独立的封闭区域 S1时, 此处暂记为 P点, 正在的行进方向记为 q向, 沿 q向运行继 续执行动作 2走至 A点的近似点, 然后遍历该相对独立的区域 S1, 返回 P点背离障 碍物一个车位的点, 将该点看作 Z点, 方向调整为 q向的反方向, 走相邻一侧已 走过路线的近似路线。

[0012] 在绕行完区域边界以后的遍历运行时如果从 0点出发, 首次遇到大的独立障碍 物时, 此处暂记为 A点, 在 A点出发沿障碍物的边界绕行过程中, 在某一转角点 检测到将要行走的路线右侧不超过 2个车位的距离有已经走过的非本次绕行障碍 物的平行路线, 说明剩余的障碍物绕行路线与已走过的路线之 间存在一个相对 独立的封闭区域 S1时, 此处暂记为 P点, 将要的行进方向记为 q向, 沿 q向运行继 续执行动作 2走至 A点的近似点, 然后遍历该相对独立的区域 S1, 遍历完 S1后, 返回 P点, 将该 P点看作 Z点, 方向调整为 q向反方向, 走相邻一侧已走过路线的 近似路线。

[0013] 在第 n (n >=l) 次非处理独立障碍物的行走过程中, 检测到正在行走的通道与 已经走过的线路之间存在一个相对独立的封闭 区域 S1时, 此处暂记为 P点, 原本 的行进方向记为 q向, 首先遍历该相对独立的区域 S1, 遍历完 S1后, 返回 P点, 继续沿 q向运行。

发明的有益效果

有益效果

[0014] 本发明的实质在于将复杂的边界或障碍物处理 方法简单化, 一次性分片解决区 域性复杂问题。

对附图的简要说明

附图说明

[0015] 图 1~4为本发明对于部分相对封闭区域的定义示意 图。

[0016] 图 5 (a、 b、 c) 为对障碍物整体处理的方法示意图。

[0017] 图 6~7为完整遍历路径示例图。

发明实施例

实施例

[0018] 当机器人在一片区域内遍历运行时, 必先沿区域的边界绕行一周并返回起始点 或起始点的近似点 (动作 1) , 当机器人在沿边界运行过程或绕独立障碍物运 行 时, 检测到正在行走的路线与已经走过的路线 (绕行独立障碍物的路线及障碍 物外侧相邻的路线) 之间存在一个相对独立的封闭区域时, 此处暂记为 P点, 原 本的行进方向记为 q向, 首先遍历该相对独立的区域, 然后走至 P点, 继续沿 q向 运行, 在以后的遍历过程中, 不再走该相对独立的区域内, 如图 1。 如果需要经 过该区域, 可沿该区域靠近内圈的边沿走简捷路线或近似 路线。

[0019] 在绕行完区域边界以后的遍历运行时从 0点出发, 如果首次遇到大的独立障碍 物时, 此处暂记为 A点, 原本的行进方向记为 OA向, 也必沿障碍物的边界绕行 一周并返 A点或 A的近似点, (动作 2, 此处 A点的近似点指 OA方向 A点左手位置 不到一个车位距离的点) ,然后绕过障碍物, 在执行动作 2的过程中, 如果检测到 正在行走的路线与已经走过的路线之间存在一 个相对独立的封闭区域 S 1时, 优 先遍历该相对独立的区域 S1, 然后继续绕行并返 A点或 A的近似点, 然后行走至 从 A点沿 OA延伸至独立障碍物的另一面的 Z点或 Z点背离障碍物一个车位的点 ( 动作 3) ,如图 1 (a) 。

[0020] 动作 3是沿刚才从 A点至 Z点绕行的路线, 在障碍物右侧以简捷线路行走至 Z点

[0021] 动作 3是沿刚才从 A点至 Z点绕行的路线的近似路线, 行走至 Z点背离障碍物一 个车位的点。

[0022] 动作 3是沿刚才从 A点至 Z点绕行的路线部分简捷路线、 部分近似路线, 行走至 Z点或 Z点背离障碍物一个车位的点。 如图 2 (a) 中, G-H-I-J-K处路线比较曲折 , 可以以 HI的近似路线, 逐步将 G至 K处的行走路线与 FG拉直。

[0023] 动作 3是沿 Z点至 A点的路线的反方向以简捷线路在障碍物左侧 走至 Z点。

[0024] 在以后从 0的右侧 n (n>=l) 个车位处再开始遍历运行时, 在第 m (m>l) 次遇 到或将遇到已经绕行过的障碍物时, 可照上述动作 3任意一项路线的类似路线执 行。

[0025] 在绕行完区域边界以后的遍历运行时如果从 0点出发, 首次遇到大的独立障碍 物时, 此处暂记为 A点, 在 A点出发沿障碍物的边界绕行过程中, 在某一转角点 检测到正在行走的路线右侧不超过 2个车位的距离有已经走过的非本次绕行障碍 物的平行路线, 说明剩余的障碍物绕行路线与已走过的路线之 间存在一个相对 独立的封闭区域 SI时, 此处暂记为 P点, 正在的行进方向记为 q向, 沿 q向运行继 续执行动作 2走至 A点的近似点, 然后遍历该相对独立的区域 S1, 返回 P点背离障 碍物一个车位的点, 将该点看作 Z点, 方向调整为 q向的反方向, 继续走向下一 目标点, 也就是走相邻一侧已走过路线的近似路线, 如图 2 (a) 。

[0026] 在绕行完区域边界以后的遍历运行时如果从 0点出发, 首次遇到大的独立障碍 物时, 此处暂记为 A点, 在 A点出发沿障碍物的边界绕行过程中, 在某一转角点 检测到将要行走的路线右侧不超过 2个车位的距离有已经走过的非本次绕行障碍 物的平行路线, 说明剩余的障碍物绕行路线与已走过的路线之 间存在一个相对 独立的封闭区域 S1时, 此处暂记为 P点, 将要的行进方向记为 q向, 沿 q向运行继 续执行动作 2走至 A点的近似点, 然后遍历该相对独立的区域 S1, 遍历完 S1后, 返回 P点, 将该 P点看作 Z点, 方向调整为 q向反方向, 走相邻一侧已走过路线的 近似路线, 如图 2 (b) , 图中 P点为 F点、 图 3, P点为 E点。

[0027] 在第 n (n >=l) 次非处理独立障碍物的行走过程中, 检测到正在行走的通道与 已经走过的线路之间存在一个相对独立的封闭 区域 S1时, 此处暂记为 P点, 原本 的行进方向记为 q向, 首先遍历该相对独立的区域 S1, 遍历完 S1后, 返回 P点, 继续沿 q向运行, 如图 4。

[0028] 所谓边界: 针对一个封闭的相对平坦的区域的 (比如室内的墙和关闭的门) , 它同样适用于一片敞开的区域, 指指定设置的长度、 宽度所形成的一个长方形 区域, 长方形的边就是边界、 或者敞开的区域局部被一下障碍物所封闭, 那么 边界就是没有被封闭的长方形的边以及与没有 被封闭的长方形的边连在一起的 障碍物共同构成, 如果障碍物没有连在一起, 但障碍物之间的宽度小于一个机 器人的宽度 (机器人走不进去) , 那么也被认为是连在一起的障碍物, 障碍物 与长方形边界之间的宽度小于一个机器人的宽 度, 那么也被认为是长方形的边 界与障碍物连在一起了, 如果障碍物有两段与长方形边界连在一起或与 长方形 边界之间的宽度均小于一个机器人的宽度, 那么长方形的一部分就被障碍物封 闭了。

[0029] 可遍历区域不包括封闭在障碍物之内的, 或者机器人根本走不进去的区域, 对 于有落差的上升台阶 (超过机器人本身的跨越能力) 或者下降台阶或者悬空的 楼板边缘也被认为是障碍物或边界, 或者是机器人的传感器所检测到的边界, 比如垂下来的窗帘或掉落在地上的衣服袜子等 , 会被非接触型传感器检测到认 为是障碍物 (或边界) , 但如果是遇到比较硬的机器人接触型传感器, 会被机 器人推着走, 就不能算作障碍物 (或边界) , 对于机器人检测到或碰到的会移 动的比如人或动物或另外的机器人等, 机器人刚遇到并开始围绕运行时突然又 消失了, 这种情况可算作特例, 机器人可返回上一个检测点 (转弯点) 检测障 碍物是否存在, 如果不存在, 继续返回机器人可返回前一个检测点 (转弯点) 检测。

[0030] 所谓大的障碍物是指障碍物的长度或宽度达到 一个指定的值 (比如一个机器人 的宽度, 由程序预先设定) , 如果机器人遇到的不是大的障碍物, 作为特例 ( 比如椅子腿) , 机器人可不遵循本发明的规则, 直接绕过即可, 当然也可依据 大的障碍物绕行一圈的规则。

[0031] 所谓独立障碍物是指障碍物每条边与边界之间 至少有一个机器人宽度的距离 ( 可以通过机器人) 的障碍物。

[0032] 所谓绕行方向是设定机器人沿区域边界运行或 沿障碍物运行时是顺时针运行还 是逆时针运行, 一般设定机器人从充电座 (或起始点) 直接前行的方向为运行 的绝对前方, 如果绕边界运行是顺时针运行, 那么机器人就优先检测它的左手 方向是否可以行走, 也就是检测前右后左 (顺时针) 四个方向中的第四方向 ( 上一目标方向) 是否可以行走, 如果可行, 那就往左走, 往左走后, 就要优先 检测左前右后四个方向中的第四个方向, 也就是后方向, 诸如此类。 如果在沿 边界向前运行时, 左方向是边界 (或障碍物) , 前方可行, 你们机器人就沿当 前方向向前行走, 如果前方也是边界 (或障碍物) —一般为房间的墙角, 那 就往前右后左的第二个方向 (下一目标方向) 就是右方向行走, 在向右方向行 走时, 优先检测的就是右后左前的第四个方向前方向 , 如果机器人左前右均不 能走 (死胡同) , 那么机器人只能往后方向行走, 往后方向行走时优先检测后 左前右的第四方向也就是右方向, 机器人沿边行走的示意图如图 6~7中的最外围 一圈, 这是定义的“绕边界运行是顺时针运行”, 当然按照这种法则, 机器人绕独 立障碍物的趋势是逆时针运行, 也就是在区域内走是顺时针运行, 但遇到独立 障碍物时相对于障碍物是逆时针运行, 也可以认为这是左手优先的左手法则。 当然也可以设定机器人逆时针绕边界或障碍物 运行, 按照右手优先的右手法则 运行, 对应的方向完全相反, 可以看做是机器人 (按左手优先法则) 运行的一 种“镜像”。 遍历运行原理是一样的。

[0033] 所谓近似点是指机器人在某一点开始一段线路 的行走, 然后存在返回该点的趋 势 (方向是起始运行方向的上一个方向) , 在与该点的距离小于一个车位时, 可以认为这段线路已经走完, 这种近似点一般于机器人开始沿边界行走, 准备 走完一圈时设定, 或者机器人第一次遇到一个独立障碍物, 准备沿障碍物外围 行走一圈时设定。 但要区别出当前运行方向的右侧 (左手法则) 相邻位置, 否 则会刚开始走就被误认为已走完, 广义的近似点指某一点前后左右四个方向上 与机器人当前目标方向反方向距离不超过一个 车位长度的点 (作为近似路线的 起点) 或正方向距离不超过一个车位长度的点 (作为近似路线的终点) 或当前 路线相邻一侧且距离不超过一个车位长度的点 。

[0034] 所谓相对封闭的区域是指:

[0035] 1) 在绕行区域边界或大的独立障碍物边界过程中 的某个方向改变处, 第 n (n

>=1) 次进入后又转出时, 进入通道与转出通道处的通道宽度不大于两个 车位 ( 机器人行走所覆盖的宽度称之为一个车位, 可以理解为机器人的垂直于行走方 向的宽度, 不大于两个车位, 表示这两个位置之间没有障碍物存在) -出口 时判定, 口子内的区域在第 n次绕行后, 存在能走但没有走到的区域, 如图 1 (b ) 中 S1区域、 图 1 (c) 中的 SI、 S2。

[0036] 2) 在机器人遍历过程中的某个转弯处, 它刚行走的行走通道与已经走过的区 域之间的宽度不大于两个车位, 在另一个相同时针方向 (要么同样顺、 要么同 样逆) 的转弯处, 它的行走通道与已经走过的区域之间的宽度也 不大于两个车 位, 并且在这个转进—前一个转弯处和转出—后一 个转弯处的之间的行走 线路与已经走过的区域间, 存在能走但没有走到的区域。 上述的转进是指如果 机器人绕障碍物的方向是逆时针方向, 那么, 机器人的每次逆时针转弯就可能 是转进, 接下来的另 n次逆时针转弯就可能是转出; 如果机器人绕障碍物的方向 是顺时针方向, 那么, 机器人的每次顺时针转弯就可能是转进, 接下来的另 n次 顺时针转弯就可能是转出, 如图 1 (a) 中 S1、 图 2 (a、 b) 中的 S1、 图 3中的 SI 、 S2, 这种相对封闭的区域存在于独立障碍物与已走 过相邻的路线之间或者正 常行走 (不处于绕行独立障碍物过程中) 的路线间。

[0037] 3) 在第 n (n >=l) 次正常行走 (非处理独立障碍物) 过程中, 检测到正行走 的路线与前次绕行的独立障碍物 (路线 3) 或区域边界的部分路线相邻 (正在行 走的通道与已经走过的障碍物外沿线路之间的 宽度不大于两个车位) , 如图 4 (a ) 中的 S1、 图 4 (b) 中的 SI、 S2, 可以看作是 2) 的特例。

[0038] 相对封闭的区域可能存在于一个需要遍历的区 域的轮廓线 (边界) 上, 或存在 于障碍物的轮廓线上, 或存在 ^于其它正在行走的线路 (无论与正在绕行的障碍 物有关或无关) 与已遍历区域或已走过的路线之间。

[0039] 相对封闭的区域还有一个需要特别划分出来, 就是由于受部分传感器量程或测 距方法 (主要是三角测量法) 的限制, 测距在某个范围内才比较正确, 那么需 要把整个可遍历区域划分成一个个独立的固定 大小 (比如 5米长短) 的小区域, 这个小区域的边界可看作是上述相对封闭的区 域的轮廓线 (边界) 。 如果通过 计算, 检测到的相对封闭的区域小于小的区域 (比如 5米乘 5米) , 则不考虑再 把它划分出小区域 (即便它跨越预先定义的多个小区域之间) , 如果通过计算 相对封闭的区域大于小区域, 仍需要将该相对封闭的区域划分出小区域, 依次 遍历。

[0040] 所谓简捷线路是指如果机器人在某一区域一次 进出后, 该区域已遍历, 在下一 次需走同样的路线时, 可直接绕过该区域, 走一捷径。 如图 2 (a、 b) 、 图 3中, 机器人首次绕行障碍物走过 A-B-C-D-E-F, CD之间的距离不大于一个车位, 那 么如图 2 (a) , 因为 AB、 EF在一直线上, 那么下次需要走相同路线 (或相邻平 行路线) 时, 直接走 AF之间的直线 (或 AF的近似线路) ; 对于图 2 (b) , 下次 可走 A-B-E’ (E’为 FE在 BC上的垂足) -E-F这段路线或者这段线路的近似线路; 对于图 3, 下次可走 A-B-B’ (B’为 AB在 DE上的垂足, ) -E-F这段路线或者这段 线路的近似线路。

[0041] 或者行进路线上存在一个相对封闭的区域, 而且这片区域已经遍历过, 那么下 一次走该区域时可直接在该区域的右边缘 (左手法则) 走过。 上一自然段中 CD 间也可以看作一片已走遍的相对密封的区域的 入口与出口。 更复杂的简捷线路 还可以计算绕过障碍物时从左绕和从右绕的简 捷线路长度, 选择较短的一段线 路走。

[0042] 机器人在前面的行走过程中, 已经在该区域或者该区域旁走过线路 ql, 现在机 器人需走同样的线路时, 可以走 ql同样的线路, 或者 ql的简捷线路, 或者与 ql 相邻一个车位 (机器人还未走过的那一侧) 的方向与 ql—致 (平行) 的线路 ( 称之为 ql的近似线路) , 或走相邻一侧已走过路线的近似路线, 或者局部与 ql (或 ql的简捷线路) 重合, 局部与 ql相邻一个车位 (机器人还未走过的那一侧 ) 的方向与 ql—致的线路, 走 ql同样的线路, 或者 ql的简捷线路是为了在一些 特定点 (比如障碍物的拐弯点) 对机器人进行定位纠偏, 或者为了机器人控制 程序的简化, 走 ql相邻一个车位的近似线路是为了尽量少走重 线路, 更快地 收束遍历区域, 缺点是程序复杂并且增加了封闭区域的数量, 且增加了封闭区 域间过渡移动的数量。

[0043] 上述已遍历的区域表示在一定的区域内, 机器人已全部走遍, 除了可能存在的 轮廓线外部及障碍物, 已不存在没有走到的区域。

[0044] 所谓下一目标点, 指机器人在绕行独立障碍物回到 A的近似点后, 接着要去的 目标点, 常用的有两个, 一个为从 A点沿 OA方向延伸至独立障碍物的另一面的 Z 点或 Z的近似点 (Z点离开障碍物方向一个车位的点) , 如图 1 (a) , 另一个为 A 点右手方向相邻一个车位的点 A”点或 A”的近似点 (A”离开障碍物方向一个车位 的点) 。 对于“回”字形走法 (又称螺旋式走法) , 目标点为 Z点或 Z的近似点, 对于“川”字形走法 (又称往返式走法) , 下一目标点为可为 A”点或 A”的近似点 , 也可以为 Z点或 Z的近似点。 不过由于存在相对封闭的区域, 独立障碍物的另 一面的 Z点所在的区域可能已经遍历过, 那么 Z点的位置 (下一目标点) 及离开 Z 点后的方向 (下一目标方向) 也会发生改变, 如图 2 (a、 b) 、 图 3: 在首次绕障 碍物边界移动过程中检测到有相对封闭的区域 时记录该点 (图 2 (a) 中的 L点、 图 2 (b) 中的 F点、 图 3中的 E点) 的位置及当前的移动方向, 在遍历完相对封闭 的区域后以点对点的方式移动至该点 (L/F/E点) ,并调整机器人的移动方向为首 次到该点 (F/E点) 时的移动方向的反方向、 将该点看作 Z点, 方向调整为首次 到该点 (F/E点) 时方向的下一个目标方向, 下一目标位置为左侧相邻路线的目 标位置的近似点,如图 2 (b) 中, 走 F’X的近似路线, 其中 F’为 EF线段在 WX线段 上的垂足; 或如图 3中, 走 E’Y的近似路线, 其中 E’为 B’E线段在 XY线段上的垂 足; 或返回 P点背离障碍物一个车位的点, 将该点看作 Z点, 方向调整为 q向的反 方向, 走相邻一侧已走过路线的近似路线, 如图 2 (a) , 走 L’-W-X的近似路线, 其中 L’为 ML线段在 VW线段上的垂足。

[0045] 如图 4 (a、 b) 在检测到有相对封闭的区域时记录该点 (B或 E) 的位置及当前 的移动方向, 在遍历完相对封闭的区域后以点对点的方式移 动至该点 (B或 E) , 并调整机器人的移动方向与首次到该点 (B或 E) 时的移动方向一致, 继续走至 原来的目标点。

[0046] 所谓下一个目标方向指当机器人遵循“左手优 先法则”执行“回”字形走法遍历时 , 如果当前运行目标方向是前方, 那么下一目标运行方向就是右方向, 再下一 (第三) 目标运行方向就是后方, 再一 (第四) 目标运行方向就是左方向, 第 五目标运行方向即是原目标方向 (依次顺时针循环改变方向) , 当然如果当前 目标方向是右方, 下一目标方向就是后方, 再下一目标方向就是左方, 诸如此 类; 对于“川”字形走法, 下一目标方向则是当前方向的反方向。

[0047] 所谓上一个目标方向为上述下一个目标方向的 反方向。

[0048] 所谓一个车位一般指机器人的宽度, 也可以把机器人的功能性部件 (比如扫地 机器人前进时, 清扫部件) 覆盖的宽度作为一个车位的宽度, 一般使用机器人 的功能性部件覆盖的宽度作为一个车位的宽度 , 也可将机器人的功能性部件覆 盖的宽度作为一个车位的宽度用于遍历的路线 之间的间距, 走简捷路线、 近似 路线的判别宽度 (如图 2、 图 3) 也使用功能性部件覆盖的宽度作为一个车位的 宽度, 而判别相对密封区域时或者检测障碍物时可使 用机器人的宽度, 当然也 可使用功能性部件覆盖的宽度。 在绕行边界或障碍物时的线路与相邻已走过的 路线不一定是一个车位的宽度, 但机器人贴近边界或障碍物当然贴得越近越好 , 因此本发明的遍历路线不需要限制每条路线与 相邻路线固定间隔一个车位的 距离 (示意图简化起见可这么标) 。

[0049] 当机器人在行进过程中首次遇到独立障碍物时 , 此处以机器人的中心位置 (也 可以是其它约定的点) 暂记为为 A点, 所谓大致一圈指下述两种情况: a) 就是 一圈, 即返回 A点; b) 机器人的在地面投影的中心点走到 A点的相邻位置 A’点 (A的近似点) , 不到一圈, A’点与 A点相距不超过一个车位的距离。

[0050] 回字形走法总的说来是从外向内一圈圈依次环 线方式行走, 如图 5 (a) 、 图 6~ 7 , 起始点 (比如清洁机器人的充电座或走下充电座的地 方) 一般要求在区域的 边界上, 每一圈的终点可以是该圈的起始点 (回到原点) , 下一圈的起始点则 是上一圈最后接近该点时的近似点; 或者每一圈的终点是绕一圈最后接近起始 点时的近似点, 下一圈的起始点就是该终点。 实施例中 (如图 6~7) 采用的起始 点是上一圈第一段线段终点前的相邻一个车位 的位置, 图中用小“□”标示, 这样 设置的目的是因为有可能起始点或终点位于一 个独立障碍物的周围, 环绕这个 障碍物再去设置起始点相对来说程序稍稍复杂 些。

[0051] 开始遍历的起始点如果没有设置在区域的边沿 (可以使用碰撞传感器检测或者 机器人只是简单地逆时针改变方向四次且走了 四步—说明机器人放置在一个 四不着边的地方, 在原地打转) , 那么机器人需要向任意方向, 最好使用测距 传感器检测离那个方向的边界 (障碍物) 最近, 或者就是朝前移动直至遇到障 碍物, 遇到障碍物后还需要绕行障碍物一圈回到原点 或近似点, 并且判断这个 障碍物是独立障碍物还是区域边界, 判断的原则是在绕行障碍物的起始点开始 对机器人在绕行过程中左转还是右转进行计数 , 如果机器人绕行后回到起始点 或起始点的近似点时顺时针改变方向的次数比 逆时针改变方向的次数多三次 ( 或以上) 则表明对于左手法则的机器人运行, 这个障碍物是区域的边界 (环绕 在边界的内圈) , 如果机器人绕行后回到起始点或起始点的近似 点时顺时针改 变方向的次数比逆时针改变方向的次数少三次 (或以上) 则表明机器人是在绕 独立障碍物运行 (环绕在障碍物外围) , 如果目前只是在环绕独立障碍物运行 , 则机器人还需要继续绕过障碍物 (根据计步选择左绕或者右绕 (步数少的一 侧) , 如果只是为了算法简单, 指定右绕即可) , 沿原来的方向一直向前, 继 续绕过独立障碍物直至确实在围绕区域的内边 界并已回到该次围绕的起始点 ( 或近似点) , 并将这个起始点作为开始遍历的原点。

[0052] 机器人在遍历过程中还需要进行点对点的移动 , 点对点主要应用于遍历完一个 相对封闭的区域后回到开始遍历这个相对封闭 区域的起始点, 或者在全部遍历 完一片区域后回到机器人开始工作的起始点 (比如充电座) , 点对点的工作方 法可依据上一段寻找起始点的方法执行, 稍有区别的是因为知道目标点的具体 位置, 在绕行独立障碍物时, 不需要回到原点或近似点, 直接走到原方向的障 碍物另一侧即可脱离障碍物, 点对点算法还可进一步优化: 因为知道目标点在 哪个位置, 假设到目标点之间没有障碍物或者只是简单障 碍物 (形状不是很复 杂的小块) , 那么就可以将起始点与目标点看做是长方形的 两个对角点, 选择 走长方形的边长一侧 (程序简单点就是优先走顺时针方向—针对左 手法则)

, 当然也可直接走对角线 (斜线) , 到位后再纠正方向。

[0053] “川”字形走法形式上看上去比较简单, 无非是向前走 (或向右走, 可以看作向 前走的方式转过 90度) 到边界, 再侧向走过 (左手法则是向右移动) 一个车位 的距离, 然后向后移动 (也可看作掉头再直行) 或者反方向移动, 直至走到反 方向的边界处, 这个边界可以指障碍物 (或区域边界) , 或者是已走过的边界 (开始时绕行区域边界一周建地图或者是首次 绕行独立障碍物时建立的障碍物 地图) , 如图 5 (c) , “川”字形走法的每次直行也可不走到边界, 而是边界的近 似点 (因为边界一圈已经走过) , 如图 5 (b) , 遍历更加快速, 走到边界的好 处是: 可以利用物理障碍物调整下机器人的方位。 “川”字形走法可以是单纯的一 种前后 (或左右) 方向移动, 或者是独立障碍物前后方位前后向移动、 独立障 碍物左右方位左右向移动的混合方式, 甚至是独立障碍物前后方位左右向移动 、 独立障碍物左右方位前后向移动。 每次移动的目标点 (即到目标点即掉头回 走处) 可以是整个区域的边界, 或者是移动过程中依次遇到的第一个独立障碍 物的边界, 如果需要将整个可遍历区域划分小区域 (比如 5米乘 5米) , 目标点 也可以是小区域的边界。

[0054] “川”字形走法的也包含起始位置、 目标位置 (含终点) 的设定、 点到点的移动 等回字形走法类似的问题, 可参考回字形的处理方式, 不过区别在于目标 (结 束) 位置或者是下一目标点可能在起始位置的相邻 位置, 比如图 3中, 遇到障碍 物的起始位置为 A点, “川”字形走法的目标位置 (或者下一目标点) 也可以是 A 的右侧相邻位置 A”点或 A”点的近似点 (A”离开障碍物方向一个车位的点) 。 [0055] 本发明中对障碍物的认定方式是针对一个封闭 的相对平坦的区域的 (比如室内 ) , 它同样适用于一片敞开的、 或局部封闭、 局部敞开的区域中, 不包括封闭 在障碍物之内的障碍物, 或者机器人根本走不进去的区域, 对于有落差的上升 台阶或者下降台阶也被认为是障碍物。

[0056] 对于敞开的区域比如花园, 可遍历区域是指比设定的固定的长度和宽度范 围大 的区域; 局部封闭、 局部敞开的区域是指该区域部分存在障碍物边 界, 局部需 要人为设置边界, 比如可以用某种物品 (比如线) 或者电子围栏方式围住的一 片区域。

[0057] 图 1~4中粗线表示已走过的线路 (相邻部分) , 细线表示本次任务 (正在绕行 独立障碍物或者正在向目标点行走 (不在绕行障碍物) ) 正在走的路线, 虚线 表示绕行外障碍物或相对封闭区域后下一次目 标路线 (自 Z或 Z近似位置出发)

[0058] 虽然本发明给出的方法只是用于处理边界或障 碍物, 并不是完整的整套遍历方 案, 但因为机器人在空旷的场合走法比较简单, 对于多个相对封闭的区域或者 大的相对封闭的区域套小的相对封闭的区域均 可用此方法处理, 多个是一个一 个依次处理, 大套小是应用递归算法 (程序调用自身的编程技巧称为递归) 处 理。

[0059] 示例图中为简单起见障碍物都摆放得方方正正 , 如果是斜放的, 可以将斜边量 化为锯齿 (阶梯) 状的线段, 如图 1 (b) 的局部。 例图中粗线段标示已走过的 路线 (只画了相关联的部分部分) , 细线标示正在 (或正欲) 走的路线, 虚线 标示目标走的路线, 路线一般表示机器人的在地面投影的中心的移 动轨迹。

[0060] 本发明不能被看做是现有一些遍历路径规划的 完善, 而是提出了新的方法解 决现有的方案中的具体缺陷, 事实上本发明人也是世界上唯一一位敢于宣称 编 制成功“在任意复杂障碍物情况下 100%遍历且不受 CPU (MPU) 速度、 存储单元 大小限制”程序的人, 见附图 6~7