移 动机 器人 路径 规划 的研 究起 始 于 ２０世 纪 ７０ 年代 ，到 目前 为 止 ，已有 大 量 的研 究 成 果。例 如 Ｄｉｊｋｓｔｒａ算 法 Ｊ、Ａ ；｝＝算 法 Ｊ、人 工 势 场 算 法 及 遗 传 算法 等 在不 同领 域 的应用 。Ａ 算 法 是一 种 启 发 式路 径最 短搜 索 算 法 ，根 据 估 价 函 数决 定 待 扩 展 节 点 的操 作 方 向 ，进 而 修 改 ｏｐｅｎ列 表 和 ｃｌｏｓｅ列 表 里 的节点 ，直 到 目标 节 点 找 到 或 者 ｏｐｅｎ列 表 为 空 ，
（Ｓｃｈｏｏｌ ｏｆ Ａｕｔｏｍａｔｉｏｎ，Ｂｅｉｊｉｎｇ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅ＆ Ｔｅｃｈｎｏｌｏｇｙ Ｕｎｉｖｅｒｓｉｔｙ，Ｂｅｉｊｉｎｇ １００１９２，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ｉｎ ｖｉｅｗ ｏｆ ｔｈｅ ｌｏｎｇ ｐａｔｈ ｓｅａｒｃｈ ｔｉｍｅ ｏｆ ｔｈｅ ｔｒａｄｉｔｉｏｎａｌ Ａ ：ｌ：ｓｅａｒｃｈ ａｌｇｏｒｉｔｈｍ ，ｔｈｅ ｊｕｍｐ ｐｏｉｎｔ ｓｅａｒｃｈ ａｌｇｏｒｉｔｈｍ （ｊｕｍｐ ｐｏｉｎｔ ｓｅａｒｃｈ，ＪＰＳ）ｉｓ ｕｓｅｄ ｔｏ ｒｅｄｕｃｅ ｔｈｅ ｐａｔｈ ｆ ｉｎｄｉｎｇ ｔｉｍｅ ｏｆ ｔｈｅ ｈｏｍｅ
第 ３３卷 第 ３期 ２０１８年 ６月
北 京 信 息 科 技 大 学 学 报 Ｊｏｕｒｎａｌ ｏｆ Ｂｅｉｊｉｎｇ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅ＆ Ｔｅｃｈｎｏｌｏｇｙ Ｕｎｉｖｅｒｓｉｔｙ
Ｖｏ１．３３ Ｎｏ．３ Ｊｕｎ．２０１８
文 章 编 号 ：１６７４—６８６４（２０１８）０３－００８５－０５
ｓｅｒｖｉｃｅ ｒｏｂｏｔ． Ｂｙ ｓｅｌｅｃｔｉｎｇ ｔｈｅ ａｐｐｒｏｐｒｉａｔｅ ｈｅｕｒｉｓｔｉｃ ｆｕｎｃｔｉｏｎ，ｕｓｉｎｇ ｔｈｅ ｏｂｓｔａｃｌｅ ｅｘｐａｎｓｉｏｎ ｍｅｔｈｏｄ ａｎｄ ｓｉｍｕｌａｔｉｎｇ ｔｈｅ ｓｅａｒｃｈ ａｌｇｏｒｉｔｈｍ ｉｎ ｔｈｅ ｖｉｒｔｕａｌ ｍａｐ ａｎｄ ｔｈｅ ｒｅａｌ ｍａｐ， ｔｈｅ ｒｅｓｕｌｔｓ ｏｆ ｔｈｅ ｔｅｓｔ ｄａｔａ ａｒｅ ａｎａｌｙｚｅｄ ａｎｄ ｃｏｍｐａｒｅｄ， ａｎｄ ｔｈｅ ｓｅａｒｃｈ ｓｐｅｅｄ ｏｆ ｔｈｅ ｈｏｍｅ ｓｅｒｖｉｃｅ ｒｏｂｏｔ ｉｓ ｉｍｐｒｏｖｅｄ ｓｙｎｔｈｅｔｉｃａｌｌｙ． Ｃｏｍｐａｒｅｄ ｗｉｔｈ ｔｈｅ ｔｒａｄｉｔｉｏｎａｌ Ａ ａｌｇｏｒｉｔｈｍ ，ｔｈｅ ＪＰＳ ａｌｇｏｒｉｔｈｍ ｉｓ ｆｅａｓｉｂｌｅ ａｎｄ ｅｆｆｅｃｔｉｖｅ ｆｏｒ ｆａｍｉｌｙ ｓｅｒ ｖ ｉｃｅ ｒｏｂｏｔｓ．
最 后利 用节 点 的父节 点 回溯构 建 路 径 。ＪＰＳ算 法 是 基 于 Ａ 算 法 的一 种改 进 启 发 式搜 索 算 法 ，其 根 据 邻 居修 剪规 则 ，淘汰 了大量 可 能会 添加 到 ｏｐｅｎ列 表 和 ｃｌｏｓｅ列 表 的 中 间节 点 ，极 大 地 缩 短 了路 径 搜 索 时 间 。
本 文通 过将 ＪＰＳ搜索 算法 应用 于 ３种不 同类 型 和尺寸 的寻路环 境 进 行 多组 测 试 ，来 测 试 其 路 径 规 划 的效 果 和效 率 ，并 与 Ａ 算 法 进 行 对 比。测 试 结 果 表 明 ：ＪＰＳ搜 索 算 法 路 径 规 划 时 间远 远 小 于 Ａ 算 法 的规划 时 间 ；将 其 应 用 到 家庭 服务 机 器 人 的 寻 路 上 面 ，ＪＰＳ搜索 算法 可 以 避开 障碍 物 ，找 到最 优 路 径 。所谓 最优 路 径 在 本 文 中指 路 径 最 短 ，文 献 ［６］ 和 ［７］证 明 Ａ 算 法 和 ＪＰＳ算 法 在 一 定条 件 下 能 够 找到 最短路 径 。
Ｋｅｙｗｏｒｄｓ：ｎｅｉｇｈｂｏｒ ｐｒｕｎｉｎｇ ｒｕｌｅｓ；ｐａｔｈ ｐｌａｎｎｉｎｇ；ｊｕｍｐ ｐｏｉｎｔ ｓｅａｒｃｈ；Ａ ａｌｇｏｒｉｔ疾 人 口的迅 速增 长极 大 地增 加 了社会 的护理 压力 ，使 用 家 庭 服 务 机 器 人 是 减轻 社会 护 理 压 力 的有 效 手 段 ¨Ｊ。机 器 人 的 路 径 规划 是指 在有 障 碍物 的工 作 环 境 中 ，机 器 人 按 照 某 一 性 能指 标 （如距 离 、时 间等 ）寻找 一 条从 起 始 位 置 到 目标位 置 的最 优或 者次 优路 径 。
关 键 词 ：邻居 修剪 规 则 ；路 径规 划 ；跳 点 ；Ａ 算法 中图分 类 号 ：ＴＰ ２４２ 文献 标 志码 ：Ａ
Ｊｕｍ ｐ ｐｏｉｎｔ ｓｅａｒｃｈ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｐａｔｈ ｐｌａｎｎｉｎｇ ｏｆ ｈｏｍ ｅ ｓｅｒｖｉｃｅ ｒｏｂｏｔ
ｒＡＮＧ Ｆｅｎｇｍａｎ，ＺＨＡＮＧ Ｑｉｚｈｉ，ＺＨＯＵ Ｙａｌｉ
ＤＯＩ：１０．１６５０８／ｊ．ｃｎｋｉ．１１—５８６６／ｎ．２０１８．０３．０１８
家庭 服 务 机 器 人 路 径 规 划 的跳 点 搜 索算 法
杨 凤 满 ，张 奇 志 ，周 亚 丽
（北京信息科技大学 自动化学院 ，北京 １００１９２）
摘 要 ：针 对传 统 Ａ 搜 索 算 法路 径 搜 索 时 间过 长 的 问题 ，采 用 跳 点 搜 索 算 法 （ｉｕｍｐ ｐｏｉｎｔ ｓｅａｒｃｈ，ＪＰＳ）减 小 家庭服 务机 器 人 的 寻路 时 间 。通过 选取 合 适 的启 发 函数 、采 用 障碍 物 扩 张 方 法及在 虚拟 地 图和 真 实地 图 中对搜 索算 法进 行 仿 真 测试 ，对 测试 数 据 结 果分 析 和对 比 ，综合 地 提 高 了机 器人 的 寻径速度 。通过 与传 统 Ａ 算 法进 行 比较 ，ＪＰＳ算 法 用 于 家庭 服 务机 器人 的寻路 是 可行 和 有效 的 。