典型航路規(guī)劃方法的基本原理例習(xí)題展示

1、典型航路規(guī)劃方法的基本原理例題展示典型航路規(guī)劃方法的基本原理例題展示PAGE19典型航路規(guī)劃方法的基本原理例題展示簡要論述典型航路規(guī)劃方法的基本原理（任選方法之一，且選擇該方法中的一種具體方法。）并舉例說明。（1）路標(biāo)圖法；（2）單元分解方法；（3）人工勢場法答：選擇（1）路標(biāo)圖法。概略圖( Skeleton)也稱路標(biāo)圖( Roadmap )。在基于概略圖空間的路徑規(guī)劃方法中，首先根據(jù)一定的規(guī)則將自由的C空間（Configuration Space)表示成一個(gè)由維的線段構(gòu)成的網(wǎng)絡(luò)圖，然后采用某一搜索算法在該網(wǎng)絡(luò)圖上進(jìn)行航跡搜索。這樣，規(guī)劃問題被轉(zhuǎn)化為一個(gè)網(wǎng)絡(luò)圖的搜索問題。概略圖必須表示出C空間

2、中的所有可能的路徑，否則該方法就是不完全的，即可能丟失最優(yōu)解。常用的概略圖方法包括通視圖法( Visibility Graph)、Voronoi圖法、輪廓圖法( Silhouette)、 子目標(biāo)網(wǎng)絡(luò)法(Subgoal Network )和隨機(jī)路線圖法( Probabilistic Roadmap, PRM)。 通視圖法通視圖由規(guī)劃空間中的障礙物的相互可見的頂點(diǎn)間的連線構(gòu)成。圖1-1給出了包含三個(gè)多邊形障礙物的二維規(guī)劃空間的通視圖，其中較粗的線表示起始點(diǎn)S和目標(biāo)點(diǎn)G之間的一條最短路徑。1989 年，Asano等證明在具有n個(gè)頂點(diǎn)的二維規(guī)劃空間中，其通視圖的邊數(shù)具有數(shù)量級0 (n2)，構(gòu)造通視圖所

3、需時(shí)間的數(shù)量級也為0 (n2)。圖1-1通視圖 通視圖法可用于求解二維規(guī)劃空間中的最短路徑問題。盡管它也可用于高維規(guī)劃空間，但此時(shí)生成的路徑將不再是最短的。由于通視圖不能表達(dá)物體運(yùn)動的方向性約束，除非運(yùn)動物體可以按任何方向以任意角度轉(zhuǎn)彎，通常很少用通視圖法求解實(shí)際的路徑規(guī)劃問題。 Voronoi圖法如果運(yùn)動物體要求與障礙(或威脅)的距離越遠(yuǎn)越好，可以采用Voronoi圖方法。Voronoi 圖由與兩個(gè)或多個(gè)障礙(或威脅)的給定特征元素距離相等的點(diǎn)的集合構(gòu)成。圖1-2 給出了以多邊形障礙物自身作為特征元素生成的Voronoi 圖。如果以多邊形的邊作為特征元素則可以得到不同的Voronoi 圖。對

4、于只包含有威脅的規(guī)劃空間來說，可以將威脅源的中心點(diǎn)作為特征元素。Voronoi圖將規(guī)劃空間分為多個(gè)區(qū)域，每個(gè)區(qū)域只包含一個(gè)特征元素。對于區(qū)域中的每一點(diǎn)，該區(qū)域的特征元素是所有特征元素中最近的。圖1-2 Voronoi 圖與通視圖比較，Voronoi 圖具有明顯的優(yōu)點(diǎn)，Voronoi 圖的邊數(shù)只有數(shù)量級0 (n)， 構(gòu)造Voronoi圖所需時(shí)間的數(shù)量級為0(nlogn),其中n為所選特征元素?cái)?shù)目。如果將多邊形的邊作為特征元素，則Voronoi圖一般都包含有曲線段。1987 年，Canny 和Donald通過使用一種不同于歐氏距離的度量方法，構(gòu)造出了一種只包含直線段的Voronoi 圖。對于維數(shù)大

