(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211001163.2 (22)申请日 2022.08.19 (71)申请人 北京控制工程研究所 地址 100080 北京市海淀区北京272 9信箱 (72)发明人 刘昊　黄煌　汤亮　谢心如　 (74)专利代理 机构 中国航天科技专利中心 11009 专利代理师 马全亮 (51)Int.Cl. G06F 30/27(2020.01) G06N 3/12(2006.01) G06Q 10/04(2012.01) G06Q 10/08(2012.01) (54)发明名称 基于偏随机密钥遗传算法的不规则岩石三 维装箱优化方法 (57)摘要 一种基于偏随机密钥遗传算法的不规则岩 石三维装箱优化方法， 包括： 对岩石样本进行视 觉采样和三维重建； 对网格模型进行处理； 对偏 随机密钥遗传算法进行初始化， 生成初代种群； 建立容器及OBB包围盒的碰撞模型， 设置其位置 和姿态； 建立各OBB包围盒对应的岩石样本的碰 撞模型， 设置其位置和姿态； 添加重力和摩擦力， 计算容器空间占有率作为个体的适应度； 根据适 应度大小将种群个体分为精英个体和一般个体 两类， 按照偏随机密钥遗传算法对种群进行复 制、 交叉和变异操作， 产生下一代种群； 重复执 行， 当满足终止条件时， 输出最大适应度个体解 码装箱后各岩石样本的最终位置和姿态作为最 终装箱方案。 本发明能实现有限容器内对不规则 岩石最大化装箱。 权利要求书3页 说明书5页 附图5页 CN 115470695 A 2022.12.13 CN 115470695 A 1.基于偏随机密钥遗传算法的不 规则岩石三维装箱优化方法， 其特 征在于包括： 步骤1： 对每 个岩石样本进行视 觉采样和三维重建， 得到各岩石样本的网格模型； 步骤2： 对各岩石样本网格模型进行处理， 使其最小有向包围盒OBB与轴对齐包围盒 AABB重合， 即最小 有向包围盒OB B与网格模型坐标轴平行、 与坐标原点重合； 步骤3： 对偏随机密钥遗传算法进行初始化， 对个 体进行编码生成初代种群； 步骤4： 在pybullet中， 建立容器及OBB包围盒的碰撞模型， 并对每个个体的基因进行解 码， 根据解码后所得的装箱 顺序和方向对各OBB包围盒进 行装箱， 输出各包围盒的位置和姿 态； 其中基因解码后， 检测OBB包围盒尝试以6个方向放置后， 其前右上角距离容器前右上角 距离最远的极点作为 放置位置； 步骤5： 在pybullet中， 建立各OBB包围盒对应的岩石样本的碰撞模型， 设置其位置和姿 态为步骤4中OB B包围盒的位置和姿态； 步骤6： 在pybullet中添加重力和摩擦力， 岩石样本的碰撞模型在重力作用下开始下 落， 使得装箱更紧密， 待各碰撞模型 稳定后， 计算 容器空间占有率作为个 体的适应度； 步骤7： 根据适应度 大小将种群个体分为精英个体和一般个体两类， 按照偏随机密钥遗 传算法对种群进行复制、 交叉和变异操作， 产生下一代种群； 步骤8： 重复步骤4至步骤7， 当满足终止条件时， 输出最大适应度个体解码装箱后各岩 石样本的最终位置和姿态， 作为 最终装箱方案， 终止计算。 2.根据权利要求1所述的基于偏随机密钥遗传算法的不规则岩石三维装箱优化方法， 其特征在于： 未 处理岩石样 本网格模型AABB 包围盒与OBB 包围盒不重合， 处理后岩石样 本网 格模型OB B包围盒与A ABB包围盒重合。 3.根据权利要求1或2所述的基于偏随机密钥遗传算法的不规则岩石三维装箱优化方 法， 其特征在于： 所述步骤2对 各岩石样 本网格模 型进行处理， 使其最小有向包围盒OBB与轴 对齐包围盒AABB重合， 具体为： 使用open3d对 各岩石样 本网格模 型进行处理， 得到各网格模 型的最小有向包围盒OBB， 并得到包围盒的中心OBB.center、 尺寸OBB.extent、 旋转矩阵 OBB.R； 然后对网格模 型进行平移、 旋转； 处理后生 成新的网格模型STL_New和新的最小有向 包围盒OBB_New； 如此得到的包围盒OBB_New与网格模型STL_New的坐标轴平行， 坐标原点重 合。 4.根据权利要求1所述的基于偏随机密钥遗传算法的不规则岩石三维装箱优化方法， 其特征在于： 对偏随机密钥遗传算法进行初始化包括： 设置进化代数num_generations、 相 同适应度等待次数patient、 种群个体数num_individuals、 精英个体数num_elites、 变异 个 体数num_mutants、 精英 选择概率eliteCProb。 5.根据权利要求1或4所述的基于偏随机密钥遗传算法的不规则岩石三维装箱优化方 法， 其特征在于： 对个体进行编码， 具体为： 有N个待装箱岩石样本， 则每个个体包含2N个基 因， 前N个基因代表装箱顺序， 后N个基因代表装箱方向， 生成N个随机密钥对应于每个待装 箱物品， 按照升序排列， 即得到装箱顺序， 作为前N个基因； 生成N个随机密钥对应于每个待 装箱物品， 作为后N个基因， 每个待装箱OBB包围盒有六个装箱方向， 其随机密钥的数值乘6 后向前取整则为当前包围盒的装箱方向。 6.根据权利要求1所述的基于偏随机密钥遗传算法的不规则岩石三维装箱优化方法， 其特征在于： 步骤6中所述容器空间占有率是指所放置模型的总体积Vobj与已放置模型的权　利　要　求　书 1/3 页 2 CN 115470695 A 2最高点Zmax以下 所占据的容器空间体积之比， 容器空间占有率计算公式如下： Rate＝Vobj/(Zmax*L*W) 其中， Rate为容器空间占有率， Vobj为放置模型的总体积， Zmax为已放置模型的最高 点， L为容器底面长度， W 为容器底面宽度。 7.根据权利要求1所述的基于偏随机密钥遗传算法的不规则岩石三维装箱优化方法， 其特征在于： 所述步骤7根据适应度大小将种群个体 分为精英个体和一般个体两类， 按照偏 随机密钥遗传算法对种群进行复制、 交叉和变异操作， 产生下一代种群， 具体为： 对每一代种群的个体根据适应度大小降序排序， 前num_elites个个体为精英个体， 剩 余个体为一般个体； 精英个体直接复制 到下一代种群中， 以确保解的质量在进化过程不断 获得提升； 交叉操作的两个个体， 一个来自精英个体， 另一个 以随机方式从全部个体中产 生； 交叉概率为eliteCProb， 即子代个体以eliteCProb的概率从父代精英个体中获得基因， 以(1‑eliteCPr ob)的概率 从父代一般个体中获得基因； 变异操作采用随机的方法产生num_ mutants个新个 体。 8.根据权利要求1所述的基于偏随机密钥遗传算法的不规则岩石三维装箱优化方法， 其特征在于： 步骤8所述终止条件为达到进化代数num_generations、 或适应度连续patient 次不再改变。 9.一种根据权利要求1所述的基于偏随机密钥 遗传算法的不规则岩石三维装箱优化方 法实现的不 规则岩石三维装箱优化系统， 其特 征在于包括： 网格模型获取及处理模块： 对每个岩石样本进行视觉采样和三维重建， 得到各岩石样 本的网格模型； 对 各岩石样 本网格模 型进行处理， 使其最小有向包围盒OBB与轴对齐包围盒 AABB重合， 即最小 有向包围盒OB B与网格模型坐标轴平行、 与坐标原点重合； 算法初始化模块： 对偏随机密钥遗传算法进行初始化， 对个 体进行编码生成初代种群； 碰撞模型建立模块： 在pybullet中， 建立容器及OBB包围盒的碰撞模型， 并对每个个体 的基因进 行解码， 根据解码后所得的装箱 顺序和方向对各OBB包围盒进 行装箱， 输出各包围 盒的位置和姿态； 其中基因解码后， 检测OBB包围盒尝试以6个方向放置后， 其前右上角距离 容器前右上角距离最远的极点作为放置位置； 在pybullet中， 建立各OBB包围盒对应的岩石 样本的碰撞模型， 设置其位置和姿态为步骤4中OBB包围盒的位置和姿态； 在pybullet中添 加重力和摩擦力， 岩石样本的碰撞模型在重力作用下开始下落， 使得装箱更紧密， 待 各碰撞 模型稳定后， 计算 容器空间占有率作为个 体的适应度； 种群产生和 处理模块： 根据适应度大小将种群个体分为精英个体和一般个体两类， 按 照偏随机密钥遗传算法对种群进 行复制、 交叉和变异操作， 产生下一代种群； 重复碰撞模型 建立模块， 当满足终止条件时， 输出最大适应度个体解码装箱后各岩石样本的最终位置和 姿态， 作为 最终装箱方案， 终止计算。 10.根据权利要求9所述的不规则岩石三维装箱优化系统， 其特征在于： 对各岩石样本 网格模型进行处理， 使其最小有向包围盒OBB与轴对齐包围盒AABB重合， 具体为： 使用 open3d对 各岩石样 本网格模 型进行处理， 得到各网格模 型的最小有向包围盒OBB， 并得到包 围盒的中心OBB.center、 尺寸OBB.extent、 旋转矩阵OBB.R； 然后对网格模型进行平移、 旋 转； 处理后生成新的网格模型STL_New和新的最小有向包围盒OBB_New； 如此得到的包围盒 OBB_New与网格模型STL_New的坐标轴平行， 坐标原点重合；权　利　要　求　书 2/3 页 3 CN 115470695 A 3