装配式建筑机器人施工路径优化方法

张润梅，任 瑞，袁 彬+，罗谷安，毕利君

(1.安徽建筑大学 机械与电气工程学院，安徽 合肥 230601；2.安徽建筑大学 工程机械智能制造重点实验室，安徽 合肥 230601)

0 引 言

装配式建筑是促进建筑产业现代化发展的新型建造方式，但其技术难度较高，发展限制性较大，为了进一步提高工作效率，减轻工人劳动强度，建筑机器人的引入是建筑行业发展的必由之路[1,2]。针对装配式建筑环境，利用传统外部传感器采集环境信息构建地图时，计算量较大，且因地图环境复杂，信息采集困难，难以构建出完整的地图[3]，因此，设计新型导航地图建立方法对建筑机器人路径寻优有重大意义。

路径规划问题经过国内外学者多年的研究，提出了大量的遗传蚁群优化算法[4]。Qiang Luo等[5]提出了一种改进的蚁群算法，提高了蚁群算法的全局搜索能力。Yen CT等[6]提出了一种模糊蚁群优化方法，可以对简单和复杂的拓扑结构进行路径规划和避障。Lamini C等[7]提出了一种改进的交叉算子，用遗传算法在静态环境中解决路径规划问题。传统蚁群算法具有正、负反馈和高鲁棒性的特点[8]，而遗传算法被称为鲁棒优化方法，利于全局择优。因此，通过结合两种算法的优点，可以提高算法的迭代速度和求解效率[9]。

本文针对装配式建筑这一复杂的应用新领域，设计了一种基于BIM融合遗传蚁群混合式算法的路径优化方法，通过BIM技术对建筑物进行数字建模，建立导航地图和实验环境，以3种传统算法和混合式算法作为搜索策略，利用软件分别在不同规格的栅格地图和某常规公寓的BIM施工地图的工作环境进行了算法性能测试，探究了混合式算法在不同障碍物布局的工作环境中路径规划的最优性及应用于装配式建筑的可行性。

1 混合式优化算法

1.1 蚁群算法

蚁群算法是模拟蚂蚁觅食的原理，寻找优化路径的一种几率型算法[10]。蚁群算法在求解机器人路径优化问题时，主要内容如下：

(1)输入机器人要寻找最优路径的地图，并初始化各种信息参数。

(2)利用轮盘法选择下一步节点

(1)

式中：α、β分别表示信息素、距离对蚂蚁选择路径的影响程度；τij(t)表示路径(i,j)上的信息素浓度；ηij(t)表示与路径(i,j)相关联的启发式信息；Jk(i)表示蚂蚁路径搜索下一步所有可选路径。

(3)持续更新路径和路径长度，直到某一代m只蚂蚁全部迭代结束。

(4)更新信息素矩阵，未到达的蚂蚁不计算在内

τij(t+1)=(1-ρ)τij(t)+Δτij(t)

(2)

(3)

(4)

(5)当第n代蚂蚁迭代结束时，算法结束，得到最优路径。

1.2 遗传算法

遗传算法是一种模拟自然界生物进化机制的智能优化算法，主要通过种群初始化、适应度函数计算、选择、交叉和变异求出机器人路径规划的最优解[11]。移动机器人利用遗传算法在栅格环境中进行路径寻优时，主要内容如下：

(1)初始化种群，要求随机产生多条可行路径，可行路径表示不与障碍物相碰撞的路径。

(2)通过适应度计算可以判断路径的长短和平滑程度。

(3)选择方法最常用的是轮盘赌法，可根据每个个体的概率选择出下一代个体，保证了部分非优个体，有效防止产生局部最优解。

(4)交叉方式通常采用单点交叉式，找出所有路径中相同的点，随机选择其中一个点，将之后的路径进行交叉操作。

(5)变异方式是随机选取除起点和终点的任意两栅格，使两栅格间连续化成功。

(6)当迭代次数达到预设数值时，算法结束，得到最优路径。

1.3 混合式算法原理

传统的遗传蚁群混合式算法仅在遗传算法结果的基础上，利用蚁群算法再搜索一遍[12]。本文设计了一种全新的遗传蚁群混合式算法，在混合式算法中，以蚁群算法为基础，通常每只蚂蚁在构造出一条从起点到终点的路径后，会根据路径的总长度来更新这条路径所包含的每条边上信息素的浓度，而遗传算法的染色体编码结构与蚁群算法信息素结构类似，可以将蚁群算法当前的信息素转化为遗传算法染色体，通过遗传算法和精英选择，选择出最优个体，再转化为信息素增量，影响蚁群整体的信息素。经过多次迭代计算，可以得到最优路径。