5、于2的高維空間，通視圖與Voronoi圖將變得非常復(fù)雜，而且一般沒有確定的特征元素選擇方法。例如，多面體間的Voronoi 圖由二維曲面構(gòu)成，它不再是一維的輪廓線。盡管通視圖仍然可以由多面體的各項(xiàng)點(diǎn)間的連線組成，但此時(shí)最短路徑不再存在于通視圖之中(如圖1-3 所示)。因此，Voronoi圖一般只應(yīng)用于二維路徑規(guī)劃。圖1-3最短路徑不經(jīng)過多面體的頂點(diǎn) 輪廓線法對于高維空間，Canny 于1987 年給出了另一種構(gòu)造概略圖的方法。該方法先將高維空間中的物體投影到一個(gè)較低維的空間中，然后在低維空間中找出其投影的邊界曲線，稱為輪廓。該輪廓又投影到一個(gè)更低維的空間中，如此繼續(xù)下去，直到輪廓變成一維的輪廓

6、線。對于同一障礙物其輪廓不相連的部分，需用連接線將它們連接起來(如圖1-4 (b)所示)。這樣得到的一維輪廓線圖比原始的高維空間簡單得多，可以從中找到一條可行的路徑。該方法通常在理論上用于分析問題的復(fù)雜性，而很少用于實(shí)際中的路徑規(guī)劃。使用輪廓線方法得到的路徑，運(yùn)動物體總是沿著障礙物邊緣移動。圖1-4輪廓線 子目標(biāo)網(wǎng)絡(luò)法子目標(biāo)網(wǎng)絡(luò)方法不直接構(gòu)造明顯的概略圖，而是保存一個(gè)可以從起始點(diǎn)達(dá)到的節(jié)點(diǎn)列表。如果目標(biāo)點(diǎn)出現(xiàn)在該表中，則規(guī)劃成功結(jié)束。規(guī)劃空間中兩點(diǎn)之間的可達(dá)性由一個(gè)簡單的局部規(guī)劃算法來判斷，該局部規(guī)劃算法稱為局部算子。局部算子的選擇一般根據(jù)具體問題確定，例如，可以簡單地在兩節(jié)點(diǎn)之間按直線運(yùn)動。

7、開始的時(shí)候，該算法在起始節(jié)點(diǎn)與目標(biāo)點(diǎn)之間選取一個(gè)由稱為子目標(biāo)的中間節(jié)點(diǎn)組成的候選序列，并運(yùn)用局部算子依次連接這些子目標(biāo)。在選取子目標(biāo)候選序列時(shí)可以采用某些啟發(fā)式信息，也可以隨機(jī)選取。如果連接過程不能到達(dá)目標(biāo)點(diǎn)，則將已經(jīng)連接的子目標(biāo)保存在列表中。然后任取一個(gè)已到達(dá)的子目標(biāo)，并在該子目標(biāo)與目標(biāo)節(jié)點(diǎn)之間選取一個(gè)候選序列，如此反復(fù)，直至到達(dá)目標(biāo)節(jié)點(diǎn)。在該算法中，可到達(dá)的節(jié)點(diǎn)間的運(yùn)動路徑可以由局部算子非常容易地重新得到，因此不用保存。該算法的一個(gè)主要優(yōu)點(diǎn)是節(jié)省內(nèi)存空間。通視圖可以看作是一個(gè)子目標(biāo)網(wǎng)絡(luò)，其子目標(biāo)為障礙物的頂點(diǎn)，局部算子為“直線運(yùn)動”。圖1-5顯示了一個(gè)“沿對角線方向運(yùn)動”的局部算子生成的子

