局部搜索技術在析取時序問題中的應用.pdf

1、帶有時序信息的推理問題是人工智能領域的重要研究內容。析取時序問題(Disjunctive Temporal Problem，DTP)是時序推理及調度領域內更具表達能力的問題模型，由于其事件間約束的復雜性，生成問題的可行解現已證明是較難解決的問題。因此如何快速獲得問題的可行解引起了大量研究人員的關注:一類解決方案是將DTP轉化為約束可滿足問題(Constraint Satisfaction Problems，CSP)，使用標準的CSP求解

2、技術來求解;另一類是將DTP編碼為一個命題可滿足問題(Propositional Satisfaction Problem，SAT)，使用現有求解SAT的算法來求解。然而，DTP在問題轉化、啟發(fā)式策略及搜索技術的應用等方面仍然存在改進空間。
　　局部搜索技術一直受到人工智能界的極大關注，GSAT算法的出現再次證明該技術在求解可滿足問題時有著較高的效率。但是，局部搜索技術目前仍沒有成功的用于求解DTP。本文主要研究如何將局部搜索技術

3、應用于求解DTP。為此，本文實現了應用局部搜索技術并加入約束加權思想的TSAT算法，將其做部分修改，用于對DTP直接進行求解;通過分析DTP的問題結構，我們將TSAT算法與DPC算法結合，提出了TSAT算法的改進算法—mTSAT，并將DTP轉化為元約束可滿足問題(meta-CSP)，用mTSAT算法在各變量的鄰域內搜索并生成簡單時序問題，然后判斷其一致性，達到縮小搜索空間以提高DTP求解效率的目的。
　　為了評估TSAT算法的性能