[發(fā)明專利]一種多智能體高階信念認(rèn)知規(guī)劃器實(shí)現(xiàn)方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201611139540.3
• 申請(qǐng)日: 2016-12-12
• 公開（公告）號(hào): CN106779046A
• 公開（公告）日: 2017-05-31
• 發(fā)明（設(shè)計(jì)）人: 黃曉;劉詠梅
• 申請(qǐng)（專利權(quán)）人: 中山大學(xué)
• 主分類號(hào): G06N3/00
• 分類號(hào): G06N3/00
• 代理公司: 廣州粵高專利商標(biāo)代理有限公司44102
• 代理人: 林麗明

技術(shù)領(lǐng)域

本發(fā)明涉及計(jì)算理論下人工智能的自動(dòng)化規(guī)劃領(lǐng)域，更具體地，涉及一種多智能體高階信念認(rèn)知規(guī)劃器實(shí)現(xiàn)方法。

背景技術(shù)

自動(dòng)化規(guī)劃是人工智能領(lǐng)域中的一個(gè)極其重要的分支。其主要目的在于描述實(shí)際應(yīng)用場景中的實(shí)體與動(dòng)作，并自動(dòng)生成能夠達(dá)到某一目標(biāo)的動(dòng)作樹或者動(dòng)作序列。而要實(shí)現(xiàn)這個(gè)目標(biāo)，我們需要通過形式化方法來表示實(shí)體的知識(shí)庫、動(dòng)作的前提與效果、目標(biāo)等。在此基礎(chǔ)上，我們可以嘗試對(duì)此進(jìn)行實(shí)驗(yàn)，實(shí)現(xiàn)正確的、能夠處理一系列規(guī)劃實(shí)例的應(yīng)用規(guī)劃器，從而自動(dòng)生成可行正確的規(guī)劃方案，來解決各種規(guī)劃問題。

就自動(dòng)化規(guī)劃領(lǐng)域而言，經(jīng)典規(guī)劃是目前各種主流研究工作的重要基礎(chǔ)。經(jīng)典規(guī)劃可以憑借其以下特點(diǎn)對(duì)其他類型的規(guī)劃加以區(qū)分，即其狀態(tài)變遷系統(tǒng)是可完全觀察的、確定性的、有限的、與靜態(tài)的，而且也往往伴隨著受限的目標(biāo)。

然而，隨著自動(dòng)化規(guī)劃理論體系的不斷鞏固與拓展，人們發(fā)現(xiàn)許多現(xiàn)實(shí)生活中的實(shí)際情景無法得到很好的表達(dá), 許多規(guī)劃問題實(shí)例也無法以傳統(tǒng)的經(jīng)典規(guī)劃方法得到解決。相對(duì)于傳統(tǒng)不帶認(rèn)知模態(tài)算子的規(guī)劃，擁有自身知識(shí)庫與信念的智能體能夠擁有更加強(qiáng)大的表達(dá)能力；相對(duì)于傳統(tǒng)的單智能體規(guī)劃，有許多設(shè)計(jì)涉及智能體間互動(dòng)的規(guī)劃問題僅僅在多智能體設(shè)定下能得到解決方案；相對(duì)于過去可完全觀察的、確定性的，靜態(tài)的環(huán)境，如今存在大量部分可觀察的、隨機(jī)的、動(dòng)態(tài)的規(guī)劃問題當(dāng)且僅當(dāng)在多智能體認(rèn)知規(guī)劃的理論體系下才能得到解決。

由此可見，多智能體認(rèn)知規(guī)劃是目前規(guī)劃領(lǐng)域中一個(gè)重要的問題。與傳統(tǒng)的經(jīng)典規(guī)劃不同，當(dāng)一個(gè)規(guī)劃問題里存在多個(gè)智能體時(shí)，我們不僅僅要處理某一個(gè)智能體個(gè)體所擁有的知識(shí)與信念的推理，而且要面臨智能體對(duì)相互之間的信念的推理問題以及智能體群體的公共知識(shí)問題。這往往導(dǎo)致了一個(gè)尋求可行規(guī)劃算法搜索空間的急劇膨脹。除此之外，引入智能體間互動(dòng)后，要給出智能體如何做知識(shí)更新與演進(jìn)的自然的、可行的語義定義，會(huì)顯得十分困難。在此情況下，尋求出一種對(duì)多智能體認(rèn)知規(guī)劃的、擁有良好性質(zhì)的形式化定義，在目前自動(dòng)化規(guī)劃領(lǐng)域有著非常重要的意義。

