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

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

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

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

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