一種用於海上搜尋力量任務分配的搜尋區域劃分方法及系統的製作方法
2023-09-22 02:25:20 1
一種用於海上搜尋力量任務分配的搜尋區域劃分方法及系統的製作方法
【專利摘要】本發明公開了一種用於海上搜尋力量任務分配的搜尋區域劃分方法及系統，所述方法包括如下步驟：初始化待搜尋海域的面積、搜尋力量的種類和數量、各搜尋力量的搜尋面積和初始位置；輸入待搜尋區域所等效的凸多邊形的頂點信息、各搜尋力量的初始位置點信息；根據初始化待搜尋海域的面積、搜尋力量的種類和數量、各搜尋力量的搜尋面積、待搜尋區域所等效的凸多邊形的頂點信息、各搜尋力量的初始位置點信息採用凸多邊形剖分方法對待搜尋區域進行剖分；輸出顯示剖分後的各子區域和子區域內包括的搜尋力量的初始位置點信息；本發明能夠根據各搜尋力量的搜尋能力，將搜尋區域剖分成適合搜尋作業的子區域，使搜尋力量更加高效協同工作。
【專利說明】一種用於海上搜尋力量任務分配的搜尋區域劃分方法及系統
【技術領域】
[0001]本發明涉及一種用於海上搜尋力量任務分配的搜尋區域劃分方法及系統。
【背景技術】
[0002]海上遇險事故發生後，立即開展高效的搜尋行動、及早發現遇險目標並對其實施有效救助對於挽救生命和減少財產損失意義重大。海上搜尋行動是在特定地理範圍內開展的，該範圍是由搜尋計劃人員確定的最有可能包含遇險目標的搜尋區域；為了保證搜尋的高效性，當搜尋區域範圍很大且遇險目標位置在該區域內的概率分布為均勻分布時，應對其進行合理剖分，形成搜尋子區域即搜尋分區，並分別指派給每個搜尋力量協同開展行動，從而迅速實現對整個區域的完全覆蓋。在海上搜尋實踐中，通常採用多邊形來建模搜尋區域，搜尋區域的大小等於多邊形面積，近年來，國內外針對移動機器人、無人航空器在陸地上如何開展協同工作方面進行了大量的研究，其中不少都涉及到了區域剖分問題。
【發明內容】
[0003]本發明針對以上問題的提出，而研製一種能夠根據各搜尋力量的搜尋能力，將搜尋區域剖分成多個形狀大小合適且適合搜尋作業的子區域，使搜尋力量更加高效協同工作的用於海上搜尋力量任務分配的搜尋區域劃分方法及系統。
[0004]本發明的技術手段如下:
[0005]一種用於海上搜尋力量任務分配的搜尋區域劃分方法，包括如下步驟:
[0006]步驟一:
[0007]確定待搜尋海域，並利用凸多邊形對待搜尋區域建模；
[0008]步驟二:
[0009]初始化待搜尋海域的面積、搜尋力量的種類和數量、各搜尋力量的搜尋面積和初始位置；
[0010]步驟三:
[0011]輸入待搜尋區域所等效的凸多邊形的頂點信息、各搜尋力量的初始位置點信息；
[0012]步驟四:
[0013]根據初始化待搜尋海域的面積、搜尋力量的種類和數量、各搜尋力量的搜尋面積、待搜尋區域所等效的凸多邊形的頂點信息、各搜尋力量的初始位置點信息採用凸多邊形剖分方法對待搜尋區域進行剖分；
[0014]步驟五:
[0015]輸出顯示剖分後的各子區域和子區域內包括的搜尋力量的初始位置點信息；
[0016]進一步地，所述步驟二具體為:
[0017]設定待搜尋海域所等效的凸多邊形P的面積為Area (P);設定m艘船舶和η架飛機在該待搜尋海域內開展搜尋行動，第i架飛機的搜尋面積為片1，其中i e {1，…，η}，第j艘船舶的搜尋面積為f 其中j e {1，...，πι}，且
【權利要求】
1.一種用於海上搜尋力量任務分配的搜尋區域劃分方法，其特徵在於包括如下步驟: 步驟一: 確定待搜尋海域，並利用凸多邊形對待搜尋區域建模； 步驟二: 初始化待搜尋海域的面積、搜尋力量的種類和數量、各搜尋力量的搜尋面積和初始位置； 步驟三: 輸入待搜尋區域所等效的凸多邊形的頂點信息、各搜尋力量的初始位置點信息； 步驟四: 根據初始化待搜尋海域的面積、搜尋力量的種類和數量、各搜尋力量的搜尋面積、待搜尋區域所等效的凸多邊形的頂點信息、各搜尋力量的初始位置點信息採用凸多邊形剖分方法對待搜尋區域進行剖分； 步驟五: 輸出顯示剖分後的各子區域和子區域內包括的搜尋力量的初始位置點信息。
2.根據權利要求1所述的一種用於海上搜尋力量任務分配的搜尋區域劃分方法，其特徵在於所述步驟二具體為: 設定待搜尋海域所等效的凸多邊形P的面積為Area (P);設定m艘船舶和η架飛機在該待搜尋海域內開展搜尋行動，第i架飛機的搜尋面積為^，其中ie {I,…，n}，第j艘船
舶的搜尋面積為J 其中j e {I,…，m}，且
3.根據權利要求2所述的一種用於海上搜尋力量任務分配的搜尋區域劃分方法，其特徵在於所述步驟三具體為: 輸入待搜尋區域所等效的凸多邊形P的頂點集合V(CP);輸入頂點和錨點的集合W(CP),所述W(CP) = (CO1，…，ω,}，其中COk為錨點或凸多邊形P的頂點，多個頂點和錨點按照逆時針順序排列；輸入錨點集合S (CP) Jy^iiS(CP) = {S1;…，StJ，其中Sq為錨點，多個錨點按照其在集合W (CP)的排列順序進行排列。
4.根據權利要求3所述的一種用於海上搜尋力量任務分配的搜尋區域劃分方法，其特徵在於步驟四包括如下步驟: 步驟1:設置掃描線L，該掃描線的起點為集合W(CP)中的第一個點O1，終點為集合S(CP)中的第一個錨點S1，執行步驟2 ； 步驟2:將錨點S1置於集合只CP/)中，其中集合RCP/)為掃描線L右邊的錨點集合，執行步驟3 ； 步驟3:計算掃描線L右邊的多邊形面積)，執行步驟4 ；步驟 4:判斷是否 Areu[CP;:) < Area ReCiuired(S(CF:))且 Le 關 S,，其中 Areu(CP[)為掃描線L右邊的多邊形面積、AreaRoclI,ired{S{CP； ))為集合5'(C7^)中錨點對應的搜尋力量的搜尋面積、Le為掃描線L的終點、Sq為集合S(CP)中的最後一個錨點，是則執行步驟5，否則執行步驟8 ； 步驟5:當Le在集合W(CP)中的序號大於I時判斷Le的前一個點是否為錨點，是則執行步驟6，否則執行步驟7，其中Le為掃描線L的終點； 步驟6:將Le的前一個點置於集合WCP/)中，其中集合 Area Rcciuired{S{CP；))且 Le = S1，其中)為掃描線L右邊的多邊形面積、為集合S(C/f)中錨點對應的搜尋力量的搜尋面積、Le為掃描線L的終點、Si為集合S(CP)中的第一個錨點，是則執行步驟9，否則執行步驟IO ； 步驟9:沿著掃描線L右邊的多邊形CP/逆時針移動掃描線L的起點直至AreuiCP;:) = Arm Recjkired(S(CP；；))，其中 Area(Ci);:)為掃描線 L 右邊的多邊形面積、中錨點對應的搜尋力量的搜尋面積，執行步驟14 ;步驟 10:判斷是否 Απ^Ρ;:))，其中 『4reu(CP;:)為掃描線 L 右邊的多邊形面積、AreciRcqiiired(S(CP;:))為集介S(CC)中錨點對應的搜尋力量的搜尋面積，執行步驟14 ；步驟12:在Le的前一個點與Le構成的邊上通過內插法找到點t，使得當Le為點tIN', Arca(CP；；) = Area Re Cj uired(S (CP:；))，其中 /iw/(C70 為掃描線 L 右邊的多邊形面積、Area Rcquircd{S(CP[))、J、j ^<\S(CP[):戶錨點對應的搜尋力量的搜尋面積、Le為掃描線L的終點，執行步驟13 ； 步驟13:將點t作為新的Le，其中Le為掃描線L的終點，執行步驟14 ； 步驟14:移動掃描線L的起點Ls和終點Le保證jrea(CP/)保持不變，直至多邊形CF/的最小內角最大化，執行步驟15 ； 步驟15:根據/irtY/?) = /ir(Y/(CP)-計算得出掃描線L左邊的多邊形面積Area(CP[)，其中Area (CP)是凸多邊形P的面積、Area{CP[)為掃描線L右邊的多邊形面積，執行步驟16 ； 步驟16:根據掃描線L左邊的錨點集合S(Cg)等於錨點集合S(CP)減去掃描線L右邊的錨點集合只CP/)計算得出S(CPl)。
5.根據權利要求4所述的一種用於海上搜尋力量任務分配的搜尋區域劃分方法，其特徵在於步驟五包括如下步驟: 輸出Area(CP[)和Area(CP[)並顯示，輸出S(CP[)和S(CP[)並顯示。
6.一種用於海上搜尋力量任務分配的搜尋區域劃分系統，其特徵在於包括: 用於確定待搜尋海域，並利用凸多邊形對待搜尋區域建模的建模單元； 用於初始化待搜尋海域的面積、搜尋力量的種類和數量、各搜尋力量的搜尋面積和初始位置的初始化單元； 連接建模系統，用於輸入待搜尋區域所等效的凸多邊形的頂點信息、各搜尋力量的初始位置點信息的輸入單元； 連接初始化系統和輸入系統，用於根據初始化待搜尋海域的面積、搜尋力量的種類和數量、各搜尋力量的搜尋面積、待搜尋區域所等效的凸多邊形的頂點信息、各搜尋力量的初始位置點信息採用凸多邊形剖分方法對待搜尋區域進行剖分的剖分系統； 連接剖分系統，用於輸出顯示剖分後的各子區域和子區域內包括的搜尋力量的初始位置點信息的顯示單元。
7.根據權利要求1所述的一種用於海上搜尋力量任務分配的搜尋區域劃分系統，其特徵在於所述剖分系統包括: 用於設置掃描線L的起點為集合W(CP)中的第一個點O1，終點為集合S(CP)中的第一個錨點S1的第一設置單元； 用於將錨點S1置於集合只CF/)中 的第一操作單元，其中集合S(CP/)為掃描線L右邊的錨點集合； 連接初始化單元、輸入單元、第一設置單元和第一操作單元，用於計算掃描線L右邊的多邊形面積Im(OY)的第一計算單元； 連接初始化單元和第一計算單元，用於判斷是否-4rm(CP;') <Area Re quired (S (CP；；))且Le古Sq的第一判斷單元，其中Area(CP[)為掃描線L右邊的多邊形面積、AreaRequired(SiCPD)為集合S{CP[)中錨點對應的搜尋力量的搜尋面積、Le為掃描線L的終點、Sq為集合S(CP)中的最後一個錨點； 連接輸入單元和第二判斷單元，用於當—(CP;:) < Area Rcc!uircd(S(CP；；))且Le Φ S,、以及Le在集合W(CP)中的序號大於I時，判斷Le的前一個點是否為錨點的第二判斷單元；連接第二判斷單元，用於當Le的前一個點為錨點時，將Le的前一個點置於集合S(CZf)中的第二操作單元，其中集合S(CZ)!')為掃描線L右邊的錨點集合，其中Le為掃描線L的終佔.連接第一判斷單元，用於當乂層(C/O Area Re c, ui red (S (CP；；)) Π.1v = S丨的第三判斷單元,其中Area(CP[)為掃描線L右邊的多邊形面積、Area Required(SiCP;'Y)為集合S(CT,)中錨點對應的搜尋力量的搜尋面積、Le為掃描線L的終點、S1為集合S(CP)中的第一個錨點； 連接第一設置單元和第三判斷單元，用於當Areu(CP;:) > Area Re cjuircdiSiCP；))且L6 = S1時，沿著掃描線L右邊的多邊開(I逆時針移動掃描線L的起點直至Area(CP[) = AreaRQquired(S(CP[))的第一處理單元，其中Area(CP[)為掃描線L右邊的多邊形面積、Areci Rcquired(S(CPf ))為集介5K)十鋪點對應的搜尋力量的搜尋面積； 連接第三判斷單元，用於判斷是否AreuiCP;:) < Area Recjuired(S(CP1''))且Le = Sq的第四判斷單元，其中AreaiCPD為掃描線L右邊的多邊形面積、AreaRQquired(S(CP[))為集合S(CZf)中錨點對應的搜尋力量的搜尋面積、Le為掃描線L的終點、Sq為集合S(CP)中的最後一個錨點； 連接第四判斷單元，用於當Areu(CP[) < AreuRcquirediSiCP; ))且Le=Sq時，沿著掃描線L右邊的多邊3 CP順時針移動掃描線L的起點直至Area{CP[) = AreaReqmred(S(CP[))的第二處理單元，其中Area(CP[)為掃描線L右邊的多邊形面積、AreaRoquired(S(CP:))為集合S(Cf)中錨點對應的搜尋力量的搜尋面積； 連接第四判斷單元，用於當Areu(CP;J < Areu Rc_Kd(S(CP;.)、且Le < Sq時，在Le的前一個點與Le構成的邊上通過內插法找到點t,使得當Le為點t時，Area(CP[) = AreaR^quired(S(CP[))的查找單元，其中Area(CP[)為掃描線L右邊的多邊形面積、AreaRQquired(S(CP[))為集合只CP/)中錨點對應的搜尋力量的搜尋面積、Le為掃描線L的終點； 連接查找單元，用於當Areu(CP[) < Re屮〃_/w/(5XCTf))且Le < Sq時，將點t作為新的Le的第三設置單元，其中Le為掃描線L的終點； 連接第一處理單元、第二處理單元和第三設置單元，用於移動掃描線L的起點Ls和終點Le保證2rea(CP/)保持不變，直至多邊形CF/的最小內角最大化的第三處理單元； 連接第三處理單元，用於根據Areu(CP;) = Area(CP) - AreaiCP；)計算得出掃描線L左邊的多邊形面積的第二計算單元，其中Area(CP)是凸多邊形P的面積、Area{CP'；)為掃描線L右邊的多邊形面積； 連接第三處理單元，用於根據掃描線L左邊的錨點集合S(Of )等於錨點集合S(CP)減去掃描線L右邊的錨點集合計算得出S(CP/)的第三計算單元。
【文檔編號】G06F19/00GK103699799SQ201310732746
【公開日】2014年4月2日 申請日期:2013年12月26日 優先權日:2013年12月26日
【發明者】邢勝偉, 張英俊, 楊雪鋒, 李元奎, 劉 文 申請人:大連海事大學