8、目標(biāo)網(wǎng)絡(luò)。圖1-5 子目標(biāo)網(wǎng)絡(luò)局部算子的選擇確定了規(guī)劃算法的實(shí)現(xiàn)。一種極端的情形是采用“直線運(yùn)動”，但當(dāng)兩個(gè)節(jié)點(diǎn)之間的距離很遠(yuǎn)時(shí)，該方法通常很難找到可行的路徑。因此，相鄰的兩個(gè)子目標(biāo)間的距離一般很近，這勢必增加子目標(biāo)的數(shù)目，從而增加內(nèi)存空間。另一個(gè)極端就是采用一種精確的全局規(guī)劃算法作為局部算子，此時(shí)僅有一個(gè)包含有起始點(diǎn)和目標(biāo)點(diǎn)的候選序列需要連接。這種方法將一個(gè)全局規(guī)劃問題分解成若千個(gè)比較簡單的局部規(guī)劃問題。 隨機(jī)路線圖法隨機(jī)路線圖法是近年發(fā)展起來的一種針對多自由度問題的路徑規(guī)劃方法，由Overmars等于1992年率先提出。該方法通過在規(guī)劃空間中隨機(jī)進(jìn)行采樣生成路線圖，然后在該路線圖中搜索路徑

9、。隨機(jī)路線圖的構(gòu)造如下:如果最新的采樣點(diǎn)與路線圖中的某節(jié)點(diǎn)間存在可行路徑，則將該采樣點(diǎn)加入到路線圖中，同時(shí)找出該節(jié)點(diǎn)與路線圖中的近鄰節(jié)點(diǎn)間可能存在的路徑，并將可行路徑作為節(jié)點(diǎn)間的邊加入到路線圖中。該方法的優(yōu)點(diǎn)之一就是可以在規(guī)劃時(shí)間和路徑的質(zhì)量之間進(jìn)行權(quán)衡，構(gòu)造隨機(jī)路線圖的時(shí)間越長，得到最優(yōu)路徑的可能性就越大。在確定環(huán)境下，隨機(jī)路線圖一般可以事先構(gòu)造。然而，如果規(guī)劃環(huán)境一日發(fā)生變化，隨機(jī)路線圖并不能通過局部更新以適應(yīng)新的環(huán)境，因此，該算法-般不適于在線實(shí)時(shí)應(yīng)用。簡要論述航路規(guī)劃啟發(fā)式搜索算法A*， .D*，anytime algorithms (ARA*)，anytime re-planning

10、 algorithms (AD*)的特點(diǎn)。A*A*（A-Star)算法是一種靜態(tài)路網(wǎng)中求解最短路最有效的方法。和Dijkstra一樣，A*能用于搜索最短路徑。和BFS一樣，A*能用啟發(fā)式函數(shù)引導(dǎo)它自己。它把Dijkstra算法（靠近初始點(diǎn)的結(jié)點(diǎn)）和BFS算法（靠近目標(biāo)點(diǎn)的結(jié)點(diǎn)）的信息塊結(jié)合起來。有點(diǎn)不同的是，類似BFS的啟發(fā)式方法經(jīng)常給出一個(gè)近似解而不是保證最佳解。然而，盡管A*基于無法保證最佳解的啟發(fā)式方法，A*卻能保證找到一條最短路徑。在討論A*的標(biāo)準(zhǔn)術(shù)語中，g(n)表示從初始結(jié)點(diǎn)到任意結(jié)點(diǎn)n的代價(jià)，h(n)表示從結(jié)點(diǎn)n到目標(biāo)點(diǎn)的啟發(fā)式評估代價(jià)（heuristic estimated co

11、st）。當(dāng)從初始點(diǎn)向目標(biāo)點(diǎn)移動時(shí)，A*權(quán)衡這兩者。每次進(jìn)行主循環(huán)時(shí)，它檢查f(n)最小的結(jié)點(diǎn)n，其中f(n) = g(n) + h(n)。保證找到最短路徑（最優(yōu)解的）條件，關(guān)鍵在于估價(jià)函數(shù)h(n)的選?。汗纼r(jià)值h(n)n到目標(biāo)節(jié)點(diǎn)的距離實(shí)際值，這種情況下，搜索的點(diǎn)數(shù)多，搜索范圍大，效率低。但能得到最優(yōu)解。如果估價(jià)值實(shí)際值,搜索的點(diǎn)數(shù)少，搜索范圍小，效率高，但不能保證得到最優(yōu)解。估價(jià)值與實(shí)際值越接近，估價(jià)函數(shù)取得就越好。A*算法的搜索過程實(shí)際上是被選節(jié)點(diǎn)擴(kuò)展的過程，它存在一種潛能，可以采用最少的估價(jià)源找到最近的優(yōu)化路徑。在確定優(yōu)化路徑后，要進(jìn)行航路回朔，計(jì)算是否滿足任務(wù)系統(tǒng)中設(shè)定的燃油、時(shí)間、速

