《AI EDAM》：A novel two-stage approach to parallel disassembly sequence planning using reinforcement learning
编辑推荐：
并行拆解序列规划（Parallel Disassembly Sequence Planning, DSP）涉及通过在产品某些拆解层级上并行拆解多个零件来确定拆解序列。以往研究仅使用优先图（precedence graph）表示产品装配并确定零件取出顺序。这不能
并行拆解序列规划（Parallel Disassembly Sequence Planning, DSP）涉及通过在产品某些拆解层级上并行拆解多个零件来确定拆解序列。以往研究仅使用优先图（precedence graph）表示产品装配并确定零件取出顺序。这不能保证所有零件以安全且稳定的方式被拆解，凸显了拆解中稳定性约束的重要性。引入稳定性约束后，由于问题的组合爆炸，难以在较低拆解层级下完整拆解产品，同时最小化方向变化。本文提出一种使用强化学习（Reinforcement Learning, RL）的并行DSP两阶段方法。在第一阶段，引入数学模型，随后为产品建立稳定性集成优先图（stability-integrated precedence graph）以简化问题。然后，获得产品的各种零件组合。在下一阶段，提出问题的无模型强化学习（model-free RL）表述以及自适应模拟退火线性衰减Q学习（Adaptive Simulated Annealing Linear Decay-based Q-learning, ASALD-Q）算法，以动态调整ASALD参数并避免局部最优，从而实现更快收敛。采用稀疏Q表（sparse Q-table）表示使ASALD-Q学习算法能很好地泛化到复杂产品。将所提算法应用于四个复杂度不同的产品，包括文献报道的产品，并将结果与采用两种探索技术的另一种无模型强化学习算法进行比较。结果证明了所提方法的有效性和相关性，尤其是在处理大规模产品时。
并行拆解序列规划（Parallel Disassembly Sequence Planning, DSP）要求在产品特定拆解层级上并行拆解多个零件，以确定满足约束与目标的拆解序列。产品装配体在寿命终期（End-of-Life, EoL）循环中应被拆解，以支持再利用、回收、再制造和翻新，从而降低环境影响。拆解是取出零件并确保其保持原始形态与功能的前提。DSP问题可分为顺序或并行、完全或选择性等类型。完全并行DSP中，至少一个拆解层级同时拆解多个零件，直到所有零件被拆解；选择性并行DSP则拆解至目标零件。由于顺序DSP具有线性特征，尤其对大型复杂产品，需要更多拆解层级或步骤，因此研究人员关注并行DSP。并行拆解首先必须满足优先约束（precedence constraint），即零件仅在其前驱零件已于先前层级拆解后才能拆解。但优先约束只表达拆解顺序，不能保证产品在拆解过程中安全稳定，因此必须考虑稳定性约束（stability constraint）。稳定性约束提供零件永久稳定（permanent stability）、部分稳定（partial stability）或无稳定（no stability）的信息，有助于规划拆解过程并避免零件损伤。已有研究对顺序DSP考虑稳定性约束，但较少针对并行DSP。由于DSP是NP难组合问题，考虑全部约束后求最优解仍然困难。已有研究探索多种无模型RL算法，但文献中尚未发现将稳定性数据与建模作为基于表格的无模型RL问题用于并行DSP的研究。这促使研究人员提出新的两阶段无模型RL方法。该方法适用于完全产品拆解，取出零件可在后续再制造中利用。
研究人员开展了两阶段方法研究。第一阶段引入数学模型，并构建稳定性集成优先图，将稳定性数据与优先图整合，从而在后续拆解中只需使用该集成图，简化问题；同时生成产品不同零件组合，并将并行度限制为3。第二阶段将并行DSP表述为无模型RL问题，提出ASALD-Q算法，动态调整ASALD参数以避免局部最优，并采用稀疏Q表表示以处理组合爆炸。研究人员将所提算法应用于四个不同复杂度产品，包括8零件、13零件、21零件装配体以及37零件齿轮减速器装配体，并与另一种无模型RL算法在两种探索技术下比较。结果表明，所提方法能获得更优并行拆解序列，减少拆解层级和方向变化，尤其在大规模产品中表现有效。
主要关键技术方法可概括为：构建稳定性图并与优先图集成为稳定性集成优先图；依据无前驱且同方向条件生成一零件、二零件和三零件组合，并行度设为3；将并行DSP建模为无模型RL，状态为表示零件是否已拆解的二进制向量，动作为满足约束的零件子集，奖励函数为 R=|a|
2+R
direction+R
penalty；采用稀疏Q表以Python字典存储非零Q值；提出ASALD-Q，温度初值1.0、线性衰减率0.01，依据奖励与方向变化动态调整，停滞50回合触发reheating。案例产品为原文采用的8零件、13零件、21零件装配体及文献报道的37零件齿轮减速器装配体。
研究结果如下。
Case study 1：针对8零件产品装配体，研究人员使用Q-learning智能体（agent）学习拆解策略。该产品生成两个满足优先与方向条件的二零件组合。ASALD-Q收敛更快，获得序列 (5,6)→4→3→(7,8)→2→1，含4个并行零件、3次方向变化和5个拆解层级。与SARSA及其他探索策略比较，ASALD-Q更快达到高奖励并保持稳定。
Case study 2：针对13零件产品装配体，研究人员将方向数据输入ASALD-Q。智能体选择无前驱零件开始拆解，得到序列 12→(4,5,13)→11→(9,10)→7→6→8→2→3→1，含5个并行零件、5次方向变化和9个拆解层级。ASALD-Q在相对更少回合内获得高奖励，优于SARSA和其他探索策略。
Case study 3：针对21零件产品装配体，该产品有45个二零件组合和92个三零件组合满足优先与方向条件。智能体获得序列 (7,9,20)→(13,15,19)→(10,14,21)→6→16→17→18→11→12→8→5→4→1→2→3，含9个并行零件、3次方向变化和14个拆解层级。ASALD-Q早期收敛至最高奖励，其他探索策略并行拆解零件数较少。
Comparison of proposed approach with recent work：研究人员将方法用于37零件齿轮减速器装配体，并与已有改进蚁群优化（Ant Colony Optimization, ACO）方法比较。已有方法报告18次方向变化、7个并行零件和32个拆解层级；所提ASALD-Q方法得到12次方向变化、17个并行零件和25个拆解层级，在所有指标上更优。与SARSA比较时，ASALD-Q在收敛速度和奖励上更优。
Discussion：讨论表明，ASALD-Q对本文所有产品均产生优于SARSA和其他探索策略的最优拆解序列；与37零件产品文献结果比较，ASALD-Q在所有指标上优于已有工作；ASALD-Q具有良好收敛性。主要因素包括：算法每50回合监测学习行为，若奖励和方向变化未改善则进行reheating，使智能体探索未搜索区域；奖励结构促使智能体识别同方向变化的更多并行零件；提供一零件、二零件和三零件组合作为输入，减少智能体额外约束。上置信界（Upper Confidence Bound, UCB）未识别更多并行零件，影响解质量和奖励；epsilon-greedy指数衰减在初期探索较好，但影响最优策略收敛；小产品上不同算法差异较小，产品规模增大时ASALD-Q优势明显。SARSA对小零件可找到合理质量解，但零件数增加后不如Q-learning。实验表明，所提方法可用于不同尺度产品的完整拆解，在满足优先与稳定性约束的同时最小化方向变化。
结论部分可翻译为：本文构建了稳定性集成优先图来表示产品结构，并在整个拆解过程中使用，从而以有序、安全且稳定的方式拆解产品。此外，生成不同产品零件组合以促进并行，使决策者能够持续选择与问题目标一致的有效零件。第一阶段的这些预处理步骤有助于简化问题，并在下一阶段将其表述为无模型RL问题。随后，研究人员提出ASALD-Q算法，以获得包含更多并行零件的完整拆解序列，通过最小化方向变化减少拆解层级。研究人员采用稀疏Q表表示，使所提算法能较好泛化并求解大规模并行DSP，而密集Q表无法做到。所提出的一种新颖自适应机制reheating根据先前表现动态调整ASALD参数，有助于在搜索空间探索中避免局部最优并选择合适产品零件。所提算法在四个不同尺寸产品上测试了有效性，并与另一种使用两种不同探索技术的无模型RL算法进行比较。结果表明，与现有算法相比，所提算法对大规模产品能更快收敛到最优策略。未来可研究不确定环境下的并行DSP，并结合拆解工具和时间等因素，以改进所提方法的应用。
