带夹持装置的折叠纸箱的运动规划方法【中文10100字】
收藏
资源目录
压缩包内文档预览：
编号：14918103
类型：共享资源
大小：4.87MB
格式：ZIP
上传时间：2019-02-19
上传人：闰***
认证信息
个人认证
冯**（实名认证）
河南
IP属地：河南
20
积分
- 关 键 词：
-
中文10100字
夹持
装置
折叠
纸箱
运动
规划
计划
方法
法子
中文
- 资源描述：
-
带夹持装置的折叠纸箱的运动规划方法【中文10100字】,中文10100字,夹持,装置,折叠,纸箱,运动,规划,计划,方法,法子,中文
- 内容简介：
-
带夹持装置的折叠纸箱的运动规划方法陆良.Srinivas Akella，IEEE会员摘要：组装后封装像电话和双向无线电此类产品是一项常见的制造任务。纸箱折叠是一种通常由人工操作员或固定自动化执行的包装操作。我们提出了一种使用固定装置折叠纸板箱的灵活方法;将纸箱坯料通过机器人夹具移动折叠。该方法使用可互换的夹具来实现产品模型之间的快速转换。我们概述了在给定纸箱和折叠序列的情况下设计夹具的方法。我们提出了一种实施的运动规划算法，通过将其作为具有旋转关节和分支链接的多自由度机器人操纵器进行建模，生成纸箱的所有折叠序列。折叠夹具将纸箱运动约束到由其配置空间中的线段组成的路径。我们描述了这些纸箱机器人的有效路径集，并使用运动规划器生成它们。为了说明这种方法，我们为一个简单的纸箱选择了折叠顺序，设计了一个夹具，并展示了用工业机器人从空白处折叠纸箱。关键词：纸箱折叠，灵活制造，包装，机器人运动规划。1.简介装配后封装产品是一项常见的制造任务。纸箱从平板纸板坯料折叠起来用于包装电话，双向无线电和汽车组件等产品。纸箱折叠操作发生在包装，分配和仓储中心，通常由操作人员或固定自动化执行。由人类折叠的纸箱需要灵巧地操纵纸箱并且可能导致重复的压力损伤。商业纸箱折叠机不是为了用于处理由产品和线路变化所必需的不同纸箱样式而设计的。我们提出了一种使用固定装置折叠纸箱的方法，其中通过用机器人将纸箱坯料移动通过夹具来折叠纸箱坯料。这些夹具可以互换，可以在产品型号之间实现快速转换。折叠带有夹具的纸箱需要为纸箱生成有效的折叠序列，为选定的折叠序列设计夹具，并使用机器人在夹具上实施折叠操作。纸箱是铰接式结构，我们将其模型化为具有旋转接头和分支链接的机器人机械手。我们提出了一种运动规划算法，可以自动生成一类纸板箱的折叠顺序，这些纸板箱是从带有自锁卡口的扁平纸箱坯料折叠而成的（图1）。我们概述了在给定纸箱和折叠序列的情况下设计夹具的方法。折叠夹具将纸箱运动约束到由其配置空间中的线段组成的路径。我们描述了具有多个自由度的这些纸箱机器人的有效路径集，并使用运动规划器生成可行的纸箱折叠序列。为了说明该方法，我们为一个示例纸箱选择了一个计划生成的折叠序列，使用设计程序设计了一个夹具，并展示了使用AdeptOne机器人从空白处折叠纸箱。图1.无线电纸箱坯料的初始配置和折叠配置。纸箱折叠过程的自动化涉及若干子任务，包括自动折叠序列生成，自动折叠夹具设计，执行机器人的运动规划，纸盒形状的可折叠性设计，以及用于从库存切割的纸箱坯料的有效布局。在本文中，我们解决了第一个必要的任务：生成物理上有效的折叠序列，以便在生成固定装置和驱动机器人的运动期间进行考虑。这项工作是我们实现夹具可折叠序列和自动设计纸箱折叠夹具的长期目标的第一步。该未来的工作将需要考虑致动机器人的可行运动，保持工具约束和折痕的刚度。纸箱折叠是一项涉及操纵结构的任务。折叠纸盒通常比用于折叠纸盒的机器人具有更多的自由度。我们的方法是使用运动规划器来帮助人类设计师设计最小的复杂硬件。规划器可以用于类似的形状修改制造任务，例如钣金弯曲或来自铰接2D元件的3D微电子机械结构（MEMS）的设计。在对第II节中的相关工作进行审查之后，我们在第III节中概述了给定纸箱和折叠顺序的夹具设计方法。然后，我们描述了纸箱折叠问题，并提出了运动规划算法，以便在第IV节中生成折叠序列。在第五节中，我们将介绍不同纸箱样式的方法。我们提供了一个针对示例纸箱设计的夹具和在第VI节中使用机器人实现的折叠序列。最后，我们总结并概述了第VII节中的未来工作。这项工作的部分内容在1中更早出现。2.相关工作包装百科全书2和Hanlon 3以及Friedman和Kipnees 4的书籍提供了包装的介绍和概述。用于工业用途的纸箱折叠机通常可用于在其最终配置中胶合或胶粘的纸箱。我们知道至少有一台商用机器可以折叠本文所考虑的纸箱类5，但机器不能轻易地适应不同的纸箱类型。该专利文献描述了几种纸箱折叠设计，其配备有旋转轮6，7，螺旋杆或不同方向的螺旋带8，9或可旋转的杆夹10，其逐渐折叠襟翼作为纸箱空白通过。具有大量移动元件的这种装置不能容易地修改以处理其他纸箱。纸箱折叠的问题与通过弯曲从金属板坯料制造三维钣金零件的问题具有几何相似性。两者都涉及在形状变化时操纵对象。然而，在至少两个方面，金属板弯曲与纸板折叠不同。首先，弯曲的金属板部件保持弯曲。其次，同时的金属板弯曲通常仅沿共线进行。弯曲顺序的确定是与弯曲工具的选择相结合的组合问题。大多数方法都侧重于生成可能不太理想的可行解决方案。 de Vin等。 11描述了一种计算机辅助工艺规划系统，用于确定钣金制造的弯曲顺序。它们为带有直弯曲线的钣金零件产生反向弯曲顺序，弯曲在折弯机上。系统使用规则来提高准确性，最小化处理，选择工具，并避免零件和打孔工具之间的碰撞。Shpitalni和Saddan 12描述了一种自动生成最多18条弯曲线的弯曲序列的系统。它们使用特定领域的成本，例如工具更换次数和零件重新定向，以及基于所用工具数量和弯曲长度和位置的启发式方法来指导A *搜索算法。Radin等。13提出了一个两阶段算法，首先使用碰撞避免试探法快速生成一个可行的弯曲序列，然后搜索成本较低的解决方案，而不会影响其时间限制。Inui等。14开发了一种用于弯曲钣金零件的自动计划器。古普塔等人。15描述了一个全自动的工艺规划系统，用于计划和执行机器人金属板弯曲折弯机的弯道。Wang 16开发了将金属板材产品分解成组件的方法，以便在切割，弯曲和装配过程中易于制造。特别是，他将3-D产品展开为2-D模式，并识别出可以避免与工具发生碰撞的展开弯曲序列。 Wang和Bourne 17使用形状对称来减少钣金布局规划，弯曲规划，零件堆叠和装配的规划复杂性。纸箱折叠的几何约束与装配规划中的几何约束相同。通过拆卸排序进行装配规划是一种常见技术。 Mattikalli和Khosla 18提出了一种方法，用于从接触几何中确定装配体中物体运动的约束。 Wilson和Latombe 19开发了无方向阻塞图，以有效地生成单调双手装配计划。 Wilson 20考虑了装配工具对装配的几何可达性限制。目前机器人技术研究的趋势是降低复杂性设备21，使用简单，廉价，坚固的执行器和传感器。特别感兴趣的是Goldberg和Moradi 22关于装配机器装配规划的工作，这些装配机器执行流水线系列的零件旋转和垂直插入，只需要一个或两个自由度。我们将纸箱模型化规划为具有许多自由度，可使用运动规划技术生成折叠序列的机器人操纵器， Latombe的书中23全面介绍了运动规划。为具有多个自由度的机械臂开发实用的运动规划器是一个正在进行的研究领域。 Barraquand和Latombe 24开发了一种随机路径规划器（RPP），它使用潜在的场技术和随机搜索技术的组合。RPP可以有效地为具有大量自由度的机器人生成运动计划。 Kavraki等。25构建高维配置空间中路径规划的概率路线图。他们的方法首先通过在学习阶段期间在配置空间中采样点来开发路线图的图形表示。在查询阶段，将搜索路线图以查找连接起始配置和目标配置的路径。Gupta和Guo 26开发了一个带有回溯的顺序框架，用于具有多个自由度的机器人的运动规划。他们将问题分解为每个链接的一系列规划问题，并在没有找到特定链接的解决方案时进行回溯。 Amato等。 27描述了一种基于障碍的概率路线图技术，用于在混乱的环境中进行运动规划，该技术对配置空间障碍物上或附近的点进行采样。 Lozano-Perez 28开发了一种简单的算法，该算法使用近似细胞分解来计划连续机器人操纵器的无碰撞运动。该算法是机器人自由度的指数。他生成了一个有效的自由空间近似值，从配置空间的一维切片中递归建立。我们使用他的递归树数据结构，其叶子代表机器人的合法配置范围。最近在计算几何方面的工作涉及到多面体和它们可以展开的多边形形状，并且开发了与折纸艺术的联系。 Lubiw和ORourke 29提出了一种动态编程算法，用于确定给定的多边形是否可以折叠成凸多边形。 Biedl等人。30研究两类非凸正交多面体的展开。德马恩等人。 31表明，方形纸可以折叠成任何连接的多边形区域，而且，任何多面体都可以从单张纸折叠。纸箱折叠中的几何问题类似于从二维铰链元件创建三维MEMS的几何问题。 Pister等。32描述了由表面微机械加工制成的二维铰接多晶硅结构产生的各种三维结构。Syms 33提出了一种自组装三维微结构的方法，该方法依赖于由于来自可熔材料的表面张力而使二维表面微加工零件旋转。 Yi和Liu 34开发了一种用于铰接平面微结构的磁面外致动的方法，以创建自锁3-DMEMS器件。3.用固定装置折叠纸箱坯料是一种扁平纸板切口结构，由一组面板组成，折叠折痕将相邻的连接面板分开（图1）。纸箱折叠通常由人工进行，他们用双手折叠纸箱并保持纸箱面板的中间折叠配置。纸箱通常可以以折叠顺序不同的多种方式折叠到其目标状态。有关示例折叠顺序，请参见图2。我们使用固定装置将纸箱坯料折叠成纸箱。我们设计夹具形状以匹配纸箱以选择折叠顺序，以便通过与夹具接触移动纸箱沿其折痕折叠（图3）。为了在折叠时将纸箱折叠起来，我们在折痕处放置一个垂直于纸箱面板的墙壁元件。 该壁使纸板面板沿折痕旋转并保持面板的折叠形状。对于选定的折叠序列，选择沿着运动方向的壁之间的距离以确保折叠以期望的顺序发生。折壁位于经验确定的距离折痕的距离，以确保成功折叠。图2.折叠顺序示例。折痕用虚线表示。图3.设计折叠夹具。创建夹具元件以执行左侧所示的折叠序列的每个折叠以进行向下的纸箱平移，导致夹具F1显示在右下方。 在每个阶段，创建或修改夹具壁以完成相应的折叠。 请注意，不受限制的襟翼可以在折叠的中间阶段弹回，并且需要额外的折叠来折叠上襟翼。通过夹具的恰如其分的设计，可以同时进行纸箱的多次折叠。使夹具成为被动结构并使用工业机器人将纸箱移动通过夹具导致具有少量移动元件的坚固设计。 由于折叠顺序仅指定纸板面板的相对方向，因此给定的折叠顺序可以在世界框架中具有多个实例，每个实例可以产生不同的折叠夹具。4.折叠序列的生成识别可行的折叠序列是夹具设计过程的核心。我们的方法是生成所有有效的折叠序列，与夹具形状无关，供人类设计师进行评估。我们将折叠序列的生成表示为机器人运动规划问题。 我们将纸箱建模为具有旋转关节和分支连杆序列的关节机器人（图4）。由于纸箱具有多个自由度（在我们的示例中为12个），我们利用纸箱形状的对称性来减少要考虑的关节数量。假设纸箱一侧的面板运动与另一侧的面板相同。 从初始机器人配置到目标机器人配置的每个有效路径确定折叠顺序。 我们寻求生成所有可能的路径，并使用其中一个来设计折叠夹具。图4.无线电纸箱作为铰接式机械手机器人，具有旋转关节和分支连杆序列。 纸箱形状的对称性足以仅将纸箱的一半建模为机器人。运动规划问题如下所述。鉴于纸箱形状及其作为机器人的运动表示，找到其初始配置和目标配置之间的所有物理上有效的路径。物理上有效的路径是由于抽象夹具而满足运动约束的路径，并且不涉及纸箱面板的自动收集。我们识别独立于夹具形状和致动机器人的可行运动的有效路径，并且不将致动机器人或夹具建模为障碍物。从运动计划的角度来看，由于以下原因，产生折叠序列的问题具有挑战性。1）纸箱机器人具有大量的自由度，即使在考虑纸箱对称性之后，示例纸箱的自由度也在7到9之间。2）纸箱机器人是具有分支链接序列的非串行机械手。3）为了生成所有折叠序列，我们寻找所有可能的路径，这与寻找从初始配置到目标配置的单个路径的大多数运动规划算法不同。我们可以考虑将纸箱从展开配置移动到折叠配置，或从折叠配置移动到展开配置的联合动作。由于折叠配置对允许的关节运动具有比展开配置更多的限制，因此考虑将纸箱从其折叠配置展开到其展开配置更有效。在下文中，我们生成展开序列而不是折叠序列。A.配置空间表示对象的配置是一组参数，它们完全指定对象的每个点相对于固定参考帧的位置。对象35的配置空间是对象的所有配置的空间，其中每个坐标代表一个自由度。例如，关节机器人的关节角度集合定义了配置空间，该配置空间通常用于旋转关节。由于与其他物体碰撞或由于自碰撞而被禁用于机器人的配置构成了配置空间障碍物的集合。机器人的一套合法配置构成了它的自由空间。具有关节的纸箱的配置空间，其中关节具有下限 和上限。我们使用由Lozano-Perez 28开发的用于串行操纵器的递归树结构来表示使用配置空间的一维切片的纸盒机器人的配置空间。树的每个级别包含一组对应于机器人的一个关节的离散间隔的单元。树的叶子是表示被识别为属于或的一系列机器人配置的单元。我们扩展Lozano-Perez的树形表示来处理纸盒机器人的分支链接。我们选择一个基本面板并像以前一样计算最长链接链的树表示。对于来自此主链的每个链接分支序列，我们创建树的其他级别。第一个分支序列的级别附加到主链树的叶节点。链接的每个分支链按顺序表示，并且连接链的水平连接。结果树中的叶节点表示配置空间中的单元，并对其是否处于可用空间进行编码。我们不会将夹具或驱动机器人建模为障碍物，并假设没有外部障碍物与纸箱碰撞。由于移动面板在纸板折叠时可能与其他面板碰撞，因此配置空间障碍物对应于纸板面板之间的碰撞。在生成配置空间树时，我们检查每个旋转面板与固定面板的碰撞36。 我们当前的实施假设除了移动接头之外的所有接头都固定在其定向范围的中间。Lozano-Perez树表示的一个优点是可以通过扫描体积计算来补偿关节角度的变化。这给出了自由空间的保守表示，因此保证生成的路径无冲突，尽管可以修剪一些有效路径。B.运动规划制定生成折叠序列的最简单方法是假设一次只能移动一个关节，并且每个移动关节单调移动到其目标方向。所以我们可以测试了！通过检查序列的每个阶段，如果移动的关节可以从其初始方向到达其目标方向而没有任何中间配置，则可能的联合序列用于可行性。然而，这种方法只给出了折叠序列的一个子集，因为它无法生成多个面板同时移动的解决方案。为了生成多个关节可以一起移动的折叠序列，我们首先描述机器人在被抽象（未实例化）夹具折叠时在其配置空间中可以采用的路径。每个接头都是未致动的，当它所连接的面板接触夹具的壁时开始旋转。我们将所有关节建模为以相同的恒定角速度运动，并假设一旦关节开始移动，它将单调旋转至完成。 （第IV-D节讨论了关节以不同的速度旋转时的情况。）关节可能同时开始移动或延迟运动。我们寻找从折叠配置到展开配置的纸箱路径。我们通过这个序列代表ith联合序列，开始在之前为同时开始移动为，开始后依次为，等等。（注意，我们用来表示关节以及它的角度值。）对于每个这样的关节序列，我们还必须识别连续关节之间的旋转延迟。延迟意味着在关节旋转一个角度后关节开始旋转。因此，我们表示对应于关节序列的延迟序列为，通过关节旋转到，关节的运动以时间表示 (1) 对于指定的关节序列和延迟序列，关节角度之间的相互关系可以通过以下运动约束等效地表达： (2)初始配置限制是目标配置约束是延迟可以假定间隔中的任何值0,。如果为零，则两个关节和同时开始移动，如果是，则关节在关节完成其运动后才开始移动。对于我们研究的纸箱和 。 因此，这些纸箱机器人的配置空间为90,180，并且可以采用0到90之间的任何值。当n关节处于运动状态m时，存在m-1主动运动约束和主动初始或目标配置约束。每个约束定义了一个约束平面-机器人的三维配置空间，以及总活动约束平面沿一条线相交。因此，机器人的路径由一系列线段组成。路径中的最大线段数2n-1。有关示例3-D情况的示例路径，请参见图5。图5.沿着三维配置空间中的路径的约束平面和线段。C.搜索算法我们的目标是确定纸箱机器人的无碰撞路径。路径或折叠序列由关节序列和相应的延迟序列定义，以使机器人从其折叠配置到其展开配置。有关节的机器人联合序列。为了识别每个可行的关节序列的有效值，我们将每个范围离散化为在其中点采样的间隔。 因此每个联合序列都有可能的延迟序列。 我们必须识别序列中的有效折叠序列。最直接的算法是生成所有联合序列，并且对于每个联合序列，生成对应于每个可能的延迟序列的路径。对于每个路径，如果其任何线段都没有与配置空间障碍物碰撞，则折叠顺序是可行的。我们修改上述算法以更有效地修剪不可行路径。对于给定的联合序列，到目标的多个路径可以共享一个或多个线段。如果线段与障碍物碰撞，则它所属的所有路径都是不可行的。每个部分实例化的延迟序列指定一组线段，并且我们按顺序循环它们。对于每个实例，测试定义的线段以进行合并。如果它确实发生碰撞，则从碰撞线段发出的整个路径组可以被分类为不可行，而不实例化延迟序列的其余部分。对于产生一系列无碰撞线段的延迟序列的每个实例，我们通过利用障碍物的空间相干性找到有效值。如果针对某个值定义的线段与障碍物发生碰撞，则以该邻居的增量值对碰撞池进行单元测试。如果这些是无冲突的，则测试由增量值为可行性定义的新线段。否则再次增加并重复该过程。关于算法生成的示例折叠序列，参见图6。请注意，配置空间的离散化表示和延迟值会导致计划方法可能不完整。也就是说，规划人员可能不会返回一些有效的解决方案。算法的最坏情况是关节数量的指数的复杂。通过识别可以从初始折叠配置首先移动的关节集，我们消除了一些不可行的组合并缩短了搜索时间。 我们测试关节是否可以先移动，检查它是否在旋转少量时是否具有无碰撞配置，使所有其他关节保持在其起始方向。对于可以先移动的每个关节，我们确定可能可能移动的关节组。快速识别可以移动的前两个关节意味着我们只探索一部分联合序列。图6.由算法生成的无线电纸箱的示例（联合）折叠序列具有联合序列（）和延迟序列（90,90,90,90,0.10）。 序列从左到右，从上到下。 底部面板在折叠期间具有恒定的取向。图7. HP纸箱图8.斜面纸箱D.多角速度公式由于所有关节都不能以相同的角速度旋转，我们可以允许每个关节以恒定的角速度旋转， 对于指定的关节序列和延迟序列，关节的运动现在由下式给出 (5) 初始和目标配置约束保持不变。搜索算法类似于相等角速度的搜索算法，另外考虑对于每个联合序列，我们必须考虑所有可能的有效角速度实例。 我们对每个关节允许的角速度进行离散化。当关节可以各自具有角速度时，最坏情况下的运行时间增加了一倍。图9.利用HP纸箱的对称性将模型的关节数量减少到5个。图10.斜面纸箱的对称结构可用于将其模拟为具有镜像关节运动的两个机器人，将要考虑的关节数量减少到5。图11.斜面纸箱的（非）折叠顺序，模拟为两个五关节机器人，具有联合序列（）和延迟序列（90,90,50,90）。E.评估折叠序列运动规划器返回潜在的大量有效折叠序列。设计师必须根据夹具的可折叠性选择序列。通过让设计者指定联合序列来折叠序列以丢弃，可以使折叠序列生成成为交互式的。在选择夹具设计的折叠顺序时，设计者还必须考虑使机器人的允许运动。图6中的折叠序列实例化仅可以使机器人翻折纸箱，而图13中实施的序列也涉及旋转。由于折叠顺序仅指定纸板面板的相对方向，因此可以通过多种方式进行实例化。实例化取决于执行机器人的可行运动，以及它是否只能翻转纸箱或两者都可旋转和平移。即使当纸箱只能进行翻折时，也可以选择几个面板中的任何一个以在折叠期间具有固定的方向。因此，可以针对给定的折叠顺序设计若干不同的折叠固定件。夹具的实例化序列的可折叠性由夹具限制和折痕的刚度决定。因此，实例化的可折叠性可以显着不同。实际上，并非每个物理上有效的折叠序列都保证具有有效的夹具实现。表1 无线电，HP和斜面纸箱样式的比较。 除了相应的10个和18个分辨率的采样分辨率之外，所有分别为10个和18个分辨率的所有分别为所有分子的数量，以及每个分子的抽样间隔数量为10个。 （*）斜面纸箱的路径生成时间是生成每个有效联合序列的单个延迟序列的时间表2当允许多个角度速度时，对称减少的纸盒样式的比较。带有角速度的每个关节旋转关节， 离散联合区间的数量和每个区域的抽样间隔数量为10对于所有具有相应取样分辨率为10度的纸盒。图12.已使用的夹具和AdeptOne机器人。图13.执行的折叠序列包括纸箱的旋转。展开的联合序列是（），具有延迟序列（0,90,90,70,20,0）和角速度三倍于所有其他关节。5.纸箱样式运动规划算法可以为任何纸箱样式生成折叠序列，可以将其建模为具有旋转关节的机器人和没有运动环的链接的分支序列。例子包括HP纸箱（图7）和斜面纸箱（图8）。由于折叠序列的产生是关节数量的指数，我们寻求减少纸箱的模型关节的数量。我们利用HP纸箱的附加对称性将其建模为连续操纵器（图9），将机器人关节的数量从原来的12减少到5.斜面纸箱可以建模为两个具有不同链接的串行机器人尺寸和镜像关节运动（图10），以减少每个机器人的关节数量从12到5。各个机器人的配置空间树是独立计算的，并且共同用于路径规划。纸箱尺寸确定是否必须对相对面板的集合进行测试。斜面纸箱的折叠顺序示例如图11所示。将纸箱建模为具有较少关节的机器人可缩短搜索时间和有效折叠顺序的数量，从而使人工检查更容易。我们假设人类将对称减少的联合表示指定为输入。虽然现有算法可以检测多边形和多面体形状的对称17，但是当对称面板的尺寸不同时，它们可能无法检测到部分对称性，如斜面纸箱中所示。图14.初始纸箱折叠操作，从左到右，从上到下显示。将纸箱坯料转移到夹具中，在夹具中进行关键折痕的预折叠。 然后进行多关节折叠，接着进行襟翼对齐操作和纸箱的旋转。6.执行我们用C +实现了运动规划器，为给定的纸盒机器人生成折叠序列。表1比较了当所有关节具有相同角速度时不同纸箱样式的运行时间和可行解决方案。所有计算都在360-MHz Sun ULTRA 60上进行。在计算配置空间树时，我们当前的实现假设除了移动关节之外的所有关节都固定在其离散间隔的中点。根据关节数量及其运动范围，根据经验选择离散的关节间隔数和离散延迟间隔的数量。表2比较了当每个关节可以以角速度旋转时对称减小的纸箱，其中候选值是根据经验确定的。我们展示了使用具有额外第五关节的AdeptOne SCARA机器人折叠无线电纸箱样式（图12）。图15.在夹具的前半部分继续进行纸箱折叠操作。前面板借助两个气动执行器折叠。 然后使用自锁舌片折叠并固定上翼片。 折叠的纸箱由机器人从夹具中取出并放置以便装载。 序列从左到右，从上到下。执行的折叠顺序包括纸箱的中间旋转（图13）。我们按照第三节的方法，在一个考虑夹具形状和驱动机器人运动的迭代过程中为这个序列设计了一个夹具。夹具由金属板和乐高积木构成，可在设计和测试过程中快速更换夹具。第一组折叠操作发生在夹具的后半部分（图14），第二组折叠操作发生在前部（图15），并通过纸板箱的旋转分开。夹具有两个气动执行器，有助于折叠过程。机器人使用带有真空吸盘的固定板来拾取纸箱。由于保持板被拉伸以实现期望的折叠而不与夹具碰撞，因此当纸箱样式或尺寸改变时可能需要与夹具一起更换。我们使用相同的夹具和固定板进行两个无线电纸箱模型的实验，这两个模型的刚度和折痕位置略有不同。一个模型在10个试验中的9个中成功折叠，而另一个模型在16个试验中的10个中成功折叠。如果纸箱有不希望的折叠，明显的划伤，面板和保持板发生意外碰撞，或者自锁片没有完全插入，则试验被归类为失败。 通过更好的夹具制造可以消除这些困难。 在我们目前的执行中，机器人可以在大约一分钟内折叠纸箱37。对折叠操作进行流水线操作或并行使用多个执行器可以显着缩短执行时间。7.总结我们提出了一种使用可互换夹具折叠纸板箱的灵活方法;将纸箱坯料通过机器人夹具移动折叠。本文作出以下贡献。首先，它通过固定装置识别纸箱折叠的自动化，作为可以应用运动规划技术的新任务。其次，它提出了一种运动规划公式和一种实施的算法，该算法利用对使用固定装置折叠的纸箱运动的约束来自动生成从扁平纸箱坯料折叠的一类自锁纸箱的所有折叠顺序。规划器生成的序列使人类设计者能够可视化和识别夹具可折叠序列并设计相应的夹具。利用纸箱对称性和仔细选择要建模为机器人的面板可显着提高计划效率。为了说明这种方法，我们为一个示例纸箱选择了折叠序列，设计了一个夹具，并展示了使用AdeptOne机器人从空白处折叠纸箱。这种方法可以实现不同纸箱样式之间的快速转换，因为它只需要更换夹具，固定板和机器人程序。我们开发了运动规划算法，通过利用由于固定装置引起的运动约束来生成所有可能的折叠序列。纸箱被建模为具有许多自由度的机器人，使用概率技术的运动规划师通常非常有效地在这些机器人的起始和目标配置之间找到路径。然而，据我们所知，概率规划者在开始和目标配置之间产生所有可能路径时，没有表现出性能的特征。我们的方法的主要优点是其简单性和易于实施，以及能够生成所有解决方案，直至离散化分辨率。该方法的主要缺点是为具有大量自由度的纸箱生成所有路径所需的指数时间。然而，许多纸箱可以减少到具有5到7个自由度的机器人，从而实现合理的规划性能。通过使用而不是快速碰撞检测包，可以消除配置空间树的空间要求。像其他使用近似表示的规划者一样对于自由空间，它可能找不到一些可行的解决方案。运动规划器可由人类设计者以交互方式使用，指定要聚焦的折叠序列。 未来改善计划性能的工作包括对配置空间障碍的懒惰评估，快速碰撞检测包的使用（例如，38，39）以避免明确计算障碍，表征自由空间的复杂性。纸箱机器人，以及路径生成的并行化。确定排序折叠序列的标准并消除那些不能被夹具折叠的标准将是有用的。一些有趣的问题仍有待解决，包括开发自动规划器来设计夹具，表征执行器机器人自由度对夹具设计空间的影响，以及设计纸盒以实现高效折叠。这种运动规划方法可以应用于钣金弯曲和二维铰链元件的三维MEMS结构设计32。致谢作者要感谢摩托罗拉的J. Nguyen，S. Mok和T. Babin的指导和支持。 他们还要感谢S. Hutchinson提供富有洞察力的反馈和有用的建议。LU AND AKELLA: FOLDING CARTONS WITH FIXTURES: A MOTION PLANNING APPROACH349带夹持装置的折叠纸箱的运动规划方法Planning ApproachLiang Lu and Srinivas Akella, Member, IEEEotionFolding Cartons with Fixtures: A MAbstractPackaging products such as telephones and two-way radios after assembly is a common manufacturing task. Carton folding is a packaging operation typically performed by human op- erators or with fixed automation. We present a flexible method to fold cardboard cartons using fixtures; a carton blank is folded by moving it through a fixture with a robot. This method uses inter- changeable fixtures to enable rapid changeovers between product models. We outline an approach to design a fixture given a carton and a folding sequence. We present an implemented motion plan- ning algorithm that generates all folding sequences for a carton by modeling it kinematically as a many degree-of-freedom robot ma- nipulator with revolute joints and branching links. Folding fixtures constrain the carton motion to paths consisting of line segments in its configuration space. We characterize the set of valid paths for these carton robots and generate them using the motion planner. To illustrate the method, we selected a folding sequence for an ex- ample carton, designed a fixture, and demonstrated folding of the carton from blanks with an industrial robot.Index TermsCarton folding, flexible manufacturing, pack- aging, robot motion planning.I. INTRODUCTIONPACKAGING products after assembly is a common man- ufacturing task. Cartons folded from flat cardboard blanksare used to package products such as telephones, two-way radios, and automotive components. Carton folding operations occur in packaging, distribution, and warehousing centers, and are typically performed by human operators or with fixed automation. Carton folding by humans requires dextrous manipulation of the carton and can lead to repetitive stress injuries. Commercial carton folding machines are not designed to handle the different carton styles necessitated by product and line changes.We present a method to fold cartons using fixtures, where a carton blank is folded by moving it through the fixture with a robot. The fixtures are interchangeable and enable rapid changeovers between product models. Folding a carton with a fixture requires generating valid folding sequences for theManuscript received January 11, 1999; revised October 31, 1999. This paper was recommended for publication by Associate Editor L. Kavraki and EditorP. Luh upon evaluation of the reviewers comments. This work was supported in part by the Beckman Institute and by Motorola through the Manufacturing Research Center at the University of Illinois at Urbana-Champaign. This paper was presented in part at the IEEE International Conference on Robotics and Automation, Detroit, MI, 1999.L. Lu was with the Beckman Institute for Advanced Science and Technology, University of Illinois at Urbana-Champaign, Urbana, IL 61801 USA. He is now with the Cellular Subscriber Sector, Motorola, Inc., Libertyville, IL 60048 USA.S. Akella was with the Beckman Institute for Advanced Science and Tech- nology, University of Illinois at Urbana-Champaign, Urbana, IL 61801 USA. He is now with the Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY 12180 USA (e-mail: ).Publisher Item Identifier S 1042-296X(00)06951-2.Fig. 1. The radio carton blank in its initial configuration and its folded configuration.carton, designing a fixture for a selected folding sequence, and implementing the folding operations on the fixture with a robot. A carton is an articulated structure and we model it kinemati- cally as a robot manipulator with revolute joints and branching links. We present a motion planning algorithm to automatically generate all folding sequences for a class of cardboard cartons folded from flat carton blanks with self-locking tabs (Fig. 1). We outline an approach to design a fixture given a carton and a folding sequence. Folding fixtures constrain the carton motion to paths consisting of line segments in its configuration space. We characterize the set of valid paths for these carton robots with many degrees of freedom, and generate feasible carton folding sequences with the motion planner. To illustrate the method, we selected a planner generated folding sequence for an example carton, designed a fixture using the design procedure, and demonstrated folding of the carton from blanks with an AdeptOne robot.Automation of the carton folding process involves several subtasks including automatic folding sequence generation, au- tomated folding fixture design, motion planning of the actu- ating robot, design of carton shapes for foldability, and efficient layout of carton blanks for cutting from stock. In this paper, we address the first and necessary task: generating physically valid folding sequences for consideration during generation of fix- tures and motions of the actuating robot. This work is a first step toward our long term goal of identifying fixture-foldable sequences and automatically designing carton folding fixtures. This future work will require taking into account the feasible motions of the actuating robot, holding tool constraints, and the stiffnesses of the fold creases.Carton folding is a task that involves the manipulation of ar- ticulated structures. A folding carton typically has many more degrees of freedom than the robot used to fold it. Our approach is to use the motion planner to aid the design of minimal com- plexity hardware by a human designer. The planner can poten- tially be used for similar shape modifying manufacturing tasks, such as sheet metal bending or in the design of 3-D microelec- tromechanical structures (MEMS) from hinged 2-D elements.1042296X/00$10.00 2000 IEEEAfter a review of related work in Section II, we outline the fixture design approach for a given carton and folding sequence in Section III. We then characterize the carton folding problem and present a motion planning algorithm to generate folding se- quences in Section IV. In Section V, we illustrate the approach on different carton styles. We present a fixture designed for an example carton and a folding sequence implemented with a robot in Section VI. We conclude with a summary and outline future work in Section VII. Portions of this work appeared ear- lier in 1.II. RELATED WORKThe packaging encyclopedia 2 and the books by Hanlon 3 and Friedman and Kipnees 4 provide an introduction and overview of packaging. Carton folding machines for industrial use are typically available for cartons that are glued or taped in their final configuration. We are aware of at least one commercial machine to fold the class of cartons considered in this paper 5, but the machines cannot be easily adapted to different carton styles. The patent literature describes several carton folding designs equipped with rotating wheels 6, 7, spiral bars or spiral belts at different orientations 8, 9, or rotatable bar folders 10 that gradually fold the flaps as a carton blank passes through. Such devices with a large number of moving elements cannot be easily modified to handle other cartons.The problem of carton folding shares geometric similarities with the problem of creating 3-D sheet metal parts from sheet metal blanks by bending. Both involve manipulating objects as their shape changes. However, sheet metal bending differs from carton folding in at least two aspects. First, a bent sheet metal part remains bent. Second, simultaneous sheet metal bends are usually performed only along collinear lines. Determination of bending sequences is a combinatorial problem coupled with the selection of bending tools. Most approaches focus on generating feasible solutions that may be suboptimal. de Vin et al. 11 describe a computer-aided process planning system to deter- mine bending sequences for sheet-metal manufacturing. They generate reverse bending sequences for sheet-metal components with straight bending lines, bent on press brakes. The system uses rules to increase accuracy, minimize handling, select tools, and avoid collisions between parts and punch tools. Shpitalni and Saddan 12 describe a system to automatically generate bend sequences with up to 18 bend lines. They use domain-spe- cific costs such as the number of tool changes and part reorienta- tions as well as heuristics based on the number of tools used and lengths and locations of bends to guide the A* search algorithm. Radin et al. 13 present a two-stage algorithm that first rapidly generates a feasible bending sequence using collision avoidance heuristics and then searches for lower cost solutions without vi- olating its time limitations. Inui et al. 14 developed an auto- matic planner for bending sheet metal parts. Gupta et al. 15 describe a fully automated process planning system to plan and execute bends with a robotic sheet metal bending press brake. Wang 16 develops methods to decompose sheet metal prod- ucts into components for ease of manufacturing during cutting, bending, and assembly. In particular, he unfolds 3-D productsinto 2-D patterns, and identifies unfolding bend sequences that avoid collisions with tools. Wang and Bourne 17 use shape symmetry to reduce planning complexity for sheet metal layout planning, bend planning, part stacking, and assembly.The geometric constraints in carton folding parallel those in assembly planning. Assembly planning by disassembly sequencing is a common technique. Mattikalli and Khosla 18 present a method to determine the constraints on motion of objects in an assembly from their contact geometry. Wilson and Latombe 19 developed the nondirectional blocking graph to efficiently generate monotone two-handed assembly plans. Wilson 20 has considered the geometric accessibility con- straints on assembly resulting from assembly tools. A current trend in robotics research is toward reduced complexity devices 21 that use simple, cheap, and robust actuators and sensors. Of particular interest is the work of Goldberg and Moradi 22 on assembly planning for assembly machines that perform a pipelined series of part rotations and vertical insertions that require only one or two degrees of freedom.We model cartons as robot manipulators with many de- grees of freedom to generate folding sequences using motion planning techniques. The book by Latombe 23 provides a comprehensive introduction to motion planning. Developing practical motion planners for manipulator arms with many degrees of freedom is an area of ongoing research. Barraquand and Latombe 24 developed a randomized path planner (RPP) that uses a combination of potential field techniques and randomized search techniques. An RPP can effectively generate motion plans for robots with a large number of degrees of freedom. Kavraki et al. 25 construct probabilistic roadmaps for path planning in high dimensional configuration spaces. Their method first develops a graph representation of the roadmap by sampling points in the configuration space during a learning phase. In the query phase, the roadmap is searched for paths connecting the start and goal configurations. Gupta and Guo 26 develop a sequential framework with backtracking for motion planning of robots with many degrees of freedom. They decompose the problem into a sequence of planning problems for each link, and backtrack when no solution is found for a particular link. Amato et al. 27 describe an obstacle-based probabilistic roadmap technique for motion planning in cluttered environments that samples points on or near configuration space obstacles. Lozano-Perez 28 developed a simple algorithm that uses an approximate cell decomposition to plan collision-free motions of serial robot manipulators. The algorithm is exponential in the number of degrees of freedom of the robot. He generates an efficient approximation of the free space, built up recursively from one-dimensional slices of the configuration space. We use his recursive tree data structure, whose leaves represent legal ranges of configurations for the robot.Recent work in computational geometry relates polyhedra and the polygonal shapes to which they can be unfolded, and de- velops connections to the art of origami. Lubiw and ORourke 29 present a dynamic programming algorithm to determine if a given polygon can be folded to a convex polytope. Biedl et al. 30 study unfoldings of two classes of nonconvex orthog- onal polyhedra. Demaine et al. 31 show that a square piece ofFig. 2. An example folding sequence. Fold creases are indicated by dotted lines.paper can be folded into any connected polygonal region, and further, any polyhedron can be folded from a single paper.The geometric issues in carton folding are similar to those in creating 3-D MEMS from 2-D hinged elements. Pister et al. 32 describe a variety of 3-D structures created from 2-D hinged polysilicon structures made by surface micromachining. Syms 33 presents a process for self-assembly of 3-D microstructures that relies on rotation of 2-D surface micromachined parts due to surface tension forces from a meltable material. Yi and Liu 34 developed a method for magnetic out-of-plane actuation of hinged planar microstructures to create self-locking 3-D MEMS devices.III. FOLDING WITH FIXTURESA carton blank is a flat cardboard cutout structure consisting of a set of panels, with fold creases separating adjacent con- nected panels (Fig. 1). Carton folding is often performed by hu- mans using their hands both to fold the carton and to maintain the intermediate folded configurations of the carton panels.A carton can usually be folded to its goal state in multiple ways that differ in the sequence of folds. See Fig. 2 for an example folding sequence. We fold carton blanks into cartons using fixtures. We design the fixture shape to match the carton for a selected folding sequence so that the carton is folded along its creases by being moved in contact with the fixture (Fig. 3). To fold the carton at a crease as it translates, we place a wall ele- ment perpendicular to the carton panel at the crease location. A wall is a flat plane whose length is chosen to be slightly greater than the crease length. The wall causes a carton panel to rotate along the crease and maintains the folded shape of the panels. For a chosen fold sequence, the distances between walls along the motion direction are selected to ensure the folds occur in the desired sequence. The walls are located an empirically de- termined distance away from the creases to ensure successful folds.Multiple folds of the carton can be performed simultaneously by judicious design of the fixture. Making the fixture a pas-Fig. 3. Designing a folding fixture. Creating fixture elements to perform each fold of the folding sequence shown on the left for a downward carton translation results in the fixture F1 shown at bottom right. At each stage, fixture walls are created or modified to accomplish the corresponding fold. Note that unrestrained flaps can spring back at intermediate stages of the folding and that an additional fold is necessary to tuck in the upper flaps.sive structure and using an industrial robot to move the carton through the fixture leads to a robust design with a small number of moving elements. Since a folding sequence specifies only the relative orientations of the carton panels, a given folding se- quence can have several instantiations in the world frame, each of which may yield a different folding fixture.IV. FOLDING SEQUENCE GENERATIONIdentifying feasible folding sequences is central to the fixture design process. Our approach is to generate all valid folding sequences, independent of fixture shape, for a human designer to evaluate. We formulate the generation of folding sequences as a robot motion planning problem. We model a carton as an articulated robot with revolute joints and a branching sequence of links (Fig. 4). Since a carton has many degrees of freedom (12 in our examples), we exploit symmetry in the carton shape to reduce the number of joints to consider. The motions of panels on one side of the carton are assumed to mirror those on the other side. Each valid path from the initial robot configuration to the goal robot configuration determines a folding sequence. We seek to generate all possible paths, and to use one of them to design a folding fixture.Fig. 4. The radio carton as an articulated manipulator robot with revolute joints and a branching sequence of links. Symmetry in the cartons shape makes it sufficient to model only one half of the carton as a robot.The motion planning problem is stated as follows. Given the carton shape and its kinematic representation as a robot, find all physically valid paths between its initial and goal configu- rations. A physically valid path is one that satisfies motion con- straints due to an abstract fixture and does not involve self-col- lisions of the carton panels. We identify valid paths independent of the fixture shape and feasible motions of the actuating robot, and do not model the actuating robot or the fixture as obstacles. From a motion planning perspective, the problem of generating folding sequences is challenging for the following reasons.1) A carton robot has a large number of degrees of freedom, ranging from 7 to 9 for the example cartons, even after considering carton symmetry.2) A carton robot is a nonserial manipulator with branching sequences of links.3) To generate all folding sequences, we seek all possible paths, unlike most motion planning algorithms that look for a single path from the initial configuration to the goal configuration.We can consider the joint motions to move a carton from its unfolded configuration to its folded configuration, or from its folded configuration to its unfolded configuration. Since a folded configuration has more constraints on the permissible joint motions than an unfolded configuration, it is more effi- cient to consider unfolding a carton from its folded configura- tion to its unfolded configuration. In what follows, we generate unfolding sequences rather than folding sequences.A. Configuration Space RepresentationThe configuration of an object is a set of parameters that com- pletely specify the position of every point of the object relative to a fixed reference frame. The configuration space of an ob- ject 35 is the space of all configurations of the object, where each coordinate represents a degree of freedom. For example, the set of joint angles of an articulated robot define a configura- tion space, which is in generalfor revolute joints. The configurations forbidden to the robot due to collisions with other objects or due to self-collisions constitute the set of configura- tion space obstacles . The set of legal configurations of the robot constitute its free space .The configuration space of a carton with joints where the th joint has a lower limit of and an upper limit ofis. We use a recursive tree structure, developed by Lozano-Perez 28 for a serial manipulator, to represent the configuration space of thecarton robot using one-dimensional slices of the configuration space. Each level of the tree contains a set of cells corresponding to discretized intervals of one joint of the robot. A leaf of the tree is a cell representing a range of robot configurations identified as belonging to or . We extend Lozano-Perezs tree representation to handle the branching links of the carton robot. We select a base panel and compute the tree representa- tion for the longest chain of links as before. For each branching sequence of links from this main chain, we create additional levels of the tree. The levels for the first branching sequence are attached to the leaf nodes of the tree for the main chain. Each branching chain of links is represented in sequence, and the levels for the branching chains are concatenated. A leaf node in the resulting tree represents a cell in configuration space and encodes whether or not it is in free space.We do not model the fixture or the actuating robot as ob- stacles, and assume there are no external obstacles that collide with the carton. Since a moving panel may collide with other panels as the carton is folded, the configuration space obstacles correspond to collisions between carton panels. When gener- ating the configuration space tree, we check for collisions of each rotating panel with the stationary panels 36. Our current implementation assumes all joints except the moving joint are fixed at the middle of their orientation ranges. An advantage of Lozano-Perezs tree representation is that variations in joint angles can be compensated for by swept volume computations. This gives a conservative representation of the free space so gen- erated paths are guaranteed to be collision-free, although some valid paths may be pruned.B. Motion Planning FormulationThe simplest approach to generating folding sequences is to assume only one joint can be moved at a time, and that each moving joint moves monotonically to its goal orientation. So we can test the ! possible joint sequences for feasibility by checking at each stage of a sequence if the moving joint can get from its initial orientation to its goal orientation without any intermediate configurations being in . However, this ap- proach gives only a subset of the folding sequences since it cannot generate solutions where multiple panels move simul- taneously.To generate folding sequences where multiple joints may move together, we first characterize the paths the robot can take in its configuration space when folded by an abstract (uninstantiated) fixture. Each joint is unactuated and begins rotating when a panel it is attached to contacts a wall of the fixture. We model all joints as moving at the same constant angular velocity , and assume that once a joint starts moving, it rotates monotonically to completion. (Section IV-D discusses the case when joints rotate at different velocities.) Joints may begin moving simultaneously or with delays in motion. We look for paths that take a carton from its folded configuration to its unfolded configuration. A robot with joints has ! possible joint sequences. We represent the th joint sequence by which means joint starts moving before or at the same time as , starts moving before or at the same time as , and so on. (Note that we use to represent joint as well as its angular value.) For each suchjoint sequence, we must also identify the rotational delay between successive joints. A delay means jointstarts rotating after joint has rotated through an angle . So we represent a delay sequence corresponding to the joint sequenceby . A joint rotates fromto. For a specified joint sequence and delay sequence, the motion of joint expressed in terms of the timeis given by (1)The dependence of the joint angles on each other, for a speci- fied joint sequence and delay sequence, can be equivalently ex- pressed by the following motion constraints: (2)The initial configuration constraints areFig. 5. Constraint planes and line segments along a path in a 3-D configuration space with d= (90, 90, 90) and d= (180, 180, 180). The 。 坦 path 之 composed of line segments , , , , and corresponds to joint sequence （。 and delay sequence （坦. The planes b and b correspond to the constraints 。 二 。 坦 and 。 二 。 坦 respectively. Line segment lies at the intersection of planes 。 二 a0 and 。 二 a0, and has length 坦 . Line segment lies at the intersection of b with plane。 二 a0, and the length of its projection on the 。 axis is 坦 . lies at the intersection of b and b , lies at the intersection of b with 。 二 J80, and lies at the intersection of 。 二 J80 with 。 二 J80. The goal configuration constraints are(3)(4)most straightforward algorithm would be to generate all ! joint sequences, and for each joint sequence, generate the paths corresponding to each of the possible delay sequences. For each path, if none of its line segments collides with a configuration space obstacle, the folding sequence is feasible.We modify the above algorithm to more efficiently prune in-Thedelaycan assume any value in the interval. If is zero, the two jointsand begin moving simultaneously, and if is, joint begins moving only after jointhas completed its motion. For the cartons we studied,andfor all . The configuration space of these carton robots is therefore 90, 180 , and , can assume any value from 0 to 90 .When of the joints are in motion, there areactive motion constraints andactive initial or goal configura- tion constraints. Each constraint defines a constraint plane in the-dimensional configuration space of the robot, and thetotal active constraint planes intersect along a line. So a path for the robot consists of a sequence of line segments. The maximum number of line segments in a path is. See Fig. 5 for an example path illustrating the 3-D case.C. Search AlgorithmOur goal is to identify collision-free paths for the carton robot. A path or a folding sequence is defined by a joint sequence and a corresponding delay sequence to take the robot from its folded configuration to its unfolded configuration. A robot with joints has ! joint sequences. To identify valid values for each feasible joint sequence, we discretize each range into intervals sampled at their midpoints. So each joint sequence has possible delay sequences. We must identify the valid folding sequences among the sequences. Thefeasible paths. For a given joint sequence, multiple paths to the goal may share one or more line segments. If a line segment col- lides with an obstacle, all the paths it belongs to are infeasible. Each partially instantiated delay sequence specifies a set of line segments, and we sequentially loop over them. For each instan- tiated , , test the defined line segment for a col- lision. If it does collide, the entire set of paths emanating from the colliding line segment can be classified as infeasible without instantiating the rest of the delay sequence. For each instantia- tion of the delay sequence that yields a sequence of collision-free line segments, we find valid values for by exploiting spatial coherence of the obstacles. If the line segment defined for some value of collides with an obstacle, test the cells at the incremented value of that neighbor the colli- sion cell. If those are collision-free, test the new line segment defined by the incremented value of for feasibility. Else again increment and repeat the process. See Fig. 6 for an example folding sequence generated by the algorithm. Note that the discretized representation of the configuration space and the delay values results in possible incompleteness of the planning method. That is, some valid solutions may not be returned by the planner.The worst-case time complexity of the algorithm is expo- nential in the number of joints. By identifying the set of joints that can move first from the initial folded configuration, we eliminate some infeasible combinations and reduce the search time. We test if a joint can move first by checking if it has a351IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION, VOL. 16, NO. 4, AUGUST 2000Fig. 6. Example (un)folding sequence for the radio carton generated by the algorithm has joint sequence (。 , 。 , 。 , 。 , 。 , 。 , 。 ) and delay sequence (90, 90, 90, 90, 0, 10). The sequence goes from left to right and top to bottom. The bottom panel has a constant orientation during folding.Fig. 7. The HP carton.Fig. 8. The Slope carton.collision-free configuration when rotated by a small amount, keeping all other joints at their start orientations. For each of the joints that can move first, we identify the set of joints that can potentially move second. Rapidly identifying the first two joints that can move means we explore only a subset of the ! joint sequences.D. Multiple Angular Velocity FormulationSince all joints may not rotate at the same angular velocity, we can permit each joint to rotate with a constant angular velocity , . For a specified joint sequence and delay sequence, the motion of joint is now given by (5)The initial and goal configuration constraints remain un- changed. The search algorithm is similar to that for equalFig. 9. Exploiting symmetry of the HP carton reduces the number of joints to model to 5.Fig. 10. The symmetric structure of the Slope carton can be exploited to model it as two robots with mirrored joint motions, reducing the number of joints to consider to 5.Fig. 11. An (un)folding sequence for the Slope carton, modeled as two five-joint robots, with joint sequence (。 , 。 , 。 , 。 , 。 ) and delay sequence (90, 90, 50, 90).angular velocities, with the additional consideration that for each joint sequence we must consider all possible valid angular velocity instantiations. We discretize the set of allowed angular velocities for each joint. When joints can each have angular velocities, the worst-case running time increases by a factor of .E. Evaluating the Folding SequencesThe motion planner returns a potentially large number of valid folding sequences. The human designer must select a sequence based on its foldability by a fixture. Folding sequence generation can be made interactive by having the designer specify joint sequences to explore and folding sequences to discard. The designer must also consider the permitted motionsTABLE IA COMPARISON OF THE RADIO, HP, AND SLOPE CARTON STYLES AND THE SYMMETRY-REDUCED HP AND SLOPE CARTONS. THE NUMBER OF DISCRETIZED JOINT INTERVALS AND ?, THE NUMBER OF SAMPLING INTERVALS FOR EACH y, ARE 10 FOR ALL CARTONS EXCEPT THE 9-JOINT SLOPE CARTON FOR WHICH THEY ARE 6, WITH CORRESPONDING SAMPLING RESOLUTIONS OF 10 DEGREES AND 18 DEGREES, RESPECTIVELY. (*) THE PATH GENERATION TIME FOR THE SLOPE CARTON IS THE TIME TO GENERATE A SINGLE DELAY SEQUENCE FOR EACH VALID JOINT SEQUENCETABLE IIA COMPARISON OF THE SYMMETRY-REDUCED CARTON STYLES WHEN MULTIPLE ANGULAR VELOCITIES ARE PERMITTED. EACH JOINT ROTATES WITH ANGULAR VELOCITY 牛 叭, WHERE 牛 J. 3. THE NUMBER OF DISCRETIZED JOINT INTERVALS AND ?, THE NUMBER OF SAMPLING INTERVALS FOR EACH y, ARE 10FOR ALL CARTONS WITH A CORRESPONDING SAMPLING RESOLUTION OF 10 DEGREESFig. 13. The implemented folding sequence includes a rotation of the carton. The unfolding joint sequence is (。 , 。 , 。 , 。 , 。 , 。 , 。 ）, with delay sequence (0, 90, 90, 70, 20, 0) and the angular velocity of 。 thrice that of all other joints.Fig. 12. Implemented fixture and AdeptOne robot.of the actuating robot when selecting a folding sequence for fixture design. The folding sequence instantiation in Fig. 6 requires only translation of the carton by the robot, while the implemented sequence in Fig. 13 involves a rotation as well.Since a folding sequence specifies only the relative orienta- tions of the carton panels, it may be instantiated in several ways. The instantiations depend on the feasible motions of the actu- ating robot, and whether it can only translate the carton or both rotate and translate it. Even when the carton can only be trans-lated, any one of several panels may be selected to have a fixed orientation during folding. Thus, several different folding fix- tures may be designed for a given folding sequence. The fold- ability of an instantiated sequence by a fixture is further deter- mined by the holding tool constraints and the stiffnesses of the fold creases. Therefore, the foldability of the instantiations can differ significantly. In fact, not every physically valid folding sequence is guaranteed to have a valid fixture implementation.V. CARTON STYLESThe motion planning algorithm can generate folding se- quences for any carton style that can be modeled as a robot with revolute joints and branching sequences of links with no kinematic loops. Examples include the HP carton (Fig. 7) and the Slope carton (Fig. 8).Since the generation of folding sequences is exponential in the number of joints, we seek to reduce the number of mod-LU AND AKELLA: FOLDING CARTONS WITH FIXTURES: A MOTION PLANNING APPROACH355Fig. 14. The initial carton folding operations, shown from left to right, top to bottom. The carton blank is transferred to the fixture, where prefolding of critical creases is performed. A multiple-joint fold is then performed, followed by flap alignment operations and a rotation of the carton.eled joints of the carton. We exploit the additional symmetry of the HP carton to model it as a serial manipulator (Fig. 9), reducing the number of robot joints from the original 12 to 5. The Slope carton can be modeled as two serial robots with dif- ferent link dimensions and mirrored joint motions (Fig. 10), to reduce the number of joints from 12 to 5 for each robot. The configuration space trees for the individual robots are computed independently, and used jointly for path planning. The carton dimensions determine if these sequences must be tested for col- lisions of opposite panels. An example folding sequence for the Slope carton is shown in Fig. 11. Modeling a carton as a robot with fewer joints reduces the search time and the number ofvalid folding sequences, making human inspection easier. We assume the human specifies the symmetry-reduced joint repre- sentation as input. While existing algorithms can detect sym- metry in polygonal and polyhedral shapes 17, they may not de- tect partial symmetry when the symmetric panels differ in their dimensions, as in the Slope carton.VI. IMPLEMENTATIONWe implemented the motion planner in C+ to generate folding sequences for a given carton robot. Table I compares the run times and feasible solutions for different carton styles whenFig. 15. Carton folding operations are continued in the front half of the fixture. The front panel is folded with the aid of two pneumatic actuators. The upper flaps are then folded and secured using self-locking tabs. The folded carton is removed from the fixture by the robot and placed for loading. The sequence runs from left to right and top to bottom.all joints have the same angular velocity. All computations were on a 360-MHz Sun ULTRA 60. When computing the configuration space tree, our current implementation assumes all joints except the moving joint are fixed at the midpoints of their discretized intervals. The number of discretized joint intervals and the number of discretized delay intervals, , are empirically chosen based on the number of joints and their mo- tion ranges. Table II compares the symmetry-reduced cartons when each joint can rotate with an angular velocity, where the candidate values forwere empirically identified. We demonstrated folding of the Radio carton style using an AdeptOne SCARA robot with an additional fifth joint (Fig. 12).The implemented folding sequence includes an intermediate ro- tation of the carton (Fig. 13). We designed a fixture for this se- quence, following the approach of Section III, in an iterative process that considered the fixture shape and actuating robot motions. The fixture was constructed from sheet metal and Lego blocks to enable quick changes to the fixture during design and testing. The first set of folding operations occur in the back half of the fixture (Fig. 14) and the second set of folding operations occur in the front (Fig. 15), and are separated by the rotation of the carton. The fixture has two pneumatic actuators to aid the folding process. The robot uses a holding plate with vacuum suction cups to pick up the carton. Since the holding plate is di-mensioned to enable the desired folds without collisions with the fixture, it may need to be changed along with the fixture when the carton style or size changes.We used the same fixture and holding plate for experiments on two Radio carton models that differed slightly in their stiff- ness and crease locations. One model was successfully folded on 9 of 10 trials while the other was successfully folded on 10 of 16 trials. A trial was classified a failure if the carton had undesired folds, noticeable scuffing, an accidental collision of a panel and the holding plate occurred, or the self-locking tabs were not fully inserted. These difficulties can be eliminated with better fixture fabrication. The robot can fold a carton in about a minute in our current implementation 37. Pipelining the folding operations or using multiple actuators in parallel can significantly reduce the execution time.VII. CONCLUSIONWe presented a flexible method to fold cardboard cartons using interchangeable fixtures; a carton blank is folded by moving it through a fixture with a robot. This paper makes the following contributions. First, it identifies the automation of carton folding by fixtures as a new task to which motion planning techniques can be applied. Second, it presents a mo- tion planning formulation and an implemented algorithm that exploits the constraints on the motion of cartons folded using fixtures to automatically generate all folding sequences for a class of self-locking cartons folded from flat carton blanks. The planner generated sequences enable a human designer to visualize and identify fixture-foldable sequences and design the corresponding fixtures. Exploiting carton symmetry and careful selection of the panels to be modeled as a robot improve planner efficiency significantly. To illustrate this method, we selected a folding sequence for an example carton, designed a fixture, and demonstrated folding of the carton from blanks with an AdeptOne robot. This method enables rapid changeovers between different carton styles as it requires only a change in the fixture, the holding plate, and the robot program.Our motion planning algorithm was developed to generate all possible folding sequences by exploiting the motion constraints due to fixtures. Cartons are modeled as robots with many de- grees of freedom, and motion planners using probabilistic tech- niques are typically very effective in efficiently finding a path between the start and goal configurations for such robots. How- ever, to the best of our knowledge, there has been no characteri- zation of the performance of probabilistic planners in generating all possible paths between the start and the goal configurations. The primary advantages of our approach are its simplicity and ease of implementation, and its ability to generate all solutions up to the discretization resolution. The primary disadvantage of the method is the exponential time required to generate all paths for cartons with a large number of degrees of freedom. However, many cartons can be reduced to robots with 5 to 7 degrees of freedom, enabling reasonable planner performance. The space requirements for the configuration space tree can be eliminated by the use instead of fast collision detection pack- ages. Like other planners that use an approximate representationof the free space, it may not find some feasible solutions.The motion planner can be used interactively by a human de- signer specifying folding sequences on which to focus. Future work to improve planner performance includes lazy evaluation of the configuration space obstacles, the use of fast collision de- tection packages (e.g., 38, 39) to avoid explicitly computing the obstacles, characterizing the complexity of the free space of the carton robot, and parallelization of path generation. Identi- fying criteria to rank folding sequences and eliminate those that cannot be folded by a fixture will be useful. Several interesting problems remain to be addressed, including developing auto- matic planners to design fixtures, characterizing the effect of ac- tuator robot degrees of freedom on the space of fixture designs, and designing cartons for efficient folding. This motion plan- ning approach can potentially be applied to sheet metal bending and the design of 3-D MEMS structures from 2-D hinged ele- ments 32.ACKNOWLEDGMENTThe authors would like to thank J. Nguyen, S. Mok, and T. Babin at Motorola for their guidance and support. They would also like to thank S. Hutchinson for insightful feedback and helpful suggestions.REFERENCES1 L. Lu and S. Akella, “Folding cartons with fixtures: A motion planning approach,” in IEEE Int. Conf. on Robotics and Automation, Detroit, MI, May 1999, pp. 15701576.2 A. L. Brody and K. S. Marsh, Wiley Encyclopedia of Packaging Tech- nology, 2nd ed. New York: Wiley, 1997.3 J. F. Hanlon, Package Engineering, New York: McGraw-Hill, 1984. 4 W. F. Friedman and J. J. Kipnees, Industrial Packaging. New York:Wiley, 1960.5 Automatic tray and box former BEM-102, Dorell Equipment, Inc., North Brunswick, NJ, 1999.6 C. R. Marschke, “Folding of paperboard sheets and the like,” U.S. Patent 4 834 696, May 1989.7 J. McBride and R. Lile, “Corner laminating apparatus and method for cartons,” U.S. Patent 4624653, Nov. 1986.8 B. Capdeboscq, “Sheet folding machine,” U.S. Patent 4614512, July 1985.9 J. Takeda and H. Yoshizuka, “Folding device in a corrugated cardboard box making machine,” U.S. Patent 5035683, Apr. 1990.10 H. D. Ward, “Box blank folding apparatus,” U.S. Patent 4295841, Oct.1981.11 L. J. de Vin, J. de Vries, A. H. Streppel, E. J. W. Klaassen, and H. J. J. Kals, “The generation of bending sequences in a CAPP system for sheet- metal components,” J. Mater. Processing Technol., vol. 41, pp. 331339, 1994.12 M. Shpitalni and D. Saddan, “Automatic determination of bending se- quence in sheet metal products,” Ann. CIRP, vol. 43, no. 1, pp. 2326, 1994.13 B. Radin, M. Shpitalni, and I. Hartman, “Two-stage algorithm for de- termination of the bending sequence in sheet metal products,” ASME J. Mechan. Design, vol. 119, pp. 259266, 1997.14 M. Inui, A. Kinosada, H. Suzuki, F. Kimura, and T. Sata, “Automatic process planning for sheet metal
- 温馨提示:
1: 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
人人文库网所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
川公网安备: 51019002004831号