Efficiently Guiding K-Robots Along Pathways with Minimal Turns

Hamid Hoorfar; Nedasadat Taheri; Houman Kosarirad; Alireza Bagheri

doi:10.4108/airo.3492

Authors

Hamid Hoorfar University of Maryland, Baltimore
Nedasadat Taheri University of Nebraska–Lincoln
Houman Kosarirad University of Nebraska–Lincoln
Alireza Bagheri Amirkabir University of Technology

DOI:

https://doi.org/10.4108/airo.3492

Keywords:

robot navigation, watchman robot, guarding, algorithm, motion planning

Abstract

INTRODUCTION: This paper addresses the navigation of a team of k protector robots within pathways, focusing on minimizing the total number of turns. These robots utilize orthogonal routes known as watchman routes, which prioritize finding the shortest path while maintaining visibility of all points in the environment from at least one robot on its designated route. The main objective of this research is to optimize robot navigation by reducing the overall number of turns.
OBJECTIVES: The primary objective of this study is to develop a linear-time algorithm that efficiently processes and determines routes for k robots within a specified area. By minimizing the number of turns, this algorithm aims to enhance the navigation capabilities of watchman robots, enabling them to effectively traverse complex environments.
METHODS: This research employs techniques derived from computational geometry to investigate the navigation of protector robots. The focus is on developing an algorithm that can efficiently process and determine the optimal routes for the robots, considering factors such as visibility and shortest path length. The algorithm is designed to minimize the number of turns while ensuring efficient coverage of the environment.
RESULTS: The main results of this paper include the development of a linear-time algorithm for determining routes for a team of k protector robots. The algorithm efficiently processes the input data and produces separate routes for each robot. By minimizing the number of turns, the algorithm improves the overall navigation efficiency of the robots. The results demonstrate the effectiveness of the algorithm in optimizing robot paths and reducing the complexity of navigation in real-world scenarios.
CONCLUSION: In conclusion, this research contributes to the field of robotic systems by addressing the navigation challenges faced by a team of protector robots. The introduced linear-time algorithm optimizes the routes for k robots, aiming to minimize the total number of turns. The outcomes of this study have significant implications for the advancement of watchman robots, enhancing their coverage and surveillance capabilities in real-world applications. The algorithm’s efficiency and effectiveness in minimizing turns open new opportunities for developing efficient navigation strategies in complex environments.

Downloads

Download data is not yet available.

References

Shahparvari S, Hassanizadeh B, Mohammadi A, Kiani B, Lau KH, Chhetri P, Abbasi B. A decision support system for prioritised COVID-19 two-dosage vaccination allocation and distribution. Transportation Research Part E: Logistics and Transportation Review. 2022 Mar 1;159:102598.

Maydanchi M, Ziaei A, Basiri M, Azad AN, Pouya S, Ziaei M, Haji F, Sargolzaei S. Comparative Study of Decision Tree, AdaBoost, Random Forest, Naïve Bayes, KNN, and Perceptron for Heart Disease Prediction. InSoutheastCon 2023 2023 Apr 1 (pp. 204-208). IEEE.

Toragay O, Silva DF. Fast heuristic approach for control of complex authentication systems. Applied Stochastic Models in Business and Industry. 2021 Jul;37(4):744-66.

Moshtaghi Largani S, Lee S. Efficient Sampling for Big Provenance. InCompanion Proceedings of the ACM Web Conference 2023 2023 Apr 30 (pp. 1508-1511).

Kashgarani H, Kotthoff L. Is algorithm selection worth it? Comparing selecting single algorithms and parallel execution. InAAAI Workshop on Meta-Learning and MetaDL Challenge 2021 Aug 18 (pp. 58-64). PMLR.

Hoorfar H, Fathi F, Moshtaghi Largani S, Bagheri A. Securing Pathways with Orthogonal Robots. The 21st International Conference on Scientific Computing; Las Vegas, USA2023.

Hoorfar H, Moshtaghi Largani S, Rahimi R, Bagheri A. Minimizing Turns inWatchman Robot Navigation: Strategies and Solutions. The 21st International Conference on Scientific Computing; Las Vegas, USA2023.

Hoorfar H, Bagheri A. Minimum hidden guarding of histogram polygons. arXiv preprint arXiv:1708.05815. 2017 Aug 19.

Kazemzadeh F, Safaei AA, MirzarezaeeM, Afsharian S, Kosarirad H. Determination of influential nodes based on the Communities’ structure to maximize influence in social networks. Neurocomputing. 2023 May 14;534:18-28.

