一種基于最小沖突集的約束沖突消解方法

劉曉平， 季 浩， 石 慧

（合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院VCC研究室，安徽 合肥 230009）

在協(xié)同設(shè)計(jì)中，不同設(shè)計(jì)者在網(wǎng)絡(luò)化平臺(tái)上依據(jù)各自經(jīng)驗(yàn)和理解對(duì)產(chǎn)品進(jìn)行分工設(shè)計(jì)，實(shí)際過程中存在著大量相互影響、相互制約的約束關(guān)系。筆者所在的團(tuán)隊(duì)在多年協(xié)同模板理論的研究過程中逐漸發(fā)現(xiàn)協(xié)同模板中約束關(guān)系的復(fù)雜 性[1]，當(dāng)在協(xié)作過程中不同的設(shè)計(jì)選擇發(fā)生沖突時(shí)，如果設(shè)計(jì)者們對(duì)約束信息的組織關(guān)系把握不清楚，無疑會(huì)增加沖突消解的難度和設(shè)計(jì)過程的反復(fù)，降低協(xié)同設(shè)計(jì)的效率。

為了保證并行產(chǎn)品設(shè)計(jì)順利進(jìn)行，文獻(xiàn)[2]采用改進(jìn)的區(qū)間傳播算法用于實(shí)時(shí)在線檢測(cè)沖突，在約束網(wǎng)絡(luò)中沒有沖突時(shí)，給出傳播后變量的取值范圍。文獻(xiàn)[3]提出利用基于最小沖突集修補(bǔ)的算法，求解動(dòng)態(tài)變化的約束滿足問題。但事實(shí)上都不能使設(shè)計(jì)者在變更約束的同時(shí)清楚了解約束條件之間的關(guān)系，而在約束信息發(fā)生沖突時(shí)，及時(shí)、準(zhǔn)確地提取約束信息的制約關(guān)系、輔助設(shè)計(jì)者利用已有的知識(shí)進(jìn)行協(xié)商調(diào)整約束信息是建立以人為中心的沖突消解方法的關(guān)鍵。

本文主要工作是從最小沖突集的角度出發(fā)，分析最小沖突集元素個(gè)數(shù)范圍和判定方法，并結(jié)合交邊算法[4]實(shí)現(xiàn)對(duì)最小沖突集的提取，通過算例說明最小沖突集，該方法對(duì)建立以人為中心進(jìn)行控制和管理約束信息、消解約束沖突的有效性。

1 相關(guān)概念和性質(zhì)

1.1 相關(guān)概念

一個(gè)工程設(shè)計(jì)問題實(shí)際上是多個(gè)約束條件滿足問題，即對(duì)滿足約束條件

1.2 相關(guān)性質(zhì)

為了方便描述和證明最小沖突集的相關(guān)性質(zhì)，這里先給出交邊算法的數(shù)學(xué)描述和Helly 定理。

下面給出在交邊算法中提取最小沖突集時(shí)所用到的一些性質(zhì)：

最小沖突集元素個(gè)數(shù)k 不小于2 是顯然。

若 1k d＞ + ，由最小沖突集的定義知

Ω ( d ,k)= ?， Ωi( d , k? 1)≠?， i = 1,… ,， k ? 1≥ d+1。

所以最小沖突集的元素個(gè)數(shù)k 滿足2 ≤ k ≤ d+1。

表1 約束冗余的判斷方法

對(duì)于 L1= L2的情況，通過指向 L1,L2所表示 區(qū)域的法向量是否相同來判斷冗余。

性質(zhì)1 說明在d 維約束條件中，如果存在最小沖突集， 其元素個(gè)數(shù)k 的應(yīng)該滿足 2 ≤ k ≤ d+1。性質(zhì)2 指出判斷元素個(gè)數(shù)范圍為 [2, d+1]的沖突集方法，其證明由交邊算法的數(shù)學(xué)描述中易得。性質(zhì)3 用來化簡(jiǎn)冗余約束。在利用交邊算法判斷原約束集為沖突的同時(shí)，利用上述性質(zhì)提取出最小沖突集和冗余約束。

2 約束沖突消解方法

本文在上述性質(zhì)的基礎(chǔ)上，結(jié)合交邊算法提取最小沖突集和冗余約束，到達(dá)消解約束的目的。以下是約束沖突消解方法：

