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

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

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

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