BDDRPA-：基于OBDD的RPA-算法.pdf

1、在人工智能領(lǐng)域，不確定的動態(tài)環(huán)境下的重搜索問題的求解空間、時間復雜度都是比較大的，如何改進算法以提高重搜索效率就成為研究者們一直關(guān)注的問題。在近兩年研究成果基礎(chǔ)上，本文對如何把啟發(fā)方法(A*算法)、基于OBDD的搜索技術(shù)和漸進搜索(incrementalsearch)結(jié)合在一起，從而改進重搜索算法這一問題進行了研究。本文提出了一個在動態(tài)環(huán)境下的搜索算法BDDRPA*，它的優(yōu)點是可以應用到動態(tài)的持續(xù)變化的領(lǐng)域中，例如持續(xù)規(guī)劃問題、移動的機

2、器人問題等。這些問題的特點是系統(tǒng)的狀態(tài)隨時間不斷發(fā)生改變，因此，初始的規(guī)劃會變得不太合適甚至不能再使用。一般的處理方法是對新的狀態(tài)的全局進行重新搜索，從而得到新的規(guī)劃來執(zhí)行。但是，我們發(fā)現(xiàn)在較多的問題中，這些改變是局部的，對于整個系統(tǒng)來說都往往是比較小的。這樣，由于搜索狀態(tài)的改變只是一小部分，那么再進行一次徹底的搜索就顯得不必要，因為我們可以利用上很多原先的搜索記錄，這樣可以減少我們的搜索空間和時間，這就是漸進搜索的基本思想。而BDDR

3、PA*算法就是綜合了漸進搜索和基于OBDD的啟發(fā)式搜索方法而提出的。本文首先簡要地介紹了經(jīng)典的搜索算法(比如A*，寬度優(yōu)先搜索算法等)，和基于OBDD的搜索算法BDDA*和SetA*；接著詳細介紹了我們提出的Pre-BDDRPA*算法以及在它基礎(chǔ)上做了改進后的正式的BDDRPA*算法，我們給出了該算法的C++偽代碼并對其做了一些詳細的分析；然后通過實驗將BDDRPA*和BDDA*算法、LPA*算法、A*算法以及BFS寬度優(yōu)先等重搜索算法