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

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

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

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

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

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

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

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

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

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