約束滿足問(wèn)題的符號(hào)算法及其在裝配規(guī)劃中的應(yīng)用研究.pdf

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

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

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

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

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

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

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