Liu Q, Kosarirad H, Meisami S Alnowibet KA Hoshyar AN. An Optimal Scheduling Method in IoT-Fog-Cloud Network Using Combination of Aquila Optimizer and African Vultures Optimization. Processes. 2023 Apr 10;11(4):1162.

Kosarirad H, Ghasempour Nejati M, Saffari A, Khishe M, Mohammadi M. Feature Selection and Training Multilayer Perceptron Neural Networks Using Grasshopper Optimization Algorithm for Design Optimal Classifier of Big Data Sonar. Journal of Sensors. 2022 Nov 14;2022.

Mahmudi F, SoleimaniM,NaderiMH. Some Properties of the Maximal Graph of a Commutative Ring. Southeast Asian Bulletin of Mathematics. 2019 Jul 1;43(4).

Moshayedi AJ, Khan AS, Shuxin Y, Kuan G, Jiandong H, Soleimani M, Razi A. E-Nose design and structures from statistical analysis to application in robotic: a compressive review. EAI Endorsed Transactions on AI and Robotics. 2023 Apr 20;2(1):e1-.

Soleimani M, Mahmudi F, Naderi MH. Some results on the maximal graph of commutative rings. Advanced Studies: Euro-Tbilisi Mathematical Journal. 2023 Mar;16(supp1):21-6.

Gaur A, Sharma A. Maximal graph of a commutative ring. Int. J. Algebra. 2013;7(12):581-8.

Pourghorban A, Dorothy M, Shishika D, Von Moll A, Maity D. Target Defense against Sequentially Arriving Intruders. In2022 IEEE 61st Conference on Decision and Control (CDC) 2022 Dec 6 (pp. 6594-6601). IEEE.

Pourghorban A, Maity D. Target defense against periodically arriving intruders. arXiv preprint arXiv:2303.05577. 2023 Mar 9.

Chin WP, Ntafos S. Shortest watchman routes in simple polygons. Discrete and Computational Geometry. 1991 Mar, 6(1):9-31.

Tan X, Hirata T, Inagaki Y. An incremental algorithm for constructing shortest watchman routes. International

Journal of Computational Geometry and Applications. 1993 Dec;3(04):351-65.

Tan X. A linear-time 2-approximation algorithm for the watchman route problem for simple polygon. Theoretical Computer Science. 2007 Sep 24;384(1):92-103.

Chin WP, Ntafos S. Optimum watchman routes. In Proceedings of the second annual symposium on Computational geometry 1986 Aug 1 (pp. 24-33).

Hoorfar H, Bagheri A. NP-completeness of chromatic orthogonal art gallery problem. The Journal of Supercomputing. 2021 Mar;77(3):3077-109.

Biedl T, Mehrabi S. On r-Guarding Thin Orthogonal Polygons. arXiv preprint arXiv:1604.07100. 2016 Apr 25.

Hoorfar H, Mohades A. Special guards in chromatic art gallery. 31st European Conference on Computational Geometry, 2015. 16

Schuchardt D, Hecker HD. Two NP-Hard Art-Gallery Problems for Ortho-Polygons. Mathematical Logic Quarterly. 1995;41(2):261-7.

Hoorfar H, Bagheri A. Guarding Path Polygons with Orthogonal Visibility. arXiv preprint arXiv:1709.01569. 2017 Sep 5.

Hoorfar H, Bagheri A. A linear-time algorithm for orthogonal watchman route problem with minimum bends. arXiv preprint arXiv:1708.01461. 2017 Aug 4.

Gewali LP. Placing guards inside orthogonal polygons. Information sciences. 1996 Jan 1;88(1-4):1-4.

Hoorfar H, Bagheri A. Geometric Embedding of Path and Cycle Graphs in Pseudo-convex Polygons. arXiv preprint arXiv:1708.01457. 2017 Aug 4.

Hoorfar H, Bagheri A. A New Optimal Algorithm for Computing the Visibility Area of a simple Polygon from a Viewpoint. arXiv preprint arXiv:1803.10184. 2018 Mar 27.

Froncek D, Miller M, Kratochvíl J. Combinatorial Algorithms: 25th International Workshop, IWOCA 2014 Duluth, MN, USA, October 15-17, 2014 Revised Selected Papers. In25th International Workshop on Combinatorial Algorithms, IWOCA 2014 2015. Springer Verlag.