多機器人在樹結構上最小化最大延遲巡邏調度;Multi-Robot Patrol-Scheduling with Min-Max Latency on trees

NCU Institutional Repository > 資訊電機學院 > 資訊工程研究所 > 博碩士論文 > Item 987654321/95730

請使用永久網址來引用或連結此文件: http://ir.lib.ncu.edu.tw/handle/987654321/95730

題名:	多機器人在樹結構上最小化最大延遲巡邏調度;Multi-Robot Patrol-Scheduling with Min-Max Latency on trees
作者:	許珮萱;Hsu, Pei-Hsuan
貢獻者:	資訊工程學系
關鍵詞:	持續監控;運動規劃;星形樹結構;Persistent monitoring;Motion Planning;Star-shaped tree
日期:	2024-08-02
上傳時間:	2024-10-09 17:13:13 (UTC+8)
出版者:	國立中央大學
摘要:	我們關注機器人巡邏調度問題，該問題涉及尋找多個機器人反覆訪問一組指定地點的調度計劃。我們將這個問題設定在一個連續的度量空間中。為了更好地應用在現實生活，我們將問題設置在樹結構上，具體來說是一個根狀星形子圖。此外，每個機器人的最大速度相同，每個地點的權重也相同。我們的目標是確定一個最優調度方案，目標是最小化最大延遲L∗。一個地點的延遲L 被定義為連續兩次被機器人拜訪的時間間隔。我們證明了最優的調度策略包括部署一些機器人永久留在地點上，而其他機器人則持續遍歷其他地點，或者讓每個機器人持續巡邏所有地點。此外，我們提出了一個O(nlogn) 算法，用來羅列所有可能的最優延遲並獲得最佳延遲。最優的最小最大延遲是計算星形樹未被配置任何機器人永久停留的葉子總長度除以可移動的機器人數量得出的。;We focus on the patrol scheduling problem, which involves finding schedules for multiple robots to repeatedly visit a given set of sites. We set the problem within a continuous metric space. To better align with real-world applications, the problem is modeled on a tree structure, specifically a rooted star-shaped subgraph. Moreover, each robot has same maximum speed and each site has the same weight. Our objective is to determine the optimal schedule that minimizes the maximum latency L∗. The latency L of a site is defined as the longest interval between consecutive visits to that site. This problem is NP-hard, because it can be reduced to the traveling salesman problem when there is only one robot assigned to traverse all sites, with each site having equal weight. We prove that the optimal scheduling strategy entails deploying some robots to permanently remain at the sites while others continuously traverse other sites, or alternatively, having each robot continuously patrol all sites. Furthermore, we present an O(n log n) algorithm to enumerate all possible optimal latencies and to obtain the optimal one. The optimal min-max latency is calculated by dividing the total length of leaves in a star-shaped tree, where no robots are permanently stationed, by the number of mobile robots.
顯示於類別:	[資訊工程研究所] 博碩士論文

文件中的檔案:

檔案	描述	大小	格式	瀏覽次數
index.html		0Kb	HTML	19	檢視/開啟

在NCUIR中所有的資料項目都受到原著作權保護.

社群 sharing

資料載入中.....