支持強(qiáng)偏序約束的智能規(guī)劃與調(diào)度方法研究.pdf

1、隨著人工智能的快速發(fā)展，智能無(wú)人平臺(tái)逐漸向小型化和智能化轉(zhuǎn)變，多無(wú)人平臺(tái)的高效協(xié)同將在未來(lái)的信息化戰(zhàn)場(chǎng)、太空探索、搶險(xiǎn)救援等領(lǐng)域有著廣泛而深入的應(yīng)用。在該問題背景下，當(dāng)目標(biāo)任務(wù)隨機(jī)到達(dá)，目標(biāo)之間存在強(qiáng)偏序約束，且目標(biāo)任務(wù)的執(zhí)行時(shí)間和執(zhí)行的成功概率都具有時(shí)間相關(guān)不確定時(shí)，為了實(shí)現(xiàn)多無(wú)人平臺(tái)之間的在線協(xié)同，滿足在線計(jì)劃過程中的時(shí)效性，需要設(shè)計(jì)高效的在線規(guī)劃與調(diào)度方法，實(shí)時(shí)的生成執(zhí)行計(jì)劃，并優(yōu)化調(diào)度相關(guān)的無(wú)人平臺(tái)去執(zhí)行。本文以此為研究目的，主

2、要討論：如何建立智能規(guī)劃與優(yōu)化調(diào)度相結(jié)合的在線計(jì)劃系統(tǒng)；如何利用智能規(guī)劃語(yǔ)言PDDL進(jìn)行計(jì)劃問題的描述與建模，描述無(wú)人平臺(tái)之間的協(xié)同交互關(guān)系；如何在目標(biāo)任務(wù)之間存在強(qiáng)偏序約束的情況下快速搜索執(zhí)行目標(biāo)任務(wù)的行動(dòng)序列；以及如何在時(shí)間相關(guān)不確定環(huán)境下，針對(duì)規(guī)劃過程生成的行動(dòng)序列進(jìn)行行動(dòng)的起止時(shí)間推理和無(wú)人平臺(tái)的在線優(yōu)化調(diào)度，獲得全局較優(yōu)計(jì)劃方案。本研究主要內(nèi)容包括：
　?、沤⒘穗x線狀態(tài)下基于運(yùn)籌學(xué)方法的問題模型，并討論了在線計(jì)劃框架和

3、基于PDDL的規(guī)劃問題建模。文中通過基于運(yùn)籌學(xué)方法的問題建模，對(duì)本文研究問題的特點(diǎn)和問題求解的復(fù)雜度進(jìn)行了詳細(xì)討論；然后，根據(jù)智能規(guī)劃和運(yùn)籌學(xué)中優(yōu)化調(diào)度的各自特點(diǎn)，設(shè)計(jì)了智能規(guī)劃與優(yōu)化調(diào)度相結(jié)合的在線計(jì)劃系統(tǒng)框架。文中以單艦的不同武器平臺(tái)自動(dòng)協(xié)同防空為例，討論了針對(duì)某一給定規(guī)劃問題的PDDL描述與建模方法，為后續(xù)的智能規(guī)劃搜索算法提供模型基礎(chǔ)，并以該案例為背景，討論了艦艇防空的在線計(jì)劃系統(tǒng)的運(yùn)行流程，設(shè)計(jì)開發(fā)了艦艇防空的在線計(jì)劃仿真實(shí)驗(yàn)

4、平臺(tái)。
　?、铺岢隽艘?guī)劃過程中的死鎖檢測(cè)算法和多步前向搜索算法，用于解決初始狀態(tài)下目標(biāo)任務(wù)之間存在強(qiáng)偏序約束的規(guī)劃問題。在該類問題中，目標(biāo)任務(wù)的實(shí)現(xiàn)順序必須滿足初始狀態(tài)下存在的偏序約束，搜索過程一旦違背任何偏序約束都會(huì)導(dǎo)致搜索過程進(jìn)入死鎖?，F(xiàn)有的規(guī)劃算法在規(guī)劃解的搜索過程中，不能準(zhǔn)確發(fā)現(xiàn)該類問題中目標(biāo)任務(wù)之間的強(qiáng)偏序約束關(guān)系，從而無(wú)法快速獲得規(guī)劃解。本文針對(duì)這一問題，構(gòu)建了基于目標(biāo)實(shí)現(xiàn)圖的死鎖檢測(cè)算法，該算法能快速預(yù)測(cè)搜索過程中因

