前向狀態(tài)空間搜索中并行規(guī)劃算法的研究及實(shí)現(xiàn).pdf

1、智能規(guī)劃是一個活躍的研究和應(yīng)用領(lǐng)域——它涉及到動作及規(guī)劃表示、規(guī)劃綜合與推理、規(guī)劃算法分析、規(guī)劃執(zhí)行等等。基于狀態(tài)空間搜索的規(guī)劃方法是該領(lǐng)域的一個研究熱點(diǎn)，基于前向狀態(tài)空間搜索的FF規(guī)劃器和基于后向狀態(tài)空間搜索的AItAlt規(guī)劃器都是其中的代表。它們所求得的規(guī)劃解都限制一個時間步只能執(zhí)行一個非空動作，規(guī)劃相對冗長，并且不完全符合現(xiàn)實(shí)應(yīng)用領(lǐng)域的需求?；跔顟B(tài)空間搜索的規(guī)劃方法在求解并行規(guī)劃上存在著指數(shù)分支因子的問題，基于后向狀態(tài)空間搜索的

2、并行規(guī)劃求解器AltAlt-p，它打破了這些限制，但是由于它針對目標(biāo)性較強(qiáng)并且剪枝過于嚴(yán)格，失去了一些求得次優(yōu)解的機(jī)會。 針對基于狀態(tài)空間搜索的并行規(guī)劃算法存在的這些問題，提出了基于前向狀態(tài)空間搜索的并行規(guī)劃算法。通過引入獨(dú)立動作以及動作間沖突的定義，實(shí)現(xiàn)了并行規(guī)劃，該方法不僅在一定程度上，彌補(bǔ)了原有規(guī)劃算法在完備性上的不足，并且在完備性和最優(yōu)性之間找到了一個平衡點(diǎn)。PPFF算法充分利用了放寬規(guī)劃圖的特性，提高了規(guī)劃器的求解質(zhì)量