12、度等約束條件(這些約束條件有一定的次序)。如果不能滿足所有的約束條件，則計(jì)劃就失敗，必須重新計(jì)劃并修改有關(guān)參數(shù)。啟發(fā)式函數(shù)h(n)告訴A*從任意結(jié)點(diǎn)n到目標(biāo)結(jié)點(diǎn)的最小代價(jià)評估值。例如對于幾何路網(wǎng)來說，可以取兩節(jié)點(diǎn)間歐幾理德距離（直線距離）做為估價(jià)值，即f=g(n)+sqrt(dx-nx)*(dx-nx)+(dy-ny)*(dy-ny)；這樣估價(jià)函數(shù)f在g值一定的情況下，會或多或少的受估價(jià)值h的制約，節(jié)點(diǎn)距目標(biāo)點(diǎn)近，h值小，f值相對就小，能保證最短路的搜索向終點(diǎn)的方向進(jìn)行。A*算法的關(guān)鍵是對評價(jià)函數(shù)的定義，從找到一條最小代價(jià)路徑的思路出發(fā)，在計(jì)算時(shí)可以把評價(jià)函數(shù)值分為從初始節(jié)點(diǎn)到節(jié)點(diǎn)n的代價(jià)，和

13、從節(jié)點(diǎn)n到達(dá)目標(biāo)節(jié)點(diǎn)的代價(jià)兩個(gè)部分來進(jìn)行計(jì)算和分析。估價(jià)函數(shù)的正確選取將直接關(guān)系到A*算法的成功與否，而函數(shù)的確定卻與實(shí)際情形有著密切的關(guān)系。所選擇的啟發(fā)式函數(shù)的好壞是很重要的。一個(gè)不恰當(dāng)?shù)膯l(fā)式函數(shù)反而會減慢A*算法，導(dǎo)致其產(chǎn)生出不好的路徑來。如果啟發(fā)式估值是精確的，則A*將不會偏離最佳路徑。當(dāng)然，很難得到一個(gè)精確的啟發(fā)式估值，但知道當(dāng)給A*一個(gè)正確的信息，它會正確地進(jìn)行操作，這是非常有用的。另外，如果啟發(fā)式估值趨向于精確值，則A*搜索操作就會越少。因此，f值的增加是與搜索的多少相關(guān)。當(dāng)啟發(fā)式估值是精確的，則f將不會變化。當(dāng)啟發(fā)式估值低于實(shí)際值太多，f值就會迅速地增加。啟發(fā)式越好，搜索的地方

14、就越少。當(dāng)探測器檢測到實(shí)際的環(huán)境和已知的環(huán)境信息存在差異時(shí),則更新原有的環(huán)境地圖信息,那么原先規(guī)劃的路徑也許就是不可通的或者不是最優(yōu)的。此時(shí),可以根據(jù)更新的環(huán)境信息重新規(guī)劃一條從當(dāng)前所在位置到目標(biāo)點(diǎn)的新的路徑,但是代價(jià)很大。據(jù)于此,Anthony Stentz提出的動態(tài)A*算法或者叫D*算法。D*A* 在靜態(tài)路網(wǎng)中非常有效，但不適于在動態(tài)路網(wǎng)，環(huán)境如權(quán)重等不斷變化的動態(tài)環(huán)境下。D*是動態(tài)A*（D-Star,Dynamic A Star）。相對于A*算法，D*算法的主要特點(diǎn)是可以應(yīng)用于環(huán)境僅為部分已知或環(huán)境不斷變化的情況下的路徑尋優(yōu)。該算法根據(jù)當(dāng)前已知環(huán)境狀況沿最有啟發(fā)性的節(jié)點(diǎn)搜索，如探測到下一

