[發明專利]一種面向裝配規劃的符號加權約束求解方法

有效

• 申請號: 201611234708.9
• 申請日: 2016-12-28
• 公開（公告）號: CN106650129B
• 公開（公告）日: 2020-05-08
• 發明（設計）人: 徐周波;唐浩;劉桂珍;寧黎華
• 申請（專利權）人: 桂林電子科技大學
• 主分類號: G06F30/17
• 分類號: G06F30/17;G06F111/04
• 代理公司: 桂林市持衡專利商標事務所有限公司 45107
• 代理人: 陳躍琳

本發明公開一種面向裝配規劃的符號加權約束求解方法，首先獲取裝配體的裝配聯接圖、移動向量矩陣和裝配代價指標；然后根據裝配體信息刻劃WCSP模型；接著根據裝配體的裝配聯接圖、移動向量矩陣和裝配代價指標創建聯接圖和移動向量矩陣的OBDD表示以及裝配代價指標的ADD表示；最后搜索出一個可行的裝配序列并記錄其總的代價Cost，再對剩余未擴展完成的聯接邊逐一擴展，并將擴展的代價Cost1與Cost進行比較；搜索完所有的聯接邊之后，最終得到的最小代價值的裝配序列就是最優裝配序列。本發明能夠在較高的時間和空間效率下，完成對裝配體的最優裝配序列的生成。

技術領域

本發明涉及裝配序列規劃技術領域，具體涉及一種面向裝配規劃的符號加權約束求解方法。

背景技術

裝配序列規劃(Assembly Sequences Planning，ASP)是裝配規劃中的一個技術難點，在產品設計開發和生產過程中占有很重要的地位。對于大規模產品的生產，一條優秀的裝配序列將會大大的縮短產品的生產周期，降低產品的生產費用，提高產品的質量性能。

用于減緩或者部分程度上避免組合復雜性問題的一種可行策略是采用符號或者隱式描述技術。有序二叉決策圖(Ordered Binary Decision Diagrams，OBDD)及其擴展形式可以實現狀態空間或者變量組合的隱式表示和搜索，是迄今為止最為有效的符號技術之一。近年來，OBDD及其擴展形式(比如ADD和ZBDD)在裝配序列規劃方面已經有了一些應用。實驗結果表明，利用OBDD或其擴展形式作為裝配序列的表示比使用AND/OR圖表示占用更小的存儲空間。

約束滿足問題(Constraint Satisfaction Problem，CSP)作為人工智能和計算機科學領域中的大量復雜問題的一個通用的求解范例，已得到廣泛的應用。CSP的求解技術為解決裝配序列規劃問題提供了新的思路和手段。然而，現有的CSP求解技術主要在不考慮裝配代價的模型上進行研究，當CSP中對約束的限制過多時，往往會使得問題無解。

發明內容

本發明所要解決的是現有約束滿足問題求解技術不考慮裝配體的裝配代價的問題，提供一種面向裝配規劃的符號加權約束求解方法，其能夠求解出裝配規劃的最優裝配序列。

為解決上述問題，本發明是通過以下技術方案實現的：

一種面向裝配規劃的符號加權約束求解方法，包括步驟如下：

步驟1.獲得裝配體知識，即裝配聯接圖、移動向量矩陣和所需的裝配代價指標；

步驟2.根據裝配體知識，將一個裝配序列規劃問題描述成一個加權約束滿足問題；

步驟3.根據裝配體的裝配聯接圖，創建裝配聯接圖的OBDD表示；

步驟4.根據裝配體的移動向量矩陣，創建移動向量矩陣的OBDD表示；

步驟5.根據所需的裝配代價指標，創建裝配代價指標矩陣的ADD表示；

步驟6.將裝配聯接圖的OBDD表示、移動向量矩陣的OBDD表示和裝配代價指標矩陣的ADD表示代入到步驟2的加權約束滿足問題中，并通過求解加權約束滿足問題去搜索出一條最優的可行的裝配。

上述步驟2的具體步驟如下：

步驟21.用加權約束滿足問題中的變量來表示具有連接關系的兩零件在建立裝配關系時在裝配序列中的順序號，即裝配聯接圖中的一條連接邊對應加權約束滿足問題中的一個變量，并生成變量集X＝{v₁，v₂，v₃，...，v_m}；

步驟22.根據裝配體的零件個數n，設定加權約束滿足問題中各變量的域D為[1，n-1]；

步驟23.對加權約束滿足問題進行約束定義；