在编码设计中，蚁群算法的信息素结构设计为：每一条边有一个优先级，节点通过边与周围的节点相连接，仅和上下左右相邻节点连接。选择下一个节点时，在节点与相邻节点连线间边的优先级基础上，计算概率随机选择。

遗传算法的染色体编码结构与蚁群算法的信息素结构类似。因此，遗传蚁群混合式算法通过编码设计，能够使遗传算法的染色体和蚁群算法的蚂蚁个体相互转换，使遗传算法和蚁群算法结合更加紧密，能够得到更好搜索效果，进一步提升了算法全局搜索的能力,并极大避免陷入局部最优解的机率。

1.4 混合式算法步骤

基于混合式算法的路径规划流程如图1所示，其主要步骤如下：

步骤1初始化参数，开始迭代计算。

步骤2初代种群蚂蚁进行路径寻优，记录路径和适应度函数值。

步骤3按照遗传算法产生下一代。

步骤4将当前信息素转化为一条新的染色体，加入到子代，通过精英选择选出新的父代种群。

步骤5将新的父代种群的最优染色体转化为蚂蚁的搜索路径，即转化为信息素增量，调节并更新当前蚁群的信息素。

步骤6将新蚂蚁加入到当前的蚂蚁群体中，进行路径寻优。

图1 遗传蚁群混合式算法流程

步骤7如果满足循环结束条件(收敛或者达到迭代上限)，算法结束，输出结果，否则转到步骤3。

2 实验内容

2.1 实验方案

本文实验配备了戴尔R730服务器和AGV小车，如图2所示，主要是通过服务器交换实时信息，控制AGV小车运动，完成小车路经规划和避障工作。

图2 戴尔R730服务器与AGV小车

实验将在不同障碍物布局的工作环境下，分别对蚁群算法、遗传算法、粒子群算法和遗传蚁群混合式算法进行性能测试，以最终路径长度和收敛迭代次数作为性能判定指标，验证混合式算法的优越性及应用于装配式建筑环境的可行性。因此，本文分别在20×20栅格地图、30×30栅格地图这两种不同复杂程度的工作环境进行算法性能测试，主要通过Matlab软件进行实验仿真，主要参数见表1。

表1 仿真参数

2.2 栅格法

实验环境模拟方法有许多种，如拓扑图法、栅格法和顶点图法等。其中栅格法在移动机器人系统中应用的较为广泛，主要是把移动机器人所在的工作环境划进行单元分割，用等尺寸的正方形表示出来，该方法在处理障碍物边界问题上具有较大优势[13]。

利用栅格法对建筑机器人的路径规划过程进行实验环境建模时，可做如下假设：建筑机器人工作环境中的墙体、支持斜柱等均为有限已知的障碍物，且忽略障碍物高度。因此，可以把整个工作空间建立成XOY二维坐标系，分为障碍物区域和自由区域两个部分，可表示为

(5)

式中：f(x,y)=1表示障碍物区域，f(x,y)=0表示移动机器人可运动的自由区域。

移动机器人在栅格环境中的运动轨迹通常有8个方向可以选择，如图3所示，分别是OA、OB、OC、OD、OE、OF、OG和OH。但在装配式建筑环境的现实工作空间中，由于机器人体型较大且规格不一，在运动过程中，容易与墙体发生碰撞，如图3中节点1所示。所以本文在实验过程中将只选取OA、OB、OC、OD这4个机器人运动方向。

2.3 实验结果与分析

本文在20×20栅格地图的工作环境下进行算法性能测试，机器人移动路线可视化结果如图4所示，粒子群算法的总里程为39，遗传算法的总里程为41，蚁群算法的总里程为37，遗传蚁群混合式算法总里程为35。其中遗传蚁群混合式算法得到的最终路径长度最短，且收敛迭代次数最少。

本文在30×30栅格地图工作环境下进行算法测试，机器人移动路线可视化结果如图5所示，粒子群算法的总里 程为67，遗传算法的总里程为59，蚁群算法的总里程为为了便于比较遗传蚁群混合式算法的优势，记录图4和图5相关数据见表2。

图3 机器人运动轨迹

109，遗传蚁群混合式算法的总里程为55。其中遗传蚁群混合式算法得到的最终路径长度最短，且收敛迭代次数最少。