5、違背目標(biāo)任務(wù)之間的強(qiáng)偏序約束而導(dǎo)致的顯性和隱性死鎖，從而引導(dǎo)多步前向搜索過程快速向目標(biāo)狀態(tài)逼近，并快速返回規(guī)劃解。文中對(duì)算法的復(fù)雜度、充分性和適用領(lǐng)域進(jìn)行了討論，并通過三個(gè)不同領(lǐng)域的規(guī)劃問題將本文算法和歷年的冠軍規(guī)劃器進(jìn)行了實(shí)驗(yàn)對(duì)比，驗(yàn)證了本文算法在解決該類問題時(shí)的充分性和有效性。
　?、翘岢霾⒔鉀Q了因相斥目標(biāo)實(shí)現(xiàn)行動(dòng)導(dǎo)致的強(qiáng)偏序約束規(guī)劃問題。在該類規(guī)劃問題的初始狀態(tài)下，目標(biāo)任務(wù)之間不存在任何強(qiáng)偏序約束。但是隨著規(guī)劃過程的進(jìn)行，由

6、于相斥目標(biāo)實(shí)現(xiàn)行動(dòng)的存在，對(duì)某一目標(biāo)任務(wù)實(shí)現(xiàn)過程中的目標(biāo)實(shí)現(xiàn)行動(dòng)的選擇不當(dāng)，可能給后續(xù)的規(guī)劃過程中引入目標(biāo)實(shí)現(xiàn)順序的強(qiáng)偏序約束。文中對(duì)該類問題的性質(zhì)進(jìn)行了分析，并從理論和實(shí)驗(yàn)上論證了該類問題的復(fù)雜性。通過對(duì)前面提出的死鎖檢測(cè)算法的進(jìn)一步拓展，提出了以相斥目標(biāo)實(shí)現(xiàn)行動(dòng)集為啟發(fā)式函數(shù)的多步前向搜索算法，并對(duì)算法的復(fù)雜度、算法求解該類問題的充分性和算法適合的問題特點(diǎn)進(jìn)行了討論。而且，文中構(gòu)造了以編隊(duì)艦艇防空為背景的相斥目標(biāo)實(shí)現(xiàn)行動(dòng)導(dǎo)致的強(qiáng)偏序

7、約束規(guī)劃問題，通過與歷年的冠軍自動(dòng)規(guī)劃器相比較，充分顯示了現(xiàn)有規(guī)劃算法在求解這一新的規(guī)劃問題時(shí)存在的不足，以及本文算法在求解該類規(guī)劃問題時(shí)的有效性。
　　⑷研究了基于重計(jì)劃的在線計(jì)劃優(yōu)化方法。在線過程中，由于目標(biāo)任務(wù)的連續(xù)隨機(jī)到達(dá)和計(jì)劃執(zhí)行結(jié)果的不確定性，當(dāng)前的計(jì)劃策略不可避免的存在“短視”現(xiàn)象。在對(duì)未來(lái)目標(biāo)任務(wù)到達(dá)分布未知的情況下，為了能夠獲得全局較優(yōu)解，文中設(shè)計(jì)了基于重計(jì)劃的在線規(guī)劃與調(diào)度策略，對(duì)當(dāng)前已經(jīng)生成但還未執(zhí)行的目標(biāo)任

8、務(wù)的計(jì)劃方案進(jìn)行在線優(yōu)化處理，以獲得全局較優(yōu)解。重計(jì)劃過程具備實(shí)時(shí)性，充分考慮算法耗時(shí)對(duì)計(jì)劃過程的影響、行動(dòng)的時(shí)間推理、以及無(wú)人平臺(tái)之間的最優(yōu)化協(xié)同調(diào)度。文中以單艦的不同武器平臺(tái)的協(xié)同防空為仿真案例，設(shè)計(jì)開發(fā)了仿真實(shí)驗(yàn)平臺(tái)，驗(yàn)證了重計(jì)劃的在線優(yōu)化方法在獲取全局較優(yōu)解時(shí)的有效性，且用于重計(jì)劃的時(shí)間越長(zhǎng)，對(duì)全局解的優(yōu)化程度越高。
　?、裳芯苛嘶诜稚⑹今R爾科夫決策過程的在線計(jì)劃方法。該研究主要針對(duì)能準(zhǔn)確估計(jì)未來(lái)目標(biāo)任務(wù)到達(dá)的概率分布，

9、目標(biāo)任務(wù)的執(zhí)行持續(xù)時(shí)間和計(jì)劃執(zhí)行的成功概率都具有時(shí)間相關(guān)不確定性，以及不允許進(jìn)行重計(jì)劃情況下的在線計(jì)劃方法。針對(duì)每一個(gè)到達(dá)的目標(biāo)任務(wù)，既要考慮調(diào)度無(wú)人平臺(tái)以最大期望完成該目標(biāo)任務(wù)，又要確保該決策造成的潛在機(jī)會(huì)損失最小，以獲得計(jì)劃過程的全局較優(yōu)解。文中采用基于分散式馬爾科夫決策過程的在線計(jì)劃模型，模型的收益函數(shù)考慮了當(dāng)前的決策收益和未來(lái)潛在的機(jī)會(huì)損失，并以編隊(duì)的艦艇防空為案例，設(shè)計(jì)開發(fā)了仿真實(shí)驗(yàn)平臺(tái)，通過仿真實(shí)驗(yàn)論證了考慮潛在機(jī)會(huì)損失的計(jì)