15、節(jié)點(diǎn)將會發(fā)生阻塞，則適時(shí)調(diào)整估價(jià)函數(shù)，改變方向繼續(xù)搜索，從而最終得到整個(gè)路徑。D*算法彌補(bǔ)了A*算法必須事先知道全部環(huán)境信息的缺點(diǎn)，且具有與A*算法一樣的高效特征。在環(huán)境信息是靜態(tài)的時(shí)候，D*的搜索方法和Dijkstra算法的搜索過程是一樣的。D*算法的主要過程分為離線和在線兩個(gè)部分。離線部分主要是指在已有的部分環(huán)境信息下規(guī)劃出一條機(jī)器人的行進(jìn)路徑;而在線部分主要指移動機(jī)器人在沿著離線部分規(guī)劃出的路徑行進(jìn)，當(dāng)遇到和己知的部分環(huán)境不相同的情況或者說接受到新的環(huán)境信息的時(shí)候，重新規(guī)劃一條從機(jī)器人當(dāng)前位置到目標(biāo)的路徑的過程。D*算法的作用相當(dāng)于靜態(tài)情況下，信息完全己知的情況下的路徑規(guī)劃算法。此時(shí)它的

16、執(zhí)行過程和Dijksart搜索算法相同，在離線情況下，基本的D*算法的效能是不及A*算法的。但是，A*算法利用啟發(fā)信息限制了搜索擴(kuò)展到的狀態(tài)，而其中一些沒有擴(kuò)展到的狀態(tài)很有可能是在后面的在線規(guī)劃中所需要用到的，因而D*必須使用這種離線的規(guī)劃方法。對于在線規(guī)劃部分，此時(shí)算法的執(zhí)行時(shí)間和很多因素直接相關(guān)，比如，預(yù)先己知的環(huán)境信息量，實(shí)際環(huán)境中障礙物密度，機(jī)器人環(huán)境傳感器感知范圍等。因此根前面的一般的重規(guī)劃方法相比，在相同的障礙物密度，相同的已知部分信息量，相同的感知范圍情況下，D*算法所重新規(guī)劃的環(huán)境中的狀態(tài)只是環(huán)境中的一部分，而一般的重規(guī)劃策略則需要在整個(gè)更新的環(huán)境中重新規(guī)劃。從這一點(diǎn)來說，該算

17、法是很有優(yōu)勢的。并且隨著環(huán)境大小的增加，算法比普通的最優(yōu)重規(guī)劃方法所節(jié)約的時(shí)間也成倍的增加。環(huán)境信息部分未知的情況下全局規(guī)劃部分很明顯需要一個(gè)重規(guī)劃的過程。這里的重規(guī)劃是指當(dāng)遇到已知環(huán)境與原有實(shí)際環(huán)境存在差異時(shí)，使得原有的全局規(guī)劃路徑無法通過而必須重新進(jìn)行的規(guī)劃。按照重規(guī)劃與原規(guī)劃的起點(diǎn)相同與否可以劃分為完全重規(guī)劃與不完全重規(guī)劃。所謂完全重規(guī)劃，是指重規(guī)劃路徑的起點(diǎn)與原規(guī)劃的起點(diǎn)相同，而不完全重規(guī)劃或部分重規(guī)劃則是指重規(guī)劃路徑的起點(diǎn)與原規(guī)劃的起點(diǎn)不同。動態(tài)的D*算法是不完全的重規(guī)劃，但是利用了原有的規(guī)劃信息，在一定程度上實(shí)現(xiàn)了最優(yōu)性和實(shí)時(shí)性的結(jié)合。D*算法做到全局規(guī)劃和局部信息相結(jié)合、離線的規(guī)