（1） 根據(jù)信息的屬性確定約束信息的維數(shù)d，由性質(zhì)2 得最小沖突集的元素個(gè)數(shù)范圍。

（2） 將約束信息用改進(jìn)的交邊算法，進(jìn)行求解、檢測(cè)沖突和記錄相關(guān)信息。改進(jìn)的交邊算法的非形式的描述如下：

Step 6 在記錄信息中依據(jù)上述的性質(zhì)，化簡(jiǎn)冗余約束信息，并提取 2k = 的最小沖突集。

Step 7 選取k s= 的最小沖突集，滿足：

Step 8 若 s ≤ d+1，則轉(zhuǎn)Step 7。否則算法結(jié)束。

（3） 由記錄的信息，去除冗余信息并提取最小沖突集。

（4） 對(duì)最小沖突集中的約束序號(hào)進(jìn)行編碼，通過對(duì)編碼的運(yùn)算，方便以后查找關(guān)鍵的約束信息。

（5） 設(shè)計(jì)者依照保留最多的約束、指定的約束等準(zhǔn)則或要求，進(jìn)行協(xié)商消解沖突。

3 算法示例

下面給出一個(gè)算例，假設(shè)設(shè)計(jì)者在進(jìn)行約束沖突消解時(shí)，以保留最多約束條件為準(zhǔn)則。

例：

由于線性約束是2 維的，只可能存在元素個(gè)數(shù)是2 或3 的最小沖突集。通過改進(jìn)的交邊算法判定該約束集是沖突的，并得到如表2 的矛盾信息記錄。

表2 矛盾信息記錄

對(duì)最小沖突集中的約束進(jìn)行01 編碼：

將編碼相加得：11010221，因有3 個(gè)最小沖突集，每個(gè)約束至多參與2 個(gè)最小沖突集，所以至少要剔除兩個(gè)約束，才能使得沖突消解。所以依據(jù)保留最多約束條件的準(zhǔn)則，應(yīng)當(dāng)剔除約束條 件 L2, L3,L6。

圖1 約束條件的直觀圖

4 結(jié) 束 語

為了使設(shè)計(jì)者在協(xié)同設(shè)計(jì)中能清晰地把握約束信息的制約關(guān)系，有效地去除冗余信息、消解約束沖突。本文從最小沖突集的角度出發(fā)，在分析最小沖突集的相關(guān)性質(zhì)和交邊算法的基礎(chǔ)上，提出了利用改進(jìn)交邊算法提取最小沖突集，方便設(shè)計(jì)者按照一定的準(zhǔn)則去除沖突約束信息。由于對(duì)最小沖突集剔除部分約束信息，需要建立在設(shè)計(jì)者的相關(guān)知識(shí)和準(zhǔn)則上，并且在約束信息非常多的情況下，設(shè)計(jì)者不容易利用抽象思維完全把握約束信息之間的關(guān)系，而可視化具有細(xì)致、完善地展現(xiàn)約束信息，使設(shè)計(jì)者清晰、直觀地了解約束信息之間的關(guān)系，所以下一步工作將考慮結(jié)合約束信息可視化手段，研究可視約束信息、交互式處理沖突的方法。

[1] 劉曉平, 石 慧, 毛崢強(qiáng). 協(xié)同模板中的信息可視化[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2005, 17(10)： 2334-2338.

[2] 朱湘毅, 唐 泉, 陳文培, 等. 并行工程中基于約束的沖突檢測(cè)研究[J]. 機(jī)械科學(xué)與技術(shù), 2000, 19(5)： 849-852.

[3] 孫吉貴, 高 健, 張永剛. 一個(gè)基于最小沖突修補(bǔ)的動(dòng)態(tài)約束滿足求解算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2007, 44(12)： 2078-2084.

[4] 宋恩民, 黃文奇. 判斷具有多線性約束條件的凸空間是否為空的交邊算法[J]. 計(jì)算機(jī)學(xué)報(bào), 1996, 19(9)： 704-708.

[5] Dimitri P Bertsekas, Angelia Nedic, Asuman E Ozdaglar. Convex analysis and optimization [M]. 北京： 清華大學(xué)出版社, 2006. 112-165.