靈活圖規(guī)劃框架下的時序規(guī)劃算法研究.pdf

1、智能規(guī)劃是人工智能的重要研究領(lǐng)域之一。1995年Blum和Furst提出了一種基于規(guī)劃圖的快速規(guī)劃方法一圖規(guī)劃，第一次采用圖的方式來解決規(guī)劃問題，在智能規(guī)劃領(lǐng)域中取得了革命性進(jìn)展。 靈活圖規(guī)劃(FGP)采用了圖規(guī)劃中圖擴(kuò)張與逆向解搜索結(jié)合的求解方式，在此基礎(chǔ)上，引入了命題真值度和目標(biāo)滿意度的概念，打破了圖規(guī)劃中嚴(yán)格的約束限制。每個問題中，約束與問題目標(biāo)各對應(yīng)一個數(shù)值來表示其重要程度，通過這些數(shù)值計算出靈活規(guī)劃的滿意度，從而來衡量

2、一個規(guī)劃的質(zhì)量優(yōu)劣。解決問題時，靈活規(guī)劃器產(chǎn)生滿意度不同的多個規(guī)劃，用戶可以根據(jù)自己實際情況的需要來選擇規(guī)劃解。 但靈活圖規(guī)劃中的動作為瞬時動作，規(guī)劃器無法處理規(guī)劃領(lǐng)域定義語言PDDL2.1中所定義的持續(xù)操作，即無法產(chǎn)生時序規(guī)劃。 本文提出了路徑圖和可移動動作的概念，并提出了一種算法，能夠解決帶有持續(xù)動作的靈活規(guī)劃問題。其基本過程是先通過靈活規(guī)劃圖擴(kuò)張與逆向解搜索結(jié)合的方法求解出由瞬時動作組成的靈活規(guī)劃解，再從靈活規(guī)劃圖

3、中提取出包含靈活規(guī)劃解的路徑圖。通過時序壓縮算法對靈活規(guī)劃解中動作的性質(zhì)進(jìn)行分析，找出可移動動作，使此類動作與其它層次動作并行以縮短規(guī)劃執(zhí)行時間。同時分析前后層動作之間的關(guān)系，為存在因果關(guān)系和互斥關(guān)系的動作設(shè)置時序約束條件。對動作的起止時間進(jìn)行賦值，使其滿足所有約束，從而獲得靈活時序規(guī)劃解。 靈活圖規(guī)劃框架下的靈活時序規(guī)劃算法，拓展了解決問題的范圍，具有處理持續(xù)動作和生成靈活時序規(guī)劃的能力，使生成的規(guī)劃解在時間上更加合理。本文用

4、Java語言在eclipse平臺下對算法進(jìn)行了實現(xiàn)，并對“l(fā)ogistics”域的問題進(jìn)行了實驗，實驗結(jié)果表明靈活時序規(guī)劃算法能夠比較快速有效地處理持續(xù)動作，生成靈活時序規(guī)劃解。 帶有持續(xù)動作的靈活規(guī)劃問題得到解決，將使靈活規(guī)劃問題更加準(zhǔn)確地描述及解決現(xiàn)實世界中的問題。靈活圖規(guī)劃是一個較新的研究領(lǐng)域，雖然靈活圖規(guī)劃是國內(nèi)外研究的熱點，但目前國內(nèi)外還沒有關(guān)于怎樣在靈活規(guī)劃框架下處理持續(xù)動作的研究。所以本文的研究工作在理論上具有很高