18、劃和在線的規(guī)劃相結(jié)合。D*的搜索步驟如下：1.先用Dijstra算法從目標(biāo)節(jié)點(diǎn)G向起始節(jié)點(diǎn)搜索。儲存路網(wǎng)中目標(biāo)點(diǎn)到各個(gè)節(jié)點(diǎn)的最短路和該位置到目標(biāo)點(diǎn)的實(shí)際值h,k（k為所有變化h之中最小的值,當(dāng)前為k=h。每個(gè)節(jié)點(diǎn)包含上一節(jié)點(diǎn)到目標(biāo)點(diǎn)的最短路信息1(2),2(5),5(4)，4（7）。則1到4的最短路為1-2-5-4。原OPEN和CLOSE中節(jié)點(diǎn)信息保存。2.機(jī)器人沿最短路開始移動，在移動的下一節(jié)點(diǎn)沒有變化時(shí)，無需計(jì)算，利用上一步Dijstra計(jì)算出的最短路信息從出發(fā)點(diǎn)向后追述即可，當(dāng)在Y點(diǎn)探測到下一節(jié)點(diǎn)X狀態(tài)發(fā)生改變，如堵塞。機(jī)器人首先調(diào)整自己在當(dāng)前位置Y到目標(biāo)點(diǎn)G的實(shí)際值h(Y)，h(Y)=

