基于合作博弈的智能集群自主聚集研究

基于合作博弈的智能集群自主聚集研究收稿收稿日期：2015-基金項目：國家863計劃資助項目(2014AA7041002)作者簡介：王訓（1989-），男，湖南常德人，博士研究生，Email:wangxun1989@王兆魁（通信作者），男，副教授，博士生導師，Email:wangzk@王訓1王兆魁2張育林1,2（1.國防科學技術(shù)大學航天科學與工程學院，長沙410073；2.清華大學航天航空學院，北京100084）摘要：以無人車集群系統(tǒng)協(xié)同監(jiān)視再入體著靶過程為任務背景，開展智能集群自組織策略相關(guān)技術(shù)研究。設計了無人車集群執(zhí)行再入體著靶協(xié)同監(jiān)視的集群行為模式，針對協(xié)同監(jiān)視過程中的集群聚集行為，提出了基于合作博弈的智能集群自主聚集策略，各智能體以實現(xiàn)群體聚集為“合作目標”，以降低自身能量消耗為“競爭目標”，開展博弈，基于微粒群算法規(guī)劃局部路徑，最終使群體系統(tǒng)涌現(xiàn)出聚集行為。仿真實驗驗證了設計的自主聚集策略的有效性。關(guān)鍵詞：智能集群，無人車，再入體，合作博弈，自主聚集中圖分類號：TP181文獻標志碼：A文章編號：ResearchofIntelligentSwarm’sAutonomousAggregationBasedonCooperativeGameWangXun1WangZhaokui2ZhangYulin1,2（1.CollegeofAerospaceScienceandEngineering,NationalUniversityofDefenseTechnology,Changsha410073;2.SchoolofAerospace,TsinghuaUniversity,Beijing10084）Abstract:Unmannedgroundvehicleswarmisproposedtomonitortheprocessofreentryvehiclelanding.Techniquesaboutintelligentswarmself-organizingstrategyareresearched.Swarmbehaviorpatternsaboutunmannedvehicleswarmcollaborativelymonitoringtheprocessofreentryvehiclelandingaredesignedandtheswarmself-organizingstrategybasedoncooperativegameispresented.EachAgentregardsachievingswarmaggregationandsavingenergyastopgoalandcarriesoutgaming.FinallyParticleSwarmOptimizationisusedtoprogramlocalpathandaggregationbehaviorbecomereality.Simulationexperimentprovetheeffectivenessoftheautonomousaggregationstrategy.Keywords:IntelligentSwarms,unmannedvehicle,reentryvehicle,cooperativegame,autonomousaggregation蜂群、蟻群、鳥群是自然界中十分普遍的生物集群現(xiàn)象，集群中個體微不足道，它們卻能通過彼此交互，自組織工作，使群體涌現(xiàn)出各種復雜行為，集群的能力遠遠超過單個個體的能力，甚至超過個體能力簡單數(shù)量上的疊加[1,2]。源于對自然界生物集群的啟發(fā)，國內(nèi)外眾多學者和研究機構(gòu)在對單機器人系統(tǒng)、多機器人系統(tǒng)研究的基礎上，開始了對群體機器人系統(tǒng)的研究，美國國家航天局提出了自主納衛(wèi)星集群（TheAutonomicNanoTechnologySwarm，ANTS）計劃，將利用1000顆航天器組成的群體對位于火星和木星軌道之間小行星帶進行探測[3]。在美國國防部先進研究項目局的支持下，美國賓夕法尼亞州費城大學提出了一種自適應自主空/地機器人群組，通過形成立體視覺網(wǎng)絡，實現(xiàn)對城市環(huán)境下各種目標的探測[4]。再入體著靶過程監(jiān)視是火箭裝備研制、定型過程中的關(guān)鍵環(huán)節(jié)，由于再入體著靶時散布區(qū)域大、落點存在偏差，因此固定式的遠距離探測系統(tǒng)無法及時準確的捕獲著靶過程。借鑒生物集群和群體機器人系統(tǒng)的研究成果，開展無人車集群系統(tǒng)執(zhí)行再入體著靶過程監(jiān)視的研究，無人車集群攜帶多傳感器設備，在再入體著靶過程中，通過機動探查、抵近監(jiān)視、協(xié)同觀測，獲取再入體運動軌跡、幾何外形、信號、光學等基本特征。本文重點探討無人車集群的自組織策略，包括各種組織方式、信息交互方式、進化機制等問題，通過無人車之間的協(xié)同工作，適應復雜的動態(tài)環(huán)境，高效的完成任務。目前集群系統(tǒng)自組織策略的研究主要基于一致性算法和虛擬勢場法展開。RenW等人率先對一致性算法開展研究[5-7]，證明了群體系統(tǒng)中的智能體在特定通信拓撲約束下，協(xié)作變量達到一致的條件，以此為基礎，設計了群體系統(tǒng)形成特定構(gòu)型的編隊算法，提出的包容控制算法，解決了群體系統(tǒng)在一定范圍內(nèi)的聚集問題。但是一致性算法難以求得最優(yōu)解，同時當通信拓撲結(jié)構(gòu)切換時，一致性要求很難達到。VeyselGazi，M.Passino等人從虛擬勢場的角度，開展了集群自主實現(xiàn)聚集、覓食、編隊等行為的研究，并研究了集群行為達到穩(wěn)定的條件，分析了各項勢函數(shù)的吸引排斥作用,以及利用滑模控制實現(xiàn)復雜系統(tǒng)的集群行為[8-10]。但是采用基于虛擬勢函數(shù)的集群控制，系統(tǒng)達到的平衡點為各個智能體初始位置的平均值，且在進行控制時也沒有考慮智能體自身能量的消耗。并且一致性算法和虛擬勢場法都需要滿足復雜的約束，才能確保群體系統(tǒng)最終的穩(wěn)定性。本文以無人車集群系統(tǒng)協(xié)同監(jiān)視再入體著靶過程為任務背景，首先對無人車集群實施對再入體著靶協(xié)同監(jiān)視的任務模式和集群行為進行設計，重點針對無人車集群的聚集行為和指標進行了分析。以此為基礎，設計了一種綜合考慮群體聚集目標和節(jié)約自身能量消耗目標，使無人車集群涌現(xiàn)出聚集行為的自組織策略，并對該自組織策略進行了仿真實驗驗證。1、無人車集群實施再入體著靶協(xié)同監(jiān)視任務模式分析1.1再入體著靶協(xié)同監(jiān)視系統(tǒng)構(gòu)成實施再入體著靶協(xié)同監(jiān)視的無人車集群由多輛無人車（UnmannedGroundVehicle,UGV）構(gòu)成，無人車攜帶全球定位系統(tǒng)（GlobalPositioningSystem,GPS）等慣性導航設備，對自身進行定位，攜帶光學觀測、雷達探測等載荷，對再入體著靶過程進行協(xié)同監(jiān)視，攜帶無線通信節(jié)點，接受地面測控站發(fā)出的目標位置信息，同時向無人車集群廣播自身的位置信息和探測到的目標信息，各無人車接收到其余無人車的信息后，通過自主分析任務目標，執(zhí)行自組織策略，完成任務。利用無人車集群實施對再入體著靶協(xié)同監(jiān)視的運行過程如下：地面站產(chǎn)生動態(tài)目標方位信息，將此信息廣播給所有的無人車移動平臺；各個無人車利用GPS獲取定位信息，并將自己的位置信息廣播給其它無人車；各個無人車根據(jù)自身位置信息和其它無人車的位置信息，協(xié)同機動，形成對動態(tài)目標的全方位、多角度觀測；并將觀測數(shù)據(jù)發(fā)送給地面站，完成整個再入體著靶協(xié)同監(jiān)視。無人車集群執(zhí)行再入體著靶協(xié)同監(jiān)視示意圖如圖1所示。圖1無人車集群執(zhí)行再入體著靶協(xié)同監(jiān)視示意圖Fig.1SchematicdiagramofUGVswarmcollaborativelymonitoringtheprocessofreentryvehiclelanding以無人車集群實現(xiàn)再入體著靶協(xié)同監(jiān)視的運行過程為基礎，分析單個無人車完成任務的決策過程，決策過程如圖2所示。圖2無人車任務執(zhí)行決策過程Fig.2Decision-makingprocessofUGV無人車分析再入體著靶協(xié)同監(jiān)視任務，產(chǎn)生完成任務所需的基本行為規(guī)則，包括集群聚集、分散、編隊、以及個體的碰撞避免，在完成任務的過程中，無人車需要根據(jù)集群中其余無人車的運行情況，采取適當?shù)男袨?，例如在聚集或者分散機動過程中，當無人車檢測到可能發(fā)生碰撞時，需要切換到碰撞避免行為，因此在行為規(guī)則的基礎上，需要選取特定行為，然后驅(qū)動底層的機動控制，完成具體行為，確保順利完成任務。1.2無人車集群自主聚集任務分析在集群的聚集、分散、編隊、碰撞避免等眾多行為中，聚集行為是一種基本的行為，其他集群行為都可以以聚集行為為基礎開展研究，同時多群體機器人系統(tǒng)的工程實現(xiàn)，都是以聚集行為為基礎。因此，在研究無人車集群實現(xiàn)再入體著靶協(xié)同監(jiān)視的過程中，重點分析無人車集群自主聚集行為實現(xiàn)。首先給出集群系統(tǒng)自主聚集行為實現(xiàn)的定義：考慮一個由個智能體組成的智能集群系統(tǒng)，智能體狀態(tài)為，，各個智能體之間保持一定距離，定義輸入作用于各個智能體，使得當時，對于所有智能體和，有，則稱智能集群系統(tǒng)最終實現(xiàn)聚集[11]，為集群最終形成聚集范圍的大小指標。不失一般性，假設應用于靶場探測的無人車智能體為一階積分系統(tǒng)。無人車智能體的動力學模型為：（1）式（1）中，表示無人車集群系統(tǒng)中各無人車智能體的個數(shù)，和分別為第個無人車智能體的狀態(tài)和控制輸入。將（1）式離散化后，得到無人車智能體的離散動力學模型。（2）式（2）中，為第個無人車智能體在時刻的狀態(tài)，為第個無人車智能體在時刻的狀態(tài)，為第個無人車智能體時刻的控制輸入，它與自身的狀態(tài)和集群中其余智能體的狀態(tài)有關(guān)。2、基于合作博弈的智能集群自主聚集策略設計2.1、智能集群自主聚集策略本文設計的智能集群自主聚集策略的目的是為了使智能體涌現(xiàn)出聚集行為，其算法流程圖如圖3所示。圖3智能集群自主聚集策略流程圖Fig.3Flowchartofintelligentswarm’sautonomousaggregationstrategy智能集群自主聚集策略中，首先使各智能體隨機分布在一定位置，此后，各智能體分布式的執(zhí)行基于合作博弈的局部路徑規(guī)劃（下一小節(jié)有介紹），進而得到各智能體的最新位置，此時各智能體進行判斷，是否符合集群聚集行為達到的條件，如果不達到，則繼續(xù)執(zhí)行基于合作博弈的局部路徑規(guī)劃，如果達到，則結(jié)束算法，得到聚集行為滿足時的各智能體位置。2.2、智能體合作博弈思想達到聚集行為是整個智能集群系統(tǒng)的統(tǒng)一目標，各個智能體在進行行為選擇時，只有使群體系統(tǒng)最終聚集，各智能體的行為選擇才是有效的。但是由于集群系統(tǒng)中，不存在全局的控制器，各智能體在作出決策時，難以找到一個符合最終條件的全局最優(yōu)解，可能只存在pareto最優(yōu)解。各智能體在進行行為決策時，會進行博弈，不但為了達到聚集的目標，同時還會以降低自身能量消耗為優(yōu)化指標進行行為選擇，上述思想即為各智能體為形成集群聚集行為的合作博弈思想。智能體在進行局部路徑規(guī)劃時，以下述兩式作為優(yōu)化指標。（3）（4）式（3）中表示的是第個智能體進行第步?jīng)Q策時自身能量的消耗，以此為優(yōu)化指標，最小化，體現(xiàn)的是智能體的“自私性”，各智能體進行博弈，期望自身能量消耗最少。式（4）中表示的是第個智能體進行第步?jīng)Q策時，其第步狀態(tài)與其它智能體第步狀態(tài)之差的絕對值的和，為期望的下一步狀態(tài)，代表第個智能體通信范圍內(nèi)的其它智能體第步狀態(tài)。為了達到各智能體狀態(tài)最終聚集，希望最小化代價函數(shù)，體現(xiàn)的是智能體的“合作性”，各智能體以此方式進行合作，最終使智能集群系統(tǒng)涌現(xiàn)出聚集行為。2.3、基于微粒群算法求解局部路徑重新考慮智能體的動力學方程式（2），，為第個智能體時刻的控制輸入，它與智能體自身的狀態(tài)和能感知到的環(huán)境中其余智能體的狀態(tài)有關(guān)。令滿足下列關(guān)系式：（5）表示與智能體通信范圍內(nèi)的其余的智能體，將式（2）、（5）代入到式（3）、（4）中，得到：（6）（7）其中，，由于和均為已知量，因此基于合作博弈思想的智能體局部路徑規(guī)劃就是求解，使得和最小。同時設計時考慮到智能體速度的限制：（8）即每個智能體速度不超過其最大速度。因此，智能體在基于合作博弈的思想進行局部路徑規(guī)劃的問題可歸納總結(jié)為下式：（9）針對式（9）所述帶約束多目標優(yōu)化問題，假設每個智能體能得到其余智能體信息，即。在求解時，利用線性加權(quán)法處理多目標優(yōu)化，利用懲罰函數(shù)法處理約束，因此可將式（9）所述的帶約束多目標優(yōu)化問題轉(zhuǎn)化為下式：（10）其中、為多目標優(yōu)化的加權(quán)項，為懲罰函數(shù)，采用微粒群優(yōu)化算法求解，首先隨機初始化一群微粒，為設計微粒群算法時選取的微粒個數(shù)。設為微粒的當前位置，為微粒的當前飛行速度，每個微粒根據(jù)自己的歷史個體極值和群體歷史全局極值來更新自己的速度和位置[12]。微粒群算法的進化方程式是：（11）是粒子在第代的速度，是粒子在第代的位置，是介于之間的隨機數(shù)，，是加速度因子，通常在間取值。式（11）中的第一部分是粒子先前的速度；第二部分為“認知”部分，表示粒子自身的經(jīng)驗；第三部分為為“社會”部分，表示粒子間的信息共享。這三部分共同決定粒子的空間搜索能力。通過調(diào)整，參數(shù)，可以影響不同部分的權(quán)重，從而影響微粒群算法的性能。微粒群算法的實現(xiàn)步驟如下：Step1初始化一群微粒，包括微粒的隨機位置和速度；Step2根據(jù)優(yōu)化指標函數(shù)計算每個微粒的優(yōu)化指標值；Step3對每個微粒，將其優(yōu)化指標值與歷史個體極值作比較，如果較好，則將其作為當前的最好位置；Step4對每個微粒，將其優(yōu)化指標值與群體歷史全局極值作比較，如果較好，則將其作為當前的全局最好位置；Step5根據(jù)上兩式對微粒的速度和位置進行進化；Step6如未達到結(jié)束條件（通常為足夠好的優(yōu)化指標值或達到一個預設最大代數(shù)），則返回Step2。利用上述微粒群算法，各智能體求得使優(yōu)化指標值最小的，作為的取值，從而完成局部路徑規(guī)劃，每個智能體在完成局部路徑規(guī)劃后，按照1.2節(jié)所述，判斷是否達到集群系統(tǒng)形成聚集的條件，否則繼續(xù)執(zhí)行自主聚集策略。3、無人車集群自主聚集仿真實驗在進行無人車集群自主聚集的仿真實驗中，用智能體表示無人車智能集群系統(tǒng)中的每個無人車。首先選取智能集群系統(tǒng)中智能體的個數(shù)，假設由20個智能體構(gòu)成了智能集群系統(tǒng)，則。初始化各智能體的位置，將平面內(nèi)的位置變量作為各智能體的狀態(tài)變量，即，其中代表智能體水平方向的位置，代表智能體豎直方向的位置，隨機選取二維標準正態(tài)分布中的20個點，作為智能體的初始位置。聚集范圍的大小指標，設置初始化各智能體的速度限制。在利用微粒群算法求解各智能體的局部路徑規(guī)劃時，需要設置微粒群優(yōu)化算法的參數(shù)，設置粒子個數(shù)，多目標優(yōu)化的加權(quán)項，，加速度因子，。得到基于競爭合作的智能集群自主聚集策略的仿真結(jié)果，如圖4和圖5所示。（a）智能體位置變化圖（a）PositionalterationofAgent（b）智能體最終位置圖（b）FinalpositionofAgent圖4基于競爭合作的智能集群自主聚集策略的仿真結(jié)果（）Fig.4Simulationresultsofintelligentswarm’sautonomousaggregationstrategybasedoncooperativegame（）圖4為設置智能體的最大速度限制時，基于競爭合作的智能集群自主聚集策略的仿真結(jié)果。從圖中可知，二十個智能體位置初始分布在，的區(qū)域，經(jīng)過多次迭代后，智能體最終收斂在，的區(qū)域。通過該仿真證明，基于競爭合作的智能集群自主聚集策略能夠使集群系統(tǒng)最終收斂到一定范圍內(nèi)，實現(xiàn)群體的聚集行為。（a）智能體位置變化圖（a）PositionalterationofAgent（b）智能體最終位置圖（b）FinalpositionofAgent圖5基于競爭合作的智能集群自主聚集策略的仿真結(jié)果（）Fig.5Simulationresultsofintelligentswarm’sautonomousaggregationstrategybasedoncooperativegame（）圖5為設置智能體的最大速度限制時，基于競爭合作的智能集群自主聚集策略的仿真結(jié)果。從圖中可知，二十個智能體的位置初始分布在，的區(qū)域，經(jīng)過多次迭代后，智能體最終收斂在，的區(qū)域。上述兩個實驗證明了基于競爭合作的智能集群自組織策略實現(xiàn)無人車集群聚集行為的有效性。第二次實驗與第一次實驗結(jié)果相比，只是智能體的最大速度限制的取值不同，第二次取值較大，從圖中能看出，這樣的變化使得智能體移動軌跡較為平滑。4、結(jié)論本文以無人車構(gòu)成的集群系統(tǒng)應用于再入體著靶監(jiān)視為背景，以實現(xiàn)群體聚集為目標，設計了一種基于合作博弈的智能集群自主聚集策略。運用博弈論的思想，設計了既考慮合作目標和自身能量消耗的優(yōu)化指標，基于微粒群算法規(guī)劃出局部路徑。該自組織策略通過個體的迭代優(yōu)化求解，無需對群體的穩(wěn)定性進行復雜的數(shù)學分析，最終使群體系統(tǒng)涌現(xiàn)出聚集行為，同時魯棒性較強，可為研究群體系統(tǒng)的更多群體行為提供指導。參考文獻（References）吳啟迪,康琦,汪鐳,陸金山.自然計算導論[M].上海：上?？茖W技術(shù)出版社,2011.WuQidi,Kangqi,Wanglei,LuJingshan.AnIntroductionToNature-InspiredComputation[M].Shanghai:ShangHaiScientificandTechnicalPublishers,2011.(inChinese)Kauffman,S..OriginsofOrder:Self-OrganizationandSelectioninEvolution[M].Oxford:OxfordUniversityPress,1993.Truszkowski,W.,HaroldHallock,ChristopherRouff,etal.AutonomousandAutonomicSystems:WithApplicationstoNASAIntelligentSpacecraftOperationsandExplorationSystems[M].Berlin:Springer,2009.Hsieh,M.A.,AnthonyCowley,JamesF.Keller,etal.AdaptiveTeamsofAutonomousAerialandGroundRobotsforSituationalAwareness[J].JournalofFieldRo