２ 模 型假 设
１ ） 假设绕过障碍物我们均走最小半径的圆弧 ； ２ ） 假设 机 器人 能够 抽象 成点 来处理 ；
３ ） 假 设不 考虑 弧度 计算 ；
圆相 切 ， 切点 分别 为 Ｅ和 Ｆ， 当 Ｙ趋 近 于 Ｙ 时 ， 显 然 Ａ Ｃ Ｂ是这 种折 线 路 径 中最 短 的。 因 为 当 ： ０＜ Ｏ ｔ ＜
１ ８
数
字
通
信
第４ ０卷
与障碍 物 问的最 近距离 为 １ ０个单 位 ， 否则将 发 生碰 撞， 若碰 撞 发生 ， 机 器 人则无 法完 成行 走 。 建立 机器人 从 区域 中一点 到达 另一 点 的避 障最 短路径 和 最短 时问路 径 的数 学模 型 。场 景 图 中有 ４ 个 目标 点 ０（ ０ ， ０） ， ４（ ３ ０ ０ ， ３ ０ ０ ） ， Ｂ（ １ ０ ０ ，７ ０ ０ ） ， Ｃ （ ７ ０ ０ ， ６ ４ ０ ） 。具 体分 别计算 ：机 器人 从 ０（ ０ ， ０ ） 点
出发 ， Ｄ 一４， Ｄ —Ｂ， Ｄ — Ｃ和 Ｄ —Ａ —Ｂ —Ｃ — Ｄ 的最 短路 径及 长度 。
问题 ： 证 明绳 子拉 紧时 的情况 ， 则 为 ２个 点 之 间
的最 短路 径 。 假设 在平 面 中有 Ａ（ ａ ， ０ ） 和 曰（一ａ ， ０ ） ２点 ， 中
间有 １ 个半圆形的障碍物 ， 证 明从 到 Ｂ的最路径
分析 中的绳子拉到最紧时的情况 。
Ｔ Ａ Ｅ Ｆ Ｂ是 满足 条件 Ａ到 的最短 路径 。
第 ６期
侯学 慧 ： 机器人避 障问题模型研究
ｌ ９
３ ． ２ 模型 准 备 １
所 以，
＝２ 一Ｏ ｔ 一卢 一
我们可以这样认为 ， 起点 到 目标点无论 中间障
碍 物 有多 少 ， 最 短 路径 都 应 该 是 由若 干 个 线 圆 结 构
， 、
Ａ Ｃ ． Ｂ， 记 线段 Ａ Ｅ、 弧 度Ｅ Ｆ 、 线 段 船 的路线 为 Ａ Ｅ Ｆ Ｂ，
符号
说 明
路 径 的 总 长 度
那么 Ａ Ｅ Ｆ Ｂ的长度比任何折线路径都短 。
下面再考 察 １ 条不穿 过障碍物 的任何 １条路径 ， 设其 分别 与 Ｏ Ｅ和 Ｏ Ｆ的延长线 交 于 Ｐ， Ｑ ２点 ， 记Ａ
一
— ‘、
时， 有ｏ ｔ ＜ｔ ａ ｎ ｔ ｘ ， 所 以易 知 弧 长 Ｅ ・ Ｆ小 于 折 线 段
二
／ ’、 ‘、
４ ） 本 文所 用 到的特 殊符 号说 明如 表 ２所 示 。
表 ２ 本 文 所 用 到 的特 殊 符 号 说 明 表
Ｅ Ｃ ｌ Ｆ的长 ，即Ｅ ・ Ｆ＜Ｅ Ｃ 】 Ｆ， 从而 Ａ Ｅ＋ Ｅ・ Ｆ＋ Ｆ Ｂ＜
一
再来比较 Ｐ Ｑ之 问路径长度Ｐ Ｑ 和圆弧Ｅ Ｆ 长度
的大小 。因为路径长度 Ｐ ９大于或者等于最小的圆
弧长度 Ｐ Ｑ， 我们知道弧长 ＝ 半 径 ×圆心角 ， 弧 Ｐ Ｑ 所在圆的半径大 于弧 Ｅ Ｆ所在 圆的半径 ， 圆心角相 同， 因此路径 长度 Ｐ ｐ大于 圆弧 Ｆ， 即路 径 Ａ Ｐ Ｑ Ｂ
和 Ｐ之 间 的路 径 长度为Ａ Ｐ， 显 然Ａ 尸＞ｌ Ａ ＰＩ ， 又 由Ａ Ｅ
第 ｉ 段切 线的长度 第 段 圆弧 的长度 转弯半径
垂 直于 Ｅ Ｏ， 所以 ｌ Ａ Ｐｌ ＞ Ａ Ｅ， 从 而Ａ Ｐ＞ Ａ Ｅ， 同理 可 得
Ｂ Ｑ＞Ｂ Ｆ。
／ 、
３ 模型 的建立
３ ． １ 首先 证 明一个 猜想
为４ 一Ｅ —Ｆ （ 圆弧 ） 一 日， 如 图 ２所 示 。
ｃ ｏ， ｒ ）
／、
１ 问题 Байду номын сангаас 析
问题 中要 求 从 点 ０（ ０ ， ０ ） 出发 ， 按 照 一 定 的行
） 入Ｑ
走规则直线或者曲线绕过障碍物到达 目 标点的最短
路 径 。我们 可 以采 用 走 曲线 时 通 过 最小 半 径 ， 然 后 采 用 固定 圆拉 绳 子 的 方 法 ¨ Ｊ ， 寻 找 可 能 的 最 短 路 径 。比如 ： 求 ０和 之 间 的最 短 路 径 ， 我 们 就 用 一 段 绳 子连接 ０和 Ａ ２个 点 ， 以拐 角处 半 径 为 最 小 单 位 １ ０的 圆为支撑 圆 ， 从 常识 可 知道 ， 当拉 紧绳 子 时 ， 这 段 绳 子 的长 度 便 是 ０到 的一 条 可 能 的 最 短 路 径； 然后 ， 采 用 穷 举 法 列 出 ０到 每 个 目标 点 的 可 能 路 径 中 的最 短路 径 ； 最后 ， 比较 其 大 小 关 系 ， 便 可 得 出 ０到 目标点 的最 短路 径 。用 同样 的方 法 去讨论 ０
到达 Ｂ， Ｃ以及 ０一 Ａ—Ｂ—Ｃ一０ 的最 短路 径 。
图２ Ａ 到 Ｂ 的最 短 路 径 为 Ａ —Ｅ — Ｆ（ 圆弧 ） 一曰
Ａ （ ｎ ， ０ ） ０ 口 （ 一 ０ ０
平面上连接 ２ 点 的最短路径是通过这 ２点的直线
段， 但是连接 ２ 点 的线段与障碍物相交 ， 所以设法尝
的长 度超 过路 径 Ａ Ｅ Ｆ Ｂ的长度 。以上证 明足 以说 明
一
猜想 １ ： 具有圆形限定区域 。从 一Ｂ的最短路
径 由 ２部 分组 成 ： 一部 分 是 平 面 上 的 自然 最 短 路 径
（ 即直线段 ） ； 另一部分是限定 区域 的部分边界 （ 圆
弧 部分 ） ， 这 ２部 分 是 相 切 的 ， 互相 连接的， 即 问题
试折线 路径 。在 Ｙ 轴 上取一 点 ｃ （ ｏ， Ｙ ） ， 若 Ｙ适 当大 ，
则折线 Ａ Ｃ Ｂ与障碍物不相交 ， 折线 Ａ Ｃ Ｂ的长度为
Ｉ Ａ Ｃ Ｂ Ｉ ：２
＿ ＿
显然 ｌ Ａ Ｃ Ｂ ｌ 随 着 Ｙ的减 小 而 减 小 。设 点 Ｃ 的
坐标为（ ０， Ｙ ， ） ， 其中 Ａ Ｃ ， 与Ｂ Ｃ 分 别 与 已知 的障 碍
从 而可 得 ，