19、X到Y(jié)的新權(quán)值c(X,Y)+X的原實(shí)際值h(X).X為下一節(jié)點(diǎn)(到目標(biāo)點(diǎn)方向Y-X-G），Y是當(dāng)前點(diǎn)。k值取h值變化前后的最小。3.用A*或其它算法計(jì)算，這里假設(shè)用A*算法,遍歷Y的子節(jié)點(diǎn)，點(diǎn)放入CLOSE,調(diào)整Y的子節(jié)點(diǎn)a的h值，h(a)=h(Y)+Y到子節(jié)點(diǎn)a的權(quán)重C(Y,a),比較a點(diǎn)是否存在于OPEN和CLOSE中。D*算法在動態(tài)環(huán)境中尋路非常有效，向目標(biāo)點(diǎn)移動中，只檢查最短路徑上下一節(jié)點(diǎn)或臨近節(jié)點(diǎn)的變化情況，如機(jī)器人尋路等情況。對于距離遠(yuǎn)的最短路徑上發(fā)生的變化，則感覺不太適用。anytime algorithms (ARA*)在很多情況下，最短路徑不一定就是我們想要的，還需要考慮時(shí)間

20、等因素。在有限的時(shí)間內(nèi)得到好的、可行的結(jié)果才是我們想要的。ARA*算法就是解決這類問題的。Anytime算法是80年代末期Dean和Boddy在關(guān)于時(shí)間依賴規(guī)劃(Time-dependent planning)研究中提出的，其核心思想是使解的質(zhì)量隨計(jì)算時(shí)間的增加而不斷提高。它具有在求解質(zhì)量和求解時(shí)間之間折中的能力，被廣泛應(yīng)用于時(shí)間約束條件下復(fù)雜問題的近寸以求解。同時(shí)也提出了一種問題元級控制的方法，使得智能系統(tǒng)具有高層調(diào)度的能力，且擴(kuò)充了傳統(tǒng)算法的輸入一處理一輸出的計(jì)算過程，提供了運(yùn)行中動態(tài)輸出結(jié)果的功能。Anytime算法把每一組輸入和特定的計(jì)算時(shí)間映射為一組輸出結(jié)果，這一特征使得該算法可以在

21、任何時(shí)候被中斷，返回特定質(zhì)量的解，因此被稱為Anytime算法。從某種意義上說，具有如下特征的近以算法都可以稱為Anytime算法: 1.在算法執(zhí)行的任何時(shí)候都能給出問題的一個(gè)解; 2.解質(zhì)量隨計(jì)算時(shí)間的增加而提高?？梢钥闯鯝nytime算法是一個(gè)逐步求精的過程。在這一點(diǎn)上，許多現(xiàn)有的算法都可視為Anytime算法。如:計(jì)算方法中的迭代算法、迭代加深的啟發(fā)式搜索算法、各種貪心算法、利用隨機(jī)原理的蒙特卡歲方法、遺傳算法。這些傳統(tǒng)的Anytime算法是被動式的，缺乏完善的元級調(diào)度機(jī)制。研究者公認(rèn)，作為完善的Anytime算法，還應(yīng)該具有如下特征:1.質(zhì)量的度量Anytime算法用多值度量模型代替了

22、傳統(tǒng)的二值度量模型，因此解的質(zhì)量是可以度量的;它反映了近似解和真實(shí)解的質(zhì)量差距。 2.可預(yù)言性Anytime算法本身包含許多關(guān)于輸入、執(zhí)行時(shí)間和解質(zhì)量映射關(guān)系的統(tǒng)計(jì)信息，俠得算法可預(yù)言在一定計(jì)算時(shí)間內(nèi)輸出解的質(zhì)量，以便做高層的調(diào)度和控制。3.單調(diào)性Anytime算法具有解質(zhì)量隨執(zhí)行時(shí)間增加而單調(diào)增加的特性。這一點(diǎn)是以解質(zhì)量可以度量為前提的。只有這樣，Anytime算法才能隨計(jì)算時(shí)間的增加返回一個(gè)質(zhì)量更好的解，而不僅是最新產(chǎn)生的解。4.遞減性Anytime算法的解質(zhì)量在運(yùn)行的早期提高較快，隨著計(jì)算時(shí)間的增加，解質(zhì)量提高的速率會逐漸減小。中斷及可恢復(fù)性是Anytime算法最本質(zhì)的特性。它能在運(yùn)洲于

23、的任何時(shí)候停止，同時(shí)也能夠恢復(fù)執(zhí)行，且利用Anytime算法的系統(tǒng)能夠在運(yùn)行中重新分配計(jì)算資源。anytime algorithms (ARA*)算法在每次搜索中,根據(jù)新的因子的值,只處理在上次處理中可能不是有效的節(jié)點(diǎn)。首先,根據(jù)因子0的值通過A*算法來搜索路徑,只不過每個(gè)節(jié)點(diǎn)最多處理一次。在某次搜索過程中,如果某個(gè)節(jié)點(diǎn)已經(jīng)擴(kuò)展過,但是由于周圍于周圍節(jié)點(diǎn)之間邊的代價(jià)的改變需要再次處理時(shí),不是將其再放入OPEN表中處理,而是放入INCONS表中,當(dāng)本次搜索結(jié)束后,再將INCONS表中的節(jié)點(diǎn)全部插入OPEN表中用于下次搜索。這里INCONS表是用來保存這類已擴(kuò)展過但是需要再次處理的節(jié)點(diǎn)。這個(gè)算法在

24、兩個(gè)方面提高了每次搜索效率。首先,由于對每個(gè)節(jié)點(diǎn)最多只擴(kuò)展一次,所以路徑可以很快產(chǎn)生。其次,由于每次處理中,只處理在ICONS表中的節(jié)點(diǎn),所以以前搜索的結(jié)果可以重用。因此,當(dāng)因子的值在每次連續(xù)的搜索中減少時(shí),一個(gè)相對較少計(jì)算量就可以產(chǎn)生新結(jié)果。在A*算法時(shí)我們了解到：f(n)=g(n)+h(n)，用d(n)表達(dá)狀態(tài)n到目標(biāo)狀態(tài)的距離，那么h(n)的選取大致有如下三種情況：如果h(n)d(n)，搜索的點(diǎn)數(shù)少，搜索范圍小，效率高，但不能保證得到最優(yōu)解。當(dāng)h(n)d(n)的時(shí)候，會搜索較少的點(diǎn)，快速的產(chǎn)生一個(gè)解。ARA*算法就是用到了這一點(diǎn)。anytime re-planning algorithm

25、s (AD*)AD*算法就是結(jié)合了D*算法中的一升級版D*Lite算法和ARA*算法提出的一種新算法，兼顧D*Lite算法和ARA*算法的優(yōu)點(diǎn)。在AD*算法之前已經(jīng)存在了很多算法，如A*，D*，稀疏D*。由于它們有效的啟發(fā)函數(shù)和動態(tài)數(shù)據(jù)更新而被廣泛應(yīng)用。D*已經(jīng)被證明效率更高于A*，而稀疏D*在某些方面效率要高于D*。D*和稀疏D*都保證了最優(yōu)路徑并且是動態(tài)的算法，并且都適用于導(dǎo)航規(guī)劃。但總體說來，稀疏D*效率要高于D*而且容易理解。但是當(dāng)同時(shí)面對復(fù)雜規(guī)劃和動態(tài)環(huán)境時(shí)，將稀疏D*和ARA*結(jié)合起來，得到一種更高效的算法，即AD*算法。當(dāng)邊緣代價(jià)和膨脹因子發(fā)生變化時(shí)， AD*都能處理。當(dāng)出發(fā)點(diǎn)也

26、不斷變化時(shí)，AD*略作修改即可適應(yīng)這種情況。AD*比稀疏D*和ARA*更有優(yōu)勢，因?yàn)锳D*僅僅在當(dāng)前搜索路徑或即將導(dǎo)致搜索路徑矛盾時(shí)作出修改，這使得它效率更高。AD*在計(jì)算過程中盡可能的使用已經(jīng)計(jì)算好的路徑，當(dāng)遇到環(huán)境改變時(shí)，適當(dāng)?shù)倪x擇次優(yōu)解，以此來提高計(jì)算速度。當(dāng)環(huán)境的改變不可避免時(shí)，AD*有能力修改以往的路徑。最新的試驗(yàn)結(jié)果證明，在啟發(fā)式搜索算法這個(gè)大家庭中，AD*是一種在工程應(yīng)用中十分有效的算法。在動態(tài)路網(wǎng)，環(huán)境如權(quán)重等不斷變化的動態(tài)環(huán)境下，考慮時(shí)間等因素，在有限的時(shí)間內(nèi)得到好的、可行的結(jié)果。對下面的路標(biāo)圖，采用Greedy Best-First 或 A*搜索從Arad到Buchares