傳統(tǒng)的自動(dòng)化規(guī)劃不僅在學(xué)術(shù)上有著重大的意義，而且在工業(yè)界更是有廣泛的應(yīng)用，例如救援仿真機(jī)器人系統(tǒng)，以及實(shí)現(xiàn)日常生活當(dāng)中的消防、醫(yī)療、警衛(wèi)智能體等等。因此，多智能體認(rèn)知規(guī)劃無論是在學(xué)術(shù)上與工業(yè)界都有更加深遠(yuǎn)的意義與光明的前景。在理論上，它能給出擁有更強(qiáng)表達(dá)能力的規(guī)劃語言，拓展規(guī)劃領(lǐng)域中能夠建模的問題范圍。而在實(shí)際應(yīng)用上，它能指導(dǎo)仿真機(jī)器人群體互動(dòng)等的技術(shù)實(shí)現(xiàn)，促進(jìn)機(jī)器人完成更加復(fù)雜的語言與行為。

對(duì)多智能體認(rèn)知規(guī)劃進(jìn)行研究，將推動(dòng)多智能體規(guī)劃在現(xiàn)實(shí)和研究中的應(yīng)用，豐富多智能體規(guī)劃的理論基礎(chǔ)，為其他類型更為復(fù)雜的規(guī)劃問題提供解決問題的新思路。

發(fā)明內(nèi)容

本發(fā)明為克服上述現(xiàn)有技術(shù)所述的至少一種缺陷，提供一種多智能體高階信念認(rèn)知規(guī)劃器實(shí)現(xiàn)方法。

為解決上述技術(shù)問題，本發(fā)明的技術(shù)方案如下：

一種多智能體高階信念認(rèn)知規(guī)劃器實(shí)現(xiàn)方法，包括以下步驟：

S1：輸入epddl文件，通過語言編譯器將epddl文件轉(zhuǎn)化為帶K模動(dòng)態(tài)詞的公式樹，所述epddl文件是對(duì)多智能體認(rèn)知規(guī)劃問題的智能體個(gè)數(shù)、動(dòng)作的前提與效果，初始知識(shí)庫與目標(biāo)進(jìn)行描述的集成文件；

S2：將公式樹轉(zhuǎn)化為CDF(Cover Disjunctive Formula)范式，CDF范式表示一個(gè)知識(shí)庫；

S3：將得到的CDF范式作為初始知識(shí)庫輸入到PrAO規(guī)劃算法，所述PrAO規(guī)劃算法為多智能體高階信念認(rèn)知規(guī)劃器求解算法；

S4：PrAO規(guī)劃算法通過用鏈表這種數(shù)據(jù)結(jié)構(gòu)進(jìn)行建圖并生成解。

在一種優(yōu)選的方案中，步驟S1-S2中，使用lex+yacc將epddl文件轉(zhuǎn)化為帶K模動(dòng)態(tài)詞的公式樹，其中l(wèi)ex為生成掃描器工具，yacc為語法分析器工具，兩者均為開源資源，操作系統(tǒng)為Linux或者M(jìn)ac。

在一種優(yōu)選的方案中，步驟S1-S2中，將epddl語言描述的初始知識(shí)庫、動(dòng)作的前提與效果、目標(biāo)取下來用C++中特定的數(shù)據(jù)結(jié)構(gòu)存放，然后用一個(gè)類去實(shí)現(xiàn)CDF范式，最終再將原來的數(shù)據(jù)結(jié)構(gòu)用CDF范式的類去表示

在一種優(yōu)選的方案中，步驟S4中，具體包括以下步驟：

S4.1：判斷初始知識(shí)庫是否蘊(yùn)含目標(biāo)，若否，則構(gòu)造根節(jié)點(diǎn)并跳轉(zhuǎn)到步驟S4.2，若是，則返回空；

S4.2：判斷所有可達(dá)節(jié)點(diǎn)是否已探索過，若否，則選取一個(gè)為探索的可達(dá)節(jié)點(diǎn)并跳轉(zhuǎn)到步驟S4.3，若是，則返回空；

S4.3：計(jì)算可執(zhí)行動(dòng)作的集合S；