Đề tài Multi - Objective drone path planning for search and rescue with quality - of - service requirements

Multi-objective drone path planning for search and rescue with quality-of-service requirements Samira Hayat1 · Evs¸en Yanmaz2 · Christian Bettstetter1 · Timothy X. Brown3 Received: 9 July 2019 / Accepted: 12 June 2020 Trình bày: Đặng Thái Sơn - KHMT k63 1. Mở đầu 2. Các đề tài liên quan 3. Mô tả hệ thông 4. Thuật toán lập kế hoạch 5. Kết quả 1. Mở đầu Máy bay không người lái (UAV), thường được gọi là máy bay không người lái, được sử dụng trong tìm kiếm và cứu nạn (SAR), theo dõi và giám sát, cung cấp mạng và các ứng dụng khác. Trong công việc trước đây, nhóm tác giả đã nghiên cứu các yêu cầu về lưu lượng và kết nối của các ứng dụng bay không người lái (Hayat và cộng sự 2016) và sử dụng kiến ​​thức để thiết kế thuật toán lập kế hoạch đường dẫn đa mục tiêu (MOPP) (Hayat và cộng sự 2017 ). Một tham số duy nhất λ được sử dụng để điều chỉnh giữa vùng phủ sóng và kết nối. λ = 1 : Tối ưu hóa vùng phủ sóng λ = 0 : Tối ưu hóa kết nối λ = 0,5 : Vùng phủ sóng và kết nối quan trọng như nhau Sơ lược về giải thuật MOPP:  MOPP là một thuật toán lập kế hoạch đường đi nhiều giai đoạn với trọng tâm đặc biệt là các nhiệm vụ SAR . GĐ 1: Mục đích của giai đoạn 1 (vùng phủ sóng) là tìm kiếm một mục tiêu đứng yên trên một khu vực riêng biệt bằng cách sử dụng các bước thời gian rời rạc. Điều này được thực hiện bởi các tác vụ tìm kiếm. GĐ 2: Mục đích của giai đoạn 2 (kết nối) là phổ biến thông tin trong mạng. Nó bao gồm hai nhiệm vụ: Nhiệm vụ thông báo mang thông tin vị trí mục tiêu đến trạm gốc mặt đất (BS). Nhiệm vụ giám sát thiết lập một liên kết chất lượng dịch vụ (QoS) tốt nhất giữa vị trí mục tiêu và BS 2. Các đề tài liên quan Việc sử dụng máy bay không người lái đã được đề xuất để phát hiện mục tiêu trong Flint et al. (2002), Gan và Sukkarieh (2011), Lin và Goodrich (2009), Waharte và Trigoni (2010), York và Pack (2012 ), sử dụng các thuật toán tìm kiếm đã được sử dụng để lập kế hoạch đường đi. Các công trình này tập trung vào phát hiện mục tiêu (giai đoạn 1), sử dụng các thuật toán cung cấp khả năng bao phủ khu vực nhanh (Waharte và Trigoni 2010), hoặc tối đa hóa xác suất tích lũy để phát hiện mục tiêu (Lin và Goodrich 2009). Tuy nhiên, việc hoàn thành thành công các nhiệm vụ tìm kiếm không chỉ dựa vào việc xác định vị trí mục tiêu mà còn phải thông báo cho BS về vị trí. Thông báo cho BS yêu cầu một số hình thức kết nối trong mạng. Khả năng kết nối là một hạn chế Hầu hết các công trình nghiên cứu về phạm vi phủ sóng của nhiều máy bay không người lái giả định kết nối hình đĩa cơ bản giữa các máy bay không người lái Đề xuất của nhóm tác giả Đề xuất 2 chiến lược thích ứng SIC với QoS (SICQ): tối ưu hóa các nhiệm vụ tìm kiếm, thông báo và đồng thời giám sát SIC tuân theo QoS (SIC +) đầu tiên tối ưu hóa tìm kiếm và thông báo các nhiệm vụ cùng nhau sau đó tìm các vị trí tối ưu để theo dõi Cả hai chiến lược đều sử dụng thông tin ngay khi có sẵn để xác định nhiệm vụ của các UAV. Các chiến lược có thể được điều chỉnh để ưu tiên các nhiệm vụ nhất định so với những nhiệm vụ khác Họ minh họa rằng có thể thực hiện nhiều nhiệm vụ hơn trong thời gian nhiệm vụ nhất định bằng cách kết hợp hiệu quả thông tin liên lạc trong thiết kế đường dẫn. và cũng nhận thấy rằng chất lượng của các đường dẫn kết quả được cải thiện về mặt kết nối. 3. Mô tả hệ thống Bài toán đặt ra yêu cầu với một nhiệm vụ SAR với nhiều UAV và một mục tiêu đứng yên tại một vị trí không xác định trong khu vực giới hạn. Trước khi nhiệm vụ bắt đầu, người lập kế hoạch đường dẫn được thông báo về khu vực tìm kiếm, công nghệ truyền thông (ví dụ: tốc độ dữ liệu có sẵn), nhu cầu QoS (ví dụ: thông lượng hoặc độ trễ) và các hạn chế về năng lượng . Trong giai đoạn 1, các đường dẫn tìm kiếm được lên kế hoạch trước được chỉ định cho các máy bay không người lái. Giai đoạn 1 hoàn thành khi một UAV phát hiện mục tiêu. UAV này di chuyển phía trên mục tiêu như một UAV cảm biến. Giai đoạn 2 bắt đầu khi một UAV thứ hai trong phạm vi liên lạc của UAV cảm biến. Sau đó, UAV thứ hai hoạt động như một mule data và bay trên một con đường trực tiếp để thông báo cho BS về vị trí mục tiêu . Một UAV đi theo đường bao phủ của nó cho đến khi nó được thông báo về việc phát hiện mục tiêu. Sau đó, nó từ bỏ lộ trình phủ sóng và cập nhật kế hoạch truyền bá thông tin mục tiêu qua mạng. Khi các UAV tiếp xúc với nhau và học được thông tin mới, chúng sẽ lập kế hoạch lại. Việc lập kế hoạch lại tiếp tục cho đến khi giai đoạn kết nối hoàn tất. Các ký hiệu Từ quan điểm thiết kế thuật toán, nhiệm vụ được hoàn thành khi đường dẫn QoS đã được thiết lập. Tổng thời gian nhiệm vụ là τ = τS + τI + τM . Thời gian cần thiết của UAV m để hoàn thành bước k trong phạm vi phủ song của nó đường đi p m k là T m k = t m k + t s Với t s là thời gian không đổi để cảm nhận 1 ô Thời gian Δ k cần thiết để các UAV trong chuyến bay kết thúc bước k là Δ k = max{ T m k } Do đó thời gian kết thúc của τS là τS = 4 . Thuật toán lập kế hoạch 4.1 Giai đoạn phủ sóng 4.2 Giai đoạn kết nối Giai đoạn kết nối tiếp theo các UAV trong U trực hiện các nhiệm vụ thông báo và giám sát. Nếu tại k1 s nằm trong phạm vi của BS thì τI = 0 vào các thuật toán phía sau sẽ không được thực hiện. Các trường hợp giả thiết sau sẽ chỉ xét đến trường hợp BS không được thông báo vị trị mục tiêu tại k1, các UAV còn lại trong U nói chung không biết được rằng mục tiêu đã được xác định do đó tiếp tục tìm kiếm. Có 4 cách để 1 UAV m có thể có trong phạm vi của s : + Hai UAV liên kết trực tiếp giữa chúng khi s được gán nhãn + Hai UAV có giao tiếp trực tiếp mối liên hệ của chúng trong các bước tiếp theo trong khi s nằm trên L và m theo dõi đường dẫn xác định của nó + Hai UAV dự kiến có thể ở trong phạm vi của nhau trong tương lại, nếu m ko thế kết nối với s trong thời gian này nó giả định s đã phát hiện mục tiêu và bắt đầu truy tìm đường đi của s cho đến khi phát hiện thấy s + Nếu không UAV còn lại nào trong U xuất hiện trong phạm vi của s thì sau khi quay trở lại BS các UAV M-1 bắt đầu sau đường đi của s cho tới khi phát hiện ra s Tại k2 có 3 trường hợp cần lập lại kế hoạch đường dẫn TH1: W0 trống một UAV gần nhất với W0 được chọn ra từ R di chuyển đến và chiếm lĩnh W0 các UAV con lại trong R sẽ di chuyển dần đến các W gần nhất mà chưa được sử dụng bởi bất kì UAV nào trong R TH2: W0 bị chiếm các và các w còn lại chưa bị chiếm BS đã được thông báo về vị trí mục tiêu, các UAV còn lại thuộc R\ rd lập lại kế hoạch đường đi của chúng để đặt chúng ở gần vị trí W còn lại gần điểm W0 nhất TH3: Tất cả các W đã bị chiếm giữ BS đã được thông báo về mục tiêu các UAV còn lại quay về BS 4.3 Lập kế hoạch đường dẫn đa mục tiêu với GA Hàm mục tiêu cho SIC+ τ   SIC + =  E  [  λτ S  +  (  1 -  λ) τ I  +  τ M  |  P  ]  Hàm mục tiêu cho SICQ τ  SICQ =  E  [  (λτ S  +  (  1 -  λ) (τ I  +  τ M ))  |  P  ]  Trong đó P = { P 1 , P 2 , . . . PN } Pn = { pn 1 , pn 2 , . . . pnM }  5. Kết quả Để minh họa những lợi ích của việc kết hợp giao tiếp như một mục tiêu nhiệm vụ thay vì là một ràng buộc, nhóm tác giả đã so sánh MOPP đối với thuật toán liên quan liên quan, cụ thể là đối với thuật toán đường chân trời ngắn (SH, với bế tắc) và đường ngắn thuật toán hợp tác đường chân trời (SHC, tránh bế tắc ) ( Scherer và Rinner 2017 ). Nhóm tác giả thấy rằng SIC + nhanh hơn khoảng 33% so với SH và nhanh hơn SHC khoảng 64%; SICQ khoảng 23% nhanh hơn SH và nhanh hơn 59% so với SHC