約束滿足問題的符號算法及其在裝配規(guī)劃中的應用研究.pdf

1、約束滿足問題(CSP)是人工智能和計算機科學領域的一個重要研究課題，現(xiàn)實生活中的大量問題均可以適當地描述成一個CSP。由于受組合復雜性問題的制約，傳統(tǒng)的CSP求解算法無法高效地求解大規(guī)模CSP。采用隱式的符號表示和操作技術是緩減乃至克服組合爆炸問題的一種可行策略。裝配序列規(guī)劃是產品設計生產過程中的重要環(huán)節(jié)，它極大地影響著裝配成本及生產周期。裝配序列規(guī)劃的目標是求解滿足各種裝配約束條件的可行裝配序列，通過適當描述，可將裝配序列規(guī)劃問題轉化

2、為約束滿足問題。本文以有序二叉決策圖和代數決策圖為基礎，對約束滿足問題的符號求解技術進行了探索和研究；在此基礎上，對裝配序列規(guī)劃問題的約束求解技術進行了研究。論文主要研究結果包括：
　　 1.對經典約束滿足問題進行了研究。通過建立變量和變量域的二進制編碼，以及約束的布爾特征函數表示，給出了經典CSP的有序二叉決策圖(OBDD)描述。將經典CSP中的約束按變量在約束圖中的度進行歸類，結合問題歸約法，提出了一種新的求解經典CSP的符

3、號OBDD算法。為進一步提高算法的執(zhí)行效率，結合桶消元算法，提出了經典CSP求解的符號OBDD桶消元算法。通過與傳統(tǒng)桶消元算法和符號直接求解算法的實驗對比，結果表明本文提出的兩種符號算法均擴大了問題的求解規(guī)模，并提高了算法的執(zhí)行效率。
　　 2.對加權約束滿足問題(WCSP)進行了研究。通過對變量和變量域值的二進制編碼，將WCSP轉換成偽布爾函數表示，進而給出了WCSP的代數決策圖(ADD)描述。在此基礎上，將ADD的符號操作技

4、術與分支定界搜索算法以及桶消元算法相結合，引入結點一致性預處理技術，在靜態(tài)變量序的情況下給出了求解WCSP的符號ADD算法。為了進一步提高該算法的搜索下界，通過引入有向弧一致性計數技術，給出了另一種符號ADD求解算法。對大量隨機生成的測試用例進行實驗分析，結果表明本文提出的兩種符號算法在性能上明顯優(yōu)于帶有結點一致性或存在有向弧一致性技術的具有前向檢查功能的深度優(yōu)先分支定界搜索算法。
　　 3.對裝配體模型及裝配序列的符號OBDD

5、表示進行了研究。通過對裝配體中零件的二進制編碼，基于符號OBDD技術，給出了裝配體聯(lián)結圖和Gottipolu裝配體模型的OBDD描述。建立了裝配狀態(tài)和裝配任務的布爾函數表示，給出了裝配序列的符號OBDD表示。建立了從裝配序列的AND/OR圖模型到OBDD表示的轉換規(guī)則，給出了AND/OR圖的符號OBDD表示。通過與裝配序列表示的與或圖模型、有向圖模型的實驗對比，結果表明，裝配序列的符號OBDD表示具有較高的存儲效率，適合于復雜裝配體的可

6、行裝配序列的描述。
　　 4.基于拆卸法對裝配序列規(guī)劃問題進行了研究。通過對無向圖的OBDD表示的重新分析，給出了裝配聯(lián)接圖的新的OBDD表示和移動向量函數的共享二叉決策圖(SBDD)表示。針對無向圖G，給出了求解圖G的頂點子集的導出子圖的符號OBDD技術和判定圖G的連通性的符號OBDD技術，并在此基礎上，基于Sharafat遞歸收縮算法的思想，給出了求解無向圖G的所有割集的符號OBDD算法。基于裝配聯(lián)接圖和移動向量函數的新的符

7、號表示模型，將符號OBDD割集算法與裝配序列的割集分解法相結合，利用OBDD的符號操作實現(xiàn)裝配操作的幾何可行性分析，給出了裝配序列的符號OBDD分解算法。通過裝配體實驗驗證了基于分解法的裝配序列的符號OBDD算法的正確性和可行性。
　　 5.基于裝配法對裝配序列規(guī)劃問題進行了研究。以裝配聯(lián)接圖和移動向量函數為裝配體模型，給出了裝配聯(lián)接圖的SBDD表示，移動向量函數的OBDD表示。建立了裝配序列規(guī)劃問題的CSP模型，將裝配序列規(guī)劃