图4 20×20栅格地图工作环境下的测试结果

图5 30×30栅格地图工作环境下的测试结果

表2 普通地图下4种算法指标对比

通过仿真图和记录的相关数据可以看出，在20×20栅格地图和30×30栅格地图的工作环境下，遗传蚁群混合式算法相较于蚁群算法、遗传算法和粒子群算法，在最终的路径规划长度和收敛迭代次数上都优于其它3种算法，可以得到最短路径和最少收敛迭代次数。实验结果可以看出，通过遗传算法对蚁群算法搜索路径信息素的最优化选择，化为信息素增量，实时负反馈影响蚁群信息素的方法来进行路径规划，实际效果达到最优，验证了混合式算法的优越性。

3 BIM建模

BIM(building information modeling)技术是Autodesk公司在2002年率先提出的一种应用于建造、管理与工程设计的数字化工具[14]，具有可视化、协调性、模拟性、优化性和可出图性；主要通过建立虚拟的建筑工程三维模型，为项目提供一个工程信息交换和共享的平台，有助于建筑工程信息集成程度的提高[15]。

针对装配式建筑的复杂工作环境，因建筑机器人体型庞大，移动缓慢，在路径寻优过程中，利用传统外部传感器采集环境信息构建地图，信息采集较困难，存在计算量大，耗时，耗能的缺点，难以构建出完整的地图。因此，可以利用BIM技术对建筑物进行数字建模，建立一种新型导航地图。

在移动机器人路径规划的过程中，利用软件Revit2018对装配式建筑进行数字建模，可以准确模拟出现实的工作环境。如图6所示，为两个常规装配式建筑三维模型，主要有障碍物墙体及墙体支撑斜柱等。根据建筑物三维模型可以建立出二维导航地图，并模拟出BIM施工地图实验环境。

4 工程应用

通过BIM建立常规装配式建筑三维模型，模拟出装配式建筑栅格地图，如图7所示。

图6 装配式建筑三维模型

图7 装配式建筑栅格地图

在常规住宅BIM栅格地图工作环境下进行算法测试，机器人移动路线可视化结果如图8所示，粒子群算法的总里程为40，遗传算法的总里程为38，蚁群算法的总里程为34，遗传蚁群混合式算法的总里程为34。遗传蚁群混合式算法得到的最终路径长度最短，收敛迭代次数最少。

在常规公寓BIM栅格地图工作环境下进行算法测试，机器人移动路线可视化结果如图9所示，粒子群算法的总里程为59，遗传算法的总里程为57，蚁群算法的总里程为63，遗传蚁群混合式算法的总里程为55。其中遗传蚁群混合式算法得到的最终路径长度最短，且收敛迭代次数最少。

为了验证遗传蚁群混合式算法应用于装配式建筑环境的可行性及优越性，记录图8和图9相关数据见表3。

通过仿真图和记录的相关数据可以看出，在不同规格的BIM地图工作环境下的性能测试中，遗传蚁群混合式算法相较于蚁群算法、遗传算法和粒子群算法，在最终的路径规划长度和收敛迭代次数上均优于其它3种算法，可以得到最短路径和最少收敛迭代次数。实验结果验证了混合式算法应用于装配式建筑的可行性和优越性。

5 结束语

本文设计了一种遗传蚁群混合式算法，通过遗传算 法染色体和蚁群算法搜索路径的信息素相互转换，使这两个算法结合的更加紧密，利用该算法对装配式建筑机器人施工路径问题进行了研究。为了测试该算法的实际效果，在Matlab中利用栅格法，分别在20×20栅格地图、30×30栅格地图和BIM建模的装配式建筑这3种不同障碍物布局的工作环境中进行了算法性能测试。实验结果表明，与传统的蚁群算法、遗传算法和粒子群算法相比，混合式算法在优化路径和搜索效率方面具有更大的优势。验证了遗传蚁群混合式算法在装配式建筑机器人路径规划求解过程中，具有较好的收敛性能、较优的全局搜索能力和较高的搜索效率。同时，本文由于没有具体的工程实验背景，仿真结果与实际工程应用仍将存在一定的偏差，后期需要进一步改进及验证，但本文方法具有普适性，可为多领域路径规划提供借鉴的思想和方法。

图8 常规住宅BIM地图环境下的测试结果

图9 常规公寓BIM地图环境下的测试结果

表3 BIM地图下4种算法指标对比