智能規(guī)劃中觀測約簡及互斥檢測的進一步研究.pdf

1、本文在前人已有的工作基礎(chǔ)上對智能規(guī)劃領(lǐng)域的觀測約簡和互斥檢測問題做進一步的研究。智能規(guī)劃的研究領(lǐng)域在近年來得到了不少的擴展，比如不確定規(guī)劃(NDP)放松了確定性系統(tǒng)的假設(shè)、過度規(guī)劃(OSP)放松了嚴(yán)格目標(biāo)的假設(shè)等等。這些擴展帶來了不少新的問題，比如不確定規(guī)劃中的觀測個數(shù)約簡問題，還有過度規(guī)劃中互斥目標(biāo)的檢測問題及經(jīng)典規(guī)劃器的改造等問題。這些新問題包括了很多有待進一步研究的子問題，比如觀測約簡中觀測個數(shù)最小化、啟發(fā)式的互斥檢測、改造優(yōu)秀的

2、經(jīng)典規(guī)劃器以利用互斥檢測中的知識等。本文提出了解決上述三個有待進一步研究的子問題的方法。 本文從三方面改進觀測約簡：一是如何找最小觀測集合(MOS)，二是如何在觀測代價不均等時找最優(yōu)觀測集合(OOS)，三是如何找到容錯的OOS。通過MOS問題和圖論中的最小覆蓋集問題(MSC)的類似性，可證MOS是NP難的問題，還可參考MSC算法得出時間復(fù)雜性為O(2m*㎡)及Ω(2m-1)的算法，其中m是觀測的個數(shù)。通過使用整數(shù)規(guī)劃(IP)技術(shù)

3、，可找到OOS以及容錯的OOS?？梢宰C明，上述算法能夠保證找到解，并且能夠保證解的最優(yōu)性。 互斥檢測本身是NP完全的，本文提出兩種用較小的代價給重構(gòu)目標(biāo)子集提供啟發(fā)信息的方法。第一種方法將實現(xiàn)子目標(biāo)的規(guī)劃視為宏動作，通過識別這些宏動作之間的關(guān)系推測目標(biāo)之間的關(guān)系。第二種方法基于動作之間的因果鏈提出因果鏈圖(CLG)來檢測動作之間的競爭性前提，從而識別目標(biāo)之間的沖突。其中對第一種方法實現(xiàn)了一個名為Combinator的目標(biāo)關(guān)系檢測