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

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

2、器人問(wèn)題等。這些問(wèn)題的特點(diǎn)是系統(tǒng)的狀態(tài)隨時(shí)間不斷發(fā)生改變，因此，初始的規(guī)劃會(huì)變得不太合適甚至不能再使用。一般的處理方法是對(duì)新的狀態(tài)的全局進(jìn)行重新搜索，從而得到新的規(guī)劃來(lái)執(zhí)行。但是，我們發(fā)現(xiàn)在較多的問(wèn)題中，這些改變是局部的，對(duì)于整個(gè)系統(tǒng)來(lái)說(shuō)都往往是比較小的。這樣，由于搜索狀態(tài)的改變只是一小部分，那么再進(jìn)行一次徹底的搜索就顯得不必要，因?yàn)槲覀兛梢岳蒙虾芏嘣鹊乃阉饔涗洠@樣可以減少我們的搜索空間和時(shí)間，這就是漸進(jìn)搜索的基本思想。而B(niǎo)DDR

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