多機器人在樹結構上最小化最大延遲巡邏調度

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：59

、訪客IP：18.217.189.152

姓名

許珮萱(Pei-Hsuan Hsu) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

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

相關論文

★ PXGen:生成模型的事後可解釋方法	★ 使用時序圖卷積網絡進行環境異常檢測
★ 隨機性巡邏排程對抗具有不同攻擊時長的敵手

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

至系統瀏覽論文 (2027-7-31以後開放)

摘要(中)

我們關注機器人巡邏調度問題，該問題涉及尋找多個機器人反覆訪問一組指定地點的調度計劃。我們將這個問題設定在一個連續的度量空間中。為了更好地應用在現實生活，我們將問題設置在樹結構上，具體來說是一個根狀星形子圖。此外，每個機器人的最大速度相同，每個地點的權重也相同。我們的目標是確定一個最優調度方案，目標是最小化最大延遲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.

關鍵字(中)

★ 持續監控
★ 運動規劃
★ 星形樹結構

關鍵字(英)

★ Persistent monitoring
★ Motion Planning
★ Star-shaped tree

論文目次

1 Introduction 1
2 Related Work 3
3 Problem Definition 6
4 Algorithm 7
5 Conclusion 12
References 13

參考文獻

[1] Christos H Papadimitriou. “The Euclidean travelling salesman problem is NPcomplete”. In: Theoretical computer science 4.3 (1977), pp. 237–244.
[2] Sanjeev Arora. “Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems”. In: Journal of the ACM (JACM) 45.5 (1998), pp. 753–782.
[3] Joseph SB Mitchell. “Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems”. In: SIAM Journal on computing 28.4 (1999), pp. 1298–1309.
[4] Nicos Christofides. “Worst-case analysis of a new heuristic for the travelling salesman problem”. In: Operations Research Forum. Vol. 3. 1. Springer. 2022, p. 20.
[5] Tolga Bektas. “The multiple traveling salesman problem: an overview of formulations and solution procedures”. In: omega 34.3 (2006), pp. 209–219.
[6] Greg N Frederickson, Matthew S Hecht, and Chul E Kim. “Approximation algorithms for some routing problems”. In: 17th annual symposium on foundations of computer science (sfcs 1976). IEEE. 1976, pp. 216–227.
[7] Bruce L Golden and Arjang Assad. “Vehicle routing: methods and studies”. In: STUDIES IN MANAGEMENT SCIENCE AND SYSTEMS; 16 (1988).
[8] George B Dantzig and John H Ramser. “The truck dispatching problem”. In: Management science 6.1 (1959), pp. 80–91.
[9] Olli Br¨aysy and Michel Gendreau. “Vehicle routing problem with time windows, Part I: Route construction and local search algorithms”. In: Transportation science 39.1 (2005), pp. 104–118.
[10] Bruce L Golden, Subramanian Raghavan, and Edward A Wasil. The vehicle routing problem: latest advances and new challenges. Vol. 43. Springer Science & Business Media, 2008.
[11] Paolo Toth and Daniele Vigo. The vehicle routing problem. SIAM, 2002.
[12] Yehuda Elmaliach, Asaf Shiloni, and Gal A Kaminka. “A realistic model of frequencybased multi-robot polyline patrolling”. In: Proceedings of the 7th international joint
conference on Autonomous agents and multiagent systems-Volume 1. Citeseer. 2008, pp. 63–70.
[13] Luca Iocchi, Luca Marchetti, and Daniele Nardi. “Multi-robot patrolling with coordinated behaviours in realistic environments”. In: 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems. IEEE. 2011, pp. 2796–2801.
[14] Hao-Tsung Yang et al. “Patrol scheduling against adversaries with varying attack durations”. In: Proceedings of the 18th International Conference on Autonomous
Agents and MultiAgent Systems. 2019, pp. 1179–1188.
[15] Kin Sum Liu et al. “Joint sensing duty cycle scheduling for heterogeneous coverage guarantee”. In: IEEE INFOCOM 2017-IEEE Conference on Computer Communications. IEEE. 2017, pp. 1–9.
[16] David Portugal et al. “Finding optimal routes for multi-robot patrolling in generic graphs”. In: 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems. IEEE. 2014, pp. 363–369.
[17] Ethan Stump and Nathan Michael. “Multi-robot persistent surveillance planning as a vehicle routing problem”. In: 2011 IEEE international conference on automation science and engineering. IEEE. 2011, pp. 569–575.
[18] Jonathan Las Fargeas et al. “Persistent visitation under revisit constraints”. In: 2013 International Conference on Unmanned Aircraft Systems (ICUAS). IEEE. 2013, pp. 952–957.
[19] Soroush Alamdari, Elaheh Fata, and Stephen L Smith. “Persistent monitoring in discrete environments: Minimizing the maximum weighted latency between observations”. In: The International Journal of Robotics Research 33.1 (2014), pp. 138–154.
[20] Ahmad Bilal Asghar, Stephen L Smith, and Shreyas Sundaram. “Multi-robot routing for persistent monitoring with latency constraints”. In: 2019 American Control Conference (ACC). IEEE. 2019, pp. 2620–2625.
[21] Nir Drucker, Michal Penn, and Ofer Strichman. “Cyclic routing of unmanned aerial vehicles”. In: International Conference on AI and OR Techniques in Constriant Programming for Combinatorial Optimization Problems. Springer. 2016, pp. 125–141.
[22] Hsi-Ming Ho and Jo¨el Ouaknine. “The cyclic-routing UAV problem is PSPACEcomplete”. In: Foundations of Software Science and Computation Structures: 18th International Conference, FOSSACS 2015, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2015, London, UK, April 11-18, 2015, Proceedings 18. Springer. 2015, pp. 328–342.
[23] Nicola Basilico, Nicola Gatti, and Francesco Amigoni. “Patrolling security games: Definition and algorithms for solving large instances with single patroller and single
intruder”. In: Artificial intelligence 184 (2012), pp. 78–123.
[24] Peyman Afshani et al. “Approximation algorithms for multi-robot patrol-scheduling with min-max latency”. In: Algorithmic Foundations of Robotics XIV: Proceedings of
the Fourteenth Workshop on the Algorithmic Foundations of Robotics 14. Springer. 2021, pp. 107–123.
[25] Guy Even et al. “Covering graphs using trees and stars”. In: International Workshop on Randomization and Approximation Techniques in Computer Science. Springer. 2003, pp. 24–35.
[26] Guy Even et al. “Min–max tree covers of graphs”. In: Operations Research Letters 32.4 (2004), pp. 309–315.
[27] M Reza Khani and Mohammad R Salavatipour. “Improved approximation algorithms for the min-max tree cover and bounded tree cover problems”. In: Algorithmica 69.2 (2014), pp. 443–460.
[28] Wenzheng Xu, Weifa Liang, and Xiaola Lin. “Approximation algorithms for minmax cycle cover problems”. In: IEEE Transactions on Computers 64.3 (2013), pp. 600–613.
[29] Ian Sommerville. Software engineering 9th Edition. Pearson, 2017, p. 768. isbn: 978-8543024974.

指導教授

楊晧琮(Hao-Tsung Yang)

審核日期

2024-8-2

推文