27、t的路徑，給出搜索過程結(jié)果。采用A*搜索搜索結(jié)果AradSibiuRimnicu VilceaPitestiBucharest總長度418實(shí)驗(yàn)代碼:class A_Starprivate:int MaxWeight=10000;stack s,ss;public:void A_Search(Graph g,int v0,int vg,int H)bool flag=true;int x;:2);f=x1.2+x2.2;%優(yōu)化目標(biāo)函數(shù)figure(1);contour3(x1,x2,f,15);figure(2);contour(x1,x2,f,15);x2=-x1-2;%約束條件hold on

28、;plot(x1,x2,*);結(jié)果：分析：最優(yōu)點(diǎn)為圖2中等高線與約束條件投影曲線相切點(diǎn)，此時(shí)約束條件滿足x1=-1,x2=-1;目標(biāo)函數(shù)最優(yōu)值為2，也即目標(biāo)函數(shù)的最小值。設(shè)函數(shù)，函數(shù)的定義域?yàn)?。?）利用牛頓法計(jì)算初值分別為和的疊代序列。（2）給出牛頓法疊代的準(zhǔn)確公式。答：（1）序列 （舍去）序列 （舍去）（2）XK+1=XK-9Xk-4ln(Xk-7).對圖1最短路徑問題，利用動態(tài)規(guī)劃原理求從點(diǎn)A到點(diǎn)B的最短路線。圖1 最短路徑問題程序代碼：ab=1 1 2 2 3 3 4 4 5 5 6 6 7 8 8 9 9 10 11 12 12 13 14 15;bb=2 3 4 5 5 6 7 8 8 9 9 10 11 11 12 12 13 13 14 14 15 15