(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210500796.1 (22)申请日 2022.05.09 (71)申请人 浙江大学 地址 310058 浙江省杭州市西湖区余杭塘 路866号 (72)发明人 裘乐淼　董良宇　高一聪　 (74)专利代理 机构 杭州求是专利事务所有限公 司 33200 专利代理师 林超 (51)Int.Cl. B25J 9/16(2006.01) (54)发明名称 用于救援清障的移动机器人机械臂搬运最 优时间规划方法 (57)摘要 本发明公开了一种用于救援清障的移动机 器人机械臂搬运任务最优时间规划方法。 根据救 援清障任务确定搬运操作执行总次数， 确定三种 位置点的空间坐标以及三种位置点的通过顺序， 进而构建成分层有向图， 通过分层有向图的处理 获得最优循环路径； 确定最优循环路径的重复数 目和剩余最 短路径， 将连续重复数目的多个最优 循环路径与剩余最短路径进行拼接获得最终最 短路径。 相比于利用最短路径算法搜索大规模有 向图求解， 本方法能够显著降低优化过程的算法 复杂度， 并能快速实现对任务的规划， 达到最短 的完成时间。 权利要求书3页 说明书7页 附图1页 CN 114770512 A 2022.07.22 CN 114770512 A 1.一种用于救援清障的移动机器人机械臂搬运最优时间规划方法， 其特征在于包括以 下步骤： 1)根据救援清障任务的需要， 确定搬运操作执行总次数N， 对障碍物在机械臂空间坐标 系下的位置进行标定， 确定抓取点、 避障点和 放置点的三种位置点的空间坐标以及三种位 置点在救援清障任务中机 械臂末端空间路径的通过顺序； 2)根据三种位置点的空间坐标以及三种位置点的通过顺序构建成分层有向图， 通过分 层有向图的处 理获得最优循环路径； 3)根据救援清障任务中的搬运操作执行总次数N， 确定最优循环路径 的重复数目和剩 余最短路径， 将连续重复数目的多个最优循环路径与剩余最短路径进 行拼接获得最 终最短 路径。 2.根据权利要求1所述的用于救援清障的移动机器人搬运任务最优时间规划方法， 其 特征在于， 所述 步骤1)具体为： 根据救援清障任务的需要， 对 障碍物在机械臂空间坐标系下的位置进行标定， 且根据 障碍物的分布情况确定机械臂的单一搬运操作的抓取点、 避障点和放置点， 以及抓取点、 避 障点和放置点在机械臂末端空间路径的通过顺序； 根据需搬运物体的数量确定机械臂的搬 运操作执 行总次数N。 3.根据权利要求1所述的一种用于救援清障的移动机器人搬运任务最优时间规划方 法， 其特征在于： 所述 步骤2)具体为： 2.1)根据抓取点、 避障点和放置点的空间坐标， 求解获得每种位置点下的多种可能的 机械臂关节配置， 并按照三种位置点的通过顺序， 计算顺序下相邻两个位置点的所有可能 的关节配置之间的运行时间， 以三种位置点的关节配置作为节点， 一种位置点对应的所有 关节配置作为层， 关节配置之间的运行时间作为 边， 构建分层有向图的基元； 2.2)对分层有向图的基元中进行最短运行时间的赋权路径搜索， 求得起始层和结束层 之间的不同节点间的最短路径， 组成单次搬运操作下机 械臂关节配置的最短路径集 合； 2.3)按照救援清障任务中的搬运操作执行总次数N对多次搬运操作的最短路径集合进 行适配组合， 获得多基元循环路径， 选取最优循环路径。 4.根据权利要求3所述的一种用于救援清障的移动机器人搬运任务最优时间规划方 法， 其特征在于： 所述步骤2.1)具体为： 根据确定单次搬运操作中的抓取点、 避障点和放置 点的空间坐标， 求取机械臂在每种位置点下 的所有可能的关节配置， 机械臂在一种位置点 下的一个关节配置作为多层有向图的一层中的一个节点， 机械臂在一种位置点下的所有多 个关节配置组成了多层有向图的一层节点； 将单次搬运操作中的三种位置点在多层有向图 中对应的层按照所述通过顺序进 行依次排序， 且作为起始位置点和目标位置点的位置点在 多层有向图中对应的层结构重复两次， 分别 设置在多层有向图中的起始层和结束层， 不作 为起始位置点和目标位置点的位置点在多层有向图中对应的层作为中间层； 利用梯形控制 曲线求得相邻 层的每两个关节配置之 间的运行时间作为两个节点之 间的边， 从而构成了代 表单次搬运操作的分层有向图的基元。 5.根据权利要求3所述一种用于救援清障的移动机器人搬运任务最优时间规划方法， 其特征在于： 所述 步骤2.2)具体为： 在一个分层有向图的基元中， 分别以起始层的一个节点到结束层的一个节点构建作为权　利　要　求　书 1/3 页 2 CN 114770512 A 2一对循环节点对， 分别求得每对循环节点对的两个节点之 间的最短运行时间的路径作为该 对对循环节点对的最短路径； 再由每对循环 节点对下获得的最短路径组成最短路径集 合。 6.根据权利要求3所述的一种用于救援清障的移动机器人搬运任务最优时间规划方 法， 其特征在于： 所述 步骤2.3)具体为： 设置搬运操作次数n， 在 救援清障任务中的搬运操作执行总次数N的约束下遍历所有可 能的搬运操作次数n， 搬运操作次数n大于等于1小于等于N； 在每种搬运操作次数n下， 进行 以下操作： 按照n次搬运操作的顺序将n次搬运操作对应的分层有向图的基元进行依次拼接形成 分层有向图， 且按照n次搬运操作的顺序将n次搬运操作对应的最短路径集合中的各条最短 路径进行依 次拼接， 一种拼接结果作为一条多基元循环路径， 按照排列 组合方式获得多种 拼接结果， 所有拼接结果的多基元循环路径组成了分层有向图对应的多基元循环路径集 合； 且拼接过程中， 每条多基元循环路径中符合以下约束： A)分层有向图中， 起始的基元在多基元循环路径中对应的首条最短路径的起始层节点 和尾条最短路径的结束层节点相同， 形成一个 循环； B)分层有向图中， 位于中间的基元在多基元循环路径中对应的中间最短路径的起始层 节点和结束层节点互不相同， 且和起始的基元在多基元循环路径中对应的首条最短路径的 起始层节点 也不同； C)搬运操作次数n小于单个 基元中起始层/结束层的节点总数j1； 根据以上约束， 求得当前分层有向图和多基元循环路径集合下的多基元循环路径的总 数为： 其中， n为分层有向图所含基元 数目， j1为单个基元中起始层/结束层的节点总数； 从 个多基元循环路径中选取最短的多 基元循环路径作为当前的搬运操作次数n下的 最短循环路径 在不同的搬运操作次数n下获得各自的最短循环路径 再求取不同的搬运操作次数n 下最短循环路径 的平均基元路径长度： 选取其中最短的平均基元路径长度对应的最短循环路径作为当前救援清障任务下的 最优循环路径。 7.根据权利要求1所述一种用于救援清障的移动机器人搬运任务最优时间规划方法， 其特征在于： 所述步骤3)中， 将搬运操作执行总次数N除以最优循环路径对应的分层有向图中的基 元数， 获得余数， 按照余数 下的搬运操作次数通过搜索算法获得剩余 最短路径。 8.根据权利要求1所述一种用于救援清障的移动机器人搬运任务最优时间规划方法，权　利　要　求　书 2/3 页 3 CN 114770512 A 3