基于图论和启发式搜索的装配序列规划算法

Algorithm for Assembly Sequences Planning Using Graph Theory and Heuristic Search

将装配序列规划中成熟的割集法和人工智能中启发式搜索方法相结合，提出一个高效的装配序列生成算法。此算法在启发函数的指导下，直接产生所需的最佳装配规划，避免了单独采用割集法产生装配AND/OR图而导致的组合爆炸的问题。同时省去了在选择装配规划时，对整个装配AND/OR图进行再次搜索。此算法与其它算法相比具有效率高、智能性强的特点。最后给出了一个实例。

Associating the cut sets of graph theory and heuristic search algorithm of AI, this paper presents an efficient algorithm for the automatic generation of the assembly sequences. In the guide of the heuristic functions, the algorithm generates the best assembly sequence directly. It not only avoids the problem of combinational explosion when only using cut sets to generate the AND/OR graph, but also avoids the traversal of the AND/OR graph when selecting the best assembly sequence. This algorithm has the features of high efficiency and strong intelligence. An example is given to illustrate the algorithm.