多点加工问题的最短时间路径规划策略及验证 - 钻孔/点焊作业路径规划的优化方法

HOS T E D B Y可在www.sciencedirect.com网站上查阅计算设计与工程学报3（2016）132www.elsevier.com/locate/jcde钻孔/点焊作业张强，赵中国科学院数学与系统科学研究院，北京，中国接收日期：2015年3月24日;接收日期：2015年10月13日;接受日期：2015年10月202015年11月14日在线发布摘要针对钻孔/点焊作业中的多点加工问题，提出了一种最短时间路径规划策略。通过优化给定点的行程计划和点间的详细传递路径，在充分利用机器人动力学性能的前提下，实现了最短时间的加工任务根据钻孔/点焊作业的起停运动，将路径规划问题转化为旅行商问题（TSP）和一系列点对点最短时间转移路径规划问题。采用三次Hermite插值多项式对传输路径进行参数化，并对路径参数进行优化，使点到点传输时间最短以点-点转移时间作为TSP参数，构造了一种新的时间指标最小的TSP采用经典的遗传算法求解最优出行计划。以三自由度机器人的几个最短时间钻孔任务为例，验证了该方法的有效性&2016 年 CAD/CAM 工 程 师 协 会 。 由 Elsevier 制 作 和 主 持 。 这 是 一 个 在 CC BY-NC-ND 许 可 证 下 的 开 放 获 取 文 章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。关键词：最小时间;混合整数;路径规划;点到点运动;钻孔/点焊任务1. 介绍机器人最短时间运动规划问题在工业应用中得到了广泛的研究，并提出了几种有效的求解方法。针对沿给定路径的最短时间运动规划问题，Bobrow等人[1]提出了一种相平面分析方法，以获得具有约束力矩的最短时间运动轨迹。Zhang等人[2]用贪婪搜索算法和Zhang等人[3，4]用凸优化方法解决了类似的问题。对于更一般的最小时间点到点运动规划问题，解决方案变得复杂，因为路径和沿路径的运动需要同时优化。Bobrow[5]应用相平面分析方法计算沿给定路径的最小运动时间，然后通过在可行路径空间中搜索最小时间路径与上面提到的单一运动规划问题不同，在制造业中存在一类称为多点制造的复杂任务，例如钻孔[6，7]，点焊和装配[8]。这些任务有许多无序点，因此有必要规划一个最优策略，以有序的方式遍历所有期望的点，同时满足最小距离，最小时间或最小能量等要求。结果表明，所研究的钻孔/点焊任务可以用性能受限的旅行推销员问题（TSP）[9由于TSP问题的计算复杂度高，其求解一直是一个开放性问题.目前，TSP可行解的分类方法主要有枚举法、动态规划法、分枝定界法和智能优化法http://dx.doi.org/10.1016/j.jcde.2015.10.0042288-4300/2016 CAD/CAM工程师协会。&由Elsevier制作和主持。这是一个在CC BY-NC-ND许可证下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。Q. 张曼-Y. 赵/计算设计与工程学报3（2016）132133¼ð Þ ð Þ ð Þð Þ¼¼8>X不>ð Þ<>ð Þð Þ联系我们：FG¼¼nc>Wi½1;1;N;1]nc;>¼ð Þ ð Þ(such如遗传算法（GA）[12]、模拟退火（SA）、粒子群优化（PSO）等）。为了简化问题，多点制造的常用路径规划策略假设任意两点之间的转移路径是直线，并且该问题可以被描述为具有最小距离指标的TSP[11]。然而，Bobrow[8]和Dubowsky和Blubaugh[9]指出，由于机械手运动动力学和重力力矩的非线性表达式，最小时间路径和最小距离路径是不等价的，甚至从点i到点j的最小时间路径也不同于点j到点i的路径，因此除了优化设定点的行程计划外，还需要优化加工点之间的转移路径以获得最小转移时间。研究了多点加工的最短时间路径规划问题。由于设定点的行程方案和点间的详细转移路径必须同时优化，因此构造了一个混合整数最优控制方程来描述该问题。基于钻孔/点焊作业中的起停运动，该问题可进一步转化为一个纯整数线性规划问题和一系列点到点最短时间转移路径规划问题。在本文中，一个典型的遗传算法（GA）被应用于解决所产生的整数线性规划问题。采用三次Hermite插值多项式对传递路径进行参数化，并对路径参数进行优化，获得最小点对点传输时间。科里奥利力，其中向心力矩与q_2i成正比，而科里奥利力矩与q_iq_j成正比，GqARn是重力引起的力矩的矢量，即使在机器人静止或缓慢运动时，它也总是存在，n3.本文的目标是规划一条合理的路径，使机械手在满足动力学约束的条件下，一次完成所有给定点的加工任务，同时任务时间最短。设nc表示任务点的数量。 将p1;p2; p n;pnc定义为任务空间中与nc个钻孔点和piAR3相对应的效应器位置。运动每个接头的性能受到扭矩约束的限制，-τBrτrτB：102μm以及关节速度约束，-q_Brq_rq_B;当jointvelocitysatisfiesp_Jqq和Jq表示正运动学映射的雅可比矩阵。由于在钻孔/点焊过程中末端执行器需要保持静止，因此我们有q_i0对应于任务空间中的第i个点位置pi，其中i1; 2;n;c。首先，期望的最小时间路径规划问题用于钻孔/点焊任务的材料具有以下配方。minTf格利特qi-QWi 1/40;q_i<$0;i<$1;2;nc;2. 问题描述在实际应用中，通常要求六自由度机器人操作器能够获得末端执行器的自由位姿输出。六自由度机械臂的常见构型是前三个关节用于定位末端执行器的位置，后三个关节通过协调实现姿态调整。在本文中，我们专注于在每一个时间的位置优化和执行器的方向可以自动计算，根据制造要求。因此，这里只讨论机械手的前三个关节。建立了前三关节机械手的动力学模型M其中qARn表示关节角位置矢量，τARn表示关节力矩矢量，M qARn~n是对称的机械手惯性矩阵，其中对角元素Mj，j表示关节j的惯性，非对角元素Mi，j表示关节j的加速度与关节i上广义力的耦合，CqARn~n包含离心力的信息，时间：1/1M-τBrτrτB;-q_Brq_rq_B;>qAΩq：其中，Qq1;q2;qncn n包含任务点s的所有关节位置，并且dq_i表示任务点s的关节速度，WAZnc~nc作为使能开关，以确保机械手通过其中，WiA 0; 1 nc是一个n c维列向量，Ωq表示关节位置的几何约束，0 t1ot2ootncTf.问题（4）是一个典型的混合整数最优控制问题.与Dubowsky和Blubaugh[9]类似，由于每个关节的运动速度需要在任务点处降至零，因此问题（4）实际上可以分解为一个最小时间TSP和一系列只有连续变量的点对点最小时间路径规划子问题。本文采用直接参数化方法求解每个点到点路径规划子问题，得到最小转移时间Tij，然后构造最小时间TSP，并采用典型的遗传算法（GA）求解4Þ134Q. 张曼-Y. 赵/计算设计与工程学报3（2016）132>：.Σ半]ðÞ3232如果TT路径variableu/r r，则问题（5）可以重写。>-τBrτsrτB;-q_Brq0u;sparq_B;>q_=0;q_=0。不>0;uu;b0一8>>-3. 子问题解决方案-获得转移路径和Tij从点qi可以用公式表示为通常，问题（12）可以用CVP、联立逼近等常用的直接参数化方法近似为一个NLP问题，然后用SQP、BFGS等方法求解。然而，一方面，从Equ。（十一）min格利特Tij我们得到问题（12）关于路径变量u之间没有明确的相关性，MτBrτrτB;-q_Brq_rq_B;时间：IJ优化目标和路径变量u。另一方面，我们可以看到运动变量a;b是线性的，问题（12）的约束函数和优化目标的凸性。基于上述，合理的巢q10qi;qT ij <$qj;qAΩq：为了生成平滑的传递路径，采用三次Hermite多项式对路径进行近似，定义路径参数为sA0; 1，则从点i到点j的参数路径可以描述为：qsh00sqih10srih01s qjh11srj;sA ½0;1]6其中，ri表示路径的初始斜率，并且rj表示最后的斜坡。（6）中的Hermite基是H00 ¼2s- 3s-1;本文提出了优化策略[8，13]。假设在问题（12）中路径变量u是固定的，则可以实现凸优化解，因为问题（12）此时具有凸优化问题公式。因此，对于对应于任何可行非奇异路径的每个变量u，存在唯一的最优变量对a*;b*和唯一的最小转移时间Tij*。然后，最小时间点到点路径规划问题可以进一步描述为以下优化问题。min.Tij*m;s：t： q<$u;s<$AΩq：<$13<$h01¼ -2s33s2;的 两 水平 巢 优化 战略 为解决h10 ¼s-2ss;ð7Þ问题（13）如图所示。 1，其中λ是搜索步长h11¼ s3- s2：则路径的梯度信息为参数s是在每个NLP循环中，d是基于负梯度方向计算的搜索方向。在实践中，问题（13）可以使用现有的NLP求解器，如SQP，BFGS等来解决。q0sdqh0sph斯图尔赫斯拉普什ðsÞr;ð8Þds00id2q″10 我″01j″11J″q"sds2h00spih10srih01spjh11srj：9接头速度可以等于q_tq0s ts_t：10关节扭矩变为τ¼mðsÞs€þcðsÞs_2þgðsÞ;ð11Þ其中，msMqsq0sARn;csMq s q“s Cq s;q0sq0sARn;gsGqsARn：因此，在问题（5）中需要优化的变量是路径斜率ri;rj和参数加速度变量sωtω。 定义新的变量a <$s_2和b <$s。德费恩我 ;j作为下面的参数空间中的最优控制问题minTijR1p1ds时间：8smu;sbcu;sa gu;s;q_u;0^0;q_u;1^0;qu;0pi;qu;1pj;：qu;sAΩq：ð12ÞFig. 1.两级嵌套优化策略求解点对点最短时间换乘路径规划问题。000ð5ÞQ. 张曼-Y. 赵/计算设计与工程学报3（2016）132135¼¼¼¼ þ联系我们>：WAf0;lg;DAf0：ijii¼¼>Xð Þð Þ¼ð Þð Þð Þ¼>1/2XX4. 主问题-多点最短时间遍历多点制造应用中的最优路径规划问题实际上可以描述为一个TSP问题。将矩阵D定义为TSP的测量矩阵。则对于最小距离策略，对于任意i和j，存在Dij Dji，这意味着从点i到j的距离等于从j到i的距离。然而，对于最小时间策略，D的元素表示传输时间，写为Dij Tij* [8][9]在大多数情况下，条件Dij Dji多点加工过程的最短时间路径可以通过求解以下整数线性规划问题来获得。ncnc最小Tf¼Wij Dij8>Xncncð14Þ基于GA的路径选择过程：步骤5. ii1.结束时。结束程序。5. 案例研究在这一部分中，一个钻孔任务在Y-Z平面上的研究，以验证所提出的方法的有效性。案例研究分为三个部分：一是验证了点-点最短时间换乘路径规划的有效性;二是将最短运行时间调度与最小行程距离调度和最小角度行程调度进行比较，验证了算法的优化性;三是通过100个点的任务验证了算法的实用性。一个三自由度机械手（如图2所示），并且所有三个接头的扭矩界限设定为[140; 140; 50]N.m.。Y-Z工作平面放置在s： t： Wij1;i 1; 2;nc;第1页本文采用经典的遗传算法搜索最优路径，模拟自然选择、遗传和变异过程。算法程序编程如下：基于GA的路径选择过程：输入：点的个数nc，计算出的测量矩阵D。输出：优化的遍历路径和最短时间的运动轨迹。操作步骤：初始化：populationsize;i0;Number ofgeneration;在问题（14）中的准则下初始化遍历顺序种群Pa_pop irandperm（pop_size，nc基于测量矩阵D，评估总体Pa_pop i的每个个体的相应最小时间，并选择最佳解Tmin*。回路：While（iomax_gen）步骤1. 在问题（14）的准则下，通过应用交叉和变异操作从Pa_pop i再生后代群体Ch_pop i步骤2. 根据矩阵D，求出种群Ch_pop i中每个个体对应的最小时间，并选择最优解Tmin;步骤3. 更新最佳解决方案Tmin*Tmin（如果当前）Tmin*4T min;步骤4. 从Pa_pop菜单中选择新的PopulationPa_ pop菜单和Ch_popi;x机器人基座前方1 m和路径几何形状将约束设置为工作平面与机器人效应器之间无干涉。如图3所示，在Y-Z平面上放置八个钻孔点。基于运动学逆解，可以计算出每个钻孔点5.1. 点-点最短时间传递路径试验以3点到8点的换乘路径规划为例，验证了该方法的有效性。初始路径是连接两点的直线。初始路径长度为0.8879m，对应的最小运动时间为0.4839 s。所有三个接头的最佳扭矩如图5所示。利用第3节的方法，计算出从点3到点8的时间最优转移路径，如图4所示。最小时间路径的长度为1.0346 m，图二. 模拟机器人用于钻孔任务。Wij<$1;j< $1; 2;nc;136Q. 张曼-Y. 赵/计算设计与工程学报3（2016）132图三. Z-Y平面中的任务点。见图4。 Z-Y平面中的初始路径和优化路径。图六、优化路径下每个关节的最小时间扭矩曲线见图7。分别给出了初始直线轨迹和优化最短时间轨迹的最短时间进给速度曲线时间最优路径的速度可行空间比初始路径的速度可行空间大，因此可以允许更快的运动速度和更小的转移时间。（图第七章）5.2. 多任务点最短时间遍历测试表I. 典型遗传算法集。图五、初始直线路径的每个关节的最小时间扭矩曲线相应的最小运动时间为0.4510 s。三个关节的最佳力矩如图所示。 六、根据如图1A和1B所示的继电器式扭矩结构，如图5和图6所示，这意味着相应的速度轨迹已经接近最佳。图6给出了初始路径和最佳路径的优化进给速度曲线。在本测试中，最小时间路径比直线路径长，但相应的运动时间可以pop_size40max_gen100总突变率75%突变操作翻转25%掉期25%滑动25%通过应用5.1中的结果，我们可以获得最小操作时间策略的测量矩阵D该方法还可以方便地计算出最小行程距离策略和最小角行程策略 如图 8、旅游时间表Q. 张曼-Y. 赵/计算设计与工程学报3（2016）132137----------------三种策略是不同的。在这里我们记录测试数据并将其列出如下。(a). 最小行程策略的行程表为7-6-5-3-2-1-4-8-7，相关路径长度为5.456 m，总角行程为11.046 rad，总运动时间为3.25 s。每个传输路径的长度为0.555米0.555米0.887米0.504米0.8米0.8米0.8米0.555米对应的最小转移时间为0.43s-0.38s-0.48s-0.33s-0.42s-0.41s-0.41s-0.39s。见图8。分别针对最小运行时间策略、最小行程距离策略和最小角行程策略(b). 最小角行程策略的行程表为7-6-5-2-1-4-3-8-7，相关路径长度为5.613 m，总角行程为9.386 rad，总运动时间为3.344 s。每条转运路径的长度为0.564 m 0.563 m 0.855 m 0.827 m0.827 m 0.527 m 0.888 m0.563米。及其对应的最小转移时间是0.44秒0.40秒0.44秒0.41秒0.42秒0.36秒0.48秒0.39秒。(c). 最小运行时间策略的行程表为5-6-3-7-8-4-1-2-5，相关运动时间为3.04 s，路径长度为5.858 m，总角行程为11.495拉德每个传输路径的运动时间为 0.38秒0.35秒0.35秒0.37秒0.39秒0.41秒0.40秒0.39秒。相应的传输路径长度为0.571米0.688米-0.682米0.565米0.829米0.835米0.836米0.852米。在该测试中，最小时间运动的路径长度比最小距离运动的路径长度长7.3%最小时间运动的总角行程比最小角行程运动的总角行程大22.5%与最小行程策略相比，该策略的最优运动时间减少了6.5%，与最小角行程策略相比减少了9.1%。5.3. 实用性试验在本节中，通过执行一系列钻孔任务，分别为10，25，50和100点，测试所提出的算法的实用性 任务点如图所示。9.第九条。图9.第九条。测试示例（从左起，10分，25分，50分，100分）。表1三种策略的运动性能比较。试验（点）行程距离（m）角行程（rad）运行时间（s）我们的Alg最小直径闵昂我们的Alg最小直径闵昂我们的Alg最小直径闵昂103.15973.14033.60615.78655.56644.65402.41132.57523.5774253.79233.74325.21416.21476.01435.49284.12554.45787.7990506.87686.694410.637811.279911.09519.94568.03448.589217.396510012.761612.490320.102320.305119.825717.475814.929116.061633.1522*Min D是最小行程距离的缩写，Min Ang是最小角行程的缩写-138Q. 张曼-Y. 赵/计算设计与工程学报3（2016）132~0.70.60.50.40.30.20.1010 25 50 100任务点图十一岁100分任务的时间最佳行进路径见图10。与最小行程距离策略和最小角行程策略相比，性能有所提高。表2三种策略的计算成本比较。测试计算时间（H：MIN：S）我们的算法最小距离最小角度10分时间00：02：39时间00：00：15时间00：01：4925分时间00：15：10时间00：00：35时间00：12：3650分时间01：20：23时间00：02：10时间00：50：49100分时间02：53：56时间00：11：40时间01：47：13*计算时间是在笔记本电脑平台Core i3条件下获得的2.53 G，2 GB RAM，Matlab环境.表1中列出了最小操作时间策略、最小行程距离策略和最小角行程策略之间的性能比较。 由表1可知，虽然最小操作时间策略的行程和角位移比其他两种策略大，但操作时间明显比它们短。 图图10示出了与最小行程距离策略和最小角行程策略相比，我们的策略的操作时间改善。根据四个实例的测试结果，该算法可以提高生产率约7% 55%，与现有的算法相比。表2记录了这三种策略的计算时间本文不涉及算法复杂度的理论分析然而，通过使用测试结果，我们可以检查算法的复杂度。从测试结果可以看出，该算法是耗时的。这是因为在所提出的算法中，必须执行大量的优化子过程来计算然而，由于该算法是并行执行的，我们认为该方法的计算成本是可以接受的。最后，我们绘制了100点任务的时间最优旅行路径，如图所示。 十一岁6. 结论针对钻孔/点焊作业中的多点加工问题，提出了一种最短时间路径规划方法。在满足机械手动力学性能的前提下，通过同时优化各点的行程计划和各点间的详细传递路径，得到了最短时间路径算例结果因此，所提出的多点任务的最小时间策略是可行的。引用[1] Bobrow JE，Dubowsky S，Gibson JS.机器人机械手沿指定路径的时间最优控制。 国际机器人研究杂志1985; 4（3）3-17.[2] 张凯，高晓松，李海波，袁春明.数控机床沿曲线刀具轨迹进给速度规划的贪婪算法。 机器人计算集成制造2012; 28：472-83。[3] 张强，李世瑞。数控加工中最短时间光滑轨迹的有效计算。Int JAdv Manuf Technol 2013; 68（1-4）683-92。[4] 张强，李思仁，高晓生.路径跟踪机器人实用光滑最短时间轨迹规划。 Am Control Conf，USA，Jun 2013：17-9.[5] 博布罗·J以最短时间为准则之最佳机器人路径规划IEEE J Robot Autom1988;4（4）443[6] Erkorkmaz K，Alzaydi A，El fizy A，Engin S. 5轴在线激光打孔的时间最优轨迹生成。CIRP Ann-Manuf Technol2011; 60：411-4.[7] Erkorkmaz K，Alzaydi A，El fizy A，Engin S.用于5轴在线激光钻孔的时间优化孔序列规划。CIRP Ann-ManufTechnol 2014; 63：377-80。[8] 黄天，王平峰，梅太平，赵晓梅，谢伟东。2-DOF平移并联机器人取放作业的时间最小轨迹规划。CIRP Ann-Manuf Technol2007; 56（1）365-8。[9] Dubowsky S，Blubaugh TD.规划时间最佳的机器人机械手运动和工作地点点到点的任务。IEEE TransRobotAutom 1989; 5（3）337-81.[10] Petiot JF，Chedmail P，Hascoet JY.对机器人轨迹调度的贡献。机器人计算-集成制造1998; 14：237-51.业绩改善（%）与最小距离相比与最小角度Q. 张曼-Y. 赵/计算设计与工程学报3（2016）132139[11] Th Zacharia P，Aspragathos NA.基于遗传算法的机器人任务优化调度。机器人计算-集成制造2005; 21：67-79.[12] Qu L，Sun R.遗传算法求解旅行商问题的一种协同方法。InfSci1999; 117：267-83.[13] Shiller Z，Dubowsky S.机器人机械手在障碍物存在下的全局时间最优运动的计算。IEEE TransRobotAutom 1991; 7（6）785-97.