Advancing Robot Perception in Non-Spiral Environments through Camera-based Image Processing
Keywords:robot perception, visibility regions, optimal-time complexity, memory utilization, constant-memory model
Robot perception heavily relies on camera-based visual input for navigating and interacting in its environment. As robots become integral parts of various applications, the need to efficiently compute their visibility regions in complex environments has grown. The key challenge addressed in this paper is to devise an innovative solution that not only accurately computes the visibility region V of a robot operating in a polynomial environment but also optimizes memory utilization to ensure real-time performance and scalability.
The main objective of this research is to propose an algorithm that achieves optimal-time complexity and significantly reduces memory requirements for visibility region computation. By focusing on sub-linear memory utilization, we aim to enhance the robot's ability to perceive its surroundings effectively and efficiently.
Previous approaches have provided solutions for visibility region computation in non-spiral environments, but most were not tailored to memory limitations. In contrast, the proposed algorithm is designed to achieve optimal time complexity that is O(n) while reducing memory usage to O(c/log n) variables, where c < n represents the number of critical corners in the environment. Leveraging the constant-memory model and memory-constrained algorithm, we aim to strike a balance between computational efficiency and memory usage.
The algorithm's performance is rigorously evaluated through extensive simulations and practical experiments. The results demonstrate its linear-time complexity and substantial reduction in memory usage without compromising the accuracy of the visibility region computation. By efficiently handling memory constraints, the robot gains a cost-effective and reliable perception mechanism, making it well-suited for a wide range of real-world applications.
The constant-memory model and memory-constrained algorithm presented in this paper offer a significant advancement in robot perception capabilities. By optimizing the visibility region computation in polynomial environments, our approach contributes to the efficient operation of robots, enhancing their performance and applicability in complex real-world scenarios. The results of this research hold promising potential for future developments in robotics, computer vision, and related fields.
Zare, S, Yazdi, M, Masouleh, M, Zhang, D, Ajami, S, Afkhami Ardekani, A. Experimental study on the control of a suspended cable-driven parallel robot for object tracking purpose. Robotica. 2022; 40(11), 3863-3877.
Ochieze C, Zare S, Sun Y. Wearable upper limb robotics for pervasive health: A review. Progress in Biomedical Engineering. 2023 Mar 23;5(3)
Zare S, Ghanatian M, Yazdi MR, Masouleh MT. Reconstructing 3-D Graphical Model Using an Under- Constrained Cable-Driven Parallel Robot. In 2020 6th
Zare S, Haghighi MS, Yazdi MR, Kalhor A, Masouleh MT. Kinematic analysis of an under-constrained cabledriven robot using neural networks. In2020 28th Iranian Conference on Electrical Engineering (ICEE) 2020 Aug 4 (pp. 1-6). IEEE.
Hoorfar H, Taheri N, Kosarirad H, Bagheri A. Efficiently Guiding K-Robots Along Pathways with Minimal Turns. EAI Endorsed Transactions on AI and Robotics. 2023 Jul 12;2.
Hoorfar H, Kosarirad H, Taheri N, Fathi F, Bagheri A. Concealing Robots in Environments: Enhancing Navigation and Privacy through Stealth Integration. EAI Endorsed Transactions on AI and Robotics. 2023 Jul 31;2.
Joe B, Simpson RB. Corrections to Lee’s visibility polygon algorithm. BIT Numerical Mathematics. 1987 Dec;27(4):458-73.
Asano T, Buchin K, Buchin M, Korman M, Mulzer W, Rote G, Schulz A. Memory-constrained algorithms for simple polygons. Computational Geometry. 2013 Oct 1;46(8):959-69.
Ghosh SK, Shermer TC, Bhattacharya BK, Goswami PP. Computing the maximum clique in the visibility graph of a simple polygon. Journal of Discrete Algorithms. 2007 Sep 1;5(3):524-32.
Toth CD, O’Rourke J, Goodman JE. Handbook of discrete and computational geometry. CRC press; 2017 Nov 22.
Abrahamsen M. Constant-workspace algorithms for visibility problems in the plane. Master’s thesis, University of Copenhagen. 2013.
Barba L, KormanM, Langerman S, Silveira RI. Computing the visibility polygon using few variables. International Symposium on Algorithms and Computation 2011 Dec 5 (pp. 70-79). Berlin, Heidelberg: Springer Berlin Heidelberg.
De M, Maheshwari A, Nandy SC. Space-efficient algorithms for visibility problems in simple polygon. arXiv preprint arXiv:1204.2634. 2012 Apr 12.
Hoorfar H, Mohades A. Special guards in chromatic art gallery. 31st European Conference on Computational Geometry, 2015.
Hoorfar H, Bagheri A. Guarding Path Polygons with Orthogonal Visibility. arXiv preprint arXiv:1709.01569. 2017 Sep 5.
Barba L, KormanM, Langerman S, Silveira RI. Computing a visibility polygon using few variables. Computational geometry. 2014 Oct 1;47(9):918-26.
Asano T, Asano T, Guibas L, Hershberger J, Imai H. Visibility of disjoint polygons. Algorithmica. 1986 Nov;1:49-63.
Hoorfar H, Fathi F, Moshtaghi Largani S, Bagheri A. Securing Pathways with Orthogonal Robots. The 21st International Conference on Scientific Computing, Las Vegas, USA, 2023.
HoorfarH,Moshtaghi Largani S, Rahimi R, Bagheri A. Minimizing Turns inWatchman Robot Navigation: Strategies and Solutions. The 21st International Conference on Scientific Computing, Las Vegas, USA, 2023.
Xu G, Khan AS, Moshayedi AJ, Zhang X, Shuxin Y. The Object Detection, Perspective and Obstacles In Robotic: A Review. EAI Endorsed Transactions on AI and Robotics. 2022 Oct 18;1(1).
Moshayedi AJ, Li J,Sina N, Chen X, Liao L, Gheisari M, Xie X. Simulation and validation of optimized pid controller in agv (automated guided vehicles) model using pso and bas algorithms. Computational Intelligence and Neuroscience. 2022 Nov 14;2022.
Moshayedi AJ, Gharpure DC. Evaluation of bio inspired Mokhtar: Odor localization system. In2017 18th international carpathian control conference (ICCC) 2017 May 28 (pp. 527-532). IEEE.
Moshayedi AJ, Chen ZY, Liao L, Li S. Sunfa Ata Zuyan machine learning models for moon phase detection: algorithm, prototype and performance comparison. TELKOMNIKA (Telecommunication Computing Electronics and Control). 2022 Feb 1;20(1):129-40.
Moshayedi AJ, Hosseinzadeh M, Joshi BP, Emadi Andani M. Recognition System for Ergonomic Mattress and Pillow: Design and Fabrication. IETE Journal of Research. 2023 Jan 10:1-9.
Moshayedi AJ, Gharpure DC. Development of position monitoring system for studying performance of wind tracking algorithms. InROBOTIK 2012; 7th German Conference on Robotics 2012 May 21 (pp. 1-4). VDE.
Mahmudi F, SoleimaniM,NaderiMH. Some Properties of the Maximal Graph of a Commutative Ring. Southeast Asian Bulletin of Mathematics. 2019 Jul 1;43(4).
Hoorfar H, Bagheri A. Geometric Embedding of Path and Cycle Graphs in Pseudo-convex Polygons. arXiv preprint arXiv:1708.01457. 2017 Aug 4.
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.
Hoorfar H, Bagheri A. NP-completeness of chromatic orthogonal art gallery problem. The Journal of Supercomputing. 2021 Mar;77(3):3077-109.
How to Cite
Copyright (c) 2023 Alireza Bagheri, Hamid Hoorfar
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
This is an open access article distributed under the terms of the CC BY-NC-SA 4.0, which permits copying, redistributing, remixing, transformation, and building upon the material in any medium so long as the original work is properly cited.